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

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