a) Starting with
(¬r ∧ p ∧ q) ∨ (¬r ∧ ¬p ∧ q)
distribute the disjunction (∨) :
((¬r ∧ p ∧ q) ∨ ¬r) ∧ ((¬r ∧ p ∧ q) ∨ ¬p) ∧ ((¬r ∧ p ∧ q) ∨ q)
and once more among the grouped statements:
(¬r ∧ p ∧ q) ∨ ¬r ≡ (¬r ∨ ¬r) ∧ (p ∨ ¬r) ∧ (q ∨ ¬r)
(¬r ∧ p ∧ q) ∨ ¬p ≡ (¬r ∨ ¬p) ∧ (p ∨ ¬p) ∧ (q ∨ ¬p)
(¬r ∧ p ∧ q) ∨ ¬p ≡ (¬r ∨ q) ∧ (p ∨ q) ∧ (q ∨ q)
So, the original statement is equivalent to
[(¬r ∨ ¬r) ∧ (p ∨ ¬r) ∧ (q ∨ ¬r)] ∧ [(¬r ∨ ¬p) ∧ (p ∨ ¬p) ∧ (q ∨ ¬p)] ∧ [(¬r ∨ q) ∧ (p ∨ q) ∧ (q ∨ q)]
which reduces to
[¬r ∧ (p ∨ ¬r) ∧ (q ∨ ¬r)] ∧ [(¬r ∨ ¬p) ∧ (q ∨ ¬p)] ∧ [(¬r ∨ q) ∧ (p ∨ q) ∧ q]
and further to
¬r ∧ (p ∨ ¬r) ∧ (¬r ∨ ¬p) ∧ (q ∨ ¬p) ∧ (p ∨ q) ∧ q
For any statements X and Y, we have the identity
• X ≡ (X ∨ Y) ∧ (X ∨ ¬Y)
so another step of simplification reduces the underlined expressions to
¬r ∧ ¬r ∧ q ∧ q
which leaves us with
¬r ∧ q
###
b) Recall the identity,
p ⇒ q ≡ ¬p ∨ q
Then
(p ⇒ q) ⇒ q ≡ (¬p ∨ q) ⇒ q ≡ ¬(¬p ∨ q) ∨ q
Distributing the negation gives
(p ⇒ q) ⇒ q ≡ (p ∧ ¬q) ∨ q
and distributing the disjunction gives
(p ⇒ q) ⇒ q ≡ (p ∨ q) ∧ (¬q ∨ q)
from which it follows that
(p ⇒ q) ⇒ q ≡ p ∨ q
