Álgebra booleana

Mientras que el álgebra elemental tiene cuatro operaciones (suma, resta, multiplicación y división), el álgebra booleana tiene solo tres operaciones básicas: conjunción , disyunción y negación , expresadas con los operadores binarios correspondientes AND (${\displaystyle \land }$) y O (${\displaystyle \lor }$) y el operador unario NOT (${\displaystyle \neg }$), denominados colectivamente operadores booleanos . ^{[ 20 ]} Las variables en álgebra booleana que almacenan el valor lógico de 0 y 1 se denominan variables booleanas . Se utilizan para almacenar valores verdaderos o falsos. ^{[ 21 ]} Las operaciones básicas sobre las variables booleanas x e y se definen de la siguiente manera:

Alternativamente, los valores de x ∧ y , x ∨ y , y ¬ x pueden expresarse tabulando sus valores con tablas de verdad como sigue: ^{[ 22 ]}

Cuando se utilizan en expresiones, los operadores se aplican según las reglas de precedencia. Al igual que en el álgebra elemental, las expresiones entre paréntesis se evalúan primero, siguiendo las reglas de precedencia. ^{[ 23 ]}

Si los valores de verdad 0 y 1 se interpretan como números enteros, estas operaciones pueden expresarse con las operaciones aritméticas ordinarias (donde x + y utiliza la suma y xy utiliza la multiplicación), o mediante las funciones mínimo/máximo:

${\displaystyle {\begin{aligned}x\wedge y&=xy=\min(x,y)\\x\vee y&=x+y-xy=x+y(1-x)=\max(x,y)\\\neg x&=1-x\end{aligned}}}$

Podría considerarse que solo la negación y una de las otras dos operaciones son básicas debido a las siguientes identidades que permiten definir la conjunción en términos de negación y disyunción, y viceversa ( leyes de De Morgan ): ^{[ 24 ]}

${\displaystyle {\begin{aligned}x\wedge y&=\neg (\neg x\vee \neg y)\\x\vee y&=\neg (\neg x\wedge \neg y)\end{aligned}}}$

Las operaciones compuestas a partir de las operaciones básicas incluyen, entre otras, las siguientes:

Estas definiciones dan lugar a las siguientes tablas de verdad que proporcionan los valores de estas operaciones para las cuatro posibles entradas.

Material condicional

La primera operación, x  → y , o C xy , se denomina implicación material . Si x es verdadero, el resultado de la expresión x → y se considera igual a y (por ejemplo, si x es verdadero e y es falso, entonces x → y también es falso). Pero si x es falso, el valor de y puede ignorarse; sin embargo, la operación debe devolver un valor booleano y solo hay dos opciones. Por definición, x → y es verdadero cuando x es falso ( la lógica de la relevancia rechaza esta definición, al considerar una implicación con una premisa falsa como algo distinto de verdadero o falso).       

OR exclusivo ( XOR )

La segunda operación, x  ⊕ y , o J xy , se denomina disyunción exclusiva (a menudo abreviada como XOR) para distinguirla de la disyunción, que es la disyunción inclusiva. Excluye la posibilidad de que tanto x como y sean verdaderas (véase, por ejemplo, la tabla): si ambas son verdaderas, el resultado es falso. En términos aritméticos, se define como una suma donde módulo 2 es 1 + 1 = 0.    

Equivalencia lógica

La tercera operación, el complemento de la disyunción exclusiva, es la equivalencia o igualdad booleana: x  ≡ y , o E xy , es verdadera solo cuando x e y tienen el mismo valor. Por lo tanto, x ⊕ y, como su complemento, puede entenderse como x ≠ y , que es verdadera solo cuando x e y son diferentes. Así, su equivalente en aritmética módulo 2 es x + y . El equivalente de la equivalencia en aritmética módulo 2 es x + y + 1.     

El álgebra booleana satisface muchas de las mismas leyes que el álgebra ordinaria cuando se asocia ∨ con la suma y ∧ con la multiplicación. En particular, las siguientes leyes son comunes a ambos tipos de álgebra: ^{[ 25 ] [ 26 ]}

Las siguientes leyes se cumplen en el álgebra booleana, pero no en el álgebra ordinaria:

Tomar x = 2 en la tercera ley anterior muestra que no es una ley de álgebra ordinaria, ya que 2 × 2 = 4. Las cinco leyes restantes pueden ser refutadas en álgebra ordinaria tomando todas las variables como 1. Por ejemplo, en la ley de absorción 1, el lado izquierdo sería 1(1 + 1) = 2 , mientras que el lado derecho sería 1 (y así sucesivamente).

