python - 扩展逻辑语句（乘法）

Question

我正在寻找一种方法来扩展形式的逻辑表达式（在字符串中）：

'(A 或 B) 和 ((C 和 D) 或 E)'

在 Python 中生成所有正集的列表，即

['A and C and D',
'A and E',
'B and C and D',
'B and E']

但我一直无法找到如何做到这一点。我调查了 pyparser，但我无法确定在这种情况下哪个示例是相关的。通过某种逻辑操作，这可能很容易，但我不知道任何形式逻辑。任何帮助或对可能有帮助的资源的参考将不胜感激。

Answer 1

这是 pyparsing 位，取自示例SimpleBool.py。首先，使用infixNotation（以前称为operatorPrecedence）定义支持括号分组并识别操作优先级的表达式语法：

from pyparsing import *

term = Word(alphas)

AND = Keyword("and")
OR = Keyword("or")

expr = infixNotation(term,
    [
    (AND, 2, opAssoc.LEFT),
    (OR, 2, opAssoc.LEFT),
    ])

sample = '(A or B) and ((C and D) or E)'

result = expr.parseString(sample)

from pprint import pprint
pprint(result.asList())

印刷：

[[['A', 'or', 'B'], 'and', [['C', 'and', 'D'], 'or', 'E']]]

从这里，我们可以看到表达式至少被正确解析了。

接下来，我们将解析操作添加到操作层次结构的每个级别。对于此处的解析操作，我们实际上传递了类，因此解析器将调用类构造函数和初始化程序并返回特定子表达式的类实例，而不是执行函数并返回一些值：

class Operation(object):
    def __init__(self, tokens):
        self._tokens = tokens[0]
        self.assign()

    def assign(self):
        """
        function to copy tokens to object attributes
        """

    def __repr__(self):
        return self.__class__.__name__ + ":" + repr(self.__dict__)
    __str__ = __repr__

class BinOp(Operation):
    def assign(self):
        self.op = self._tokens[1]
        self.terms = self._tokens[0::2]
        del self._tokens

class AndOp(BinOp):
    pass

class OrOp(BinOp):
    pass

expr = infixNotation(term,
    [
    (AND, 2, opAssoc.LEFT, AndOp),
    (OR, 2, opAssoc.LEFT, OrOp),
    ])

sample = '(A or B) and ((C and D) or E)'

result = expr.parseString(sample)
pprint(result.asList())

返回：

[AndOp:{'terms': [OrOp:{'terms': ['A', 'B'], 'op': 'or'}, 
                   OrOp:{'terms': [AndOp:{'terms': ['C', 'D'], 
                                    'op': 'and'}, 'E'], 'op': 'or'}],
'op': 'and'}]

现在表达式已转换为子表达式的数据结构，我让您来完成向 AndOp 和 OrOp 添加方法的工作，以生成将总体评估为 True 的各种术语组合。（查看反转正则表达式的invregex.py示例中的逻辑，了解如何将生成器函数添加到已解析的类以生成所需的不同术语组合。）

Answer 2

听起来好像您想将这些表达式转换为Disjunctive Normal Form。一种典型的算法是 Quine-McCluskey 算法；您可以在相关的Wikipedia 文章和此 SO question的答案中找到有关其 Python 实现的一些信息。