作者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/cn.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