8
$\begingroup$

Below, an attempt at solving a knight/knave puzzle using the truth table method.

Are there other methods?

Source : https://en.wikipedia.org/wiki/Knights_and_Knaves

enter image description here

$\endgroup$
  • 3
    $\begingroup$ If you rearranged the truth table with the third column first with four T and four F cases you would see clearly that you do not need that column - it's a hypothesis, so true by assumption. That would avoid the repeated reason. You could then reason about other columns in turn - but that would be recreating the truth table as a sequence of implications. Does that count as a differrent method? $\endgroup$ – Ethan Bolker May 26 at 12:49
9
$\begingroup$

Truth-tables are certainly a very solid method for Knights and Knaves puzzles: they are systematic and easy.

However, instead of your truth-table, may I suggest:

First, let's use $J$ for "John is a knight"

and $B$ for "Bill is a knight

Then, there are 4 options .. as reflected by 4 rows in the truth-table, rather than your 8. Indeed, as Ethan Bolker explains in the comment, John's claim that "we are both knaves" is really derivative on the claims of $J$ and $B$ ... namely it is just $\neg J \land \neg B$:

\begin{array}{cc|c} J&B&\neg J \land \neg B\\ \hline T&T&F\\ T&F&F\\ F&T&F\\ F&F&T\\ \end{array}

Finally, John must speaking the truth if and only if he is a knight, i.e. the truth-values of column for $J$ and $\neg J \land \neg B$ should match. This rules out rows 1,2, and 4, and leaves us with row 3: John is a knave, and Bill is a knight.

However, there are many other logic methods you can be used.

Note that John is speaking the truth if and only if he is a knight, and so we have:

$J \leftrightarrow (\neg J \land \neg B)$

OK, first let's use Boolean Algebra to simplify:

$J \leftrightarrow (\neg J \land \neg B) \Leftrightarrow$

$(J \land (\neg J \land \neg B)) \lor (\neg J \land \neg (\neg J \land \neg B)) \Leftrightarrow$

$(J \land \neg J \land \neg B) \lor (\neg J \land (\neg \neg J \lor \neg \neg B)) \Leftrightarrow$

$(\bot \land \neg B) \lor (\neg J \land (J \lor B)) \Leftrightarrow$

$\bot \lor ((\neg J \land J) \lor (\neg J \land B)) \Leftrightarrow$

$\bot \lor (\neg J \land B) \Leftrightarrow$

$\neg J \land B$

Cool: John is a knave and Bill is a knight

Now, this particular algebraic derivation was actually somewhat complicated, but from experience I can tell you that algebra often works like a charm for these Knights and Knaves puzzles. For example, let's take a random Knights and Knaves puzzle from an only website containing 382 Knights and Knaves puzzles. OK ...generating a random number between 1 and 382 ... 78! OK, problem 78 reads:

You meet three inhabitants: Homer, Dave and Bill. Homer tells you that neither Dave nor Bill are knights. Dave tells you that Homer and Bill are both knights. Bill says that Homer is a knight or Dave is a knave.

OK, let's symbolize:

$H \leftrightarrow \neg(D \lor B)$

$D \leftrightarrow (H \land B)$

$B \leftrightarrow (H \lor \neg D)$

OK, biconditionals can be used as kinds of substitutions. That is, given $B \leftrightarrow (H \lor \neg D)$, we can substitute $H \lor \neg D$ for $B$. Let's do this for $D \leftrightarrow (H \land B)$, so we get:

$D \leftrightarrow (H \land (H \lor \neg D))$

which by Absorption simplifies to:

$D \leftrightarrow H$

Aha, so we can substitute $D$ and $H$ for each other as well. In particular, let's do this for $B \leftrightarrow (H \lor \neg D)$, so we get:

$B \leftrightarrow (H \lor \neg H)$

which by Complement becomes:

$B \leftrightarrow \top$

This not only tells you that $$ is a knight .. but we can now also use this as a substitution for the first premise:

$H \leftrightarrow \neg(D \lor \top)$

which simplifies to:

$H \leftrightarrow \neg \top$

and thus:

$H \leftrightarrow \bot$

So now we know Homer is a knave ... and since we hd that $D \leftrightarrow H$, we therefore also have that $D$ is a knave.

Without all the comments, here is what we did:

\begin{array} 1. & H \leftrightarrow \neg(D \lor B) & Premise\\ 2. & D \leftrightarrow (H \land B) & Premise\\ 3. & B \leftrightarrow (H \lor \neg D) & Premise\\ 4. & D \leftrightarrow (H \land (H \lor \neg D)) & Biconditional \ Substitution 2,3\\ 5 & D \leftrightarrow H & Absorption \ 4\\ 6. & B \leftrightarrow (H \lor \neg H) & Biconditional \ Substitution 3,5\\ 7. & B \leftrightarrow \top & Complement \ 6\\ 8. & B & 7\\ 9. & H \leftrightarrow \neg(D \lor \top) & Biconditional \ Substitution 1,8\\ 10. & H \leftrightarrow \neg \top & Annihilation \ 9\\ 11. & H \leftrightarrow \bot & Inverse \ 10\\ 12. & \neg H & 11\\ 13. & \neg D & 5,12\\ \end{array}

