COMP 1002 Unit 1 Practice problem set

Problem 1: Knights and Knaves puzzle

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).

Solve this puzzle by using truth tables. Refer to the lecture 1.6 (on truth tables) for a similar solved problem.

  1. Define propositional variables you will use in your solution.
    Answer

    Let $A$ be true iff Al is a knight, and let $B$ be true iff Bertha is a knight.

  2. Using these variables, translate the problem into formulas. Which formula should be true in the scenario(s) that will tell you the answer?
    Answer

    Al said $A \wedge B$. Bertha said $\neg A$. By the rules of knights and knaves puzzles, what Al said is true iff Al is a knight $A \leftrightarrow (A \wedge B)$ and what Bertha said is true iff she is a knight $B \leftrightarrow \neg A$. So the formula that would be true exactly in scenarios that satisfy the rules of the puzzle is $(A \leftrightarrow (A \wedge B)) \wedge (B \leftrightarrow \neg A)$.

  3. Fill in a truth table, and state which line(s) of the truth table give(s) you the answer.
    Answer
    $A$ $B$ $A \wedge B $ $A \leftrightarrow (A \wedge B)$ $\neg A$ $ B \leftrightarrow \neg A $ $ A \leftrightarrow (A \wedge B)) \wedge (B \leftrightarrow \neg A) $
    T TTTFFF
    T FFFFTF
    F TFTTTT
    F FFTTFF
    The only scenario where what Al and Bertha say obey the rules of the puzzle is the third one, $A = false, B=true$. So Al must be a knave, and Bertha a knight.

  4. Finally, state your answer: is Al a knight or a knave? Is Bertha a knight or a knave?
    Answer

    Al is a knave, Bertha is a knight.

Problem 2: Detective story puzzle

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 gardiner cannot both be telling the truth, the gardiner and the handyman are not both lying and if the handyman is telling the truth then the cook was lying.

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. Here you can use a similar approach to the knights and knaves puzzle, and solve the problem using a truth table.

  1. Define propositional variables you will use in your solution.
    Answer

    Let $p$ be true iff the butler is telling the truth,
    $q$ true iff the cook is telling the truth,
    $r$ true iff the gardiner is telling the truth
    $s$ true iff the handyman is telling the truth.

    (This choice of variable names is fairly arbitrary: calling them B, C, G and H is another possibility. As long as you have a variable for each witness with the value corresponding to whether that witness tells the truth, it should be fine).

  2. Using these variables, translate the problem into formulas. Which formula should be true in the scenario(s) that will tell you the answer?
    Answer

    The four statements that the detective decided are true are:

    1. If the butler is telling the truth then so is the cook: $p \to q$.
    2. The cook and the gardener cannot be both be telling the truth: $\neg (q \wedge r)$
    3. The gardiner and the handyman are not both lying: $\neg (\neg r \wedge \neg s)$
    4. If the handyman is telling the truth, then the cook was lying: $s \to \neg q$.

    The formula that should be true in the scenarios satisfying the rules of the puzzle is the AND of those 4 statements: $(p \to q) \wedge \neg (q \wedge r) \wedge \neg (\neg r \wedge \neg s) \wedge (s \to \neg q)$.

  3. Fill in a truth table, and state which line(s) of the truth table give(s) you the answer.
    Answer
    For the sake of space, we will not show the columns for some intermediate formulas (you should have those columns in your solution, though): we will skip $(p \to q) \wedge \neg (q \wedge r)$ and $(p \to q) \wedge \neg (q \wedge r) \wedge \neg (\neg r \wedge \neg s)$, which would come right before the last column. The "final formula" stands for $(p \to q) \wedge \neg (q \wedge r) \wedge \neg (\neg r \wedge \neg s) \wedge (s \to \neg q)$.

    $p$ $q$ $r$ $s$ $p \to q $ $q \wedge r$ $\neg (q \wedge r)$ $\neg r$ $\neg s$ $ \neg r \wedge \neg s$ $\neg ( \neg r \wedge \neg s) $ $\neg q$ $s \to \neg q$ Final formula
    T T T T T TF FFFT FFF
    T T T F T TF FTFT FTF
    T T F T T FT TFFT FFF
    T T F F T FT TTTF FTF
    T F T T F FT FFFT TTF
    T F T F F FT FTFT TTF
    T F F T F FT TFFT TTF
    T F F F F FT TTTF TTF
    F T T T T TF FFFT FFF
    F T T F T TF FTFT FTF
    F T F T T FT TFFT FFF
    F T F F T FT TTTF FTF
    F F T T T FT FFFT TTT
    F F T F T FT FTFT TTT
    F F F T T FT TFFT TTT
    F F F F T FT TTTF TTF

    There are three scenarios which agree with the detective's four statements. In all of them, $p = False, q = False$, so we can infer that both the butler and the cook are lying. With the gardiner and the handyman, we cannot say for sure; we only know that they cannot both be lying (at least one of them is telling the truth), as the detective already figured out.

  4. Finally, state your answer: what can you infer about each of the four witnesses?
    Answer

    The butler and the cook are both lying. Between the gardiner and the handyman, at least one (maybe both) is telling the truth, but this is the most we can say.