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

Ниже перечислены булевы функции, которые наиболее часто употребляются и потому считаются «элементарными». Эти функции имеют собственные обозначения и названия:

1)g0 называется тождественным нулем и обозначается 0 ;

2)g1 называется тождественной функцией и обозначается по имени переменной (в

нашем случае x );

3)	g2	называется отрицанием x , обозначается x или ¬x и читается «не x »;
4)	g3	называется тождественной единицей и обозначается 1;
5)	f1	называется конъюнкцией, обозначается x Ù y или x & y , или x × y и читается « x и
y »;
6)	f6	называется сложением по модулю 2, обозначается x Å y	и читается « x плюс y »;
7)	f7	называется дизъюнкцией, обозначается x Ú y и читается	« x или y »;

8)f8 называется стрелкой Пирса, обозначается x ¯ y ;

9)f9 называется эквивалентностью, обозначается x ↔ y и читается « x эквивалентно

(равносильно) y »;

10) f13 называется импликацией, обозначается x → y и читается « x имплицирует

(влечет) y ».

11) f14 называется штрихом Шеффера и обозначается x y .

Символы Ø, Ù, Ú, Å, ¯, «, ®, , с помощью которых обозначают элементарные

функции, называются логическими связками.

Для удобства дальнейшего изложения приведем таблицы истинности элементарных функций с учетом введенных обозначений (табл. 2.5 и 2.6).

Таблица 2.5

x	0	1	x	x
0	0	0	1	1
1	0	1	0	1

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

Таблица 2.6

x	y	x y	x Å y	x y	x ↓ y	x ↔ y	x → y	x		y
0	0	0	0	0	1	1	1	1
0	1	0	1	1	0	0	1	1
1	0	0	1	1	0	0	0	1
1	1	1	0	1	0	1	1	0

3. Задание булевых функций формулами. Для задания булевых функций, помимо таблиц, используют формулы, которые обычно строят по «принципу матрешек», вкладывая друг в друга символические обозначения функций. Говоря о формуле, часто указывают, с использованием каких функций она строилась. В некоторых случаях нужно указывать и то, какие использовались переменные.

Например, ((x1 x2 ) → (x2 x3 )) - формула над множеством функций, состоящим из дизъюнкции, импликации и штриха Шеффера с переменными из множества {x1, x2 , x3} ,

а ((x2 (¬x1 )) ↔ x1 ) - формула над множеством функций, состоящим из конъюнкции,

отрицания и эквивалентности, с переменными из множества {x1, x2 } .

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

Например, ((x1 x1 ) ↔ (x2 (¬x2 ))) - формула над множеством функций, состоящим

из конъюнкции, дизъюнкции и эквивалентности, с переменными из множества {x1, x2 } ,

а (x1 x1 ) , (¬x2 ), (x2 (¬x2 )) - подформулы этой формулы.

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

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

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

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

а) f (x1, x2 ) = ((x2 (¬x1 )) ↔ x1 );

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

◄ а) Пошаговое построение таблицы истинности функции f (x1, x2 ) = ((x2 (¬x1 )) ↔ x1 )

приведено в табл. 2.7.

					Таблица 2.7
	x1	x2	¬x1	x2 (¬x1 )	((x2 (¬x1 )) ↔ x1 )
	0	0	1	0	1
	0	1	1	1	0
	1	0	0	0	0
	1	1	0	0	0
Вектор значений функции			f (x1, x2 )	= (1000) .

б) Пошаговое построение таблицы истинности функции f (x1, x2 , x3 ) = ((x1 x2 ) → (x2 x3 )) приведено в табл. 2.8.

							Таблица 2.8
x1	x2	x3	x1 x2	x2		x3	((x1 x2 ) → (x2		x3 ))
0	0	0	0	1			1
0	0	1	0	1			1
0	1	0	1	1			1
0	1	1	1	1			1
1	0	0	1	0			0
1	0	1	1	1			1
1	1	0	1	1			1
1	1	1	1	1			1

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

Вектор значений функции f (x1, x2 , x3 ) = (1111 0111) . ►

