Совершенные нормальные формы

Совершенная дизъюнктивная нормальная форма. Элементарной конъюнкцией высказываний называется конъюнкция этих высказываний и их отрицаний.

Дизъюнктивной нормальной формой формулы А (ДНФ (Л)) называется дизъюнкция элементарных конъюнкций. Для любой формулы путем равносильных преобразований можно получить ДНФ, причем не единственную.

Совершенной дизъюнктивной нормальной формой формулы Л (СДНФ (Л)) называется дизъюнктивная нормальная форма формулы Л, удовлетворяющая следующим свойствам совершенства.

• 1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию.
• 2. Все логические слагаемые формулы различны.
• 3. Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.
• 4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Правило построения СДНФ булевой функции с помощью таблиц истинности:

• • выделяем строки, где формула принимает значение 1;
• • составляем дизъюнкцию конъюнкций при условии, что если переменная входит в конъюнкцию со значением 1, то записываем эту переменную, если со значением 0, то ее отрицание.

Получаем СДНФ.

Совершенная конъюнктивная нормальная форма. Элементарной дизъюнкцией высказываний называется дизъюнкция этих высказываний и их отрицаний.

Конъюнктивной нормальной формой формулы А (КНФ (Л)) называется конъюнкция элементарных дизъюнкций.

Совершенной конъюнктивной нормальной формой формулы А (СКНФ (Л)) называется конъюнктивная нормальная форма формулы Л, удовлетворяющая следующим условиям.

• 1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию.
• 2. Все логические слагаемые формулы различны.
• 3. Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.
• 4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Правило построения СКНФ булевой функции с помощью таблиц истинности:

• • выделяем строки, где формула принимает значение 0;
• • составляем конъюнкцию дизъюнкций при условии, что если переменная входит в дизъюнкцию со значением 0, то записываем эту переменную, если со значением 1, то ее отрицание.

Получаем СКНФ.

Пример 4.20. Следующую формулу привести к СДНФ:

Решение (табл. 4.18).

Таблица 4.18

Таблица истинности для решения примера 4.20.

Выделяем строки, где формула принимает значение 1, составляем дизъюнкцию конъюнкций и получаем СДНФ:

Пример 4.21. Следующую формулу привести к СКНФ двумя способами:

Решение (табл. 4.19).

Таблица 4.19

Таблица истинности для решения примера 4.21.

Для значений формулы, равных 0, составляем конъюнкцию дизъюнкций и получаем СКИФ: