Álgebra booleana (estructura)

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]

Historia

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 .

Definición

Un álgebra booleana es un conjunto $A$ , equipado con dos operaciones binarias $\land$ (llamada "encontrarse" o "y"), $\lor$ (llamada "unir" u "o"), una operación unaria $\neg$ (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

a = b \land a

si y sólo si

a \lor b = b

La relación $\leq$ definida por $a \leq b$ si se cumplen estas condiciones equivalentes, es un orden parcial con menor elemento 0 y mayor elemento 1. El encuentro $a \land b$ y el encuentro $a \lor 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 $\lor$ por $\land$ 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]

Ejemplos

El álgebra booleana no trivial más simple, el álgebra booleana de dos elementos , tiene sólo dos elementos, $0$ y $1$ , y está definida por las reglas:

Tiene aplicaciones en lógica , interpretando $0$ como falso , $1$ como verdadero , $\land$ como y , $\lor$ como o y $\neg$ como no . Las expresiones que involucran variables y las operaciones booleanas representan formas de enunciado, y se puede demostrar que dos de esas expresiones son iguales usando los axiomas anteriores si y solo si las formas de enunciado correspondientes son lógicamente equivalentes .

El álgebra booleana de dos elementos también se utiliza para el diseño de circuitos en ingeniería eléctrica ; ^{[nota 1]} aquí 0 y 1 representan los dos estados diferentes de un bit en un circuito digital , generalmente alto y bajo voltaje . Los circuitos se describen mediante expresiones que contienen variables, y dos de esas expresiones son iguales para todos los valores de las variables si y sólo si los circuitos correspondientes tienen el mismo comportamiento de entrada-salida. Además, cada posible comportamiento de entrada-salida se puede modelar mediante una expresión booleana adecuada.

El álgebra booleana de dos elementos también es importante en la teoría general de las álgebras booleanas, porque una ecuación que involucra varias variables es generalmente cierta en todas las álgebras booleanas si y sólo si es cierta en el álgebra booleana de dos elementos (que puede verificarse mediante un algoritmo trivial de fuerza bruta para un número pequeño de variables). Esto se puede utilizar, por ejemplo, para demostrar que las siguientes leyes ( teoremas de consenso ) son generalmente válidas en todas las álgebras de Boole:
- $(a \lor b) \land (\neg a \lor c) \land (b \lor c) \equiv (a \lor b) \land (\neg a \lor c)$
- $(un \land segundo) \lor (\neg un \land c) \lor (segundo \land c) \equiv (un \land segundo) \lor (\neg un \land c)$

El conjunto potencia (conjunto de todos los subconjuntos) de cualquier conjunto no vacío $S$ dado forma un álgebra booleana, un álgebra de conjuntos , con las dos operaciones $\lor := \cup$ (unión) y $\land := \cap$ (intersección). El elemento más pequeño 0 es el conjunto vacío y el elemento más grande $1$ es el propio conjunto $S.$

Después del álgebra booleana de dos elementos, el álgebra booleana 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 booleana y un álgebra de conjuntos llamada álgebra finito-cofinito . Si $S$ es infinito entonces el conjunto de todos los subconjuntos cofinitos de S $,$ que se llama filtro de Fréchet , es un ultrafiltro libre en $A.$ Sin embargo, el filtro Fréchet no es un ultrafiltro en el conjunto de potencia de $S.$
Comenzando con el cálculo proposicional con $κ$ símbolos de oraciones, forme el álgebra de Lindenbaum (es decir, el conjunto de oraciones en el cálculo proposicional de equivalencia módulológica ). Esta construcción produce un álgebra booleana. De hecho, es el álgebra booleana libre sobre generadores $κ$ . Una asignación de verdad en cálculo proposicional es entonces un homomorfismo de álgebra booleana de esta álgebra al álgebra booleana de dos elementos.
Dado cualquier conjunto $L$ linealmente ordenado con un elemento mínimo, el álgebra de intervalos es el álgebra booleana más pequeña 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 $\infty$ . Las álgebras de intervalo son útiles en el estudio de las álgebras de Lindenbaum-Tarski ; Cada álgebra booleana contable es isomorfa a un álgebra de intervalo.

Para cualquier número natural $n$ , el conjunto de todos los divisores positivos de $n$ , que definen $a \leq b$ si $a$ divide $a b$ , forma una red distributiva . Esta red es un álgebra booleana si y sólo si $n$ no tiene cuadrados . Los elementos inferior y superior de esta álgebra booleana son los números naturales $1$ y $n$ , respectivamente. El complemento de $a$ viene dado por $n / a$ . El encuentro y la unión 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$ viene dada por $mcm(a, b) / gcd(a, b)$ . La imagen muestra un ejemplo para $n = 30$ . Como contraejemplo, considerando el $n = 60$ no libre de cuadrados , 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 forma un álgebra de Boole con las operaciones $\lor := \cup$ (unión) y $\land := \cap$ (intersección).
Si $R$ es un anillo arbitrario entonces su conjunto de idempotentes centrales , que es el conjunto

