2可满足性问题算法

Question

任何人都可以解释2可满足性问题的算法还是提供相同的链接？我无法找到理解它的好链接。

Answer 1

你可以用贪婪的方法解决它。 或者使用图论，这里是使用图论解释解的链接。 http://www.cs.tau.ac.il/~safra/Complexity/2SAT.ppt

Answer 2

这是关于该主题的Wikipedia页面，其中描述了一个多项式时间算法。 （仅仅尝试所有不同真值分配的蛮力算法就是指数时间。）也许一些进一步的解释会有所帮助。

表述“如果P则Q”是假仅当P为真和Q是假的。因此表达式具有与“Q或不P”相同的真值表值。它也相当于它的对立性，即“如果不是Q然后不是P”，并且又相当于“不是P或Q”（与另一个相同）。

所以算法涉及取代形式为“A或B”的每个表达式中，用两个表达式，“如果不是A，那么B”和“如果不是则B A”。 （把它的另一种方式，A和B不能同时为假。）

接下来，构造表示这些影响的曲线图。为每个“A”和“不是A”创建节点，并为上面获得的每个影响添加链接。

最后一步是确保没有一个变量是相当于其自身的否定。也就是说，对于每个变量A（或不是A），按照链接发现所有可以从它到达的节点，并注意检测循环。

如果这些变量中的一个，A，可以达到“非A”，和“未A”也可以达到A，则原始表达式是不令人满意的。 （这是一个悖论。）如果没有一个变量做到这一点，那么它是可以满足的。

（这没关系，如果A蕴含“不是”，而不是其他方式这仅仅意味着一个必须被否定，满足表达式。）

Answer 3

如果你有个变量和M条款：

用2n个顶点创建一个图形：直观上，每个顶点类似于每个变量的真或假真值。对于每个子句（a v b），其中a和b是文字，创建一个从！a到b和从！b到a的边。这些边缘意味着如果a不是真的，那么b必须是真的，反之亦然。

一旦有向图被创建，经过图，看看是否有是同时包含A和！一对一些变量的循环。如果存在，那么2SAT就不可满足（因为a意味着！a，反之亦然）。否则，它是令人满意的，这甚至可以给你一个令人满意的假设（选择一些字面意思，以便a不暗示！a，从那里强制所有含义，重复）。您可以使用任何标准图算法ala Breadth-First Search，Floyd-Warshall或这些算法来完成这部分任务，具体取决于您对算法的时间复杂程度有多敏感。

Answer 4

2 satisfiabilty：！

如果x & x被强连接 然后从X，我们可以达到X 从X，我们可以达到X

所以在我们的操作中， 万一！ x， 我们只有2个选项， 1.taking x（x）导致！X 2.rejecting X，导致X 两者的选择都是导致的在同一时间服用，并拒绝选择的悖论

因此可满足是不可能的（X！）：d