Дискретка учебник

αm = 1 αm = 0

αm · f(α1, . . . , αm−1, 0, αm+1, . . . , αn)

αm · f(α1, . . . , αm−1, 1, αm+1, . . . , αn) =

=1 · f(α1, . . . , αm−1, 0, αm+1, . . . , αn)

1 · f(α1, . . . , αm−1, 1, αm+1, . . . , αn) =

=0 · f(α1, . . . , αm−1, 0, αm+1, . . . , αn)

1 · f(α1, . . . , αm−1, 1, αm+1, . . . , αn) =

=f(α1, . . . , αm−1, 1, αm+1, . . . , αn) =

=f(α1, . . . , αm−1, αm, αm+1, . . . , αn).

При выводе мы использовали тождества 1·A = A, 0·A = 0 и A 0 = A. Итак, мы получили:

f(α1, α2, . . . αn) =

=αm · f(α1, . . . , αm−1, 0, αm+1, . . . , αn)

αm · f(α1, . . . , αm−1, 1, αm+1, . . . , αn) =

=f(α1, α2, . . . , αm−1, αm, αm+1, . . . , αn).

Так как αe - произвольный двоичный набор, равенство (3.1) выполняется для всех αe Bn, и, значит, является тождеством. Заметим, что xmm = 1 xm = σm. Тогда тождество (3.1) можно представить следующим образом:

f(x1, . . . , xm−1, xm, xm+1, . . . , xn) =

= xmm f(x1, . . . , xm−1, σm, xm+1, . . . , xn).

Аналогично доказываются две следующие теоремы.

