# 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. Apr 3, 2014 at 17:02
• @BrianRushton I edited the post.
– user230
Apr 3, 2014 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 Apr 3, 2014 at 18:57
• @brendansullivan07 Thanks for the link.
– user230
Apr 3, 2014 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 . May 6, 2014 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$.