Postulados y teoremas del álgebra de Boole, con ejemplos

Postulados y teoremas del álgebra de Boole, con ejemplos
Índice
  1. Notación que usamos
  2. Postulados del álgebra de Boole
  3. El principio de dualidad
  4. Teoremas fundamentales
    1. Demostración de la idempotencia a partir de los postulados
    2. Ley de absorción
    3. Teorema del consenso
  5. Comprobar un teorema con una tabla de verdad
  6. Ejemplos de simplificación paso a paso
    1. Ejemplo 1
    2. Ejemplo 2
    3. Ejemplo 3, con De Morgan
  7. Errores habituales
  8. Un poco de historia
  9. Relación con otros resultados
  10. Preguntas frecuentes
    1. ¿Qué diferencia hay entre un postulado y un teorema del álgebra de Boole?
    2. ¿Qué dice la ley de absorción?
    3. ¿Qué es el teorema del consenso?
    4. ¿Cómo compruebo que una simplificación está bien?
  11. Fuentes

Actualizado el

El álgebra de Boole es el cálculo con dos valores, 0 y 1 (falso y verdadero), y tres operaciones: suma lógica (OR), producto lógico (AND) y complemento (NOT). Sus teoremas son las reglas que permiten transformar y simplificar expresiones lógicas, y son la base del diseño de circuitos digitales: una expresión más corta significa menos puertas lógicas.

Notación que usamos

  • A + B: suma lógica (OR). Vale 1 si al menos una variable vale 1.
  • A·B o AB: producto lógico (AND). Vale 1 solo si las dos valen 1.
  • A': complemento (NOT). Cambia 0 por 1 y 1 por 0. En muchos libros se escribe con una barra encima.

Ojo: aquí 1 + 1 = 1. No es la suma de los números enteros.

Postulados del álgebra de Boole

Un postulado es una regla que se acepta sin demostración y a partir de la cual se deduce todo lo demás (si te interesa la diferencia, la explicamos en qué es un teorema y en qué se diferencia de un axioma). La lista habitual en los cursos de electrónica digital es la de Edward Huntington:

PostuladoForma con +Forma con ·
P1. CierreA + B está en el conjuntoA·B está en el conjunto
P2. Elemento neutroA + 0 = AA·1 = A
P3. ConmutativaA + B = B + AA·B = B·A
P4. DistributivaA + B·C = (A + B)·(A + C)A·(B + C) = A·B + A·C
P5. ComplementoA + A' = 1A·A' = 0
P6. Al menos dos elementosExisten x, y con x ≠ y(el mismo)

Fíjate en la distributiva de la suma respecto del producto, A + BC = (A + B)(A + C). En el álgebra de los números es falsa, pero en la de Boole es cierta, y es la que más se olvida en los exámenes.

El principio de dualidad

Todos los postulados vienen en parejas: si en una igualdad intercambias + por · y 0 por 1, obtienes otra igualdad también válida. Por eso cada teorema demostrado regala su dual sin trabajo adicional. Por ejemplo, el dual de A + 0 = A es A·1 = A.

Teoremas fundamentales

TeoremaForma con +Forma dual
IdempotenciaA + A = AA·A = A
Elemento absorbenteA + 1 = 1A·0 = 0
Involución(A')' = A—
AbsorciónA + A·B = AA·(A + B) = A
Absorción del complementoA + A'·B = A + BA·(A' + B) = A·B
AsociativaA + (B + C) = (A + B) + CA·(B·C) = (A·B)·C
De Morgan(A + B)' = A'·B'(A·B)' = A' + B'
ConsensoAB + A'C + BC = AB + A'C(A + B)(A' + C)(B + C) = (A + B)(A' + C)

Demostración de la idempotencia a partir de los postulados

