Álgebras booleanas definidas canónicamente

Las álgebras booleanas son modelos de la teoría ecuacional de dos valores; esta definición es equivalente a las definiciones de retículo y anillo.

El álgebra booleana es una rama matemáticamente rica del álgebra abstracta . La Enciclopedia de Filosofía de Stanford define el álgebra booleana como «el álgebra de la lógica bivaluada con conectivas solo sentenciales, o equivalentemente, de las álgebras de conjuntos bajo unión y complementación». ^{[ 1 ]} Así como la teoría de grupos se ocupa de los grupos y el álgebra lineal de los espacios vectoriales , las álgebras booleanas son modelos de la teoría ecuacional de los dos valores 0 y 1 (cuya interpretación no tiene por qué ser numérica). Común a las álgebras booleanas, los grupos y los espacios vectoriales es la noción de estructura algebraica , un conjunto cerrado bajo ciertas operaciones que satisfacen determinadas ecuaciones. ^{[ 2 ]}

Así como existen ejemplos básicos de grupos, como el grupo${\displaystyle \mathbb {Z} }$Además de los números enteros y el grupo simétrico S _n de permutaciones de n objetos, también existen ejemplos básicos de álgebras booleanas como los siguientes.

• El álgebra de dígitos binarios o bits 0 y 1 bajo las operaciones lógicas, incluyendo la disyunción, la conjunción y la negación. Sus aplicaciones incluyen el cálculo proposicional y la teoría de circuitos digitales.
• El álgebra de conjuntos bajo las operaciones de conjuntos, incluyendo la unión , la intersección y el complemento . Sus aplicaciones son muy amplias porque la teoría de conjuntos es la base estándar de las matemáticas .

El álgebra booleana permite, por lo tanto, aplicar los métodos del álgebra abstracta a la lógica matemática y a la lógica digital .

A diferencia de los grupos de orden finito , que presentan complejidad y diversidad y cuya teoría de primer orden solo es decidible en casos especiales, todas las álgebras booleanas finitas comparten los mismos teoremas y poseen una teoría de primer orden decidible. En cambio, las complejidades del álgebra booleana se dividen entre la estructura de las álgebras infinitas y la complejidad algorítmica de su estructura sintáctica .

El álgebra booleana trata la teoría ecuacional del álgebra finita máxima de dos elementos , llamada prototipo booleano , y los modelos de esa teoría, llamados álgebras booleanas . ^{[ 3 ]} Estos términos se definen de la siguiente manera.

Un álgebra es una familia de operaciones sobre un conjunto, llamado conjunto subyacente del álgebra. Tomamos como conjunto subyacente del prototipo booleano {0,1}.

Un álgebra es finita cuando cada una de sus operaciones toma un número finito de argumentos. Para el prototipo, cada argumento de una operación es 0 o 1 , al igual que el resultado de la operación. El álgebra máxima de este tipo consta de todas las operaciones finitas sobre {0,1}.

El número de argumentos que toma cada operación se denomina aridad de la operación. Una operación sobre {0,1} de aridad n , o operación n -aria, puede aplicarse a cualquiera de los ²ⁿ valores posibles para sus n argumentos. Para cada elección de argumentos, la operación puede devolver 0 o 1 , por lo que existen 2n operaciones ^{n -} arias .

El prototipo tiene, por lo tanto, dos operaciones que no toman argumentos, llamadas operaciones zeroarias o nullarias , a saber, cero y uno. Tiene cuatro operaciones unarias , dos de las cuales son operaciones constantes, otra es la identidad, y la más utilizada, llamada negación , devuelve el opuesto de su argumento: 1 si 0 , 0 si 1. Tiene dieciséis operaciones binarias ; de nuevo, dos de estas son constantes, otra devuelve su primer argumento, otra más devuelve su segundo, una se llama conjunción y devuelve 1 si ambos argumentos son 1 y 0 en caso contrario, otra se llama disyunción y devuelve 0 si ambos argumentos son 0 y 1 en caso contrario, y así sucesivamente. El número de operaciones ( n +1) -arias en el prototipo es el cuadrado del número de operaciones n -arias, por lo que hay 16² = 256 ^operaciones ternarias, 256² = 65 536 ^operaciones cuaternarias, y así sucesivamente.

Una familia se indexa mediante un conjunto de índices . En el caso de una familia de operaciones que forman un álgebra, los índices se denominan símbolos de operación , que constituyen el lenguaje de dicha álgebra. La operación indexada por cada símbolo se denomina denotación o interpretación de ese símbolo. Cada símbolo de operación especifica la aridad de su interpretación, por lo que todas las posibles interpretaciones de un símbolo tienen la misma aridad. En general, es posible que un álgebra interprete símbolos distintos con la misma operación, pero este no es el caso del prototipo, cuyos símbolos están en correspondencia biunívoca con sus operaciones. Por lo tanto, el prototipo tiene 2 ^{2 n} n -arios símbolos de operación, denominados símbolos de operación booleanos y que forman el lenguaje del álgebra booleana. Solo unas pocas operaciones tienen símbolos convencionales, como ¬ para la negación, ∧ para la conjunción y ∨ para la disyunción. ^{[ 4 ]} Es conveniente considerar el i -ésimo símbolo n -ario como ⁿ f _i como se hace más adelante en la sección sobre tablas de verdad .

Una teoría ecuacional en un lenguaje dado consiste en ecuaciones entre términos construidos a partir de variables usando símbolos de ese lenguaje. Las ecuaciones típicas en el lenguaje del álgebra booleana son x ∧ y = y ∧ x , x ∧ x = x , x ∧¬ x = y ∧¬ y , y x ∧ y = x .

Un álgebra satisface una ecuación cuando esta se cumple para todos los valores posibles de sus variables en dicha álgebra, interpretando los símbolos de las operaciones según lo especificado por esa álgebra. Las leyes del álgebra booleana son las ecuaciones en el lenguaje del álgebra booleana que satisface el prototipo. Los tres primeros ejemplos anteriores son leyes booleanas, pero no el cuarto, ya que 1∧0 ≠ 1 .

La teoría de ecuaciones de un álgebra es el conjunto de todas las ecuaciones que satisface dicho álgebra. Por lo tanto, las leyes del álgebra booleana constituyen la teoría de ecuaciones del prototipo booleano.

Un modelo de una teoría es un álgebra que interpreta los símbolos de las operaciones en el lenguaje de la teoría y satisface las ecuaciones de la misma.

Un álgebra booleana es cualquier modelo de las leyes del álgebra booleana.

Es decir, un álgebra booleana es un conjunto y una familia de operaciones sobre él que interpretan los símbolos de las operaciones booleanas y satisfacen las mismas leyes que el prototipo booleano.

Si definimos un homólogo de un álgebra como un modelo de la teoría ecuacional de esa álgebra, entonces un álgebra booleana puede definirse como cualquier homólogo del prototipo.

Ejemplo 1. El prototipo booleano es un álgebra booleana, puesto que satisface trivialmente sus propias leyes. Es, por lo tanto, el álgebra booleana prototípica. No la denominamos así inicialmente para evitar cualquier apariencia de circularidad en la definición.

No es necesario que todas las operaciones se indiquen explícitamente. Una base es cualquier conjunto a partir del cual se pueden obtener las demás operaciones mediante composición. Un álgebra booleana puede definirse a partir de varias bases diferentes. Tres bases de uso común para el álgebra booleana son la base reticular, la base anular y la base de Sheffer ( o NAND). Estas bases confieren, respectivamente, un carácter lógico, aritmético y de parsimonia.

• La base reticular tuvo su origen en el siglo XIX con el trabajo de Boole , Peirce y otros que buscaban una formalización algebraica de los procesos de pensamiento lógico.
• La base de anillos surgió en el siglo XX con el trabajo de Zhegalkin y Stone y se convirtió en la base preferida para los algebristas que llegaban al tema desde una formación en álgebra abstracta . La mayoría de los tratamientos del álgebra booleana asumen la base reticular, una excepción notable es Halmos [1963], cuya formación en álgebra lineal evidentemente le hizo apreciar la base de anillos. ^{[ 5 ]}
• Dado que todas las operaciones finitas en {0,1} se pueden definir en términos de la puerta NAND de Sheffer (o su NOR dual), la base económica resultante se ha convertido en la base de elección para analizar circuitos digitales , en particular matrices de puertas en electrónica digital .

Los elementos comunes de las bases reticular y anular son las constantes 0 y 1, y una operación binaria asociativa conmutativa , denominada intersección x ∧ y en la base reticular y multiplicación xy en la base anular. La distinción es meramente terminológica. La base reticular incluye además las operaciones de unión , x ∨ y , y complemento , ¬ x . La base anular, en cambio, incluye la operación aritmética de suma x ⊕ y ( se utiliza el símbolo ⊕ en lugar de + porque a este último a veces se le da la lectura booleana de unión).

Ser una base implica producir todas las demás operaciones por composición, por lo que cualesquiera dos bases deben ser intertraducibles. La base reticular traduce x ∨ y a la base anular como x ⊕ y ⊕ xy , y ¬ x como x ⊕1 . Recíprocamente, la base anular traduce x ⊕ y a la base reticular como ( x ∨ y )∧¬( x ∧ y ) .

Ambas bases permiten definir álgebras booleanas mediante un subconjunto de las propiedades de igualdad de las operaciones booleanas. Para la base reticular, basta con definir un álgebra booleana como una retícula distributiva que satisface x ∧¬ x = 0 y x ∨¬ x = 1 , denominada retícula distributiva complementada . La base anular transforma un álgebra booleana en un anillo booleano , concretamente un anillo que satisface x ² = x .

Emil Post dio una condición necesaria y suficiente para que un conjunto de operaciones sea una base para las operaciones booleanas no nulas. Una propiedad no trivial es aquella que comparten algunas, pero no todas, las operaciones que componen una base. Post enumeró cinco propiedades no triviales de las operaciones, identificables con las cinco clases de Post , cada una preservada por composición, y demostró que un conjunto de operaciones formaba una base si, para cada propiedad, el conjunto contenía una operación que carecía de esa propiedad. (El recíproco del teorema de Post , que extiende "si" a " si y solo si ", es la fácil observación de que una propiedad de entre estas cinco que se cumple para cada operación en una base candidata también se cumplirá para cada operación formada por composición a partir de esa candidata, por lo que, debido a la no trivialidad de esa propiedad, la candidata no será una base). Las cinco propiedades de Post son:

• monótono , ninguna transición de entrada de 0 a 1 puede causar una transición de salida de 1 a 0;
• afín , representable con polinomios de Zhegalkin que carecen de términos bilineales o superiores, por ejemplo x ⊕ y ⊕1 pero no xy ;
• autodual , de modo que complementar todas las entradas complementa la salida, como con x , o el operador de mediana xy ⊕ yz ⊕ zx , o sus negaciones;
• estricto (asignar la entrada de todos ceros a cero);
• costrict (mapear todos los unos a uno).

La operación NAND (doble NOR) carece de todas estas características, formando así una base por sí misma.

Las operaciones finitas en {0,1} pueden representarse como tablas de verdad , considerando 0 y 1 como los valores de verdad falso y verdadero . ^{[ 6 ]} Pueden organizarse de manera uniforme e independiente de la aplicación, lo que nos permite nombrarlas, o al menos numerarlas, individualmente. Estos nombres proporcionan una abreviatura conveniente para las operaciones booleanas. Los nombres de las operaciones n -arias son números binarios de 2 ⁿ bits. Al haber 2 ^{2 n} de estas operaciones, no se puede pedir una nomenclatura más sucinta. Nótese que cada operación finita puede llamarse función de conmutación .

Esta disposición y la nomenclatura asociada de las operaciones se ilustran aquí en su totalidad para aridades de 0 a 2.

Estas tablas continúan en aridades más altas, con 2 ⁿ filas en la aridad n , cada fila da una valoración o vinculación de las n variables x ₀ ,... x _{n −1} y cada columna encabezada ⁿ f _i da el valor ⁿ f _i ( x ₀ ,..., x _{n −1} ) de la i -ésima operación n -aria en esa valoración. Las operaciones incluyen las variables, por ejemplo ¹ f ₂ es x ₀ mientras que ² f ₁₀ es x ₀ (como dos copias de su contraparte unaria) y ² f ₁₂ es x ₁ (sin contraparte unaria). La negación o complemento ¬ x ₀ aparece como ¹ f ₁ y nuevamente como ² f ₅ , junto con ² f ₃ ( ¬ x ₁ , que no apareció en aridad 1), la disyunción o unión x ₀ ∨ x ₁ como ² f ₁₄ , la conjunción o intersección x ₀ ∧ x ₁ como ² f ₈ , la implicación x ₀ → x ₁ como ² f ₁₃ , la diferencia simétrica exclusiva-or x ₀ ⊕ x ₁ como ² f ₆ , la diferencia de conjuntos x ₀ − x ₁ como ² f ₂ , y así sucesivamente.

Como detalle menor, más importante por su forma que por su contenido, las operaciones de un álgebra se organizan tradicionalmente como una lista. Aunque aquí indexamos las operaciones de un álgebra booleana mediante las operaciones finitas en {0,1}, la presentación de la tabla de verdad anterior ordena fortuitamente las operaciones primero por aridad y segundo por la disposición de las tablas para cada aridad. Esto permite organizar el conjunto de todas las operaciones booleanas en el formato de lista tradicional. El orden de la lista para las operaciones de una aridad dada se determina mediante las dos reglas siguientes.

(i) La i -ésima fila en la mitad izquierda de la tabla es la representación binaria de i con su bit menos significativo o 0 a la izquierda (orden "little-endian", propuesto originalmente por Alan Turing , por lo que no sería descabellado llamarlo orden de Turing).

(ii) La j -ésima columna de la mitad derecha de la tabla es la representación binaria de j , también en orden little-endian. En efecto, el subíndice de la operación es la tabla de verdad de dicha operación. Por analogía con la numeración de Gödel de las funciones computables, esta numeración de las operaciones booleanas podría denominarse numeración booleana.

Cuando se programa en C o Java, la disyunción bit a bit se denotax | y, conjunciónx e yy negación~ xPor lo tanto, un programa puede representar, por ejemplo, la operación x ∧( y ∨ z ) en estos lenguajes comox & ( y | z ), habiendo establecido previamentex  =  0xaa,y  = 0xcc, yz  = 0xf0(el "0x" indica que la siguiente constante debe leerse en hexadecimal o base 16), ya sea asignándola a variables o definiéndola como macros. Estas constantes de un byte (ocho bits) corresponden a las columnas de las variables de entrada en la extensión de las tablas anteriores a tres variables. Esta técnica se utiliza casi universalmente en hardware de gráficos rasterizados para proporcionar una variedad flexible de formas de combinar y enmascarar imágenes; las operaciones típicas son ternarias y actúan simultáneamente sobre los bits de origen, destino y máscara.

Las operaciones booleanas n -arias constituyen en sí mismas un álgebra de conjuntos potencia 2 ^W , es decir, cuando W se toma como el conjunto de 2 ⁿ valoraciones de las n entradas. En términos del sistema de nombres de operaciones ⁿ f _i donde i en binario es una columna de una tabla de verdad, las columnas se pueden combinar con operaciones booleanas de cualquier aridad para producir otras columnas presentes en la tabla. Es decir, podemos aplicar cualquier operación booleana de aridad m a m operaciones booleanas de aridad n para producir una operación booleana de aridad n , para cualesquiera m y n .

La importancia práctica de esta convención, tanto para software como para hardware, radica en que las operaciones booleanas n -arias pueden representarse como palabras de la longitud adecuada. Por ejemplo, cada una de las 256 operaciones booleanas ternarias puede representarse como un byte sin signo. Las operaciones lógicas disponibles, como AND y OR, pueden utilizarse para formar nuevas operaciones. Si tomamos x , y y z (prescindiendo por ahora de las variables con subíndices) como 10101010 , 11001100 y 11110000 respectivamente (170, 204 y 240 en decimal, 0xaa , 0xcc y 0xf0 en hexadecimal), sus conjunciones por pares son x ∧ y  = 10001000 , y ∧ z  = 11000000 y z ∧ x  = 10100000 , mientras que sus disyunciones por pares son x ∨ y  = 11101110 , y ∨ z  = 11111100 y z ∨ x  = 11111010 . La disyunción de las tres conjunciones es 11101000 , que también resulta ser la conjunción de tres disyunciones. Por lo tanto, hemos calculado, con una docena de operaciones lógicas sobre bytes, que las dos operaciones ternarias

${\displaystyle (x\land y)\lor (y\land z)\lor (z\land x)}$

y

${\displaystyle (x\lor y)\land (y\lor z)\land (z\lor x)}$

En realidad son la misma operación. Es decir, hemos demostrado la identidad de la ecuación.

${\displaystyle (x\land y)\lor (y\land z)\lor (z\land x)=(x\lor y)\land (y\lor z)\land (z\lor x)}$,

para el álgebra booleana de dos elementos. Por definición de "álgebra booleana", esta identidad debe cumplirse en toda álgebra booleana.

Esta operación ternaria formó incidentalmente la base de las álgebras booleanas ternarias de Grau [1947], que él axiomatizó en términos de esta operación y negación. La operación es simétrica, lo que significa que su valor es independiente de cualquiera de las 3!  = 6 permutaciones de sus argumentos. Las dos mitades de su tabla de verdad 11101000 son las tablas de verdad para ∨ , 1110 , y ∧ , 1000 , por lo que la operación puede expresarse como si z entonces x ∨ y sino x ∧ y . Dado que es simétrica, puede expresarse igualmente bien como si x entonces y ∨ z sino y ∧ z , o si y entonces z ∨ x sino z ∧ x . Vista como una etiqueta del 3-cubo de 8 vértices, la mitad superior está etiquetada como 1 y la mitad inferior como 0; Por esta razón se le ha llamado operador de mediana , con la evidente generalización a cualquier número impar de variables (impar para evitar el empate cuando exactamente la mitad de las variables son 0).

La técnica que acabamos de usar para demostrar una identidad del álgebra booleana puede generalizarse a todas las identidades de forma sistemática, lo que puede considerarse una axiomatización sólida y completa de las leyes ecuacionales de la lógica booleana . La formulación habitual de un sistema de axiomas consiste en un conjunto de axiomas que "preparan el terreno" con algunas identidades iniciales, junto con un conjunto de reglas de inferencia para deducir las identidades restantes a partir de los axiomas y las identidades previamente demostradas. En principio, es deseable tener un número finito de axiomas; sin embargo, en la práctica no es necesario, ya que resulta igualmente eficaz tener un esquema de axiomas finito con un número infinito de instancias, cada una de las cuales, al usarse en una demostración, puede verificarse fácilmente como una instancia válida, el enfoque que seguimos aquí.

Las identidades booleanas son afirmaciones de la forma s  = t donde s y t son términos n -arios, por lo que aquí entenderemos términos cuyas variables están limitadas a x ₀ a x _n-1 . Un término n -ario es un átomo o una aplicación. Una aplicación ^m f _i ( t ₀ ,..., t _{m ​​-1} ) es un par que consta de una operación m -aria ^m f _i y una lista o m- tupla ( t ₀ ,..., t _{m ​​-1} ) de m términos n- arios llamados operandos .

Cada término tiene asociado un número natural llamado altura . Los átomos tienen altura cero, mientras que las aplicaciones tienen altura uno más la altura de su operando más alto.

Ahora bien, ¿qué es un átomo? Convencionalmente, un átomo es una constante (0 o 1) o una variable x _i donde 0 ≤ i < n . Para la técnica de demostración aquí, es conveniente definir los átomos como operaciones n -arias ⁿ f _i , que, aunque se tratan aquí como átomos, significan lo mismo que los términos ordinarios de la forma exacta ⁿ f _i ( x ₀ ,..., x _{n -1} ) (exacta en el sentido de que las variables deben enumerarse en el orden mostrado sin repetición ni omisión). Esto no es una restricción porque los átomos de esta forma incluyen todos los átomos ordinarios, a saber, las constantes 0 y 1, que surgen aquí como las operaciones n -arias ⁿ f ₀ y ⁿ f ₋₁ para cada n (abreviando 2 ^{2 n} −1 a −1 ), y las variables x ₀ ,..., x _{n -1} como se puede ver en las tablas de verdad donde x ₀ aparece como la operación unaria ¹ f ₂ y la operación binaria ² f ₁₀ mientras que x ₁ aparece como ² f ₁₂ .

El siguiente esquema axiomático y tres reglas de inferencia axiomatizan el álgebra booleana de términos n -arios.

A1 . ^m f _i ( ⁿ f _{j 0} ,..., ⁿ f _{j m -1} )  = ⁿ f _{i o ĵ} donde ( i o ĵ ) _v  = i _{ĵ v} , siendo ĵ la j transpuesta, definida por ( ĵ _v ) _u  = ( j _u ) _v .

R1 . Sin premisas, infiere t  = t .

R2 . De s  = u y t  = u se infiere s  = t donde s , t y u son términos n -arios.

R3 . De s ₀  = t ₀  ,  ...  , s _{m -1} = t _{m -1}   infiere ^m f _i ( s ₀ ,..., s _{m -1} )  = ^m f _i ( t ₀ ,..., t _{m ​​-1} ) , donde todos los términos s _i , t _i son n -arios.

El significado de la condición lateral en A1 es que i o ĵ es aquel número de 2 ⁿ bits cuyo v -ésimo bit es el v - _ésimo bit de ĵ de i , donde los rangos de cada cantidad son u : m , v : 2 ⁿ , j _u : 2 ^{2 n} , y ĵ _v : 2 ^m . (Así pues, j es una m -tupla de números de 2 ⁿ bits, mientras que ĵ, como transpuesta de j, es una 2 ^n- tupla de números de m bits. Por lo tanto, tanto j como ĵ contienen m 2 ⁿ bits).

A1 es un esquema axiomático más que un axioma en virtud de contener metavariables , a saber , m , i , n y j ₀ a j _m-1 . Los axiomas reales de la axiomatización se obtienen estableciendo las metavariables a valores específicos. Por ejemplo, si tomamos m  = n  = i  = j ₀  = 1 , podemos calcular los dos bits de i o ĵ a partir de i ₁  = 0 e i ₀  = 1 , de modo que i o ĵ  = 2 (o 10 cuando se escribe como un número de dos bits). La instancia resultante, a saber, ¹ f ₁ ( ¹ f ₁ )  = ¹ f ₂ , expresa el conocido axioma ¬¬ x  = x de doble negación. La regla R3 nos permite entonces inferir ¬¬¬ x  = ¬ x tomando s ₀ como ¹ f ₁ ( ¹ f ₁ ) o ¬¬ x ₀ , t ₀ como ¹ f ₂ o x ₀ , y ^m f _i como ¹ f ₁ o ¬ .

Para cada m y n, solo hay un número finito de axiomas que instancian A1 , a saber, 2 ^{2 m} × (2 ^{2 n} ) ^m . Cada instancia se especifica mediante 2 ^m + m 2 ⁿ bits.

Consideramos R1 como una regla de inferencia, aunque se asemeja a un axioma al carecer de premisas, porque es una regla independiente del dominio, junto con R2 y R3, común a todas las axiomatizaciones ecuacionales, ya sean de grupos, anillos o cualquier otra variedad. La única entidad específica de las álgebras booleanas es el esquema axiomático A1 . De esta manera, al hablar de diferentes teorías ecuacionales, podemos dejar de lado las reglas, considerándolas independientes de las teorías particulares, y centrarnos en los axiomas como la única parte del sistema axiomático que caracteriza la teoría ecuacional específica en cuestión.

Esta axiomatización es completa, lo que significa que toda ley booleana s  = t es demostrable en este sistema. Primero se muestra por inducción sobre la altura de s que toda ley booleana para la cual t es atómico es demostrable, usando R1 para el caso base (ya que los átomos distintos nunca son iguales) y A1 y R3 para el paso de inducción ( s una aplicación). Esta estrategia de prueba equivale a un procedimiento recursivo para evaluar s para producir un átomo. Luego, para probar s  = t en el caso general cuando t puede ser una aplicación, se usa el hecho de que si s  = t es una identidad, entonces s y t deben evaluarse al mismo átomo, llamémoslo u . Así que primero se prueba s  = u y t  = u como se indicó anteriormente, es decir, se evalúan s y t usando A1 , R1 y R3 , y luego se invoca R2 para inferir s  = t .

En A1 , si consideramos el número n ^m como el tipo de función m → n , y m _n como la aplicación m ( n ) , podemos reinterpretar los números i , j , ĵ , e i o ĵ como funciones de tipo i :  ( m →2)→2 , j : m →(( n →2)→2)  , ĵ :  ( n →2)→( m →2) , e i o ĵ :  ( n →2)→2 . La definición ( i o ĵ ) _v  = i _{ĵ v} en A1 se traduce entonces en ( i o ĵ )( v )  = i ( ĵ ( v )) , es decir, i o ĵ se define como la composición de i y ĵ entendidos como funciones. Así pues, el contenido de A1 se reduce a definir la aplicación del término como esencialmente composición, salvo la necesidad de transponer la m -tupla j para que los tipos coincidan adecuadamente para la composición. Esta composición es la de la categoría de conjuntos potencia y sus funciones mencionada anteriormente por Lawvere. De este modo, hemos traducido los diagramas conmutativos de dicha categoría, como la teoría ecuacional de las álgebras booleanas, a las consecuencias ecuacionales de A1 como la representación lógica de esa ley de composición en particular.

Debajo de cada álgebra booleana B hay un conjunto parcialmente ordenado o poset ( B ,≤) . La relación de orden parcial se define por x ≤ y solo cuando x  = x ∧ y , o equivalentemente cuando y  = x ∨ y . Dado un conjunto X de elementos de un álgebra booleana, una cota superior en X es un elemento y tal que para cada elemento x de X , x ≤ y , mientras que una cota inferior en X es un elemento y tal que para cada elemento x de X , y ≤ x .

Un sup de X es una cota superior mínima de X , es decir, una cota superior de X menor o igual que cualquier otra cota superior de X. De manera similar, un inf de X es una cota inferior máxima de X. El sup de x e y siempre existe en el poset subyacente de un álgebra booleana, siendo x ∨ y , y de igual modo existe su inf, es decir, x ∧ y . El sup vacío es 0 (el elemento inferior) y el inf vacío es 1 (el superior). De ello se deduce que todo conjunto finito tiene tanto un sup como un inf. Los subconjuntos infinitos de un álgebra booleana pueden o no tener un sup y/o un inf; en un álgebra de conjuntos potencia, siempre los tienen.

Cualquier conjunto parcialmente ordenado ( B , ≤) tal que cada par x , y de elementos tenga tanto un supremo como un ínfimo se denomina retículo . Escribimos x ∨ y para el supremo y x ∧ y para el ínfimo. El conjunto parcialmente ordenado subyacente de un álgebra booleana siempre forma un retículo. Se dice que el retículo es distributivo cuando x ∧ ( y ∨ z )  = ( x ∧ y ) ∨ ( x ∧ z ) , o equivalentemente cuando x ∨ ( y ∧ z )  = ( x ∨ y ) ∧ ( x ∨ z ) , ya que una ley implica la otra en un retículo. Estas son leyes del álgebra booleana por las cuales el conjunto parcialmente ordenado subyacente de un álgebra booleana forma un retículo distributivo.

Dado un retículo con un elemento inferior 0 y un elemento superior 1, un par de elementos x , y se denomina complementario cuando x ∧ y  = 0 y x ∨ y  = 1 , y entonces decimos que y es el complemento de x y viceversa. Cualquier elemento x de un retículo distributivo con superior e inferior puede tener como máximo un complemento. Cuando cada elemento de un retículo tiene un complemento, el retículo se denomina complementado. De ello se deduce que, en un retículo distributivo complementado, el complemento de un elemento siempre existe y es único, lo que convierte al complemento en una operación unaria. Además, todo retículo distributivo complementado forma un álgebra de Boole, y viceversa, todo álgebra de Boole forma un retículo distributivo complementado. Esto proporciona una definición alternativa de álgebra de Boole, a saber, como cualquier retículo distributivo complementado. Cada una de estas tres propiedades puede axiomatizarse con un número finito de ecuaciones, de donde estas ecuaciones tomadas en conjunto constituyen una axiomatización finita de la teoría ecuacional de las álgebras booleanas.

En una clase de álgebras definida como el conjunto de todos los modelos de un sistema de ecuaciones, es habitual que algunas álgebras satisfagan más ecuaciones de las necesarias para pertenecer a dicha clase. La clase de álgebras booleanas es singular porque, con una sola excepción, todas satisfacen exactamente las identidades booleanas y ninguna más. La excepción es el álgebra booleana de un elemento, que necesariamente satisface todas las ecuaciones, incluso x  = y , y por lo tanto a veces se la denomina álgebra booleana inconsistente.

Un homomorfismo booleano es una función h : A → B entre álgebras booleanas A , B tal que para cada operación booleana ^m f _i :

$${\displaystyle h(^{m}\!f_{i}(x_{0},...,x_{m-1}))={}^{m}\!f_{i}(h(x_{0},...,x_{m-1}))}$$

La categoría Bool de álgebras booleanas tiene como objetos todas las álgebras booleanas y como morfismos los homomorfismos booleanos entre ellas.

Existe un único homomorfismo del álgebra booleana de dos elementos 2 a cualquier álgebra booleana, ya que los homomorfismos deben preservar las dos constantes, que son los únicos elementos de 2. Un álgebra booleana con esta propiedad se denomina álgebra booleana inicial . Se puede demostrar que cualesquiera dos álgebras booleanas iniciales son isomorfas, por lo que, salvo isomorfismo, 2 es el álgebra booleana inicial.

En sentido contrario, pueden existir muchos homomorfismos de un álgebra booleana B a 2. Cualquier homomorfismo de este tipo divide B en aquellos elementos asignados a 1 y aquellos asignados a 0. El subconjunto de B que consta de los primeros se denomina ultrafiltro de B. Cuando B es finito, sus ultrafiltros se emparejan con sus átomos; un átomo se asigna a 1 y el resto a 0. Cada ultrafiltro de B consta, por lo tanto, de un átomo de B y todos los elementos superiores a él; por consiguiente, exactamente la mitad de los elementos de B están en el ultrafiltro, y hay tantos ultrafiltros como átomos.

Para las álgebras booleanas infinitas, la noción de ultrafiltro se vuelve considerablemente más delicada. Los elementos mayores o iguales a un átomo siempre forman un ultrafiltro, pero también muchos otros conjuntos; por ejemplo, en el álgebra booleana de conjuntos finitos y cofinitos de enteros, los conjuntos cofinitos forman un ultrafiltro aunque ninguno de ellos sea un átomo. De igual modo, el conjunto potencia de los enteros tiene entre sus ultrafiltros el conjunto de todos los subconjuntos que contienen un entero dado; hay una cantidad numerable de estos ultrafiltros "estándar", que pueden identificarse con los enteros mismos, pero hay una cantidad incontable de ultrafiltros "no estándar". Estos forman la base del análisis no estándar , proporcionando representaciones para objetos clásicamente inconsistentes como los infinitesimales y las funciones delta.

Recordemos la definición de sup e inf de la sección anterior sobre el orden parcial subyacente de un álgebra booleana. Un álgebra booleana completa es aquella cuyos subconjuntos, incluso los infinitos, poseen tanto un sup como un inf. Gaifman [1964] y Hales [1964] demostraron independientemente que no existen álgebras booleanas completas libres infinitas . Esto sugiere que una lógica con operaciones de tamaño infinito puede tener muchos términos de clase, al igual que una lógica con operaciones finitas puede tener infinitos términos.

Sin embargo, existe otro enfoque para introducir operaciones booleanas infinitas: simplemente eliminar "finitario" de la definición de álgebra booleana. Un modelo de la teoría ecuacional del álgebra de todas las operaciones en {0,1} de aridad hasta la cardinalidad del modelo se denomina álgebra booleana atómica completa, o CABA . (En lugar de esta incómoda restricción de aridad, podríamos permitir cualquier aridad, lo que conllevaría otra incomodidad, ya que la signatura sería mayor que cualquier conjunto, es decir, una clase propia. Una ventaja de este último enfoque es que simplifica la definición de homomorfismo entre CABA de diferente cardinalidad ). Dicha álgebra puede definirse equivalentemente como un álgebra booleana completa que es atómica , lo que significa que cada elemento es un supremo de algún conjunto de átomos. Existen CABA libres para todas las cardinalidades de un conjunto V de generadores , concretamente el álgebra de conjuntos potencia 2 ^{2 V} , que es la generalización obvia de las álgebras booleanas libres finitas. Esto rescata elegantemente la lógica booleana infinita del destino al que parecía condenarla el resultado de Gaifman-Hales.

La inexistencia de álgebras booleanas completas libres se debe a la falta de extensión adecuada de las ecuaciones de la lógica booleana a todas las leyes que deberían cumplirse para la conjunción y disyunción infinitas, en particular, a la omisión de la distributividad en la definición de álgebra booleana completa. Un álgebra booleana completa se denomina completamente distributiva cuando las conjunciones arbitrarias se distribuyen sobre las disyunciones arbitrarias y viceversa. Un álgebra booleana es un CABA si y solo si es completa y completamente distributiva, lo que proporciona una tercera definición de CABA. Una cuarta definición es como cualquier álgebra booleana isomorfa a un álgebra de conjuntos potencia.

Un homomorfismo completo es aquel que preserva todos los supremos existentes, no solo los supremos finitos, y lo mismo ocurre con los infs. La categoría CABA de todos los CABA y sus homomorfismos completos es dual a la categoría de conjuntos y sus funciones, lo que significa que es equivalente a la opuesta de esa categoría (la categoría resultante de invertir todos los morfismos). Las cosas no son tan simples para la categoría Bool de álgebras booleanas y sus homomorfismos, que Marshall Stone demostró en efecto (aunque carecía tanto del lenguaje como del marco conceptual para hacer explícita la dualidad) que es dual a la categoría de espacios de Hausdorff compactos totalmente disconexos , posteriormente llamados espacios de Stone .

Otra clase infinitaria intermedia entre las álgebras booleanas y las álgebras booleanas completas es la noción de sigma-álgebra . Esta se define de forma análoga a las álgebras booleanas completas, pero con supremos e ínfimos limitados a una aridad numerable. Es decir, una sigma-álgebra es un álgebra booleana con supremos e ínfimos numerables. Dado que los supremos e ínfimos tienen cardinalidad acotada , a diferencia de lo que ocurre con las álgebras booleanas completas , el resultado de Gaifman-Hales no se aplica y existen sigma-álgebras libres . Sin embargo, a diferencia de lo que ocurre con las CABA, la sigma-álgebra libre con generación numerable no es un álgebra de conjuntos potencia.

Ya hemos encontrado varias definiciones de álgebra booleana, como modelo de la teoría ecuacional del álgebra de dos elementos, como retículo distributivo complementado, como anillo booleano y como functor que preserva el producto de cierta categoría (Lawvere). Dos definiciones más que vale la pena mencionar son:

Piedra (1936)

Un álgebra booleana es el conjunto de todos los conjuntos abiertos y cerrados de un espacio topológico . No es una limitación exigir que el espacio sea un espacio de Hausdorff compacto totalmente disconexo o un espacio de Stone ; es decir, toda álgebra booleana surge de esta manera, salvo isomorfismo . Además, si las dos álgebras booleanas formadas como conjuntos abiertos y cerrados de dos espacios de Stone son isomorfas, también lo son los propios espacios de Stone, lo cual no ocurre con espacios topológicos arbitrarios. Esta es simplemente la dualidad inversa a la mencionada anteriormente, de las álgebras booleanas a los espacios de Stone . Esta definición se desarrolla con más detalle en la siguiente definición.

Johnstone (1982)

Un álgebra booleana es un colímite filtrado de álgebras booleanas finitas.

(La circularidad de esta definición puede eliminarse sustituyendo "álgebra booleana finita" por "conjunto potencia finito" equipado con las operaciones booleanas interpretadas de forma estándar para conjuntos potencia).

Para poner esto en perspectiva, los conjuntos infinitos surgen como colímites filtrados de conjuntos finitos, los CABA infinitos como límites filtrados de álgebras de conjuntos potencia finitas, y los espacios de Stone infinitos como límites filtrados de conjuntos finitos. Así, si se parte de los conjuntos finitos y se pregunta cómo se generalizan a objetos infinitos, hay dos maneras: "sumarlos" da como resultado conjuntos ordinarios o inductivos, mientras que "multiplicarlos" da como resultado espacios de Stone o conjuntos profinitos . La misma elección existe para las álgebras de conjuntos potencia finitas como duales de los conjuntos finitos: la suma produce álgebras booleanas como objetos inductivos, mientras que la multiplicación produce CABA o álgebras de conjuntos potencia como objetos profinitos.

Una característica distintiva es que la topología subyacente de los objetos así construidos, cuando se definen como Hausdorff , es discreta para objetos inductivos y compacta para objetos profinitos. La topología de los espacios Hausdorff finitos es siempre discreta y compacta, mientras que para los espacios infinitos, "discreto" y "compacto" son mutuamente excluyentes. Por lo tanto, al generalizar álgebras finitas (de cualquier tipo, no solo booleanas) a infinitas, "discreto" y "compacto" se separan, y hay que elegir cuál conservar. La regla general, tanto para álgebras finitas como infinitas, es que las álgebras finitas son discretas, mientras que sus duales son compactas y presentan operaciones infinitas. Entre estos dos extremos, existen muchas álgebras booleanas infinitas intermedias cuya topología no es ni discreta ni compacta.

• Birkhoff, Garrett (1935). "Sobre la estructura de las álgebras abstractas". Actas Matemáticas de la Sociedad Filosófica de Cambridge . 31 (4): 433– 454. Bibcode : 1935PCPS...31..433B . doi : 10.1017/s0305004100013463 .
• Boole, George (2003) [1854]. Una investigación de las leyes del pensamiento . Prometheus Books. ISBN 978-1-59102-089-9.
• Dwinger, Felipe (1971). Introducción a las álgebras de Boole . Würzburg: Physica Verlag.
• Gaifman, Haim (1964). "Polinomios booleanos infinitos, I" . Fundamentos Mathematicae . 54 (3): 229– 250. doi : 10.4064/fm-54-3-229-250 .
• Givant, Steven; Halmos, Paul (2009). Introducción a las álgebras booleanas . Textos de pregrado en matemáticas . Springer. ISBN 978-0-387-40293-2.
• Grau, AA (1947). "Álgebra booleana ternaria" . Bull. Am. Math. Soc . 33 (6): 567– 572. doi : 10.1090/S0002-9904-1947-08834-0 .
• Hales, Alfred W. (1964). "Sobre la no existencia de álgebras booleanas completas libres" . Fundamenta Mathematicae . 54 : 45–66 . doi : 10.4064/fm-54-1-45-66 .
• Halmos, Paul (1963). Conferencias sobre álgebras booleanas . van Nostrand. ISBN 0-387-90094-2.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
• Givant, Steven; Halmos, Paul (1998). La lógica como álgebra . Exposición Matemática Dolciani. Asociación Matemática de América . ISBN 978-0-883-85327-6.
• Johnstone, Peter T. (1982). Espacios de piedra . Cambridge, Reino Unido: Cambridge University Press. ISBN 978-0-521-33779-3.
• Ketonen, Jussi (1978). "La estructura de las álgebras booleanas contables". Annals of Mathematics . 108 (1): 41– 89. doi : 10.2307/1970929 . JSTOR 1970929 . 
• Koppelberg, Sabine (1989) «Teoría general de las álgebras booleanas» en Monk, J. Donald y Bonnet, Robert (eds.), Manual de álgebras booleanas, vol. 1. North Holland. ISBN 978-0-444-70261-6.
• Peirce, CS (1989) Escritos de Charles S. Peirce: Edición cronológica: 1879–1884 . Kloesel, CJW, ed. Indianápolis: Indiana University Press. ISBN 978-0-253-37204-8.
• Lawvere, F. William (1963). "Semántica funcional de las teorías algebraicas" . Actas de la Academia Nacional de Ciencias . 50 (5): 869– 873. Bibcode : 1963PNAS...50..869L . doi : 10.1073/pnas.50.5.869 . PMC 221940. PMID 16591125 .  
• Schröder, Ernst (1890-1910). Vorlesungen über die Algebra der Logik (exakte Logik), I–III . Leipzig: BG Teubner.
• Sikorski, romano (1969). Álgebras de Boole (3ª  ed.). Berlín: Springer-Verlag. ISBN 978-0-387-04469-9.
• Stone, MH (1936). "La teoría de la representación para álgebras booleanas". Transactions of the American Mathematical Society . 40 (1): 37– 111. doi : 10.2307/1989664 . JSTOR 1989664 . 
• Tarski, Alfred (1983). Lógica, semántica, metamatemáticas , Corcoran, J., ed. Hackett. 1956 1.ª edición editada y traducida por JH Woodger, Oxford University Press. Incluye traducciones al inglés de los dos artículos siguientes:
  • Tarski, Alfred (1929). "Sur les classs closes par rapport à surees opérations élémentaires". Fundamentos Mathematicae . 16 : 195-97 .
  • Tarski, Alfred (1935). "Zur Grundlegung der Booleschen Algebra, I" . Fundamentos Mathematicae . 24 : 177– 98. doi : 10.4064/fm-24-1-177-198 .
• Vladímirov, DA (1969). булевы алгебры (Álgebras de Boole, en ruso, traducción al alemán Boolesche Algebren 1974) . Nauka (traducción alemana Akademie-Verlag).