Simplificación

01 · Punto de partida

Cada puerta cuesta

Armar una función directo desde su tabla da una suma de minterms: un AND por cada fila con 1, un OR que los junta y los inversores necesarios. Para Σm(1, 2, 3) son tres AND, un OR y dos NOT: seis puertas para lo que en realidad es A + B, una sola. Cada puerta ocupa espacio, consume, agrega retardo y es un punto más donde algo puede fallar.

• ¿Cuándo se pueden fusionar dos minterms y qué desaparece?
• ¿Qué son los implicantes primos y por qué importan?
• ¿Cuándo hay que elegir entre dos soluciones igual de buenas?
• ¿Cómo se aprovechan las filas de «no importa»?
• ¿Qué significa realmente «mínimo»?

02 · Adyacencia

Difieren en uno, se va uno

Dos minterms son adyacentes si difieren en exactamente un bit. Eso es lo que permite fusionarlos con la combinación del Tema 13, A·B + A·~B = A·(B + ~B) = A: la variable que cambia queda multiplicada por (X + ~X) = 1 y desaparece.

Entonces Σm(1, 2, 3) = B + A. El minterm m3 se usó dos veces, una con m1 y otra con m2, y está bien: A + A = A (idempotencia). Reusar un minterm es legal, y de hecho necesario para llegar al mínimo.

Grupos de 2, 4, 8…

Cuando los vecinos a su vez tienen vecinos, los grupos crecen. Un grupo de 2^k minterms adyacentes elimina k variables: cuanto más grande el grupo, menos literales tiene el término.

Solo potencias de dos

Tres minterms no se pueden fusionar «de una»: el grupo tiene que ser de 1, 2, 4, 8… Un conjunto de tres se hace con dos grupos de dos que comparten un minterm.

Vecino por cambio de un bit

m5 (0101) y m4 (0100) son adyacentes; m5 y m6 (0110) no (difieren en dos bits). Con el XOR del Tema 10: a ^ b debe tener un solo uno.

Minterms que no tienen vecinos

Quedan solos con todos sus literales. La paridad (XOR de 3 o más) es el caso extremo: ninguna fila tiene vecinas con 1, no se simplifica nada.

03 · Implicantes

Primos y esenciales

Tres definiciones, todas sencillas, dan nombre a lo que hacés al simplificar:

Implicante

Un producto (un grupo de minterms adyacentes) que, cuando vale 1, garantiza que la función vale 1. Cada minterm es un implicante, y cada fusión de vecinos también.

Implicante primo

Un implicante que no se puede agrandar: no hay un grupo mayor que lo contenga. Son los candidatos a formar el mínimo, porque un grupo más grande siempre es mejor que uno más chico (menos literales).

Implicante primo esencial

Un primo que es el único que cubre algún minterm. Si lo sacás, ese minterm se queda sin cubrir: entra sí o sí.

El procedimiento general es entonces:

1. 1
   Encontrar todos los implicantes primos.

   Fusionar vecinos, luego los vecinos de los vecinos, hasta que no se pueda más.

2. 2
   Tomar los esenciales.

   Los que cubren un minterm que nadie más cubre. Entran siempre.

3. 3
   Cubrir lo que falta con la menor cantidad posible.

   Entre los primos restantes, elegir los que cubran los minterms sin cubrir con el mínimo costo.

4. 4
   Sumar los términos elegidos.

   El resultado es la suma de productos mínima.

El m7 está en los tres primos (reuso), pero m3, m5 y m6 solo en uno cada uno. Resultado: mayoría = A·B + A·C + B·C, con 6 literales y 4 puertas (tres AND y un OR), frente a los 12 literales y 8 puertas de la forma canónica.

04 · Método tabular

Quine-McCluskey, paso a paso

El método de Quine y McCluskey (1956) hace exactamente lo anterior de forma mecánica, sin necesidad de «ver» nada. Es el que implementa un programa. Lo recorremos con una función de 4 variables: Σm(0, 1, 3, 7, 8, 9, 11, 15).

Paso 1: agrupar por cantidad de unos

