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

f2 (x,t, y)

соответствующих наборам (0,0,0) и (1,0,0) , надо проставить значение g(0,0) = 0 , в

строках, соответствующих наборам (0,0,1) и (1,0,1) , - g(0,1) =1 , в строках,

соответствующих наборам (0,1,0) и (1,1,0) , - g(1,0) = 0 и, наконец, в строках,

соответствующих наборам (0,1,1) и (1,1,1) , - g(1,1) =1 .

Заготовим шаблон таблицы истинности функции f2 (x,t, y) (табл. 2.15), отведя первый столбец под значения переменной x , второй - под значения t , третий - под значения y ,

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

заполним, исходя из того, что на каждой паре наборов вида (a,0,b) и (a,1,b) значение

функции f2 должны совпадать со значением функции g(x, y) на наборе (a,b) .

Заготовим шаблон таблицы истинности функции f3 (x, y,t)

(табл. 2.16), отведя первый столбец под значения переменной x , второй - под значения y , третий - под значения t , четвертый - под значения самой функции. Столбец

значений функции f3 (x, y,t) заполним, исходя из того, что на каждой паре наборов вида

(a,b,0) и (a,b,1) значение функции									f3 должны совпадать со значением функции g(x, y)
на наборе (a,b) . ►
		Таблица 2.14								Таблица 2.15						Таблица 2.16
t	x		y		f1			x	t	y		f2		x	y		t	f3
0	0		0		0			0	0	0		0		0	0		0	0
0	0		1		1			0	0	1		1		0	0		1	0
0	1		0		0			0	1	0		0		0	1		0	1
0	1		1		0			0	1	1		1		0	1		1	1
1	0		0		0			1	0	0		0		1	0		0	0
1	0		1		1			1	0	1		0		1	0		1	0
1	1		0		0			1	1	0		0		1	1		0	0
1	1		1		0			1	1	1		0		1	1		1	0
Упражнение 2.8. Из						функции g(x, y) = (0010)					путем введения фиктивной переменной
t получить функции f1 (t, x, y) ,								f2 (x,t, y) ,		f3 (x, y,t) .

Упражнение 2.9. Найти функцию, зависящую существенным образом от всех своих аргументов и равную функции f (x, y, z,t) = (1100 0011 1100 0011 ).

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

Удаление фиктивных переменных упрощает дальнейшую работу с функцией. Однако в некоторых случаях фиктивные переменные полезно не удалять, а вводить. Дело в том, что, выполнив такую операцию неоднократно, можно перейти от данной функции к функции, которая ей равна и при этом зависит от любого наперед заданного числа переменных (большего исходного). Благодаря этому, рассматривая одновременно несколько функций, можно считать их зависящими от одного и того же множества переменных (в качестве такого множества можно взять объединение множеств переменных всех этих функций).

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

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

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

Например, при желании вместо системы функций f1 (x) = (10) , f2 (y) = (11) , f3 (x, y, z) = (10011101) можно рассматривать систему равных им функций

f1(x, y, z) = (11110000), f2 (x, y, z) = (11111111) , f3 (x, y, z) = (10011101) .

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

Пусть B - некоторое множество булевых функций, X - некоторое счетное множество переменных. Используя индукцию, определим множество формул над B с переменными из X . Одновременно будем определять числовую характеристику dep(Φ)

формулы Φ , называемую ее глубиной, а также множество ее подформул.

Определение. Базис индукции. Каждая переменная xi из X и каждая константа c

из B является формулой глубины 0, т.е. dep(xi ) = dep(c) = 0 . Множество подформул формулы глубины 0 состоит из нее самой.

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

Индуктивный переход. Пусть f (x1, x2 ,..., xn ) - функция из B, A1 , A2 ,..., An - формулы и max{dep(A1 ), dep(A2 ),..., dep(An )} = k . Тогда выражение Φ = ( f (A1, A2 ,..., An )) является формулой, ее глубина dep(Φ) равна k + 1, а множество подформул Φ включает саму формулу Φ и все подформулы A1 , A2 ,..., An .

Используя индукцию по глубине формулы, определим функцию, заданную формулой.

Определение. Базис индукции. Пусть dep(Φ) = 0 . Тогда Φ имеет вид Φ = xi , где xi -

переменная из X , или Φ = c , где c - константа из B. В первом случае Φ задает тождественную функцию xi , во втором - функцию, тождественно равную константе c .

