Caballeros y escuderos: acertijo 4 - Jesus89/logic-games GitHub Wiki
Enunciado
En la isla de los caballeros y los escuderos se encuentran dos habitantes: A y B. A dice: «Uno al menos de nosotros es escudero». ¿Qué son A y B?
Descripción formal
En la isla de los caballeros y los escuderos se encuentran dos habitantes: A y B.
Tenemos dos parámetros de entrada A y B.
A dice: «Uno al menos de nosotros es escudero».
A dice una única frase P (+info):
A ↔ P
La sentencia P se puede expresar de dos formas equivalentes:
- «O A es escudero o B es escudero»: ¬A ∨ ¬B
- «A y B no son ambos caballeros»: ¬(A ∧ B)
Esta relación en álgebra binaria es de hecho una de las Leyes de De Morgan. Estas leyes indican que:
- ¬(A ∧ B) ↔ ¬A ∨ ¬B
- ¬(A ∨ B) ↔ ¬A ∧ ¬B
Por lo tanto podemos definir P de dos formas:
A: P = ¬A ∨ ¬B = ¬(A ∧ B)
¿Qué son A y B?
Circuito digital
Entradas y salidas
Añadimos las entradas A y B (conectadas a LED0 y LED1, respectivamente) y una señal de salida S (conectada a LED7) que se activará cuando el circuito encuentre una solución.
A ↔ P
La operación bicondicional se implementa mediante una puerta XNOR (+info).
A: P = ¬A ∨ ¬B = ¬(A ∧ B)
La primera sentencia se representa con una puerta OR (+info) y dos puertas NOT (+info).
Descargar circuito en Icestudio
También podemos representar la segunda sentencia equivalente, en este caso con una puerta NAND (+info).
Descargar circuito en Icestudio
Resolución en FPGA
Para resolver el circuito añadimos un bloque que comprueba todas las posibilidades y encuentra la solución o soluciones correctas (+info). Sintetizamos este circuito en la FPGA.
Descargar circuito de pruebas en Icestudio
Solución
Al sintetizar y descargar el circuito obtenemos una única solución (1, 0).
| (1, 0) |
|---|
 |
Por lo tanto tenemos que (A, B) = (1, 0). A es caballero y B es escudero.
Conclusiones
-
Una puerta NAND permite determinar si al menos una entrada vale 0
-
Las Leyes de De Morgan indican que:
- ¬(A ∧ B) ↔ ¬A ∨ ¬B
- ¬(A ∨ B) ↔ ¬A ∧ ¬B
Referencias
- Raymond Smuyllan, ¿Cómo se llama este libro? Capítulo 3: Caballeros y Escuderos [28] (1989) Ediciones Cátedra, S.A. [1]