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