CODEWITHSUNDEEP
mathlogicboolean
taw
taw

Reputation: 18841

Simplification of boolean formulas without negation, just and/or

I'd like to preprocess boolean formulas so that a and (a or b) and c

becomes just a and c

There are never any negations, so it should be a simple problem, but nothing really obvious comes to mind (other than folding and-in-and, or-in-or, duplicates, sorting). Am I missing something totally obvious perhaps?

Upvotes: 2

Views: 1031

Answers (6)

smichr
smichr

Reputation: 19057

Here is a small routine that I learned from Oscar Benjamin while working on SymPy that converts list of arguments from cnf to dnf or vice versa.

def cnfdnf(eqs):
    """Change cnf args set to dnf (or vice versa). For And(x, Or(x,z)) pass
    [{x}, {x,z}]
    """
    if not eqs:
        return [set()]
    elif len(eqs) == 1:
        return [{f} for f in eqs[0]]
    else:
        assert all(type(i) is set for i in eqs)
        f = list(eqs[0])[0]
        eqs_f_zero = [_ for _ in eqs if f not in _]
        dnf_f = cnfdnf(eqs_f_zero)
        if {f} in eqs:
            dnf = [s | {f} for s in dnf_f]
        else:
            f_free_eqs = [_ - {f} for _ in eqs]
            eqs_f_nonzero = list(filter(None, f_free_eqs))
            dnf_no_f = cnfdnf(eqs_f_nonzero)
            dnf = dnf_no_f + [s | {f} for s in dnf_f if s not in dnf_no_f]
        return dnf

If there were sets that were totally independent of others, they could be handled separately by adding each of their cartesian products to each of the dependent arguments, e.g. 'a','ab','bc' are each dependent on each other whereas 'de' and 'f' are not. So to each result of the 3 dependents would become two more results containing 'df' or 'ef'. But if you want to keep the same form, you would run cnfdnf again and that will just return the independent arguments back to how they were at the start. But doing that, as @wnoise points out, is equivalent to just removing supersets. So rather than provide a routine for that I will show how to quickly change between cnf and dnf while watching out for independent args.

def cnf_dnf(eqs):
    """simplify a cnf or dnf form"""
    from itertools import product as cartes
    eqs = [set(i) for i in eqs]
    indep = []
    for i in range(len(eqs)):
        for j in range(len(eqs)):
            if i != j and any(x in eqs[i] for x in eqs[j]):
                # it is dependent
                break
        else:
            indep.append(i)
    if indep:
        new = cnfdnf([eqs[i] for i in range(len(eqs)) if i not in indep])
        rv = []
        for i in cartes(*[eqs[i] for i in indep]):
            rv.extend( [n|set(i) for n in new] )
        return rv
    else:
        return cnfdnf(eqs)

>>> [''.join(i) for i in cnf_dnf(['a','ab','bf','c','de'])]
['cabd', 'cadf', 'cabe', 'cafe']
>>> cnf_dnf(_)  # back to simplified original form
[{'d', 'e'}, {'b', 'f'}, {'a'}, {'c'}]

Notice how all that we have done is to remove the superset 'ab'. So if that's all we want to do (and don't want to change from one form to another) then there is a nice routine to do that here.

Upvotes: 0

Daniel Zinn
Daniel Zinn

Reputation: 316

I had a related question on CSTheory.stackexchange, answered negatively here.

The problem you are describing is coNP-hard. Thus, unless P=NP, you wont find an efficient algorithm to do that.

Converting to CNF or DNF will result in an exponential blow-up of some formulas.

Upvotes: 1

starblue
starblue

Reputation: 56772

From your example it is not really clear what you want in general.

It seems you want to use the absorption laws to simplify the formula as much as possible:

A ∨ (A ∧ B) = A 

A ∧ (A ∨ B) = A

In your example you just need to apply the second absorption law once.

Upvotes: 1

wnoise
wnoise

Reputation: 9922

Consider converting to CNF or DNF.

Simplifying the "bottom level" is easy -- just remove duplicates. Simplifying the next level up is almost as easy -- remove subsets or supersets.

Upvotes: 0

cdhowie
cdhowie

Reputation: 169018

Use a K-map.

Basically, you will create an in-memory graph of possible outcomes of the formula. Parse it, and store it in such a way that given arbitrary input for all of the variables, you can get a result. Then create an N-dimension array (where N is the number of variables) and try each combination, storing the result in the array.

Once this is done, follow the steps in the above article to come up with a simplified expression.

Note that this will work for expressions containing all types of boolean operators, including not.

Upvotes: 0

Christian Mann
Christian Mann

Reputation: 8125

A(A+B)C

AAC + ABC

AC + ABC

A1C + ABC

A(1+B)C

A(1)C

AC

Is that what you were looking for?

Upvotes: 0

Related Questions