---
title: Truth Assignments, Tautologies, and Consequence
module: Sentential Logic
moduleNumber: 2
lessonNumber: 2
order: 202
summary: >
  A truth assignment fixes the sentence symbols true or false, and a recursion
  extends it uniquely to every formula. Satisfaction, tautologies, and
  tautological implication — one formula following semantically from others —
  rest on that extension, and the truth-table procedure decides implication for
  finite premise sets.
topics: [Sentential Logic]
sources:
  - book: Enderton
    ref: "Ch. 1 — Sentential Logic; §1.2 Truth Assignments"
draft: false
---

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.[^enderton-truth]

## 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.

> **Definition (Truth assignment).** A **truth assignment** for a set $S$ of
> sentence symbols is a function $v : S \to \{F, T\}$, assigning a truth value to
> each symbol in $S$.

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.

> **Definition (Truth recursion).** $\bar{v}$ is the function on $\bar S$
> satisfying, for every $A \in S$ and all $\alpha, \beta \in \bar S$:
>
> $$
> \begin{aligned}
> \bar{v}(A) &= v(A), \\
> \bar{v}((\neg \alpha)) &= \begin{cases} T & \text{if } \bar v(\alpha) = F,\\ F & \text{otherwise,} \end{cases}
> &\bar{v}((\alpha \wedge \beta)) &= \begin{cases} T & \text{if } \bar v(\alpha)=T \text{ and } \bar v(\beta)=T,\\ F & \text{otherwise,} \end{cases}\\
> \bar{v}((\alpha \vee \beta)) &= \begin{cases} T & \text{if } \bar v(\alpha)=T \text{ or } \bar v(\beta)=T,\\ F & \text{otherwise,} \end{cases}
> &\bar{v}((\alpha \to \beta)) &= \begin{cases} F & \text{if } \bar v(\alpha)=T \text{ and } \bar v(\beta)=F,\\ T & \text{otherwise,} \end{cases}\\
> \bar{v}((\alpha \leftrightarrow \beta)) &= \begin{cases} T & \text{if } \bar v(\alpha)=\bar v(\beta),\\ F & \text{otherwise.} \end{cases}
> \end{aligned}
> $$

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

| $\alpha$ | $\beta$ | $\neg\alpha$ | $\alpha\wedge\beta$ | $\alpha\vee\beta$ | $\alpha\to\beta$ | $\alpha\leftrightarrow\beta$ |
| --- | --- | --- | --- | --- | --- | --- |
| $T$ | $T$ | $F$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $F$ | $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ | $F$ | $T$ | $T$ | $F$ |
| $F$ | $F$ | $T$ | $F$ | $F$ | $T$ | $T$ |

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

