Skip to content
Topos Uranos
English

Semantics of propositional logic

Summary

So far formulas have been strings of circles and disks, and deductions, manipulations of strings: nothing has been said about their truth. This lesson gives them meaning. A valuation assigns to each variable one of the two truth values, 11 (true) and 00 (false), and is extended to all formulas in a unique way, by recursion on their complexity, with a single clause: (φ↓ψ)(\varphi \downarrow \psi) has the value 11 exactly when φ\varphi and ψ\psi have the value 00. From that clause and from the official abbreviations one computes, without stipulating anything else, the values of negation, disjunction, conjunction, implication, the biconditional and exclusive disjunction. The coincidence lemma, proved by induction on complexity, ensures that the value of a formula depends only on the values of its variables; it follows that the truth table, with 2n2^n rows for nn variables, contains everything that the infinitely many valuations can say about the formula. With this, satisfaction, validity, satisfiability, contradiction and contingency are defined, the formulas ⊤\top and ⊥\bot are fixed, and the problem of deciding validity is posed, which tables solve at a cost that grows exponentially with the number of variables.

Learning objectives

  1. Compute the truth value of a formula under a valuation by means of its recursive extension, and derive from the official abbreviations the value of each defined connective.
  2. Prove the coincidence lemma by induction on complexity, and explain with it why a truth table with 2n2^n rows suffices to study a formula with nn variables.
  3. Build truth tables column by column and classify formulas as valid, contingent or contradictions, and sets of formulas as satisfiable or unsatisfiable, without confusing ⊭φ\not\models \varphi with contradiction.
  4. Decide the validity of a formula by searching for a valuation that falsifies it, and estimate the cost of the method of tables as a function of the number of variables.

The meaning of formulas

The unit on language built, in the lesson on the language of propositional logic, a set of strings of two symbols, and the unit on deduction taught how to obtain some strings from others with axioms and rules. Neither of them spoke of truth: the deductive system transforms symbols according to their form, like a machine that does not understand what it writes. Now, the language was built to represent statements, and the lesson on the formalization of natural language gave them informal readings: (φ↓ψ)(\varphi \downarrow \psi) is true when φ\varphi and ψ\psi are both false, and the readings of the other connectives were derived from this one. Semantics turns those readings into mathematical definitions.

Two decisions found it. The first is bivalence: there are exactly two truth values, written 11 (true) and 00 (false), and each formula, in each situation, has one of them. The second is truth-functionality: the value of a compound formula depends only on the values of its components, not on its subject matter, so that the truth of the variables decides that of all formulas. The lesson on formalization showed the price of this second decision (causality, modality and time are left out); its reward is that the semantics of the whole language is obtained from a single clause, that of the primitive connective.

It should also be noted that this unit works entirely in the metalanguage. The assertions “φ\varphi is true under such a valuation” or “φ\varphi is a tautology” are not formulas, but mathematical statements about formulas, and they are proved by ordinary reasoning, often by induction on complexity; they are not deductions in the course system. The relation between the two worlds, that everything derivable is true and that everything true in the precise sense of this unit is derivable, is the subject of the unit on metatheory.