Лекция 4 СДНФ СКНФ для студентов

1. 4. Совершенные дизъюнктивные и конъюнктивные нормальные формы

Совершенные нормальные
формы формул алгебры
высказываний

2. Определения

Элементарная конъюнкция (дизъюнкция)
называется правильной,
если в её составе нет одинаковых переменных.
Дизъюнкт (конъюнкт) является полным,
относительно некоторого набора переменных,
если в его составе представлены
все переменные этого набора.

3. СДНФ, СКНФ

Совершенная дизъюнктивная
(конъюнктивная) нормальная форма
СДНФ (СКНФ) данной формулы f
называется такая её ДНФ (КНФ),
которая не содержит одинаковых
конъюнктов (дизъюнктов), каждый
конъюнкт (дизъюнкт) правилен и
обладает свойством полноты.

4. Основные теоремы

Теорема 1. Любая формула f, не
являющаяся тождественной ложью,
обладает единственной СДНФ.
Теорема 2. Любая формула f, не
являющаяся тавтологией, обладает
единственной СКНФ.

5. Алгоритм перехода от таблицы истинности формулы к её записи в виде СДНФ(СКНФ)

• выбрать в таблице такие наборы исходных
переменных, на которых истинностное значение
формулы равно 1 (0);
• записать элементарные конъюнкции (дизъюнкции) для
выбранных наборов переменных; при этом
необходимо руководствоваться следующим правилом:
если значение входной переменной в наборе –
единичное, то она записывается в прямой форме
(форме отрицания), если же значение переменной –
нулевое, то – в форме отрицания (прямой форме);
• полученные конъюнкты (дизъюнкты) объединить
между собой знаками дизъюнкции (конъюнкции).

6. Пример 1

y z x y
xyz x yz x yz
СДНФ
x y z x y z x y z x y z x y z СКНФ

7. Алгоритм получения СДНФ и СКНФ с помощью равносильных переходов

1) привести формулу с помощью равносильных преобразований к ДНФ;
2) удалить члены дизъюнкции, содержащие переменную вместе с ее
отрицанием (если такие окажутся);
3) из одинаковых членов дизъюнкции (если такие окажутся) удалить все,
кроме одного;
4) из одинаковых членов каждой конъюнкции (если такие окажутся)
удалить все, кроме одного;
5) если в какой-нибудь конъюнкции не содержится переменной из числа
переменных, входящих в исходную формулу, добавить к этой
конъюнкции член а a b a b – закон расщепления;
6) если в полученной дизъюнкции окажутся одинаковые члены,
воспользоваться предписанием из п. 3.
СКНФ получается аналогично.
Закон расщепления имеет вид: a a b a b

8. Пример 1

y z x y y z xy x y
y z yxy y x y y z x y
x y z x y z x yz x y z x y z x y z x yz СДНФ
y z x y y z x y x y y x z y z
x y z x y z x y z x y z x y z
x y z x y z x y z x y z x y z x y z
y x z x y x y x y z x y z
СКНФ

9. Пример 2

z y x y
Решение
z y x y z y y z x y
z y y z x y z y x y z x y
z y x y z x y z y x y
z x y КНФ
z x y x y z x y z x y x y
x y z x y z x y z x y z x y z x y z
x y z x y z x y z x y z x y z СКНФ

10. Пример 2

z x y z y x y ДНФ
z y x y x yz x yz x yz x y z x yz x yz x y z СДНФ
Таблица истинности

11. Решить самостоятельно

Привести данную формулу к СДНФ и СКНФ.
Результат проверить с помощью таблицы
истинности
3.
x y z x
4.
x y z y