ALJABAR BOOLEAN

Aljabar Boolean

· Aljabar Boolean ditemukan oleh George Boole, pada tahun 1854.

· Boole melihat bahwa himpunan dan logika proposisi mempunyai sifat-sifat yang serupa (perhatikan kemiripan hukum-hukum aljabar logika dan hukum-hukum aljabar himpunan).

· Dalam buku The Laws of Thought, Boole memaparkan aturanaturan dasar logika.

· Aturan dasar logika ini membentuk struktur matematika yang disebut aljabar Boolean.

· Aplikasi: perancangan rangkaian pensaklaran, rangkaian digital, dan rangkaian IC (integrated circuit) komputer.

Definisi Aljabar Boolean

DEFINISI.

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

· Berhubung elemen-elemen B tidak didefinisikan nilainya (kita bebas menentukan anggota-anggota B), maka terdapat banyak sekali aljabar boolean.

· Untuk mempunyai sebuah aljabar Boolean, orang harus memperlihatkan: 1. elemen-elemen himpunan B, 2. kaidah/aturan operasi untuk dua operator biner dan operator uner, 3. himpunan B, bersama-sama dengan dua operator tersebut, memenuhi keempat aksioma di atas

· Aljabar himpunan dan aljabar logika proposisi juga merupakan aljabar Boolean karena memenuhi empat aksioma di atas.

· Dengan kata lain, aljabar himpunan dan aljabar proposisi adalah himpunan bagian (subset) dari aljabar Boolean.

· Pada aljabar proposisi misalnya: - B berisi semua proposisi dengan n peubah. - dua elemen unik berbeda dari B adalah T dan F, - operator biner: Ú dan Ù, operator uner: ~ - semua aksioma pada definisi di atas dipenuhi

· Dengan kata lain <B, Ú , Ù , ~, F, T> adalah aljabar Booelan.

Aljabar Boolean 2-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:

a	b	a.b
0	0	0
0	1	0
1	0	0
1	1	1

a	b	a+b
0	0	0
0	1	1
1	0	1
1	1	1

a	a’
0	1
1	0

(iv)   Keempat aksioma di atas dipenuhi

Ekspresi Boolean

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

· Contoh 1:

0

1

a

b

a + b

a . b

a’. (b + c)

a . b’ + a . b . c’ + b’, dan sebagainya

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)    (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

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

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 3:

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.

Bentuk Baku

• Tidak harus mengandung literal yang lengkap.

• Contohnya,    

f(x, y, z) = y’ + xy + x’yz (bentuk baku SOP)  

f(x, y, z) = x(y’ + z)(x’ + y + z’) (bentuk baku POS)