Преобразовать логическое выражение в конъюнктивную нормальную форму

10

Цель:

Напишите полную программу или функцию, которая принимает формулу в логике высказываний (далее называемую логическим выражением или выражением ) и выводит эту формулу в конъюнктивной нормальной форме . Есть две константы, и представляющих истинные и ложные, унарный оператор , ¬представляющий отрицание и бинарные операторы , , , и представляющих импликации, эквивалентности, конъюнкции и дизъюнкции, соответственно , которые подчиняются все обычные логические операции ( закон де Моргана , устранение двойного отрицания , так далее.).

Конъюнктивная нормальная форма определяется следующим образом:

  1. Любое атомное выражение (в том числе и ) находится в конъюнктивной нормальной форме.
  2. Отрицание любого ранее построенного выражения находится в конъюнктивной нормальной форме.
  3. Дизъюнкция любых двух ранее построенных выражений имеет конъюнктивную нормальную форму.
  4. Конъюнкция любых двух ранее построенных выражений имеет конъюнктивную нормальную форму.
  5. Любое другое выражение не в соединительной нормальной форме.

Любое логическое выражение может быть преобразовано (не однозначно) в логически эквивалентное выражение в конъюнктивной нормальной форме (см. Этот алгоритм ). Вам не нужно использовать этот конкретный алгоритм.

Входные данные:

Вы можете принять участие в любом удобном формате; например, символическое логическое выражение (если ваш язык поддерживает это), строка, некоторая другая структура данных. Вам не нужно использовать те же символы для истинных, ложных и логических операторов, что и здесь, но ваш выбор должен быть последовательным, и вы должны объяснить свой выбор в своем ответе, если он неясен. Вы не можете принимать любые другие входные данные или кодировать любую дополнительную информацию в своем формате ввода. У вас должен быть какой-то способ выражения произвольного числа атомарных выражений; например, целые числа, символы, строки и т. д.

Вывод:

Формула в соединительной нормальной форме, опять же в любом удобном формате. Он не обязательно должен быть в том же формате, что и ваши входные данные, но вы должны объяснить, есть ли различия.

Тестовые случаи:

P ∧ (P ⇒ R) -> P ∧ R
P ⇔ (¬ P) -> ⊥
(¬ P) ∨ (Q ⇔ (P ∧ R)) -> ((¬ P) ∨ ((¬ Q) ∨ R)) ∧ ((¬ P) ∨ (Q ∨ (¬ R)))

Ноты:

  1. Если входное выражение является тавтологией, будет правильным выводом. Точно так же, если входное выражение является противоречием, будет допустимым выводом.
  2. Оба ваших формата ввода и вывода должны иметь четко определенный порядок операций, способный выразить все возможные логические выражения. Вам могут понадобиться какие-то круглые скобки.
  3. Вы можете использовать любой четко определенный выбор инфиксной, префиксной или постфиксной нотации для логических операций. Если ваш выбор отличается от стандартного (отрицание - префикс, остальные - инфикс), объясните это в своем ответе.
  4. Конъюнктивная нормальная форма не уникальна в целом (даже до переупорядочения). Вам нужно только вывести на действительную форму.
  5. Однако вы представляете атомарные выражения, они должны отличаться от логических констант, операторов и символов группировки (если они у вас есть).
  6. Разрешены встроенные модули, которые вычисляют конъюнктивную нормальную форму.
  7. Стандартные лазейки запрещены.
  8. Это ; кратчайший ответ (в байтах) выигрывает.
ngenisis
источник
1
CNF не уникален вплоть до переупорядочения: эквивалентные выражения Pи (P ∨ Q) ∧ (P ∨ (¬Q))оба в соединительной нормальной форме.
Грег Мартин
1
Проверка на тавтологию / противоречие является второй задачей, не связанной с трансформацией CNF, поэтому я бы предложил отказаться от этого требования и поставить перед ним собственную задачу.
Лайкони
@Laikoni Очень верно. Я обновил вопрос, чтобы сказать, что это возможные результаты для тавтологий и противоречий, а не требуемые результаты.
ngenisis

Ответы:

1

Максима, 4 байта

pcnf

Попробуйте онлайн!

Вы можете использовать implies, eq, and, or операторы импликации, эквивалентности, конъюнкции и дизъюнкции соответственно.

rahnema1
источник
8

Ты будешь меня ненавидеть ....

Mathematica, 23 байта

#~BooleanConvert~"CNF"&

Вход будет использовать Trueи Falseвместо и , но в противном случае будет выглядеть очень похожи на обозначение вопроса: все символы ¬, , , и признается в Mathematica (если вход с UTF-8 символов 00AC, F523, 29E6, 2227 и 2228 соответственно), а скобки действуют так, как вы и ожидаете.

По умолчанию в выходных данных будут использоваться предпочтительные символы Mathematica: например, (! P || ! Q || R) && (! P || Q || ! R)вместо последнего будет выводиться последний контрольный пример ((¬ P) ∨ ((¬ Q) ∨ R)) ∧ ((¬ P) ∨ (Q ∨ (¬ R))). Тем не менее, изменение функции на

TraditionalForm[#~BooleanConvert~"CNF"]&

сделает вывод красивым и соответствующим этим обычным символам:

традиционная форма

Грег Мартин
источник
2

JavaScript (ES6), 127 байт

f=(s,t='',p=s.match(/[A-Z]/),r=RegExp(p,'g'))=>p?'('+f(s.replace(r,1),t+'|'+p)+')&('+f(s.replace(r,0),t+'|!'+p)+')':eval(s)?1:0+t

Формат ввода / вывода выглядит следующим образом (в порядке приоритета):

  • (: (
  • ): )
  • : 1
  • : 0
  • ¬: !
  • : <=
  • : ==
  • : &
  • : |

Примеры:

P&(P<=R) -> ((1)&(0|P|!R))&((0|!P|R)&(0|!P|!R))
P==(!P) -> (0|P)&(0|!P)
(!P)|(Q==(P&R)) -> (((1)&(0|P|Q|!R))&((0|P|!Q|R)&(1)))&(((1)&(1))&((1)&(1)))

Функция тривиально переписана для получения дизъюнктивной нормальной формы:

f=(s,t='',p=s.match(/[A-Z]/),r=RegExp(p,'g'))=>p?'('f(s.replace(r,1),t+'&'+p)+')|('+f(s.replace(r,0),t+'&!'+p)+')':eval(s)?1+t:0

8 байт можно было бы сохранить из этой версии, если бы мне было позволено принять вышеупомянутый приоритет при выводе, что позволило бы удалить все скобки из выходных примеров:

P&(P<=R) -> ((1&P&R)|(0))|((0)|(0))
P==(!P) -> (0)|(0)
(!P)|(Q==(P&R)) -> (((1&P&Q&R)|(0))|((0)|(1&P&!Q&!R)))|(((1&!P&Q&R)|(1&!P&Q&!R))|((1&!P&!Q&R)|(1&!P&!Q&!R)))
Нил
источник