Teorema19.15
Un reticulado \(L\) es distributivo si y solo si
\begin{equation*} a \vee ( b \wedge c ) = ( a \vee b ) \wedge ( a \vee c ) \end{equation*}para todo \(a, b, c \in L\text{.}\)
Investiguemos el ejemplo del conjunto potencia, \({\mathcal P}(X)\text{,}\) de un conjunto \(X\) en mayor detalle. El conjunto potencia es un reticulado ordenado por inclusión. Por la definición de conjunto potencias, el mayor elemento en \({\mathcal P}(X)\) es \(X\) mismo y el menor elemento es \(\emptyset\text{,}\) el conjunto vacío. Para cualquier conjunto \(A\) en \({\mathcal P}(X)\text{,}\) sabemos que \(A \cap X = A\) y \(A \cup \emptyset = A\text{.}\) Esto sugiere la siguiente definición para reticulados. Un elemento \(I\) en un conjunto parcialmente ordenado \(X\) es un elemento mayor si \(a \preceq I\) para todo \(a \in X\text{.}\) Un elemento \(O\) es un elemento menor de \(X\) si \(O \preceq a\) para todo \(a \in X\text{.}\)
Sea \(A\) en \({\mathcal P}(X)\text{.}\) Recuerde que el complemento de \(A\) es
\begin{equation*} A' = X \setminus A = \{ x : x \in X \text{ y } x \notin A \}. \end{equation*}Sabemos que \(A \cup A' = X\) y \(A \cap A' = \emptyset\text{.}\) Podemos generalizar este ejemplo a reticulados. Un reticulado \(L\) con mayor elemento \(I\) y menor elemento \(O\) es complementado si para cada \(a \in L\text{,}\) existe un \(a'\) tal que \(a \vee a' = I\) y \(a \wedge a' = O\text{.}\)
En un reticulado \(L\text{,}\) las operaciones binarias \(\vee\) y \(\wedge\) satisfacen leyes conmutativas y asociativas; pero, no necesariamente satisfacen la ley distributiva
\begin{equation*} a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ); \end{equation*}sin embargo, en \({\mathcal P}(X)\) la ley distributiva se satisface pues
\begin{equation*} A \cap ( B \cup C ) = (A \cap B ) \cup ( A \cap C ) \end{equation*}para \(A, B, C \in {\mathcal P}(X)\text{.}\) Diremos que un reticulado \(L\) es distributivo si se satisfacen las siguientes leyes distributivas:
\begin{equation*} a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ) \end{equation*}para todo \(a, b, c \in L\text{.}\)
Un reticulado \(L\) es distributivo si y solo si
\begin{equation*} a \vee ( b \wedge c ) = ( a \vee b ) \wedge ( a \vee c ) \end{equation*}para todo \(a, b, c \in L\text{.}\)
Supongamos que \(L\) es un reticulado distributivo.
\begin{align*} a \vee ( b \wedge c ) & = [a \vee (a \wedge c) ] \vee ( b \wedge c )\\ & = a \vee [(a \wedge c) \vee ( b \wedge c )]\\ & = a \vee [(c \wedge a) \vee ( c \wedge b )]\\ & = a \vee [c \wedge ( a \vee b )]\\ & = a \vee [( a \vee b ) \wedge c ]\\ & = [( a \vee b ) \wedge a ] \vee [(a \vee b) \wedge c ]\\ & = ( a \vee b ) \wedge ( a \vee c ). \end{align*}El recíproco es consecuencia directa del Principio de Dualidad.
Un álgebra Booleana es un reticulado \(B\) con elemento mayor \(I\) y elemento menor \(O\) tal que \(B\) es distributivo y complementado. El conjunto potencia de \(X\text{,}\) \({\mathcal P}(X)\text{,}\) es nuestro prototipo de álgebra Booleana. Resulta, que es además una de las álgebras Booleanas más importantes. El siguiente teorema nos permite caracterizar las álgebras Booleanas en términos de las relaciones binarias \(\vee\) y \(\wedge\) sin mencionar el hecho de que un álgebra Booleana es un conjunto parcialmente ordenado.
Un conjunto \(B\) es un álgebra Booleana si y solo si existen operaciones binarias\(\vee\) y \(\wedge\) en \(B\) que satisfacen los siguientes axiomas.
\(a \vee b = b \vee a\) y \(a \wedge b = b \wedge a\) for \(a, b \in B\text{.}\)
\(a \vee ( b \vee c) = (a \vee b) \vee c\) y \(a \wedge ( b \wedge c) = (a \wedge b) \wedge c\) para \(a, b, c \in B\text{.}\)
\(a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c )\) y \(a \vee ( b \wedge c ) = (a \vee b ) \wedge ( a \vee c )\) para \(a, b, c \in B\text{.}\)
Existen elementos \(I\) y \(O\) tales que \(a \vee O = a\) y \(a \wedge I = a\) para todo \(a \in B\text{.}\)
Para todo \(a \in B\) existe \(a' \in B\) tal que \(a \vee a' = I\) y \(a \wedge a' = O\text{.}\)
Sea \(B\) un conjunto que satisface (1)–(5) en el teorema. Una de las leyes idempotentes se satisface pues
\begin{align*} a & = a \vee O\\ & = a \vee (a \wedge a')\\ & = (a \vee a) \wedge (a \vee a')\\ & = (a \vee a ) \wedge I\\ & = a \vee a. \end{align*}Observemos que
\begin{equation*} I \vee b = (I \vee b ) \wedge I = (I \wedge I) \vee (b \wedge I) = I \vee I = I. \end{equation*}Concluimos que se satisface la primera de las dos leyes de absorción, pues
\begin{align*} a \vee (a \wedge b) & = (a \wedge I) \vee (a \wedge b)\\ & = a \wedge (I \vee b)\\ & = a \wedge I\\ & = a. \end{align*}La otra ley idempotente y de absorción se demuestran de forma similar. Como \(B\) también satisface (1)–(3), se cumplen las condiciones del Teorema 19.14; por lo tanto, \(B\) es un reticulado. La condición (4) nos dice que \(B\) es un reticulado distributivo.
Para \(a \in B\text{,}\) \(O \vee a = a\text{;}\) luego, \(O \preceq a\) y \(O\) es el menor elemento en \(B\text{.}\) Para mostrar que \(I\) es el mayor elemento en \(B\text{,}\) mostraremos primero que \(a \vee b = b\) es equivalente a \(a \wedge b = a\text{.}\) Como \(a \vee I = a\) para todo \(a \in B\text{,}\) usando las leyes de absorción podemos determinar que
\begin{equation*} a \vee I =(a \wedge I) \vee I = I \vee ( I \wedge a) = I \end{equation*}y \(a \preceq I\) para todo \(a\) in \(B\text{.}\) Finalmente, como sabemos que \(B\) es complementado po (5), \(B\) es un álgebra Booleana.
Recíprocamente, supongamos que \(B\) es un álgebra Booleana. Sean \(I\) y \(O\) el elemento mayor y el elemento menor en \(B\text{,}\) respectivamente. Si definimos \(a \vee b\) y \(a \wedge b\) como el supremo y el ínfimo de \(\{ a, b\}\) respectivamente, entonces \(B\) satisface las condiciones (1)–(5).
Muchas otras identidades se satisfacen en las álgebras Booleanas. Algunas de estas identidades están listada en el siguiente teorema.
Sea \(B\) un álgebra Booleana. Entonces
\(a \vee I = I\) y \(a \wedge O = O\) para todo \(a \in B\text{.}\)
Si \(a \vee b = a \vee c\) y \(a \wedge b = a \wedge c\) for \(a, b, c \in B\text{,}\) entonces \(b = c\text{.}\)
Si \(a \vee b = I\) y \(a \wedge b = O\text{,}\) entonces \(b = a'\text{.}\)
\((a')'=a\) para todo \(a \in B\text{.}\)
\(I' = O\) y \(O' = I\text{.}\)
\((a \vee b)' = a' \wedge b'\) y \((a \wedge b)' = a' \vee b'\) (Leyes de De Morgan).
Solo demostraremos (2). El resto de las identidades las dejamos como ejercicios. Para \(a \vee b = a \vee c\) y \(a \wedge b = a \wedge c\text{,}\) tenemos
\begin{align*} b & = b \vee (b \wedge a) \\ & = b \vee (a \wedge b) \\ & = b \vee (a \wedge c) \\ & = ( b \vee a) \wedge ( b \vee c) \\ & = ( a \vee b) \wedge ( b \vee c) \\ & = ( a \vee c) \wedge ( b \vee c) \\ & = ( c \vee a ) \wedge ( c\vee b ) \\ & = c \vee (a \wedge b)\\ & = c \vee ( a \wedge c )\\ & = c \vee ( c \wedge a )\\ & = c. \end{align*}Un álgebra Booleana es un álgebra Booleana finita si contiene un número finito de elementos como conjunto. Las álgebras Booleanas finitas son particularmente amigables, pues las podemos clasificar módulo isomorfismo.
Sean \(B\) y \(C\) álgebras Booleanas. Una función biyectiva \(\phi : B \rightarrow C\) es un isomorfismo de álgebras Booleanas si
\begin{align*} \phi( a \vee b ) & = \phi(a) \vee \phi(b)\\ \phi( a \wedge b ) & = \phi(a) \wedge \phi(b) \end{align*}para todo \(a\) y \(b\) en \(B\text{.}\)
Mostraremos que cualquier álgebra Booleana finita es isomorfa al álgebra Booleana obtenida de tomar el conjunto potencia de algún conjunto finito \(X\text{.}\) Necesitaremos algunos lemas y definiciones antes de demostrar este resultado. Sea \(B\) un álgebra Booleana finita. Un elemento \(a \in B\) es un átomo de \(B\) si \(a \neq O\) y \(a \wedge b = a\) o \(a \wedge b = O\) para todo \(b \in B\text{.}\) Equivalentemente, \(a\) es un átomo de \(B\) si no existe \(b \in B\) distinto de cero y distinto de \(a\) tal que \(O \preceq b \preceq a\text{.}\)
Sea \(B\) un álgebra Booleana finita. Si \(b\) es un elemento no nulo de \(B\text{,}\) entonces existe un átomo \(a\) en \(B\) tal que \(a \preceq b\text{.}\)
Si \(b\) es un átomo, sea \(a =b\text{.}\) De lo contrario, elija un elemento \(b_1\text{,}\) distinto de \(O\) y de \(b\text{,}\) tal que \(b_1 \preceq b\text{.}\) Estamos seguros que esto es posible ya que \(b\) no es un átomo. Si \(b_1\) es un átomo, entonces estamos listos. Si no, elegimos \(b_2\text{,}\) distinto de \(O\) y de \(b_1\text{,}\) tal que \(b_2 \preceq b_1\text{.}\) Nuevamente, si \(b_2\) es un átomo, sea \(a = b_2\text{.}\) Continuando este proceso, obtenemos una cadena
\begin{equation*} O \preceq \cdots \preceq b_3 \preceq b_2 \preceq b_1 \preceq b. \end{equation*}Como \(B\) es un álgenra Booleana finita, esta cadena debe ser finita. Es decir, para algún \(k\text{,}\) \(b_k\) es un átomo. Sea \(a = b_k\text{.}\)
Sean \(a\) y \(b\) átomos en un álgebra Booleana finita \(B\) tales que \(a \neq b\text{.}\) Entonces \(a \wedge b = O\text{.}\)
Como \(a \wedge b\) es el ínfimo de \(a\) y \(b\text{,}\) sabemos que \(a \wedge b \preceq a\text{.}\) Luego, ya sea \(a \wedge b = a\) o \(a \wedge b = O\text{.}\) Pero, si \(a \wedge b = a\text{,}\) entonces ya sea \(a \preceq b\) o \(a = O\text{.}\) En cualquier caso tenemos una contradicción pues \(a\) y \(b\) son ambos átomos; por lo tanto, \(a \wedge b = O\text{.}\)
Sea \(B\) un álgebra Booleana y \(a, b \in B\text{.}\) Los siguientes enunciados son equivalentes.
\(a \preceq b\text{.}\)
\(a \wedge b' = O\text{.}\)
\(a' \vee b = I\text{.}\)
(1) \(\Rightarrow\) (2). Si \(a \preceq b\text{,}\) entonces \(a \vee b = b\text{.}\) Por lo tanto,
\begin{align*} a \wedge b' & = a \wedge (a \vee b)'\\ & = a \wedge ( a' \wedge b')\\ & = ( a \wedge a') \wedge b'\\ & = O \wedge b'\\ & = O. \end{align*}(2) \(\Rightarrow\) (3). Si \(a \wedge b' = O\text{,}\) entonces \(a' \vee b = (a \wedge b')' = O' = I\text{.}\)
(3) \(\Rightarrow\) (1). Si \(a' \vee b = I\text{,}\) entonces
\begin{align*} a & = a \wedge (a' \vee b) \\ & = (a \wedge a') \vee (a \wedge b)\\ & = O \vee (a \wedge b)\\ & = a \wedge b. \end{align*}Luego, \(a \preceq b\text{.}\)
Sea \(B\) un álgera Booleana y sean \(b\) y \(c\) elementos en \(B\) tales que \(b \not\preceq c\text{.}\) Entonces existe un átomo \(a \in B\) tal que \(a \preceq b\) y \(a \not\preceq c\text{.}\)
Por el Lema 19.20, \(b \wedge c' \neq O\text{.}\) Luego, existe un átomo \(a\) tal que \(a \preceq b \wedge c'\text{.}\) Concluimos que \(a \preceq b\) y \(a \not\preceq c\text{.}\)
Sea \(b \in B\) y sean \(a_1, \ldots, a_n\) los átomos de \(B\) tales que \(a_i \preceq b\text{.}\) Entonces \(b = a_1 \vee \cdots \vee a_n\text{.}\) Más aún, si \(a, a_1, \ldots, a_n\) son átomos de \(B\) tales que \(a \preceq b\text{,}\) \(a_i \preceq b\text{,}\) y \(b = a \vee a_1 \vee \cdots \vee a_n\text{,}\) entonces \(a = a_i\) para algún \(i = 1, \ldots, n\text{.}\)
Sea \(b_1 = a_1 \vee \cdots \vee a_n\text{.}\) Como \(a_i \preceq b\) para cada \(i\text{,}\) sabemos que \(b_1 \preceq b\text{.}\) Si podemos mostrar que \(b \preceq b_1\text{,}\) entonces el lema se cumple por la antisimetría. Supongamos que \(b \not\preceq b_1\text{.}\) Entonces existe un átomo \(a\) tal que \(a \preceq b\) y \(a \not\preceq b_1\text{.}\) Como \(a\) es un átomo y \(a \preceq b\text{,}\) deducimos que \(a = a_i\) para algún \(a_i\text{.}\) Pero esto es imposible pues \(a \preceq b_1\text{.}\) Por lo tanto, \(b \preceq b_1\text{.}\)
Ahora supongamos que \(b = a_1 \vee \cdots \vee a_n\text{.}\) Si \(a\) es un átomo menor que \(b\text{,}\)
\begin{equation*} a = a \wedge b = a \wedge( a_1 \vee \cdots \vee a_n ) = (a \wedge a_1) \vee \cdots \vee ( a \wedge a_n ). \end{equation*}Pero cada término es \(O\) o \(a\) con \(a \wedge a_i\) solo para un \(a_i\text{.}\) Luego, por el Lema 19.19, \(a = a_i\) para algún \(i\text{.}\)
Sea \(B\) un ágebra Booleana finita. Entonces existe un conjunto \(X\) tal que \(B\) es isomorfo a \({\mathcal P}(X)\text{.}\)
Mostraremos que \(B\) es isomorfo a \({\mathcal P}(X)\text{,}\) donde \(X\) es el conjunto de átomos de \(B\text{.}\) Sea \(a \in B\text{.}\) Por el Lema 19.22, podemos escribir \(a\) de forma única como \(a = a_1 \vee \cdots \vee a_n\) para \(a_1, \ldots, a_n \in X\text{.}\) Concluimos que es posible definir una función \(\phi : B \rightarrow {\mathcal P}(X)\) por
\begin{equation*} \phi(a) = \phi( a_1 \vee \cdots \vee a_n ) = \{a_1, \ldots, a_n \}. \end{equation*}Claramente, \(\phi\) es sobre.
Ahora sean \(a = a_1 \vee \cdots \vee a_n\) y \(b = b_1 \vee \cdots \vee b_m\) elementos en \(B\text{,}\) donde cada \(a_i\) y cada \(b_i\) es un átomo. Si \(\phi(a) = \phi(b)\text{,}\) entonces \(\{a_1, \ldots, a_n \} = \{b_1, \ldots, b_m \}\) y \(a = b\text{.}\) Concluimos que \(\phi\) es inyectiva.
El supremo de \(a\) y \(b\) es preservado por \(\phi\) pues
\begin{align*} \phi(a \vee b) & = \phi( a_1 \vee \cdots \vee a_n \vee b_1 \vee \cdots \vee b_m )\\ & = \{ a_1, \ldots, a_n, b_1, \ldots, b_m \}\\ & = \{ a_1, \ldots, a_n \} \cup \{ b_1, \ldots, b_m \}\\ & = \phi( a_1 \vee \cdots \vee a_n ) \cup \phi( b_1 \wedge \cdots \vee b_m )\\ & = \phi(a) \cup \phi(b). \end{align*}Similarmente, \(\phi( a \wedge b ) = \phi(a) \cap \phi(b)\text{.}\)
Dejaremos la demostración del siguiente corolario como un ejercicio.
El orden de cualquier álgebra Booleana finita es \(2^n\) para algún entero positivo \(n\text{.}\)