A=\left\{e\in R:e^{2}=e{\text{ y }}ex=xe\;{\text{ para todos }}\;x\in R\right\ },

e \lor f := e + f - ef

e \land f := ef

Homomorfismos e isomorfismos.

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

f (un \lor segundo) = f (un) \lor f (segundo)

f (una \land segundo) = f (una) \land f (segundo)

f (0) = 0

f (1) = 1

Entonces se deduce que $f (\neg a) = \neg 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 \to B$ con un homomorfismo inverso, es decir, un homomorfismo $g : B \to A$ tal que la composición $g \circ f : A \to A$ es la función identidad en $A$ , y la composición $f \circ g : B \to B$ es la función identidad en $B$ . Un homomorfismo de álgebras de Boole es un isomorfismo si y sólo si es biyectivo .

anillos booleanos

Todo álgebra booleana $(A, \land, \lor)$ da lugar a un anillo $(A, +, \cdot)$ al definir $a + b := (a \land \neg b) \lor (b \land \neg a) = (a \lor b) \land \neg (a \land b)$ (esta operación se llama diferencia simétrica en el caso de conjuntos y XOR en el caso de lógica) y $a \cdot b := a \land 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 \cdot 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 \lor y := x + y + (x \cdot y)$ y $x \land y := x \cdot 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 \to 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 .

Ideales y filtros

Un ideal del álgebra booleana A $es$ un subconjunto $I$ no vacío tal que para todo $x$ , $y$ en $I$ tenemos $x \lor y$ en $I$ y para todo $a$ en $A$ tenemos $un \land 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 \neq A$ y si a $\land b en$ I $siempre$ implica $a$ en $I$ o $b$ en $I.$ Además, para cada $a \in A$ tenemos que $a \land - a = 0 \in I$ , y luego si $I$ es primo tenemos $a \in I$ o $- a \in I$ para cada $a \in A$ . Un ideal $I$ de $A$ se llama máximo si $I \neq A$ y si el único ideal que contiene adecuadamente $a I$ es el propio $A.$ Para un ideal $I$ , si $a \notin I$ y $- a \notin I$ , entonces $I \cup a$ o $I \cup {- 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 \land y$ en $p$ y para todo $a$ en $A$ tenemos $un \lor 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.

Representaciones

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 ).

axiomática

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 \lor 1 = 1$ y $x \land 0 = 0$ . En 1904, el matemático estadounidense Edward V. Huntington (1874-1952) hizo probablemente la axiomatización más parsimoniosa basada en $\land$ , $\lor$ , $\neg$ , 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:

Conmutatividad : $x + y = y + x$ .
Asociatividad : $(x + y)+ z = x +(y + z)$ .
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:

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? 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 .