Dos minterms solo pueden ser adyacentes si la cantidad de unos de sus binarios difiere en uno, así que alcanza con comparar grupos contiguos.

Paso 2: fusionar vecinos (el bit que cambia pasa a «-»)

Paso 3: tabla de cobertura

Se arma una tabla con los primos en las filas y los minterms en las columnas, marcando qué cubre cada uno. Los minterms cubiertos por un solo primo señalan los esenciales.

El m0 y el m8 solo los cubre ~B·~C: esencial. El m7 y el m15 solo los cubre C·D: esencial. Con esos dos primos ya están cubiertos todos los minterms (1, 9 por el primero; 3, 11 por el segundo). El primo ~B·D, aunque es primo, sobra: es redundante.

De 32 literales y 13 puertas (la forma canónica) a 4 literales y 5 puertas (dos AND de dos entradas, un OR y dos inversores). Sin ningún ingenio algebraico.

05 · Casos especiales

Cuando el mínimo no es obvio

Sin esenciales: el caso cíclico

La función Σm(0, 1, 2, 5, 6, 7) tiene seis implicantes primos y ninguno es esencial: cada minterm está cubierto por dos. Hay que elegir, y hay dos soluciones igual de buenas.

Las dos soluciones, ~A·~B + B·~C + A·C y ~A·~C + ~B·C + A·B, tienen 6 literales y 4 puertas. El mínimo existe, pero no es único. A veces conviene elegir la que comparte más términos con otra salida del mismo circuito (Tema 17).

Condiciones de «no importa» (X)

Las filas marcadas con X (Tema 6) se pueden tratar como 0 o como 1, a conveniencia. En la simplificación entran como minterms «comodín»: ayudan a formar grupos más grandes, pero no es obligatorio cubrirlas.

Las seis X (10 a 15) permitieron armar el grupo de ocho A (que cubre 8, 9 y los comodines 10 a 15) y completar BC y BD. El circuito baja de siete a tres puertas, sin inversores. Una cautela: solo se pueden usar las X cuyas combinaciones realmente no ocurren (Tema 6).

La paridad no se simplifica

Σm(1, 2, 4, 7), la paridad de tres bits, no tiene ningún par de minterms adyacentes: cada 1 está rodeado de ceros. Sus cuatro primos son los cuatro minterms. La suma de productos mínima tiene 12 literales y 8 puertas. Un XOR en cadena (Tema 10) la resuelve con dos puertas XOR: la forma «suma de productos» no siempre es la mejor del universo, solo la mejor de su familia.

Producto de sumas: simplificar los ceros

Hay una segunda manera de llegar al mínimo: simplificar la función complementada, es decir, agrupar los ceros, y después aplicar De Morgan (Tema 14). El resultado es un producto de sumas.

Las dos tienen el mismo costo, porque la mayoría es autodual. Para otras funciones, una de las dos formas puede ser bastante más corta: conviene probar ambas cuando hay pocos ceros o pocos unos.

06 · Costo

¿Qué es «mínimo»?

Reducir literales es un buen indicador, pero no es lo único que cuenta. Según el proyecto, «mínimo» puede querer decir cosas distintas:

Dos niveles, el objetivo clásico

La suma de productos mínima es una red de dos niveles (AND-OR, que se convierte en NAND-NAND por el Tema 14): rápida y regular. El costo de buscar un mínimo en literales es un buen sustituto del costo real.

A veces el mínimo en literales no es el más rápido

Una función puede tener una forma de tres niveles con menos literales (por ejemplo, factorizando) y ser más lenta, o al revés. Es un compromiso entre área, retardo y consumo.

Para funciones grandes

Encontrar el mínimo exacto es un problema difícil: la cantidad de implicantes primos crece rápidamente con las variables, y la cobertura mínima es un problema NP-difícil (el mismo que el de minimizar casos de prueba que cubren todos los requisitos). Las herramientas reales usan heurísticas, como el algoritmo Espresso, y no garantizan el mínimo absoluto.

Para vos, hoy

