(related to Lemma: Every Contraposition to a Proposition is a Tautology to this Proposition)
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\)