Todas las leyes tratadas hasta ahora se refieren a la conjunción y la disyunción. Estas operaciones tienen la propiedad de que cambiar cualquiera de los argumentos deja la salida sin cambios, o bien la salida cambia de la misma manera que la entrada. De forma equivalente, cambiar cualquier variable de 0 a 1 nunca produce un cambio en la salida de 1 a 0. Se dice que las operaciones con esta propiedad son monótonas . Por lo tanto, los axiomas hasta ahora se refieren a la lógica booleana monótona. La no monotonicidad entra en juego mediante el complemento ¬ de la siguiente manera. ^{[ 5 ]}

La operación de complemento se define mediante las dos leyes siguientes.

${\displaystyle {\begin{aligned}&{\text{Complementation 1}}&x\wedge \neg x&=0\\&{\text{Complementation 2}}&x\vee \neg x&=1\end{aligned}}}$

Todas las propiedades de la negación, incluidas las leyes que se mencionan a continuación, se derivan únicamente de las dos leyes anteriores. ^{[ 5 ]}

Tanto en el álgebra ordinaria como en el álgebra booleana, la negación funciona intercambiando pares de elementos, por lo que en ambas álgebras satisface la ley de la doble negación (también llamada ley de involución).

${\displaystyle {\begin{aligned}&{\text{Double negation}}&\neg {(\neg {x})}&=x\end{aligned}}}$

Pero mientras que el álgebra ordinaria satisface las dos leyes

${\displaystyle {\begin{aligned}(-x)(-y)&=xy\\(-x)+(-y)&=-(x+y)\end{aligned}}}$

El álgebra booleana satisface las leyes de De Morgan :

${\displaystyle {\begin{aligned}&{\text{De Morgan 1}}&\neg x\wedge \neg y&=\neg {(x\vee y)}\\&{\text{De Morgan 2}}&\neg x\vee \neg y&=\neg {(x\wedge y)}\end{aligned}}}$

Las leyes enumeradas anteriormente definen el álgebra booleana, en el sentido de que implican el resto de la materia. Las leyes de complementación 1 y 2, junto con las leyes monótonas, son suficientes para este propósito y, por lo tanto, pueden considerarse como un posible conjunto completo de leyes o axiomatización del álgebra booleana. Cada ley del álgebra booleana se deduce lógicamente de estos axiomas. Además, las álgebras booleanas pueden definirse como modelos de estos axiomas, tal como se trata en la sección «  Álgebras booleanas» .

Escribir más leyes del álgebra booleana no puede generar nuevas consecuencias de estos axiomas, ni descartar ningún modelo de los mismos. Por el contrario, en una lista de algunas, pero no todas, las mismas leyes, podrían existir leyes booleanas que no se derivaran de las de la lista, y además, habría modelos de las leyes enumeradas que no serían álgebras booleanas.

Esta axiomatización no es en absoluto la única, ni siquiera necesariamente la más natural, dado que no se prestó atención a si algunos de los axiomas se derivaban de otros, sino que simplemente se optó por detenerse cuando se habían observado suficientes leyes, tratado con más detalle en §  Axiomatización del álgebra booleana . O bien, se puede prescindir por completo de la noción intermedia de axioma definiendo una ley booleana directamente como cualquier tautología , entendida como una ecuación que se cumple para todos los valores de sus variables sobre 0 y 1. ^{[ 27 ] [ 28 ]} Se puede demostrar que todas estas definiciones de álgebra booleana son equivalentes.

Principio: Si {X, R} es un conjunto parcialmente ordenado , entonces {X, R(inverso)} también es un conjunto parcialmente ordenado.

No hay nada especial en la elección de símbolos para los valores del álgebra booleana. 0 y 1 podrían renombrarse como α y β , y siempre que se hiciera de forma consistente, seguiría siendo álgebra booleana, aunque con algunas diferencias estéticas evidentes.

Pero supongamos que 0 y 1 se renombraran como 1 y 0 respectivamente. Seguiría siendo álgebra booleana y, además, operaría con los mismos valores. Sin embargo, no sería idéntica a nuestra álgebra booleana original, ya que ahora ∨ se comporta como lo hacía ∧ y viceversa. Por lo tanto, aún existen algunas diferencias superficiales que indican que la notación ha cambiado, a pesar de que se siguen utilizando 0 y 1.

Pero si, además de intercambiar los nombres de los valores, también se intercambian los nombres de las dos operaciones binarias, entonces no queda rastro de lo que se hizo. El resultado final es completamente indistinguible del original. Las columnas de x ∧ y y x ∨ y en las tablas de verdad han cambiado de lugar, pero ese cambio es irrelevante.

Cuando los valores y las operaciones se pueden emparejar de forma que todo lo importante permanezca inalterado al intercambiar todos los pares simultáneamente, los miembros de cada par se denominan duales entre sí. Así, 0 y 1 son duales, y ∧ y ∨ también lo son. El principio de dualidad , también llamado dualidad de De Morgan , afirma que el álgebra booleana permanece inalterada cuando se intercambian todos los pares duales.

