КНФ

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

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

Пример КНФ: [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]

Теорема:

Для любой булевой функции [math]f(\vec{x})[/math], не равной тождественной единице, существует СКНФ, ее задающая.

Доказательство:

[math]\triangleright[/math]

Поскольку инверсия функции [math]\neg f(\vec x)[/math] равна единице на тех наборах, на которых [math]f(\vec x)[/math] равна нулю, то СДНФ для [math]\neg f(\vec x)[/math] можно записать следующим образом:

[math]\triangleleft[/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]