# Puzzles for Logic Courses featuring propositional logic and set theory?

Puzzles are interesting form of exercises. They help students to learn the teaching material in a funny way. Particularly in logic, puzzles could be very useful to show the complexity of the subject.

Question: What are good examples of logic puzzles for undergraduate logic courses, focused on propositional logic and set theory?

• I feel that this is too broad. It is asking for any example at all of logical puzzles, which is a very large field. It's like asking for a good example of optimization. Perhaps you should choose one element from each of your parenthesis (e.g. propositional logic in set theory at the high-school level) to make it more focused. – Brian Rushton Apr 3 '14 at 17:02
• @BrianRushton I edited the post. – user230 Apr 3 '14 at 17:10
• Check out Jason Rosenhouse's "problem of the week page". They are all logic puzzles: educ.jmu.edu/~rosenhjd/POTW/Spring14/homepage.html – Brendan W. Sullivan Apr 3 '14 at 18:57
• @brendansullivan07 Thanks for the link. – user230 Apr 3 '14 at 22:52
• Disclaimer: I know it only from reviews, but the Ergo card game might be of use. See e.g. boardgamegeek.com/boardgame/55279/ergo . – mbork May 6 '14 at 10:05

For propositional logic (especially truth tables and implication) I suggest Raymond's Smullyan's wonderful book, What is the name of this book?.

From memory: one example has a prosecutor in a court say to the defendant: 'If you committed the crime, then you must have had an accomplice'. The defendant hotly denies this. But $A \implies B$ is false only if $A$ is true, and $B$ is false, so his denial is also an admission of guilt.

Pirates (disjunctive/conjunctive normal form). Another puzzle I like has five pirates, who want to padlock their treasure chest so that it can be opened if and only if (at least) four of them are present. How many padlocks are needed?

Writing $p_i$ for the proposition 'Pirate $i$ is present', the condition is

$$(p_1 \wedge p_2 \wedge p_3 \wedge p_4) \vee (p_1 \wedge p_2 \wedge p_3 \wedge p_5) \vee \cdots \vee (p_2 \wedge p_3 \wedge p_4 \wedge p_5).$$

This holds if and only if no two pirates who are absent, so a logically equivalent condition is

$$(p_1 \vee p_2) \wedge (p_1 \vee p_3) \wedge \cdots \wedge (p_4 \vee p_5)$$

in conjunctive normal form. The corresponding (minimal) solution puts 10 padlocks on the chest, labelled by the $2$-subsets of $\{1,2,\ldots, 5\}$, and gives the keys to the padlock labelled $\{r,s\}$ to pirates $r$ and $s$.

• (+1) Nice answer. Thanks. – user230 Apr 6 '14 at 11:16

One puzzle I rather like comes from a website (forget where) that gives a problem about four cards. Each card contains a letter on one side, and a number on another. Also, each card ostensibly has the property that if one side contains a vowel, then the other side contains an even number. Then, you're given four cards, with the following faces showing:

• 7
• 2
• E
• S

and asked which cards would you need to turn over to be sure that that card followed the bolded property. It turns out that you need to flip 7 and E (because those are the only ones that could possibly have a vowel on one side and an odd number on another side), but most people who don't know this beforehand would get something else.