Teoremas y De Morgan

01 · Punto de partida

Ya lo usaste en el Tema 9

Cuando armaste un OR con tres NAND escribiste A + B = ~(~A·~B). Eso es el segundo teorema de De Morgan leído al revés. Y en programación lo aplicás sin pensar cada vez que negás una condición: !(a && b) es !a || !b. Los teoremas dicen exactamente cómo se «rompe» una barra de negación larga: se niega cada variable y se intercambia AND por OR.

• ¿Cómo se enuncian los dos teoremas, para dos y para N variables?
• ¿Cómo se demuestran sin tabla?
• ¿Qué es una «burbuja» y por qué una NAND se puede dibujar de dos maneras?
• ¿Cómo se complementa una función completa?
• ¿Qué otros teoremas ahorran puertas?

02 · De Morgan

Barra larga, dos caminos

Augustus De Morgan los formuló en el siglo XIX para la lógica. En el álgebra booleana son dos igualdades que se obtienen una de la otra por dualidad (Tema 13):

Con palabras

«No (A y B)» significa «A no o B no»: para que un AND falle basta con que una condición falle. «No (A o B)» significa «ni A ni B»: para que un OR falle tienen que fallar todas. Son las dos intuiciones de la lógica cotidiana, en la jerga del álgebra.

Para N variables

Se rompe de a pares y se generaliza: ~(A·B·C) = ~A + ~B + ~C y ~(A+B+C) = ~A·~B·~C. Se puede probar por inducción, o simplemente con la regla: negar cada término, cambiar el operador.

La regla de las barras

Si una barra cubre a varios términos, al romperla en la parte de arriba cambia el operador y cada término queda con su propia barra. Si ya tenía barra, la doble barra se cancela: ~~A = A.

Demostración algebraica

Para demostrar un teorema sin tabla se usa una propiedad del complemento: el complemento de un elemento es único. Si un elemento X cumple a la vez X + Y = 1 y X·Y = 0, entonces X es el complemento de Y, y no hay otro. Así que para probar que ~A·~B es el complemento de A + B alcanza con mostrar que se suman a 1 y se multiplican a 0.

Por dualidad, la demostración «espejo» da el otro teorema. Y como todo vale para cualquier expresión que se sustituya en A y B, los teoremas se aplican a términos compuestos: ~(X·Y) = ~X + ~Y aun cuando X e Y sean expresiones largas.

03 · Símbolos alternativos

La misma puerta, dos dibujos

Si ~(A·B) = ~A + ~B, entonces una NAND se puede dibujar de dos maneras equivalentes: como un AND con una burbuja a la salida, o como un OR con burbujas en las dos entradas. Es la misma puerta física con otro símbolo. La burbuja representa una negación en cualquier pin (Tema 7), y mover burbujas de un lado a otro de una puerta es aplicar De Morgan en el dibujo.

Empujar burbujas

La técnica se llama bubble pushing y sigue una regla única: una burbuja que atraviesa una puerta cambia su tipo (AND se vuelve OR, OR se vuelve AND). Con ella se transforma un esquema sin redibujar nada:

1. 1
   Identificá una burbuja en la salida de una puerta.

   Por ejemplo, una NAND (AND con burbuja de salida).

2. 2
   Empujala hacia las entradas de la puerta siguiente.

   Al hacerlo, la puerta de la que sale pierde la burbuja (y cambia de tipo) y la siguiente gana burbujas en sus entradas.

3. 3
   Cancelá burbujas dobles.

   Donde se encuentran dos burbujas en un mismo cable, desaparecen (~~X = X). Es lo que convierte un AND-OR en NAND-NAND: las burbujas de la salida del primer nivel se anulan con las de las entradas del segundo.

04 · Más teoremas

Consenso, factorización y la XNOR gratis

Además de De Morgan hay unos pocos teoremas que ahorran puertas y vale la pena reconocer a primera vista. Todos se demuestran con los postulados del Tema 13.

El consenso

El término B·C es redundante porque cuando B·C vale 1, alguno de los otros dos ya vale 1: si A = 1 se cumple A·B; si A = 0 se cumple ~A·C. Dicho de otro modo, B·C queda «cubierto» por los otros. La demostración:

