Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to simplify the following booleans:

Y = ¬A¬B¬C¬D + ¬A¬B¬CD + ¬A¬BC¬D + ¬A¬BCD + A¬B¬C¬D + A¬BC¬D + ABC¬D

The solution is:

Y = ¬A¬B + ¬B¬D + AC¬D

My solution is:

Y = ¬A¬B (¬C¬D + ¬CD + C¬D + CD) + A¬B¬C¬D + A¬BC¬D + ABC¬D
  = ¬A¬B (¬C (¬D + D) + C (¬D + D)) + A¬B¬C¬D + A¬BC¬D + ABC¬D
  = ¬A¬B (¬C + C) + A¬B¬C¬D + A¬BC¬D + ABC¬D
  = ¬A¬B + A¬D (¬B¬C + ¬BC + BC) 
  = ¬A¬B + A¬D (¬B¬C + (¬BC + ¬BC) + BC) // law of idempotency
  = ¬A¬B + A¬D (¬B (¬C + C) + C (¬B + B))
  = ¬A¬B + A¬D (¬B + C)
  = ¬A¬B + A¬B¬D + AC¬D

As you can see.. my answer varies with the solution by the 2nd term. Any ideas? Thanks.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

All your work is right. The first two terms of your answer simplify to:

Y = ¬A¬B + A¬B¬D
  = ¬B(¬A + A¬D)
  = ¬B(¬AD + ¬A¬D + A¬D) // split the first term
  = ¬B(¬AD + ¬A¬D + ¬A¬D + A¬D) // idempotence
  = ¬B(¬A + ¬D) // combine the first two and last two terms
  = ¬A¬B + ¬B¬D.

I wouldn't have believed it myself at first, but idempotence lets the ¬A "spit out" a ¬A¬D, which is, after all, just a subset.

share|improve this answer
    
+1: I said a similar thing. I will delete my answer. –  Aryabhata Oct 7 '10 at 21:28
    
Thanks. I guess it takes practice to see this kind of thing. –  Sam Oct 7 '10 at 21:39
    
Actually, I don't really have much practice working with Boolean algebra, and I certainly didn't see it immediately. What I did was put in truth values for A, B, and D, and that showed the statements were somehow equivalent. It took a little playing around to see how. Also, it looks like Mathematica has tools for working with Booleans that would give you the right answer, and I'd assume the other symbolic math programs do as well. –  Paul VanKoughnett Oct 8 '10 at 3:18

I agree with you. The last three terms all have A required, so anything that comes out of them (your last two terms) need an A. Are you sure the given solution is right?

share|improve this answer
    
Both answers are correct, as they are actually equivalent. See Paul's answer. –  Aryabhata Oct 7 '10 at 21:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.