1

所以我得到了这个作业问题，我们被要求将一个 k 独立集可满足性问题简化为合取范式下的 3-SAT 子句集。

所以对于G (V, E) 我们有顶点集
V = {x1, x2, x3, x4, x5, x6}
和边集
E = { e1 = (x1,x3), e2 = (x1,x5), e3 = (x1,x6), e4 = (x2,x5), e5 = (x2,x6), e6 = (x3,x4), e7 = (x3,x5), e8 = (x5,x6) }

我的第一种方法是每条边都有一个子句，因为我们不能在独立集中的两个顶点之间有一条边：
e1: (¬x1 v ¬x3)
e2: (¬x1 v ¬x5)
e3: (¬ x1 v ¬x6)
e4: (¬x2 v ¬x5)
e5: (¬x2 v ¬x6)
e6: (¬x3 v ¬x4)
e7: (¬x3 v ¬x5)
e8: (¬x5 v ¬x6)

但问题是，例如，对于 k = 3，如何编写子句以确保至少 3 个不同的变量 (xi) 设置为 true ？
使用加权 2 可满足性可以实现这一点，但仅使用良好的旧 3-SAT 似乎很难实现。
有关如何进行的任何提示？

4

1 回答 1

2

如果您关心的是这个 G 和 k = 3，那么为所有{ i , j , k, ℓ } ⊆ V和然后将它们简化为 3-CNF，例如，(x ∨ y ∨ z ∨ w) 变为 (v ∨ x ∨ y) ∧ (¬v ∨ z ∨ w)，其中 v 是一个新变量。

一般来说，你会想要

  1. 定义一个布尔电路来计算 x1 + … + xn ≥ k（您可以使用波纹进位加法器在二进制补码算法中计算 x 1 + … + x n - k ，然后反转符号位）。

  2. 将此电路转换为 3-CNF 公式。首先，用多个双输入门替换具有两个以上输入的门。然后为电路中的每个节点创建一个变量。为每个门写四个约束输出的子句，每个可能的输入一个，例如，如果有一个输入 x 和 y 以及输出 z 的 AND 门，那么写子句 (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∧ ¬z) ∧ (¬x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z)。异或门将是 (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∧ z) ∧ (¬x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)。

于 2020-12-20T13:26:12.510 回答