КНФ

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

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