El consenso importa por una razón práctica: aparece cuando se simplifican funciones con Karnaugh (Tema 16) y su omisión es la fuente de los glitches (Tema 28). A veces conviene dejar el término redundante a propósito.

Una XNOR a partir de una XOR

De Morgan sirve para pasar de una puerta a su opuesta sin tablas. Partiendo del XOR del Tema 10:

Se rompe la barra (De Morgan, dos veces), se distribuye (ahora aparece A·~A = 0 y B·~B = 0) y queda la XNOR: «A y B» o «ni A ni B». Se obtiene la igualdad sin mirar ninguna tabla.

05 · Complementar

Cómo se niega una función entera

A veces necesitás el opuesto de una función completa (por ejemplo, la señal activa en bajo de otra activa en alto). Hay una regla mecánica, que es De Morgan aplicado de afuera hacia adentro:

La conexión con la tabla de verdad (Tema 6)

En el Tema 6 viste que una función se puede escribir como suma de minterms (las filas con 1) o como producto de maxterms (las filas con 0). Ahora sabés por qué las dos formas son equivalentes: De Morgan convierte una en la otra.

1. 1
   Mirá las filas con 0.

   Para la mayoría de tres son las filas 0, 1, 2 y 4. La función complementada ~Y vale 1 justo en esas filas: ~Y = m0 + m1 + m2 + m4 (suma de minterms de los ceros).

2. 2
   Complementá de nuevo con De Morgan.

   Y = ~(m0 + m1 + m2 + m4) = ~m0·~m1·~m2·~m4. Cada ~m_i es un OR de literales negados: un maxterm.

3. 3
   Resultado.

   Y = (A + B + C)·(A + B + ~C)·(A + ~B + C)·(~A + B + C) = ΠM(0, 1, 2, 4), la forma que viste en el Tema 6.

Forma normal negativa

Una expresión con las negaciones solo sobre variables (nunca sobre grupos) se dice que está en forma normal negativa. Los compiladores y los solvers la usan como paso previo a muchas transformaciones: es el resultado de aplicar De Morgan hasta que no quedan barras largas. El simulador de este tema hace exactamente eso.

Una advertencia sobre XOR

~(A⊕B) = ~A⊕B = A⊕~B, pero ~A⊕~B = A⊕B. Negar las dos entradas de un XOR no cambia el resultado; negar una sola invierte la salida.

06 · Aplicaciones

Adaptar, leer y refactorizar

Adaptar una función a las puertas que tenés

La transformación de AND-OR a NAND-NAND no siempre es la más económica: la conversión mecánica de un XOR (A·~B + ~A·B) cuesta 2 NAND de primer nivel, 1 final y 2 inversores, es decir, 5 puertas; el diseño ingenioso del Tema 9 lo logra con 4 compartiendo una NAND. Los teoremas dan una receta; simplificar da el mínimo.

Leer señales activas en bajo

Los chips usan señales como ~CS (selección) o ~OE (habilitación de salida), activas en 0 (Temas 7 y 11). ¿Cómo se combinan? Suponé que un dispositivo debe habilitarse cuando ~CS está activo y ~OE está activo, es decir, cuando ambos valen 0, y que su pin de entrada ~EN también es activo en bajo.

Se resuelve con una puerta OR (74HC32), aunque la condición sea «las dos activas» (un «AND» de condiciones). Es De Morgan: en lógica negativa, el OR de las señales es el AND de las condiciones. En el esquema se dibuja como un AND con burbujas en las entradas y en la salida: «~CS activa Y ~OE activa → ~EN activa». El nombre de las señales y el símbolo hablan el mismo idioma.

Refactorizar condiciones en el código

07 · Simulador

Laboratorio: romper barras paso a paso

Escribí una expresión con barras largas y el simulador la reescribe aplicando De Morgan una vez por paso, hasta que las negaciones queden solo sobre variables. Al final comprueba por tabla de verdad que el resultado es equivalente al original. Además puede complementar la expresión (agregarle una barra completa y romperla).

• Sintaxis: variables A a D; + para OR; *, · o yuxtaposición para AND; ~, ! o ' para NOT; paréntesis; 0 y 1.
• Modo «Romper las barras»: normaliza la expresión que escribís.
• Modo «Complementar»: calcula ~(tu expresión) y la lleva a la misma forma.
• Pasos: cada uno nombra la regla aplicada. La tabla de abajo compara «antes» y «después».

