Tablas de verdad

01 · Punto de partida

«Si pasa esto, sale esto»

Un cliente te pide: «que suene la alarma si hay humo, o si hace calor y la puerta está cerrada». Suena razonable hasta que alguien pregunta: ¿y si hay humo y calor? ¿Y si la puerta está abierta y hay calor? El lenguaje natural deja huecos. Un circuito digital no puede tener huecos: para cada combinación posible de sus entradas, la salida es 0 o es 1.

• ¿Cómo se arma una tabla y en qué orden van las filas?
• ¿Cómo se lee la función que describe, y qué son los minterms y maxterms?
• ¿Cuántas funciones distintas existen con dos entradas?
• ¿Qué se hace con las combinaciones que nunca ocurren?
• ¿Cómo se pasa de un enunciado en palabras a una tabla sin errores?

02 · Anatomía

Entradas, filas y una salida

Una tabla de verdad tiene una columna por cada entrada, una columna por cada salida y una fila por cada combinación de entradas. Las filas siempre van en orden binario: la primera es todo ceros y se cuenta hacia arriba como en el Tema 4, con la primera entrada como bit más significativo. Así el número de la fila es literalmente el número binario que forman las entradas.

Para armar el orden sin pensar: la última columna alterna 0, 1, 0, 1…; la anterior alterna de a dos; la anterior de a cuatro. Es la misma observación del Tema 4 sobre cómo cambia cada bit al contar.

La segunda cuenta es la que sorprende: con cada entrada nueva las filas se duplican y las funciones posibles se elevan al cuadrado. Por eso las tablas son la herramienta para pocas variables; los circuitos grandes se arman combinando bloques chicos (multiplexores, sumadores, comparadores en los Temas 18 a 27), cada uno con su tabla pequeña.

03 · Minterms y maxterms

De la tabla a la función

Mirar la tabla ya es «saber» la función. Pero para construir el circuito hace falta una expresión. Hay un método mecánico que sirve siempre, sin ingenio, y tiene dos versiones simétricas.

Suma de productos: mirar los 1

Cada fila con salida 1 se convierte en un minterm: un AND de todas las entradas, donde cada entrada aparece directa si vale 1 en esa fila y negada si vale 0. Ese producto vale 1 solo en esa fila. La función es el OR de todos los minterms.

La notación Σm(3, 5, 6, 7) es la firma compacta de la función: la lista de filas donde vale 1. La fila 3 es 011, es decir A = 0, B = 1, C = 1, de ahí el minterm ~A·B·C.

Producto de sumas: mirar los 0

La versión simétrica parte de las filas con salida 0. Cada una se convierte en un maxterm: un OR de todas las entradas, donde cada entrada aparece directa si vale 0 en esa fila y negada si vale 1 (al revés que el minterm). Ese OR vale 0 solo en esa fila. La función es el AND de todos los maxterms.

Las dos expresiones describen la misma función: todas las filas que no son minterms son maxterms. Con N variables, (cantidad de minterms) + (cantidad de maxterms) = 2^N. Una función con 6 unos y 2 ceros se escribe más corto como producto de sumas.

04 · Las puertas como tablas

Las firmas de dos entradas

Las puertas lógicas que vas a conocer en los Temas 8 a 10 no son más que tablas de dos entradas con nombre. Leerlas como cuatro bits (las salidas para 00, 01, 10 y 11) las convierte en algo que se memoriza de un vistazo:

NAND es exactamente lo opuesto de AND (todos los bits cambiados), igual que NOR de OR y XNOR de XOR. Y XOR tiene una firma que se ve en el espejo: 0110.

Las 16 funciones de dos entradas

Con cuatro filas hay 2⁴ = 16 maneras de elegir las salidas. Las seis puertas de arriba son solo una parte; el resto también existe, aunque algunas parezcan triviales.

Dos son constantes (ignoran las entradas), cuatro dependen de una sola (buffers y NOT) y las diez restantes dependen de las dos. No toda función útil tiene nombre propio: «A y no B» (habilitar con inhibición) aparece seguido en la práctica sin que haya una puerta comercial para ella.

