Álgebra de Boole

En matemáticas y lógica matemática , el álgebra de Boole es una rama del álgebra . Se diferencia del álgebra elemental en dos aspectos. En primer lugar, los valores de las variables son los valores de verdad verdadero y falso , normalmente denotados como 1 y 0, mientras que en el álgebra elemental los valores de las variables son números. En segundo lugar, el álgebra de Boole utiliza operadores lógicos como la conjunción ( y ) denotada como ∧ , ​​la disyunción ( o ) denotada como ∨ , y la negación ( no ) denotada como ¬ . El álgebra elemental, por otro lado, utiliza operadores aritméticos como la suma, la multiplicación, la resta y la división. Por tanto, el álgebra de Boole es una forma formal de describir las operaciones lógicas de la misma forma que el álgebra elemental describe las operaciones numéricas.

El álgebra de Boole fue introducida por George Boole en su primer libro The Mathematical Analysis of Logic (1847), ^[1] y expuesta con más detalle en su An Investigation of the Laws of Thought (1854). ^[2] Según Huntington , el término álgebra de Boole fue sugerido por primera vez por Henry M. Sheffer en 1913, ^[3] aunque Charles Sanders Peirce le dio el título "Un álgebra booliana [ sic ] con una constante" al primer capítulo de su "Las matemáticas más simples" en 1880. ^[4] El álgebra de Boole ha sido fundamental en el desarrollo de la electrónica digital y está prevista en todos los lenguajes de programación modernos . También se utiliza en la teoría de conjuntos y la estadística . ^[5]

Un precursor del álgebra de Boole fue el álgebra de conceptos de Gottfried Wilhelm Leibniz . El uso del binario en relación con el I Ching fue central para la characteria universalis de Leibniz . Con el tiempo creó las bases del álgebra de conceptos. ^[6] El álgebra de conceptos de Leibniz es deductivamente equivalente al álgebra de conjuntos de Boole. ^[7]

El álgebra de Boole precedió a los desarrollos modernos en álgebra abstracta y lógica matemática ; sin embargo, se la considera conectada con los orígenes de ambos campos. ^[8] En un entorno abstracto, el álgebra de Boole fue perfeccionada a fines del siglo XIX por Jevons , Schröder , Huntington y otros, hasta que alcanzó la concepción moderna de una estructura matemática (abstracta) . ^[8] Por ejemplo, la observación empírica de que uno puede manipular expresiones en el álgebra de conjuntos , traduciéndolas a expresiones en el álgebra de Boole, se explica en términos modernos diciendo que el álgebra de conjuntos es un álgebra de Boole (nótese el artículo indefinido ). De hecho, MH Stone demostró en 1936 que cada álgebra de Boole es isomorfa a un campo de conjuntos .

En la década de 1930, mientras estudiaba circuitos de conmutación , Claude Shannon observó que también se podían aplicar las reglas del álgebra de Boole en este contexto, ^[9] e introdujo el álgebra de conmutación como una forma de analizar y diseñar circuitos por medios algebraicos en términos de puertas lógicas . Shannon ya tenía a su disposición el aparato matemático abstracto, por lo que presentó su álgebra de conmutación como el álgebra de Boole de dos elementos . En los entornos de ingeniería de circuitos modernos, hay poca necesidad de considerar otras álgebras de Boole, por lo que "álgebra de conmutación" y "álgebra de Boole" a menudo se usan indistintamente. ^{[10] [11] [12]}

La implementación eficiente de funciones booleanas es un problema fundamental en el diseño de circuitos lógicos combinacionales . Las herramientas de automatización de diseño electrónico modernas para circuitos de integración a muy gran escala (VLSI) a menudo se basan en una representación eficiente de funciones booleanas conocidas como diagramas de decisión binaria (BDD) (ordenados reducidos ) para la síntesis lógica y la verificación formal . ^[13]

Las oraciones lógicas que se pueden expresar en el cálculo proposicional clásico tienen una expresión equivalente en el álgebra de Boole. Por lo tanto, la lógica de Boole se utiliza a veces para denotar el cálculo proposicional realizado de esta manera. ^{[14] [15] [16]} El álgebra de Boole no es suficiente para capturar fórmulas lógicas utilizando cuantificadores , como los de la lógica de primer orden .

Aunque el desarrollo de la lógica matemática no siguió el programa de Boole, la conexión entre su álgebra y la lógica se estableció posteriormente sobre una base firme en el contexto de la lógica algebraica , que también estudia los sistemas algebraicos de muchas otras lógicas. ^[8] El problema de determinar si las variables de una fórmula booleana (proposicional) dada se pueden asignar de tal manera que la fórmula evalúe como verdadera se denomina problema de satisfacibilidad booleana (SAT), y es de importancia para la informática teórica , siendo el primer problema que se demostró que era NP-completo . El modelo de computación estrechamente relacionado conocido como circuito booleano relaciona la complejidad temporal (de un algoritmo ) con la complejidad del circuito .

Mientras que las expresiones denotan principalmente números en álgebra elemental, en álgebra de Boole denotan los valores de verdad falso y verdadero . Estos valores se representan con los bits , 0 y 1. No se comportan como los enteros 0 y 1, para los cuales 1 + 1 = 2 , sino que pueden identificarse con los elementos del cuerpo de dos elementos GF(2) , es decir, aritmética de enteros módulo 2 , para el cual 1 + 1 = 0. La suma y la multiplicación entonces juegan los roles booleanos de XOR (o-exclusivo) y AND (conjunción), respectivamente, con la disyunción x ∨ y (o-inclusivo) definible como x + y − xy y la negación ¬ x como 1 − x . En GF(2) , − puede reemplazarse por + , ya que denotan la misma operación; Sin embargo, esta forma de escribir operaciones booleanas permite aplicar las operaciones aritméticas habituales de números enteros (esto puede ser útil cuando se utiliza un lenguaje de programación en el que GF(2) no está implementado).

