python - 如何在不使用真值表的情况下用 Python 中的无关项简化 bool 表达式？

Question

我正在尝试将涉及数百个 bool 变量的 bool 表达式简化为 OR of Ands 形式 (DNF)。此外，还有一些don't care 项可以用另一个 bool 表达式来表示。

我发现有几个 Python 包，例如 SymPy，可用于 bool 表达式最小化。但是，它无法处理表达式格式中的don't care 术语。

例如，

>>> from sympy.logic import SOPform
>>> from sympy import symbols
>>> w, x, y, z = symbols('w x y z')
>>> minterms = [[0, 0, 0, 1], [0, 0, 1, 1],
...             [0, 1, 1, 1], [1, 0, 1, 1], [1, 1, 1, 1]]
>>> dontcares = [[0, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 1]]
>>> SOPform([w, x, y, z], minterms, dontcares)
Or(And(Not(w), z), And(y, z))

SOPform函数可以处理dontcares项，但它需要真值表格式的项，这不适合我的情况，因为变量太多。

另一个函数 simplify_logic 接受表达式格式，但没有 dontcares 项的选项。

>>> from sympy.logic import simplify_logic
>>> from sympy.abc import x, y, z
>>> from sympy import S
>>> b = (~x & ~y & ~z) | ( ~x & ~y & z)
>>> simplify_logic(b)
And(Not(x), Not(y))

Python 中有没有一种方法可以处理表达式格式中不关心术语的 bool 表达式的最小化？

谢谢!

Answer 1

这里的问题是使代码更具可扩展性，以便它可以处理大量输入。

我假设输入的最小项和不关心项是整数格式(这是我所知道的除真值表格式之外的唯一其他格式)

N = 4           # number of boolean variables
minterms = [1, 3, 7, 11, 15]
dontcares = [0, 2, 5]

---

转换为真值表格式:

1. 首先将十进制转换为二进制 ( see here )

   >>> num = 2
   >>> f'{num:b}'
   '10'
   

2. 由于有 N 个变量，在本例中为 4 个，我们需要填充额外的零。 ( see here )

   >>> '10'.zfill(4)
   '0010'
   

3. 最后将其转换为整数列表

   >>> [int(i) for i in '0010']
   [0, 0, 1, 0]
   

将这三个步骤组合成一个函数，我们得到

def convert(num, N):
    return [int(i) for i in f'{num:b}'.zfill(N)]

---

在此之后，过程就很简单了。要生成 N 符号，我们可以简单地使用 for 循环并为符号变量添加数字后缀。最后在 SOPform 的输出上应用 simplify_logic。

X = [symbols(f'x{i+1}') for i in range(N)]
# [x1, x2, x3, x4]

minterms_new = [convert(t, N) for t in minterms]
dontcares_new = [convert(t, N) for t in dontcares]
ans = SOPform(X, minterms_new, dontcares_new)

print(ans)
# (x3 & x4) | (x4 & ~x1)

print(simplify_logic(ans))
# x4 & (x3 | ~x1)