Convert Boolean AND-OR to OR-AND

Question

How can I convert a'b'c + a'bc + ab'c + abc' to an equivalent OR-AND. I cannot seem to find a solution that mirrors the truth table. I've tried the Distributive Law as well as using De Morgans Law without success.

Answer 1

You have an expression in Disjunctive Normal Form and seek to express it in Conjunctive Normal Form.

You can convert the DNF to a CNF by double negating the expression, applying deMorgan's Law to the inner negation, using distribution, and finally applying deMorgan's Law on the outer negation.

The trick is to ignore contradiction terms during the distribution while ensuring you catch all non-contradictions.   Is this causing the difficulties?   Just take it slowly and be thorough.

Answer 2

You can use rules of boolean algebra; they should always preserve the truth table. Specifically, a helpful rule here is this distribution law:

$$x + pqr \equiv (x+p)(x+q)(x+r)$$

There may be other elegant approaches, but this one is pretty systematic. You can make it easier by simplifying first:

1. $a^\prime b^\prime c + a^\prime b c + a b^\prime c + abc^\prime$.

2. Factor out $c$:

   $c\left(a^\prime b^\prime + a^\prime b + ab^\prime \right) + abc^\prime$.

3. Because $a^\prime b^\prime + a^\prime b + ab^\prime$ contains all combinations of $a$ and $b$ except for $ab$, it is equivalent to $(ab)^\prime$

   $c(ab)^\prime + (ab)c^\prime$

4. DeMorgan's law:

   $(a^\prime + b^\prime)c + abc^\prime$

5. Distribute between these two terms:

   $\left[(a^\prime + b^\prime)c + a \right]\left[(a^\prime + b^\prime)c+ b \right]\left[(a^\prime + b^\prime)c+ c^\prime\right]$

6. Distribute each term in square brackets separately.

   $\left[(a^\prime + b^\prime+a)(c+a) \right]\left[(a^\prime + b^\prime + b)(c+b)\right]\left[(a^\prime + b^\prime+c^\prime)(c+ c^\prime)\right]$

7. Simplify using the rule $x + x^\prime = \top$ and the rule $x + \top = \top$:

   $\left[(c+a) \right]\left[(c+b)\right]\left[(a^\prime + b^\prime+c^\prime)\right]$

8. Remove irrelevant groupings, leaving the final result: $$(c+a)(c+b)(a^\prime + b^\prime+c^\prime)$$