Основы дискретной математики

Теперь, когда коэффициенты найдены, запишем полином Жегалкина:

f (x1, x2 , x3 ) = 1Å1× x3 Å 0× x2 Å1× x2 x3 Å

Å1× x1 Å 0 × x1x3 Å1× x1x2 Å 0 × x1x2 x3 .

Упростив запись, получим

f (x1, x2 , x3 ) =1Å x3 Å x2 x3 Å x1 Å x1x2 . ►

Упражнение 2.26. Используя метод неопределенных коэффициентов, построить полином Жегалкина функции:

а) f (x1 , x2 ) = (1011) ;

б) f (x1 , x2 , x3 ) = (11100101) .

Определение. Булева функция называется линейной, если ее полином Жегалкина имеет степень 0 или 1.

Иначе говоря, функция линейна, если ее можно представить формулой вида

f = b0 Å b1x1 Å b2 x2 Å ... Å bn xn .

Обозначим через L множество всех линейных булевых функций, через L(n) -

множество линейных функций от n переменных.

Пример 10. а) Все функции одной переменной 0,1, x, x = x Å1 линейные.

б) Функции xy , x Ú y = x Å y Å xy , x y =1Å xy , x ¯ y =1Å x Å y Å xy и

x ® y = x Ú y = x Å y Å xy =1Å x Å xy линейными не являются. Функции x Å y , x « y = x Å y = x Å y Å1 линейные.

Упражнение 2.27. Задать полиномами Жегалкина все линейные функции от двух переменных.

Множества функций T0 , T1 , S , M , L называют классами				Поста.
Пример 11. Определить, каким из			классов Поста	принадлежит функция
f (x, y, z) = (x Ú y) Å (z ¯		).
	x
◄ Выпишем таблицу истинности функции f			(табл. 2.28).

PDF created with pdfFactory Pro trial version www.pdffactory.com

													Таблица 2.28
		y	z		x y								f (x, y, z) = (x Ú y) Å (z ¯	x	)
	x							x		z ¯ x
	0	0	0		0		1			0			0
	0	0	1		0		1			0			0
	0	1	0		1		1			0			1
	0	1	1		1		1			0			1
	1	0	0		1		0			1			0
	1	0	1		1		0			0			1
	1	1	0		1		0			1			0
	1	1	1		1		0			0			1
f (0,0,0) = 0 , следовательно,					f ÎT0 .
f (1,1,1) =1, следовательно, f ÎT1 .
f (0,0,1) = f (1,1,0) , следовательно, f							ÏS .
(0,1,0) p (1,1,0) , а			f (0,1,0) > f (1,1,0) , следовательно,										f ÏM .

Чтобы определить, линейна ли функция, найдем ее полином Жегалкина методом элементарных преобразований. Выпишем СДНФ функции и упростим ее:

f = xyz xyz xyz xyz = xy (z z) xz ( y y) = xy xz =

= xy Å xz = (x Å1)y Å xz = xy Å y Å xz .

Поскольку в полиноме Жегалкина есть произведения переменных, то f ÏL . ►

Упражнение 2.28. Определить, каким из классов Поста принадлежит функция f (x, y, z) = (x ↓ y) ↔ (z y) .

5. Замыкание системы булевых функций. Замыкание [B] системы булевых функций

B - это множество всех функций, которые можно задать формулами над B.

Заметим что термин «система» используется в дискретной математике как синоним слова «множество».

PDF created with pdfFactory Pro trial version www.pdffactory.com

Пример 12. а) Пусть B = {1, x} , тогда [B] = {0,1,x, x} .

б) Замыканием системы B = {Ù, Ú,Ø} является множество всех булевых функций P2 ,

поскольку любая булева функция представима в виде СДНФ или СКНФ.

в) Замыканием системы B = {0,1, Ù, Å} является множество всех булевых функций P2 ,

поскольку любая булева функция представима в виде полинома Жегалкина.

Определение. Система функций B называется замкнутой, если [B] = B.

Классы Поста T0 , T1 , S , M , L являются замкнутыми множествами.

Из этого утверждения (его доказательство приведено во второй части параграфа) вытекает, что если функции f1 , f2 ,..., fk принадлежат некоторому классу Поста, то любая функция, записанная формулой с использованием только функций этого класса, также будет принадлежать данному классу Поста.

Пример 13. а) Функция f = xy Ú xz Ú yz монотонная, поскольку она представлена
исключительно через дизъюнкцию и конъюнкцию, а эти две функции - монотонные.
б) Функция	f =		« z линейная, поскольку она представлена через линейные
		x Å y
функции - отрицание, сложение по модулю два и эквивалентность.
В то же время функцию, не принадлежащую какому-нибудь классу Поста, нельзя
представить формулой только через функции, входящие в этот класс.
Пример	14. Доказать, что функцию f = (1001)			нельзя	задать формулой над
множеством B = {Ù} .
◄ Конъюнкция принадлежит к классу T0 .				Класс T0	является замкнутым

множеством, следовательно, любая функция, заданная формулой над его функциями,

сохраняет 0. Функция f = (1001) этим свойством не обладает, значит,		ее нельзя задать
формулой только через конъюнкцию. ►
Упражнение 2.29. Доказать, что функцию f нельзя задать		формулой над
множеством B, если:
а)	f = (1100) , B = {«} ;
б)	f = (01111101) , B = {Ú} ;

в) f = xy Å1, B = {Å,Ø} .

PDF created with pdfFactory Pro trial version www.pdffactory.com

Теоретические обоснования Теорема 2.10. Замыкание обладает следующими свойствами:

1)BÍ [B] ;

2)é[B]ù = [B] ;

ë û

3)(B1 Í B2 ) Þ ([B1] Í [B2 ]) ;

4)([B1] È[B2 ]) Í [B1 ÈB2 ] .

Доказательство. Справедливость утверждения (1) непосредственно следует из определения замыкания, поскольку всякая функция реализуется формулой в виде символической записи самой функции.

Справедливость утверждения (2) вытекает из индуктивного определения формулы:

всякая функция из [B] задается некоторой формулой над B, а тогда всякая функция из

é[B]ù , которая задается формулой над [B] , задается также некоторой формулой над B.

ë û

Утверждение (3) очевидно, поскольку, если B1 подмножество B2 , то любая формула над B1 является также формулой над B2 .

Докажем утверждение (4). Возьмем произвольную функцию f		Î[B1 ] È [B2 ] . Согласно
определению объединения множеств, f Î[B1 ] или f Î[B2 ] ,		т.е. f можно задать
формулой над B1 или формулой над B2 . Но любая формула над B1 (B2 ) будет
формулой и над B1 B2 . Следовательно, f	Î[B1 È B2 ] , что и требовалось доказать. ■
Теорема 2.11. Классы Поста T0 , T1 , S , M ,	L являются замкнутыми множествами.

Доказательство. Надо доказать, что классы Поста совпадают со своими замыканиями. Для этого нужно доказать два утверждения: 1) каждый класс Поста принадлежит своему замыканию и 2) замыкание каждого класса Поста принадлежит самому классу.

Справедливость первого утверждения непосредственно вытекает из первого свойства замыкания.

Второе утверждение сводится к тому, что любая функция, заданная формулой через функции класса Поста, также принадлежит этому классу. Справедливость этого утверждения несложно установить индукцией по построению формул.

Базис индукции. Тождественная функция принадлежит всем классам Поста, значит, когда формула есть переменная, утверждение справедливо.

PDF created with pdfFactory Pro trial version www.pdffactory.com

Индуктивный переход. 1. Покажем, что функция F = f ( f1, f2 ,..., fn ) T0 , если f , f1 , f2 ,..., fn T0 :

F(0,0,...,0) = f ( f1 (0,0,...,0), f2 (0,0,...,0),..., fn (0,0,...,0)) =

fi =T0 f (0,0,...,0) f =T0 0 .

2. Покажем, что функция F = f ( f1, f2 ,..., fn ) T1 , если f , f1 , f2 ,..., fn T1 :

F(1,1,...,1) = f ( f1 (1,1,...,1), f2 (1,1,...,1),..., fn (1,1,...,1)) =

	fi =T1	f (1,1,...,1) f =T1 1.
3. Покажем, что функция F = f ( f1 , f2 ,..., fn ) S , если							f ,	f1 , f2 ,..., fn S :
F = ( f ( f1, f2 ,..., fn ))				принип двойственности
						=
= f ( f ,	f ,..., f ) = f ( f			, f	2	,..., f		n	) = F .
1	2	n	1
4. Покажем, что функция F = f ( f1, f2 ,..., fn ) M , если							f , f1 , f2 ,..., fn M .
		%								%
Возьмем два произвольных набора α% и β значений переменных таких, что α%										p β .
Тогда в силу монотонности функций f1 , f2 ,..., fn			имеем:
			%				;
ξ1 = f1 (α% ) ≤ f1 (β) = η1

