Answer to Question #316040 in Discrete Mathematics for Pravin

Question

1.  Prove or disprove that the two propositions in each pair are equivalent.

a)   (p $\to$ (q $\to$ r)) , ((p $\to$ q ) $\to$ ( p $\to$ r ))

Answer 1

Remind that logical implication $\rightarrow$ can be rewritten via a logical disjunction. Namely, $a\rightarrow b=\bar{a}\lor b$. Thus, the first statement can be rewritten as: $p\rightarrow(q\rightarrow r)=\bar{p}\lor{\bar{q}}\lor r$. The second statement can be rewritten as: $(p\rightarrow q)\rightarrow(p\rightarrow r)=\overline{(\bar{p}\lor q)}\lor(\bar{p}\lor r)$. Remind that a negation of a disjunction can be rewritten via conjunction. Namely, $\overline{(\bar{p}\lor q)}=p\land {\bar{q}}$. It can checked via the truth table. Thus, we get: $(p\rightarrow q)\rightarrow(p\rightarrow r)=(p\land {\bar{q}})\lor(\bar{p}\lor r)$. To complete the proof, it is enough to check that $(p\land {\bar{q}})\lor{\bar{p}}=\bar{p}\lor{\bar{q}}$ . It holds, since the statement $p\lor{\bar{p}}$ is tautology, From the latter we get: $(p\land {\bar{q}})\lor({\bar{p}}\lor r)=\bar{p}\lor({\bar{q}}\lor r)$. Thus, both statements are equivalent.