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

1)выбрать в таблице истинности функции все наборы значений переменных, на которых функция равна 1;

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

3)записать дизъюнкцию всех выписанных в п. 2 конъюнкций.

Пример 5. Задать функцию в виде СДНФ:

а) x1 → x2 ;	б) x1		x2 ;
в) x1 ↓ x2 ;			г)	f (x, y, z) = (11001010) .

◄ а) - в) Зададим функции таблично (табл. 2.19) и выпишем для них СДНФ.

						Таблица 2.19
x1	x2	x1 → x2	x1		x2		x1 ↓ x2
0	0	1	1				1
0	1	1	1				0
1	0	0	1				0
1	1	1	0				0

x1 → x2 = x1x2 x1x2 x1x2 ; x1 x2 = x1x2 x1x2 x1x2 ;

x1 ↓ x2 = x1x2 .

г) Запишем СДНФ, воспользовавшись таблицей истинности функции

f (x, y, z) = (11001010) (см. табл. 2.18):

f = x y z x y z x y z x y z . ►

Упражнение 2.15. Задать функцию f = (01011011) в виде СДНФ.

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

Рассмотрим еще один способ задания функции формулой над множеством, состоящим из дизъюнкции, конъюнкции и отрицания.

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

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

формулой

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

f (τ1,...,τn )=0

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

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

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

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

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

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

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

3)записать конъюнкцию всех выписанных в п. 2 дизъюнкций.

Пример 6. Задать функцию в виде СКНФ:

а) x1 → x2 ;	б) x1		x2 ;
в) x1 ↓ x2 ;			г)	f (x, y, z) = (11001010) .

◄ а) - г) Опираясь на таблицы истинности функций (см. табл. 2.19 и 2.18), запишем:

а) x1 → x2 = x1 x2 ;

б) x1 x2 = x1 x2 ;

в) x1 ↓ x2 = (x1 x2 )(x1 x2 )(x1 x2 );

г) f = (x y z)(x y z )(x y z )(x y z ). ►

Упражнение 2.16. Задать функцию f (x, y, z) = (01011011) в виде СКНФ.

Каждая булева функция может быть задана формулой над множеством B = { , ,¬} .

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

A2 ,…, An

Действительно, если f ≡ 0 , то f можно задать в виде СКНФ. Если f ≡/ 0 , то f можно задать в виде СДНФ.

Теоретические обоснования

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

Теорема 2.2 (принцип двойственности). Если формула Φ[ f1, f2 ,..., fn ] задает функцию g , то формула Φ [ f1, f2 ,..., fn ] , полученная из нее заменой символов функций

f1 , f2 ,..., fn на символы двойственных к ним функций f1* , f2* ,..., fn* , задает функцию g* ,

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

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

Базис индукции.	Пусть dep(Φ) = 0 . Тогда Φ имеет вид Φ = xi , где xi - переменная из
X , или Φ = c , где c	- константа из B. В первом случае двойственная формула имеет

вид Φ = (xi ) , во втором - Φ = (c) . В обоих случаях двойственная формула реализует функцию, которая двойственна к функции, заданной формулой Φ .

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

Произвольная формула глубины k + 1 в соответствии с индуктивным определением формулы может быть записана в виде Φ = ( f (A1, A2 ,..., An )), где f - функция из B, A1 ,

- формулы такие, что max{dep(Ai )} = k . Причем, согласно определению

1≤i≤n

функции, заданной формулой, всем формулам A1 , A2 ,..., An сопоставлены соответственно некоторые функции f1 (x1,..., xn ) , f2 (x1,..., xn ) ,…, fn (x1,..., xn ) , а

формуле Φ - функция g (x1,..., xn ) = f ( f1 (x1,..., xn ), f2 (x1,..., xn ),..., fn (x1,..., xn )) , значение которой на каждом наборе (α1,α2 ,...,αn ) находится как значение функции f на наборе

( f1 (α1, α2 ,...,αn ),..., fn (α1,α2 ,...,αn )) .

Используя определение двойственной функции, зададим формулой функцию, двойственную к g :

g* (x1,..., xn ) = g (x1,..., xn ) =

= f ( f1 (x1,..., xn ),..., fn (x1,..., xn )) =

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

(

=

f1 (x1,..., xn ),...,

fn (x1,..., xn ))=

f

æ

ö

ç

÷

=

f ç

( f 1 (x1,..., xn )),....,( f n (x1,..., xn ))

