Aljabar Boolean.pertemuan Terakhir

  • Published on
    26-Jun-2015

  • View
    77

  • Download
    2

Embed Size (px)

Transcript

Aljabar Boolean 1. Aljabar Boolean Aljabar Boole adalah 1. Suatu jenis simbol-simbol yang ditemukan oleh George Boole untuk memanipulasi nilai-nilai kebenaran logika secara aljabar 2. Suatu struktur aljabar yang operasi-operasinya memenuhi aturan-aturan tertentu. Secara umum, aljabar boole didefinisikan sebagai suatu himpunan dengan operasi , , dan (atau ) serta elemen 0 dan 1 yang ditulis sebagai ,,, ,0,1 atau ,,, , 0,1 maka untuk setiap x,y,x,y yang memenuhi sifat-sifat berikut : 1. Hukum Komutatif a. = b. = 2. Hukum Assosiatif a. = ( ) b. = ( ) 3. Hukum Distributif a. = ( ) b. = ( ) 4. Hukum Identitas a. 0 = b. 1 = 5. Hukum Negasi (komplemen) a. = 1 b. = 0 6. Hukum Idempoten a. = b. = 7. Hukum Ikatan a. 1 = 1 b. 0 = 0 8. Hukum Absorbsi a. = b. = 9. Hukum De Morgan a. = b. = 2. Fungsi Boolean Misal B = ,,, , 0,1 adalah aljabar boolean. Suatu fungsi Boolean n variabel adalah fungsi f : B n B Fungsi Boolean disebut sederhana jika B = {0,1}, jadi, f : {0,1} n {0,1} Masukannya adalah {0,1}n dan keluaran fungsi adalah {0,1}.

Operasi Not, And dan Or dalam logika dipandang sebagai fungsi boolean dari {0,1} 2 {0,1} Fungsi Not : {0,1}2 {0,1} didefinisikan sebagai 0, = 1, Fungsi ini biasanya ditulis (x)

= 1 = 0

Fungsi And : {0,1}2 {0,1} didefinisikan sebagai 1, = = 1 = 0, Fungsi Or : {0,1}2 {0,1} didefinisikan sebagai 0, = = 0 = 1, Contoh 1 : Nyatakan penghubung XOR (eksklusif Or) dalam fungsi {0,1}2 {0,1} Penyelesaian : Penghubung XOR (simbol ) mirip dengan penghubung atau (v). Akan tetapi, jika kedua kalimat penyusunnya benar maka hasilnya salah. p q pvq T T T F T F T T F T T T F F F F Jika T dinyatakan dengan 1 dan F dengan 0 maka dapat dinyataka dengan tabel masukan/keluaran sebagai berikut : p q 1 1 0 1 0 1 0 1 1 0 0 0 berharga 0 jika p = q dan berharga 1 jika pq. Jika XOR dinyatakan sebagai fungsi {0,1}2 {0,1}, maka : XOR : {0,1}2 {0,1} yang didefinisikan sebagai 0, = , = 1, Contoh 2 : Perhatikan fungsi Boolean f : {0,1}3 {0,1} yang didefinisikan dengan aturan : 1 , 2 , 3 = 1 + 2 + 3 2 Nyatakan f dengan menggunakan tabel masukan / keluaran!

Penyelesaian : f(1,1,1) = (1+1+1) mod 2 = 3 mod 2 = 1 f(1,1,0) = (1+1+0) mod 2 = 2 mod 2 = 0 dan seterusnya. Masukan x2 x3 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 Keluaran (x1+x2+x3) mod 2 1 0 0 1 0 1 1 0

x1 1 1 1 1 0 0 0 0

3. Ekspresi Boolean Ekspresi Boolean dalam n variabel x1, x2, ...,xn didefinisikan secara rekursif sebagai berikut : a. 0 dan 1 adalah ekspresi boolean b. x1, x2, ...,xn masing-masing adalah ekspresi boolean c. Jika E1 dan E2 adalah ekspresi boolean maka 1 2 , 1 2 , 1 adalah ekspresi boolean juga. Contoh 3 : (contoh ekspresi boolean) a. z b. c. ( ) d. ( ) 1 Contoh 4 : Telitilah apakah kedua ekspresi Boolean di bawah ini ekuivalen 1 : dan 2 = Penyelesaian : Ekuivalensi ekspresi boolean dibuktikan dengan dua cara : 1. Menggunakan hukum aljabar boolean = (1 ) hukum distributif = . 1 hukum ikatan = hukum identitas Karena E2 bisa diperoleh dari E1 maka dapat disimpulkan E1 = E2

