Bulevy_funktsii_Polnye_sistemy_BF

3

Содержание

Введение ………………………………………………………………….………………………………..		4
1.	Полные системы булевых функций….………………….…………...…………………..	5
	Суперпозиция булевых функций…..………………………………………..…………	5
	Замыкание. Свойства замыкания…………………….………….…………………….	5
	Полные системы. Первый критерий полноты……….…….……………………	5
	Независимые системы БФ. Базисы………………….…….….……………………….	6
2.	Замечательные классы БФ………….………………………………….…………………….	7
	Классы Т0, Т1.Теоремы о классах Т0, Т1 … ………………….……………… .………	7
	Класс линейных функций L. Теорема о классе L…………………….…....……	8

Класс самодвойственных функций S. Теорема о классе S …….…....……… 9

Класс монотонных функций М. Критерий. Теорема о классе М ..…….. 11

3.Теорема Поста (второй критерий полноты)……………………………….. .…….. 14

Лемма 3.1 (о функциях, не сохраняющих константы)…………...……..……. 14

Лемма 3.2 (о построении константы)..…………………………..………….………. 15

Лемма 3.3 (о «скачке» немонотонной функции)……………………………… 15

Лемма 3.4 (о построении отрицания)………………………..……………………... 16

Лемма 3.5 (о построении конъюнкции)……………………………….…………... 16

Теорема 3.1 (критерий Поста)…………………… ……………………..……………... 17

Пример………………………………………………………………………………………………. 20

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

5.Рекомендуемая литература……………………………………………………………….. 24

4

Введение

Настоящие методические указания предназначены для студентов первого курса факультета прикладной математики и информационных технологий ИМЭМ ОНУ им. И.И.Мечникова (специальности «компьютерные системы и сети»). Курс дискретной математики на этом факультете читается в первом и во втором семестре. Материал курса разбит на четыре модуля. Предлагаемые методические указания содержат материал четвертого модуля - второго во втором семестре. Количество отводимых на курс дискретной математики учебных часов явно недостаточно для подробного и обстоятельного изучения тем этого курса. Этот факт и новизна материала (нет необходимой базы со средней школы) вызывают у студентов трудности в процессе изучения дискретной математики. Для устранения этого пробела и для облегчения процесса обучения студентам предлагается подробное изложение темы «Полные системы булевых функций» с доказательством большинства необходимых теорем, решением иллюстрирующих примеров. В конце конспекта лекций даются задачи для самостоятельного решения с указанием ответов и приводится список рекомендуемой литературы.

Предлагаемый конспект лекций несомненно будет полезен и студентам специальностей «прикладная математика», «классическая математика» и «математическая экономика», изучающих дискретную математику на первом курсе в ИМЭМ ОНУ им. И,И,Мечникова.

i 1,n

5

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

Определение 1.1.

m

Пусть f n , g m , g m ,..., g m P ,где

f n f n (x , x

2

,..., x

n

) и : g m g m ( y , y

2

,..., y

m

) .

1 2

n

2

1

i 1

i

i 1

Тогда функция F m F m ( y1 , y2 ,..., ym ) S n 1 ( f n , g1m , g2m ,..., gnm )

f n (g1m ( y1 , y2 ,..., ym ), g2m ( y1 , y2 ,..., ym ),..., gnm ( y1 , y2 ,..., ym )) называется суперпозицией исходных булевых функций (БФ) в указанном порядке.

Замечание 1.1.В теории булевых функций операции алгебры высказываний (АВ) над формулами АВ рассматриваются и понимаются как соответствующие суперпозиции булевых функций,представленных формулами.Например,

x y (x yz) S 3 (x y, x y, x yz) (x y, x yz) .

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

Определение 1.2.

Пусть H f1 , f2 ,..., fn ,... fi P2 ; i, n - произвольное множество (конечное

или нет) булевых функций. Тогда множество всевозможных суперпозиций ф-ций из H называется замыканием H и обозначается [H].

Очевидные свойства замыкания:

1.H H ;

2.H1 H2 H1 H2 ;

3.H H ;

4.H1 H2 H1 H2 ;

5.H1 H2 H1 H2 .

Определение 1.3.

Система БФ называется полной,если её замыкание равно множеству всех без исключения БФ.Т.о.

H f1 , f2 ,..., fn ,...		fi P2 ;	i, n - полная	def	H P2 .

В дальнейшем мы будем рассматривать, как правило, конечные полные системы.

