Question

Prove the following equivalences without using truth tables, and specify at each step of your proof the equivalence law you are using.

(a) ¬ (p ∨ (¬ p ∧ q)) ≡ ¬ p ∧ ¬ q

(b) ( x → y) ∧ ( x → z) ≡ x → ( y ∧ z)

(c) (q → (p → r)) ≡ (p → (q → r))

(d) ( Q → P) ∧ ( ¬Q → P) ≡ P

Answer 1

a.

¬ (p ∨ (¬ p ∧ q)) ≡ ¬ p ∧ ¬ q

{de morgan law}

¬p ∧ ¬(¬ p ∧ q)) ≡ ¬ p ∧ ¬ q

{de morgan law}

¬p ∧ (¬(¬p) ∨ ¬ q)) ≡ ¬ p ∧ ¬ q

{double negation law}

¬p ∧ (p ∨ ¬ q)) ≡ ¬ p ∧ ¬ q

{distributive law}

(¬p ∧ p) ∨ (¬p ∧ ¬ q) ≡ ¬ p ∧ ¬ q

{negation law}

F ∨ (¬p ∧ ¬ q) ≡ ¬ p ∧ ¬ q

{identity law}

(¬p ∧ ¬ q) ≡ ¬ p ∧ ¬ q

hence proved

b.

(¬ x ∨ y) ∧ (¬ x ∨ z) = (¬ x ∨ (y∧z))

{distributive law}

(¬ x ∨ y) ∧ (¬ x ∨ z) = (¬ x ∨ y) ∧ (¬ x ∨ z)

hence proved

c.

(¬q ∨ (¬ p ∨ r)) ≡ (¬ p ∨ (¬q ∨ r))

{associative law}

((¬q ∨ ¬ p) ∨ r) ≡ (¬ p ∨ (¬q ∨ r))

{commutative law}

((¬p ∨ ¬ q) ∨ r) ≡ (¬ p ∨ (¬q ∨ r))

{associative law}

(¬ p ∨ (¬q ∨ r)) ≡ (¬ p ∨ (¬q ∨ r))

hence proved

d.

( ¬Q ∨ P) ∧ ( ¬(¬Q)∨ P) ≡ P

{DOUBLE NEGATION LAW}

( ¬Q ∨ P) ∧ ( Q∨ P) ≡ P

{reverse distributive law : ( r ∨ q) ∧ ( p∨ q) ≡ ( r ∧ p)∨q }

( ¬Q ∧ Q) ∨ P ≡ P

{negation law}

F ∨ P ≡ P

{identity law}

P ≡ P

hence proved