Булевы функции

функции f поскольку р — ее импликанта.

Минимизация по методу Квайна выполняется по следующему алгоитму:

1. Выполняются все склеивания в СДНФ.

2. Выполняются все поглощения.

3. Результирующая функция проверяется на возможность дальнейшего склеивания и поглощения.

4. После получения сокращенной ДНФ строится импликантная матрица, по которой находятся “лишние” импликанты.

Пример. Пусть имеется булева функция, заданная таблицей истинности (табл 9). Ее СДНФ имеет вид:


f= Булевы функцииЪБулевы функцииЪБулевы функцииЪБулевы функцииЪБулевы функцииЪБулевы функции


Для удобства изложения пометим каждую конституенту единицы из СДНФ функции f каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2 ) конституента 2 с конституентой 4 и т. д. В результате получаем:


1-2: Булевы функции

1-3: Булевы функции

2-4: Булевы функции

3-4: Булевы функции

4-6: Булевы функции

5-6: Булевы функции


Заметим, что результатом склеивания является всегда элементарное произведение, представляющее собой общую часть склеиваемых конституент.

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:


Булевы функцииЪБулевы функции=Булевы функцииЪБулевы функцииЪБулевы функции

Булевы функцииЪБулевы функции=Булевы функцииЪБулевы функцииЪБулевы функции


с появлением одного и того же элементарного произведения Булевы функции. Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:


Булевы функцииЪБулевы функцииЪБулевы функции


Переходим к следующему этапу. Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простые импликанты. Это делается с помощью специальной импликантной матрицы Квайна. Строки такой матрицы отмечаются простыми импликантами булевой функции, т. е. членами сокращенной ДНФ, а столбцы — конституентами единицы, т. е. членами СДНФ булевой функции.

Пример (продолжение). Импликантная матрица имеет вид (табл. 10).


Таблица 10.

Простые Конституенты единицы
импликанты

Булевы функции

Булевы функции

Булевы функции

Булевы функции

Булевы функции

Булевы функции

Булевы функции

Х Х Х Х

Булевы функции




Х
Х

Булевы функции





Х Х

Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной матрицы на пересечении строки (с рассматриваемой простой импликантой) и столбца (с конституентой единицы) отмечается крестиком (табл. 10). Минимальные ДНФ строятся по импликантной матрице следующим образом:

1) ищутся столбцы импликантной матрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными и составляют так называемое ядро булевой функции. Ядро обязательно входит в минимальную ДНФ.

2) рассматриваются различные варианты выбора совокупности простых импликант, которые накроют крестиками остальные столбцы импликантной матрицы, и выбираются варианты с минимальным суммарным числом букв в такой совокупности импликант.

Пример (продолжение). Ядром нашей функции являются импликанты Булевы функции и Булевы функции. Импликанта Булевы функции - лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ:

fmin=Булевы функцииЪБулевы функции

Следует отметить, что число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что N = 2n-k, где k — число букв, содержащихся в простой импликанте.

Заметим также, что используя различные соотношения, можно расширить область применения метода Квайна за пределы совершенной ДНФ.


7.2 Метод Квайна-Мак-Класки


Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Формализация производится следующим образом:

1. Все конституенты единицы из СДНФ булевой функции f записываются их двоичными номерами.

2. Все номера разбиваются на непересекающиеся группы. Признак образования і-й группы: і единиц в каждом двоичном номере конституенты единицы.

3. Склеивание производят только между номерами соседних групп. Склеиваемые номера отмечаются каким-либо знаком (зачеркиванием, звездочкой и т.д.).

4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Нахождение минимальных ДНФ далее производится по импликантной матрице, как и в методе Квайна. Более подробно рассмотрим метод на примере решения следующей задачи: минимизировать методом Квайна-Мак-Класки булеву функцию f, заданную таблицей истинности (табл. 9).

1. В СДНФ функции f заменим все конституенты единицы их двоичными номерами: f=0001Ъ0011Ъ0101Ъ0111Ъ1110Ъ1111

2. Образуем группы двоичных номеров. Признаком образования і-й группы является і единиц в двоичном номере конституенты единицы (табл.11).

3. Склеим номера из соседних групп табл.11. Склеиваемые номера обозначим звездочками (номер отмечается в том случае, если участвует в склеивании хотя бы один раз). На месте разрядов, по которым произошло склеивание, проставляются прочерки. Результаты склеивания занесем в табл. 12. Склеим номера из соседних групп табл. 12. Склеиваться могут только номера, имеющие прочерки в одинаковых позициях. Склеиваемые номера отметим. Результаты склеивания занесем в табл. 13.

4. Имеем три простые импликанты: -111, 111-, 0--1.


Таблица 11 Таблица 12 Таблица 13

Номер группы Двоичные номера кон-ституент 1

Номер

группы

Двоичные номера

импликант


Номер

