5.6 Algebras de Boole

Un reticulado terna \((L,\mathsf{s},\mathsf{i})\) se llamara distributivo cuando cumpla la siguiente identidad

  1. adhocprefixDis\(_{1}\)adhocsufix \(x\mathsf{\;i\;}(y\;\mathsf{s}\;z)=(x\mathsf{\;i\;}y)\;\mathsf{s}\;(x\mathsf{\;i\;}z)\), cualesquiera sean \(x,y,z\in L\)

Diremos que un reticulado acotado \((L,\mathsf{s},\mathsf{i},0,1)\) (resp. complementado \((L,\mathsf{s},\mathsf{i},^{c},0,1)\)) es distributivo cuando \((L,\mathsf{s},\mathsf{i})\) lo sea. Consideremos la distributividad dual a Dis\(_{1}\), es decir

  1. adhocprefixDis\(_{2}\)adhocsufix \(x\;\mathsf{s}\;(y\mathsf{\;i\;}z)=(x\mathsf{\;s\;}y)\mathsf{\;i\;}(x\;\mathsf{s}\;z)\), cualesquiera sean \(x,y,z\in L\)

5.24. Sea \((L,\mathsf{s},\mathsf{i})\) un reticulado terna. Entonces \((L,\mathsf{s},\mathsf{i})\) satisface Dis\(_{1}\) sii \((L,\mathsf{s},\mathsf{i})\) satisface Dis\(_{2}\)

Proof. Supongamos \((L,\mathsf{s},\mathsf{i})\) satisface Dis\(_{1}\). Sean \(a,b,c\in L\) elementos fijos. Por Dis\(_{1}\) tenemos que \[(a\mathsf{\;s\;}b)\mathsf{\;i\;}(a\;\mathsf{s}\;c)=((a\mathsf{\;s\;}b)\mathsf{\;i\;}a)\;\mathsf{s}\;((a\mathsf{\;s\;}b)\mathsf{\;i\;}c)\] Pero por conmutatividad tenemos que \[((a\mathsf{\;s\;}b)\mathsf{\;i\;}a)\;\mathsf{s}\;((a\mathsf{\;s\;}b)\mathsf{\;i\;}c)=(a\mathsf{\;i\;}(a\mathsf{\;s\;}b))\;\mathsf{s}\;(c\mathsf{\;i\;}(a\mathsf{\;s\;}b))\] Por (I7) tenemos que \(a\mathsf{\;i\;}(a\mathsf{\;s\;}b)=a\) y por \(Dis_{1}\) tenemos que \(c\mathsf{\;i\;}(a\mathsf{\;s\;}b)=(c\mathsf{\;i\;}a)\mathsf{\;s\;}(c\mathsf{\;i\;}b)\) por lo cual \[(a\mathsf{\;i\;}(a\mathsf{\;s\;}b))\;\mathsf{s}\;(c\mathsf{\;i\;}(a\mathsf{\;s\;}b))=a\;\mathsf{s}\;((c\mathsf{\;i\;}a)\mathsf{\;s\;}(c\mathsf{\;i\;}b))\] Por asociatividad tenemos que \[a\;\mathsf{s}\;((c\mathsf{\;i\;}a)\mathsf{\;s\;}(c\mathsf{\;i\;}b))=(a\;\mathsf{s}\;(c\mathsf{\;i\;}a))\mathsf{\;s\;}(c\mathsf{\;i\;}b)\] Pero por conmutatividad tenemos que \[(a\;\mathsf{s}\;(c\mathsf{\;i\;}a))\mathsf{\;s\;}(c\mathsf{\;i\;}b)=(a\;\mathsf{s}\;(a\mathsf{\;i\;}c))\mathsf{\;s\;}(b\mathsf{\;i\;}c)\] Lo cual por (I6) nos dice que \[(a\;\mathsf{s}\;(a\mathsf{\;i\;}c))\mathsf{\;s\;}(b\mathsf{\;i\;}c)=a\mathsf{\;s\;}(b\mathsf{\;i\;}c)\] Por transitividad de la igualdad, las igualdades anteriores nos dicen que \[a\mathsf{\;s\;}(b\mathsf{\;i\;}c)=(a\mathsf{\;s\;}b)\mathsf{\;i\;}(a\;\mathsf{s}\;c)\] Pero \(a,b,c\) eran elementos arbitrarios por lo que hemos probado que vale \(Dis_{2}\).  


  1. adhocprefixEjercicio:adhocsufix Use la prueba del lema anterior para hacer un algoritmo el cual tome de entrada un reticulado acotado \((L,\mathsf{s},\mathsf{i},0,1)\) y elementos \(x,y,z\in L\) tales que \(y\neq z\) son complementos de \(x\), y de como salida elementos \(a,b,c\) tales que \(a\mathsf{\;i\;}(b\;\mathsf{s}\;c)\neq(a\mathsf{\;i\;}b)\;\mathsf{s}\;(a\mathsf{\;i\;}c)\)

Por un Algebra de Boole entenderemos un reticulado complementado que es distributivo. Algunos ejemplos:

  1. adhocprefixE1adhocsufix Dado un conjunto no vacio \(X\), la \(6\)-upla \((X,\cup,\cap,^{c},\emptyset,X)\) es un algebra de Boole

