# Which law of logical equivalence says P ∨(~P ∧ Q) ≡ P ∨Q?

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?

-

## 2 Answers

• 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.
-
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
@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.

-