Automating Logic: Solving the Knights and Knaves Problem

If you’ve studied discrete math, you may have come across the following knights and knaves problem:

Knights and Knaves is a type of logic puzzle invented by Raymond Smullyan where knights can only answer questions truthfully, and knaves only falsely. You come across two characters:

Alice says: Both of us are knights.

Bob says: Alice is a knave.

What are Alice and Bob?

I encountered this a few weeks into my Discrete Math class in a module about truth tables. This problem caught me by surprise because it initially seemed like a departure from the previous truth table-related problems. After thinking for a bit, I found that Alice must be a knave and Bob must be a knight. Alice must be a knave because if she were telling the truth (being a knight), Bob would also have to be a knight, contradicting Bob’s statement that Alice is a knave. Bob must be a knight because if he were a knave, his statement that Alice is a knave would be false; that would make Alice a knight, contradicting her claim.

I later learned that this problem is not a departure from the truth tables I saw previously. If we can find a way to mathematically search for logical inconsistencies, a truth table can be perfectly applied.

We can say “if the character is a knight, then their claim must be true; if the character is a knave, the claim must be false.” Mathematically, we can say:

a implies c and not a implies not c

Where a is the character (true if a knight, false if a knave), and c is the character’s claim.

The previous statement uses the x → y “implies” operator, reading as “if x, then y.” This operator produces a false output if and only if x is true and y is false, and a true output otherwise.

Since we know that Alice is claiming:

a equals true and b equals true

And Bob is claiming:

a equals false

We can construct the following truth table:

Truth table showing that the only possible state where a logical contradiction is not present is where Alice (represented by ‘a’) is a knave (represented by ‘false’) and Bob (represented by ‘b’) is a knight (represented by ‘true’)

We find that Alice must be a knave and Bob must be a knight, since that is the only row such that the values in the two rightmost columns are true.

Automation of This Problem

I have been programming for eight years across seven different languages, and enjoy coding as a hobby. After learning that this problem can be solved with a truth table, my first thought was “how can I automate this?” This one question led me on a 2-day rabbit hole.

The Goal

My Java program has two requirements:

1. The input should be each characters’ claim as a string.
2. The output should accurately state all knight/knave possibilities.

For example, in our previous problem, we could provide the input strings

a is claiming: (a = T) & (b = T)
b is claiming: (a = F)

And receive the output:

a is a knave, b is a knight

Converting Characters’ Claims to Mathematical Statements

Converting the characters’ claims to mathematical statements is the simplest step in this algorithm, only requiring basic string concatenation. In Java, the conversion can be done using the following code:

String statement = "(" + character + " > (" + claim + "))" + " & (!(" + character + ") > !(" + claim + "))";

where the character variable is the letter of the character making the claim (e.g., ‘a’ for Alice, ‘b’ for Bob), and the claim is the character’s claim. Note we use ‘>’ for the ‘implies’ operator and ‘&’ for the and operator, because those characters can be typed on a standard United States keyboard.

The Tokenizer

In most algorithms that evaluate strings, the first step is to tokenize the expression. This converts a series of characters, or groups of characters, into tokens, which can be more easily interpreted by our algorithm. This is one of the first steps of most compiled and interpreted programming languages.

Our interpreter can be simple, since we only have a few operations we need to perform. Our tokenizer can recognize 8 tokens:

• A variable (e.g., ‘a’ or ‘b’, or ‘T’ and ‘F’ for true and false)
• The equals operator
• The implies operator
• The not operator
• The and operator
• The or operator
• Open parenthesis
• Close parenthesis

The tokenizer outputs a list of tokens, in the order that they are in the original string.

Reverse Polish Notation

Now that we have our tokens, we need to reorder them into reverse polish notation (RPN). This notation is special because it allows us to parse any mathematical expression with a simple method, without needing to worry about operator precedence.

RPN converts the following expression:

a times b plus c

to

The RPN expression: “a b times c plus”

To convert to RPN, we use the shunting yard algorithm, created by Edsger Dijkstra. It cleverly utilizes a stack and queue to produce the final result.

Side note: the shunting yard algorithm can also create an abstract syntax tree (AST) for expressions, another important step in creating a programming language.

To provide a general overview, the shunting yard algorithm pushes all operators and open parenthesis tokens onto a stack, and all variable tokens into a queue. If a closing parenthesis token is detected, it removes all tokens from the stack and pushes the tokens to the output queue until the corresponding open parenthesis is found, then discards both parenthesis. If an operator of higher precedence is added to the stack, all operators are removed and inserted into the queue until an operator of equal or greater precedence is found. After this algorithm iterates through all tokens, the stack is emptied.

Evaluating RPN

Evaluating the RPN can be done using a simple algorithm utilizing a single stack. The algorithm iterates through the RPN and does the following:

• If the token is a variable, push the value of the variable onto the stack. If the variable’s value is ‘T’ or ‘F’, evaluate it as ‘true’ or ‘false’ respectively.
• If the token is the not operator, pop the last value of the stack, invert it, and push it back onto the stack.
• If the token is any other operator, pop the last two values of the stack, perform the token’s operation, and push the output back onto the stack. This should reduce the stack size by 1, since the operator requires 2 inputs and only provides 1 output.

Truth Table Evaluation

Finally, we can employ a truth table to find all correct answers to the riddle, similar to what we did manually beforehand. We can iterate through each permutation of knight/knave possibilities, and identify each combination that does not produce a logical fallacy (i.e., all output columns for the row are true).

Result

Here is the final output of the program:

Enter a claim for character a (or 'end' to finish): (a = T) & (b = T)
Enter a claim for character b (or 'end' to finish): a = F
Enter a claim for character c (or 'end' to finish): end
a is a Knave, b is a Knight, 

In this article, I implemented an algorithm to solve the Knights and Knaves problem by tokenizing and evaluating boolean expressions as well as truth tables. This was an interesting challenge because it gave me a deeper understanding of foundational discrete math concepts. It also allowed me learn about tokenization, reverse polish notation (RPN), and the shunting yard algorithm. One project that’s been on my bucket-list for a while is to make a simple programming language, and the tokenization and shunting yard algorithms learned in this project will be valuable as I work towards that goal.

All code is open-source and available on GitHub: https://github.com/AlexanderJCS/knave-engine.git