Lewati ke konten utama

Bagian 19.2 Aljabar Boolean

Mari kita telaah lebih saksama contoh berupa himpunan kuasa \({\mathcal P}(X)\) dari suatu himpunan \(X\text{.}\) Himpunan kuasa merupakan latis yang terurut oleh inklusi. Berdasarkan definisi himpunan kuasa, unsur terbesar dalam \({\mathcal P}(X)\) adalah \(X\) sendiri dan unsur terkecilnya adalah \(\emptyset\text{,}\) yaitu himpunan kosong. Untuk sebarang himpunan \(A\) dalam \({\mathcal P}(X)\text{,}\) kita mengetahui bahwa \(A \cap X = A\) dan \(A \cup \emptyset = A\text{.}\) Hal ini mengarahkan kita pada definisi berikut untuk latis. Suatu unsur \(I\) dalam poset \(X\) disebut unsur terbesar jika \(a \preceq I\) untuk semua \(a \in X\text{.}\) Suatu unsur \(O\) disebut unsur terkecil dari \(X\) jika \(O \preceq a\) untuk semua \(a \in X\text{.}\)
Misalkan \(A\) berada dalam \({\mathcal P}(X)\text{.}\) Ingat bahwa komplemen dari \(A\) adalah
\begin{equation*} A' = X \setminus A = \{ x : x \in X \text{ dan } x \notin A \}\text{.} \end{equation*}
Kita mengetahui bahwa \(A \cup A' = X\) dan \(A \cap A' = \emptyset\text{.}\) Contoh ini dapat kita perumum untuk latis. Suatu latis \(L\) dengan unsur terbesar \(I\) dan unsur terkecil \(O\) disebut berkomplemen jika untuk setiap \(a \in L\text{,}\) terdapat \(a'\) sedemikian sehingga \(a \vee a' = I\) dan \(a \wedge a' = O\text{.}\)
Dalam suatu latis \(L\text{,}\) operasi biner \(\vee\) dan \(\wedge\) memenuhi hukum komutatif dan asosiatif; namun, keduanya tidak selalu memenuhi hukum distributif
\begin{equation*} a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ); \end{equation*}
Akan tetapi, dalam \({\mathcal P}(X)\text{,}\) hukum distributif terpenuhi karena
\begin{equation*} A \cap ( B \cup C ) = (A \cap B ) \cup ( A \cap C ) \end{equation*}
untuk \(A, B, C \in {\mathcal P}(X)\text{.}\) Kita menyebut suatu latis \(L\) distributif jika hukum distributif berikut berlaku:
\begin{equation*} a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c ) \end{equation*}
untuk semua \(a, b, c \in L\text{.}\)

Bukti.
Misalkan \(L\) merupakan latis distributif.
\begin{align*} a \vee ( b \wedge c ) & = [a \vee (a \wedge c) ] \vee ( b \wedge c )\\ & = a \vee [(a \wedge c) \vee ( b \wedge c )]\\ & = a \vee [(c \wedge a) \vee ( c \wedge b )]\\ & = a \vee [c \wedge ( a \vee b )]\\ & = a \vee [( a \vee b ) \wedge c ]\\ & = [( a \vee b ) \wedge a ] \vee [(a \vee b) \wedge c ]\\ & = ( a \vee b ) \wedge ( a \vee c )\text{.} \end{align*}
Arah sebaliknya langsung mengikuti Prinsip Dualitas.
Aljabar Boolean adalah latis \(B\) dengan unsur terbesar \(I\) dan unsur terkecil \(O\) sedemikian sehingga \(B\) bersifat distributif sekaligus berkomplemen. Himpunan kuasa dari \(X\text{,}\) yaitu \({\mathcal P}(X)\text{,}\) menjadi prototipe kita untuk aljabar Boolean. Ternyata, himpunan kuasa juga merupakan salah satu aljabar Boolean yang paling penting. Teorema berikut memungkinkan kita mencirikan aljabar Boolean melalui operasi biner \(\vee\) dan \(\wedge\) tanpa perlu menyebutkan bahwa aljabar Boolean merupakan poset.

