[Math] Which law of logical equivalence says P ∨(~P ∧ Q) ≡ P ∨Q

logic

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?

Best Answer

  • 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.
Related Question