El álgebra de Boole también se ocupa de funciones que tienen sus valores en el conjunto {0,1} . Una secuencia de bits es un ejemplo de uso común de este tipo de función. Otro ejemplo común es la totalidad de subconjuntos de un conjunto E : para un subconjunto F de E , se puede definir la función indicadora que toma el valor 1 en F y 0 fuera de F. El ejemplo más general son los elementos del conjunto de un álgebra de Boole , siendo todos los anteriores instancias de los mismos.

Al igual que en el álgebra elemental, la parte puramente ecuacional de la teoría puede desarrollarse sin considerar valores explícitos para las variables. ^[17]

Esta sección necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables en esta sección. El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Álgebra de Boole» – noticias  · periódicos  · libros  · académico  · JSTOR ( abril de 2019 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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

Alternativamente, los valores de x ∧ y , x ∨ y y ¬ x se pueden expresar tabulando sus valores con tablas de verdad de la siguiente manera: ^[20]

${\estilo de visualización x}$ ${\estilo de visualización y}$ ${\displaystyle x\cuña y}$ ${\displaystyle x\vee y}$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

${\estilo de visualización x}$ ${\displaystyle \neg x}$ 0 1 1 0

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. ^[21]

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 suma y xy utiliza 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}}}$

Se podría considerar que sólo 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 la negación y la disyunción, y viceversa ( leyes de De Morgan ): ^[22]

${\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:

Material condicional :	${\textstyle x\rightarrow y=\neg {x}\vee y}$
Material bicondicional :	${\textstyle x\leftrightarrow y=(x\land y)\lor (\neg x\land \neg y)=(x\lor \neg y)\land (\neg x\lor y)}$
OR exclusivo ( XOR ):	${\textstyle x\oplus y=\neg (x\leftrightarrow y)=(x\vee y)\wedge \neg (x\wedge y)=(x\vee y)\wedge (\neg x\vee \neg y)=(x\wedge \neg y)\vee (\neg x\wedge y)}$

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

Operaciones secundarias. Tabla 1

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle x\rightarrow y}$	${\displaystyle x\oplus y}$	${\displaystyle x\leftrightarrow y,x\equiv y}$
0	0	1	0	1
1	0	0	1	0
0	1	1	1	0
1	1	1	0	1

Material condicional

