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开发者_如何学Python folding and-in-and, or-in-or, duplicates, sorting). Am I missing something totally obvious perhaps?

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.

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.

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?

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.

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.