DisMathTPU

31

Упр.4. Двойственны ли формулы Ff è Gg? Функции f è g?

1)

Ff = x y x z y z

Gg =

_

_

,

x

y

x

z

y

z

2)

Ff = x y # x z,

Gg = (x _ y)=(x _ z),

3)

Ff = (

x

!

y

) ! (y ! x), Gg = (x ! y)(

y

!

x

).

Упр.5. Показать, что f = g.

1)

Ff =

3)

Ff = x y z,

xyz _ x(y z),

'g = 10010111,

Fg = x y z,

2)

Ff = xy _ xz _ yz,

4)

Mf1 = f0101; 0110; 1001; 1010g,

Fg = xy _ xz _ yz,

I1 = 0 0

Ig = I1; I2; I3; I4 ,

I2 = 1 1

f

g

I3 =

0 0

I4 = 1 1

6. Контрольная работа 1

Тема контрольной работы: булевы функции, фиктивные перемен-

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

Ff

по определению

0

?

по определению

двойственной функции

двойственной формулы

3

(F )f

4

?

?

1

?

(F 0)f

#таблица

(F )f

00

000

истинности

?

f

?

Ff0

"

! Ff

#

2

?

10

истинности f

100

-

таблица

"

5

!

удалить

#таблица

фиктивные переменные

?

истинности f

"

!

Схема контрольной работы (решение каждой из десяти предложен-

ных здесь задач начинать с постановки задачи и делать вывод из сравнения таблиц истинности функции f , полученных разными способами; F обозна-

чает формулу без лишних скобок, (F ) с недостающими скобками).

32

Задания на контрольную работу (формула Ff )

1) x ! y		! (z
			xy)
2) x		(z
	y		xy)

3)x=y=(z xy)

4)z ! y ! (x zy)

5)x ! y ! (z xy)

16)x ! y ! (y xz)

17) y		(z
	y		xy)

18)x=y ! (z xy)

19)z ! xy ! (x z)

20)x ! xy ! (z y)

6) xz # y=(y x)

7) z y (x y)

8)x _ z # y=(y x)

9)xz ! y # (y x)

10)xz y ! (x y)

21)z xy ! (x # y)

22)xz # y=x(y z)

23)x _ yz # (y x)

24)z # xy (x ! z)

25)xy # x=(x y)

11)y z ! y(x # z)

12)x z ! x(y=z)

13)xy _ z=(x ! z)

14)y z ! y(x=z)

15)x ! z=x(y # z)

26)y zy=y(x # z)

27)x=z ! y(x # z)

28)x=z ! y(x ! z)

29)x z ! y(x=z)

30)x ! y=x(y # z)

Пример. Задана формула

Ff = z y (x yz):

0) Расставим недостающие скобки в формуле Ff . Возьмем в скобки конъюнкцию, затем остальные подформулы слева направо.

(F )f = (z y) (x (yz)):

1), 2) Построим таблицу истинности функции f(x; y; z) по формуле (F )f . Получим таблицу истинности двойственной функции f (x; y; z) по таблице истинности функции f(x; y; z), переворачивая и инвертируя столбец значений функции f(x; y; z).

x y z			(z y)		(			(			f(x; y; z)	f (x; y; z)
						x			yz))
0	0	0	0	0	1		1	0			0	1
0	0	1	1	1	1		1	1			1	0
0	1	0	1	1	1		1	0			1	0
0	1	1	0	0	1		1	0			0	1
1	0	0	0	0	0		1	0			0	1
1	0	1	1	1	0		0	1			1	0
1	1	0	1	1	0		1	0			1	0
1	1	1	0	0	0		1	0			0	1
			2	5	3		4	1

3) По определению двойственной функции получим из формулы (F )f

формулу двойственой функции (F 0)f , инвертируя переменные и саму функцию f. Упростим формулу (F 0)f , заменив инверсию функции обратной импликации на не обратную импликацию.

(F 0)f = (z y) (x (yz)) = (z y) - (x (yz)):

33

