Объяснение преобразования CNF в императивную нормальную форму в 2-SAT проблема?

Question

так что многим из вас этот вопрос может показаться глупым, но мне несколько трудно найти asp преобразование предложения CNF в INF.

Я проходил через это article где говорится:

Сначала нам нужно преобразовать задачу в другую форму, так называемую импликативную нормальную форму. Обратите внимание, что выражение a∨b эквивалентно ¬a⇒b∧¬b⇒a (если одна из двух переменных является ложной, то другая должна быть истинной).

Может кто-нибудь объяснить, как мы получаем этот результат / как это преобразование имеет смысл? Я понятия не имею, что означает этот знак "=>". Заранее спасибо!

Обновление 1 : Если у вас возникли сомнения по поводу использования различных логических символов, обратитесь к этой wiki .

Answer 1

=> подразумевается, с таблицей истинности:

A B | A => B
----+-------
F F |   T
F T |   T
T F |   F
T T |   T

Фактически, вы можете показать, что a => b эквивалентно ~a \/ b. (Просто заполните таблицы правды.)

Теперь у нас есть:

  ~a => b 
= ~(~a) \/ b
= a \/ b

Итак, это еще сильнее: a \/ b эквивалентно ~a => b. Вы также можете показать, что это также эквивалентно ~b => a; таким образом, взятие соединения может быть излишним, но оно не меняет эквивалентности.

Если вы сомневаетесь, всегда рисуйте полные таблицы истинности, предполагая, что у вас есть 4-5 переменных, это было бы очень познавательно. Если у вас есть больше переменных, используйте решатель SAT / SMT, чтобы доказать эквивалентность. Вот для чего они хороши.