Совершенные нормальные формы
Пример 28.
Привести следующие формулы к СКНФ с помощью равносильных преобразований:
1. 
;
2. 
.
Решение.
1. 
2. 
2-й способ – табличный.
Составляем таблицу истинности для данной функции.
Приведение к СДНФ. Алгоритм приведения.
Строим таблицу значений формулы. Рассматриваем только те строки, в которых значение формулы равно единице. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Причем, аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 – без отрицания. Наконец, образуем дизъюнкцию всех полученных конъюнкций.
Пример 29.
Построить СДНФ для данных формул логики высказываний.
1. 
.
2. 
Решение.
1. .
Строим таблицу истинности (табл. 13) для формулы F:
Таблица 13
|
№ |
x |
y |
z |
|
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
2 |
0 |
1 |
0 |
0 |
0 |
0 |
|
3 |
0 |
1 |
1 |
0 |
1 |
0 |
|
4 |
1 |
0 |
0 |
1 |
1 |
1 |
|
5 |
1 |
0 |
1 |
1 |
1 |
1 |
|
6 |
1 |
1 |
0 |
0 |
0 |
0 |
|
7 |
1 |
1 |
1 |
0 |
1 |
1 |
Рассматриваем только 4, 5 и 7 наборы, так как только на этих наборах формула принимает значение равное единице.
СДНФ имеет вид: 
2. 2.
Строим таблицу истинности (табл. 14) для формулы F:
Таблица 14
|
№ |
x |
y |
x® y |
F=(x® y)ЩxЩy |
|
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
0 |
|
2 |
1 |
0 |
0 |
0 |
|
3 |
1 |
1 |
1 |
1 |
СДНФ (1): № 3:
предыдущаяследующая