Álgebra booleana

01 · Punto de partida

Tablas que caben en el bolsillo

Mirá esta condición que alguien escribió en un programa: if (listo || (!listo && habilitado)). ¿Se puede escribir más corta? Sí: if (listo || habilitado). La tabla de verdad con dos variables te lo confirma en cuatro filas. Pero en un circuito con diez entradas la tabla tiene 1024 filas, y nadie la dibuja a mano. Lo que se hace es transformar la expresión con reglas, igual que transformás una ecuación en álgebra.

• ¿Cuáles son las reglas base, las que se aceptan sin demostrar?
• ¿Qué es la dualidad y por qué regala el doble de teoremas?
• ¿Cómo se deriva, por ejemplo, la absorción A + A·B = A desde esas reglas?
• ¿Cuál es la precedencia de los operadores?
• ¿Cuándo conviene usar una tabla y cuándo el álgebra?

02 · Postulados

Las reglas que se aceptan sin demostración

Un álgebra booleana es un conjunto con dos operaciones binarias (suma + y producto ·), una unaria (complemento ~) y dos elementos distintos, 0 y 1, que cumplen un conjunto de reglas. En 1904 Edward Huntington propuso una lista mínima. Se las llama postulados: no se demuestran, se asumen, y todo el resto se deduce de ellas.

Qué se asume y qué no

Estos ocho enunciados son los cimientos: se aceptan. Otros que ya usaste en el Tema 8 (dominancia A+1 = 1, idempotencia A+A = A, absorción A+A·B = A, asociativa) no son postulados: se derivan de estos, como vas a ver en la sección 04.

La distributiva «rara»

En el álgebra común, el producto se distribuye sobre la suma pero no al revés: 2 + 3·4 ≠ (2+3)·(2+4). En el álgebra booleana la suma también se distribuye sobre el producto: A + B·C = (A+B)·(A+C). No es un error: es lo que hace al álgebra booleana simétrica. Convence más verificarla por tabla (8 filas) que creerla.

Existen 0 y 1, y son distintos

Parece obvio, pero es parte de la definición: sin dos elementos distintos todo colapsaría. Con el complemento, 0 y 1 se corresponden: ~0 = 1 y ~1 = 0.

Por qué funciona con circuitos

Los postulados valen en cualquier modelo que los cumpla. Los interruptores en serie y en paralelo (Tema 8), las puertas lógicas, los conjuntos con unión e intersección, y los booleanos de tu lenguaje de programación son todos modelos del mismo álgebra.

03 · Dualidad

Dos teoremas por uno

Mirá la tabla de postulados: cada fila tiene dos columnas que se corresponden. Eso no es casualidad. El principio de dualidad dice:

Por qué es válido: los postulados vienen en pares duales, así que cualquier demostración construida con ellos se puede «espejar» paso a paso y da una demostración de la igualdad dual. Cada teorema que probás viene con un gemelo gratis.

Cómo se dualiza

Reemplazá cada + por · y viceversa, cada 0 por 1 y viceversa. Las variables (A, B, C) y sus complementos (~A) no cambian. Conservá los paréntesis.

Dual no es complemento

El dual de A + 0 = A es A · 1 = A. No es la negación de la igualdad ni se obtiene complementando las variables. Es otra igualdad, de otra forma, igualmente verdadera.

Lo que no cambia

Cuando negás una expresión completa, el NOT se queda donde está y se dualiza lo de adentro. Es el mecanismo detrás de los teoremas de De Morgan (Tema 14).

04 · Teoremas

Derivar sin tablas

Una demostración algebraica es una cadena de igualdades. En cada paso reemplazás una parte de la expresión por otra equivalente y anotás qué postulado o teorema usaste. Veamos las cuatro derivaciones fundamentales.

Dominancia: A + 1 = 1

Idempotencia: A + A = A

Absorción: A + A·B = A

Un resultado muy útil: A + ~A·B = A + B

Esta última es oro puro: elimina una variable negada. En el ejemplo del inicio, listo || (!listo && habilitado) es A + ~A·B con A = listo y B = habilitado, y se reduce a listo || habilitado. Una puerta de menos.

05 · Notación

Quién opera primero (y cómo se escribe)

