¿Por qué seguir corriendo en contradicciones en este problema (variación de caballeros y bribones)?

Question

Edit: he intentado solucionar de otra manera, y publicado como una posible respuesta. Reacio a aceptar, y agradecería si alguien pudiera ir a través de ella y confirmar que es el camino a seguir.

Hay una isla habitada por dos tribus, la tribu de los Bribones (que siempre mienten) y Espías (que mienten a los Bribones, pero decir la verdad a otros Espías).

\begin{align} A \text{ says to } B &: F \text{ is a Spy, } C \text{ is a Knave.}\\ B \text{ says to } C &: \text{ If } D \text{ is a Knave, then so is }E\text{.}\\ C \text{ says to } D &: \text{ If } A \text{ is a Knave, then } F \text{ is a Spy.}\\ D \text{ says to } E &: \text{ Either } F \text{ is a Spy, or } A \text{ is a Knave.}\\ \end{align}

Determinar cual de las personas $A$, $B$, $C$, $D$ y $E$ son Espías, y que son los Bribones.

Aquí es cómo me trató de abordar el problema:

Para mayor claridad, escribo negación como $\bar p$, la conjunción como $pq$, la disyunción como $p+q$, la disyunción exclusiva como $p\oplus q$, implicación como $p\implies q$ y la contradicción como ↯.

Si una persona $x$ es un Truhán, I denota como $x=0$. Del mismo modo, si $x$ es un Espía, $x=1$.

El truthfullness de una declaración $T$ ($0$ para falso y $1$ por cierto) es una función de la persona que realiza la declaración ($x$) y la persona que la declaración sea hecha a ($y$). Obviamente $T(x,y)=1$ fib $xy=1$.

Lo primero que hice fue escribir las declaraciones de este modo:

\begin{align} AB&=F \tag{1a}\\ AB&=\bar C \tag{1b}\\ BC&=\bar D\implies \bar E = \\ &=\bar D \bar E + D = \\ &=D+ \bar E \tag{2}\\ CD&=\bar A\implies F = \\ &=\bar AF + A = \\ &=A+ F \tag{3}\\ DE&=F\oplus \bar A = \\ &=\bar F \bar A + FA \tag{4}\\ \end{align}

He hecho diferentes supuestos acerca de la $A$ $B$ (para todos los $4$ combinaciones posibles) y con base en ellos, el cálculo de los valores de $C$, $D$, $E$ y $F$. En todos los casos con los que me encontré contradicción. Fui sobre este montón de veces, y simplemente no puede ver ningún error en mi razonamiento, por lo que agradecería cualquier ayuda. También algún consejo acerca de alternativas (probablemente más elegante) enfoques a este problema sería bienvenido.

Aquí es exactamente lo que hice: \begin{align} \text{Assume}: A=0, B=0\tag{I}\\ \text{From (1a) and (1b)}: F=0, C=1\\ \text{From (2)}: D+\bar E=0\\ D=0, E=1\\ \text{From (3)}: A+F=0\\ \text{From (4)}: \bar F \bar A + FA=0 \\ 1+0=0 ↯\\ \end{align}

\begin{align} \text{Assume}: A&=0, B=1\tag{II}\\ \text{From (1a) and (1b)}: F&=0, C=1\\ \text{From (2)}: D+\bar E&=1\\ \text{Assume}: D&=0, E=0\tag{IIa}\\ \text{From (3)}: A&=0, F=0\\ \text{From (4)}: 1+0&=0 ↯\\ \text{Assume}: D&=1, E=1\tag{IIb}\\ \text{From (3)}: A+F&=1 ↯\\ \text{Assume}:D&=1, E=0\tag{IIc}\\ \text{From (3)}: A+F&=1 ↯\\ \end{align}

\begin{align} \text{Assume}: A&=1, B=0\tag{III}\\ \text{From (1a) and (1b)}: F&=0, C=1\\ \text{From (2)}: D&=0, E=1\\ \text{From (3)}: A+F&=0 ↯\\ \end{align}

\begin{align} \text{Assume}: A&=1, B=1\tag{IV}\\ \text{From (1a) and (1b)}: F&=1, C=0\\ \text{From (2)}: D&=0, E=1\\ \text{From (3)}: A+F&=0 ↯\\ \end{align}

Answer 1

He traducido su enigma en un Boolean circuit:

BC1.1

//  A says to B: F is a Spy, C is a Knave
S1 := F & !C;
//  if A is a Knave or B is a Spy
//  the statement of A is false
A1 := (!A | (A & !B)) => !S1;
//  if A and B are Spies, the statement is true
A2 := (A & B) => S1;

