Expandiendo una statement lógica (multiplicando)

Estoy buscando una manera de expandir una expresión lógica (en una cadena) de la forma:

‘(A o B) y ((C y D) o E)’

en Python para producir una lista de todos los conjuntos positivos, es decir,

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

pero no he podido encontrar cómo hacer esto. He investigado pyparser, pero no puedo averiguar qué ejemplo es relevante en este caso. Esto puede ser muy fácil con algún tipo de manipulación lógica, pero no conozco ninguna lógica formal. Cualquier ayuda, o una referencia a un recurso que pueda ayudar sería muy apreciada.

    Aquí está el bit pyparsing, tomado del ejemplo SimpleBool.py . Primero, use infixNotation (anteriormente conocida como operatorPrecedence ) para definir una gramática de expresión que admita la agrupación entre paréntesis y reconozca la precedencia de las operaciones:

     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()) 

    huellas dactilares:

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

    A partir de esto, podemos ver que la expresión al menos se analiza correctamente.

    A continuación, agregamos acciones de análisis a cada nivel de la jerarquía de operaciones. Para las acciones de análisis aquí, en realidad pasamos clases, de modo que en lugar de ejecutar funciones y devolver algún valor, el analizador llamará al constructor y al inicializador de la clase y devolverá una instancia de clase para la subexpresión en particular:

     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()) 

    devoluciones:

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

    Ahora que la expresión se ha convertido en una estructura de datos de subexpresiones, le dejo que haga el trabajo de agregar métodos a AndOp y OrOp para generar las diversas combinaciones de términos que se evaluarán en general a True. (Mire la lógica en el ejemplo invregex.py que invierte expresiones regulares para obtener ideas sobre cómo agregar funciones de generador a las clases analizadas para generar las diferentes combinaciones de términos que desee).

    Suena como si quisiera convertir estas expresiones a una forma normal disyuntiva . Un algoritmo canónico para hacer eso es el algoritmo Quine-McCluskey; Puede encontrar información sobre las implementaciones de Python en el artículo relevante de Wikipedia y en las respuestas a esta pregunta de SO .