Un cambio que no fue necesario hacer como parte de este intercambio fue el complemento. Complementar es una operación autodual . La operación identidad o de no hacer nada x (copiar la entrada a la salida) también es autodual. Un ejemplo más complicado de una operación autodual es ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) . No hay ninguna operación binaria autodual que dependa de ambos argumentos. Una composición de operaciones autoduales es una operación autodual. Por ejemplo, si f ( x , y , z ) = ( x ∧ y ) ∨ ( y ∧ z ) ∨ ( z ∧ x ) , entonces f ( f ( x , y , z ), x , t ) es una operación autodual de cuatro argumentos x , y , z , t .

El principio de dualidad puede explicarse desde la perspectiva de la teoría de grupos por el hecho de que existen exactamente cuatro funciones que son aplicaciones biyectivas ( automorfismos ) del conjunto de polinomios booleanos sobre sí mismo: la función identidad, la función complemento, la función dual y la función contradual (dual complementada). Estas cuatro funciones forman un grupo bajo la composición de funciones , isomorfo al grupo de Klein de cuatro funciones , que actúa sobre el conjunto de polinomios booleanos. Walter Gottschalk señaló que, en consecuencia, un nombre más apropiado para el fenómeno sería el principio (o cuadrado ) de cuaternalidad . ^{[ 5 ] : 21–22}

Un diagrama de Venn ^{[ 29 ]} puede utilizarse para representar una operación booleana mediante regiones superpuestas sombreadas. Hay una región para cada variable, todas circulares en los ejemplos presentados. El interior y el exterior de la región x corresponden respectivamente a los valores 1 (verdadero) y 0 (falso) para la variable x . El sombreado indica el valor de la operación para cada combinación de regiones, donde el color oscuro representa 1 y el claro 0 (algunos autores utilizan la convención opuesta).

Los tres diagramas de Venn en la figura siguiente representan respectivamente la conjunción x ∧ y , la disyunción x ∨ y y el complemento ¬ x .

En el caso de la conjunción, la región dentro de ambos círculos está sombreada para indicar que x ∧ y es 1 cuando ambas variables son 1. Las otras regiones se dejan sin sombrear para indicar que x ∧ y es 0 para las otras tres combinaciones.

El segundo diagrama representa la disyunción x ∨ y sombreando las regiones que se encuentran dentro de uno o ambos círculos. El tercer diagrama representa el complemento ¬ x sombreando la región que no se encuentra dentro del círculo.

Aunque no hemos mostrado los diagramas de Venn para las constantes 0 y 1, son triviales, ya que representan respectivamente un recuadro blanco y uno oscuro, ninguno de los cuales contiene un círculo. Sin embargo, podríamos colocar un círculo para x en esos recuadros, en cuyo caso cada uno denotaría una función de un argumento, x , que devuelve el mismo valor independientemente de x , denominada función constante. En lo que respecta a sus resultados, las constantes y las funciones constantes son indistinguibles; la diferencia radica en que una constante no toma argumentos, lo que se denomina operación nula o de cero argumentos , mientras que una función constante toma un argumento, el cual ignora, y es una operación unaria .

Los diagramas de Venn son útiles para visualizar leyes. Las leyes de conmutatividad para ∧ y ∨ se pueden observar en la simetría de los diagramas: una operación binaria que no fuera conmutativa no tendría un diagrama simétrico, ya que intercambiar x e y tendría el efecto de reflejar el diagrama horizontalmente, y cualquier fallo de conmutatividad aparecería entonces como un fallo de simetría.

La idempotencia de ∧ y ∨ se puede visualizar deslizando los dos círculos juntos y observando que el área sombreada se convierte entonces en el círculo completo, tanto para ∧ como para ∨.

Para ver la primera ley de absorción, x ∧ ( x ∨ y ) = x , comience con el diagrama del medio para x ∨ y y observe que la porción del área sombreada en común con el círculo x es todo el círculo x . Para la segunda ley de absorción, x ∨ ( x ∧ y ) = x , comience con el diagrama de la izquierda para x ∧ y observe que al sombrear todo el círculo x , solo se sombrea el círculo x , ya que el sombreado anterior estaba dentro del círculo x .

La ley de doble negación se puede observar complementando el sombreado del tercer diagrama para ¬ x , que sombrea el círculo x .

Para visualizar la primera ley de De Morgan, (¬ x ) ∧ (¬ y ) = ¬( x ∨ y ) , partimos del diagrama central para x ∨ y y complementamos su sombreado de manera que solo se sombree la región fuera de ambos círculos, que es lo que describe el lado derecho de la ley. El resultado es el mismo que si sombreáramos la región que está fuera del círculo x y fuera del círculo y, es decir, la conjunción de sus exteriores, que es lo que describe el lado izquierdo de la ley.

