Friday, April 14, 2006

March 2006: A Lewis Carroll puzzle

In addition to being the author of classic children's books such as Alice in Wonderland, Lewis Carroll was an accomplished logician. Below is one of Lewis Carroll's famous logic puzzles. Use all ten statements of the riddle to draw the logical conclusion.

The only animals in this house are cats.
Every animal is suitable for a pet, that loves to gaze at the moon.
When I detest an animal, I avoid it.
No animals are carnivorous, unless they prowl at night.
No cat fails to kill mice.
No animals ever take to me, except what are in this house.
Kangaroos are not suitable for pets.
None but carnivora kill mice.
I detest animals that do not take to me.
Animals, that prowl at night, always love to gaze at the moon.

Hint: turn this into a puzzle of symbolic logic. For example, here is how you could solve another of Carroll's puzzles:

Things sold in the street are of no great value.
Nothing but rubbish can be had for a song.
Eggs of the Great Auk are very valuable.
It is only what is sold in the street that is really rubbish.

S: it is sold in the streets
V: it is valuable
R: it is rubbish
I: it is inexpensive
E: it is the egg of the Great Auk

Symbolically the puzzle becomes:

S --> ~V (or, using the contrapositive, V --> ~S)
I --> R (or ~R --> ~I)
E --> V (or ~V --> ~E)
R -->S (~S --> ~R)

Stringing these together we obtain: I --> R --> S --> ~V --> ~E

Thus the conclusion is I --> ~E or E --> ~I which can be written as:
If it is inexpensive then it is not the egg of a Great Auk.
If it is the egg of the Great Auk then it is not inexpensive.
Nothing inexpensive can be the egg of the Great Auk.
No egg of the Great Auk is inexpensive.
An egg of the Great Auk cannot be had for a song.