КНФ

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

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


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

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

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

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

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

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

Медиана трёх: [math]( 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]