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 going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in this table.

1. Commutative laws:      p∧q ≡ q∧p                p∨q ≡ q∨p
2. Associative laws:      (p∧q)∧r ≡ p∧(q∧r)        (p∨q)∨r ≡ p∨(q∨r)
3. Distributive laws:     p∧(q∨r) ≡ (p∧q)∨(p∧r)    p∨(q∧r) ≡ (p∨q)∧(p∨r)
4. Identity laws:         p∧t ≡ p                  p∨c ≡ p
5. Negation laws:         p∨∼p ≡ t                 p∧∼p ≡ c
6. Double negative law:   ∼(∼p) ≡ p
7. Idempotent laws:       p∧p ≡ p                  p∨p ≡ p
8. Universal bound laws:  p∨t≡t                    p∧c≡c
9. De Morgan’s laws:      ∼(p∧q) ≡ ∼p∨∼q           ∼(p∨q) ≡ ∼p∧∼q
10. Absorption laws:      p∨(p∧q) ≡ p              p∧(p∨q) ≡ p
11. Negations of t and c: ∼t ≡ c                   ∼c ≡ t

The first circuit is equivalent to this: (P∧Q) ∨ (P∧~Q) ∨ (~P∧~Q), which I managed to simplify to this: P ∨ (~P∧~Q).

The other circuit is simply this: P ∨ ~Q

I can see their equivalence clearly with a truth table. But the book is asking me to show it using the equivalence laws in the above table, and I can't see how any of them apply here. So, do any of those laws apply here in a way I'm not understanding? Or is there some other known law that does apply here?

share|improve this question

2 Answers 2

up vote 2 down vote accepted
  • Distributive law: P ∨ (~P ∧ ~Q) ≡ (P ∨ ~P) ∧ (P ∨ ~Q)
  • Negation law: (P ∨ ~P) ∧ (P ∨ ~Q) ≡ t ∧ (P ∨ ~Q)
  • Identity law: t ∧ (P ∨ ~Q) ≡ P ∨ ~Q.
share|improve this answer
    
Thank you. I never think to go that way with the Distributive law, because I'm always trying to reduce the number of symbols. –  Benjamin Lindley Apr 19 '12 at 21:15
2  
@Benjamin: In the long-term, reducing symbols is a reasonable goal in a derivation. However, in the short-term, the key is to see which laws are even applicable first, and then test where these lead off to. Distributivity was one of the most obviously applicable laws from where you were, and then the negation law was after that, and then the identity law. The other two steps fell into place after I tested the first. :) –  anon Apr 19 '12 at 21:18

Use idempotence backwards to write $P = P \vee (P\wedge \tilde Q)$ and then combine $(P\wedge \tilde Q)$ and $(\tilde P \wedge \tilde Q)$ using distributivity and universal bound.

share|improve this answer

Your Answer

 
discard

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

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