Bulevy_funktsii_Polnye_sistemy_BF

13

~

выполняется независимо от того, какое значение принимает f на наборе . Если же

~

xi

...xi

,

f ( ) 1 , то в позитивной ДНФ(f ) существует элементарная конъюнкция xi

~

~

1

2

k

на местах с номерами

принимающая на наборе

значение 1. Тогда в наборе

~

~

~

~

i1 ,i2 ,...,ik стоит 1. Для всякого набора

, такого, что

, в наборе

на местах с

~

номерами i1 ,i2 ,...,ik тогда тоже должна стоять 1. Но тогда на таком наборе

отмеченная ранее элементарная конъюнкция xi

xi

...xi будет также равна 1 и,

~

1

2

k

~

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

~

f ( ) = 1. Таким образом, и в этом случае неравенство

f ( ) f

( )

~

~

~

выполняется для всякого набора , такого, что

. В итоге, для функции f

имеет место

~

~

~

~

- монотонная.

: (

) ( f ( ) f ( )) , т.е. функция f

~ ~

n

, B

Достаточность доказана.

Теорема 2.6 (о классе М).

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

1.М Ø;

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

	n / 2			n / 2		n!
3.	2Сn		М (n)	3Сn	, где C k			.
					n	k!(n k)!
4.	[М] ≠ P2.

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

1.Функции-константы 0 и 1 монотонные, т.е. 0 М и 1 М. Значит М Ø.

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

f n , g1m , g2m ,..., gnm М .

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

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

~

~

m

,

~

~

,..., m )

Выберем два произвольных набора

, B

( 1 , 2 ,..., m ),

