El álgebra de Boole es una rama matemáticamente rica del álgebra abstracta . La Enciclopedia de Filosofía de Stanford define el álgebra de Boole como "el álgebra de la lógica de dos valores con sólo conectivos oracionales, o equivalentemente de las álgebras de conjuntos bajo unión y complementación". [1] Así como la teoría de grupos trata con los grupos y el álgebra lineal con los espacios vectoriales , las álgebras de Boole son modelos de la teoría ecuacional de los dos valores 0 y 1 (cuya interpretación no necesita ser numérica). Un concepto común a las álgebras de Boole, los grupos y los espacios vectoriales es la noción de una estructura algebraica , un conjunto cerrado bajo algunas operaciones que satisfacen ciertas ecuaciones. [2]
Así como existen ejemplos básicos de grupos, como el grupo de números enteros y el grupo simétrico S n de permutaciones de n objetos, también existen ejemplos básicos de álgebras de Boole como los siguientes.
El álgebra de Boole permite así 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 es decidible solo en casos especiales, todas las álgebras booleanas finitas comparten los mismos teoremas y tienen 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 de Boole trata la teoría ecuacional del álgebra finitaria máxima de dos elementos, llamada prototipo booleano , y los modelos de esa teoría, llamados álgebras de Boole . [3] Estos términos se definen de la siguiente manera.
Un álgebra es una familia de operaciones sobre un conjunto, llamado el conjunto subyacente del álgebra. Tomamos el conjunto subyacente del prototipo booleano como {0,1}.
Un álgebra es finita cuando cada una de sus operaciones toma sólo 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. La álgebra máxima de este tipo consiste en 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 , u operación n -aria, se puede aplicar a cualquiera de los 2 n valores posibles para sus n argumentos. Para cada elección de argumentos, la operación puede devolver 0 o 1 , por lo que hay 2 2 n n operaciones -arias.
Por lo tanto, el prototipo tiene dos operaciones que no toman argumentos, llamadas operaciones ceroarias o nularias , a saber, cero y uno. Tiene cuatro operaciones unarias , dos de las cuales son operaciones constantes, otra es la identidad y la más comúnmente utilizada, llamada negación , devuelve el opuesto de su argumento: 1 si 0 , 0 si 1. Tiene dieciséis operaciones binarias ; nuevamente dos de estas son constantes, otra devuelve su primer argumento, otra devuelve su segundo, una se llama conjunción y devuelve 1 si ambos argumentos son 1 y en caso contrario 0, otra se llama disyunción y devuelve 0 si ambos argumentos son 0 y en caso contrario 1, 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 2 = 256 operaciones ternarias, 256 2 = 65,536 operaciones cuaternarias, y así sucesivamente.
Una familia está indexada por 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 esa á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 interpretaciones posibles 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, llamados símbolos de operación booleanos y que forman el lenguaje del álgebra booleana. Solo unas pocas operaciones tienen símbolos convencionales, como ¬ para negación, ∧ para conjunción y ∨ para disyunción. [4] Es conveniente considerar que el i -ésimo símbolo n -ario es n f i como se hace a continuación en la sección sobre tablas de verdad.
Una teoría de ecuaciones en un lenguaje determinado consiste en ecuaciones entre términos construidas a partir de variables utilizando símbolos de ese lenguaje. Las ecuaciones típicas en el lenguaje del álgebra de Boole son x ∧ y = y ∧ x , x ∧ x = x , x ∧¬ x = y ∧¬ y , y x ∧ y = x .
Un álgebra satisface una ecuación cuando la ecuación se cumple para todos los valores posibles de sus variables en esa álgebra cuando los símbolos de la operación se interpretan como lo especifica esa álgebra. Las leyes del álgebra de Boole son las ecuaciones en el lenguaje del álgebra de Boole que satisface el prototipo. Los primeros tres de los ejemplos anteriores son leyes de Boole, pero no el cuarto, ya que 1∧0 ≠ 1 .
La teoría ecuacional de un álgebra es el conjunto de todas las ecuaciones que satisface el álgebra. Las leyes del álgebra de Boole constituyen, por tanto, la teoría ecuacional del prototipo booleano.
Un modelo de una teoría es un álgebra que interpreta los símbolos de operación en el lenguaje de la teoría y satisface las ecuaciones de la teoría.
Es decir, un álgebra de Boole es un conjunto y una familia de operaciones sobre él que interpretan los símbolos de operación booleanos y satisfacen las mismas leyes que el prototipo booleano. [5]
Si definimos un homólogo de un álgebra como un modelo de la teoría ecuacional de esa álgebra, entonces un álgebra de Boole puede definirse como cualquier homólogo del prototipo.
Ejemplo 1. El prototipo booleano es un álgebra booleana, ya que satisface trivialmente sus propias leyes. Es, por tanto, el álgebra booleana prototípica. No la llamamos así inicialmente para evitar cualquier apariencia de circularidad en la definición.
No es necesario que todas las operaciones estén expresadas explícitamente. Una base es cualquier conjunto del que se pueden obtener las operaciones restantes por composición. Un "álgebra de Boole" se puede definir a partir de varias bases diferentes. Se utilizan comúnmente tres bases para el álgebra de Boole: la base reticular, la base anular y la base de trazo de Sheffer o NAND. Estas bases imparten al tema un carácter lógico, aritmético y parsimonioso, respectivamente.
Los elementos comunes de las bases reticular y anular son las constantes 0 y 1, y una operación binaria conmutativa asociativa , llamada encuentro x ∧ y en la base reticular, y multiplicación xy en la base anular. La distinción es solo terminológica. La base reticular tiene las operaciones adicionales de unión , x ∨ y , y complemento , ¬ x . La base anular tiene en cambio la operación aritmética x ⊕ y de adición (el símbolo ⊕ se usa en preferencia a + porque a este último a veces se le da la lectura booleana de unión).
Ser una base es producir todas las demás operaciones por composición, por lo que dos bases cualesquiera deben ser intertraducibles. La base reticular traduce x ∨ y a la base del anillo como x ⊕ y ⊕ xy , y ¬ x como x ⊕1 . A la inversa, la base del anillo traduce x ⊕ y a la base reticular como ( x ∨ y )∧¬( x ∧ y ) .
Ambas bases permiten definir álgebras de Boole mediante un subconjunto de las propiedades ecuacionales de las operaciones booleanas. Para la base reticular, basta con definir un álgebra de Boole como una red distributiva que satisface x ∧¬ x = 0 y x ∨¬ x = 1 , llamada red distributiva complementada . La base anular convierte un álgebra de Boole en un anillo booleano , es decir, un anillo que satisface x 2 = 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 una que comparten algunas pero no todas las operaciones que forman 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 sólo 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 de esa candidata, por lo que, por la no trivialidad de esa propiedad, la candidata no podrá ser una base). Las cinco propiedades de Post son:
La operación NAND (dualmente NOR) carece de todo esto, por lo que forma una base por sí misma.
Las operaciones finitarias en {0,1} pueden ser exhibidas como tablas de verdad , pensando en 0 y 1 como los valores de verdad falso y verdadero . [7] Pueden ser presentadas de una manera uniforme e independiente de la aplicación que nos permite nombrarlas, o al menos numerarlas, individualmente. [8] Estos nombres proporcionan una abreviatura conveniente para las operaciones booleanas. Los nombres de las operaciones n -arias son números binarios de 2 n bits. Habiendo 2 2 n de tales operaciones, no se puede pedir una nomenclatura más sucinta. Nótese que cada operación finitaria puede ser llamada una función de conmutación .
Este diseño y la denominación asociada de operaciones se ilustran aquí en su totalidad para las aridades de 0 a 2.
Estas tablas continúan en aridades superiores, con 2 n filas en la aridad n , cada fila da una valoración o unión de las n variables x 0 ,... x n −1 y cada columna encabezada n f i da el valor n f i ( x 0 ,..., x n −1 ) de la i - ésima operación n -aria en esa valoración. Las operaciones incluyen las variables, por ejemplo 1 f 2 es x 0 mientras que 2 f 10 es x 0 (como dos copias de su contraparte unaria) y 2 f 12 es x 1 (sin contraparte unaria). La negación o complemento ¬ x 0 aparece como 1 f 1 y nuevamente como 2 f 5 , junto con 2 f 3 ( ¬ x 1 , que no apareció en aridad 1), disyunción o unión x 0 ∨ x 1 como 2 f 14 , conjunción o intersección x 0 ∧ x 1 como 2 f 8 , implicación x 0 → x 1 como 2 f 13 , diferencia exclusiva o simétrica x 0 ⊕ x 1 como 2 f 6 , diferencia de conjuntos x 0 − x 1 como 2 f 2 , 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í estamos indexando las operaciones de un álgebra de Boole por las operaciones finitas en {0,1}, la presentación de la tabla de verdad anterior ordena casualmente 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 está determinado por las dos reglas siguientes.
Al programar en C o Java, la disyunción bit a bit se denotax | y, conjunciónx y y, y negación~ x. Por lo tanto, un programa puede representar, por ejemplo, la operación x ∧( y ∨ z ) en estos lenguajes comox y ( y | z ), habiendo fijado previamentex = 0xaa,y = 0xcc, yz = 0xf0(el "0x" indica que la siguiente constante debe leerse en hexadecimal o base 16), ya sea por asignación a variables o definidas como macros. Estas constantes de un byte (ocho bits) corresponden a las columnas para 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, siendo las operaciones típicas ternarias y actuando simultáneamente sobre bits de origen, destino y enmascaramiento.
Ejemplo 2. Todos los vectores de bits de una longitud dada forman un álgebra booleana "puntual", lo que significa que cualquier operación booleana n -aria se puede aplicar a n vectores de bits, una posición de bit a la vez. Por ejemplo, el OR ternario de tres vectores de bits, cada uno de longitud 4, es el vector de bits de longitud 4 formado mediante la operación OR de los tres bits en cada una de las cuatro posiciones de bits, por lo tanto, 0100∨1000∨1001 = 1101. Otro ejemplo son las tablas de verdad anteriores para las operaciones n -arias, cuyas columnas son todos los vectores de bits de longitud 2 n y que, por lo tanto, se pueden combinar puntualmente, de modo que las operaciones n -arias forman un álgebra booleana. [9] Esto funciona igualmente bien para vectores de bits de longitud finita e infinita, siendo la única regla que todas las posiciones de bits estén indexadas por el mismo conjunto para que la "posición correspondiente" esté bien definida.
Los átomos de dicha álgebra son los vectores de bits que contienen exactamente un 1. En general, los átomos de un álgebra de Boole son aquellos elementos x tales que x ∧ y tiene solo dos valores posibles, x o 0 .
Ejemplo 3. El álgebra de conjuntos de potencias , el conjunto 2 W de todos los subconjuntos de un conjunto dado W. [10] Este es simplemente el Ejemplo 2 disfrazado, con W sirviendo para indexar las posiciones de bit. Cualquier subconjunto X de W puede verse como el vector de bit que tiene 1 solo en aquellas posiciones de bit indexadas por elementos de X. Por lo tanto, el vector de todos los ceros es el subconjunto vacío de W mientras que el vector de todos los unos es el propio W , siendo estas las constantes 0 y 1 respectivamente del álgebra de conjuntos de potencias. La contraparte de la disyunción x ∨ y es la unión X ∪ Y , mientras que la de la conjunción x ∧ y es la intersección X ∩ Y . La negación ¬ x se convierte en ~ X , complemento relativo a W . También existe la diferencia de conjuntos X \ Y = X ∩~ Y , la diferencia simétrica ( X \ Y )∪( Y \ X ) , la unión ternaria X ∪ Y ∪ Z , etc. Los átomos aquí son los singletons, aquellos subconjuntos con exactamente un elemento.
Los ejemplos 2 y 3 son casos especiales de una construcción general del álgebra llamada producto directo , aplicable no sólo a las álgebras de Boole sino a todo tipo de álgebra incluyendo grupos, anillos, etc. El producto directo de cualquier familia B i de álgebras de Boole donde i abarca algún conjunto de índices I (no necesariamente finito o incluso contable) es un álgebra de Boole que consiste en todas las I -tuplas (... x i ,...) cuyo i -ésimo elemento se toma de B i . Las operaciones de un producto directo son las operaciones correspondientes de las álgebras constituyentes que actúan dentro de sus respectivas coordenadas; en particular, la operación n f j del producto opera sobre n I -tuplas aplicando la operación n f j de B i a los n elementos en la i -ésima coordenada de las n tuplas, para todo i en I .
Cuando todas las álgebras que se multiplican de esta manera son la misma álgebra A, llamamos al producto directo una potencia directa de A. El álgebra de Boole de todos los vectores de bits de 32 bits es el álgebra de Boole de dos elementos elevada a la 32.ª potencia, o álgebra de conjuntos de potencias de un conjunto de 32 elementos, denotada 2 32 . El álgebra de Boole de todos los conjuntos de números enteros es 2 Z . Todas las álgebras de Boole que hemos expuesto hasta ahora han sido potencias directas del álgebra de Boole de dos elementos, lo que justifica el nombre de "álgebra de conjuntos de potencias".
Se puede demostrar que cada álgebra booleana finita es isomorfa a algún álgebra de conjuntos de potencias. [11] Por lo tanto, la cardinalidad (número de elementos) de un álgebra booleana finita es una potencia de 2 , es decir, una de 1,2,4,8,...,2 n ,... Esto se llama teorema de representación , ya que proporciona una idea de la naturaleza de las álgebras booleanas finitas al dar una representación de ellas como álgebras de conjuntos de potencias.
Este teorema de representación no se extiende a las álgebras de Boole infinitas: aunque cada álgebra de conjuntos de potencias es un álgebra de Boole, no toda álgebra de Boole necesita ser isomorfa a un álgebra de conjuntos de potencias. En particular, mientras que no puede haber álgebras de conjuntos de potencias infinitas numerables (la álgebra de conjuntos de potencias infinitas más pequeña es el álgebra de conjuntos de potencias 2 N de conjuntos de números naturales, que según Cantor es incontable ) , existen varias álgebras de Boole infinitas numerables.
Para ir más allá de las álgebras de conjuntos de potencias necesitamos otra construcción. Una subálgebra de un álgebra A es cualquier subconjunto de A cerrado bajo las operaciones de A . Toda subálgebra de un álgebra de Boole A debe satisfacer las ecuaciones que se cumplen para A , ya que cualquier violación constituiría una violación para la propia A . Por lo tanto, toda subálgebra de un álgebra de Boole es un álgebra de Boole. [12]
Una subálgebra de un álgebra de conjuntos de potencias se denomina cuerpo de conjuntos ; equivalentemente, un cuerpo de conjuntos es un conjunto de subconjuntos de algún conjunto W que incluye el conjunto vacío y W y está cerrado bajo unión y complemento finitos con respecto a W (y, por lo tanto, también bajo intersección finita). El teorema de representación de Birkhoff [1935] para álgebras de Boole establece que toda álgebra de Boole es isomorfa a un cuerpo de conjuntos. Ahora bien , el teorema HSP de Birkhoff para variedades puede enunciarse como que toda clase de modelos de la teoría ecuacional de una clase C de álgebras es la imagen homomórfica de una subálgebra de un producto directo de álgebras de C. Normalmente, se necesitan los tres H, S y P; lo que muestra el primero de estos dos teoremas de Birkhoff es que, para el caso especial de la variedad de álgebras de Boole, el homomorfismo puede reemplazarse por el isomorfismo . El teorema HSP de Birkhoff para variedades en general se convierte, por tanto, en el teorema ISP de Birkhoff para la variedad de álgebras de Boole.
Es conveniente, cuando se habla de un conjunto X de números naturales, verlo como una secuencia x 0 , x 1 , x 2 ,... de bits, con x i = 1 si y solo si i ∈ X . Este punto de vista hará más fácil hablar de subálgebras del álgebra de conjuntos de potencias 2 N , que este punto de vista convierte en el álgebra booleana de todas las secuencias de bits. [13] También encaja bien con las columnas de una tabla de verdad: cuando una columna se lee de arriba a abajo constituye una secuencia de bits, pero al mismo tiempo puede verse como el conjunto de aquellas valoraciones (asignaciones a variables en la mitad izquierda de la tabla) en las que la función representada por esa columna evalúa a 1.
Ejemplo 4. Sucesiones en última instancia constantes . Cualquier combinación booleana de sucesiones en última instancia constantes es en última instancia constante; por lo tanto, forman un álgebra de Boole. Podemos identificarlas con los números enteros al considerar las sucesiones en última instancia cero como numerales binarios no negativos (el bit 0 de la sucesión es el bit de orden inferior) y las sucesiones en última instancia uno como numerales binarios negativos (piense en la aritmética del complemento a dos con la sucesión de todos unos como −1 ). Esto hace que los números enteros sean un álgebra de Boole, donde la unión es OR bit a bit y el complemento es −x−1 . Solo hay una cantidad contable de números enteros, por lo que esta álgebra de Boole infinita es contable. Los átomos son las potencias de dos, es decir, 1,2,4,.... Otra forma de describir esta álgebra es como el conjunto de todos los conjuntos finitos y cofinitos de números naturales, con las secuencias finalmente compuestas por todos unos correspondientes a los conjuntos cofinitos, y esos conjuntos omitiendo solo un número finito de números naturales.
Ejemplo 5. Sucesión periódica . Una sucesión se denomina periódica cuando existe algún número n > 0 , llamado testigo de periodicidad, tal que x i = x i + n para todo i ≥ 0. El periodo de una sucesión periódica es su testigo menor. La negación deja el periodo inalterado, mientras que la disyunción de dos sucesiones periódicas es periódica, siendo el periodo como máximo el mínimo común múltiplo de los periodos de los dos argumentos (el periodo puede ser tan pequeño como 1 , como ocurre con la unión de cualquier sucesión y su complemento). Por tanto, las sucesiones periódicas forman un álgebra de Boole.
El ejemplo 5 se parece al ejemplo 4 en que es numerable, pero se diferencia en que no tiene átomos. Esto último se debe a que la conjunción de cualquier secuencia periódica distinta de cero x con una secuencia de período coprimo (mayor que 1) no es ni 0 ni x . Se puede demostrar que todas las álgebras booleanas infinitas numerables sin átomos son isomorfas, es decir, hasta el isomorfismo solo hay una de esas álgebras.
Ejemplo 6. Sucesión periódica con periodo una potencia de dos . Esta es una subálgebra propia del Ejemplo 5 (una subálgebra propia es igual a la intersección de sí misma con su álgebra). Estas pueden entenderse como las operaciones finitarias, con el primer periodo de dicha sucesión dando la tabla de verdad de la operación que representa. Por ejemplo, la tabla de verdad de x 0 en la tabla de operaciones binarias, es decir 2 f 10 , tiene periodo 2 (y por lo tanto puede reconocerse como que utiliza solo la primera variable) aunque 12 de las operaciones binarias tienen periodo 4 . Cuando el periodo es 2 n la operación solo depende de las primeras n variables, el sentido en el que la operación es finitaria. Este ejemplo es también un álgebra booleana infinita numerable sin átomos. ¡Por lo tanto, el Ejemplo 5 es isomorfo a una subálgebra propia de sí mismo! El ejemplo 6, y por tanto el ejemplo 5, constituyen el álgebra booleana libre sobre un número contable de generadores, es decir, el álgebra booleana de todas las operaciones finitas sobre un conjunto contablemente infinito de generadores o variables.
Ejemplo 7. Sucesiones en última instancia periódicas , sucesiones que se vuelven periódicas después de un período finito inicial de anarquía. Constituyen una extensión propia del Ejemplo 5 (lo que significa que el Ejemplo 5 es una subálgebra propia del Ejemplo 7) y también del Ejemplo 4, ya que las sucesiones constantes son periódicas con período uno. Las sucesiones pueden variar en cuanto a cuándo se estabilizan, pero cualquier conjunto finito de sucesiones se estabilizará eventualmente no más tarde que su miembro más lento en estabilizarse, por lo que las sucesiones en última instancia periódicas son cerradas bajo todas las operaciones booleanas y forman así un álgebra booleana. Este ejemplo tiene los mismos átomos y capas que el Ejemplo 4, por lo que no es sin átomos y por lo tanto no es isomorfo al Ejemplo 5/6. Sin embargo, contiene una subálgebra infinita sin átomos , a saber, el Ejemplo 5, y por lo tanto no es isomorfo al Ejemplo 4, cada subálgebra del cual debe ser un álgebra booleana de conjuntos finitos y sus complementos y por lo tanto atómico. Este ejemplo es isomorfo al producto directo de los Ejemplos 4 y 5, lo que proporciona otra descripción del mismo.
Ejemplo 8. Producto directo de una sucesión periódica (ejemplo 5) con cualquier álgebra booleana finita pero no trivial. (El álgebra booleana trivial de un elemento es la única álgebra booleana finita sin átomos). Esto se parece al ejemplo 7 en que tiene átomos y una subálgebra sin átomos , pero difiere en que tiene solo un número finito de átomos. El ejemplo 8 es, de hecho, una familia infinita de ejemplos, uno para cada número finito posible de átomos.
Estos ejemplos no agotan en modo alguno las posibles álgebras de Boole, ni siquiera las numerables. De hecho, hay un número incontable de álgebras de Boole numerables no isomorfas, que Jussi Ketonen [1978] clasificó completamente en términos de invariantes representables por ciertos conjuntos numerables hereditariamente.
Las operaciones booleanas n -arias constituyen en sí mismas un álgebra de conjuntos de potencias 2 W , es decir, cuando W se toma como el conjunto de 2 n valoraciones de las n entradas. En términos del sistema de nombres de las operaciones n 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 cualquier m y n .
La importancia práctica de esta convención, tanto para el software como para el hardware, es que las operaciones booleanas n -arias se pueden representar como palabras de la longitud adecuada. Por ejemplo, cada una de las 256 operaciones booleanas ternarias se puede representar como un byte sin signo. Las operaciones lógicas disponibles, como AND y OR, se pueden utilizar para formar nuevas operaciones. Si tomamos x , y y z (prescindiendo de las variables con subíndice por ahora) 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 es 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
y
son en realidad la misma operación. Es decir, hemos demostrado la identidad ecuacional
para el álgebra de Boole de dos elementos. Por la definición de "álgebra de Boole", esta identidad debe cumplirse en todas las álgebras de Boole.
Esta operación ternaria formó incidentalmente la base para las álgebras booleanas ternarias de Grau [1947], que 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 de lo contrario x ∧ y . Dado que es simétrica, puede expresarse igualmente como si x entonces y ∨ z de lo contrario y ∧ z , o si y entonces z ∨ x de lo contrario z ∧ x . Vista como un etiquetado 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 mediano , 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 utilizar para demostrar una identidad del álgebra de Boole puede generalizarse a todas las identidades de una manera sistemática que puede tomarse como una axiomatización sólida y completa , o un sistema axiomático para, las leyes ecuacionales de la lógica de Boole . La formulación habitual de un sistema axiomático consiste en un conjunto de axiomas que "preparan el terreno" con algunas identidades iniciales, junto con un conjunto de reglas de inferencia para inferir las identidades restantes a partir de los axiomas y las identidades demostradas previamente. En principio, es deseable tener un número finito de axiomas; sin embargo, como cuestión práctica, no es necesario, ya que es igualmente efectivo tener un esquema axiomático finito que tenga un número infinito de instancias, cada una de las cuales, cuando se utiliza en una prueba, puede verificarse fácilmente que es una instancia legal, el enfoque que seguimos aquí.
Las identidades booleanas son afirmaciones de la forma s = t donde s y t son términos n -arios, con lo que aquí nos referiremos a términos cuyas variables están limitadas a x 0 a x n-1 . Un término n -ario es un átomo o una aplicación. Una aplicación m f i ( t 0 ,..., t m -1 ) es un par que consiste en una operación m -aria m f i y una lista o m -tupla ( t 0 ,..., t m -1 ) de términos m n- arios llamados operandos .
A cada término se le asocia un número natural llamado altura . Los átomos tienen una altura de cero, mientras que las aplicaciones tienen una altura de 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 n f i , que aunque aquí se tratan como átomos, sin embargo significan lo mismo que los términos ordinarios de la forma exacta n f i ( x 0 ,..., x n -1 ) (exacta en el sentido de que las variables deben enumerarse en el orden mostrado sin repeticiones u omisiones). Esto no es una restricción porque los átomos de esta forma incluyen todos los átomos ordinarios, es decir, las constantes 0 y 1, que surgen aquí como las operaciones n -arias n f 0 y n f −1 para cada n (abreviando 2 2 n −1 a −1 ), y las variables x 0 ,..., x n -1 como se puede ver en las tablas de verdad donde x 0 aparece como la operación unaria 1 f 2 y la operación binaria 2 f 10 mientras que x 1 aparece como 2 f 12 .
El siguiente esquema axiomático y tres reglas de inferencia axiomatizan el álgebra booleana de términos n -arios.
El significado de la condición lateral en A1 es que i o ĵ es ese número de 2 n bits cuyo v -ésimo bit es el ĵ v -ésimo bit de i , donde los rangos de cada cantidad son u : m , v : 2 n , j u : 2 2 n y ĵ v : 2 m . (Por lo tanto , j es una m -tupla de 2 n números de bits mientras que ĵ como la transpuesta de j es una 2 n -tupla de m números de bits. Por lo tanto, tanto j como ĵ contienen m 2 n bits).
A1 es un esquema axiomático en lugar de un axioma en virtud de contener metavariables , a saber, m , i , n y j 0 a j m-1 . Los axiomas reales de la axiomatización se obtienen fijando las metavariables en valores específicos. Por ejemplo, si tomamos m = n = i = j 0 = 1 , podemos calcular los dos bits de i o ĵ a partir de i 1 = 0 e i 0 = 1 , por lo que i o ĵ = 2 (o 10 cuando se escribe como un número de dos bits). La instancia resultante, a saber, 1 f 1 ( 1 f 1 ) = 1 f 2 , expresa el conocido axioma ¬¬ x = x de doble negación. La regla R3 nos permite entonces inferir ¬¬¬ x = ¬ x tomando s 0 como 1 f 1 ( 1 f 1 ) o ¬¬ x 0 , t 0 como 1 f 2 o x 0 , y m f i como 1 f 1 o ¬ .
Para cada m y n solo hay un número finito de axiomas que instancian A1 , es decir, 2 2 m × (2 2 n ) m . Cada instancia se especifica mediante 2 m + m 2 n bits.
Tratamos a R1 como una regla de inferencia, aunque es como un axioma al no tener 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 de Boole es el esquema axiomático A1 . De esta manera, cuando hablamos de diferentes teorías ecuacionales, podemos dejar de lado las reglas como independientes de las teorías particulares y limitar la atención a los axiomas como la única parte del sistema axiomático que caracteriza la teoría ecuacional particular en cuestión.
Esta axiomatización es completa, lo que significa que cada ley booleana s = t es demostrable en este sistema. Primero se muestra por inducción sobre la altura de s que cada ley booleana para la cual t es atómico es demostrable, usando R1 para el caso base (ya que á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 demostrar 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, llámelo u . Entonces, primero demuestre s = u y t = u como arriba, es decir, evalúe s y t usando A1 , R1 y R3 , y luego invoque 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 , ĵ y i o ĵ como funciones del tipo i : ( m →2)→2 , j : m →(( n →2)→2) , ĵ : ( n →2)→( m →2) y i o ĵ : ( n →2)→2 . La definición ( i o ĵ ) v = i ĵ v en A1 se traduce entonces a ( i o ĵ )( v ) = i ( ĵ ( v )) , es decir, i o ĵ se define como una composición de i y ĵ entendidas como funciones. Así, el contenido de A1 equivale a definir la aplicación del término como esencialmente composición, módulo la necesidad de transponer la m -tupla j para hacer que los tipos coincidan adecuadamente para la composición. Esta composición es la de la categoría de conjuntos de potencias y sus funciones mencionada anteriormente por Lawvere. De esta manera, hemos traducido los diagramas conmutativos de esa categoría, como la teoría ecuacional de las álgebras de Boole, en las consecuencias ecuacionales de A1 como la representación lógica de esa ley de composición particular.
Subyacente a cada álgebra de Boole B hay un conjunto parcialmente ordenado o poset ( B ,≤) . La relación de orden parcial está definida por x ≤ y justo cuando x = x ∧ y , o equivalentemente cuando y = x ∨ y . Dado un conjunto X de elementos de un álgebra de Boole, un límite superior de X es un elemento y tal que para cada elemento x de X , x ≤ y , mientras que un límite inferior de X es un elemento y tal que para cada elemento x de X , y ≤ x .
Un sup de X es un límite superior mínimo de X , es decir, un límite superior de X que es menor o igual a cada límite superior de X . Dualmente, un inf de X es un límite inferior máximo de X . El sup de x e y siempre existe en el conjunto parcial subyacente de un álgebra de Boole, siendo x ∨ y , y, de la misma manera, existe su inf, es decir, x ∧ y . El sup vacío es 0 (el elemento inferior) y el inf vacío es 1 (superior). De ello se deduce que todo conjunto finito tiene tanto un sup como un inf. Los subconjuntos infinitos de un álgebra de Boole pueden tener o no un sup y/o un inf; en un álgebra de conjuntos de potencias siempre los tienen.
Cualquier conjunto parcial ( B ,≤) tal que cada par x , y de elementos tiene tanto un sup como un inf se llama retículo . Escribimos x ∨ y para el sup y x ∧ y para el inf. El conjunto parcial subyacente de un álgebra de Boole 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 cada ley implica a la otra en un retículo. Estas son leyes del álgebra de Boole, por lo que el conjunto parcial subyacente de un álgebra de Boole forma un retículo distributivo.
Dado un retículo con un elemento inferior 0 y un elemento superior 1, un par x , y de elementos se denomina complementario cuando x ∧ y = 0 y x ∨ y = 1 , y entonces decimos que y es un complemento de x y viceversa. Cualquier elemento x de un retículo distributivo con parte 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 hace que el complemento sea una operación unaria. Además, todo retículo distributivo complementado forma un álgebra de Boole y, a la inversa, todo álgebra de Boole forma un retículo distributivo complementado. Esto proporciona una definición alternativa de un álgebra de Boole, es decir, como cualquier retículo distributivo complementado. Cada una de estas tres propiedades puede axiomatizarse con un número finito de ecuaciones, por lo que estas ecuaciones tomadas en conjunto constituyen una axiomatización finita de la teoría ecuacional de las álgebras de Boole.
En una clase de álgebras definidas como todos los modelos de un conjunto de ecuaciones, suele suceder que algunas álgebras de la clase satisfacen más ecuaciones que las necesarias para calificarlas para la clase. La clase de álgebras de Boole es inusual en el sentido de que, con una sola excepción, todas las álgebras de Boole satisfacen exactamente las identidades de Boole y no más. La excepción es el álgebra de Boole de un elemento, que necesariamente satisface todas las ecuaciones, incluso x = y , y por lo tanto a veces se la denomina álgebra de Boole inconsistente.
Un homomorfismo booleano es una función h : A → B entre las álgebras booleanas A , B tal que para cada operación booleana m f i :
La categoría Bool de las álgebras de Boole tiene como objetos todas las álgebras de Boole y como morfismos los homomorfismos booleanos entre ellas.
Existe un homomorfismo único desde el álgebra de Boole de dos elementos 2 a toda álgebra de Boole, ya que los homomorfismos deben conservar las dos constantes y esas son los únicos elementos de 2 . Un álgebra de Boole con esta propiedad se llama álgebra de Boole inicial . Se puede demostrar que dos álgebras de Boole iniciales cualesquiera son isomorfas, por lo que hasta el isomorfismo 2 es el álgebra de Boole inicial.
En la otra dirección, pueden existir muchos homomorfismos de un álgebra booleana B a 2 . Cualquier homomorfismo de este tipo divide a B en aquellos elementos mapeados a 1 y aquellos a 0. El subconjunto de B que consiste en el primero se llama ultrafiltro de B . Cuando B es finito sus ultrafiltros se aparean con sus átomos; un átomo se mapea a 1 y el resto a 0. Cada ultrafiltro de B consiste entonces en un átomo de B y todos los elementos por encima de él; por lo tanto 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 lo hacen muchos otros conjuntos; por ejemplo, en el álgebra booleana de conjuntos finitos y cofinitos de números enteros, los conjuntos cofinitos forman un ultrafiltro aunque ninguno de ellos sea un átomo. De la misma manera, el conjunto potencia de los números enteros tiene entre sus ultrafiltros el conjunto de todos los subconjuntos que contienen un número entero dado; hay una cantidad contable de estos ultrafiltros "estándar", que pueden identificarse con los números enteros mismos, pero hay una cantidad incontable de ultrafiltros "no estándar". Estos forman la base del análisis no estándar , que proporciona 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 de Boole. Un álgebra de Boole completa es aquella en la que cada subconjunto tiene tanto un sup como un inf, incluso los subconjuntos infinitos. Gaifman [1964] y Hales [1964] demostraron de forma independiente que no existen álgebras de Boole completas libres infinitas . Esto sugiere que una lógica con operaciones de tamaño infinito puede tener muchos términos de clase, así como una lógica con operaciones finitarias puede tener muchos términos de clase infinita.
Sin embargo, existe otro enfoque para introducir operaciones booleanas infinitarias: simplemente eliminar "finitario" de la definición de álgebra de Boole. Un modelo de la teoría ecuacional del álgebra de todas las operaciones en {0,1} de aridad hasta la cardinalidad del modelo se llama álgebra booleana atómica completa o CABA (en lugar de esta incómoda restricción sobre la aridad, podríamos permitir cualquier aridad, lo que llevaría a una incomodidad diferente, ya que la firma sería entonces mayor que cualquier conjunto, es decir, una clase propia. Un beneficio de este último enfoque es que simplifica la definición de homomorfismo entre CABA de diferente cardinalidad ). Un álgebra de este tipo se puede definir de manera equivalente como un álgebra booleana completa que es atómica , lo que significa que cada elemento es un sup de algún conjunto de átomos. Existen CABAs libres para todas las cardinalidades de un conjunto V de generadores , es decir, el álgebra de conjuntos de potencias 2 2 V , siendo esta la generalización obvia de las álgebras booleanas libres finitas. Esto rescata hábilmente a la lógica booleana infinitaria del destino al que parecía condenarla el resultado de Gaifman-Hales.
La inexistencia de álgebras de Boole completas y libres se puede atribuir a la incapacidad de extender las ecuaciones de la lógica de Boole de manera adecuada a todas las leyes que deberían cumplirse para la conjunción y la disyunción infinitarias, en particular la negligencia de la distributividad en la definición de álgebra de Boole completa. Un álgebra de Boole completa se denomina completamente distributiva cuando las conjunciones arbitrarias se distribuyen sobre las disyunciones arbitrarias y viceversa. Un álgebra de Boole es una CABA si y solo si es completa y completamente distributiva, lo que da una tercera definición de CABA. Una cuarta definición es como cualquier álgebra de Boole isomorfa a un álgebra de conjuntos de potencias.
Un homomorfismo completo es aquel que preserva todos los sups que existen, no solo los sups finitos, y lo mismo para 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 al opuesto 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 las álgebras de Boole 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 desconectados , posteriormente llamados espacios de Stone .
Otra clase infinitaria intermedia entre las álgebras de Boole y las álgebras de Boole completas es la noción de álgebra sigma . Esta se define de manera análoga a las álgebras de Boole completas, pero con sups e infs limitados a la aridad numerable. Es decir, una álgebra sigma es un álgebra de Boole con todos los sups e infs numerables. Debido a que los sups e infs son de cardinalidad acotada , a diferencia de la situación con las álgebras de Boole completas , el resultado de Gaifman-Hales no se aplica y existen álgebras sigma libres . Sin embargo, a diferencia de la situación con las CABA, el álgebra sigma libre generada de manera numerable no es un álgebra de conjuntos de potencias.
Ya hemos encontrado varias definiciones del álgebra de Boole, como modelo de la teoría ecuacional del álgebra de dos elementos, como red distributiva complementada, como anillo de Boole y como funtor que preserva el producto de una cierta categoría (Lawvere). Otras dos definiciones que vale la pena mencionar son:
(La circularidad de esta definición se puede eliminar reemplazando "álgebra booleana finita" por "conjunto potencia finito" equipado con las operaciones booleanas interpretadas de manera 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 finitos y los espacios de Stone infinitos como límites filtrados de conjuntos finitos. Por lo tanto, si uno comienza con los conjuntos finitos y pregunta cómo estos se generalizan a objetos infinitos, hay dos formas: "sumándolos" da conjuntos ordinarios o inductivos mientras que "multiplicándolos" da espacios de Stone o conjuntos profinitos . La misma elección existe para las álgebras de conjuntos potencia finitos como los duales de conjuntos finitos: la adición produce álgebras booleanas como objetos inductivos mientras que la multiplicación produce CABA o álgebras de conjuntos potencia como objetos profinitos.
Un rasgo distintivo característico es que la topología subyacente de los objetos así construidos, cuando se define de modo que sea Hausdorff , es discreta para objetos inductivos y compacta para objetos profinitos. La topología de los espacios finitos de Hausdorff es siempre tanto discreta como compacta, mientras que para los espacios infinitos "discreta" y "compacta" son mutuamente excluyentes. Por lo tanto, cuando se generalizan álgebras finitas (de cualquier tipo, no solo booleanas) a las infinitas, "discreta" y "compacta" se separan, y uno debe elegir cuál conservar. La regla general, tanto para las álgebras finitas como para las infinitas, es que las álgebras finitas son discretas, mientras que sus duales son compactas y presentan operaciones infinitarias. Entre estos dos extremos, hay muchas álgebras booleanas infinitas intermedias cuya topología no es ni discreta ni compacta.
