El acertijo lógico más difícil

«El acertijo lógico más difícil del mundo» es un título que acuñó George Boolos en La República (1992) bajo el título «L'indovinello più difficile del mondo» para el siguiente acertijo lógico inspirado en Raymond Smullyan:

Tres dioses A, B, y C son llamados, en algún orden, Verdad, Falso, y Aleatorio. Verdad siempre habla expresando la verdad, Falso siempre habla expresando algo falso, pero la respuesta de Aleatorio es completamente aleatoria pudiendo ser verdadera o falsa. Su tarea es determinar las identidades de A, B, y C preguntando tres preguntas cuya respuesta es sí o no; cada pregunta debe ser formulada a un único dios. Los dioses entienden el español, pero contestarán todas las preguntas en su propio idioma, en el cual las palabras para Sí y No son 'da' y 'ja', en algún orden. Usted no sabe qué significado se asocia a cada palabra.

Boolos además dio las siguientes aclaraciones:^[1]

Es posible formularle a un mismo dios más de una pregunta (y por lo tanto puede ocurrir que a algún dios no se le haga ninguna pregunta).
Cuál es la segunda pregunta, y a qué dios se le realiza, puede depender de la respuesta que se reciba a la primera pregunta (y en forma similar para la tercera pregunta).
La decisión sobre si Aleatorio responderá con la verdad o la falsedad puede ser pensado como que depende de arrojar una moneda dentro de su cabeza: si la moneda cae cara él hablará con la verdad; si cae cruz, hablará falsamente.
Aleatorio responderá 'da' o 'ja' toda vez que se le realice una pregunta Si-No.^[2]

Introducción a la Lógica como premisa[editar]

Al tratarse de Lógica, uno de los campos de las Matemáticas discretas más deductivos que existen, es de gran necesidad aplicar un apartado introductorio que explique de forma escueta y concisa de qué trata este campo que, como se ve en este artículo, lleva al límite sus fundamentos.

La lógica, textualmente del propio artículo de Wikipedia previamente mencionado:

<<...es la ciencia formal que estudia los principios de la demostración y la inferencia válida. La palabra deriva del griego antiguo λογική logikḗ, que significa «dotado de razón, intelectual, dialéctico, argumentativo», que a su vez viene de λόγος (lógos), «palabra, pensamiento, idea, argumento, razón o principio».>>

Partiendo de esa base y teniendo en cuenta que se sabe un mínimo de este campo, se puede mencionar el siguiente ejemplo, más sencillo que el objeto del propio artículo, el cual terminará de facilitar el entendimiento de este intrínseco modo de ver las matemáticas.

Esto es un ejemplo de Lógica proposicional básico(Conectivas lógicas), más concretamente Conjunción lógica, y se resuelve teniendo en cuenta la expresión de la siguiente forma:

Si tenemos:

p=1 ; q=0 y se propone  $(p\land q)$ , si para que sean modelo deben cumplirse 'p y q' simultáneamente, entonces la expresión no es modelo además de insatisfactible, es decir:

p	q	p^q
T	F	F	$\Leftarrow$ (Interpretación)

Esto es un ejemplo básico de lo que se necesita para que una interpretación $(p\land q)$ sea modelo (que según las condiciones de la interpretación den 1 como resultado final) en lógica proposicional.

También podemos ver un ejemplo de disyunción lógica con los valores de esas variables anteriormente creadas, esto es:

Si tenemos:

p=1 ; q=0 y se propone  $(p\lor q)$ , si para que sean modelo deben cumplirse 'p o q', entonces la expresión es modelo, además de satisfactible, ya que:

p	q	p∨q
T	F	T	$\Leftarrow$ (Interpretación)

Además de estos dos ejemplos, hay más tipos de conectivas lógicas, las cuales se pueden ver en el artículo de Wikipedia $\Rightarrow$ Lógica proposicional, además de todas las tablas de verdad genéricas de estas conectivas, añadiendo y completando también las mencionadas anteriormente.

Historia[editar]