( 1 , 2

~

~

~

и F

~

таких, что

. Рассмотрим значения

F ( )

( ) , и сравним их. Имеем:

~

n

m ~

m ~

~

f

n

m

~

m

~

F ( ) = f

(g1 ( ),..., gn ( )) ;

F( )

(g1

( ),..., gn

( )) .

~

m m

m

~

~

m ~

m

~

m ~

m

Поскольку g1 , g

2

,..., gn

М и

, то

g1

( )

g1 ( ) ; …;

gn

( ) gn

( ) .

m

~

m

~

m

~

m

~

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

(g1

( ),..., gn ( )) . Тогда, учитывая монотонность

f

n

, получим

f

n

m

~

m ~

n

m

~

m

~

~

~

(g1

( ),..., gn

( )) f

(g1

( ),..., gn

( )) . Таким образом, F ( )

F ( ) ,

т.е. F( y1 , y2 ,..., ym ) - монотонная.

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

М = [М]

и класс М замкнут.

n / 2

n / 2

n!

3.

2Сn

М

(n)

3Сn

,

где C k

(без доказательства).

n

k!(n k)!

4. Функция отрицание х не является монотонной, а потому [М] ≠ P2.

14

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

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

С помощью функций f0 и f1, несохраняющих соответственно 0 и 1, и тождественной функции х могут быть построены либо обе константы,либо одна из констант и функция отрицание, либо функция отрицание. Иначе:

f		T			0,1 f0 , f1 ;
				const, x f0 , f1 ;
	0	0
f1		T1			x	f					.
									0	, f
										1

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

1.Используя функцию f0, построим новую функцию (х) от одной переменной, отождествив все переменные функции f0 с х:

(x) S n 1 ( f0n , x,..., x) f0 (x, x,..., x) .

Поскольку f0 T0, то (0) 1. Для (1)				возможны два случая: либо (1) =0, либо
(1) =1. Имеем:
(0) 1
			(х) х ;
									f0 ;
(1) 0							х
	(0)	1							f0 .
			(х) 1.				1
	(1)	1

2. Если же воспользоваться функцией f1, то аналогично предыдущему можно построить функцию (х) от одной переменной, отождествив все переменные

функции f1 с х:
(x) S n 1 ( f n , x,..., x) f						(x, x,..., x) .
		1		1
Поскольку f1 T1, то (1) 0 . Для (0)					возможны два случая: либо (0) =0, либо
(0) =1. Имеем:
(1) 0
	(х) х ;
						х f					;
(0)	1									1
									f1		.
(1)	0	(х)		0.		0
(0)	0

Объединяя теперь полученные результаты, заключаем:

f0 f1

			0,1 f								0	, f		;
												1
T			0,							f , f				;
							x
0											0		1
T1			1,						f0 , f1 ;
						x
				x f , f .
				0								1

и, тем самым, лемма доказана.

15

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

С помощью несамодвойственной функции,тождественной функции х и функции отрицания может быть построена функция константа,т.е.

f s S const { f s , x} .

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

Пусть fs – несамодвойственная функция ( f s S ). Тогда существует такой набор

			~						~
							, что			f		~			f s (x1 , x2 ,..., xn ) . Имеем:
значений переменных									f ( )		( ) . Пусть f s
~										1	1			1	1			2		n		) ;
fs ( ) fs (1 ,2 ,...,n ) fs (1											,2			,...,n ) fs	(1		,1		,...,1
	~		( 1 , 2							0	0			0	(0	1		2		,...,0	n		) .
fs ( ) fs							,..., n ) fs ( 1 , 2							,..., n ) fs				,0

Используя функцию fs и полученные выше соотношения, построим новую функцию

(х) от одной переменной (x) fs(x 1 , x 2 ,..., x т ) . Тогда

~~

(0) f s ( ) f s ( ) (1) .

Таким образом, построенная функция (х) - это функция-const (0 или 1 неважно). Лемма доказана.

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

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

~	~		def	~ ~
(1 ,...,i 1 ,0,i 1 ,...,n )		(1 ,...,i 1 ,1,i 1 ,...,n )		, соседние .

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

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

f

M

~

~

~

~

~

~

M

~

: [( ,

соседние) (

) ( f ( )

f ( ))].

~

n

, B

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

~

Пусть f M

M . Тогда существует такая пара наборов значений переменных

~

~

~

и f M

~

~

и , что

( )

f M ( ) . Последнее неравенство выполняется только в том

случае, когда

~

~

. Не ограничивая общности, будем считать, что

f M ( ) 1 , а f M ( ) 0

~

~

~

~

наборы

и

различаются в первых k компонентах. Тогда, поскольку

, в

~

~

они равны 1, т.е.

наборе

эти компоненты равны 0,

а в наборе

~

~

(0,...,0,k 1 ,...,n ) и (1,...,1, k 1 ,..., n ) .

~

~

так, чтобы в полученной последовательности

Вставим (k – 1) набор между

и

наборов любые два рядом расположенных набора были соседними и каждый набор последовательности предшествовал ниже расположенным наборам. Имеем:

~

(0,0,...,0,0,k 1 ,...,n ) ;

~

~1 (1,0,...,0,0,k 1 ,...,n ) ;2 (1,1,...,0,0,k 1 ,...,n ) ;

	16
………………………….
~		;
k 1 (1,1,...,1,0,k 1 ,...,n )
~	(1,1,...,1,1, k 1 ,..., n ) .

~

Поскольку на начальном наборе последовательности (наборе ) функция

~

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

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

Лемма доказана.

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

С помощью констант,тождественной функции х и немонотонной функции может быть построена функция отрицание,т.е.

					fM M			1,0, fM .
							x
Доказательство.
Поскольку				f M	M , то в силу Леммы 3.3 существует пара соседних двоичных
наборов			~				~		~	и
			(1	,...,i 1 ,0,i 1 ,...,n ) и ( 1 ,..., i 1 ,1, i 1 ,..., n ) таких, что f M					( ) 1
~
f M ( ) 0			. Используя функцию fМ построим новую функцию (х) от одной
переменной (x)					fM (1 ,...,i 1 , x,i 1 ,...,n ) . Тогда (0) 1, а (1) = 0.
Таким образом, построенная функция (х) - это функция-отрицание, т.е.
(х) = x .
Лемма доказана.

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

С помощью нелинейной функции,констант и,может быть,функции отрицания

может быть построена функция конъюнкция,т.е.
f L L		xy 0,1, x, f L .

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

Поскольку f L L , то в многочлене Жегалкина для этой функции существует

хотя бы одно слагаемое, содержащее конъюнкцию каких-то переменных. Не ограничивая общности, будем считать, что такими переменными являются x1 и x2 .

Сгруппируем слагаемые многочлена Жегалкина, содержащие конъюнкцию x1 x2 и вынесем эту конъюнкцию за скобки. Затем сгруппируем слагаемые, содержащие x1 и не содержащие x2 , и вынесем x1 за скобки. Аналогично поступим со слагаемыми, содержащими x2 . Все оставшиеся слагаемые объединим в одну группу. Получим

f L (x1 , x2 ,..., xn ) x1 x2 f1 (x3 , x4 ,..., xn ) x1 f2 (x3 , x4 ,..., xn ) x2 f3 (x3 , x4 ,..., xn ) f4 (x3 , x4 ,..., xn ) .

Заметим, что f1 (x3 , x4 ,..., xn ) не является константой 0 (т.е. является функцией выполнимой) ибо в противном случае многочлен Жегалкина не содержал бы

конъюнкцию x1 x2 , а это бы противоречило условию. Следовательно, существует
~	,4 ,...,n ) , на котором f1 (3 ,4 ,...,n ) = 1. Пусть
такой набор (3
f2 (3 ,4 ,...,n ) a ,	f3 (3 ,4 ,...,n ) b , f4 (3 ,4 ,...,n ) c . Тогда:

17

f L (x1 , x2 ,3 ...,n ) x1 x2 ax1 bx2 c (x1 , x2 ) .

Имеем далее:

(x1 , x2 ) (x1 b, x2 a) ab c (x1 b)(x2 a) a(x1 b) b(x2 a) ab = x1 x2 .

Таким образом, (x1 , x2 ) x1 x2 и лемма доказана.

Теорема 3.1 (Критерий Поста полноты системы БФ).

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

( R g1 , g2 ,..., gk	P2 )	(	К		: R K).
		K T0 ,T1,L,S ,M
Доказательство.
1. Необходимость. Нужно доказать:
( R P2 )	(	К	: R K).
	K T0 ,T1,L,S ,M
Докажем контрапозицию (от противного). Пусть утверждение К							: R K
						K T0 ,T1,L,S ,M
неверное. Тогда верным будет утверждение			К			: R K . Тогда, в силу свойств
		K T0 ,T1,L,S ,M

замыкания,

[R] [K] . Но каждый из замечательных классов не является полным ( [K]≠P2 ) и поэтому [R] ≠ P2. Контрапозиция, а вместе с ней необходимость теоремы доказана.

2. Достаточность. Нужно доказать:
(		К	: R K ) ( R P2 ) .
	K T0 ,T1,L,S ,M
Условие К		: R K означает, что (R T0 ) (R T1 ) (R L) (R S) (R M) ,
K T0 ,T1,L,S ,M

т.е. среди функций R есть хотя бы одна несохраняющая ноль функция f0 , хотя бы одна несохраняющая единицу функция f1 , хотя бы одна нелинейная функция f L , хотя бы одна несамодвойственная функция f S , хотя бы одна немонотонная функция f M . Выберем эти функции. Ясно, что f0 , f1 , f L , f S , f M R . Воспользуемся

теперь результатами доказанных ранее лемм 3.1; 3.2; 3.3; 3.5. Результаты сведем в таблицу (при этом стрелки передают словосочетание «будет получено множество функций», а над стрелками стоит обоснование такого получения):

0,1

fM

, Лемма

3.3

0,1,

f L ,Лемма

3,5

0,1,

, ху ;

х

х

Лемма

3.1

f

,Лемма

3,5

fo , f1

const,

x

0,1,

х

L

0,1,

х

, ху ;

x

fS , Лемма 3.2

х

, const 0,1,

f L

,Лемма 3,5

0,1,

, ху .

x

х

18

Таким образом, исходя из системы функций f0 , f1 , f L , f S , f M , может быть построена система 0,1, х, ху . Иными словами, 0,1, х, ху [ f0 , f1 , f L , f S , f M ].

Система 0,1, х, ху - полная, т.к. содержит полную подсистему х, ху . Поскольку

f0 , f1 , f L , f S , f M R, то

[ f0 , f1 , f L , f S , f M ] [R]. В итоге имеем:

х, ху 0,1, х, ху [ f0 , f1 , f L , f S , f M ] [R].

Но тогда

P2 [ х, ху ] [[R]] = [R], т.е. P2 [R].

Обратное включение [R] P2 очевидное. Поэтому [R] = P2 и достаточность теоремы

доказана.

Теорема доказана полностью.

Замечание 3.1.

Можно дать другую (эквивалентную предложенной ранее) формулировку критерия Поста полноты системы булевых функций,а именно:

Система булевых функций полна тогда и только тогда,когда она содержит хотя бы одну функцию f0 ,несохраняющую ноль; хотя бы одну функцию f1 ,

несохраняющую единицу; хотя бы одну нелинейную функцию f L ; хотя бы одну несамодвойственную функцию f S ; хотя бы одна немонотонную функцию f M ; т.е.

		f0 : f0 R f0 T0 ;
		f1 : f1 R f1 T1 ;
R P2		f L : f L R f L L;
		f S : f S R f S S;
	f		M	: f	M	R f	M	M .

Следствие .

Всякий замкнутый класс R,отличный от Р2,содержится по крайней мере в одном из пяти замечательных классов.

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

Воспользуемся тем, что (F = G ) ( F G ). Тогда утверждение теоремы Поста равносильно утверждению

R P2		К	: R K
		K T0 ,T1,L,S ,M
И следствие доказано.

Теорема 3.2.

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

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

В силу критерия Поста из всякой полной системы R можно выделить полную подсистему из пяти функций f0 , f1 , f L , f S , fM . Для функции f0 возможны два

19

					~	0
варианта: ее значения на единичном наборе значений переменных – либо f0 (1)							,
~		не сохраняет 1, т.е. f0 можно использовать в
либо f0 (1) 1. В первом случае f0
качестве f1 и тогда система f0 ,	f L	, f S , f M	- полная. Во втором случае f0 можно
использовать в качестве fS (т.к.		~	~	~	~
	f0 (0) f		0 (1) ) и	fМ (т.к. f0 (0)	f0 (1) ) и тогда
система f0 , f1 , f L - полная. Теорема доказана.

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

Класс R булевых функций называется предполным (максимальным), если он неполный и f R : R f P2 .

Теорема 3.3.

В алгебре логики (в теории БФ) существуют только пять предполных (максимальных) классов,а именно T0 ,T1 , L, S, M .

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

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

T0

T1

L

S

M

T0

0

xy

0

x + y

T1

1

xy

1

1 + x + y

L

1

0

0

x + y

S

1

xy+xz+yz

х

х

M

0

xy

0

х

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

2) Докажем, что все замечательные классы являются предполными. Пусть R T0 ,T1 , L, S, M и f R. Тогда система R { f } - полная (поскольку R не входит в

остальные четыре класса, а f R). Следовательно [R { f }] = P2 и R – предполный класс.

