aljabar boolean

ALJABAR BOOLEAN

Aljabar Boolean atau dalam bahasa Inggris disebut dengan Boolean Algebra adalah matematika yang digunakan untuk menganalisis dan menyederhanakan Gerbang Logika pada Rangkaian-rangkaian Digital Elektronika. Boolean pada dasarnya merupakan Tipe data yang hanya terdiri dari dua nilai yaitu “True” dan “False” atau “Tinggi” dan “Rendah” yang biasanya dilambangkan dengan angka “1” dan “0” pada Gerbang Logika ataupun bahasa pemrograman komputer. Aljabar Boolean ini pertama kali diperkenalkan oleh seorang Matematikawan yang berasal dari Inggris pada tahun 1854. Nama Boolean sendiri diambil dari nama penemunya yaitu George Boole.

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:

 

·     Cara membentuk minterm dan maxterm dari tabel kebenaran untuk tiga 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).