[Part 6] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles First example - Truth table approach

So far in this series, we have been working on the following Knights and Knaves puzzle:

A makes the following statement, "At least one of us is a knave."  

What are A and B?

First, we solved it informally.

Second, we solved it using a rather long, linear formal proof. 

Third, in the previous post, we solved it using a hierarchical, natural deduction-style proof.

In this post, we will solve it using the truth table approach.

A truth table is a two-dimensional representation (as a grid) of all the possible values that a logical formula can take based on the values of the propositions that it contains.

A truth table for formula \(\varphi\) contains one column for each proposition in \(\varphi\). If \(\varphi\) contains \(n\) distinct propositions, the \(n\) leftmost columns of its truth table will correspond to these \(n\) propositions, in arbitrary (usually alphabetical) order.

Each row of the table contains one possible assignment of truth values to all \(n\) propositions in \(\varphi\).

Therefore, the number of rows in a truth table is equal to the total number of distinct assignments of truth values to the propositions in \(\varphi\). 

Since each proposition has exactly two possible values (\(T\) or \(F\), for True or False, respectively), the number of distinct assignments to all \(n\) distinct propositions in a formula is equal to \(2^n\).

The rightmost column in a truth table contains the truth value of the whole formula \(\varphi\) for each assignment of truth values to the propositions in \(\varphi\).

The middle columns of a truth table correspond to sub-formulas of \(\varphi\).

With this layout, the truth table can easily be filled in from left to right, a process that we now illustrate using our Knight and Knaves puzzle.

Recall that our puzzle is represented by the following formula \(\varphi\):

\(A \leftrightarrow (-A\ |\ {-B})\)

In this case, \(\varphi\) contains \(n=2\) propositions, namely \(A\) and \(B\).

We start building our truth table for \(\varphi\) with the two leftmost columns corresponding to \(A\) and \(B\), respectively.

\(A\)	\(B\)
\(F\)	\(F\)
\(F\)	\(T\)
\(T\)	\(F\)
\(T\)	\(T\)

Note that \(n=2\) propositions give use \(2^n = 2^2 = 4\) rows, not counting the header row. 

It is common to order these rows in a systematic way. Here, I ordered them going downward by counting in binary from 0 up to 3 (i.e., 00, 01, 10, 11) while mentally mapping \(F\) to the digit 0 and \(T\) to the digit 1.

Then, since \(-A\) and \(-B\) are the next two smallest sub-formulas in \(\varphi\), we add a column for each one of these sub-formulas based on the truth table for negation:

\(A\)	\(B\)	\(-A\)	\(-B\)
\(F\)	\(F\)	\(T\)	\(T\)
\(F\)	\(T\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)

Next, since \(-A\ |\ {-B}\) is the next smallest sub-formula in \(\varphi\), we add a column for it based on the truth table for disjunction:

\(A\)	\(B\)	\(-A\)	\(-B\)	\(-A\ |\ {-B}\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)

Finally, the next smallest sub-formula is \(\varphi\) itself; so we add a final column for it based on the truth table for the biconditional connective:

\(A\)	\(B\)	\(-A\)	\(-B\)	\(-A\ |\ {-B}\)	\(A \leftrightarrow (-A\ |\ {-B})\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)

Looking at the rightmost column in this complete table, we observe that \(\varphi\) is only True in the third row:

\(A\)	\(B\)	\(-A\)	\(-B\)	\(-A\ |\ {-B}\)	\(\varphi\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)

This means that there is only one assignment of truth values to \(A\) and \(B\) that make \(\varphi\) True.

Since \(\varphi\) represents the statement of our puzzle, this means that there is only one solution to the puzzle, namely the one corresponding to the truth values of \(A\) and \(B\) in the third row.

\(A\)	\(B\)	\(-A\)	\(-B\)	\(-A\ |\ {-B}\)	\(\varphi\)
\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)

Not surprisingly, the solution yielded by the truth table approach is the same one yielded by all of our previous proofs:

A is Knight and B is a Knave.