[其他] 2-Satisfiability

[fmtshk (fmtshk)]

https://i.imgur.com/KW7Gczj.jpg
大家好，請問這題的紅色底線那小題，意思是要把它轉成( OR )AND( OR )AND...AND( OR )
這種形式對嗎？
https://i.imgur.com/v0wEisv.jpg
我寫成這樣不知是否可行....

感謝各位

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.58.167 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1604307817.A.9E4.html
→ hwanger     : 你理解的沒錯 不過2-CNF畢竟是conjunctive normal
→ hwanger     : form 所以他的每個clauses都是literals用
→ hwanger     : disjunction連接才對 所以第一個被轉換的X2 AND -X3
→ hwanger     : 應該換成(X2 OR X2) AND (-X3 OR -X3)才對 你原本的
→ hwanger     : -(-X2 OR X3)並不是變數或變數的否定用or來連接的形
→ hwanger     : 式 至於第一個XOR的部份 則是對的
→ hwanger     :          二
→ hwanger     : 把X2 AND X3換成(X2 OR X3) AND (-X2 OR X3) AND
→ hwanger     : (X2 OR -X3) 應該會更好
→ hwanger     : 忘了X3前面有否定 所以應該是把X2 AND -X3換成
→ hwanger     : (X2 OR -X3) AND (-X2 OR -X3) AND (X2 OR X3)才對
→ fmtshk      : 原來如此，感謝！
→ fmtshk      : https://i.imgur.com/BCzxFLP.jpg
→ fmtshk      : 順便畫了implication graph
→ hwanger     : 圖沒錯 再依接下來的小題就可以得satisfiable的結
→ hwanger     : 論(不過題目也只問scc而已 XD)