Es un buen ejemplo de cómo se razona solo con P1-P6:

  1. A + A = (A + A)·1, por el neutro del producto (P2).
  2. = (A + A)·(A + A'), porque A + A' = 1 (P5).
  3. = A + A·A', por la distributiva de la suma (P4).
  4. = A + 0, porque A·A' = 0 (P5).
  5. = A, por el neutro de la suma (P2).

El dual, A·A = A, se obtiene cambiando cada paso por su dual.

Ley de absorción

A + A·B = A·1 + A·B = A·(1 + B) = A·1 = A. Se usa el neutro, la distributiva y el elemento absorbente (1 + B = 1). La idea intuitiva: si A ya vale 1, el término AB no añade nada; si A vale 0, AB también vale 0.

La variante A + A'B = A + B se demuestra con la distributiva de la suma: A + A'B = (A + A')(A + B) = 1·(A + B) = A + B.

Teorema del consenso

En AB + A'C + BC, el término BC (el «consenso» de AB y A'C) sobra. Demostración: BC = BC·(A + A') = ABC + A'BC. Entonces AB + A'C + ABC + A'BC = AB(1 + C) + A'C(1 + B) = AB + A'C. Este teorema se usa mucho al simplificar, y también al revés: en un circuito real, mantener el término de consenso puede evitar los fallos transitorios por carreras (race hazards) que aparecen cuando una variable cambia y dos caminos de la señal no conmutan a la vez. El nombre «consenso» lo acuñó Willard Quine en 1955.

Comprobar un teorema con una tabla de verdad

Como cada variable solo toma dos valores, cualquier igualdad se puede comprobar probando todas las combinaciones. Para la absorción del complemento:

ABA'BA + A'BA + B
00000
01111
10011
11011

Las dos últimas columnas coinciden, así que la igualdad es cierta. Con n variables hay 2n filas: es cómodo hasta 3 o 4 variables.

Ejemplos de simplificación paso a paso

Ejemplo 1

F = AB + AB' + A'B.

  1. AB + AB' = A(B + B') = A·1 = A. Queda F = A + A'B.
  2. Por la absorción del complemento, A + A'B = A + B.

Resultado: F = A + B, una sola puerta OR en lugar de tres AND, un OR de tres entradas y un inversor.

Ejemplo 2

G = ABC + AB'C + ABC'.

  1. ABC + AB'C = AC(B + B') = AC.
  2. ABC + ABC' = AB(C + C') = AB. Se puede reutilizar ABC gracias a la idempotencia (ABC = ABC + ABC).
  3. G = AC + AB = A(B + C).

Ejemplo 3, con De Morgan

H = (AB)' + C. Aplicando De Morgan al primer término: H = A' + B' + C. Esta forma es útil si solo dispones de entradas complementadas o si quieres implementar la función con puertas NAND. Las leyes de De Morgan tienen su propia guía, con la versión para conjuntos y para proposiciones.

Errores habituales

  • Escribir A + A = 2A. En Boole, A + A = A.
  • Pensar que (A + B)' = A' + B'. Es falso: el complemento de una suma es el producto de los complementos.
  • Simplificar A + AB como si fuera A(1 + B) y luego detenerse: 1 + B vale 1, así que el resultado es A.
  • Olvidar la distributiva de la suma, que permite pasar de A + BC a (A + B)(A + C).

Un poco de historia

George Boole presentó este cálculo en The Mathematical Analysis of Logic (1847) y lo desarrolló en An Investigation of the Laws of Thought (1854). La conexión con la electrónica llegó con Claude Shannon, que en su tesis de máster de 1937, A Symbolic Analysis of Relay and Switching Circuits, mostró que los circuitos de relés y conmutadores obedecen esas reglas. Huntington propuso en 1904 el sistema de postulados de la tabla anterior.

Relación con otros resultados

Toda función booleana se puede descomponer respecto de una variable: F = A·F(1, …) + A'·F(0, …). Es el teorema de expansión de Shannon, que justifica las formas canónicas (suma de productos y producto de sumas) y los multiplexores. Los conjuntos con unión, intersección y complemento también forman un álgebra de Boole, y por eso los diagramas de Venn sirven para visualizar estas leyes con dos o tres variables.

Preguntas frecuentes

¿Qué diferencia hay entre un postulado y un teorema del álgebra de Boole?

Los postulados (neutro, conmutativa, distributiva, complemento) se aceptan sin demostración. Los teoremas, como la absorción o De Morgan, se deducen de ellos.

¿Qué dice la ley de absorción?

Que A + A·B = A y, en su forma dual, A·(A + B) = A. El término que contiene a A multiplicada por otra variable no aporta nada.

¿Qué es el teorema del consenso?

Que AB + A'C + BC = AB + A'C: el término BC sobra porque ya está cubierto por los otros dos. Su dual es (A + B)(A' + C)(B + C) = (A + B)(A' + C).

¿Cómo compruebo que una simplificación está bien?

Haz la tabla de verdad de la expresión original y de la simplificada. Si coinciden en todas las filas, son equivalentes.

Fuentes

Teoremas

RELACIONADOS

Subir