0
$\begingroup$

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

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)$

$\endgroup$
1
$\begingroup$

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$

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

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
$\endgroup$
  • $\begingroup$ here is a reference for mathjax to help typesetting maths on the site. $\endgroup$ – Siong Thye Goh Sep 7 '18 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.