Search code examples
mathlogicboolean

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?

Solution

  • 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.