[skip-to-content]
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\gcd}{\operatorname{mcd}} \renewcommand{\lcm}{\operatorname{mcm}} \renewcommand{\deg}{\operatorname{gr}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Sección19.2Álgebras Booleanas

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{.}\)

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.

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.

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*}

SubsecciónÁlgebras Booleanas Finitas

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{.}\)

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{.}\)

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{.}\)

(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{.}\)

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_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{.}\)

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.