2  Retículos y álgebras de Boole

2.1 Conjuntos parcialmente ordenados

En la Capítulo 1 se ha estudiado el concepto general de relación y las propiedades que determinan las relaciones de orden. Las relaciones de orden proporcionan el modelo matemático para describir comparaciones entre elementos de un conjunto, generalizando las nociones de “menor o igual”, “precedencia” o “jerarquía”. En la vida cotidiana y en diversas disciplinas, encontramos ejemplos de ordenaciones: en un conjunto de personas, podemos establecer comparaciones basadas en la estatura, la edad, el salario, etc., lo que induce relaciones de orden entre los individuos. En la organización de tareas, las dependencias entre ellas definen un orden parcial, donde algunas tareas deben completarse antes que otras, pero puede haber tareas independientes que no están relacionadas en el orden.

Ejemplo 2.1  

• Conjunto potencia con la relación de inclusión: Si \(S\) es un conjunto cualquiera, el par \((\mathcal{P}(S), \subseteq)\) es un conjunto parcialmente ordenado. La relación de inclusión \(\subseteq\) es reflexiva (todo conjunto está incluido en sí mismo), antisimétrica (si \(A \subseteq B\) y \(B \subseteq A\), entonces \(A = B\)) y transitiva (si \(A \subseteq B\) y \(B \subseteq C\), entonces \(A \subseteq C\)). En general, \((\mathcal{P}(S), \subseteq)\) no es totalmente ordenado, a menos que \(S\) tenga como mucho un elemento. Por ejemplo, si \(S = \{1, 2\}\), \(\mathcal{P}(S) = \{\varnothing, \{1\}, \{2\}, \{1, 2\}\}\). Observamos que \(\{1\} \not\subseteq \{2\}\) y \(\{2\} \not\subseteq \{1\}\), por lo que la relación no es conexa.

• Conjuntos numéricos con el orden usual: La relación “\(\leq\)” en los conjuntos numéricos \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\) y \(\mathbb{R}\) es una relación de orden total. En cada caso, “\(\leq\)” es reflexiva, antisimétrica, transitiva y conexa. Por ejemplo, \((\mathbb{R}, \leq)\) es un conjunto totalmente ordenado.

• Números naturales con la relación de divisibilidad: La relación de divisibilidad (\({|}\)) en el conjunto de los números naturales \(\mathbb{N}\) (o en \(\mathbb{Z}^+\)) es una relación de orden parcial. Es reflexiva (todo número se divide a sí mismo), antisimétrica (si \(a {|} b\) y \(b {|} a\), entonces \(a = b\) para números naturales) y transitiva (si \(a {|} b\) y \(b {|} c\), entonces \(a {|} c\)). Sin embargo, \((\mathbb{N}, {|})\) no es totalmente ordenado. Por ejemplo, \(2 \not{|} 3\) y \(3 \not{|} 2\).

Es habitual utilizar símbolos como \(\leq\), \(\preceq\) o \(\sqsubseteq\) para representar relaciones de orden, escribiéndolos de forma infija: \(x \preceq y\). Cuando trabajamos con un conjunto ordenado \((A, \preceq)\) y se cumple \(x \preceq y\), decimos que \(x\) es anterior o precede a \(y\), o que \(y\) es posterior o supera a \(x\). Si además \(x \preceq y\) y \(x \neq y\), escribimos \(x \prec y\) para indicar que \(x\) es estrictamente anterior a \(y\).

Los conjuntos parcialmente ordenados finitos pueden representarse gráficamente mediante diagramas de Hasse, que son grafos dirigidos simplificados que facilitan la visualización de la relación de orden. La construcción de un diagrama de Hasse se basa en las siguientes simplificaciones:

Hasse

1. Omisión de bucles (reflexividad): Dado que la relación de orden es reflexiva, todo elemento \(a\) está relacionado consigo mismo (\(a \preceq a\)). En el diagrama, esto se representaría con un bucle en cada vértice. Para simplificar la representación, se omiten todos los bucles en los diagramas de Hasse, ya que la reflexividad se asume implícitamente.

2. Omisión de aristas transitivas (transitividad): Si \(a \preceq b\) y \(b \preceq c\), entonces por transitividad \(a \preceq c\). En el grafo, esto implicaría la existencia de aristas \((a, b)\), \((b, c)\) y \((a, c)\). Para simplificar, se omiten las aristas que se deducen por transitividad. Es decir, si existen caminos “más largos” que implican la relación, se elimina la arista “directa”.

3. Omisión de direcciones (antisimetría y convención ascendente): Dado que la relación de orden es antisimétrica, no puede haber pares de elementos distintos \(a, b\) tales que \(a \preceq b\) y \(b \preceq a\). En el grafo, esto significa que no habrá pares de vértices unidos por dos aristas en sentidos opuestos. Para indicar la dirección del orden, se adopta la convención de dibujar los diagramas de forma ascendente: si \(x \preceq y\), el vértice que representa a \(x\) se dibuja a un nivel inferior que el vértice que representa a \(y\). De esta forma, se pueden omitir las puntas de flecha en las aristas, ya que la dirección del orden se indica por la posición vertical relativa de los vértices.

En resumen, un diagrama de Hasse de un conjunto parcialmente ordenado \((A, \preceq)\) es un grafo donde:

• Los vértices representan los elementos de \(A\).
• Se dibuja una arista ascendente desde \(x\) hasta \(y\) si y solo si \(y\) es un sucesor inmediato de \(x\), es decir, \(x \prec y\) y no existe ningún elemento \(z \in A\) tal que \(x \prec z \prec y\).

Los diagramas de Hasse son especialmente útiles para visualizar conjuntos parcialmente ordenados finitos e incluso algunos conjuntos infinitos numerables, particularmente cuando cada elemento tiene un número finito de sucesores inmediatos.

Definición 2.1 Sean \(x\) e \(y\) elementos de un conjunto parcialmente ordenado \((A, \preceq)\). Decimos que \(y\) es un sucesor inmediato de \(x\) si \(x \preceq y\), \(x \neq y\) (es decir, \(x \prec y\)) y no existe ningún elemento \(z\in A\) tal que \(x \prec z \prec y\).

Ejemplo 2.2 Si \(n>1\) es un número natural, denotamos por \(D_n\) al conjunto de sus divisores positivos, \[ D_n=\{ m \in \mathbb{Z}^+ \mid m \text{ divide a } n\} \] y por \(\mathcal{D}_n=(D_n,|\) al correspondiente conjunto ordenado con la relación de divisibilidad. Por ejemplo, para \(n=30\), \(D_{30}=\{1, 2, 3, 5, 6, 10, 15, 30\}\), y \(\mathcal{D}_{30}=(D_{30},|)\). El diagrama de Hasse de la relación de divisibilidad en \(\mathcal{D}_{30}\) se muestra en la siguiente figura.

En el diagrama de Hasse de \(\mathcal{D}_{30}\):

• El elemento mínimo es 1 (en la parte inferior).
• El elemento máximo es 30 (en la parte superior).
• Los elementos minimales (que no tienen elementos por debajo, aparte de sí mismos) son únicamente 1.
• Los elementos maximales (que no tienen elementos por encima, aparte de sí mismos) son 30.
• Los sucesores inmediatos de 1 son 2, 3, 5.
• Los sucesores inmediatos de 2 son 6, 10.
• Los sucesores inmediatos de 3 son 6, 15.
• Los sucesores inmediatos de 5 son 10, 15.
• Los sucesores inmediatos de 6 son 30.
• Los sucesores inmediatos de 10 son 30.
• Los sucesores inmediatos de 15 son 30.
• Los elementos 12 y 20 no están en \(\mathcal{D}_{30}\) porque no son divisores de 30.

Consideremos ahora métodos para construir nuevas relaciones de orden a partir de relaciones de orden dadas. Dos métodos importantes son el orden producto y el orden lexicográfico.

Ejemplo 2.3 Si \((A, \preceq_1)\) y \((B, \preceq_2)\) son dos conjuntos parcialmente ordenados, podemos definir en el producto cartesiano \(A \times B\) la relación producto \(\preceq\) como: \[ (x_1, y_1) \preceq (x_2, y_2) \quad\Longleftrightarrow\quad x_1 \preceq_1 x_2 \quad \text{y} \quad y_1 \preceq_2 y_2. \] Esta relación \(\preceq\) es una relación de orden parcial en \(A \times B\). Para verificarlo, comprobamos las propiedades:

• Reflexividad: Para todo \((x, y) \in A \times B\), se cumple \(x \preceq_1 x\) y \(y \preceq_2 y\) (por reflexividad de \(\preceq_1\) y \(\preceq_2\)), luego \((x, y) \preceq (x, y)\).
• Antisimetría: Si \((x_1, y_1) \preceq (x_2, y_2)\) y \((x_2, y_2) \preceq (x_1, y_1)\), entonces \(x_1 \preceq_1 x_2\) y \(y_1 \preceq_2 y_2\), y también \(x_2 \preceq_1 x_1\) y \(y_2 \preceq_2 y_1\). Por antisimetría de \(\preceq_1\) y \(\preceq_2\), se tiene \(x_1 = x_2\) e \(y_1 = y_2\), luego \((x_1, y_1) = (x_2, y_2)\).
• Transitividad: Si \((x_1, y_1) \preceq (x_2, y_2)\) y \((x_2, y_2) \preceq (x_3, y_3)\), entonces \(x_1 \preceq_1 x_2\) e \(y_1 \preceq_2 y_2\), y también \(x_2 \preceq_1 x_3\) e \(y_2 \preceq_2 y_3\). Por transitividad de \(\preceq_1\) y \(\preceq_2\), se tiene \(x_1 \preceq_1 x_3\) e \(y_1 \preceq_2 y_3\), luego \((x_1, y_1) \preceq (x_3, y_3)\).

Por ejemplo, si consideramos \(A=B=\mathbb{R}\) con la relación de orden habitual “\(\leq\)”, la relación producto en \(\mathbb{R}\times \mathbb{R} = \mathbb{R}^2\) se define como: \[ (x_1, y_1) \preceq (x_2, y_2) \quad\Longleftrightarrow\quad x_1 \leq x_2 \quad \text{y} \quad y_1 \leq y_2. \] En este orden producto en \(\mathbb{R}^2\), \((2,1) \preceq (3,5)\) ya que \(2 \leq 3\) y \(1 \leq 5\). Sin embargo, \((2,5) \not\preceq (3, 1)\) porque aunque \(2 \leq 3\), no se cumple \(5 \leq 1\). De hecho, en este caso, \((3, 1) \not\preceq (2,5)\) tampoco, ya que aunque \(1 \leq 5\), no se cumple \(3 \leq 2\). Esto ilustra que, aunque “\(\leq\)” es una relación de orden total en \(\mathbb{R}\), su extensión al orden producto en \(\mathbb{R} \times \mathbb{R}\) no es una relación de orden total. En el orden producto, elementos como \((2,5)\) y \((3, 1)\) son incomparables.

Consideremos ahora el conjunto \(\mathbb{B}=\{0,1\}\) con la relación de orden \(\preceq\) dada por \(0\preceq 0\), \(0\preceq 1\), \(1\preceq 1\) (que coincide con el orden usual \(\leq\) en \(\{0, 1\}\)). Los siguientes diagramas de Hasse representan los conjuntos \(\mathbb{B}\), \(\mathbb{B}^2 = \mathbb{B} \times \mathbb{B}\), \(\mathbb{B}^3 = \mathbb{B} \times \mathbb{B} \times \mathbb{B}\) utilizando el orden producto.

En estos diagramas:

• \(\mathbb{B}\) es una cadena de dos elementos.
• \(\mathbb{B}^2\) es un retículo cuadrado de 4 elementos.
• \(\mathbb{B}^3\) es un cubo de 8 elementos.

Ejemplo 2.4 Si \((A, \preceq_1)\) y \((B, \preceq_2)\) son dos conjuntos parcialmente ordenados, se define el orden lexicográfico \(\sqsubseteq\) en el producto cartesiano \(A \times B\) como: \[ (x_1, y_1) \sqsubseteq (x_2, y_2) \quad\Longleftrightarrow\quad (x_1 \prec_1 x_2) \quad \text{o bien} \quad (x_1 = x_2 \quad \text{y} \quad y_1 \preceq_2 y_2). \] En palabras, \((x_1, y_1)\) es lexicográficamente anterior a \((x_2, y_2)\) si \(x_1\) es anterior a \(x_2\) en \(A\), o si \(x_1\) es igual a \(x_2\) y \(y_1\) es anterior o igual a \(y_2\) en \(B\). El orden lexicográfico generaliza el orden alfabético de las palabras en un diccionario.

La relación \(\sqsubseteq\) es una relación de orden parcial en \(A \times B\). Además, si \(\preceq_1\) es un orden total en \(A\) y \(\preceq_2\) es un orden total en \(B\), entonces el orden lexicográfico \(\sqsubseteq\) es un orden total en \(A \times B\).

El orden lexicográfico se extiende de forma natural al producto cartesiano de \(n\) conjuntos ordenados \(A_1 \times A_2 \times \dots \times A_n\) y al conjunto \(A^*\) de las listas (o cadenas) finitas de elementos de un conjunto ordenado \(A\). Por ejemplo, el orden alfabético de las palabras en un diccionario es un orden lexicográfico en el conjunto de cadenas de letras.

Dentro de los conjuntos parcialmente ordenados, podemos identificar elementos con propiedades especiales, que nos ayudan a describir la estructura del orden.

Definición 2.2 Sea \((A, \preceq)\) un conjunto parcialmente ordenado y \(B \subseteq A\) un subconjunto de \(A\).

• Se dice que \(c \in A\) es cota superior de \(B\) si \(c\) es posterior o igual a todos los elementos de \(B\): para todo \(x\in B\), \(x\preceq c\). Denotamos por \(\mathop{CS}(B)\) al conjunto de todas las cotas superiores de \(B\).

• Se dice que \(c \in A\) es cota inferior de \(B\) si \(c\) es anterior o igual a todos los elementos de \(B\): para todo \(x\in B\), \(c\preceq x\). Denotamos por \(\mathop{CI}(B)\) al conjunto de todas las cotas inferiores de \(B\).

• Se dice que \(M \in A\) es la mínima cota superior o supremo de \(B\), si \(M\) es la menor de todas las cotas superiores de \(B\): \(M\in \mathop{CS}(B)\) y para todo \(x\in \mathop{CS}(B)\), \(M\preceq x\). Si el supremo de \(B\) existe, se denota por \(\sup(B)\).

• Se dice que \(m \in A\) es la máxima cota inferior o ínfimo de \(B\), si \(m\) es la mayor de todas las cotas inferiores de \(B\): \(m\in \mathop{CI}(B)\) y para todo \(x\in \mathop{CI}(B)\), \(x\preceq m\). Si el ínfimo de \(B\) existe, se denota por \(\inf(B)\).

• Se dice que \(M \in B\) es maximal en \(B\) si no existe ningún elemento de \(B\) estrictamente posterior a \(M\): no existe \(x\in B\) tal que \(M \prec x\).

• Se dice que \(m \in B\) es minimal en \(B\) si no existe ningún elemento de \(B\) estrictamente anterior a \(m\): no existe \(x\in B\) tal que \(x \prec m\).

• Se dice que \(M \in B\) es máximo de \(B\) si \(M\) es un elemento de \(B\) posterior o igual a todos los elementos de \(B\): \(M\in B\) y para todo \(x\in B\), \(x\preceq M\). Si el máximo de \(B\) existe, se denota por \(\mathrm{m\acute{a}x}(B)\).

• Se dice que \(m \in B\) es mínimo de \(B\) si \(m\) es un elemento de \(B\) anterior o igual a todos los elementos de \(B\): \(m\in B\) y para todo \(x\in B\), \(m\preceq x\). Si el mínimo de \(B\) existe, se denota por \(\mathrm{m\acute{i}n}(B)\).

Un subconjunto \(B\) de un conjunto parcialmente ordenado \((A, \preceq)\) puede tener varias cotas superiores o inferiores, y también puede tener varios elementos maximales o minimales. Sin embargo, si existen, el supremo, el ínfimo, el máximo y el mínimo son únicos.

Teorema 2.1 Sea \(B\) un subconjunto de un conjunto parcialmente ordenado \((A,\preceq)\).

• Si existe el supremo de \(B\), entonces es único.
• Si existe el ínfimo de \(B\), entonces es único.
• Si existe el máximo de \(B\), entonces es único.
• Si existe el mínimo de \(B\), entonces es único.

Prueba. Demostraremos la unicidad del supremo. Las demostraciones para ínfimo, máximo y mínimo son análogas.

Supongamos que \(s_1\) y \(s_2\) son supremos de \(B\). Como \(s_1\) es supremo, es una cota superior de \(B\), por lo que para todo \(x \in B\), \(x \preceq s_1\). Análogamente, \(s_2\) es supremo, y también es cota superior de \(B\), por lo que para todo \(x \in B\), \(x \preceq s_2\).

Ahora, como \(s_1\) es supremo, es la mínima de las cotas superiores de \(B\). Como \(s_2\) es una cota superior de \(B\), debe ser que \(s_1 \preceq s_2\). Recíprocamente, como \(s_2\) es supremo (mínima cota superior), y \(s_1\) es una cota superior, debe ser que \(s_2 \preceq s_1\).

Tenemos entonces que \(s_1 \preceq s_2\) y \(s_2 \preceq s_1\). Por la propiedad de antisimetría de la relación de orden \(\preceq\), se concluye que \(s_1 = s_2\). Por lo tanto, el supremo de \(B\), si existe, es único.

Dado un conjunto parcialmente ordenado \((A, \preceq)\), a menudo es útil encontrar una relación de orden total \(\ll\) que sea “compatible” con \(\preceq\). Esto significa buscar un orden total \(\ll\) que extienda el orden parcial \(\preceq\), en el sentido de que si \(x \preceq y\), entonces \(x \ll y\). El proceso de construir tal relación de orden total \(\ll\) se denomina ordenación topológica. La existencia de una ordenación topológica se basa en el siguiente lema:

Lema 2.1 Si \((A, \preceq)\) es un conjunto parcialmente ordenado, finito y no vacío, entonces \(A\) tiene al menos un elemento minimal.

Prueba. Sea \(A\) un conjunto parcialmente ordenado finito y no vacío. Consideremos una cadena descendente en \(A\), es decir, una secuencia de elementos \(a_1 \succeq a_2 \succeq a_3 \succeq \dots\). Dado que \(A\) es finito, cualquier cadena descendente no puede ser infinitamente larga (no puede haber infinitos elementos distintos en la cadena, debido a la antisimetría). Por lo tanto, toda cadena descendente debe terminar en algún elemento \(a_k\) que no tiene ningún elemento estrictamente anterior a él en la cadena. Este elemento \(a_k\) es un elemento minimal de \(A\).

Alternativamente, podemos considerar un algoritmo para encontrar un elemento minimal: Comenzamos eligiendo un elemento cualquiera \(x_1 \in A\). Si \(x_1\) es minimal, hemos terminado. Si no, existe algún \(x_2 \in A\) tal que \(x_2 \prec x_1\). Si \(x_2\) es minimal, hemos terminado. Si no, existe \(x_3 \in A\) tal que \(x_3 \prec x_2\), y así sucesivamente. Como \(A\) es finito y la relación \(\prec\) es antisimétrica, este proceso no puede continuar indefinidamente sin repetir elementos (de hecho, no puede repetir ningún elemento, ya que \(x_{i+1} \prec x_i\) implica \(x_{i+1} \neq x_i\)). Por lo tanto, en algún momento debemos llegar a un elemento \(a_k\) que sea minimal, es decir, que no tenga ningún elemento estrictamente anterior a él en \(A\).

El algoritmo de ordenación topológica utiliza este lema para construir un orden total compatible con un orden parcial dado en un conjunto finito:

1. Elegir un elemento minimal \(a_1 \in A\). Como \(A\) es finito y no vacío, por el lema anterior, existe al menos un elemento minimal. Si hay varios elementos minimales, se elige uno arbitrariamente.

2. Eliminar el elemento elegido y considerar el conjunto restante \(A_1 = A - \{a_1\}\). Si \(A_1\) no es vacío, también es un conjunto parcialmente ordenado finito y no vacío (con la relación de orden restringida de \(A\)). Por el lema, \(A_1\) tiene al menos un elemento minimal. Elegimos un elemento minimal \(a_2 \in A_1\). Definimos \(a_1 \ll a_2\).

3. Repetir el proceso: Continuamos eliminando el elemento minimal elegido en el paso anterior y seleccionando un elemento minimal del conjunto restante. En el paso \(k\), habiendo elegido \(a_1, a_2, \dots, a_{k-1}\), elegimos un elemento minimal \(a_k\) del conjunto \(A_{k-1} = A - \{a_1, a_2, \dots, a_{k-1}\}\). Definimos \(a_{k-1} \ll a_k\).

4. Terminación: Este proceso continúa hasta que se hayan elegido todos los elementos de \(A\). Dado que \(A\) es finito, el proceso terminará en un número finito de pasos, digamos \(n = |A|\) pasos, generando una secuencia \(a_1, a_2, \dots, a_n\) que contiene todos los elementos de \(A\). Se define la relación \(\ll\) como el orden dado por esta secuencia: \(a_1 \ll a_2 \ll \dots \ll a_n\).

El orden \(\ll\) así definido es un orden total en \(A\). Además, es compatible con el orden parcial inicial \(\preceq\), en el sentido de que si \(x \preceq y\), entonces \(x \ll y\). Esto se debe a que en el algoritmo siempre elegimos elementos minimales en cada paso. Si \(a_i \prec a_j\) en el orden parcial \(\preceq\), entonces necesariamente tendremos que elegir \(a_i\) antes que \(a_j\) en la secuencia \(\ll\), ya que \(a_i\) es minimal en un conjunto que contiene a \(a_j\) (o a un elemento anterior en la cadena descendente que lleva a \(a_j\)). Por lo tanto, si \(a_i \prec a_j\), entonces \(a_i \ll a_j\).

Ejemplo 2.5 Consideremos el conjunto parcialmente ordenado \(A = \{2, 4, 5, 10, 12, 20 \}\) con la relación de divisibilidad, cuyo diagrama de Hasse se mostró anteriormente. Vamos a construir una ordenación topológica de \(A\).

1. Primer elemento: Los elementos minimales de \(A\) son 2 y 5. Elegimos arbitrariamente \(a_1 = 5\).

2. Segundo elemento: Eliminamos 5 de \(A\), obteniendo \(A_1 = A - \{5\} = \{2, 4, 10, 12, 20\}\). Los elementos minimales de \(A_1\) son 2. Elegimos \(a_2 = 2\). Tenemos \(5 \ll 2\).

3. Tercer elemento: Eliminamos 2 de \(A_1\), obteniendo \(A_2 = A_1 - \{2\} = \{4, 10, 12, 20\}\). Los elementos minimales de \(A_2\) son 4 y 10. Elegimos arbitrariamente \(a_3 = 10\). Tenemos \(5 \ll 2 \ll 10\).

4. Cuarto elemento: Eliminamos 10 de \(A_2\), obteniendo \(A_3 = A_2 - \{10\} = \{4, 12, 20\}\). El único elemento minimal de \(A_3\) es 4. Elegimos \(a_4 = 4\). Tenemos \(5 \ll 2 \ll 10 \ll 4\).

5. Quinto elemento: Eliminamos 4 de \(A_3\), obteniendo \(A_4 = A_3 - \{4\} = \{12, 20\}\). Los elementos minimales de \(A_4\) son 12 y 20. Elegimos arbitrariamente \(a_5 = 20\). Tenemos \(5 \ll 2 \ll 10 \ll 4 \ll 20\).

6. Sexto elemento: Eliminamos 20 de \(A_4\), obteniendo \(A_5 = A_4 - \{20\} = \{12\}\). El único elemento minimal de \(A_5\) es 12. Elegimos \(a_6 = 12\). Tenemos \(5 \ll 2 \ll 10 \ll 4 \ll 20 \ll 12\).

Hemos obtenido la ordenación topológica total: \(5 \ll 2 \ll 10 \ll 4 \ll 20 \ll 12\). En forma de lista, esta ordenación es \([5, 2, 10, 4, 20, 12]\).

Es importante observar que la ordenación topológica no es única, ya que en cada paso, si existen varios elementos minimales, podemos elegir cualquiera de ellos. Por ejemplo, en el paso 1, podríamos haber elegido 2 en lugar de 5. En el paso 3, podríamos haber elegido 4 en lugar de 10. En el paso 5, podríamos haber elegido 12 en lugar de 20. En consecuencia, existen múltiples ordenaciones topológicas posibles para un mismo conjunto parcialmente ordenado. Por ejemplo, otra ordenación topológica válida para \(\mathcal{D}_{30}\) sería \(2 \ll 4 \ll 12 \ll 5 \ll 10 \ll 20\), correspondiente a la lista \([2, 4, 12, 5, 10, 20]\). Ambas ordenaciones (y otras posibles) son órdenes totales compatibles con la relación de divisibilidad en \(A\).

2.2 Retículos

Vemos ahora un tipo importante de conjunto ordenado, los retículos.

Definición 2.3 Se dice que un conjunto parcialmente ordenado \((L, \preceq)\) es un retículo (ordenado) si cada par de elementos \(x, y \in L\) tiene supremo e ínfimo en \(L\), es decir, si \(\sup\{x, y\},\inf\{x, y\}\in L\).

Un retículo se dice completo si todo subconjunto \(X\subseteq L\) tiene supremo e ínfimo \(\sup(X) \in L\), \(\inf(X)\in L\).

Podemos definir operadores binarios para el supremo y el ínfimo de dos elementos. Se denotan usualmente por \(\sqcup\) o \(\vee\) (para el supremo) y \(\sqcap\) o \(\wedge\) (para el ínfimo): \[\begin{align*} x \vee y = x \sqcup y = & \sup \{x, y\} \\ x \wedge y = x \sqcap y = & \inf \{x, y\} \end{align*}\]

Ejemplo 2.6 Aquí tenemos tres conjuntos parcialmente ordenados. Los dos primeros son retículos: el primero de ellos se denomina diamante; el segundo, pentágono. El tercer poset no es retículo, pues no existe el ínfimo de \(a\) y \(c\).

Ejemplo 2.7 Son siempre retículos ordenados:

• \((\mathcal{D}_n, |)\) y \((\mathbb{Z}^+, |)\), donde \(\sqcup \equiv \mathrm{mcm}\) y \(\sqcap \equiv \mathrm{mcd}\).

• Dado un conjunto \(S\), \((\mathcal{P}(S), \subseteq)\), donde \(\sqcup \equiv \cup\) y \(\sqcap \equiv \cap\).

2.2.1 Retículos algebraicos

Estudiemos los retículos desde un punto de vista más algebraico.

Teorema 2.2 Sea \((L, \le)\) un retículo ordenado. Entonces, sus operadores supremo e ínfimo, \(\sqcup\) y \(\sqcap\), verifican las siguientes propiedades:

1. Propiedad conmutativa: \(x \sqcup y = y\sqcup x\), \(x \sqcap y = y\sqcap x\).
2. Propiedad asociativa: \(x \sqcup (y \sqcup z) = (x \sqcup y)\sqcup z\), \(x \sqcap (y \sqcap z) = (x \sqcap y)\sqcap z\).
3. Propiedad de absorción: \(x \sqcup (x \sqcap y) = x\), \(x \sqcap (x \sqcup y) = x\).
4. Propiedad de idempotencia: \(x \sqcup x = x\), \(x \sqcap x = x\).

Definición 2.4 Un conjunto \(L\) dotado de dos operadores \(\sqcup\) y \(\sqcap\) se denomina retículo algebraico si dichos operadores verifican las propiedades 1 a 4 del teorema anterior. Se denotará como \((L, \sqcup, \sqcap)\).

Teorema 2.3 Todo retículo ordenado es algebraico y todo retículo algebraico es ordenado.

Para la primera parte, es la definición junto con el teorema de la diapositiva anterior. Para la segunda parte, dado \((L, \sqcup, \sqcap)\) algebraico, podemos definir un orden \(\le\) en \(L\) de forma que \((L, \le)\) es un retículo ordenado: \[x \le y \Longleftrightarrow x \sqcup y = y \qquad \big(\Longleftrightarrow x \sqcap y = x\big)\]

En este caso, los operadores supremo e ínfimo del nuevo retículo ordenado coinciden con \(\sqcup\) y \(\sqcap\).

2.2.2 Subretículos

Definición 2.5 Sea \((L, \sqcup, \sqcap)\) un retículo y \(M\subseteq L\). Decimos que \(M\) es un subretículo de \(L\) si para todo \(x,y \in M,\) se tiene que \(x \sqcup y \in M\), y \(x \sqcap y \in M\).

Ejemplo 2.8 El retículo de la izquierda es \((\mathcal{D}_{36}, |)\). Podemos comprobar que los otros dos retículos mostrados son subretículos.

Estudiemos ahora los siguientes conjuntos ordenados:

Tomando como referencia el retículo de la izquierda, si nos preguntamos si el central es subretículo, la respuesta debería ser inmediata: el poset central no es ni siquiera retículo.

El poset de la derecha es un retículo, pero no es subretículo de \((\mathcal{D}_{36}, |)\), pues \[\sup\{2,3\} = 6\not\in \mathcal M_4.\]

2.2.3 Isomorfismo de retículos

Introducimos ahora la idea de isomorfismo.

Definición 2.6 Sean \((L_1, \preceq_1)\) y \((L_2, \preceq_2)\) dos retículos y \(f \colon L_1 \to L_2\) una aplicación biyectiva. \(f\) es un isomorfismo de retículos si y solo si \[f(x \sqcup_1 y) = f(x) \sqcup_2 f(y),\qquad\ f(x \sqcap_1 y) = f(x) \sqcap_2 f(y)\] o, equivalentemente, \[x \preceq_1 y \ \Longleftrightarrow \ f(x) \preceq_2 f(y),\quad \text{ para todo } x,y\in L_1\]

Dos retículos isomorfos son idénticos algebraicamente y como conjuntos ordenados y, por lo tanto, sus diagramas de Hasse sólo se diferenciarán en las etiquetas de los vértices.

Ejemplo 2.9 A continuación, presentamos \((\mathcal{D}_{30}, |)\) y \(\mathcal{P}(\{a, b, c\})\):

\((\mathcal{D}_{30}, |)\) y \(\mathcal{P}(\{a, b, c\})\) son isomorfos. Por ejemplo, con el isomorfismo: \[\begin{multline*} f(1)=\varnothing,\\ f(2)=\{a\},\quad f(3)=\{b\},\quad f(5)=\{c\},\\ f(6)=\{a,b\},\quad f(10)=\{a,c\},\quad f(15)=\{b,c\},\\ f(30)=\{a,b,c\} \end{multline*}\]

2.2.4 Elementos irreducibles

Vamos ahora a buscar un subconjunto muy destacado dentro de un retículo: un conjunto suficientemente grande para que nos identifique perfectamente el retículo, pero suficientemente pequeño para que sea manejable.

Definición 2.7 Un elemento \(x \in L\) de un retículo se dice que es \(\sqcup\)-irreducible o sup-irreducible si no se puede expresar como el supremo de otros elementos (distintos a él), es decir:

Si \(x = y\sqcup z\), entonces o bien \[x = y\quad\text{o bien}\quad x = z.\]

Ejemplo 2.10 Veamos cuáles son los elementos \(\sqcup\)-irreducibles en el retículo de los divisores de 20.

\(2\), \(4\) y \(5\) son irreducibles porque cada uno de ellos no se puede expresar como el supremo de dos elementos distintos al mismo.

Ejercicio 2.1 Encontrar los elementos \(\sqcup\)-irreducibles de \((\mathcal{D}_{60}, |)\)

Teorema 2.4 Un elemento \(x\in L\) es \(\sqcup\)-irreducible es sucesor inmediato de exactamente un elemento.

Ejemplo 2.11 Los elementos \(\sqcup\)-irreducibles de \((\mathcal{D}_{60}, |)\) son \(2\), \(3\), \(4\) y \(5\).

En general, en \((\mathcal{D}_n, |)\), los \(\sqcup\)-irreducibles son los elementos potencia de un número primo.

Teorema 2.5 Cada elemento \(x\ne\bot\) de un retículo finito se puede expresar como supremos de elementos \(\sqcup\)-irreducibles: \(x = d_1 \sqcup d_2 \sqcup \dots \sqcup d_t\) tales que \(d_i\not\preceq d_j\) para cada para \(i,j\) (es decir, no hay elementos redundantes).

Por lo general, la expresión descrita en el teorema anterior no tiene por qué ser única.

\[ \begin{array}{ll} f &= c \sqcup d = c \sqcup e = d \sqcup e = \\ & = c \sqcup d \sqcup e \\ h & = g \sqcup c = g \sqcup d = g \sqcup e\\ & = g \sqcup b = g \sqcup c \sqcup d = \ldots\\ & = {\color{red}g \sqcup b \sqcup c}\quad(\text{cuidado,}\quad b \preceq c) \end{array}\]

2.3 Tipos de retículos

2.3.1 Retículos distributivos

Buscamos tipos de retículos que verifiquen las propiedades que solemos tener en otras “álgebras”.

Definición 2.8 Se dice que el retículo \((L, \sqcup, \sqcap )\) es distributivo si para cada \(x, y, z \in L\) se verifica \[\begin{array}{rcl} x \sqcap ( y \sqcup z ) & = &(x \sqcap y) \sqcup ( x \sqcap z) \\ x \sqcup ( y \sqcap z ) & = & (x \sqcup y) \sqcap ( x \sqcup z) \end{array}\]

Ejemplo 2.12  

• Para cada conjunto \(S\), \((\mathcal P (S), \cup, \cap)\) es un retículo distributivo.

• Para cada \(n\in\mathbb{Z}^+\), \((\mathcal{D}_{n}, \mathrm{mcm}, \mathrm{mcd})\) es un retículo distributivo.

• Ni el diamante ni el pentágono son distributivos.

El diamante no es distributivo, ya que los siguientes resultados son distintos: \[\begin{array}{rcccl} a \sqcap ( b \sqcup c ) & = & a \sqcap 1& = & a \\ (a \sqcap b) \sqcup ( a \sqcap c) & = & 0 \sqcup 0 & = & 0 \end{array}\]

El pentágono tampoco es distributivo porque los siguientes resultados son distintos: \[\begin{array}{rcccl} a \sqcup ( b \sqcap c ) & = & a \sqcup 0 & = & a \\ (a \sqcup b) \sqcap ( a \sqcup c) & = & b \sqcap 1& = & b \end{array}\]

Proposición 2.1 Todo subretículo de un retículo distributivo es también distributivo.

Teorema 2.6 Un retículo es no distributivo si y sólo si contiene un subretículo isomorfo al diamante o al pentágono.

Ejemplo 2.13  

El subretículo \(\{a,b,d,e,g\}\) es isomorfo al pentágono. Luego el retículo no es distributivo.

Teorema 2.7 Sea \((L, \sqcup, \sqcap )\) un retículo distributivo y sean \(x,y,z \in L\) tales que \[x \sqcup y = x \sqcup z \qquad \text{y} \qquad x \sqcap y = x \sqcap z\] Entonces \(y = z\).

Para poder simplificar la \(x\) en el teorema anterior, es necesario que se den 3 condiciones:

1. El retículo debe ser distributivo.
2. Condición para el supremo: \(x \sqcup y = x \sqcup z\).
3. Condición para el ínfimo: \(x \sqcap y = x \sqcap z\).

2.3.2 Retículos acotados

El siguiente tipo de retículo nos ayudará a encontrar elementos neutros para las operaciones de supremo e ínfimo.

Definición 2.9 Sea \(\mathcal{L}=(L, \preceq)\) un retículo.

Se llama mínimo, primer elemento o bottom de \(\mathcal{L}\) al elemento, si existe, que es anterior a todo elemento del retículo, y se denota por \(0\) o por \(\bot\).

Se llama máximo, último elemento, o top de \(\mathcal{L}\) al elemento, si existe, que es posterior a todo elemento del retículo, y se denota por \(1\) o \(\top\).

Decimos que un retículo es acotado si tiene primer y último elemento.

Proposición 2.2 Todo retículo finito es acotado.

Ejemplo 2.14  

• Para cada conjunto \(S\), \(\big(\mathcal{P}(S), \subseteq \big)\) es retículo acotado, siendo \(\varnothing\) su mínimo y \(S\) su elemento máximo. Nota: \(S\) puede ser un conjunto infinito, así pues \((\mathcal{P}(\mathbb{N}), \subseteq)\) es un retículo infinito pero acotado.

• Para todo entero positivo \(n\), \((\mathcal{D}_{n}, |)\) es un retículo acotado, siendo \(1\) su mínimo y \(n\) su elemento máximo.

• \((\mathbb{Z}, \le)\) no es acotado, puesto que no tiene ni primer ni último elemento.

Proposición 2.3 Si \((L, \preceq )\) un retículo acotado, entonces todo elemento \(x\) del retículo verifica: \[\qquad x \sqcup 0 = x, \qquad x \sqcap 0 = 0\] \[\qquad x \sqcap 1 = x, \qquad x \sqcup 1 = 1\]

Definición 2.10 Sea \((L, \preceq)\) un retículo acotado. Se llama átomo a cada elemento que es sucesor inmediato del primer elemento. Se llama superátomo o coátomo a cada elemento cuyo sucesor inmediato es el último elemento.

Ejemplo 2.15  

\[(\mathcal{D}_{20}, |)\]

\[(\mathcal{P}(\{a, b, c\}), \cap, \cup)\]

Los átomos del retículo \(\mathcal{D}_{20}\) son \(2\) y \(5\) y los superátomos son 4 y 10.

En \(\mathcal{P}(\{a, b, c\})\), los átomos son los subconjuntos con un único elemento y los superátomos son los subconjuntos con dos elementos.

Teorema 2.8 Los átomos en un retículo acotado son elementos \(\sqcup\)-irreducibles.

En general, puede haber elementos \(\sqcup\)-irreducibles que no sean átomos.

Por ejemplo, en el retículo \(\mathcal D_{20}\) del ejemplo anterior a este teorema, habíamos visto que 4 es un elemento \(\sqcup\)-irreducible y no es átomo.

2.3.3 Retículos complementados

Por último, necesitamos un tipo de retículo donde podamos hablar de la negación o complemento de un elemento.s

Definición 2.11 Sea \(\mathcal{L}\) un retículo acotado. Decimos que dos elementos del retículo, \(x\), \(y\), son complementarios si \[x \sqcup y = \top \quad \text{ y } \quad x \sqcap y = \bot\] También decimos que \(x\) es complemento de \(y\) y que \(y\) es complemento de \(x\). En particular, \(\top\) y \(\bot\) son complementarios.

Decimos que el retículo es complementado si cada elemento tiene al menos un complemento. Si cada elemento \(x\) tiene un único complemento, lo denotamos por \(\overline{x}\).

La segunda parte de la definición tiene sentido porque en un retículo acotado, un elemento puede no tener complemento, tener un único complemento o puede tener más de un complemento.

Ejemplo 2.16  

\[\mathcal{D}_{12}\]

\[\text{Diamante}\]

En el retículo \(\mathcal{D}_{12}\), los elementos \(2\) y \(6\) no tienen complementos; el único complemento de \(3\) es \(4\), que tiene a \(3\) como único complemento.

En el diamante:

• \(b\) y \(c\) son complementos de \(a\), ya que \(a \sqcup b = \top\), \(a \sqcap b = \bot\), \(a \sqcup c = \top\) y \(a \sqcap c = \bot\).

• \(b\) y \(c\) son complementarios, ya que \(b \sqcup c = \top\) y \(b \sqcap c = \bot\).

2.4 Álgebras de Boole

2.4.1 Definiciones básicas

En este momento, pasamos a la estructura algebraica relacionada con conjuntos ordenados más importante desde el punto de vista de la computación.

Definición 2.12 Un álgebra (o retículo) de Boole:: es un retículo distributivo y complementado.

Notación: En álgebras de Boole genéricas, se utiliza la notación \(+\) y \(\cdot\) para los operadores supremo (\(\sqcup\)) e ínfimo (\(\sqcap\)), respectivamente.

Ejemplo 2.17  

• \(\mathbb B = \{ 0, 1 \}\) con el orden habitual, es un álgebra de Boole, con las operaciones: \(+ = \mathtt{OR}\), \(\cdot = \mathtt{AND}\) y el complemento es: \(\overline 1=0\), \(\overline 0=1\).

• Para cada conjunto \(S\) el conjunto de las partes de \(S\) forma un álgebra de Boole, \(\big(\mathcal{P}(S), \cup, \cap \big)\), en donde el complemento es \(\overline{X} = S - X\).

El producto cartesiano de dos álgebras de Boole también será un álgebra de Boole considerando las operaciones por componentes.

Ejemplo 2.18 Las siguientes álgebras de Boole se construyen a partir de \(\mathbb{B}\):

\[\mathbb{B}\]

\[\mathbb{B}^2\]

\[\mathbb{B}^3\]

Definición 2.13 Sea \(\mathcal{A}\) un conjunto no vacío que contiene dos elementos especiales \(0, 1\), \(0 \ne 1\); dos operaciones binarias \(+\) y \(\cdot\) y una operación unaria \(-\). Se dice que \((\mathcal{A}, +, \cdot, -, 0, 1)\) es un álgebra de Boole si para todo \(x,y,z \in \mathcal{A}\) se verifican las siguientes propiedades:

• Asociativa: \(x+ (y + z) = (x +y) + z\), \((x \cdot y) \cdot z = x \cdot (y \cdot z )\)

• Identidad: \(x + 0 = x\), \(x \cdot 1 = x\).

• Conmutativa: \(x+ y = y + x\), \(x\cdot y = y \cdot x\).

• Distributiva: \(x+(y\cdot z) = (x+y)\cdot (x+z)\), \(x\cdot (y+z) = x\cdot y+ x\cdot z\).

• Complemento: \(x + \overline{x} = 1\), \(x \cdot \overline{x} = 0\)

De esta forma, si \((\mathcal{A}, +, \cdot, -, 0, {1})\) es un álgebra de Boole, consideraremos como definida la relación de orden que le dota de la estructura de retículo distributivo y complementado: \[x \preceq y \ \Longleftrightarrow \ x + y = y \ \Longleftrightarrow \ x\cdot y = x\]

Teorema 2.9 En todo álgebra de Boole \((\mathcal{A}, +, \cdot, -, 0, 1)\) se verifican las siguiente propiedades:

• Absorción: \(x + (x \cdot y) = x\), \(x \cdot (x + y) = x\).

• Idempotencia: \(x + x = x\), \(x \cdot x = x\).

• Dominancia: \(x + 1 = 1\), \(0 \cdot x = 0\).

• De Morgan: \((\overline{x + y}) = \overline{x} \cdot \overline{y}\), \(\overline{x \cdot y} = \overline{x} + \overline{y}\).

• Involución: \(\overline{ \overline{x} }= x\).

Todos los conceptos y resultados que hemos visto en la sección correspondiente a retículos son aplicables a las álgebras de Boole, por ejemplo, los conceptos de átomos, superátomos y elementos irreducibles.

2.4.2 Representación en Álgebras de Boole

Este resultado es un caso particular del teorema de representación en retículos finitos.

Lema 2.2 Sea \((\mathcal{A}, +, \cdot, -, 0, 1)\) un álgebra de Boole finita. Si \(b\) es cualquier elemento distinto de \(0\) en \(\mathcal{A},\) y \(a_1, a_2,... , a_k\) son todos los átomos de \(\mathcal{A}\) tales que \(a_i \preceq b,\) entonces \(b = a_1 + a_2 + ... + a_k\) de forma única.

Es decir, en un álgebra de Boole finita, todo elemento se puede expresar como suma de los átomos anteriores a él.

Ejemplo 2.19  

• En el álgebra de Boole \(\mathcal P(\{a, b, c, d, e\})\) cada elemento se expresa como unión de los subconjuntos unitarios contenidos en él. Por ejemplo, \(\{a, c, d \}=\{a\} \cup \{c\} \cup \{d\}\).

• En el álgebra de Boole \(\mathbb{B}^7\), el elemento \((0,1,0,0,1,1,0)\) se expresa como suma de los átomos \((0,1,0,0,0,0,0) +(0,0,0,0,1,0,0) + (0,0,0,0,0,1,0)\).

Del lema de representación se deduce que hay una biyección entre los elementos de un álgebra de Boole y los subconjuntos de sus átomos (que son los únicos irreducibles).

Ejemplo 2.20  

\[\mathcal{D}_{30}\]

\[\varphi \colon \mathcal{D}_{30} \longrightarrow \mathcal{P}(\{2, 3, 5\})\]

\[\begin{array}{rclrcl} \varphi(1) & = & \varnothing & \quad \varphi(2) & = & \{2\} \\ \varphi(3) & = & \{3\} \quad & \varphi(5) & = & \{5\} \\ \varphi(6) & = & \{2, 3\} & \quad \varphi(10) & = & \{2, 5\} \\ \varphi(15) & = & \{3, 5\} \quad & \varphi(30) & = & \{2, 3, 5\} \end{array}\]

2.4.3 Isomorfismos de Álgebras de Boole

Volvemos a fijarnos en los isomorfismos, esta vez de álgebras de Boole, que nos va a permitir saber qué estructura concreta tienen estas álgebras.

Definición 2.14 Sean \((\mathcal{A}, +, \cdot, -, 0, {\Large 1})\) y \((\mathcal{B}, \lor, \land, -, 0, 1)\) dos álgebras de Boole. Un isomorfismo de álgebras de Boole es una aplicación \(\varphi \colon \mathcal{A} \to \mathcal{B}\) que es biyectiva y que verifica, para todo \(x,y\in\mathcal{A}\):

• \(\varphi(x + y) = \varphi(x) \lor \varphi(y)\), y \(\varphi(x \cdot y) = \varphi(x) \land \varphi(y)\).

• \(\varphi(\overline{x}) = \overline{\varphi(y)}\).

La biyección que nos da el lema de representación es un isomorfismo de \(\mathcal{A}\) con \(\mathcal{P}(S)\), en donde \(S\) es el conjunto de átomos de \(\mathcal{A}.\)

Ejemplo 2.21 El álgebra \((\mathcal{D}_{30}, \mathrm{mcm}, \mathrm{mcd}, -, 1, 30)\) es isomorfa a \((\mathcal{P}(\{2,3,5\}), \cup, \cap, -, \varnothing, \{2,3,5\})\)

Teorema 2.10 Toda álgebra de Boole finita \((\mathcal{A}, +, \cdot, -, 0, 1)\) es isomorfa al álgebra de Boole \((\mathcal{P}(S), \cup, \cap, -, \varnothing, S)\), donde \(S\) es el conjunto de átomos de \(\mathcal{A}\).

Como consecuencia, se deduce que el cardinal de un álgebra de Boole con \(n\) átomos es igual al cardinal de \(\mathcal{P}(S)\), es decir, \(2^n\) (siendo \(S\) el conjunto de los átomos de \(\mathcal{A}\)).

2.5 Funciones Booleanas

2.5.1 Definiciones básicas

Pasamos a estudiar funciones donde las variables o argumentos son elementos de una álgebra de Boole.

Definición 2.15 Una función booleana de \(n\) variables es cualquier función \[ f\colon \mathbb B^n\to \mathbb B \] El conjunto de todas las aplicaciones booleanas se denota por \(\mathcal{F}_n\) o por \(\mathcal{F}\big(\mathbb{B}^n, \mathbb{B}\big)\).

Las funciones booleanas se pueden usar para representar los requerimientos de salida de un circuito para todos los posibles valores de entrada dados por voltajes indicadores 0, 1.

Para definir una función \(f\colon \mathbb B^3 \to \mathbb B\), se puede usar una tabla como sigue: \[ \begin{array}{|c|c|c|c|c|} x_1 & x_2 & x_3 & f(x_1, x_2, x_3) \\ \hline 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \end{array} \]

Para una función de \(n\) variables hay que definir la salida (\(0\) o \(1\)) de las \(2^n\) posibles entradas. Luego podemos definir \(2^{2^n}\) funciones booleanas distintas. Es decir, \[| \mathcal{F}\big(\mathbb{B}^n, \mathbb{B}\big) | = 2^{2^{n}}\]

Teorema 2.11 \(\mathcal{F}\big(\mathbb{B}^n, \mathbb{B}\big)\) es un álgebra de Boole con las operaciones:

• Suma: \[(f + g)(x_1,x_2, \dots , x_n) = f(x_1,x_2, \dots , x_n) + g(x_1,x_2, \dots , x_n)\]

• Producto: \[(f \cdot g)(x_1,x_2, \dots , x_n) = f(x_1,x_2, \dots , x_n) \cdot g(x_1,x_2, \dots , x_n)\]

• Complemento: \[\overline{f}(x_1, \dots , x_n) = \overline{f(x_1, \dots , x_n)}\]

Los átomos de \(\mathcal{F}\big(\mathbb{B}^n, \mathbb{B}\big)\) son las funciones que sólo valen 1 para una combinación concreta de las entradas: \(f(a_1, \ldots, a_n) = 1\) para un \((a_1, \ldots, a_n)\) concreto, y \(f(x_1, \ldots, x_n) = 0\) si \((x_1,\ldots,x_n) \ne (a_1, \ldots, a_n)\).

Por el teorema de representación de álgebras de Boole, todas las demás funciones booleanas se pueden poner como suma de estas funciones.

Una forma alternativa de entender una función booleana es la siguiente.

Definición 2.16 Una expresión booleana es una expresión en la que intervienen una o varias variables y los operadores binarios (\(+\), \(\cdot\)) o monario (\(-\)) de las álgebras de Boole.

Por ejemplo, \[ E_1(x,y,z) = \overline {x}\cdot z + \overline {x}\cdot y + \overline {z},\qquad E_2(x,y,z) = x\cdot \overline{(z + \overline {x}\cdot y)} + y\cdot \overline {z} \] son expresiones booleanas.

Naturalmente, cada expresión booleana define una función booleana y decimos que dos expresiones son equivalentes si son iguales como funciones, es decir, \(E_1(x_1,x_2, ... ,x_n)=E_2(x_1,x_2, ... ,x_n)\) si \[ E_1(b_1,b_2, ... ,b_n)=E_2(b_1,b_2, ... ,b_n),\text{ para todo } b_i\in\{0,1\} \]

Ejemplo 2.22 Consideremos la función \(f \colon \mathbb B^3 \to \mathbb B\) definida por la siguiente tabla: \[ \begin{array}{|l|l|} \hline f(0,0,0)=1 &f(1,0,0)= 0 \\ f(0,0,1)= 0 &f(1,0,1)= 0 \\ f(0,1,0)= 1 &f(1,1,0)= 0 \\ f(0,1,1)= 0 &f(1,1,1)= 1 \\ \hline \end{array} \] Si nos fijamos en las salidas iguales a 1, y cada entrada 0 identificamos con \(\overline{x}_i\), y cada entrada 1 la identificamos con \(x_i\), construiríamos la siguiente igualdad: \[ f(x_1,x_2,x_3)=(\overline{x}_1 \cdot \overline{x}_2 \cdot \overline{x}_3) + (\overline{x}_1 \cdot x_2 \cdot \overline{x}_3) + (x_1 \cdot x_2 \cdot x_3) \] Basta sustituir cada una de las ocho posibles entradas para verificar la igualdad.

También podemos fijarnos en las salidas iguales a 0 e identificar cada entrada 0 con \(x_i\) y cada entrada 1 con \(\overline{x}_i\) para construir la siguiente igualdad: \[\begin{align*} f(x_1,x_2,x_3) = & \, (x_1 + x_2 + \overline{x}_3) \cdot (x_1 + \overline{x}_2 + \overline{x}_3 ) \cdot (\overline{x}_1 + x_2 + x_3) \cdot\\ & \cdot (\overline{x}_1 + x_2 + \overline{x}_3) \cdot (\overline{x}_1 + \overline{x}_2 + x_3) \end{align*}\]

Nuevamente, basta sustituir cada una de las ocho posibles entradas para verificar la igualdad.

En este ejemplo, hemos construido expresiones booleanas que responden a esquemas específicos: suma de productos o productos de sumas, de forma que el operador complemento solo se aplica a variables.

2.5.2 Formas normales

Comencemos con la expresión mínima:

Definición 2.17 Las expresiones booleanas que constan de una única variable o su complemento se llaman literales.

Definición 2.18 Decimos que una expresión booleana de \(n\) variables es un minitérmino si es de la forma \[\ell_1 \cdot \ell_2 \cdot\dots \cdot \ell_n\] en donde cada \(\ell_i\in\{x_i, \overline{x}_i\}\).

Se dice que una expresión booleana está en su forma normal disyuntiva si es una suma de minitérminos.

Ejemplo 2.23  

• La expresión \(x_1\cdot \overline{x}_2\cdot x_3\) es un minitérmino en las tres variables \(x_1, x_2, x_3\). La función correspondiente en \(\mathcal{F}_3\) toma el valor 1 solamente en \((1, 0, 1)\).

• La expresión \(x_1\cdot \overline{x}_3\) es un minitérmino en dos variables \(x_1, x_3\). Pero no es un minitérmino en las tres variables \(x_1, x_2, x_3\). La función correspondiente en \(\mathcal{F}_3\) toma el valor 1 en \((1,0,0)\) y en \((1,1,0).\)

• La expresión \(x_1\cdot \overline{x}_2\cdot x_3\cdot \overline{x}_1\) no es un minitérmino ya que involucra a la variable \(x_1\) en más de un literal.

• \((\overline{x}_1 \cdot \overline{x}_2 \cdot \overline{x}_3) + (\overline{x}_1 \cdot x_2 \cdot \overline{x}_3) + (x_1 \cdot x_2 \cdot x_3)\) es una expresión booleana en forma normal disyuntiva, con tres minitérminos.

Definición 2.19 Decimos que una expresión booleana de \(n\) variables es un maxitérmino si es de la forma \[ \ell_1 + \ell_2 +\dots + \ell_n \] en donde cada \(\ell_i\in\{x_i, \overline{x}_i\}\).

Se dice que una expresión booleana está en su forma normal conjuntiva si es un producto de maxitérminos.

1. Tanto en los minitérminos como en los maxitérminos, cada variable aparece exactamente una vez (normal o su complemento).

2. La forma normal disyuntiva es suma de productos.

3. La forma normal conjuntiva es producto de sumas.

Las propiedades fundamentales de las álgebras de Boole permiten transformar cualquier expresión booleana en una forma normal disyuntiva equivalente y en una forma normal conjuntiva equivalente.

Ejemplo 2.24 Vamos obtener una forma normal disyuntiva equivalente a la expresión \[E(x, y, z) =\overline{x\cdot z + y \cdot \overline{z}} + \overline{y}\]

Paso 1: Como es forma normal disyuntiva, transformar en suma de productos. \[\begin{aligned} \overline{x\cdot z + y \cdot \overline{z}} + \overline{y} & = (\overline x+ \overline z) \cdot (\overline y + \overline{\overline z}) + \overline{y} & \text{ (De Morgan)}\\ & = (\overline x+ \overline z) \cdot (\overline y + z ) + \overline{y} & \text{ (Involución)}\\ & = \overline x\cdot \overline y+ \overline x\cdot z + \overline z \cdot \overline y + \overline z \cdot z + \overline{y} & \text{ (Distribución)}\\ & = \overline x\cdot \overline y+ \overline x\cdot z + \overline z \cdot \overline y + \overline{y} & \text{ (Complem. e identidad)}\\ \end{aligned} \]

Paso 2: Algunos sumandos no son minitérminos, puesto que no incluyen a las tres variables. Para completarlos, basta multiplicar los sumandos por \(1 = v+ \overline v\) con las variables \(v\) que falten y aplicar la propiedad distributiva las veces necesarias.

\[\begin{multline*} \overline x\cdot \overline y+ \overline x\cdot z + \overline z \cdot \overline y + \overline{y} = \\ = \overline x\cdot \overline y\cdot(z+\overline z)+ \overline x\cdot z\cdot(y+\overline y) + \overline z \cdot \overline y\cdot(x+\overline x) + \overline{y} \cdot(x+\overline x) \cdot(z+\overline z) = \\ = \overline x\cdot \overline y\cdot z+ \overline x\cdot \overline y\cdot \overline z + \overline x\cdot y\cdot z +\overline x\cdot \overline y\cdot z + x\cdot \overline y\cdot \overline z + \overline x\cdot \overline y\cdot \overline z + x\cdot \overline{y} \cdot z + \overline x\cdot \overline{y} \cdot z + x\cdot \overline{y} \cdot \overline z + \overline x\cdot \overline{y} \cdot \overline z = \\ = \overline x\cdot \overline y\cdot z+ \overline x\cdot \overline y\cdot \overline z + \overline x\cdot y\cdot z + x\cdot \overline y\cdot \overline z + x\cdot \overline{y} \cdot z \end{multline*}\]

En la última igualdad, hemos eliminado los sumandos repetidos (idempotencia).

2.6 Ejercicios

Veamos algunos ejercicios.

Ejercicio 2.2 🔴🔴 Sea \((A, \preceq)\) un conjunto parcialmente ordenado. Demuestra que si \(A\) es finito, entonces todo subconjunto no vacío de \(A\) tiene al menos un elemento maximal y al menos un elemento minimal. ¿Es cierto este resultado si \(A\) es infinito? Da un ejemplo o contraejemplo.

Ejercicio 2.3 🔴 Sea \(D_{12} = \{1, 2, 3, 4, 6, 12\}\) el conjunto de divisores positivos de 12. Considera la relación de divisibilidad \({|}\) en \(D_{12}\).

1. Determina los elementos minimales y maximales de \(D_{12}\) con respecto a la relación de divisibilidad.
2. Determina el mínimo y el máximo de \(D_{12}\) (si existen).
3. Para el subconjunto \(B = \{2, 3, 6\} \subseteq D_{12}\), determina las cotas superiores e inferiores de \(B\), y el supremo e ínfimo de \(B\) (si existen).

Ejercicio 2.4 🔴🔴 Sea \((A, \preceq)\) un conjunto parcialmente ordenado. Una cadena en \(A\) es un subconjunto \(C \subseteq A\) tal que la restricción de \(\preceq\) a \(C\) es un orden total. Una anticadena en \(A\) es un subconjunto \(D \subseteq A\) tal que para cualesquiera \(x, y \in D\) distintos, \(x\) e \(y\) son incomparables.

1. En el conjunto \(\mathcal{D}_{30}\) con la relación de divisibilidad, encuentra una cadena de longitud máxima y una anticadena de tamaño máximo.
2. (Teorema de Dilworth) Demuestra que en un conjunto parcialmente ordenado finito, el tamaño máximo de una anticadena es igual a la longitud mínima de una descomposición de \(A\) en cadenas disjuntas.