Теорема 1.1 (Первый критерий полноты). Пусть даны две системы булевых функций

H f1 , f2 ,..., fn - полная и G g1 , g2 ,..., gk .

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

( G P2 ) ( i fi : fi G ) .

fi H

			6
Доказательство:				( G P2 ) ( i							fi : fi G ) .
Необходимость . Нужно доказать:
										i 1,n	fi H
Имеем:
		G P								G )
2			(H G ) ( fi : fi
		Н P			fi		H
2
И необходимость доказана.
Достаточность . Нужно доказать: (						i f			: fi	G ) ( G P2 ) .
						i
				i 1,n			fi	H
Имеем:
(					свойство 2				замыканий
		i fi : fi G ) (H [G])									( H G ) .
i 1,n fi H
Поскольку Н, по условию, полная, то H P2 и, следовательно, имеем P2 G .
Обратное включение G P2 очевидное, ибо P2								содержит все без исключения БФ, а
значит и функции из G . Имеем:
			P2 G
			G P	( G P2 )
			2
Т.е. система G - полная. Теорема доказана.

Примеры.

1. Система H= , , , , - полная, т.к. всякую булеву функцию можно

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

H , , , , P2 ,

т.е. Н - полная;

2.Поскольку x y (x y)( y x) , то функция (x y) , , , =[Н1].

Остальные функции системы Н предыдущего примера содержатся в Н1. Таким образом, H H1 . Поскольку Н – полная (см. предыдущий пример), то в силу первого критерия полноты имеем - система Н1 = , , , - полная.

Упражнения: Используя первый критерий полноты доказать полноту систем:

, , , , , , , , , , ,1 , , \ .

Определение 1.4.

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

	( H f1 , f2 ,..., fn - независимая)	def				fi : fi [H\{fi}]
					i
			i 1,n
						fi H

Определение 1.5.

Система БФ называется базисом,если она является полной и никакая её собственная подсистема полной не является (т.е.если она полная и независимая).

7

2. Замечательные классы БФ

Определение 2.1.

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

		~
def	f P2	f (0) 0 .
T0

Определение 2.2.

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

		~
def	f P2	f (1) 1
T1

Теорема 2.1 (о классе Т0).

Пусть T0(n) - множество функций класса Т0,которые зависят от n переменных. Тогда справедливы следующие утверждения:

1.Т0 Ø;

2.Т0 – замкнут (Т0 = [Т0]);

3.T0(n) 22n 1 (т.е.половина всех без исключения БФ от n переменных

принадлежит классу Т0).

4. [Т0] ≠ P2.

Доказательство.

1.Нуль-функция (const 0) принадлежит классу Т0, а потому Т0 Ø.

2.Рассмотрим произвольную совокупность функций класса Т0:

f n , g1m , g2m ,..., gnm T0 .

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

F( y1 , y2 ,..., ym ) S n 1 ( f n , g1m , g2m ,..., gnm ) f n (g1m ( y1 , y2 ,..., ym ),..., gnm ( y1 , y2 ,..., ym )) .

Тогда

F(0,0,...,0) f n (g1m (0,0,...,0),..., gnm (0,0,...,0)) f n (0,0,...,0) 0

и, следовательно, F Т0. Значит, T0 T0 . Обратное включение T0 T0 очевидное. Таким образом, Т0 = [Т0], т.е. класс Т0 замкнут.

3. Рассмотрим таблицу произвольной функции f (n) из T0(n) :

f (n) : 0 f1 f2 ... f2n 2 f2n 1.

Поскольку первое место таблицы занято нулем (значение f (n) на нулевом наборе значений переменных), то таблица f (n) определяется двоичным набором

( f

, f

2

,..., f

n

2

, f

n

1

) из B2n 1

. Поэтому

1

2

2

T (n)

22n 1 .

B2n 1

0

4. Сonst 1 Т0. Поэтому [Т0] ≠ P2 и теорема доказана.

8

Теорема 2.2 (о классе Т1).

Пусть T1(n) - множество функций класса Т1,которые зависят от n переменных. Тогда справедливы следующие утверждения:

1.Т1 Ø;

2.Т1 – замкнут (Т1 = [Т1]);

3.T1(n) 22n 1 (т.е.половина всех без исключения БФ от n переменных

принадлежит классу Т1). 4. [Т1] ≠ P2.

Доказательство.

1.Сonst 1 принадлежит классу Т1, а потому Т1 Ø.

2.Рассмотрим произвольную совокупность функций класса Т1:

f n , g1m , g2m ,..., gnm T1 .

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

F( y , y

2

,..., y

m

) S n 1 ( f n , g m , g m ,..., g m ) f n (g m ( y , y

2

,..., y

m

),..., g m

( y , y

2

,..., y

m

)) .

1

1

2

n

1 1

n

1

Тогда

F(1,1,...,1)

f n (g m (1,1,...,1),..., g m (1,1,...,1))

f n (1,1,...,1) 1

1

T1

n

T1

очевидное.

и, следовательно, F Т1. Значит,

T1 . Обратное включение T1

Таким образом, Т1 = [Т1], т.е. класс Т1 замкнут.

3. Рассмотрим таблицу произвольной функции f (n) из T1(n) :

f (n) : f0 f1 f2 ... f2n 21.

Поскольку последнее место таблицы занято единицей (значение f (n) на единичном наборе значений переменных), то таблица f (n) определяется двоичным набором

( f0 , f1 , f2 ,..., f2n 2 ) из B2n 1 . Поэтому

T (n)		B2n 1	22n 1 .
1

4. Сonst 0 Т1. Поэтому [Т1] ≠ P2 и теорема доказана.

Определение 2.3.

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

def	f P2	f (x1 , x2 ,..., xn ) a0 a1 x1 ... an xn ; n 0 .
L

Теорема 2.3 (о классе L).

Пусть L(n) - множество функций класса L,которые зависят от n переменных. Тогда справедливы следующие утверждения:

1.L Ø;

2.L – замкнут (L = [L]);

3.L(n) 2n 1

4.[L] ≠ P2.

Доказательство.

1.Тождественная функция х принадлежит L, а потому L Ø.

2.Рассмотрим произвольную совокупность функций класса L:

9

f n , g1m , g2m ,..., gnm L .

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

f (n) f (n) (x1 , x2 ,..., xn ) a0 a1 x1 ... an xn ;

g (m) g (m) ( y , y
			2	,..., y	m	) b	b y	... b y	m	, i 1, n
i	i	1				0i	1i 1	mi

Имеем:

F( y1 , y2 ,..., ym ) S n 1 ( f n , g1m , g2m ,..., gnm ) f n (g1m ( y1 , y2 ,..., ym ),..., gnm ( y1 , y2 ,..., ym )) =

a0 a1 (b01 b11 y1 ... bm1 ym ) ... an (b0n b1n y1 ... bmn ym )

(a0 a1b01 ... anb0n ) (a1b11 ... anb1n ) y1 ... (a1bm1 ... anbmn ) ym

c0 c1 y1 ... cm ym ,

где c0

a0

a1b01

... anb0n

и

ci a1bi1 ... anbin ,

i 1, m

и, следовательно,

F( y , y

2

,..., y

m

) S n 1

( f n , g m , g m ,..., g m )

f n (g m ( y , y

2

,..., y

m

),..., g m ( y , y

2

,..., y

m

)) L.

1

1

2

n

1

1

n 1

Значит,

L L . Обратное включение L L очевидное. Таким образом,

L = [L] и

класс L замкнут.

3. Рассмотрим произвольную функцию f (n) из L (n).

f (n)

f

(n) (x , x

2

,..., x

n

) a

0

a x

... a

n

x

n

.

1

1 1

Поскольку всякий многочлен Жегалкина однозначно определяется двоичным

набором своих коэффициентов, то f (n) f (n) (x , x

,..., x

n

)

a

0

a x

... a

x

n

1 2

1 1

n

однозначно определяется двоичным набором

(a

, a ,..., a

n

) из Вn+1. Следовательно

0

1

L(n)

Bn 1

2n 1 .

4. Конъюнкция ху L. Поэтому [L] ≠ P2

и теорема доказана.

Определение 2.4.

Множество булевых функций,каждая из которых совпадает с двойственной ей функцией (самодвойственных),называется классом самодвойственных функций и обозначается S,т.е.

def	f P						f * (x , x				); n .
S		f (x , x	2	,..., x	n	)		2	,..., x	n
	2	1					1

Теорема 2.4 (о классе S).

Пусть S (n) - множество функций класса S,которые зависят от n переменных. Тогда справедливы следующие утверждения:

1.S Ø;

2.S – замкнут (S = [S]);

3.S (n) 22n 1

4.[S] ≠ P2.

Доказательство.

1.Из определения двойственной функции

10

f * (x , x				def
	2	,..., x	n	)	f (x , x				2	,..., x		n	)
1					1

сразу следует, что для самодвойственной функции (f = f *) имеет место

f (x1 , x2 ,..., xn ) f (x1 , x2 ,..., xn ) или f (x1 , x2 ,..., xn ) f (x1 , x2 ,..., xn ) ,

т.е. всякая самодвойственная функция на противоположных наборах значений переменных принимает противоположные значения. Поскольку в таблице БФ противоположные наборы расположены симметрично относительно середины таблицы, то признаком самодвойственной функции является антисимметрия ее таблицы относительно середины таблицы, т.е. таблица всякой самодвойственной функции от n переменных имеет вид

f : f0 f1 f2 ... f2 f1 f0 .

Таким свойством обладает, например, таблица тождественной функции х. Поэтому

хпринадлежит классу S. Значит S Ø.

2.Рассмотрим произвольную совокупность функций класса S:

f n , g1m , g2m ,..., gnm S .

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

F( y , y	2	,..., y	m	) S n 1 ( f n , g m , g m ,..., g m )																										f n (g m ( y , y																	2		,..., y						m		),..., g m ( y , y								2	,..., y	m	)) .
1												1			2										n											1			1																									n 1
Тогда
F * ( y , y				2		,..., y		m		)		f n (g m ( y , y										2		,..., y				m			),..., g m								( y , y										2		,..., y						m			))
		1										1			1																							n 1
																									g m
Навесим по два отрицания на функции																												( y , y								2		,..., y					m			), i 1; n . Получим
																									i							1
F * ( y , y					2		,..., y		m		)		f n (g m ( y , y										2		,..., y				m			),..., g m ( y , y																		2		,..., y						m			)) .
		1										1			1																							n					1

Последовательно применяя теперь определение двойственной функции и, учитывая самодвойственность функций f n , g1m , g2m ,..., gnm , получим:

F * ( y , y

2

,..., y

m

) f n ((g m ( y , y

2

,..., y

m

))* ,..., (g m ( y , y

2

,..., y

m

))* )

1

1

1

n

1

f n (g m ( y , y

2

,..., y

m

),..., g m ( y

, y

2

,..., y

m

))

( f n )* (g m ( y , y

2

,..., y

m

),..., g m ( y , y

2

,..., y

m

))

1 1

n 1

1

1

n

1

f n (g m ( y , y

2

,..., y

m

),..., g m ( y , y

2

,..., y

m

)) F( y , y

2

,..., y

m

) .

1

1

n 1

1

Следовательно, F S. Тем самым S S . Обратное включение S S очевидное.

Таким образом,

S = [S] и класс S замкнут.

3. В силу отмеченного ранее свойства антисимметричности таблиц

самодвойственных функций их таблицы

однозначно

f : f0

f1

f2 ... f2n 1 1

f2n 1 1... f2 f1

f0

ДНФ( f ) : ДНФ( f ) позитивная)) .