Para probar algunas propiedades fundamentales de un algebra de Boole necesitaremos el siguiente

5.25. Si \((L,\mathsf{s},\mathsf{i},0,1)\) un reticulado acotado y distributivo, entonces todo elemento tiene a lo sumo un complemento. Es decir, si \(x\;\mathsf{s\;}u=x\;\mathsf{s\;}v=1\) y \(x\;\mathsf{i\;}u=x\;\mathsf{i\;}v=0\), entonces \(u=v\), cualesquiera sean \(x,u,v\in L\).

Proof. Sean \(a,b,c\in L\) elementos fijos. Supongamos que \[\begin{aligned} a\;\mathsf{s\;}b & =a\;\mathsf{s\;}c=1\\ a\;\mathsf{i\;}b & =a\;\mathsf{i\;}c=0 \end{aligned}\] (es decir \(b\) y \(c\) son ambos complementos de \(a\)). Veremos que entonces \(b=c\). Notese que \[b=b\;\mathsf{i\;}1=b\;\mathsf{i\;}(a\;\mathsf{s\;}c)=(b\;\mathsf{i\;}a)\;\mathsf{s\;}(b\;\mathsf{i\;}c)=0\;\mathsf{s\;}(b\;\mathsf{i\;}c)=b\;\mathsf{i\;}c\] por lo cual \(b\leq c\). Analogamente se puede probar que \(c\leq b\) por lo cual \(b=c\). Ya que \(a,b,c\) eran elementos cualesquiera de \(L\), hemos probado el lema.  


Una propiedad muy importante que se da en las algebras de Boole es

5.26. Sea \((B,\mathsf{s},\mathsf{i},^{\mathbf{c}},0,1)\) un álgebra de Boole. Cualesquiera sean \(x,y\in B\), se tiene que \(y=(y\;\mathsf{i\;}x)\;\mathsf{s\;}(y\mathsf{\;i\mathsf{\;}}x^{c})\).

Proof. Sean \(a,b\in B\), fijos. Se tiene que \[b=b\;\mathsf{i\;}1=b\mathsf{\;i\mathsf{\;}}(a\mathsf{\;s\mathsf{\;}}a^{c})=(b\;\mathsf{i\;}a)\;\mathsf{s\;}(b\mathsf{\;i\mathsf{\;}}a^{c})\] Ya que \(a\) y \(b\) eran elementos cualesquiera de \(B\), hemos probado el lema.  


5.2. Sea \((L,\mathsf{s},\mathsf{i},^{\mathbf{c}},0,1)\) un álgebra de Boole y sean \(a,b\in B\). Se tiene que:

  1. adhocprefix(1)adhocsufix \((a\,\mathsf{i\,}b)^{c}=a^{c}\,\mathsf{s\,}b^{c}\)

  2. adhocprefix(2)adhocsufix \((a\,\mathsf{s\,}b)^{c}=a^{c}\,\mathsf{i\,}b^{c}\)

  3. adhocprefix(3)adhocsufix \(a^{cc}=a\)

  4. adhocprefix(4)adhocsufix \(a\,\mathsf{i\,}b=0\) si y solo si \(b\leq a^{c}\)

  5. adhocprefix(5)adhocsufix \(a\leq b\) si y solo si \(b^{c}\leq a^{c}\)

Proof. (1) Es facil ver que \(a^{c}\,\mathsf{s\,}b^{c}\) es un complemento de \(a\,\mathsf{i\,}b\) (hacer!). Pero ya que \((L,\mathsf{s},\mathsf{i},^{\mathbf{c}},0,1)\) es un reticulado complementado, tenemos que \((a\,\mathsf{i\,}b)^{c}\) es un complemento de \(a\,\mathsf{i\,}b\). El Lema 5.25 nos dice que \((a\,\mathsf{i\,}b)^{c}\) y \(a^{c}\,\mathsf{s\,}b^{c}\) deben ser iguales.

(2) y (3) se prueban en forma similar (hacer!)

(4) Supongamos \(a\,\mathsf{i\,}b=0\). Se tiene \[\begin{aligned} b & =(b\;\mathsf{i\;}a)\;\mathsf{s\;}(b\mathsf{\;i\mathsf{\;}}a^{c})\mathsf{\,}\\ & =(a\;\mathsf{i\;}b)\;\mathsf{s\;}(b\mathsf{\;i\mathsf{\;}}a^{c})\\ & =0\;\mathsf{s\;}(b\mathsf{\;i\mathsf{\;}}a^{c})\\ & =(b\mathsf{\;i\mathsf{\;}}a^{c}) \end{aligned}\] lo cual dice que \(b\leq a^{c}\). Supongamos \(b\leq a^{c}\). Entonces \(a\,\mathsf{i\,}b\leq a\,\mathsf{i\,}a^{c}=0\) por lo cual \(a\,\mathsf{i\,}b=0\).

(5) Supongamos \(a\leq b\). Entonces \(a\,\mathsf{i\,}b=a\), lo cual por (1) nos dice que \(a^{c}\,\mathsf{s\,}b^{c}=a^{c}\) obteniendo que \(b^{c}\leq a^{c}\). La resiproca es dejada al lector (hint: use (3))