Latihan 19.5 Latihan

1.

Gambarlah diagram latis untuk himpunan kuasa dari $X = \{ a, b, c, d \}$ dengan relasi inklusi himpunan, $\subset\text{.}$

2.

Gambarlah diagram untuk himpunan bilangan bulat positif yang merupakan pembagi dari $30\text{.}$ Apakah poset ini merupakan aljabar Boolean?

Petunjuk.

$Graf dengan 30 pada tingkat teratas yang terhubung ke 10 dan 15 pada tingkat kedua. Tingkat ketiga memuat 2, yang terhubung ke 30 dan 10; 5, yang terhubung ke 10 dan 15; serta 3, yang terhubung ke 15. Tingkat terbawah memuat 1 yang terhubung ke 2, 3, dan 5.$

3.

Gambarlah diagram latis subgrup dari ${\mathbb Z}_{12}\text{.}$

4.

Misalkan $B$ himpunan bilangan bulat positif yang merupakan pembagi dari $210\text{.}$ Definisikan suatu urutan pada $B$ dengan $a \preceq b$ jika $a \mid b\text{.}$ Buktikan bahwa $B$ merupakan aljabar Boolean. Carilah himpunan $X$ sedemikian sehingga $B$ isomorfik dengan ${\mathcal P}(X)\text{.}$

Petunjuk.

Apa saja atom dari $B\text{?}$

5.

Buktikan atau berikan sangkalan: ${\mathbb Z}$ merupakan poset di bawah relasi $a \preceq b$ jika $a \mid b\text{.}$

Petunjuk.

Salah.

6.

Gambarlah rangkaian pensakelaran untuk setiap ekspresi Boolean berikut.

$\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)'$

Petunjuk.

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

$Graf dari kiri ke kanan yang bercabang menjadi tiga lintasan, a, b, dan b’, kemudian bergabung kembali menjadi satu lintasan dan melewati a.$

$Graf dari kiri ke kanan yang bercabang menjadi dua lintasan lalu bergabung kembali. Lintasan atas melewati a kemudian b. Lintasan bawah melewati a.$

7.

Gambarlah rangkaian yang akan tertutup tepat ketika hanya satu dari tiga sakelar $a\text{,}$ $b\text{,}$ dan $c$ tertutup.

8.

Buktikan atau berikan sangkalan bahwa kedua rangkaian yang ditampilkan bersifat ekuivalen.

$Dua graf. Graf di kiri bercabang menjadi tiga lintasan, a-b-c, a’-b, dan a-c’, kemudian bergabung kembali. Graf di kanan bercabang menjadi dua lintasan, a-b dan a-c’, kemudian bergabung kembali.$

Petunjuk.

Tidak ekuivalen.

9.

Misalkan $X$ suatu himpunan hingga yang memuat $n$ unsur. Buktikan bahwa $|{\cal P}(X)| = 2^n\text{.}$ Simpulkan bahwa orde setiap aljabar Boolean hingga harus berbentuk $2^n$ untuk suatu $n \in {\mathbb N}\text{.}$

10.

Untuk setiap rangkaian berikut, tuliskan suatu ekspresi Boolean. Jika rangkaian tersebut dapat diganti dengan rangkaian yang memiliki lebih sedikit sakelar, berikan ekspresi Boolean dan gambarlah diagram rangkaian yang baru.

$Tiga graf. Dari kiri ke kanan, graf atas melewati a’, kemudian bercabang menjadi lintasan atas a-b’ dan lintasan bawah a, lalu bergabung kembali. Graf tengah dari kiri ke kanan bercabang menjadi dua lintasan dengan a pada lintasan atas dan b pada lintasan bawah. Graf kemudian bergabung kembali dan bercabang menjadi tiga lintasan: lintasan atas a-b, lintasan tengah a’, dan lintasan bawah a’-b. Graf kemudian bergabung kembali. Graf bawah bercabang menjadi tiga lintasan: lintasan atas a-b-c, lintasan tengah a’-b’-c, dan lintasan bawah a-b’-c’. Ketiga lintasan kemudian bergabung kembali.$

Petunjuk.

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

11.

Buktikan atau berikan sangkalan: himpunan semua bilangan bulat tak nol merupakan latis, dengan $a \preceq b$ didefinisikan oleh $a \mid b\text{.}$

12.

Misalkan $L$ suatu himpunan tak kosong dengan dua operasi biner $\vee$ dan $\wedge$ yang memenuhi hukum komutatif, asosiatif, idempoten, dan absorpsi. Kita dapat mendefinisikan urutan parsial pada $L\text{,}$ sebagaimana dalam Teorema 19.1.14, dengan $a \preceq b$ jika $a \vee b = b\text{.}$ Buktikan bahwa batas bawah terbesar dari $a$ dan $b$ adalah $a \wedge b\text{.}$

13.

