Math 2.0

Areas Mathematical logic Topic

The propositional calculus

Summary

This topic is a part of mathematical logic. It covers classical propositional logic as a formal system, with its formal language, valuations, normal forms, functional completeness, deductive systems, and the theorems of soundness, completeness and compactness. It also treats the proof systems for automated reasoning on clauses, resolution and the Tseitin transformation, and the interpolation theorem. The connectives, truth tables and the elementary laws of logic at school level are in the topic propositions, connectives and quantifiers.

Remarks

Reading order

  1. Propositional calculus: the formal system as a whole, its language, semantics and proof theory.
  2. Propositional formula: the formulas, defined by induction from variables and connectives.
  3. Unique readability theorem: each formula is built in exactly one way.
  4. Truth valuation: the unique extension of a truth assignment to all formulas.
  5. Logical consequence: the relation Γ⊨φ\Gamma \models \varphi.
  6. Satisfiability: sets of formulas that some assignment makes true.
  7. Equisatisfiability: formulas that are satisfiable together or not at all.
  8. Conjunctive normal form: conjunctions of clauses, and the conversion to them.
  9. Disjunctive normal form: disjunctions of conjunctions of literals, read off a truth table.
  10. Clause: finite sets of literals, read as disjunctions.
  11. Horn clause: clauses with at most one positive literal, and their fast satisfiability test.
  12. Functional completeness: sets of connectives that express every truth function.
  13. Post's functional completeness theorem: the five classes that decide functional completeness.
  14. Hilbert system: the axiom system L with modus ponens.
  15. Deduction theorem: from Γ,φ⊢ψ\Gamma, \varphi \vdash \psi to Γ⊢φ→ψ\Gamma \vdash \varphi \to \psi.
  16. Peirce's law: a classical tautology in implication alone.
  17. Implicational propositional calculus: the fragment with implication as the only connective.
  18. Single axioms for propositional logic: one axiom schema with one rule.
  19. Independence of axioms: the method of many-valued truth tables.
  20. Soundness theorem for propositional logic: every derivable formula is a consequence.
  21. Completeness theorem for propositional logic: every consequence is derivable.
  22. Compactness theorem for propositional logic: satisfiability is decided by finite subsets.
  23. Applications of propositional compactness: colourings, orders and other infinite combinatorics.
  24. Resolution: a proof system with one rule on clauses.
  25. Tseitin transformation: a linear-size equisatisfiable CNF.
  26. Craig interpolation for propositional logic: an implication explained in the shared variables.

Prerequisites

Everything in this topic

