En matemáticas , un álgebra booleana residuada es una red residuada cuya estructura de red es la de un álgebra booleana . Los ejemplos incluyen álgebras booleanas con el monoide tomado como conjunción, el conjunto de todos los lenguajes formales sobre un alfabeto dado Σ bajo concatenación, el conjunto de todas las relaciones binarias en un conjunto X dado bajo composición relacional, y más generalmente el conjunto de potencias de cualquier equivalencia. relación, de nuevo bajo composición relacional. La aplicación original era relacionar álgebras como una generalización finitamente axiomatizada del ejemplo de relación binaria, pero existen ejemplos interesantes de álgebras booleanas residuadas que no son álgebras de relación, como el ejemplo del lenguaje.
Definición
Un álgebra booleana residual es una estructura algebraica ( L , ∧, ∨, ¬, 0, 1, •, I , \, /) tal que
- (i) ( L , ∧, ∨, •, I , \, /) es una celosía residual , y
- (ii) ( L , ∧, ∨, ¬, 0, 1) es un álgebra booleana.
Una firma equivalente más adecuada para la aplicación del álgebra de relaciones es ( L , ∧, ∨, ¬, 0, 1, •, I , ▷, ◁) donde las operaciones unarias x \ yx ▷ son intertraducibles a la manera de las leyes de De Morgan vía
- x \ y = ¬ ( x ▷ ¬ y ), x ▷ y = ¬ ( x \ ¬ y ),
y dualmente / y y ◁ y como
- x / y = ¬ (¬ x ◁ y ), x ◁ y = ¬ (¬ x / y ),
con los axiomas de residuación en el artículo de celosía residual reorganizados en consecuencia (reemplazando z por ¬ z ) para leer
- ( x ▷ z ) ∧ y = 0 ⇔ ( x • y ) ∧ z = 0 ⇔ ( z ◁ y ) ∧ x = 0
Esta reformulación dual de De Morgan está motivada y discutida con más detalle en la siguiente sección sobre conjugación.
Dado que las celosías residuales y las álgebras booleanas se pueden definir con un número finito de ecuaciones, también lo son las álgebras booleanas residuales, de donde forman una variedad finitamente axiomatizable .
Ejemplos de
- Cualquier álgebra booleana, con la multiplicación de monoide • tomada como conjunción y ambos residuales tomados como implicación material x → y . De las 15 operaciones booleanas binarias restantes que podrían considerarse en lugar de la conjunción para la multiplicación de monoide, solo cinco cumplen con el requisito de monotonicidad, a saber, 0, 1, x , y y x ∨ y . Estableciendo y = z = 0 en el axioma de residuación y ≤ x \ z ⇔ x • y ≤ z , tenemos 0 ≤ x \ 0 ⇔ x • 0 ≤ 0, que se falsifica tomando x = 1 cuando x • y = 1 , x , ox ∨ y . El argumento dual para z / y descarta x • y = y . Esto sólo hojas x • y = 0 (una operación binaria constante independiente de X y Y ), que satisface casi todos los axiomas cuando los residuos se toman tanto ser la constante operación x / y = x \ y = 1. El axioma se falla es x • I = x = I • x , a falta de un valor adecuado para que . Por tanto, la conjunción es la única operación booleana binaria que hace que la multiplicación monoide sea la de un álgebra booleana residuada.
- El conjunto de potencias 2 X 2 hizo un álgebra booleana como de costumbre con ∩, ∪ y complemento relativo a X 2 , y creó un monoide con composición relacional. La unidad monoide I es la relación de identidad {( x , x ) | x ∈ X }. El residual derecho R \ S está definido por x ( R \ S ) y si y solo si para todo z en X , zRx implica zSy . Dualmente, la S / R residual izquierda está definida por y ( S / R ) x si y solo si para todo z en X , xRz implica ySz .
- El conjunto de potencia 2 Σ * hizo un álgebra booleana como en el Ejemplo 2, pero con la concatenación del lenguaje para el monoide. Aquí, el conjunto Σ se usa como un alfabeto, mientras que Σ * denota el conjunto de todas las palabras finitas (incluidas las vacías) sobre ese alfabeto. La concatenación LM de las lenguas L y M se compone de todas las palabras UV tal que u ∈ L y V ∈ M . La unidad monoide es el lenguaje {ε} que consiste solo en la palabra vacía ε. El derecho residual M \ L consta de todas las palabras w sobre Σ tal que Mw ⊆ L . El L / M residual izquierdo es el mismo con wM en lugar de Mw .
Conjugado
Los duales de De Morgan ▷ y ◁ de residuación surgen de la siguiente manera. Entre las redes residuales, 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
- y ≤ x \ z ⇔ x • y ≤ z ⇔ x ≤ z / y
en la axiomatización de los dos residuos en términos de disjunción, a través de la equivalencia x ≤ y ⇔ x ∧¬ y = 0. Abreviando x ∧ y = 0 ax # y como la expresión de su disjunción, y sustituyendo ¬ z por z en los axiomas, se convierten con una pequeña manipulación booleana
- ¬ ( x \ ¬ z ) # y ⇔ x • y # z ⇔ ¬ (¬ z / y ) # x
Ahora ¬ ( x \ ¬ z ) es una reminiscencia de la dualidad de De Morgan , lo que sugiere que x \ debe pensarse 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 de derecha e izquierda, ya que esa distinción se hereda de la diferencia entre x • y • x , que tienen como sus respectivos conjugados x ▷ y ◁ x . (Pero esta ventaja se aplica también a los residuos cuando se toma x \ como la operación residual ax •).
Todo esto produce (junto con el álgebra booleana y los axiomas monoides) la siguiente axiomatización equivalente de un álgebra booleana residuada.
- y # x ▷ z ⇔ x • y # z ⇔ x # z ◁ y
Con esta firma, sigue siendo cierto que esta axiomatización puede expresarse como un número finito de ecuaciones.
Conversar
En los ejemplos 2 y 3 se puede demostrar que x ▷ I = I ◁ x . En el Ejemplo 2, ambos lados son iguales a la inversa 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 este último porque x ▷ I apenas retiene información sobre x . Por lo tanto, en el Ejemplo 2 podemos sustituir x ˘ por x en x ▷ I = x ˘ = I ◁ x y cancelar (profundamente) para dar
- x ˘ ▷ Yo = x = Yo ◁ x ˘.
x ˘˘ = x se puede demostrar a partir de estas dos ecuaciones. La noción de Tarski de un álgebra de relaciones se puede definir como un álgebra booleana residuada que tiene una operación x ˘ que satisface estas dos ecuaciones.
La etapa de cancelación en el anterior no es posible para el Ejemplo 3, que por lo tanto no es un álgebra de relación, x ˘ ser determinada únicamente como x ▷ I .
Las consecuencias de esta axiomatización del inverso incluyen x ˘˘ = x , ¬ ( x ˘) = (¬ x ) ˘, ( x ∨ y ) ˘ = x ˘ ∨ y ˘, y ( x • y ) ˘ = y ˘ • x ˘.
Referencias
- Bjarni Jónsson y Constantine Tsinakis, Álgebras de relaciones como álgebras booleanas residuales , Algebra Universalis, 30 (1993) 469-478.
- Peter Jipsen, Investigaciones asistidas por computadora de álgebras de relaciones , Ph.D. Tesis, Universidad de Vanderbilt, mayo de 1992.