The Boolean Enlightenment Problem

Boolean Enlightenment Guard

The path to enlightenment lies behind one of two doors. In front of each door stands a guard who knows which door leads to enlightenment, but one of the guards always lies and the other one always tells the truth. In your search for enlightenment, you are allowed to ask one guard only one question that can be answered "yes" or "no", but unfortunately, you do not know which guard is the liar. You will be banished to the dungeon of logical illiteracy if you fail in your quest. What question should you ask to find the path to enlightenment?

Answer:

If you ask a guard directly "Are you guarding the path to enlightenment?", and the answer is "no", he could be guarding the path to enlightenment and be lying about it, or he could be telling the truth and the path to enlightenment is behind the other door.

The question that you ask has to involve both guards at the same time:

"Would the other guard say that you are guarding the path to enlightenment?"

When we ask a guard this question, there are 4 cases:

The liar is guarding the path to enlightenment. He answers "no" because the truthful guard would say "yes".
The liar is not guarding the path to enlightenment: He answers "yes" because the truthful guard would say "no".
The truth teller is guarding the path to enlightenment. He answers "no" because the other guard (liar) would say "no".
The truth teller is not guarding the path to enlightenment. He answers "yes" because the other guard (liar) would say "yes".

So, if a guard answers "no", he is guarding the path to enlightenment. If he answers "yes", the path to enlightenment is the other door. Notice that even though we have learned which is the path to enlightenment, we still don't know which guard is the liar. To find out who is the liar we would have to ask a question like: "Would the other guard say that you always tell the truth?" A reply of "no" means you are talking to the truth teller, a reply of "yes" means you are talking to the liar.

George Boole (1815-1864) was an English mathematician and logician who devised a system for representing logical symbolic relationships now known as Boolean algebra. The logical relationships, called Boolean expressions, use the logical operators AND, OR, and NOT between entities. These expressions have application in computer circuit design, information retrieval strategies, and logic problems such as this. Tables that list all the outcomes of a logical expression, like our four cases above, are known as "Truth Tables".