÷

=

ç

1442443

1442443

÷

ç

*

*

÷

è

f1

fn

ø

(

(x1,..., xn ),...,

(x1,..., xn ))= = f * ( f1* (x1,..., xn ),..., fn* (x1,..., xn )).

=

f1*

fn*

f

Поскольку глубина каждой из формул A1 , A2 ,..., An не превышает k , то для этих формул

выполнено предположение индукции, и, значит, функции		f , f		,..., f реализуются
		1	2		n
формулами, двойственными к формулам A , A ,..., A , т.е.		f	(x ,..., x ) = A			(x ,..., x ) (
1 2	n	i	1	n	i	1	n

i =1,..., n ). Но тогда g (x1,..., xn ) = f * (A1* (x1,..., xn ),..., An* (x1,..., xn )), и, значит, g (x1,..., xn ) = F (x1,..., xn ) . ■

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

Теорема 2.3 (о разложении функции по переменным). Каждую булеву функцию f (x1, x2 ,..., xn ) при любом m (1£ m £ n) можно задать формулой

Ú	(x1σ1 Ù x2σ2 Ù ... Ù xmσm Ù f (s1,...,sm , xm+1,..., xn ))
(σ1,σ2 ,...,σm )

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

).

Доказательство. Напомним, что	x	σ	ìx при s = 0,	0			1	= 1 ,
			= í	Следовательно, 0	= 0 =1, 1
			î x при s =1.

10 = 1 = 0 , 01 = 0 , т.е. xσ =1 тогда и только тогда, когда x = σ .

Возьмем произвольный набор (a1,a2 ,...,an ) значений переменных и найдем на этом наборе значение функции, заданной доказываемой формулой:

Ú	(a1σ1 Ù aσ22 Ù ... Ù aσmm Ù f (s1,...,sm ,am+1,...,an )) =
(σ1,σ2 ,...,σm )

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

æ

ö

= çaa1

Ù aa2

2

Ù ... Ù aamm

Ù f (a1,...,am ,am+1,...,an )÷

Ú

ç 144424443

÷

è

=1

ø

æ

ö

Ú

ç

(s

Ú

)

as1 Ù ... Ù asm Ù f

s ,...,s

,a

m+1

,...,a

÷

=

ç

,...,s

( 1

m

( 1 m

n ))÷

ç

(s

1

m

)

1444444442444444443

÷

,...,s

)¹(a ,...,a

A

è

1

m

1

m

ø

= f (a1,..., am , am+1,..., an ) .

Поясним последний переход: если ((s1,...,sm ) ¹ (a1,..., am )), то хотя бы при одном i ai ¹ si и, значит, aisi = 0 , следовательно, A = 0 .

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

f (x1, x2 ,..., xn ) =	Ú	(x1s1 Ù x2s2 Ù ... Ù xmsm Ù f (s1,...,sm , xm+1,..., xn )).■
	(s1,s2 ,...,sm )

В качестве примера приведем разложение функции f (x1, x2 ,..., xn ) :

а) по переменной x1 :

f (x1, x2 ,..., xn ) = (x1 Ù f (1, x2 ,..., xn )) Ú (x1 Ù f (0, x2 ,..., xn ));

б) по переменным x1, x2 :

f = (x1 Ù x2 Ù f (0,0,..., xn ))Ú (x1 Ù x2 Ù f (0,1,..., xn ))Ú

Ú (x1 Ù x2 Ù f (1,0,..., xn ))Ú (x1 Ù x2 Ù f (1,1,..., xn )).

Теорема 2.4 (о задании функции в виде СДНФ). Каждую булеву функцию f от n

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

f (x1, x2 ,..., xn ) =	Ú	(x1s1 Ù ... Ù xnsn ).
	(s1,...,sn )
	f (s1,...,sn )=1

Доказательство. Запишем разложение функции f (x1, x2 ,..., xn ) по всем переменным и преобразуем его:

f (x1, x2	,..., xn ) =		Ú			(x1s1	Ù ... Ù xnsn Ù f (s1,...,sn )) =
		(s1,...,sn )
æ			æ				s	ö	ö
ç	Ú		s						÷	Ú
= ç			ç x1	1	Ù ... Ù xn n Ù f (s1,...,sn )÷				÷
ç	(s1,...,sn )		ç				142443	÷	÷
è f (s1,...,sn )=1			è				=1	ø	ø

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