La segunda ley de De Morgan, (¬ x ) ∨ (¬ y ) = ¬( x ∧ y ) , funciona de la misma manera intercambiando los dos diagramas.

La primera ley del complemento, x ∧ ¬ x = 0 , establece que el interior y el exterior del círculo x no se superponen. La segunda ley del complemento, x ∨ ¬ x = 1 , establece que todo está dentro o fuera del círculo x .

La lógica digital es la aplicación del álgebra booleana de 0 y 1 al hardware electrónico, que consiste en compuertas lógicas conectadas para formar un diagrama de circuito . Cada compuerta implementa una operación booleana y se representa esquemáticamente mediante una forma que indica la operación. Las formas asociadas a las compuertas de conjunción (compuertas AND), disyunción (compuertas OR) y complemento (inversores) son las siguientes: ^{[ 30 ]}

Las líneas a la izquierda de cada compuerta representan los cables o puertos de entrada . El valor de la entrada se representa mediante un voltaje en el terminal. En la lógica de nivel alto activo, el 0 se representa con un voltaje cercano a cero o a tierra, mientras que el 1 se representa con un voltaje cercano al de la fuente de alimentación; en la lógica de nivel bajo activo, esto se invierte. La línea a la derecha de cada compuerta representa el puerto de salida, que normalmente sigue las mismas convenciones de voltaje que los puertos de entrada.

La función de complemento se implementa mediante una puerta inversora. El triángulo indica la operación que simplemente copia la entrada a la salida; el pequeño círculo en la salida representa la inversión que complementa la entrada. La convención de colocar dicho círculo en cualquier puerto significa que la señal que pasa por este puerto se complementa durante su recorrido, ya sea un puerto de entrada o de salida.

El principio de dualidad , o leyes de De Morgan , establece que al complementar los tres puertos de una puerta AND, esta se convierte en una puerta OR, y viceversa, como se muestra en la Figura 4. Sin embargo, al complementar ambos puertos de un inversor, el funcionamiento permanece inalterado.

De manera más general, se puede complementar cualquiera de los ocho subconjuntos de los tres puertos de una puerta AND u OR. Las dieciséis posibilidades resultantes dan lugar a solo ocho operaciones booleanas, a saber, aquellas con un número impar de 1s en su tabla de verdad. Hay ocho de estas porque el "bit diferente" puede ser 0 o 1 y puede ir en cualquiera de las cuatro posiciones en la tabla de verdad. Al haber dieciséis operaciones booleanas binarias, esto debe dejar ocho operaciones con un número par de 1s en sus tablas de verdad. Dos de estas son las constantes 0 y 1 (como operaciones binarias que ignoran ambas entradas); cuatro son las operaciones que dependen no trivialmente de exactamente una de sus dos entradas, a saber, x , y , ¬x y ¬y ; y las dos restantes son x ⊕ y (XOR) y su complemento x ≡ y .

Un álgebra booleana concreta o cuerpo de conjuntos es cualquier conjunto no vacío de subconjuntos de un conjunto dado X cerrado bajo las operaciones de ^unión , intersección y complemento con respecto a X. ^{[ 5} ]

(Históricamente, se requería que X también fuera no vacío para excluir el álgebra booleana degenerada o de un solo elemento, que es la única excepción a la regla de que todas las álgebras booleanas satisfacen las mismas ecuaciones, ya que el álgebra degenerada satisface todas las ecuaciones. Sin embargo, esta exclusión entra en conflicto con la definición puramente ecuacional preferida de "álgebra booleana", pues no hay forma de descartar el álgebra de un solo elemento utilizando solo ecuaciones;  0  ≠  1 no cuenta, al ser una ecuación negada. Por lo tanto, los autores modernos permiten el álgebra booleana degenerada y dejan que X sea vacío).

Ejemplo 1. El conjunto potencia 2 ^X de X , que consta de todos los subconjuntos de X. Aquí X puede ser cualquier conjunto: vacío, finito, infinito o incluso no numerable .

Ejemplo 2. El conjunto vacío y X. Esta álgebra de dos elementos muestra que un álgebra booleana concreta puede ser finita incluso cuando consta de subconjuntos de un conjunto infinito. Se puede observar que todo cuerpo de subconjuntos de X debe contener el conjunto vacío y X. Por lo tanto, no es posible un ejemplo más pequeño, salvo el álgebra degenerada que se obtiene al considerar X como vacío para que el conjunto vacío y X coincidan.