00) Уберем лишние скобки в формуле (F 0)f вокруг конъюнкции и первой слева функции ( ).

Ff0 = z y - (x yz):

10) Построим таблицу истинности двойственной функции f (x; y; z)

по формуле Ff0							.							f (x; y; z)
	x y z								- (x				)
					z			y			yz
0		0	0	1		0	1		1	1	0			1
0		0	1	0		1	1		0	1	0			0
0		1	0	1		1	0		0	0	1			0
0		1	1	0		0	0		1	1	0			1
1		0	0	1		0	1		1	1	0			1
1		0	1	0		1	1		0	1	0			0
1		1	0	1		1	0		0	1	1			0
1		1	1	0		0	0		1	1	0			1
				2		4	3		6	5	1

4) Построим формулу, двойственную (F )f . Заменим в формуле (F )f

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

(F )f = (z y) ,! (x ,! (y _ z)):

000) Уберем лишние скобки в формуле (F )f . Опустим скобки вокруг первой слева функции ( ).

Ff = z y ,! (x ,! (y _ z)):

100) Построим таблицу истинности двойственной функции f (x; y; z) по формуле Ff .

x y z			z		y ,	(x ,			(y			z))	f (x; y; z)
					!			!			_
0	0	0		1	1	1		0	1		1		1
0	0	1		0	0	1		0	1		1		0
0	1	0		0	0	1		1	0		0		0
0	1	1		1	1	1		0	0		1		1
1	0	0		1	1	0		0	1		1		1
1	0	1		0	0	0		0	1		1		0
1	1	0		0	0	0		0	0		0		0
1	1	1		1	1	0		0	0		1		1
				1	6	2		5	3		4

Вывод. Таблицы истинности функции f (x; y; z) èç 2), 10), 100) совпадают, значит, все задачи решены верно (кроме, может быть, задачи 0).

34

5) Удалим фиктивные переменные функции f (x; y; z) в ее таблице ис-

тинности. Так как вес столбца значений функции четный, то переменные функции могут быть фиктивными. Рассмотрим переменную x. Верхняя половина столбца значений функции f (x; y; z) (1001) равна нижней половине

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

тинности столбец x и все строки, в которых x принимает значение 0. y z f (y; z)

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

В полученной таблице истинности верхняя половина столбца значений функции f (y; z) (10) не равна нижней половине (01), значит, переменная y ñó-

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

7. Разложение булевой функции по переменным и совершенные нормальные формы

7.1. Разложение Шеннона

Рассмотрим следующее разложение булевой функции f(x1; : : : ; xn) по переменной xi.

Разложение Шеннона.

f(x1; : : : ; xn) = xif(x1; : : : ; xi 1; 1; xi+1; : : : ; xn) _ _xif(x1; : : : ; xi 1; 0; xi+1; : : : ; xn):

Доказательство (не умаляя общности, для i = 1). Ïðè x1 = 0 имеем: f(0; x2; : : : ; xn) = 0f(1; x2; : : : ; xn) _ 0f(0; x2; : : : ; xn) = f(0; x2; : : : ; xn):

Ïðè x1 = 1 имеем:

f(1; x2; : : : ; xn) = 1f(1; x2; : : : ; xn) _ 1f(0; x2; : : : ; xn) = f(1; x2; : : : ; xn):

Следовательно, разложение верно.

Определение. Сомножитель f(x1; : : : ; xi 1; 1; xi+1; : : : ; xn) называется

коэффициентом разложения функции f(x1; : : : ; xn) по переменной xi ïðè xi, а сомножитель f(x1; : : : ; xi 1; 0; xi+1; : : : ; xn) коэффициентом разложения функции f(x1; : : : ; xn) по переменной xi ïðè xi.

35

Пример. Булеву функцию f(x; y; z) = y x z ! y z разложим по переменной x:

y x z ! y z = x(y 1 z ! y z) _ x (y 0 z ! y z) =

[ упростим коэффициенты разложения на основе свойств 0 и 1 для конъюнкции ]

= x(y z ! y z) _ x (y 0 ! y z) =