Recorrido guiado (7 minutos)

1. 1
   Mirá el ejemplo inicial: ~(A·B).

   Un solo paso: la barra se rompe, el AND pasa a OR y cada variable queda negada. La tabla de abajo no cambia ni un bit.

2. 2
   Probá ~(A·B·C).

   El teorema se aplica a tres términos de una vez: ~A + ~B + ~C. La regla no depende de cuántas variables haya.

3. 3
   Probá ~(A·~B + C).

   Dos barras anidadas: primero se rompe la externa (queda ~(A·~B)·~C) y después la interna (~A + ~~B se cancela a ~A + B). Resultado: (~A + B)·~C.

4. 4
   Probá la XNOR negada: ~(A·B + ~A·~B).

   Termina en (~A + ~B)·(A + B): la XOR, escrita como producto de sumas. Es la demostración de la sección 04 hecha por el simulador.

5. 5
   Cambiá a «Complementar» con una expresión sin barras, por ejemplo A*B+~A*C.

   Agrega la barra y la rompe: (~A + ~B)·(A + ~C). Es el complemento de una suma de productos, un producto de sumas.

6. 6
   Probá la «doble barra y anidada».

   La doble negación se cancela como un paso propio. Fijate que el resultado siempre tiene las negaciones solo sobre variables.

7. 7
   Escribí una expresión propia, con 4 variables.

   Por ejemplo ~(AB + CD) o ~(A + B)(C + D)'. Aunque la forma final cambie por completo, la tabla de verdad de antes y después coincide siempre en las 16 filas.

Preguntas para pensar

1. Rompé ~(A + B·C). ¿Cuántos pasos hacen falta y por qué dos?
2. Complementá A·B + C. ¿Qué forma (suma de productos o producto de sumas) tiene el resultado?
3. ¿Por qué el simulador nunca cambia la columna «Después» de la tabla?
4. ¿Qué pasa si escribís ~~A? ¿Cuánto vale la forma final?

08 · De Morgan en código

Romper, complementar y adaptar con un programa

Estos bloques verifican De Morgan para cualquier cantidad de variables, implementan la reescritura de barras sobre un árbol de expresiones (la misma del simulador), complementan una función a partir de su tabla, comprueban los teoremas de simplificación, validan las equivalencias de burbujas y calculan el costo de una red NAND-NAND.

Paso 1: De Morgan para N variables

from itertools import product


def dm_and(bits):          # ~(x1·x2·...·xn) = ~x1 + ~x2 + ... + ~xn
    return (1 - int(all(bits))) == int(any(1 - b for b in bits))


def dm_or(bits):           # ~(x1+x2+...+xn) = ~x1·~x2·...·~xn
    return (1 - int(any(bits))) == int(all(1 - b for b in bits))


for n in range(1, 6):
    filas = list(product((0, 1), repeat=n))
    print(f"N={n}: {len(filas):>2} filas  ~(AND) = OR de negados: {all(dm_and(f) for f in filas)}   "
          f"~(OR) = AND de negados: {all(dm_or(f) for f in filas)}")

mal = [(a, b) for a, b in product((0, 1), repeat=2) if (1 - (a & b)) != ((1 - a) & (1 - b))]
print("el error clásico ~(A·B) = ~A·~B falla en las filas:", mal)

Los dos teoremas valen de 1 a 5 variables en todas las filas. Repartir la barra sin cambiar el operador falla en 01 y 10.

Paso 2: romper barras sobre un árbol

from itertools import product


def V(n): return ("var", n)
def C(v): return ("const", v)
def NOT(a): return ("not", a)
def AND(*xs): return ("and",) + xs
def OR(*xs): return ("or",) + xs


def ev(e, env):
    t = e[0]
    if t == "var": return env[e[1]]
    if t == "const": return e[1]
    if t == "not": return 1 - ev(e[1], env)
    vals = [ev(x, env) for x in e[1:]]
    return int(all(vals)) if t == "and" else int(any(vals))