Теорема	3.2. О разложении функции по нескольким переменным
Всякую функцию					алгебры логики f(x1, x2, . . . , xn) при любом m
(1 6 m 6 n) можно представить в виде
f(x1, x2, . . . , xm−1, xm, xm+1, . . . , xn) =
=	;	;:::; m		1	; m)	m x11 x22 · · · xmm−−11 xmm f(σ1, σ2, . . . , σm−1, σm,
(						B
1	2	−

xm+1, . . . , xn),

31

Это равенство называется разложением функции по переменным x1, x2, . . . , xm.

Теорема 3.3. О разложении функции по всем переменным

f(x1, x2, . . . , xn) = σe Bn x11 x22 · · · xnn−−11 xnn f(σ1, σ2, . . . , σn−1, σn).

Если f(x1, x2, . . . xn) ̸≡0, то, удалив логические слагаемые, для

которых f(σ1, σ2, . . . σn) = 0, получим

f(x1, x2, . . . , xn) = σe Nf x11 x22 · · · xnn−−11 xnn .

Найденное разложение называется Совершенной Дизъюнктивной Нормальной Формой (СДНФ).

Замечание 3.4. В СДНФ входят элементарные конъюнкции, имеющие одинаковый ранг n, где n- количество переменных.

rсднф = |Nf | · n

Замечание 3.5. СДНФ имеет максимальный ранг среди всех ДНФ, реализующих данную функцию.

Теорема 3.4. Любая булева функция может быть представлена булевой формулой, являющейся суперпозицией дизъюнкции, конъюнкции и отрицания.

Доказательство. Рассмотрим два случая:

1.Пусть функция f(xe) ̸≡0. Тогда, согласно теореме 3.3, эту функцию можно представить в виде СДНФ, то есть формулы, содержащей элементарные функции , &, ¬.

2.Если функция является тождественным нулем (f(xe) ≡ 0), то её можно представить, например, в виде формулы f(xe) = x1 · x1, являющейся суперпозицией конъюнкции и отрицания.

32

3.2.1Алгоритм построения СДНФ булевой функции

1.Находим носитель функции Nf = {σe Bn|f(σe) = 1}, то есть те двоичные наборы σ,e на которых значение функции равно 1.

2.Для каждого набора σe из носителя выписываем элементарную конъюнкцию K = x11 x22 · · · xnn .

Если значение i- той координаты в наборе σe равно нулю (σi = 0), то переменная xi входит в элементарную конъюнкцию с отрицанием; если же σi = 1, то без отрицания.

3.Составляем СДНФ, соединяя полученные конъюнкции знаком дизъюнкции.

Пример 3.7. Найти СДНФ функции, заданной вектором значений fe= (01001100). Вычислить ранг полученной формулы.

Решение.

1.Так как длина вектора значений равна 8 = 23, то функция зависит от трех переменных. Представим функцию таблично.

x	y	z		f
0	0	0		0
0	0	1		1
0	1	0		0
0	1	1		0
1	0	0		1
1	0	1		1
1	1	0		0
1	1	1		0

2.Подчеркнем все наборы носителя и сопоставим каждому набору σe Nf элементарную конъюнкцию.

33

x	y	z		f
0	0	0		0	K1 = x0y0z1 =
0	0	1		1					·		· z
								x		y
0	1	0		0
0	1	1		0
1	0	0		1	1	0	0
					K2 = x1y0z1 = x ·					y	· z
1	0	1		1
					K3 = x y z = x · y · z
1	1	0		0
1	1	1		0

3. Выписываем СДНФ:

fсднф = K1 K2 K3 = x · y · z x · y · z x · y · z

и вычисляем её ранг rсднф = 9.

3.3Совершенная конъюнктивная нормальная форма

Теорема 3.5. Любая функция алгебры логики, отличная от тож-

дественной единицы (f(xe) ̸≡1), может быть представлена в виде

формулы f(x1, x2, . . . , xn) = e Nf (x11 x22 · · · xn−n−11 xnn ).

Такое представление двоичной функции называется Совершенной Конъюнктивной Нормальной Формой (СКНФ).

Доказательство. Рассмотрим функцию, f(xe) противоположную данной. Так как f(xe) ̸≡1, то f(xe) ̸≡0, и, значит, функцию f(xe) можно представить в виде СДНФ:

(x1, x2, . . . , xn) = σ N

x11 x22

· · · xnn−−11 xnn =

f

f

e

= σ

f x11 x22 · · · xnn−−11 xnn (3.2)

N

Логическое тождество

A = B

не

изменится, если к обеим его частям

e

применить операцию отрицания, то есть, A = B

A = B.

34

Проинвертируем обе части равенства (3.2):

f(x , x , . . . , x ) = x 1 x 2 · · · x n−1 x n .

1 2 n σe Nf 1 2 n−1 n

К левой части тождества применим закон двойного отрицания

f(xe) = f(xe),

а к правойзаконы де Моргана (см. пункт 4 на стр. 19)

{

x y

=

x

y

,

x y =

x

y

обобщив их на произвольное количество переменных

i=1

=

.

i=1;:::;m xi

;:::;m xi

i=1;:::;m xi

= i=1;:::;m

i

x

Получим

f(x) = σ

f (

· · ·

)

x11 x22 · · · xnn−−11 xnn

xnn−−11

f

=

σ

x11

x22

xnn

N

N

e

e

Так

e как

= x 1 = (x σ 1) 1 = x (σ 1) 1 = x

1 = x

,

x

σ

окончательно получим:

σ Nf (x

−n−11 x

n ).

f(x) =

1

1 x

2

2 · · · x

n

n

e

e

Замечание 3.6. rсднф+rскнф = n·2n, где n- количество переменных.

35

3.3.1Алгоритм построения СКНФ булевой функции

1. Находим					дополнение	к	носителю	функции
				e	e	0}, то	есть те двоичные	наборы	e
	на
	Nf		=	{σ	Bn|f(σ) =				σ,

которых значение функции равно 0.

2.Для каждого набора σe из дополнения к носителю выписываем элементарную дизъюнкцию D = x11 x22 · · · xnn .

Если значение i- той координаты в наборе σe равно единице (σi = 1), то переменная xi входит в элементарную конъюнкцию с отрицанием; если же σi = 0, то без отрицания.

3.Составляем СКНФ, соединяя полученные дизъюнкции знаком конъюнкции.

Пример 3.8. Представить функцию fe= (01001100) из примера 3.7 в виде СКНФ.

Решение.

1.Подчеркнем все булевы двоичные наборы, принадлежащие дополнению к носителю и сопоставим каждому набору σe Nf элементарную дизъюнкцию.

x	y	z		f
0	0	0		0	D1 = x		y		z		= x1 y1 z1 = x y z
						0		0		0
0	0	1		1	D2 = x
0	1	0		0		0	y	1	z	0	= x1 y0 z1 = x				z
														y
0	1	1		0	D3 = x	0	y	1	z	1	= x1 y0 z0 = x
														y		z
1	0	0		1
1	0	1		1	D4 = x
1	1	0		0		1	y	1	z	0	= x0 y0 z1 =				z
												x		y
1	1	1		0	D5 = x	1	y	1	z	1	= x0 y0 z0 =
												x		y		z

2. Получаем СКНФ:

fскнф = D1&D2&D3&D4&D5 =

= (x y z)(x y z)(x y z)(x y z)(x y z). (3.3)

Её ранг равен 15.

36

Пример 3.9. Построить таблицу истинности, найти носитель функции, СДНФ и СКНФ булевой функции, заданной формулой

f(x, y, z) = ((x ↓ z) (y z)) | (x y)&(z → x).

Решение.

1. Установим порядок выполнения двоичных функций

					7
1	3	2	8	4	6	5

f(x, y, z) = ((x ↓ z) (y z)) |((x y) & (z → x))

2. Разобьем формулу на элементарные функции:

f1 = x ↓ z f2 = y z f3 = f1 f2 f4 = x y f5 = z → x f6 = f4&f5

f7 = f6

f8 = f3 | f7

3.Вычислим значение элементарных функций f1, . . . , f8 на всех двоичных наборах:

x y z f1 f2 f3 f4 f5 f6 f7 f8

0	0	0		1	1	0	0	1	0	1	1
0	0	1		0	0	0	0	0	0	1	1
0	1	0		1	0	1	1	1	1	0	1
0	1	1		0	1	1	1	0	0	1	0
1	0	0		0	1	1	1	1	1	0	1
1	0	1		0	0	0	1	1	1	0	1
1	1	0		0	0	0	1	1	1	0	1
1	1	1		0	1	1	1	1	1	0	1

4. Таблица истинности Tf заданной функции:

37

x	y	z		f
0	0	0		1
0	0	1		1
0	1	0		1
0	1	1		0
1	0	0		1
1	0	1		1
1	1	0		1
1	1	1		1

5. Сопоставим всем наборам носителя элементарные конъюнкции:

x	y	z		f	K1 =
0	0	0		1			·		·
						x		y		z
					K2 =		·		· z
0	0	1		1
						x		y
					K3 =		· y ·
0	1	0		1
						x				z
0	1	1		0	K4 = x ·
1	0	0		1					·
								y		z
					K5 = x ·				· z
1	0	1		1
								y
					K6 = x · y ·
1	1	0		1
										z
					K7 = x · y · z
1	1	1		1

6. Итак, СДНФ заданной функции равна

fсднф = K1 K2 K3 K4 K5 K6 K7 =

= x · y · z x · y · z x · y · z x · y · z x · y · z x · y · z x · y · z.

Её ранг rсднф = 21.

7.Найдем СКНФ заданной функции. Она совпадает с элементарной дизъюнкцией, соответствующей единственному набору, на котором функция принимает нулевое значение.

fскнф = D1 = x y z; rскнф = 3.

Замечание 3.7. Очевидно, что порядок выполнения операций алгебры логики может задаваться, вообще говоря, не единственным образом. Так, в приведенном выше примере возможен и такой порядок

38

действий:

					7
1	6	2	8	3	5	4

f(x, y, z) = ((x ↓ z) (y z)) |(x y) & (z → x) .

3.3.2Выражение сложения по модулю 2, эквивалентности

иимпликации через другие элементарные функции

Используя алгоритмы представления функций в виде СДНФ и СКНФ, выразим основные элементарные функции через дизъюнкцию, конъюнкцию и отрицание:

1. x y = (xy) (xy) = (x y)&(x y)

2.x y = x y = xy (x&y) = (x y)&(x y)

3.	x → y =		y.
		x

3.4Многочлен Жегалкина

Определение 3.7. Многочленом Жегалкина называется формула вида

P (xe) =

= a0 a1x1 a2x2 . . . anxn a12x1x2 a13x1x3 . . . a12:::nx1x2 · · · xn.

Другими словами, многочлен Жегалкина - сумма по модулю два попарно различных элементарных конъюнкций, не содержащих отрицаний переменных (многочлен по модулю 2).

Пример 3.10. Многочленами Жегалкина являются следующие формулы:

f1(xe) = 1 x1 x1x2x3; f2(xe) = x1x2 x1x3.

Теорема 3.6 (И.И.Жегалкина). Всякая булева функция представима в виде многочлена Жегалкина, причем единственным образом (с точностью до порядка слагаемых и порядка сомножителей в конъюнкциях).

39

Доказательство. Если функция f(x) ≡ const, то она уже представ-

лена в виде многочлена Жегалкина.
Пусть	f(x)	const,	тогда		функцию можно представить в виде
	e	̸≡					e
СДНФ:					1			2	n−1 n
		f(x) =	σ	Nf x1				x2	· · · xn−1 xn .
Учитывая, что		e	e
				x · x			= 0,

получаем

(x1 1 x2 2 · · · xnn )(x11 x22 · · · xnn ) ≡ 0

при (α1, α2, . . . , αn) ≠ (β1, β2, . . . , βn).

Поскольку первые 3 строки таблиц истинности для функций двух переменных "дизъюнкция" и "сложение по модулю 2" совпадают, то x y = x y при x · y = 0. Поэтому, учитывая, что в СДНФ нет одинаковых логических слагаемых, булеву функцию "дизъюнкция" в СДНФ можно заменить на функцию "сложение по модулю 2".

Функция принимает вид

f(xe) = σe Nf x11 x22 · · · xnn−−11 xnn .

Используя равенство x = x σ 1, заменяем в полученной формуле все x на x σ 1. Раскрываем скобки; учитывая тождество x x = 0, приводим подобные, вычеркивая пары одинаковых слагаемых. В результате этих преобразований получим многочлен Жегалкина.

Существование многочлена Жегалкина доказано. Докажем его единственность.

В общем виде многочлен Жегалкина можно представить формулой
f(x) = (i1, i2, . . . , k)αi1i2::: k xi1 · xi2 · · · xik ,	αi1i2::: k {0, 1}.
Числоeразличных конъюнкций xi1 ·nxi2 · · · xik	равно числу всех под-

множеств из n элементов, то есть 2 . Число различных многочленов равно числу всех подмножеств множества конъюнкций, то есть 22n . Таким образом, число всех многочленов Жегалкина, зависящих от n переменных, равно числу всех булевых функций n переменных (см. теорему 2.2). Из этого, как следствие, делаем вывод о единственности представления булевой функции многочленом Жегалкина.

40