Дискретка / 5 - БФ (часть 2) - Нормальные формы

Нормальные формы

Элементарное произведение – это конъюнкция, каждый множитель которой является переменной либо её отрицанием, или одна переменная.

Элементарная сумма – это дизъюнкция, каждое слагаемое которой является переменной либо её отрицанием, или одна переменная.

Дизъюнктивная нормальная форма (ДНФ) – дизъюнкция элементарных произведений или одно произведение.

Теорема. Для любой формулы существует равносильная ей ДНФ (не одна).

Конъюнктивная нормальная форма (КНФ) – конъюнкция элементарных сумм или одна сумма.

Теорема. Для любой формулы существует равносильная ей КНФ (не одна).

Алгоритм нахождения ДНФ и КНФ:

1) исключить связки , ≡,

,

, |, т.е. перейти к виду, содержащему лишь связки ¬, &, ˅;

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

3)для ДНФ: применить всюду, где возможно, 1-й закон дистрибутивности:

x & y z ~ x & y x & z ;

для КНФ: применить всюду, где возможно, 2-й закон дистрибутивности x y & z ~ x y & x z .

Эта схема является общей. Кроме описанных действий, по ходу преобразований также можно упрощать формульные записи с использованием законов:

двойного отрицания (1),

идемпотентности (10, 11),

исключённого третьего (12),

противоречия (13),

свойств 0 и 1 (14 – 17),

поглощения (18, 19).

Совершенные нормальные формы

Совершенная ДНФ (СДНФ) для булевой функции f (x1, … xn) – это ДНФ, удовлетворяющая следующим условиям:

1.в каждом слагаемом содержится каждая из переменных только один раз – с отрицанием или без;

2.нет одинаковых слагаемых.

Теорема. Для каждой выполнимой (не тождественно равной нулю) формулы

существует единственная равносильная ей СДНФ. Аналитический способ построения СДНФ:

1)найти один из видов ДНФ;

2)исключить из неё по закону (16) все тождественно равные нулю слагаемые;

3)исключить по законам идемпотентности (10, 11) одинаковые слагаемые – и в них – одинаковые переменные (с отрицанием или без);

4)добавить в слагаемые недостающие переменные по следующей схеме:

B ~ B & x x ~ B & x B & x ;

(12,15) (6)

1

здесь предполагается, что исходная формула содержит переменную x, а B представляет собой одно из элементарных произведений ДНФ без переменной x;

5)исключить по второму закону идемпотентности (11) из полученной суммы одинаковые слагаемые, если таковые возникли в результате последнего преобразования.

Табличный способ построения СДНФ.

Предполагается построенной таблица истинности булевой функции.

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

2)Для каждой выбранной строки строим конституенту единицы, т.е. элементарное произведение, в котором переменная берётся с отрицанием, если она в этой строке принимает значение 0 и без – если – 1;

3)Суммируем полученные конституенты единиц (соединяем дизъюнкцией). Совершенная КНФ (СКНФ) для булевой функции f (x1, … xn) – это КНФ,

удовлетворяющая следующим условиям:

1.в каждом множителе содержится каждая из переменных только один раз – с отрицанием или без;

2.нет одинаковых множителей.

	Теорема. Для каждой формулы, не равной тождественно единице, существует
единственная равносильная ей СКНФ.
	Аналитический способ построения СКНФ:
1)	найти один из видов КНФ;
2)	исключить неё по закону (15) все тождественно равные единице сомножители;
3)	исключить по законам идемпотентности (10, 11) одинаковые множители и в них –
	одинаковые переменные (с отрицанием или без);
4)	добавить в сомножители недостающие переменные по следующей схеме:
	C ~	C x & x ~ C x & C x ;
	(13,16)	(7)
	здесь предполагается, что исходная формула содержит переменную x, а С
	представляет собой некоторый множитель КНФ без переменной x;
5)	исключить по первому закону идемпотентности (10) из полученной КНФ
	одинаковые сомножители, если таковые возникли в результате последнего
	преобразования.

Табличный способ построения СКНФ.

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

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

2)Для каждой выбранной строки строим конституенту нуля, т.е. элементарную сумму,

вкоторой переменная берётся с отрицанием, если она в этой строке принимает значение 1 и без – если – 0.

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

а) y & x z y & z x .

Решение.

1. Найдём СДНФ и СКНФ аналитически. Проведём следующую цепочку преобразований:

2

												~
y & x z y & z				x	~ y & x z y & z x				& x z
	20		21				20			20

	z
~ y & x			y & x z & x z	~ y &	x z	y & x z & x z ~
	5				19

~ y & x z .

КНФ

Раскрыв скобки по первому закону дистрибутивности (6), получим ДНФ:

y & x z ~ x & y y & z .
6		ДНФ

Получим теперь СДНФ. По описанному алгоритму осталось лишь выполнить пункты 4 и 5. Добавим в слагаемые недостающие переменные: в первое – z, во второе – x и исключим одинаковые слагаемые:

x & y y & z ~ x & y & z z y & z & x x ~

~ x & y & z x & y & z x & y & z x & y & z ~ x & y & z x & y & z x & y & z .

СДНФ

Теперь из КНФ получим СКНФ. Здесь также осталось выполнить лишь 2 шага алгоритма: добавить недостающие переменные в сомножители (в первый – x и z, во второй – y) и исключить одинаковые слагаемые. Получаем, что: y & x z ~ x y z & x y z & x y z & x y z & x y z & x y z ~

КНФ ~ x y z & x y z & x y z & x y z & x y z .

СКНФ

2. Построим	совершенные
нормальные формы	табличным

способом. Для этого построим сначала таблицу истинности для исходной формулы:

По строкам, отмеченным символом «*», по описанному алгоритму построим СДНФ:

x	y	z	y	&	( x		z	˅	y	( z	≡ x))
0	0	0		0	1	0		0	1	1	0	-
0	0	1		0	1	1		1	1	0	1	-
0	1	0		0	1	0		0	0	1	0	-
0	1	1		1	1	1		1	0	0	1	*
1	0	0		0	0	1		1	1	1	1	-
1	0	1		0	0	1		1	1	0	0	-
1	1	0		1	0	1		1	0	1	1	*
1	1	1		1	0	1		1	0	0	0	*

y & x z y & z x ~ x & y & z x & y & z x & y & z. СДНФ

По строкам, отмеченным символом «-», по описанному алгоритму построим СКНФ:

y & x z y & z x ~ x y z & x y z & x y z & x y z & x y z .

СКНФ
Видим, что обоими способами получены одинаковые СДНФ и СКНФ, различается
лишь порядок следования в них имеющихся конституент.	□

б)

в)

г)

д)

е)

x y y x ;

x & y z x y ; x y y x ;

x y & z x z ; x | y t z & x y .

3