The members of this topic and each page that they need, 253 pages in all.

  1. Alphabet concept
  2. Arity concept
  3. Boolean function concept
  4. Cartesian product concept
  5. Clone concept
  6. Clopen set concept
  7. Countable set concept
  8. Countermodel concept
  9. Definition by recursion concept
  10. Effectively decidable set concept
  11. Element definition
  12. Equality (mathematics) concept
  13. Finitary operation concept
  14. Finite set concept
  15. Formal language concept
  16. Function concept
  17. Graph concept
  18. Graph colouring concept
  19. Heyting algebra concept
  20. Induction on well-formed formulas concept
  21. Mathematical statement definition
  22. Maximal and minimal elements concept
  23. Monotone function concept
  24. Natural numbers object
  25. Partial order concept
  26. Peano axioms concept
  27. Product topology concept
  28. Proof of Zorn's lemma proof
  29. Proposition concept
  30. Propositional letter concept
  31. Real numbers object
  32. Rooted tree concept
  33. Set concept
  34. String concept
  35. Total order concept
  36. Tuple concept
  37. Signature concept
  38. Functional completeness definition member
  39. Set definition
  40. Logical connective definition
  41. Connectives in mathematical language concept
  42. Successor function definition
  43. Conjunction definition
  44. Disjunction definition
  45. Material implication definition
  46. Principle of bivalence concept
  47. Linear extension definition
  48. Predicate concept
  49. Predicate definition
  50. Empty set object
  51. Family of sets definition
  52. Ordered pair definition
  53. Intersection definition
  54. Union definition
  55. Addition of natural numbers definition
  56. Conditional statements concept
  57. Structure concept
  58. Biconditional definition
  59. The successor function is injective statement
  60. Zero is not a successor statement
  61. Term concept
  62. Negation concept
  63. Negation definition
  64. Cartesian product definition
  65. Atomic formula concept
  66. Truth table concept
  67. Order on the natural numbers definition
  68. Material implication concept
  69. Conjunction concept
  70. Disjunction concept
  71. Tautology concept
  72. Biconditional concept
  73. Universal quantifier concept
  74. Universal quantifier definition
  75. Existential quantifier definition
  76. Intersection of a family of sets definition
  77. Union of a family of sets definition
  78. Axiom of extensionality statement
  79. Subset definition
  80. Uniqueness quantifier definition
  81. Logical equivalence concept
  82. Logical connective concept
  83. Existential quantifier concept
  84. Binary relation definition
  85. Topological space definition
  86. Universal set definition
  87. Well-formed formula concept
  88. A switching circuit read as a propositional formula example member
  89. Converse and inverse of an implication concept
  90. Propositional calculus concept member
  91. Proof of the double negation law by a truth table proof
  92. Propositional formula definition member
  93. Propositional formula concept member
  94. Antisymmetric relation definition
  95. Reflexive relation definition
  96. Transitive relation definition
  97. Basis of a topology definition
  98. Function definition
  99. Subspace topology definition
  100. Tautology definition
  101. Complement definition
  102. Truth valuation definition member
  103. First-order logic concept
  104. Double negation law statement
  105. Conjunctive normal form definition member
  106. Disjunctive normal form definition member
  107. Reading a formula in Polish notation example member
  108. Formal system concept
  109. Proof of unique readability by counting brackets proof member
  110. Strings that are not propositional formulas example member
  111. Formation sequence and parse tree of a propositional formula example member
  112. Product topology definition
  113. Subbasis definition
  114. Preorder definition
  115. Choice function definition
  116. Disjunctive normal form of p ↔ q example member
  117. The Boolean function of exclusive or defined by a formula example member
  118. Full disjunctive normal form of the majority of three variables example member
  119. Conjunctive normal form of exclusive or from the truth table example member
  120. A map on formulas that extends an assignment but is not a truth valuation example member
  121. Computing the truth value of a formula example member
  122. Logical equivalence definition
  123. Metric space definition
  124. The formula p ∧ (q ∨ r) is not in disjunctive normal form example member
  125. Unique readability theorem statement member
  126. Product topology on an arbitrary product definition
  127. Partial order definition
  128. Axiom of choice statement
  129. Truth valuation concept member
  130. Open ball definition
  131. Proof of De Morgan's laws (logic) by truth tables proof
  132. Maximal element definition
  133. Total order definition
  134. Upper bound definition
  135. Modus ponens as a logical consequence example member
  136. A conjunction of literals is not a clause example member
  137. Affirming the consequent is not a logical consequence example member
  138. Disjunctive normal form concept member
  139. Metric topology definition
  140. Conjunctive normal form concept member
  141. Logical consequence concept member
  142. De Morgan's laws (logic) statement
  143. An unsatisfiable set from modus ponens example member
  144. Logical consequence definition member
  145. Satisfiability definition member
  146. A clause with three literals example member
  147. A satisfiable set of three clauses example member
  148. Disjunctive syllogism as a logical consequence example member
  149. Clause concept member
  150. Chain definition
  151. Open set definition
  152. Proof of De Morgan's laws for sets proof
  153. Functional completeness concept member
  154. Negation and implication form a functionally complete set example member
  155. An argument checked in the propositional calculus example member
  156. Proof of Craig interpolation for propositional logic proof member
  157. Satisfiability concept member
  158. Rule of inference concept
  159. Conjunctive normal form of (p → q) → r example member
  160. The Socrates syllogism is not valid in the propositional calculus example member
  161. A disjunction of two variables is not a Horn clause example member
  162. The formula ¬(p ∨ q) ∧ r is not in conjunctive normal form example member
  163. Horn clause definition member
  164. Open cover definition
  165. Closed set definition
  166. Modus ponens concept
  167. Equisatisfiability concept member
  168. Splitting a clause with a new variable example member
  169. The empty clause example member
  170. De Morgan's laws for sets statement
  171. Proof of the description of the open sets of a metric space proof
  172. Zorn's lemma statement
  173. Direct proof of propositional compactness for countably many variables proof member
  174. Sheffer stroke concept
  175. Craig interpolation for propositional logic statement member
  176. A formula and its negation as equisatisfiable formulas example member
  177. A satisfiable formula and a contradiction are not equisatisfiable example member
  178. Horn clause concept member
  179. Solving a Horn formula by marking example member
  180. The least model of a set of definite clauses example member
  181. Resolution concept member
  182. Compact space definition
  183. Closure definition
  184. Mathematical proof concept
  185. Affirming the consequent and denying the antecedent concept
  186. Hypothetical syllogism concept
  187. Open sets of a metric space statement
  188. The Sheffer stroke alone is functionally complete example member
  189. Hilbert system concept member
  190. Hilbert system definition member
  191. Tseitin transformation concept member
  192. A run of the Davis-Putnam procedure example member
  193. Resolution refutation of a chain of implications example member
  194. Resolving two variables at once example member
  195. Proof that the closure is closed proof
  196. Compact set definition
  197. Independence of axioms concept member
  198. A list that affirms the consequent is not a derivation in L example member
  199. Proof that a union of open sets of a metric space is open proof
  200. A derivation of p → p in the Hilbert system L example member
  201. Proof of the deduction theorem proof member
  202. Proof of the soundness theorem by induction on derivations proof member
  203. Renaming a subformula without defining clauses example member
  204. Tseitin transformation against the distributive CNF example member
  205. Tseitin transformation of a disjunction of conjunctions example member
  206. Mathematical induction concept
  207. Proof that compactness of a subset can be tested with open sets of the ambient space proof
  208. Independence of the third axiom of L example member
  209. Union of open sets is open statement
  210. Independence of the first and second axioms of L example member
  211. Deduction theorem statement member
  212. Soundness theorem for propositional logic statement member
  213. A satisfiable infinite chain of implications example member
  214. Proof of strong induction from ordinary induction proof
  215. Inductive and recursive definitions concept
  216. Compactness via open covers statement
  217. Proof that an intersection of closed sets of a metric space is closed proof
  218. A derivation of the transitivity law in L with the deduction theorem example member
  219. Proof of the basic theorems of the Hilbert system L proof member
  220. Strong induction statement
  221. Structural induction concept
  222. Proof of the finite intersection property characterisation of compactness proof
  223. Proof that a product of compact sets is compact by the tube lemma proof
  224. Intersection of closed sets is closed statement
  225. Basic theorems of the Hilbert system L statement member
  226. Proof of Hall's marriage theorem by induction on the number of sets proof
  227. Proof of Post's functional completeness theorem proof member
  228. Conjunction and disjunction do not form a functionally complete set example member
  229. Product of compact sets is compact statement
  230. Finite intersection property statement
  231. Closure is closed statement
  232. A matrix that does not respect modus ponens proves no independence example member
  233. Proof of Peirce's law proof member
  234. Hall's marriage theorem statement
  235. Kalmár's proof of the completeness theorem for propositional logic proof member
  236. Proof of the strong completeness theorem by maximal consistent sets proof member
  237. Post's functional completeness theorem statement member
  238. Proof that the closure is the smallest closed superset proof
  239. Peirce's law statement member
  240. Completeness theorem for propositional logic statement member
  241. Closure is the smallest closed superset statement
  242. Implicational propositional calculus concept member
  243. Proof of Tychonoff's theorem by maximal families with the finite intersection property proof
  244. Disjunction defined from implication example member
  245. Single axioms for propositional logic example member
  246. A derivation that uses Peirce's law in the implicational calculus example member
  247. Negation is not expressible in the implicational calculus example member
  248. Tychonoff's theorem statement
  249. Proof of propositional compactness by Tychonoff's theorem proof member
  250. Compactness theorem for propositional logic statement member
  251. Proof of the soundness and completeness of propositional resolution proof member
  252. Applications of propositional compactness example member
  253. Soundness and completeness of propositional resolution statement member
About this page
TagJDK63589SA
URIm2://JDK63589SA
Kindtopic
WritingW0 stub
MSC03B05
Part ofMathematical logic
Changed17 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a same_as or a source (0 of 1)
  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

History

Each change to this page, from its provenance log. A change by an agent names its run.

The changes to this page, the oldest first
DateChangeFieldBy
2026-11-17addthe whole nodetamnd
2026-11-17addthe section Remarkstamnd
2026-11-17changethe section Summarytamnd

What links here

Nodes in this topic