Boolos le da el crédito al lógico Raymond Smullyan como creador del acertijo y a John McCarthy por la dificultad agregada de no conocer el significado de 'da' y 'ja'. Numerosos acertijos relacionados con este se encuentran profusamente en los escritos de Smullyan, por ejemplo en ¿Cómo se llama este libro?, pp. 149-156, describe una isla en Haití donde la mitad de los habitantes son zombis (que siempre mienten) y la otra mitad son humanos (que siempre dicen la verdad) y además explica que "la situación es sumamente complicada ya que si bien todos los nativos entienden el español perfectamente, un antiguo taboo de la isla les prohíbe utilizar palabras que no sean nativas para expresarse. Por lo tanto toda vez que se les pregunta una pregunta del tipo Si-No, ellos contestarán 'Bal' o 'Da' - una de las cuales significa Si y la otra No. El problema es que nosotros no sabemos cual de las dos palabras 'Bal' o 'Da' significa Si y cual significa No". Hay otros acertijos relacionados en The Riddle of Scheherazade.

En una forma más general este acertijo está basado en los famosos acertijos Knights and Knaves de Smullyan (en una isla ficticia, todos los habitantes o son caballeros, que siempre dicen la verdad, o escuderos, que siempre mienten. Los acertijos incluyen a un visitante de la isla que debe formular un número de preguntas del tipo por la afirmativa o por la negativa (si/no) para descubrir lo que él desea saber). Una versión de estos acertijos se popularizó en una escena de la película de fantasía, Laberinto con David Bowie. En la misma hay dos puertas con dos guardianes. Un guardián miente y el otro dice la verdad. Una puerta conduce al castillo y la otra conduce a "una muerte segura". El acertijo es descubrir que puerta lleva al castillo haciéndole a uno de los guardias una pregunta. En la película Sarah lo resuelve realizando la pregunta "¿El otro guardia me diría que esta puerta conduce al castillo?".

(Suponga que usted se dirige con el guardia de la puerta izquierda y formula la pregunta de Sarah; si la respuesta es "no" y el guardia siempre miente, entonces la puerta izquierda conduce al castillo; si la respuesta es "no" y el guardia siempre dice la verdad, la puerta izquierda conduce igualmente al castillo. Si la respuesta es "sí" y el guardia siempre miente, la puerta izquierda conduce a la muerte; si la respuesta es "sí" y el guardia siempre dice la verdad, la puerta izquierda conduce igualmente a la muerte.)

Como extensión a este tipo de problemas de lógica proposicional, tenemos la serie de acertijos que Raymond Smullyan presenta bajo el título de "El tigre y la doncella" donde se ha de escoger entre dos puertas el camino hacia la hija del sultán o la muerte segura a manos del felino.

También cabe destacar el capítulo de los Cofres de Porcia que Raymond toma prestado del relato El mercader de Venecia, en el cual se nos presentan varios cofres: oro, plata, plomo, con inscripciones verdaderas y falsas que se hacen referencia entre sí.

Un ejemplo extra de acertijo sobre lógica más sencillo[editar]

En la película Labyrinth (película) de Jim Henson (como antes se ha mencionado en el apartado de historia), se muestra un ejemplo en una escena[1] del filme en el que se puede facilitar la captación de este modo de pensar.

Como antes se ha explicado, la chica se ve en una confrontación al querer entrar al castillo, el cual tiene dos puertas "custodiadas" por dos guardias, uno de ellos explica que, para saber por qué puerta debe entrar, debe formular una sola pregunta a uno de los dos guardias, aunque también le afirma que uno dice la verdad y otro miente, con lo cual se complica la elección.

La chica, construye y lanza la siguiente pregunta al guardia de la izquierda: <<¿Me diría él que esta puerta es la que lleva al castillo?>> (refiriéndose a la puerta situada en la izquierda).

A lo que el guardia de la izquierda responde: <<Si>>

Teniendo en cuenta esto, si dice la verdad (el guardia de la izquierda), se puede asegurar que si el guardia de la izquierda dice que el guardia de la derecha diría si, la respuesta es que la puerta de la izquierda no es la correcta, ya que el otro estaría mintiendo.

