En matemáticas y álgebra abstracta , el álgebra de Boole de dos elementos es el álgebra de Boole cuyo conjunto subyacente (o universo o portador ) B es el dominio de Boole . Los elementos del dominio de Boole son 1 y 0 por convención, de modo que B = {0, 1}. El nombre que Paul Halmos le dio a esta álgebra, " 2 ", tiene algunos seguidores en la literatura y será el que se empleará aquí.
B es un conjunto parcialmente ordenado y los elementos de B son también sus límites .
Una operación de aridad n es una aplicación de B n a B . El álgebra de Boole consta de dos operaciones binarias y complementación unaria . Las operaciones binarias han sido nombradas y anotadas de varias maneras. Aquí se llaman 'suma' y 'producto', y se anotan con los infijos '+' y '∙', respectivamente. La suma y el producto conmutan y asocian , como en el álgebra habitual de números reales . En cuanto al orden de las operaciones , los corchetes son decisivos si están presentes. De lo contrario, '∙' precede a '+'. Por lo tanto, A ∙ B + C se analiza como ( A ∙ B ) + C y no como A ∙ ( B + C) . La complementación se denota escribiendo una barra superior sobre su argumento. El análogo numérico del complemento de X es 1 − X . En el lenguaje del álgebra universal , un álgebra de Boole es un álgebra ∙ de tipo .
La correspondencia biunívoca entre {0,1} y { Verdadero , Falso } produce lógica bivalente clásica en forma ecuacional, con complementación que se lee como NOT . Si 1 se lee como Verdadero , '+' se lee como OR y '∙' como AND , y viceversa si 1 se lee como Falso . Estas dos operaciones definen un semianillo conmutativo , conocido como semianillo booleano .
2 puede verse como fundamentado en la siguiente aritmética "booleana" trivial:
Tenga en cuenta que:
Esta aritmética booleana es suficiente para verificar cualquier ecuación de 2 , incluidos los axiomas, examinando cada posible asignación de 0 y 1 a cada variable (véase el procedimiento de decisión ).
Ahora se pueden verificar las siguientes ecuaciones:
Cada uno de '+' y '∙' se distribuye sobre el otro:
El hecho de que '∙' se distribuya sobre '+' concuerda con el álgebra elemental , pero no con '+' sobre '∙'. Por esta y otras razones, se emplea más comúnmente una suma de productos (que conduce a una síntesis NAND ) que un producto de sumas (que conduce a una síntesis NOR ).
Cada uno de '+' y '∙' se puede definir en términos del otro y de la complementación:
Solo necesitamos una operación binaria, y la concatenación es suficiente para denotarla. Por lo tanto, la concatenación y la barra superior son suficientes para denotar 2. Esta notación es también la de los esquemas de términos booleanos de Quine . Si ( X ) denota el complemento de X y "()" denota 0 o 1, obtenemos la sintaxis del álgebra primaria de las Leyes de la forma de G. Spencer- Brown .
Una base para 2 es un conjunto de ecuaciones, llamadas axiomas , de las cuales se pueden derivar todas las ecuaciones anteriores (y más). Existen muchas bases conocidas para todas las álgebras de Boole y, por lo tanto, para 2. Una base elegante anotada utilizando solo concatenación y barra superior es:
Donde concatenación = OR, 1 = verdadero y 0 = falso, o concatenación = AND, 1 = falso y 0 = verdadero. (la barra superior es negación en ambos casos).
Si 0=1, (1)-(3) son los axiomas para un grupo abeliano .
(1) sólo sirve para demostrar que la concatenación conmuta y asocia. Supongamos primero que (1) asocia desde la izquierda o la derecha, luego demostremos la conmutatividad. Luego demostremos la asociación desde la otra dirección. La asociatividad es simplemente la asociación desde la izquierda y la derecha combinadas.
Esta base permite un enfoque fácil para la prueba, llamada "cálculo" en Leyes de la Forma , que procede simplificando expresiones a 0 o 1, invocando los axiomas (2)–(4), las identidades elementales y la ley distributiva.
El teorema de De Morgan establece que si se hace lo siguiente, en el orden dado, con cualquier función booleana :
El resultado es lógicamente equivalente al que tenías al principio. La aplicación repetida del teorema de De Morgan a partes de una función se puede utilizar para reducir todos los complementos a las variables individuales.
Un metateorema poderoso y no trivial establece que cualquier identidad de 2 se cumple para todas las álgebras de Boole. [1] A la inversa, una identidad que se cumple para un álgebra de Boole no trivial arbitraria también se cumple en 2 . Por lo tanto, todas las identidades del álgebra de Boole están capturadas por 2 . Este teorema es útil porque cualquier ecuación en 2 puede verificarse mediante un procedimiento de decisión . Los lógicos se refieren a este hecho como " 2 es decidible ". Todos los procedimientos de decisión conocidos requieren un número de pasos que es una función exponencial del número de variables N que aparecen en la ecuación a verificar. Si existe un procedimiento de decisión cuyos pasos son una función polinómica de N cae dentro de la conjetura P = NP .
El metateorema anterior no se cumple si consideramos la validez de fórmulas lógicas de primer orden más generales en lugar de solo igualdades positivas atómicas. Como ejemplo, considere la fórmula ( x = 0) ∨ ( x = 1) . Esta fórmula siempre es verdadera en un álgebra de Boole de dos elementos. En un álgebra de Boole de cuatro elementos cuyo dominio es el conjunto potencia de , esta fórmula corresponde al enunciado ( x = ∅) ∨ ( x = {0,1}) y es falsa cuando x es . La decidibilidad para la teoría de primer orden de muchas clases de álgebras de Boole todavía se puede demostrar, utilizando la eliminación de cuantificadores o la propiedad del modelo pequeño (con el tamaño del dominio calculado como una función de la fórmula y generalmente mayor que 2).
En los primeros años de la era informática se publicaron muchos textos elementales sobre álgebra de Boole. Quizá el mejor de todos ellos, y el que todavía se publica, sea:
Los siguientes elementos revelan cómo el álgebra booleana de dos elementos es matemáticamente no trivial.
