stringtranslate.com

Álgebra booleana residual

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.

Definición

Un álgebra booleana residual es una estructura algebraica ( L , ∧, ∨, ¬, 0, 1, •, I , \, /) tal que

  1. ( L , ∧, ∨, •, I , \, /) es una red residual , y
  2. ( 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 \ y x ▷ son intertraducibles a la manera de las leyes de De Morgan a través de

x \ y = ¬( x ▷¬ y ),   xy = ¬( xy ),

y dualmente / y y ◁ y como

x / y = ¬(¬ xy ),   xy = ¬(¬ x / y ),

con los axiomas de residuación en el artículo de red residual reorganizado en consecuencia (reemplazando z por ¬ z ) para leer

( xz )∧ y = 0   ⇔   ( xy )∧ z = 0   ⇔   ( zy )∧ x = 0

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 .

Ejemplos

  1. Cualquier álgebra booleana, con la multiplicación monoide • tomada como conjunción y ambos residuos tomados como implicación material xy . De las 15 operaciones booleanas binarias restantes que podrían considerarse en lugar de la conjunción para la multiplicación monoide, solo cinco cumplen el requisito de monotonía, a saber, 0, 1, x , y y xy . Fijando y = z = 0 en el axioma de residuo yx \ z   ⇔   xyz , tenemos 0 ≤ x \0 ⇔   x •0 ≤ 0, lo cual se refuta al tomar x = 1 cuando xy = 1, x o xy . El argumento dual para z / y descarta xy = y . Esto sólo deja xy = 0 (una operación binaria constante independiente de x e y ), que satisface casi todos los axiomas cuando los residuos se toman como la operación constante x / y = x \ y = 1. El axioma que no cumple es xI = x = Ix , por falta de un valor adecuado para I . Por lo tanto, la conjunción es la única operación booleana binaria que hace que la multiplicación de monoides sea la de un álgebra booleana residual.
  2. El conjunto potencia 2 X 2 hizo un álgebra de Boole como es usual con ∩, ∪ y complemento relativo a X 2 , e hizo un monoide con composición relacional. La unidad monoide I es la relación identidad {( x , x )| xX }. El residuo derecho R \ S se define por x ( R \ S ) y si y solo si para todo z en X , zRx implica zSy . Dualmente el residuo izquierdo S / R se define por y ( S / R ) x si y solo si para todo z en X , xRz implica ySz .
  3. El conjunto potencia 2 Σ* hizo un álgebra booleana como en el Ejemplo 2, pero con concatenación de lenguajes para el monoide. Aquí el conjunto Σ se usa como un alfabeto mientras que Σ* denota el conjunto de todas las palabras finitas (incluyendo las vacías) sobre ese alfabeto. La concatenación LM de los lenguajes L y M consiste en todas las palabras uv tales que uL y vM . La unidad del monoide es el lenguaje {ε} que consiste solamente en la palabra vacía ε . El residuo derecho M \ L consiste en todas las palabras w sobre Σ tales que MwL . El residuo izquierdo L / M es el mismo con wM en lugar de Mw .

Conjugación

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.

yx \ z   ⇔   xyz   ⇔   xz / y

en la axiomatización de los dos residuos en términos de disyunción, a través de la equivalencia xyx ∧¬ y = 0. Abreviando xy = 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

¬( xz ) # y   ⇔   xy # z   ⇔ ¬(¬ z / y ) # x

Ahora bien, ¬( xz ) 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 ¬ fy ), análogo a ∀ x φ( x ) = ¬∃ x ¬φ( x ). Denotando esta operación dual como x ▷, definimos xz como ¬( xz ). De manera similar, definimos otra operación zy 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.

y # xz   ⇔   xy # z   ⇔   x # zy

Con esta firma se mantiene el caso de que esta axiomatización puede expresarse como un número finito de ecuaciones.

Conversar

En los ejemplos 2 y 3 se puede demostrar que xI = Ix . 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 xI retiene casi ninguna información sobre x . Por lo tanto, en el ejemplo 2 podemos sustituir x ˘ por x en xI = x ˘ = Ix y cancelar (correctamente) para obtener

x ˘▷ yo = x = yox ˘ .

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 xI .

Las consecuencias de esta axiomatización del recíproco incluyen x ˘˘ = x , ¬( x ˘) = (¬ x )˘, ( xy )˘ = x ˘ ∨ y ˘ , y ( xy )˘ = y ˘• x ˘.

Referencias