Álgebra de Boole

El álgebra de Boole es un espacio vectorial de forma axiomática. Se definen los siguientes elementos:

$$(B,+,\cdot {,}^{\prime },O_B,1_B)$$

1. $O_B\ne 1_B\in B$
2. $+:B\times B\to B,x+y$
3. $\cdot :B\times B\to B,xy$
4. ${}^{\prime }:B\to B,x’$

Estos elementos deben satisfacer los siguientes axiomas:

1. Conmutatividad: $\forall x,y\in B:x+y=y+x,xy=yx$
2. Distributividad: $\forall x,y,z\in B:x(y+z)=xy+xz,x+yz=(x+y)(x+z)$
3. Neutros: $\forall x\in B:x+0_B=x,x{1}_B=x$
4. Complementos: $\forall X\in B:x+x’=1_B,x{x}^{\prime }=0_b$

A partir de los axiomas, podemos demostrar el resto de propiedades del álgebra de Boole:

1. Acotación: $1+x=1,0x=0$
2. Asociativa: $(x+y)+z=x+(y+z),(xy)z=x(yz)$
3. Involución: $(x^{\prime }{)}^{\prime }=x$
4. De Morgan: $(x+y{)}^{\prime }=x^{\prime }{y}^{\prime },(xy{)}^{\prime }=x^{\prime }+y^{\prime }$
5. Idempotencia: $x+x=x,xx=x$
6. Absorción: $x+xy=x,x(x+y)=x$

Decimos que un álgebra de Boole tiene definido un orden natural cuando $x\le y⟺xy=x$

Pruebas de Unicidad

Las pruebas de unicidad se suelen demostrar de la misma forma. Se supone que no hay unicidad y se elaboran las expresiones hasta llegar a que estos dos valores son el mismo.

Cuando demostramos algo en el álgebra de Boole, podemos inmediatamente asumir que su dual es válido también. Esto se debe a que todos los axiomas son duales, si se intercambia $0_B$ por $1_B$ y $\cdot$ por $+$, entonces la expresión sigue siendo completamente válida.

Pruebas de equivalencia

Se parte de una de las expresiones de la igualdad y, aplicando axiomas y propiedades derivadas de los axiomas, se llega a la segunda expresión. En algunos casos, también podemos utilizar los supuestos planteados para la igualdad (hipótesis).

Átomos

En el álgebra de Boole, se llama átomo a los sucesores inmediatos del $O_B$. En otras palabras, $a\ne 0_B$ es un átomo si y solo si

$$\forall x\in B,ax=b⟹x=a\vee x=0_B$$

Es decir, si $x\le b$, entonces $x$ deberá ser el propio elemento o el elemento neutro $0_B$.

El producto de dos átomos distintos es $0_B$

$$a_1{a}_2=0_B$$

Todo elemento del álgebra puede anotarse como una combinación de los átomos del conjunto.

$$\forall x\in B:x={\alpha }_1{a}_1+{\alpha }_2{a}_2+\cdots +{\alpha }_n{a}_n$$

Donde $a_1,\cdots ,a_n$ son átomos en $B$ y ${\alpha }_1,\cdots ,{\alpha }_n\in \{0_B,1_B\}$

Como todos los elementos del álgebra pueden anotarse como una combinación de los átomos, entonces la cantidad de elementos del álgebra será $|B|=2^n$, donde $n$ es la cantidad de átomos. Si un conjunto cumple los axiomas del álgebra de Boole, entonces esta propiedad se cumplirá.

Cotas

Sea $(A,\le )$ un poset y sea $S\in A,S\ne 0$:

• $m\in A$ es una cota inferior de $S$ si y solo si $\forall x\in S,m\le x$.
• $M\in A$ es una cota superior de $S$ si y solo si $\forall x\in S,x\le M$.

Un conjunto que admite cota superior (inferior) se llama superiormente (inferiormente) acotado. Si admite ambas se llama acotado.

• $x\in S$ es minimal (maximal) de $S$ si y solo si $\forall y\in S,y\le x(y\ge x)$
• $u\in S$ es mínimo (máximo) de $S$ si y solo si $\forall x\in S:u\le x(u\ge x)$. El elemento se denota comúnmente como $u=\min S(\max S)$
• $u\in A$ es el ínfimo (supremo) de $S$ si y solo si $S$ está inferiormente (superiormente) acotado y además $u$ es la máxima (mínima) cota inferior (superior). Se denota como $u=\inf S(\sup S)$

Note

Si $S$ tiene mínimo, es único. Esta observación también es análoga para el máximo.

Note

Si $u=\min S$ entonces $u$ la mayor de las cotas inferiores, y además pertenece a $S$. Esta observación también es análoga para el máximo.

Isomorfismos

Sean $B_1,B_2$ dos álgebras de Boole, se dice que son isomorfas si preservan sus tres leyes a través de $f:B_1\to B_2$ biyectiva tales que:

1. $\forall x,y\in B_1:f(x{+}_{1}y)=f(x){+}_{2}f(y)$
2. $\forall x,y\in B_1:f(x{\cdot }_{1}y)=f(x){\cdot }_{2}f(y)$
3. $\forall x\in B_1:f(x^{{}_1^{\prime }})=f(x{)}^{{}_2^{\prime }}$

Se puede demostrar que si preserva algunas dos de las tres leyes mostradas, entonces preserva las tres.

Si se cumplen estas tres leyes, entonces podemos demostrar que se preservan también los siguientes elementos:

• Neutro: $f(0_{B_1})=0_{B_2}$
• Orden: $\forall x,y\in B_1:x{\le }_{1}y\to f(x){\le }_{2}f(y)$
• Átomos: Si $a$ es átomo en $B_1$, entonces $f(a)$ es átomo en $B_2$.

Como cualquier elemento del álgebra de Boole se puede escribir como combinación de los átomos, entonces para definir un isomorfismo basta con definir la transformación de sus átomos. De esta forma definimos la cantidad de isomorfismos posibles entre dos álgebras como $n!$, siendo $n$ la cantidad de átomos (ambas álgebras tendrán el mismo número de átomos).