Con hasta cuatro o cinco variables, un método a mano o un programa pequeño resuelve todo. Más allá, se parte la función en bloques (multiplexores, decodificadores, sumadores) y se minimiza cada uno.

07 · Simulador

Laboratorio: minimizador

Definí una función de 2, 3 o 4 variables marcando cada fila de su tabla como 0, 1 o X (no importa), y el simulador ejecuta el método de Quine-McCluskey: encuentra los implicantes primos, los esenciales, elige la cobertura mínima y compara el costo con la forma canónica. Verifica el resultado fila por fila.

• Columnas del gráfico: los minterms. Círculo amarillo lleno = 1, naranja hueco = X, punto gris = 0.
• Filas del gráfico: los implicantes primos. Los puntos marcan lo que cubre cada uno.
• Bordes: verde = elegido para la solución; naranja y «E» = esencial; gris = descartado (redundante).

Recorrido guiado (8 minutos)

1. 1
   Mirá la mayoría de tres (estado inicial).

   Tres primos, los tres esenciales y los tres elegidos. Resultado: A·B + A·C + B·C. El minterm 7 aparece cubierto tres veces (reuso).

2. 2
   Apretá «Σm(1,2,3)».

   Dos variables, dos primos (B y A) y el resultado A + B. De seis puertas a una.

3. 3
   Apretá «Con un primo redundante».

   Aparecen tres primos, pero solo dos se eligen (los esenciales). El tercero (~B·D) queda gris: es primo, pero sobra. Resultado: C·D + ~B·~C, de 32 literales a 4.

4. 4
   Apretá «Cíclica».

   Seis primos y ninguno esencial. El simulador elige tres y avisa que hay otra solución equivalente. El mínimo existe, pero no es único.

5. 5
   Apretá «BCD mayor que 4 (con X)».

   Los círculos naranjas huecos (10 a 15) son los comodines. Resultado: A + B·C + B·D. Ahora marcá a mano esas seis X como 0 y mirá cómo crece el costo.

6. 6
   Apretá «Paridad de 3».

   Cuatro primos, uno por minterm, todos esenciales. El costo de la minimizada es igual al de la canónica: no hay nada que podar.

7. 7
   Armá tu función de 4 variables.

   Elegí 4 variables, poné todo en 0 y tocá las filas (cada clic pasa de 0 a 1 y a X). Probá poner un 1 en las filas 0, 1, 2 y 3: se funden en un único primo, ~A·~B, con 2 literales en lugar de 16. Agregá después un 1 en la fila 15 y fijate que queda solo, con sus 4 literales.

8. 8
   Volvé a la mayoría y cambiá un solo 1 a 0.

   Por ejemplo, quitá el m7. Los minterms 3, 5 y 6 ya no son vecinos entre sí: los tres primos pasan a ser minterms individuales y el costo sube de 6 a 9 literales. Un solo bit de la tabla cambia por completo la forma mínima.

Preguntas para pensar

1. En la mayoría, ¿por qué los tres primos son esenciales?
2. En la función con un primo redundante, ¿por qué ~B·D sobra aunque sea primo?
3. En la cíclica, ¿cuántas soluciones mínimas hay y cuántos literales tiene cada una?
4. ¿Qué ganás con las X del BCD? ¿Qué peligro hay?

08 · Simplificación en código

Quine-McCluskey con 30 líneas

Los bloques implementan el método completo: hallar primos, esenciales y una cobertura mínima exacta, medir el costo, aprovechar las X, pasar a producto de sumas y ver cómo escala el problema con una heurística sobre funciones al azar.

Paso 1: implicantes primos

from itertools import combinations


def primos(unos, dcs, n):
    actual = {format(m, f"0{n}b") for m in set(unos) | set(dcs)}
    primos_ = set()
    while actual:
        siguiente, usados = set(), set()
        for a, b in combinations(sorted(actual), 2):
            difs = [i for i in range(n) if a[i] != b[i]]
            if len(difs) == 1 and "-" not in (a[difs[0]], b[difs[0]]):
                i = difs[0]
                siguiente.add(a[:i] + "-" + a[i + 1:])
                usados.update((a, b))
        primos_ |= actual - usados
        actual = siguiente
    return sorted(primos_)


