Совершенная конъюнктивная нормальная форма

Материал из Википедии — свободной энциклопедии
(перенаправлено с «СКНФ»)
Перейти к навигации Перейти к поиску

Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:

  • в ней нет одинаковых элементарных дизъюнкций
  • в каждой дизъюнкции нет одинаковых пропозициональных переменных
  • каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

Любая булева формула, не являющаяся тождественно истинной, может быть приведена к СКНФ.[1].

Пример нахождения СКНФ[править | править код]

Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности статьи минимизация логических функций методом Квайна:

0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 1

В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.

Четвёртая строка содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:

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

Остальные члены СКНФ составляются по аналогии:[2]

См. также[править | править код]


Примечания[править | править код]