Álgebra booleana (estructura)
Estructura algebraica modelando operaciones lógicas
En álgebra abstracta, un álgebra booleana o rejilla booleana es una red distributiva complementada. Este tipo de estructura algebraica captura las propiedades esenciales tanto de las operaciones con conjuntos como de las operaciones lógicas. Un álgebra booleana puede verse como una generalización de un álgebra de conjuntos de potencia 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 booleanos tiene una asimetría inherente entre los dos operadores, mientras que los axiomas y teoremas del álgebra booleana expresan la simetría de la teoría descrita por el principio de dualidad.
Boolean lattice of subsets
Historia
El término "álgebra booleana" rinde homenaje 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 luego 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 de álgebra booleana y redes distributivas se debe a la Vorlesungen de 1890 de Ernst Schröder. El primer tratamiento extenso del álgebra booleana en inglés es Universal Algebra de A. N. 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áticas serias 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 y profundos resultados en la lógica matemática y la teoría axiomática de conjuntos utilizando ramificaciones del álgebra booleana, es decir, modelos forzados y de valores booleanos.
Definición
Un álgebra booleana es un sextuple que consta de un conjunto A, equipado con dos operaciones binarias ∧ (llamadas "conocer" o &# 34;y"), ∨ (llamada "join" o "or"), una operación unaria ¬ (llamada "complement" o "not& #34;) y dos elementos 0 y 1 en A (llamados "bottom" y "top", o "menos" y & #34;elemento mayor", también indicado por los símbolos ⊥ y ⊤, respectivamente), tal que para todos los elementos a, b y c de A, se cumplen los siguientes axiomas:
| a Alternativab Alternativa c) =a Alternativa b) c | a ∧b ∧ c) =a ∧ b∧ c | asociatividad
|
| a Alternativa b = b Alternativa a | a ∧ b = b ∧ a | Comutatividad
|
| a Alternativaa ∧ b) a | a ∧a Alternativa b) a | absorción
|
| a Alternativa 0 a | a ∧ 1 = a | identidad
|
| a Alternativab ∧ c) =a Alternativa b∧a Alternativa c)
| a ∧b Alternativa c) =a ∧ b) ∨a ∧ c)
| Distribución
|
| a ∨a = 1
| a ∧ ¬a = 0
| complementos
|
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 los otros axiomas (consulte Propiedades demostradas).
Un álgebra booleana con un solo elemento se denomina álgebra booleana trivial o álgebra booleana degenerada. (En trabajos anteriores, algunos autores requerían que 0 y 1 fueran elementos distintos para excluir este caso).
Se sigue de los últimos tres pares de axiomas anteriores (identidad, distributividad y complementos), o del axioma de absorción, que
- a = b ∧ a si a Alternativa b = b.
La relación ≤ definida por a ≤ b si se cumplen estas condiciones equivalentes, es un orden parcial con el elemento mínimo 0 y el elemento máximo 1. El encuentro a ∧ b y la unión a ∨ 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 sigue que todo complemento es único.
El conjunto de axiomas es autodual en el sentido de que si uno intercambia ∨ con ∧ y 0 con 1 en un axioma, el resultado es nuevamente un axioma. Por lo tanto, al aplicar esta operación a un álgebra booleana (o celosía booleana), se obtiene otra álgebra booleana con los mismos elementos; se llama su dual.
Ejemplos
- El álgebra booleana más simple, el álgebra booleana de dos elementos, tiene sólo dos elementos, 0 y 1, y se define por las reglas:
- Tiene aplicaciones en lógica, interpretando 0 como falso, 1 como verdadero, ∧ as y, latitud como o, y ¬ como no. Las expresiones que implican variables y las operaciones booleanas representan formularios de declaración, y dos de estas expresiones pueden ser iguales usando los axiomas anteriores si y sólo si los formularios de declaración 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; aquí 0 y 1 representan los dos estados diferentes de un poco en un circuito digital, típicamente alta y baja tensión. Los circuitos se describen por expresiones que contienen variables, y dos de estas expresiones son iguales para todos los valores de las variables si y sólo si los circuitos correspondientes tienen el mismo comportamiento de salida de entrada. Además, cada posible comportamiento de salida de entrada puede ser modelado por una expresión booleana adecuada.
- El álgebra booleana de dos elementos también es importante en la teoría general de álgebras booleanas, porque una ecuación que implica varias variables es generalmente verdadera en todos álgebras booleanas si y sólo si es verdad en el álgebra booleana de dos elementos (que puede ser verificada por un algoritmo de fuerza bruta trivial para pequeños números de variables). Esto puede, por ejemplo, ser usado para demostrar que las siguientes leyes (Teoremas de consenso) son generalmente válidos en todos los álgebras booleanos:
- ()a Alternativa b∧a Alternativa c∧b Alternativa c)a Alternativa b∧a Alternativa c)
- ()a ∧ b) ∨a ∧ c) ∨b ∧ c)a ∧ b) ∨a ∧ c)
- El conjunto de potencia (conjunto de todos los subconjuntos) de cualquier conjunto no vacío dado S forma un álgebra booleana, 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 en sí mismo.
- Después del álgebra booleana de dos elementos, el álgebra boo más simple es que se define por el conjunto de potencia de dos átomos:
| | ∧ | 0 | a | b | 1
|
|---|
| 0
| 0 | 0 | 0 | 0
|
|---|
| a
| 0 | a | 0 | a
|
|---|
| b
| 0 | 0 | b | b
|
|---|
| 1
| 0 | a | b | 1
|
|---|
| | | | Alternativa | 0 | a | b | 1
|
|---|
| 0
| 0 | a | b | 1
|
|---|
| a
| a | a | 1 | 1
|
|---|
| b
| b | 1 | b | 1
|
|---|
| 1
| 1 | 1 | 1 | 1
|
|---|
| | | |
- El set A{displaystyle A}
de todos los subconjuntos S{displaystyle S.
que son finitos o cofinitos es un álgebra booleana y un álgebra de conjuntos llamado el álgebra finito-cofinito. Si S{displaystyle S. es infinito entonces el conjunto de todos los subconjuntos cofinitos de S,{displaystyle S,}
que se llama filtro Fréchet, es un ultrafiltro gratis A.{displaystyle A.}
Sin embargo, el filtro Fréchet no es un ultrafiltro en el conjunto de potencia S.{displaystyle S.}
- Empezando con el cálculo proposicional con símbolos de frase κ, forma el álgebra Lindenbaum (es decir, el conjunto de frases en el cálculo proposicional modulo equivalencia lógica). Esta construcción produce un álgebra booleana. Es de hecho el álgebra Boolean libre en generadores κ. Una asignación de verdad en cálculo proposición es entonces un homomorfismo de álgebra booleano de este álgebra al álgebra booleana de dos elementos.
- Dado cualquier orden lineal L con un elemento menos, el álgebra de intervalo es el álgebra más pequeño de subconjuntos L que contiene todos los intervalos medio abiertos [a, b. a está dentro L y b está bien L o igual a ∞. Los álgebras interval son útiles en el estudio de álgebras Lindenbaum–Tarski; cada álgebra booleana contable es isomorfo a un álgebra de intervalo.
Hasse diagrama del álgebra booleana de divisores de 30.
- Para cualquier número natural n, el conjunto de todos los divisores positivos n, definición a≤ ≤ b{displaystyle aleq b}
si a divideciones b, forma una celosía distributiva. Esta celosa es un álgebra booleana si y sólo si n es libre de cuadrados. El elemento inferior y superior de este álgebra booleana es el número natural 1 y n, respectivamente. El complemento a es dado por n/a. El encuentro y la unión de a y b es dado por el mayor divisor común (gcd) y el múltiplo menos común (lcm) de a y b, respectivamente. La adición del anillo a+b es dado por lcm(a,b)/gcd(a,b). La imagen muestra un ejemplo para n = 30. Como contra-ejemplo, considerando el libre de espacio n=60, el mayor divisor común de 30 y su complemento 2 sería 2, mientras que debe ser el elemento inferior 1. - Otros ejemplos de álgebras booleanas surgen de los espacios topológicos: si X es un espacio topológico, luego la colección de todos los subconjuntos de X que son ambas formas abiertas y cerradas un álgebra booleana con las operaciones ∨:= ∪ (unión) y ∧:= ∩ (intersección).
- Si R{displaystyle R.
es un anillo arbitrario entonces su conjunto de Idempotents centrales, que es el conjunto A={}e▪ ▪ R:e2=eyex=xepara todosx▪ ▪ R},{displaystyle A=left{ein R:e^{2}=e{text{ and }ex=xe;{text{ for all };xin Rright}
y e∧ ∧ f:=ef.{displaystyle ewedge f:=ef.}
Homomorfismos e isomorfismos
Un homomorfismo entre dos álgebras booleanas A y B es una función f: A → B tal que para todo a, b en A:
- f()a Alternativa b) f()a) f()b),
- f()a ∧ b) f()a∧ f()b),
- f(0) = 0,
- f1) = 1.
Entonces sigue que f(¬a) = ¬f(a) para todo a en A. La clase de todas las álgebras booleanas, junto con esta noción de morfismo, forma una subcategoría completa de la categoría de redes.
Un isomorfismo entre dos álgebras booleanas 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 booleanas es un isomorfismo si y solo si es biyectivo.
Anillos booleanos
Cada á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 booleana; el elemento identidad multiplicativo del anillo es el 1 del álgebra booleana. Este anillo tiene la propiedad de que a · a = a para todo a en A; Los anillos con esta propiedad se denominan 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.
Como estas dos construcciones son inversas entre sí, podemos decir que todo anillo booleano surge de un álgebra booleana y viceversa. Además, un mapa f: A → 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.
Hsiang (1985) proporcionó un algoritmo basado en reglas para verificar si dos expresiones arbitrarias denotan el mismo valor en cada anillo booleano.
En términos más generales, Boudet, Jouannaud y Schmidt-Schauß (1989) dieron un algoritmo para resolver ecuaciones entre expresiones de anillo booleano arbitrarias.
Empleando 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 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 anillo ideal 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 yo. Además, para cada a ∈ A tenemos que a ∧ -a = 0 ∈ I y luego a ∈ I o -a ∈ I para cada a ∈ A, si I es primo. Un I ideal de A se llama máximo si I ≠ A y si el el único ideal que contiene correctamente I es A mismo. Para un I ideal, si a ∉ I y -a ∉ I, entonces I ∪ {a} o I ∪ {-a} está propiamente contenido en otro ideal J. Por lo tanto, un I no es maximal y, por lo tanto, las nociones de ideal primo e ideal maximal son equivalentes en álgebras booleanas. 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 booleana A es un subconjunto 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 máximo (o primo) ideal en un álgebra booleana es ultrafiltro. Los ultrafiltros se pueden describir alternativamente como morfismos de 2 valores desde A hasta el álgebra booleana de dos elementos. La declaración todo filtro en un álgebra booleana se puede extender a un ultrafiltro se denomina Teorema del ultrafiltro y no se puede probar en ZF, si ZF es consistente. Dentro de ZF, es estrictamente más débil que el axioma de elección.
El teorema del ultrafiltro tiene muchas formulaciones equivalentes: toda álgebra booleana tiene un ultrafiltro, todo ideal en un álgebra booleana puede extenderse a un ideal primo, etc.
Representaciones
Se puede demostrar que cada á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 cada álgebra booleana finita es una potencia de dos.
El célebre teorema de representación de Stone para álgebras booleanas establece que toda álgebra booleana A es isomorfa al álgebra booleana de todas las conjuntos en algún espacio topológico (Hausdorff compacto totalmente desconectado).
Axiomática
| Propiedades probadas |
|---|
| UId1 | | Si x Alternativa o = x para todos x, entonces o = 0
|
|---|
| Prueba: | | Si x Alternativa o = x, entonces
| | | 0
| | = | 0 Alternativa o | por hipótesis
| | = | o Alternativa 0 | por Cmm1 | | = | o | por Idn1 |
| UId2 [dual] Si x ∧ i = x para todos x, entonces i = 1
|
| Idm1 | | x Alternativa x = x |
|---|
| Prueba: | | x Alternativa x | | = | ()x Alternativa x∧ 1 | por Idn2 | | = | ()x Alternativa x∧x ∨x) | por Cpl1 | | = | x Alternativax ∧ ¬x) | por Dst1 | | = | x Alternativa 0 | por Cpl2 | | = | x | por Idn1 |
| Idm2 [dual] x ∧ x = x |
| Bnd1 | | x Alternativa 1 = 1
|
|---|
| Prueba: | | x Alternativa 1
| | = | ()x Alternativa 1) ∧ 1 | por Idn2 | | = | 1 ∧ (x Alternativa 1) | por Cmm2 | | = | ()x ∨x∧x Alternativa 1) | por Cpl1 | | = | x ∨x ∧ 1) | por Dst1 | | = | x ∨x | por Idn2 | | = | 1 | por Cpl1 |
| Bnd2 [dual] x ∧ 0 = 0
|
| Abs1 | | x Alternativax ∧ Sí.) x |
|---|
| Prueba: | | x Alternativax ∧ Sí.)
| | = | ()x ∧ 1) latitudx ∧ Sí.) | por Idn2 | | = | x ∧ (1 ∨ Sí.) | por Dst2 | | = | x ∧Sí. Alternativa 1) | por Cmm1 | | = | x ∧ 1 | por Bnd1 | | = | x | por Idn2 |
| Abs2 [dual] x ∧x Alternativa Sí.) x |
| UNg | | Si x Alternativa xn = 1 y x ∧ xn = 0, entonces xn =x |
|---|
| Prueba: | | Si x Alternativa xn = 1 y x ∧ xn = 0, entonces
| | | xn | | = | xn ∧ 1 | por Idn2 | | = | xn ∧x ∨x) | por Cpl1 | | = | ()xn ∧ x) ∨xn ∧ ¬x) | por Dst2 | | = | ()x ∧ xn) ∨x ∧ xn) | por Cmm2 | | = | 0 ─x ∧ xn) | por hipótesis
| | = | ()x ∧ ¬x) ∨x ∧ xn) | por Cpl2 | | = | (x ∧ x) ∨x ∧ xn) | por Cmm2 | | = | ¬x ∧x Alternativa xn) | por Dst2 | | = | ¬x ∧ 1 | por hipótesis
| | = | ¬x | por Idn2 |
|
| DNg | | ¬x = x |
|---|
| Prueba: | | ¬x Alternativa x = x ∨x = 1 | por Cmm1, Cpl1 | | y | ¬x ∧ x = x ∧ ¬x = 0 | por Cmm2, Cpl2 | | de aquí | x =x | por UNg |
|
| A1 | | x ∨x Alternativa Sí.) = 1
|
|---|
| Prueba: | | x ∨x Alternativa Sí.)
| | = | ()x ∨x Alternativa Sí.) ∧ 1 | por Idn2 | | = | 1 ∧ (x ∨x Alternativa Sí.) | por Cmm2 | | = | ()x ∨x∧x ∨x Alternativa Sí.) | por Cpl1 | | = | x ∨x ∧x Alternativa Sí.) | por Dst1 | | = | x ∨x | por Abs2 | | = | 1 | por Cpl1 |
| A2 [dual] x ∧x ∧ Sí.) = 0
|
| B1 | | ()x Alternativa Sí.) ∨x ∧ ¬Sí.) = 1
|
|---|
| Prueba: | | ()x Alternativa Sí.) ∨x ∧ ¬Sí.)
| | = | ()x Alternativa Sí.¬x∧ ()x Alternativa Sí.¬Sí.) | por Dst1 | | = | (x Alternativax Alternativa Sí.) ∧ (¬)Sí. AlternativaSí. Alternativa x) | por Cmm1 | | = | (x ─x Alternativa Sí.) ∧ (¬)Sí. ─Sí. Alternativa x) | por DNg | | = | 1 ∧ 1 | por A1 | | = | 1 | por Idn2 |
| B2 [dual]x ∧ Sí.∧x ∨Sí.) = 0
|
| C1 | | ()x Alternativa Sí.∧x ∧ ¬Sí.) = 0
|
|---|
| Prueba: | | ()x Alternativa Sí.∧x ∧ ¬Sí.)
| | = | (x ∧ ¬Sí.∧x Alternativa Sí.) | por Cmm2 | | = | (x ∧ ¬Sí.∧ x) ∨x ∧ ¬Sí.∧ Sí.) | por Dst2 | | = | ()x ∧x ∧ ¬Sí.) ∨Sí. ∧Sí. ∧ ¬x) | por Cmm2 | | = | 0 latitud 0 | por A2 | | = | 0 | por Idn1 |
| C2 [dual]x ∧ Sí.) ∨x ∨Sí.) = 1
|
| DMg1 | | ¬x Alternativa Sí.) = ¬x ∧ ¬Sí. |
|---|
| Prueba: | | por B1, C1, y UNg |
| DMg2 [dual] ¬x ∧ Sí.) = ¬x ∨Sí. |
| D1 | | ()x∨Sí.Alternativaz) ∨x = 1
|
|---|
| Prueba: | | ()x AlternativaSí. Alternativa z) ∨x | | = | ¬x Alternativax AlternativaSí. Alternativa z) | por Cmm1 | | = | ¬x ─x AlternativaSí. Alternativa z) | por DNg | | = | 1 | por A1 |
| D2 [dual]x∧Sí.∧z) ∧ ¬x = 0
|
| E1 | | Sí. ∧x∨Sí.Alternativaz) = Sí. |
|---|
| Prueba: | | Sí. ∧x AlternativaSí. Alternativa z)
| | = | ()Sí. ∧ x) ∨Sí. ∧Sí. Alternativa z) | por Dst2 | | = | ()Sí. ∧ x) Sí. | por Abs2 | | = | Sí. AlternativaSí. ∧ x) | por Cmm1 | | = | Sí. | por Abs1 |
| E2 [dual] Sí. Alternativax∧Sí.∧z) = Sí. |
| F1 | | ()x∨Sí.Alternativaz) ∨Sí. = 1
|
|---|
| Prueba: | | ()x AlternativaSí. Alternativa z) ∨Sí. | | = | ¬Sí. Alternativax AlternativaSí. Alternativa z) | por Cmm1 | | = | (Sí. Alternativax AlternativaSí. Alternativa z)) ∧ 1 | por Idn2 | | = | 1 ∧ (¬Sí. Alternativax AlternativaSí. Alternativa z)) | por Cmm2 | | = | ()Sí. ∨Sí.∧Sí. Alternativax AlternativaSí. Alternativa z)) | por Cpl1 | | = | (Sí. Alternativa Sí.∧Sí. Alternativax AlternativaSí. Alternativa z)) | por Cmm1 | | = | ¬Sí. AlternativaSí. ∧x AlternativaSí. Alternativa z)) | por Dst1 | | = | ¬Sí. Alternativa Sí. | por E1 | | = | Sí. ∨Sí. | por Cmm1 | | = | 1 | por Cpl1 |
| F2 [dual]x∧Sí.∧z) ∧ ¬Sí. = 0
|
| G1 | | ()x∨Sí.Alternativaz) ∨z = 1
|
|---|
| Prueba: | | ()x AlternativaSí. Alternativa z) ∨z | | = | ()x Alternativaz Alternativa Sí.) ∨z | por Cmm1 | | = | 1 | por F1 |
| G2 [dual]x∧Sí.∧z) ∧ ¬z = 0
|
| H1 | | ¬(xAlternativaSí.)z∧ x = 0
|
|---|
| Prueba: | | ¬(x Alternativa Sí.) z∧ x | | = | (x Alternativa Sí.) ∧ ¬z∧ x | por DMg1 | | = | (x ∧ ¬Sí.) ∧ ¬z∧ x | por DMg1 | | = | x ∧ (¬x ∧ ¬Sí.) ∧ ¬z) | por Cmm2 | | = | ()x ∧ (¬x ∧ ¬Sí.) ∧ ¬z) latitud 0 | por Idn1 | | = | 0 latitudx ∧ (¬x ∧ ¬Sí.) ∧ ¬z) | por Cmm1 | | = | ()x ∧ ¬x) ∨x ∧ (¬x ∧ ¬Sí.) ∧ ¬z) | por Cpl2 | | = | x ∧x ()x ∧ ¬Sí.) ∧ ¬z) | por Dst2 | | = | x ∧x ∨z ∧x ∧ ¬Sí.)) | por Cmm2 | | = | x ∧ ¬x | por E2 | | = | 0 | por Cpl2 |
| H2 [dual] ¬(x∧Sí.) Dejarz) x = 1
|
| I1 | | ¬(xAlternativaSí.)z∧ Sí. = 0
|
|---|
| Prueba: | | ¬(x Alternativa Sí.) z∧ Sí. | | = | ¬(Sí. Alternativa x) z∧ Sí. | por Cmm1 | | = | 0 | por H1 |
| I2 [dual] ¬(x∧Sí.) Dejarz) Sí. = 1
|
| J1 | | ¬(xAlternativaSí.)z∧ z = 0
|
|---|
| Prueba: | | ¬(x Alternativa Sí.) z∧ z | | = | (x Alternativa Sí.) ∧ ¬z∧ z | por DMg1 | | = | z ∧ (¬)x Alternativa Sí.) ∧ ¬z) | por Cmm2 | | = | z ∧z ∧ ¬x Alternativa Sí.) | por Cmm2 | | = | 0 | por A2 |
| J2 [dual] ¬(x∧Sí.) Dejarz) z = 1
|
| K1 | | ()x AlternativaSí. Alternativa z) ‹x Alternativa Sí.) z) = 1
|
|---|
| Prueba: | | ()x∨Sí.Alternativaz) ‹x Alternativa Sí.) z)
| | = | ()x∨Sí.Alternativaz) ∨ (¬x Alternativa Sí.) ∧ ¬z) | por DMg1 | | = | ()x∨Sí.Alternativaz) ∨ ((¬)x ∧ ¬Sí.) ∧ ¬z) | por DMg1 | | = | ()x∨Sí.Alternativaz) ∨ (¬)x ∧ ¬Sí.) ∧ (x∨Sí.Alternativaz) ∨z) | por Dst1 | | = | (((()x∨Sí.Alternativaz) ∨x∧ ()x∨Sí.Alternativaz) ∨Sí.) ∧ (x∨Sí.Alternativaz) ∨z) | por Dst1 | | = | (1 ∧ 1) ∧ 1 | por D1,F1,G1 | | = | 1 | por Idn2 |
| K2 [dual]x ∧Sí. ∧ z) ∧ ¬(x ∧ Sí.∧ z) = 0
|
| L1 | | ()x AlternativaSí. Alternativa z) ∧ ¬(x Alternativa Sí.) z) = 0
|
|---|
| Prueba: | | ()x AlternativaSí. Alternativa z) ∧ ¬(x Alternativa Sí.) z)
| | = | ¬(xAlternativaSí.)z∧x AlternativaSí. Alternativa z) | por Cmm2 | | = | (xAlternativaSí.)z∧ x) ∨xAlternativaSí.)z∧Sí. Alternativa z) | por Dst2 | | = | (xAlternativaSí.)z∧ x∨ (¬()xAlternativaSí.)z∧ Sí.) ∨xAlternativaSí.)z∧ z) | por Dst2 | | = | 0 Alternativa (0 latitud 0) | por H1,I1,J1 | | = | 0 | por Idn1 |
| L2 [dual]x ∧Sí. ∧ z) ‹x ∧ Sí.∧ z) = 1
|
| Ass1 | | x AlternativaSí. Alternativa z) =x Alternativa Sí.) z |
|---|
| Prueba: | | por K1, L1, UNg, DNg |
| Ass2 [dual] x ∧Sí. ∧ z) =x ∧ Sí.∧ z |
| Abreviaturas
|
|---|
| UId | Identidad única
| | Idm | Idempotence
| | Bnd | Boundaries
| | Abs | Ley de Absorción
| | UNg | Negación única
| | DNg | Doble negación
| | DMg | Ley de De Morgan
| | Ass | Associativity
|
|
| Huntington 1904 Axiomas de álgebra booleana |
|---|
| Idn1 | x Alternativa 0 x | Idn2 | x ∧ 1 = x |
| Cmm1 | x Alternativa Sí. = Sí. Alternativa x | Cmm2 | x ∧ Sí. = Sí. ∧ x |
| Dst1 | x AlternativaSí.∧z) =xAlternativaSí.∧xAlternativaz)
| Dst2 | x ∧Sí.Alternativaz) =x∧Sí.) ∨x∧z)
|
| Cpl1 | x ∨x = 1
| Cpl2 | x ∧ ¬x = 0
|
| Abreviaturas
|
|---|
| Idn | Identidad
| | Cmm | Commutativity
| | Dst | Distribución
| | Cpl | Complementos
|
|
La primera axiomatización de las redes/álgebras booleanas en general fue realizada por el filósofo y matemático inglés Alfred North Whitehead en 1898.
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 ∧, ∨, ¬, e incluso probó las leyes de asociatividad (ver recuadro).
También demostró que estos axiomas son independientes entre sí.
En 1933, Huntington estableció la siguiente axiomatización elegante para el álgebra booleana. Requiere solo una operación binaria + y un símbolo funcional unario n, para leerse como 'complemento', que satisfacen las siguientes leyes:
- Commutativity: x + Sí. = Sí. + x.
- Associativity#x + Sí.) + z = x +Sí. + z).
- Ecuación de Huntington: n()n()x) + Sí.) + n()n()x) + n()Sí.) = x.
Herbert Robbins inmediatamente preguntó: Si la ecuación de Huntington se reemplaza con su dual, a saber:
- 4. Ecuación de Robbins: n()n()x + Sí.) + n()x + n()Sí.) = x,
¿(1), (2) y (4) forman una base para el álgebra booleana? Al llamar a (1), (2) y (4) un álgebra de Robbins, la pregunta entonces es: ¿Toda álgebra de Robbins es un álgebra booleana? Esta pregunta (que llegó a conocerse como la conjetura de Robbins) permaneció abierta durante décadas y se convirtió en la pregunta favorita de Alfred Tarski y sus alumnos. En 1996, William McCune del Laboratorio Nacional de 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 de computadora EQP que diseñó. Para una simplificación de la demostración de McCune, véase Dahn (1998).
Se ha trabajado más para reducir el número de axiomas; ver Axiomas mínimos para álgebra booleana.
Generalizaciones
Al eliminar el requisito de existencia de una unidad de los axiomas del álgebra booleana, se obtienen "álgebras booleanas generalizadas". Formalmente, un retículo distributivo B es un retículo booleano generalizado, si tiene un elemento mínimo 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 el único x tal que (a ∧ b) ∨ x = a y (a ∧ b) ∧ x = 0, decimos que la estructura (B,∧,∨,∖,0) es un álgebra booleana generalizada, mientras que (B,∨,0) es un semiretículo booleano generalizado. Los retículos booleanos generalizados son exactamente los ideales de los retículos booleanos.
Una estructura que satisface todos los axiomas de las álgebras booleanas excepto los dos axiomas de distributividad se denomina retícula ortocomplementada. Las redes ortocomplementadas surgen naturalmente en la lógica cuántica como redes de subespacios cerrados para espacios de Hilbert separables.
