· Misalkan terdapat
- Dua operator biner: + dan ×
- Sebuah operator uner: ’.
- B : himpunan yang didefinisikan pada operator +, ×, dan ’
- 0 dan 1 adalah dua elemen yang berbeda dari B.
Tupel
(B, +, ×, ’)
disebut aljabar Boolean jika untuk setiap a, b, c Î Bberlaku aksioma-aksioma atau postulat Huntington berikut:
1. Closure: (i) a + b Î B
(ii) a × bÎ B
2. Identitas: (i) a + 0 = a
(ii) a × 1 = a
3. Komutatif: (i) a + b = b + a
(ii) a × b= b . a
4. Distributif: (i) a × (b + c) = (a × b) + (a × c)
(ii) a + (b × c) = (a + b) × (a + c)
5. Komplemen[1]: (i) a + a’ = 1
(ii) a × a’ = 0
- Untuk mempunyai sebuah aljabar Boolean, harus diperlihatkan:
1. Elemen-elemen himpunan B,
2. Kaidah operasi untuk operator biner dan operator uner,
3. Memenuhi postulat Huntington.
Aljabar Boolean Dua-Nilai
Aljabar Boolean dua-nilai:
- B = {0, 1}
- operator biner, + dan ×
- operator uner, ’
- Kaidah untuk operator biner dan operator uner:
| a | b | a × b | | a | b | a + b | | a | a’ |
| 0 | 0 | 0 | | 0 | 0 | 0 | | 0 | 1 |
| 0 | 1 | 0 | | 0 | 1 | 1 | | 1 | 0 |
| 1 | 0 | 0 | | 1 | 0 | 1 | | | |
| 1 | 1 | 1 | | 1 | 1 | 1 | | | |
Cek apakah memenuhi postulat Huntington:
1. Closure : jelas berlaku
2. Identitas: jelas berlaku karena dari tabel dapat kita lihat bahwa:
(i) 0 + 1 = 1 + 0 = 1
(ii) 1 × 0 = 0 × 1 = 0
3. Komutatif: jelas berlaku dengan melihat simetri tabel operator biner.
4. Distributif: (i) a × (b + c) = (a × b) + (a × c) dapat ditunjukkan benar dari tabel operator biner di atas dengan membentuk tabel kebenaran:
| a | b | c | b + c | a × (b + c) | a × b | a × c | (a × b) + (a × c) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
(ii) Hukum distributif a + (b × c) = (a + b) × (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengan cara yang sama seperti (i).
1. Komplemen: jelas berlaku karena Tabel 7.3 memperlihatkan bahwa:
(i) a + a‘ = 1, karena 0 + 0’= 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1
(ii) a × a = 0, karena 0 × 0’= 0 × 1 = 0 dan 1 × 1’ = 1 × 0 = 0
- Misalkan (B, +, ×, ’) adalah sebuah aljabar Boolean. Suatu ekspresi Boolean dalam (B, +, ×, ’) adalah:
(i) setiap elemen di dalam B,
(ii) setiap peubah,
(iii) jika e1dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 × e2, e1’ adalah ekspresi Boolean
Contoh:
0
1
a
b
c
a+ b
a× b
a’× (b + c)
a× b’ + a × b × c’ + b’, dan sebagainya
Mengevaluasi Ekspresi Boolean
- Contoh: a’× (b + c)
jika a = 0, b = 1, dan c = 0, maka hasil evaluasi ekspresi:
0’× (1 + 0) = 1 × 1 = 1
- Dua ekspresi Boolean dikatakan ekivalen (dilambangkan dengan ‘=’) jika keduanya mempunyai nilai yang sama untuk setiap pemberian nilai-nilai kepada n peubah.
Contoh:
a × (b + c) = (a . b) + (a × c)
Contoh. Perlihatkan bahwa a + a’b= a + b .
Penyelesaian:
| a | b | a’ | a’b | a + a’b | a + b |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
- Perjanjian: tanda titik (×) dapat dihilangkan dari penulisan ekspresi Boolean, kecuali jika ada penekanan:
(i) a(b+ c) = ab + ac
(ii) a + bc = (a + b) (a + c)
(iii) a × 0 , bukan a0
Prinsip Dualitas
- Misalkan S adalah kesamaan (identity) di dalam aljabar Boolean yang melibatkan operator +, ×, dan komplemen, maka jika pernyataan S* diperoleh dengan cara mengganti
× dengan +
+ dengan ×
0 dengan 1
1 dengan 0
dan membiarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar. S* disebut sebagai dual dari S.
Contoh.
(i) (a × 1)(0 + a’) = 0 dualnya (a + 0) + (1 × a’) = 1
(ii) a(a‘ + b) = ab dualnya a + a‘b = a+ b
Hukum-hukum Aljabar Boolean
| 1. Hukum identitas: (i) a + 0 = a (ii) a × 1 = a | 2. Hukum idempoten: (i) a + a = a (ii) a × a = a |
| 3. Hukum komplemen: (i) a + a’ = 1 (ii) aa’ = 0 | 4. Hukum dominansi: (i) a × 0 = 0 (ii) a + 1 = 1 |
| 5. Hukum involusi: (i) (a’)’ = a | 6. Hukum penyerapan: (i) a + ab = a (ii) a(a + b) = a |
| 7. Hukum komutatif: (i) a + b = b + a (ii) ab = ba | 8. Hukum asosiatif: (i) a + (b + c) = (a + b) + c (ii) a (b c) = (a b) c |
| 9. Hukum distributif: (i) a + (b c) = (a + b) (a + c) (ii) a (b + c) = a b + a c | 10. Hukum De Morgan: (i) (a + b)’ = a’b’ (ii) (ab)’ = a’ + b’ |
| 11. Hukum 0/1 (i) 0’ = 1 (ii) 1’ = 0 |  |
No comments:
Post a Comment