Упражнение 2.3. Построить таблицу истинности и выписать вектор значений функции, заданной формулой:

а) f (x1, x2 , x3 ) = (((x2 ¯ x1 ) Ú x3 ) Å x1 );

б) f (x1, x2 , x3 ) = ((1 (x1 Ù x3 ))Å (0 ¯ x2 )).

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

Для обозначения формулы над множеством функций B={ f1, f2 ,..., fk } используют запись F[ f1, f2 ,..., fk ] или F[B] . Если хотят обратить внимание на то, что при написании формулы использовались переменные x1, x2 ,..., xn , то пишут Φ(x1, x2 ,..., xn ) .

Запись f = F[B] означает, что формула F[B] задает функцию										f .
Функция f , заданная формулой над множеством функций								{	1	2	}
									f , f		,... , называется
суперпозицией функций			{	1	, f	2	}
				f			,... .
Для упрощения записи формул разрешается опускать у формул внешние скобки,
вместо ¬f писать		; опускать символ конъюнкции « » (« & »,«× »), т.е. вместо f Ù g (
	f
f & g , f × g ) писать		f g . Чтобы сократить число скобок в формуле, среди операций

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

Например, согласно введенным договоренностям, формулу (x1 ↔ (x2 (¬x1 ))) можно записать в виде x1 ↔ x2 x1 . Составляя таблицу истинности функции, заданной этой формулой, сначала следует найти отрицание x1 , затем конъюнкцию x2 и x1 и только затем эквивалентность x1 и x2 x1 .

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

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

а) x (y (x y)) ;

б) ((x y) (x ( y z))) → ((x y ) z) .

Одну и ту же функцию можно задать разными формулами. Покажем это на примерах.

Пример 5. Показать, что формулы x xy и x y задают одну функцию.

◄ Обозначим функцию, заданную первой формулой, f1 , а функцию, заданную второй формулой, - f2 (табл. 2.9).

					Таблица 2.9
x	y	x	xy	f1 = x xy	f2 = x y
0	0	1	0	1	1
0	1	1	0	1	1
1	0	0	0	0	0
1	1	0	1	1	1

Сравнив последние два столбца таблицы, убедимся, что функции f1 и f2 на одинаковых векторах принимают равные значения. ►

Упражнение 2.5. Показать, что формулы x → y и x y задают одну функцию.

Если формулы Φ1 и Φ2 задают одну функцию, то их называют равносильными и пишут

Φ1 = Φ2 .

Например, x xy = x y , x → y = x y (см. пример 5 и упражнение 2.5).

Теорема 2.1. Для формул над множеством {0,1, , ,¬} имеют место следующие

равносильности:

1. x y = y x ;

2. x y = y x ;

3. x ( y z) = (x y) z ; 4. x ( y z) = (x y) z ;

5.x ( y z) = (x y) (x z) ;

6.x ( y z) = (x y) (x z) ;

7. x x = x ;

8. x x = x ;

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

9.

x y

=

x

y

;

10.

x y

=

x

y

;

11.

x 0 = x ;

12.

x 0 = 0 ;

13.

x 1 = x

14.

x 1 = 1 ;

15.

x (x y) = x ;

16. x (x y) = x ;

17. x x = 0 ;

18.

x x = 1 ;

19.

= x .

x

Доказательство. Чтобы доказать любую из равносильностей

1 - 19, нужно

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

Из табл. 2.10 и 2.11 видно, что формулы	x y	и x y	задают равные функции,
следовательно, они равносильны.
Таблица 2.10			Таблица 2.11

x	y	x y
				x y
0	0	0		1
0	1	0		1
1	0	0		1
1	1	1		0

x	y	x	y	x y
0	0	1	1	1
0	1	1	0	1
1	0	0	1	1
1	1	0	0	0

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

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

■

Равносильности 1 - 19 характеризуют свойства дизъюнкции, конъюнкции и отрицания: 1 и 2 - коммутативность, 3 и 4 - ассоциативность, 5 - дистрибутивность конъюнкции относительно дизъюнкции, 6 - дистрибутивность дизъюнкции относительно конъюнкции, 7 и 8 - идемпотентность. Равносильности 9 и 10 называют законами де Моргана, 11 и 12 - законами нуля, 13 и 14 - законами единицы, 15 и 16 - законами поглощения, 17 и 18 - законами отрицания, 19 - законом двойного отрицания.

