назад

2.3 Совершенные нормальные формы

Дизъюнктивные нормальные формы

Важным примером эквивалентности является разложение булевой функции по переменной - представление функции Z = ƒ(X1, X2, ...,Xn) в виде
ƒ(X1, X2, ...,Xn) = ┐X1 ƒ(0, X2, ...,Xn) X1 ƒ(1, X2, ...,Xn).

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

Функции (n-1} переменных ƒ (0, X2, ...,Xn) и ƒ(1, X2, ...,Xn) имеют в качестве столбцов значений соответственно верхнюю и нижнюю половины столбца значений ƒ(X1, X2, ...,Xn).

Например, функция m3(X,Y,Z) , имеющая столбец значений [00010111]T , при разложении по первой переменной может быть представлена: m3(X,Y,Z) = ┐X[0001]T X[0111]T, и поскольку [0001]T - таблица для конъюнкции, а [0111]T - для дизъюнкции, то
m3(X,Y,Z) = ┐X∙(YZ) X∙(Y Z)= ┐XYZ XY XZ .

В каждом из слагаемых функции от переменных X2,...,Xn могут быть таким же образом разложены по переменному Х2 и т.д.

Примеры

1) Для функции одной переменной ƒ(X) разложение имеет вид ƒ(X) = ┐X∙ƒ(0) X∙ƒ{1} . Обозначим α=ƒ(0), β=ƒ(1). Тогда ƒ(X)=α∙X β∙X; α и β- константы, равные значениям функции ƒ при Х=0,1 . В этих обозначениях таблица функции ƒ(Х) есть [α,β]Т.

2) Для функции 3 переменных ƒ(X,Y,Z) разложение по переменной Х дает:

ƒ(X, Y, Z) = ┐X∙ƒ(0, Y, Z) X∙ƒ(1, Y, Z).
Далее, обозначая ƒ(0, Y, Z) через g0(Y, Z), a ƒ(1, Y, Z) - через g1(Y,Z) , разложим их по переменной Y :

ƒ(0, Y, Z) =g1(Y, Z) = ┐Y∙g0(0,Z) Y∙g1(l,Z) = ┐Y∙ƒ(0, 0, Z) Y∙ƒ(0, 1, Z);
      ƒ(1, Y, Z) =g1(Y, Z) = ┐Y∙g1(0,Z) Y∙g1(l,Z) = ┐Y∙ƒ(l, 0, Z) Y∙ƒ(1, 1, Z).

Тем самым, получаем разложение исходной функции на 4 логических слагаемых:
       ƒ(X, Y, Z) = ┐Х∙(Y∙g0(0, Z) Y∙g0(l, Z)) X∙┐Y∙g0(0, Z)
       X∙┐Y∙g1(0, Z) Y∙ g1(1, Z)) = [раскрывая скобки] =
      = ┐X∙┐Y∙g0(0, Z) ┐X∙Y∙g0(l, Z) X∙┐Y∙ g1(0, Z) X∙Y∙g1(l, Z).

Далее, вводя новые обозначения, h00 = g0(0, Z); h01 = g0(l, Z); h10 =g1(0, Z); h11 = g1(l, Z) , разложим эти 4 функции по их единственной переменной Z :

h00(Z) = ┐Z∙h00(0) Z∙h00(1) = ┐Z∙ƒ(0, 0, 0) Z∙ƒ(0, 0, 1);
      h01(Z) = ┐Z∙h01(0) Z∙h01(1) = ┐Z∙ƒ(0, 1, 0) Z∙ƒ(0, 1, 1);
      h10(Z) = ┐Z∙h10(0) Z∙h10(1) = ┐Z∙ƒ(1, 0, 0) Z∙ƒ(1, 0, 1);
      h11(Z) = ┐Z∙h11(0) Z∙h11(1) = ┐Z∙ƒ(1, 1, 0) Z∙ƒ(1, 1, 1).

Окончательно подставляя эти выражения в предыдущую формулу и раскрывая скобки, получаем разложение ƒ{X, Y, Z) по всем трем переменным в виде дизъюнкции 8 логических слагаемых:

ƒ(X, Y, Z) = ┐X┐Y┐Zƒ(0, 0, 0) ┐X┐YZƒ(0, 0, 1)
       ┐XY┐Zƒ(0, 1, 0) ┐XYZƒ(0, 1, 1) X┐Y┐Zƒ(1, 0, 0)
       X┐YZƒ(1, 0, 1) XY┐Zƒ(1, 1, 0) XYZƒ(1, 1, 1).

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

Элементарная конъюнкция - конъюнкция нескольких переменных и их отрицаний, в которую каждая переменная входит не более одного раза. Примеры элементарных конъюнкций: Х , ┐XY , ┐X┐Y , X┐ZS┐T , YZT . Формулы ┐XZX и XZX не являются элементарными конъюнкциями: первая содержит одновременно переменную X и ее отрицание, во вторую переменная Х входит дважды.

Для дальнейшего введем удобное обозначение: Х σ - форма записи функции Х σ , где Х - переменная, а σ - двоичный параметр. Рассмотрим подробнее: если подставить константу вместо обеих переменных, получим равенства: 01 = 0; 00 = 0; 11 = 1; 10 = 0; подстановка констант вместо Х дает:

0σ = ┐σ; 1σ = σ наконец, при подстановке констант вместо σ получаем Х0 = ┐Х, Х1 = Х.

Приведенные выше примеры элементарных конъюнкций можно в новых обозначениях записать так:

X =Х1; ┐XY = X0Y1; ┐X┐Y = X0Y0; X┐ZS┐T = X1Z0S1T0 и т. п.

Элементарная конъюнкция, соответствующая набору =(σ1, σ2,:,σ3) - конъюнкция Х1σ1 & Х2σ2 & :& Хnσn. Для n-мерного набора конъюнкция содержит ровно n множителей с отрицаниями или без них. Как функция n переменных она принимает значение 1 только на наборе (σ1, σ2,:,σn)

Используя введенные обозначения, можно записать предыдущее разложение функции ƒ(X,Y,Z) по-другому:
ƒ(X,Y,Z) = V Xσ1 Yσ2 Zσ3ƒ(σ1, σ2,σ3)
         σ1,σ2,σ3=0,1

Теперь можно удалить из этой логической суммы те слагаемые, для которых ƒ(σ1, σ23) = 0 (пользуясь свойствами 16 и 15). Логическую сумму оставшихся членов можно записать так:

ƒ(X,Y,Z) = V Xσ1 Yσ2 Zσ3, или короче: Vƒ(σ1,σ2,σ3)=1 Xσ1 Yσ2 Zσ3
      {σ1,σ2,σ3 : ƒ(σ1,σ2,σ3)=1}

Имеется в виду, что в логической сумме участвуют только те элементарные конъюнкции, которые соответствуют наборам констант (σ1, σ23), для которых ƒ(σ1, σ23) = 1.

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

Совершенная дизъюнктивная нормальная форма (СДНФ) - представление функции Z = ƒ(X1, X2,:,Xn) в виде дизъюнкции всех элементарных конъюнкций, соответствующих наборам значений σ1, σ2,:,σn на которых Z = 1 :

ƒ(X1, X2,:,Xn) = V X1σ1 X2σ2 : Xnσn
                        ƒ(σ123)=1

СДНФ содержит ровно столько n -членных элементарных конъюнкций, сколько единиц в столбце значений функции ƒ(X1, X2,:,Xn). На каждом из 2n наборов либо все логические слагаемые СДНФ обращаются в 0 (если функция ƒ на этом наборе равна 0), либо ровно одна конъюнкция обращается в 1 (если ƒ равна 1). Не имеет СДНФ единственная функция - тождественно равная нулю (константа 0).

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

Примеры

1) Выражения
X Y = ┐XY X┐Y,
X Y = ┐X┐Y XY,
X Y =┐X┐Y ┐XY XY,
X |Y = ┐X┐Y ┐XY X┐Y суть СДНФ этих функций; a X Y = ┐X Y, X | Y = ┐X ┐Y не СДНФ.

2) СДНФ для функции большинства m3(X, Y, Z) содержит 4 элементарные конъюнкции:
      m3(X, Y, Z) = ┐XYZ X┐YZ XY┐Z XYZ .

3) СДНФ для функции 4 переменных g(X, Y, Z, T) со столбцом значений [0100100100011001]T содержит 6 элементарных конъюнкций
      g(X, Y, Z, Т) = ┐X┐Y┐ZT ┐XY┐Z┐T ┐XYZ┐T X┐YZT XY┐ZT XYZT

Совершенная дизъюнктивная нормальная форма является частным случаем более общего вида формул.

Дизъюнктивная нормальная форма (ДНФ) - дизъюнкция нескольких элементарных конъюнкций. Подчеркнем, что ДНФ - это не всякая формула, выражающая функцию через операции конъюнкции, дизъюнкции и отрицания: например, X∙(┐Y Z) - не ДНФ; однако ее можно привести к ДНФ, раскрывая скобки: Х∙┐Y Х∙Z .

Используя некоторые из эквивалентностей, прежде всего, 1-6, можно выносить за скобки общие множители, а применяя равенства 7-10, 13-18, а также приемы склеивания, упрощать формулы, поскольку, как уже отмечалось, в этих равенствах правые части короче левых.

Примеры
       1) Докажем тождество:
X∙(X1) = 0. X∙(X1)=[раскрываем скобки]=X∙XX)=[устраняем кратность]=XX=0.

2) Докажем тождество:
YZ=┐Z┐Y. Преобразуем обе части равенства, выражая импликацию через дизъюнкцию: AB┐AB; получаем: ┐Y┐Z=┐(┐Z)┐Y=[снимаем двойное отрицание]=Z┐Y. Равенство доказано, поскольку дизъюнкция - коммутативная операция.

3) Упростить формулу ƒ = ┐X∙Y∙┐Z X∙┐Z.
Выносим за скобки общий множитель: ƒ=┐Z∙(┐X∙YX)=┐Z∙(XY).

 

Вопросы для самоконтроля

  1. Дайте определение элементарной конъюнкции, СДНФ, ДНФ.
  2. Сформулируйте определение элементарной дизъюнкции, СКНФ, КНФ.
  3. Приведите примеры представления функции СДНФ, СКНФ.
  4. Дайте определение дизъюктивного терма, конъюктивного терма.
  5. Сформулируйте определения НДФ, ДНФ, КНФ.
  6. Приведите примеры преобразования функции к ДНФ и КНФ.

Практические задания

Tест для самоконтроля