Modéliser et résoudre : enquêtes et énigmes

1. $r$ : « l'objet est rare », $c$ : « il est cher ». $\Sigma = \{r \to c,\; c \to \lnot r\}$.
2. Possible : $\Sigma$ est satisfiable, par exemple avec $r = 0$. Mais si $r = 1$, alors $c = 1$, puis $\lnot r$ : contradiction. Tout modèle a $r = 0$, donc $\Sigma \vDash \lnot r$ : l'objet n'est pas rare. Sur son prix, on ne sait rien.

1. Avec $p$, $j$, $a$ : « Pierre (Jacques, André) est blond ». Fait 1 : $p \lor j \lor a$. Fait 2 : $p \land \lnot j \to a$. Fait 3 : $j \to \lnot p$. Fait 4 : $(a \land j) \lor (\lnot a \land \lnot j)$, c'est-à-dire $a \leftrightarrow j$.
2. Par cas sur $j$. Si $j = 0$ : le fait 4 donne $a = 0$, le fait 1 donne $p = 1$, et le fait 2 exige alors $a = 1$ : contradiction. Donc $j = 1$ : le fait 4 donne $a = 1$, le fait 3 donne $p = 0$, et les faits 1 et 2 sont satisfaits. Les faits sont cohérents, avec un seul modèle : Jacques et André sont blonds, Pierre ne l'est pas.

1. $(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)$. La clause 2 vient de $\lnot(p \land \lnot j) \lor a$ ; le fait 4 donne les deux dernières.
2. Aucune clause unitaire au départ. Choix $j = 0$ : $\lnot a \lor j$ devient $\lnot a$, donc $a = 0$ ; $p \lor j \lor a$ devient $p$, donc $p = 1$ ; $\lnot p \lor j \lor a$ devient vide : conflit. Retour arrière, $j = 1$ : $\lnot j \lor \lnot p$ devient $\lnot p$, donc $p = 0$ ; $a \lor \lnot j$ devient $a$, donc $a = 1$. Toutes les clauses sont satisfaites : modèle $p = 0, j = 1, a = 1$.

1. « Suis-je un Négatif ? » : $x \leftrightarrow \lnot x$, insatisfiable. Personne ne peut poser cette question : la rencontre est impossible. « Suis-je un Positif ? » : $x \leftrightarrow x$, valide : tout le monde peut la poser, on ne conclut rien.
2. $a \leftrightarrow (\lnot a \land \lnot b)$. Si $a = 1$, le membre droit est faux : contradiction. Donc $a = 0$, et $\lnot a \land \lnot b$ doit être fausse, donc $b = 1$. Adam est Négatif, Barbara Positive.
3. $c \leftrightarrow (c \oplus d)$. Si $c = 1$ : $c \oplus d = 1$, donc $d = 0$. Si $c = 0$ : $c \oplus d = 0$, donc $d = 0$. Denis est Négatif ; sur Céline, on ne sait rien.
4. D'après la question 1, personne ne peut demander s'il est Négatif : la question de Zorn a pour vraie réponse non. Donc $z \leftrightarrow \bot$ : Zorn est Négatif, et l'histoire est possible.
5. Soit $k$ : « Xylef peut poser cette question ». Par l'indication, $k \leftrightarrow (x \leftrightarrow k)$. Or il la pose, donc $k = 1$, et il reste $x \leftrightarrow 1$ : Xylef est Positif.

1. $b \leftrightarrow (\lnot a \land \lnot b)$ : même structure que Adam. Barnabé est un Pire, Amanda une Pure.
2. $a \leftrightarrow (a \land \lnot b)$. Si $a = 1$ : $b = 0$. Si $a = 0$ : le membre droit est faux quel que soit $b$. Trois modèles : $(a, b) = (1, 0), (0, 0), (0, 1)$. On ne sait qui est qui, mais $\lnot(a \land b)$ est vraie dans les trois : ils ne sont pas tous les deux Purs.

Avec $g$ : « le chemin de gauche mène au trésor » et $x$ : « tu es un Pur », poser la question $g \leftrightarrow x$ : « Le chemin de gauche mène-t-il au trésor si et seulement si tu es un Pur ? »

Un Pur répond la vraie valeur de $g \leftrightarrow 1$, c'est-à-dire $g$. Un Pire répond le contraire de $g \leftrightarrow 0$, c'est-à-dire $\lnot\lnot g = g$. Dans les deux cas, il répond oui si et seulement si le chemin de gauche est le bon. Variante en français : « Si je te demandais si le chemin de gauche mène au trésor, répondrais-tu oui ? »