Важным примером эквивалентности является разложение булевой
функции по переменной - представление функции 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, σ2,σ3) = 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, σ2,σ3), для которых ƒ(σ1, σ2,σ3) = 1.
Подобное представление возможно для любой булевой функции, и мы приходим к важному понятию.
Совершенная дизъюнктивная нормальная форма (СДНФ) - представление функции Z = ƒ(X1, X2,:,Xn) в виде дизъюнкции всех элементарных конъюнкций, соответствующих наборам значений σ1, σ2,:,σn на которых Z = 1 :
ƒ(X1, X2,:,Xn) = V X1σ1 X2σ2 : Xnσn
ƒ(σ1,σ2,σ3)=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, а также приемы склеивания, упрощать формулы, поскольку, как уже отмечалось, в этих равенствах правые части короче левых.
2) Докажем тождество:
YZ=┐Z
┐Y.
Преобразуем обе части равенства, выражая импликацию через
дизъюнкцию: A
B┐A
B;
получаем: ┐Y
┐Z=┐(┐Z)
┐Y=[снимаем
двойное отрицание]=Z
┐Y. Равенство доказано, поскольку дизъюнкция - коммутативная операция.
3) Упростить формулу ƒ = ┐X∙Y∙┐Z X∙┐Z.
Выносим за скобки общий множитель: ƒ=┐Z∙(┐X∙YX)=┐Z∙(X
Y).
![]() |
Практические задания |
![]() |
Tест для самоконтроля |