Bukti.
Misalkan \(B\) suatu himpunan yang memenuhi (1)–(5) dalam teorema. Salah satu hukum idempoten terpenuhi karena
\begin{align*} a & = a \vee O\\ & = a \vee (a \wedge a')\\ & = (a \vee a) \wedge (a \vee a')\\ & = (a \vee a ) \wedge I\\ & = a \vee a\text{.} \end{align*}
Perhatikan bahwa
\begin{equation*} I \vee b = (b \vee b' ) \vee b = (b' \vee b ) \vee b = b' \vee (b \vee b) = b' \vee b = I\text{.} \end{equation*}
Akibatnya, hukum pertama dari kedua hukum absorpsi berlaku, sebab
\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{align*}
Hukum idempoten dan hukum absorpsi lainnya dibuktikan dengan cara serupa. Karena \(B\) juga memenuhi (1)–(3), syarat-syarat dalam Teorema 19.1.14 terpenuhi; oleh karena itu, \(B\) harus merupakan latis. Syarat (4) memberi tahu kita bahwa \(B\) merupakan latis distributif.
Untuk \(a \in B\text{,}\) berlaku \(O \vee a = a\text{;}\) dengan demikian, \(O \preceq a\) dan \(O\) merupakan unsur terkecil dalam \(B\text{.}\) Untuk menunjukkan bahwa \(I\) merupakan unsur terbesar dalam \(B\text{,}\) terlebih dahulu kita akan menunjukkan bahwa \(a \vee b = b\) ekuivalen dengan \(a \wedge b = a\text{.}\) Karena \(a \vee I = a\) untuk semua \(a \in B\text{,}\) dengan menggunakan hukum absorpsi kita dapat menentukan bahwa
\begin{equation*} a \vee I =(a \wedge I) \vee I = I \vee ( I \wedge a) = I \end{equation*}
atau \(a \preceq I\) untuk semua \(a\) dalam \(B\text{.}\) Akhirnya, karena berdasarkan (5) kita mengetahui bahwa \(B\) berkomplemen, \(B\) harus merupakan aljabar Boolean.
Sebaliknya, misalkan \(B\) merupakan aljabar Boolean. Misalkan \(I\) dan \(O\) masing-masing merupakan unsur terbesar dan terkecil dalam \(B\text{.}\) Jika kita mendefinisikan \(a \vee b\) dan \(a \wedge b\) sebagai batas atas terkecil dan batas bawah terbesar dari \(\{ a, b\}\text{,}\) maka \(B\) merupakan aljabar Boolean berdasarkan Teorema 19.1.14, Teorema 19.2.1, dan hipotesis kita.
Banyak identitas lain berlaku dalam aljabar Boolean. Beberapa di antaranya dicantumkan dalam teorema berikut.

Bukti.
Kita hanya akan membuktikan (2). Identitas-identitas lainnya diserahkan sebagai latihan. Untuk \(a \vee b = a \vee c\) dan \(a \wedge b = a \wedge c\text{,}\) kita memperoleh
\begin{align*} b & = b \vee (b \wedge a)\\ & = b \vee (a \wedge b)\\ & = b \vee (a \wedge c)\\ & = ( b \vee a) \wedge ( b \vee c)\\ & = ( a \vee b) \wedge ( b \vee c)\\ & = ( a \vee c) \wedge ( b \vee c)\\ & = ( c \vee a ) \wedge ( c\vee b )\\ & = c \vee (a \wedge b)\\ & = c \vee ( a \wedge c )\\ & = c \vee ( c \wedge a )\\ & = c\text{.} \end{align*}

Subbagian 19.2.1 Aljabar Boolean Hingga

