lec07_1

Доказательство (продолжение):

Единственность МЖ.

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

С помощью символов переменных x1, x2, … xn можно составить

2 2 … 2 = 2n – возможных разных произведений, в которых переменные располагаются слева направо в порядке возрастания индексов. К таким произведениям относится и пустое произведение (МЖ = a0).

Различных полиномов ровно столько, сколько существует различных подмножеств множества из различных произведений: ?

	N = 22n	– существует МЖ.
При этом пустое подмножество множества всех таких произведений
соответствует МЖ = 0.	n
Булевых функций столько же 22	. Следовательно, существуют взаимно

однозначные отображения.

21

Следствие теоремы 7.3.

Если произвольный МЖ содержит вхождение некоторой переменной xi, то xi является существенной переменной для функции, представляемой этим полиномом.

Доказательство: от противного.

Действительно, если полином Жегалкина W представляет f и содержит вхождение несущественной переменной xi, то существует функция g, равная f и не имеющая xi в качестве своей переменной. Тогда полином Жегалкина V, представляющий функцию g, не содержит вхождений переменной xi f представляется двумя разными полиномами W и V, что невозможно в силу теоремы 7.3. Поэтому xi является существенной переменной функции f.

22

Булева функция (x1, x2, … xn) называется линейной, если ее МЖ содержит только одночлены не выше первой степени (0 и 1).

(x1, x2, … xn) = с 1 2 … ,

где свободный член - c {0,1}. Не все переменные обязательно входят в сумму, члены с «0» коэффициентом отбрасываем.

Пример 7.2.

Для (x1, x2) линейный полином Жегалкина имеет вид:

		(x1,x2) = a0 a1 x1 a2 x2
Линейные функции:
а) (x1,x2) = x1	a2 x2, (a0=0, a1=a2=1);
б) (x1,x2) = x1	x2 = 1 2 = x1 x2 1, (a0=a1=a2=1);
Нелинейные функции:
(x1,x2) = x1| x2	= 1 & 2	= x1 x2 1.	23

Алгоритм (1) построения МЖ по ТИ для (x1,x2,x3) (на примере 7.3).

Пример 7.3.

Представим в виде МЖ булеву функцию: = (0011 1100).

Для n = 3 МЖ самого общего вида:

(x1,x2,x3) ≡ a0 a1 x1 a2 x2 a3 x3 a4 x1 x2 a5 x1 x3 a6 x2 x3 a7 x1 x2 x3, (7.1)

где a = (a0, a2, … ai, … a7), ai {0,1}.	= x , 2
!!! в МЖ нет высших степеней: 2			= x .
1	1		i

Найдем a.

Т.к. (7.1) – тождество, то в B3 из ТИ имеем 23 наборов (x1,x2,x3, ) и 23 одночленов Жегалкина, т.о. из 8-ми уравнений найти 8 неизвестных.

24

Пример 7.3. (продолжение)

x1	x2	x3	(x1,x2,x3) =
0	0	0	0	a0
0	0	1	0	a3
0	1	0	1	a2
0	1	1	1	1 a6 = 1		a6 = 0
1	0	0	1	a1
1	0	1	1	1 a5 = 1		a5 = 0
1	1	0	0	1 1	a4 = 0 a4 =0
1	1	1	0	1 1 a7 = 0 a7 = 0

a = (01100000).

Таким образом: (x1,x2,x3) = 1 2 – т.е. оказалась линейной.

25

Алгоритм (2) построения МЖ по СДНФ (x1, … xn).

Основан на тереме 7.3 о единственности МЖ представления БФ.

1)Заменяем каждый символ на .

2)Заменяем на x 1.

3)Раскрываем скобки.

4)Вычеркиваем пары одинаковых слагаемых.

Пример 7.4.

Представим в виде МЖ булеву функцию (x,y,z), заданную СДНФ. n = 3.

СДНФ = (¬x y z) (x ¬y z) (x y ¬z) (x y z) = 1) = (¬x y z) (x ¬y z) (x y ¬z) (x y z) =

2)= ((x 1)yz) (x(y 1)z) (xy(z 1)) (xyz) =

3)= xyz yz xyz xz xyz xy xyz = yz xz xy.

a = (00001110).

26

МЖ элементарных БФ:

Константы 0 и 1, тождественная функция, а также конъюнкция x1 x2 и x1 x2 уже являются МЖ. Инверсия: x = 1 x.

(x1,x2)		МЖ
	≡0	0
	≡1	1
	x1	x1
	x2	x2
x1		1 x1
x2		1 x2
x1	x2	x1x2
x1	x2	x1 x2

a

0000

1000

0100

0010

1100

1010

0001

0110

(x1,x2) x1 x2 x1 x2 x2 x1 x1 x2 x1 | x2

x1 x2

(x1 x2)(x2 x1)

МЖ

x1 x2 x1x2

1 x1 x1x2

1 x2 x1x2

1 x1 x2 x1x2 1 x1x2

1 x1 x2 x1 x1x2 x2 x1x2

a

0111

1101

1011

1111

1001

1100

0101

0011

27

Алгоритм (3) построения МЖ.

Если БФ задана произвольной формулой F, то ее МЖ можно получить подстановкой в формулу вместо элементарных булевых функций их МЖ.

Пример 7.5. Функция (x,y,z) задана формулой F= x y Представим ее в виде МЖ:

← z | (x y).

F= (x y ← z) | (x y) = (расставляем приоритеты)

=((x y) ← z) | (x y) = (расписываем штрих Шеффера |)

=1 ((x y) ← z)(x y) = (расписываем импликацию )

=1 (1 z (x y)z)(1 x x y) = (расписываем эквивалентность )

=1 (1 z (1 x y)z)(1 x x y) = (расписываем инверсию )

=1 (1 z (1 x y)z)(1 x x (1 y)) = (раскрываем скобки)

=1 (1 z z xz yz)(1 x x xy) = (удаляем пары слагаемых)

=1 (1 xz yz)(1 xy) = (раскрываем скобки)

=1 1 xz yz xy xzxy xyyz = (удаляем пары слагаемых)

=xz yz xy