2. Menggunakan tabel masukan/ keluaran x 1 1 1 1 0 0 0 0 y 1 1 0 0 1 1 0 0 z 1 0 1 0 1 0 1 0 xy 1 1 0 0 0 0 0 0 xyz 1 0 0 0 0 0 0 0 E1 = 1 1 1 0 1 0 1 0 E2 = 1 1 1 0 1 0 1 0

4. Bentuk Normal Disjungtif (DNF) Ekspresi boolean yang hanya terdiri dari satu variabel disebut literal. Sedangkan ekspresi boolean yang terdiri dari n variabel x1, x2, ...,xn yang merupakan gabungan dari beberapa literal yang dihubungkan dengan " " disebut minterm. Contoh 5 : Buatlah tabel masukan/keluaran fungsi literal f : {0,1} 2 {0,1} yang didefinisikan sebagai , = Penyelesaian : x 1 1 0 0 y 1 0 1 0 y' 0 1 0 1

Contoh 6 : Tentukan apakah ekspresi-ekspresi di bawah ini merupakan minterm dalam 3 variabel x,y,z a. xyz b. xz c. xyxz Penyelesaian : a. Merupakan minterm dalam x, y dan z karena memuat literal x, y dan z. b. Bukan minterm dalam x, y dan z karena tidak memuat literal y. c. Bukan minterm karena x muncul dalam 2 literal yaitu x dan x.

Contoh 7 : Buatlah tabel untuk ekspresi Boolean E dalam 3 variabel x,y, dan z E = x 1 1 1 1 0 0 0 0 y 1 1 0 0 1 1 0 0 z 1 0 1 0 1 0 1 0 x'yz' 0 0 0 0 0 1 0 0 xy'z' 0 0 0 1 0 0 0 0 xy'z 0 0 1 0 0 0 0 0 xyz' 0 1 0 0 0 0 0 0 E 0 1 1 1 0 1 0 0

Contoh 8 : Jadikan ekspresi = () dalam bentuk DNF Penyelesaian : Nilai kebenaran dari ekspresi diatas adalah sebagai berikut : x y z yz' x v yz' yz (yz)' E 1 1 1 0 1 1` 0 0 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 Nilai E = 1 terjadi pada baris 2,3,4,dan 6 yang masing-masing bersesuaian dengan minterm xyz, xyz, xyz dan xyz sehingga = Contoh 9 : Carilah bentuk DNF dengan menggunakan hukum-hukum aljabar Boolean untuk ekspresi di bawah ini : a. (dalam 2 variabel p dan q) b. (dalam 3 variabel p,q dan r) Penyelesaian : a. = . 1 1. = = ( ) = b. = = ( ) =

5. Komplemen Fungsi Fungsi komplemen berguna untuk menyederhanakan fungsi boolean. Fungsi komplemen dari suatu fungsi yaitu f yang dapat dicari dengan dua cara berikut : A. Cara pertama : menggunakan hukum De Morgan Hukum De Morgan untuk dua buah variabel x1 dan x2 adalah i) 1 + 2 = 1 2 ii) 1 . 2 = 1 +2 Contoh 10 : Misalkan , , = ( + ) maka , , = ( + ) = + ( + ) = + . () = + + . ( + ) B. Cara kedua : menggunakan prinsip dualitas Mengubah + , +, 1 0, dan 0 1 Contoh 11 : , , = ( + ) maka dual dari f adalah + + ( + ) Maka komplemenkan tiap literal (variabel) fungsinya = + + ( + ) Jadi (, , ) = + + ( + ) 6. Bentuk Kanonik (Baku) Ada dua macam bentuk yaitu : 1. Penjumlahan dari hasil kali (Sum Of Product atau SOP) 2. Perkalian dari hasil jumlah (Product Of Sum atau POS)

Contoh 12 : 1. f(x, y, z) = xyz + xyz + xyz SOP Setiap suku (term) disebut minterm 2. g(x, y, z) = (x + y + z)(x + y + z)(x + y + z)(x + y + z)(x + y + z) POS Setiap suku (term) disebut maxterm Setiap minterm/maxterm mengandung literal lengkap Minterm Lambang m0 m1 m2 m3 Maxterm Lambang M0 M1 M2 M3

x 0 0 1 1

y 0 1 0 1

Suku xy xy xy xy

Suku x+y x + y x + y x + y

x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

Suku xyz xyz xy z xy z x yz x yz x y z xyz