[ продолжим упрощение коэффициента при x на основе свойства 0 для эквивалентности a 0 = a ïðè a = y; напомним, что способ получения таких свойств был рассмотрен в подразделе 4.4 ]

=x(y z ! y z) _ x (y ! y z);

âрезультате имеем следующие коффициенты разложения, зависящие лишь от y è z:

y z ! y z коэффициент разложения функции f(x; y; z) по переменной x ïðè x,

y ! y z коэффициент разложения функции f(x; y; z) по переменной x ïðè x.

7.2. Разложение функции по k переменным

Разложим функцию f(x1; : : : ; xn) последовательно по двум переменным: сначала саму функцию по переменной x1, затем коэффициенты разложе- ния по переменной x2.

f(x1; : : : ; xn) = x1f(1; x2; : : : ; xn) _ x1f(0; x2; : : : ; xn) = = x1[x2f(1; 1; x3; : : : ; xn) _ x2f(1; 0; x3; : : : ; xn)] _

_ x1[x2f(0; 1; x3; : : : ; xn) _ x2f(0; 0; x3; : : : ; xn)] =

[раскроем скобки по закону дистрибутивности ]

=x1x2f(1; 1; x3; : : : ; xn) _ x1x2f(1; 0; x3; : : : ; xn) _ _ x1x2f(0; 1; x3; : : : ; xn) _ x1x2f(0; 0; x3; : : : ; xn):

Введем обозначения: x = x1, x = x0 (условимся читать символы xc êàêx в степени c ). Тогда разложение функции f(x1; : : : ; xn) по переменным x1, x2 в свернутой форме примет вид

f(x1; : : : ; xn) =			x1c1x2c2f(c1; c2; x3; : : : ; xn):
c c2			2
1	_
		2B

36

Пример. Продолжим разложение функции f(x; y; z) из предыдущего примера. Мы уже получили ее разложение по x:

f(x; y; z) = y x z ! y z = x(y z ! y z) _ x (y ! y z):

Разложим теперь коэффициенты по переменной y:

x [y(1 z ! 1 z) _ y(0 z ! 0 z)] _ x [y(1 ! 1 z) _ y(0 ! 0 z)] =

[используем свойства 0 и 1 и раскроем квадратные скобки ]

=x [y(0 z ! z) _ y(1 z ! 0)] _ x [y(1 ! z) _ y(0 ! 0)] =

=x y(z ! z) _ x y(z ! 0) _ x y z _ x y =

=x y(z ! z) _ x y z _ x y z _ x y:

Решим теперь тот же пример, но не последовательным применением разложения Шеннона, а непосредственно по формуле разложения функции по двум переменным.

Пример. Найдем коэффициенты разложения Шеннона булевой функции f(x; y; z) = y x z ! y z по переменным x è y:

f(1; 1; z) = 1 1 z ! 1 z = 0 z ! z = z ! z;

f(1; 0; z) = 0 1 z ! 0 z = 1 z ! 0 = z ! 0 = z; f(0; 1; z) = 1 0 z ! 1 z = 0 0 ! z = 1 ! z = z; f(0; 0; z) = 0 0 z ! 0 z = 1 0 ! 0 = 0 ! 0 = 1:

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

f(x; y; z) = x1 y1f(1; 1; z) _ x1 y0f(1; 0; z) _ x0 y1f(0; 1; z)_ _x0 y0f(0; 0; z) = x y(z ! z) _ x y z _ x y z _ x y:

Заметим, что в данном случае оба способа привели к одинаковым формулам. В общем случае формулы могут не совпадать, но они с очевидностью равносильны, ибо задают одну функцию.

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

Разложение функции по k переменным.

f(x1; : : : ; xn) = _ xc11 : : : xckk f(c1; : : : ; ck; xk+1; : : : ; xn):

c1:::ck2Bk

Доказательство. Подставим в левую и правую части равенства произвольный набор a1 : : : an:

f(a1; : : : ; an) = _ ac11 : : : ackk f(c1; : : : ; ck; ak+1; : : : ; an):