La precedencia del álgebra booleana imita la de la aritmética: el complemento va primero (como el menos unario), después el producto (como la multiplicación) y al final la suma. Por eso A + ~A·B se lee A + ((~A)·B).

El paréntesis no cuesta

Escribí los paréntesis aunque sobren. El que lee tu expresión (vos en seis meses) no tiene que recordar la tabla de precedencias.

Tres trampas de lenguajes

(1) En Python, ~1 vale −2, no 0: el ~ es negación bit a bit sobre enteros, no sobre booleanos. Para un bit usá 1 - a o not a. (2) En C y Python, a & b == c se evalúa como a & (b == c), porque == tiene mayor precedencia que &. (3) && corta la evaluación; & no.

Convenciones de escritura

En este curso: + para OR, · o yuxtaposición (AB) para AND, ~ para NOT, ⊕ para XOR. Con la comilla (A') o la barra superior se escribe lo mismo.

06 · Estrategias

Cómo demostrar (o refutar) una identidad

Frente a una igualdad que alguien afirma, hay cuatro caminos. Elegir bien ahorra horas.

Una fila refuta, mil filas no demuestran

Probar con un caso que da bien no prueba nada. Basta una sola fila donde los dos lados difieran para tirar una «identidad». En cambio, para confirmarla hay que cubrir todas las filas (o derivarla).

Trucos para elegir el paso

Buscá A y ~A juntos (complemento). Buscá un factor común (distributiva, de las dos formas). Buscá términos que contengan a otro (absorción). Y si te trabás, expandí primero: multiplicar un término por (B + ~B) = 1 introduce una variable que a veces permite un grupo mayor.

Expansión de Shannon

Toda función de A se puede partir según el valor de una variable: f = A·f(1) + ~A·f(0), donde f(1) y f(0) son la misma función con A fijada en 1 o en 0. Por ejemplo, la mayoría de tres es A·(B + C) + ~A·B·C. Es la idea detrás del multiplexor (Tema 18): A elige entre dos funciones más simples.

07 · Simulador

Laboratorio: probador de identidades

Escribí dos expresiones con las variables A, B, C y D, y el simulador las evalúa en todas las filas de la tabla de verdad y te dice si son equivalentes. Si no lo son, marca la primera fila que las separa. Podés calcular el dual de ambas y comprobar que el veredicto no cambia.

• Sintaxis: + para OR; *, · o yuxtaposición para AND (AB); ~ o ! delante, o ' detrás, para NOT; 0 y 1; paréntesis.
• Precedencia: NOT primero, después AND, al final OR. A+B*C es A + (B·C).
• Tabla: filas verdes: los dos lados coinciden. Filas rojas: la identidad falla en esa fila.

Recorrido guiado (7 minutos)

1. 1
   Mirá la identidad inicial.

   A + B·C contra (A+B)·(A+C): la distributiva «rara». Las ocho filas se ven verdes. Una igualdad que en aritmética sería falsa vale en booleana.

2. 2
   Apretá «Calcular el dual».

   Los dos lados se reescriben intercambiando + y ·: A·(B+C) y A·B + A·C, la distributiva común. El veredicto sigue siendo «equivalentes». La dualidad regala el teorema gemelo.

3. 3
   Probá «Absorción» y después su dual.

   A + A·B = A pasa a A·(A+B) = A. Una variable, una constante: dos filas y dos lados verdes en cada una.

4. 4
   Probá «A + ~A·B = A + B».

   El teorema de la sección 04, que elimina una negación. La fila donde A = 1 coincide trivialmente; la importante es A = 0.

5. 5
   Probá «Una falsa»: A·(B+C) contra A·B + C.

   Parece una distributiva, pero no lo es. Aparecen filas rojas y el primer contraejemplo (A = 0 y C = 1). Una sola fila alcanza para refutarla.

6. 6
   Probá «Consenso» con tres variables.

   A·B + ~A·C + B·C contra A·B + ~A·C: coinciden en las ocho filas. El término B·C es redundante, un resultado que se desarrolla en el Tema 14.

7. 7
   Escribí tu propia identidad.

   Por ejemplo, (A+B)(A+~B) contra A, o AB'+A'B contra A+B (esta última es falsa: es el XOR). Podés usar yuxtaposición y el apóstrofo.

Preguntas para pensar

1. Probá A + A·B = A. ¿Cuántas filas tiene la tabla y cuál es su dual?
2. ¿Qué identidad de las precargadas usa 3 variables y cuál 2? ¿Cuántas filas tiene cada una?
3. Inventá una falsa (por ejemplo, A + 1 = A) y pasala por el probador. ¿Qué fila falla?
4. ¿Por qué el dual de una identidad falsa también es falso?

08 · Álgebra en código

Verificar, dualizar y demostrar con un programa

Estos bloques hacen en Python lo que el simulador hace en pantalla: verifican los postulados y los teoremas por fuerza bruta, implementan la dualidad sobre un árbol de expresiones, comprueban paso a paso una derivación algebraica, demuestran la expansión de Shannon y muestran dos trampas clásicas (la «cancelación» y los operadores de los lenguajes). Al final, cuánto tarda la fuerza bruta cuando crecen las variables.

Paso 1: postulados y teoremas, comprobados

from itertools import product

N = lambda a: 1 - a      # NOT sobre un bit

LEYES = {
    "P1 conmutativa +          A+B = B+A":      lambda a, b, c: (a | b) == (b | a),
    "P1 conmutativa ·          A·B = B·A":      lambda a, b, c: (a & b) == (b & a),
    "P2 neutro +               A+0 = A":        lambda a, b, c: (a | 0) == a,
    "P2 neutro ·               A·1 = A":        lambda a, b, c: (a & 1) == a,
    "P3 distributiva           A(B+C)":         lambda a, b, c: (a & (b | c)) == ((a & b) | (a & c)),
    "P3 distributiva «rara»    A+BC":           lambda a, b, c: (a | (b & c)) == ((a | b) & (a | c)),
    "P4 complemento +          A+~A = 1":       lambda a, b, c: (a | N(a)) == 1,
    "P4 complemento ·          A·~A = 0":       lambda a, b, c: (a & N(a)) == 0,
    "T  dominancia             A+1 = 1":        lambda a, b, c: (a | 1) == 1,
    "T  idempotencia           A+A = A":        lambda a, b, c: (a | a) == a,
    "T  absorción              A+AB = A":       lambda a, b, c: (a | (a & b)) == a,
    "T  absorción (dual)       A(A+B) = A":     lambda a, b, c: (a & (a | b)) == a,
    "T  A+~AB = A+B":                           lambda a, b, c: (a | (N(a) & b)) == (a | b),
    "T  combinación            AB+A~B = A":     lambda a, b, c: ((a & b) | (a & N(b))) == a,
    "T  involución             ~~A = A":        lambda a, b, c: N(N(a)) == a,
    "T  asociativa +           (A+B)+C":        lambda a, b, c: ((a | b) | c) == (a | (b | c)),
    "T  consenso":                              lambda a, b, c: ((a & b) | (N(a) & c) | (b & c)) == ((a & b) | (N(a) & c)),
    "falsa: A+1 = A":                           lambda a, b, c: (a | 1) == a,
}

for nombre, ley in LEYES.items():
    filas = list(product((0, 1), repeat=3))
    ok = sum(1 for f in filas if ley(*f))
    print(f"{'vale ' if ok == len(filas) else 'FALLA'} {nombre}   ({ok}/{len(filas)})")

Todas valen en las 8 filas excepto la última, trampa deliberada que falla en la mitad de ellas. Las leyes con menos variables se prueban igual con tres: las que no usan B o C simplemente las ignoran.

Paso 2: dualidad sobre un árbol de expresiones

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 dual(e):
    t = e[0]
    if t == "var": return e
    if t == "const": return ("const", 1 - e[1])
    if t == "not": return ("not", dual(e[1]))
    return (("or" if t == "and" else "and"),) + tuple(dual(x) for x in e[1:])


def equivalentes(l, r):
    vs = sorted(variables(l) | variables(r))
    for bits in product((0, 1), repeat=len(vs)):
        env = dict(zip(vs, bits))
        if ev(l, env) != ev(r, env):
            return False
    return True


A, B, Cc = V("A"), V("B"), V("C")
IDENTIDADES = {
    "distributiva rara  A+B·C = (A+B)(A+C)": (OR(A, AND(B, Cc)), AND(OR(A, B), OR(A, Cc))),
    "absorción          A+A·B = A":          (OR(A, AND(A, B)), A),
    "idempotencia       A+A = A":            (OR(A, A), A),
    "útil               A+~A·B = A+B":       (OR(A, AND(NOT(A), B)), OR(A, B)),
    "falsa              A+B = A·B":          (OR(A, B), AND(A, B)),
    "falsa              A·(B+C) = A·B+C":    (AND(A, OR(B, Cc)), OR(AND(A, B), Cc)),
}
for nombre, (l, r) in IDENTIDADES.items():
    print(f"{nombre:<40} válida={equivalentes(l, r)!s:<5}  su dual válida={equivalentes(dual(l), dual(r))}")

En cada fila las dos últimas columnas coinciden: una identidad y su dual son ambas verdaderas o ambas falsas. Es la dualidad en acción (el dual del dual es la identidad original).

Paso 3: un verificador de demostraciones

from itertools import product

N = lambda a: 1 - a


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


def verificar(titulo, cadena, n):
    print(titulo)
    for (_, f0), (txt1, f1) in zip(cadena, cadena[1:]):
        print(f"   {txt1:<38} {'✓' if paso_valido(f0, f1, n) else '✗ paso inválido'}")


verificar("A + ~A·B = A + B", [
    ("dado",                  lambda a, b: a | (N(a) & b)),
    ("(A+~A)·(A+B)  [distr.]",  lambda a, b: (a | N(a)) & (a | b)),
    ("1·(A+B)  [complemento]",  lambda a, b: 1 & (a | b)),
    ("A+B  [neutro]",           lambda a, b: a | b),
], 2)

verificar("una demostración con un error", [
    ("dado: A·B + A·~B",      lambda a, b: (a & b) | (a & N(b))),
    ("A·(B+~B)  [distr.]",    lambda a, b: a & (b | N(b))),
    ("A·(B+B)  [¡error!]",    lambda a, b: a & (b | b)),
    ("A·B",                   lambda a, b: a & b),
], 2)

La primera cadena es correcta en los tres pasos. La segunda se rompe en el segundo: cambiar B+~B por B+B no es un paso permitido (en el primero valía 1; en el segundo vale B). Un verificador de pasos atrapa errores que a simple vista pasan.

Paso 4: la expansión de Shannon

from itertools import product


def mayoria(a, b, c):
    return int(a + b + c >= 2)


def shannon(f, i):
    # f = x·f(x=1) + ~x·f(x=0), respecto de la variable de índice i
    def g(*bits):
        x = bits[i]
        con1 = bits[:i] + (1,) + bits[i + 1:]
        con0 = bits[:i] + (0,) + bits[i + 1:]
        return (x & f(*con1)) | ((1 - x) & f(*con0))
    return g


for i, nombre in enumerate("ABC"):
    g = shannon(mayoria, i)
    ok = all(g(*b) == mayoria(*b) for b in product((0, 1), repeat=3))
    print(f"expansión respecto de {nombre}: {'vale' if ok else 'FALLA'}")

print("f(A=1, B, C):", [mayoria(1, b, c) for b in (0, 1) for c in (0, 1)], " = B + C")
print("f(A=0, B, C):", [mayoria(0, b, c) for b in (0, 1) for c in (0, 1)], " = B·C")

Con A = 1 la mayoría se reduce a B + C ([0,1,1,1]); con A = 0, a B·C ([0,0,0,1]). Es decir, mayoría = A·(B + C) + ~A·B·C: A elige entre dos funciones más chicas (un multiplexor, Tema 18).

Paso 5: no hay cancelación, y las trampas del lenguaje

from itertools import product

print("¿A+B = A+C implica B = C?")
for a, b, c in product((0, 1), repeat=3):
    if (a | b) == (a | c) and b != c:
        print(f"   contraejemplo: A={a} B={b} C={c}   A+B={a | b} = A+C={a | c}, pero B≠C")

print("¿A·B = A·C implica B = C?")
for a, b, c in product((0, 1), repeat=3):
    if (a & b) == (a & c) and b != c:
        print(f"   contraejemplo: A={a} B={b} C={c}   A·B={a & b} = A·C={a & c}, pero B≠C")

print()
print("~1 =", ~1, "  ~0 =", ~0, "  1 - 1 =", 1 - 1, "  not 1 =", not 1)
a, b, c = 0, 0, 0
print("a & b == c se lee a & (b == c):", a & b == c, "   (a & b) == c:", (a & b) == c)

Cuando A = 1 la suma vale 1 sin importar B o C; cuando A = 0 el producto vale 0 sin importar B o C: por eso no se puede «cancelar». Y en Python, ~ sobre un entero da −2 o −1, no 0 o 1: para un bit se usa 1 - a.

Paso 6: cuándo la fuerza bruta deja de servir

EVAL_POR_S = 1_000_000          # filas que se evalúan por segundo (supuesto)

print("variables           filas   tiempo")
for n in (4, 8, 16, 24, 32, 40, 64):
    filas = 2 ** n
    seg = filas / EVAL_POR_S
    if seg < 1:
        t = f"{seg * 1000:.3g} ms"
    elif seg < 3600:
        t = f"{seg:.3g} s"
    elif seg < 86400:
        t = f"{seg / 3600:.3g} h"
    elif seg < 86400 * 365:
        t = f"{seg / 86400:.3g} días"
    else:
        t = f"{seg / (86400 * 365):.3g} años"
    print(f"{n:>9} {filas:>20,}   {t}")

Hasta unas 20 variables la tabla es instantánea; con 32 ya lleva más de una hora; con 40, días; con 64, siglos. Por eso los circuitos reales se verifican con álgebra, solvers SAT y verificación formal, no con tablas.

09 · Analogía de programador

Axiomas, refactors y optimizaciones

1. 1
   Postulados = axiomas.

   Se asumen y se comprueban en el modelo; todo lo demás se deriva. Cambiar de modelo (circuitos, conjuntos, booleanos de un lenguaje) no cambia las reglas.

2. 2
   Absorción = simplificar condiciones.

   El linter ya lo hace en software; en silicio cada puerta que se elimina ahorra superficie, consumo y retardo.

3. 3
   Dualidad = simetría.

   Una demostración, dos resultados. Como De Morgan en conjuntos, o la dualidad entre primal y dual en optimización.

Una diferencia importante: en un compilador, simplificar una condición suele ser opcional; en hardware, cada puerta es un componente físico. El álgebra no es una elegancia: es dinero.

10 · Comprensión

Confusiones frecuentes

11 · Práctica guiada

Ejercicios de reglas

Ejercicio 1: absorción a mano

Demostrá A + A·B = A factorizando (sin tabla) e indicá qué postulado o teorema usás en cada paso.

Ejercicio 2: duales

Escribí el dual de A + ~A = 1; de A·(A + B) = A; y de A + B·C = (A+B)·(A+C). Verificá uno con el probador de identidades.

Ejercicio 3: cazar la falsa

¿Valen A·(B+C) = A·B + C? ¿Y A·B + A·C = A·(B+C)? ¿Y (A+B)·(A+C) = A + B·C? Para la que falle, encontrá una fila que la refute.

Ejercicio 4: simplificar con la distributiva rara

Simplificá (A + B)·(A + ~B) y A + ~A·B·C. Indicá cada paso.

Ejercicio 5: condiciones en código

Simplificá if (listo || (!listo && habilitado)) y if (a && b || a && !b). ¿Cuántas operaciones lógicas se ahorran?

Ejercicio 6: idempotencia desde los postulados

Demostrá A + A = A usando solo los postulados P1 a P4 (no vale usar la idempotencia ni la absorción).

12 · Síntesis

Ideas para recordar

¿Listo para el Tema 14?

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

• Enunciar los cuatro pares de postulados y sus duales.
• Escribir el dual de una igualdad dada.
• Demostrar la absorción A + A·B = A con pasos justificados.
• Simplificar A + ~A·B y (A + B)·(A + ~B).
• Explicar por qué no se puede «cancelar» A en A + B = A + C.
• Decir por qué ~a en Python no es la negación de un booleano.

Ya tenés las reglas del juego. Ahora vienen los teoremas más famosos, los que dan vuelta una negación completa y permiten construir todo con NAND: en el próximo tema, teoremas y De Morgan.