Publicación:

Un análogo al teorema de Taylor para funciones Booleanas.

Resumen

INTRODUCCIÓN. A. Definiciones Preliminares Un conjunto es un ente indefinible cuyos sinónimos son: colección, agrupación, etc. Definición: A los objetos que forman un conjunto se les llama elementos. Notación: Si x es elemento del conjunto M se notará x€M. En caso contrario se escribirá x€M. Definición: El conjunto A se denomina subconjunto de B si y sólo si, todo elemento del conjunto A pertenece al conjunto B (es decir, si Vx€A x €B). En el caso en que A es un subconjunto de B y A no es igual a B se dice que A es un subconjunto propio de B. Notación: A es subconjunto de B se denotará AcB. Definición: Para cualquier A y B conjuntos. Se dice que A = B ssi AcB y BcA. Definición: Para cada conjunto A existe un conjunto, cuyos elementos son los subconjuntos del conjunto A y sólo ellos. Tal conjunto se llamará el conjunto potencia de A. Notación: P(A). Definición: Un conjunto M del tipo, M={(a,b) : a€A y b€B} donde A y B son conjuntos, se denomina Producto Cartesiano de A con B. Notación: AxB Definición: El subconjunto FcAxB se llama función, si para cada uno de los elementos x€A existe un elemento único y€B tal que (x,y) €F. Si para cada x€A existe un elemento y€B tal que (x,y) €F, la función se denominará completamente definida. En caso contrario, parcialmente definida. Al conjunto A se le llama dominio de la función F y al conjunto B se le llamará contradominio de la función F. Notación: (x,y) €F se escribe a veces como y=F(x) donde y es el valor de F y x es el argumento de F. Definición: Llámese Producto Cartesiano M=Mi x...x M(n) de los conjuntos M(1) ,...,M, al conjunto M={ m(1) ,..., m ) : m, e M(1) ,..., €M(n)}. Nota: Si en la definición de función, A es el producto cartesiano M, x...xM(n), se obtiene la definición de función n-ádica. Definición: Una operación n-ádica en el conjunto M, x...xM(n) es una función n-ádica y=F(x(1),...,x(n) ), cuyos dominio M(1) x...xM(n) y contradominio B satisfacen M(1) =...=M(n) —B. Definición: La unión AuB de los conjuntos A y B es el conjunto: AuB={ x : x€A o x€B}. La intersección AnB de los conjuntos A y B es el conjunto: AnB={ x : x€A y x€B}. La diferencia A\ B de los conjuntos A y B es el conjunto: A \ B={ x x€A y x€B}. El complemento —A del conjunto A, es el conjunto: ~A={ x : x€A}. Definición: Una función F se llama inyectiva ssi, para cada x,y del dominio de definición de F, x*y -f(x)*f(y) Definición: Una función F se llama sobreyectiva ssi para cada elemento y del contradominio de F, ax del dominio de F tal que y=f(x). Definición: Una función F se llama biyectiva o correspondencia biunívoca si y sólo si F es sobreyectiva e inyectiva. Definición: Se dice que dos conjuntos son cardinalmente equivalentes si, y sólo si, existe una correspondencia biunívoca entre ellos. Definición: Se dice que un conjunto A es infinito si, y sólo si, A es cardinalmente equivalente a un subconjunto propio de A. Definición: Un conjunto A es un conjunto finito si, y sólo si, A no es un conjunto infinito. Definición: Para cualquier f:A→B y g:B→C funciones. Se dice que la composición de funciones de f y g es la función gºf A—> C tal que (gºf(x)=g[f(x)], Vx€A. Definición: Para cualquier f :X-+Y y g:X→Y funciones. Se dice que f=g ssi f(x)=g(x), Vx€X. Definición: Un álgebra A es una colección del conjunto M=Ø con operaciones prefijadas en éste S. Notación: A=<M,S>., Nota: Para identificar un todo común que contiene objetos de distintas estructuras matemáticas, por ejemplo, un conjunto y operaciones en él, se propuso utilizar el término colección y designarlo con los paréntesis angulares <,>. Definición: Se denomina relación binaria T en el conjunto M, a cualquier subconjunto del producto cartesiano de M con él mismo, MxM. Nota: Uno de los conceptos fundamentales, en el estudio de la matemática discreta, es el de relación binaria , ya que se utiliza para designar la ligazón entre objetos o nociones. Definición: Sea T una relación binaria. Por relación binaria inversa de T,T¹ , se comprende aquella tal que (x,y) € T-¹ si y sólo si (y,x) €T. Definición: Una relación binaria T definida en el conjunto M se llama reflexiva, si Vx€M, (x,x) €T. Definición: Una relación binaria T en el conjunto M se llama antisimétrica, si (x,y) €T y (y,x) €T→ x=y. Definición: Una relación binaria T en el conjunto M se llama transitiva, si (x,y) €T y (y,z) €T→(x,z) €T. Definición: Una relación binaria T en el conjunto M se llama relación de orden parcial y se designa con s, si cumple con ser reflexiva, antisimétrica y transitiva . Definición: Un conjunto M en el cual se define una relación de orden parcial <, se denomina conjunto parcialmente ordenado. 1. Teorema: (Principio de Dualidad) La relación binaria inversa de la relación de orden parcial < es también una relación de orden parcial. La relación binaria inversa se designará por < T. Demostración: Sea M un conjunto parcialmente ordenado respecto a <. Como a<a, Va€M, por ser la relación < reflexiva, entonces a<,a, Va€M. Sean a,b€M. Si a <, b y <a → b<a y a<b→ a=b, por ser la relación < antisimétrica. Sean a,b,c€M. Si a<,b y b <c→ c<y b< a→ c< a→ <c, por ser la relación < transitiva. Por lo tanto, la relación < es de orden parcial Ͱ Definición: Se llama dual del conjunto parcialmente ordenado M, el conjunto parcialmente ordenado M definido sobre el mismo conjunto M empleando la relación binaria inversa. Nota: Es usual encontrar la siguiente formulación del principio de dualidad: Si un teorema es válido para los conjuntos parcialmente ordenados también es válido su teorema dual. Definición: Sea a,b€M un conjunto parcialmente ordenado. Un elemento c€M es cota superior de a y b ,si a<c y b< c. Definición: Sea a,b€M un conjunto parcialmente ordenado. Un elemento d€M es cota inferior de a y b, si <a y d<b. Definición: Sea a,b€M un conjunto parcialmente ordenado. Un elemento c€M es la menor cota superior (supremo) de a y b, si: i) ces cota superior de a y b. ii) no existe d, cota superior de a y b, tal que d<c. Notación: sup(a,b) es el supremo de a y b. Definición: Sean a,b€M un conjunto parcialmente ordenado. Un elemento c€M es la mayor cota inferior (ínfimo) de a y b, si: i) ces cota inferior de a y b. fi) no existe d, cota inferior de a y b, tal que c<d. Notación: inf(a,b) es el ínfimo de a y b. Definición: Sea a€M un conjunto parcialmente ordenado. Un elemento c€M cubre al elemento a si no existe b€M tal que a<b<c. B. Retículos Definición: Llamase retículo a un conjunto parcialmente ordenado <M,<>, en el cual cualquiera de dos elementos a,b€M tienen un único ínfimo y un único supremo. Sea <M, <> un retículo. Defínase el sistema algebraico <M,y,^>, donde v y ^ son operaciones binarias en M tales que sólo, para cualquier a,b€M, avb=sup(a,b) y a^b=inf(a,b) 1. Teorema: Si Mes un retículo con la relación de orden parcial <, M conserva su calidad de retículo, si se considera con la relación de orden parcial dual a la dada, designada por <. Demostración: Por el principio de dualidad se tiene que la relación dual < es un orden parcial en M. Sean a,b€M. Pruébese que el supremo de a y b con la relación dual < es a^b. Como a^b<a y a^b<b→ a< a^ y b< a^b a.^b es cota superior de a y b con la relación < de orden parcial. Sea c una cota superior de a y b con la relación < de orden parcial, entonces a <c y b <c → c< a y c<b c-s a^b por ser a^b la mayor cota inferior de a y b→a^btc→a^b es la menor cota superior de a y b con la relación < de orden parcial. Nótese que el supremo de a y b con la relación < de orden parcial es único porque el ínfimo con la relación s de orden parcial es único por ser <M,<> un retículo. Pruébese ahora, que el ínfimo de a y b con la relación dual <(t) es avb. Como a<avb y b<avb a y b →a y avb < (t)b→ avb es cota inferior de a y b con la relación <(t) de orden parcial. Sea c una cota inferior de a y b con la relación < de orden parcial. Entonces c < (t) a y c < (t) b → a<c y b<c avb<c por ser avb la menor cota superior de a y b, por lo tanto c < (t) avb → avb es la mayor cota inferior de a y b con la relación <(t) de orden parcial. Nótese que el ínfimo de a y b con la relación <(t) de orden parcial, es único porque el supremo con la relación < de orden parcial es único por ser <M,<> un retículo Ͱ Notación: Utilizando la relación < (t) de orden parcial, se designará sup(a,b)—avb y inf(a,b)=a^b. 2. Teorema: Para cualquier a y b en un retículo <M,<> se tiene a< avb y a^b<a. Demostración: Por definición, avb es cota superior de a. Entonces, a<avb. De igual manera, por definición, a^b es cota inferior de a. Entonces, a^b< a Ͱ 3. Teorema: Para cualquier a,b,c,d en un retículo <M,<>, si a<b y c<d entonces avc<bvd y a^c <b^d. Demostración: Como b<bvd y d<bvd por el teorema anterior. Por hipótesis y por transitividad se tiene: a<bvd y c<byd. Por tanto, bvd es cota superior de a y c. Pero la menor cota superior de a y ces avc entonces, avc<bvd. De igual forma, como a^c< a y a^c<c por el teorema anterior. Por hipótesis y por transitividad se tiene: a^c<b y a^c< d. Entonces a^c es cota inferior de b y d. Pero la mayor cota inferior de b y d es b^d entonces, a^c<b^d Ͱ 4. Teorema: (Idempotencia) Para cada a en el retículo <M, <>, se tiene: ava=a y a^a=a. Demostración: Sea a en el retículo <M,<>. Por definición de supremo, se tiene: a<ava. Además, a<a por reflexividad. Entonces, a esa cota superior de sí mismo. Con lo cual, ava<a ya que ava es la mínima cota superior de a. Por ser antisimétrica la relación <, se tiene: ava=a. De igual forma, por definición de ínfimo se tiene: a^a<a. Además, asa por reflexividad. Por lo anterior, a esa cota inferior de sí mismo. Con lo cual, a<a^a. Al ser antisimétrica la relación < se tiene: a^a=aͰ 5. Teorema: (Absorción) Para cualesquiera a y b en un retículo <A,z> se tiene: av(a^b)=a y a^(avb)=a. Demostración: Sea a y b elementos del retículo <A, <>. Por definición de supremo se tiene: A<av(a^b). Luego, asa por reflexividad y a^b<a por definición de ínfimo. Entonces, av(a^b)<ava por el teorema I.B.3. Por idempotencia se tiene: av(a^b)<a. Como la relación <, es antisimétrica se concluye que: av(a^b)=a. De igual forma, como a^(avb)<a por la definición de ínfimo. Luego, a<a por reflexividad y a<avb por definición de supremo. Por consiguiente, a^a<a^(avb) por el teorema I.B.3. Entonces, a<a^(avb) por idempotencia. Como la relación < es antisimétrica se tiene: a^(avb)=aͰ 6. Teorema: Las operaciones v y ^ son asociativas. Demostración: Sean a,b,c en un retículo <M,<>. Nótese que a<av(bvc) y bvc<av(bvc). Además, b<bvc y c<bvc = a<av(bvc) y b-<av(bvc) y C<av(bvc) por transitividad. Entonces, avb<av(bvc) y c<av(bvc) por el teorema I.B.3 e idempotencia. Por lo tanto, (avb)vc<av(bvc) por el teorema I.B.3 e idempotencia. Por otro lado, nótese que avb<(avb)vc y c<(avb)vc por definición de supremo. Como a<avb y b<avb entonces, a<(avb)vc y b<(avb)vc por transitividad. Por lo tanto, a<(avb)vc y bvc<(avb)yc por el teorema I.B.3 e idempotencia. Con lo cual, av(byc)<(avb)vc por el teorema I.B.3 e idempotencia. Por ser la relación < antisimétrica se tiene: av(bvc)=(avb)vc. Por tanto, la operación y es asociativa. De igual forma, para el retículo <M, < 7.> se tendría: av(bvc)=(ayb)vc ,Va,b,c€M A^(b^c)<(a^b)^c, Va,b,c€M por el teorema I.B.1. Por ello, la operación ^ es asociativa Ͱ Definición: Un retículo <M, <> es distributivo si para cada a,b,c€M se cumple: i) ay(b^c)=(avb)^(avc) ii) a^(bvc)=(a^b)v(a^c). 7. Teorema: Sea <M<> un retículo. La operación ves distributiva respecto a ^ en el retículo si y sólo si ^ es distributivo respecto a v. Demostración: (<=) Supóngase ^ es distributiva respecto a v. Entonces, Va,b,c€M se cumple que A^(bvc)=(a^b)y(a^c). Luego, (avb)^(avc)=((avb)^a)v((avb)^c)=av((avb)^c)=av((a^c)v(b^c))= (av(a^c))y(b^c)=av(b^c). De esta forma, la operación y es distributiva respecto a ^. (=>) Sea y es distributiva respecto a ^. Así, se cumple que av(b^c)=(avb)^(avc). Como <M,<(t).> es un retículo. Entonces, av(b^c)=(avb)^(avc) ,Va,b,c€M → a^(bvc)=(a^b)v(a^c) ,Va,b,c€M por el teorema I.B.1. Por lo tanto, la operación A es distributiva respecto a v Ͱ Definición: Sea <M,<> un retículo. Un elemento aeM es llamado mayor cota universal si Vb€M, b < a. Notación: La mayor cota universal se denotará por 1. Nota: Si un retículo tiene mayor cota universal, ésta es única. Definición: Sea <M,<> un retículo. Un elemento a€M es llamado menor cota universal si Vb€M, a<b. Notación: La menor cota universal se denotará por O. Nota: Si un retículo tiene menor cota universal, ésta es única. 8. Teorema: Sea <M,<> un retículo con 1 y O. Entonces: av1=1, av0=a, a.^1=a y a.^0=0 ,Va€M. Demostración: Sea a€M. Nótese que avl <.1 por ser 1 la mayor cota superior. Además, 1<avl por definición de supremo de a y 1. Como la relación -s de orden parcial es antisimétrica, entonces av1=1. Nótese que O<a por ser O menor cota universal. Como a<a por ser la relación < reflexiva, entonces, av0<a por el teorema I.B.3 e idempotencia. Además, a<av0 por definición de supremo de a y o. Como la relación s de orden parcial es antisimétrica, entonces av0=a. Por el teorema I.B.1 se tiene: <M, <(t).> es un retículo, Vb€M, b< 1 y 0<b Vb€M, 1 < (t) b y b< (t)0 → 1 es la menor cota universal y O es la mayor cota universal del retículo <M, <(t)>. Entonces, <M, <(t)> es un retículo con 1 y O donde 1 es la mayor cota universal y O es la menor cota universal. Entonces, av 1=1 y av 0=a. Por lo anterior, y el teorema I.B.1, se tiene: a^0=0 y a^1=a Ͱ Definición: Sea <M,<> un retículo con I y O. Para un elemento a€M, el elemento b€M es su complemento ssi avb=1 y a^b=0. Nota: Por la conmutatividad del v,^, si b es complemento de a, entonces a ese complemento de b. El complemento no necesariamente es único. Un elemento no necesariamente tiene complemento. Definición: Un retículo es complementado, si cada elemento del retículo tiene complemento. 9. Teorema: Sea <M,<> un retículo distributivo con 1 y O. Si un elemento tiene complemento, entonces éste es único. Demostración: Sea a un elemento de <M,<>, retículo distributivo con 1 y O, el cual tiene complemento. Supóngase que b y c son complementos de a, entonces avb=1, a^b=0 y avc=1, a^c=0 por definición. Con lo cual , b=b^1=b^(avc)=(b^a)v(b^c)=0v(b^c)=(a^c)v(b^c)= (avb)^c= l^c=c. Por lo tanto, b=c Ͱ Definición: Un Retículo complementado y distributivo se llama Retículo Booleano. Nota: Como cada elemento <M,z> tiene un único complemento defínase una operación unaria en el conjunto M, denotada —, así que para cada a€M, ~a es el complemento de a. La operación antes definida se llama complementación. Entonces, El retículo Booleano <M,<> define el sistema algebraico <M,v,^,~>. Definición: Dado un retículo booleano <M,<>. Se define ø:MxM→M tal que aøb=(a^-b)v(~a^b), V a,b€M. Nota: ø recibe el nombre de " ó exclusivo". 10. Lema: Dado un retículo booleano <M,<>. Entonces: i) ~(aøb)=(~a^~b)v(a^b), Va,b€M ii) aøb=bøa, Va,b€M. iii) aø(bøc)=(aøb)øc, Va,b,c€M. iv) a^(bøc)=(a^b)ø(a^c), Va,b,c€M. y) aøa=0, aøa=1, aø0=a y -a=løa, Va€M. vi) avb=aøbø(a^b), Va,b€M. Demostración: Sea a,b,c€M. i) ~(aøb)=(a^b)v(~a^b)}=(~av~b)^(~av~b)={ (~avb)^a} (~avb)^~b }={ (~a^a)v(b^a)}v {(~ a^~b)v(b^~b)}={ 0v(a^b)} { (~a^,~b)v0 } =(a^b)v(~a^~b)=(~a^~b)v(a^b) por conmutatividad de ^ y v, distributividad de v con respecto ^ , distributividad de ^ con respecto a v. ii) aøb=(a^~b)v(~a^b)=(~a^b)v(a^~b)=(b^~a)v(~b^a)=bøa por conmutatividad de ^ y v. iii) aø(bøc)=aø{(b^~c)v(~b^c)}=[a^~{(b^~c)v(~b^c)}]y[~a^{(b^~c)y(~b^c)}]=[a^{(~b^~c)v (Vø)} ]v{(~a^(b^~c))v(~a^(~b^c))}~ { (a^(b^~c))v(a^(b^c))}y{ ((~a^b)^~c)v((~a^~)^c)} =[1((a^~b)^~c)v((a^b)^c)}v((~a^b)^~c)]v((~a^~b)^c)=[((a^~b)^~c)v( ((a^b)^c)v((~a^b)^ ~c)} }y((~a^~b)^c)=[((a^~b)^~c)v{ ((~a^b)^~c)v((a^b)^c)} lv((~a^~b)^c)=[ { ((a^~b)^~c)v((~a^b)^~c)} v((a^b)^c)]v((~a^~b)^c)=[ ((a^~b)v(~a^b)}^~c]v{((a^b)^c)v((~a^~b)^c) }= ((aøb)v-c}v[{(a^b)v(---a^-c)}^~c}={(aø)^~o}v[{(-a^--b)v(a^b)}^c}={(aø)^~c}v{-(aø)^c}= (aøb)øc.[1((a^~b)^~c)v((a^b)^c)}v((~a^b)^~c)]v((~a^~b)^c)=[((a^~b)^~c)v( ((a^b)^c)v((~a^b)^~c)} }y((~a^~b)^c)=[((a^~b)^~c)v{ ((~a^b)^~c)v((a^b)^c)} lv((~a^~b)^c)=[ { ((a^~b)^~c)v((~a^b)^~c)} v((a^b)^c)]v((~a^~b)^c)=[ ((a^~b)v(~a^b)}^~c]v{((a^b)^c)v((~a^~b)^c) }= ((aøb)v-c}v[{(a^b)v(---a^-c)}^~c}={(aø)^~o}v[{(-a^--b)v(a^b)}^c}={(aø)^~c}v{-(aø)^c}= (aøb)øc. C. Algebra Booleana Definición: Un sistema algebraico definido por un retículo Booleano se llama Algebra Booleana. 1. Teorema: (Leyes de DeM organ): Para cualesquiera a,b en un álgebra Booleana se tiene: ~(avb)=a^~b y ~(a^b)=av~b. Demostración: Sean a,b en un álgebra Booelana <M,v.^,—>. Luego, (avb)v(~a^~b) = { (avb)v~,a }^{ (avb)v~b }={ (av~a)vb }^{ av(bv~b)} =(1 vb)^(av1)=1^ 1=1 y (avb)^(~a^~b)={ a^(~a^~b)} v{ b^(~a^~b)}={(a^~a)^~b}v{~a^(b^~b)}=(0^~b) v(0^~a)=0v0=0. Como el complemento de avb es único, entonces ~(avb)=a^.~b. Como <M,v,^~> es un álgebra Booleana. Por lo anterior se tiene: ~(avb)=a^~b,Va,b€M→~(a^b)→av~b, Va, b€mͰ Definición: Un elemento a de un retículo Booleano es un átomo si cubre a 0. 2. Lema: Sea <M,<> un retículo booleano finito. Para cada a elemento no cero, existe por lo menos un átomo b, tal que: b<a. Demostración: Si a es un átomo, se obtiene el resultado. En caso contrario, si a no es un átomo, el elemento a no cubre a 0 por lo que Eb€M tal que 0<b<a y b=a. Si b es un átomo, entonces queda demostrado. En caso que b no es un átomo, se sigue el mismo argumento. Como M es un conjunto finito, este proceso eventualmente termina, con lo que se obtiene: O<b<…<b(2)<b(1)< a→b, es átomo y es tal que b,<a Ͱ 3. Lema: Sea <M,<> un retículo distributivo con 0 y 1. Si b^~c=0 b<c. Demostración: Si b^~c=0→ c=0vc=(b^~c)vc~(bvc)^(~cyc)=(bvc)^1=bvc →b<c Ͱ 4. Lema: Sea <M,v,^,~> un álgebra booleana finita. Sea b un elemento no cero de M y a(1)a(2),...,a todos los átomos de M tales que a, <_b para i=1,...,n. Entonces b=a(1) va(2) v...va„. Demostración: Por hipótesis, a, <b para i=1,...,n, entonces, a(l) va(2) <b Supóngase c=a(1) va(2) v...va, y que b^,~c=0. En este caso, E€M, átomo, tal que a<b^--c. Además b^~b y b^~c<c. Por transitividad se tiene: a<b y a<c → a es uno de los a(1) , a(2),...,a(n), de lo que se sigue que a<<c y a<c. Entonces, a<c^~c=0, lo cual es una contradicción. Por lo tanto, b^,--c=0, lo que implica que b<c. Es decir, b<a(1) va(2) v...va(n) . Entonces, b=a(1) va(2) v...va(n) por antisimetría Ͱ 5. Lema: Sea <M,v,^,~> un álgebra booleana finita. Sea x elemento de M y sea a un átomo de M, entonces a<x ó a^x=0. Demostración: Sea x en M y a un átomo de M. Nótese que 0<x y 0<a→ 0<x^a<a. Entonces x^a=0 ó x^a=a por ser a un átomo. Por lo tanto, x^a=0 ó a=x^a<x, con lo cual, x^a=0 6 a<x Ͱ 6. Teorema: Sea <M,v,^,~> un álgebra booleana finita con conjunto de átomos S={a(1),a(2),..,a(n)}. Sea x un elemento no cero de M. Así, x puede representarse: x= a(a1) v...va(2) donde a(1)…a(2) son todos los átomos <x. Más aún, esa expresión es única, excepto por el orden de los átomos. Demostración: Sea x=0 en M. Nótese que a<1,Va, €S. Entonces 1—a(1) v.. va(n) por el lema I.C.4. Luego, x=x^1=x^(a(1) v...va(n)=(x^al )v...v(x^a(n). Como x^a,=a(i) si a,<xyx^a,=0, en caso contrario, entonces x=a(i) v...va donde a… a son todos los átomos <x. Para verificar la unicidad, supóngase que x=b(1 )v...vb(k) donde b(1) ,...,b(k) son átomos. Entonces, b(1) <x para i:1,…k, por lo tanto b, € {a€S:a<x}. Por otro lado, si a€S y a<x entonces ø=a=a^x=a^(b(1) v...vb(k))=(a^b(1) ) v...v(a^b(k) ). Con lo cual, para algún b, con i=1, ...,k se tiene que a^b,=0, ya que de lo contrario, si todos los a^b,=0, entonces a=0, lo cual es una contradicción. Lo anterior implica que, a^b(i)=a=b, ya que a y b, son átomos. Por lo tanto a€{b(1) ,..., b(k) }. En consecuencia, {b(1) ,..., b(k) }={a€S:a:<x}. 7. Lema: Sean x,y elementos de una álgebra booleana y a un átomo. i) a<xvy si y sólo si a<x o a<y. ii) a<x^y si y sólo si a<x y a<y. iii) a<x ó a<~x. Demostración: Sean x,y elementos de un álgebra booleana y a un átomo. i) (→) Como x es un elemento de un álgebra booleana, se tiene: a<x ó a^x=0 por lema I.C.5. Para el caso a<x, se obtiene el resultado. Para el caso contrario, por hipótesis se tiene que: a<xvy a→a^(xvy). Luego, a=(a^x)v(a^y)=0v(a^y)=a^y > a<y. i) (→) Por hipótesis se tiene que a<x o a<y. Además, x<xvy y y<xvy por definición de supremo. En cualquiera de los dos casos por transitividad se tiene: a<xvy. ii) (→) Por hipótesis se tiene que: a<x^y. Además, x^y<x y x^y<y por definición de ínfimo. Entonces, a<x y a<y por transitividad. ii) (→) Por hipótesis se tiene que a<x y a<y. Entonces, a^a<x^y por el teorema I.B.3. Por lo tanto, a<x^y por idempotencia. iii) Como x es un elemento de un álgebra booleana se tiene: a<x ó a^x=0. Para el caso a<x queda demostrado. Para el caso contrario, como a^x=0 → a^~x=0, por unicidad del complemento de ~ x. Entonces, a<~ x por lema I.C.3. 8. Teorema: Si A es un álgebra Booleana finita con conjunto de átomos S={a(1)…a(n)}, y B es un álgebra booleana finita con conjunto de átomos D={b(1)…b(n)}, entonces existe una corresepondencia uno a uno f de A en B, tal que f(a,)=b(i), para i=1, ...,n y cumple las siguientes propiedades: i) x< y si y sólo si f(x)<f(y) , Vx,y€A ii) f(xvy)=f(x)vf(y) , Vx,y€A. iii) f(x^y)=f(x)^f(y) , Vx,y€A. iv) f(~x)=f(x) Vx€A v) f(xøy)=f(x)øf(y), Vx,y€A Demostración: Sea x€A un álgebra booleana finita con conjunto de átomos S. Si x=0 entonces, x puede escribirse de manera única en la forma x=a(1) v...va(k). Defínase fA→B tal que f(x)=b(1) v...vb(k), si x=0 ó f(x)=0, si x=0. En particular, f(a(1) )=bi para i=1,...,n. Para cada x€A, f(x) tiene representación única (salvo por el orden de los átomos). Entonces f está bien definida. Pruébese ahora, que f es biyectiva. Sea y€B. Luego, y=b(1) v...vb(k) por el teorema I.C.6. Como f(a(1))=bi para i=1,...,n. Considérese x=a(1),., v...va(k) , de donde f(x)=b(1) v...vb(k) =y por definición de f Sean x,y€A tal que f(x)=f(y). Luego, x=a(1)v...va(k) y y-a(1) v...va.. Entonces, B, v...vb(k) =f(x)=f(y)=b.v. ..vb. . Como la representación de f(x) y f(y) es única, se tiene que k=m y Vt€{1,...,k}, Ǝ! w tal que bi = bL . Entonces ai =aj , con lo cual, x=a. v...va =a v...va. =y. Entonces f es biyectiva. A probar, que Vy€A y Va€S si a<y si y sólo si f(a)<f(y). (-) Sean yeA y aeS, tal que, asy. Nótese que y=yAl=y^(av-a)-(y^a)v(y^-a)-avy^-a, por ser asy. Como y^-aeA, se tiene y"--a=afi v...vain por el lema I.C.6; entonces, y=ava va „, J . Luego, f(y)=f(a)vf(a )v...vf(a n, ) por definición de f. Entonces, f(a)sf(y). J, I (=) Sean yEA y aeS tal que f(a)sf(y). Nótese que f(y)=f(y)^1=f(y)^(f(a)v---f(a))=(f(y)^f(a)) v(f(y)^,--f(a))=f(a)v(f(y)^4(a)). Como f(y)^-4(a)eB se tiene que f(y)^-f(a)=bv...vb,.. Siendo así, f(y)=f(a)yb. v...vb . Además, f(a,)=b, para i=1 ,...,n y, por definición de f, se tiene 1, f(y)=f(ava v...va. ). Como f es inyectiva entonces y=ava va . Por lo tanto, a-y. i) (-) Sean x,yeA tal que xsy. Como x EA se tiene: x=ava, por el teorema I.C.6. En ese caso, a, Vje{1,...,k} = f(a,)-f(y), Vje {1,...,10. Como f(x)=f(a,i )v...vf(a,k ) por definición de f, entonces f(x)-sf(y). i) () Sean x,yeA tal que f(x)sf(y). Como f(x)EB se tiene: f(x)=bv...vb,, por el teorema I.C.6. Como f(a,)=b, para i=1,...,n ,entonces f(x)-f(a,i )v...vf(a/k). Por lo tanto, f(a,j)-sf(y), VjE{1,...,k} se tiene: a, Vje{1,...,k}. Con lo cual, xsy. fi) Sean x,yeA. Como f(xvy)EB se tiene que: f(xvy)=1),, y...vb,, por el teorema I.C.6. Nótese que b, f(xvy), Vje { 1,...,k}. Por ser f sobreyectiva, a a1 tal que f(a,)= b,, Vje{l,...,k}, entonces f(a, )sf(xvy), Vje{1,...,k}. Con lo cual, a, -nvy, Vje{1,...,k} por i) a, :sx o a, -sy, Vje{1,...,k} por el lema I.C.7. Luego, f(a, )sf(x) o f(a,)sf(y), Vje{1,...,k} por i). De lo anterior se tiene: f(aisf(x)vf(y), Vje{1,.. k} por el lema I.C.7, entonces b, sf(x)vf(y), Vje{1,...,k}. Por lo tanto, f(xvy)sf(x)vf(y). Como f(x)vf(y)eB se tiene que: f(x)vf(y)=b,y. vb,k por el teorema I.C.6. Nótese que b 5. f(x)vf(y), Vje{1,...,k}. Por ser f sobreyectiva, Sal tal que f(a ,)= b Vje{1,...,k}, entonces f(a,)f(x)vf(y), Vje{1,. .,k}. Luego, f(a1 )_<f(x) o f(as)s.f(y), Vje{1,...,k} por el lema I.C.7. Con lo cual, as <_x o assy, Vje{1,...,k} por i). Por lo tanto, aii -sx-vy, Vje{1,...,k} por el lema I.C.7. De lo anterior se tiene: f(as)sf(wy), Vje{1,...,k} por i) , así, bs -sf(xvy), Vje{1,...,k}. Por tanto, f(x)vf(y)sf(xvy). Por antisimetría se tiene: f(xvy)=f(x)vf(y). iii) Sea x,yeA. Como f(x^y)eB se tiene que: f(x^y)---b. ..vb,á por I Vje{1,...,k} Por ser f sobreyectiva, Ras tal que el teorema I.C.6. Nótese que b f(x^y), 5 f(as)= bs, Vje{1,...,k}, de esta manera )-sf(x^y), Vje{1,...,k}. Con lo cual, a, sx^y, Vje{1,...,k} por i) a, -sx y a, -sy, \ 1,...,k} por el lema I.C.7. Luego, f(a1 )<_f(x) y A, ) s f(y), Vje{1,...,k} por i) . De lo anterior se tiene: f(a,)sf(x)Af(y), Vje{1,...,k} por el lema I.C.7, entonces b,sf(x)^f(y), Vje{1,...,k}. Por lo tanto, f(x^y)-sf(x)^f(y). Como f(x)^f(y)eB se tiene que: f(x)^f(y)=b,v...vbik por teorema I.C.6. Nótese que b -sf(x)^f(y), Vje{1,...,k}. Por ser f sobreyectiva, 3a, tal que f( a, )= b1 , Vje{1,...,k}, J J entonces f(a, )-sf(x)^f(y), Vje{ 1,...,k} Luego, f(a1 )<f(x)y f(a, )sf(y), Vje{1,...,k} por lema I.C.7. Con lo cual, a, -sx y a, <y, Vje{1,...,k} por i). Por lo tanto, a, -sx^y, Vje{1,...,k} por el lema I.C.7. De lo anterior se tiene: la, )-sf(x^y), Vje{1,...,k} por i), siendo así, bi -sf(x^y), Vje{1,...,k}. Por lo tanto, f(x)^f(y)sf(x^y). Por antisimetría se tiene: f(x^y)=f(x)^f(y). iv) Sea xeA. Nótese que f(0)=0 y «1)=1. Luego, f(x)vg-x)=f(xv-x)=-- f(1)=1 por ii), y f(x)^f(-x)=f(x^-x)=f(0) por iii). Entonces, f(-x) es complemento de f(x). Por unicidad del complemento de f(x) se tiene: f(-x)=--f(x). y) Sea x,yEA. Luego, f(xsy)=f((x^—y)y(—x^y))=f((x^—y))yf((—x^y))=(f(x)^1—y)) y(f(—x)^f(y))=(f(x)^ —f(y))y(—f(x)^f(y))----f(x)Esf(y) por ii), iii) y iv) Ͱ Definición: Dos álgebras booleanas A y B son isomorfas si existe una función f biyectiva tal que: i) f(xvy)—f(x)vf(y) , Vx,yeA. ii) f(x^y)--f(x)^f(y) , Vx,yA. iii) f(—x)—f(x) , VxeA. 9. Corolario: (Teorema de Stone) Toda álgebra booleana con n átomos es isomorfa al álgebra Booleana P(S) de todos los subconjuntos de un conjunto S con n elementos.