c1:::ck2Bk

37

Для упрощения правой части докажем сперва вспомогательный резуëüòàò: ac = 1 тогда и только тогда, когда a = c. Действительно, 00 = 0 = 1,

11 = 1, íî 01 = 0, 10 = 1 = 0. Следовательно, конъюнкция ac11 : : : ackk = 1 тогда и только тогда, когда a1 : : : ak è c1 : : : ck совпадают. Это означает, что конъюнкция не обращает в ноль лишь одно слагаемое правой части, для которого c1 = a1; : : : ; ck = ak, и разложение имеет вид:

f(a1; : : : ; an) = aa11 : : : aakk f(a1; : : : ; ak; ak+1; : : : ; an) = f(a1; : : : ; an):

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

Разложив булеву функцию f(x1; : : : ; xn) ïî k переменным при k = n,

получим

f(x1; : : : ; xn) = _ xc11 : : : xcnnf(c1; : : : ; cn):

c1:::cn2Bn

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

либо набор c1 : : : cn 2 Mf0, тогда f(c1; : : : ; cn) = 0, и поэтому обращается в 0 соответствующее слагаемое правой части;

либо набор c1 : : : cn 2 Mf1, тогда f(c1; : : : ; cn) = 1, и слагаемое упроща-

åòñÿ.

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

f(x1; : : : ; xn) =	_		x1c1 : : : xncn:
1			f
c :::cn		2	M1

Пример. Найдем коэффициенты разложения той же булевой функции f(x; y; z) = y x z ! y z по всем переменным (для удобства наборы

c1 : : : cn 2 Bn будем перебирать в естественном порядке): f(0; 0; 0) = 0 0 0 ! 0 0 = 1 0 ! 0 = 0 ! 0 = 1,

f(0; 0; 1) = 0 0 1 ! 0 1 = 1 0 ! 0 = 0 ! 0 = 1, f(0; 1; 0) = 1 0 0 ! 1 0 = 0 0 ! 0 = 1 ! 0 = 0, f(0; 1; 1) = 1 0 1 ! 1 1 = 0 0 ! 1 = 1 ! 1 = 1, f(1; 0; 0) = 0 1 0 ! 0 0 = 1 1 ! 0 = 1 ! 0 = 0, f(1; 0; 1) = 0 1 1 ! 0 1 = 1 0 ! 0 = 0 ! 0 = 1, f(1; 1; 0) = 1 1 0 ! 1 0 = 0 1 ! 0 = 0 ! 0 = 1, f(1; 1; 1) = 1 1 1 ! 1 1 = 0 0 ! 1 = 1 ! 1 = 1.

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

f(x; y; z) = x y z _ x y z _ x y z _ x y z _ x y z _ x y z:

38

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

Определение. Совершенная дизъюнктивная нормальная форма функ- öèè f(x1; : : : ; xn) (СовДНФf ) это формула вида

_xc11 : : : xcnn:

c1:::cn2Mf1

Из данной формулы с очевидностью вытекает следующее утверждение.

Утверждение о единственности совершенной ДНФ. Любая булева функция, кроме константы 0, представима cовершенной дизъюнктивной нормальной формой, единственной для данной функции.

Алгоритм построения совершенной ДНФ по таблице истинности (основан на определении совершенной ДНФ).

Начало: задана таблица истинности булевой функции.

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

Шаг 2 : по набору значений аргументов выбранной строки формируется конъюнкция всех аргументов с соблюдением правила: если i-я компонента

набора равна 0, то i-я переменная входит в конъюнкцию в степени 0 (с

инверсией), иначе в степени 1 (без инверсии). Полученная конъюнкция добавляется в формулу как очередное слагаемое. Идем на шаг 1.

Конец.

Пример. Применим алгоритм к той же функции (с переименованными аргументами) f(x1; x2; x3) = x2 x1x3 ! x2x3.

x1 x2 x3			f(x1; x2; x3)	x10x20x30 =
0	0	0	1			1		2		3
					x		x		x