11

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

( f0 , f1 , f2 ,..., f2n 1 1 ) первой половины таблицы. Длина этих наборов равна 2n-1. Поэтому

S (n)

B2n 1

22n 1 .

4. Конъюнкция ху S. Поэтому [S] ≠ P2 и теорема доказана.

Определение 2.5.

~

~

n

,

~

~

~

Пусть

, B

( 1 , 2 ,..., n ),

( 1 , 2 ,..., n ) . Набор

предшествует

~

~

набору ,если в каждой позиции компоненты набора не превышают компонент

~

~

~

набора .Обозначается этот факт

.Итак,

~

~

def

i : i

i .

i 1;n

Замечание 2.1. Отношение предшествования на булевом кубе Вn является обычным
отношением частичного порядка,поскольку рефлексивно,транзитивно и
антисимметрично (убедиться в этом самостоятельно).Это отношение на Вn не
					3		~	(0,1,0)	и	~
является линейным порядком.Например,на В наборы							1			1 (1,1,0)
		~	~		~		(0,1,1) и		~	(1,0,1)
сравнимы между собой (причем 1 1 ),а наборы						2			2
	~	~	и	~	~	~		~
несравнимы между собой,т.к. 2		2		2 2 . Если			,то будем говорить,что
~	~			~				~
набор «меньше»	набора (или набор				«больше» набора ).

