Propositional Logic · Tautologies

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Formulas that are always true are called tautologies. Thus, the truth table of a tautology consists of all ones. For example, all twelve formulas above are tautologies.

For the curious 🤓
It can be proven that any tautology can be derived from the following eleven so-called axiomatic schemes using a single rule of inference known as modus ponens: \[\frac{A \quad (A \Rightarrow B)}{B}\] (in plain English: if we have established the truth of \(A\) and the truth of the implication \(A \Rightarrow B\), then we have also established the truth of \(B\)). Conversely, only tautologies can be derived from these axioms.
  1. \(A \Rightarrow (B \Rightarrow A)\);
  2. \((A \Rightarrow (B \Rightarrow C)) \Rightarrow ((A \Rightarrow B) \Rightarrow (A \Rightarrow C))\);
  3. \((A \land B) \Rightarrow A\);
  4. \((A \land B) \Rightarrow B\);
  5. \(A \Rightarrow (B \Rightarrow (A \land B))\);
  6. \(A \Rightarrow (A \lor B)\);
  7. \(B \Rightarrow (A \lor B)\);
  8. \((A \Rightarrow C) \Rightarrow ((B \Rightarrow C) \Rightarrow (A \lor B \Rightarrow C))\);
  9. \(\neg A \Rightarrow (A \Rightarrow B)\);
  10. \((A \Rightarrow B) \Rightarrow ((A \Rightarrow \neg B) \Rightarrow \neg A)\);
  11. \(A \lor \neg A\).
These formulas are called axiomatic schemes rather than just axioms because arbitrary formulas can be substituted for \(A, B, C\) in them.