Индуктивный переход. По предположению индукции каждой формуле глубины k сопоставлена некоторая функция. Пусть Φ(x1, x2 ,..., xn ) - произвольная формула глубины dep(Φ) = k +1 . Следовательно, она имеет вид Φ = ( f (A1, A2 ,..., An )), где f -

функция из B, A1 , A2 ,..., An - формулы, для которых max{dep(A1 ), dep(A2 ),..., dep(An )} = k ,

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

функции f1 (x1, x2 ,..., xn ) ,	f2 (x1, x2 ,..., xn ) ,…, fn (x1, x2 ,	..., xn ) . Тогда формула Φ задает
функцию g (x1, x2 ,..., xn ) =	= ( f ( f1 (x1, x2 ,..., xn ), f2 (x1, x2	,..., xn ),..., fn (x1, x2 ,..., xn ))) ,

значение которой на каждом наборе (α1,α2 ,...,αn ) находится как значение функции f

на наборе ( f1 (α1, α2 ,...,αn ),..., fn (α1,α2 ,...,αn )) .

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

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

Зададимся вопросом: можно ли по виду формулы, которой задана функция, определить, какие из переменных этой функции существенны, а какие фиктивны? Очевидно, если функция задана формулой, в которую некоторая переменная не входит, то эта переменная фиктивная. Обратное утверждение в общем случае неверно, т.е. в формуле, задающей функцию, могут присутствовать как существенные, так и фиктивные переменные этой функции. Убедимся в этом на примерах.

Пример 9. Указать существенные и фиктивные переменные функции

f(x1, x2 , x3 ) = (x3 → (x3 x2 )) → x1 .

◄Вначале упростим формулу, которой задается функция, используя равносильность

a → b = a b :

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

f(x1, x2 , x3 ) = (x3 → (x3 x2 )) → x1 =

=(x3 (x3 x2 )) → x1 = (1 x2 ) → x1 = 1 → x1.

Таким образом, значение функции определяется исключительно значением переменной x1 , причем f (1,0,0) =1→1 =1, f (0,0,0) = 0 →1 = 0. Значит, x1 - существенная, x2 , x3 -

фиктивные.►

Упражнение 2.10. Указать существенные и фиктивные переменные функции

	f (x1, x2 , x3 ) = x1x2 x3 x1x2 x3 x1x2 x3 x1x2 x3 .
	Задачи повышенной сложности
Назовем весом булева вектора число его координат, равных 1.
2.1. Сколько булевых векторов длины n имеет вес k?
Булевы векторы часто называют вершинами булева куба.								Расстоянием
	%		n					%
(Хэмминга) между вершинами α% и β куба B				называют число ρ(α%,β), равное числу
				%	n
						αi − βi		. Вершины (векторы) α%
координат, в которых они различаются, т.е. ρ(α%,β) = å
%	соседними, если	%		i=1				%
и β называют		ρ(α%,β) = 1, и противоположными, если ρ(α%,β) = n .
Например, расстояние между векторами (1,0,0,1,0) и (0,0,0,1,1)								равно 2. Расстояние
между векторами (0,0,1,0) и (1,0,1,0)		равно 1 и, значит, они соседние. Расстояние

между векторами (1,0,0,1,0,0) и (0,1,1,0,1,1) равно длине этих векторов, и,

следовательно, они противоположные.

2.2.Найти число неупорядоченных пар вершин булева куба Bn , удаленных друг от друга на расстояние k ( 0 ≤ k ≤ n ).

2.3.Показать, что для любых противоположных наборов α% и β% выполняется равенство v (α% ) + v (β%) = 2n −1 .

2.4.Подсчитать число функций от n переменных, у которых:

а) одна переменная фиктивная, остальные существенные;

б) k (1≤ k ≤ n ) переменных фиктивные, остальные - существенные.

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

2.5. Пусть B = { f , g, h} - подмножество булевых функций, причем f Î P2 (1) , g Î P2 (2) , hÎ P2 (3) и ни одна из функций не является тождественной константой, X = { x, y, z} -

алфавит переменных. Определить, является ли выражение A формулой над множеством B независимо от вида функций f , g, h :

