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
- Propositional calculus: the formal system as a whole, its language, semantics and proof theory.
- Propositional formula: the formulas, defined by induction from variables and connectives.
- Unique readability theorem: each formula is built in exactly one way.
- Truth valuation: the unique extension of a truth assignment to all formulas.
- Logical consequence: the relation .
- Satisfiability: sets of formulas that some assignment makes true.
- Equisatisfiability: formulas that are satisfiable together or not at all.
- Conjunctive normal form: conjunctions of clauses, and the conversion to them.
- Disjunctive normal form: disjunctions of conjunctions of literals, read off a truth table.
- Clause: finite sets of literals, read as disjunctions.
- Horn clause: clauses with at most one positive literal, and their fast satisfiability test.
- Functional completeness: sets of connectives that express every truth function.
- Post's functional completeness theorem: the five classes that decide functional completeness.
- Hilbert system: the axiom system L with modus ponens.
- Deduction theorem: from to .
- Peirce's law: a classical tautology in implication alone.
- Implicational propositional calculus: the fragment with implication as the only connective.
- Single axioms for propositional logic: one axiom schema with one rule.
- Independence of axioms: the method of many-valued truth tables.
- Soundness theorem for propositional logic: every derivable formula is a consequence.
- Completeness theorem for propositional logic: every consequence is derivable.
- Compactness theorem for propositional logic: satisfiability is decided by finite subsets.
- Applications of propositional compactness: colourings, orders and other infinite combinatorics.
- Resolution: a proof system with one rule on clauses.
- Tseitin transformation: a linear-size equisatisfiable CNF.
- Craig interpolation for propositional logic: an implication explained in the shared variables.
Prerequisites
- The connectives, truth tables, tautologies and logical equivalence, from the topic propositions, connectives and quantifiers.
- Formal languages, formal systems and rules of inference, from the topic logic, formal systems and foundations.
- Proofs by induction, in particular structural induction, and the habits of proof from the area reasoning and proof.
- For the compactness theorem on uncountable sets of variables: Zorn's lemma or Tychonoff's theorem.
Everything in this topic
The members of this topic and each page that they need, 253 pages in all.
- Alphabet concept
- Arity concept
- Boolean function concept
- Cartesian product concept
- Clone concept
- Clopen set concept
- Countable set concept
- Countermodel concept
- Definition by recursion concept
- Effectively decidable set concept
- Element definition
- Equality (mathematics) concept
- Finitary operation concept
- Finite set concept
- Formal language concept
- Function concept
- Graph concept
- Graph colouring concept
- Heyting algebra concept
- Induction on well-formed formulas concept
- Mathematical statement definition
- Maximal and minimal elements concept
- Monotone function concept
- Natural numbers object
- Partial order concept
- Peano axioms concept
- Product topology concept
- Proof of Zorn's lemma proof
- Proposition concept
- Propositional letter concept
- Real numbers object
- Rooted tree concept
- Set concept
- String concept
- Total order concept
- Tuple concept
- Signature concept
- Functional completeness definition member
- Set definition
- Logical connective definition
- Connectives in mathematical language concept
- Successor function definition
- Conjunction definition
- Disjunction definition
- Material implication definition
- Principle of bivalence concept
- Linear extension definition
- Predicate concept
- Predicate definition
- Empty set object
- Family of sets definition
- Ordered pair definition
- Intersection definition
- Union definition
- Addition of natural numbers definition
- Conditional statements concept
- Structure concept
- Biconditional definition
- The successor function is injective statement
- Zero is not a successor statement
- Term concept
- Negation concept
- Negation definition
- Cartesian product definition
- Atomic formula concept
- Truth table concept
- Order on the natural numbers definition
- Material implication concept
- Conjunction concept
- Disjunction concept
- Tautology concept
- Biconditional concept
- Universal quantifier concept
- Universal quantifier definition
- Existential quantifier definition
- Intersection of a family of sets definition
- Union of a family of sets definition
- Axiom of extensionality statement
- Subset definition
- Uniqueness quantifier definition
- Logical equivalence concept
- Logical connective concept
- Existential quantifier concept
- Binary relation definition
- Topological space definition
- Universal set definition
- Well-formed formula concept
- A switching circuit read as a propositional formula example member
- Converse and inverse of an implication concept
- Propositional calculus concept member
- Proof of the double negation law by a truth table proof
- Propositional formula definition member
- Propositional formula concept member
- Antisymmetric relation definition
- Reflexive relation definition
- Transitive relation definition
- Basis of a topology definition
- Function definition
- Subspace topology definition
- Tautology definition
- Complement definition
- Truth valuation definition member
- First-order logic concept
- Double negation law statement
- Conjunctive normal form definition member
- Disjunctive normal form definition member
- Reading a formula in Polish notation example member
- Formal system concept
- Proof of unique readability by counting brackets proof member
- Strings that are not propositional formulas example member
- Formation sequence and parse tree of a propositional formula example member
- Product topology definition
- Subbasis definition
- Preorder definition
- Choice function definition
- Disjunctive normal form of p ↔ q example member
- The Boolean function of exclusive or defined by a formula example member
- Full disjunctive normal form of the majority of three variables example member
- Conjunctive normal form of exclusive or from the truth table example member
- A map on formulas that extends an assignment but is not a truth valuation example member
- Computing the truth value of a formula example member
- Logical equivalence definition
- Metric space definition
- The formula p ∧ (q ∨ r) is not in disjunctive normal form example member
- Unique readability theorem statement member
- Product topology on an arbitrary product definition
- Partial order definition
- Axiom of choice statement
- Truth valuation concept member
- Open ball definition
- Proof of De Morgan's laws (logic) by truth tables proof
- Maximal element definition
- Total order definition
- Upper bound definition
- Modus ponens as a logical consequence example member
- A conjunction of literals is not a clause example member
- Affirming the consequent is not a logical consequence example member
- Disjunctive normal form concept member
- Metric topology definition
- Conjunctive normal form concept member
- Logical consequence concept member
- De Morgan's laws (logic) statement
- An unsatisfiable set from modus ponens example member
- Logical consequence definition member
- Satisfiability definition member
- A clause with three literals example member
- A satisfiable set of three clauses example member
- Disjunctive syllogism as a logical consequence example member
- Clause concept member
- Chain definition
- Open set definition
- Proof of De Morgan's laws for sets proof
- Functional completeness concept member
- Negation and implication form a functionally complete set example member
- An argument checked in the propositional calculus example member
- Proof of Craig interpolation for propositional logic proof member
- Satisfiability concept member
- Rule of inference concept
- Conjunctive normal form of (p → q) → r example member
- The Socrates syllogism is not valid in the propositional calculus example member
- A disjunction of two variables is not a Horn clause example member
- The formula ¬(p ∨ q) ∧ r is not in conjunctive normal form example member
- Horn clause definition member
- Open cover definition
- Closed set definition
- Modus ponens concept
- Equisatisfiability concept member
- Splitting a clause with a new variable example member
- The empty clause example member
- De Morgan's laws for sets statement
- Proof of the description of the open sets of a metric space proof
- Zorn's lemma statement
- Direct proof of propositional compactness for countably many variables proof member
- Sheffer stroke concept
- Craig interpolation for propositional logic statement member
- A formula and its negation as equisatisfiable formulas example member
- A satisfiable formula and a contradiction are not equisatisfiable example member
- Horn clause concept member
- Solving a Horn formula by marking example member
- The least model of a set of definite clauses example member
- Resolution concept member
- Compact space definition
- Closure definition
- Mathematical proof concept
- Affirming the consequent and denying the antecedent concept
- Hypothetical syllogism concept
- Open sets of a metric space statement
- The Sheffer stroke alone is functionally complete example member
- Hilbert system concept member
- Hilbert system definition member
- Tseitin transformation concept member
- A run of the Davis-Putnam procedure example member
- Resolution refutation of a chain of implications example member
- Resolving two variables at once example member
- Proof that the closure is closed proof
- Compact set definition
- Independence of axioms concept member
- A list that affirms the consequent is not a derivation in L example member
- Proof that a union of open sets of a metric space is open proof
- A derivation of p → p in the Hilbert system L example member
- Proof of the deduction theorem proof member
- Proof of the soundness theorem by induction on derivations proof member
- Renaming a subformula without defining clauses example member
- Tseitin transformation against the distributive CNF example member
- Tseitin transformation of a disjunction of conjunctions example member
- Mathematical induction concept
- Proof that compactness of a subset can be tested with open sets of the ambient space proof
- Independence of the third axiom of L example member
- Union of open sets is open statement
- Independence of the first and second axioms of L example member
- Deduction theorem statement member
- Soundness theorem for propositional logic statement member
- A satisfiable infinite chain of implications example member
- Proof of strong induction from ordinary induction proof
- Inductive and recursive definitions concept
- Compactness via open covers statement
- Proof that an intersection of closed sets of a metric space is closed proof
- A derivation of the transitivity law in L with the deduction theorem example member
- Proof of the basic theorems of the Hilbert system L proof member
- Strong induction statement
- Structural induction concept
- Proof of the finite intersection property characterisation of compactness proof
- Proof that a product of compact sets is compact by the tube lemma proof
- Intersection of closed sets is closed statement
- Basic theorems of the Hilbert system L statement member
- Proof of Hall's marriage theorem by induction on the number of sets proof
- Proof of Post's functional completeness theorem proof member
- Conjunction and disjunction do not form a functionally complete set example member
- Product of compact sets is compact statement
- Finite intersection property statement
- Closure is closed statement
- A matrix that does not respect modus ponens proves no independence example member
- Proof of Peirce's law proof member
- Hall's marriage theorem statement
- Kalmár's proof of the completeness theorem for propositional logic proof member
- Proof of the strong completeness theorem by maximal consistent sets proof member
- Post's functional completeness theorem statement member
- Proof that the closure is the smallest closed superset proof
- Peirce's law statement member
- Completeness theorem for propositional logic statement member
- Closure is the smallest closed superset statement
- Implicational propositional calculus concept member
- Proof of Tychonoff's theorem by maximal families with the finite intersection property proof
- Disjunction defined from implication example member
- Single axioms for propositional logic example member
- A derivation that uses Peirce's law in the implicational calculus example member
- Negation is not expressible in the implicational calculus example member
- Tychonoff's theorem statement
- Proof of propositional compactness by Tychonoff's theorem proof member
- Compactness theorem for propositional logic statement member
- Proof of the soundness and completeness of propositional resolution proof member
- Applications of propositional compactness example member
- Soundness and completeness of propositional resolution statement member
About this page
| Tag | JDK63589SA |
|---|---|
| URI | m2://JDK63589SA |
| Kind | topic |
| Writing | W0 stub |
| MSC | 03B05 |
| Part of | Mathematical logic |
| Changed | 17 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.
| Date | Change | Field | By |
|---|---|---|---|
| 2026-11-17 | add | the whole node | tamnd |
| 2026-11-17 | add | the section Remarks | tamnd |
| 2026-11-17 | change | the section Summary | tamnd |
What links here
Nodes in this topic
- Disjunctive normal form
- Conjunctive normal form
- Propositional calculus
- Conjunctive normal form
- Disjunctive normal form
- Independence of the third axiom of L
- Conjunctive normal form of exclusive or from the truth table
- Logical consequence
- Hilbert system
- Proof of Peirce's law
- A run of the Davis-Putnam procedure
- Compactness theorem for propositional logic
- Splitting a clause with a new variable
- Single axioms for propositional logic
- Proof of unique readability by counting brackets
- Proof of the deduction theorem
- Unique readability theorem
- The formula ¬(p ∨ q) ∧ r is not in conjunctive normal form
- Direct proof of propositional compactness for countably many variables
- Independence of axioms
- A list that affirms the consequent is not a derivation in L
- The formula p ∧ (q ∨ r) is not in disjunctive normal form
- Completeness theorem for propositional logic
- A satisfiable infinite chain of implications
- A disjunction of two variables is not a Horn clause
- Tseitin transformation of a disjunction of conjunctions
- Deduction theorem
- Solving a Horn formula by marking
- A clause with three literals
- Equisatisfiability
- Formation sequence and parse tree of a propositional formula
- Resolving two variables at once
- A satisfiable set of three clauses
- Soundness and completeness of propositional resolution
- Conjunctive normal form of (p → q) → r
- Disjunction defined from implication
- The Socrates syllogism is not valid in the propositional calculus
- Proof of the soundness and completeness of propositional resolution
- Hilbert system
- Computing the truth value of a formula
- The Boolean function of exclusive or defined by a formula
- Negation and implication form a functionally complete set
- Functional completeness
- A derivation that uses Peirce's law in the implicational calculus
- Peirce's law
- Proof of the strong completeness theorem by maximal consistent sets
- Truth valuation
- Conjunction and disjunction do not form a functionally complete set
- Modus ponens as a logical consequence
- Strings that are not propositional formulas
- Tseitin transformation against the distributive CNF
- The empty clause
- Satisfiability
- Kalmár's proof of the completeness theorem for propositional logic
- Logical consequence
- Disjunctive normal form of p ↔ q
- A satisfiable formula and a contradiction are not equisatisfiable
- A derivation of the transitivity law in L with the deduction theorem
- Proof of propositional compactness by Tychonoff's theorem
- Reading a formula in Polish notation
- An unsatisfiable set from modus ponens
- Proof of Craig interpolation for propositional logic
- Truth valuation
- Negation is not expressible in the implicational calculus
- The Sheffer stroke alone is functionally complete
- A formula and its negation as equisatisfiable formulas
- Proof of Post's functional completeness theorem
- Full disjunctive normal form of the majority of three variables
- Satisfiability
- Horn clause
- Resolution refutation of a chain of implications
- Tseitin transformation
- Applications of propositional compactness
- A derivation of p → p in the Hilbert system L
- A matrix that does not respect modus ponens proves no independence
- A switching circuit read as a propositional formula
- Clause
- Functional completeness
- Propositional formula
- An argument checked in the propositional calculus
- Craig interpolation for propositional logic
- Propositional formula
- A conjunction of literals is not a clause
- Disjunctive syllogism as a logical consequence
- The least model of a set of definite clauses
- Independence of the first and second axioms of L
- Proof of the soundness theorem by induction on derivations
- Post's functional completeness theorem
- A map on formulas that extends an assignment but is not a truth valuation
- Soundness theorem for propositional logic
- Proof of the basic theorems of the Hilbert system L
- Basic theorems of the Hilbert system L
- Renaming a subformula without defining clauses
- Resolution
- Implicational propositional calculus
- Horn clause
- Affirming the consequent is not a logical consequence