# Boolean Logic

Boolean Logic is a form of algebra in which all values are reduced to either true or false. It was developed by the English mathematician George Boole in the mid-19th century. Its rules govern logical functions (true/false) and are the foundation of all electronic circuits in a computer. As add, subtract, multiply and divide are the primary operations of arithmetic, AND, OR and NOT are the primary operations of Boolean logic. Boolean logic is turned into logic gates on the chip, and the logic gates make up logic circuits that perform functions such as, how to add two numbers together.

However, we would be concerned here with the logical application of Boolean Logic in True/False situations only. Boolean Logic is, sometimes, also referred to as Binary Logic.

Let us see a Boolean Logic situation:

On a fictional island, all the inhabitants are either knights, who always tell the truth, or knaves, who always lie. The question set involves a stranger to the island who meets small groups of inhabitants there.

Usually the aim is for the visitor to conclude the inhabitants’ type from their statements but some questions of this type ask for other facts to be deduced. The question may also be to determine a Yes/No question which the visitor can ask in order to discover what he needs to know.

A primitive example of this type of question involves three inhabitants referred to as A, B and C. The visitor asks A what type he is, but does not hear A’s answer. B then says “A said that he is a knave” and C says “Do not believe B: he is lying!”

To solve the puzzle, understand that no inhabitant can say that he is a knave. Reason for this can be given as—If somebody is a knight, then he speaks the truth always and of course he cannot say that “I am a knave.” Similarly, if somebody is a knave, then he speaks false always. Now, if somebody speaks false only, he cannot say that he always speaks false as this amounts to contradiction.

Coming back to the original question, hence, B’s statement must be untrue, so he is a knave, and C’s statement must be true, so he is a knight. Since B is a knave, he will always lie. Therefore B was lying when he said that A had said he was a knave. Therefore A must have said that he was a Knight.

# Some More Examples of Knights and Knaves

A large number of elementary Boolean Logic questions can be solved by using the simple logic or elementary Boolean Algebra (or, logic truth tables). To increase our familiarity with Boolean Logic and its simplification process, let us see some more basic questions.

Example-1

Jain and Baid are residents of the island of knights and knaves.

Jain says: We are both knaves. Who is who?

Solution

This is what Jain is saying in a more extended form:

“Jain is a knave and Baid is a knave.”

If Jain was a knight, he would not be able to say that he was a knave since he would be lying. Therefore the statement “Jain is a knave” must be true.

Since knaves lie and one statement is true, hence, to make the statement given by Jain false, the other statement must be false. Therefore the statement “Baid is a knave” must be false which leads to the conclusion that Baid is a knight.

The solution is that Jain is a knave and Baid is a knight.

Alternatively, we can use Boolean algebra to find out who’s who as follows:

Let J be true if Jain is a knight and let B be true if Baid is a knight. Now, either Jain is a knight and what he said was true, or Jain is not a knight and what he said was false. Translating that into Boolean algebra, we get:

Jain is a knave and Baid is a knight. (Although we can do this question without using Boolean algebra very easily.)

“Jain is a knave and Baid is a knave.”

If Jain was a knight, he would not be able to say that he was a knave since he would be lying. Therefore the statement “Jain is a knave” must be true.

Since knaves lie and one statement is true, hence, to make the statement given by Jain false, the other statement must be false. Therefore the statement “Baid is a knave” must be false which leads to the conclusion that Baid is a knight.

The solution is that Jain is a knave and Baid is a knight.

Alternatively, we can use Boolean algebra to find out who’s who as follows:

Let J be true if Jain is a knight and let B be true if Baid is a knight. Now, either Jain is a knight and what he said was true, or Jain is not a knight and what he said was false. Translating that into Boolean algebra, we get:

Jain is a knave and Baid is a knight. (Although we can do this question without using Boolean algebra very easily.)

Example-2

Here is a rendition of perhaps the most famous of Boolean Logic questions:
A prince visits an island inhabited by Knights and Knaves. Knights always tell the truth and knaves always lie.
The prince comes to a fork in the road. He needs to know which road leads to the jungle so as to rescue the princess. (Although the prince does not know it, the south road leads to the jungle and the north road leads to the monster.)
Standing at this fork in the road are a knight and a knave, but the prince cannot tell who is who. What question should he ask to find the road to the jungle so that he can save the princess?

Solution

Simply asking which road leads to the jungle would not help. The answer would not tell us who is lying and who is telling the truth. However, we only need to talk to one of them. The trick is to ask a question where the response will be the same from both of them: a question that incorporates how a knight or a knave not answering would respond to the same question.

For example, what if we say to one of them, “If I asked a member of the type you do not belong to, which road I should take to get to the jungle, what would he say?”

For example, what if we say to one of them, “If I asked a member of the type you do not belong to, which road I should take to get to the jungle, what would he say?”

- If we ask a truth-teller, the response will be: “He would say to take the north road.” The road to the castle is the south road so the liar will tell us to take the north road, and the truth teller will faithfully report this to us.
- If we ask a liar, the response will be: “He would say to take the north road.” The road to the jungle is the south road and the truth teller will tell us to take the south road, but the liar will not report this faithfully to us—he will say the opposite.

In both cases we will get the same response. We should do the opposite of what we have been told because, regardless of whether we are speaking to a liar or a truth teller, our question will always produce the wrong answer regarding the road that we should take.

# Variations in Knights and Knaves Problems

In some variants, inhabitants may also be alternators, who alternate between lying and telling the truth; or normals, who can say whatever they want (as we can see in the case of Knight/Knave/Spy puzzles). A further complication can be added by bringing in the situation where the inhabitants may answer yes/no questions in their own language; and the visitor knows that “bal” and “da” mean “yes” and “no” but does not know which is which. Therefore, this question will now lead to two Y-junctions.

Knights always tell the truth.

Knaves always lie.

Spies can either lie or tell the truth.
Normally, we encounter a group of three people, A, B and C and one of them is a Knight, one of them is a Knave and the one left is a spy, but we do not know who is who. However, they all know the identity of each other.

Example-1

A says: I am a knight.
B says: That is true.
C says: I am the spy.

Solution

We can understand that neither B nor C can be the knight.
(B is saying that somebdoy else is a knight and C says that he is a spy). Hence, A is a knight. What B is saying is true so he cannot be the knave. Hence, he is the spy. So, C is the knave.

Example-2

A says: B is the spy.

B says: No, C is the spy.

C says: No, B is definitely the spy.

B says: No, C is the spy.

C says: No, B is definitely the spy.

Solution

B cannot be the spy, as in that case both a knave and a knight would be accusing him of being the spy. And if B is not the spy, then in that case neither A nor C can be the knights since they would not be telling the truth. Hence, B is a knight, as a result A and C are knave and spy respectively.

There can be only six possibilitites of Knights, knaves and its spy that we can have for any particular set:

There can be only six possibilitites of Knights, knaves and its spy that we can have for any particular set:

- Knight Knave Spy
- Knight Spy Knave
- Knave Spy Knight
- Spy Knight Knave
- Knave Knight Spy
- Spy Knave Knight

Any statement made by a person in a question can be classified into various possibilites. For example—the statement that ‘I am a knave’ cannot be made by a knight, a knave. Hence, anybody making this statement has to be a spy. Similarly, the statement ‘I am a spy’ cannot be made by a knight. Hence, anybody making this statement has to be either a knave or a spy.

However, there can be some useless statements too like ‘I am a knight’. It can be seen that this statement can be made by anybody–a knight or a knave or a spy.

However, there can be some useless statements too like ‘I am a knight’. It can be seen that this statement can be made by anybody–a knight or a knave or a spy.