Makalah Sistem Digital [PDF]

Citation preview

MAKALAH SISTEM DIGITAL “Konsep Dasar Teorema Boole & De Morgan”



Disusun Oleh : Anin Rodahad (12131307) Abdurrahman Ar-Rohim (12131299) Bayu Ari Utomo ()



TEKNIK INFORMATIKA STMIK EL RAHMA YOGYAKARTA Jl. Sisingamangaraja no. 76 Karangkajen Yogyakarta 2014



KATA PENGANTAR



Puji syukur kami ucapkan kehadapan Tuhan Yang Maha Esa karena atas berkat rahmatnyalah kami dapat menyelesaikan makalah yang berkaitan dengan Mata Kuliah Sistem Digital. Makalah ini memberikan gambaran materi teorema bolle dan de Morgan, dari dasar hukum penyajian fungsi boole, serta contoh soal Makalah ini tentunya masih sangat jauh dari sempurna, kami berharap semoga makalah ini dapat berguna bagi semua pihak sesuai dengan tujuan pembuatan makalah ini. Selain itu juga kami mengharapkan kritik dan saran untuk menyempurnakan makalah kami ini. Kami juga berterima kasih kepada semua pihak dan sumber-sumber referensi yang telah membantu dalam penulisan makalah ini.



Yogyakarta, 5 Oktober 2014 Penulis



1



DAFTAR ISI



KATA PENGANTAR



2



DAFTAR ISI



3



BAB I PENDAHULUAN A. Latar Belakang



4



B. Rumusan Masalah



5



C. Tujuan Dan Manfaat



5



BAB II PEMBAHASAN A.Teorema dasar Bolee



6



Hukum Distributif



6



Hukum Asosiatif



6



Hukum Komutatif



7



Hukum Komplemen



8



Hukum Operasi 0 dan 1



8



Hukum Idempoten



9



Hukum Involusi



10



B.Penyajian Fungsi Boole



11



A.bentuk kanomik Penjumlahan dari hasil kali (sum-of-product atau SOP)



12



Perkalian dari hasil jumlah (product-of-sum atau POS)



12



D.Penyederhanaan fungsi Boole



13



A. Penyederhanaan secara Teorema 13 B.Penyederhanaan dengan peta karnaugh E.Teorema dasar De morgan



13 18



BAB III PENUTUP KESIMPULAN.................................................................................



21



SARAN



21



DAFTAR PUSTAKA



22 2



BAB I PENDAHULUAN



A. Latar Belakang Teorema boole dan de Morgan merupakan teorema yang berhubungan dengan variabel-variabel biner dan operasi-operasi logik. Variabel-variabel diperlihatkan dengan huruf-huruf alfabet, dan tiga operasi dasar dengan AND, OR dan NOT (komplemen). Fungsi boole terdiri dari variabel-variabel biner yang menunjukkan fungsi, suatu tanda sama dengan, dan suatu ekspresi teorema yang dibentuk dengan menggunakan variabel-variabel biner, konstanta-konstanta 0 dan 1, simbol-simbol operasi logik, dan tanda kurung. Suatu fungsi boole bisa dinyatakan dalam tabel kebenaran. Suatu tabel kebenaran untuk fungsi boole merupakan daftar semua kombinasi angka-angka biner 0 dan 1 yang diberikan ke variabel-variabel biner dan daftar yang memperlihatkan nilai fungsi untuk masing-masing kombinasi biner. Oleh karena itulah si penulis berharap si pembaca dapat mengetahui fungsi dan menambah wawasan tentang teorema Boole & De Morgan.



B. Rumusan Masalah a. Pengertian Teorema dasar boole & Hukum hukumnya? b. Cara penyajian Fungsi Boole? c. Penyederhanaan Fungsi Boole? d. Pengertian Teorema dasar De Morgan? C. Tujuan Penulisan Selain permasalahan yang ditemuai dalam pembuatan makalah ini si penulis juga mempunyai beberapa tujuan dalam menulis makalah ini yaitu sebagai berikut: 1.