En cambio, si miente (el guardia de la izquierda), entonces la puerta que dice el guardia de la izquierda que diría el guardia de la derecha que es la correcta no es la que lleva al castillo, y por tanto sería la puerta de la derecha la correcta.

Tomando como premisa el hecho de que:

Respuesta de los guardias

$p$ = "guardia de la izquierda dice la verdad"

$q$ = "guardia de la derecha dice la verdad"

Se puede formalizar todo esto, creando dos variables discretas seguidas de la siguiente expresión:

Expresión formalizada

$p\Leftrightarrow \neg q$

Este $\Leftrightarrow$ se debe a que, teniendo en cuenta que mientras uno de los dos miente el otro, de manera simultánea, dice la verdad y viceversa.

Gracias a la pregunta realizada por la chica el problema se reduce a dos posibilidades de solución que, al fin y al cabo, llevan al mismo sitio.

Esto se demuestra con la tabla de verdad:

p	q	p $\Leftrightarrow$ $\neg$ q
T	T	F
T	F	T
F	T	T
F	F	F

Tomando como referencia esta formalización la cual demuestra que, si el guardia $p$ dice la verdad, el guardia $q$ miente o viceversa, como ya se ha dicho anteriormente, se puede afirmar que la pregunta de la chica siempre te llevará a la puerta del castillo, es decir, la derecha.

Este ejemplo de acertijo es mucho más fácil de procesar que el propio tratado en el artículo (aunque también hace falta tener bien sentadas las bases de Lógica proposicional), y sirve como referencia "genérica" para llevar a cabo un desarrollo exhaustivo sobre la solución del otro.

Solución al acertijo de Raymond Smullyan[editar]

Boolos publicó su solución en el mismo artículo en el que publicó el acertijo. Boolos indica que "la primera jugada posee la finalidad de encontrar un dios sobre el que se tenga la certeza que no es Aleatorio, y que por lo tanto es o bien Verdadero o Falso". Existen diversas preguntas posibles que permiten obtener este resultado. Una estrategia es utilizar conectivos lógicos complejos en las preguntas (sean bicondicionales o alguna construcción equivalente).

La pregunta de Boolos era preguntar a A:

¿Es que da significa sí si y solo si tu eres Verdadero si y solo si B es aleatorio?

O en forma equivalente:

¿Es un número impar de las siguientes afirmaciones verdadera: tu eres Falso, da significa si, B es Aleatorio?

Roberts en el 2001 hizo notar que la solución al acertijo puede ser simplificada si se utilizan ciertos contrafactuales. La clave para la solución es que, para toda pregunta Q si/no, preguntarle a Verdadero o a Falso la pregunta:

¿Si yo te pregunto a ti Q, es que tu responderías ja?

De donde se obtiene la respuesta ja si la respuesta falsa a la pregunta Q es sí, y la respuesta da si la respuesta verdadera a la pregunta Q es no (Rabern and Rabern (2008) denominan a este resultado el lema interno de la pregunta). La razón por la cual funciona es posible analizarla si se observan los ocho casos posibles. Suponiendo que ja significa si y da significa no.

Se le pregunta a Verdadero y responde con ja. Dado que él dice la verdad, la respuesta verdadera a Q es ja, que significa si.

Se le pregunta a Verdadero y responde con da. Dado que él dice la verdad, la respuesta verdadera a Q es da, que significa no.

Se le pregunta a Falso y responde con ja. Dado que el miente entonces se deduce que si le preguntaras Q el responderia da. Él estaría mintiendo, por lo que la respuesta verdadera a Q es ja, que significa si.

Se le pregunta a Falso y responde con da. Dado que el miente entonces se deduce que si le preguntaras Q el responderia ja. Él estaría mintiendo, por lo que la respuesta verdadera a Q es da, que significa no.

Suponiendo que ja significa no y da significa si.

Se le pregunta a Verdadero y responde con ja. Dado que él dice la verdad, la respuesta verdadera a Q es da, que significa si.

