En álgebra abstracta , un álgebra booleana o red booleana es una red distributiva complementada . Este tipo de estructura algebraica captura propiedades esenciales tanto de operaciones de conjuntos como de operaciones lógicas . Un álgebra booleana puede verse como una generalización de un álgebra de conjuntos de potencias o un campo de conjuntos , o sus elementos pueden verse como valores de verdad generalizados . También es un caso especial de un álgebra de De Morgan y un álgebra de Kleene (con involución) .
Cada álgebra booleana da lugar a un anillo booleano , y viceversa, con la multiplicación de anillos correspondiente a la conjunción o encuentro ∧, y la suma de anillos a la disyunción exclusiva o diferencia simétrica (no a la disyunción ∨). Sin embargo, la teoría de los anillos de Boole tiene una asimetría inherente entre los dos operadores, mientras que los axiomas y teoremas del álgebra de Boole expresan la simetría de la teoría descrita por el principio de dualidad . [1]
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 folleto, El análisis matemático de la lógica , 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 de la descrita anteriormente en algunos aspectos importantes. Por ejemplo, la conjunción y la disyunción en Boole no eran un par dual de operaciones. El álgebra booleana surgió en la década de 1860, en artículos escritos por William Jevons y Charles Sanders Peirce . La primera presentación sistemática del álgebra booleana y las redes distributivas se debe a las Vorlesungen de 1890 de Ernst Schröder . El primer tratamiento extenso del álgebra booleana en inglés es el Álgebra universal de AN Whitehead de 1898 . El álgebra booleana como estructura algebraica axiomática en el sentido axiomático moderno comienza con un artículo de 1904 de Edward V. Huntington . El álgebra booleana alcanzó la mayoría de edad como matemática seria con el trabajo de Marshall Stone en la década de 1930 y con la Teoría del entramado de Garrett Birkhoff de 1940 . En la década de 1960, Paul Cohen , Dana Scott y otros encontraron resultados nuevos y profundos en lógica matemática y teoría de conjuntos axiomáticos utilizando ramas del álgebra booleana, concretamente modelos forzados y con valores booleanos .
Un álgebra booleana es un conjunto A , equipado con dos operaciones binarias ∧ (llamada "encontrarse" o "y"), ∨ (llamada "unir" u "o"), una operación unaria ¬ (llamada "complementar" o "no" ) y dos elementos 0 y 1 en A (llamados "inferior" y "superior", o elemento "menor" y "mayor", también indicados por los símbolos ⊥ y ⊤ , respectivamente), de modo que para todos los elementos a , b y c de A , se cumplen los siguientes axiomas : [2]
Tenga en cuenta, 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 otros axiomas (consulte Propiedades probadas).
Un álgebra de Boole con un solo elemento se llama álgebra de Boole trivial o álgebra de Boole degenerada . (En trabajos más antiguos, algunos autores exigían que 0 y 1 fueran elementos distintos para excluir este caso). [ cita necesaria ]
De los últimos tres pares de axiomas anteriores (identidad, distributividad y complementos), o del axioma de absorción, se deduce que
La relación ≤ definida por a ≤ b si se cumplen estas condiciones equivalentes, es un orden parcial con menor elemento 0 y mayor elemento 1. El encuentro a ∧ b y el encuentro a ∨ b de dos elementos coinciden con su mínimo y supremo , respectivamente, con respecto a ≤.
Los primeros cuatro pares de axiomas constituyen una definición de red acotada .
De los primeros cinco pares de axiomas se deduce que cualquier complemento es único.
El conjunto de axiomas es autodual en el sentido de que si se intercambia ∨ por ∧ y 0 por 1 en un axioma, el resultado vuelve a ser un axioma. Por tanto, aplicando esta operación a un álgebra booleana (o red booleana), se obtiene otra álgebra booleana con los mismos elementos; se llama dual . [3]
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 :
Entonces 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 completa de la categoría de celosías.
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 en A , y la composición f ∘ g : B → B es la función identidad en B . Un homomorfismo de álgebras de Boole es un isomorfismo si y sólo si es biyectivo .
Todo álgebra booleana ( A , ∧, ∨) da lugar a un anillo ( A , +, ·) al definir 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 anillos booleanos .
Por el contrario, si se da un anillo booleano A , podemos convertirlo en un álgebra booleana definiendo x ∨ y := x + y + ( x · y ) y x ∧ y := x · y . [4] [5] Dado que estas dos construcciones son inversas entre sí, podemos decir que cada anillo de Boole surge de un álgebra de Boole, y viceversa. Además, un mapa f : A → B es un homomorfismo de álgebras booleanas si y sólo si es un homomorfismo de anillos booleanos. Las categorías de anillos booleanos y álgebras booleanas son equivalentes ; [6] 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. De manera más general, Boudet, Jouannaud y Schmidt-Schauß (1989) dieron un algoritmo para resolver ecuaciones entre expresiones arbitrarias de anillos booleanos. Al emplear la similitud de los anillos booleanos y las álgebras booleanas, ambos algoritmos tienen aplicaciones en la demostración automatizada de teoremas .
Un ideal del álgebra booleana A es un subconjunto I no vacío tal que para todo x , y en I tenemos x ∨ y en I y para todo a en A tenemos un ∧ x en I. Esta noción de ideal coincide con la noción de ideal de anillo en el anillo booleano A. Un I ideal 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 cada a ∈ A tenemos que a ∧ − a = 0 ∈ I , y luego si I es primo tenemos a ∈ I o − a ∈ I para cada a ∈ A . Un ideal I de A se llama máximo si I ≠ A y si el único ideal que contiene adecuadamente a I es el propio A. Para un ideal I , si a ∉ I y − a ∉ I , entonces I ∪ a o I ∪ {− a } está contenido en otro ideal propio J. Por tanto, tal I no es máximo y, por tanto, las nociones de ideal primo e ideal máximo son equivalentes en las álgebras de Boole. Además, estas nociones coinciden con las de la teoría de anillos de ideal primo e ideal máximo en el anillo booleano A.
El dual de un ideal es un filtro . Un filtro del álgebra booleana A es un subconjunto p no vacío tal que para todo x , y en p tenemos x ∧ y en p y para todo a en A tenemos un ∨ x en p . El dual de un ideal máximo (o primo ) en un álgebra booleana es ultrafiltro . Alternativamente, los ultrafiltros se pueden describir como morfismos de 2 valores desde A hasta el álgebra booleana de dos elementos. La afirmación de que cada filtro en un álgebra booleana se puede extender a un ultrafiltro se llama lema del ultrafiltro y no se puede probar 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: cada álgebra de Boole tiene un ultrafiltro , cada ideal en un álgebra de Boole se puede extender a un ideal primo , etc.
Se puede demostrar que todo álgebra de Boole finita es isomorfa al álgebra de Boole de todos los subconjuntos de un conjunto finito. Por tanto, el número de elementos de todo álgebra booleana finita es una potencia de dos .
El célebre teorema de representación de Stone para álgebras de Boole establece que cada álgebra de Boole A es isomorfa al álgebra de Boole de todos los conjuntos abiertos en algún espacio topológico ( compacto de Hausdorff totalmente desconectado ).
La primera axiomatización de celosías/álgebras booleanas en general fue dada por el filósofo y matemático inglés Alfred North Whitehead en 1898. [7] [8] Incluía los axiomas anteriores y además x ∨ 1 = 1 y x ∧ 0 = 0 . En 1904, el matemático estadounidense Edward V. Huntington (1874-1952) hizo probablemente la axiomatización más parsimoniosa basada en ∧ , ∨ , ¬ , demostrando incluso las leyes de asociatividad (ver recuadro). [9] También demostró que estos axiomas son independientes entre sí. [10] En 1933, Huntington estableció la siguiente axiomatización elegante para el álgebra de Boole. [11] Requiere solo una operación binaria + y un símbolo funcional unario n , que se lee como 'complemento', que satisface las siguientes leyes:
Herbert Robbins preguntó inmediatamente: Si la ecuación de Huntington se reemplaza por su dual, a saber:
¿Forman (1), (2) y (4) una base para el álgebra de Boole? Al llamar a (1), (2) y (4) un álgebra de Robbins , la pregunta entonces es: ¿Es cada álgebra de Robbins un álgebra de Boole? Esta pregunta (que llegó a conocerse como la conjetura de Robbins ) permaneció abierta durante décadas y se convirtió en una de las preguntas favoritas de Alfred Tarski y sus alumnos. En 1996, William McCune del Laboratorio Nacional Argonne , basándose en trabajos anteriores de Larry Wos, Steve Winker y Bob Veroff, respondió afirmativamente a la pregunta de Robbins: cada álgebra de Robbins es un álgebra booleana. Crucial para la prueba de McCune fue el programa informático EQP que diseñó. Para una simplificación de la prueba de McCune, véase Dahn (1998).
Se han realizado más trabajos para reducir el número de axiomas; consulte Axiomas mínimos para el álgebra booleana .
Eliminar el requisito de existencia de una unidad de los axiomas del álgebra de Boole produce "álgebras de Boole generalizadas". Formalmente, una red distributiva B es una red booleana generalizada, si tiene un elemento más pequeño 0 y para cualquier elemento a y b en B tal que a ≤ b , existe un elemento x tal que a ∧ x = 0 y a ∨ x = b . Definiendo a \ b como la única x tal que ( a ∧ b ) ∨ x = a y ( a ∧ b ) ∧ x = 0 , decimos que la estructura ( B , ∧, ∨, \, 0) es una estructura booleana generalizada. álgebra , mientras que ( B , ∨, 0) es una semired booleana generalizada . Las redes booleanas generalizadas son exactamente los ideales de las redes booleanas.
Una estructura que satisface todos los axiomas de las álgebras booleanas excepto los dos axiomas de distributividad se denomina red ortocomplementada . Las redes ortocomplementadas surgen naturalmente en la lógica cuántica como redes de subespacios lineales cerrados para espacios de Hilbert separables .