Generalizaciones

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 \leq b$ , existe un elemento $x$ tal que $a \land x = 0$ y $a \lor x = b$ . Definiendo $a \ b$ como la única $x$ tal que $(a \land b) \lor x = a$ y $(a \land b) \land x = 0$ , decimos que la estructura $( B , ∧, ∨, \, 0)$ es una estructura booleana generalizada. álgebra , mientras que $(B, \lor, 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 .

Ver también

Notas

^ Estrictamente, los ingenieros eléctricos tienden a utilizar estados adicionales para representar otras condiciones del circuito, como la alta impedancia; consulte IEEE 1164 o IEEE 1364 .

Referencias

^ Givant y Halmos 2009, pág. 20.
^ Davey y Priestley 1990, págs.109, 131, 144.
^ Goodstein 2012, pag. 21 y sigs.
^ Piedra 1936.
^ Hsiang 1985, pág. 260.
^ Cohn 2003, pag. 81.
^ Padmanabhan y Rudeanu 2008, pág. 73.
^ Whitehead 1898, pag. 37.
^ Huntington 1904, págs. 292-293.
^ Huntington 1904, pag. 296.
^ Huntington 1933a.

Trabajos citados

Davey, Licenciatura en Letras; Priestley, HA (1990). Introducción a las celosías y al orden . Libros de texto de matemáticas de Cambridge. Prensa de la Universidad de Cambridge.
Cohn, Paul M. (2003), Álgebra básica: grupos, anillos y campos , Springer, págs. 51, 70–81, ISBN 9781852335878
Givant, Steven; Halmos, Paul (2009), Introducción a las álgebras booleanas , Textos de pregrado en matemáticas , Springer , ISBN 978-0-387-40293-2.
Goodstein, RL (2012), "Capítulo 2: El sistema autodual de axiomas", Álgebra booleana , Courier Dover Publications, págs. 21 y siguientes, ISBN 9780486154978
Hsiang, Jieh (1985). "Demostración del teorema refutacional mediante sistemas de reescritura de términos". Inteligencia artificial . 25 (3): 255–300. doi :10.1016/0004-3702(85)90074-8.
Huntington, Eduardo V. (1904). "Conjuntos de postulados independientes para el álgebra de la lógica". Transacciones de la Sociedad Matemática Estadounidense . 5 (3): 288–309. doi : 10.1090/s0002-9947-1904-1500675-4 . JSTOR 1986459.
Padmanabhan, Ranganathan; Rudeanu, Sergiu (2008), Axiomas para celosías y álgebras booleanas , World Scientific, ISBN 978-981-283-454-6.
Piedra, Marshall H. (1936). "La teoría de las representaciones del álgebra booleana". Transacciones de la Sociedad Matemática Estadounidense . 40 : 37-111. doi : 10.1090/s0002-9947-1936-1501865-8 .
Whitehead, AN (1898). Tratado sobre álgebra universal. Prensa de la Universidad de Cambridge. ISBN 978-1-4297-0032-0.

Referencias generales

Marrón, Esteban; Vranesic, Zvonko (2002), Fundamentos de lógica digital con diseño VHDL (2ª ed.), McGraw-Hill , ISBN 978-0-07-249938-4. Consulte la Sección 2.5.
Boudet, A.; Jouannaud, JP; Schmidt-Schauß, M. (1989). "Unificación en anillos booleanos y grupos abelianos". Revista de Computación Simbólica . 8 (5): 449–477. doi : 10.1016/s0747-7171(89)80054-9 .
Cori, René; Lascar, Daniel (2000), Lógica matemática: un curso con ejercicios , Oxford University Press , ISBN 978-0-19-850048-3. Consulte el Capítulo 2.
Dahn, BI (1998), "Las álgebras de Robbins son booleanas: una revisión de la solución generada por computadora de McCune al problema de Robbins", Journal of Algebra , 208 (2): 526–532, doi : 10.1006/jabr.1998.7467.

Halmos, Paul (1963), Conferencias sobre álgebras booleanas , Van Nostrand, ISBN 978-0-387-90094-0.
Halmos, Pablo ; Givant, Steven (1998), Lógica como álgebra , Exposiciones matemáticas de Dolciani, vol. 21, Asociación Matemática de América , ISBN 978-0-88385-327-6.
Huntington, EV (1933a), "Nuevos conjuntos de postulados independientes para el álgebra de la lógica" (PDF) , Transactions of the American Mathematical Society , American Mathematical Society, 35 (1): 274–304, doi :10.2307/1989325, JSTOR 1989325.
Huntington, EV (1933b), "Álgebra booleana: una corrección", Transactions of the American Mathematical Society , 35 (2): 557–558, doi :10.2307/1989783, JSTOR 1989783
Mendelson, Elliott (1970), Álgebra booleana y circuitos de conmutación , Schaum's Outline Series in Mathematics, McGraw-Hill , ISBN 978-0-07-041460-0
Monje, J. Donald; Bonnet, R., eds. (1989), Manual de álgebras booleanas , Holanda Septentrional , ISBN 978-0-444-87291-3. En 3 volúmenes. (Vol.1: ISBN 978-0-444-70261-6 , Vol.2: ISBN 978-0-444-87152-7 , Vol.3: ISBN 978-0-444-87153-4 )
Sikorski, Roman (1966), Álgebras booleanas , Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer Verlag.
Stoll, RR (1963), Teoría y lógica de conjuntos , WH Freeman, ISBN 978-0-486-63829-4. Reimpreso por Publicaciones de Dover , 1979.

enlaces externos

"Álgebra booleana", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
Enciclopedia de Filosofía de Stanford : "Las matemáticas del álgebra de Boole", por J. Donald Monk.
McCune W., 1997. Las álgebras de Robbins son booleanas JAR 19(3), 263—276
"Álgebra booleana" de Eric W. Weisstein , Proyecto de demostraciones Wolfram , 2007.
Burris, Stanley N.; Sankappanavar, HP, 1981. Un curso de álgebra universal. Springer-Verlag. ISBN 3-540-90578-2 .
Weisstein, Eric W. "Álgebra booleana". MundoMatemático .