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

a × b

a’× (b + c)

a × 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 ×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).