Aljabar Boolean (Matematika diskrit)

ALJABAR BOOLEAN

1.1 Definisi Aljabar Boolean
Misalkan B adalah himpunan yang didefinisikan pada dua operator biner, + dan ×, dan sebuah operator uner, ’. Misalkan 0 dan 1 adalah dua elemen yang berbeda dari B. Maka, tupel
<B,+, ., ‘,0,1>
disebut aljabar Boolean jika untuk setiap a, b, c Î B berlaku aksioma berikut:
1. Identitas
(i)   a + 0 = a
(ii) a 
× 1 = a

2. Komutatif
(i) a + b = b + a
(ii) a 
× b = b . a

3. Distributif
(i)   a 
× (b + c) = (a × b) + (a × c)
(ii) a + (b 
× c) = (a + b) × (a + c)


4. Komplemen
Untuk setiap a Î B terdapat elemen unik a‘ΠB sehingga
(i)   a + a’ = 1
(ii) a 
× a’ = 0

1.2 Aljabar Boolean Dua-Nilai
·        Merupakan aljabar Boolean yang paling popular, karena aplikasinya luas.
·        Pada aljabar 2-nilai:
(i) B = {0, 1},
(ii) operator biner: + dan ×, operator uner: ’
(iii) Kaidah untuk operator biner dan operator uner:


(iv) Keempat aksioma di atas dipenuhi

1.3 Ekspresi Boolean
Ekspresi Boolean dibentuk dari elemen-elemen B dan/atau peubah-peubah yang dapat dikombinasikan satu sama lain dengan operator +, ×, dan ’.

Contoh :
0
1
a
b
a + b
× b
a’× (b + c)
× b’ + a × b × c’ + b’, dan sebagainya.

1.4 Hukum-hukum Aljabar Boolean
1. Closure:
·                     (i) a + b  B 
·                     (ii) a  b  B 
2. Identitas: 
·                     (i) a + 0 = a 
·                     (ii) a  1 = a
3. Idempoten: 
·                     (i) a + a = a 
·                     (ii) a  a = a
4. Komplemen:
·                     (i) a + a’ = 1 
·                     (ii) aa’ = 0
5. Dominansi: 
·                     (i) a  0 = 0
·                     (ii) a + 1 = 1 
6. Involusi:
·                     (i) (a’)’ = a
7. Penyerapan: 
·                     (i) a + ab = a 
·                     (ii) a(a + b) = a
8. Komutatif: 
·                     (i) a + b = b + a 
·                     (ii) ab = ba
9. Asosiatif:
·                     (i) a + (b + c) = (a + b) + c 
·                     (ii) a (b c) = (a b) c
10 Distributif:
·                     (i) a + (b c) = (a + b) (a + c) 
·                     (ii) a (b + c) = a b + a c
11. De Morgan: 
·                     (i) (a + b)’ = a’b’ 
·                     (ii) (ab)’ = a’ + b’
12. Hukum 0/1:
·                     (i) 0’ = 1 
·                     (ii) 1’ = 0
Contoh :
Buktikan bahwa untuk sembarang elemen a dan b dari aljabar Boolean maka kesamaaan berikut:
a + a’b = a + b dan a(a’ + b) = ab adalah benar.
Penyelesaian:
(i)  a + a’b            = (a + ab) + a’b (Hukum Penyerapan)
= a + (ab + a’b) (Hukum Asosiatif)
= a + (a + a’)b (Hukum Distributif)
= a + 1 × b (Hukum Komplemen)
= a + b (Hukum Identitas)
(ii) a(a’ + b)         = a a’ + ab (Hukum Distributif)
= 0 + ab (Hukum Komplemen)
= ab (Hukum Identitas)

