Совершенная конъюнктивная нормальная форма (СКНФ) — одна из форм представления функции алгебры логики (булевой функции) в виде логического выражения. Представляет собой частный случай КНФ, удовлетворяющий следующим трём условиям:
в ней нет одинаковых множителей (элементарных дизъюнкций); в каждом множителе нет повторяющихся переменных; каждый множитель содержит все переменные, от которых зависит булева функция (каждая переменная может входить в множитель либо в прямой, либо в инверсной форме).
Любая булева формула, не являющаяся тождественно истинной, может быть приведена к СКНФ..
Пример нахождения СКНФ
Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности статьи минимизация логических функций методом Квайна:
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. Первый член СКНФ рассматриваемой функции выглядит так:
Остальные члены СКНФ составляются по аналогии:В.И. Игошин. Задачник-практикум по математической логике. 1986
См. также
Конъюнктивная нормальная форма Дизъюнктивная нормальная форма Совершенная дизъюнктивная нормальная форма
Примечания
Категория:Булева алгебра