There is an island of knights who always say the truth and of knaves who never do. There is a country of day-knights who speak truthfully only at daytime and of night-knights whose speech at the day is a lie. There is an island of Democrats and Republicans. And they all came into being only to let use solve riddles.
But solving riddles is not the only thing one can do on this strange archipelago. One can also search for the general laws that govern the life on the islands. I will now use propositional logic for both: solving riddles in a systematical way and finding some of the general laws. Both activities are aspects of the same question.
There are many variants of these riddles. In their simplest form, we read a dialogue between persons who could be knights or knaves, without knowing who is which, and we must find out who has said the truth or at least which of their statements are true. Sometimes only partial solutions are possible.
Then there are the day-knights and night-knights that Raymond Smullyan describes in his book “To Mock a Mockingbird”. Day-knights speak the truth at daytime and lie when you meet them at night, while the night-knights do the opposite. As Smullyan tells us, these knights live in a subterranean place where you cannot see the sun and clocks are forbidden – only they know how late it is. He does not tell us where their country is located, but I am certain it is on an island.
A newer variant is Ben Orlin’s “Island of Democrats and Republicans” where the inhabitants tell the truth to members of their own party and lie to their opponents. As usual in such riddles, everyone belongs to one of the two parties.
In a simple knights-and-knaves riddle, a person could say, “Among me and my wife, one is a knight and one is a knave”, and the wife add, “He is the knight”. Since each of them could be a knave, we can take none of their statements at face value.
To translate this into logic, we introduce variables for the unknown facts. Since the unknown facts are here whether husband and wife are knights, we introduce the variables and to express that. This are logical variables and can take only the values and . The in stands for truth-sayer.
I use and not something like for the fact that person is a knight because otherwise we might also think that means that is a knave. In fact, “ is a knave” is translated to and literally means that is not a knight: The symbol stands for negation.
Returning to the riddle, we can now translate the “dialog” between husband and wife into formulas as The husband’s statement uses the symbol for logical equivalence. So the statement is true if and only if either the two terms at its side are both true or both false, and this happens only if one of the two persons is a knight and the other one a knave.
There is some variation in the symbols that are used in propositional logic. I will use here for “and”, for “or” and for the logical implication. For more information see the list of logical connectives in Wikipedia.
On the island of knights and knaves, a statement is true exactly then when the person that makes it is a knight. This can be translated to the rule (from Raymond Smullyan’s book “Forever Undecided”, Chapter 7): When person makes a statement , its meaning is .
There are similar rules for the other islands:
On the island of of day-knights and night-knights, a person says the truth if they are either a day-knight and it is day, or not a day-knight and it is not day. We can therefore define the variables for “ is a day-knight” and for “it is now day” and have the rule, When person makes a statement , its meaning is .
On the island of Democrats and Republicans, the variable takes the meaning, “Person is a Democrat”, and the translation of a statement depends on the person to which it is directed: When person makes a statement to person , its meaning is .
All these rules have the same structure. A statement is translated to a formula , where is the local truth condition for that island. On the island of knights and knaves, the truth condition is , on the island of day-knights and night-knights it is , and so on.
This will be useful when we speak about observations that are true on all islands; I can describe them in the form that is true on the island of knights and knaves and you can then translate them for other islands by replacing the term at the right with the local truth conditions of these islands.
Let us return to the husband-and-wife riddle.
We can now translate the statements of the husband and the wife, and their meanings are and , respectively.
To find a solution, we need to know that logical equivalence is associative: is equivalent to .
Because of this, the statement of the husband is equivalent to which is equivalent to and then to . So the wife is a knave and therefore, because of the wife’s translated statement , the husband is a knave too and the riddle is solved.
Before we proceed further, a remark about notation is in order.
There is a convention in mathematics that relational operators like or can be chained: We can for example write , and it must be understood as .
Chained operators are good for long computations, and I want to use them for example instead of “is equivalent to” in the computation of the last section. But I will also need the unchained version of these operators.
Therefore I introduce the following convention: The operators , and are the chained versions of , and . All other logical operators are not chained. The chained operators have also lower precedence, so that for example means .
With this convention, the computation of the previous paragraph becomes
The proof of the associativity of is still missing. One could do that by comparing the values of and for all values of , and , but that is boring. A more insightful way to do it is to note that both terms, and , changes their truth value when one of the variables changes its value. So if the terms have same truth value for one setting of , and , they will agree for all settings of these variables. We can therefore set all variables to , see that is the same as , and conclude that the terms and also agree for all other settings of , and .
Associativity of also means that we can now remove the braces from terms that consist of a longer sequence of symbols. I will however leave them in the formulas when it makes the meaning clearer.
The associativity of the operator leads to an interesting “inversion” phenomenon. On the island of day-knights, when a person says, “I am a day-knight”, it means that it is now day, and when they say, “It is now day”, it means that they are a day-knight.
This is because if person says, “I am a day-knight”, it means while “It is now day” means
In the same way we can show that on the island of Democrats and Republicans, when says to , “I am a Democrat”, it means, “You are a Democrat”, and vice versa. And similar phenomena occur when speaking about night-knights and Republicans.
In the last calculations, I have used a theorem that is worth spelling out explicitly: If a chain of logical equivalences contains the same term twice, then both occurrences can be removed and the value of the chain stays the same.
This theorem, which I will call the “pair rule”, follows from the associativity and commutativity of the operator: An expression like can be brought into the form in which some of the braces are restored for clarity. The term is always true, and is equivalent to for any term between the braces, therefore the whole formula is equivalent to The terms , and can also be themselves longer chains of equivalences.
Longer chains of equivalences especially arise when the inhabitants of the islands ask each other questions. Person may ask person whether a statement is true, and will answer with “Yes” or “No”. If they answer with “Yes”, they actually make the statement , and if they answer with “No”, they state . But may be a liar, at least in this situation, and so we must transform the answer in the usual way:
On the island of knights and knaves, if asks “?” and answers “yes”, this means ; an answer “No” means . On other islands, must be replaced with the local truth condition.
Sometimes we need to make ’s answer a variable that is true when says “yes” and otherwise is false.
Then we can say: If asks “?” and answers with , this means on the island of knights and knaves. On other islands, must be replaced with the local truth condition, which might make the formula a bit complex: With Democrats and Republicans, the interpretation of ’s answer is , which is already a longish chain.
So far we have only listened to questions – but how do we ask them? Smullyan has a simple rule for asking the the right question even if you do not know whether the person you ask says the truth: If you want to know whether a statement is true, ask, “Are you one of the people who can say that is true?”
He calls this rule Nelson Goodman’s principle, after the philosopher Nelson Goodman, who is best known for his “bleen-grue” paradox.
Let us now unpack Nelson Goodman’s principle. It relies on the fact that the people on the islands always follow their rules. They may lie under certain conditions, but under these conditions they always lie. On the island of knights and knaves, an inhabitant can say a true statement if and only if they are a knight, that is, if is true. In other words, the people who can say that is true are exactly those for which the meaning of the statement when they say it, in our case , is true.
Now it is clear what happens: In order to know whether is true, we ask “” from person , and replies with the statement . This answer then has the meaning which by associativity and the pair rule is equivalent to We have our answer!
Nelson Goodman’s principle is especially useful when we can simplify Goodman’s convoluted phrase. As an example, assume that on the island of Democrats and Republicans, wants to ask whether is in the same party as a third person, . Goodman’s question is then, “Are you one of the people who can say to me that is in the same party as you?”, or Simplified with the pair rule, this becomes and only needs to ask, “Is a member of my party?” to get the answer they want.
There are more logical connectives than just equivalence, and we must be able to handle them too. Unfortunately, the equivalence operator does not cooperate well with the other logical operator: There is for example no analogue to the distributive law for formulas with and .
There is however a general transformation that is often useful. With it, we can (almost) eliminate a specific variable from a given formula. To demonstrate it, let be a logical formula that depends on and possibly other variables. Then is equivalent to the expression This is simply a proof by cases: For to be true, must be true if is false and must be true if is true.
This formula can be brought into a shorter form. We must only notice that its left term is equivalent to : Then we can use the chained form of the operator and the formula becomes I call this the case expansion of . It is especially useful when the variable occurs multiple times in because then and could become much smaller expressions.
To actually apply this rule, we will also need something that is usually not given when a logical system is described, namely a list of simplification rules for terms where one operand of a logical connective is the constant or
With the case expansion we can especially get an interesting formula for a logical equivalence in which one side consists of a single variable: is then an expression of the form , with an arbitrary formula. The case expansion of this is and with help of the table it can be simplified to
As an illustration for this method, let us use it for the solution of another husband-and-wife riddle by Smullyan (“Forever Undecided”, Chapter 3 No. 3). In it, a man says, “If I am a knight, my wife is one too”. What can be made out of such a statement?
Well, its meaning is since it was made by the husband. The term is then , and so we have the expansion Now the term at the left is always true, while that at the right is equivalent to , so that the expansion is equivalent to And evaluating it from left to right, we see that husband and wife both must be knights.