AATA Ejercicios

Exercícios 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?

Dica.

\begin{tikzpicture}[scale=0.7] \node at (0,0) {1}; \node at (0,2) {5}; \node at (0,4) {10}; \node at (0,6) {30}; \node at (-2,2) {2}; \node at (2,2) {3}; \node at (2,4) {15}; \draw (0,0.25) -- (0,1.75); \draw (0,2.25) -- (0,3.75); \draw (0,4.25) -- (0,5.75); \draw (2,2.25) -- (2,3.75); \draw (0.2,0.25) -- (2,1.75); \draw (-0.2,0.25) -- (-2,1.75); \draw (0.2,2.25) -- (1.8,3.75); \draw (-1.8,2.25) -- (-0.2,3.75); \draw (-2,2.25) -- (-0.2,5.75); \draw (2,4.25) -- (0.2,5.75); \end{tikzpicture}

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{.}$

Dica.

Falso.

6.

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

$\displaystyle (a \vee b \vee a') \wedge a$
$\displaystyle (a \vee b)' \wedge (a \vee b)$
$\displaystyle a \vee (a \wedge b)$
$\displaystyle (c \vee a \vee b) \wedge c' \wedge (a \vee b)'$

Dica.

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

\begin{tikzpicture}[scale=0.7] \node at (0,0) {$a'$}; \node at (0,1) {$b$}; \node at (0,2) {$a$}; \node at (4,1) {$a$}; \draw (-3,1) -- (-0.2,1); \draw (0.2,1) -- (3.8,1); \draw (4.2,1) -- (5,1); \draw (-2,1) -- (-2,2) -- (-0.2,2); \draw (-2,1) -- (-2,0) -- (-0.2,0); \draw (0.2,2) -- (2,2) -- (2,1); \draw (0.2,0) -- (2,0) -- (2,1); \end{tikzpicture}

\begin{tikzpicture}[scale=0.7] \node at (0,0) {$a$}; \node at (-1,2) {$a$}; \node at (1,2) {$b$}; \draw (-3,1) -- (-2,1); \draw (2,1) -- (3,1); \draw (-2,1) -- (-2,2) -- (-1.2,2); \draw (-2,1) -- (-2,0) -- (-0.2,0); \draw (1.2,2) -- (2,2) -- (2,1); \draw (0.2,0) -- (2,0) -- (2,1); \draw (-0.8,2) -- (0.8,2); \end{tikzpicture}

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.

\begin{tikzpicture}[scale=0.7,node distance=5mm, text height=1.5ex,text depth=.25ex] \node at (2,1) {$a$}; \node at (3,1) {$b$}; \node at (4,1) {$c$}; \node at (2.5,0) {$a'$}; \node at (3.5,0) {$b$}; \node at (2.5,-1) {$a$}; \node at (3.5,-1) {$c'$}; \draw (1,0) -- (1,1) -- (1.7,1) (2.3,1) -- (2.7,1) (3.3,1) -- (3.7,1) (4.3,1) -- (5,1) -- (5,0); \draw (1,0) -- (1,-1) -- (2.2,-1) (2.8,-1) -- (3.2,-1) (3.8,-1) -- (5,-1) -- (5,0); \draw (0,0) -- (2.2,0) (2.8,0) -- (3.2,0) (3.8,0) -- (6,0); \node at (9,1) {$a$}; \node at (9,-1) {$a$}; \node at (10,1) {$b$}; \node at (10,-1) {$c'$}; \draw (8,0) -- (8,1) -- (8.7,1) (9.3,1) -- (9.7,1) (10.3,1) -- (11,1) -- (11,0); \draw (8,0) -- (8,-1) -- (8.7,-1) (9.3,-1) -- (9.7,-1) (10.3,-1) -- (11,-1) -- (11,0); \draw (7,0) -- (8,0) (11,0) -- (12,0); \end{tikzpicture}

Dica.

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.

\begin{tikzpicture}[scale=0.7,node distance=5mm, text height=1.5ex,text depth=.25ex] \node at (-1,1) {$a$}; \node at (0,1) {$b$}; \node at (1,1) {$c$}; \node at (-1,0) {$a'$}; \node at (0,0) {$b'$}; \node at (1,0) {$c$}; \node at (-1,-1) {$a$}; \node at (0,-1) {$b'$}; \node at (1,-1) {$c'$}; \draw (-2,0) -- (-2,1) -- (-1.3,1) (-0.7,1) -- (-0.3,1) (0.3,1) -- (0.7,1) (1.3,1) -- (2,1) -- (2,0); \draw (-2,0) -- (-2,-1) -- (-1.3,-1) (-0.7,-1) -- (-0.3,-1) (0.3,-1) -- (0.7,-1) (1.3,-1) -- (2,-1) -- (2,0); \draw (-3,0) -- (-1.3,0) (-0.7,0) -- (-0.3,0) (0.3,0) -- (0.7,0) (1.3,0) -- (3,0); \node at (-2,5) {$a$}; \node at (1,5) {$a$}; \node at (2,5) {$b$}; \node at (1.5,4) {$a'$}; \node at (-2,3) {$b$}; \node at (1,3) {$a'$}; \node at (2,3) {$b$}; \draw (-3,4) -- (-3,5) -- (-2.3,5) (-1.7,5) -- (-1,5) -- (-1,4) (0,4) -- (0,5) -- (0.7,5) (1.3,5) -- (1.8,5) (2.3,5) -- (3,5) -- (3,4); \draw (-3,4) -- (-3,3) -- (-2.3,3) (-1.7,3) -- (-1,3) -- (-1,4) (0,4) -- (0,3) -- (0.7,3) (1.3,3) -- (1.8,3) (2.3,3) -- (3,3) -- (3,4); \draw (-4,4) -- (-3,4) (-1,4) -- (1.2,4) (1.8,4) -- (4,4); \node at (-2,8) {$a'$}; \node at (0,9) {$a$}; \node at (1,9) {$b'$}; \node at (0.5,7) {$b$}; \draw (-3,8) -- (-2.3,8) (-1.7,8) -- (-1,8) (2,8) -- (3,8); \draw (-1,8) -- (-1,9) -- (-0.3,9) (0.3,9) -- (0.7,9) (1.3,9) -- (2,9) -- (2,8); \draw (-1,8) -- (-1,7) -- (0.2,7) (0.8,7) -- (2,7) -- (2,8); \end{tikzpicture}

Dica.

(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.

Dica.

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.

$a \vee I = I$ y $a \wedge O = O$ para todo $a \in B\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).

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.

Es $a \mid b$ un orden total en ${\mathbb N}\text{?}$
Demuestre que ${\mathbb N}\text{,}$ ${\mathbb Z}\text{,}$ ${\mathbb Q}\text{,}$ y ${\mathbb R}$ son conjuntos totalmente ordenados con el orden usual $\leq\text{.}$

Dica.

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

Dica.

$( \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.