how to prove $A+A'B+A'B'C+A'B'C'D=A+B+C+D$

Question

Prove the above relationship by using the Boolean definition. I tried $A+A'B=A+B$, but end up with $A+B+A'B'(C+D)$, how can I go next?

Answer 1

First, $A+A'B=1-A'B'$.

Then $1-A'B'+A'B'C=1-A'B'(1-C)=1-A'B'C'$.

Same for the last term, and then $1-A'B'C'D'=A+B+C+D$.

Answer 2

I tried $A+A'B=A+B$

Apply this to $\,A+A'B'C=A+B'C\,$ then again to $\,B+B'C=B+C\,$:

$$ \begin{align} A+A'B+A'B'C &= \color{red}{A+B}+A'B'C \\ &= \color{red}{A}+B+\color{red}{B'C} \\ &= A+\color{red}{B+C} \end{align} $$

Repeat the steps to prove the equality with all four terms.

---

[ EDIT ] $\;$ Another way also using OP's attempt, only working from the end backwards.

$$ \begin{align} A+A'B+A'B'C+A'B'C'D &= A+A'B+A'B'(\color{blue}{C+C'D}) \\ &= A+A'B+A'B'(\color{blue}{C+D}) \\ &= A+A'\big(\color{red}{B+B'(C+D)}\big) \\ &= A+A'\big(\color{red}{B+(C+D)}\big) \\ &= \color{green}{A+A'(B+C+D)} \\ &= \color{green}{A+(B+C+D)} \\ &= A+B+C+D \end{align} $$

Answer 3

This is morally the same as the answer given by dxiv, but anyway the idea again is to exclusively use the identity suggested by the OP

$$ \begin{array}{rcl} A + B + C + D & = & A + B + (C+D) \\ & = & A + B + (C + C'D)\\ & = & A + (B+(C+C'D)) \\ & = & A + (B + B'(C+C'D)) \\ & = & A + (B+B'C + B'C'D) \\ & = & A + A'(B+B'C + B'C'D) \\ & = & A + A'B + A'B'C + A'B'C'D \end{array}$$

Specifically this applies the identity "right to left" whereas the other answer applies the identity "left to right", again morally the same. Maybe some people find it easier to read this way.

Answer 4

Let us convert the boolean expression:

$$A+A'B+A'B'C+A'B'C'D=A+B+C+D$$

into its set equivalent:

$$A \cup (A^c \cap B) \cup (A^c \cap B^c\cap C) \cup (A^c \cap B^c \cap C^c \cap D)=A \cup B \cup C \cup D \tag{1}$$

Let us use a "spoken proof" of (1). Consider its LHS:

To the set $A$ one "adds"

• (by taking $(A^c \cap B) $) all remaining elements of $B$ that aren't already in $A$, then

• (by taking $(A^c \cap B^c \cap C) $) all remaining elements of $C$ that aren't already selected either with $A$ or with $B$,

• etc.

No surprize to find at the end the RHS of (1)...