КНФ

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

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

Пример КНФ: [math]f(x,y) = (x \lor y) \land (y \lor \neg z)[/math]

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

СКНФ (Совершенная Конъюнктивная Нормальная Форма) — это такая КНФ, которая удовлетворяет условиям: в ней нет одинаковых элементарных дизъюнкций в каждой дизъюнкции нет одинаковых переменных каждая элементарная дизъюнкция содержит каждый из аргументов функции.

Пример СКНФ: [math]f(x,y,z) = (x \lor \neg y \lor z) \land (x\lor y \lor \neg z)[/math]

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

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

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

Стрелка Пирса: [math] x \downarrow y = (\neg x \lor y) \land (x \lor \neg y) \land (\neg x \lor \neg y)[/math]

Медиана трёх: [math]f(x,y,z) = ( x \lor y \lor z) \land (\neg x \lor y \lor z) \land (x \lor \neg y \lor z) \land ( x \lor y \lor \neg z)[/math]