def cubre(p, m, n):
    b = format(m, f"0{n}b")
    return all(x in ("-", y) for x, y in zip(p, b))


def termino(p, vs="ABCD"):
    t = "·".join(v if x == "1" else "~" + v for v, x in zip(vs, p) if x != "-")
    return t or "1"


CASOS = {
    "mayoría de 3": ([3, 5, 6, 7], [], 3),
    "cíclica": ([0, 1, 2, 5, 6, 7], [], 3),
    "con un primo redundante": ([0, 1, 3, 7, 8, 9, 11, 15], [], 4),
    "paridad de 3": ([1, 2, 4, 7], [], 3),
}
for nombre, (unos, dcs, n) in CASOS.items():
    print(f"{nombre}  Σm{tuple(unos)}")
    for p in primos(unos, dcs, n):
        print(f"   {p}  {termino(p):<8} cubre {[m for m in unos if cubre(p, m, n)]}")

La mayoría tiene 3 primos; la cíclica, 6 (cada minterm en dos); la de 4 variables, 3 (uno redundante); la paridad, 4 (los propios minterms). Cada patrón usa «-» donde la variable desapareció.

Paso 2: esenciales, cobertura mínima y costo

from itertools import combinations


def primos(unos, dcs, n):
    actual = {format(m, f"0{n}b") for m in set(unos) | set(dcs)}
    primos_ = set()
    while actual:
        siguiente, usados = set(), set()
        for a, b in combinations(sorted(actual), 2):
            difs = [i for i in range(n) if a[i] != b[i]]
            if len(difs) == 1 and "-" not in (a[difs[0]], b[difs[0]]):
                i = difs[0]
                siguiente.add(a[:i] + "-" + a[i + 1:])
                usados.update((a, b))
        primos_ |= actual - usados
        actual = siguiente
    return sorted(primos_)


def cubre(p, m, n):
    b = format(m, f"0{n}b")
    return all(x in ("-", y) for x, y in zip(p, b))


def termino(p, vs="ABCD"):
    t = "·".join(v if x == "1" else "~" + v for v, x in zip(vs, p) if x != "-")
    return t or "1"


def esenciales(ps, unos, n):
    esc = set()
    for m in unos:
        cub = [p for p in ps if cubre(p, m, n)]
        if len(cub) == 1:
            esc.add(cub[0])
    return esc


def cobertura_minima(ps, unos, n):
    esc = esenciales(ps, unos, n)
    resto = [m for m in unos if not any(cubre(p, m, n) for p in esc)]
    libres = [p for p in ps if p not in esc]
    for k in range(len(libres) + 1):
        sol = [c for c in combinations(libres, k)
               if all(any(cubre(p, m, n) for p in c) for m in resto)]
        if sol:
            mejor = min(sol, key=lambda c: sum(x != "-" for p in c for x in p))
            return sorted(esc | set(mejor)), esc, len(sol)
    return sorted(esc), esc, 1


def costo(ps):
    lits = sum(x != "-" for p in ps for x in p)
    ands = sum(1 for p in ps if sum(x != "-" for x in p) >= 2)
    ors = 1 if len(ps) > 1 else 0
    negadas = {i for p in ps for i, x in enumerate(p) if x == "0"}
    return lits, ands + ors + len(negadas)


def verifica(elegidos, unos, dcs, n):
    for m in range(2 ** n):
        v = any(cubre(p, m, n) for p in elegidos)
        if m in unos and not v:
            return False
        if m not in unos and m not in dcs and v:
            return False
    return True


