lec03

Доказательство теоремы 3.1. Продолжение.

2) Строим КНФ (схема аналогична).

Каждому набору значений, на котором функция ложна, мы сопоставим дизъюнкт. Если переменная в этом наборе истинна, то в конъюнкт будет включено ее отрицание, а если ложна, то она сама. Итоговая КНФ будет конъюнкцией всех таких дизъюнктов. Формально можно записать так:

=		1−σ	(3.3)
(σ1… σ )=0	=1

11

Следствие 3.1. из теоремы о существовании КНФ и ДНФ для любой БФ.

Теорема 3.1 доказывает для любой БФ существование СДНФ, кроме тождественно ложной и СКНФ, кроме тождественно истинной. (по способу конструирования конъюнкты/дизъюнкты содержат ровно 1 включение каждой переменной).

Важный случай – разложение БФ по первому аргументу (Шеннона).

(x1,x2, … xn) = 1 (0,x2, … xn) x1 (1,x2, … xn)

12

Пример 3.2. Нахождение СДНФ для БФ. Найти СДНФ для БФ, заданной таблично.

Эквивалентно векторному заданию (x1,x2,x3) = (00010111)

x1	x2	x3	(x1,x2,x3)	конъюнкты дизъюнкты
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1	13

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

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

	x1	x2	x3	(x1,x2,x3)			конъюнкты	дизъюнкты
	0	0	0	0				x1 x2 x3
	0	0	1	0
								x1 x2 ¬x3
	0	1	0	0
								x1 ¬x2 x3
	0	1	1	1			¬x1 x2 x3
	1	0	0	0				¬x1 x2 x3
	1	0	1	1			x1 ¬x2 x3
	1	1	0	1			x1 x2 ¬x3
	1	1	1	1			x1 x2 x3

14

Пример 3.2. Итог.

СДНФ - все полученные конъюнкции связываем операциями дизъюнкции:

(x1,x2,x3) = K1 K2 K3 K4 =

= (¬x1 x2 x3) (x1 ¬x2 x3) (x1 x2 ¬x3) (x1 x2 x3)

СКНФ - все полученные дизъюнкции связываем операциями конъюнкции:

(x1,x2,x3) = D1 D2 D3 D4 =

= (x1 x2 x3) (x1 x2 ¬x3) (x1 ¬x2 x3) (¬x1 x2 x3)

15

Символьное задание БФ.

Возможно символьное задание БФ:

где n – арность БФ, k – десятичное представление бинарной записи характеристического вектора.

Здесь для примера 3.2: (x1,x2,x3) = (00010111) (23=16+4+2+1):

(x1, x2, x3) = (00010111) = 233

16

Пример 3.3. Нахождение СДНФ для БФ.

Найти СДНФ для функции арности 5, заданной носителем.

Если в БФ 5 аргументов – значит единичных вершин в носителе до 32 (=25).

Носитель может быть задать в виде множества единичных вершин:

Nf = { 00111, 01001, 01101, 01110, 01111, 10011, 10101, 10110, 10111, 11001, 11010, 11011, 11100, 11101, 11110, 11111 }

или по номерам позиций значений переменных БФ для единичных вершин:

(x1,x2,x3,x4,x5) = (8, 12, 14, 15, 16, 20, 22, 23, 24, 26, 27, 28, 29, 30, 31, 32).

17

	№	x1	x2	x3	x4	x5	f		конъюнкты
1		0	0	0	0	0	0
2		0	0	0	0	1	0
3		0	0	0	1	0	0
4		0	0	0	1	1	0
5		0	0	1	0	0	0
6		0	0	1	0	1	0
7		0	0	1	1	0	0
	8	0	0	1	1	1	1		(¬x1 x2 ¬x3 x4 x5)
9		0	1	0	0	0	0
10		0	1	0	0	1	0
11		0	1	0	1	0	0
	12	0	1	0	1	1	1		(¬x1 x2 ¬x3 x4 x5)
13		0	1	1	0	0	0
	14	0	1	1	0	1	1		(¬x1 x2 x3 ¬x4 x5)
	15	0	1	1	1	0	1		(¬x1 x2 x3 x4 ¬x5)

18

№	x1	x2	x3	x4	x5	f	конъюнкты
16	0	1	1	1	1	1	(¬x1 x2 x3 x4 x5)
17	1	0	0	0	0	0
18	1	0	0	0	1	0
19	1	0	0	1	0	0
20	1	0	0	1	1	1	(x1 ¬x2 ¬x3 x4 x5)
21	1	0	1	0	0	0
22	1	0	1	0	1	1	(x1 ¬x2 x3 ¬x4 x5)
23	1	0	1	1	0	1	(x1 ¬x2 x3 x4 ¬x5)
24	1	0	1	1	1	1	(x1 ¬x2 x3 x4 x5)
25	1	1	0	0	0	0
26	1	1	0	0	1	1	(x1 x2 ¬x3 ¬x4 x5)
27	1	1	0	1	0	1	(x1 x2 ¬x3 x4 ¬x5)
28	1	1	0	1	1	1	(x1 x2 ¬x3 x4 x5)
29	1	1	1	0	0	1	(x1 x2 x3 ¬x4 ¬x5)
30	1	1	1	0	1	1	(x1 x2 x3 ¬x4 x5)
31	1	1	1	1	0	1	(x1 x2 x3 x4 ¬x5)
32	1	1	1	1	1	1	(x1 x2 x3 x4 x5)	19

Пример 3.3. Итог.

СДНФ (x1,x2,x3,x4,x5) найдена в виде:

(x1,x2,x3,x4,x5) = K1 K2 … K16 =

(¬x1 x2 ¬x3 x4 x5) (¬x1 x2 ¬x3 x4 x5) (¬x1 x2 x3 ¬x4 x5) (¬x1 x2 x3 x4 ¬x5) (¬x1 x2 x3 x4 x5) (x1 ¬x2 ¬x3 x4 x5) (x1 ¬x2 x3 ¬x4 x5) (x1 ¬x2 x3 x4 ¬x5) (x1 ¬x2 x3 x4 x5) (x1 x2 ¬x3 ¬x4 x5) (x1 x2 ¬x3 x4 ¬x5) (x1 x2 ¬x3 x4 x5) (x1 x2 x3 ¬x4 ¬x5) (x1 x2 x3 ¬x4 x5) (x1 x2 x3 x4 ¬x5) (x1 x2 x3 x4 x5).

20