Ejemplo 3. El conjunto de conjuntos finitos y cofinitos de enteros, donde un conjunto cofinito es aquel que omite solo una cantidad finita de enteros. Este conjunto es claramente cerrado bajo el complemento y también bajo la unión, ya que la unión de un conjunto cofinito con cualquier otro conjunto es cofinita, mientras que la unión de dos conjuntos finitos es finita. La intersección se comporta como la unión con los términos "finito" y "cofinito" intercambiados. Este ejemplo es infinitamente numerable porque solo existen una cantidad numerable de conjuntos finitos de enteros.

Ejemplo 4. Para un ejemplo menos trivial del punto planteado en el ejemplo 2, consideremos un diagrama de Venn formado por n curvas cerradas que dividen el diagrama en 2 ^{× n} regiones, y sea X el conjunto (infinito) de todos los puntos en el plano que no están en ninguna curva pero sí en algún lugar dentro del diagrama. El interior de cada región es, por lo tanto, un subconjunto infinito de X , y cada punto en X está en exactamente una región. Entonces, el conjunto de todas las 2 × ^{2 × n} posibles uniones de regiones (incluido el conjunto vacío obtenido como la unión del conjunto vacío de regiones y X obtenido como la unión de todas las 2 × ⁿ regiones) es cerrado bajo unión, intersección y complemento con respecto a X y, por lo tanto, forma un álgebra booleana concreta. Nuevamente, hay un número finito de subconjuntos de un conjunto infinito que forman un álgebra booleana concreta, siendo el ejemplo 2 el caso en el que n = 0 no hay curvas.

Un subconjunto Y de X puede identificarse con una familia indexada de bits con conjunto de índices X , donde el bit indexado por x ∈ X es 1 o 0 según si x ∈ Y o no . (Esta es la llamada noción de función característica de un subconjunto). Por ejemplo, una palabra de computadora de 32 bits consta de 32 bits indexados por el conjunto {0,1,2,...,31}, donde 0 y 31 indexan los bits de orden bajo y alto respectivamente. Para un ejemplo más pequeño, si${\displaystyle X=\{a,b,c\}}$donde a, b, c se consideran posiciones de bits en ese orden de izquierda a derecha, los ocho subconjuntos {}, { c }, { b }, { b ,c } , { a }, { a , c }, { a , b } y { a , b , c } de X se pueden identificar con los respectivos vectores de bits 000, 001, 010, 011, 100, 101, 110 y 111. Los vectores de bits indexados por el conjunto de números naturales son secuencias infinitas de bits, mientras que aquellos indexados por los reales en el intervalo unitario [0,1] están empaquetados demasiado densamente para poder escribirlos de forma convencional, pero no obstante forman familias indexadas bien definidas (imagínese colorear cada punto del intervalo [0,1] de negro o blanco independientemente; los puntos negros forman entonces un subconjunto arbitrario de [0,1]).

Desde este punto de vista de los vectores de bits, un álgebra booleana concreta puede definirse equivalentemente como un conjunto no vacío de vectores de bits todos de la misma longitud (más generalmente, indexados por el mismo conjunto) y cerrados bajo las operaciones de vectores de bits de ∧, ∨ y ¬, como en 1010∧0110 = 0010 , 1010∨0110 = 1110 y ¬1010 = 0101 , las realizaciones de vectores de bits de intersección, unión y complemento respectivamente.

El conjunto {0,1} y sus operaciones booleanas, tal como se trataron anteriormente, pueden entenderse como el caso especial de vectores de bits de longitud uno, que, al identificar los vectores de bits con subconjuntos, también pueden entenderse como los dos subconjuntos de un conjunto de un solo elemento. Esto se denomina álgebra booleana prototípica , justificada por la siguiente observación.

Las leyes que satisfacen todas las álgebras booleanas concretas no degeneradas coinciden con las que satisface el álgebra booleana prototípica.

Esta observación se demuestra de la siguiente manera. Ciertamente, cualquier ley que satisfaga todas las álgebras booleanas concretas también la satisface la prototípica, puesto que es concreta. A la inversa, cualquier ley que no se cumpla para alguna álgebra booleana concreta debe haber fallado en una posición de bit específica, en cuyo caso dicha posición constituye un contraejemplo de un bit para esa ley. La no degeneración garantiza la existencia de al menos una posición de bit, ya que solo existe un vector de bits vacío.

El objetivo final de la siguiente sección puede entenderse como la eliminación del término "concreto" de la observación anterior. Dicho objetivo se alcanza mediante la observación más contundente de que, salvo isomorfismo, todas las álgebras booleanas son concretas.

Hasta ahora, todas las álgebras booleanas han sido concretas, compuestas por vectores de bits o, equivalentemente, por subconjuntos de algún conjunto. Dicha álgebra booleana consta de un conjunto y operaciones sobre ese conjunto que, según se puede demostrar , satisfacen las leyes del álgebra booleana.