def variables(e):
    if e[0] == "var": return {e[1]}
    if e[0] == "const": return set()
    return set().union(*(variables(x) for x in e[1:]))


def equivalentes(l, r):
    vs = sorted(variables(l) | variables(r))
    return all(ev(l, dict(zip(vs, b))) == ev(r, dict(zip(vs, b)))
               for b in product((0, 1), repeat=len(vs)))


def romper(e, neg=False):
    t = e[0]
    if t == "var": return ("not", e) if neg else e
    if t == "const": return ("const", 1 - e[1]) if neg else e
    if t == "not": return romper(e[1], not neg)           # ~~X = X, y la barra baja
    op = t if not neg else ("or" if t == "and" else "and")  # De Morgan: cambia el operador
    return (op,) + tuple(romper(x, neg) for x in e[1:])


def mostrar(e, padre=0):
    t = e[0]
    if t == "var": return e[1]
    if t == "const": return str(e[1])
    if t == "not": return "~" + mostrar(e[1], 3)
    s, prec = (("·".join(mostrar(x, 2) for x in e[1:]), 2) if t == "and"
               else (" + ".join(mostrar(x, 1) for x in e[1:]), 1))
    return f"({s})" if padre > prec else s


A, B, Cc, D = V("A"), V("B"), V("C"), V("D")
CASOS = [
    NOT(AND(A, B)),
    NOT(OR(AND(A, NOT(B)), Cc)),
    NOT(OR(AND(A, B), AND(NOT(A), NOT(B)))),
    NOT(NOT(OR(A, B))),
    NOT(AND(OR(A, B), OR(Cc, NOT(D)))),
]
for e in CASOS:
    r = romper(e)
    print(f"{mostrar(e):<24} =  {mostrar(r):<22} {'ok' if equivalentes(e, r) else 'FALLA'}")

Una sola pasada recursiva lleva la barra hasta las variables: ~(A·~B + C) queda (~A + B)·~C; la doble barra desaparece. Cada resultado se comprueba por tabla contra el original.

Paso 3: de Σm a ΠM con De Morgan

from itertools import product


def V(n): return ("var", n)
def NOT(a): return ("not", a)
def AND(*xs): return ("and",) + xs
def OR(*xs): return ("or",) + xs


def ev(e, env):
    t = e[0]
    if t == "var": return env[e[1]]
    if t == "not": return 1 - ev(e[1], env)
    vals = [ev(x, env) for x in e[1:]]
    return int(all(vals)) if t == "and" else int(any(vals))


def romper(e, neg=False):
    t = e[0]
    if t == "var": return ("not", e) if neg else e
    if t == "not": return romper(e[1], not neg)
    op = t if not neg else ("or" if t == "and" else "and")
    return (op,) + tuple(romper(x, neg) for x in e[1:])


def mostrar(e, padre=0):
    t = e[0]
    if t == "var": return e[1]
    if t == "not": return "~" + mostrar(e[1], 3)
    s, prec = (("·".join(mostrar(x, 2) for x in e[1:]), 2) if t == "and"
               else (" + ".join(mostrar(x, 1) for x in e[1:]), 1))
    return f"({s})" if padre > prec else s


VS = ["A", "B", "C"]
mayoria = lambda a, b, c: int(a + b + c >= 2)


def minterm(i):
    return AND(*[V(v) if (i >> (2 - k)) & 1 else NOT(V(v)) for k, v in enumerate(VS)])


unos = [i for i in range(8) if mayoria(*[(i >> (2 - k)) & 1 for k in range(3)])]
ceros = [i for i in range(8) if i not in unos]
print("Σm =", unos, "  ceros =", ceros)

suma = OR(*[minterm(i) for i in unos])
producto = romper(NOT(OR(*[minterm(i) for i in ceros])))     # Y = ~(minterms de los ceros)
print("SOP:", mostrar(suma))
print("POS:", mostrar(producto))
ok = all(ev(producto, dict(zip(VS, b))) == mayoria(*b) for b in product((0, 1), repeat=3))
print("el producto de maxterms coincide con la mayoría:", ok)

Negar los minterms de los ceros y romper la barra da (A + B + C)·(A + B + ~C)·(A + ~B + C)·(~A + B + C): los maxterms del Tema 6. De Morgan es el puente entre las dos formas canónicas.

