Modelling and solving: investigations and puzzles

Version without JavaScript, read-only: workshops, quizzes and running code are not available here. Full version · Catalogue · Sign in

Translating facts into formulas, testing their consistency, running DPLL by hand, and sorting out the inhabitants of two islands. Chapter 4.

Solution

$r$: “the object is rare”, $c$: “it is expensive”. $\Sigma = \{r \to c,\; c \to \lnot r\}$.
Possible: $\Sigma$ is satisfiable, for example with $r = 0$. But if $r = 1$, then $c = 1$, then $\lnot r$: contradiction. Every model has $r = 0$, so $\Sigma \vDash \lnot r$: the object is not rare. About its price, we know nothing.

Solution

With $p$, $j$, $a$: “Pierre (Jacques, André) is blond”. Fact 1: $p \lor j \lor a$. Fact 2: $p \land \lnot j \to a$. Fact 3: $j \to \lnot p$. Fact 4: $(a \land j) \lor (\lnot a \land \lnot j)$, that is, $a \leftrightarrow j$.
By cases on $j$. If $j = 0$: fact 4 gives $a = 0$, fact 1 gives $p = 1$, and fact 2 then requires $a = 1$: contradiction. So $j = 1$: fact 4 gives $a = 1$, fact 3 gives $p = 0$, and facts 1 and 2 are satisfied. The facts are consistent, with a single model: Jacques and André are blond, Pierre is not.

Solution

$(p \lor j \lor a) \land (\lnot p \lor j \lor a) \land (\lnot j \lor \lnot p) \land (\lnot a \lor j) \land (a \lor \lnot j)$. Clause 2 comes from $\lnot(p \land \lnot j) \lor a$; fact 4 gives the last two.
No unit clause at the start. Choice $j = 0$: $\lnot a \lor j$ becomes $\lnot a$, so $a = 0$; $p \lor j \lor a$ becomes $p$, so $p = 1$; $\lnot p \lor j \lor a$ becomes empty: conflict. Backtrack, $j = 1$: $\lnot j \lor \lnot p$ becomes $\lnot p$, so $p = 0$; $a \lor \lnot j$ becomes $a$, so $a = 1$. All the clauses are satisfied: model $p = 0, j = 1, a = 1$.

Exercise · The Island of Questions

On the Island of Questions, the inhabitants do nothing but ask questions, which are answered with yes or no. The Positives can only ask questions whose true answer is yes; the Negatives, only questions whose true answer is no. A Positive may ask “Do two and two make four?”, a Negative may not.

An inhabitant shouts at you: “Am I a Negative?” What should you conclude? And if he had shouted: “Am I a Positive?”
Adam asks: “Are Barbara and I both Negatives?” Who is what?
Céline asks her husband Denis: “Darling, are we of different types?” What do we know?
Zorn asks: “Am I one of those who can ask whether they are Negatives?” What can we deduce, or is this story impossible?
Xylef asks: “Am I among those who can ask the question I am asking you?” What do you make of it?

Hint: with $x$ = “$X$ is Positive”, an inhabitant $X$ can ask the question $Q$ if and only if $x \leftrightarrow Q$.

Solution

“Am I a Negative?”: $x \leftrightarrow \lnot x$, unsatisfiable. Nobody can ask this question: the encounter is impossible. “Am I a Positive?”: $x \leftrightarrow x$, valid: everyone can ask it, we conclude nothing.
$a \leftrightarrow (\lnot a \land \lnot b)$. If $a = 1$, the right-hand side is false: contradiction. So $a = 0$, and $\lnot a \land \lnot b$ must be false, so $b = 1$. Adam is Negative, Barbara Positive.
$c \leftrightarrow (c \oplus d)$. If $c = 1$: $c \oplus d = 1$, so $d = 0$. If $c = 0$: $c \oplus d = 0$, so $d = 0$. Denis is Negative; about Céline, we know nothing.
By question 1, nobody can ask whether they are Negative: the true answer to Zorn's question is no. So $z \leftrightarrow \bot$: Zorn is Negative, and the story is possible.
Let $k$ be “Xylef can ask this question”. By the hint, $k \leftrightarrow (x \leftrightarrow k)$. Now he does ask it, so $k = 1$, and what remains is $x \leftrightarrow 1$: Xylef is Positive.

Solution

$b \leftrightarrow (\lnot a \land \lnot b)$: same structure as Adam. Barnabé is a Knave, Amanda a Knight.
$a \leftrightarrow (a \land \lnot b)$. If $a = 1$: $b = 0$. If $a = 0$: the right-hand side is false whatever $b$ is. Three models: $(a, b) = (1, 0), (0, 0), (0, 1)$. We do not know who is who, but $\lnot(a \land b)$ is true in all three: they are not both Knights.

Solution

With $g$: “the left path leads to the treasure” and $x$: “you are a Knight”, ask the question $g \leftrightarrow x$: “Does the left path lead to the treasure if and only if you are a Knight?”

A Knight answers the true value of $g \leftrightarrow 1$, that is, $g$. A Knave answers the opposite of $g \leftrightarrow 0$, that is, $\lnot\lnot g = g$. In both cases, he answers yes if and only if the left path is the right one. Variant in plain English: “If I asked you whether the left path leads to the treasure, would you answer yes?”