Is there a general effective method to solve Smullyan style Knights and Knaves problems? Is the truth table method the most appropriate one?

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:

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:

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.

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.

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.