En lugar de demostrar que se cumplen las leyes booleanas, podemos postular un conjunto X , dos operaciones binarias sobre X y una operación unaria, y exigir que dichas operaciones satisfagan las leyes del álgebra booleana. Los elementos de X no tienen por qué ser vectores de bits ni subconjuntos, sino que pueden ser cualquier cosa. Esto nos lleva a la definición abstracta más general.

Un álgebra booleana es cualquier conjunto con operaciones binarias ∧ y ∨ y una operación unaria ¬ sobre él que satisface las leyes booleanas. ^{[ 31 ]}

Para los fines de esta definición, es irrelevante cómo las operaciones llegaron a satisfacer las leyes, ya sea por decreto o por demostración. Todas las álgebras booleanas concretas satisfacen las leyes (por demostración, no por decreto), por lo que toda álgebra booleana concreta es un álgebra booleana según nuestras definiciones. Esta definición axiomática de un álgebra booleana como un conjunto y ciertas operaciones que satisfacen ciertas leyes o axiomas por decreto es completamente análoga a las definiciones abstractas de grupo , anillo , cuerpo , etc., características del álgebra moderna o abstracta .

Dada cualquier axiomatización completa del álgebra booleana, como los axiomas para un retículo distributivo complementado , una condición suficiente para que una estructura algebraica de este tipo satisfaga todas las leyes booleanas es que satisfaga precisamente esos axiomas. Por lo tanto, la siguiente es una definición equivalente.

Un álgebra booleana es un retículo distributivo complementado.

La sección sobre axiomatización enumera otras axiomatizaciones, cualquiera de las cuales puede servir de base para una definición equivalente.

Aunque toda álgebra booleana concreta es una álgebra booleana, no toda álgebra booleana tiene por qué ser concreta. Sea n un entero positivo libre de cuadrados , es decir, uno que no es divisible por el cuadrado de un entero, por ejemplo, 30 pero no 12. Se puede demostrar que las operaciones de máximo común divisor , mínimo común múltiplo y división entre n (es decir, ¬ x = n / x ) satisfacen todas las leyes booleanas cuando sus argumentos abarcan los divisores positivos de n . Por lo tanto, esos divisores forman un álgebra booleana. Estos divisores no son subconjuntos de un conjunto, lo que hace que los divisores de n constituyan un álgebra booleana que, según nuestras definiciones, no es concreta.

Sin embargo, si cada divisor de n se representa mediante el conjunto de sus factores primos, esta álgebra booleana no concreta es isomorfa al álgebra booleana concreta que consta de todos los conjuntos de factores primos de n , donde la unión corresponde al mínimo común múltiplo, la intersección al máximo común divisor y el complemento a la división en n . Así pues, este ejemplo, aunque no sea técnicamente concreto, es al menos "moralmente" concreto a través de esta representación, denominada isomorfismo . Este ejemplo es una instancia de la siguiente noción.

Un álgebra de Boole se denomina representable cuando es isomorfa a un álgebra de Boole concreta.

La siguiente pregunta se responde afirmativamente de la siguiente manera.

Toda álgebra booleana es representable.

Es decir, salvo isomorfismo, las álgebras booleanas abstractas y concretas son lo mismo. Este resultado depende del teorema del ideal primo booleano , un principio de elección ligeramente más débil que el axioma de elección . Esta fuerte relación implica un resultado más débil que refuerza la observación de la subsección anterior, dando lugar a la siguiente consecuencia sencilla de la representabilidad.

Las leyes que satisfacen todas las álgebras de Boole coinciden con las que satisface el álgebra de Boole prototípica.

Es más débil en el sentido de que no implica por sí misma la representabilidad. Las álgebras booleanas son especiales en este caso; por ejemplo, un álgebra de relaciones es un álgebra booleana con estructura adicional, pero no es cierto que toda álgebra de relaciones sea representable en el sentido propio de las álgebras de relaciones.

Una aplicación motivadora del cálculo proposicional es el análisis de proposiciones y argumentos deductivos en lenguaje natural. ^{[ 33 ]} Mientras que la proposición "si x = 3, entonces x + 1 = 4" depende de los significados de símbolos como + y 1, la proposición "si x = 3, entonces x = 3" no; es verdadera simplemente en virtud de su estructura, y sigue siendo verdadera ya sea que " x = 3" se reemplace por " x = 4" o "la luna está hecha de queso verde". La forma genérica o abstracta de esta tautología es "si P , entonces P ", o en el lenguaje del álgebra booleana, P → P.

