Use 2SAT para mostrar que um gráfico de implicação deve ter um ciclo se não for satisfatório

Question

Usando gráficos de 2SAT e implicação, como posso provar as seguintes propriedades dos gráficos de implicação:

Suponha que haja um caminho dirigido entre literais L1 e L2 em g_φ. Então há também um caminho dirigido entre seus complementos. Então, há τ, uma tarefa de verdade satisfazendo φ onde τ (l1) é verdadeiro, então τ (l2) também deve ser verdadeiro.

Usando isso, mostre que φ é insatisfatório <=> Há algum ciclo direcionado em g_φ contendo uma variável x e seu complemento.

Onde g_φ é o gráfico de implicação dirigido de 2sat contendo fórmula φ com n variáveis. Portanto, vértices 2n com um para cada literal possível em φ, e bordas (não L1, L2) e (não L2, L1) para cada cláusula (L1 ∨ L2) em φ.

Minha primeira intuição foi uma prova por contradição, no entanto, não consegui construir uma suposição geral suficientemente. Eu então tentei mostrar que, se a tarefa da verdade significar que L1 e L2 são verdadeiras, construindo um ciclo conectando todas as variáveis, a atribuição é válida apenas quando essas bordas existem. No entanto, isso não parece rigoroso o suficiente, já que não estou entendendo adequadamente por que o ciclo requer que o complemento de X exista.

Atualmente eu construo g adicionando um vértice para cada variável x e é complemento também. Em seguida, para cada cláusula (a v b) adiciono uma borda entre não A e B e não B e A.

No entanto, não consigo ver como isso formaria especificamente um ciclo.

Trabalho do livro didático da extremidade.

Answer 1

Aqui está um esboço de prova. Vamos mostrar que a fórmula dada é insatisfatível IFF Existe um ciclo contendo ambos $ x $ e $ \ lnot x $ < / span>, para alguma variável $ x $ .

Suponha primeiro que existe um ciclo contendo ambos $ x $ e $ \ lnot x $ . A existência de um caminho $ x \ to ^ * y $ no gráfico de implicação significa que em uma atribuição satisfatória, se $ X $ Holds, em seguida, o mesmo acontece com $ y $ (você pode provar isso por indução no comprimento do caminho). Como há um ciclo contendo ambos $ x $ e $ \ lnot x $ , há caminhos $ x \ to ^ * \ lnot x $ e $ \ lnot x \ to ^ * x $ . Em qualquer tarefa satisfatória, seja $ x $ ou $ \ lnot x $ detém, e ambos os casos levam a Contradição.

Suponha que next se não há ciclos contendo ambos $ x $ e $ \ lnot x $ . Vamos construir uma tarefa satisfatória da seguinte forma. Escolha alguma variável $ x $ . Se houver um caminho $ x \ to ^ * lnot x $ , atribuir $ x= F $ , e para cada literal $ \ ell $ tal que $ \ lnot x \ to ^ * \ ell $ , Atribua o valor à variável subjacente que torna a $ \ ell $ true. Você não pode estar atribuindo a mesma variável dois valores de verdade diferentes, uma vez que se $ \ lnot x \ to ^ * y $ e $ \ lnot x \ to ^ \ \ lnot y $ então também $ y \ to ^ * x $ e assim também $ \ lnot x \ to ^ * x $ , completando um ciclo envolvendo $ x $ e $ \ lnot x $ .

Se houver um caminho $ \ lnot x \ to ^ * x $ , atribuir $ x= t $ < / Span> e continue analogamente.

Se nenhum desses caminhos existir, atribuir $ x $ arbitrariamente e continue como antes. Isso não pode levar a uma contradição, pelo seguinte motivo. Suponha que atribuímos $ x= F $ e que existem caminhos $ x \ to ^ * y $ e $ x \ to ^ * \ lnot y $ . Em seguida, há também um caminho $ y \ to ^ * \ lnot x $ e assim um caminho $ x \ to ^ * \ lnot x $ , contradizando a suposição de que nenhum dos dois caminhos existe.

Se após este processo há alguma variável não atribuída à esquerda, escolha uma delas e repita até que a atribuição cubra todas as variáveis.