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

Question

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.

Answer 1

The following line of reasoning may help:

$\qquad\begin{align} (p\to q)\to(\neg q\to\neg p)&\equiv\neg(\neg p\lor q)\lor(q\lor\neg p)&&\text{material implication}\\[1em] &\equiv\neg(\neg p\lor q)\lor(\neg p\lor q)&&\text{commutativity}\\[1em] &\equiv \neg M\lor M&&{M:\neg p\lor q}\\[1em] &\equiv \mathbf{T}&&\text{negation law} \end{align}$

Is the above clear? It makes minimal use of other logical equivalences.

Answer 2

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.

Answer 3

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.