Si pembaca dapat mengetahui apa yang dimaksud dengan Teorema Boole & De Morgan



2.



Si pembaca dapat mengetahui cara penyajian & penyederhanaan fungsi Boole.



3.



Si pembaca dapat mengetahui apa saja hukum-hukum dari teorema dasar Boole.



D.Manfaat Penulisan Dengan menulis makalah ini si penulis mengharapkan si pembaca dapat menambah wawasan, memperdalami teorema Boole dan Teorema De Morgan.



3



BAB II PEMBAHASAN



A. Teorema Dasar Boole Konsep dasar teorema Boole (Boole Algebra) telah diletakkan oleh seorang matematisi Inggris George Boole, pada tahun 1854. Konsep dasar itu membutuhkan waktu yang cukup lama untuk disadari kegunaannya, baik dalam bidang matematika maupun dalam bidang teknik. Pada tahun 1938 Claude Shannon, seorang ahli komunikasi, memanfaatkan dan menyempurnakan konsep Boole tersebut. Sekarang ini, teorema Boole memegang peranan yang sangat penting, tidak saja dalam logika, tetapi juga di bidang lain seperti teori peluang/kemungkinan, teori informasi/komunikasi, teori himpunan dan lain-lain. Teori ini juga dipakai dalam merancang komputer elektronik dengan menerjemahkannya ke dalam rangkaian saklar (switching circuits) yang pada dasarnya adalah logika, tertutup atau terbuka, mengalirkan arus listrik atau tidak. Seperti telah diterangkan di bagian depan, setiap peubah Boole hanya dapat berkeadaan satu dari dua keadaan, 0 atau 1. Jadi, kalau satu peubah di-OR-kan dengan 0 maka hasilnya akan tidak berubah sedangkan bila satu peubah di-OR-kan dengan 1, maka apapun keadaan peubah itu sebelumnya akan menjadi 1. Tetapi, bila satu peubah di-ANDkan dengan 1, maka hasilnya tidak akan berubah sedangkan bila di-AND-kan dengan 0, apapun keadaan peubah itu sebelumnya akan berubah menjadi 0. Ini dapat disimpulkan dalam bentuk teorema dasar: X+0=X X.0 = 0 X+1=1 X.1 = X  Kalau suatu peubah di-OR-kan dengan dirinya sendiri, maka hasilnya akan 0 bila keadaan variabel itu adalah 0 dan hasilnya akan 1 bila keadaan variabel itu adalah 1.  Jadi, peng-OR-an satu variabel dengan dirinya sendiri menghasilkan keadaan yang sama dengan keadaan variabel itu. Keadaan serupa berlaku untuk operasi AND. Ini disebut hukum idempoten: X+X=X



X.X = X 4



 Sesuai dengan logika, maka kalau tidak benar disangkal (di-NOT-kan), hasilnya menjadi benar dan kalau tidak-salah di-NOT-kan, hasilnya menjadi salah.  Dengan kata lain, penidakan/penyangkalan (komplementasi) dua kali akan menghasilkan keadaan aslinya. Ini dikenal dengan nama hukum involusi yang dituliskan sebagai: =X







Hasil dari keadaan benar ATAU tidak benar pasti selalu benar dan keadaan salah ATAU tidak salah juga akan selalu benar (terpenuhi). Tetapi keadaan salah DAN tidak salah dan benar DAN tidak benar akan selalu salah. Jadi, dalam teorema Boole dapat dinyatakan dengan hukum komplemen sebagai berikut: X + X = 1 (selalu benar) X. X=0



(selalu salah)



Untuk fungsi-fungsi Boole dengan dua peubah atau lebih, dikenal juga hukum-hukum kumulatif, assosiatif dan distributif yang berlaku dalam teorema biasa, yaitu: Hukum Kumutatif :



XY = YX X +Y=Y+X



Hukum Assosiatif:



(X Y) Z = X (Y Z) = XYZ (X+Y) + Z = X + (Y+Z) = X + Y + Z



Hukum Distributif:



X (Y + Z) = X Y + X Z X + Y Z = (X + Y)(X + Z)



5



B.Teorema dasar Boole



Hukum Distributif 1. A (B + C) = A B + A C (BENAR) Pembuktian:



2. A+(B+C)=(A+B)+C=A+B+C (BENAR) 3. Pembuktian:



6



Hukum Asosiatif



1.



(A + B) + C = A + (B + C)(BENAR) Pembuktian: A



B



C



A+B



B+C (A+B)+C A+(B+C)



0



0



0



0



0



0



0



0



0



1



0



1



1



1



0



1



0



1



1



1



1



0



1



1



1



1



1



1



1



0



0



1



0



1



1



1



0



1



1



1



1



1



1



1



0



1



1



1



1



1



1



1



1



1



1



1



2. (A B) C = A (B C) (BENAR) Pembuktian: A



B



C



AB



BC



(A B) C



A (B C)



0



0



0



0



0



0



0



0



0



1



0



0



0



0



0



0



1



0



0



0



0



0



1



1



0



1



0



0



1



0



0



0



0



0



0



1



0



1



0



0



0



0



1



1



0



1



0



0



0



1



1



1



1



1



1



1



7



Hukum Komutatif



(a) A + B = B + A(BENAR) Pembuktian: A



B



A+B



B+A



0



0



0



0



0



1



1



1



1



0



1



1



1



1



1



1



(b) A B = B A(BENAR) Pembuktian: A



B



AB



BA



0



0



0



0



0



1



0



0



1



0



0



0



1



1



1



1



Teorema kompelement (a) A + Ā=1) (BENAR) Pembuktian: A



Ā



1



(A + Ā=1)



0



1



1



1



0



1



1



1



1



0



1



1



1



0



1



1



8



(b) A Ā = 0 (BENAR) Pembuktian: A



Ā



0



(A Ā= 0)



0



1



0



0



0



1



0



0



1



0



0



0



1



0



0



0



Hukum Operasi 0 dan 1 (a) 1 + A = 1(BENAR) Pembuktian: A



1



1+A



1



1



0



1



1



1



1



1



1



1



1



0



(b) 1 A = A (BENAR) Pembuktian:



A



1



1.A=A



1



0



0



1



0



1



1



1



1



1



1



0



(a) 0 + A = A (BENAR) Pembuktian:



9



A



0



0+A=A



0



0



0



0



0



0



1



0



1



1



0



1



(b) 0 A = 0 (BENAR) Pembuktian: A



0



0A=0



0



0



0



0



0



0



1



0



0



1



0



0



Hukum Idempoten (a) A + A = A (BENAR) Pembuktian: A



A



A+A=A



0



0



0



0



0



0



1



1



1



1



1



1



(b) A A = A (BENAR) Pembuktian:



10



A



A



A.A=A



0



0



0



0



0



0



1



1



1



1



1



1



Hukum Involusi =A . = A (BENAR) Pembuktian: . =A 0



0



0



0



0



0



1



1



1



1



1



1



C.Penyajian Fungsi Boole A.bentuk kanomik •



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)



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



(x’ + y + z’)(x’ + y’ + z)  POS Setiap suku (term) disebut maxterm •



Setiap minterm/maxterm mengandung literal lengkap



•



Suatu fungsi Booelan dapat dibentuk secara teorema dari tabel kebenaran yang diketahui dengan membentuk minterm/maxterm dari setiap kombinasinya. Untuk membentuk SOP, tinjau kombinasi peubah-peubah yang menghasilkan nilai 1. Untuk membentuk POS, tinjau kombinasi peubah-peubah yang menghasilkan nilai 0.



•



Contoh: Nyatakan fungsi Boole f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS!



•



Cara 1 f(x, y, z) = x + y’z (a) SOP x = x(y + y’) = xy + xy’ = xy (z + z’) + xy’(z + z’) = xyz + xyz’ + xy’z + xy’z’ 12



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



13