05 · No importa

La X que simplifica

A veces hay filas cuya salida no importa, ya sea porque la combinación de entradas es imposible o porque el sistema nunca mira la salida en ese caso. Esas filas se marcan con X (don't care) y le dan libertad al diseñador: puede elegir 0 o 1 en cada X, según le salga más barato el circuito.

No es un tercer valor

El circuito real siempre da 0 o 1. La X no existe en el silicio: existe en la tabla, como permiso. Cada X es una decisión que se toma al diseñar.

Combinaciones imposibles

Un tanque con dos flotadores (alto y bajo) no puede tener el alto mojado y el bajo seco. Esa fila nunca ocurre, así que su salida es X.

Códigos sin uso

Un dígito BCD usa 10 de las 16 combinaciones de un nibble (Tema 5). Las seis restantes (1010 a 1111) nunca llegan a un decodificador de display bien alimentado: seis filas con X.

Cuánto vale la libertad

Con k filas en X hay 2^k funciones que cumplen la especificación. Los mapas de Karnaugh (Tema 16) las aprovechan para armar grupos más grandes y, por lo tanto, circuitos más chicos.

Para el segmento «a» hay 8 unos, 2 ceros y 6 X: la función es Σm(0, 2, 3, 5, 6, 7, 8, 9) + d(10…15). Cada X que se resuelva a 1 puede completar un grupo; cada una que se resuelva a 0 puede cerrarlo. El Tema 21 usa esto para armar el decodificador de siete segmentos completo.

06 · Método

Del enunciado a la tabla

Casi nunca te dan la tabla: te dan un enunciado en palabras. El trabajo de ingeniería es traducirlo sin perder casos. Este método tiene cuatro pasos y evita la mayoría de los errores.

1. 1
   Nombrar las entradas y fijar qué significa 1.

   H = hay humo; T = temperatura alta; P = puerta cerrada. Importa la polaridad: un botón con resistencia pull-up da 0 al pulsarlo (Tema 11). Escribí «1 = pulsado» solo después de resolver eso.

2. 2
   Dibujar las 2^N filas en orden binario.

   Sin mirar todavía el enunciado. Con tres entradas, ocho filas, de 000 a 111.

3. 3
   Llenar la salida fila por fila.

   Para cada fila, leé el enunciado y decidí. Cuando dudes («¿y si hay humo y calor?»), esa duda es una pregunta al cliente, no un detalle de implementación.

4. 4
   Extraer la función y verificar.

   Minterms, maxterms o simplificación. Después, probá con casos concretos del enunciado: si la tabla contradice un ejemplo, la tabla (o el enunciado) tiene un error.

La función es Σm(3, 4, 5, 6, 7): cinco unos de ocho filas. Los cuatro unos de abajo (H = 1) se agrupan en un solo término, y queda Alarma = H + T·P, que es exactamente el enunciado. Fijate lo que hizo la tabla: obligó a decidir las filas 2 («calor con puerta abierta») y 1 («puerta cerrada sola»), que el enunciado original no mencionaba.

07 · Simulador

Laboratorio: inventar funciones

El simulador te deja armar cualquier tabla de dos o tres entradas, fila por fila, y te devuelve su firma, sus minterms y maxterms, su nombre si lo tiene y una expresión. Cada fila es un botón que alterna entre 0, 1 y X.

• Filas amarillas: las que valen 1, con su minterm a la derecha.
• Filas turquesa: las que valen 0, con su maxterm.
• Filas naranjas: las que valen X (no importa).
• Resultados: la firma de la función, Σm, ΠM y una expresión (simplificada si la función tiene nombre conocido).

Recorrido guiado (6 minutos)

1. 1
   Mirá la tabla inicial (XOR de 2 entradas).

   Firma 0110, Σm(1, 2): solo valen 1 las filas 01 y 10. Fijate en el maxterm de las filas 00 y 11: son las filas donde las dos entradas coinciden.

2. 2
   Apretá «AND» y después «NAND».

   Las dos firmas son opuestas bit a bit: 0001 y 1110. Los minterms de una son los maxterms de la otra. Lo mismo vale para OR y NOR.

3. 3
   Pasá a 3 entradas y apretá «Mayoría».

   Los unos aparecen en 011, 101, 110 y 111: Σm(3, 5, 6, 7). A la derecha de cada fila amarilla se ve el producto que la identifica.

4. 4
   Cambiá la fila 000 de la mayoría a 1.

   La función deja de tener nombre y pasa a «función a medida». Con un solo bit de la tabla cambiado, es otra función: la tabla es la definición completa.

5. 5
   Poné una X en alguna fila.

   Aparece d(…) junto a los minterms y el estado te informa cuántas formas de completar la tabla existen (2^k). Con una sola X ya hay dos funciones válidas.

6. 6
   Volvé a 2 entradas y apretá «Aleatoria» varias veces.

   Salen las 16 funciones posibles. Contá cuántas tienen nombre popular (AND, OR, NAND, NOR, XOR, XNOR) y cuántas son un buffer, un NOT, una constante o una combinación como «A y no B».

Preguntas para pensar

1. Con 2 entradas, programá 0001. ¿Qué puerta es? ¿Y 1001?
2. Con 3 entradas, armá la paridad (XOR de 3). ¿Cuántos unos tiene? ¿En qué filas?
3. Armá una tabla con solo la fila 10 en 1. ¿Tiene nombre? ¿Qué significa en palabras?
4. Partiendo de AND de 3, poné X en la fila 110. ¿Cuántas funciones distintas cumplen esa tabla?

08 · Tablas en código

Generar, leer y comprobar tablas

Una tabla es un objeto que la computadora maneja con comodidad. Estos bloques la generan, extraen las dos formas canónicas, comprueban equivalencias, enumeran las 16 funciones de dos entradas y usan una tabla como test de una implementación.

Paso 1: tabla completa de cualquier función

def bits_de(i, n):
    return [(i >> (n - 1 - k)) & 1 for k in range(n)]


def tabla(f, n=2, nombres="ABC"):
    print(" ".join(nombres[:n]), "| Y")
    mins = []
    for i in range(2 ** n):
        bits = bits_de(i, n)
        y = int(bool(f(*bits)))
        if y:
            mins.append(i)
        print(" ".join(map(str, bits)), "|", y, f"  (fila {i})")
    print(f"Y = Σm({', '.join(map(str, mins))})")
    return mins


tabla(lambda a, b: a & b)
tabla(lambda a, b, c: a + b + c >= 2, n=3)

AND → Σm(3). Mayoría → Σm(3, 5, 6, 7). ¿Qué sale con a ^ b ^ c?

Paso 2: suma de productos y producto de sumas

def bits_de(i, n):
    return [(i >> (n - 1 - k)) & 1 for k in range(n)]


def formas(mins, n, nombres="ABC"):
    v = nombres[:n]

    def minterm(i):
        b = bits_de(i, n)
        return "·".join(v[k] if b[k] else "~" + v[k] for k in range(n))

    def maxterm(i):
        b = bits_de(i, n)
        return "(" + "+".join("~" + v[k] if b[k] else v[k] for k in range(n)) + ")"

    ceros = [i for i in range(2 ** n) if i not in mins]
    print("SOP:", " + ".join(minterm(i) for i in mins) or "0")
    print("POS:", "".join(maxterm(i) for i in ceros) or "1")
    print(f"Σm({', '.join(map(str, mins))})  =  ΠM({', '.join(map(str, ceros))})")


formas([3, 5, 6, 7], 3)
formas([1, 2], 2)

Mayoría: cuatro productos de tres variables o cuatro sumas de tres variables. Fijate que los números de Σm y ΠM no se repiten: juntos suman las 2^N filas.

Paso 3: equivalencias a prueba (De Morgan)

def bits_de(i, n):
    return [(i >> (n - 1 - k)) & 1 for k in range(n)]


def equivalentes(f1, f2, n=2):
    for i in range(2 ** n):
        b = bits_de(i, n)
        if bool(f1(*b)) != bool(f2(*b)):
            print(f"DISTINTAS en la fila {i} {b}: {bool(f1(*b))} vs {bool(f2(*b))}")
            return False
    print("equivalentes en las", 2 ** n, "filas")
    return True


equivalentes(lambda a, b: not (a and b), lambda a, b: (not a) or (not b))
equivalentes(lambda a, b: not (a or b), lambda a, b: (not a) and (not b))
equivalentes(lambda a, b: not (a and b), lambda a, b: (not a) and (not b))

Las dos primeras son las leyes de De Morgan y son equivalentes. La tercera mezcla NAND con NOR y falla en la fila 1. Demostrar una equivalencia = verificar sus 2^N filas.

Paso 4: de los minterms de vuelta a una función

def bits_de(i, n):
    return [(i >> (n - 1 - k)) & 1 for k in range(n)]


def desde_minterms(mins, n):
    def f(*bits):
        fila = sum(b << (n - 1 - k) for k, b in enumerate(bits))
        return int(fila in mins)
    return f


def igual(f1, f2, n):
    return all(f1(*bits_de(i, n)) == f2(*bits_de(i, n)) for i in range(2 ** n))


xor = desde_minterms([1, 2], 2)
print([xor(*bits_de(i, 2)) for i in range(4)])

paridad = desde_minterms([1, 2, 4, 7], 3)
print("paridad == a^b^c:", igual(paridad, lambda a, b, c: a ^ b ^ c, 3))
print("paridad == mayoria:", igual(paridad, lambda a, b, c: int(a + b + c >= 2), 3))

Σm(1, 2) reconstruye el XOR: [0, 1, 1, 0]. La paridad coincide con a ^ b ^ c y no con la mayoría. Σm y la tabla son la misma información.

Paso 5: las 16 funciones de dos entradas

NOMBRES = {
    "0000": "constante 0", "0001": "AND", "0010": "A·~B", "0011": "A",
    "0100": "~A·B", "0101": "B", "0110": "XOR", "0111": "OR",
    "1000": "NOR", "1001": "XNOR", "1010": "~B", "1011": "A+~B",
    "1100": "~A", "1101": "~A+B", "1110": "NAND", "1111": "constante 1",
}

for codigo in range(16):
    firma = format(codigo, "04b")
    mins = [i for i in range(4) if firma[i] == "1"]
    print(f"{codigo:>2} {firma}  {NOMBRES[firma]:<12} Σm({', '.join(map(str, mins))})")

print()
for n in range(1, 7):
    print(f"{n} entradas: {2 ** n:>3} filas, {2 ** (2 ** n):,} funciones")

Las 16 firmas, de 0000 a 1111, se recorren contando en binario. Con 6 entradas ya hay más funciones que granos de arena en una playa grande.

Paso 6: las X de un display BCD

ENCENDIDO = {0, 2, 3, 5, 6, 7, 8, 9}   # segmento «a» encendido
NO_IMPORTA = set(range(10, 16))         # códigos BCD que nunca llegan


def seg_a(i):
    if i in ENCENDIDO:
        return "1"
    return "X" if i in NO_IMPORTA else "0"


print("D C B A | a")
for i in range(16):
    print(f"{i:04b} | {seg_a(i)}")

unos = len(ENCENDIDO)
equis = len(NO_IMPORTA)
print(f"{unos} unos, {16 - unos - equis} ceros, {equis} X")
print(f"formas de completar la tabla: 2 ** {equis} = {2 ** equis}")

8 unos, 2 ceros y 6 X: hay 64 funciones que cumplen la especificación. Karnaugh elegirá la más barata (Tema 16).

Paso 7: la tabla como test de una implementación

def bits_de(i, n):
    return [(i >> (n - 1 - k)) & 1 for k in range(n)]


ESPEC = [0, 0, 0, 1, 1, 1, 1, 1]   # filas H T P = 000 .. 111


def alarma(h, t, p):
    if h:
        return 1
    return int(t and p)


def alarma_con_bug(h, t, p):
    return int(h or t or p)


def verificar(impl, espec, n):
    malas = [i for i in range(2 ** n) if int(impl(*bits_de(i, n))) != espec[i]]
    if malas:
        print(f"{impl.__name__}: FALLA en las filas {malas} {[bits_de(i, n) for i in malas]}")
    else:
        print(f"{impl.__name__}: cumple las {2 ** n} filas")


verificar(alarma, ESPEC, 3)
verificar(alarma_con_bug, ESPEC, 3)

La primera cumple las 8 filas. La segunda confunde «alguno de los tres» con «humo, o calor con puerta cerrada» y falla en las filas 1 y 2: sin mirar el código, la tabla encontró el bug.

09 · Analogía de programador

Tests exhaustivos y lookup tables

La tabla de verdad es una vieja conocida de quien programa, pero con una propiedad rara en el software: aquí el espacio de entradas es tan chico que se puede probar todo.

1. 1
   Tabla = suite de tests completa.

   Si la tabla es el contrato, probar un diseño es recorrer todas las filas, algo imposible para un programa con entradas de 32 bits pero trivial aquí.

2. 2
   Cualquier función cabe en una memoria.

   Una ROM con N líneas de dirección y 1 bit de salida es una tabla de verdad física. Las FPGA hacen casi toda su lógica así: LUT de 4 a 6 entradas programadas con las 16 a 64 salidas.

3. 3
   X = código inalcanzable.

   Marcar una fila como «no importa» es la versión de hardware de decirle al compilador que un caso no ocurre, para que optimice sin cubrirlo.

La diferencia con el software es el costo del error. En un programa, un caso sin cubrir da una excepción o un else silencioso; en un circuito, lo que no pensaste lo decide el cableado. Por eso se escribe la tabla antes de dibujar una sola puerta.

10 · Comprensión

Confusiones frecuentes

11 · Práctica guiada

Ejercicios de tablas

Ejercicio 1: alarma de dos sensores

Suena si hay humo (H) O (temperatura alta (T) Y puerta cerrada (P)). Armá la tabla de 8 filas y sacá los minterms. Verificá con tabla().

Ejercicio 2: paridad de 3 bits

Y = 1 si hay una cantidad impar de unos entre A, B y C. ¿Cuáles son los minterms? Verificá con desde_minterms() y a ^ b ^ c.

Ejercicio 3: De Morgan a prueba

Verificá con equivalentes() que NOT(A OR B) = (NOT A) AND (NOT B). ¿Y que NOT(A AND B) es (NOT A) AND (NOT B)?

Ejercicio 4: luz de pasillo

Una luz se controla desde dos interruptores conmutados (uno en cada extremo del pasillo): cada vez que se cambia cualquiera, la luz cambia. Con ambos abajo está apagada. Armá la tabla. Después, ¿qué pasa con un tercer interruptor?

Ejercicio 5: tanque con X

Un tanque tiene dos flotadores: HI (alto, mojado = 1) y LO (bajo, mojado = 1). Hay que llenarlo (Y = 1) cuando está vacío, es decir con ambos secos. La combinación HI = 1, LO = 0 es físicamente imposible. Armá la tabla de 4 filas con la X y proponé la expresión más simple.

Ejercicio 6: contar libertades

Una especificación de 4 entradas tiene 5 filas en X. ¿Cuántas funciones distintas la cumplen? ¿Cuántas funciones de 4 entradas existen en total?

12 · Síntesis

Ideas para recordar

¿Listo para el Tema 7?

Podés avanzar si sos capaz de responder esto sin mirar:

• Decir cuántas filas tiene la tabla de 5 entradas.
• Escribir de memoria las firmas de AND, OR, XOR, NAND y NOR.
• Sacar los minterms de una tabla de 3 entradas con cuatro unos.
• Explicar la diferencia entre un minterm y un maxterm.
• Dar un ejemplo de combinación que justifique una X.
• Traducir «A o B pero no ambos» a una tabla y nombrar la puerta.

Ya tenés el lenguaje con el que se describe cualquier decisión. Ahora las piezas con las que se construye: en el próximo tema, empezamos por las más simples, NOT, buffer y tri-estado.