Caballeros y escuderos: introducción

Introducción

El siguiente curso es una introducción a la electrónica digital y la lógica binaria que utiliza una perspectiva diferente para interiorizar los conceptos básicos (+info).

Esta perspectiva consiste en diseñar cirtuitos digitales a partir de acertijos lógicos mediante la descripción formal del enunciado y a continuación añadir un circuito de test para encontrar de forma automática la solución o soluciones del problema.

Los acertijos que utilizaremos han sido extraidos del libro de Raymond Smuyllan, ¿Cómo se llama este libro? [1], y comienzan así:

Existe una isla en la que ciertos habitantes llamados «caballeros» dicen siempre la verdad, y otros llamados «escuderos» mienten siempre. Se supone que todo habitante de la isla es o caballero o escudero.

Descripción formal

Existen dos tipos de habitantes, los caballeros y los escuderos. Vamos a asignar un valor binario a cada uno:

Escuderos: 0
Caballeros: 1

Estos habitantes dicen proposiciones que pueden ser verdaderas o falsas. Asignamos también un valor numérico:

Frase falsa: 0
Frase verdadera: 1

Se utilizarán las letras A, B, C para identificar a los personajes y P, Q, R, para identificar las frases que dicen dichos personajes, respectivamente. A, B, C, etc. pueden ser escuderos (0) o caballeros (1). P, Q, R, etc. pueden ser sentencias verdaderas (1) o falsas (0).

Los caballeros siempre dicen la verdad y los escuderos mienten siempre

Esta sentencia significa que los caballeros (1) siempre dicen frases verdaderas (1), y los escuderos (0) siempre dicen frases falsas (0). Por lo tanto ésto se cumplirá siempre y cuando el valor del personaje y el valor de su frase sean iguales:

A ↔ P

En cada acertijo se deducirán una serie de ecuaciones que definirán formal y completamente el enunciado planteado.

Circuito de pruebas

Vamos a encontrar la solución a los problemas lógicos implementando los circuitos en una FPGA real. Para ello utilizaremos:

La placa con FPGA IceZUM Alhambra
El editor de circuitos digitales Icestudio 0.3

El resultado de la descripción formal del enunciado se puede traducir a un circuito combinacional formado por puertas lógicas. Éste circuito tendrá como parámetros de entrada los personajes (A, B, C, etc.) y como salida una señal (S) que determinará si la combinación de personajes (caballeros y escuderos) genera una solución válida.

Para encontrar las soluciones añadimos un circuito secuencial que comprueba todas las posibles combinaciones 2^N (000, 001, 010, 011, etc.) y se detiene cuando encuentra una solución. Como es un circuito electrónico cada combinación se prueba en un ciclo de reloj. En el caso de la IceZUM Alhambra el reloj es de 12 MHz, por lo que tarda unos 80 nanosegundos en validar cada combinación.

Además contiene un botón de Next (SW2), que permite continuar buscando soluciones tras encontrar una solución válida y un botón de Reset asíncrono (SW1) para reiniciar el proceso en cualquier momento.


Ejemplo de circuito de pruebas

El algoritmo termina cuando se han probado todas las combinaciones. Se pueden haber obtenido una o más soluciones durante la búsqueda. Si no se obtienen soluciones se deduce que el enunciado está incorrectamente planteado.

Cuando se encuentra una solución la señal S, conectada al LED7, se activa y muestra la combinación válida de personales en los LED0, LED1, LED2, etc. Por ejemplo, si tenemos dos personajes A y B y el LED7 se activa con LED0 encendido y LED1 apagado, esto significa que A (LED0 encendido) es caballero y B (LED1 apagado) es escudero.