python - 将复杂逻辑表达式转换为 CNF（无指数爆炸）

Question

在我的布尔逻辑问题中，我有一组长度超过 10,000（从 10 到 100k）的变量（编码为整数）。每个变量都有它的一组约束，即来自同一组的其他变量与之相矛盾。矛盾是相互的，即

(1 & -2) | (2 & -1)

任务是最大化相互满足的变量的数量。在SAT术语中，它应该被表述为：

MAXIMIZE {
(1 & -2 & -3 ...) |
(2 & -1 & -4 ...) |
...
}

这个表达式直观地是DNF 格式，但是 SAT 求解器使用CNF表达式，所以转换是必要的。

我想要：

• 使用 SAT 求解器（我使用PySAT 工具包）求解表达式，这意味着将其转换为 CNF 形式，同时避免子句的指数增长（需要应用Tseitin 转换/基数约束——但只是不知道如何）;
• 最大化表达式中真实子句的数量，即解决“max-SAT”问题，满足变量的最大数量

请帮我制定一个有效的 CNF（参考如何在 Python SAT 求解器或原始表达式中完成）。

标签： pythonbooleanlogical-operatorsboolean-expressionsat