Sustituir P ​​por x = 3 o cualquier otra proposición se denomina instanciación de P mediante dicha proposición. El resultado de instanciar P en una proposición abstracta se denomina instancia de la proposición. Por lo tanto, x = 3 → x = 3 es una tautología por ser una instancia de la tautología abstracta P → P. Todas las ocurrencias de la variable instanciada deben instanciarse con la misma proposición para evitar sinsentidos como P → x = 3 o x = 3 → x = 4.

El cálculo proposicional restringe la atención a las proposiciones abstractas, aquellas construidas a partir de variables proposicionales mediante operaciones booleanas. La instanciación sigue siendo posible dentro del cálculo proposicional, pero solo instanciando variables proposicionales mediante proposiciones abstractas, como instanciar Q mediante Q → P en P → ( Q → P ) para producir la instancia P → (( Q → P ) → P ).

(La disponibilidad de la instanciación como parte del mecanismo del cálculo proposicional evita la necesidad de metavariables dentro del lenguaje del cálculo proposicional, ya que las variables proposicionales ordinarias pueden considerarse dentro de dicho lenguaje para denotar proposiciones arbitrarias. Las metavariables en sí mismas están fuera del alcance de la instanciación, pues no forman parte del lenguaje del cálculo proposicional, sino del mismo lenguaje para hablar de él en el que está escrita esta oración, donde existe la necesidad de poder distinguir las variables proposicionales y sus instanciaciones como entidades sintácticas distintas).

Una axiomatización del cálculo proposicional es un conjunto de tautologías llamadas axiomas y una o más reglas de inferencia para generar nuevas tautologías a partir de las antiguas. Una demostración en un sistema axiomático A es una secuencia finita no vacía de proposiciones, cada una de las cuales es una instancia de un axioma de A o se deduce, mediante alguna regla de A, de proposiciones que aparecen anteriormente en la demostración (evitando así el razonamiento circular). La última proposición es el teorema demostrado por la demostración. Todo segmento inicial no vacío de una demostración es en sí mismo una demostración, por lo que toda proposición en una demostración es en sí misma un teorema. Una axiomatización es correcta cuando todo teorema es una tautología, y completa cuando toda tautología es un teorema. ^{[ 34 ]}

A principios del siglo XX, varios ingenieros eléctricos reconocieron intuitivamente que el álgebra booleana era análoga al comportamiento de ciertos tipos de circuitos eléctricos. Claude Shannon demostró formalmente que dicho comportamiento era lógicamente equivalente al álgebra booleana en su tesis de maestría de 1937, titulada "Análisis simbólico de circuitos de relés y conmutación" .

Hoy en día, todos los ordenadores modernos de propósito general realizan sus funciones mediante lógica booleana binaria; es decir, sus circuitos eléctricos son una manifestación física de dicha lógica. Lo consiguen de diversas maneras: mediante voltajes en cables de circuitos de alta velocidad y dispositivos de almacenamiento capacitivo, mediante la orientación de un dominio magnético en dispositivos de almacenamiento ferromagnético, mediante perforaciones en tarjetas perforadas o cintas de papel , etc. (Algunos ordenadores antiguos utilizaban circuitos o mecanismos decimales en lugar de circuitos lógicos binarios).

Por supuesto, es posible codificar más de dos símbolos en cualquier medio. Por ejemplo, se podrían usar 0, 1, 2 y 3 voltios para codificar un alfabeto de cuatro símbolos en un cable, o agujeros de diferentes tamaños en una tarjeta perforada. En la práctica, las estrictas limitaciones de alta velocidad, tamaño reducido y bajo consumo de energía hacen que el ruido sea un factor importante. Esto dificulta la distinción entre símbolos cuando hay varios posibles símbolos que podrían aparecer en un mismo lugar. En lugar de intentar distinguir entre cuatro voltajes en un solo cable, los diseñadores digitales han optado por dos voltajes por cable: uno alto y otro bajo.

Las computadoras utilizan circuitos booleanos de dos valores por las razones antes mencionadas. Las arquitecturas de computadoras más comunes utilizan secuencias ordenadas de valores booleanos, llamados bits, de 32 o 64 valores, por ejemplo, 01101000110101100101010101001011. Al programar en código máquina , lenguaje ensamblador y otros lenguajes de programación , los programadores trabajan con la estructura digital de bajo nivel de los registros de datos . Estos registros operan con voltajes, donde cero voltios representan el valor booleano 0, y un voltaje de referencia (a menudo +5  V, +3.3  V o +1.8  V) representa el valor booleano 1. Dichos lenguajes admiten tanto operaciones numéricas como lógicas. En este contexto, "numérico" significa que la computadora trata las secuencias de bits como números binarios (números en base dos) y ejecuta operaciones aritméticas como suma, resta, multiplicación o división. El término "lógica" se refiere a las operaciones lógicas booleanas de disyunción, conjunción y negación entre dos secuencias de bits, donde cada bit de una secuencia se compara con su equivalente en la otra. Por lo tanto, los programadores pueden trabajar y aplicar las reglas del álgebra numérica o del álgebra booleana según sea necesario. Una característica distintiva fundamental entre estas familias de operaciones es la existencia de la operación de acarreo en la primera, pero no en la segunda.