La primera operación, x  →  y , o C xy , se denomina implicación material . Si x es verdadera, entonces el resultado de la expresión x  →  y se toma como el de y (por ejemplo, si x es verdadera e y es falsa, entonces x  →  y también es falsa). Pero si x es falsa, entonces el valor de y puede ignorarse; sin embargo, la operación debe devolver algún valor booleano y solo hay dos opciones. Entonces, por definición, x  →  y es verdadera cuando x es falsa. ( La lógica de relevancia sugiere 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 operación exclusiva o (a menudo abreviada como XOR) para distinguirla de la disyunción como la operación inclusiva. Excluye la posibilidad de que tanto x como y sean verdaderas (p. ej., consulte la tabla): si ambas son verdaderas, el resultado es falso. Definida en términos aritméticos, es una suma donde módulo 2 es 1 + 1 = 0.

Equivalencia lógica

La tercera operación, el complemento de la operación o 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 , siendo verdadera solo cuando x e y son diferentes. Por lo tanto, su contraparte en aritmética módulo 2 es x + y . La contraparte de la equivalencia en aritmética módulo 2 es x + y + 1.

Una ley del álgebra de Boole es una identidad como x ∨ ( y ∨ z ) = ( x ∨ y ) ∨ z entre dos términos booleanos, donde un término booleano se define como una expresión construida a partir de variables y las constantes 0 y 1 utilizando las operaciones ∧, ∨ y ¬. El concepto se puede extender a términos que involucran otras operaciones booleanas como ⊕, → y ≡, pero tales extensiones son innecesarias para los propósitos para los que se establecen las leyes. Estos propósitos incluyen la definición de un álgebra de Boole como cualquier modelo de las leyes de Boole, y como un medio para derivar nuevas leyes a partir de antiguas, como en la derivación de x ∨ ( y ∧ z ) = x ∨ ( z ∧ y ) a partir de y ∧ z = z ∧ y (como se trata en § Axiomatización del álgebra de Boole ).

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

Asociatividad de ∨ :		${\displaystyle x\vee (y\vee z)}$	${\displaystyle =(x\vee y)\vee z}$
Asociatividad de ∧ :		${\displaystyle x\wedge (y\wedge z)}$	${\displaystyle =(x\wedge y)\wedge z}$
Conmutatividad de ∨ :		${\displaystyle x\vee y}$	${\displaystyle =y\vee x}$
Conmutatividad de ∧ :		${\displaystyle x\wedge y}$	${\displaystyle =y\wedge x}$
Distributividad de ∧ sobre ∨ :		${\displaystyle x\wedge (y\vee z)}$	${\displaystyle =(x\wedge y)\vee (x\wedge z)}$
Identidad para ∨ :		${\displaystyle x\vee 0}$	${\displaystyle =x}$
Identidad para ∧ :		${\displaystyle x\wedge 1}$	${\displaystyle =x}$
Aniquilador para ∧ :		${\displaystyle x\wedge 0}$	${\displaystyle =0}$

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

Aniquilador para ∨ :		${\displaystyle x\vee 1}$	${\displaystyle =1}$
Idempotencia de ∨ :		${\displaystyle x\vee x}$	${\displaystyle =x}$
Idempotencia de ∧ :		${\displaystyle x\wedge x}$	${\displaystyle =x}$
Absorción 1:		${\displaystyle x\wedge (x\vee y)}$	${\displaystyle =x}$
Absorción 2:		${\displaystyle x\vee (x\wedge y)}$	${\displaystyle =x}$
Distributividad de ∨ sobre ∧ :		${\displaystyle x\vee (y\wedge z)}$	${\displaystyle =(x\vee y)\wedge (x\vee z)}$

Si tomamos x = 2 en la tercera ley anterior, se demuestra que no se trata de una ley del álgebra ordinaria, ya que 2 × 2 = 4. Las cinco leyes restantes se pueden refutar en el á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 han sido para conjunción y disyunción. Estas operaciones tienen la propiedad de que al cambiar cualquiera de los argumentos, la salida permanece inalterada o la salida cambia de la misma manera que la entrada. De manera equivalente, cambiar cualquier variable de 0 a 1 nunca da como resultado que la salida cambie de 1 a 0. Se dice que las operaciones con esta propiedad son monótonas . Por lo tanto, todos los axiomas hasta ahora han sido para lógica booleana monótona. La no monotonía entra a través del complemento ¬ de la siguiente manera. ^[5]

La operación de complemento se define por 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 siguientes, se derivan únicamente de las dos leyes anteriores. ^[5]

Tanto en el álgebra ordinaria como en el álgebra de Boole, la negación funciona intercambiando pares de elementos, por lo tanto, en ambas álgebras satisface la ley de 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 de Boole 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 de Boole, 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 tomarse como un posible conjunto completo de leyes o axiomatización del álgebra de Boole. Cada ley del álgebra de Boole se sigue lógicamente de estos axiomas. Además, las álgebras de Boole pueden definirse como los modelos de estos axiomas, tal como se trata en § Álgebras de Boole .

La redacción de nuevas leyes del álgebra de Boole no puede dar lugar a nuevas consecuencias de estos axiomas, ni puede descartar ningún modelo de ellos. Por el contrario, en una lista de algunas leyes, pero no todas, podría haber leyes de Boole que no se dedujeran de las de la lista y, además, habría habido modelos de las leyes enumeradas que no fueran álgebras de Boole.

Esta axiomatización no es de ninguna manera la única, o incluso necesariamente la más natural dado que no se prestó atención a si algunos de los axiomas se seguían de otros, sino que simplemente había una opción de parar cuando se habían notado suficientes leyes, tratada más adelante en § Axiomatización del álgebra de Boole . O la noción intermedia de axioma puede eludirse por completo 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. ^{[25] [26]} Se puede demostrar que todas estas definiciones de álgebra de Boole 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 de Boole. 0 y 1 podrían renombrarse como α y β , y siempre que se hiciera de manera consistente en todo momento, seguiría siendo álgebra de Boole, aunque con algunas diferencias cosméticas obvias.

Pero supongamos que 0 y 1 se renombraran como 1 y 0 respectivamente. Entonces seguiría siendo álgebra de Boole y, además, operaría con los mismos valores. Sin embargo, no sería idéntica a nuestra álgebra de Boole original porque ahora ∨ se comporta de la misma manera que ∧ y viceversa. Por lo tanto, todavía hay algunas diferencias cosméticas que muestran que la notación ha cambiado, a pesar del hecho de que todavía 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, ya no queda rastro de lo que se ha hecho. El producto final es completamente indistinguible del producto inicial. Las columnas para 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 manera que todo lo importante permanece inalterado cuando todos los pares se intercambian simultáneamente, los miembros de cada par se denominan duales entre sí. Por lo tanto, 0 y 1 son duales, y ∧ y ∨ son duales. El principio de dualidad , también llamado dualidad de De Morgan , afirma que el álgebra de Boole no cambia cuando se intercambian todos los pares duales.

Un cambio que no fue necesario hacer como parte de este intercambio fue complementar. El complemento 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 una perspectiva de teoría de grupos por el hecho de que hay exactamente cuatro funciones que son aplicaciones uno a uno ( 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 composición de funciones , isomorfas al cuatrigrupo de Klein , 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 de principio (o cuadrado ) de cuaternalidad . ^{[5] : 21–22}

Se puede utilizar un diagrama de Venn ^[27] como representación de una operación booleana utilizando regiones superpuestas sombreadas. Hay una región para cada variable, todas circulares en los ejemplos aquí. 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 denota 1 y el color 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 .

Para 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.

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

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

La idempotencia de ∧ y ∨ se puede visualizar deslizando los dos círculos juntos y observando que el área sombreada se convierte 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 y observe que sombrear todo el círculo x da como resultado que solo se sombree el círculo x , ya que el sombreado anterior estaba dentro del círculo x .

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

Para visualizar la primera ley de De Morgan, (¬ x ) ∧ (¬ y ) = ¬( x ∨ y ) , comience con el diagrama del medio para x ∨ y y complemente su sombreado de modo que solo la región fuera de ambos círculos esté sombreada, que es lo que describe el lado derecho de la ley. El resultado es el mismo que si sombreáramos esa región que está tanto fuera del círculo x como 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 con los dos diagramas intercambiados.

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

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

Las líneas a la izquierda de cada compuerta representan cables o puertos de entrada . El valor de la entrada está representado por un voltaje en el cable. Para la denominada lógica "activa-alta", 0 está representado por un voltaje cercano a cero o "tierra", mientras que 1 está representado por un voltaje cercano al voltaje de suministro; la lógica activa-baja invierte esto. 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.

El complemento se implementa con una compuerta inversora. El triángulo denota la operación que simplemente copia la entrada a la salida; el círculo pequeño en la salida denota la inversión real que complementa la entrada. La convención de colocar un círculo de este tipo en cualquier puerto significa que la señal que pasa por este puerto se complementa en el camino, ya sea un puerto de entrada o de salida.

El principio de dualidad, o leyes de De Morgan , puede entenderse como la afirmación de que complementar los tres puertos de una compuerta AND la convierte en una compuerta OR y viceversa, como se muestra en la Figura 4 a continuación. Sin embargo, complementar ambos puertos de un inversor deja la operación sin cambios.

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

El término "álgebra" designa tanto un sujeto, a saber, el sujeto del álgebra , como un objeto, a saber, una estructura algebraica . Mientras que en lo anterior se ha abordado el tema del álgebra de Boole, en esta sección se tratan los objetos matemáticos llamados álgebras de Boole, definidas en su generalidad completa como cualquier modelo de las leyes de Boole. Comenzamos con un caso especial de la noción definible sin referencia a las leyes, a saber, las álgebras de Boole concretas, y luego damos la definición formal de la noción general.

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

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

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

Ejemplo 2. El conjunto vacío y X . Esta álgebra de dos elementos muestra que un álgebra de Boole concreta puede ser finita incluso cuando consta de subconjuntos de un conjunto infinito. Se puede ver 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, aparte del álgebra degenerada obtenida al tomar X como vacío de modo que el conjunto vacío y X coincidan.

Ejemplo 3. El conjunto de conjuntos finitos y cofinitos de números enteros, donde un conjunto cofinito es aquel que omite solo un número finito de números enteros. Esto es claramente cerrado bajo complemento, y es cerrado bajo unión porque la unión de un conjunto cofinito con cualquier conjunto es cofinita, mientras que la unión de dos conjuntos finitos es finita. La intersección se comporta como una unión con "finito" y "cofinito" intercambiados. Este ejemplo es infinito numerable porque solo hay un número numerable de conjuntos finitos de números enteros.

Ejemplo 4. Para un ejemplo menos trivial del punto planteado en el ejemplo 2, considere un diagrama de Venn formado por n curvas cerradas que dividen el diagrama en 2 ⁿ regiones, y sea X el conjunto (infinito) de todos los puntos en el plano que no están en ninguna curva sino 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á exactamente en 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 relativo a X y, por lo tanto, forma un álgebra de Boole concreta. Nuevamente, hay un número finito de subconjuntos de un conjunto infinito que forman un álgebra de Boole concreta, y el ejemplo 2 surge como el caso n = 0 de ninguna curva.

Un subconjunto Y de X se puede identificar con una familia indexada de bits con el conjunto de índices X , donde el bit indexado por x ∈ X es 1 o 0 según si x ∈ Y es 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 ven como 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 los indexados por los reales en el intervalo unitario [0,1] están empaquetados demasiado densamente para poder escribirse de manera convencional, pero no obstante forman familias indexadas bien definidas (imagine 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 vectores de bits, un álgebra booleana concreta puede definirse de manera equivalente 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 ¬ bit a bit, 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, como se ha tratado anteriormente, pueden entenderse como el caso especial de los vectores de bits de longitud uno, que, mediante la identificación de los vectores de bits con subconjuntos, también pueden entenderse como los dos subconjuntos de un conjunto de un elemento. Esto se denomina álgebra booleana prototípica , justificada por la siguiente observación.

Las leyes satisfechas por todas las álgebras de Boole concretas no degeneradas coinciden con las satisfechas por el álgebra de Boole prototípica.

Esta observación se demuestra de la siguiente manera. Ciertamente, cualquier ley satisfecha por todas las álgebras de Boole concretas se satisface por la prototípica, ya que es concreta. A la inversa, cualquier ley que no se cumpla para alguna álgebra de Boole concreta debe haber fallado en una posición de bit particular, en cuyo caso esa posición por sí misma proporciona un contraejemplo de un bit a esa ley. La no degeneración asegura la existencia de al menos una posición de bit porque solo hay un vector de bits vacío.

El objetivo final de la siguiente sección puede entenderse como la eliminación de lo "concreto" de la observación anterior. Ese objetivo se alcanza mediante la observación más sólida de que, salvo el isomorfismo, todas las álgebras de Boole son concretas.

Hasta ahora, todas las álgebras de Boole han sido concretas, consistentes en vectores de bits o, equivalentemente, en subconjuntos de algún conjunto. Una álgebra de Boole de este tipo consiste en un conjunto y operaciones sobre ese conjunto que se puede demostrar que satisfacen las leyes del álgebra de Boole.

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

Un álgebra de Boole es cualquier conjunto con operaciones binarias ∧ y ∨ y una operación unaria ¬ sobre ellas que satisfacen las leyes de Boole. ^[29]

Para los fines de esta definición, es irrelevante cómo las operaciones llegaron a satisfacer las leyes, ya sea por decreto o por prueba. Todas las álgebras de Boole concretas satisfacen las leyes (por prueba en lugar de por decreto), por lo que toda álgebra de Boole concreta es un álgebra de Boole según nuestras definiciones. Esta definición axiomática de un álgebra de Boole 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 de Boole, 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 de Boole es que satisfaga sólo esos axiomas. La siguiente es, por tanto, una definición equivalente.

Un álgebra de Boole es una red distributiva complementada.

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 de Boole concreta es un álgebra de Boole, no toda álgebra de Boole necesita ser concreta. Sea n un entero positivo sin cuadrados , uno no 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 de Boole cuando sus argumentos abarcan los divisores positivos de n . Por lo tanto, esos divisores forman un álgebra de Boole. Estos divisores no son subconjuntos de un conjunto, lo que hace que los divisores de n sean un álgebra de Boole que no es concreta según nuestras definiciones.

Sin embargo, si cada divisor de n está representado por el conjunto de sus factores primos, esta álgebra de Boole no concreta es isomorfa al álgebra de Boole concreta que consiste en todos los conjuntos de factores primos de n , correspondiendo la unión al mínimo común múltiplo, la intersección al máximo común divisor y el complemento a la división entre n . Por lo tanto, este ejemplo, si bien no es técnicamente concreto, es al menos "moralmente" concreto a través de esta representación, llamada isomorfismo . Este ejemplo es una instancia de la siguiente noción.

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

La siguiente pregunta se responde afirmativamente de la siguiente manera.

Toda álgebra de Boole es representable.

Es decir, hasta el isomorfismo, las álgebras de Boole abstractas y concretas son la misma cosa. Este resultado depende del teorema del ideal primo de Boole , 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 hasta la siguiente consecuencia fácil de representabilidad.

Las leyes satisfechas por todas las álgebras de Boole coinciden con aquellas satisfechas por el álgebra de Boole prototípica.

Es más débil en el sentido de que no implica por sí misma representabilidad. Las álgebras de Boole son especiales en este sentido; por ejemplo, un álgebra relacional es un álgebra de Boole con estructura adicional, pero no es el caso de que toda álgebra relacional sea representable en el sentido apropiado para las álgebras relacionales.

La definición anterior de un álgebra de Boole abstracta como un conjunto de operaciones que satisfacen "las" leyes de Boole plantea la cuestión de cuáles son esas leyes. Una respuesta simplista es "todas las leyes de Boole", que pueden definirse como todas las ecuaciones que se cumplen para el álgebra de Boole de 0 y 1. Sin embargo, dado que existen infinitas leyes de ese tipo, esta no es una respuesta satisfactoria en la práctica, lo que lleva a la pregunta de si basta con que se cumplan un número finito de leyes.

En el caso de las álgebras de Boole, la respuesta es "sí": las ecuaciones finitas enumeradas anteriormente son suficientes. Por lo tanto, se dice que el álgebra de Boole es finitamente axiomatizable o finitamente basada .

Además, el número de ecuaciones necesarias se puede reducir aún más. Para empezar, algunas de las leyes anteriores están implícitas en algunas de las otras. Un subconjunto suficiente de las leyes anteriores consiste en los pares de leyes de asociatividad, conmutatividad y absorción, la distributividad de ∧ sobre ∨ (o la otra ley de distributividad; una es suficiente) y las dos leyes complementarias. De hecho, esta es la axiomatización tradicional del álgebra de Boole como un retículo distributivo complementado .

Al introducir leyes adicionales no incluidas en la lista anterior, es posible acortar aún más la lista de ecuaciones necesarias; por ejemplo, con la barra vertical que representa la operación de trazo de Sheffer , el axioma único es suficiente para axiomatizar por completo el álgebra de Boole. También es posible encontrar axiomas individuales más largos utilizando operaciones más convencionales; consulte Axiomas mínimos para el álgebra de Boole . ^[30]${\displaystyle ((a\mid b)\mid c)\mid (a\mid ((a\mid c)\mid a))=c}$

La lógica proposicional es un sistema lógico que está íntimamente conectado con el álgebra de Boole. ^[5] Muchos conceptos sintácticos del álgebra de Boole se trasladan a la lógica proposicional con solo cambios menores en la notación y la terminología, mientras que la semántica de la lógica proposicional se define a través de las álgebras de Boole de manera que las tautologías (teoremas) de la lógica proposicional corresponden a los teoremas ecuacionales del álgebra de Boole.

Sintácticamente, cada término booleano corresponde a una fórmula proposicional de la lógica proposicional. En esta traducción entre el álgebra de Boole y la lógica proposicional, las variables booleanas x, y, ... se convierten en variables proposicionales (o átomos ) P, Q , ... Los términos booleanos como x ∨ y se convierten en fórmulas proposicionales P ∨ Q ; 0 se convierte en falso o ⊥ , y 1 se convierte en verdadero o T . Es conveniente, cuando se hace referencia a proposiciones genéricas, utilizar las letras griegas Φ, Ψ, ... como metavariables (variables fuera del lenguaje del cálculo proposicional, utilizadas cuando se habla de cálculo proposicional) para denotar proposiciones.

La semántica de la lógica proposicional se basa en asignaciones de verdad . La idea esencial de una asignación de verdad es que las variables proposicionales se asignan a elementos de un álgebra de Boole fija, y luego el valor de verdad de una fórmula proposicional que utiliza estas letras es el elemento del álgebra de Boole que se obtiene al calcular el valor del término booleano correspondiente a la fórmula. En la semántica clásica, solo se utiliza el álgebra de Boole de dos elementos, mientras que en la semántica con valores booleanos se consideran álgebras de Boole arbitrarias. Una tautología es una fórmula proposicional a la que se le asigna un valor de verdad 1 por cada asignación de verdad de sus variables proposicionales a un álgebra de Boole arbitraria (o, equivalentemente, cada asignación de verdad al álgebra de Boole de dos elementos).

Estas semánticas permiten una traducción entre tautologías de lógica proposicional y teoremas ecuacionales del álgebra de Boole. Toda tautología Φ de lógica proposicional puede ser expresada como la ecuación booleana Φ = 1, que será un teorema del álgebra de Boole. Por el contrario, todo teorema Φ = Ψ del álgebra de Boole corresponde a las tautologías (Φ ∨ ¬Ψ) ∧ (¬Φ ∨ Ψ) y (Φ ∧ Ψ) ∨ (¬Φ ∧ ¬Ψ). Si → está en el lenguaje, estas últimas tautologías también pueden escribirse como (Φ → Ψ) ∧ (Ψ → Φ), o como dos teoremas separados Φ → Ψ y Ψ → Φ; Si ≡ está disponible, entonces se puede utilizar la tautología simple Φ ≡ Ψ.

Una aplicación motivadora del cálculo proposicional es el análisis de proposiciones y argumentos deductivos en lenguaje natural. ^[31] 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 depende de ello; es verdadera simplemente en virtud de su estructura, y sigue siendo verdadera ya sea que " x = 3" sea reemplazado 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 de Boole, P → P . ^{[ cita requerida ]}

Reemplazar P por x = 3 o cualquier otra proposición se denomina instanciación de P por esa 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 en virtud de 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 tonterías como P → x = 3 o x = 3 → x = 4.

El cálculo proposicional restringe su atención a proposiciones abstractas, aquellas construidas a partir de variables proposicionales utilizando operaciones booleanas. La instanciación aún es 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 obtener la instancia P → (( Q → P ) → P ).

(La disponibilidad de la instanciación como parte de la maquinaria 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 del lenguaje para denotar proposiciones arbitrarias. Las metavariables en sí mismas están fuera del alcance de la instanciación, al no ser parte del lenguaje del cálculo proposicional sino más bien parte del mismo lenguaje para hablar sobre él en el que está escrita esta oración, donde existe la necesidad de poder distinguir las variables proposicionales y sus instancias 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 producir 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 por alguna regla de A de proposiciones que aparecen antes en la demostración (lo que impide el razonamiento circular). La última proposición es el teorema demostrado por la demostración. Cada segmento inicial no vacío de una demostración es en sí mismo una demostración, por lo que cada proposición en una demostración es en sí misma un teorema. Una axiomatización es válida cuando cada teorema es una tautología, y completa cuando cada tautología es un teorema. ^[32]

El cálculo proposicional se organiza comúnmente como un sistema de Hilbert , cuyas operaciones son simplemente las del álgebra de Boole y cuyos teoremas son tautologías booleanas, aquellos términos booleanos iguales a la constante booleana 1. Otra forma es el cálculo secuente , que tiene dos tipos, proposiciones como en el cálculo proposicional ordinario, y pares de listas de proposiciones llamadas secuentes , como A ∨ B , A ∧ C , ... ⊢ A , B → C , .... Las dos mitades de un secuente se llaman antecedente y sucedente respectivamente. La metavariable habitual que denota un antecedente o parte del mismo es Γ, y para un sucedente Δ; Así, Γ, A ⊢ Δ denotaría un consecuente cuyo sucedente es una lista Δ y cuyo antecedente es una lista Γ con una proposición adicional A añadida después de ella. El antecedente se interpreta como la conjunción de sus proposiciones, el sucedente como la disyunción de sus proposiciones y el consecuente mismo como la implicación del sucedente por el antecedente.

La implicación se diferencia de la implicación en que, mientras que esta última es una operación binaria que devuelve un valor en un álgebra de Boole, la primera es una relación binaria que se cumple o no. En este sentido, la implicación es una forma externa de implicación, es decir, externa al álgebra de Boole, considerando al lector del consecuente como también externo e interpretando y comparando antecedentes y sucedentes en alguna álgebra de Boole. La interpretación natural de ⊢ es como ≤ en el orden parcial del álgebra de Boole definida por x ≤ y justo cuando x ∨ y = y . Esta capacidad de mezclar la implicación externa ⊢ y la implicación interna → en la misma lógica es una de las diferencias esenciales entre el cálculo consecuente y el cálculo proposicional. ^[33]

El álgebra de Boole, como cálculo de dos valores, es fundamental para los circuitos informáticos, la programación informática y la lógica matemática, y también se utiliza en otras áreas de las matemáticas, como la teoría de conjuntos y la estadística. ^[5]

A principios del siglo XX, varios ingenieros eléctricos ^{[ ¿quiénes? ]} reconocieron intuitivamente que el álgebra de Boole 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 de Boole en su tesis de maestría de 1937, Un análisis simbólico de circuitos de conmutación y relés .

En la actualidad, todas las computadoras modernas de propósito general realizan sus funciones utilizando lógica booleana de dos valores; es decir, sus circuitos eléctricos son una manifestación física de la lógica booleana de dos valores. Lo logran de diversas maneras: como voltajes en cables en circuitos de alta velocidad y dispositivos de almacenamiento capacitivos, como orientaciones de un dominio magnético en dispositivos de almacenamiento ferromagnético, como agujeros en tarjetas perforadas o cinta de papel , etc. (Algunas de las primeras computadoras usaban circuitos o mecanismos decimales en lugar de circuitos lógicos de dos valores).

Por supuesto, es posible codificar más de dos símbolos en un medio determinado. Por ejemplo, se pueden utilizar respectivamente 0, 1, 2 y 3 voltios para codificar un alfabeto de cuatro símbolos en un cable, o agujeros de distintos tamaños en una tarjeta perforada. En la práctica, las estrictas restricciones de alta velocidad, tamaño pequeño y bajo consumo se combinan para hacer del ruido un factor importante. Esto dificulta la distinción entre símbolos cuando hay varios símbolos posibles que podrían aparecer en un solo sitio. En lugar de intentar distinguir entre cuatro voltajes en un cable, los diseñadores digitales se han decidido por dos voltajes por cable, alto y bajo.

Las computadoras utilizan circuitos booleanos de dos valores por las razones anteriores. Las arquitecturas de computadora más comunes utilizan secuencias ordenadas de valores booleanos, llamados bits, de 32 o 64 valores, por ejemplo, 01101000110101100101010101010011. Al programar en código de máquina , lenguaje ensamblador y algunos 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 representa el 0 booleano y un voltaje de referencia (a menudo +5 V, +3,3 V o +1,8 V) representa el 1 booleano. Dichos lenguajes admiten tanto operaciones numéricas como operaciones lógicas. En este contexto, "numérico" significa que la computadora trata las secuencias de bits como números binarios (números de base dos) y ejecuta operaciones aritméticas como sumar, restar, multiplicar o dividir. "Lógica" se refiere a las operaciones lógicas booleanas de disyunción, conjunción y negación entre dos secuencias de bits, en las que cada bit de una secuencia se compara simplemente con su contraparte en la otra secuencia. Por lo tanto, los programadores tienen la opción de trabajar y aplicar las reglas del álgebra numérica o del álgebra booleana según sea necesario. Una característica diferenciadora 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 en los que dos valores son una buena opción son el derecho y las matemáticas. En una conversación cotidiana y relajada, son aceptables respuestas matizadas o complejas como "tal vez" o "sólo los fines de semana". Sin embargo, en situaciones más concretas, como un tribunal de justicia o matemáticas basadas en teoremas, se considera ventajoso formular las preguntas de modo que admitan una respuesta simple de sí o no (¿el acusado es culpable o inocente?, ¿la proposición es verdadera o falsa?) y no admitan ninguna otra respuesta. Sin embargo, limitar esto podría resultar en la práctica para el acusado, el principio de la pregunta simple de sí o no se ha convertido en una característica central tanto de la lógica judicial como de la matemática, lo que hace que la lógica de dos valores merezca organización y estudio por derecho propio.

Un concepto central de la teoría de conjuntos es la pertenencia. Una organización puede permitir múltiples grados de pertenencia, como novato, asociado y pleno. Sin embargo, en los conjuntos, un elemento está dentro o fuera. Los candidatos a ser miembros de un conjunto funcionan como los cables de una computadora digital: cada candidato es miembro o no miembro, de la misma manera que cada cable es alto o bajo.

Siendo el álgebra 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 importancia fundamental para el hardware de las computadoras, la lógica matemática y la teoría de conjuntos.

La lógica de dos valores se puede extender a la lógica multivaluada , en particular reemplazando el dominio booleano {0, 1} con el intervalo unitario [0,1], en cuyo caso, en lugar de tomar solo los valores 0 o 1, se puede asumir cualquier valor entre 0 y 1 inclusive. Algebraicamente, la negación (NOT) se reemplaza con 1 −  x , la conjunción (AND) se reemplaza con la multiplicación ( xy ) y la disyunción (OR) se define mediante la ley de De Morgan . Interpretar estos valores como valores de verdad lógicos produce una lógica multivaluada, que forma 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: en qué medida una proposición es verdadera o la probabilidad de que la proposición sea verdadera.

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

Los lenguajes naturales como el inglés tienen palabras para varias operaciones booleanas, en particular conjunción ( y ), disyunción ( o ), negación ( no ) e implicación ( implica ). Pero no es sinónimo de y no . Cuando se usa para combinar afirmaciones situacionales como "el bloque está sobre la mesa" y "los gatos beben leche", que ingenuamente son verdaderas o falsas, los significados de estos conectivos lógicos a menudo tienen el significado de sus contrapartes lógicas. Sin embargo, con descripciones de comportamiento como "Jim entró por la puerta", uno comienza a notar diferencias como el fallo de la conmutatividad, por ejemplo, la conjunción de "Jim abrió la puerta" con "Jim entró por la puerta" en ese orden no es equivalente a su conjunción en el otro orden, ya que y generalmente significa y luego en tales casos. Las preguntas pueden ser similares: el orden "¿El cielo es azul y por qué es azul?" tiene más sentido que el orden inverso. Los mandatos conjuntivos sobre el comportamiento son como las afirmaciones conductuales, como en vístete y ve a la escuela . Los mandatos disyuntivos como "ámame" o "déjame" o "pesca" o "corta el cebo" tienden a ser asimétricos a través de la implicación de que una alternativa es menos preferible. Los sustantivos unidos como "té" y "leche" generalmente describen la agregación como con la unión de conjuntos mientras que "té" o "leche" son una opción. Sin embargo, el contexto puede invertir estos sentidos, como en " tus opciones son café y té ", que generalmente significa lo mismo que " tus opciones son café o té " (alternativas). La doble negación, como en "no me gusta la leche", rara vez significa literalmente "me gusta la leche", sino que transmite algún tipo de evasiva, como para implicar que hay una tercera posibilidad. "No no P" puede interpretarse libremente como "seguramente P", y aunque P necesariamente implica "no no P ", lo inverso es sospechoso en inglés, al igual que con la lógica intuicionista . En vista del uso altamente idiosincrásico de las conjunciones en los lenguajes naturales, el álgebra de Boole no puede considerarse un marco confiable para interpretarlas.

Las operaciones booleanas se utilizan en lógica digital para combinar los bits transportados en cables individuales, interpretándolos así sobre {0,1}. Cuando se utiliza un vector de n puertas binarias idénticas para combinar dos vectores de bits cada uno de n bits, las operaciones de bits individuales pueden entenderse colectivamente como una única operación sobre valores de un álgebra booleana con 2 ⁿ elementos.

La teoría de conjuntos ingenua interpreta las operaciones booleanas como si actuaran sobre subconjuntos de un conjunto dado X. Como vimos anteriormente, este comportamiento es exactamente paralelo a las combinaciones de vectores de bits según las coordenadas, donde la unión de dos conjuntos corresponde a la disyunción de dos vectores de bits, y así sucesivamente.

El álgebra booleana libre de 256 elementos en tres generadores se utiliza en pantallas de ordenador basadas en gráficos rasterizados , que utilizan el bit blit para manipular regiones enteras formadas por píxeles , apoyándose en operaciones booleanas para especificar cómo debe combinarse la región de origen con la de destino, normalmente con la ayuda de una tercera región llamada máscara . Las tarjetas de vídeo modernas ofrecen las 2 ^{2 3} = 256 operaciones ternarias para este fin, siendo la elección de la operación un parámetro de un byte (8 bits). Las constantes SRC = 0xaa o 0b10101010 , DST = 0xcc o 0b11001100 , y MSK = 0xf0 o 0b11110000 permiten que operaciones booleanas como (es decir, XOR el origen y el destino y luego AND el resultado con la máscara) se escriban directamente como una constante que denota un byte calculado en tiempo de compilación, 0x80 en el ejemplo, 0x88 si solo , etc. En tiempo de ejecución, la tarjeta de video interpreta el byte como la operación rasterizada indicada por la expresión original de una manera uniforme que requiere notablemente poco hardware y que lleva tiempo completamente independiente de la complejidad de la expresión.(SRC^DST)&MSK(SRC^DST)&MSKSRC^DST

Los sistemas de modelado de sólidos para el diseño asistido por ordenador ofrecen una variedad de métodos para construir objetos a partir de otros objetos, siendo la combinación mediante operaciones booleanas uno de ellos. En este método, el espacio en el que existen los objetos se entiende como un conjunto S de vóxeles (el análogo tridimensional de los píxeles en gráficos bidimensionales) y las formas se definen como subconjuntos de S , lo que permite combinar objetos como conjuntos mediante unión, intersección, etc. Un uso obvio es la construcción de una forma compleja a partir de formas simples simplemente como la unión de estas últimas. Otro uso es en la escultura entendida como eliminación de material: cualquier operación de pulido, fresado, enrutamiento o taladrado que se pueda realizar con maquinaria física sobre materiales físicos se puede simular en el ordenador con la operación booleana x ∧ ¬ y o x − y , que en teoría de conjuntos es diferencia de conjuntos, eliminar los elementos de y de los de x . Así, dadas dos formas, una a mecanizar y la otra el material a eliminar, el resultado de mecanizar la primera para eliminar el segundo se describe simplemente como su diferencia de conjuntos.

Las consultas de los motores de búsqueda también emplean lógica booleana. Para esta aplicación, cada página web de Internet puede considerarse un "elemento" de un "conjunto". Los siguientes ejemplos utilizan una sintaxis compatible con Google . ^{[NB 1]}

• Las comillas dobles se utilizan para combinar palabras separadas por espacios en blanco en un único término de búsqueda. ^{[NB 2]}
• Los espacios en blanco se utilizan para especificar el operador lógico AND, ya que es el operador predeterminado para unir términos de búsqueda:

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

• La palabra clave OR se utiliza para OR lógico:

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

• Se utiliza un signo menos prefijado para el NO lógico:

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

• Mano, Morris; Ciletti, Michael D. (2013). Diseño digital . Pearson. ISBN 978-0-13-277420-8.
• Whitesitt, J. Eldon (1995). Álgebra de Boole y sus aplicaciones . Courier Dover Publications . ISBN 978-0-486-68483-3.
• Dwinger, Philip (1971). Introducción a las álgebras de Boole . Würzburg, Alemania: Physica Verlag.
• Sikorski, romano (1969). Álgebras de Boole (3 ed.). Berlín, Alemania: Springer-Verlag . ISBN 978-0-387-04469-9.
• Bocheński, Józef Maria (1959). Resumen de lógica matemática . Traducido de las ediciones francesa y alemana por Otto Bird. Dordrecht, Holanda Meridional: D. Reidel.

• Boole, George (1848). "El cálculo de la lógica". 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 surgimiento 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 relativos . Princeton University Press . ISBN 978-0-691-05853-5.
• Stanković, Radomir S. [en alemán] ; Astola, Jaakko Tapio [en finlandé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 . pp. 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 Burris, Stanley, "El álgebra de la tradición lógica" en la Stanford Encyclopedia of Philosophy , 21 de febrero de 2012

El Wikilibro Cómo buscar tiene una página sobre el tema: Lógica booleana

La Wikilibro Electrónica tiene una página sobre el tema: Álgebra de Boole