CODEWITHSUNDEEP
pythonboolean-expression
u003f
u003f

Reputation: 483

Disjunctive Normal Form in Python

Using python, what is the best way to convert a string of ANDs and ORs into disjunctive normal form (also known as "sum of products")?

b AND (c OR (a AND d))

becomes

(b AND c) OR (b AND a AND d)

I would like to also sort these, lexicographically

(a AND b AND d) OR (b AND c)

Upvotes: 0

Views: 4764

Answers (2)

sdementen
sdementen

Reputation: 462

Here is a sample answering partially the question (i.e. not the parsing/sorting)

REPR_FORM_AS_TEXT = False


class Or(frozenset):
    def __repr__(self):
        if REPR_FORM_AS_TEXT:
            return " OR ".join(repr(e) for e in self)
        else:
            return super().__repr__()


class And(frozenset):
    def __repr__(self):
        if REPR_FORM_AS_TEXT:
            if len(self) > 1:
                return "(" + " AND ".join(repr(e) for e in self) + ")"
            else:
                return "".join(repr(e) for e in self)
        else:
            return super().__repr__()


def dnf(expr, ):
    """Normalize a boolean expression to its DNF.

    Expr can be an element, it this case it returns Or({And({element})}).
    Expr can be an Or(...) / And(...) expressions, in which cases it returns also a disjunctive normalised form (removing identical elements)

    assert dnf(And((Or((4, 5, 1)), Or((1, 2)), 7, 7))) == Or(
        (
            And((2, 5, 7)),
            And((1, 5, 7)),
            And((1, 2, 7)),
            And((1, 7)),
            And((2, 4, 7)),
            And((1, 4, 7)),
        )
    )
    """

    if not isinstance(expr, (Or, And)):
        result = Or((And((expr,)),))
    elif isinstance(expr, Or):
        result = Or(se for e in expr for se in dnf(e))
    elif isinstance(expr, And):
        total = []
        for c in itertools.product(*[dnf(e) for e in expr]):
            total.append(And(se for e in c for se in e))
        result = Or(total)
    return result

Upvotes: 3

Don
Don

Reputation: 17606

Maybe this library can help: pyeda

here is a method to turn an expression into DNF: to_dnf()

Of course you must turn your string into a valid pyeda expression...

Upvotes: 3

Related Questions