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: (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:
Cek apakah
memenuhi postulat Huntington:
1. Closure :
jelas berlaku
2. Identitas: jelas berlaku karena dari tabel
dapat kita lihat bahwa:
1) 0 + 1 = 1 + 0 = 1
2) 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:
(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:
1) a + a‘
= 1, karena 0 + 0’= 0 + 1 = 1 dan 1 + 1’= 1 + 0 = 1
2) 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:
- 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
Contoh 7.3. Buktikan (i) a + a’b = a
+ b
dan (ii) a(a’ + b) = ab
Penyelesaian:
- a + a’b = (a + ab) + a’b (Penyerapan)
- a + a’b = a + (ab + a’b) (Asosiatif)
- a + a’b = a + (a + a’)b (Distributif)
- a + a’b = a + 1 · b (Komplemen)
- a + a’b = a + b (Identitas)
Tidak ada komentar:
Posting Komentar