2.1
Aljabar Boolean
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)
(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.
Fungsi Boolean
·
Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan
dari Bn ke B melalui ekspresi Boolean, kita
menuliskannya sebagai
f
: Bn ® B
yang dalam hal ini Bn adalah himpunan yang
beranggotakan pasangan terurut ganda-n (ordered n-tuple) di dalam
daerah asal B.
·
Setiap ekspresi Boolean
tidak lain merupakan fungsi Boolean.
·
Misalkan sebuah fungsi
Boolean adalah
f(x, y, z) = xyz + x’y
+ y’z
Fungsi f memetakan
nilai-nilai pasangan terurut ganda-3
(x, y, z) ke
himpunan {0, 1}.
Contohnya, (1, 0, 1) yang berarti x
= 1, y = 0, dan z = 1
sehingga f(1, 0, 1) = 1 × 0 × 1 + 1’ × 0 + 0’× 1 = 0 + 0 + 1 = 1 .
Contoh-contoh
fungsi Boolean yang lain:
1. f(x)
= x
2. f(x,
y) = x’y + xy’+ y’
3. f(x,
y) = x’ y’
4. f(x,
y) = (x + y)’
5. f(x,
y, z) = xyz’
·
Setiap peubah di dalam
fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal.
Contoh: Fungsi h(x, y,
z) = xyz’ pada contoh di atas terdiri dari 3 buah literal, yaitu x, y, dan z’.
Contoh. Diketahui
fungsi Booelan f(x, y, z) = xy
z’, nyatakan h dalam tabel
kebenaran.
Penyelesaian:
|
X
|
y
|
z
|
f(x,
y, z) = xy z’
|
|
0
0
0
0
1
1
1
1
|
0
0
1
1
0
0
1
1
|
0
1
0
1
0
1
0
1
|
0
0
0
0
0
0
1
0
|
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 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)
Komentar
Posting Komentar