Переход от табличной формы задания булевых функций к аналитическим

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

Для получения СДНФ на основе таблицы истинности необходимо :

1) Каждый из входных наборов, на которых булева функция принимает значения 1, представить в виде элементарного произведения (конъюнкции), причем если переменная равна 0, то она входит в конъюнкцию с инверсией, а если 1 - то без инверсии.

2) Полученные элементарные конъюнкции объединяются знаками дизъюнкции.

Для получения СКНФ на основе таблицы истинности необходимо :

1) Каждый из входных наборов, на которых булева функция принимает значения 0, представить в виде элементарной логической суммы (дизъюнкции), причем если переменная равна 1, то она входит в дизъюнкцию с инверсией, а если 0 - то без инверсии.

2) Полученные элементарные дизъюнкции объединяются знаками конъюнкции.

В качестве примера рассмотрим булеву функцию трех переменных,   f (1,3,5,6,7)=1.   Ниже приведены таблица истинности и полученные на ее основе СДНФ и СКНФ.

x1 x2 x3	f (x1, x2, x3)
0   0   0	0
0   0   1	1
0   1   0	0
0   1   1	1
1   0   0	0
1   0   1	1
1   1   0	1
1   1   1	1

СДНФ  

f = 12x3 v 1x2x3 v x12x3 v x1x23 v x1x2x3 ; СКНФ  

f = ( x1 v x2 v x3 )· ( x1 v 2 v x3 )· ( 1 v x2 v x3 ).

Инверсные функции

Так как в булевой алгебре функции принимают только два значения 0 и 1, то существует особый класс функций, являющихся инверсными по отношению к рассматриваемым функциям, т.е. на тех наборах, где данная функция принимает значение 0 (1), инверсная функция принимает значение 1 (0) соответственно.

На основании закона Де-Моргана можно сформулировать правило получения инверсной функции.

Для получения аналитического выражения инверсной функции необходимо в исходной функции все переменные заменить на инверсные им, все знаки дизъюнкции заменить на знаки конъюнкции и наоборот.

Например, для ДНФ   f = x1x2 v x3,   = ( 1 v 2 )· 3 ; Полученную таким образом инверсную функцию называют обратной КНФ.

Для КНФ   f = ( x1 v x3 )· ( x2 v x3 ),   = 13 v 23 ; Полученную таким образом инверсную функцию называют обратной ДНФ.

Минимизация логических функций.

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

Минимизация производится с помощью применения законов склеивания и поглощения.

Пример.

Найти минимальную ДНФ функции Y=f (x1, x2, x3); f (0,2,3,4,5,7)=1.

Решение.

Построим таблицу истинности функции Y.

x1 x2 x3	f (x1, x2, x3)
0   0   0	1
0   0   1	0
0   1   0	1
0   1   1	1
1   0   0	1
1   0   1	1
1   1   0	0
1   1   1	1

По данным таблицы запишем аналитическое выражение:

Y=123 v 1x23 v 1x2x3 v x123 v x12x3 v x1x2x3

Из дискретного анализа известно, что существуют такие формулы представления функции, которые дальше уже нельзя упростить. Они называются сокращенными. Известно также, что не всякая сокращенная форма является минимальной. Однако минимальную по числу переменных следует искать среди сокращенных форм. Переход к сокращенной форме основан на последовательном применении двух операций: операции склеивания и операции поглощения.

Для выполнения операции склеивания в выражении функции выявляются пары членов вида

w x и w ,

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

w xw=w ( x)=w

Результаты склеивания w в выражение функции.

Операция поглощения основана на равенстве

ww z=w(1z)=w

Член w поглощает член wz. При проведении этой операции из логического выражения вычеркиваются все члены, поглощаемые членами, которые введены в результате операции склеивания. Операции склеивания и поглощения выполняются последовательно до тех пор, пока это возможно.

Для получения нормальной минимальной конъюнктивной формы логической функции имеются следующие особенности:

• исходной формой для минимизации логического выражения является СКНФ;

• пары склеиваемых членов имеют вид

w  x и w;

• операция поглощения проводится в соответствии с выражением

z (z  y) = z  zy= z (1y)= z .

Сокращенная форма может содержать лишние члены, исключение которых из выражения не повлияет на значение функции. Дальнейшее упрощение логического выражения достигается исключением из выражения лишних членов. В этом заключается содержание минимизации.

Получим:

Y=1x2 v x2x3 v x1x3 v x12 v 23 v 13

Данная ДФ является избыточной, так как отдельные конъюнкции могут быть лишними, т.е. их составные части могут включаться в другие конъюнкции. У данной функции существует пять безызбыточных ДФ, из которых только две являются минимальными:

Y1=1x2 v x1x3 v 2x3;

Y2=1x2 v x2x3 v x12 v 13;

Y3=1x2 v x1x3 v x12 v 13;

Y4=13 v x2x3 v x12;

Y5=13 v 1x2 v x1x3 v x12.

Их приведенных зависимостей видно, что только функции Y1 и Y4 являются минимальными формами функций, так как они содержат наименьшее число конъюнкций и имеют минимальный ранг этих конъюнкций.