Bulevy_funktsii_Normalnye_formy_algebry_logiki

33

По условию нам дано (F = G).Поэтому, в силу критерия равносильности по ОЛ, имеем: ОЛ(F) = ОЛ(G). Если ОЛ(F) = ОЛ(G) = , то F=G=1.Если же ОЛ(F) = ОЛ(G) ≠, то СКНФ(F) = СКНФ(G), поскольку, в силу теоремы существования, СКНФ(f )

однозначно определяется областью ложности f. Необходимость доказана. б) Достаточность.

(F=1 G=1) (СКНФ(F) = СКНФ(G)) (F = G).

Если (F=1 G=1), то (F=1=G) и все доказано. Если же (СКНФ(F) = СКНФ(G)),

то

F = СКНФ(F) = СКНФ(G) = G.И в этом случае все доказано.

Итак, мы познакомились со второй разновидностью нормальных форм алгебры логики (теории булевых функций), а именно с КНФ и ее совершенным видом – СКНФ. Отметим еще раз применения этих нормальных форм.

Применения конъюнктивной нормальной формы (КНФ): − критерий тождественной ложности по КНФ:

F = 0 КНФ( F ) = 1;

− критерий тождественной истинности по КНФ:

F = 1 КНФ(F) = 1;

−построение таблиц формул по их КНФ;

−КНФ(F) − промежуточный этап построения СКНФ(F).

Применения совершенной конъюнктивной нормальной формы (СКНФ): − критерий равносильности по СКНФ:

(F = G) (F=1 G=1) (СКНФ(F) = СКНФ(G));

−СКНФ применяется для аналитического задания опровержимой булевой функции по ее таблице;

−по СКНФ( f ) легко восстанавливается таблица f

5.Многочлен Жегалкина.

Сумма по модулю два,ее свойства.

			def
	По определению:	x y		x y .
	Свойства: (5.1) х + у = у + х;
	(5.2)	(х + у) + z = x +(y + z);
	(5.3) x(y + z) = xy + xz;
	(5.4)	х + х = 0;

34

(5.5) x + 0 = x;

(5.6) x + 1 = x ;

Любой из приведенных выше законов может быть доказан с помощью таблиц Квайна или с использованием критериев равносильности на основании совершенных ДНФ или КНФ.

Определение 5.1. Многочленом Жегалкина от n переменных x1, x2 ,..., xn (нормальной формой Жегалкина (НФЖ)) называется сумма по модулю два

ai1i2 ...ik xi1 xi2 xik = a0 a1x1 a2 x2 an xn a12x1x2 a13x1x3 an 1 n xn 1xn

{i1 ,i2, ...,ik } {1,2,...,n}

+ a123x1x2 x3 a124x1x2 x4 an 2 n 1 n xn 2 xn 1xn a12...n x1x2 xn

(в которой каждое слагаемое представляет собой конъюнкцию некоторых переменных с двоичным коэффициентом,индекс которого определяется множеством индексов переменных,входящих в конъюнкцию), берущаяся по всем без исключения подмножествам {i1,i2 ,...,ik } множества индексов {1,2,..., n} .

Пример 5.1. Общий вид многочлена Жегалкина от трех переменных x1, x2 , x3 :

f (x1, x2 , x3 ) = a0 a1x1 a2 x2 a3 x3 a12x1x2 a13x1x3 a23x2 x3 a123x1x2 x3 .

Определение 5.2. НФЖ,равносильная данной формуле f ,называется НФЖ для данной формулы и обозначается НФЖ(f ), т.е.:

НФЖ = НФЖ(f ) def НФЖ = f.

Теорема 5.1. Для всякой формулы (булевой функции) существует и притом единственный ее многочлен Жегалкина,т.е.:

( f ФАВ)( !НФЖ)[НФЖ НФЖ( f )].

Доказательство. Пусть исходная функция зависит от n переменных, т.е.					f P(n) .
						2
Каждый многочлен Жегалкина от n переменных однозначно определяется
двоичным набором своих коэффициентов (a , a ,..., a , a ,..., a		n 1 n	, a ,..., a			) B2n .
0 1	n 12		123	12...n

Таким образом, существует │ B2n │= 22n различных многочленов Жегалкина от n переменных, т.е. ровно столько, сколько существует различных булевых функций от n переменных. Многочлен Жегалкина, как всякая формула АВ, имеет некоторую таблицу. Эту таблицу можно рассматривать, как таблицу некоторой БФ. Пусть M (n) − множество различных многочленов Жегалкина от n переменных. Установим соответствие : P2(n) M (n) , сопоставив каждой булевой функции от n переменных