группы

Двоичные номера

импликант

0 -
1 (1-2) 00-1 *
1 0--1
1 0001 *

0-01 *

0--1
2 0011 *
2 (2-3) 0-11 *
2 -111

0101 *

01-1 *

111-
3 0111 *
3 (3-4) -111



1110 *

111-


4 1111 *





Таблица 14

Простые Конституенты единицы
импликанты

Булевы функции

Булевы функции

Булевы функции

Булевы функции

Булевы функции

Булевы функции

Булевы функции(0--1)

Х Х Х Х

Булевы функции(-111)




Х
Х

Булевы функции(111-)





Х Х

5. Строим импликантную матрицу (табл. 14). По таблице определяем совокупность простых импликант - 0--1 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам:

fmin=Булевы функцииЪБулевы функции

Заметим, что разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании.


7.3 Метод диаграмм Вейча


Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (табл. 15). Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. В табл.15. это соответствие показано. В клетке диаграммы Вейча ставится единица, если булева функция принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид (табл. 16). Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (табл. 17). Таким же образом, т. е. приписыванием еще одной диаграммы 4-х переменных, к только что рассмотренной, можно получить диаграмму для функции 5-ти переменных и т. д., однако диаграммы для функций с числом переменных больше 4-х используются редко.

Для приведенных диаграмм характерно следующее:

каждой клетке диаграммы соответствует свой набор;


Таблица 15. Таблица 16.


Булевы функции

Булевы функции



Булевы функции

Булевы функции


Булевы функции

11 01

Булевы функции

110 111 011 010

Булевы функции

10 00

Булевы функции

100 101 001 000





Булевы функции

Булевы функции

Булевы функции



Таблица 17. Таблица 18.


Булевы функции

Булевы функции




х1

Булевы функции

х1 1100 1101 1001 1000

Булевы функции


Булевы функции

1 1
1
х1 1110 1111 1011 1010 х3

Булевы функции




1

Булевы функции

0110 0111 0011 0010 х3

Булевы функции

Булевы функции

Булевы функции

Булевы функции

0100 0101 0001 0000

Булевы функции








Булевы функции

х4 х4

Булевы функции









2) соседние наборы расположены рядом в строке либо в столбце. Соседними наборами называются наборы, отличающиеся одной компонентой. Напомним, что конституенты, соответствующие таким наборам, склеиваются (см. метод Квайна-Мак-Класки). Например, для функции, заданной табл. 18, конституенты, соответствующие паре единиц в левой части таблицы, склеиваются и порождают элементарное произведение из двух букв:


Булевы функцииБулевы функции=Булевы функции


О паре единиц в правой части диаграммы можно сказать то же самое: Булевы функцииБулевы функции=Булевы функции.


Отметим, что получающееся элементарное произведение легко определить сразу по диаграмме: это произведение переменных, принимающих одно и то же значение в обеих клетках.

Еще одно важное замечание: столбцы, расположенные по краям диаграммы, тоже считаются соседними. Для нашего примера это означает, что имеет место еще одно склеивание, в результате которого, следуя указанному правилу, получаем элементарное произведение Булевы функции. Из рассмотренных ранее методов нам известно, что возможно дальнейшее склеивание получаемых элементарных произведений. На диаграммах Вейча они тоже располагаются рядом. Общее правило склеивания на диаграммах Вейча можно сформулировать следующим образом: склеиванию подлежат прямоугольные конфигурации, заполненные единицами и содержащие число клеток, являющееся степенью 2. Получающееся новое элементарное произведение определяется как произведение переменных, не меняющих своего значения на всех склеиваемых наборах. Число m оставшихся переменных в элементарном произведении определяется легко:

m=n-log2M,

где n- число переменных,

M - число склеиваемых наборов.

Метод широко используется на практике, благодаря простоте и удобству. После небольшой тренировки достигается элементарный навык определения минимальной ДНФ по диаграмме «с первого взгляда».

Минимизация булевой функции заключается в нахождении минимального покрытия всех единиц диаграммы Вейча блоками из единиц (указанной конфигурации), расположенных в соседних клетках диаграммы. При этом всегда считается, что левый край диаграммы Вейча 4-х переменных примыкает к ее правому краю, а верхний край диаграммы примыкает к нижнему ее краю. Для удобства можно предположить, что диаграмма сворачивается в цилиндр как по горизонтали, так и по вертикали. После получения минимального покрытия всех единиц диаграммы Вейча, минимальная ДНФ булевой функции записывается как дизъюнкция элементарных конъюнкций, соответствующих выделенным блокам единиц в диаграмме.

В диаграмме Вейча необходимо и достаточно, чтобы каждая единичная клетка участвовала в склейке хотя бы один раз.

Новую склейку можно образовывать в том случае, если есть хотя бы одна единичная клетка, не участвовавшая до этого в склейке.