Ассоциативность конъюнкции и дизъюнкции позволяет дополнить договоренности об упрощенной записи формул договоренностью опускать скобки в случае многократного последовательного применения только дизъюнкции или только конъюнкции.

Например, формулу x ( y z) можно записать в виде x y z . В дальнейшем будем также употреблять следующие обозначения:

n		= x	x	... x	и	n		= x	x	... x .
x						x
i=1	i	1	2	n		i=1	i	1	2	n

До сих пор мы доказывали равносильность формул следующим образом: по каждой формуле восстанавливали таблицу функции, после чего полученные таблицы сравнивали. Есть и другой подход - использование равносильных преобразований. Он основан на том, что результат вычисления значения функции по формуле не зависит от того, как получены значения переменных, входящих в формулу (брались они произвольно, как значения независимых переменных, или были получены в результате каких-то вычислений). В частности, равносильности 1 - 19 (см. теорему 2.1) остаются справедливыми при подстановке вместо переменных любых формул. Важно лишь соблюдать следующее правило: при подстановке в равносильность вместо некоторой переменной формулы Φ все вхождения этой переменной в исходное равенство должны быть одновременно заменены формулой Φ . Например, используя равносильность

x xy = x y (см. пример 5), можно записать новые равносильности x xy = x y ( x

заменено на x ) и y y x = y x ( x заменено на y , а y на x ), а используя равносильность x y = x y - равносильность x y = x y ( x заменено на x , а y на y

).

Таким образом, действует принцип: если A - подформула формулы Φ , то при замене в формуле Φ любого вхождения A на равносильную ей формулу A1 формула Φ переходит в равносильную ей формулу Φ1 .

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

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

Пример 6. Применяя равносильные преобразования, упростить формулу:

а) y xyz xyz ; б) (x ® y)Ú (x ® y ) .

◄ а) y Ú xyz Ú xyz = y Ú (xyz Ú xyz ) =

æ ö

=y Ú xyç {z Ú z ÷ = y Ú xy = y Ú x ; è =1 ø

б) (x ® y) Ú (x ® y ) = (x Ú y) Ú (x Ú y ) =

= x Ú y Ú x Ú y = (x Ú x ) Ú ( y Ú y ) = x Ú1 = 1. ►

Упражнение 2.6. Применяя равносильные преобразования, упростить формулу:

а) (x ®		)Ú		;	б)		(x Ú		).
	y		x Ú y			x Ú y		xy
					Теоретические обоснования

Есть булевы функции, которые не меняют своих значений при изменении значений некоторых своих переменных. Например, на значение функции f3 (см. табл. 2.4) не влияет значение переменной y , поскольку f3 (0,0) = f3 (0,1) , f3 (1,0) = f3 (1,1) , а на значение функции f5 не влияет значение переменной x , поскольку f5 (0,0) = f5 (1,0) , f5 (0,1) = f5 (1,1) . Переменные, значения которых не влияют на значения функции,

называют фиктивными. Определим это понятие строго.

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

если на всех наборах a1 ,..., ai−1 , ai+1,..., an значений переменных x1 ,..., xi−1 , xi+1 ,..., xn

выполняются равенства

f (a1,..., ai−1 ,0, ai+1 ,...an ) = f (a1 ,..., ai−1 ,1, ai+1 ,...an ) .

В противном случае переменная xi называется существенной, т.е. переменная xi

называется существенной переменной функции f (x1,..., xn ) , если найдется такой набор a1 ,..., ai−1 , ai+1,..., an значений переменных x1 ,..., xi−1 , xi+1 ,..., xn , что

f (a1,..., ai−1 ,0, ai+1 ,...an ) ¹ f (a1 ,..., ai−1,1, ai+1,...an ) .

Чтобы определения фиктивной и существенной переменных легче было усвоить, адаптируем их к каким-нибудь частным случаям. Например, определим y как

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