D. Penyederhanaan fungsi Boole dapat dilakukan dengan 2 cara: Secara teorema Menggunakan Peta Karnaugh a. Penyederhanaan Secara Teorema Contoh: 1.f(x, y) = x + x’y = (x + x’)(x + y) hukum distributif = 1 . (x + y ) hukum komplemen =x+y



2. f(x, y, z) = x’y’z + x’yz + xy’ = x’z(y’ + y) + xy’ hukum distributif = x’z + xz’



3. f(x, y, z) = xy + x’z + yz = xy + x’z + yz(x + x’) = xy + x’z + xyz + x’yz hukum asosiatif = xy(1 + z) + x’z(1 + y) = xy + x’z hukum distributif



b.Penyederhanaan dengan Peta Karnaugh Peta Karnaugh adalah sebuah diagram / peta yang terbentuk dari kotak - kotak yang bersisian. Tiap kotak merepresentasikan sebuah minterm. Peta Karnaugh dengan jumlah kotak lebih dari 4 buah akan memiliki sisi yang berseberangan. Sisi yang berseberangan tersebut sebenarnya merupakan sisi yang bersisian juga. Artinya sebuah peta karnaugh dapat dibayangkan sebagai sebuah kotak kubus atau balok atau silinder yang tersusun atas kotak – kotak itu.



14



a. Peta Karnaugh dengan dua peubah



Fungsi Boole yang merepresentasikannya adalah f (x, y) = x y



Fungsi Boole yang merepresentasikannya adalah f (x, y) = x y‘ + x y b. Peta Karnaugh dengan tiga peubah



15



Fungsi Boole yang merepresentasikannya adalah f (x, y,z) = x’ y z‘ + x y z’ + x y z c. Peta Karnaugh dengan empat peubah Teknik Minimasi Fungsi Boole dengan Peta Karnaugh 1. Pasangan : dua buah 1 yang bertetangga



Fungsi Boole sebelum disederhanakan : f (w, x, y, z) = w x y z + w x y z’ Setelah disederhanakan : f (w, x, y, z) = w x y 16



Bandingkan dengan cara teorema f (w, x, y, z) = w x y z + w x y z’ = w x y (z + z’ ) = w x y (1) =wxy



2. Kuad : empat buah 1 yang bertetangga



Fungsi Boole sebelum disederhanakan : f (w, x, y, z) = w x y’ z’ + w x y’ z + w x y z + w x y z’ Setelah disederhanakan : f (w, x, y, z) = w x 3. Oktet : delapan buah 1 yang bertetangga



Fungsi Boole sebelum disederhanakan : f (w, x, y, z) = w x y’ z’ + w x y’ z + w x y z + w x y z’ + w x’ y’ z’ + w x’ y’ z + w x’ y z + w x’ y z’ Setelah disederhanakan : f (w, x, y, z) = w



E. Teorema Dasar De Morgan Dua persamaan berikut dikenal dengan nama Hukum De Morgan:



Untuk membuktikan Persamaan (1-1) perlu di perhatikan, bahwa jikalau semua masukan 1, 17



masing-masing ruas persamaan akan memberikan suatu hasil yang sama dengan 0. Di pihak lain, kalau satu (atau lebih dari satu) masukan sama dengan 0, maka masing-masing ruas persamaan akan memberikan suatu hasil yang sama dengan 1. Sehingga, untuk semua kemungkinan masukan dari ruas sebelah kanan persamaan sama dengan ruas sebelah kiri. Persamaan (1-2) dibuktikan dengan cara yang sama. Hukum De Morgan memperlengkap daftar identitas Boole dasar. Untuk masing-masing acuan selanjutnya, semua hubunganhubungan tersebut di ringkas dalam tabel 1a.



Contoh penggunaan teorema boole hukum-hukum De Morgan pada ekuivalensi rangkaian EXCLUSIVE OR adalah sebagai berikut: Diketahui suatu fungsi logika boole EXCLUSIVE OR fungsi logika boole



dan ekuivalen dengan



, buktikan bahwa memang kedua persamaan tersebut