Suatu aljabar Boolean disebut aljabar Boolean hingga jika sebagai himpunan ia memuat sejumlah hingga unsur. Aljabar Boolean hingga sangat menyenangkan untuk dipelajari karena kita dapat mengklasifikasikannya hingga isomorfisma.
Misalkan \(B\) dan \(C\) merupakan aljabar Boolean. Suatu pemetaan bijektif \(\phi : B \rightarrow C\) disebut isomorfisma aljabar Boolean jika
\begin{align*} \phi( a \vee b ) & = \phi(a) \vee \phi(b)\\ \phi( a \wedge b ) & = \phi(a) \wedge \phi(b) \end{align*}
untuk semua \(a\) dan \(b\) dalam \(B\text{.}\)
Kita akan menunjukkan bahwa setiap aljabar Boolean hingga isomorfik dengan aljabar Boolean yang diperoleh dengan mengambil himpunan kuasa dari suatu himpunan hingga \(X\text{.}\) Sebelum membuktikan hasil ini, kita memerlukan beberapa lema dan definisi. Misalkan \(B\) suatu aljabar Boolean hingga. Suatu unsur \(a \in B\) disebut atom dari \(B\) jika \(a \neq O\) dan \(a \wedge b = a\) untuk semua \(b \in B\) dengan \(b \neq O\text{.}\) Secara ekuivalen, \(a\) merupakan atom dari \(B\) jika tidak terdapat \(b \in B\) dengan \(b \neq O\) yang berbeda dari \(a\) sedemikian sehingga \(O \preceq b \preceq a\text{.}\)

Bukti.
Jika \(b\) merupakan atom, ambil \(a =b\text{.}\) Jika tidak, pilih unsur \(b_1\text{,}\) yang tidak sama dengan \(O\) maupun \(b\text{,}\) sedemikian sehingga \(b_1 \preceq b\text{.}\) Pilihan ini dijamin mungkin karena \(b\) bukan atom. Jika \(b_1\) merupakan atom, pembuktian selesai. Jika tidak, pilih \(b_2\text{,}\) yang tidak sama dengan \(O\) maupun \(b_1\text{,}\) sedemikian sehingga \(b_2 \preceq b_1\text{.}\) Sekali lagi, jika \(b_2\) merupakan atom, ambil \(a = b_2\text{.}\) Dengan melanjutkan proses ini, kita memperoleh suatu rantai
\begin{equation*} O \preceq \cdots \preceq b_3 \preceq b_2 \preceq b_1 \preceq b\text{.} \end{equation*}
Karena \(B\) merupakan aljabar Boolean hingga, rantai ini harus berhingga. Artinya, untuk suatu \(k\text{,}\) \(b_k\) merupakan atom. Ambil \(a = b_k\text{.}\)

Bukti.
Karena \(a \wedge b\) merupakan batas bawah terbesar dari \(a\) dan \(b\text{,}\) kita mengetahui bahwa \(a \wedge b \preceq a\text{.}\) Oleh karena itu, \(a \wedge b = a\) atau \(a \wedge b = O\text{.}\) Akan tetapi, jika \(a \wedge b = a\text{,}\) maka \(a \preceq b\) atau \(a = O\text{.}\) Kedua kemungkinan tersebut menimbulkan kontradiksi karena \(a\) dan \(b\) sama-sama atom; dengan demikian, \(a \wedge b = O\text{.}\)

