# Prove that $(p \to q) \to (\neg q \to \neg p)$ is a tautology using the law of logical equivalence

I'm new to discrete maths and I have been trying to solve this:

Decide whether $$(p \to q) \to (\neg q \to \neg p)$$ is a tautology or not by using the law of logical equivalence

I have constructed the truth table and concluded that it is indeed a tautology. However, I am having difficulty proving it using the law of logical equivalence. I can only realize that I can use $$(p \to q ) \equiv (\neg p \lor q)$$ but after that I have no idea how to continue. Any help would be appreciated.

• ( ¬q → ¬p ) ≡ ( ¬¬ q ∨ ¬p ) ≡ ( q ∨ ¬p ) ≡ ( ¬p ∨ q ) – Mathematician 42 Jul 19 '16 at 14:29
• By Double Negation and Commutativity, $¬ p ∨ q$ is equivalent to $¬¬ q ∨ ¬ p$. – Mauro ALLEGRANZA Jul 19 '16 at 14:30
• Sorry. I really do not know what are you saying about @MauroALLEGRANZA – Lim Kha Shing Jul 19 '16 at 15:20
• $\neg q\implies \neg p$ is just a contrapositive of a conditional. – Invisible Jan 7 '20 at 16:26

The following line of reasoning may help: \begin{align} (p\to q)\to(\neg q\to\neg p)&\equiv\neg(\neg p\lor q)\lor(q\lor\neg p)\tag{material implication}\\[1em] &\equiv\neg(\neg p\lor q)\lor(\neg p\lor q)\tag{commutativity}\\[1em] &\equiv \neg M\lor M\tag{$M:\neg p\lor q$}\\[1em] &\equiv \mathbf{T}.\tag{negation law} \end{align} Is the above clear? It makes minimal use of other logical equivalences.

• still a little bit not clear on the third statement ¬M∨M what do it mean by M : ¬ p ∨ q ? – Lim Kha Shing Jul 20 '16 at 12:19
• It's just to help you see that you have a statement of the form $\neg M\lor M$ which clearly must be true. The letter $M$ can be stand for any compound statement you want. – Daniel W. Farlow Jul 20 '16 at 14:14
• @AhShing The justification, $(M: \neg p\vee q)$, reads "we defined a new symbol, $M$, to be equivalent to $\neg p\vee q$, so we could use substitution." – Graham Kemp Jul 21 '16 at 0:01
• Sorry for late reply. Now i finally get it. Thank you for your help :D @GrahamKemp – Lim Kha Shing Jul 22 '16 at 14:23

It depends on the logical inferences you have available. One way is to note that $$(p\rightarrow q)\equiv(\neg q\rightarrow\neg p)\qquad\text{(contrapositive)}$$ so your original expression is equivalent to $$(p\rightarrow q)\rightarrow(p\rightarrow q)$$ and if we let $r=(p\rightarrow q)$ we have $r\rightarrow r$, which we either know is true or if you don't have that equivalence you can use material implication to get $(r\rightarrow r)\equiv (\neg r\lor r)$, which is true by inverse for OR.

• wow now i finally understand thanks for the explanation :D – Lim Kha Shing Jul 20 '16 at 12:14

They're indeed equivalent (implication goes both ways). In fact

$$p\Rightarrow q \equiv \neg(p \land \neg q)$$ and

$$\neg q \Rightarrow \neg p \equiv \neg (\neg q \land \neg \neg p)\equiv \neg (p \land \neg q)$$

So the two are equal, and therefore one implies the other.

• okay so they are implies each other. But what are the exactly the steps or laws I can use to prove it as tautology ? – Lim Kha Shing Jul 19 '16 at 15:20
• If this does not convince you, you can simply write down the truth table, for all possible values for $p$ and $q$ and see what's the output. It will always be T. In fact, there is no way that the left hand side is T and the right hand side is F, because we showed that they are the same statement. – bartgol Jul 19 '16 at 15:22