Boolean algebra

Question

I'm stuck in proving $(A+B+C+D)(A’+B’+C’+D’) = AD'+A'B+C'D+B'C$ using algebraic manipulation. I tried to solve it. I expanded $(A+B+C+D)(A’+B’+C’+D’)$, and I got:

$$AD’+BD’+CD’+BA’+CA’+DA’+AC’+BC’+DC’+AB’+CB’+DB’$$

But I don't know how to proceed. How can I solve this problem?

Answer 1

This looks like a perfect job for the Consensus theorem:

Consensus

$PQ + Q'R + PR = PQ + Q'R$

Proof:

$$PQ + Q'R +PR = (Adjacency) $$

$$PQ +Q'R +PQR + PQ'R = (Absorption) $$

$$PQ + Q'R$$

So, notice that you have all terms of the expected answer, and so try to get rid of the others using the Consensus Theorem. For example, $BD'$ can be eliminated given that you have $BA'$ and $AD'$

p.s. I you don't have or are unfamiliar with Adjacency and Absorption:

Adjacency

$P = PQ + PQ'$

Absorption

$P + PQ = P$

Answer 2

You have a conjunction of maxterms, but I prefer to reason in terms of disjunction of minterms so I dualize it (first step in the next formula) and then (second step) compute the negation by writing down all the minterms with the exception of those two under the NOT operator:

\begin{equation} \begin{split} &(A+B+&C+D)(A'+B'+C'+D')=(ABCD+A'B'C'D')' = \\ ( 1)&A B C D'&+\\ ( 2)&A B C'D &+\\ ( 3)&A B C'D'&+\\ ( 4)&A B'C D &+\\ ( 5)&A B'C D'&+\\ ( 6)&A B'C'D &+\\ ( 7)&A B'C'D'&+\\ ( 8)&A'B C D &+\\ ( 9)&A'B C D'&+\\ (10)&A'B C'D &+\\ (11)&A'B C'D'&+\\ (12)&A'B'C D &+\\ (13)&A'B'C D'&+\\ (14)&A'B'C'D\\ \end{split} \end{equation}

Now you can see by inspection that: \begin{equation} \begin{split} &(1, 3, 5, 7) \textrm{ reduces to }AD'\textrm{ because it is }AD'(BC+B'C+BC'+B'C')\\ &(8, 9, 10, 11) \textrm{ reduces to } A'B\\ &(2, 6, 10, 14) \textrm{ reduces to } C'D\\ &(4, 5, 12, 13) \textrm{ reduces to } B'C\\ \end{split} \end{equation}

No term has been left out (some has been used more than once, but that is not a problem) and that means that (1 through 14) reduces to $A'B+C'D+B'C$. Of course you can have other equivalent forms of the result depending on the way you choose the cluster of minterms to reduce.

Anyway to solve systematically this kind of problem you'd better study Karnaugh.

Answer 3

Stepping aside from algebraic manipulation, already covered by @Bram28, let's reorder the right-hand side as

$$ A'B + B'C + C'D + D'A \enspace. $$

Note the circular structure that emerges and think of $A$, $B$, $C$, and $D$ as labeling the corners of a square clockwise.

The left-hand side $$ (A+B+C+D)(A'+B'+C'+D') $$ says that at least one corner of the square is labeled $1$ and at least one corner is labeled $0$. The right-hand side says that there must be two successive corners of the square such that the first of them is labeled $0$, while the second is labeled $1$.

A moment's thought convinces us that the two conditions are equivalent. In fact, another equivalent condition is that there are two successive corners such that the first is labeled $1$ and the second is labeled $0$; and indeed,

$$ AB' + BC' + CD' + DA'$$

is another equivalent expression for the left-hand side.

The choice of the order $A,B,C,D$ is very natural to most, but there's nothing sacred about it. If we label the corners of the square with $A$, $B$, $D$, $C$ clockwise, for example, we get

$$ A'B + B'D + D'C + C'A \enspace, $$

which is yet another expression equivalent to the left-hand side. (Proving that algebraically will let you practice your consensus skills.)

There are $(n-1)!$ circular permutations of $n$ objects, which means that we can label our four corners in $6$ distinct ways. To each corresponds an expression that is equivalent to the left-hand side:

$$\begin{gather} A'B + B'C + C'D + D'A \\ A'B + B'D + D'C + C'A \\ A'C + C'B + B'D + D'A \\ A'C + C'D + D'B + B'A \\ A'D + D'B + B'C + C'A \\ A'D + D'C + C'B + B'A \end{gather}$$ These are all the minimum-cost, sum-of-product covers of the left-hand side.