многочлен Жегалкина от n переменных так, что их таблицы совпадают. Легко убедиться (проделать это!), что это соответствие является биективным отображением. Тем самым, теорема доказана.

Рассмотрим методы построения НФЖ(f ).

35

1).Построение НФЖ(f ) по таблице f.

Рассмотрим этот метод на конкретном примере, из которого будет следовать алгоритм построения НФЖ(f ) по таблице f в общем случае.

Пример 5.2. Построить многочлен Жегалкина булевой функции, заданной своей таблицей: f : 10001101.

Решение. Заметим, прежде всего, что исходная функция зависит от трех переменных, т.к. таблица функции содержит восемь значений. Пусть f = f (x,y,z). Запишем НФЖ(f ) от указанных переменных пока еще с неопределенными коэффициентами:

f (x, y, z) = a0 a1x a2 y a3 z a12xy a13xz a23 yz a123xyz .

Теперь, для определения коэффициентов, воспользуемся тем, что таблица БФ известна, т. е. известны значения НФЖ(f ) на каждом наборе значений переменных. Подставим последовательно в выражение НФЖ значения наборов переменных, увеличивая на каждом шаге количество единиц в записи наборов, и учтем значения БФ на этих наборах. Рассмотрим сначала набор, в записи которого нет единиц. Имеем:

f (0,0,0) = a0 a1 0 a2 0 a3 0 a12 00 a1300 a2300 a123000 = 1.

Тогда, учитывая свойства сложения по модулю два, получим:

f (0,0,0) = а0 = 1.

Тем самым, первый коэффициент многочлена Жегалкина a0 найден ( a0 = 1) и исходное выражение НФЖ(f ) принимает вид:

f (x, y, z) = 1 a1x a2 y a3 z a12xy a13xz a23 yz a123xyz .

Далее последовательно используем наборы, в записи которых присутствует одна единица (причем эта единица будет занимать последовательно места в записи наборов, начиная с первого). Имеем:

f (1,0,0) = a0 a11 a2 0 a3 0 a1210 a1310 a2300 a123100 = a0 a1 = 1 a1 = 1.

Откуда:	а1 = 0.
f (0,1,0) = a0 a10 a21 a3 0 a1201 a1300 a2310 a123010 = a0 a2		= 1 a2 = 0.
Откуда:	а2 = 1.

f (0,0,1) = a0 a10 a2 0 a31 a1200 a1301 a2300 a123001 = a0 a31 = 1 a3 = 0.

Откуда: а3 = 1. Таким образом:

f (x, y, z) = 1 0x 1y 1z a12xy a13xz a23 yz a123xyz .

Теперь используем наборы, в записи которых присутствуют две единицы. Имеем:

	36
f (1,1,0) = a0 a11 a21 a3 0 a1211 a1310 a2310 a123110 = a0		a1	a2	a12 =
	= 1+0+1+а12 = 0.
Откуда:	а12 = 0.
f (1,0,1) = a0 a11 a2 0 a31 a1210 a1311 a2301 a123101 = a0 a1 a3 а13 =
	= 1 0 1 а13 = 1.
Откуда:	а13 = 1.
f (0,1,1) = a0 a1 0 a21 a31 a12 01 a1301 a2311 a123011 = a0		a2	a3	a23 =
	= 1 1 1 a23 = 0.
Откуда:	а23 = 1.
Таким образом: f (x, y, z) = 1 0x 1y 1z 0xy 1xz 1yz a123xyz .

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

	f (1,1,1)	= a0 a11 a21 a31 a1211 a1311 a2311 a123111 =
a0 a1 a2		a3 a12 a13 a23 a123 = 1 0 1 1 0 1 1 a123 =		1 a123 = 1.
Откуда:	а123 = 0.
Таким образом: f (x, y, z) = 1 0x 1y 1z 0xy 1xz 1yz 0xyz			= 1 y z xz yz .
Ответ.	f (x, y, z) = НФЖ(f ) = 1 y z xz yz .

Замечание 5.1. Проведенные вычисления коэффициентов многочлена Жегалкина удобнее оформлять с помощью таблицы:

x	y	z	f	соотношения	коэффициенты
0	0	0	1	= а0	а0 = 1
0	0	1	0	= а0 +а3	а3 = 1
0	1	0	0	= а0 + а2	а2 = 1
0	1	1	0	= а0 + а2 + а3 + а23	а23 = 1
1	0	0	1	= а0 + а1	а1 = 0
1	0	1	1	= а0 + а1+ а3 + а13	а13 = 1
о	1	0	0	= а0+а1+а2+а12	а12 = 0
1	1	1	1	= а0+а1+а2+а3+а12+а13+а23+а123	а123 = 0

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

37

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

а0,а1,а3,а13.

2).Построение НФЖ(f ) аналитически,с использованием НФЖ основных БФ f.

Рассмотрим сначала НФЖ основных БФ. Для булевых функций от одной переменной их многочлены Жегалкина следующие:

(5.7) х = НФЖ(х);

(5.8) x 1 x НФЖ(x);

(5.9) 0 = НФЖ(0);

(5.10) 1 = НФЖ(1).

Для булевых функций от двух переменных имеем:

(5.11) ху =НФЖ( ху);

(5.12) xy x / y 1 xy НФЖ(xy) НФЖ(x / y) ;

(5.13) x y x y 1 x y 1 (1 x)(1 y) 1 1 x y xy x y xy НФЖ(x y) ;

(5.14) x y x y 1 (x y) 1 x y xy НФЖ(x y) НФЖ(x y) ;

(5.15) x y x y x y xy 1 x y (1 x) y 1 x xy НФЖ(x y) ;

(5.16) x y 1 (x y) 1 1 x xy x xy НФЖ(x y) ;

(5.17) x y x y НФЖ(x y) НФЖ(x y) ;

(5.18) x y x y x y 1 x y НФЖ(x y) ;

Полученные равенства можно рассматривать, как выражения основных булевых функций в виде суперпозиций функций системы Жегалкина − {xy; x y; 0;1}, т.е. как некоторые правила, с помощью которых любую булеву функцию можно представить в виде формулы, содержащей только операции системы Жегалкина.

Покажем на примере, как эти правила работают при построении НФЖ(f ) для функций, заданных некоторыми формулами ТБФ.

Пример 5.3.Построить многочлен Жегалкина для БФ:

f (x, y, z) (x y (x z y)) x( y z) .

Решение. Порядок преобразования исходной формулы неважен, но для алгоритмизации процесса построения НФЖ(f ) будем всякий раз преобразовывать в функции системы Жегалкина «внешние» функции соответствующих суперпозиций (последние операции подформул, не входящие в систему Жегалкина). Последней

38

операцией исходной формулы является импликация. Поэтому, используя (5.15), получим:

f(x, y, z) (x y (x z y)) x( y z) =

=1 (x y (x z y)) (x y (x z y))x( y z) =

Далее, используя (5.18) заменим вхождения эквиваленций. Получим, учитывая ассоциативность операции «+»:

= 1 1 x y (x z y) (1 x y (x z y))x( y z) =

Используя (5.15) и (5.8), имеем:

= 0 x y 1 (x z) (x z) y (1 x y 1 (x z) (x z) y)(1 x( y z)) =

Заменим теперь дизъюнкции и стрелку Пирса, пользуясь (5.13) и (5.14). Получим:

=1 x y x z xz (x z xz) y (0 x y x z xz (x z xz) y)(1 x(1 y z y z)) =

Раскроем скобки на основании дистрибутивного закона (5.3) и упростим формулу с применением (5.4) и (5.5). Получим:

= 1 x y x z xz x y z y xz y (x y x z xz x y z y xz y)(1 x x y xz x y z) =

= 1 x z xz z y xz y (x z xz z y xz y)(1 x x y xz x y z) =

Можем еще воспользоваться равенством

(5.19) x x y x(1 y) x y xy ;

Тогда имеем:

= 1 x yz xyz (x yz xyz)(1 xz x yz) =

Раскроем скобки и упростим:

=1 x yz xyz (x yz xyz)(1 xz x(1 у)z) =

=1 x yz xyz (x yz xyz)(1 xz xz хуz) = 1 x yz xyz (x yz xyz)(1 хуz) =

=1 x yz xyz x yz xyz хуz xyz xyz = 1 xyz = НФЖ(f ) .

Ответ: НФЖ(f ) = 1 xyz .

