Recent Articles

Logic puzzle

A logic puzzle is a puzzle deriving from the mathematics field of deduction.

This branch was pioneered by Charles Lutwidge Dodgson, who is better known under his pseudonym Lewis Carroll, the author of Alice's Adventures in Wonderland. In his book The Game of Symbolic Logic he introduced a game to solve problems such as

• some games are fun
• every puzzle is a game

Are all puzzles fun? Not Necessarily

Of course, this example is trivial. Dodgson goes on to construct much more complex puzzles consisting of up to 8 thesis.

In the second half of the 20th century mathematician Raymond M. Smullyan has continued and expanded the branch of logic puzzles with books as "the Lady and the Tiger", "To mock a mocking bird" and "Alice in puzzle-land".

Here is perhaps the most famous of this type of puzzle:

Two men stand at a fork in the road. One fork leads to Someplaceorother; the other fork leads to Nowheresville. One of these people always answers the truth to any yes/no question which is asked of him. The other always lies when asked any yes/no question. By asking one yes/no question, can you determine the road to Someplaceorother?

The fact that there are two men is a red herring - you only need one of them. Ask either of them the question:

"If I ask you if the left fork leads to Someplaceorother, will you answer 'yes'?"

If the person asked is a truthteller, he will answer "yes" if the left fork leads to Someplaceorother, and "no" otherwise. But so will the liar. So, either way, go left if the answer is "yes", and right otherwise.

Another form of logic puzzle, popular among puzzle enthusiasts and available in large magazines dedicated to the subject, is a format in which the set-up to a scenario is given, as well as the object (for example, determine who brought what dog to a dog show, and what breed each dog was), certain clues are given ("neither Misty nor Rex is the German shepherd"), and then the reader fills out a matrix with the clues and attempts to deduce the solution.

boolean algebra and logic truth tables. Familiarity with boolean algebra and its simplification process is a prerequisite to understand the following examples.

On the Keikei Island, there lived two kinds of people -- knights and knaves. The knights always tell the truth, but the knaves always tell a lie.

John and Bill are residents of the Keikei Island.

Question 1

John says: We are both knaves.

Who is who?

Question 2

John: If Bill is a knave then I'm a knight.

Bill: We are different.

Who is who?

Question 3

Logician: Are you both knights? John: Yes or No. Logician: Are you both knaves? John: Yes or No.

Who is who?

Solution to Question 1

We can use Boolean algebra to deduce who's who as follows:

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

<math>

(J \ \wedge (J' \wedge B')) \vee (J' \wedge (J' \wedge B')') = \mbox{tautology} <math>

Simplification process:

<math>

(J \ \wedge (J' \wedge B')) \vee (J' \wedge (J' \wedge B')') <math>

<math>

false \vee (J' \wedge (J' \wedge B')'); \qquad J \wedge J' = \mbox{contradiction} <math>

<math>

(J' \wedge (J' \wedge B')');\qquad \mbox{contradiction}\vee X = X <math>

<math>(J' \wedge (J \vee B));\qquad<math> by de Morgan's theorem.

<math> ((J' \wedge J) \vee (J'\wedge B)) <math>

<math>

(J'\wedge B) = \mbox{tautology} <math>

Therefore John is a knave and Bill is a knight. Although most people can solve this puzzle without using Boolean algebra, the example still serves as a powerful testament of the power of Boolean algebra in solving logic puzzles.

Another Example

Here is another famous logic puzzle, generally attributed to Albert Einstein.

There are 4 facts:

1. There are 5 houses in 5 different colours.

2. In each house lives a person with a different nationality.

3. These 5 owners drink a certain beverage, smoke a certain brand of cigarette and keep a certain pet.

4. No owners have the same pet, brand of cigaratte, or drink.

And 15 clues:

1. The Brit lives in a red house

2. The Swede keeps a dog

3. The Dane drinks tea

4. The green house is on the left of the white house.

5. The green house owner drinks coffee.

6. The person who smokes Pall Mall keeps birds.

7. The owner of the yellow house smokes Dunhill.

8. The man living in the house right in the center drinks milk

9. The Norwegian lives in the first house.

10. The man who smokes Blend lives next to the one who keeps cats

11. The man who keeps horses lives next to the man who smokes Dunhill

12. The owner who smokes Camel drinks beer

13. The German smokes Marlborough.

14. The Norwegian lives next to the blue house

15. The man who smokes Blend has a neighbour who drinks water.

Using these, determine who keeps the fish.

Logic Puzzle Resources