CASOS = {
    "mayoría de 3":          ([3, 5, 6, 7], [], 3),
    "cíclica":               ([0, 1, 2, 5, 6, 7], [], 3),
    "primo redundante":      ([0, 1, 3, 7, 8, 9, 11, 15], [], 4),
    "paridad de 3":          ([1, 2, 4, 7], [], 3),
    "BCD > 4, sin usar X":    ([5, 6, 7, 8, 9], [], 4),
    "BCD > 4, aprovechando X": ([5, 6, 7, 8, 9], [10, 11, 12, 13, 14, 15], 4),
}
for nombre, (unos, dcs, n) in CASOS.items():
    ps = primos(unos, dcs, n)
    elegidos, esc, alternativas = cobertura_minima(ps, unos, n)
    canon = [format(m, f"0{n}b") for m in unos]
    l0, g0 = costo(canon)
    l1, g1 = costo(elegidos)
    expr = " + ".join(termino(p) for p in elegidos) or "0"
    print(f"{nombre:<28} {expr}")
    print(f"{'':<28} esenciales={len(esc)} de {len(ps)} primos, {alternativas} cobertura(s) mínima(s) | "
          f"canónica {l0} lit/{g0} puertas -> mínima {l1} lit/{g1} puertas | "
          f"{'ok' if verifica(elegidos, unos, dcs, n) else 'FALLA'}")

La de cuatro variables baja de 32 literales y 13 puertas a 4 y 5, sin usar ingenio. La cíclica muestra 2 coberturas mínimas. Las X del BCD bajan el costo de 9 literales y 7 puertas a 5 y 3. Y todo se verifica contra la tabla original.

Paso 3: producto de sumas simplificando los ceros

from itertools import combinations


def primos(unos, dcs, n):
    actual = {format(m, f"0{n}b") for m in set(unos) | set(dcs)}
    primos_ = set()
    while actual:
        siguiente, usados = set(), set()
        for a, b in combinations(sorted(actual), 2):
            difs = [i for i in range(n) if a[i] != b[i]]
            if len(difs) == 1 and "-" not in (a[difs[0]], b[difs[0]]):
                i = difs[0]
                siguiente.add(a[:i] + "-" + a[i + 1:])
                usados.update((a, b))
        primos_ |= actual - usados
        actual = siguiente
    return sorted(primos_)


def cubre(p, m, n):
    b = format(m, f"0{n}b")
    return all(x in ("-", y) for x, y in zip(p, b))


def suma(p, vs="ABCD"):
    # el producto ~A·~B del complemento pasa a la suma (A + B) de la función (De Morgan)
    lits = [v if x == "0" else "~" + v for v, x in zip(vs, p) if x != "-"]
    return "(" + " + ".join(lits) + ")"


def eval_pos(ps, m, n):
    b = [int(c) for c in format(m, f"0{n}b")]
    return int(all(any((b[i] == 0) if x == "1" else (b[i] == 1)
                       for i, x in enumerate(p) if x != "-") for p in ps))


mayoria = lambda m: int(bin(m).count("1") >= 2)
n = 3
ceros = [m for m in range(2 ** n) if not mayoria(m)]
ps = primos(ceros, [], n)                       # (aquí todos son esenciales)
print("ceros:", ceros, " primos del complemento:", ps)
print("producto de sumas:", "".join(suma(p) for p in ps))
print("coincide con la mayoría en las 8 filas:", all(eval_pos(ps, m, n) == mayoria(m) for m in range(2 ** n)))

Agrupar los ceros (0, 1, 2, 4) da tres primos ~A·~B, ~A·~C y ~B·~C; pasarlos a sumas con De Morgan da (A + B)(A + C)(B + C), igual de buena que A·B + A·C + B·C.

Paso 4: cómo escala (con una heurística)

import random
from itertools import combinations


def primos(unos, dcs, n):
    actual = {format(m, f"0{n}b") for m in set(unos) | set(dcs)}
    primos_ = set()
    while actual:
        siguiente, usados = set(), set()
        for a, b in combinations(sorted(actual), 2):
            difs = [i for i in range(n) if a[i] != b[i]]
            if len(difs) == 1 and "-" not in (a[difs[0]], b[difs[0]]):
                i = difs[0]
                siguiente.add(a[:i] + "-" + a[i + 1:])
                usados.update((a, b))
        primos_ |= actual - usados
        actual = siguiente
    return sorted(primos_)


