# verify logical equivalence without truth table

$(p\land q)\rightarrow r$ and $(p\rightarrow r)\lor (q\rightarrow r)$

Have to try prove if they are logically equivalent or not using the laws listed below and also if need to use negation and implication laws. I was going to use associative law and then distributive but I wasn't sure how to get rid of the "implies"

Commutative laws: p ∧ q ≡ q ∧ p
p ∨ q ≡ q ∨ p

De Morgan’s laws: ∼(p ∧ q) ≡ ∼p ∨ ∼q
∼(p ∨ q) ≡ ∼p ∧ ∼q

Idempotent laws: p ∧ p ≡ p
p ∨ p ≡ p

Associative laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

Distributive laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

• Those two statements are not equivalent! Did you maybe mean $(p \rightarrow r) \lor (q \rightarrow r)$? – Bram28 Mar 22 '17 at 1:59
• how would i prove they are not equivalent ? – M.Jones Mar 22 '17 at 2:01
• Im trying to prove if they are equivalent or not – M.Jones Mar 22 '17 at 2:02
• @Phyllotactic Good advice! Always looking to improve the community! Thanks! :) – Bram28 Mar 22 '17 at 2:32
• @Phyllotactic Best wishes to you!! Keep up those logic skills! :) – Bram28 Mar 22 '17 at 2:55

## 3 Answers

With the laws that you provide you will not ba able to prove their equivalence. You need an equivalence involving implications. here is the one that is typically used:

Implication: $p \rightarrow q \equiv \neg p \lor q$

Use it as follows:

$(p \land q) \rightarrow r \equiv$ (implication)

$\neg (p \land q) \lor r \equiv$ (deMorgan)

$(\neg p \lor \neg q) \lor r \equiv$ (Idempotence)

$(\neg p \lor \neg q) \lor (r \lor r) \equiv$ (Association)

$\neg p \lor ( \neg q \lor (r \lor r)) \equiv$ (Association)

$\neg p \lor ((\neg q \lor r) \lor r) \equiv$ (commutation)

$\neg p \lor (r \lor (\neg q \lor r)) \equiv$ (Association)

$(\neg p \lor r) \lor (\neg q \lor r) \equiv$ (implication)

$(p \rightarrow r) \lor (q \rightarrow r)$

The two statements are not equivalent.

Obviously you cannot use equivalence principles to demonstrate non-equivalence, so let's use a counterexample:

Let $p=True$, $q =False$, and $r=False$

then $(p \land q) \rightarrow r = (T\land F) \rightarrow F = F \rightarrow F = T$

But $(p \rightarrow r) \land (q \rightarrow r) = (T \rightarrow F) \land (F \rightarrow F) = F\land T =F$

• Sorry the RHS equation should be (p implies r) or ( q implies r ) – M.Jones Mar 22 '17 at 2:14
• Would that change the answer? – M.Jones Mar 22 '17 at 2:16
• @M.Jones Ah! As I expected! Yes, that changes things, as now they are equivalent! – Bram28 Mar 22 '17 at 2:26

You are missing a equivalence:

1. p → q ≡ ¬p v q


I find it easier to work on the right side:

 (p ∧ q)→r ≡ (p → r) ∨ (q → r)


Taking only the right side:

(p → r) ∨ (q → r)   (Using 1.)

(¬p v r) ∨ (¬q v r) (Commutative laws on the right parentheses)

(¬p v r) ∨ (r v ¬q) (Associative laws)

¬p v ((r ∨ r) v ¬q) (Idempotent laws)

¬p v ((r) v ¬q)     (Commutative laws)

¬p v (¬q v r)       (Associative laws)

((¬p v ¬q) v r)     (De Morgan's laws)

¬(p ∧ q) v r        (Using 1.)

(p ∧ q) → r

• here is a reference for mathjax to help typesetting maths on the site. – Siong Thye Goh Sep 7 '18 at 3:27