ξ2 = f2 (α% ) ≤ f2 (β%) = η2 ;

……………………………

ξn = fn (α% ) ≤ fn (β%) = ηn .

Следовательно, (ξ1,ξ2 ,...,ξn ) p (η1,η2 ,...,ηn ) , и в силу монотонности f

f (ξ1,ξ2 ,..., ξn ) ≤ f (η1, η2 ,...,ηn ) .

Или

f ( f1 (α% ), f2 (α% ),..., fn (α% )) ≤ f ( f1 (β%), f2 (β%),..., fn (β%)).

Таким образом, для любых наборов α% и β% таких что α% p β% , выполняется неравенство

F (α% ) ≤ F (β%), что и требовалось доказать.

PDF created with pdfFactory Pro trial version www.pdffactory.com

5. Покажем что функция F = f ( f1 , f2 ,..., fn )ÎL , если f , f1 , f2 ,..., fn ÎL .

Пусть

f = b0 Å b1 y1 Å b2 y2 Å ...Å bn yn ;

f1 = a10 Å a11x1 Å a12 x2 Å ...Å a1n xn ;

f2 = a02 Å a12 x1 Å a22 x2 Å ...Å an2 xn ;

……………………………………….

fn = a0n Å a1n x1 Å a2n x2 Å ... Å ann xn .

Подставим правые части этих равенств в формулу для F :

F = b

Å b

æ

1

Å

n

1

ö

Å b

æ

2

Å

n

2

x

ö

Å ... Å

ça

a x

÷

ç a

a

÷

0

1

ç

0

å i i ÷

2

ç 0

å i i

÷

è

i=1

ø

è

i=1

ø

æ

n

Å

n

n

x

ö

= b

1

Å b a

2

Å ... Å b a

n

Å

Åb ç a

a

÷

Å b a

n ç

0

å i i

÷

0

1 0

2 0

n 0

è

i=1

ø

n

Å b2 ai2 xi Å ... Å bn ain xi )=

Åå(b1ai1xi

i=1

= b0 Å b1a10

Å b a02

Å ... Å bn a0n

Å

n

(b ai1

Å b2 ai2

Å ... Å bn ain )xi =

1444442444443

åi=1 14444244443

c0

ci

= c0 Å c1x1 Å c2 x2 Å ... Å cn xn .■

Задачи повышенной сложности

2.19. Сколько функций содержит множество:

а) S(n) ;	б) T1 (n) Ç S (n) ;
в) L(n)	г) T0 (n) È S(n) ;
д) L(n) Ç T0 (n) Ç T1 (n) ;	е) L(n) Ç S(n) ?

2.20. Доказать, что ни один из классов Поста не содержится в другом.

PDF created with pdfFactory Pro trial version www.pdffactory.com

2.21. Пусть f (x1, x2 ,..., xn )	- произвольная булева	функция; φ(x) получена из
f (x1, x2 ,..., xn ) путем отождествления всех переменных:		φ(x) = f (x, x,..., x) . Определить
φ(x) , если:
а) f ÎT1 \ T0 ;	б) f S .

2.22.Показать, что если f ÏT0 , то f либо немонотонная, либо несамодвойственная.

2.23.Доказать, что функция, двойственная к монотонной функции, монотонна.

2.24. Доказать, что функция, двойственная к линейной функции, линейна.

2.25.Доказать, что пересечение замкнутых классов - замкнутый класс.

2.26.Является ли объединение замкнутых классов замкнутым классом?

2.27.Доказать, что совокупность функций, двойственных к функциям из функционально замкнутого класса, образует функционально замкнутый класс.

2.28.Назовем булеву функцию f монотонно невозрастающей, если для любых

наборов α% и β% значений переменных, таких что α% p β% , выполняется неравенство

f (a% ) ³ f (b%). Привести пример булевой функции, заданной формулой над множеством

монотонно невозрастающих функций, которая не является монотонно невозрастающей. Замечание. Задача 2.28 объясняет, почему в теории булевых функций не

рассматривают монотонно невозрастающие функции. Дело в том, что интерес представляют свойства функций, которые «наследуются» при задании функций формулами, т.е. такие свойства, которые выделяют обладающие ими функции в замкнутый класс. Множество монотонно невозрастающих функций замкнутым не является.

2.29.Дана произвольная несамодвойственная функция. Отождествить ее переменные так, чтобы получилась несамодвойственная функция от возможно меньшего числа переменных.

