作者fmtshk (fmtshk)
看板Math
標題[其他] 2-Satisfiability
時間Mon Nov 2 17:03:35 2020
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://webptt.com/m.aspx?n=bbs/Math/M.1604307817.A.9E4.html
1F：→ hwanger : 你理解的沒錯 不過2-CNF畢竟是conjunctive normal 11/02 18:10
2F：→ hwanger : form 所以他的每個clauses都是literals用 11/02 18:12
3F：→ hwanger : disjunction連接才對 所以第一個被轉換的X2 AND -X3 11/02 18:13
4F：→ hwanger : 應該換成(X2 OR X2) AND (-X3 OR -X3)才對 你原本的 11/02 18:14
5F：→ hwanger : -(-X2 OR X3)並不是變數或變數的否定用or來連接的形 11/02 18:16
6F：→ hwanger : 式 至於第一個XOR的部份 則是對的 11/02 18:17
7F：→ hwanger : 二 11/02 18:29
8F：→ hwanger : 把X2 AND X3換成(X2 OR X3) AND (-X2 OR X3) AND 11/02 19:04
9F：→ hwanger : (X2 OR -X3) 應該會更好 11/02 19:04
10F：→ hwanger : 忘了X3前面有否定 所以應該是把X2 AND -X3換成 11/02 19:08
11F：→ hwanger : (X2 OR -X3) AND (-X2 OR -X3) AND (X2 OR X3)才對 11/02 19:09
12F：→ fmtshk : 原來如此，感謝！ 11/02 22:48
14F：→ fmtshk : 順便畫了implication graph 11/02 22:53
15F：→ hwanger : 圖沒錯 再依接下來的小題就可以得satisfiable的結 11/03 00:00
16F：→ hwanger : 論(不過題目也只問scc而已 XD) 11/03 00:00