Aljabar Boolean PDF [PDF]

Citation preview

Aljabar Boolean Noor Yulita Dwi Setyaningsih, M.Eng



Rangkaian digital yang ekivalen dengan persamaan logika



Misal, diketahui persamaan logika : X = A.B+C Maka, rangkaian digitalnya adalah



Komponen Level Gate 1. Rangkaian Kombinasional Rangkaian dimana setiap outputnya hanya merupakan fungsi input pada suatu saat tertentu saja. Komponennya terdiri dari : Logcic Gate (Gerbang Logika) 2. Rangkaian Sequential Rangkaian dimana setiap outputnya tidak hanya tergantung pada input waktu itu saja, tetapi juga pada keadaan input sebelumnya Komponennya terdiri dari : Flip-Flop



Aljabar Boolean • Aljabar Boolean merupakan cara yang ekonomis untuk menjelaskan fungsi rangkaian digital, bila fungsi yang diinginkan telah diketahui, maka aljabar boolean dapat digunakan untuk membuat implementasi fungsi tersebut dengan cara yang lebih sederhana.



Dalam mengembangkan sistem aljabar boolean, perlu memulainya dengan asumsiasumsi yakni Postulat Boolean dan Teorema Aljabar Boolean



Sifat Komutatif



Sifat Asosiatif



Sifat Distributif



Mengevaluasi Ekspresi Boolean • Contoh: a’.(b+c) jika a=0, b=1, dan c=0, maka hasil evaluasi ekspresi: 0’.(1+0) = 1.1 = 1 • Dua ekspresi Boolean dikatakan ekivalen (dilambangkan dengan ‘=‘) jika keduanya mempunyai nilai yang sama untuk pemberian nilai-nilai kepada n peubah. Contoh: a.(b+c) = (a.b) + (a.c)



• Perlihatkan bahwa a + a’b = a + b penyelesaian:



• Perjanjian: tanda titik (.) dapat dihilangkan dari penulisan ekspresi Boolean, kecuali jika ada penekanan:



Prinsip Dualitas • Misalkan S adalah kesamaan (identity) di dalam aljabar boolean yang melibatkan operator +,.,’(komplemen), maka jika pernyataan S* diperoleh dengan cara mengganti . dengan + + dengan . 0 dengan 1 1 dengan 0 dan membiarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar. S* disebut sebagai dual dari S contoh:



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



• Dalam Aljabar Boolean, variable x disebut peubah Boolean. FungsiBoolean adalah ekspresi yang dibentuk dari peubah Boolean melalui operasi penjumlahan, perkalian, atau komplemen.



• Selain dengan cara aljabar, fungsi Boolean dapat dinyatakan dalam bentuk tabel kebenaran. Tabel kebenaran adalah suatu tabel yang menyatakan seluruh kemungkinan nilai peubah dari fungsinya. Jika suatu fungsi Boolean memuat n peubah, maka banyaknya baris dalam tabel kebenaran ada 2^n.



• Fungsi Boolean tidak unik (tunggal), artinya dua fungsi yang ekspresinya berbeda dikatakan sama jika keduanya mempunyai nilai yang sama pada tabel kebenaran untuk setiap kombinasi peubahpeubahnya.



Aplikasi Soal Aljabar Boolean • Dari postulat dan teorema aljabar boolean, tujuan utamanya adalah untuk penyederhanaan: – Ekspresi Logika – Persamaan Logika – Persamaan Boolean (Fungsi Boolean) Dimana dari kesemuanya itu, intinya adalah untuk mendapatkan Rangkaian Logika yang paling sederhana



Contoh Buktikan (i) a+a’b = a+b Jawab : a+a’b = (a+ab)+a’b (penyerapan) = a+(ab+a’b) ( asosiatif ) = a+1.b ( Komplemen ) = a+b ( Identitas) (ii) a(a’+b) = ab dimana (ii) merupakan dual dari (i)



1. X + X’ .Y = = (X + X’).(X +Y) = X+Y



2. X .(X’+Y) = = X.X’ + X.Y = X.Y 3. X.Y+ X’.Z+Y.Z = = X.Y + X’.Z + Y.Z.(X+X)’ = X.Y + X’.Z + X.Y.Z + X’.Y.Z = X.Y.(1+Z) + X’.Z.(1+Y) = X.Y + X’.Z



SOAL 1. Sederhanakan Persamaan Berikut: a. A.(A.B+C) b. A’.B + A.B + A’.B’ c. A + A.B’ + A’.B



2. Buat Tabel Kebenaran dari Persamaan Logika Berikut: a. X.Y + X’.Y + X’.Y’ = X’ + Y b. A.B.C + A.C + B.C = A+B+C



Bentuk Kanonik Adalah fungsi Boolean yang dinyatakan sebagai jumlah dari hasil kali,hasil kali dari jumlah dengan setiap suku mengandung literal yang lengkap. Ada dua macam bentuk kanonik: 1. Minterm atau sum-of-product (SOP) 2. Maxterm atau product-of-sum(POS) Minterm



Maxterm



x



y



suku



lambang



suku



lambang



0 0 1 1



0 1 0 1



xy xy xy xy



m0 m1 m2 m3



x+y x + y x + y x + y



M0 M1 M2 M3



Contoh: 1. f(x, y, z) = x’y’z + xy’z’ + 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



x 0 0 1 1



y 0 1 0 1



Minterm Suku Lambang x’y’ m0 x’y m1 xy’ m2 xy m3



Maxterm Suku Lambang x+y M0 x + y’ M1 x’ + y M2 x’ + y’ M3



30



Minterm x



0 0 0 0 1 1 1 1



y



0 0 1 1 0 0 1 1



Maxterm



z



suku



lambang



Suku



lambang



0 1 0 1 0 1 0 1



xyz xyz xyz xyz xyz xyz xyz xyz



m0 m1 m2 m3 m4 m5 m6 m7



x+y+z x + y + z x + y + z x + y + z x + y + z x+ y + z x + y + z x + y+ z



M0 M1 M2 M3 M4 M5 M6 M7



Perbedaan minterm dan maxterm adalah: Untuk membentuk minterm perhatikan kombinasi peubah yang menghasilkan nilai 1. Kombinasi 001, 100 dan 111 dituliskan x y z, xy z dan xyz. Untuk membentuk maxterm perhatikan kombinasi peubah yang menghasilkan nilai 0. kombinasi 000, 010, 011, 101 dan110 dituliskan (x+y+z), (x+y +z), (x+y +z),(x +y+z) dan (x +y +z) Notasi  dan  berguna untuk mempersingkat penulisan ekspresi dalam bentuk SOP dan POS.



Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS. Tabel 7.10 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



f(x, y, z) 0 1 0 0 1 0 0 1 33



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) = x’y’z + xy’z’ + xyz atau (dengan menggunakan lambang minterm), f(x, y, z) = m1 + m4 + m7 =  (1, 4, 7)



34



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



35



Contoh Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS. Penyelesaian: (a) SOP x = x(y + y’) = xy + xy’ = xy (z + z’) + xy’(z + z’) = xyz + xyz’ + xy’z + xy’z’



y’z = y’z (x + x’) = xy’z + x’y’z Jadi f(x, y, z) = x + y’z = xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z = x’y’z + xy’z’ + xy’z + xyz’ + xyz atau f(x, y, z) = m1 + m4 + m5 + m6 + m7 =  (1,4,5,6,7)



36



(b) POS f(x, y, z) = x + y’z = (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)



37