2-CNF Problem — Doubts

Правка en1, от LoppA, 2017-04-04 16:37:45

Hi I'm having trouble with the 2-CNF (Conjuctive Normal Form) problem, not just 2-SAT but the more general case of Conjuctive Normal Forms, ie :a => b (a implies b), c => ¬d (c implies not d). I've got some doubts, if you can help me with any of them it would help me a lot.

1 — What is the answer for the case (a => b) and (b => ¬a) and (¬a => c) and (c => d) and (d => ¬c)? I think its not satisfiable but some algorithms just get the variable with higher toposort between (x and ¬x).

2 — There is an algorithm to find if some 2-CNF is solvable? And if its solvable how can we get some solution.

3 -

Теги graph, 2-cnf

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский LoppA 2017-04-04 17:12:09 0 (published)
en7 Английский LoppA 2017-04-04 17:10:28 1 Tiny change: ' ¬x has no in edge n' -> ' ¬x has not in edge n'
en6 Английский LoppA 2017-04-04 17:09:26 28
en5 Английский LoppA 2017-04-04 17:08:45 88
en4 Английский LoppA 2017-04-04 17:04:39 93
en3 Английский LoppA 2017-04-04 16:57:18 5
en2 Английский LoppA 2017-04-04 16:56:10 720
en1 Английский LoppA 2017-04-04 16:37:45 742 Initial revision (saved to drafts)