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

Question

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

Answer 1

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.

Answer 2

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$.

Answer 3

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'$$