а) A = h (x, x, f ( y)) ;		б) A = g ( f (z),0) ;
в) A = h(g (x, y), x, f (z)) ;		г) A = g (g (x, f (y)), x) ;
д) A = h ( f (x), g(y, z)) ;		е)	A = h (g (x), g(y),1) .
2.6. По функциям	f (x1, x2 )	и	g (x3 , x4 ) , заданным векторами значений, построить

векторы значений функции h :

а) f = (0111) , g = (0100) , h(x2 , x3 , x4 ) = f (g (x4 , x2 ), x3 ) ;

б) f = (1110) , g = (0001) ,

h(x1, x2 , x3 , x4 ) = g (g (x1, x4 ), f (x3 , x2 )) .

2.7. Указать существенные и фиктивные переменные функции

f (x1,..., xn ) = (x1 Ú x2 ) Å (x2 Ú x3 ) Å...Å (xn−1 Ú xn ) Å (xn Ú x1 ) ,

где n ³ 3 .

2.8. Выяснить, на скольких векторах булева куба B6 обращается в нуль функция:

а) f (x1, x2 ,..., x6 ) = x1x2 x3 Å x4 x5 x6 ;

б) f (x1, x2 ,..., x6 ) = x1x2 Ú x3 x4 Ú x5 x6 .

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

§ 2.2. Совершенные дизъюнктивные и конъюнктивные нормальные формы

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

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

1. Принцип двойственности. Функция, заданная формулой f (x1, x2 ,..., xn ) , называется

двойственной к функции f (x1, x2 ,..., xn ) .

Функцию, двойственную к f , обозначают f , таким образом,

f (x1, x2..., xn ) = f (x1, x2 ,..., xn ) .

Пример 1. Используя определение, найти функции, двойственные к дизъюнкции, конъюнкции и функциям одной переменной.

◄ Пусть f (x1, x2 ) = x1 x2 . Тогда

f * (x1, x2 ) =

=

x1 x2

x1 x2 = x1 x2 .

Пусть

f (x1, x2 ) = x1 x2 . Тогда

f * (x1, x2 ) =

=

x1 x2

x1 x2 = x1 x2 .

Пусть

f (x) = x . Тогда

f * (x) =

= x .

(x )

f (x) =

f * (x) =

= x .

Пусть

. Тогда

(

)

(x )

x

Пусть

f (x) = 0 . Тогда

f * (x) =

=1.

0

Пусть f (x) =1. Тогда f * (x) = 1 = 0 . ►

Сравним таблицы истинности произвольной функции f (x1, x2 ) и двойственной к ней функции f * (x1, x2 ) (табл. 2.17).

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

				Таблица 2.17
x1	x2	f (x1, x2 )				f * (x1, x2 )
0	0	f (0,0)			(
				f		0, 0) = f (1,1)
0	1	f (0,1)			(
				f		0,1)= f (1,0)
1	0	f (1,0)								)=						(0,1)
				f	(1,0								f
1	1	f (1,1)			(1,1) =										(0,0)
				f								f

Нетрудно заметить, что столбец значений функции f * можно получить из столбца значений функции f , действуя по следующему алгоритму:

1) столбец значений функции f переписать в обратном порядке (т.е. число, стоящее в первой строке, записать в последнюю строку; число, стоящее во второй строке, - в предпоследнюю строку и т.д.);

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

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

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

Пример 2. Задать вектором значений функцию, двойственную к данной:

а) f = (1101) ;		б) f = (1001 0000) .
◄ а)	f = (1101) a (1011) a f = (0100) ;
б) f	= (1001 0000) a (0000 1001) a f = (1111 0110) . ►
Упражнение 2.11		. Задать вектором значений функцию, двойственную к данной:
а) f = (0001 0110) ;б) f = (1001 0000 0101 1110) .
Упражнение 2.12		. Найти функции, двойственные к сложению по модулю два,

эквивалентности, штриху Шеффера и стрелке Пирса.

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

На примерах мы имели возможность убедиться, что отношение двойственности между функциями симметрично, т.е. если функция g = f , то функция f = g . Это утверждение несложно обосновать теоретически.

Действительно, пусть g (x1, x2 ,..., xn ) = f (x1, x2 ,..., xn ). Тогда

	g (x1, x2 ,..., xn ) = ( f (x1, x2 ,..., xn )) = (										(x1, x2 ,..., xn ))* =
										f
	=		(				2 ,...,		n ) = f (x1, x2 ,..., xn ).
		f
				x1,		x		x
