2
$\begingroup$

(!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)

= (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(1)

= (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)(C + !C)

= (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABDC) + (!ABD !C)

= (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABDC) + (!ABD !C)

= (!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABCD) + (!AB !CD)

= (!A B !C) + (!AB !CD) + (B !C !D) + (!ACD) + (!ACDB) + (!BCD)

= [(!A B !C)(1 + D)] + (B !C !D) + [(!ACD)(1 + B)] + (!BCD)

= (!A B !C) + (B !C !D) + (!ACD) + (!BCD)

At this point I don't know how to continue the problem. I verified it using a calculator and seems there is still some simplification to do.

$\endgroup$
2
$\begingroup$

Here are two handy equivalences:

Adjacency

$PQ + P!Q=P$

Absorption

$P + PQ=P$

With that:

$$(!A B !C) + (B !C !D) + (!ACD) + (!BCD) + (!ABD)\overset{Adjacency \ x \ 2}=$$

$$(!A B !C D) + (!A B !C !D) + (B !C !D) + (!ABCD) + (!A!BCD)+ (!BCD) + (!ABD)\overset{Absorption \ x \ 4}=$$

$$(B !C !D) + (!BCD) + (!ABD)$$

I am sure that went a little quick though, so here is an explanation:

In step 1, I applied Adjacency to:

$(!A B !C)$ ... becoming $(!A B !C D) + (!A B !C !D)$

and to $(!ACD)$ ... becoming $(!ABCD) + (!A!BCD)$

Then, in step 2:

$(!A B !C D)$ got absorbed by $(!ABD)$

$(!A B !C !D)$ got absorbed by $(B !C !D)$

$(!ABCD)$ got absorbed by $(!ABD)$

$(!A!BCD)$ got absorbed by $(!BCD)$

More equivalences to put in your toolbox!

Now, notice that you effectively did Adjacency as well in your first few steps, expanding $(!ABD)$ to $(!ABCD)+(!AB!CD)$ ... and yet that one isn't as useful as the ones I did. So, I know you are going to ask: how did I know which terms to expand using Adjacency? Well, I created a little K-map. Look it up!

$\endgroup$
  • $\begingroup$ Oh I finally understood what Adjacency is. Jesus Christ great work. Thank you for taking all that time for this as well as the K-map. On a side note, do you know of any good Boolean algebra calculators. I've tried plugging the problem in but it seems it gives me a different answer compared to yours. $\endgroup$ – JohnJohnyPapaJohn Feb 19 at 2:44
  • $\begingroup$ @JohnJohnyPapaJohn Oh? What answer did your calculator give? Oh, and yeah, this form of Adjacency is a lot more intuitive than its dual I used in the other question (the $(P + Q)(P + !Q)=P$ one). Indeed, the $PQ+P!Q$ form is what you use in K-Maps $\endgroup$ – Bram28 Feb 19 at 3:06
  • $\begingroup$ @JohnJohnyPapaJohn wolframalpha.com/input/… It shows the same DNF I arrived at .. but shows that the CNF is even more efficient yet. Looking back at the K-Map, I see that now as well. I missed that :( $\endgroup$ – Bram28 Feb 19 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.