$\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$8

3 Answers

$\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$$\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$3$\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$1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password

Post as a guest

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