Вся диаграмма должна быть покрыта наименьшим количеством склеек. В склейку может входить 2n соседних клеток (2, 4, 8, 16. и т.д.).

Рассмотрим несколько примеров.


Таблица 19 Таблица 20

Булевы функцииБулевы функцииБулевы функцииБулевы функции Булевы функции X4 X3

Булевы функции

Булевы функции

Булевы функции



Булевы функции

Булевы функции






Булевы функциих1





Булевы функции

х1
1 1

Булевы функции





х1 1 1

х3 х1 1 1 1 1 х3



Булевы функцииБулевы функции


1 1
х3

Булевы функцииБулевы функции

1 1 1 1 х3



Булевы функции


1 1

Булевы функции

Булевы функции


1 1

Булевы функции






Булевы функции

х4 х4

Булевы функции



Булевы функции

х4 х4

Булевы функции






















f1=Булевы функцииvБулевы функции f2= X4 v X3


7.4 Карты Карно


Иногда удобно пользоваться несколько другим представлением диаграмм с цифровым кодом. Это карты Карно. Примеры карт Карно приведены на рисунке 2. По граням карты проставляются двоичные коды - коды Грея, что дает возможность легко проставлять значения функции и находить результат. Правила минимизации с применение карт Карно такие же, как и для диаграмм Вейча.

Булевы функцииБулевы функции

х2х3

х1

00 01 11 10

х3х4

х1х2

00 01 11 10
0 000 001 011 010
00 0000 0001 0011 0010
1 100 101 111 110
01 0100 0101 0111 0110






11 1100 1101 1111 1110






10 1000 1001 1011 1010

а)






б)

Рисунок 2- Карты Карно:

а) функции 3-х переменных;

б) функции 4-х переменных.


8.Особенности минимизации булевых функций большим числом переменных


Рассмотрим некоторые особенности работы с картами Карно для большого числа переменных. При числе переменных, равном или больше пяти, отобразить графически функцию в виде единой плоской карты невозможно. В таких случаях строят комбинированную карту, состоящую из совокупности более простых базовых карт, например карт для функции 4-х переменных. Процедура минимизации в этом случае состоит в том, что сначала находят минимальные формы внутри базовых карт, а затем, расширяя понятия соседних клеток, находят минимальные накрытия для совокупности карт. Соседними клетками являются клетки, совпадающие при наложении базовых карт друг на друга. Примеры карт Карно для булевых функций 5-ти и 6-ти переменных представлены на рис. 3 и 4. соответственно.


Булевы функцииРисунок 3-Карта Карно для булевой функции 5-ти переменных

Булевы функциих3х4

х1х2

00 01 11 10 00 01 11 10
00








01








11








10










х5=0


х5=1

Рисунок 4- Карта Карно для булевой функции шести переменных

х3х4

х1х2

00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10
00
















01
















Булевы функции11


















10


(1)


(2)


(3)


(4)

Булевы функциих5х6


00


01


11


10



По рисунку 4 можно сделать вывод, что соседними являются для 1-й базовой карты - 2-я и 4-я; для 2-й - 1-я и 3-я; для 3-й 2-я и 4-я; для 4-й - 1-я и 3-я.

При увеличении количества переменных на одну, площадь карты увеличивается в два раза - к ней пририсовывается еще такая же карта. При этом новая переменная равняется 1 на новой карте, и 0 на той, которая была ранее.


9.Минимизация конъюнктивных нормальных форм


Минимизация КНФ производится аналогично рассмотренным методам минимизации ДНФ булевых функций, поэтому остановимся лишь на основных положениях.

Напомним, что конституентой нуля называется функция, принимающая значение 0 на одном наборе. Она выражается дизъюнкцией всех переменных функций. Например, набору 0110 соответствует конституента нуля X1 vБулевы функции v Булевы функции v X4

Определение. Имплицентой g булевой функции f называется функция, принимающая значение 0 на подмножестве нулевых наборов функции f.

Определение. Простой имплицентой функции f называется элементарная дизъюнкция, являющаяся имплицентой функции f, причем никакая ее собственная часть имплицентой функции f не является.

Задачей, минимизации КНФ является определение минимальной КНФ. Эта задача также решается в два этапа— поиск сокращенной КНФ (конъюнкция всех простых имплицент) и затем нахождение минимальной КНФ. Второй этап минимизации выполняется с помощью таблицы Квайна точно так же, как при поиске минимальной ДНФ, так как возможны только два варианта: либо данная простая имплицента поглощает данную конституенту нуля, либо нет в соответствии с соотношением поглощения: (A v x)A=A

Что касается первого этапа — поиска всех простых имплицент, то практически все методы минимизации ДНФ имеют свои аналоги для КНФ. Расссмотрим это подробнее.

Соотношение склеивания по Квайну:


(A v x) (A v

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: