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

Question

Как я могу преобразовать это уравнение в CNF?

¬((p ∨ ¬Q) ⊃ R) ⊃ (P ∧ R))

Answer 1

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

1. Вставьте отрицания в формулу, неоднократно применяя Закон де Моргана , пока все отрицания не будут применены только к атомам. Вы получаете формулу в отрицательной нормальной форме .

   • ¬(p ∨ q) до (¬p) ∧ (¬q)

   • ¬(p ∧ q) до (¬p) ∨ (¬q)

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

   • p ∨ (q ∧ r) до (p ∨ q) ∧ (p ∨ r)

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

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

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

Answer 2

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

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

1. Конвертировать в отрицательную форму.
   1. Устранить последствия: преобразовать x → y в & not; x ∨ y
   2. Переместить НЕ внутрь.
2. Стандартизировать переменные
3. Сколемизируйте высказывание
4. Падение универсальных квантификаторов
5. Распределение И по ИЛИ.

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

Answer 3

Могу ли я предложить это? На странице представлен алгоритм конвертации.

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

Answer 4

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