ekuivalen. Maka dua persamaan tersebut dapat dibuktikan dengan penjabaran dengan pertolongan teorema boole sebagai berikut:



18



Dari hukum De Morgan dapat disimpulkan, bahwa untuk mendapatkan komplemen (pelengkap) dari suatu fungsi boole adalah dengan mengubah semua operasi OR menjadi operasi AND, ataupun sebaliknya mengubah semua operasi AND menjadi operasi OR, dan melakukan penolakan masing-masing simbol binernya. Dan dengan pertolongan hukum De Morgan dapat kita tunjukkan bahwa suatu rangkaian AND untuk logika positif juga bekerja seperti halnya suatu gerbang OR untuk logika negatif. Misalkan Y adalah keluaran dan A, B, ... , N adalah masukan-masukan ke AND positif, sehingga



Kalau keluaran dan semua masukan dari rangkaian dikomplemenkan sedemikian hingga 1 menjadi 0 dan sebaliknya, maka logika positif berubah menjadi logika negatif. Karena Y dan menggambarkan terminal keluaran yang sama, A dan menggambarkan terminal masukan yang sama, dan lain sebagainya. Rangkaian yang melaksanakan logika AND positif dalam persamaan (1-3) juga bekerja sebagai gerbang logika OR negatif pada persamaan (1-4). Alasan yang sama digunakan untuk membuktikan, bahwa rangkaian yang sama mungkin berlaku sebagai AND negatif atau OR positif, tergantung kepada bagaimana tingkat biner didefinisikan. Hal ini telah dibuktikan untuk logika dioda. Untuk lebih jelasnya berikut ditampilkan aplikasi teorema De Morgan dalam diagram blok fungsi logika boole pada gambar 1-1c. Suatu OR yang diubah ke AND dengan membalikkan semua masukan dan keluarannya, gambar 1-1d. Suatu AND menjadi OR, kalau semua masukan dan keluaran komplemen. 19



20



BAB III PENUTUP



A.KESIMPULAN Teorema boole digunakan untuk menyatakan pengaruh berbagai rangkaian digital pada masukan-masukan logika, dan untuk memanipulasi variabel logika dalam menentukan cara terbaik pada pelaksaan



fungsi rangkaian tertentu. Oleh karena hanya ada dua niai yang mungkin,



teorema boole lebih cocok digunakan untuk rangkaian digital dibandingkan dengan teorema yang lain. Kenyataanya alajabar boole hanya mengenal tiga operasi dasar, yaitu: Aturan operasi OR, AND dan NOT Teorema De Morgan sebenarnya juga tidak perlu menggunakan semua gerbang logika, yakni cukup adanya OR dan NOT atau AND dan NOT saja, karena dari hukum De Morgan persamaan (1-1) AND dapat diperoleh dari OR dan NOT, seperti ditunjukkan dalam gambar 1-1c. Dan dengan cara yang sama, AND dan NOT dapat dipilih sebagai rangkaian gerbang logika dasar, dan dari hukum De Morgan persamaan (1-2), OR mungkin dapat dibangun seperti ditunjukkan dalam gambar 1-1d. Gambar ini akan menjelaskan lagi, bahwa OR (AND) dibalikkan pada masukan dan keluaran membentuk logika AND (OR)



B.SARAN Untuk memahami lebih lanjut tentang Teorema Boole saya harap si pembaca dapat mencari sumber-sumber yang lain di internet dan buku-buku yang terkait dengan Teorema Boole



21



DAFTAR PUSTAKA



http://pandukristiyanto89.wordpress.com/2010/10/19/teorema-boole/ kur2003.if.itb.ac.id/file/Teorema%20Boole.doc http://rizqiprastowo.blogspot.com/2011/07/teorema-boleab.html http://habibfreak.blogspot.com/2012/10/bentuk-kanonik-matematikadiskrit.html http://www.linksukses.com/2012/11/logika-boolean-karnaugh-map.html http://eviandrianimosy.blogspot.com/2010/06/hukum-de-morgan.html



22