Álgebra de Boole (estructura)

El término «álgebra de Boole» honra a George Boole (1815–1864), un matemático inglés autodidacta. Introdujo el sistema algebraico inicialmente en un pequeño panfleto, The Mathematical Analysis of Logic, publicado en 1847 en respuesta a una controversia pública en curso entre Augustus De Morgan y William Hamilton, y más tarde como un libro más sustancial, Las leyes del pensamiento, publicado en 1854. La formulación de Boole difiere en algunos aspectos importantes de la descrita anteriormente. Por ejemplo, la conjunción y la disyunción en Boole no eran un par dual de operaciones. El álgebra de Boole surgió en la década de 1860, en trabajos escritos por William Jevons y Charles Sanders Peirce.

La primera presentación sistemática del álgebra de Boole y de los retículos distributivos se debe a las Vorlesungen de 1890 de Ernst Schröder. El primer tratamiento extenso del álgebra de Boole en inglés es Universal Algebra de A. N. Whitehead en 1898. El álgebra de Boole como estructura algebraica axiomática en el sentido axiomático moderno comienza con un artículo de 1904 de Edward V. Huntington.^[2] El álgebra de Boole alcanzó su madurez como matemática seria con los trabajos de Marshall Stone en la década de 1930, y con Lattice Theory de Garrett Birkhoff en 1940. En la década de 1960, Paul Cohen, Dana Scott y otros encontraron resultados profundos nuevos en lógica matemática y teoría axiomática de conjuntos utilizando derivados del álgebra de Boole, concretamente el forzado y el modelo booleanos.

Un álgebra de Boole es un conjunto A, equipado con dos operación binarias ∧ (llamada «meet» o «y»), ∨ (llamada «join» u «o»), una operación unaria ¬ (llamada «complemento» o «no») y dos elementos 0 y 1 en A (llamados «elemento inferior» y «elemento superior», o «elemento mínimo» y «elemento máximo», también denotados por los símbolos ⊥ y ⊤, respectivamente), tales que para todos los elementos a, b y c de A, se cumplen los siguientes axiomas:^[3]

a ∨ (b ∨ c) = (a ∨ b) ∨ c	a ∧ (b ∧ c) = (a ∧ b) ∧ c	asociatividad
a ∨ b = b ∨ a	a ∧ b = b ∧ a	conmutatividad
a ∨ (a ∧ b) = a	a ∧ (a ∨ b) = a	ley de absorción
a ∨ 0 = a	a ∧ 1 = a	elemento identidad
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)	a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)	distributividad
a ∨ ¬a = 1	a ∧ ¬a = 0	complementos

Nótese, sin embargo, que la ley de absorción e incluso la ley de asociatividad pueden excluirse del conjunto de axiomas, ya que pueden derivarse de los otros axiomas.

Un álgebra de Boole con un solo elemento se llama álgebra de Boole trivial o álgebra de Boole degenerada. (En trabajos antiguos, algunos autores requerían que 0 y 1 fueran elementos distintos para excluir este caso.)^{[cita requerida]}

De los últimos tres pares de axiomas anteriores (identidad, distributividad y complementos), o del axioma de absorción, se deduce que

a = b ∧ a si y solo si a ∨ b = b.

La relación ≤ definida por a ≤ b si se cumplen estas condiciones equivalentes, es un orden parcial con elemento mínimo 0 y elemento máximo 1. El meet a ∧ b y el join a ∨ b de dos elementos coinciden con su ínfimo y supremo, respectivamente, respecto de ≤.

Los primeros cuatro pares de axiomas constituyen una definición de un retículo acotado.

Se deduce de los primeros cinco pares de axiomas que todo complemento es único.

El conjunto de axiomas es auto-dual en el sentido de que si se intercambian ∨ con ∧ y 0 con 1 en un axioma, el resultado es nuevamente un axioma. Por lo tanto, aplicando esta operación a un álgebra de Boole (o retículo booleano), se obtiene otro álgebra de Boole con los mismos elementos; se llama su dual.^[4]

• La álgebra de Boole no trivial más simple, la álgebra de Boole de dos elementos, tiene solo dos elementos, 0 y 1, y está definida por las reglas:

• Tiene aplicaciones en lógica, interpretando 0 como «falso», 1 como «verdadero», ∧ como «y», ∨ como «o» y ¬ como «no». Las expresiones que involucran variables y las operaciones booleanas representan formas de enunciados, y dos expresiones de este tipo pueden demostrarse iguales usando los axiomas anteriores si y solo si las formas de enunciado correspondientes son lógicamente equivalentes.
• La álgebra de Boole de dos elementos también se utiliza en el diseño de circuitos en ingeniería eléctrica;^{[Nota 1]} aquí 0 y 1 representan los dos diferentes estados de un bit en un circuito digital, típicamente alto y bajo voltaje. Los circuitos se describen mediante expresiones que contienen variables, y dos expresiones de este tipo son iguales para todos los valores de las variables si y solo si los circuitos correspondientes tienen el mismo comportamiento entrada-salida. Además, todo comportamiento entrada-salida posible puede modelarse mediante una expresión booleana adecuada.
• La álgebra de Boole de dos elementos también es importante en la teoría general de las álgebras de Boole, porque una ecuación que involucra varias variables es generalmente cierta en todas las álgebras de Boole si y solo si es cierta en la álgebra de Boole de dos elementos (lo que puede verificarse mediante un trivial algoritmo de fuerza bruta para un pequeño número de variables). Esto puede utilizarse, por ejemplo, para demostrar que las siguientes leyes (teorema del consenso) son válidas en general en todas las álgebras de Boole:
  • (a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
  • (a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)

• El conjunto potencia (conjunto de todos los subconjuntos) de cualquier conjunto no vacío dado S forma un álgebra de Boole, un álgebra de conjuntos, con las dos operaciones ∨ := ∪ (unión) y ∧ := ∩ (intersección). El elemento más pequeño 0 es el conjunto vacío y el elemento más grande 1 es el conjunto S mismo.
• Después de la álgebra de Boole de dos elementos, la álgebra de Boole más simple es la definida por el conjunto potencia de dos átomos:

• El conjunto A de todos los subconjuntos de S que son finitos o cofinitos es un álgebra de Boole y un álgebra de conjuntos llamada álgebra finito-cofinita. Si S es infinito entonces el conjunto de todos los subconjuntos cofinitos de S, llamado filtro de Fréchet, es un ultrafiltro libre sobre A. Sin embargo, el filtro de Fréchet no es un ultrafiltro sobre el conjunto potencia de S.

• Partiendo del cálculo proposicional con κ símbolos de enunciado, formar el álgebra de Lindenbaum–Tarski (es decir, el conjunto de enunciados en el cálculo proposicional módulo equivalencia lógica). Esta construcción produce un álgebra de Boole. De hecho es el álgebra de Boole libre sobre κ generadores. Una asignación de verdad en el cálculo proposicional es entonces un homomorfismo de álgebra de Boole desde esta álgebra hacia la álgebra de Boole de dos elementos.

• Dado cualquier conjunto totalmente ordenado L con un elemento mínimo, el álgebra de intervalos es la menor álgebra de Boole de subconjuntos de L que contiene todos los intervalos semiabiertos [a, b) tales que a está en L y b está en L o es igual a ∞. Las álgebras de intervalos son útiles en el estudio de las álgebra de Lindenbaum–Tarski; todo álgebra de Boole numerable es isomorfa a una álgebra de intervalos.

• 

  Para cualquier número natural n, el conjunto de todos los divisores positivos de n, definiendo a ≤ b si a divide a b, forma un retículo distributivo. Este retículo es un álgebra de Boole si y solo si n es entero libre de cuadrados. El elemento inferior y el elemento superior de esta álgebra de Boole son los números naturales 1 y n, respectivamente. El complemento de a está dado por n/a. El meet y el join de a y b están dados por el máximo común divisor (mcd) y el mínimo común múltiplo (mcm) de a y b, respectivamente. La suma del anillo a + b está dada por mcm(a, b) / mcd(a, b). La imagen muestra un ejemplo para n = 30. Como contraejemplo, considerando el número no libre de cuadrados n = 60, el máximo común divisor de 30 y su complemento 2 sería 2, mientras que debería ser el elemento inferior 1.

• Otros ejemplos de álgebras de Boole surgen de espacios topológicos: si X es un espacio topológico, entonces la colección de todos los subconjuntos de X que son abiertos y cerrados (clopen) al mismo tiempo forma un álgebra de Boole con las operaciones ∨ := ∪ (unión) y ∧ := ∩ (intersección).

• Si R es un anillo arbitrario entonces su conjunto de idempotente centrales, que es el conjunto$${\displaystyle A=\left\{e\in R:e^{2}=e{\text{ y }}ex=xe\;{\text{ para todo }}\;x\in R\right\},}$$se convierte en un álgebra de Boole cuando sus operaciones se definen por e ∨ f := e + f − ef y e ∧ f := ef.

Un homomorfismo entre dos álgebras de Boole A y B es una función f : A → B tal que para todo a, b en A:

f(a ∨ b) = f(a) ∨ f(b),

f(a ∧ b) = f(a) ∧ f(b),

f(0) = 0,

f(1) = 1.

De ello se deduce que f(¬a) = ¬f(a) para todo a en A. La clase de todas las álgebras de Boole, junto con esta noción de morfismo, forma una subcategoría plena de la categoría de retículos.

Un isomorfismo entre dos álgebras de Boole A y B es un homomorfismo f : A → B con un homomorfismo inverso, es decir, un homomorfismo g : B → A tal que la composición g ∘ f : A → A es la función identidad sobre A, y la composición f ∘ g : B → B es la función identidad sobre B. Un homomorfismo de álgebras de Boole es un isomorfismo si y solo si es biyectivo.

Todo álgebra de Boole (A, ∧, ∨) da lugar a un anillo (A, +, ·) definiendo a + b := (a ∧ ¬b) ∨ (b ∧ ¬a) = (a ∨ b) ∧ ¬(a ∧ b) (esta operación se llama diferencia simétrica en el caso de conjuntos y XOR en el caso de lógica) y a · b := a ∧ b. El elemento cero de este anillo coincide con el 0 del álgebra de Boole; el elemento identidad multiplicativo del anillo es el 1 del álgebra de Boole. Este anillo tiene la propiedad de que a · a = a para todo a en A; los anillos con esta propiedad se llaman anillo booleanos.

Recíprocamente, si se da un anillo booleano A, podemos convertirlo en un álgebra de Boole definiendo x ∨ y := x + y + (x · y) y x ∧ y := x · y.^[5][6] Dado que estas dos construcciones son inversas una de la otra, podemos decir que todo anillo booleano surge de un álgebra de Boole, y viceversa. Además, un mapa f : A → B es un homomorfismo de álgebras de Boole si y solo si es un homomorfismo de anillos booleanos. Las categorías de anillos booleanos y álgebras de Boole son equivalentes;^[7] de hecho las categorías son isomorfas.

Hsiang (1985) proporcionó un algoritmo basado en reglas para comprobar si dos expresiones arbitrarias denotan el mismo valor en cada anillo booleano.^[8]

De manera más general, Boudet, Jouannaud y Schmidt-Schauß (1989)^[9] proporcionaron un algoritmo para resolver ecuaciones entre expresiones arbitrarias de anillos booleanos. Aprovechando la similitud entre los anillos booleanos y las álgebras booleanas, ambos algoritmos tienen aplicaciones en la demostración automática de teoremas.

Un ideal del álgebra de Boole A es un subconjunto no vacío I tal que para todo x, y en I tenemos x ∨ y en I y para todo a en A tenemos a ∧ x en I. Esta noción de ideal coincide con la noción de ideal de anillo en el anillo booleano A. Un ideal I de A se llama primo si I ≠ A y si a ∧ b en I siempre implica a en I o b en I. Además, para todo a ∈ A tenemos que a ∧ ¬a = 0 ∈ I, y entonces si I es primo tenemos a ∈ I o ¬a ∈ I para todo a ∈ A. Un ideal I de A se llama máximo si I ≠ A y si el único ideal que contiene propiamente a I es A mismo. Para un ideal I, si a ∉ I y ¬a ∉ I, entonces I ∪ {a} o I ∪ {¬a} está contenido en otro ideal propio J. Por lo tanto, tal I no es máximo, y por consiguiente las nociones de ideal primo e ideal máximo son equivalentes en álgebras de Boole. Además, estas nociones coinciden con las nociones de ideal primo e ideal máximal en el anillo booleano A desde la teoría de anillos.

El dual de un ideal es un filtro. Un filtro del álgebra de Boole A es un subconjunto no vacío p tal que para todo x, y en p tenemos x ∧ y en p y para todo a en A tenemos a ∨ x en p. El dual de un ideal máximo (o primo) en un álgebra de Boole es un ultrafiltro. Los ultrafiltros también pueden describirse como morfismo 2-valuados desde A hacia la álgebra de Boole de dos elementos. La afirmación «todo filtro en un álgebra de Boole puede extenderse a un ultrafiltro» se llama lema del ultrafiltro y no puede demostrarse en la teoría de conjuntos de Zermelo-Fraenkel (ZF) si ZF es consistente. Dentro de ZF, el lema del ultrafiltro es estrictamente más débil que el axioma de elección. El lema del ultrafiltro tiene muchas formulaciones equivalentes: «todo álgebra de Boole tiene un ultrafiltro», «todo ideal en un álgebra de Boole puede extenderse a un ideal primo», etc.

La primera axiomatización de los retículos/álgebras de Boole en general fue dada por el filósofo y matemático inglés Alfred North Whitehead en 1898.^[10][11] Incluía los axiomas anteriores y adicionalmente x ∨ 1 = 1 y x ∧ 0 = 0. En 1904, el matemático estadounidense Edward V. Huntington (1874–1952) dio probablemente la axiomatización más económica basada en ∧, ∨, ¬, demostrando incluso las leyes de asociatividad (véase recuadro).^[12] También demostró que estos axiomas son independientes entre sí.^[13]

En 1933, Huntington presentó la siguiente elegante axiomatización para el álgebra de Boole.^[14] Requiere solo una operación binaria + y un símbolo funcional unario n, que se lee como «complemento», que satisfacen las siguientes leyes:

• 1. Conmutatividad: x + y = y + x.
• 2. Asociatividad: (x + y) + z = x + (y + z).
• 3. Ecuación de Huntington: n(n(x) + y) + n(n(x) + n(y)) = x.

Herbert Robbins preguntó inmediatamente: si la ecuación de Huntington se reemplaza por su dual, a saber:

• 4. Ecuación de Robbins: n(n(x + y) + n(x + n(y))) = x,

¿forman (1), (2) y (4) una base para el álgebra de Boole? Llamando a (1), (2) y (4) un álgebra de Robbins, la pregunta se convierte entonces en: ¿es todo álgebra de Robbins un álgebra de Boole? Esta cuestión (que llegó a conocerse como la conjetura de Robbins) permaneció abierta durante décadas y se convirtió en una pregunta favorita de Alfred Tarski y sus estudiantes.

En 1996, William McCune en el Laboratorio Nacional Argonne, basándose en trabajos anteriores de Larry Wos, Steve Winker y Bob Veroff, respondió afirmativamente a la pregunta de Robbins: todo álgebra de Robbins es un álgebra de Boole. Crucial para la demostración de McCune fue el programa informático EQP que él diseñó. Para una simplificación de la demostración de McCune, véase Dahn (1998).^[15]

Se ha trabajado más en reducir el número de axiomas; véase Axiomas mínimos para álgebra de Boole.

• Función booleana
• Álgebra de Boole
• Anillo de Boole
• Formas canónicas (álgebra de Boole)
• Leyes de De Morgan
• Forzado (matemáticas)
• Álgebra de Heyting
• Grafo hipercubo
• Mapa de Karnaugh
• Puerta lógica
• Gráficos existenciales
• Matriz booleana
• Lógica proposicional
• Algoritmo Quine-McCluskey
• Diagrama de Venn

1. [1]

   Strictamente hablando, los ingenieros eléctricos suelen utilizar estados adicionales para representar otras condiciones de circuito como alta impedancia —véase IEEE 1164 o IEEE 1364.