List of tautologies
Let $P$, $Q$ and $R$ be formulae, and let $\top$ and $\bot$ be the values for "true" and "false". The following formulae1 are then tautologies2:
| Tautology | Explanation |
|---|---|
| $P \to \top$ | - |
| $\bot \to P$ | - |
| $P \to P$ | Reflexive law of material implication |
| $P \iff P$ | - |
| $(\neg(\neg P)) \to P$ | Law of double negation |
| $P \to (\neg(\neg P ))$ | Converse law of double negation |
| $(\neg(\neg(\neg P))) \to (\neg P)$ | Law of triple negation |
| $(\neg P) \to (\neg(\neg(\neg P)))$ | Converse law of triple negation |
| $\neg(P \land \neg P)$ | Law of contradiction |
| $P \iff (P \lor P)$ | Idempotence of $\lor$ |
| $P \iff (P \land P)$ | Idempotence of $\land$ |
| $P \iff (P \lor \bot)$ | Identity, as $P \lor \bot$ is equivalent to $P$ |
| $P \iff (P \land \top)$ | Identity, as $P \land \top$ is equivalent to $P$ |
| $P \iff (P \lor (P \land Q))$ | First law of absorption |
| $P \iff (P \land (P \lor Q))$ | Second law of absorption |
| $(P \to Q) \to (\neg Q \to \neg P)$ | Law of contraposition |
| $(\neg Q \to \neg P) \to (P \to Q)$ | Converse law of contraposition |
-
Source: Adapted from Foundations of logic and mathematics: Applications to computer science and cryptography by Yves Nievergelt. The table shown here is incomplete - the actual table in the book contains a hundred tautologies, most of which were not included for reasons of specificity and time. Great book incidentally. ↩
-
It's not that a tautology is "always true" so much as it is that every line in the truth table evaluates to true. It's the process of valuation that confers a "truth value" to the formula; by themselves, the formulae have no claim to truth or falsehood. Loveys emphasises the distinction between the two very strongly, so make sure you understand it, and for the love of god don't ever refer to a tautology as something that is "always true". See the notes from the first lecture for more. ↩