Sweet!

OK, now let's do a formal proof .. which is going to formalize the following piece of reasoning: If John is a knight, then he is speaking the truth, and hence John and Bill must both ne knaves ... but that contradicts the assumption that John is a knight. Hence, John cannot be a knight, and therefore must be a knave. So, John is lying, and hence it cannot be true that John and Bill are both knaves. Since John is already known to be a knave, Bill must therefore be a knight.

OK, let's formalize this argument, and prove that John is knave and Bill is a knight using the premise that $J \leftrightarrow (\neg J \land \neg B)$:

\begin{array}{lll} 1&J \leftrightarrow (\neg J \land \neg B)&Given\\ 2&| \ J & Assumption\\ 3&| \neg J \land \neg B& \rightarrow \ Elim \ 1,2\\ 4&| \neg J & \land \ Elim \ 3\\ 5&| \bot & \bot \ Elim \ 2,4\\ 6&\neg J & \neg \ Intro \ 2-5\\ 7&| \neg B & Assumption\\ 8&|\neg J \land \neg B&\land \ Into \ 6,7\\ 9&|J&\rightarrow \ Elim \ 1,8\\ 10&|\bot&\bot \ Intro \ 6,9\\ 11&\neg \neg B& \neg \ Intro \ 7-10\\ 12&B&\neg \ Elim \ 11\\ 13&\neg J \land B& \land \ Intro \ 6,12\\ \end{array}

OK, two more methods, both of which are model-finding methods. First, the truth-tree method (also called the tableaux method), where you keep decomposing statements and see in what ways (if any) tyou can make them true:

enter image description here

And then we have Davis-Putnam, which is a little more like a truth-table, as you systematically explore what would happen to your statements as you set the variables True or False:

enter image description here

In both cases, the only open branches are the ones with $J$ being False and $B$ being true, so once again: John is a knave and Bill is a knight.

$\endgroup$
  • $\begingroup$ Bram28.Thanks a lot for the formal proof! $\endgroup$ – Eleonore Saint James May 26 at 13:11
  • 2
    $\begingroup$ @EleonoreSaintJames You're welcome! Love these puzzles! :) $\endgroup$ – Bram28 May 26 at 13:11
  • $\begingroup$ Upvoting this specifically for the tableau method, which is almost always simpler and quicker than a truth table for this sort of problem. $\endgroup$ – MJD Jun 2 at 20:27
8
$\begingroup$

Truth tables always work, of course, but another appproach is to use algebra in the field with two elements (i.e. the integers modulo 2) to represent truth values.

If we let $1$ represent a true statement and $0$ represent a false statement, then

  • "X and Y" corresponds to $xy$.
  • "not X" corresponds to $1-x$.
  • "X or Y" corresponds to $x+y-xy$.

and therefore we can represent any propositional formula by a polynomial expression. Finally, we can represent "A says (or would say) X" by the equation $$ (\text{A is a knave}) + x = 1 $$ since the if A says X then we know that either X is true or A is a knave but not both.

For the simple puzzle in question, then introduce variables $j$ and $b$ for "John is a knave" and "Bill is a knave". John's statement is then $jb$ and the known fact that he says it is the equation $$ j+jb = 1 $$ Algebra now tells us $$ j(1+b) = 1$$ and the only way for that to be true in $\mathbb F_2$ is if $j=1$ and $1+b=1$. In other words "John is a knave" must be true, and "Bill is a knave" must be false.

$\endgroup$
3
$\begingroup$

As others have noted, truth tables always work for "classify the participants based on their statements" puzzles; if you work through Smullyan's books of course not all puzzles are of this sort, even at the beginning. For example, there will puzzles like "so and so then answered my question and I knew blah; what question did I ask?" These questions requires a little more thinking, but often can be checked via truth tables once you have some ideas.

In this particular case you can arrive at the answer faster by observing this key fact:

No knight ever claims to be a knave.

"We are both knaves" is a claim to be a knave, and therefore we can immediately reject all the truth-table columns that suggest that John is a knight. By eliminating half the possibilities immediately, you can simplify this sort of problem.

$\endgroup$
  • $\begingroup$ @EricLipperet. Thanks for this remark: "no knight ever claims to be a knight". That helps! $\endgroup$ – Eleonore Saint James Jun 2 at 19:09
3
$\begingroup$

Often you can make an assumption and derive a contradiction. Here, assume John is a knight. He then tells the truth, but "we are both knaves" would be false. Therefore John is a knave. Now the statement "we are both knaves" must be false, and we know John is a knave, so Bill must be a knight.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.