How to establish that two Boolean expressions are the same by transforming one into the other?

I'm trying to figure out what rules I need to manipulate

$A + B'D + B'C + A'BD'$

into

$A + B'D + BD' + CD'$

The first I derived from the output of a combinational circuit, the second from entering the output into a K-map. I plugged these two equations into a Boolean expression calculator and they said they were equivalent, but I'm not seeing a way to get there.

I'm hoping I can get some help here, so if I come across a seemingly hopeless case, I'll have another tool for evaluation.

Any help is appreciated! Thanks!

-Jon

• just checking, does $+$ mean "xor"? – Siong Thye Goh Oct 8 '17 at 18:19
• No, in boolean conventions, $+$ means inclusive or. – Jean Marie Oct 8 '17 at 18:20
• What do you mean by a K-map ? A so-called Karnaugh array with $2^n cells$ where $n=4$ here because there are 4 variables ? – Jean Marie Oct 8 '17 at 18:22
• Yes, that it is what I mean by a K-map. – Werewoof Oct 8 '17 at 19:55

Here's an approach. We want to show equivalence of: $A + B'D + B'C + A'BD'$ with $A + B'D + BD' + CD'$ under all values of the variables. First, let's notice that if $A + B'D$ is true, then we clearly have both expressions evaluating to true. Else, $A + B'D$ is false, meaning both $A$ and $B'D$ are false. In this case, we need to just prove the equivalence of: $B'C + A'BD' \equiv BD' + CD'$. But since $A$ is false, we can further reduce this to an equivalence of: $B'C + BD' \equiv BD' + CD'$.

Now, we apply the first trick again and if $BD'$ is true, then both expressions are true and so equivalent. So we're left to prove the case where $BD'$ is false, so the equivalence further reduces to: $B'C \equiv CD'$. But since from before $B'D$ is false, and from more recently $BD'$ is false, then $B = D$, so we're left with: $D'C \equiv CD'$, which is clear from symmetry.

• Not the prettiest approach, "if this, then this, else this", but at least I don't go through all 16 combinations of valules for the four variables... it's a bit more deductive than that. – Colm Bhandal Oct 8 '17 at 18:29
• Thanks for this! I'm still not 100% confident about this yet, but I think if I review it enough and try to conceptualize it in my mind, it'll click. Thanks again! – Werewoof Oct 8 '17 at 19:53
• @Werewoof the thing about Boolean equations is- there is always an ugly but guaranteed way to solve them: try all possible true/false values for each variable. If, for all possible true false values, the equations give the same value, then they're equivalent. However, there are shortcuts you can take, such as my answer, e.g. by noting that certain subexpressions must be either true or false- reducing the total number of cases. This may or may not help, but imagine a decision tree where you don't always have to calculate all the way to the leaves. – Colm Bhandal Oct 9 '17 at 10:32

Case $1$: $A+B'D$ is true, then we are done.

Case $2$: $A+B'D$ is False. Hence $A$ is false and $B'D$ is false. Using the property that $A$ is false, it suffices to check under this condition whether $B'C+BD'$ is equivalent to $BD'+CD'$. If $BD'$ is true, again, we are done. Hence we we just have to work under the condition that $B'D$ is false and $BD'$ is false and verify if $B'C$ is equivalent to $CD'$. If $C$ is false, then we are done. Hence let's assume $C$ is true.and we just have to verify if $B'=D'$, i.e. $B=D$ under the condition that $B'D=BD'$.

$$B'D=BD'$$

If $B$ is true, we deduce that $D'$ is False, and hence $D$ must be true.

If $B$ is false, we deduce the condition that $D$ is false.

Hence $B'D=BD'$ implies that $B=D$.

• Thanks for the answer! Very simple wording, which helps a lot. – Werewoof Oct 8 '17 at 19:54

The following two principles will do:

Reduction

$P + P'Q=P + Q$

Consensus

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

With these:

$$A + B'D + B'C + A'BD' = \text{ (Reduction)}$$

$$A + B'D + B'C + BD' = \text{ (Consensus with }B'C+CD'=B'C + BD' + CD'$$

$$A + B'D + B'C + BD' + CD'= \text{ (Consensus with } B'D + CD' + B'C=B'D + CD')$$

$$A + B'D + BD' + CD'$$