Álgebra booleana residual

En matemáticas , un álgebra booleana residuada es un retículo residuado cuya estructura reticular es la de un álgebra booleana . Algunos ejemplos incluyen álgebras booleanas con el monoide considerado como conjunción, y el conjunto de todos los lenguajes formales sobre un alfabeto dado.${\displaystyle \Sigma }$bajo concatenación, el conjunto de todas las relaciones binarias en un conjunto dado${\displaystyle X}$bajo composición relacional, y más generalmente el conjunto potencia de cualquier relación de equivalencia , también bajo composición relacional. La aplicación original fue a las álgebras de relaciones como una generalización finitamente axiomatizada del ejemplo de la relación binaria, pero existen ejemplos interesantes de álgebras booleanas residuadas que no son álgebras de relaciones, como el ejemplo del lenguaje.

Un álgebra booleana residuada es una estructura algebraica.${\displaystyle (L,\wedge ,\vee ,\neg ,0,1,\bullet ,\mathbf {I} ,/,\backslash )}$de tal manera que

Una firma equivalente más adecuada para la aplicación del álgebra de relaciones es${\displaystyle (L,\wedge ,\vee ,\neg ,0,1,\bullet ,\mathbf {I} ,\triangleright ,\triangleleft )}$donde las operaciones unarias${\displaystyle x\backslash }$y${\displaystyle x\triangleright }$son intertraducibles a la manera de las leyes de De Morgan a través de

${\displaystyle x\backslash y=\neg (x\triangleright \neg y)}$, ${\displaystyle x\triangleright y=\neg (x\backslash \neg y)}$,

y de forma dual${\displaystyle /y}$y${\displaystyle \triangleleft y}$como

${\displaystyle x/y=\neg (\neg x\triangleleft y)}$, ${\displaystyle x\triangleleft y=\neg (\neg x/y)}$,

con los axiomas de residuación en el artículo de retículo residuado reorganizados en consecuencia (reemplazando${\displaystyle z}$por${\displaystyle \neg z}$) para leer

${\displaystyle (x\triangleright z)\wedge y=0\ \Leftrightarrow \ (x\bullet y)\wedge z=0\ \Leftrightarrow \ (z\triangleleft y)\wedge x=0}$

Esta reformulación dual de De Morgan se justifica y se analiza con más detalle en la sección siguiente sobre conjugación.

Dado que las retículas residuadas y las álgebras booleanas se pueden definir con un número finito de ecuaciones, también lo son las álgebras booleanas residuadas, por lo que forman una variedad finitamente axiomatizable .

