[其他] 2-Satisfiability

看板Math作者 (fmtshk)時間3年前 (2020/11/02 17:03), 編輯推噓0(0推 0噓 16→)
留言16則, 2人參與, 3年前最新討論串1/1
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
→
11/02 18:10, 3年前 , 1F
你理解的沒錯 不過2-CNF畢竟是conjunctive normal
11/02 18:10, 1F
→
11/02 18:12, 3年前 , 2F
form 所以他的每個clauses都是literals用
11/02 18:12, 2F
→
11/02 18:13, 3年前 , 3F
disjunction連接才對 所以第一個被轉換的X2 AND -X3
11/02 18:13, 3F
→
11/02 18:14, 3年前 , 4F
應該換成(X2 OR X2) AND (-X3 OR -X3)才對 你原本的
11/02 18:14, 4F
→
11/02 18:16, 3年前 , 5F
-(-X2 OR X3)並不是變數或變數的否定用or來連接的形
11/02 18:16, 5F
→
11/02 18:17, 3年前 , 6F
式 至於第一個XOR的部份 則是對的
11/02 18:17, 6F
→
11/02 18:29, 3年前 , 7F
二
11/02 18:29, 7F
→
11/02 19:04, 3年前 , 8F
把X2 AND X3換成(X2 OR X3) AND (-X2 OR X3) AND
11/02 19:04, 8F
→
11/02 19:04, 3年前 , 9F
(X2 OR -X3) 應該會更好
11/02 19:04, 9F
→
11/02 19:08, 3年前 , 10F
忘了X3前面有否定 所以應該是把X2 AND -X3換成
11/02 19:08, 10F
→
11/02 19:09, 3年前 , 11F
(X2 OR -X3) AND (-X2 OR -X3) AND (X2 OR X3)才對
11/02 19:09, 11F
→
11/02 22:48, 3年前 , 12F
原來如此，感謝！
11/02 22:48, 12F
→
11/02 22:53, 3年前 , 13F
11/02 22:53, 13F
→
11/02 22:53, 3年前 , 14F
順便畫了implication graph
11/02 22:53, 14F
→
11/03 00:00, 3年前 , 15F
圖沒錯 再依接下來的小題就可以得satisfiable的結
11/03 00:00, 15F
→
11/03 00:00, 3年前 , 16F
論(不過題目也只問scc而已 XD)
11/03 00:00, 16F
‣ 更多 fmtshk 的文章
文章代碼(AID): #1Vdyjfda (Math)