[Part 15] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles Seventh example

In this post, we will solve our last example in this series. In this seventh Knights and Knaves puzzle, we must determine if the answers to two questions posed to two inhabitants are the same.

For our seventh example, we will use the twelfth puzzle in Chapter 3 (or the \(37^{th}\) puzzle overall) of Raymond Smullyan's 1978 book entitled "What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles". As stated on page 23 of the 2011, paperback Dover Recreational Math edition [ISBN: 9780486481982], the puzzle reads:

Suppose you visit the island of knights and knaves. You come across two of its inhabitants lazily lying in the sun. You ask one of them whether the other one is a knight, and you get a (yes-or-no) answer. Then you ask the second one whether the first one is a knight. You get a (yes-or-no) answer.

Are the two answers necessarily the same?

The informal answer given by Smullyan in the book (on page 32) is again a proof by cases.

However, this is an example where the formal approach is much quicker!

Recall that the first step in a formal approach is to couch the puzzle statement in a formal language. Propositional logic is the language we have been using in this series.

As it turns out, once this puzzle is translated into propositional logic, the answer will be obvious. Therefore, there will be no need to use Mace4 nor Prover9. All of the work fun is in the representation step.

As we have done several times already, we will call the two inhabitants A and B. Then, the question posed to A becomes:

\(A \leftrightarrow B\) ?

Recall that the question mark is not part of the formula; it is added here to indicate that this is a question whose answer we do not know. If this translation is not obvious to you, refer back to this post for an explanation.

Similarly, the question posed to the other inhabitant becomes:

\(B \leftrightarrow A\) ?

Recall that the proposition on the left of the bi-conditional represents the person who gives the answer while the formula on the right is the question being asked.

Now, we are asked to determine whether the two answers are necessarily the same. 

The answer is clearly Yes, because the two logical formulas are equivalent. This is due to the fact that the bi-conditional connective is a commutative logical operator. 

In other words, for any formulas \(\varphi_1\) and \(\varphi_2\):

\(\varphi_1 \leftrightarrow \varphi_2\)

and 

\(\varphi_2 \leftrightarrow \varphi_1\)

always have the same value.

This is similar to the addition operator being commutative in the context of arithmetic. Whatever the integer or real values of \(x\) and \(y\):

\(x + y\)

and 

\(y + x\)

always have the same value, because \(+\) is a commutative operator.