1. Cualquier álgebra booleana, con la multiplicación de monoides${\displaystyle \bullet }$considerado como conjunción y ambos residuos considerados como implicación material${\displaystyle x\to y}$De las 15 operaciones booleanas binarias restantes que podrían considerarse en lugar de la conjunción para la multiplicación del monoide, solo cinco cumplen el requisito de monotonicidad, a saber:${\displaystyle 0,1,x,y}$y${\displaystyle x\vee y}$. Configuración${\displaystyle y=z=0}$en el axioma de residuación${\displaystyle y\leq x\backslash z\ \Leftrightarrow \ x\bullet y\leq z}$, tenemos${\displaystyle 0\leq x\backslash 0\ \Leftrightarrow \ x\bullet 0\leq 0}$, que se falsifica tomando${\displaystyle x=1}$cuando${\displaystyle x\bullet y=1}$,${\displaystyle x}$, o${\displaystyle x\vee y}$. El argumento dual para${\displaystyle z/y}$descarta${\displaystyle x\bullet y=y}$Esto simplemente deja${\displaystyle x\bullet y=0}$(una operación binaria constante independiente de${\displaystyle x}$y${\displaystyle y}$), lo cual satisface casi todos los axiomas cuando se considera que los residuos son la operación constante.${\displaystyle x/y=x\backslash y=1}$El axioma que no cumple es${\displaystyle x\bullet \mathbf {I} =x=\mathbf {I} \bullet x}$, por falta de un valor adecuado para${\displaystyle \mathbf {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 residuada.
2. El conjunto de potencia${\displaystyle 2^{X^{2}}}$hice un álgebra booleana como de costumbre con${\displaystyle \cap }$,${\displaystyle \cup }$y complemento relativo a${\displaystyle X^{2}}$y creó un monoide con composición relacional. La unidad monoide${\displaystyle \mathbf {I} }$es la relación de identidad${\displaystyle \{(x,x)|x\in X\}}$El residuo derecho${\displaystyle R\backslash S}$se define por${\displaystyle x(R\backslash S)y\ \Leftrightarrow \ \forall z\in X,zRx\Rightarrow zSy}$. De manera dual, el residuo izquierdo${\displaystyle S/R}$se define por${\displaystyle y(S/R)x\ \Leftrightarrow \ \forall z\in X,xRz\Rightarrow ySz}$.
3. El conjunto de potencia${\displaystyle 2^{\Sigma ^{*}}}$Se creó un álgebra booleana como en el Ejemplo 2, pero con concatenación de lenguaje para el monoide. Aquí el conjunto${\displaystyle \Sigma }$se utiliza como alfabeto mientras${\displaystyle \Sigma ^{*}}$denota el conjunto de todas las palabras finitas (incluidas las vacías) sobre ese alfabeto. La concatenación${\displaystyle LM}$de lenguas${\displaystyle L}$y${\displaystyle M}$consta de todas las palabras${\displaystyle uv}$de tal manera que${\displaystyle u\in L}$y${\displaystyle v\in M}$La unidad monoide es el lenguaje${\displaystyle \{\varepsilon \}}$que consiste únicamente en la palabra vacía${\displaystyle \varepsilon }$El residuo derecho${\displaystyle M\backslash L}$consta de todas las palabras${\displaystyle w}$encima${\displaystyle \Sigma }$de tal manera que${\displaystyle Mw\subseteq L}$El residuo izquierdo${\displaystyle L/M}$es lo mismo con${\displaystyle wM}$en lugar de${\displaystyle Mw}$.

Los duelos de De Morgan${\displaystyle \triangleright }$y${\displaystyle \triangleleft }$Las residuaciones surgen de la siguiente manera. Entre los retículos residuados, las álgebras booleanas son especiales en virtud de tener una operación de complementación.${\displaystyle \neg }$Esto permite una expresión alternativa de las tres desigualdades.

${\displaystyle y\leq x\backslash z\ \Leftrightarrow \ x\bullet y\leq z\ \Leftrightarrow \ x\leq z/y}$

en la axiomatización de los dos residuos en términos de disyunción, a través de la equivalencia${\displaystyle x\leq y\ \Leftrightarrow \ x\wedge \neg y=0}$Abreviación${\displaystyle x\wedge y=0}$a${\displaystyle x\#y}$como expresión de su disyunción, y sustituyendo${\displaystyle \neg z}$para${\displaystyle z}$En los axiomas, se convierten en con un poco de manipulación booleana.

${\displaystyle \neg (x\backslash \neg z)\#y\ \Leftrightarrow \ x\bullet y\#z\ \Leftrightarrow \ \neg (\neg z/y)\#x}$

Ahora${\displaystyle \neg (x\backslash \neg z)}$recuerda a la dualidad de De Morgan , lo que sugiere que${\displaystyle x\backslash }$ser considerado como una operación unaria${\displaystyle f}$, definido por${\displaystyle f(y)=x\backslash y}$, que tiene un De Morgan doble${\displaystyle \neg f(\neg y)}$, análogo a${\displaystyle \forall x\phi (x)=\neg \exists x\neg \phi (x)}$. Denotando esta operación dual como${\displaystyle x\triangleright }$, definimos${\displaystyle x\triangleright z}$como${\displaystyle \neg x\backslash \neg z}$. De manera similar definimos otra operación${\displaystyle z\triangleleft y}$como${\displaystyle \neg (\neg z/y)}$Por analogía con${\displaystyle x\backslash }$como la operación residual asociada con la operación${\displaystyle x\bullet }$, nos referimos a${\displaystyle x\triangleright }$como la operación conjugada, o simplemente conjugado , de${\displaystyle x\bullet }$. Asimismo${\displaystyle \triangleleft y}$es el conjugado de${\displaystyle \bullet y}$. A diferencia de los residuos, la conjugación es una relación de equivalencia entre operaciones: si${\displaystyle f}$es el conjugado de${\displaystyle g}$entonces${\displaystyle g}$es también el conjugado de${\displaystyle f}$, es decir, el conjugado del conjugado de${\displaystyle f}$es${\displaystyle f}$. Otra ventaja de la conjugación es que se vuelve innecesario hablar de conjugados derechos e izquierdos, ya que esa distinción ahora se hereda de la diferencia entre${\displaystyle x\bullet }$y${\displaystyle \bullet x}$, que tienen como sus respectivos conjugados${\displaystyle x\triangleright }$y${\displaystyle \triangleleft x}$. (Pero esta ventaja también se aplica a los residuos cuando${\displaystyle x\backslash }$se considera que es la operación residual${\displaystyle x\bullet }$.)

Todo esto produce (junto con el álgebra booleana y los axiomas de monoide) la siguiente axiomatización equivalente de un álgebra booleana residuada.

${\displaystyle y\#x\triangleright z\ \Leftrightarrow \ x\bullet y\#z\ \Leftrightarrow \ x\#z\triangleleft y}$

Con esta firma, sigue siendo cierto que esta axiomatización puede expresarse como un número finito de ecuaciones.

En los ejemplos 2 y 3 se puede demostrar que${\displaystyle x\triangleright \mathbf {I} =\mathbf {I} \triangleleft x}$En el Ejemplo 2, ambos lados son iguales al recíproco .${\displaystyle x{\breve {}}}$de${\displaystyle x}$, mientras que en el Ejemplo 3, ambos lados son${\displaystyle \mathbf {I} }$cuando${\displaystyle x}$contiene la palabra vacía y${\displaystyle 0}$de lo contrario. En el primer caso${\displaystyle x{\breve {}}=x}$Esto es imposible para este último porque${\displaystyle x\triangleright \mathbf {I} }$apenas conserva información sobre${\displaystyle x}$Por lo tanto, en el Ejemplo 2 podemos sustituir${\displaystyle x{\breve {}}}$para${\displaystyle x}$en${\displaystyle x\triangleright \mathbf {I} =x{\breve {}}=\mathbf {I} \triangleleft x}$y cancelar (sonoramente) para dar

${\displaystyle x{\breve {}}\triangleright \mathbf {I} =x=\mathbf {I} \triangleleft x{\breve {}}}$.

${\displaystyle x{\breve {}}{\breve {}}=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${\displaystyle x{\breve {}}}$satisfaciendo estas dos ecuaciones.

El paso de cancelación en lo anterior no es posible para el Ejemplo 3, que por lo tanto no es un álgebra de relaciones,${\displaystyle x{\breve {}}}$estar determinado de forma única como${\displaystyle x\triangleright \mathbf {I} }$.

Las consecuencias de esta axiomatización de lo recíproco incluyen:${\displaystyle x{\breve {}}{\breve {}}=x}$,${\displaystyle \neg (x{\breve {}})=(\neg x){\breve {}}}$,${\displaystyle (x\vee y){\breve {}}=x{\breve {}}\vee y{\breve {}}}$, y${\displaystyle (x\bullet y){\breve {}}=y{\breve {}}\bullet x{\breve {}}}$.

• Bjarni Jónsson y Constantine Tsinakis, Álgebras de relaciones como álgebras booleanas residuadas , Algebra Universalis, 30 (1993) 469-478.
• Peter Jipsen, Investigaciones asistidas por ordenador de álgebras de relaciones , Tesis doctoral, Universidad de Vanderbilt, mayo de 1992.