Замечание 5.2. Еще раз заметим,что порядок преобразований формулы при построении многочлена Жегалкина жестко нерегламентирован.Конечная цель – привести формулу только к операциям системы Жегалкина,а затем раскрыть все скобки и упростить формулу.

3).Построение НФЖ(f ) аналитически,с использованием СДНФ(f ).

Докажем теорему, лежащую в основе этого метода построения НФЖ(f ).

		39
Теорема 5.2.Пусть x , x ,..., x		− некоторый список переменных, m~ (x , x ,..., x ) и
1 2	n		1 2	n

m~ (x , x ,..., x ) − два различных минтерма от этого списка переменных.Тогда

1 2

n

m~ (x , x ,..., x ) m~ (x , x ,..., x ) =

m~ (x , x ,..., x ) + m~ (x , x ,..., x ) ,т.е.сумма

1 2

n

1 2

n

1 2

n

1 2

n

двух различных минтермов равна их сумме. Доказательство. Пусть

m~ (x , x ,..., x ) = x 1 x 2

x i x n

и

m~ (x , x ,..., x ) =

x 1 x 2

x i

x

n .

1 2

n

1 2

i

n

1

2

n

1 2

i

n

Поскольку

m~ (x , x ,..., x )

≠ m

~

(x , x ,..., x ) , то найдется индекс i такой, что

i

. Но

1

2

n

1

2

n

i

тогда i

i . Рассмотрим дизъюнкцию исходных минтермов и преобразуем ее в

сумму по модулю два на основании (5.13). Получим:

m~ (x , x ,..., x ) m~ (x , x ,..., x )

= m~

(x , x ,..., x )

+ m~

(x , x ,..., x ) +

1 2

n

1

2

n

1 2

n

1

2

n

+ m~

(x , x ,..., x ) m~ (x , x ,..., x ) = m~

(x , x ,..., x ) + m~

(x , x ,..., x ) +

1

2

n

1

2

n

1 2

n

1

2

n

+ x 1 x 2

x i

x n

x 1

x 2 x i x n

= m~ (x , x ,..., x )

+ m~ (x , x ,..., x ) + 0 =

1

2

i

n

1

2

i

n

1 2

n

1 2

n

x i x i

x i x i

0

i

i

i

i

= m~ (x , x ,..., x ) + m~

(x , x ,..., x ) .

1

2

n

1 2

n

Теорема доказана.

Следствие 5.2.Если m~ , m~ , ... , m~

− различные минтермы от одного списка

1

2

k

переменных,то

m~

m~

... m~

=

m~

m~

... m~ .

1

2

k

1

2

k

Доказательство.Операция дизъюнкция ассоциативная. Расставим в начальной

дизъюнкции скобки, прижимая их к левому краю. Получим:

((...((m~

m~ ) m~ ) ...) m~ ) .

1

2

3

k

Теперь последовательно будем преобразовывать дизъюнкции в суммы по модулю два, пользуясь (5.13), законом дистрибутивности (5.3) и учитывая, что конъюнкция различных минтермов равна нулю. В итоге получим требуемое:

m~ m~

... m~ =

m~ m~

... m~ .

1

2

k

1

2

k

Из последнего следствия имеем:

m~ (x ,..., x

f (x ,..., x

) СДНФ( f )

)

(x

) (x

n

) ... НФЖ( f ) .

1 n

~

n 1

n

1

1

n

B

~

n

~

B

f ( ) 1

~

f ( ) 1

Откуда следует третий алгоритм построения НФЖ(f ):

Для построения НФЖ(f ) достаточно:

− привести исходную функцию к СДНФ (построить СДНФ(f ));

40

−заменить все дизъюнкции в СДНФ(f ) на суммы по модулю два;

−снять отрицания над переменными (если они есть) на основании (5.6);

−раскрыть скобки и упростить формулу до НФЖ(f ).

Пример 5.4. Построить многочлен Жегалкина для функции:

f (x, y, z) (x y (x z y)) x( y z).

Решение. Построим сначала СДНФ(f ). Имеем:

f(x, y, z) (x y (x z y)) x( y z) = x y (x z y) x( y z) =

x y(x z y) x y (x z y) x ( y z) = (x y)(x z y) x y(x z) y x y z =

(x y)(x z y) x yy(x z) x y z = (x y)(x z y) x0(x z) x y z =

(x y)(x z y) 0 x y z = (x y)(x z y) x y z x z x y xyz y y x y z.