> **Theorem (Unique extension of a truth assignment).** For any truth assignment $v$ for a set $S$, there is a
> **unique** function $\bar{v} : \bar{S} \to \{F, T\}$ meeting the truth
> recursion.

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](/logic/sentential-logic/unique-readability-and-parsing); the recursion
theorem that turns unique readability into a well-defined $\bar v$ is proved in
[induction and recursion](/logic/sentential-logic/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.

$$
% caption: Evaluating a formula by propagating truth values up its formation
% tree; each node applies its connective's clause to the values already computed
% below it, ending with the value of the whole formula at the root.
\begin{tikzpicture}[font=\footnotesize, level distance=14mm,
  op/.style={draw, minimum size=9mm, inner sep=2pt, align=center, font=\footnotesize},
  lf/.style={draw, minimum size=8mm, inner sep=1pt, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[op, draw=acc, text=acc] (r) at (0,0) {or\\T};
  \node[op] (imp) at (-2.6,-1.6) {implies\\F};
  \node[op] (not) at (2.6,-1.6) {not\\T};
  \node[lf] (A) at (-3.7,-3.2) {A\\T};
  \node[lf] (B) at (-1.5,-3.2) {B\\F};
  \node[lf] (C) at (2.6,-3.2) {C\\F};
  \draw[black] (r) -- (imp);
  \draw[black] (r) -- (not);
  \draw[black] (imp) -- (A);
  \draw[black] (imp) -- (B);
  \draw[black] (not) -- (C);
\end{tikzpicture}
$$

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$.

> **Worked example.** Compute $\bar v(\alpha)$ for
> $\alpha = ((A_2 \to (A_1 \to A_6)) \leftrightarrow ((A_2 \wedge A_1) \to A_6))$
> under $v(A_1) = T$, $v(A_2) = T$, $v(A_6) = F$.
>
> Work up the formation tree, applying one connective clause per step:
>
> $$
> \begin{aligned}
> \bar v((A_1 \to A_6)) &= F && (T \to F),\\
> \bar v((A_2 \to (A_1 \to A_6))) &= F && (T \to F),\\
> \bar v((A_2 \wedge A_1)) &= T && (T \wedge T),\\
> \bar v(((A_2 \wedge A_1) \to A_6)) &= F && (T \to F),\\
> \bar v(\alpha) &= T && (F \leftrightarrow F).
> \end{aligned}
> $$
>
> The biconditional joins two $F$ subvalues, so $\bar v(\alpha) = T$. The other
> seven assignments for $\{A_1, A_2, A_6\}$ also give $T$, so $\alpha$ is a
> tautology.

## Satisfaction and consequence

> **Definition (Satisfaction).** A truth assignment $v$ **satisfies** $\varphi$
> iff $\bar v(\varphi) = T$. For this to be defined, the domain of $v$ must
> include every sentence symbol in $\varphi$.

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

> **Definition (Tautological implication).** $\Sigma$ **tautologically implies**
> $\tau$, written $\Sigma \models \tau$, iff every truth assignment (for the
> sentence symbols in $\Sigma$ and $\tau$) that satisfies every member of
> $\Sigma$ also satisfies $\tau$.

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.

$$
% caption: Tautological implication as containment of models: the assignments
% satisfying every premise all lie inside the assignments satisfying the
% conclusion, so no premise-model falsifies the conclusion.
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[black] (0,0) ellipse (4.4 and 2.9);
  \node[font=\footnotesize, anchor=north west] at (-4.3,2.8) {all assignments};
  \draw[black, fill=acc!7] (0.4,-0.1) ellipse (3.0 and 1.9);
  \node[font=\footnotesize] at (1.4,1.35) {satisfy the conclusion};
  \draw[draw=acc, fill=acc!16] (-0.5,-0.15) ellipse (1.6 and 1.15);
  \node[text=acc, font=\footnotesize, align=center] at (-0.5,-0.15) {satisfy every\\premise};
\end{tikzpicture}
$$

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.

> **Definition (Tautology, equivalence, satisfiability).** A wff $\tau$ is a
> **tautology** ($\models \tau$) iff every truth assignment satisfies it. Wffs
> $\sigma$ and $\tau$ are **tautologically equivalent**
> ($\sigma \models\mid\models \tau$) iff $\sigma \models \tau$ and
> $\tau \models \sigma$. A set $\Sigma$ is **satisfiable** iff some single
> assignment satisfies every member.

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.

$$
% caption: The truth-table search for a counterexample: scan the rows, keep only
% those satisfying all premises, and check the conclusion there; an implication
% fails exactly when some premise-satisfying row (highlighted) falsifies the
% conclusion.
\begin{tikzpicture}[font=\footnotesize,
  row/.style={draw, minimum width=52mm, minimum height=6mm, anchor=west, font=\footnotesize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[font=\footnotesize, anchor=west] at (0,3.0) {keep only premise-satisfying rows};
  \node[row] at (0,2.4) {row 1: premises fail};
  \node[row] at (0,1.7) {row 2: conclusion holds};
  \node[row, draw=acc, fill=acc!12] at (0,1.0) {row 3: conclusion fails};
  \node[row] at (0,0.3) {row 4: premises fail};
  \draw[->, acc] (5.6,1.0) -- (6.4,1.0);
  \node[text=acc, anchor=west, align=left, font=\footnotesize] at (6.5,1.0) {counterexample:\\implication fails};
\end{tikzpicture}
$$

> **Worked example.** Decide $(\neg (A \wedge B)) \models ((\neg A) \vee (\neg B))$
> by truth table.
>
> Tabulate all four assignments for $\{A, B\}$, computing each side:
>
> | $A$ | $B$ | $(\neg (A \wedge B))$ | $((\neg A) \vee (\neg B))$ |
> | --- | --- | --- | --- |
> | $T$ | $T$ | $F$ | $F$ |
> | $T$ | $F$ | $T$ | $T$ |
> | $F$ | $T$ | $T$ | $T$ |
> | $F$ | $F$ | $T$ | $T$ |
>
> The premise is $T$ in rows 2–4, and the conclusion is $T$ in each of them, so
> the implication holds. The converse holds as well, so the two sides are
> tautologically equivalent — one of **De Morgan's laws**. Replacing the
> conclusion by $((\neg A) \wedge (\neg B))$ breaks it: at $v(A) = T, v(B) = F$
> the premise is $T$ but $((\neg A) \wedge (\neg B)) = F \wedge T = F$, so
> $(\neg (A \wedge B)) \not\models ((\neg A) \wedge (\neg B))$.

$$
% caption: The four assignments for two symbols with both sides of the De Morgan
% implication computed; the three shaded rows satisfy the premise and each also
% satisfies the conclusion, so the implication holds.
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \fill[acc!12] (-0.6,0.375) rectangle (6.9,0.925);
  \fill[acc!12] (-0.6,-0.225) rectangle (6.9,0.325);
  \fill[acc!12] (-0.6,-0.825) rectangle (6.9,-0.275);
  \draw[black] (0.55,-0.85) -- (0.55,2.25);
  \draw[black] (1.55,-0.85) -- (1.55,2.25);
  \draw[black] (4.0,-0.85) -- (4.0,2.25);
  \node at (0.05,2.0) {A};
  \node at (1.05,2.0) {B};
  \node[font=\scriptsize] at (2.75,2.0) {not (A and B)};
  \node[font=\scriptsize] at (5.4,2.0) {(not A) or (not B)};
  \draw[black] (-0.6,1.68) -- (6.9,1.68);
  \foreach \y/\a/\b/\p/\c in {1.25/T/T/F/F, 0.65/T/F/T/T, 0.05/F/T/T/T, -0.55/F/F/T/T} {
    \node at (0.05,\y) {\a}; \node at (1.05,\y) {\b};
    \node at (2.75,\y) {\p}; \node at (5.4,\y) {\c};
  }
  \node[anchor=west, text=acc, font=\scriptsize, align=left] at (7.2,0.05) {premise true,\\conclusion true};
\end{tikzpicture}
$$

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.[^enderton-tt]
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.

| Name | Tautology |
| --- | --- |
| Excluded middle | $(A \vee (\neg A))$ |
| Contradiction | $(\neg (A \wedge (\neg A)))$ |
| Double negation | $((\neg (\neg A)) \leftrightarrow A)$ |
| Contraposition | $((A \to B) \leftrightarrow ((\neg B) \to (\neg A)))$ |
| Exportation | $(((A \wedge B) \to C) \leftrightarrow (A \to (B \to C)))$ |
| De Morgan | $((\neg (A \wedge B)) \leftrightarrow ((\neg A) \vee (\neg B)))$ |
| De Morgan | $((\neg (A \vee B)) \leftrightarrow ((\neg A) \wedge (\neg B)))$ |
| Distributive | $((A \wedge (B \vee C)) \leftrightarrow ((A \wedge B) \vee (A \wedge C)))$ |
| Distributive | $((A \vee (B \wedge C)) \leftrightarrow ((A \vee B) \wedge (A \vee C)))$ |

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](/logic/sentential-logic/compactness-and-effectiveness).

> **Theorem (Compactness).** A set $\Sigma$ of wffs is satisfiable iff every finite
> subset of $\Sigma$ is satisfiable.

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.

[^enderton-truth]: Enderton, §1.2 — truth values, truth assignments, the recursive extension $\bar v$, satisfaction, tautological implication and equivalence, and Theorem 12A on the unique extension.
[^enderton-tt]: Enderton, §1.2 — the truth-table decision procedure, the $2^n$-row cost, the age-of-the-universe estimate for $n = 80$, and the reference to the P versus NP problem.