1.5 Fungsi Boolean
·       Contoh-contoh fungsi Boolean:
f(x) = x
f(x, y) = x’y + xy’+ y’
f(x, y) = x’ y’
f(x, y) = (x + y)’
f(x, y, z) = xyz’
·       Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk komplemennya, disebut literal.
·       Fungsi h(x, y, z) = xyz’ terdiri dari 3 buah literal, yaitu x, y, dan z’.
·       Jika diberikan x = 1, y = 1, z = 0, maka nilai fungsinya:
h(1, 1, 0) = 1 ×× 0’ = (1 × 1) × 1 = 1 × 1 = 1

1.6 Bentuk Kanonik
·       Ekspresi Boolean yang menspesifikasikan suatu fungsi dapat disajikan dalam dua bentuk berbeda.
·       Pertama, sebagai penjumlahan dari hasil kali dan kedua sebagai perkalian dari hasil jumlah.

Contoh :
f(x, y, z) = x’y’z + xy’z’ + xyz
dan
g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)(x’ + y + z’)(x’ + y’ + z)
adalah dua buah fungsi yang sama.
·       Minterm: suku (term) di dalam ekspresi boolean mengandung literal yang lengkap dalam bentuk hasil kali
·       Maxterm: suku (term) di dalam ekspresi boolean mengandung literal yang lengkap dalam bentuk hasil jumlah.

Contoh :
f(x, y, z) = x’y’z + xy’z’ + xyz -> 3 buah minterm: x’y’z, xy’z’, xyz
g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)(x’ + y + z’)(x’ + y’ + z)
-> 5 buah maxterm: (x + y + z), (x + y’ + z), (x + y’ + z’), (x’ + y + z’), dan (x’ + y’ + z)
·       Misalkan peubah (variable) fungsi Boolean adalah x, y, dan z
Maka:
x’y -> bukan minterm karena literal tidak lengkap
y’z’ -> bukan minterm karena literal tidak lengkap
xy’z, xyz’, x’y’z -> minterm karena literal lengkap

(x + z) -> bukan maxterm karena literal tidak lengkap
(x’ + y + z’) -> maxterm karena literal lengkap
(xy’ + y’ + z) -> bukan maxterm
·       Ekspresi Boolean yang dinyatakan sebagai penjumlahan dari satu atau lebih minterm atau perkalian dari satu atau lebih maxterm disebut dalam bentuk kanonik.
·       Jadi, ada dua macam bentuk kanonik:
1. Penjumlahan dari hasil kali (sum-of-product atau SOP)
2. Perkalian dari hasil jumlah (product-of-sum atau POS)
·       Fungsi f(x, y, z) = x’y’z + xy’z’ + xyz dikatakan dalam bentuk SOP
·       Fungsi g(x, y, z) = (x + y + z)(x + y’ + z)(x + y’ + z’)(x’ + y + z’) (x’ + y’ + z) dikatakan dalam bentuk POS

Cara membentuk minterm dan maxterm:
·       Untuk minterm, setiap peubah yang bernilai 0 dinyatakan dalam bentuk komplemen, sedangkan peubah yang bernilai 1 dinyatakan tanpa komplemen.
·       Sebaliknya, untuk maxterm, setiap peubah yang bernilai 0 dinyatakan tanpa komplemen, sedangkan peubah yang bernilai 1 dinyatakan dalam bentuk komplemen. 
·     Cara membentuk minterm dan maxterm dari tabel kebenaran untuk dua peubah:

·     


·     Jika diberikan sebuah tabel kebenaran, kita dapat membentuk fungsi Boolean dalam bentuk kanonik (SOP atau POS) dari tabel tersebut dengan cara:
- mengambil minterm dari setiap nilai fungsi yang bernilai 1 (untuk SOP)
atau
- mengambil maxterm dari setiap nilai fungsi yang bernilai 0 (untuk POS).




Komentar

Postingan populer dari blog ini

Graf Planar (Matematika diskrit)

Infix Prefix Postfix Matematika diskrit

Tree (pohon) Matematika Diskrit