Otros ámbitos donde el uso de dos valores resulta una buena opción son el derecho y las matemáticas. En conversaciones informales cotidianas, se aceptan respuestas matizadas o complejas como «quizás» o «solo los fines de semana». Sin embargo, en situaciones más específicas, como un tribunal o en matemáticas basadas en teoremas, se considera ventajoso formular las preguntas de manera que admitan una respuesta simple de sí o no —¿es el acusado culpable o inocente?, ¿es la proposición verdadera o falsa?— y descartar cualquier otra respuesta. Si bien esto puede resultar limitante en la práctica para quien responde, el principio de la pregunta simple de sí o no se ha convertido en un elemento central tanto de la lógica judicial como de la matemática, lo que justifica que la lógica de dos valores se organice y estudie por derecho propio.

Un concepto central de la teoría de conjuntos es la pertenencia. Una organización puede permitir varios grados de membresía, como principiante, asociado y miembro de pleno derecho. Sin embargo, en los conjuntos, un elemento pertenece o no pertenece. Los candidatos a pertenecer a un conjunto funcionan como los cables de una computadora digital: cada candidato es miembro o no miembro, del mismo modo que cada cable es alto o bajo.

Dado que el álgebra es una herramienta fundamental en cualquier área susceptible de tratamiento matemático, estas consideraciones se combinan para hacer que el álgebra de dos valores sea de fundamental importancia para el hardware informático, la lógica matemática y la teoría de conjuntos.

La lógica bivaluada puede extenderse a la lógica multivaluada , principalmente reemplazando el dominio booleano {0,  1} por el intervalo unitario [0,1]. En este caso, en lugar de solo tomar los valores 0 o 1, se puede asumir cualquier valor entre 0 y 1, ambos inclusive. Algebraicamente, la negación (NOT) se reemplaza por 1  − x , la conjunción (AND) por la multiplicación ( xy ) y la disyunción (OR) se define mediante la ley de De Morgan . La interpretación de estos valores como valores de verdad lógica da como resultado una lógica multivaluada, que constituye la base de la lógica difusa y la lógica probabilística . En estas interpretaciones, un valor se interpreta como el "grado" de verdad: hasta qué punto una proposición es verdadera o la probabilidad de que lo sea. 

La aplicación original de las operaciones booleanas fue la lógica matemática , donde combina los valores de verdad, verdadero o falso, de fórmulas individuales.

"Término de búsqueda 1" "Término de búsqueda 2"

"Término de búsqueda 1" O "Término de búsqueda 2"

"Término de búsqueda 1" − "Término de búsqueda 2"

"Término de búsqueda 1" y ("Término de búsqueda 2" o "Término de búsqueda 3")

• Boole, George (1848). "El cálculo lógico" . Cambridge and Dublin Mathematical Journal . III : 183–198 .
• Hailperin, Theodore (1986). La lógica y la probabilidad de Boole: una exposición crítica desde el punto de vista del álgebra, la lógica y la teoría de la probabilidad contemporáneas (2.ª  ed.). Elsevier . ISBN 978-0-444-87952-3.
• Gabbay, Dov M.; Woods, John, eds. (2004). El auge de la lógica moderna: de Leibniz a Frege . Manual de Historia de la Lógica. Vol.  3. Elsevier . ISBN 978-0-444-51611-4., varios capítulos relevantes de Hailperin, Valencia y Grattan-Guinness
• Badesa, Calixto (2004). «Capítulo 1. Álgebra de clases y cálculo proposicional». El nacimiento de la teoría de modelos: el teorema de Löwenheim en el marco de la teoría de los relativos . Princeton University Press . ISBN 978-0-691-05853-5.
• Stanković, Radomir S. [en alemán] ; Astola, Jaakko Tapio [en finés] (2011). Escrito en Niš, Serbia y Tampere, Finlandia. De la lógica booleana a los circuitos de conmutación y autómatas: hacia la tecnología de la información moderna . Estudios en inteligencia computacional. Vol.  335 (1.ª  ed.). Berlín y Heidelberg, Alemania: Springer-Verlag . págs.  xviii + 212. doi : 10.1007/978-3-642-11682-7 . ISBN 978-3-642-11681-0. ISSN 1860-949X . LCCN 2011921126 . Consultado el 25 de octubre de 2022 .  
• Entrada de "La tradición del álgebra de la lógica"Por Stanley Burris en la Enciclopedia de Filosofía de Stanford , 21 de febrero de 2012