Lemma: Every Contraposition to a Proposition is a Tautology to this Proposition

For two propositions \(x,y\), the implication \(x\Rightarrow y\) is logically equivalent to its contrapositive \(\neg y\Rightarrow \neg x\), formally, the compound proposition. \[(x\Rightarrow y)\Leftrightarrow(\neg y\Rightarrow \neg x)\]

is a tautology (always valid).

Examples:

\(\text{"if Socrates is a philosopher, then Socrates is a person"}\) is logically equivalent to \(\text{"if Socrates is not a person, then Socrates is not a philosopher"}\).

\((a > 2)\Rightarrow (2 < a)\) is logically equivalent to \((2 \ge a) \Rightarrow (a \le 2)\).

Proofs: 1

Definitions: 1
Proofs: 2


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

Github:
bookofproofs


References

Bibliography

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