verify logical equivalence without truth table

16.8k Views Asked by At

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

There are 2 best solutions below

0
On BEST ANSWER

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

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

Use it as follows:

$$ \begin{align*} (p \land q) \to r &\equiv \neg (p \land q) \lor r &(\text{Implication}) \\ &\equiv (\neg p \lor \neg q) \lor r &(\text{De Morgan}) \\ &\equiv (\neg p \lor \neg q) \lor (r \lor r) &(\text{Idempotence}) \\ &\equiv \neg p \lor (\neg q \lor (r \lor r)) &(\text{Association}) \\ &\equiv \neg p \lor ((\neg q \lor r) \lor r) &(\text{Association}) \\ &\equiv \neg p \lor (r \lor (\neg q \lor r)) &(\text{Commutation}) \\ &\equiv (\neg p \lor r) \lor (\neg q \lor r) &(\text{Association}) \\ &\equiv (p \to r) \lor (q \to r) &(\text{Implication}) \end{align*} $$

3
On

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$