Paso 4: teoremas de simplificación y la XNOR gratis

from itertools import product


def eq(f, g, n=3):
    return all(f(*b) == g(*b) for b in product((0, 1), repeat=n))


N = lambda a: 1 - a

TEOREMAS = {
    "A + ~A·B = A + B":                  (lambda a, b, c: a | (N(a) & b), lambda a, b, c: a | b),
    "A·(~A + B) = A·B":                  (lambda a, b, c: a & (N(a) | b), lambda a, b, c: a & b),
    "consenso AB + ~AC + BC = AB + ~AC": (lambda a, b, c: (a & b) | (N(a) & c) | (b & c),
                                          lambda a, b, c: (a & b) | (N(a) & c)),
    "consenso (dual)":                   (lambda a, b, c: (a | b) & (N(a) | c) & (b | c),
                                          lambda a, b, c: (a | b) & (N(a) | c)),
    "AB + ~AC = (A+C)(~A+B)":            (lambda a, b, c: (a & b) | (N(a) & c),
                                          lambda a, b, c: (a | c) & (N(a) | b)),
    "~(A⊕B) = (~A+B)(A+~B)":             (lambda a, b, c: N(a ^ b), lambda a, b, c: (N(a) | b) & (a | N(b))),
    "~(A⊕B) = AB + ~A~B":                (lambda a, b, c: N(a ^ b), lambda a, b, c: (a & b) | (N(a) & N(b))),
    "~A⊕~B = A⊕B":                       (lambda a, b, c: N(a) ^ N(b), lambda a, b, c: a ^ b),
    "falsa: ~(A⊕B) = ~A⊕~B":             (lambda a, b, c: N(a ^ b), lambda a, b, c: N(a) ^ N(b)),
}
for nombre, (f, g) in TEOREMAS.items():
    print(f"{'vale ' if eq(f, g) else 'FALLA'}  {nombre}")

nand = lambda a, b: 1 - (a & b)
filas = [(a, b, c) for a, b, c in product((0, 1), repeat=3)
         if nand(nand(a, b), c) != nand(a, nand(b, c))]
print("NAND no es asociativa; las dos agrupaciones difieren en:", filas)

Todas valen salvo la que está marcada como falsa (negar una sola entrada del XOR invierte la salida; negar las dos no cambia nada). Y ojo: las NAND no se asocian, no se puede armar una NAND de tres entradas encadenando dos de dos.

Paso 5: burbujas y señales activas en bajo

from itertools import product

N = lambda a: 1 - a

EQUIV = {
    "NAND(A,B) = OR(~A,~B)":   (lambda a, b: N(a & b), lambda a, b: N(a) | N(b)),
    "NOR(A,B)  = AND(~A,~B)":  (lambda a, b: N(a | b), lambda a, b: N(a) & N(b)),
    "AND(A,B)  = NOR(~A,~B)":  (lambda a, b: a & b,   lambda a, b: N(N(a) | N(b))),
    "OR(A,B)   = NAND(~A,~B)": (lambda a, b: a | b,   lambda a, b: N(N(a) & N(b))),
}
for nombre, (f, g) in EQUIV.items():
    ok = all(f(a, b) == g(a, b) for a, b in product((0, 1), repeat=2))
    print(f"{'vale' if ok else 'FALLA'}  {nombre}")

print()
print("~CS ~OE | ~EN = ~CS + ~OE")
for cs_n in (0, 1):
    for oe_n in (0, 1):
        en_n = cs_n | oe_n
        print(f"  {cs_n}   {oe_n}  |  {en_n}      {'ACTIVO (ambas activas)' if en_n == 0 else 'inactivo'}")

Las cuatro equivalencias del símbolo con burbujas valen. Con señales activas en bajo, el OR es el «AND de las condiciones»: la salida baja solo cuando las dos entradas están bajas.

Paso 6: costo de una red NAND-NAND

from itertools import product


def costo_nand_nand(productos):
    # un NAND por producto + un NAND final + un inversor por cada variable negada
    negadas = {v for p in productos for v, val in p if val == 0}
    return len(productos) + 1 + len(negadas)


