Truth tables

A truth table for a set of formulas over \(n\) variables is a table that enumerates all the possible truth assignments over the variables and the corresponding evaluated values of the formulas in its rows. In practise, building truth tables is only applicable for formulas with few variables because a truth table for formulas involving \(n\) variables has \(2^n\) rows.

Example: Truth tables for the connectives

Negation

\begin{array}{c|c} x&\neg x\\\hline \False & \True \\ \True & \False \end{array}
Conjunction

\begin{array}{cc|c} x&y&x \land y\\\hline \False & \False & \False \\ \False & \True & \False \\ \True & \False & \False \\ \True & \True & \True \end{array}
Disjunction

\begin{array}{cc|c} x&y&x \lor y\\\hline \False & \False & \False \\ \False & \True & \True \\ \True & \False & \True \\ \True & \True & \True \end{array}
Exclusive-or

\begin{array}{cc|c} x&y&x \Xor y\\\hline \False & \False & \False \\ \False & \True & \True \\ \True & \False & \True \\ \True & \True & \False \end{array}
Implication

\begin{array}{cc|c} x&y&x \Implies y\\\hline \False & \False & \True \\ \False & \True & \True \\ \True & \False & \False \\ \True & \True & \True \end{array}
Bi-implication

\begin{array}{cc|c} x&y&x \Iff y\\\hline \False & \False & \True \\ \False & \True & \False \\ \True & \False & \False \\ \True & \True & \True \end{array}

Example: Constructing a truth table

Consider the formula

\[(a \land b) \Xor \neg c\]

and its non-variable sub-formulas \((a \land b)\) and \(\neg c\). Let’s build the truth table for them, step-by-step. We start with the table below that lists in its rows all the 8 possible value combinations (i.e., truth assignments) for the variables \(\Set{a,b,c}\) appearing in the formulas.

\begin{array}{ccc|c|c|c@{}} a & b & c & (a \land b) & \neg c & (a \land b) \Xor \neg c \\ \hline \False & \False & \False & & & \\ \False & \False & \True & & & \\ \False & \True & \False & & & \\ \False & \True & \True & & & \\ \True & \False & \False & & & \\ \True & \False & \True & & & \\ \True & \True & \False & & & \\ \True & \True & \True & & & \\ \end{array}

Based on the columns for \(a\), \(b\) and \(c\), it is easy to next evaluate the values in the columns \(a \land b\) and \(\neg c\).

\begin{array}{ccc|c|c|c@{}} a & b & c & (a \land b) & \neg c & (a \land b) \Xor \neg c \\ \hline \False & \False & \False & \False & \True & \\ \False & \False & \True & \False & \False & \\ \False & \True & \False & \False & \True & \\ \False & \True & \True & \False & \False & \\ \True & \False & \False & \False & \True & \\ \True & \False & \True & \False & \False & \\ \True & \True & \False & \True & \True & \\ \True & \True & \True & \True & \False & \\ \end{array}

Finally, we can evaluate the values in the column \((a \land b) \Xor \neg c\) by using the ones in the columns \((a \land b)\) and \(\neg c\).

\begin{array}{ccc|c|c|c@{}} a & b & c & (a \land b) & \neg c & (a \land b) \Xor \neg c \\ \hline \False & \False & \False & \False & \True & \True \\ \False & \False & \True & \False & \False & \False \\ \False & \True & \False & \False & \True & \True \\ \False & \True & \True & \False & \False & \False \\ \True & \False & \False & \False & \True & \True \\ \True & \False & \True & \False & \False & \False \\ \True & \True & \False & \True & \True & \False \\ \True & \True & \True & \True & \False & \True \\ \end{array}

Observe that if we have a truth table for a formula, then it is easy to manually check whether the formula is satisfiable (at least one row contains \(\True\) in the column of the formula) or valid (all rows contain \(\True\)). For instance, we see that the formula \((a \land b) \Xor \neg c\) is satisfiable but not valid. In addition, it is easy to enumerate all its satisfying truth assignments by using the truth table.