2.30.Дана произвольная немонотонная функция. Отождествить ее переменные так, чтобы получилась немонотонная функция от возможно меньшего числа переменных.

2.31. Доказать, что для монотонных функций справедливо разложение

f(x1 , x2 ..., xn ) = xn × f (x1,..., xn−1,1) Ú f (x1 ,..., xn−1 ,0) .

2.32.Показать, что xi является существенной переменной тогда и только тогда, когда

xi явно входит в полином Жегалкина функции.

PDF created with pdfFactory Pro trial version www.pdffactory.com

2.33. Найти число линейных функций от n переменных, существенно зависящих ровно от k переменных.

PDF created with pdfFactory Pro trial version www.pdffactory.com

{x, x y}.

{x, x y}.

§ 2.5. Полнота системы булевых функций

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

Базовые понятия и утверждения

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

Определение. Множество булевых функций B = { f1, f2 ,..., fm ,...} называется полной

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

Пример 1. а) {Ù, Ú, Ø} - полная система, поскольку любая булева функция представима в виде СДНФ или СКНФ.

б) {0,1, Ù, Å} - полная система, поскольку любая булева функция представима в виде полинома Жегалкина.

в) {x, x y} - полная система, поскольку любую булеву функцию можно сначала выразить формулой над {Ù, Ú, Ø} , а затем заменить в этой формуле все дизъюнкции формулой x y = x y . В итоге получится формула над

г) {x, x y} - полная система, поскольку любую булеву функцию можно сначала выразить формулой над {Ù, Ú, Ø} , а затем заменить в этой формуле все конъюнкции формулой x y = x y . В итоге получится формула над

Следующая теорема обобщает подход, использованный нами для доказательства полноты систем {x, x y} и {x, x y}.

Теорема 2.12 (о полноте двух систем). Пусть заданы две системы булевых функций: B1 = { f1, f2 ,...} и B2 = {g1, g2 ,...} . Тогда, если система B1 - полная и каждая ее функция может быть задана формулой над B2 , то система B2 тоже полная.

PDF created with pdfFactory Pro trial version www.pdffactory.com

Доказательство. Покажем, как для произвольной булевой функции h построить формулу над B2 . Возьмем формулу для h над B1 h = Φ[ f1, f2 ,...] (в силу полноты B1

такая формула обязательно существует) и заменим в ней вхождение символов функций

f1, f2 ,... формулами fi

= Φi

[g1, g2 ,...]

над B1 (которые существуют по условию).

Получим формулу F éF

[g , g

2

,...],F

2

[g , g

2

,...],...ù над B , которая задает h . ■

ë

1

1

1

û

2

Пример 2. Докажем, что {x

y} - полная система. Действительно, пусть B1 = {

, x Ù y}

и

x

B2 = {x

y} . Имеем x

CKHΦ

y

=

x Ú y =

xy

, откуда xy = x

y . Следовательно, x

x =

xx

=

x

и

xy =

= (x

y)

(x

y) . Таким образом, каждую функцию полной системы B1

можно

x

y

задать формулой над B2 . Следовательно, условия теоремы о полноте двух систем

выполнены и, значит,

B2 = {x

y} - полная система.

С помощью теоремы о полноте двух систем можно доказать полноту некоторой

системы булевых функций. Обосновать неполноту с ее помощью нельзя.

2. Критерий полноты системы булевых функций. Наиболее удобный способ

проверки системы функций на полноту связан с использованием критерия полноты

Поста.

Для того чтобы система функций B = { f1,...,

fk } была полна, необходимо и достаточно,

чтобы для каждого из классов Поста в B нашлась функция

fi , ему не

принадлежащая.

Доказательство этого утверждения приведено во второй части параграфа.

При проверке, выполняются ли для некоторой системы функций B = { f1,..., fk }

условия

критерия Поста, удобно использовать таблицу, которую называют таблицей Поста

(табл. 2.29).

В ячейках таблицы ставится знак «+» или «–», в

Таблица 2.29

зависимости от того, входит функция, стоящая в

данной строке, в класс, стоящий в данном столбце,

Функции

Классы Поста

или не входит. В силу теоремы Поста для полноты

T0

T1

S

M

L

системы необходимо и достаточно, чтобы в каждом

f1

столбце стоял хотя бы один минус.

…

…

…

…

…

…

Таблицу Поста исследуемой системы лучше

fk

заполнять по столбцам.

Вначале

рассматриваем

класс

T0 . Если

B

окажется

PDF created with pdfFactory Pro trial version www.pdffactory.com