¿Existe un método general eficaz para resolver los problemas de Caballeros y Caballeros al estilo de Smullyan? ¿Es el método de la tabla de verdad el más apropiado?

Question

A continuación, un intento de resolver un rompecabezas de caballero y bribón utilizando el método de la tabla de verdad.

¿Existen otros métodos?

Fuente : https://en.wikipedia.org/wiki/Knights_and_Knaves

Answer 1

Las tablas de verdad son sin duda un método muy sólido para los rompecabezas de Caballeros y Caballeros: son sistemáticas y fáciles.

Sin embargo, en lugar de su tabla de la verdad, me permito sugerir:

En primer lugar, utilicemos $J$ para "Juan es un caballero"

y $B$ para "Bill es un caballero

Entonces, hay 4 opciones reflejadas por 4 filas en la tabla de la verdad, en lugar de tus 8. De hecho, como Ethan Bolker explica en el comentario, la afirmación de John de que "ambos somos truhanes" es en realidad derivado sobre las reclamaciones de $J$ y $B$ ... a saber, es sólo $\neg J \land \neg B$ :

\begin{array}{cc|c} J&B&\neg J \land \neg B\\ \hline T&T&F\\ T&F&F\\ F&T&F\\ F&F&T\\ \end{array}

Por último, Juan debe decir la verdad si y sólo si es un caballero, es decir, los valores de verdad de la columna para $J$ y $\neg J \land \neg B$ debe coincidir. Esto descarta las filas 1, 2 y 4, y nos deja con la fila 3: John es un bribón, y Bill es un caballero.

Sin embargo, hay muchos otros métodos lógicos que se pueden utilizar.

Obsérvese que Juan dice la verdad si y sólo si es caballero, y así tenemos:

$J \leftrightarrow (\neg J \land \neg B)$

Bien, primero vamos a utilizar el álgebra booleana para simplificar:

$J \leftrightarrow (\neg J \land \neg B) \Leftrightarrow$

$(J \land (\neg J \land \neg B)) \lor (\neg J \land \neg (\neg J \land \neg B)) \Leftrightarrow$

$(J \land \neg J \land \neg B) \lor (\neg J \land (\neg \neg J \lor \neg \neg B)) \Leftrightarrow$

$(\bot \land \neg B) \lor (\neg J \land (J \lor B)) \Leftrightarrow$

$\bot \lor ((\neg J \land J) \lor (\neg J \land B)) \Leftrightarrow$

$\bot \lor (\neg J \land B) \Leftrightarrow$

$\neg J \land B$

Genial: John es un bribón y Bill es un caballero

Ahora bien, esta derivación algebraica en concreto era en realidad algo complicada, pero por experiencia puedo decirte que el álgebra suele funcionar a las mil maravillas para estos rompecabezas de Caballeros y Caballeros. Por ejemplo, tomemos un rompecabezas de Caballeros y Caballeros al azar de un único sitio web que contiene 382 rompecabezas de Caballeros y Caballeros. OK ...generando un número al azar entre 1 y 382 ... ¡78! OK, el problema 78 se lee:

Conocerás a tres habitantes: Homer, Dave y Bill. Homer te dice que ni Dave ni Bill son caballeros. Dave te dice que tanto Homer como Bill son caballeros. Bill dice que Homer es un caballero o Dave es un truhán.

Bien, simbolicemos:

$H \leftrightarrow \neg(D \lor B)$

$D \leftrightarrow (H \land B)$

$B \leftrightarrow (H \lor \neg D)$

De acuerdo, los bicondicionales pueden utilizarse como tipos de sustituciones. Es decir, dado $B \leftrightarrow (H \lor \neg D)$ podemos sustituir $H \lor \neg D$ para $B$ . Hagamos esto para $D \leftrightarrow (H \land B)$ así que tenemos:

$D \leftrightarrow (H \land (H \lor \neg D))$

que por Absorción se simplifica a:

$D \leftrightarrow H$

Aha, así que podemos sustituir $D$ y $H$ entre sí. En particular, hagámoslo para $B \leftrightarrow (H \lor \neg D)$ así que tenemos:

$B \leftrightarrow (H \lor \neg H)$

que por Complemento se convierte en:

$B \leftrightarrow \top$

Esto no sólo te dice que $$ es un caballero .. sino que ahora también podemos utilizar esto como una sustitución de la primera premisa:

$H \leftrightarrow \neg(D \lor \top)$

que se simplifica a:

$H \leftrightarrow \neg \top$

y así:

$H \leftrightarrow \bot$

Así que ahora sabemos Homero es un bribón ... y ya que teníamos que $D \leftrightarrow H$ por lo que también tenemos que $D$ es un bribón.

Sin todos los comentarios, esto es lo que hicimos:

\begin{array} 1. & H \leftrightarrow \neg(D \lor B) & Premise\\ 2. & D \leftrightarrow (H \land B) & Premise\\ 3. & B \leftrightarrow (H \lor \neg D) & Premise\\ 4. & D \leftrightarrow (H \land (H \lor \neg D)) & Biconditional \ Substitution 2,3\\ 5 & D \leftrightarrow H & Absorption \ 4\\ 6. & B \leftrightarrow (H \lor \neg H) & Biconditional \ Substitution 3,5\\ 7. & B \leftrightarrow \top & Complement \ 6\\ 8. & B & 7\\ 9. & H \leftrightarrow \neg(D \lor \top) & Biconditional \ Substitution 1,8\\ 10. & H \leftrightarrow \neg \top & Annihilation \ 9\\ 11. & H \leftrightarrow \bot & Inverse \ 10\\ 12. & \neg H & 11\\ 13. & \neg D & 5,12\\ \end{array}