def red(productos):
    def f(env):
        nivel1 = [1 - int(all(env[v] == val for v, val in p)) for p in productos]
        return 1 - int(all(nivel1))
    return f


FUNCIONES = {
    "mayoría AB+AC+BC": ([[("A", 1), ("B", 1)], [("A", 1), ("C", 1)], [("B", 1), ("C", 1)]],
                         lambda e: int(e["A"] + e["B"] + e["C"] >= 2)),
    "A·B + C·D":        ([[("A", 1), ("B", 1)], [("C", 1), ("D", 1)]],
                         lambda e: (e["A"] & e["B"]) | (e["C"] & e["D"])),
    "XOR A~B + ~AB":    ([[("A", 1), ("B", 0)], [("A", 0), ("B", 1)]],
                         lambda e: e["A"] ^ e["B"]),
}
for nombre, (prods, real) in FUNCIONES.items():
    vs = sorted({v for p in prods for v, _ in p})
    ok = all(red(prods)(dict(zip(vs, b))) == real(dict(zip(vs, b)))
             for b in product((0, 1), repeat=len(vs)))
    print(f"{nombre:<18} NAND-NAND: {costo_nand_nand(prods)} puertas   {'ok' if ok else 'FALLA'}")
print("referencia: el XOR mínimo con NAND de 2 entradas usa 4 (comparte una NAND, Tema 9)")

La conversión mecánica da 4 puertas para la mayoría, 3 para A·B + C·D y 5 para el XOR. El XOR del Tema 9 usa 4: De Morgan da una receta correcta, pero no necesariamente la más barata.

09 · Analogía de programador

Refactor de condiciones

1. 1
   De Morgan = lo que ya hacés.

   Al negar una condición compuesta lo aplicás sin pensar. En silicio, además, ahorra chips y reduce la cantidad de inversores.

2. 2
   Absorción = linter.

   a || (!a && b) se reescribe a || b: el linter lo sugiere; en el circuito se cablea una puerta menos.

3. 3
   Símbolos alternativos = nombres legibles.

   Elegir la forma que se lee mejor es como nombrar bien una función booleana: el resultado es el mismo, pero el lector entiende la intención.

10 · Comprensión

Confusiones frecuentes

11 · Práctica guiada

Ejercicios de transformación

Ejercicio 1: NOR solo con NAND

Escribí Y = ~(A + B) usando solo NAND. ¿Cuántas puertas necesitás? Contrastalo con la tabla de costos del Tema 9.

Ejercicio 2: complementar

Complementá y llevá a forma de negaciones sobre variables: ~(A·~B + C) y ~((A+B)·(C+~D)). Verificá con el simulador.

Ejercicio 3: simplificar con absorción

Reducí F = A + ~A·B + ~A·~B·C. Contá las puertas antes y después.

Ejercicio 4: leer un esquema mixto

¿Qué función hace un OR dibujado con burbujas en las dos entradas y sin burbuja en la salida? ¿Y un AND con burbujas en las entradas? ¿Y un AND con burbujas en las entradas y en la salida?

Ejercicio 5: habilitación activa en bajo

Un dispositivo se habilita (~EN = 0) cuando ~CS y ~OE valen 0 a la vez. ¿Qué puerta usás? ¿Cómo la dibujás en el esquema? ¿Y si además hubiera una tercera señal ~WR que también debe estar activa?

Ejercicio 6: la NAND no se asocia

Comprobá que NAND(NAND(A,B),C) y NAND(A,NAND(B,C)) no son iguales. Encontrá una fila que lo muestre y compará con NAND de 3 entradas.

12 · Síntesis

Ideas para recordar

¿Listo para el Tema 15?

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

• Enunciar los dos teoremas de De Morgan sin cambiar el operador de lugar.
• Complementar A·B + ~C y dejar las negaciones solo sobre variables.
• Dibujar una NAND como OR con burbujas en las entradas.
• Convertir A·B + C·D en una red de NAND.
• Decir por qué ~(A⊕B) no es ~A⊕~B.
• Combinar dos señales activas en bajo para obtener una habilitación activa en bajo.

Ya tenés todas las herramientas de transformación. Ahora hay que usarlas con método para encontrar la expresión más corta de una función: en el próximo tema, simplificación.