En matemáticas , un álgebra de Boole residual es un retículo residual cuya estructura reticular es la de un álgebra de Boole . Algunos ejemplos son las álgebras de Boole en las que el monoide se toma como conjunción, el conjunto de todos los lenguajes formales sobre un alfabeto dado Σ bajo concatenación, el conjunto de todas las relaciones binarias sobre un conjunto dado X bajo composición relacional y, de manera más general, el conjunto de potencias de cualquier relación de equivalencia, nuevamente bajo composición relacional. La aplicación original fue para las álgebras de relación como una generalización finitamente axiomatizada del ejemplo de la relación binaria, pero existen ejemplos interesantes de álgebras de Boole residuales que no son álgebras de relación, como el ejemplo del lenguaje.
Un álgebra booleana residual es una estructura algebraica ( L , ∧, ∨, ¬, 0, 1, •, I , \, /) tal que
Una firma equivalente más adecuada para la aplicación del álgebra de relaciones es ( L , ∧, ∨, ¬, 0, 1, •, I , ▷, ◁) donde las operaciones unarias x \ y x ▷ son intertraducibles a la manera de las leyes de De Morgan a través de
y dualmente / y y ◁ y como
con los axiomas de residuación en el artículo de red residual reorganizado en consecuencia (reemplazando z por ¬ z ) para leer
Esta reformulación dual de De Morgan está motivada y analizada con más detalle en la sección siguiente sobre conjugación.
Dado que las redes residuales y las álgebras de Boole se pueden definir con un número finito de ecuaciones, también lo son las álgebras de Boole, por lo que forman una variedad axiomatizable finitamente .
Los duales de De Morgan ▷ y ◁ de residuación surgen de la siguiente manera. Entre los retículos de residuos, las álgebras de Boole son especiales en virtud de tener una operación de complementación ¬. Esto permite una expresión alternativa de las tres desigualdades.
en la axiomatización de los dos residuos en términos de disyunción, a través de la equivalencia x ≤ y ⇔ x ∧¬ y = 0. Abreviando x ∧ y = 0 a x # y como expresión de su disyunción, y sustituyendo ¬ z por z en los axiomas, se convierten con un poco de manipulación booleana
Ahora bien, ¬( x \¬ z ) recuerda a la dualidad de De Morgan , lo que sugiere que x \ puede considerarse como una operación unaria f , definida por f (y) = x \ y , que tiene un dual de De Morgan ¬ f (¬ y ), análogo a ∀ x φ( x ) = ¬∃ x ¬φ( x ). Denotando esta operación dual como x ▷, definimos x ▷ z como ¬( x \¬ z ). De manera similar, definimos otra operación z ◁ y como ¬(¬ z / y ). Por analogía con x \ como la operación residual asociada con la operación x •, nos referimos a x ▷ como la operación conjugada, o simplemente conjugada , de x •. Asimismo, ◁ y es el conjugado de • y . A diferencia de los residuos, la conjugación es una relación de equivalencia entre operaciones: si f es el conjugado de g entonces g es también el conjugado de f , es decir, el conjugado del conjugado de f es f . Otra ventaja de la conjugación es que se hace innecesario hablar de conjugados derechos e izquierdos, distinción que ahora se hereda de la diferencia entre x • y • x , que tienen como conjugados respectivos x ▷ y ◁ x . (Pero esta ventaja se aplica también a los residuos cuando x \ se toma como la operación residual de x •.)
Todo esto produce (junto con el álgebra de Boole y los axiomas monoides) la siguiente axiomatización equivalente de un álgebra de Boole residual.
Con esta firma se mantiene el caso de que esta axiomatización puede expresarse como un número finito de ecuaciones.
En los ejemplos 2 y 3 se puede demostrar que x ▷ I = I ◁ x . En el ejemplo 2 ambos lados son iguales al inverso x ˘ de x , mientras que en el ejemplo 3, ambos lados son I cuando x contiene la palabra vacía y 0 en caso contrario. En el primer caso x ˘ = x . Esto es imposible para el segundo porque x ▷ I retiene casi ninguna información sobre x . Por lo tanto, en el ejemplo 2 podemos sustituir x ˘ por x en x ▷ I = x ˘ = I ◁ x y cancelar (correctamente) para obtener
x ˘˘ = x se puede demostrar a partir de estas dos ecuaciones. La noción de Tarski de un álgebra relacional se puede definir como un álgebra booleana residual que tiene una operación x ˘ que satisface estas dos ecuaciones.
El paso de cancelación mencionado anteriormente no es posible para el Ejemplo 3, que por lo tanto no es un álgebra de relaciones, ya que x ˘ se determina de forma única como x ▷ I .
Las consecuencias de esta axiomatización del recíproco incluyen x ˘˘ = x , ¬( x ˘) = (¬ x )˘, ( x ∨ y )˘ = x ˘ ∨ y ˘ , y ( x • y )˘ = y ˘• x ˘.