¡Genial!

OK, ahora vamos a hacer una prueba formal .. que va a formalizar el siguiente razonamiento: Si Juan es un caballero, entonces está diciendo la verdad, y por lo tanto Juan y Bill deben ser ambos caballeros... pero eso contradice la suposición de que Juan es un caballero. Por lo tanto, Juan no puede ser un caballero, y por lo tanto debe ser un bribón. Por lo tanto, Juan miente y no puede ser cierto que Juan y Bill sean caballeros. Como ya se sabe que Juan es un bribón, Bill debe ser un caballero.

Bien, formalicemos este argumento, y demostremos que John es un bribón y Bill un caballero usando la premisa de que $J \leftrightarrow (\neg J \land \neg B)$ :

\begin{array}{lll} 1&J \leftrightarrow (\neg J \land \neg B)&Given\\ 2&| \ J & Assumption\\ 3&| \neg J \land \neg B& \rightarrow \ Elim \ 1,2\\ 4&| \neg J & \land \ Elim \ 3\\ 5&| \bot & \bot \ Elim \ 2,4\\ 6&\neg J & \neg \ Intro \ 2-5\\ 7&| \neg B & Assumption\\ 8&|\neg J \land \neg B&\land \ Into \ 6,7\\ 9&|J&\rightarrow \ Elim \ 1,8\\ 10&|\bot&\bot \ Intro \ 6,9\\ 11&\neg \neg B& \neg \ Intro \ 7-10\\ 12&B&\neg \ Elim \ 11\\ 13&\neg J \land B& \land \ Intro \ 6,12\\ \end{array}

Bien, dos métodos más, ambos de búsqueda de modelos. En primer lugar, el método del árbol de la verdad (también llamado método de los tableaux), en el que descompones enunciados y ves de qué manera (si es que hay alguna) puedes hacer que sean verdaderos:

Y luego tenemos Davis-Putnam, que se parece un poco más a una tabla de verdad, ya que exploras sistemáticamente qué pasaría con tus enunciados al establecer las variables Verdadero o Falso:

En ambos casos, las únicas ramas abiertas son las que tienen $J$ siendo Falso y $B$ ser verdad, así que una vez más: John es un bribón y Bill es un caballero.

Answer 2

Las tablas verdadero-falso siempre funcionan, por supuesto, pero otro enfoque es utilizar álgebra en el campo con dos elementos (es decir, los números enteros módulo 2) para representar valores de verdad.

Si dejamos que $1$ representan una afirmación verdadera y $0$ representan una afirmación falsa, entonces

• "X e Y" corresponde a $xy$ .
• "no X" corresponde a $1-x$ .
• "X o Y" corresponde a $x+y-xy$ .

y, por tanto, podemos representar cualquier fórmula proposicional mediante una expresión polinómica. Por último, podemos representar "A dice (o diría) X" mediante la ecuación $$ (\text{A is a knave}) + x = 1 $$ ya que si A dice X entonces sabemos que o X es verdad o A es un bribón pero no ambos .

Para el rompecabezas simple en cuestión, introduzca entonces variables $j$ y $b$ para "John es un bribón" y "Bill es un bribón". La afirmación de John es entonces $jb$ y el hecho conocido de que dice que es la ecuación $$ j+jb = 1 $$ El álgebra nos dice ahora $$ j(1+b) = 1$$ y la única manera de que eso sea cierto en $\mathbb F_2$ es si $j=1$ y $1+b=1$ . En otras palabras, "Juan es un bribón" debe ser cierto, y "Bill es un bribón" debe ser falso.

Answer 3

A menudo se puede hacer una suposición y derivar una contradicción. En este caso, supongamos que Juan es un caballero. Entonces dice la verdad, pero "los dos somos caballeros" sería falso. Por lo tanto Juan es un truhán. Ahora la afirmación "ambos somos truhanes" debe ser falsa, y sabemos que Juan es un truhán, por lo que Bill debe ser un caballero.

Answer 4

Como otros han señalado, las tablas de verdad siempre funcionan para los rompecabezas de "clasificar a los participantes basándose en sus declaraciones"; si trabajas con los libros de Smullyan, por supuesto que no todos los rompecabezas son de este tipo, ni siquiera al principio. Por ejemplo, habrá rompecabezas del tipo "fulanito respondió a mi pregunta y yo supe bla; ¿qué pregunta hice?". Estas preguntas requieren pensar un poco más, pero a menudo se pueden comprobar mediante tablas de verdad una vez que se tienen algunas ideas.

En este caso concreto, puedes llegar a la respuesta más rápidamente observando este hecho clave:

Ningún caballero pretende ser un bribón.

"Ambos somos truhanes" es una afirmación de ser un truhán, y por lo tanto podemos rechazar inmediatamente todas las columnas de la tabla de verdad que sugieren que Juan es un caballero. Eliminando inmediatamente la mitad de las posibilidades, se puede simplificar este tipo de problema.