1.2 Semantics: Truth Tables

Semantics assigns meaning to the formulas of propositional logic by assigning truth values to propositional variables and then extending this assignment to all formulas according to the logical connectives.

Truth Values

We use two truth values:

\mathrm{T}

and:

\mathrm{F}

The value $\mathrm{T}$ means true, and the value $\mathrm{F}$ means false, and every formula in classical propositional logic will receive exactly one of these two values once a valuation has been fixed.

Definition 1.10 (Valuation)

A valuation is a function:

v : \mathrm{Var} \to \{\mathrm{T}, \mathrm{F}\}

from the set of propositional variables to the set of truth values.

Thus a valuation assigns to each propositional variable either $\mathrm{T}$ or $\mathrm{F}$ , and it should be understood as one possible assignment of truth values to the atomic statements of the language.

For example, if the variables are $p$ , $q$ , and $r$ , then one possible valuation is given by:

v(p)=\mathrm{T}, \quad v(q)=\mathrm{F}, \quad v(r)=\mathrm{T}

Definition 1.11 (Evaluation of Formulas)

Every valuation $v$ extends uniquely to a function on all formulas, also denoted by $v$ , by recursion on the structure of formulas.

If $A$ is a propositional variable, then $v(A)$ is the value already assigned to $A$ by the valuation.

If $A = ¬B$ , then:

v(A)=\mathrm{T}

if and only if:

v(B)=\mathrm{F}

If $A = (B \land C)$ , then:

v(A)=\mathrm{T}

if and only if:

v(B)=\mathrm{T} \quad \text{and} \quad v(C)=\mathrm{T}

If $A = (B \lor C)$ , then:

v(A)=\mathrm{T}

if and only if:

v(B)=\mathrm{T} \quad \text{or} \quad v(C)=\mathrm{T}

If $A = (B \to C)$ , then:

v(A)=\mathrm{F}

if and only if:

v(B)=\mathrm{T} \quad \text{and} \quad v(C)=\mathrm{F}

If $A = (B \leftrightarrow C)$ , then:

v(A)=\mathrm{T}

if and only if:

v(B)=v(C)

This recursive definition is possible because formulas were defined inductively, and it gives a precise way to compute the truth value of any formula from the truth values of its variables.

Example 1.12

Let $v$ be the valuation defined by:

v(p)=\mathrm{T} \quad \text{and} \quad v(q)=\mathrm{F}

Then:

v(¬p)=\mathrm{F}

because $p$ is true under $v$ , and negation reverses the truth value.

Also:

v(p \land q)=\mathrm{F}

because a conjunction is true only when both conjuncts are true.

We have:

v(p \lor q)=\mathrm{T}

because a disjunction is true when at least one disjunct is true.

Finally:

v(p \to q)=\mathrm{F}

because implication is false exactly when its antecedent is true and its consequent is false.

Truth Tables

A truth table records the value of a formula under all possible valuations of the variables that occur in it.

If a formula contains $n$ distinct variables, then there are:

2^n

possible assignments of truth values to those variables, and therefore the truth table has $2^n$ rows.

Truth tables are useful because they give a complete semantic description of a formula in a finite and explicit form, at least when the number of variables is small enough to make the table manageable.

Example 1.13

Consider the formula:

(p \land q) \to p

The truth table is:

$p$	$q$	$p \land q$	$(p \land q) \to p$
$\mathrm{T}$	$\mathrm{T}$	$\mathrm{T}$	$\mathrm{T}$
$\mathrm{T}$	$\mathrm{F}$	$\mathrm{F}$	$\mathrm{T}$
$\mathrm{F}$	$\mathrm{T}$	$\mathrm{F}$	$\mathrm{T}$
$\mathrm{F}$	$\mathrm{F}$	$\mathrm{F}$	$\mathrm{T}$

The last column is $\mathrm{T}$ in every row, so the formula is true under every valuation.

Definition 1.14 (Satisfiability, Validity, Contradiction)

A formula $A$ is satisfiable if there exists a valuation $v$ such that:

v(A)=\mathrm{T}

A formula $A$ is valid if for every valuation $v$ :

v(A)=\mathrm{T}

A formula $A$ is a contradiction if for every valuation $v$ :

v(A)=\mathrm{F}

These three notions classify formulas according to their behavior across all possible valuations.

Example 1.15

The formula:

p \lor ¬p

is valid, because for every valuation either $p$ is true or $p$ is false, and in both cases the disjunction is true.

The formula:

p \land ¬p

is a contradiction, because no valuation can make both $p$ and $¬p$ true at the same time.

The formula:

p \land q

is satisfiable but not valid, because it is true when both $p$ and $q$ are true, but it is false under many other valuations.

Lemma 1.16 (Unique Evaluation)

For every valuation $v$ and every formula $A$ , the truth value $v(A)$ is uniquely determined.

Proof

The proof is by structural induction on the formula $A$ .

If $A$ is a propositional variable, then $v(A)$ is uniquely determined by the definition of the valuation.

If $A = ¬B$ , then by the induction hypothesis the value $v(B)$ is uniquely determined, and therefore the value of $v(¬B)$ is uniquely determined by the truth rule for negation.

If $A = (B \circ C)$ for a binary connective $\circ$ , then by the induction hypothesis the values $v(B)$ and $v(C)$ are uniquely determined, and therefore the value of $v(B \circ C)$ is uniquely determined by the truth rule for the connective $\circ$ .

Boolean Function View

If a formula $A$ contains variables among:

p_1, p_2, \dots, p_n

then $A$ determines a Boolean function:

f_A : \{\mathrm{T}, \mathrm{F}\}^n \to \{\mathrm{T}, \mathrm{F}\}

This function sends each tuple of truth values assigned to the variables to the truth value of the formula under the corresponding valuation.

This viewpoint is useful because it connects propositional logic with Boolean algebra, digital circuits, and computation, where formulas can be studied as functions from binary inputs to binary outputs.