Caballeros y escuderos: acertijo 10
En la isla de los caballeros y los escuderos se encuentran tres habitantes: A, B y C.
Tenemos tres parámetros de entrada: A, B y C.
A dice: «Todos nosotros somos escuderos»,
A dice una única frase P (+info):
A ↔ P
Al igual que en el caso anterior, esta frase se puede representar con la siguiente ecuación:
A: P = ¬A ∧ ¬B ∧ ¬C = ¬(A ∨ B ∨ C)
B añade: «Uno de nosotros, y sólo uno, es un escudero».
B dice una única frase Q (+info):
B ↔ Q
En esta frase Q, B asegura que sólo hay un escudero entre ellos. Es decir, el escudero puede ser o A o B o C:
B: Q = (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ ¬C)
Deben ser coherentes ambas sentencias:
A ↔ P ∧ B ↔ Q
¿Puede determinarse lo que es B? ¿Puede determinarse lo que es C?
Entradas y salidas
Añadimos las entradas A, B y C (conectadas a LED0, LED1 y LED2, respectivamente) y una señal de salida S (conectada al LED7) que se activará cuando el circuito encuentre una solución.
A ↔ P
B ↔ Q
Como tenemos dos operaciones bicondicionales utilizaremos dos puertas XNOR (+info).
A ↔ P ∧ B ↔ Q
Esta ecuación se representa mediante una puerta AND (+info).
A: P = ¬A ∧ ¬B ∧ ¬C = ¬(A ∨ B ∨ C)
La frase P se puede representar de dos formas. Vamos a utilizar la más simplificada empleando una puerta NOR (+info).
B: Q = (¬A ∧ B ∧ C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ ¬C)
La sentencia Q se representa con un bloque ONE 0. Éste bloque, implementado con puertas AND y OR de 3 bit detecta si sólamente una de las entradas es 0.
Descargar circuito en Icestudio
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
Al sintetizar y descargar el circuito obtenemos dos soluciones válidas:
| (0, 0, 1) |
|---|
 |
| (0, 1, 1) |
|---|
 |
Por lo tanto (A, B, C) = (0, ?, 1), es decir no podemos afirmar lo que es B pero sabemos que A es un escudero y C es un caballero.
En este curso hemos creado circuitos digitales que encuentran soluciones a problemas lógicos.
Esta forma es mucho más rápida y eficiente que cualquier programa, en igualdad de frecuencia de reloj, ya que no requiere de un procesador que ejecute instrucciones, sino que se trata de un simple circuito secuencial.
Os animo a investigar esta metodología con circuitos más complejos para ver hasta dónde se puede llegar, pero sobre todo para pasar un buen rato pensando en hardware!
Más información en: http://FPGAwars.github.io
- Raymond Smuyllan, ¿Cómo se llama este libro? Capítulo 3: Caballeros y Escuderos [32] (1989) Ediciones Cátedra, S.A. [1]