En matemáticas y álgebra abstracta , el álgebra booleana de dos elementos es el álgebra booleana cuyo conjunto subyacente (o universo o portador ) B es el dominio booleano . Los elementos del dominio booleano son 1 y 0 por convención, de modo que B = {0, 1}. El nombre de Paul Halmos para esta álgebra " 2 " tiene algunos seguidores en la literatura y se empleará aquí.
B es un conjunto parcialmente ordenado y los elementos de B también son sus límites .
Una operación de aridad n es un mapeo de B n a B . El álgebra booleana consta de dos operaciones binarias y complementación unaria . Las operaciones binarias han sido nombradas y anotadas de varias maneras. Aquí se denominan 'suma' y 'producto', y se anotan con el infijo '+' y '∙', respectivamente. La suma y el producto se 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 booleana es un álgebra de tipo ∙ .
Cualquier correspondencia uno a uno entre {0,1} y { Verdadero , Falso } produce una lógica bivalente clásica en forma ecuacional, con la complementación leída como NOT . Si 1 se lee como Verdadero , '+' se lee como O y '∙' como Y , y viceversa si 1 se lee como Falso . Estas dos operaciones definen un semianillo conmutativo , conocido como semianillo booleano .
2 puede verse basado 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 todas las asignaciones posibles de ceros y unos a cada variable (ver procedimiento de decisión ).
Ahora se pueden verificar las siguientes ecuaciones:
Cada uno de '+' y '∙' se distribuye sobre el otro:
Que '∙' se distribuya sobre '+' concuerda con el álgebra elemental , pero no con '+' sobre '∙'. Por esta y otras razones, una suma de productos (que conduce a una síntesis NAND ) se emplea más comúnmente 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:
Sólo 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 anotar 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, se obtiene 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). Hay muchas bases conocidas para todas las álgebras de Boole y, por tanto, para 2 . Una base elegante anotada usando sólo concatenación y barra superior es:
Donde concatenación = O, 1 = verdadero y 0 = falso, o concatenación = Y, 1 = falso y 0 = verdadero. (la barra superior es negación en ambos casos).
Si 0=1, (1)-(3) son los axiomas de un grupo abeliano .
(1) sólo sirve para demostrar que la concatenación conmuta y asocia. Primero suponga que (1) se asocia desde la izquierda o desde la derecha, luego pruebe la conmutatividad. Luego prueba la asociación desde la otra dirección. La asociatividad es simplemente una asociación de izquierda y derecha combinadas.
Esta base constituye un método sencillo para la prueba, llamado "cálculo" en Leyes de la forma , que procede simplificando expresiones a 0 o 1, invocando los axiomas (2) a (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 a lo que empezaste. 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 es válida para todas las álgebras de Boole. [1] Por el contrario, una identidad que se cumple para un álgebra booleana arbitraria y no trivial también se cumple en 2 . Por tanto, todas las identidades del álgebra booleana son 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 función exponencial del número de variables N que aparecen en la ecuación a verificar. La existencia de un procedimiento de decisión cuyos pasos sean una función polinómica de N cae bajo 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 sólo igualdades atómicas positivas. Como ejemplo, considere la fórmula ( x = 0) ∨ ( x = 1) . Esta fórmula siempre es cierta en un álgebra booleana de dos elementos. En un álgebra booleana de cuatro elementos cuyo dominio es el conjunto de potencias de , esta fórmula corresponde al enunciado ( x = ∅) ∨ ( x = {0,1}) y es falsa cuando x es . La decidibilidad de la teoría de primer orden de muchas clases de álgebras booleanas todavía se puede demostrar mediante la eliminación de cuantificadores o la propiedad del modelo pequeño (con el tamaño del dominio calculado en función de la fórmula y generalmente mayor que 2).
En los primeros años de la era de las computadoras se publicaron muchos textos elementales sobre álgebra booleana. Quizás el mejor de todos, y uno todavía impreso, sea:
Los siguientes elementos revelan cómo el álgebra booleana de dos elementos es matemáticamente no trivial.