Определение 2.6.

Булева функция f называется монотонной,если на «больших» наборах значений переменных она принимает не меньшие значения,т.е.

def		~	~	~	~
f = fn - монотонная	: ((		) ( f ( ) f ( ))) .
	~ ~	n
	, B

Определение 2.7.

Дизъюнктивная нормальная форма (ДНФ) булевой функции называется позитивной, если она не содержит отрицаний переменных.

Определение 2.8.

Множество монотонных булевых функций называется классом монотонных функций и обозначается М,т.е.

def	f P2	f монотонная .
М

Теорема 2.5 (критерий монотонности).

Булева функция f - монотонная тогда и только тогда,когда эта функция - функция-const или у нее существует позитивная ДНФ,т.е.

( f M ) ( f 1 f 0 (

Доказательство.

1. Необходимость ( ). Нужно доказать:

( f M ) ( f 1 f 0 ( ДНФ( f ) : ДНФ( f ) позитивная)) .

12

Воспользуемся методом математической индукции по количеству n существенных переменных функции.

База индукции. При n = 0 функция f является константой, т.е. f = 1 f = 0 и, тем самым, утверждение верное.

Предположение индукции.Пусть для всякой монотонной функции f, зависящей от n

=k существенных переменных, утверждение верное, т.е.

ДНФ( f ) : ( ДНФ( f ) позитивная) .

Шаг индукции. Пусть f = f (x1 , x2 ,..., xk , xk 1 ) зависит от k+1 существенной

переменной и является монотонной. В силу теоремы о дизъюнктивном разложении имеет место разложение f по переменной xk 1 :

f (x1 , x2 ,..., xk , xk 1 ) xk 1 f (x1 , x2 ,..., xk ,0) xk 1 f (x1 , x2 ,..., xk ,1) .

Рассмотрим функции

f0 (x1 , x2 ,..., xk )

f (x1 , x2 ,..., xk ,0)

и f1 (x1 , x2 ,..., xk , ) f (x1 , x2 ,..., xk ,1) .

~

~

В

k

;

~

,..., k ,

Покажем, что функции f0 и f1 – монотонные. Пусть

,

1 , 2

~

~

~

~

1 ,2 ,...,k ,i 1 , 2

~

, i {0,1}.

1

, 2 ,..., k и

. Тогда i

,..., k ,i i

В силу монотонности функции f :

~

~

~

~

fi ( ) f ( i

) f ( i ) fi

( ) . Следовательно,

функции f0

и f1 – монотонные. Покажем, что

f0 f1

1. Если f0 f1

1, то

~

k

:

~

~

f

~

B

f0 ( ) f1 ( ) 0 или

0 ( ) f0 1 ,2 ,...,k f 1 ,2 ,...,k ,0 1 и

~

f1 1 ,2 ,...,k f 1 ,2 ,...,k

,1 0 . Тогда f 1 ,2 ,...,k ,0 f 1 ,2 ,...,k ,1 ,

f1 ( )

что противоречит монотонности функции f.

Таким образом,

f0 f1 1. Имеем

далее

f (x1 , x2 ,..., xk , xk 1 ) xk 1 f (x1 , x2 ,..., xk ,0) xk 1 f (x1 , x2 ,..., xk ,1) = xk 1 f0 xk 1 f1

(xk 1 f0 xk 1 f1 )( f0 f1 ) (xk 1 f0 xk 1 f1 )( f0 f1 ) xk 1 f0 f1 xk 1 f0 f1 xk 1 f1 xk 1 f0 f1 xk 1 f1 f1 (xk 1 f0 xk 1 ) f1 ( f0 xk 1 ) .

Поскольку функции f0 и f1 – монотонные и зависят от k существенных переменных, то в силу предположения индукции у них существуют позитивные ДНФ. Используя их в последнем соотношении, придем к позитивной ДНФ для f. Шаг индукции доказан.

Вывод. f P2 : ( f M ) ( f 1 f 0 ( ДНФ( f ) : ДНФ( f ) позитивная)) .

2.	Достаточность ( ). Нужно доказать:
	( f 1 f 0 ( ДНФ( f ) : ДНФ( f ) позитивная)) ( f M ) .
Доказательство. Случаи f 1 f		0 очевидные. Пусть у функции f		f (x1 , x2 ,..., xn )
			~		n	. Если
существует позитивная ДНФ. Рассмотрим произвольный набор B
~	~	~	~	~		~
f ( ) 0	, то для всех наборов , таких, что		, неравенство f	( )		f ( )