//  B says to C: If D is a Knave, then so is E
S2 := !D => !E;
B1 := (!B | (B & !C)) => !S2;
B2 := (B & C) => S2;

//  C says to D: If A is a Knave, then F is a Spy
S3 := !A => F;
C1 := (!C | (C & !D)) => !S3;
C2 := (C & D) => S3;

//  D says to E: Either F is a Spy, or A is a Knave
S4 := F ^ !A;
D1 := (!D | (D & E)) => !S4;
D2 := (D & E) => S4;

//  all variables must be true
ASSIGN A1, A2, B1, B2, C1, C2, D1, D2;

El uso de la herramienta bc2cnf, me convertí en el circuito en una Forma Normal Conjuntiva y corrió dos SAT Solvers Z3 y Cryptominisat para encontrar una solución.

Ambos regresaron UNSAT, es decir, no existe una solución, o hay algún error en mi descripción del circuito.

Answer 2

Una posible respuesta podría ser esta. No te da una solución única, y creo que es un poco dudoso, así que no voy a aceptar que todavía, y agradecería si alguien pudiera mirarlo.

Vamos a ver cómo la solución intento de cambios si tratamos a la implicación de la tabla de verdad: $$\begin{matrix} p&q&p\implies q&\overline{(p\implies q)}\\ 0&0&?&?\\ 0&1&?&?\\ 1&0&0&1\\ 1&1&1&0 \end{de la matriz}$$ en lugar de: $$\begin{matrix} p&q&p\implies q&\overline{(p\implies q)}\\ 0&0&1&0\\ 0&1&1&0\\ 1&0&0&1\\ 1&1&1&0 \end{de la matriz}$$ Hacemos esto porque al $p=0$, podemos tener ninguna confirmación sobre si la regla (si $p$$q$) se mantiene, por lo que no podemos inferir nada acerca de el Espía/Truhán estado de la declaración de fabricante y de la declaración de oyente.

• Suponga $A=1$ $B=1$
• A partir de (1a) y (1b): $F=1$ $C=0$
• A partir de (2): $\overline{D} \implies E$
• (3) es irrelevante como $A=1$
• Suponga $D=0$ $E=1$
• A partir de (4): $0=1+0$ es una contradicción
• Suponga que en lugar de $D=1$ $E=0$ o $E=1$
• Si $E=0$, (4) conduce a la contradicción de nuevo, por lo que asumen $E=1$
• A partir de (4): $1=1+0$

Esto nos lleva a una solución. $A$, $B$, $D$, $E$ y $F$ son los espías y $C$ es el Truhán.

Ahora tratamos de para otros valores de $A$$B$:

• Suponga $A=0$ $B=0$
• A partir de (1a) y (1b): $F=0$ $C=1$
• A partir de (2): $\overline{D}\implies E$
• Suponga $D=0$ $E=1$
• De (3): $\overline{A}\implies \overline{F}$, $F=0$ cual es el correcto
• A partir de (4): $0 = 0 + 1$ es una contradicción
• Suponga que en lugar de $D=1$ $E=0$ o $E=1$
• A partir de (3): $F=1$ lo cual es una contradicción, independientemente de $E$

---

• Suponga $A=0$ $B=1$
• A partir de (1a) y (1b): $F=0$ $C=1$
• A partir de (2): $\overline{D}\implies \overline{E}$
• Suponga $D=0$ $E=0$
• De (3): $\overline{A}\implies \overline{F}$, $F=0$ correcto
• (4) conduce a contradicción.
• Suponga que en lugar de $D=1$ $E=0$ o $E=1$
• A partir de (3): $F=1$ lo cual es una contradicción, independientemente de $E$

Y, finalmente,

• Suponga $A=1$ $B=0$
• A partir de (1a) y (1b): $F=0$ $C=1$
• A partir de (2): $\overline{D}\implies E$
• Suponga $D=0$ $E=1$
• (3) aquí es irrelevante debido a que $A=1$
• A partir de (4): $0 = 0 + 0$

Lo que nos da otra solución. Espías: $A$, $C$ y $E$. Los bribones: $B$, $D$, y $F$.

• Suponga $D=1$ $E=0$ o $E=1$
• Para $E=1$, (4) conduce a una contradicción, pero para $E=0$ obtenemos otra solución

Espías: $A$, $C$ y $D$. Los bribones: $B$, $E$ y $F$.

Todos los 3 soluciones parecen encajar en las declaraciones.