Un reticulado terna (L,s,i) se llamara distributivo cuando cumpla la siguiente identidad
Dis1 xi(ysz)=(xiy)s(xiz), cualesquiera sean x,y,z∈L
Diremos que un reticulado acotado (L,s,i,0,1) (resp. complementado (L,s,i,c,0,1)) es distributivo cuando (L,s,i) lo sea. Consideremos la distributividad dual a Dis1, es decir
Dis2 xs(yiz)=(xsy)i(xsz), cualesquiera sean x,y,z∈L
5.24. Sea (L,s,i) un reticulado terna. Entonces (L,s,i) satisface Dis1 sii (L,s,i) satisface Dis2
Proof. Supongamos (L,s,i) satisface Dis1. Sean a,b,c∈L elementos fijos. Por Dis1 tenemos que (asb)i(asc)=((asb)ia)s((asb)ic) Pero por conmutatividad tenemos que ((asb)ia)s((asb)ic)=(ai(asb))s(ci(asb)) Por (I7) tenemos que ai(asb)=a y por Dis1 tenemos que ci(asb)=(cia)s(cib) por lo cual (ai(asb))s(ci(asb))=as((cia)s(cib)) Por asociatividad tenemos que as((cia)s(cib))=(as(cia))s(cib) Pero por conmutatividad tenemos que (as(cia))s(cib)=(as(aic))s(bic) Lo cual por (I6) nos dice que (as(aic))s(bic)=as(bic) Por transitividad de la igualdad, las igualdades anteriores nos dicen que as(bic)=(asb)i(asc) Pero a,b,c eran elementos arbitrarios por lo que hemos probado que vale Dis2.
Ejercicio: Use la prueba del lema anterior para hacer un algoritmo el cual tome de entrada un reticulado acotado (L,s,i,0,1) y elementos x,y,z∈L tales que y≠z son complementos de x, y de como salida elementos a,b,c tales que ai(bsc)≠(aib)s(aic)
Por un Algebra de Boole entenderemos un reticulado complementado que es distributivo. Algunos ejemplos:
E1 Dado un conjunto no vacio X, la 6-upla (X,∪,∩,c,∅,X) es un algebra de Boole
Para probar algunas propiedades fundamentales de un algebra de Boole necesitaremos el siguiente
5.25. Si (L,s,i,0,1) un reticulado acotado y distributivo, entonces todo elemento tiene a lo sumo un complemento. Es decir, si xsu=xsv=1 y xiu=xiv=0, entonces u=v, cualesquiera sean x,u,v∈L.
Proof. Sean a,b,c∈L elementos fijos. Supongamos que asb=asc=1aib=aic=0 (es decir b y c son ambos complementos de a). Veremos que entonces b=c. Notese que b=bi1=bi(asc)=(bia)s(bic)=0s(bic)=bic por lo cual b≤c. Analogamente se puede probar que c≤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,s,i,c,0,1) un álgebra de Boole. Cualesquiera sean x,y∈B, se tiene que y=(yix)s(yixc).
Proof. Sean a,b∈B, fijos. Se tiene que b=bi1=bi(asac)=(bia)s(biac) Ya que a y b eran elementos cualesquiera de B, hemos probado el lema.
5.2. Sea (L,s,i,c,0,1) un álgebra de Boole y sean a,b∈B. Se tiene que:
(1) (aib)c=acsbc
(2) (asb)c=acibc
(3) acc=a
(4) aib=0 si y solo si b≤ac
(5) a≤b si y solo si bc≤ac
Proof. (1) Es facil ver que acsbc es un complemento de aib (hacer!). Pero ya que (L,s,i,c,0,1) es un reticulado complementado, tenemos que (aib)c es un complemento de aib. El Lema 5.25 nos dice que (aib)c y acsbc deben ser iguales.
(2) y (3) se prueban en forma similar (hacer!)
(4) Supongamos aib=0. Se tiene b=(bia)s(biac)=(aib)s(biac)=0s(biac)=(biac) lo cual dice que b≤ac. Supongamos b≤ac. Entonces aib≤aiac=0 por lo cual aib=0.
(5) Supongamos a≤b. Entonces aib=a, lo cual por (1) nos dice que acsbc=ac obteniendo que bc≤ac. La resiproca es dejada al lector (hint: use (3))