Saltar a contenido principal

Sección 19.4 Ejercicios

1.

Dibuje el diagrama del reticulado para el conjunto potencia de \(X = \{ a, b, c, d \}\) con la relación de inclusión conjuntista, \(\subset\text{.}\)

2.

Dibuje el diagrama para el conjunto de enteros positivos que son divisores de 30. ¿Es este conjunto parcialmente ordenado un álgebra Booleana?

3.

Dibuje un diagrama del reticulado de subgrupos de \({\mathbb Z}_{12}\text{.}\)

4.

Sea \(B\) el conjunto de enteros positivos que son divisores de 36. Defina un orden en \(B\) como \(a \preceq b\) si \(a \mid b\text{.}\) Demuestre que \(B\) es un álgebra Booleana. Encuentre un conjunto \(X\) tal que \(B\) es isomorfo a \({\mathcal P}(X)\text{.}\)

5.

Demuestre o refute: \({\mathbb Z}\) es un conjunto parcialmente ordenado por la relación \(a \preceq b\) si \(a \mid b\text{.}\)

Pista

Falso.

6.

Dibuje el circuito de conmutación para cada una de las siguientes expresiones Booleanas.

  1. \((a \vee b \vee a') \wedge a\)

  2. \((a \vee b)' \wedge (a \vee b)\)

  3. \(a \vee (a \wedge b)\)

  4. \((c \vee a \vee b) \wedge c' \wedge (a \vee b)'\)

Pista

(a) \((a \vee b \vee a') \wedge a\)

(c) \(a \vee (a \wedge b)\)

7.

Dibuje un circuito que se cierre exactamente cuando solo uno de los tres interruptores \(a\text{,}\) \(b\text{,}\) o \(c\) esté cerrado.

8.

Demuestre o refute que los dos circuitos mostrados son equivalentes.

Pista

No son equivalentes.

9.

Sea \(X\) un conjunto finito con \(n\) elementos. Demuestre que \({\cal P}(X) = 2^n\text{.}\) Concluya que el orden de cualquier álgebra Booleana finita es \(2^n\) para algún \(n \in {\mathbb N}\text{.}\)

10.

Para cada uno de los siguientes circuitos, escriba una expresión Booleana. Si el circuito puede ser reemplazado por uno con menos interruptores, dé la expresión Booleana y dibuje un diagrama para el nuevo circuito.

Pista

(a) \(a' \wedge [(a \wedge b') \vee b] = a \wedge (a \vee b) \text{.}\)

11.

Demuestre o refute: El conjunto de todos los enteros distintos de cero es un reticulado, donde \(a \preceq b\) se define como \(a \mid b\text{.}\)

12.

Sea \(L\) un conjunto no vacío con dos operaciones binarias \(\vee\) y \(\wedge\) que satisfagan la leyes conmutativa, associativa, idempotente, y de absorción. Podemos definir un orden parcial en \(L\text{,}\) como en el Teorema 19.1.14, por \(a \preceq b\) si \(a \vee b = b\text{.}\) Demuestre que el ínfimo de \(a\) y \(b\) es \(a \wedge b\text{.}\)

13.

Sea \(G\) un grupo y \(X\) el conjunto de subgrupos de \(G\) ordenados por inclusión conjuntista. Si \(H\) y \(K\) son subgrupos de \(G\text{,}\) muestre que el supremo de \(H\) y \(K\) es el subgrupo generado por \(H \cup K\text{.}\)

14.

Sea \(R\) un anillo y suponga que \(X\) es el conjunto de ideales de \(R\text{.}\) Muestre que \(X\) es un conjunto parcialmente ordenado por inclusión, \(\subset\text{.}\) Defina el ínfimo de dos ideales \(I\) y \(J\) en \(X\) como \(I \cap J\) y el supremo de \(I\) y \(J\) como \(I + J\text{.}\) Demuestre que el conjunto de los ideales de \(R\) forma un reticulado bajo estas operaciones.

Pista

Sean \(I, J\) ideales en \(R\text{.}\) Debemos mostrar que \(I + J = \{ r + s : r \in I \text{ y } s \in J \}\) es el menor ideal en \(R\) que contiene tanto a \(I\) como \(J\text{.}\) Si \(r_1, r_2 \in I\) y \(s_1, s_2 \in J\text{,}\) entonces \((r_1 + s_1) + (r_2 + s_2) = (r_1 + r_2) +(s_1 + s_2)\) está en \(I + J\text{.}\) Para \(a \in R\text{,}\) \(a(r_1 + s_1) = ar_1 + as_1 \in I + J\text{;}\) luego, \(I + J\) es un ideal en \(R\text{.}\)

15.

Sea \(B\) un álgebra Booleana. Demuestre cada una de las siguientes identidades.

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

  2. Si \(a \vee b = I\) y \(a \wedge b = O\text{,}\) entonces \(b = a'\text{.}\)

  3. \((a')'=a\) para todo \(a \in B\text{.}\)

  4. \(I' = O\) y \(O' = I\text{.}\)

  5. \((a \vee b)' = a' \wedge b'\) y \((a \wedge b)' = a' \vee b'\) (Leyes de De Morgan).

16.

Dibujando los diagramas apropiados, complete la demostración del Teorema 19.3.6 para mostrar que las funciones de conmutación forman un álgebra Booleana.

17.

Sea \(B\) un álgebra Booleana. Defina operaciones binarias \(+\) y \(\cdot\) en \(B\) como

\begin{align*} a + b & = (a \wedge b') \vee (a' \wedge b)\\ a \cdot b & = a \wedge b. \end{align*}

Demuestre que \(B\) es un anillo conmutativo bajo estas operaciones y que satisface \(a^2 = a\) para todo \(a \in B\text{.}\)

18.

Sea \(X\) un conjunto parcialmente ordenado tal que para todo \(a\) y \(b\) en \(X\text{,}\) ya sea \(a \preceq b\) o \(b \preceq a\text{.}\) Entonces \(X\) es un conjunto totalmente ordenado.

  1. Es \(a \mid b\) un orden total en \({\mathbb N}\text{?}\)

  2. Demuestre que \({\mathbb N}\text{,}\) \({\mathbb Z}\text{,}\) \({\mathbb Q}\text{,}\) y \({\mathbb R}\) son conjuntos totalmente ordenados con el orden usual \(\leq\text{.}\)

Pista

(a) No.

19.

Sean \(X\) e \(Y\) conjuntos parcialmente ordenados. Se dice que una función \(\phi : X \rightarrow Y\) preserva el orden si \(a \preceq b\) implica que \(\phi(a) \preceq \phi(b)\text{.}\) Sean \(L\) y \(M\) reticulados. Una función \(\psi: L \rightarrow M\) es un homomorfismo de reticulados si \(\psi( a \vee b ) = \psi(a) \vee \psi(b)\) y \(\psi( a \wedge b ) = \psi(a) \wedge \psi(b)\text{.}\) Muestre que todo homormorfismo de reticulados preserva el orden, pero que no toda función que preserva el orden es un homomorfismo de reticulados.

20.

Sea \(B\) un álgebra Booleana. Demeustre que \(a = b\) si y solo si \((a \wedge b') \vee ( a' \wedge b) = O\) para todo \(a, b \in B\text{.}\)

Pista

\(( \Rightarrow)\text{.}\) \(a = b \Rightarrow (a \wedge b') \vee (a' \wedge b) = (a \wedge a') \vee (a' \wedge a) = O \vee O = O\text{.}\) \(( \Leftarrow)\text{.}\) \(( a \wedge b') \vee (a' \wedge b) = O \Rightarrow a \vee b = (a \vee a) \vee b = a \vee (a \vee b) = a \vee [I \wedge (a \vee b)] = a \vee [(a \vee a') \wedge (a \vee b)] = [a \vee (a \wedge b')] \vee [a \vee (a' \wedge b)] = a \vee [(a \wedge b') \vee (a' \wedge b)] = a \vee 0 = a\text{.}\) Un argumento simétrico muestra que \(a \vee b = b\text{.}\)

21.

Sea \(B\) un álgebra Booleana. Demuestre que \(a = O\) si y solo si \((a \wedge b') \vee ( a' \wedge b) = b\) para todo \(b \in B\text{.}\)

22.

Sean \(L\) y \(M\) reticulados. Defina un orden en \(L \times M\) por \(( a, b) \preceq (c, d)\) si \(a \preceq c\) y \(b \preceq d\text{.}\) Muestre que \(L \times M\) es un reticulado bajo este orden parcial.