Resolviendo un problema al estilo Smullyan de un caballero y mentiroso usando deducción natural. ¿Cómo acortar esta prueba?

Question

[ EDITED, there were 2 useless lines in the deduction below]

El problema al estilo de Smullyan:

John: Si (y solo si) Bill es un embustero, entonces yo soy un embustero.

Bill: Somos de diferentes tipos.

Con la comprensión de que los caballeros solo dicen afirmaciones verdaderas y los embusteros solo dicen afirmaciones falsas, identifique los tipos de John y Bill.

(Por lo tanto, se sigue que si $J$ es la proposición de que John es un caballero, y John dice una afirmación lógica $X$, entonces $J\leftrightarrow X$ es una tautología.)

Mi intento utiliza deducción natural; pero el razonamiento es bastante largo.

¿Puedes pensar en una prueba de deducción natural más corta?

¿Cuál sería la forma más rápida de resolver el problema según tú?

A continuación, "J" significa "John es un caballero" y "B" significa "Bill es un caballero".

Nota: esta solución hace que la afirmación de Bill sea verdadera y la afirmación de John sea falsa; lo cual es coherente con que uno sea caballero y el otro embustero respectivamente.

De hecho, si tenemos ( B & ~J) (que es nuestra supuesta solución) la afirmación de John es falsa, ya que esta afirmación es equivalente a ( B <-> J), que a su vez es equivalente a ~ (B&~J) & ~ ( J&~B).

Answer 1

Aquí tienes una prueba que hice en http://proofs.openlogicproject.org/ El mío tiene 13 declaraciones frente a tus 39 (ya que tu prueba no llegó a mi declaración 14). Por otro lado, me mantuve con una formulación bidireccional y supongo que diferentes sistemas hacen cosas diferentes con $\leftrightarrow$E. Aun así, saca tus propias conclusiones.

Answer 2

En primer lugar, yo simbolizaría la información dada como:

$[J \leftrightarrow (~\neg J \leftrightarrow \neg B)] \land [B \leftrightarrow \neg (B \leftrightarrow J)]$

Luego, existen algunos principios de equivalencia útiles para el bicondicional:

Conmutación Bicondicional

$P \leftrightarrow Q \Leftrightarrow Q \leftrightarrow P$

Asociación Bicondicional

$P \leftrightarrow (Q \leftrightarrow R) \Leftrightarrow (P \leftrightarrow Q) \leftrightarrow R$

Negación Bicondicional

$\neg (P \leftrightarrow Q) \Leftrightarrow \neg P \leftrightarrow Q$

$\neg (P \leftrightarrow Q) \Leftrightarrow P \leftrightarrow \neg Q$

$\neg P \leftrightarrow \neg Q \Leftrightarrow P \leftrightarrow Q$

Complemento Bicondicional

$P \leftrightarrow P \Leftrightarrow \top$

$P \leftrightarrow \neg P \Leftrightarrow \bot$

$P \leftrightarrow \top \Leftrightarrow P$

$P \leftrightarrow \bot \Leftrightarrow \neg P$

Con eso:

\begin{array}{lll} 1. & [J \leftrightarrow (~\neg J \leftrightarrow \neg B)] \land [B \leftrightarrow \neg (B \leftrightarrow J)] & Dado\\ 2. & [J \leftrightarrow (~\neg J \leftrightarrow \neg B)] \land [B \leftrightarrow (\neg B \leftrightarrow J)] & Negación Bicondicional 1\\ 3. & [(J \leftrightarrow ~\neg J) \leftrightarrow \neg B] \land [(B \leftrightarrow \neg B) \leftrightarrow J] & Asociación Bicondicional 2\\ 4. & [\bot \leftrightarrow \neg B] \land [(\bot \leftrightarrow J] & Complemento Bicondicional 3\\ 5. & B \land \neg J & Complemento Bicondicional 4\\ \end{array}

También hay que notar que una simbolización razonable de la declaración de Bill hubiera sido $B \leftrightarrow (\neg B \leftrightarrow J)$, en cuyo caso podría haber comenzado en la línea 2 y obtenido el resultado en tan solo $3$ pasos de inferencia.

EDITAR: siguiendo una sugerencia de Matt Daly:

Supongamos que también tenemos:

Sustitución Bicondicional

$S(P) \land (P \leftrightarrow Q) \Leftrightarrow S(Q) \land (P \leftrightarrow Q)$

donde $S(Q)$ es el resultado de reemplazar cualquier ocurrencia de $P$ con $Q$ en $S(P)$

Reducción Bicondicional

$P \land (P \leftrightarrow Q) \Leftrightarrow P \land Q$

$\neg P \land (P \leftrightarrow Q) \Leftrightarrow \neg P \land \neg Q$

y al simbolizar la declaración de Bill como $\neg (J \leftrightarrow B)$, obtenemos:

\begin{array}{lll} 1. & [J \leftrightarrow (\neg J \leftrightarrow \neg B)] \land [B \leftrightarrow \neg (J \leftrightarrow B)] & Dado\\ 2. & [J \leftrightarrow \neg (J \leftrightarrow \neg B)] \land [B \leftrightarrow (J \leftrightarrow \neg B)] & Negación Bicondicional 1\\ 3. & [J \leftrightarrow \neg B] \land [B \leftrightarrow (J \leftrightarrow \neg B)] & Sustitución Bicondicional 2\\ 4. & [J \leftrightarrow \neg B] \land B & Reducción Bicondicional 3\\ 5. & \neg J \land B & Reducción Bicondicional 4\\ \end{array}

Answer 3

Sé que la pregunta era cómo acortar tu demostración, pero creo que primero deberíamos considerar si la demostración es válida. No está claro para mí qué axiomas o reglas de inferencia estás utilizando. Por ejemplo, "John dijo: (~B ↔ ~J)" no es una oración de lógica formal que conozca, y "Los caballeros siempre dicen la verdad" no es una regla de inferencia. Dices que J es la proposición de que John es un caballero, pero ~J sería entonces la proposición de que John no es un caballero, es decir, que John puede mentir, lo cual es bastante diferente de la proposición de que John siempre miente.

Las respuestas anteriores a la mía (las de Matthew Daly y Bram28) han tomado J y B como equivalentes a las afirmaciones hechas por John y Bill, lo que básicamente elimina la caballería/canallada del problema y lo convierte directamente en la verdad/falsedad de sus afirmaciones. Esa es la forma fácil de resolver el problema.

Pero dado que estás poniendo mucho trabajo en formalizar el argumento como ejercicio, es posible que quieras hacerlo de la manera difícil. No he pensado esto cuidadosamente, pero podrías dejar caer las proposiciones J y B, e en su lugar introducir fórmulas JP que signifiquen "John afirma P" y BP que signifique "Bill afirma P", y agregar un axioma como (∀x. Jx → x) ∨ (∀x. Jx → ~x) expresando que John es o un caballero o un canalla, y un axioma similar para Bill, y formalizar sus afirmaciones como premisas J(...) y B(...), y demostrar (∀x. Jx → ~x) & (∀x. Bx → x). Si quieres seguir con la lógica de cero orden, podrías usar un esquema de axiomas como (JP ↔ P) ↔ (JQ ↔ Q) para expresar la caballería o canallada. De cualquier manera, la demostración probablemente será significativamente más larga.

Answer 4

Entiendo que esta no es una demostración de deducción natural, pero en respuesta al comentario de benrg arriba, leí en otro lugar que puedes usar álgebra en el campo de Galois de dos elementos GF(2) para resolver cosas como estas, y en ese caso si tomas Z="A es un embustero" entonces formalizarías "A afirma p" como Z + p = 1, ya que o bien Z o p son verdaderos, pero no ambos. No conozco los detalles de cómo escalar esto para problemas difíciles, pero para el problema del OP, una solución es bastante corta:

1. Toma: A = "A es un caballero", B = "B es un caballero", Z = "A es un embustero" y Y = "B es un embustero"
2. Según la definición: A+Z = B+Y = 1
3. Lo inclusivo p o q es "p + q - pq = 1"
4. Las afirmaciones nos dan las ecuaciones: Z + AB + YZ - ABYZ = 1 y Y + AY + BZ - ABYZ = 1
5. ABYZ = 0 así que Z + AB + YZ = Z(1 + Y) + AB = 1 y Y + AY + BZ = Y(1 + A) + BZ = 1
6. Usando (2) (1+Y) = B y (1+A) = Z, sustituyendo en (5) terminamos con: B(Z+A)=1 y Z(Y+B)=1
7. Entonces B=1 y Z=1, es decir, A es un embustero y B es un caballero.