Álgebra booleana de dos elementos

En matemáticas y álgebra abstracta , el álgebra booleana de dos elementos es aquella cuyo conjunto subyacente (o universo o portador ) B es el dominio booleano . Por convención, los elementos del dominio booleano son 1 y 0, de modo que B = {0, 1}. El nombre que Paul Halmos le dio a esta álgebra, " 2 ", tiene cierta aceptación en la literatura y 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 ⁿ a B . El álgebra booleana consta de dos operaciones binarias y complementación unaria . Las operaciones binarias se han nombrado y notado de diversas maneras. Aquí se denominan 'suma' y 'producto', y se notan mediante los infijos '+' y '∙', respectivamente. La suma y el producto conmutan y se asocian , como en el álgebra usual de los números reales . En cuanto al orden de las operaciones , los paréntesis 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${\displaystyle \langle B,+,}$∙${\displaystyle ,{\overline {..}},1,0\rangle }$álgebra de tipo${\displaystyle \langle 2,2,1,0,0\rangle }$.

La correspondencia biunívoca entre {0,1} y { Verdadero , Falso } da como resultado la lógica bivalente clásica en forma de ecuación, donde la complementación 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 considerarse basado en la siguiente aritmética "booleana" trivial:

${\displaystyle {\begin{aligned}&1+1=1+0=0+1=1\\&0+0=0\\&0\cdot 0=0\cdot 1=1\cdot 0=0\\&1\cdot 1=1\\&{\overline {1}}=0\\&{\overline {0}}=1\end{aligned}}}$

Tenga en cuenta que:

• Los símbolos '+' y '∙' funcionan exactamente igual que en la aritmética numérica, excepto que 1+1=1. '+' y '∙' se derivan por analogía de la aritmética numérica; simplemente se asigna el valor 1 a cualquier número distinto de cero.
• Intercambiar 0 y 1, y '+' y '∙' preserva la verdad; esta es la esencia de la dualidad que impregna todas las álgebras booleanas.

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 (ver procedimiento de decisión ).

Ahora se pueden verificar las siguientes ecuaciones:

${\displaystyle {\begin{aligned}&A+A=A\\&A\cdot A=A\\&A+0=A\\&A+1=1\\&A\cdot 0=0\\&{\overline {\overline {A}}}=A\end{aligned}}}$

Cada uno de los símbolos '+' y '∙' se distribuye sobre el otro:

• ${\displaystyle \ A\cdot (B+C)=A\cdot B+A\cdot C;}$
• ${\displaystyle \ A+(B\cdot C)=(A+B)\cdot (A+C).}$

Que el símbolo '∙' se distribuya sobre el símbolo '+' concuerda con el álgebra elemental , pero no así el símbolo '+' sobre el símbolo '∙'. Por esta y otras razones, se suele emplear más una suma de productos (que da lugar a una síntesis NAND ) que un producto de sumas (que da lugar a una síntesis NOR ).

Cada uno de los símbolos '+' y '∙' se puede definir en términos del otro y de su complementación:

• ${\displaystyle A\cdot B={\overline {{\overline {A}}+{\overline {B}}}}}$
• ${\displaystyle A+B={\overline {{\overline {A}}\cdot {\overline {B}}}}.}$

Solo necesitamos una operación binaria, y la concatenación basta para denotarla. Por lo tanto, la concatenación y la barra superior bastan 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 , a partir de las cuales se pueden derivar todas las ecuaciones anteriores (y más). Existen muchas bases conocidas para todas las álgebras booleanas y, por lo tanto, para 2. Una base elegante, notada utilizando únicamente concatenación y barra superior, es:

1. ${\displaystyle \ ABC=BCA}$(Concatenación de desplazamientos, asociaciones)
2. ${\displaystyle {\overline {A}}A=1}$( 2 es un retículo complementado , con un límite superior de 1)
3. ${\displaystyle \ A0=A}$(0 es el límite inferior ).
4. ${\displaystyle A{\overline {AB}}=A{\overline {B}}}$( 2 es una red distributiva )

Donde la concatenación equivale a OR, 1 = verdadero y 0 = falso, o bien la concatenación equivale a AND, 1 = falso y 0 = verdadero. (La barra superior indica negación en ambos casos).

Si 0=1, (1)–(3) son los axiomas para un grupo abeliano .

(1) solo sirve para demostrar que la concatenación conmuta y asocia. Primero, supongamos que (1) asocia desde la izquierda o desde la derecha, luego demostremos la conmutatividad. Después, 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 sencillo para la demostración, llamado "cálculo" en las Leyes de la Forma , que procede simplificando expresiones a 0 o 1, invocando los axiomas (2)–(4) y las identidades elementales.${\displaystyle AA=A,{\overline {\overline {A}}}=A,1+A=1}$y la ley distributiva.

El teorema de De Morgan establece que si se realiza lo siguiente, en el orden dado, a cualquier función booleana :

• Complementa cada variable;
• Intercambia los operadores '+' y '∙' (teniendo cuidado de añadir paréntesis para asegurar que el orden de las operaciones se mantenga igual);
• Complementar el resultado,

El resultado es lógicamente equivalente al punto de partida. La aplicación repetida del teorema de De Morgan a partes de una función puede utilizarse 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 booleanas. ^{[ 1 ]} Recíprocamente, una identidad que se cumple para un álgebra booleana no trivial arbitraria también se cumple en 2 . Por lo tanto, todas las identidades del álgebra booleana 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 sean una función polinómica de N se encuentra 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 solo igualdades positivas atómicas. Como ejemplo, consideremos la fórmula ( x = 0) ∨ ( x = 1) . Esta fórmula siempre es verdadera en un álgebra booleana de dos elementos. En un álgebra booleana de cuatro elementos cuyo dominio es el conjunto potencia de ⁠${\displaystyle \{0,1\}}$⁠ , esta fórmula corresponde a la afirmación ( x = ∅) ∨ ( x = {0,1}) y es falsa cuando x es ⁠${\displaystyle \{1\}}$⁠ . La decidibilidad para la teoría de primer orden de muchas clases de álgebras booleanas aún puede demostrarse, utilizando la eliminación de cuantificadores o la propiedad de modelo pequeño (con el tamaño del dominio calculado como una función de la fórmula y generalmente mayor que 2).

• Álgebra booleana
• Conjunto acotado
• Red (orden)
• teoría del orden

En los primeros años de la era informática se publicaron muchos textos elementales sobre álgebra booleana. Quizás el mejor de todos, y uno que aún se imprime, es:

• Mendelson, Elliot, 1970. Esquema de álgebra booleana de Schaum . McGraw - Hill.

Los siguientes puntos revelan por qué el álgebra booleana de dos elementos no es matemáticamente trivial.

• Enciclopedia de Filosofía de Stanford : " Las matemáticas del álgebra booleana ", por J. Donald Monk.
• Burris, Stanley N., y HP Sankappanavar, HP, 1981. Un curso de álgebra universal. Springer-Verlag. ISBN 3-540-90578-2.