08. Нормальные формы
Теорема 1.7. Всякая булева функция заменима функцией, содержащей только три логические операции – дизъюнкцию, конъюнкцию и отрицание.
P Элементарной конъюнкцией называется конъюнкция логических переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Например, булева функция 
является элементарной конъюнкцией.
P Дизъюнктивной нормальной формой (ДНФ) булевой функции называется формула, имеющая вид дизъюнкции элементарных конъюнкций.
Например, булева функция 
является ДНФ.
P Совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции называется ДНФ, в которой каждая элементарная конъюнкция включает все переменные или их отрицания.
Например, булева функция 
является СДНФ.
Для Построения СДНФ Булевой функции 
выполняются следующие действия:
1) для каждого набора значений переменных 
, для которых 
, выписывается элементарная конъюнкция, содержащая все переменные 
и отрицания всех переменных 
(индексы I и J принимают любые значения от 1 до N);
2) все полученные элементарные конъюнкции объединяются знаками дизъюнкции.
Пример. Найти СДНФ функции 
.
Решение. В таблице истинности функции зафиксируем строки, в которых 
.
|
|
|
|
Строки для построения СДНФ |
|
1 |
1 |
1 |
* |
|
1 |
0 |
0 | |
|
0 |
1 |
1 |
* |
|
0 |
0 |
1 |
* |
Для каждого набора значений переменных X1 и X2 в выделенных знаком «*» строках запишем элементарные конъюнкции, содержащие все переменные 
и отрицания всех переменных 
: 
, 
и 
. Затем все полученные элементарные конъюнкции объединим знаками дизъюнкции и получим СДНФ данной функции: 
.□
P Элементарной дизъюнкцией Называется дизъюнкция логических переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Например, булева функция 
является элементарной дизъюнкцией.
P Конъюнктивной нормальной формой (КНФ) булевой функции называется формула, имеющая вид конъюнкции элементарных дизъюнкций.
Например, булева функция 
является КНФ.
P Совершенной конъюнктивной нормальной формой (СКНФ) булевой функции называется КНФ, в которой каждая элементарная дизъюнкция включает все переменные или их отрицания.
Например, булева функция 
является СКНФ.
Для Построения СКНФ булевой функции 
выполняются следующие действия:
1) для каждого набора значений переменных , для которых 
, выписывается элементарная дизъюнкция, содержащая отрицания всех переменных и все переменные 
(индексы I и J принимают любые значения от 1 до N);
2) все полученные элементарные дизъюнкции объединяются знаками конъюнкции.
Пример. Найти СКНФ функции .
Решение. В таблице истинности функции зафиксируем строки, в которых 
.
|
|
|
|
Строки для построения СКНФ |
|
1 |
1 |
1 | |
|
1 |
0 |
0 |
* |
|
0 |
1 |
1 | |
|
0 |
0 |
1 |
Для набора значений переменных 
и 
, для которых 
в строке, выделенной знаком «*», выпишем элементарную дизъюнкцию, содержащую отрицание переменной 
и переменную 
, и получим СКНФ данной функции: 
.□
Теорема 1.8. Любая булева функция, отличная от константы 0, представима в виде СДНФ. Любая булева функция, отличная от константы 1, представима в виде СКНФ.
Задачи и упражнения
1.34. По заданной таблице истинности постройте СДНФ и СКНФ для функций 
, 
, 
:
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
| < Предыдущая | Следующая > |
|---|