Учитывая законы поглощения, получим:

f (x, y, z) x y z ДНФ( f ) x11 1y111z x( y y)(z z) (x x) y(z z) (x x)( y y)z

xyz x yz xyz x y z x y z x y z x yz x yz xy z xyz x y z x y z

Устраняя лишние вхождения минтермов на основании идемпотентности дизъюнкции, получим:

xyz x yz xyz x y z x y z x yz xy z СДНФ( f )

Тем самым, первый шаг рассматриваемого алгоритма построения НФЖ(f ) пройден. Имеем далее (на основании следствия теоремы 5.2):

xyz x yz xyz x y z x y z x yz xy z

(1 x) yz (1 x)(1 y)z (1 x) y(1 z) (1 x)(1 y)(1 z) x(1 y)(1 z) x(1 y)z xy(1 z) yz xyz z xz yz xyz y xy yz xyz 1 y z yz x xy xz xyz x xy xz xyz xz xyz xy xyz 1 xyz НФЖ( f ).

Ответ: НФЖ(f ) = 1 + xyz.

Теорема 5.3.(критерий равносильности по НФЖ): f g НФЖ( f ) НФЖ(g)

Доказательство.Утверждение теоремы сразу следует из того, что f = НФЖ(f ) и НФЖ(g) = g .

Теорема 5.4. (критерий тождественной истинности по НФЖ): f 1 НФЖ( f ) 1

41

Доказательство.Поскольку НФЖ для всякой БФ определяется однозначно и НФЖ(1 ) = 1, то все доказано.

Теорема 5.5. (критерий тождественной ложности по НФЖ): f 0 НФЖ( f ) 0

Доказательство.Поскольку НФЖ для всякой БФ определяется однозначно и НФЖ(0) = 0, то все доказано.

Подчеркнем еще раз некоторые применения НФЖ: НФЖ используется:

−в критерии равносильности;

−в критерии тождественной истинности;

−в критерии тождественной ложности.

6.Задачи для самостоятельного решения.

Для каждой из булевых функций:

1.f1 (x, y, z) xy ( y z xz);

2.f2 (x, y, z) (x y z) (x y z);

3.f3 (x, y, z) ((x y) / z) (x yz xy);

4.f4 (x, y, z) (x y)( y z) ((x y) z);

выполнить следующие задания:

1.Построить функцию f *, двойственную данной функции f:

−непосредственно по определению;

−пользуясь принципом двойственности;

−на основании ДНФ исходной функции;

2.Найти ДНФ(f *):

−пользуясь f *, построенной по определению;

−пользуясь f *, построенной на основании принципа двойственности;

−на основании ДНФ исходной функции;

3.Найти таблицы f и f *:

−пользуясь их ДНФ;

42

−пользуясь таблицей двойственной функции (таблицу f найти на основании таблицы f * и наоборот);

4.Пользуясь результатами 1.2 и 1.3 провести классификацию функций f и f *;

5.Построить СДНФ f и f *:

−исходя из их ДНФ;

−на основании их таблиц (см. п.3);

6.Построить КНФ f и f *:

−непосредственно (теорема 4.3);

−опосредованно (пользуясь алгоритмом f → ДНФ ( f ) → (ДНФ ( f )) *= f* →

→ДНФ(f*) → ( ДНФ(f*)) *= КНФ(f ));

7.Построить СКНФ f и f *:

−используя их КНФ;

−используя таблицы функций (см. п.3);

−по алгоритму: f → ДНФ ( f ) → (ДНФ ( f )) * = f* → СДНФ(f*) →

→( СДНФ(f*)) *=СКНФ(f );

8.Построить НФЖ для f и f *:

−используя таблицы f и f *;

−используя НФЖ основных БФ;

−используя СДНФ для f и f *.

9.Проверить тождество f = f *:

−по СДНФ функций;

−по СКНФ функций;

−по НФЖ функций.

Ответы:

Для функции f1:

ДНФ(f1) = xz y z;

CДНФ(f1) = x y z x y z xy z, ({0;4;6});

KНФ(f1) = (x y)z;

CKНФ(f1) = (x y z)(x y z)(x y z)(x y z)(x y z), ({1;2;3;5;7});

НФЖ(f1) = 1 y z xy yz xyz;

f1 :10001010. f1 ВП; f1 ОП; f1 ТИ; f1 ТЛ.