Álgebra de Boole (estructura)

En álgebra abstracta , un álgebra de Boole o red de Boole es una red distributiva complementada . Este tipo de estructura algebraica captura propiedades esenciales tanto de las operaciones de conjuntos como de las operaciones lógicas . Un álgebra de Boole puede verse como una generalización de un álgebra de conjuntos de potencias o un cuerpo 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) .

Toda álgebra de Boole da lugar a un anillo de Boole , y viceversa, correspondiendo la multiplicación de anillos a la conjunción o encuentro ∧, y la adición de anillos a la disyunción exclusiva o diferencia simétrica (no a la disyunción ∨). Sin embargo, la teoría de 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" rinde homenaje 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, The Laws of Thought , 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 de Boole 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 de Boole y 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 AN Whitehead de 1898. El álgebra de Boole como una estructura algebraica axiomática en el sentido axiomático moderno comienza con un artículo de 1904 de Edward V. Huntington . El álgebra de Boole 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 de celosía de Garrett Birkhoff de 1940. En la década de 1960, Paul Cohen , Dana Scott y otros encontraron nuevos resultados profundos en la lógica matemática y la teoría de conjuntos axiomáticos utilizando ramificaciones del álgebra de Boole, a saber, modelos forzados y de valor booleano .

Definición

Un álgebra de Boole es un conjunto $A$ , equipado con dos operaciones binarias $\land$ (llamadas "encuentro" o "y"), $\lor$ (llamada "unión" u "o"), una operación unaria $\neg$ (llamada "complemento" o "no") y dos elementos $0$ y $1$ en $A$ (llamados "inferior" y "superior", o elemento "menor" y "mayor", 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 : ^[2]

Obsérvese, 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 (ver Propiedades probadas).

Un álgebra de Boole con un solo elemento se denomina á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 requerida ]}

De los tres últimos 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 la unión $a \lor b$ de dos elementos coinciden con su ínfimo y supremo , respectivamente, con respecto a ≤.

Los primeros cuatro pares de axiomas constituyen una definición de una 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 es nuevamente un axioma. Por lo tanto, al aplicar esta operación a un álgebra de Boole (o red de Boole), se obtiene otra álgebra de Boole con los mismos elementos; se la llama su dual . ^[3]

Ejemplos

El álgebra de Boole no trivial más simple, el á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 , $\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 de Boole 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 , típicamente alto y bajo voltaje . Los circuitos se describen mediante expresiones que contienen variables, y dos de estas expresiones son iguales para todos los valores de las variables si y solo 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 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 verdadera en todas las álgebras de Boole si y solo si es verdadera en el álgebra de Boole de dos elementos (lo cual puede comprobarse mediante un algoritmo de fuerza bruta trivial para un pequeño número de variables). Esto puede usarse, por ejemplo, para mostrar 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)$
- $( a\landb ) \lor (\nega\landc) \lor ( b\landc) \equiv (a\landb) \lor (\nega\landc) $

El conjunto potencia (conjunto de todos los subconjuntos) de cualquier conjunto no vacío $S$ forma un álgebra de Boole, 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 de Boole de dos elementos, el á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$ , que se llama filtro de Fréchet , es un ultrafiltro libre en $A.$ Sin embargo, el filtro de Fréchet no es un ultrafiltro en el conjunto potencia de $S.$
Partiendo del cálculo proposicional con $κ$ símbolos oracionales, se forma el álgebra de Lindenbaum (es decir, el conjunto de oraciones del cálculo proposicional módulo equivalencia lógica ). Esta construcción produce un álgebra de Boole. Es, de hecho, el álgebra de Boole libre sobre $κ$ generadores. Una asignación de verdad en el cálculo proposicional es entonces un homomorfismo del álgebra de Boole desde esta álgebra al álgebra de Boole de dos elementos.
Dado cualquier conjunto $L$ ordenado linealmente con un elemento mínimo, el álgebra de intervalos es la álgebra de Boole más pequeña de subconjuntos de $L$ que contienen 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 intervalos son útiles en el estudio de las álgebras de Lindenbaum-Tarski ; toda álgebra de Boole contable es isomorfa a un álgebra de intervalos.