æ		æ			ö	ö
ç	Ú	ç x1σ1	Ù ... Ù xnσn Ù f (s1	,...,sn )÷		÷	=
Úç						÷
ç	(σ1,...,σn )	ç	142443		÷	÷
è f (σ1,...,σn )=0		è		=0	ø	ø

=	Ú	(x1σ1 Ù...Ù xnσn ). ■
	(σ1,...,σn )
	f (σ1,...,σn )=1

Теорема 2.5 (о задании функции в виде СКНФ). Каждую булеву функцию f , не равную тождественно единице, можно задать формулой

f (x1, x2 ,..., xn ) = (τ1,Ù...,τn ) (x1τ1 Ú ...Ú xnτn ).

f (τ1,...,τn )=0

Доказательство. Представим функцию f * , двойственную к f , в виде СДНФ:

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

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

выражения

xσi остаются неизменными, поскольку они представляют собой либо x ,

i

i

либо xi ):

( f * )* =

Ù

(x1σ1 Ú ...Ú xnσn )=

=

Ù

(x1σ1 Ú ...Ú xnσn )

=

Ù

(x1σ1 Ú ...Ú xnσn ) =

(σ1,...,σn )

(σ1,...,σn )

(σ1,...,σn )

f *(σ1,...,σn )=1

(,σ1...,σn )=1

f (,σ1...,σn )=0

f

Ú ...Ú x

)

=

Ù

x

τ1

τn

.

σ1=τ1,

(τ1,...,τn ) (

1

n

L

f (τ1,...,τn )=0

σn =τn

Так как ( f

*) = f , формула доказана. ■

Задачи повышенной сложности

2.9. Пусть функция f (x1, x2 ,..., xn )

задана вектором значений (α1, α2 ,..., α2n ) . Показать,

что f * (x1, x2 ,..., xn )

задается вектором (α2n ,...,α2 ,α1 ).

2.10. Показать, что если функция

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

существенно зависит от переменной

xi ( i =1,..., n ) , то двойственная к ней функция

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

также существенно зависит

от переменной xi .

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

2.11. Подсчитать число дизъюнктных слагаемых, образующих СДНФ функции

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

2.12. Пусть множества X = { x1, x2 ,..., xn } и Y = { y1, y2 ,..., ym } не пересекаются и пусть СДНФ функций f (x1, x2 ,..., xn ) и g ( y1, y2 ,..., ym ) имеют соответственно k и p

дизъюнктных слагаемых. Найти число дизъюнктных слагаемых в СДНФ функций:

а) f (x1, x2 ,..., xn ) × g ( y1, y2 ,..., ym ) ;

б) f (x1, x2 ,..., xn ) Ú g ( y1, y2 ,..., ym ) ;

в) f (x1, x2 ,..., xn ) Å g ( y1, y2 ,..., ym ) .

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

§ 2.3. Минимизация дизъюнктивных нормальных форм

Элементарная конъюнкция, ранг элементарной конъюнкции. Дизъюнктивная нормальная форма (ДНФ), сложность ДНФ. Минимальная ДНФ. Импликанта, простая импликанта. Сокращенная ДНФ. Тупиковая ДНФ. Представление булевой функции в виде сокращенной, тупиковой и минимальной ДНФ.

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

1. Постановка задачи минимизации ДНФ. Пусть задан алфавит переменных

X = { x1, x2 ,..., xn } .

Определение. Формулу вида	K = xσ1	× xσ2	×...× xσr , где для любого i s	i	равно 0 или 1 и
	i1	i2	ir

все переменные разные ( iν ¹ iμ , если n ¹ m ), называют элементарной конъюнкцией ранга r над множеством X.

Константу 1 считают элементарной конъюнкцией ранга 0.

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

Например, пусть задан алфавит переменных X = { x1, x2 , x3 , x4 } . Тогда формула x1 × x2 × x4 - элементарная конъюнкция ранга 3, а формула x1 × x4 - элементарная

конъюнкция ранга 2 над множеством X . Формула x1 × x1 × x2 × x3 , напротив, элементарной конъюнкцией не является, так как в этой формуле дважды упоминается переменная x1 .

Пример 1. Перечислить все элементарные конъюнкции над множеством {x1, x2 } : 1, x1

, x1 , x2 , x2 , x1x2 , x1x2 , x1x2 , x1x2 .

Вообще, используя алфавит из n переменных X = {x1, x2 ,..., xn } , можно составить 3n