3) Пусть R – некоторый предполный класс. Тогда, в силу следствия критерия Поста

H T0 ,T1 , L, S, M : R H . Если R≠H, то f : f R f H . Тогда (R f ) H , а значит [R f ] [H ] . Но H P2 . Следовательно [R f ] P2 , что противоречит

предполности класса R. Таким образом, R =H . Тем самым теорема доказана полностью.

20

Замечание 3.2.

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

Пример. Выяснить, является ли полной система

R f1 xy x z y xz; f 2 x xz y ; f3 x y z; f 4 x y z .

В случае неполноты R дополнить ее до полной системы и из полученной полной системы выделить всевозможные базисы.

Решение.

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

суперпозиций) в них следующий: , , , , , .

1) Для f1 проведем распределение по классам на основании ее таблицы. Таблицу f1 можно строить, используя таблицы Квайна или на основании нормальных форм (ДНФ, СДНФ, КНФ, СКНФ). Построим СДНФ(f1). Имеем:

f1

xy x

y

x

y

z

xy( x

y

z

xz

xy

z

x

z

xz)

x

x

y

x

xy( x

y

x

xy

xz

y

z

z

z

xz)

y

z

xz y

x y y z xy x yz x yz x y z xyz xyz = СДНФ(f1).

Тогда таблица

