КНФ

Определение:

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

Пример КНФ: [math](x \or y) \and (y \or \neg z)[/math]

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

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

Пример СКНФ: [math](x \or \neg y \or z) \and (x\or y \or \neg z)[/math]

Алгоритм построения СКНФ по таблице истинности

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

Примеры СКНФ для некоторых функций

Стрелка Пирса: [math](\neg x \or y) \and (x \or \neg y) \and (\neg x \or \neg y)[/math]

Медиана трёх: [math]( x \or y \or z) \and (\neg x \or y \or z) \and (x \or \neg y \or z) \and ( x \or y \or \neg z)[/math]