Misalkan $G$ suatu grup dan $X$ himpunan subgrup dari $G$ yang diurutkan oleh inklusi himpunan. Jika $H$ dan $K$ merupakan subgrup dari $G\text{,}$ tunjukkan bahwa batas atas terkecil dari $H$ dan $K$ adalah subgrup yang dibangkitkan oleh $H \cup K\text{.}$

14.

Misalkan $R$ suatu gelanggang dan $X$ himpunan ideal dari $R\text{.}$ Tunjukkan bahwa $X$ merupakan poset yang diurutkan oleh inklusi himpunan, $\subset\text{.}$ Definisikan temu dari dua ideal $I$ dan $J$ dalam $X$ sebagai $I \cap J$ dan gabung dari $I$ dan $J$ sebagai $I + J\text{.}$ Buktikan bahwa himpunan ideal dari $R$ merupakan latis di bawah operasi-operasi ini.

Petunjuk.

Misalkan $I, J$ merupakan ideal dalam $R\text{.}$ Kita perlu menunjukkan bahwa $I + J = \{ r + s : r \in I \text{ dan } s \in J \}$ merupakan ideal terkecil dalam $R$ yang memuat $I$ dan $J\text{.}$ Jika $r_1, r_2 \in I$ dan $s_1, s_2 \in J\text{,}$ maka $(r_1 + s_1) + (r_2 + s_2) = (r_1 + r_2) +(s_1 + s_2)$ berada dalam $I + J\text{.}$ Untuk $a \in R\text{,}$ $a(r_1 + s_1) = ar_1 + as_1 \in I + J\text{;}$ dengan demikian, $I + J$ merupakan ideal dalam $R\text{.}$

15.

Misalkan $B$ suatu aljabar Boolean. Buktikan setiap identitas berikut.

$a \vee I = I$ dan $a \wedge O = O$ untuk semua $a \in B\text{.}$
Jika $a \vee b = I$ dan $a \wedge b = O\text{,}$ maka $b = a'\text{.}$
$(a')'=a$ untuk semua $a \in B\text{.}$
$I' = O$ dan $O' = I\text{.}$
$(a \vee b)' = a' \wedge b'$ dan $(a \wedge b)' = a' \vee b'$ (hukum De Morgan).

16.

Dengan menggambar diagram yang sesuai, lengkapilah pembuktian Teorema 19.3.7 untuk menunjukkan bahwa fungsi pensakelaran membentuk aljabar Boolean.

17.

Misalkan $B$ suatu aljabar Boolean. Definisikan operasi biner $+$ dan $\cdot$ pada $B$ melalui

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

Buktikan bahwa $B$ merupakan gelanggang komutatif di bawah operasi-operasi ini dan memenuhi $a^2 = a$ untuk semua $a \in B\text{.}$

18.

Misalkan $X$ suatu poset sedemikian sehingga untuk setiap $a$ dan $b$ dalam $X\text{,}$ berlaku $a \preceq b$ atau $b \preceq a\text{.}$ Maka $X$ disebut himpunan terurut total.

Apakah $a \mid b$ merupakan urutan total pada ${\mathbb N}\text{?}$
Buktikan bahwa ${\mathbb N}\text{,}$ ${\mathbb Z}\text{,}$ ${\mathbb Q}\text{,}$ dan ${\mathbb R}$ merupakan himpunan terurut total di bawah urutan biasa $\leq\text{.}$

Petunjuk.

(a) Tidak.

19.

Misalkan $X$ dan $Y$ merupakan poset. Suatu pemetaan $\phi : X \rightarrow Y$ disebut mempertahankan urutan jika $a \preceq b$ mengakibatkan $\phi(a) \preceq \phi(b)\text{.}$ Misalkan $L$ dan $M$ merupakan latis. Suatu pemetaan $\psi: L \rightarrow M$ disebut homomorfisma latis jika $\psi( a \vee b ) = \psi(a) \vee \psi(b)$ dan $\psi( a \wedge b ) = \psi(a) \wedge \psi(b)\text{.}$ Tunjukkan bahwa setiap homomorfisma latis mempertahankan urutan, tetapi tidak setiap homomorfisma yang mempertahankan urutan merupakan homomorfisma latis.

20.

Misalkan $B$ suatu aljabar Boolean. Buktikan bahwa $a = b$ jika dan hanya jika $(a \wedge b') \vee ( a' \wedge b) = O$ untuk $a, b \in B\text{.}$

Petunjuk.

$( \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{.}$ Argumen yang simetris menunjukkan bahwa $a \vee b = b\text{.}$

21.

Misalkan $B$ suatu aljabar Boolean. Buktikan bahwa $a = O$ jika dan hanya jika $(a \wedge b') \vee ( a' \wedge b) = b$ untuk semua $b \in B\text{.}$

22.

Misalkan $L$ dan $M$ merupakan latis. Definisikan suatu relasi urutan pada $L \times M$ dengan $( a, b) \preceq (c, d)$ jika $a \preceq c$ dan $b \preceq d\text{.}$ Tunjukkan bahwa $L \times M$ merupakan latis di bawah urutan parsial ini.

Sblm.Paling Atas Lanjut