Bukti.
(1) \(\Rightarrow\) (2). Jika \(a \preceq b\text{,}\) maka \(a \vee b = b\text{.}\) Oleh karena itu,
\begin{align*} a \wedge b' & = a \wedge (a \vee b)'\\ & = a \wedge ( a' \wedge b')\\ & = ( a \wedge a') \wedge b'\\ & = O \wedge b'\\ & = O\text{.} \end{align*}
(2) \(\Rightarrow\) (3). Jika \(a \wedge b' = O\text{,}\) maka \(a' \vee b = (a \wedge b')' = O' = I\text{.}\)
(3) \(\Rightarrow\) (1). Jika \(a' \vee b = I\text{,}\) maka
\begin{align*} a & = a \wedge (a' \vee b)\\ & = (a \wedge a') \vee (a \wedge b)\\ & = O \vee (a \wedge b)\\ & = a \wedge b\text{.} \end{align*}
Jadi, \(a \preceq b\text{.}\)

Bukti.
Berdasarkan Lema 19.2.6, \(b \wedge c' \neq O\text{.}\) Oleh karena itu, terdapat atom \(a\) sedemikian sehingga \(a \preceq b \wedge c'\text{.}\) Akibatnya, \(a \preceq b\) dan \(a \not\preceq c\text{.}\)

Bukti.
Ambil \(b_1 = a_1 \vee \cdots \vee a_n\text{.}\) Karena \(a_i \preceq b\) untuk setiap \(i\text{,}\) kita mengetahui bahwa \(b_1 \preceq b\text{.}\) Jika kita dapat menunjukkan bahwa \(b \preceq b_1\text{,}\) maka lema ini benar berdasarkan antisimetrisitas. Andaikan \(b \not\preceq b_1\text{.}\) Maka terdapat atom \(a\) sedemikian sehingga \(a \preceq b\) dan \(a \not\preceq b_1\text{.}\) Karena \(a\) merupakan atom dan \(a \preceq b\text{,}\) kita dapat menyimpulkan bahwa \(a = a_i\) untuk suatu \(a_i\text{.}\) Namun, hal ini mustahil karena \(a \preceq b_1\text{.}\) Oleh karena itu, \(b \preceq b_1\text{.}\)
Sekarang misalkan \(b = a_1 \vee \cdots \vee a_n\text{.}\) Jika \(a\) merupakan atom yang lebih kecil dari \(b\text{,}\)
\begin{equation*} 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{.} \end{equation*}
Akan tetapi, setiap suku bernilai \(O\) atau \(a\text{,}\) dengan \(a \wedge a_i\) muncul hanya untuk satu \(a_i\text{.}\) Jadi, berdasarkan Lema 19.2.5, \(a = a_i\) untuk suatu \(i\text{.}\)

Bukti.
Kita akan menunjukkan bahwa \(B\) isomorfik dengan \({\mathcal P}(X)\text{,}\) dengan \(X\) sebagai himpunan atom-atom dari \(B\text{.}\) Misalkan \(a \in B\text{.}\) Berdasarkan Lema 19.2.8, kita dapat menuliskan \(a\) secara tunggal sebagai \(a = a_1 \vee \cdots \vee a_n\) untuk \(a_1, \ldots, a_n \in X\text{.}\) Akibatnya, kita dapat mendefinisikan pemetaan \(\phi : B \rightarrow {\mathcal P}(X)\) melalui
\begin{equation*} \phi(a) = \phi( a_1 \vee \cdots \vee a_n ) = \{a_1, \ldots, a_n \}\text{.} \end{equation*}
Jelas bahwa \(\phi\) surjektif.
Sekarang misalkan \(a = a_1 \vee \cdots \vee a_n\) dan \(b = b_1 \vee \cdots \vee b_m\) merupakan unsur-unsur dalam \(B\text{,}\) dengan setiap \(a_i\) dan setiap \(b_i\) merupakan atom. Jika \(\phi(a) = \phi(b)\text{,}\) maka \(\{a_1, \ldots, a_n \} = \{b_1, \ldots, b_m \}\) dan \(a = b\text{.}\) Akibatnya, \(\phi\) injektif.
Gabung dari \(a\) dan \(b\) dipertahankan oleh \(\phi\) karena
\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 \} \cup \{ b_1, \ldots, b_m \}\\ & = \phi( a_1 \vee \cdots \vee a_n ) \cup \phi( b_1 \wedge \cdots \vee b_m )\\ & = \phi(a) \cup \phi(b)\text{.} \end{align*}
Serupa dengan itu, \(\phi( a \wedge b ) = \phi(a) \cap \phi(b)\text{.}\)
Pembuktian korolari berikut diserahkan sebagai latihan.
Sblm.Paling AtasLanjut