Используйте 2SAT, чтобы показать, что диаграммы подразумеваний должны иметь цикл, если он не удовлетворен

Question

Использование диаграмм 2SAT и подразумеваний, как я могу доказать следующие свойства диаграмм подразумеваний:

Предположим, что есть направленный путь между литералами L1 и L2 в G_φ. Тогда существует также направленный путь между их дополнениями. Затем есть τ, назначение истины, удовлетворяющее φ, где τ (l1) верно, то τ (l2) также должен быть правдой.

Использование этого, показать, что φ неудовлетворенна <=> Существует некоторое направленный цикл в G_φ, содержащий переменную X и его дополнение.

, где G_φ является направленным диаграммой следствия 2SAT, содержащая формула φ с n переменными. Следовательно, 2N вершины с одним для каждого возможного буквального литерала в Φ, и края (не L1, L2) и (не L2, L1) для каждого предложения (L1 ∨ L2) в φ.

Моя первая интуиция была доказательством противоречия, однако я не смог построить достаточно общего предположения. Затем я попытался показать, что если назначение правды означает, что L1 и L2 верны, то путем создания цикла, соединяющего все переменные, назначение действитеется только при наличии этих ребер. Однако это не кажется строгими достаточно строгими, так как я не правильно понимаю, почему цикл требует дополнения X для существования.

В настоящее время я строю g, добавив вершину для каждой переменной X, а также его дополнение. Тогда для каждого пункта (A V b) добавляю край между не A и B, а не B и A.

Однако я не вижу, как это конкретно образует цикл.

Работа учебника Siperer.

Answer 1

Вот достойный эскиз. Мы покажем, что заданная формула является неудовлетворительной IFF, существует цикл, содержащий как $ x $ и $ \ lnot x $ < / span>, для некоторой переменной $ x $ .

Предположим, что в первую очередь существует цикл, содержащий как $ x $ и $ \ lnot x $ . Наличие пути $ x \ to ^ * y $ в графике подразумеваний означает, что в удовлетворительном назначении, если $ x $ Тогда включает в себя значение $ y $ (вы можете доказать его по индукции по длине пути). Поскольку есть цикл, содержащий как $ x $ и $ \ lnot x $ , есть пути $ x \ to ^ * \ lnot x $ и $ \ lnot x \ to ^ * x $ . В любом удовлетворенном задании либо $ x $ или $ \ lnot x $ holds, и оба случая приводят к противоречие.

Предположим, что рядом с тем, что нет циклов, содержащих как $ x $ и $ \ lnot x $ . Мы построим удовлетворяющее задание следующим образом. Выберите некоторую переменную $ x $ . Если есть путь $ x \ to ^ * \ lnot x $ , назначить $ x= f $ и для каждого буквального уровня $ \ ell $ такой, что $ \ lnot x \ to ^ * \ ell $ Назначьте значение базовой переменной, которая делает $ \ ell $ true. Вы не можете назначить одинаковую переменную два разных значения правды, поскольку, если $ \ lnot x \ to ^ * y $ и $ \ lnot x \ to ^ * \ lnot y $ Тогда также $ y \ to ^ * x $ а так также $ x $ и $ \ lnot x $ .

Если есть путь $ \ lnot x \ to ^ * x $ , назначить $ x= t $ < / span> и продолжайте аналогично.

Если ни один из этих путей не существует, назначить $ x $ произвольно и продолжаться как раньше. Это не может привести к противоречию по следующей причине. Предположим, что мы назначаем $ x= f $ , и что есть пути $ x \ to ^ * y $ и $ x \ to ^ * \ lnot y $ . Тогда есть также путь $ y \ to ^ * \ lnot x $ и поэтому путь $ x \ to ^ * \ lnot x $ , противоречив предположению, что ни один из двух путей не существует.

Если после этого процесса остается некоторая неназначенная переменная, выберите один из них и повторите, пока назначение не охватывает все переменные.