0	0	1	1	x10x20x31 =		1		2x3
					x		x
0	1	0	0	x10x21x31 =
0	1	1	1			1x2x3
					x
1	0	0	0	x11x20x31 = x1
1	0	1	1					2x3
							x
1	1	0	1	x11x21x30 = x1x2						3
									x
1	1	1	1	x11x21x31 = x1x2x3

Соединив полученные конъюнкции знаками дизъюнкции, имеем СовДНФf = x1x2x3 _ x1x2x3 _ x1x2x3 _ x1x2x3 _ x1x2x3 _ x1x2x3:

39

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

Решение обратной задачи, то есть построение таблицы истинности по совершенной ДНФ, очевидно: степени переменных конъюнкций совершенной ДНФ задают наборы, на которых функция принимает значение 1. Это гораздо проще, чем построение таблицы истинности по совершенной ДНФ как по произвольной формуле.

7.4. Совершенная конъюнктивная нормальная форма

Пусть задана булева функция f(x1; : : : ; xn). Представим ее инверсию f(x1; : : : ; xn) совершенной ДНФ (учтем, что Mf1 = Mf0):

f(x1; : : : ; xn) = _ xc11 : : : xcnn = _ xc11 : : : xcnn

1		0
c1:::cn2M		c1:::cn2Mf
	f

Проинвертируем обе части этого равенства:

f(x1; : : : ; xn) = _ xc11 : : : xcnn

c1:::cn2Mf0

По законам двойного отрицания и де Моргана имеем:

= c1

_ : : : _

:

f(x1

; : : : ; xn) = c1:::cn

x1c1 : : : xncn

x1c1

M0

:::cn

M0

xncn

^

f

^

f

2

2

= x

. Действительно,

Заметим, что

c

xc

= x = x1 = x

;

=

= x0 = x

:

=

0

1

x0

x1

x

x

Учитывая это, получаем следующее представление функции f(x1; : : : ; xn):

	^ x	1c	1 _ : : : _ x
f(x1; : : : ; xn) =				ncn :

c1:::cn2Mf0

Определение. Совершенная конъюнктивная нормальная форма функ- öèè f(x1; : : : ; xn) (СовКНФf ) это формула вида

^ xc11 _ : : : _ xcnn :

c1:::cn2Mf0

Из данной формулы с очевидностью вытекает следующее утверждение.

Утверждение о единственности совершенной КНФ. Любая булева функция, кроме константы 1, представима cовершенной конъюнктивной нормальной формой, единственной для данной функции.

40

Алгоритм построения совершенной КНФ по таблице истинности (вытекает из определения совершенной КНФ).

Начало: задана таблица истинности булевой функции.

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

Шаг 2 : по набору значений аргументов выбранной строки формируется дизъюнкция всех аргументов с соблюдением правила: если i-я компонен-

та набора равна 0, то i-я переменная входит в дизъюнкцию в степени 1

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

Конец.

Пример. Применим алгоритм к рассмотренной в предыдущих примерах функции f(x1; x2; x3) = x2 x1x3 ! x2x3.

x1 x2 x3			f(x1; x2; x3)
0	0	0	1
0	0	1	1	x11 _ x20 _ x31 = x1 _
0	1	0	0					2 _ x3
							x
0	1	1	1	x10 _ x21 _ x31 =
1	0	0	0			1 _ x2 _ x3
					x
1	0	1	1
1	1	0	1
1	1	1	1

Соединив полученные дизъюнкции знаками конъюнкции, имеем

СовКНФf = (x1 _ x2 _ x3)(x1 _ x2 _ x3):

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

7.5. Упражнения

Упр.1. Выполнить разложения функций f1 f4 по указанным подмно-

жествам переменных двумя способами (последовательным применением разложения Шеннона и непосредственно по формуле разложения функции k по переменным):

f1(x; y; z; t) = (x _ y z t)(y ! x y z _ (x _ z)) ïî fx; tg; fy; zg, f2(x; y; z; t) = (x ! y z)(y t z) ! x t _ x ïî fxg; fy; z; tg,