Lab 1 COMP 1002

Solving puzzles with truth tables

Review:

Materials

 

For this lab, you will be working in groups to solve the following puzzles. Try solving them using the techniques we studied such as translating from English to logic and using truth tables to find out the answer. You can all work together, or split who is doing which puzzle and then explain your solution to others, it is up to you (though note that the first puzzle is the shortest, and the last is the longest). But make sure that at the end of the lab everybody understands solutions to all puzzles: if it is just you who can solve the puzzles out of your group, that does not achieve the goal of the lab.

For each of the puzzles, follow these steps to solve it (see lecture 1.10 for an example):

  1. Define propositional variables you will use in your solution.
  2. Using these variables, translate the problem into formulas. Which formula should be true in the scenario(s) that will tell you the answer?
  3. Fill in a truth table, and state which line(s) of the truth table give(s) you the answer.
  4. Finally, get your answer to the puzzle from the truth table.
    That is, in the first puzzle determine if Al is a knight and if Bertha is a knight, in the second say which envelope has the money, and in the last say which witnesses are telling the truth, which are lying, and for which it is impossible to tell from this information.

Puzzle 1: Knights and Knaves again

On the island of knights and knaves, knights always tell the truth, and knaves always lie (that is, every sentence uttered by a knight is true, and every sentence uttered by a knave is false).

Suppose you met two inhabitants of the island of knights and knaves, Al and Berta. Al says "Both of us are knights", then Bertha says "Al is a knave". Now, you want to determine who is a knight and who is a knave (they can also be both knights or both knaves).

Puzzle 2: Game show

Imagine that you are a contestant in a game show. The show host puts three identically-looking envelopes in front of you, with a note written on each one. By the rules of the game, one envelope contains money, and the other two are empty, and to win you need to select the envelope with the money.

Suppose that envelope 1 and envelope 2 have "This envelope is empty" written on them, and the envelope 3 says "the money is in the envelope 2". The show host tells you that exactly one of these notes is true, and the other two are false.

Which envelope should you choose to claim the money?

Puzzle 3 (bonus): Detective story

A strange crime happened in an old haunted mansion. The detective interviewed four witnesses (a butler, a cook, a gardener and a handyman), and determined that if the butler were telling the truth then so did the cook, the cook and the gardener cannot both be telling the truth, the gardener and the handyman are not both lying, and if the handyman is telling the truth then the cook was lying.

Now, you need to find out which witness(es), if any, were telling the truth, which (if any) were lying, and for which (if any) it cannot be determined given just this information.