Se le pregunta a Verdadero y responde con da. Dado que él dice la verdad, la respuesta verdadera a Q es ja, que significa no.

Se le pregunta a Falso y responde con ja. Dado que el miente entonces se deduce que si le preguntaras Q el responderia ja. Él estaría mintiendo, por lo que la respuesta verdadera a Q es da, que significa si.

Se le pregunta a Falso y responde con da. Dado que el miente entonces se deduce que si le preguntaras Q el responderia da. Él estaría mintiendo, por lo que la respuesta verdadera a Q es ja, que significa no.

Sobre la base de esto el análisis continúa de la forma siguiente.

Se le pregunta al dios B, "Si yo le preguntara a usted ¿es A Aleatorio?, ¿respondería usted 'ja'?". Si B responde 'ja', entonces o bien B es Aleatorio (y está respondiendo en forma aleatoria), o B no es Aleatorio y la respuesta indica que A es el Aleatorio. En cualquiera de los dos casos, C no es Aleatorio. Si B responde 'da', entonces o bien B es Aleatorio (y está respondiendo en forma aleatoria), o B no es Aleatorio y la respuesta indica que A no es Aleatorio. En cualquiera de los dos casos, A no es Aleatorio.

Se dirige a uno de los dioses que se ha identificado como que no es Aleatorio mediante la pregunta previa (A o C) y se le pregunta: "Si yo le preguntara a usted ¿es usted Verdad?, ¿respondería usted 'ja'?". Dado que no es Aleatorio, una respuesta 'ja' indica que es él es Verdad y una respuesta 'da' indica que él es Falso.

Al mismo dios se la realiza la siguiente pregunta: "Si yo le pregunto a usted ¿es B Aleatorio?, ¿sería su respuesta 'ja'?". Si la respuesta es 'ja' entonces B es Aleatorio; si la respuesta es 'da' entonces el dios al cual usted todavía no le ha hablado es Aleatorio. El dios que queda puede ser identificado por un proceso de eliminación.

El comportamiento de Aleatorio[editar]

La mayoría de las personas que leen el acertijo suponen que Aleatorio dará respuestas completamente aleatorias a toda pregunta que se le formule a él; sin embargo, no es eso lo que dice el acertijo. De hecho, en el tercer comentario aclaratorio de Boolos él refuta esta interpretación en forma específica.

Si Aleatorio dice la verdad o no debe ser interpretado como dependiendo del resultado de arrojar una moneda que se encuentra en su cabeza: si la moneda sale cara, él responderá con la verdad; si sale cruz responderá con la mentira.

O sea Aleatorio actúa aleatoriamente diciendo la verdad o mintiendo, lo que significa que Aleatorio no responde las preguntas en forma aleatorio.

Referencias[editar]

↑ https://web.archive.org/web/20070115103840/http://people.ucsc.edu/~jburke/three_gods.pdf
↑ George Boolos, The Hardest Logic Puzzle Ever (Harvard Review of Philosophy, 6:62-65, 1996).

T.S. Roberts, Some Thoughts About The Hardest Logic Puzzle Ever (Journal of Philosophical Logic 30:609–612(4), December 2001).
Brian Rabern and Landon Rabern, A Simple Solution to the Hardest Logic Puzzle Ever (Analysis, 68.2, forthcoming, April 2008).
Raymond Smullyan, What is the Name of This Book? (Prentice Hall, Englewood Cliffs, NJ, 1978).
Raymond Smullyan, The Riddle of Sheherazade (A. A. Knopf, Inc., New York, 1997).

Enlaces externos[editar]

Acertijo en video
Roberts T.S. Some thoughts about the hardest logic puzzle ever. Journal of Philosophical Logic, 30:609–612(4), December 2001. (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
An illustration of the puzzle

Datos: Q33041

[1] ttps://web.archive.org/web/20070115103840/http://people.ucsc.edu/~jburke/three_gods.pdf

[boolos-2] George Boolos, The Hardest Logic Puzzle Ever (Harvard Review of Philosophy, 6:62-65, 1996).

[1]

[2]