Minterm Lambang m0 m1 m2 m3 m4 m5 m6 m7

Maxterm Suku Lambang x+y+z M0 x + y + z M1 x + y+z M2 x + y+z M3 x+ y + z M4 x+ y + z M5 x+ y+ z M6 x+ y+ z M7

Contoh 13 : Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS. x y z f(x, y, z) 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 Penyelesaian: (a) SOP Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1 adalah 001, 100, dan 111, maka fungsi Booleannya dalam bentuk kanonik SOP adalah f(x, y, z) = xyz + xyz + xyz atau (dengan menggunakan lambang minterm), f(x, y, z) = m1 + m4 + m7 = (1, 4, 7) (b) POS Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 adalah 000, 010, 011, 101, dan 110, maka fungsi Booleannya dalam bentuk kanonik POS adalah f(x, y, z) = (x + y + z)(x + y+ z)(x + y+ z) (x+ y + z)(x+ y+ z) atau dalam bentuk lain, f(x, y, z) = M0 M2 M3 M5 M6 = (0, 2, 3, 5, 6)

Contoh 14 : Nyatakan fungsi Boolean f(x, y, z) = x + yz dalam bentuk kanonik SOP dan POS. Penyelesaian: (a) SOP x = x(y + y) = xy + xy = xy (z + z) + xy(z + z) = xyz + xyz + xyz + xyz yz = yz (x + x) = xyz + xyz Jadi f(x, y, z) = x + yz = xyz + xyz + xyz + xyz + xyz + xyz = xyz + xyz + xyz + xyz + xyz atau f(x, y, z) = m1 + m4 + m5 + m6 + m7 = (1,4,5,6,7) (b) POS f(x, y, z) = x + yz = (x + y)(x + z) x + y = x + y + zz = (x + y + z)(x + y + z) x + z = x + z + yy = (x + y + z)(x + y + z) Jadi, f(x, y, z) = (x + y + z)(x + y + z)(x + y + z)(x + y + z) = (x + y + z)(x + y + z)(x + y + z) atau f(x, y, z) = M0M2M3 = (0, 2, 3)

Konversi Antar Bentuk Kanonik Misalkan f(x, y, z) = (1, 4, 5, 6, 7)

dan f adalah fungsi komplemen dari f, f (x, y, z) = (0, 2, 3) = m0+ m2 + m3 Dengan menggunakan hukum De Morgan, kita dapat memperoleh fungsi f dalam bentuk POS: f (x, y, z) = (f (x, y, z)) = (m0 + m2 + m3) = m0 . m2 . m3 = (xyz) (xy z) (xy z) = (x + y + z) (x + y + z) (x + y + z)

= M0 M2 M3 = (0,2,3) Jadi, f(x, y, z) = (1, 4, 5, 6, 7) = (0,2,3). Kesimpulan: mj = Mj Contoh 15 : Nyatakan f(x, y, z)= (0, 2, 4, 5) dan g(w, x, y, z) = (1, 2, 5, 6, 10, 15) dalam bentuk SOP. Penyelesaian: f(x, y, z)

= (1, 3, 6, 7)

g(w, x, y, z)= (0, 3, 4, 7, 8, 9, 11, 12, 13, 14) Contoh 16 : Carilah bentuk kanonik SOP dan POS dari f(x, y, z) = y + xy + xyz Penyelesaian: (a) SOP f(x, y, z) = y + xy + xyz = y (x + x) (z + z) + xy (z + z) + xyz = (xy + xy) (z + z) + xyz + xyz + xyz = xyz + xyz + xyz + xyz + xyz + xyz + xyz atau f(x, y, z) = m0+ m1 + m2+ m4+ m5+ m6+ m7 (b) POS f(x, y, z) = M3 = x + y + z 7. Rangkaian Logika Aplikasi aljabar boolean meliputi : a. Rangkaian Listrik / Jaringan Listrik / Switching Network Saklar adalah objek yang mempunyai dua buah status yaitu : buka dan tutup. Jenis Gambar Saklar Terbuka 0 Saklar Tertutup Rangkaian Seri p q 1 (= ) (= + )

Rangkaian Pararel

Contoh 17 :

b. Rangkaian Logika Komputer dan peralatan elektronik lain dibuat dari sejumlah rangkaian logika. Rangkaian logika menerima masukan dan keluaran berupa pulsa-pulsa listrik yang dapat dipandang sebagai 0 atau 1. Elemen dasar dari rangkaian logika adalah gerbang logika (logic gate) dan setiap gerbang mengimplementasikan sebuah operasi Boolean.