# A formal proof that $(P \Rightarrow Q)$ is equivalent to its contrapositive $(\neg Q \Rightarrow \neg P)$.

I know how to show this via truth tables, but I’m confused over the formal proof.

Wikipedia tells me that:

$(P \Rightarrow Q) \equiv (\neg P \lor Q) \equiv (Q \lor \neg P) \equiv (\neg Q \Rightarrow \neg P)$.

I don’t understand how we get from $(P \Rightarrow Q)$ to $(\neg P \lor Q)$. I also don’t understand how $(Q \lor \neg P)$ implies $(\neg Q \Rightarrow \neg P)$.

• "if it rains then the ground gets wet" ($P\implies Q$). Now can it happen that both following statemens are not true: 1)"it is not raining" and 2)"the ground is getting wet."? No it cannot, so at least one of them is true ($\neg P\vee Q$) – drhab Sep 11 '16 at 18:59
• Before seeking a formal proof, you need to specify which proof calculus you wish to use. There are three well-known ones: Hilbert Calculus, Natural Deduction and Sequent Calculus. – Berrick Caleb Fillmore Sep 11 '16 at 19:05
• Another way to convince yourself is to make truth tables for the two statements. There are two variables, $P$ and $Q$, so there are four possibilities for the truth values (both false, $P$ false and $Q$ true, $P$ true and $Q$ false, and both false). For each of the four possibilites, find the truth value of $P\implies Q$ and the truth value of $\neg Q\implies P$. You’ll find that in each of the four cases the truth value of $P\implies Q$ is the same as the truth value of $\neg Q\implies P$. Thus the two are logically equivalent. – Steve Kass Sep 11 '16 at 20:19

## 1 Answer

$(P \Rightarrow Q) \equiv (\neg P \lor Q) \equiv (Q \lor \neg P) \equiv (\neg \neg Q \lor \neg P) \equiv (\neg Q \Rightarrow \neg P)$.

• Thank you! But could you tell me the logic behind P⇒Q = ¬PvQ and ¬(¬Q)v(¬P) = ¬Q⇒¬P? – Nikitau Sep 11 '16 at 18:57
• Its just manipulation.Which part you did not understand? – Ashar Tafhim Sep 11 '16 at 19:05
• DrHab replied above so I now I understand P⇒Q = ¬PvQ . I'm confused over how ¬(¬Q)v(¬P) = ¬Q⇒¬P. I guess I should provide context by saying this is my first very rigorous proof-based class. – Nikitau Sep 11 '16 at 19:07
• Let X=¬Q and Y=¬P then ¬(¬Q)v(¬P) =¬XvY = X⇒Y.Does this solve the problem? – Ashar Tafhim Sep 11 '16 at 19:09
• OH, now I get it. Thank you so much! – Nikitau Sep 11 '16 at 19:11