фиктивную переменную функции f (x, y, z) : переменная y называется фиктивной переменной функции f (x, y, z) , если выполняются четыре равенства: f (0,0,0) = f (0,1,0) , f (0,0,1) = f (0,1,1) , f (1,0,0) = f (1,1,0) , f (1,0,1) = f (1,1,1) .

Теперь определим y как существенную переменную функции f (x, y, z) : переменная y

называется существенной переменной функции f (x, y, z) , если хотя бы одно из

равенств f (0,0,0) = f (0,1,0) , f (0,0,1) = f (0,1,1) , f (1,0,0) = f (1,1,0) , f (1,0,1) = f (1,1,1) не выполняется.

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

Операция удаления (введения) фиктивных переменных. Пусть для функции f (x1, x2 ,..., xn ) переменная xi является фиктивной. Возьмем таблицу истинности функции f . Вычеркнем из нее все строки, в которых xi = 1, а также вычеркнем столбец переменной xi . Полученная таким образом таблица будет задавать некоторую функцию g (x1,..., xi−1, xi+1,..., xn ) , причем на любом наборе

α1,..., αi−1 , αi , αi+1 ,..., αn значений переменных x1,..., xi−1, xi , xi+1,..., xn для функций f и g выполнено равенство f (α1,...,αi−1,αi , αi+1,..., αn ) = g (α1,..., αi−1, αi+1,..., αn ) . О функции g говорят, что она получена из функции f путем удаления фиктивной переменной, а о функции f говорят, что она получена из функции g путем введения фиктивной переменной.

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

Пример 7. Найти фиктивные переменные функции и удалить их:

а) f (x, y) = (0011) ; б) f (x, y, z) = (11011101) .

◄ а) Для наглядности рассуждений построим таблицу истинности функции (табл. 2.12).

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

x : f (0,0) ¹ f (1,0) , следовательно, x - существенная;

y : f (0,0) = f (0,1) и f (1,0) = f (1,1) , следовательно, y - фиктивная.

Чтобы удалить фиктивную переменную y , нужно вычеркнуть из таблицы истинности функции второй столбец, а также третью и пятую строки (они закрашены серым цветом). В результате получим таблицу истинности функции g(x) = (01) , равной функции f (x, y) = (0011) .

б) Построим таблицу истинности функции (табл. 2.13).

Таблица 2.13 x : f (0,0,0) = f (1,0,0) , f (0,0,1) = f (1,0,1) ,

Таблица 2.12
x	y	f
0	0	0
0	1	0
1	0	1
1	1	1

								f (0,1,0) = f (1,1,0) , f (0,1,1) = f (1,1,1) , следовательно, x -
	x		y		z		f
								фиктивная;
0			0		0		1
								y :	f (0,0,0) ¹ f (0,1,0) , следовательно, y - существенная;
0			0		1		1
								z :	f (0,0,0) = f (0,0,1) ,	f (0,1,0) ¹ f (0,1,1) , значит, z -
0			1		0		0
								существенная.
0			1		1		1
								Чтобы удалить фиктивную переменную x , нужно
1			0		0		1	вычеркнуть из таблицы истинности функции первый столбец
1			0		1		1	и последние четыре строки (они закрашены серым цветом). В
								результате получим таблицу истинности функции
1			1		0		0
								g(y, z) = (1101) , равной функции f (x, y, z) = (11011101) . ►
1			1		1		1
								Упражнение 2.7. Найти фиктивные переменные функции
	и удалить их:
	а)	f (x, y, z) = (01011111) ;							б) f (x, y, z) = (00110011) .
	Пример 8. Из функции g(x, y) = (0100) путем введения фиктивной переменной t
	получить функции f1 (t, x, y) ,								f2 (x,t, y) , f3 (x, y,t) .
	◄ Заготовим шаблон таблицы истинности функции f1 (t, x, y) (табл. 2.14), отведя
	первый столбец под значения переменной t ,									второй - под значения x , третий - под
	значения y , четвертый - под значения самой функции.
	Значение функции						f1 (t, x, y) на каждой паре наборов вида (0, a,b) и (1, a,b) должны

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

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