Expresar los rompecabezas lógicos con la notación del cálculo de proposiciones

Question

Estoy tratando de resolver un rompecabezas lógico que dice así:

La policía tiene tres sospechosos por el asesinato del Sr. Cooper: El Sr. Smith, el Sr. Jones y el Sr. Williams. Smith, Jones y Williams declaran que no mataron a Cooper. Smith también declara que Cooper era amigo de Jones y que a Williams le caía mal. Jones también declara que no conocía a Cooper y que estaba fuera de la ciudad el día en que Cooper fue asesinado. Williams también afirma que vio tanto a Smith como a Jones con Cooper el día del asesinato y que cualquiera de los dos, Smith o Jones, debió matarlo. ¿Puedes determinar quién fue el asesino si uno de los tres hombres es culpable, los dos inocentes dicen la verdad, pero las declaraciones del culpable pueden ser ciertas o no?

Cuando era joven, solía resolver estos rompecabezas gráficamente, dibujando vértices y flechas y excluyendo los casos imposibles. Pero ahora quiero hacerlo formalmente. ¿Cómo puedo expresar esta definición de rompecabezas utilizando la notación del cálculo de proposiciones, la inferencia y las tablas de verdad? O, en otras palabras, cuando te encuentras con un rompecabezas lógico y quieres resolverlo formalmente, ¿cuál es tu algoritmo?

---

Lo que he intentado. Extraje varias proposiciones de la definición:

1. S: no mató a C
2. S: J conocía a C
3. S: W no le gustaba C
4. J: no mató a C
5. J: J no conocía a C
6. J: fuera de la ciudad
7. W: no mató a C
8. W: S con C
9. W: J con C

Hay 3 grupos de proposiciones, dos de ellas son siempre verdaderas, la tercera puede contener afirmaciones verdaderas o falsas. Sea $A = 1 \land 2 \land 3$ , $B = 4 \land 5 \land 6$ , $C = 7 \land 8 \land 9$ . Entonces, desde ¿Cómo encontrar la fórmula lógica de una tabla de verdad dada? utilizando las tablas de verdad y los mapas de Karnaugh deduzco que la afirmación "algunas dos de A, B, C son verdaderas" se parece a $(A \land B \land \neg C) \lor (A \land \neg B \land C) \lor (\neg A \land B \land C)$ . Pero espera, "puede o no puede ser verdad" significa que todas las afirmaciones podrían ser verdaderas, no que al menos una sea falsa (de ahí que la NAND no sea apropiada aquí). Así que la frase debería reformularse como "al menos algunas dos de A, B, C son verdaderas". ¿Voy en la dirección correcta?

Answer 1

Puede ignorar las declaraciones 1,4 y 7, ya que no contienen información. Entonces, como la 2 y la 5 son contradictorias, una es falsa, por lo que W es inocente y dice la verdad. Es de suponer que la 9 contradice a la 6 (aunque tal vez C también estaba fuera de la ciudad), por lo que J es el asesino. La forma de formular la lógica proposicional es clave: ¿representa que 2 y 5 se contradicen y que 6 y 9 se contradicen? Esto suele ser difícil al pasar del inglés al cálculo proposicional.

Answer 2

Creo que no hay una respuesta definitiva sobre cómo resolver estos rompecabezas. Lo principal es conocer bien el cálculo proposicional para poder expresar un puzzle como fórmulas.

Puedo dar una posible manera de resolver formalmente tales rompecabezas utilizando herramientas automatizadas, que he utilizado en este caso:

Primero expresé el rompecabezas en el TPTP que es utilizado por muchos demostradores de teoremas automatizados. (El lenguaje TPTP es para la lógica de primer orden, pero la lógica proposicional también es posible, simplemente no se utilizan variables proposicionales):

% Basic syntax:
% Lines starting with % are comments.
% A formula is given by fof(name, type, formula) where 'name' identifies the formula,
% 'type' is either 'axiom' or 'conjecture' and 'formula' is a logic expression.
% Predicates start with lower case letters, and you can use propositional
% connectives: |, &, =>, <=, <=>, <~> (XOR), ~ (negation).

% The police have three suspects for the murder of Mr. Cooper: Mr. Smith, Mr. Jones, and Mr.

% Williams. Smith, Jones, and Williams each declare that they did not kill Cooper.

% Smith also states that Cooper was a friend of Jones and that Williams disliked him.

fof(smith, axiom, (~s => ( ~s & j_friend ) )).

% Jones also states that he did not know Cooper and that he was out of town the day Cooper was killed.

fof(jones, axiom, (~j => ( ~j & ~j_friend & j_out ) )).

% Williams also states that he saw both Smith and Jones with Cooper the day of the killing and that either Smith or Jones must have killed him.

fof(williams, axiom, (~w => ( ~w & ~j_out & ~s_out & ( s | j ) ) )).

% Can you determine who the murderer was if one of the three men is guilty,

% the two innocent men are telling the truth,

% but the statements of the guilty man may or may not be true?

fof(guilty, axiom, (s & ~j & ~w) | (~s & j & ~w) | (~s & ~j & w) ).

% Uncomment one of the following conjectures:
%fof(conj, conjecture, j).
%fof(conj, conjecture, w).
%fof(conj, conjecture, s).

Como sabemos que sólo los inocentes dicen la verdad y el culpable puede mentir, formalizamos "Jones declara..." como ~j => ... . Esto nos dice que si Jones es inocente, lo que dice es cierto; si es culpable, no tenemos información.

Luego ejecuto un probador de teoremas, que decide si la conjetura es demostrable a partir de los axiomas o no (los problemas proposicionales son siempre decidibles, así que siempre dará una respuesta). He utilizado E proverbio por eso:

eprover -l 0 --tstp-format puzzle.p

y obtengo un resultado, ya sea

# No proof found!
# SZS status CounterSatisfiable

o

# SZS status Theorem
# Proof found!

dependiendo de si mi conjetura era demostrable o no.

Espero que te ayude al menos un poco.

Answer 3

Definir

$S$ = Smith es el asesino

$J$ = Jones es el asesino

$W$ = Williams es el asesino

$TS$ = Smith dice la verdad

$TJ$ = Jones dice la verdad

$TW$ = Williams dice la verdad

$A$ = Cooper era amigo de Jones

$B$ = A Williams no le gustaba Cooper

$C$ = Jones conocía a Cooper

D = Jones fuera de la ciudad

E = Smith visto con Cooper

G = Jones visto con Cooper

Supuestos

$S \vee J \vee W$

$\neg (S \wedge J)$

$\neg (S \wedge W)$

$\neg (J\wedge W)$

$\neg S \rightarrow TS$

$\neg J \rightarrow TJ$

$\neg W \rightarrow TW$

$A \rightarrow C$

$G \rightarrow C$

$D \rightarrow \neg J$

Los hechos

$TS \rightarrow A$

$TS \rightarrow B$

$TJ \rightarrow \neg C$

$TJ \rightarrow D$

$TW \rightarrow E$

$TW \rightarrow G$

La prueba

Combinando suposiciones y hechos, utilice una tabla de verdad (preferiblemente automatizada) para demostrar que $$((S \vee J \vee W) \wedge \neg (S \wedge J) ... \wedge (TW \rightarrow G)) \rightarrow J$$

es una tautología. (Para un bonito generador de tablas de verdad, véase http://mathdl.maa.org/images/upload_library/47/mcclung/index.html )

Answer 4

Esta es la respuesta corta y sencilla:

S. dice que J. y C. eran amigos J. dice que J. y C. no se conocían

Así que uno de ellos está mintiendo. Esto significa que W. está diciendo la verdad.

W. dice que vio a S. y a J. con C. ese día. J. dice que estaba fuera de la ciudad.

Esto significa que J. es el que miente. Por lo tanto, él debe ser el asesino

Answer 5

No hay una receta real para resolver estos rompecabezas, salvo que (según mi experiencia) es realmente importante centrarse en encontrar la formalización más sencilla posible, y luego utilizar la forma de las fórmulas como guía para encontrar la solución. (Como otro ejemplo, véase https://math.stackexchange.com/a/619400/11994 .)

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\text{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\implies}{\Rightarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $ En este caso escribiremos $\;s,j,w\;$ para los tres sospechosos, uno de los cuales es igual a $\;m\;$ el culpable. Escribimos $\;T(x)\;$ para ' $\;x\;$ siempre dice la verdad", así que si $\;x\;$ dice " $\;P\;$ "entonces podemos representarlo como $\;T(x) \implies P\;$ . Por último, parece importante representar explícitamente $\;x\;$ conocía a Cooper', y lo representaremos como $\;K(x)\;$ .

Ahora se nos da bastante información dada explícitamente, donde $\;x\;$ representa a cualquier sospechoso: \begin{align} \tag a T(x) & \;\implies\; x \not=m \\ \tag b T(s) & \;\implies\; K(j) \land K(w) \\ \tag c T(j) & \;\implies\; \lnot K(j) \\ \tag d T(w) & \;\implies\; K(s) \land K(j) \land (s = m \lor j = m) \\ \tag e T(x) & \lor x = m \\ \end{align} Y hay un hecho implícito, a saber, que el asesino conocía a su víctima: $$ \tag f K(m) $$

Ahora nuestro objetivo es encontrar el $\;x\;$ para lo cual $\;x = m\;$ .

---

Observando la forma de estas fórmulas, nos damos cuenta de que $\;K(j)\;$ ocurre varias veces. Como no parece haber una forma obvia de hacer la reescritura, vamos a intentar una división de casos.

Si $\;K(j)\;$ es falso, entonces los lados derechos de $\ref b$ y $\ref d$ son falsos, y por lo tanto (por contraposición) también sus lados izquierdos son falsos, así que $\;\lnot T(s)\;$ y $\;\lnot T(w)\;$ . Por lo tanto (por $\ref e$ que dice que $\;\lnot T(x) \implies x=m\;$ ) ambos $\;s=m\;$ y $\;w=m\;$ que hace que $\;s=w\;$ que es una contradicción con la distinción de $\;s,j,w\;$ .

Por lo tanto, $\;K(j)\;$ es verdadera, y por lo tanto (por $\ref c$ y contraposición) $\;\lnot T(j)\;$ y por lo tanto (de nuevo por $\ref e$ ) $\;j=m\;$ .

---

Tenga en cuenta que no necesitamos utilizar $\ref a$ y $\ref f$ y también ignoramos una gran parte de los lados derechos de $\ref b$ y $\ref d$ .

Traduciendo la prueba anterior en palabras, obtenemos algo así:

Si Jones no conocía a Cooper, entonces tanto Smith ("Cooper era amigo de Jones") como Williams ("[yo] vi a [...] Jones con Cooper") mintieron, y por tanto sólo Jones dice la verdad, contradiciendo el hecho de que al menos los dos inocentes dicen la verdad. Por lo tanto, Jones mintió cuando dijo que no conocía a Cooper, y por lo tanto no es inocente: Jones es el culpable.

Sin embargo, si la respuesta se presenta sólo de esta manera, entonces es una especie de sorpresa para el lector, y eso debe evitarse, en la medida de lo posible. Por eso prefiero utilizar la forma de las fórmulas para construir la respuesta.