CNF 真实 table

Question

我有一个由 truth table 表示的布尔函数。

总共有 10 个变量，我希望得到长度合理的 CNF（不一定是最短的，但足够短）。

我该怎么做？

Python 脚本或任何 public 可用的软件，例如 Mathematica/Mapple/etc 也适用于我。

Answer 1

sympy 包允许你做这个 out-of-the 框。 (https://www.sympy.org/en/index.html)

这是一个简单的例子。假设你有三个变量并且真相 table 编码以下集合：

  (x & y & !z) \/ (x & !y & z)

（即只有 x=true, y=true, z=false 和 x=true, y=false, z=true 对应的行是 true，而其他所有行都是 false）。您可以轻松地编写代码并将其转换为 CNF，如下所示：

$ python3
Python 3.8.5 (default, Jul 21 2020, 10:48:26)
[Clang 11.0.3 (clang-1103.0.32.62)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from sympy import *
>>> x, y, z = symbols('x y z')
>>> simplify_logic((x & y & ~z) | (x & ~y & z), form="cnf")
x & (y | z) & (~y | ~z)

simplify_logic可以根据form参数转换为CNF或DNF。看这里：https://github.com/sympy/sympy/blob/c3087c883be02ad228820ff714ad6eb9af1ad868/sympy/logic/boolalg.py#L2746-L2827

请注意，CNF 扩展通常代价高昂，而 Tseitin 编码是避免这种复杂性的首选方法 (https://en.wikipedia.org/wiki/Tseytin_transformation)。但它有引入新变量的缺点

CNF 真实 table

CNF by truth table

python

math

sat

boolean-algebra

cnf