19.2: Álgebras booleanas

Investiguemos\(X\) más de cerca el ejemplo del conjunto\({\mathcal P}(X)\text{,}\) de poder, de un conjunto. El conjunto de potencia es una celosía que está ordenada por inclusión. Por la definición del conjunto de potencia, el elemento más grande en\(X\) sí mismo\({\mathcal P}(X)\) es y el elemento más pequeño es\(\emptyset\text{,}\) el conjunto vacío. Para cualquier conjunto\(A\) en lo\({\mathcal P}(X)\text{,}\) sabemos\(A \cap X = A\) y\(A \cup \emptyset = A\text{.}\) Esto sugiere la siguiente definición para celosías. Un elemento\(I\) en un poset\(X\) es un elemento más grande si\(a \preceq I\) para todos\(a \in X\text{.}\) Un elemento\(O\) es un elemento más pequeño de\(X\) if\(O \preceq a\) for all\(a \in X\text{.}\)

Let\(A\) be in\({\mathcal P}(X)\text{.}\) Recordemos que el complemento de\(A\) es

\[ A' = X \setminus A = \{ x : x \in X \text{ and } x \notin A \}\text{.} \nonumber \]

Eso lo sabemos\(A \cup A' = X\) y\(A \cap A' = \emptyset\text{.}\) podemos generalizar este ejemplo para celosías. Una celosía\(L\) con un elemento más grande\(I\) y un elemento más pequeño\(O\) se complementa si para cada uno\(a \in L\text{,}\) existe una\(a'\) tal que\(a \vee a' = I\) y\(a \wedge a' = O\text{.}\)

En una celosía\(L\text{,}\) las operaciones binarias\(\vee\) y\(\wedge\) satisfacen las leyes conmutativas y asociativas; sin embargo, no necesitan satisfacer la ley distributiva

\[ a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ); \nonumber \]

sin embargo, en\({\mathcal P}(X)\) el derecho distributivo se satisface ya que

\[ A \cap ( B \cup C ) = (A \cap B ) \cup ( A \cap C ) \nonumber \]

para\(A, B, C \in {\mathcal P}(X)\text{.}\) Diremos que una celosía\(L\) es distributiva si se sostiene la siguiente ley distributiva:

\[ a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ) \nonumber \]

para todos\(a, b, c \in L\text{.}\)

Teorema\(19.15\)

Una celosía\(L\) es distributiva si y solo si

\[ a \vee ( b \wedge c ) = ( a \vee b ) \wedge ( a \vee c ) \nonumber \]

para todos\(a, b, c \in L\text{.}\)

Prueba

Supongamos que\(L\) es una celosía distributiva.

\ begin {alinear*} a\ vee (b\ cuña c) & = [a\ vee (a\ cuña c)]\ vee (b\ cuña c)\\ & = a\ vee [(a\ cuña c)\ vee (b\ cuña c)]\\ & = a\ vee [(c\ cuña a)\ vee (c\ cuña b)]\\ & = a\ vee [c\ cuña (a\ vee b)]\\ & = a\ vee [(a\ vee b)\ cuña c]\\ & = [(a\ vee b)\ cuña a]\ vee [(a\ vee b)\ cuña c]\\ & = (a\ vee b)\ cuña (a\ vee c)\ texto {.} \ end {alinear*}

Lo contrario se desprende directamente del Principio de Dualidad.

Un álgebra booleana es una celosía\(B\) con un elemento mayor\(I\) y un elemento más pequeño\(O\) tal que\(B\) es a la vez distributivo y complementado. El conjunto de potencia de\(X\text{,}\)\({\mathcal P}(X)\text{,}\) es nuestro prototipo para un álgebra booleana. Resulta que también es una de las álgebras booleanas más importantes. El siguiente teorema nos permite caracterizar álgebras booleanas en términos de las relaciones binarias\(\vee\) y\(\wedge\) sin mencionar el hecho de que un álgebra booleana es un poset.

Teorema\(19.16\)

Un conjunto\(B\) es un álgebra booleana si y sólo si existen operaciones binarias\(\vee\) y\(\wedge\) en la\(B\) satisfacción de los siguientes axiomas.

1. \(a \vee b = b \vee a\)y\(a \wedge b = b \wedge a\) para\(a, b \in B\text{.}\)

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

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

4. Existen elementos\(I\) y\(O\) tal que\(a \vee O = a\) y\(a \wedge I = a\) para todos\(a \in B\text{.}\)
5. Por cada\(a \in B\) existe\(a' \in B\) tal que\(a \vee a' = I\) y\(a \wedge a' = O\text{.}\)

Prueba

Dejar\(B\) ser un conjunto satisfactorio (1) — (5) en el teorema. Una de las leyes idempotentes está satisfecha desde

\ begin {alinear*} a & = a\ vee O\\ & = a\ vee (a\ cuña a')\\ & = (a\ vee a)\ cuña (a\ vee a')\\ & = (a\ vee a)\ cuña I\\ & = a\ vee a\ text {.} \ end {alinear*}

Observe que

\[ I \vee b = (b \vee b' ) \vee b = (b' \vee b ) \vee b = b' \vee (b \vee b) = b' \vee b = I\text{.} \nonumber \]

En consecuencia, la primera de las dos leyes de absorción sostiene, ya que

\ begin {align*} a\ vee (a\ wedge b) & = (a\ wedge I)\ vee (a\ wedge b)\\ & = a\ wedge (I\ vee b)\\ & = a\ wedge I\\ & = a\ text {.} \ end {alinear*}

Las otras leyes idempotentes y de absorción se prueban de manera similar. Ya que\(B\) también satisface (1) — (3),\(19.14\) se cumplen las condiciones del Teorema; por lo tanto,\(B\) debe ser una celosía. La condición (4) nos dice que\(B\) es una celosía distributiva.

Por\(a \in B\text{,}\)\(O \vee a = a\text{;}\) lo tanto,\(O \preceq a\) y\(O\) es el elemento más pequeño en\(B\text{.}\) Para mostrar que\(I\) es el elemento más grande en primero\(B\text{,}\) mostraremos que\(a \vee b = b\) es equivalente a\(a \wedge b = a\text{.}\) Dado que\(a \vee I = a\) para todos\(a \in B\text{,}\) usando las leyes de absorción podemos determinar que

\[ a \vee I =(a \wedge I) \vee I = I \vee ( I \wedge a) = I \nonumber \]

o\(a \preceq I\) para todos\(a\) en\(B\text{.}\) Finalmente, ya que sabemos que\(B\) se complementa con (5),\(B\) debe ser un álgebra booleana.

Por el contrario, supongamos que\(B\) es un álgebra booleana. Dejar\(I\) y\(O\) ser los elementos más grandes y menos en\(B\text{,}\) respectivamente. Si definimos\(a \vee b\) y\(a \wedge b\) como menos límites superiores y mayores inferiores de\(\{ a, b\}\text{,}\) entonces\(B\) es un álgebra booleana por teorema\(19.14\), teorema\(19.15\), y nuestra hipótesis.

Muchas otras identidades se mantienen en álgebras booleanas. Algunas de estas identidades se enumeran en el siguiente teorema.

Teorema\(19.17\)

\(B\)Déjese ser álgebra booleana. Entonces

1. \(a \vee I = I\)y\(a \wedge O = O\) para todos\(a \in B\text{.}\)

2. Si\(a \vee b = a \vee c\) y\(a \wedge b = a \wedge c\) para\(a, b, c \in B\text{,}\) entonces\(b = c\text{.}\)

3. Si\(a \vee b = I\) y\(a \wedge b = O\text{,}\) entonces\(b = a'\text{.}\)
4. \((a')'=a\)para todos\(a \in B\text{.}\)
5. \(I' = O\)y\(O' = I\text{.}\)
6. \((a \vee b)' = a' \wedge b'\)y\((a \wedge b)' = a' \vee b'\) (Leyes de De Morgan).

Prueba

Demostraremos solamente (2). El resto de las identidades se dejan como ejercicios. Para\(a \vee b = a \vee c\) y\(a \wedge b = a \wedge c\text{,}\) tenemos

\ begin {alinear*} b & = b\ vee (b\ cuña a)\\ & = b\ vee (a\ cuña b)\\ & = b\ vee (a\ cuña c)\\ & = (b\ vee a)\ cuña (b\ vee c)\\ & = (a\ vee b)\ cuña (b\ vee c)\\ & = (a\ vee b)\ vee c)\ cuña (b\ vee c)\\ & = (c\ vee a)\ cuña (c\ vee b)\\ & = c\ vee (a\ cuña b)\\ & = c\ vee (a\ cuña c)\\ & = c\ vee (c\ cuña a)\\ & = c\ texto {.} \ end {alinear*}

Álgebras Booleanas Finitas

Un álgebra booleana es un álgebra booleana finita si contiene un número finito de elementos como conjunto. Los álgebras booleanas finitas son particularmente agradables ya que podemos clasificarlas hasta isomorfismo.

Dejar\(B\) y\(C\) ser álgebras booleanas. Un mapa biyective\(\phi : B \rightarrow C\) es un isomorfismo de álgebras booleanas si

\ begin {align*}\ phi (a\ vee b) & =\ phi (a)\ vee\ phi (b)\\ phi (a\ cuña b) & =\ phi (a)\ phi (a)\ cuña\ phi (b)\ end {alinear*}

para todos\(a\) y\(b\) en\(B\text{.}\)

Mostraremos que cualquier álgebra booleana finita es isomórfica al álgebra booleana obtenida tomando el conjunto de potencias de algún conjunto finito\(X\text{.}\) Necesitaremos algunos lemmas y definiciones antes de probar este resultado. Dejar\(B\) ser un álgebra booleana finita. Un elemento\(a \in B\) es un átomo de\(B\) si\(a \neq O\) y\(a \wedge b = a\) para todos\(b \in B\) con\(b \neq O\text{.}\) Equivalentemente,\(a\) es un átomo de\(B\) si no hay\(b \in B\) con\(b \neq O\) distinto de\(a\) tal que\(O \preceq b \preceq a\text{.}\)

Lema\(19.18\)

Dejar\(B\) ser un álgebra booleana finita. Si\(b\) es un elemento de\(B\) con\(b \neq O\text{,}\) entonces hay un átomo\(a\) en\(B\) tal que\(a \preceq b\text{.}\)

Prueba

Si\(b\) es un átomo, vamos\(a =b\text{.}\) De lo contrario, elegir un elemento\(b_1\text{,}\) no igual\(O\) o\(b\text{,}\) tal que Se\(b_1 \preceq b\text{.}\) nos garantiza que esto es posible ya que no\(b\) es un átomo. Si\(b_1\) es un átomo, entonces ya terminamos. Si no, elige\(b_2\text{,}\) no igual\(O\) o\(b_1\text{,}\) tal que\(b_2 \preceq b_1\text{.}\) De nuevo, si\(b_2\) es un átomo, vamos\(a = b_2\text{.}\) Continuando con este proceso, podemos obtener una cadena

\[ O \preceq \cdots \preceq b_3 \preceq b_2 \preceq b_1 \preceq b\text{.} \nonumber \]

Dado que\(B\) es un álgebra booleana finita, esta cadena debe ser finita. Es decir, para algunos\(k\text{,}\)\(b_k\) es un átomo. Let\(a = b_k\text{.}\)

Lema\(19.19\)

Dejar\(a\) y\(b\) ser átomos en un álgebra booleana finita\(B\) tal que\(a \neq b\text{.}\) Entonces\(a \wedge b = O\text{.}\)

Prueba

Ya que\(a \wedge b\) es el mayor límite inferior de\(a\) y\(b\text{,}\) sabemos que\(a \wedge b \preceq a\text{.}\) Por lo tanto, cualquiera\(a \wedge b = a\) o\(a \wedge b = O\text{.}\) Sin embargo, si\(a \wedge b = a\text{,}\) entonces cualquiera\(a \preceq b\) o\(a = O\text{.}\) en cualquier caso tenemos una contradicción porque\(a\) y\(b\) son ambos átomos; por lo tanto, \(a \wedge b = O\text{.}\)

Lema\(19.20\)

Dejar\(B\) ser un álgebra booleana y\(a, b \in B\text{.}\) Las siguientes declaraciones son equivalentes.

1. \(a \preceq b\text{.}\)
2. \(a \wedge b' = O\text{.}\)
3. \(a' \vee b = I\text{.}\)

Prueba

(1)\(\Rightarrow\) (2). Si\(a \preceq b\text{,}\) entonces\(a \vee b = b\text{.}\) Por lo tanto,

\ begin {alinear*} a\ cuña b' & = a\ cuña (a\ vee b) '\\ & = a\ cuña (a'\ cuña b')\\ & = (a\ cuña a')\ cuña b'\\ & = O\ cuña b'\ & = O\ text {.} \ end {alinear*}

(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\ cuña a')\ vee (a\ cuña b)\\ & = O\ vee (a\ cuña b)\\ & = a\ cuña b\ texto {.} \ end {alinear*}

Por lo tanto,\(a \preceq b\text{.}\)

Lema\(19.21\)

Dejar\(B\) ser un álgebra booleana\(b\) y y\(c\) ser elementos en\(B\) tal que\(b \not\preceq c\text{.}\) Entonces existe un átomo\(a \in B\) tal que\(a \preceq b\) y\(a \not\preceq c\text{.}\)

Prueba

Por Lema\(19.20\),\(b \wedge c' \neq O\text{.}\) Por lo tanto, existe un átomo\(a\) tal que\(a \preceq b \wedge c'\text{.}\) Consecuentemente,\(a \preceq b\) y\(a \not\preceq c\text{.}\)

Lema\(19.22\)

Dejar\(b \in B\) y\(a_1, \ldots, a_n\) ser los átomos de\(B\) tal que\(a_i \preceq b\text{.}\) Entonces\(b = a_1 \vee \cdots \vee a_n\text{.}\) Además, si\(a, a_1, \ldots, a_n\) son átomos de\(B\) tal que\(a \preceq b\text{,}\)\(a_i \preceq b\text{,}\) y\(b = a \vee a_1 \vee \cdots \vee a_n\text{,}\) luego\(a = a_i\) para algunos\(i = 1, \ldots, n\text{.}\)

Prueba

Vamos\(b_1 = a_1 \vee \cdots \vee a_n\text{.}\) Ya que\(a_i \preceq b\) para cada uno\(i\text{,}\) sabemos que\(b_1 \preceq b\text{.}\) si podemos demostrar que\(b \preceq b_1\text{,}\) entonces el lema es cierto por antisimetría. Asumir\(b \not\preceq b_1\text{.}\) Entonces existe un átomo\(a\) tal que\(a \preceq b\) y\(a \not\preceq b_1\text{.}\) Ya que\(a\) es un átomo y\(a \preceq b\text{,}\) podemos deducir que\(a = a_i\) para algunos\(a_i\text{.}\) Sin embargo, esto es imposible ya que\(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{,}\)

\[ a = a \wedge b = a \wedge( a_1 \vee \cdots \vee a_n ) = (a \wedge a_1) \vee \cdots \vee ( a \wedge a_n )\text{.} \nonumber \]

Pero cada término es\(O\) o\(a\) con\(a \wedge a_i\) ocurrir para solo uno\(a_i\text{.}\) Por lo tanto, por Lemma\(19.19\),\(a = a_i\) para algunos\(i\text{.}\)

Teorema\(19.23\)

Dejar\(B\) ser un álgebra booleana finita. Entonces existe un conjunto\(X\) tal que\(B\) es isomórfico para\({\mathcal P}(X)\text{.}\)

Prueba

Mostraremos que\(B\) es isomórfico a\({\mathcal P}(X)\text{,}\) donde\(X\) está el conjunto de átomos de\(B\text{.}\) Let\(a \in B\text{.}\) By Lemma\(19.22\), podemos escribir de\(a\) manera única en\(a = a_1 \vee \cdots \vee a_n\) cuanto a\(a_1, \ldots, a_n \in X\text{.}\) Consecuentemente, podemos definir un mapa\(\phi : B \rightarrow {\mathcal P}(X)\) por

\[ \phi(a) = \phi( a_1 \vee \cdots \vee a_n ) = \{a_1, \ldots, a_n \}\text{.} \nonumber \]

Claramente,\(\phi\) está sobre.

Ahora dejemos\(a = a_1 \vee \cdots \vee a_n\) y\(b = b_1 \vee \cdots \vee b_m\) sean elementos en\(B\text{,}\) donde cada uno\(a_i\) y cada uno\(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{.}\) Consecuentemente,\(\phi\) es inyectivo.

La unión de\(a\) y\(b\) es preservada por\(\phi\) desde

\ 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\}\ copa\ {b_1,\ ldots, b_m\}\\ & =\ phi (a_1\ vee\ cdots\ vee a_n)\ copa\ phi (b_1\ cuña\ cdots\ vee b_m)\\ & =\ phi (a) \ copa\ phi (b)\ texto {.} \ end {alinear*}

Del mismo modo,\(\phi( a \wedge b ) = \phi(a) \cap \phi(b)\text{.}\)

Dejamos como ejercicio la prueba del siguiente corolario.

Corolario\(19.24\)

El orden de cualquier álgebra booleana finita debe ser\(2^n\) para algún entero positivo\(n\text{.}\)