如何将复杂的布尔表达式解析为所有可能的组合

Question

我正在尝试解决以下问题。我有一组逻辑运算，我想将它们解析为所有可能的组合。例如：

“((A | X) & B & C) | (C | E) & A & ~Y”

应产生以下解决方案：

“A & B & C”“X & B & C”“C & A & ~Y”“E & A & ~Y”

过去，我在这里得到了类似问题的帮助，并得到了解决方案：

from sympy.parsing.sympy_parser import parse_expr
from sympy.logic.boolalg import to_dnf

lst = ['(a | b) & (c & d)', '(e & f) | (g | h)', '(i | j) | k']
    
comb = set()

for exp in lst:
    log_expr = str(to_dnf(parse_expr(exp)))
    for e in log_expr.split('|'):
        comb.add(str(parse_expr(e)))

print(comb)

此代码在附加 OR 子句之前一直有效。有效的方法会是什么样子？ 表达式可能会变得非常复杂，具有多层括号、“与”、“或”和“非”运算。

Answer 1

你可以在你的逻辑中应用德摩根公式，即：

A AND B = NOT (NOT A OR NOT B)

和

A OR B = NOT (NOT A AND NOT B)

因此您可以将 OR 转换为 AND，反之亦然。请注意，我在这两种情况下都对方程进行了否定，以简化左侧以不假设否定，但如果您的 OR 或 AND 被否定，那么您可以使用德摩根公式的原始形式。因此，如果您不喜欢您的 OR 并且想要“标准化”您的表达式，那么理论已经为您制定好了，您只需将其应用到您的实际公式中即可。