·
Misalkan terdapat
-
Dua operator biner: + dan ×
-
Sebuah operator uner: ’.
-
B :
himpunan yang didefinisikan pada opeartor +, ×, dan ’
-
0 dan 1 adalah dua elemen yang berbeda dari B.
Tupel
(B,
+, ×, ’)
disebut aljabar Boolean jika untuk setiap a, b,
c Î B berlaku 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).
5. 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
Karena kelima postulat Huntington dipenuhi, maka
terbukti bahwa B = {0, 1} bersama-sama dengan operator biner + dan × operator komplemen ‘ merupakan aljabar
Boolean.
Ekspresi Boolean
·
Misalkan (B, +, ×, ’) adalah sebuah aljabar
Boolean. Suatu ekspresi Boolean dalam (B, +, ×, ’) adalah:
(i) setiap elemen di dalam B,
(ii) setiap peubah,
(iii) jika e1
dan 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
|
|
Contoh 7.3. Buktikan (i) a + a’b = a
+ b
dan (ii) a(a’ + b) = ab
Penyelesaian:
(i) a
+ a’b = (a + ab) + a’b (Penyerapan)
=
a + (ab + a’b) (Asosiatif)
=
a + (a + a’)b (Distributif)
=
a + 1 · b (Komplemen)
=
a + b (Identitas)
(ii) adalah dual dari (i)
No comments:
Post a Comment