Simplify Boolean Expression Condensing

Question

I need help proving the following:

Show that $(\neg{a}\wedge\neg{b}\wedge\neg{c}\wedge{d})\vee(\neg{a}\wedge\neg{b}\wedge{c})\vee(\neg{a}\wedge{b}\wedge{c}\wedge\neg{d})\vee(a\wedge\neg{b}\wedge{c}\wedge\neg{d})\vee(a\wedge{b}\wedge\neg{c}\wedge{d})\vee(a\wedge{b}\wedge{c})\equiv(a\wedge{b}\wedge{c})\vee(\neg{a}\wedge\neg{b}\wedge{c})\vee(c\wedge\neg{d})$

using the laws of Boolean Algebra.

Thanks so much!

What have you tried so far? Where did you get stuck? You'll find that questions that demonstrate some effort to solve a problem will attract more helpful comments and answers. — Brian61354270, Jan 26 '20 at 03:35

score 0 · Answer 1 · answered Jan 26 '20 at 12:49

Let me use the additive/multiplicative notation (for $\vee$/$\wedge$, respectively), uppercase letters and $A'$ for $\neg A$. This becomes for readable when we have such long expressions.

Your result is wrong, for if $A=B=C=0$ and $D=1$, then $$A'B'C'D + A'B'C + A'BCD'+ AB'CD' + ABC'D + ABC = 1,$$ while $$ABC + A'B'C + CD' = 0.$$

The right result is $$A'B'C'D + A'B'C + A'BCD'+ AB'CD' + ABC'D + ABC = ABD + A'B'D + CD'.$$

Use the following (easy to show): \begin{equation}\label{eq:1} X+X'Y = X+Y \tag{1} \end{equation} and \begin{equation}\label{eq:2} (XY'+X'Y)'= X'Y' + XY. \tag{2} \end{equation} Now, let us start by making some associations from your initial expression by using distributivity and obtain \begin{align} A'B'C'D &+ A'B'C + A'BCD'+ AB'CD' + ABC'D + ABC\\ &=A'B'(C'D+C)+AB(C'D+C)+(A'B+AB')CD'\\ &=(A'B'+AB)(C'D+C)+(A'B+AB')CD' \end{align} By \eqref{eq:1}, this becomes $$(A'B'+AB)(C+D)+(A'B+AB')CD',$$ and taking $X=A'B+AB'$, we get, by \eqref{eq:2} $$X'(C+D)+XCD'.$$ Now, \begin{align} X'(C+D)+XCD' &= X'C+X'D+XCD'\\ &= (X'+XD')C + X'D\\ &= (X'+D')C+X'D\tag{by \eqref{eq:1}}\\ &= X'C+X'D+CD'\\ &= X'C(D+D')+X'D+CD'\\ &= (X'CD + X'D) + (X'CD' + CD')\\ &= X'D + CD'. \tag{by absorption} \end{align} By \eqref{eq:2}, $X' = AB+A'B'$, yielding $$ABD+A'B'D+CD'$$ as the result.

score 0 · Answer 2 · answered Jan 27 '20 at 04:12

Use:

Adjacency

$PQ +PQ'=P$

With that:

$$A'B'C'D + A'B'C + A'BCD'+ AB'CD' + ABC'D + ABC \overset{Adjacency}{= }$$

$$A'B'C'D + A'B'CD + A'B'CD'+A'BCD'+ AB'CD' + ABC'D + ABCD +ABCD' \overset{\text{Commutation}}{=}$$

$$A'B'C'D+A'B'CD+A'B'CD'+AB'CD' +ABCD'+A'BCD'+ABCD+ABC'D \overset{\text{Adjacency}}{=}$$

$$A'B'D+B'CD'+BCD'+ABD\overset{\text{Adjacency}}{=}$$

$$A'B'D+CD'+ABD$$

Simplify Boolean Expression Condensing

2 Answers2