lec03
.pdfДоказательство теоремы 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