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