Как преобразовать пропозициональную формулу в конъюнктивную нормальную форму (CNF)?

Ответ 1

Чтобы преобразовать формулу пропозициональную формулу в конъюнктивную нормальную форму, выполните следующие два шага:

• Направьте отрицания в формулу, повторно применяя закон Де Моргана, пока все отрицания не применимы только к атомам. Вы получите формулу в отрицательной нормальной форме.

  • ¬(p ∨ q) to (¬p) ∧ (¬q)

  • ¬(p ∧ q) to (¬p) ∨ (¬q)

• Неоднократно применяйте дистрибутивный закон, где дизъюнкция происходит по соединению. Как только это невозможно, формула находится в CNF.

  • p ∨ (q ∧ r) to (p ∨ q) ∧ (p ∨ r)

Чтобы получить формулу в дизъюнктивной нормальной форме, просто примените распределение ∧ по ∨ на шаге 2.

Примечание о ⊂

Символ подмножества (⊂), используемый в вопросе, является просто альтернативной нотацией для логической импликации/вхождения, которая обычно записывается как стрелка (⇒).

Ответ 2

http://en.wikipedia.org/wiki/Conjunctive_normal_form

Чтобы преобразовать логику первого порядка в CNF:

• Преобразовать в стандартную форму отрицания.
  • Устранить последствия: конвертировать x → y в & not; x ∨ y
  • Переместите NOTs внутрь.
• Стандартизировать переменные
• Скомемизировать утверждение
• Дробные универсальные кванторы
• Распределите ANDs через OR.

(Искусственный интеллект: современный Подход [1995...] Рассел и Норвиг)

Ответ 3

Могу я предложить это? Существует алгоритм преобразования на странице.

Конъюнктивная нормальная форма

Ответ 4

Я реализовал небольшой инструмент в Java, который может выполнять базовое преобразование из булева выражения в (C | D) NF. Если вам интересно, вы можете посмотреть https://github.com/julianthome/ctrans. Реализация основана на этих примечаниях к лекции. Более подробное описание можно найти здесь. Любая обратная связь будет принята с благодарностью: -).