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.
Puzzles like this, where we are given a list of premises and asked what can be deduced from them, are known as "syllogisms". Of course, this example is trivial. Dodgson goes on to construct much more complex puzzles consisting of up to 8 premises.
In the second half of the 20th century mathematician Raymond M. Smullyan has continued and expanded the branch of logic puzzles with books such as The Lady and the Tiger, To Mock a Mockingbird 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 (because if he had just been asked whether the left fork led to Someplaceorother, he would have lied about it, but when asked the hypothetical question above, he will lie about his lie and pretend that he would have answered truthfully).
- So, either way, go left if the answer is "yes", and right otherwise.
- An alternative approach is to ask "What would the other man say if I asked him whether the left fork led to Someplaceorother?" then go right if the answer is "yes" and left 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.
| Contents |
An Example
A large class of elementary logical puzzles can be solved using the laws of boolean algebra and logic truth tables. Familiarity with boolean algebra and its simplification process is a prerequisite to understand the following examples. In particular, to solve Question 2 you must understand that the only way that an "if X then Y" statement can be false is for X to be true and Y to be false.
On the Keikei Island, there live 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 is this famous logic puzzle.
See also
- Category:Logic puzzles – list of different logic puzzles.
- list of computer puzzle games
Logic Puzzle Resources
- perplexus.info (http://perplexus.info/category/2/)
- Puzzlers Paradise (http://www.puzzlersparadise.com/page1034.html)
- Puzzles, Brain Teasers, Logic Problems (http://www.edcollins.com/logic)