элементарных конъюнкций. Действительно, произвольную элементарную конъюнкцию можно составить за n этапов. На первом этапе принять решение относительно переменной x1 (есть три возможности - включить ее в конъюнкцию саму по себе,

включить ее отрицание или не включать ее вовсе), на втором - принять решение относительно переменной x2 (вновь имеем три возможности) и т.д. Действуя

описанным образом, мы составим 31424× 3 ×...3× = 3n элементарных конъюнкций (в их число

n

входит и константа 1 - сопоставим ее случаю, когда ни одна из переменных в конъюнкцию не включена).

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

Пример 2. Перечислить все элементарные конъюнкции ранга 3 над множеством

{ x1, x2 , x3 , x4 } , обращающиеся в 1 на наборе (0,1,0,0) .

◄ Произвольная элементарная конъюнкция равна 1 в том и только в том случае, когда все образующие ее множители одновременно равны 1. Значит, переменная x2 может войти в элементарную конъюнкцию, обращающуюся в 1 на наборе (0,1,0,0) , только без отрицания, а остальные переменные - обязательно с отрицанием. Таким образом,

перебрав все варианты выбора трех переменных из множества { x1, x2 , x3 , x4 } , получим четыре конъюнкции: x1x2 x3 , x1x2 x4 , x1x3 x4 , x2 x3 x4 . ►

Упражнение 2.17. Перечислить все элементарные конъюнкции над множеством

{x1, x2 , x3} , обращающиеся в единицу на наборе (1,0,0) .

Определение. Формулу вида D = K1 Ú K2 Ú ... Ú Ks ( Ki ¹ K j при i ¹ j ), где через

Ki (i =1, 2,..., s) обозначены элементарные конъюнкции над множеством X, называют

дизъюнктивной нормальной формой над множеством X.

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

Сумма рангов конъюнкций, входящих в ДНФ, называется сложностью ДНФ.

Например, D1 = x1 × x2 Ú x1 × x2 × x3 Ú x1 - ДНФ сложности 6; D2 = x1 Ú x1 × x2 × x3 - ДНФ сложности 4; D3 = x1 Ú x2 × x3 - ДНФ сложности 3 над множеством X = {x1, x2 , x3} .

Заметим, что формулы D1, D2 , D3 равносильны и, следовательно, реализуют одну и ту же функцию f (x1, x2 , x3 ) . Таким образом, одна и та же функция может быть задана несколькими ДНФ, причем эти ДНФ могут иметь различную сложность.

Определение. ДНФ, имеющая по сравнению с другими ДНФ, задающими данную функцию, наименьшую сложность, называется минимальной ДНФ данной функции.

Так, для функции f (x1, x2 , x3 ) , реализуемой рассмотренными выше ДНФ D1 , D2 , D3 ,

дизъюнктивная нормальная форма D3 = x1 Ú x2 × x3 является минимальной.

Задача минимизации ДНФ формулируется так: для всякой булевой функции f (x1, x2 ,..., xn ) найти представление в виде минимальной ДНФ.

Задачу минимизации ДНФ можно решить методом полного перебора, организовав его следующим образом.

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

1. Построить все ДНФ над множеством X = { x1, x2 ,..., xn } .

Выше было показано, что число различных элементарных конъюнкций над алфавитом из n переменных равно 3n . При построении произвольной ДНФ каждую из этих конъюнкций можно в нее либо включить, либо не включить. Значит, всего можно составить 23n −1 ДНФ (вычтя из 23n единицу, мы учли, что если не включить в строящийся объект ни одну из элементарных конъюнкций, то ДНФ не образуется).

2. Отобрать из построенных ДНФ те, которые задают функцию f .

Заметим, что для всякой булевой функции f (x1, x2 ,..., xn ) , тождественно отличной от нуля, есть, по крайней мере, одна представляющая ее ДНФ - это СДНФ.

3. Для каждой отобранной ДНФ определить сложность; ДНФ наименьшей сложности и есть искомые минимальные ДНФ функции f .

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

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

Определение. Элементарная конъюнкция называется импликантой функции

f (x1, x2 ,..., xn ) , если на любом наборе (α1,α2 ,...,αn ) , на котором эта элементарная конъюнкция равна 1, функция f также обращается в 1.

Заметим, что любая элементарная конъюнкция, входящая в СДНФ функции, является импликантой этой функции.

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

Пример 3. Перечислить все простые импликанты функции f (x, y) = x → y .

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