Definition:Truth Table/Larger Tables

Computing Larger Truth Tables

Let $P$ be a formula we want to compute the truth table of.

We will use Peirce's Law as an example:

$P := \paren {\paren {p \implies q} \implies p} \implies p$

For each boolean interpretation for the set of propositional variables, we write its truth value underneath:

$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline \F & \F & \F & & \F & & \F & & \F \\ \end{array}$

In the above, we are using the boolean interpretation $v: \set {p, q} \to \set {\T, \F}$ given by:

\(\ds \map v p\)

\(=\)

\(\ds \F\)

\(\ds \map v q\)

\(=\)

\(\ds \F\)

Then we fill in the truth value of each of the WFFs on the parsing sequence of $P$, underneath its main connective:

$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline \F & \F & \F & & \F & & \F & & \F \\ & & & \T & & & & & \\ & & & & & \F & & & \\ & & & & & & & \T & \\ \end{array}$

In the above, this has been done on separate lines, so as to clarify the sequence in which this is done for the example.

In practice we write it like this:

$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline \F & \F & \F & \T & \F & \F & \F & \T & \F \\ \end{array}$

We repeat this for all other boolean interpretations:

$\begin{array}{cc||ccccccc} p & q & ((p & \implies & q) & \implies & p) & \implies & p \\ \hline \F & \F & \F & \T & \F & \F & \F & \T & \F \\ \F & \T & \F & \T & \T & \F & \F & \T & \F \\ \T & \F & \T & \F & \F & \T & \T & \T & \T \\ \T & \T & \T & \T & \T & \T & \T & \T & \T \\ \end{array}$

Sources

• 2012: M. Ben-Ari: Mathematical Logic for Computer Science (3rd ed.) ... (previous) ... (next): $\S 2.2.2$