f1: 10111100. Из таблицы сразу видно, что f1 Т0

(т.к.

~

1 );

f 0

~

0 ); f1 S (таблица f1 не является антисимметрической

f1 Т1 (т.к. f 1

~

~

~

~

относительно своей середины); f1 M (т.к. f 0 1

> 0 = f 1 , а

0

1 ). По СДНФ(f1)

легко построить многочлен Жегалкина и сделать выводы о принадлежности f1 классу L. Имеем:

f1 = x yz x yz x y z xyz xyz x yz x yz x y z xyz xyz

x( y 1)(z 1) x( y 1)z (x 1)( y 1)(z 1) (x 1) y(z 1) (x 1) yz

1 z xy xz yz xyz = НФЖ(f1). Поэтому f1 L.

2) Для f2 распределение по классам выполним аналитически. Имеем: f2 x xz y x xz y x(xz y) x (1 x)z 1 y x(1 y)

1 y z xy xz = НФЖ(f2).

21

Следовательно, f2 Т0 (в многочлене Жегалкина присутствует слагаемое 1); f2 Т1 (в многочлене Жегалкина нечетное количество слагаемых); f2 L. На основании многочлена Жегалкина легко построить двойственную функцию. Имеем:

f2* = 1 y z x y x z 1 1 1 y 1 z (1 x)(1 y) (1 x)(1 z) y z 1 x y xy 1 x z xz xy xz .