Пусть функция	f задана формулой, и мы хотим построить формулу для двойственной
к ней функции	f *. Согласно определению, это можно сделать, заменив в формуле,
которой задана f , каждую переменную ее отрицанием и взяв отрицание от самой
формулы (именно так мы поступили в примере 1).

Рассмотрим другой способ построения формулы для						f по формуле, представляющей
f	. Этот способ основан на принципе двойственности: если формула Φ[ f1, f2 ,..., fn ]
задает функцию g , то формула, полученная из нее заменой символов функций
f	, f	2	,..., f	n	на символы двойственных к ним функций	f * , f * ,..., f * , задает функцию g* ,
1						1 2	n

двойственную к функции g . Полученную таким образом формулу будем называть

двойственной к Φ[ f1, f2 ,..., fn ] и обозначать Φ* [ f1, f2 ,..., fn ] .

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

Если функция задана формулой над множеством {0,1, x, x, x y, x y} , то, используя пример 1, принципу двойственности можно придать более конкретный вид: если в формуле Φ , представляющей функцию f , все конъюнкции заменить на дизъюнкции,

дизъюнкции - на конъюнкции, 1 на 0, 0 на 1, то получим формулу Φ* , представляющую функцию f , двойственную к f .

Пример 3. Задать формулой функцию, двойственную к данной:

а) f =		;	б) f = (x y ) yz 1.
	x zy

◄ а) f * = (x zy )* = x (z y ) .

Обратим внимание на следующее обстоятельство. В записи формулы, представляющей f , конъюнкция вследствие соглашения о краткой записи формул в скобки не взята.

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

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

б) f * = ((x y )

Упражнение а) f = xyz xyz

yz 1)* = (xy y z) 0 . ►

2.13. Задать формулой функцию, двойственную к данной:

; б) f = (x y 0)xy .

Если функции равны, то и двойственные к ним функции равны. В сочетании с

принципом двойственности это очевидное обстоятельство позволяет получать новые равносильности, переходя от равенства Φ1 = Φ2 к равенству Φ1 = Φ2 . Например, из равносильности 1 (см. теорему 2.1) можно получить равносильность 2, а из равносильности 2 - равносильность 1.

Действительно, от равенства x y = y x перейдем к равенству (x y) = (y x) и,

заменив дизъюнкцию на конъюнкцию, а конъюнкцию на дизъюнкцию, получим равенство x y = y x .

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

3 и 4, 5 и 6, 7 и 8, 9 и 10, 11 и 12, 13 и 14, 15 и 16, 17 и 18.

Пример 4. Задать функцию, двойственную к функции f (x, y, z) = zx (x ↓ y) :

а) вектором значений;				б) формулой.
◄ а) Начнем с того, что зададим таблично (табл. 2.18) саму функцию
f (x, y, z) = zx (x ↓ y) .
							Таблица 2.18
	x	y	z	z	zx	x ↓ y	f = zx (x ↓ y)
	0	0	0	1	0	1	1
	0	0	1	0	0	1	1
	0	1	0	1	0	0	0
	0	1	1	0	0	0	0

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

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

Далее: f = (11001010) a (01010011) a f = (10101100) .

б) Используя принцип двойственности и результат выполнения упр. 2.12, из формулы f (x, y, z) = zx (x ↓ y) получим формулу f (x, y, z) = (z x)(x y) . ►

Упражнение 2.14. Задать функцию, двойственную к функции f = (z ↔ x )(x 0):

а) вектором значений; б) формулой.

2. Задание функции совершенной дизъюнктивной нормальной формой. Мы умеем переходить от реализации функции формулой к заданию ее таблицей истинности. Не меньший интерес представляет обратный переход - от таблицы истинности к формуле. Этот переход неоднозначен - формул, которыми можно задать любую булеву функцию, бесконечно много. Особый интерес имеет задание функций через дизъюнкцию, конъюнкцию и отрицание.

Введем обозначения: x0 = x , x1 = x .

Каждую булеву функцию f от n переменных, за исключением тождественно равной нулю, можно задать формулой

f (x1, x2 ,..., xn ) =		(x1σ1 ... xnσn )
	(σ1,...,σn )
	f (σ1,...,σn )=1

(здесь дизъюнкция берется по всевозможным наборам значений переменных x1, x2 ,..., xn ,

на которых функция f равна 1).

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

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

Чтобы построить СДНФ функции, нужно действовать следующим образом:

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