refactoring boolean equation

Question

Let's say you have a Boolean rule/expression like so

(A OR B) AND (D OR E) AND F

You want to convert it into as many AND only expressions as possible, like so

A AND D AND F
A AND E AND F
B AND D AND F
B AND E AND F

You are just reducing the OR's so it becomes

(A AND D AND F) OR (A AND E AND F) OR (...)

Is there a property in Boolean algebra that would do this?

Answer 1

Take a look at DeMorgan's theorem. The link points to a document relating to electronic gates, but the theory remains the same.

It says that any logical binary expression remains unchanged if we

1. Change all variables to their complements.
2. Change all AND operations to ORs.
3. Change all OR operations to ANDs.
4. Take the complement of the entire expression.

(quoting from the above linked document)

Answer 2

As far as I know boolean algebra can not be build only with AND and OR operations. If you have only this two operation you are not able to receive NOT operation.

You can convert any expression to the full set of boolean operations.

Here is some full sets:

• AND and NOT
• OR and NOT

Answer 3

Assuming you can use the NOT operation, you can rewrite any Boolean expression with only ANDs or only ORs. In your case:

(A OR B) AND (D OR E) AND F

I tend to use engineering shorthand for the above and write:

• AND as a product (. or nothing);
• OR as a sum (+); and
• NOT as a single quote (').

So:

(A+B)(D+E)F

The corollary to arithmetic is actually quite useful for factoring terms.

By De Morgan's Law:

(A+B) => (A'B')'

So you can rewrite your expression as:

(A+B)(D+E)F
(A'B')'(D'E')'F

Answer 4

Your example is exploiting the the distributivity of AND over OR, as shown here.

All you need to do is apply that successively. For example, using x*(y+z) = (x*y)+(x*z) (where * denotes AND and + denotes OR):

0. (A + B) * (D + E) * F
1. Apply to the first 2 brackets results in ((A+B)*D)+((A+B)*E)
2. Apply to content of each bracket results in (A*D+B*D)+(A*E+B*E)
3. So now you have ((A*D+B*D)+(A*E+B*E))*F
4. Applying the law again results in (A*D+B*D)*F+(A*E+B*E)*F
5. Apply one more time results in A*D*F+B*D*F+A*E*F+B*E*F, QED

Answer 5

You may be interested in reading about Karnaugh maps. They are a tool for simplifying boolean expressions, but you could use them to determine all of the individual expressions as well. I'm not sure how you might generalize this into an algorithm you could write a program for though.