Truth Assignments, Tautologies, and Consequence

The syntax so far manipulates strings without meaning. To say precisely when one wff follows logically from others — when $A_1$ follows from $(A_1\wedge A_2)$, say, no matter what English sentences the parameters translate — the vague phrase no matter what English sentence must be made exact. Its content is captured by ranging over all ways of assigning truth values to the sentence symbols.¹

Truth assignments

Fix a two-element set $\{F,T\}$ of truth values, $F$ for falsity and $T$ for truth. Committing to exactly two values is a choice; three-valued and infinite-valued logics exist, but two-valued logic is the case of primary interest and the only one treated here.

A truth assignment fixes only the atoms. To evaluate a compound formula, the assignment must be extended so that the connectives compute the right values. Write $\bar{S}$ for the set of wffs built from the symbols in $S$. We seek an extension $\bar{v}:\bar{S}\to \{F,T\}$ that agrees with $v$ on the symbols and respects each connective.

These clauses are the truth tables of the connectives, written as a recursion. Tabulated:

The conditional deserves a note. Whenever $\alpha$ is false, $(\alpha \to \beta )$ is assigned $T$ — it is vacuously true. Reading $(\alpha \to \beta )$ as a promise if $\alpha$ holds, then $\beta$, a false antecedent leaves the promise unbroken regardless of $\beta$. Whether this exactly matches if–then in ordinary speech is beside the point; the concern is with mathematical statements, where the truth-functional reading is the useful one.

The extension exists and is unique

Existence and uniqueness both hinge on formulas having exactly one formation tree. If a wff could be read two ways — as an $\wedge$-formula and as a $\vee$-formula, say — the recursion might demand two different values and no $\bar{v}$ would exist. That formulas cannot be so misread is unique readability, proved in the parsing lesson; the recursion theorem that turns unique readability into a well-defined $\bar{v}$ is proved in induction and recursion. For now, take $\bar{v}$ as given and compute with it.

To evaluate $\bar{v}(\alpha )$, assign values to the leaves of the formation tree of $\alpha$ and propagate upward, applying one connective clause at each node.

The figure evaluates $((A\to B)\vee (\neg C))$ under $v(A)=T$, $v(B)=F$, $v(C)=F$. The conditional gets $F$ (true antecedent, false consequent), the negation gets $T$, and their disjunction is $T$.

Satisfaction and consequence

Now let $\Sigma$ be a set of wffs, read as hypotheses, and $\tau$ a single wff, read as a candidate conclusion.

This is the semantic reading of follows from: if the hypotheses come out true, the conclusion is forced true. Every model of the premises is a model of the conclusion.

Two boundary cases complete the definition.

• Empty premise set. Every assignment vacuously satisfies every member of $\varnothing$, so $\varnothing \models \tau$ iff every assignment satisfies $\tau$. In that case $\tau$ is a tautology, written $\models \tau$.
• Unsatisfiable premises. If no assignment satisfies all of $\Sigma$, then $\Sigma \models \tau$ holds vacuously for every $\tau$. So $\{A,(\neg A)\}\models B$: nothing satisfies a formula and its negation together, so the implication is free. No deep principle is involved; it is a by-product of the definitions.

For a worked implication, take $\{A,(A\to B)\}\models B$. Of the four assignments for $\{A,B\}$, only $v(A)=v(B)=T$ satisfies both $A$ and $(A\to B)$, and that $v$ satisfies $B$. For an equivalence, $(\neg (C\vee K))$ and $((\neg C)\wedge (\neg K))$ are tautologically equivalent: they agree on all four assignments to $C$ and $K$.

Deciding implication by truth tables

Tautological implication is decidable by a systematic procedure. To test $\{{\sigma }_1,\dots ,{\sigma }_k\}\models \tau$, list all $2^n$ truth assignments for the $n$ sentence symbols involved, compute each ${\sigma }_i$ and $\tau$ under every assignment, and check that every row satisfying all the ${\sigma }_i$ also satisfies $\tau$. When $k=0$ the same procedure decides whether $\tau$ is a tautology.

The procedure is general but expensive. A wff with $n$ sentence symbols needs a table of $2^n$ rows, which grows beyond reach quickly: at a million rows per second, $n=80$ would take more time than the age of the universe.² Whether some procedure decides tautologyhood in time polynomial in $n$ rather than exponential is the P versus NP problem, the central open question of theoretical computer science; the answer is widely believed to be negative.

A selected list of tautologies

Certain equivalences and tautologies recur so often they are worth naming. Each is verified by its (small) truth table.

Conjunction, disjunction, and the biconditional are associative and commutative, so grouping and order inside repeated $\wedge$, $\vee$, or $\leftrightarrow$ do not affect the truth value. Two derived facts are used constantly.

• Deduction. $\Sigma ;\alpha \models \beta$ iff $\Sigma \models (\alpha \to \beta )$, where $\Sigma ;\alpha$ abbreviates $\Sigma \cup \{\alpha \}$. Hypotheses and antecedents trade places.
• Equivalence via biconditional. $\alpha \models \mid \models \beta$ iff $\models (\alpha \leftrightarrow \beta )$.

The compactness theorem

One nontrivial fact about satisfiability can be stated now, though its proof comes only in compactness and effectiveness.

For a finite $\Sigma$ the statement is trivial; the content is that satisfiability of an infinite set is controlled entirely by its finite subsets. The name comes from topology: the theorem asserts the compactness of a certain product space, and can be derived from Tychonoff's theorem. It lifts sentential logic to infinite constraint problems, such as coloring an infinite graph.