Para cualquier número natural $n$ , el conjunto de todos los divisores positivos de $n$ , que define $a \leq b$ si $a$ divide $a b$ , forma una red distributiva . Esta red es un álgebra de Boole si y solo si $n$ es libre de cuadrados . Los elementos inferior y 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 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 adición de anillo $a + b$ está dada por $mcm(a, b) / mcd(a, b)$ . La imagen muestra un ejemplo para $n = 30$ . Como contraejemplo, considerando el 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 los espacios topológicos : si $X$ es un espacio topológico, entonces la colección de todos los subconjuntos de $X$ que son tanto abiertos como 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 todo }}\;x\in R\right\},$ se convierte en un álgebra booleana cuando sus operaciones están definidas por $e \lor f := e + f - ef$ y $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 (a\lorb) = f (a) \lorf (b)

​

f (a\landb)

f

(

a

)

\landf

(

b

)

,

​

f (0) = 0

f (1) = 1

De ello 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 retículos.

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 solo si es biyectivo .

Anillos booleanos

Toda álgebra de Boole $(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 la 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 todo anillo booleano surge de un álgebra booleana, y viceversa. Además, una función $f : A \to B$ es un homomorfismo de álgebras booleanas si y solo 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) presentó un algoritmo basado en reglas para verificar si dos expresiones arbitrarias denotan el mismo valor en cada anillo booleano. De manera más general, Boudet, Jouannaud y Schmidt-Schauß (1989) presentaron 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 automática de teoremas .

Ideales y filtros

Un ideal del álgebra de Boole $A$ es un subconjunto no vacío $I$ tal que para todo $x$ , $y$ en $I$ tenemos $x \lor y$ en $I$ y para todo $a$ en $A$ tenemos $a \land 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 \neq A$ y si $a \land b$ en $I$ siempre implica $a$ en $I$ o $b$ en $I$ . Además, para todo $a \in A$ tenemos que $a \land - a = 0 \in I$ , y entonces si $I$ es primo tenemos $a \in I$ o $- a \in I$ para todo $a \in A$ . Un ideal $I$ de $A$ se llama maximal si $I \neq A$ y si el único ideal que contiene apropiadamente $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 lo tanto, tal $I$ no es maximal, y por lo tanto las nociones de ideal primo e ideal maximal 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 maximal en el anillo booleano $A$ .

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 \land y$ en $p$ y para todo $a$ en $A$ tenemos $a \lor x$ en $p$ . El dual de un ideal maximal (o primo ) en un álgebra de Boole es ultrafiltro . Los ultrafiltros pueden describirse alternativamente como morfismos de 2 valores desde $A$ hasta el álgebra de Boole de dos elementos. La afirmación de que todo filtro en un álgebra de Boole puede extenderse a un ultrafiltro se llama lema del ultrafiltro y no puede probarse 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 puede extenderse a un ideal primo , etc.

Representaciones

Se puede demostrar que toda álgebra booleana finita es isomorfa al álgebra booleana de todos los subconjuntos de un conjunto finito. Por lo tanto, el número de elementos de toda álgebra booleana finita es una potencia de dos .

El célebre teorema de representación de Stone para las álgebras de Boole establece que toda álgebra de Boole $A$ es isomorfa al álgebra de Boole de todos los conjuntos abiertos y cerrados en algún espacio topológico ( de Hausdorff compacto y totalmente desconectado ).

Axiomática

La primera axiomatización de las redes/á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 adicionalmente $x \lor 1 = 1$ y $x \land 0 = 0$ . En 1904, el matemático estadounidense Edward V. Huntington (1874-1952) dio probablemente la axiomatización más parsimoniosa basada en $\land$ , $\lor$ , $\neg$ , incluso demostrando las leyes de asociatividad (ver recuadro). ^[9] También demostró que estos axiomas son independientes entre sí. ^[10] En 1933, Huntington propuso la siguiente axiomatización elegante para el álgebra de Boole. ^[11] Requiere solo una operación binaria $+$ y un símbolo funcional unario $n$ , para ser leído como 'complemento', que satisfacen 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$ ,

¿(1), (2) y (4) forman una base para el álgebra de Boole? Si llamamos a (1), (2) y (4) un álgebra de Robbins , la pregunta entonces es: ¿toda álgebra de Robbins es 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 pregunta favorita de Alfred Tarski y sus estudiantes. En 1996, William McCune en el Laboratorio Nacional de Argonne , basándose en el trabajo anterior de Larry Wos, Steve Winker y Bob Veroff, respondió afirmativamente a la pregunta de Robbins: toda álgebra de Robbins es un álgebra de Boole. Crucial para la prueba de McCune fue el programa de computadora 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; véase Axiomas mínimos para el álgebra de Boole .