НФЖ(f2) ≠ НФЖ(f2*). Следовательно, f2 S. Осталось проверить принадлежность f2 классу М. Воспользуемся критерием монотонности. Имеем:

f2 x xz y x xz y xzy x (x z) y xyz x x y y z xyz x y z yz .

Построенная ДНФ(f2) неупрощаемая, а потому имеет неустранимые отрицания. Значит, позитивной ДНФ у f2 не существует. Следовательно, f2 М.

3) Для f3 распределение по классам выполним аналитически. Имеем:

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

Тогда f3 Т0, f3 Т1, f3 L, f3 М.

f3 * x x y x z x y z 1 1 x (1 x)(1 y) (1 x)(1 z) (1 x)(1 y)(1 z)

xy xyz НФЖ( f3 *) f3 .

Следовательно, f3 S.

4) Для f4 распределение по классам выполним аналитически. Имеем:

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

Тогда f4 Т0, f4 Т1, f4 L.

f4 * x yz x yz xy z x y(1 z) xy(1 z) x y xy yz xyz f4 .

Следовательно, f4 S. Далее:

f4 x y z x( y z) xy xz ДНФ( f4 ) с неустранимым отрицанием

(непозитивная). Таким образом, f4 М. Сведем полученные результаты в таблицу:

		T0	T1	L	S	M
	f1	-	-	-	-	-
	f2	-	+	-	-	-
	f3	+	-	-	-	-
	f4	+	+	-	-	-

(здесь «+» означает, что расположенная в строке функция принадлежит классу, определяющему столбец таблицы, а «-» - не принадлежит). Из таблицы видно, что исходная система функций не входит ни в один из пяти замечательных классов (в каждом столбце таблицы есть по крайней мере один «-»). Следовательно, в силу критерия Поста, система полная. Система содержит собственные полные подсистемы (например, {f1,f2,f3}, {f2, f3,f4}, {f1,f4} и другие). Из них базисными являются подсистемы {f1}, {f2,f3}.

22

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

Распределить по замечательным классам (аналитически и по таблицам):

f2 x y

f3 x / y z

x;

f1 x yz x z;

x z

;

y

f6 x y z

;

f4 x yz xy;

f5 x y z y;

x

f7 x y

y;

f9 x y z

;

z

f8 x y z y;

x

f10 x

y z ;

f11 x / y z

f12 x y z

;

y

x

;

y

f13 x y z y;

f15 x y z y;

f14 xy z x;

f16 x / y y

xz ;

f17

x

z ;

x y

y

f18 x y z y z;

Предварительные результаты:

f

ДНФ( f )

НФЖ( f )

НФЖ( f* )

Таблица f

f1

1 x yz

x y z yz

x y x z xyz

11100001

1 y xy xz

1 z xy xz

f2

x y x z

11001010

1 yz xyz

x xy xz xyz

f3

x y z

11101111

1 x y yz xyz

y xy xz xyz

f4

x y x z xy

11010011

1 y yz xyz

1 x y xy xz xyz

f5

x z y

11011100

f6

1 x xz

z xz

11110101

x z

1 y xz yz xyz

y z xy xyz

f7

yz x y y z

11011001

x yz

1 x y z yz

f8

x y x z x yz

00011110

1 x xz xyz

1 x y xy yz xyz

f9

x y z

11110100

1 y z xy yz

x y xy yz

f10

xy y z

10001011

1 x xz xyz

1 x y xy yz xyz

f11

x y z

11110100

f12

1 x y z xy

z xz

xz yz x y z

10010101