(Табличный способ приведения к сднф)
Составляется таблица истинности данной ПФ.
Рассматриваются те строки, в которых формула принимает истинностное значение 1. Каждой такой строке ставится в соответствие элементарная конъюнкция, причем переменная, принимающая значение 1, входит в нее без отрицания, а 0 – с отрицанием.
Образуется дизъюнкция всех полученных элементарных конъюнкций, которая и составляет СДНФ.
Алгоритм 6.4
(Табличный способ приведения к скнф)
1. Составляется таблица истинности данной ПФ.
2. Рассматриваются те строки, в которых формула принимает истинностное значение 0. Каждой такой строке ставится в соответствие элементарная дизъюнкция, причем переменная, принимающая значение 1, входит в нее с отрицанием, а 0 – без отрицания.
Образуется конъюнкция всех полученных элементарных дизъюнкций, которая и составляет СКНФ.
Пример решения задачи
Задача.
Привести
ПФ
к нормальным
и совершенным нормальным формам.
Решение. С помощью равносильных преобразований, согласно алгоритма 6.1, приведем ПФ к дизъюнктивной нормальной форме (ДНФ).
1
)
Исключим операцию импликацию (),
получим
2
)
Исключим операцию сложение по модулю
два (),
получим.
3) Исключим операцию эквиваленцию (), получим
4) Применив закон де Моргана, получим
.
Таким образом, искомая ДНФ имеет вид
С помощью равносильных преобразований приведем ПФ к конъюнктивной нормальной форме (КНФ).
Используя
дистрибутивный закон и равносильности
,
,
получим
Т
аким
образом, искомая КНФ имеет вид
.
Приведем ПФ к совершенным нормальным формам (СДНФ, СКНФ) с помощью табличного способа. Построим таблицу истинности и на ее основе составим СДНФ и СКНФ.
X |
Y |
Z |
|
|
F |
Элементарные конъюнкции |
Элементарные дизъюнкции |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
0 |
0 |
1 |
1 |
1 |
1 |
|
|
0 |
1 |
0 |
0 |
0 |
1 |
|
|
0 |
1 |
1 |
0 |
1 |
1 |
|
|
1 |
0 |
0 |
1 |
1 |
1 |
|
|
1 |
0 |
1 |
1 |
0 |
0 |
|
|
1 |
1 |
0 |
1 |
1 |
1 |
|
|
1 |
1 |
1 |
1 |
0 |
0 |
|
|
СКНФ:
.
СДНФ:
.
Приведем к СДНФ, СКНФ с помощью аналитического способа.
СДНФ:
СКНФ:
