Definiciones de álgebras Booleanas

Question

Una definición que me parece de un álgebra de boole en el libro que estoy siguiendo (V. Manca, Logica matematica, 'matemática lógica') está determinado por las operaciones binarias $\land$ $\lor$ y el unario operación $\lnot$ sobre un conjunto tal que $$\varphi\land(\psi\land \chi)=(\varphi\land \psi)\land \chi,\quad \varphi\lor(\psi\lor \chi)=(\varphi\lor \psi)\lor \chi$$ $$\varphi\land \psi=\psi\land \varphi,\quad \varphi\lor \psi=\psi\lor \varphi$$ $$\varphi\lor (\psi\land \chi) = (\varphi\lor \psi) \land (\varphi \lor \chi) ,\quad \varphi \land (\psi\lor \chi) = (\varphi \land \psi) \lor (\varphi \land \chi) $$ $$\varphi \lor (\varphi \land \psi) = \varphi,\quad \varphi\land (\varphi\lor \psi) = \varphi$$ $$\varphi\land 0 =0,\quad \varphi\lor1=1$$ $$\varphi\lor\lnot \varphi=0,\quad \varphi\land\lnot \varphi=1$$

Otra definición que me encuentre en el mismo texto, es que un álgebra de boole es un complementado celosía distributivo, es decir, un entramado donde un máximo $1$ y un mínimo de $0$ existe y tal que para todos sus elementos, $x$ hay un elemento $x'$ tal que$$\inf(\{x,x'\})=0\text{ and }\sup(\{x,x'\})=1$$ and where the $\inf$ and the $\sup$ operaciones son distributiva con respecto a cada uno de los otros.

Me pregunto si cualquier álgebra de boole de acuerdo a una de las dos definiciones es "isomorfo" de alguna manera a un álgebra Booleana de acuerdo a la primera definición, y creo que he sido capaz de probar que un orden parcial puede ser definido en un álgebra de boole dejando $\varphi\le\psi\equiv\varphi\lor\psi=\psi$. Por otra parte, creo que he sido para demostrar que, por dejar que $x\land y:=\inf(\{x,y\})$, $x\lor y:=\sup(\{x,y\})$ y $\lnot x:=x'$ un complementado distributiva de la celosía es un álgebra de boole en la primera definición.

Hay una cosa que falta para demostrar que las dos definiciones son equivalentes: ¿cómo podemos ver que $\varphi\land\psi$ es la mayor cota inferior de a $\{\varphi,\psi\}$ y $\varphi\lor\psi$ es la menor cota superior de a $\{\varphi,\psi\}$? Muchas gracias por cualquier respuesta!!!

---

*He encontrado todos los axiomas muy fácilmente demostrado ser satisfecho por un complementado distributiva de celosía, a excepción de$$\inf(\{\inf(\{x,y\}),z\})=\inf(\{x,\inf(\{y,z\})\})\text{ and }\sup(\{\sup(\{x,y\}),z\})=\sup(\{x,\sup(\{y,z\})\})$$, pero creo que el siguiente lo demuestra.

Clearly$$\inf(\{\inf(\{x,y\}),z\})\le x,y,z\text{ and }\inf(\{x,\inf(\{y,z\})\})\le x,y,z.$$Therefore $\inf(\{\inf(\{x,y\}),z\})$ is a lower bound of $\{y,z\}$ and $\inf(\{\inf(\{x,y\}),z\})\le\inf(\{y,z\})$, by definition of $\inf$, which is the greatest lower bound, and, then, $\inf(\{\inf(\{x,y\}),z\})$, which is not greater than $z$, is a lower bound of $\{x,\inf(\{y,z\})\}$: we have that $\inf(\{\inf(\{x,y\}),z\})\le\inf(\{x,\inf(\{y,z\})\})$. Pero $\inf(\{x,\inf(\{y,z\})\})$ es un límite inferior de $\{x,y\}$$\inf(\{x,\inf(\{y,z\})\})\le\inf(\{x,y\})$, y por lo tanto, desde el $\inf(\{x,\inf(\{y,z\})\})\le z$,$\inf(\{x,\inf(\{y,z\})\})\le\inf(\{\inf(\{x,y\}),z\})$. Repitiendo el mismo razonamiento con $\sup$, $\ge$, superior y pequeño-er/-est sustituyendo $\inf$, $\le$, menor y mayor/-est demuestra que $\sup(\{\sup(\{x,y\}),z\})=\sup(\{x,\sup(\{y,z\})\})$.

Answer 1

Si usted tiene un entramado, que es un conjunto parcialmente ordenado $L,\le$ donde cada dos elemento tiene un mayor límite inferior y un mínimo de límite superior, se pueden definir las operaciones de $\land$ $\lor$ por $$ un\de la tierra b=\inf\nolimits_\le\{a,b\},\qquad\lor b=\sup\nolimits_\le\{a,b\} $$ Estas operaciones satisfacen las siguientes propiedades

1. Idempotencia: $a\land a=a$, $a\lor a=a$
2. La absorción de: $a\land(a\lor b)=a$, $a\lor(a\land b)=a$
3. Conmutatividad: $a\land b=b\land a$, $a\lor b=b\lor a$
4. La asociatividad: $a\land(b\land c)=(a\land b)\land c$, $a\lor(b\lor c)=(a\lor b)\lor c$

Estas propiedades son fácilmente demostrado por el hecho de que $\le$ es una relación de orden parcial.

Por el contrario, supongamos que usted tiene dos operaciones de $\land$ $\lor$ en el conjunto de $L$ que satisfacen las propiedades antes mencionadas. Definir $$ un\le b \quad\text{significa}\quad\de la tierra b=a $$ A continuación, puede probar

1. $a\le a$ todos los $a\in L$
2. Si $a\le b$ $b\le a$ $a=b$
3. Si $a\le b$$b\le c$, $a\le c$

El primero sigue de idempotencia, el segundo de la conmutatividad, la tercera de la asociatividad. Por lo tanto $\le$ es un orden parcial en $L$.

Por otra parte $a\land b=\inf_\le\{a,b\}$. De hecho, $$ un\de la tierra b\le un $$ debido a $(a\land b)\land a=a\land(a\land b)=(a\land a)\land b=a\land b$. Si $c\le a$$c\le b$, luego $$ c\la tierra(a\de la tierra b)=(c\la tierra a)\de la tierra b=c\de la tierra b=c $$ por lo $c\le a\land b$ y que han demostrado ser $a\land b$ es la mayor cota inferior de a $\{a,b\}$.

Por simetría, si definimos $a\le'b$ a de pie para $a\lor b=b$, podemos demostrar que $\le'$ es un orden parcial en $L$$a\lor b=\sup_{\le'}\{a,b\}$.

No hicimos uso de la absorción todavía. Es demostrado por demostrar que el $a\le b$ si y sólo si $a\le' b$.

Supongamos $a\le b$$a\land b=a$. Entonces $$ un\lor b=(a\de la tierra b)\lor b=b\lor(a\de la tierra b)=b\lor(b\de la tierra a)=b $$ y por lo $a\le' b$. Por el contrario, supongamos $a\le'b$$a\lor b=b$. Entonces $$ un\de la tierra b=a\de la tierra(a\lor b)=a $$ por lo $a\le b$.

Ya que cada dos elemento del conjunto tiene al menos un límite superior con respecto a $\le'$ y un mayor límite inferior con respecto a $\le$, pero las dos relaciones son los mismos, tenemos que $L,\le$ es una celosía.

Ahora agregue el máximo, el mínimo, la distributividad y complementa y tiene un álgebra Booleana.

Answer 2

Creo que he sido capaz de demostrar la equivalencia. Veo que $\varphi\lor\psi=\psi\iff \varphi\land\psi=\varphi$.

Por lo tanto, con el fin de mostrar que el $\varphi\land\psi$ es la mayor cota inferior, podemos ver que, si $\varphi\land\psi\le\chi\le\varphi$$\varphi\land\psi\le\chi\le\varphi$,$\chi=\chi\lor(\varphi\land\psi)=(\chi\lor\varphi)\land(\chi\lor\psi)=\varphi\land\psi$.

Con el fin de mostrar que el $\varphi\land\psi$ es la menor cota superior, podemos ver que, si $\varphi\lor\psi\ge\chi\ge\varphi$$\varphi\lor\psi\ge\chi\ge\varphi$,$\chi=\chi\land(\varphi\lor\psi)=(\chi\land\varphi)\lor(\chi\land\psi)=\varphi\lor\psi$.