Generalizaciones

Si eliminamos el requisito de la existencia de una unidad de los axiomas del álgebra de Boole, obtenemos "álgebras de Boole generalizadas". Formalmente, una red distributiva $B$ es una red booleana generalizada si tiene un elemento mínimo $0$ y para cualesquiera elementos $a$ y $b$ en $B$ tales que $a \leq b$ , existe un elemento $x$ tal que $a \land x = 0$ y $a \lor x = b$ . Si definimos $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 un álgebra de Boole generalizada , 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 de Boole, excepto los dos axiomas de distributividad, se denomina red ortocomplementada . Las redes ortocomplementadas surgen de forma natural en la lógica cuántica como redes de subespacios lineales cerrados para espacios de Hilbert separables .

Véase también

Notas

^ Estrictamente, los ingenieros eléctricos tienden a utilizar estados adicionales para representar otras condiciones del circuito, como 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, pág. 21 y siguientes.
^ Piedra 1936.
^ Hsiang 1985, pág. 260.
^ Cohn 2003, pág. 81.
^ Padmanabhan y Rudeanu 2008, pág. 73.
^ Whitehead 1898, pág. 37.
^ Huntington 1904, págs. 292-293.
^ Huntington 1904, pág. 296.
^ Huntington 1933a.

Obras citadas

Davey, BA; Priestley, HA (1990). Introducción a los retículos y al orden . Cambridge Mathematical Textbooks. Cambridge University Press.
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 de Boole , Textos de pregrado en matemáticas , Springer , ISBN 978-0-387-40293-2.
Goodstein, RL (2012), "Capítulo 2: El sistema autodual de axiomas", Boolean Algebra , Courier Dover Publications, pp. 21ff, ISBN 9780486154978
Hsiang, Jieh (1985). "Demostración de teoremas de refutación utilizando sistemas de reescritura de términos". Inteligencia artificial . 25 (3): 255–300. doi :10.1016/0004-3702(85)90074-8.
Huntington, Edward V. (1904). "Conjuntos de postulados independientes para el álgebra de la lógica". Transactions of the American Mathematical Society . 5 (3): 288–309. doi : 10.1090/s0002-9947-1904-1500675-4 . JSTOR 1986459.
Padmanabhan, Ranganathan; Rudeanu, Sergiu (2008), Axiomas para redes y álgebras booleanas , World Scientific, ISBN 978-981-283-454-6.
Stone, Marshall H. (1936). "La teoría de representaciones para el álgebra de Boole". Transactions of the American Mathematical Society . 40 : 37–111. doi : 10.1090/s0002-9947-1936-1501865-8 .
Whitehead, AN (1898). Tratado sobre álgebra universal. Cambridge University Press. ISBN 978-1-4297-0032-0.

Referencias generales

Brown, Stephen; Vranesic, Zvonko (2002), Fundamentos de lógica digital con diseño VHDL (2.ª ed.), McGraw–Hill , ISBN 978-0-07-249938-4. Véase la Sección 2.5.
Boudet, A.; Jouannaud, JP; Schmidt-Schauß, M. (1989). "Unificación en anillos booleanos y grupos abelianos". Journal of Symbolic Computation . 8 (5): 449–477. doi : 10.1016/s0747-7171(89)80054-9 .
Cori, Rene; Lascar, Daniel (2000), Lógica matemática: un curso con ejercicios , Oxford University Press , ISBN 978-0-19-850048-3. Véase 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 del 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, Paul ; Givant, Steven (1998), Lógica como álgebra , Dolciani Mathematical Expositions, 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 , 35 (1), American Mathematical Society: 274–304, doi :10.2307/1989325, JSTOR 1989325.
Huntington, EV (1933b), "Álgebra de Boole: una corrección", Transactions of the American Mathematical Society , 35 (2): 557–558, doi :10.2307/1989783, JSTOR 1989783
Mendelson, Elliott (1970), Álgebra de Boole y circuitos de conmutación , Schaum's Outline Series in Mathematics, McGraw–Hill , ISBN 978-0-07-041460-0
Monk, J. Donald; Bonnet, R., eds. (1989), Manual de álgebras de Boole , North-Holland , 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 de conjuntos y lógica , WH Freeman, ISBN 978-0-486-63829-4. Reimpreso por Dover Publications , 1979.

Enlaces externos

"Álgebra de Boole", 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 de Boole" por 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 de Boole". MathWorld .