Proof

We want to show that for any two propositions $$x,y$$, the implication $$x\Rightarrow y$$ is equivalent to its contrapositive $$\neg y\Rightarrow \neg x$$.

By definition of implication, for all semantics of $x$ and $y$ have the following truth table:

$$[[x]]_I$$ $$[[y]]_I$$ $$[[x \Rightarrow y]]_I$$
$$1$$ $$1$$ $$1$$
$$0$$ $$1$$ $$1$$
$$1$$ $$0$$ $$0$$
$$0$$ $$0$$ $$1$$

Similarly, for the contrapositive, we get the respective truth table

$$[[\neg y]]_I$$| $$[[\neg x]]_I$$| $$[[\neg y\Rightarrow \neg x]]_I$$ $$0$$| $$0$$| $$1$$ $$0$$| $$1$$| $$1$$ $$1$$| $$0$$| $$0$$ $$1$$| $$1$$| $$1$$

$$x\Rightarrow y$$ is equivalent to $$\neg y\Rightarrow \neg x$$, if the equivalence $(x\Rightarrow y)\Leftrightarrow(\neg y\Rightarrow \neg x)$ is a tautology. Putting the above results together into the truth table of equivalence, we can confirm that:

$$[[x \Rightarrow y]]_I$$| $$[[\neg y \Rightarrow \neg x]]_I$$| $$[[(x\Rightarrow y)\Leftrightarrow(\neg y\Rightarrow \neg x)]]_I$$ $$1$$| $$1$$| $$1$$ $$0$$| $$0$$| $$1$$

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Mendelson Elliott: "Theory and Problems of Boolean Algebra and Switching Circuits", McGraw-Hill Book Company, 1982