Posterior: Presentación algebraica Arriba: Algebras booleanas Anterior: Algebras booleanas

Presentación reticular

Definición 3.1   Todo retículo acotado y distributivo tal que todo elemento posee un complemento se dice ser un ´ALGEBRA BOOLEANA.

Por el lema 1.2.2 se tiene que si $A$ es un álgebra booleana entonces la función complemento $\overline{\ }:A\to A$, $x\mapsto \overline{x}$ está bien definida. Nos referiremos pues a un álgebra booleana enlistando todas sus componentes: $(A,\land,\lor,\overline{\ },\mbox{\bf 1},\mbox{\bf0})$.

Por ejemplo, si $A$ es un conjunto, $({\cal P}(A),\cap,\cup,\ ^c,A,\emptyset)$ es un álgebra booleana. Ésta se dice ser el ´ALGEBRA DE SUBCONJUNTOS.

Ejemplo 3.1 (Álgebra de finitos-cofinitos)   Sea $X$ un conjunto cualquiera (por ejemplo $X={\mathbb{N}}$). Sea ${\cal F}(X)$ la colección de todos los subconjuntos de $X$ que o bien son finitos o bien son complementos de finitos en $X$.
Evidentemente ${\cal F}(X)$ es cerrada bajo las operaciones de ${\cal P}(X)$, así como también posee al conjunto vacío y al ``universo'' $X$.
Por tanto $({\cal F}(A),\cap,\cup,\ ^c,A,\emptyset)$ es un álgebra booleana. Ésta se dice ser el ´ALGEBRA DE SUBCONJUNTOS FINITOS-COFINITOS.

Definición 3.2 (Términos booleanos)   La colección de TÉRMINOS BOOLEANOS ${\cal T}_B$ se define como sigue:

Constantes.

$\mbox{\bf0},\mbox{\bf 1}\in {\cal T}_B$.

Variables.

Para cada variable $x$, $x\in {\cal T}_B$.

Complementos.

Si $\phi\in {\cal T}_B$, entonces $\overline{\phi}\in {\cal T}_B$.

Inter.

Si $\phi,\psi\in {\cal T}_B$, entonces $\phi\land\psi\in {\cal T}_B$.

Unión.

Si $\phi,\psi\in {\cal T}_B$, entonces $\phi\lor\psi\in {\cal T}_B$.

En otras palabras, un término booleano es una expresión que puede evaluarse en un álgebra booleana.

Definición 3.3 (Términos duales)   Para cada término booleano $\phi\in {\cal T}_B$ definiremos su TÉRMINO DUAL $\phi^d\in{\cal T}_B$ de manera recursiva como sigue:

Constantes.

$\mbox{\bf0}^d=\mbox{\bf 1}$ y $\mbox{\bf 1}^d=\mbox{\bf0}$.

Variables.

Para cada variable $x$, $x^d=x$.

Complementos.

Si $\phi\in {\cal T}_B$, entonces $(\overline{\phi})^d = \overline{\phi^d}$.

Inter.

Si $\phi,\psi\in {\cal T}_B$, entonces $(\phi\land\psi)^d = \phi^d\lor\psi^d$.

Unión.

Si $\phi,\psi\in {\cal T}_B$, entonces $(\phi\lor\psi)^d = \phi^d\land\psi^d$.

En otras palabras, el término dual de cualquier término booleano se obtiene al intercambiar las constantes y los operadores de unión e inter.

Observación 3.1 (Principio de dualidad)   Si $\Phi(\phi_1,\ldots,\phi_n)$ es una aseveración que se cumple en toda álgebra booleana, entonces $\Phi(\phi_1^d,\ldots,\phi_n^d)$ también vale en toda álgebra booleana.

En efecto, si ${\cal A}=(A,\land,\lor,\overline{\ },\mbox{\bf 1},\mbox{\bf0})$ es un álgebra booleana, entonces ${\cal A}^d=(A,\lor,\land,\overline{\ },\mbox{\bf0},\mbox{\bf 1})$ es también un álgebra booleana y el enunciado $\Phi(\phi_1,\ldots,\phi_n)$ válido en ${\cal A}^d$ equivale a que el enunciado $\Phi(\phi_1^d,\ldots,\phi_n^d)$ vale en ${\cal A}$.$\quad\Box$

Proposición 3.1   En toda álgebra booleana $(A,\land,\lor,\overline{\ },\mbox{\bf 1},\mbox{\bf0})$ se cumplen las relaciones siguientes:

Leyes de De Morgan.

$\forall x,y\in A$:

$$\begin{array}{l@{\ \ ;\ \ }l} \begin{array}{rcl} \overline{... ...=& \overline{x}\land \overline{y} \end{array} %%& \end{array}$$

Principio de la doble negación.

$\forall x\in A$: $\overline{\overline{x}}=x$.

Demostración
Leyes de De Morgan: Probemos la primera identidad. Ya que los complementos son únicos, basta ver que

$$\begin{array}{l@{\ \ \&\ \ }l} \begin{array}{rcl} \left[x\l... ...verline{y}\right] &=& \mbox{\bf0} \end{array} %%& \end{array}$$

Para la primera de estas igualdades, observamos que

$$\begin{eqnarray*} \left[x\land y\right] \lor \left[\overline{x}\lor \overline{y... ...eft[\mbox{\bf 1}\lor \overline{x}\right] \\ &=& \mbox{\bf 1} \end{eqnarray*}$$

La segunda de estas igualdades se sigue similarmente. La segunda Ley de De Morgan se sigue aplicando el principio de dualidad a la primera.


Principio de la doble negación: Éste se sigue de la unicidad de los complementos. $\quad\Box$

Definición 3.4   Un álgebra booleana $A$ se dice ser COMPLETA si cualquier subconjunto en ella posee un supremo y un ínfimo.

Por ejemplo el álgebra de suconjuntos finitos-cofinitos sobre ${\mathbb{N}}$ no es completa. En efecto, sea $I_n=\{2n\}$ la mónada que consiste del $n$-ésimo número par. El supremo de la colección $\left(I_n\right)_{n\in {\mathbb{N}}}$ debería ser el conjunto de todos los pares pero éste ni es finito ni es cofinito. Por tanto no puede pertenecer a ${\cal F}({\mathbb{N}})$. $\quad\Box$

Definición 3.5   Un ´ATOMO en un álgebra booleana $A$ es un elemento minimal entre sus elementos no-nulos, es decir, distintos de $\mbox{\bf0}$. El álgebra booleana $A$ se dice ser ATÓMICA si es la unión de los conos superiores de sus átomos.

Ejemplo 3.2   Un conjunto $B\subset{\mathbb{R}}$ es SEMI-BORELIANO si se puede expresar como la unión de intersecciones de intervalos semi-infinitos de la forma $[x,+\infty[$ o de complementos de ellos. Sea ${\cal B}$ la colección de conjuntos semi-borelianos. Entonces ${\cal B}$ es un álgebra booleana que no posee átomos.

Proposición 3.2   Toda álgebra booleana que sea completa y atómica puede identificarse con el álgebra de subconjuntos correspondiente a su conjunto de átomos.

Demostración
Tan sólo bosquejaremos la demostración de esta proposición y dejaremos al lector la tarea de suplir los detalles omitidos.
Sea $A$ un álgebra booleana, completa y atómica. Denotemos por $\mbox{\it Atom}(A)$ a su conjunto de átomos. Para cada elemento $x\in A$ consideremos el conjunto $\mbox{\it Atom}_x=\{a\in\mbox{\it Atom}(A)\vert a\leq x\}$ de átomos ``por debajo'' de $x$. La correspondencia $x\mapsto \mbox{\it Atom}_x$ es uno a uno, pues $x=\mbox{\rm Sup}\left(\mbox{\it Atom}_x\right)$, y es suprayectiva, pues $A$ es completa. Más aún, puede verse que esta correspondencia ``preserva las operaciones''. $\quad\Box$

En este curso sólo nos ocuparemos de álgebras booleanas completas y atómicas. Ahora bien si el conjunto de átomos es finito, digamos $\left(a_i\right)_{i=1}^n$, entonces a cada átomo $a_i$ lo podemos identificar con el vector básico $\mbox{\bf e}_i=\left(\delta_{ij}\right)_{j=1}^n$ donde $\delta_{ij}$ es la delta de Kroenecker. Y al supremo de un conjunto de átomos lo identificamos con el supremo de los vectores básicos correspondientes a esos átomos. Así, a la postre estamos identificando a la álgebra booleana de $n$ átomos con el hipercubo de dimensión $n$.

Definición 3.6   La LONGITUD de un álgebra completa y atómica es el número de átomos en ella.

En otras palabras, la longitud de un álgebra completa y atómica es la dimensión del hipercubo con el cual se identifica. Ahora bien, el hipercubo tiene una rica estructura algebraica. Para finalizar este capítulo haremos un repaso de estas nociones.
Posterior: Presentación algebraica Arriba: Algebras booleanas Anterior: Algebras booleanas