def cubre(p, m, n):
    b = format(m, f"0{n}b")
    return all(x in ("-", y) for x, y in zip(p, b))


def cobertura_voraz(ps, unos, n):
    cubiertos, elegidos = set(), set()
    for m in unos:                                   # primero los esenciales
        cub = [p for p in ps if cubre(p, m, n)]
        if len(cub) == 1:
            elegidos.add(cub[0])
    cubiertos = {m for m in unos if any(cubre(p, m, n) for p in elegidos)}
    while len(cubiertos) < len(unos):               # después, el que más cubre
        mejor = max((p for p in ps if p not in elegidos),
                    key=lambda p: sum(1 for m in unos if m not in cubiertos and cubre(p, m, n)))
        elegidos.add(mejor)
        cubiertos |= {m for m in unos if cubre(mejor, m, n)}
    return elegidos


rng = random.Random(5)
print(" N  minterms  primos  términos  literales (mínima vs canónica)")
for n in range(3, 7):
    unos = sorted(rng.sample(range(2 ** n), 2 ** (n - 1)))
    ps = primos(unos, [], n)
    elegidos = cobertura_voraz(ps, unos, n)
    lits = sum(x != "-" for p in elegidos for x in p)
    print(f"{n:>2}  {len(unos):>8}  {len(ps):>6}  {len(elegidos):>8}  {lits:>4} vs {len(unos) * n}")

Con la mitad de las filas en 1, la cantidad de primos tiende a crecer con N (los números cambian con la semilla). La cobertura voraz da una solución buena pero no garantiza el mínimo: es el tipo de compromiso que hacen las herramientas reales.

09 · Analogía de programador

DRY en silicio

1. 1
   Fusionar = factorizar.

   Código común afuera del if. Es la misma idea, con una diferencia: acá hay un método que garantiza encontrarlo todo.

2. 2
   Primo esencial = test indispensable.

   Si lo sacás, queda una línea sin cobertura. Los esenciales entran siempre; el resto es una decisión de costo.

3. 3
   Profundidad = latencia.

   En código, anidar de más complica; en hardware, cada nivel de puertas suma retardo.

10 · Comprensión

Confusiones frecuentes

11 · Práctica guiada

Ejercicios de poda

Ejercicio 1: Σm(0, 1, 2) a mano

Fusioná (0, 1) y (0, 2): ¿qué variable desaparece en cada par? Escribí el resultado y verificalo con el simulador.

Ejercicio 2: la mayoría mínima

Con los pares (3, 7), (5, 7) y (6, 7), ¿qué producto da cada uno? Sumalos y verificá las 8 filas.

Ejercicio 3: contar de verdad

Mayoría canónica contra mínima, contando inversores, AND y OR. ¿Cuántas puertas y cuántos chips de la serie 74HC en cada caso?

Ejercicio 4: la función cíclica

Para Σm(0, 1, 2, 5, 6, 7), listá los seis primos y encontrá las dos coberturas mínimas.

Ejercicio 5: el primo que sobra

Para Σm(0, 1, 3, 7, 8, 9, 11, 15) hay tres primos. ¿Cuáles son esenciales y por qué el tercero se puede descartar?

Ejercicio 6: dígito BCD mayor que 4

Con los códigos 10 a 15 como X, ¿cuál es la forma mínima? ¿Y si esos códigos pudieran llegar (error del sensor) y debieran dar 0?

12 · Síntesis

Ideas para recordar

¿Listo para el Tema 16?

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

• Decir cuándo dos minterms son adyacentes y qué pasa al fusionarlos.
• Distinguir un implicante, un primo y un esencial.
• Simplificar Σm(1, 2, 3) y Σm(0, 1, 2) a mano.
• Armar la tabla de cobertura de una función de 4 variables y elegir los esenciales.
• Explicar para qué sirven las X y cuándo es peligroso usarlas.
• Contar las puertas de una forma canónica y de la mínima.

Ya sabés qué buscar. Ahora hay una forma de verlo: reordenando la tabla para que los vecinos queden juntos. En el próximo tema, mapas de Karnaugh.