IJCCS, Vol.x, No.x, Julyxxxx, pp. 1~5ISSN: 1978-1520
PENERAPAN METODE QUINE-MC CLUSKEY UNTUK MENYEDERHANAKAN FUNGSI BOOLEAN Herman Saputra Program Studi Sistem Informasi, STMIK Royal Kisaran Jl. Prof. M. Yamin 173 Kisaran, Sumatera Utara 21222 Telp: (0623) 41079 E-mail:
[email protected] Abstrak Metode Quine McCluskey adalah metode penyederhanaan fungsi Boolean berbasis computer dan memiliki dua kelebihan dibandingkan dengan metode K-Map, pertama fungsi untuk menghasilkan fungsi minimal yang kurang bergantung pada penulisan pola, kedua skema yang layak untuk menangani besar jumlah variable. Dalam proses penyederhanaan fungsi Boolean terdapat tiga metode penyelesaian, diantaranya adalah metode aljabar, peta karnough dan metode Quine McCluskey (metode tabulasi). Ketiga metode tersebut memiliki kekurangan dan kelebihan masing-masing dalam proses penyederhanaannya, beberapa literature menyatakan bahwa metode Quine McCluskey merupakan metode yang dianggap paling baik dalam penyederhanaan fungsi Boolean. Hal ini dikarenakan metode tabulasi ini menggunakan tahap-tahap penyederhanaan yang jelas dan baku sehingga menghasilkan fungsi Boolean yang paling sederhana. Penyederhanaan fungsi Boolean dilakukan karena fungsi Boolean sering mengandung operasi-operasi yang tidak perlu, suku-suku atau literal yang berlebih, oleh karena itu kita dapat menyederhanakan fungsi Boolean lebih lanjut, dengan melakukan penyederhanaan fungsi Boolean berarti kita telah melakukan penghematan dalam pembuatan rangkaian digital. Metode Quine McCluskey adalah metode yang digunakan untuk menyederhanakan fungsi Boolean yang memiliki variable yang besar. Dengan penelitian ini mahasiswa dapat menghemat biaya dalam praktik elektronika. Kata kunci : Fungsi Boolean, Metode Quine McCluskey, Penyederhanaan
manual, yang dikarenakan begitu banyaknya rumus dan panjangnya proses penyelesaian dari sebuah materi pelajaran yang harus mereka pelajari dan selesaikan.
1. PENDAHULUAN Metode Quine-McClaskey (tabulasi) merupakan salah satu metode yang digunakan untuk menederhanakan sebuah persamaan boolean. Fungsinya sama seperti Karnaugh Map (K-Map), hanya saja dengan metode QuineMcCluskey kita dapat menghitung lebih dari 6 variabel. Format tabelnya juga menjadi lebih efisien untuk digunakan dalam algoritma komputer dan memberikan cara deterministik untuk memeriksa bahwa bentuk minimal sebuah fungsi boolean telah tercapai, (adhav Vitthal, Buchade Amar, Pune, Maharashtra, India, 2009). Metode Quine-McClaskey adalah salah satu metode yang dapat digunakan untuk mengatasi seringnya fungsi Boolean menggunakan operasi-operasi yang tidak perlu, dan dapat digunakan untuk menghasilkan fungsi Boolean yang paling sederhana. Di AMIK ROYAL khususnya mahasiswa teknik komputer seringkali menghadapi hambatan dalam mengikuti matakuliah matematika diskrit, dalam matakuliah matematika diskrit mahasiswa sering jenuh dalam melakukan perhitungan
2. TINJAUAN TEORI 2.1 Metode Quine McCluskey Metode Quine McCluskey adalah metode penyederhanaan fungsi boolean berbasis komputer dan memiliki dua keunggulan dibandingkan metode K-Map, pertama sistematis untuk menghasilkan fungsi minimal yang kurang bergantung pada penglihatan pola, kedua skema yang layak untuk menangani besar jumlah variabel, (adhav Vitthal, Buchade Amar, Pune, Maharashtra, India). Metode Quine-McCluskey adalah sebuah metode yang digunakan untuk menyederhanakan fungsi Boolean, khususnya fungsi Boolean yang memiliki jumlah peubah yang besar (di atas 6 buah). Metode QuineMcCluskey dikembangkan oleh W.V. Quine dan E.J. McCluskey pada tahun 1950. Metode Quine-McCluskey mereduksi fungsi persamaan logika dengan cara menyederhanakan suku-suku penjumlahan dari perkalian sebagai berikut: 31
Jurnal Teknologi dan Sistem Informasi, Volume 2, Nomor 1, Desember 2015, hlm 31-41 1.
Eleminasi sebanyak mungkin sukusuku persamaan dengan cara XY+Xy’=X, hasil penyederhanaan disebut suku esensi.
2.
Dari tabel yang berisi semua suku persamaan, OR-kan suku-suku persamaan/suku-suku esensi tersebut (mencoba semua pasangan yang mungkin) untuk mencari kesamaan nilai pada posisi variabel yang sama, setiap kali melakukan operasi OR hanya diperbolehkan satu variabel yang berbeda.
logika boolean. Boolean menyusun beberapa aturan hubungan antara nilai-nilai matematis yang dibatasi hanya dengan 2 (dua) nilai, yaitu true atau false, yang disimbolkan sebagai angka 1 atau 0. Sistem matematikanya ini kemudian dikenal sebagai aljabar Boolean, (Safrina Amanah Sitepu, 2009). Dalam matematika dan ilmu komputer, Aljabar Boolean adalah struktur aljabar yang “mencakup intisari” operasi logika AND, OR dan NOR dan juga teori himpunan untuk operasi union, interseksi dan komplemen. Penamaan Aljabar Boolean sendiri berasal dari nama seorang matematikawan asal Inggris, bernama George Boole. Dialah yang pertama kali mendefinisikan istilah itu sebagai bagian dari sistem logika pada pertengahan abad ke-19. Aljabar boolean merupakan aljabar 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 boolean terdiri dari variabel-variabel biner yang menunjukkan fungsi, suatu tanda sama dengan, dan suatu ekspresi aljabar yang dibentuk dengan menggunakan variabel-variabel biner, konstanta-konstanta 0 dan 1, simbol-simbol operasi logik, dan tanda kurung, (Arisah, 2009). Bentuk Boolean sangat penting untuk merancang rangkaian digital, khususnya rangkaian logika. Sedangkan aljabar Boole sangat berperan dalam penyedehanaan fungsi Boole. Batasan fungsi Boolean tentu saja memenuhi operasi-operasi dalam aljabar Boolean. Pernyataan logika AND, OR, NOT, dan kombinasinya dipenuhi oleh fungsi Boole. Dengan demikian fungsi Boole merupakan fungsi yang menyatakan hubungan antara variable-variabel masukan dan keluaran di dalam rangkaian logika. Jika suatu fungsi Boole memiliki variable-variabel masukan A, B, C, D … dan variabel keluarannya adalah Y, maka hubungan antara variabel-variabel masukan dan keluaran tersebut secara umum dapat dinyatakan sebagai Y = ƒ (A,B,C,D,…), (Wawan Setiawan,2000).
Contoh: A’BCD’+A’BCD=A’BC
3.
Fungsi hasil penyederhanaan merupakan penjumlahan dari semua suku esensi yang bukan berupa ulangan dan yang tidak dapat disederhanakan lebih lanjut, (saludin muis, 2012).
Dalam menyederhanakan persamaan dalam metode Quine-McCluskey, tahapan yang harus dilakukan adalah : 1.
Menyatakan variabel komplemen dengan 0, dan variabel yang bukan komplemen dengan 1. 2. Kelompokkan suku-suku berdasarkan jumlah 1. 3. Kombinasikan suku-suku tersebut dengan kelompok lain yang jumlah 1 nya berbeda satu, sehingga diperoleh bentuk prima yang sederhana. Setelah tahap tersebut selesai dilakukan, maka tahap selanjutnya adalah : 1.
Mencari Prime implicant : term yang menjadi calon term yang akan terdapat dalam fungsi sederhana. 2. Memilih Prime implicant yang memiliki jumlah literal paling sedikit. Dalam melakukan proses tersebut, digunakan tabel reduksi Quine-McCluskey dan tabel reduksi Prime implicant, (Susi Kartika Handayani Putri, 2005).
2.2.1 Definisi Aljabar Boolean Aljabar Boolean dapat didefinisikan secara absrak dalam beberapa cara. Cara yang paling umum adalah dengan menspesipikasikan unsur-unsur pembentuknya dan operasi-operasi yang menyertainya, seperti definisi berikut: Misalkan B adalah himpunan yang didefinisikan pada dua operator biner, + dan ., dan sebuah operator uner, ‘. Misalnya 0 dan 1
2.2 Aljabar Boolean Seorang ahli matematika dari inggris, George Boole (1815-1864) pada tahun 1854 memaparkan aturan aturan dasar logika dalam bukunya yang berjudul An Imvestigation of the Laws of Thought, on Which Are Founded the Matematical Theorities of Logic and Probabiloities, yang kemudian dikenal dengan 32
Saputra, Penerapan Metode Quine-Mc Cluskey Untuk Menyederhanakan Fungsi Boolean adalah 2 elemen yang berbeda dari B. Maka, tupel
Disebut Aljabar Boolean jika untuk setiap a, b, c € B berlaku aksioma (sering dinamakan juga Postulat Huntington) berikut: 1. Identitas (i)
a+0=a
(ii)
a . 1= a
Tabel 2. Tabel Kaidah Operasi + A
B
a+b
0
0
0
0 1 1
1 0 1
1 1 1
Tabel 3. Tabel Kaidah Operasi ‘ 2.
3.
4.
A
a’
Komutatif
0
1
(i)
a+b=b+a
1
0
(ii)
a.b=b.a
Kita harus memperhatikan bahwa keempat aksioma di dalam definisi 2.1 terpenuhi pada himpunan B = {0, 1} dengan dua operator biner dan satu operator uner yang didefinisikan di atas. 1. Identitas : jelas berlaku karena tabel dapat kita lihat bahwa : (i) 0 + 1 = 1 + 0 = 1 (ii) 1 . 0 = 0 . 1 = 0 yang memenuhi elemen identitas 0 dan 1 seperti yang didefinisikan pada postulat Huntington. 2. Komutatif : jelas berlaku dengan melihat simetri tabel operator biner. 3. Distributif : (i) a . (b + c) = (a . b) + (a . c) dapat ditunjukkan benar dari tabel operator biner di atas, dengan membentuk tabel kebenaran untuk semua nilai yang mungkin dari a, b, dan c (Tabel 2.4). Oleh karena nilai– nilai pada kolom a . (b + c) sama dengan nilai–nilai pada kolom (a . b) + (a . c), maka kesamaan a . (b + c) = (a . b) + (a . c) adalah benar. (ii) Hukum distributif a + (b . c) = (a + b) . (a + c) dapat ditunjukkan benar dengan membuat tabel kebenaran dengan cara yang sama seperti (i).
Distributif (i)
a . (b + c) = (a . b) + (a . c)
(ii)
a + (b . c) = (a + b) . (a + c)
Komplemen Untuk setiap a € B terdapat elemen unik a’ € b sehingga (i) a + a’ = 1 (ii)
a . a’ = 0
Elemen 0 dan 1 adalah dua elemen unik yang di dalam B . 0 disebut elemen terkecil dan 1 disebut elemen terbesar, (Rinaldi Munir. Matematika Diskrit. 2007 dan B. Gunawan Sudarsono, Logika Matematika,2012). 2.2.2
Aljabar Boolean Dua-Nilai Aljabar Boolean yang terkenal dan memiliki terapan yang luas adalah aljabar Boolean dua-nilai (two-valued Boolean algebra). Aljabar Boolean dua-nilai didefinisikan pada sebuah himpunan B dengan dua buah elemen 0 dan 1 (sering dinamakan bit – singkatan dari binary digit), yaitu B = {0, 1}, operator biner, + dan . operator uner, ‘. Kaidah untuk operator biner dan operator uner ditunjukkan pada Tabel 2.1, 2.2, dan 2.3 di bawah ini. Tabel 1. Tabel Kaidah Operasi . A
B
a.b
0
0
0
0 1 1
1 0 1
0 0 1
33
Jurnal Teknologi dan Sistem Informasi, Volume 2, Nomor 1, Desember 2015, hlm 31-41 a’ . (b + c) a . b’ + a . b . c + b’, dan
Tabel 4. Tabel Kebenaran a . (b + c) = (a . b) + (a . c) B
c
b +c
a . (b + c)
a. b
a. c
0
0
0
0
0
0 1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 0 1 1 1
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1
0 0 0 0 1 0 1
A 0 0 0 0 1 1 1 1
sebagainya adalah ekspresi Boolean. Ekspresi Boolean yang mengandung n peubah dinamakan ekspresi Boolean bagi n peubah. Dalam penulisan ekspresi Boolean selanjutnya, kita menggunakan perjanjian berikut : tanda kurung ‘()’ mempunyai prioritas pengerjaan paling tinggi, kemudian diikuti dengan operator ‘, + dan . Sebagai contoh, ekspresi a + b . c berarti a + (b . c), bukan (a + b) . c dan ekspresi a . b’ berarti a . (b’), bukan (a . b)’.
(a . b) + (a . c) 0 0 0 0 0 1 1 1
2.2.4
Prinsip Dualitas Di dalam aljabar Boolean, banyak ditemukan kesamaan (identity) yang dapat diperoleh dari kesamaan lainnya, misalnya pada dua aksioma distributif yang sudah disebutkan pada definisi 2.1 : (i) a . (b + c) = (a . b) + (a . c) (ii) a + (b . c) = (a + b) . (a + c) Aksioma yang kedua diperoleh dari aksioma pertama dengan cara mengganti dengan + dan mengganti + dengan . Prinsip ini dikenal dengan prinsip dualitas, prinsip yang juga kita temukan di dalam teori himpunan maupun logika. Definisi prinsip dualitas di dalam aljabar Boolean adalah sebagai berikut. Misalkan S adalah kesamaan (identity) di dalam aljabar Boolean yang melibatkan operator +, , dan ‘, maka jika pernyataan S* diperoleh dari S 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.
4.
Komplemen : jelas berlaku karena Tabel 2.4 memperlihatkan bahwa : (i) a + a’ = 1, karena 0 + 0’ = 0 + 1 = 1 dan 1 + 1’ = 1 + 0 = 1 (ii) a . a = 0, karena 0 . 0’ = 0 . 1 dan 1 . 1’ = 1 . 0 = 0 Karena keempat aksioma terpenuhi, maka terbukti bahwa B = {0 , 1} bersama–sama dengan operator biner + dan ., operator komplemen ‘ merupakan aljabar Boolean. Untuk selanjutnya, jika disebut aljabar Boolean, maka aljabar Boolean yang dimaksudkan di sini adalah aljabar Boolean dua-nilai. 2.2.3
Ekspresi Boolean Pada aljabar Boolean dua-nilai, B = {0, 1}. Kedua elemen B ini seringkali disebut elemen biner atau bit (singkatan binary bit). Peubah (variable) x disebut peubah Boolean atau peubah biner jika nilainya hanya dari B. Ekspresi Boolean dibentuk dari elemen – elemen B dan / atau peubah – peubah yang dapat dikombinasikan satu sama lain dengan operator +, ., dan ‘. Secara formal, ekspresi Boolean dapat didefinisikan secara rekursif sebagai berikut. Misalkan (B, +, ., ‘, 0, 1) adalah sebuah aljabar Boolean. Suatu ekspresi Boolean dalam (B, +, ., ‘) adalah : (i) Setiap elemen di dalam B, (ii) setiap peubah, (iii) jika e1 dan e2 adalah ekspresi Boolean, maka e1 + e2, e1 . e2, e1’ adalah ekspresi Boolean. Jadi menurut definisi di atas, setiap ekspresi di bawah ini, 0 1 a b c a+b a.b
2.2.5
Hukum–Hukum Aljabar Boolean Ada banyak hukum di dalam aljabar Boolean. Beberapa literatur bervariasi dalam mengungkapkan jumlah hukum pada aljabar Boolean, tetapi hukum–hukum yang paling penting ditampilkan pada tabel berikut.
34
Saputra, Penerapan Metode Quine-Mc Cluskey Untuk Menyederhanakan Fungsi Boolean Tabel 5. Tabel Hukum–Hukum Aljabar Boolean 1. Hukum identitas : (i) a + 0 = a (ii) a . 1 = a 3. Hukum komplemen : (i) a + a’ = 1 (ii) a . a’ = 0 5. Hukum involusi : (i) (a’)’ = a
7. Hukum komulatif : (i) a + b = b + a (ii) a . b = b . a
9. Hukum distributif : (i) a + (b . c) = (a + b) . (a + c) (ii) a . (b + c) = (a . b) + (a . c)
2.2.6
2. Hukum idempoten : (i) a + a = a (ii) a . a = a 4. Hukum dominansi : (i) a . 0 = 0 (ii) a + 1 = 1 6. Hukum penyerapan : (i) a + (a . b) =a (ii) a . (a + b) =a 8. Hukum asosiatif : (i) a + (b + c) = (a + b) + c (ii) a . (b . c) = (a . b) . c 10. Hukum De Morgan : (i) (a + b)’ = a’b’ (ii) (a . b)’ = a’ + b’
Fungsi Boolean
Fungsi Boolean (disebut juga fungsi biner) adalah pemetaan dari Bn ke B melalui ekspresi Boolean, kita menuliskannya sebagai f : Bn B yang dalam hal ini Bn adalah himpunan yang beranggotakan pasangan terurut ganda-n (ordered n-tuple) di dalam daerah asal B, (Hanif Alfatah, 2010 dan Mila Ramadiana Harahap, Giva Andriana Mutiara dan Bambang Pudjoatmojo, 2012). Misalkan ekspresi Boolean dengan n peubah adalah E(x1, x2, ..., xn). Menurut definisi di atas, setiap pemberian nilai – nilai kepada peubah x1, x2, ..., xn merupakan suatu pasangan terurut ganda-n di dalam daerah asal Bn dan nilai ekspresi tersebut adalah bayangannya di dalam daerah hasil B. Dengan kata lain, setiap ekspresi Boolean tidak lain merupakan fungsi Boolean. Misalkan sebuah fungsi Boolean adalah f(x, y, z) = xyz + x’y + y’z. Fungsi f memetakan nilai – nilai pasangan terurut ganda3 (x, y, z) ke himpunan {0, 1}. Contoh pasangan terurut ganda-3 misalnya (1, 0, 1) yang berarti x = 1, y = 0, dan z = 1 sehingga f(1, 0, 1) = 1 . 0 . 1 + 1’ . 0 + 0’ . 1 = 0 + 0 + 1 = 1. Selain secara aljabar, fungsi Boolean juga dapat dinyatakan dengan tabel kebenaran dan dengan rangkaian logika. Tabel kebenaran berisi nilai–nilai fungsi untuk semua kombinasi nilai–nilai peubahnya. Jika fungsi Boolean dinyatakan dengan tabel kebenaran, maka untuk fungsi Boolean dengan n buah peubah, kombinasi dari nilai peubah–peubahnya adalah sebanyak 2n. Ini berarti terdapat 2n baris yang berbeda di dalam tabel kebenaran tersebut. Misalkan n = 3, maka akan terdapat 23 = 8 baris tabel. Cara yang praktis membuat semua kombinasi tersebut adalah sebagai berikut : 1. Untuk peubah pertama, isi 4 baris pertama pada kolom pertama dengan sebuah 0 dan 4 baris selanjutnya dengan sebuah 1 berturut – turut. 2. Untuk peubah kedua, isi 2 baris pertama pada kolom kedua dengan 0 dan 2 baris berikutnya dengan 1, 2 baris berikutnya 0 lagi, dan 2 baris terakhir dengan 1. 3. Untuk peubah ketiga, isi kolom ketiga secara berselang – seling dengan 0 dan 1 mulai baris pertama sampai baris terakhir. Fungsi Boolean tidak selalu unik pada representasi ekspresinya. Artinya, dua buah fungsi yang ekspresi Booleannya berbeda dapat menyatakan dua buah fungsi yang sama. Misalkan f dan g adalah ekspresi dari suatu
11. Hukum 0/1 : (i) 0’ = 1 (ii) 1’ = 0 Kita dapat memperoleh hukum–hukum aljabar Boolean dari hukum–hukum aljabar dengan cara mempertukarkan dengan +, atau dengan + dengan , atau dengan U dengan 1, atau T dengan 1 dengan 0, atau F dengan 0 Perhatikanlah bahwa hukum yang ke(ii) dari setiap hukum di atas merupakan dual dari hukum yang ke-(i). Sebagai contoh, Hukum komutatif : a + b=b+a dualnya : a . b=b.a Hukum asosiatif : a + (b + c) = (a + b) + c dualnya : a . (b . c) = (a . b) . c Hukum distributif : a + (b . c) = (a + b) . (a + c) dualnya : a . (b + c) = (a . b) + (a . c)
35
Jurnal Teknologi dan Sistem Informasi, Volume 2, Nomor 1, Desember 2015, hlm 31-41 fungsi Boolean. Fungsi f dan g dikatakan merupakan fungsi yang sama jika keduanya memiliki nilai yang sama pada tabel kebenaran untuk setiap kombinasi peubah – peubahnya. Sebagai contoh, fungsi : f(x, y, z) = x’y’z + x’yz + xy’ dan g(x, y, z) = x’z + xy’ adalah dua buah fungsi Boolean yang sama. Kesamaan ini dapat dilihat pada tabel berikut.
kurang sedehana. Jika dua istilah hanya berbeda dalam satu bit seperti 101 dan 111 yaitu satu variabel muncul dalam kedua bentuk (variabel dan penyangkalan), maka kita bisa menggunakan hukum pelengkap. Iteratif, kita membandingkan semua istilah dan menghasilkan perdana implicant. 2. Mencari Esensial Perdana implicant Menggunakan prime implicants dari langkah di atas, kita menghasilkan tableuntuk menemukan prime implicants penting. Catatan bahwa beberapa prime implicants bisa berlebihan dan dapat dihilangkan, tetapi jika mereka muncul hanya sekali, mereka tidak bisa dihilangkan dan memberikan implicant utama. 3. Mencari Prime implicant Lainnya
Tabel 6. Tabel Kebenaran Fungsi f Dan g X 0 0 0 0 1 1 1 1
Y
Z
0
0
0 1 1 0 0 1 1
1 0 1 0 1 0 1
f = x’y’z + x’yz + xy’ 0 1 0 1 1 1 0 0
g = x’z + xy’ 0 1 0 1 1 1 0 0
Hal ini tidak perlu jika essential prime implicants mencakup semua minterm. Dalam hal ini, kami mempertimbangkan perdana implicant lainnya untuk memastikan bahwa semua minterm telah tertutup. alih-alih menggunakan trial and error untuk mempertimbangkan prime implicants kami dapat menggunakan Metode Petrick, (P.W. Chandana Prasad, Azam Beg, dan Ashutosh Kumar Singh, 2009).
Jika sebuah fungsi Boolean tidak unik dalam representasi ekspresinya, kita masih dapat menemukan ekspresi Boolean lainnya yang menspesifikasikan fungsi yang sama dengan melakukan manipulasi aljabar terhadap ekspresi Boolean. Yang dimaksud dengan memanipulasi atau menyederhanakan fungsi Boolean adalah menggunakan hukum–hukum aljabar Boolean untuk menghasilkan bentuk yang ekivalen. Sebagai contoh, f(x, y, z) = x’y’z + x’yz + xy’ = x’z(y’ + y) + xy’ (Hukum distributif) = x’z . 1 + xy’ (Hukum komplemen) = x’z + xy’ (Hukum identitas) Manipulasi aljabar pada ekspresi Boolean disebut juga dengan penyederhanaan fungsi Boolean, (Rialdi Munir, Matematika Diskrit, 2007). Metode ini juga dikenal sebagai metode tabulasi karena memberikan langkah-langkah deterministik untuk memeriksa bentuk minimum fungsi berdasarkan pemilihan essential prime implicants dengan menggunakan tabel. Langkah-langkah dapat dikategorikan kedalam tiga tahapan: 1. Menenentukan implicant Perdana
2.2.8
Penyederhanaan Fungsi Boolean
Dalam menyederhanakan suatu ekspresi Boolean yang rumit, kita mengubah rangkaian digital yang rumit menjadi rangkaian yang lebih sederhana. Dengan aljabar Boole, kita dapat menganalisa dan merancang sistem digital secara lebih mudah, (Slamet Winardi , Sebastiao Domingos F. Belo, 2012). Fungsi boolean sering kali mengandung operasi-operasi yang tidak perlu, literatur atau suku-suku yang tidak berlebihan. Oleh karena itu, kita dapat menyederhanakan fungsi boolean lebih lanjut. Menyederhanakan fungsi boolean artinya mencari bentuk fungsi lain yang ekivalen tetapi dengan literal atau operasi yang lebih sedikit. Penyederhanaan fungsi boolean disebut juga minimisasi fungsi. Contohnya, f(x,y) = x’y + xy’ +y’ dapat disederhanakan menjadi f(x,y) = x’ + y’ Dipandang dari segi aplikasi aljabar boolean, fungsi boolean yang lebih sederhana berarti rangkaian logikanya lebih sederhana (menggunakan jumlah gerbang logika lebih sedikit). Ada 3 metode yang dapat digunakan untuk menyederhanakan fungsi boolean: 1. Secara aljabar, menggunakan hukumhukum aljabar boolean
Dalam langkah ini, kita mengganti literal dalam bentuk 0 dan 1 dan menghasilkan tabel. Awalnya, jumlah baris dalam tabel sama dengan jumlah total fungsi minterm yang asli yang
2. 36
Metode Peta Karnaugh
Saputra, Penerapan Metode Quine-Mc Cluskey Untuk Menyederhanakan Fungsi Boolean 3.
3.
Metode Quine-McCluskey tabulasi)
(metode
menyederhanakan fungsi Boolean dalam bentuk SOP (sum-of-product) atau bentuk POS (product-of-sum), seperti yang telah dijelaskan pada bab 2 sebelumnya. Metode Quine-McCluskey menyederhanakan fungsi Boolean dengan menggabungkan minterm/maxterm menjadi himpunan bentuk prima (prime-implicant), di mana sebanyak mungkin peubah dieliminasi (dihilangkan) secara maksimal. Minterm/maxterm yang digabung untuk membentuk sebuah bentuk prima harus memiliki tepat satu buah peubah yang nilainya berbeda (komplemen dan non-komplemen). Bentuk prima yang terbentuk juga dapat digabung untuk membentuk bentuk prima lainnya, apabila memiliki satu buah peubah yang nilainya berbeda. Prosedur ini dilakukan berulang kali hingga tidak terdapat bentuk prima yang dapat terbentuk lagi. Untuk proses selanjutnya, metode ini memilih bentuk prima yang paling sederhana, yaitu bentuk prima yang tidak membentuk bentuk prima yang baru. Dari bentuk-bentuk prima yang sederhana ini, dipilih bentuk prima yang memiliki jumlah peubah paling sedikit (bentuk prima yang paling panjang) dan mencakup sebanyak mungkin minterm / maxterm dari fungsi Boolean yang di-input. Bentuk prima inilah yang merupakan hasil minimisasi dari fungsi Boolean. Keunggulan dari metode QuineMcCluskey adalah kemampuannya untuk melakukan proses penyederhanaan terhadap fungsi Boolean dengan jumlah peubah yang besar. Selain itu, prosedur atau langkah–langkah pengerjaan dari metode ini sangat sistematis, artinya pengerjaan setiap langkah sangat rapi, teratur dan terstruktur, sehingga metode ini lebih mudah diprogram di dalam komputer dibandingkan dengan metode penyederhanaan lainnya. Sebagai contoh, dilakukan penyederhanaan terhadap fungsi Boolean dalam bentuk SOP : f (w, x, y, z) = ∑ (1, 4, 6, 7, 8, 9, 10, 11, 15). Langkah–langkah penyederhanaan fungsi Boolean dengan metode QuineMcCluskey adalah sebagai berikut: LANGKAH-1 : Nyatakan tiap minterm dalam n peubah menjadi string bit biner yang panjangnya n. (Pada contoh ini, jumlah peubah adalah 4 sehingga n = 4)
METODE PENELITIAN
Metodologi penelitian yang dilakukan bertujuan untuk mengatur dan mempermudah pelaksanaan pekerjaan. Pembuatan perangkat lunak metode fungsi boolean untuk menyederhanakan rangkaian logika ini menggunakan model proses water fall atau model linear sekuensial dengan tahap-tahap pembangunan sistem secara berurutan yaitu sebagai berikut : 1. Tahap pengumpulan data Pada tahap pengumpulan data menggunakan tahap studi literatur, tahap ini menjelaskan komponenkomponen yang terkait dalam metode fungsi boolean. 2. Analisis Tahap ini digunakan untuk menjelaskan permasalahan yang ada dan menganalisa proses penyederhanaan yang akan dilakukan. 3. Perancangan Langkah-langkah dalam tahap perancangan, meliputi : parancangan algoritma, perancangan struktur data, perancangan data input dan perancangan data output untuk membangun program 4. Implementasi Program Setelah tahap studi literatur, analisis dan perancangan selesai dikerjakan, tahap selanjutnya adalah tahap pengkodean atau pembuatan program yang dibuat dalam modul-modul agar sesuai dengan rancangan program. 5. Pengujian Pada tahap ini akan dilakukan proses pengujian program untuk menyederhanakan rangkaian logika dengan cara memasukkan jumlah variabel, term masukan, dan ekspresi masukannya apakah berjalan dengan baik atau tidak. (Susi Kartika Handayani Putria, 2005, Penyederhanaan Fungsi Boolean Meng Gunakan Metode Peta Karnaugh Dan Quine Mc.Cluskey Untuk Membentuk Rangkaian Logika.) 4. ANALISIS dan HASIL 4.1 Pembahasan Proses penyederhanaan fungsi Boolean dengan metode Quine-McCluskey mempunyai 7 (tujuh) langkah pengerjaan untuk 37
Jurnal Teknologi dan Sistem Informasi, Volume 2, Nomor 1, Desember 2015, hlm 31-41 2 4 6 8 9 10 11 12 13 14
0 0 0 1 1 1 1 1 1 1
0 1 1 0 0 0 0 1 1 1
1 0 1 0 0 1 1 0 0 1
Hasil Penyelesaian Langkah - 6 :
0 0 0 0 1 0 1 0 1 0
LANGKAH-7 : Pilih bentuk prima yang memiliki jumlah literal paling sedikit namun mencakup sebanyak mungkin minterm dari ekspresi Boolean semula. Hal ini dapat dilakukan dengan cara berikut : LANGKAH-7.A : Tandai kolom-kolom yang mempunyai satu buah tanda 'x' dengan tanda '*', lalu beri tanda '√' di sebelah kiri bentuk prima yang mencakup minterm yang mempunyai tanda '*' tersebut. Bentuk prima ini telah dipilih untuk fungsi Boolean sederhana. Hasil Penyelesaian Langkah-7 dan 7.A :
LANGKAH-2 : Kelompokkan tiap minterm berdasarkan jumlah '1' yang dimilikinya.
LANGKAH-3 : Kombinasikan minterm dalam n peubah dengan kelompok lain yang jumlah '1'nya berbeda satu, sehingga diperoleh bentuk prima (prime-implicant) yang terdiri dari n-1 peubah. minterm yang dikombinasikan diberi tanda '√' LANGKAH-4 : Kombinasikan minterm dalam n - 1 peubah dengan kelompok lain yang jumlah '1'-nya berbeda satu, sehingga diperoleh bentuk prima yang terdiri dari n-2 peubah. LANGKAH-5 : Teruskan langkah 4 sampai diperoleh bentuk prima yang sesederhana mungkin. Hasil Penyelesaian Langkah-3, 4 dan 5 : Dikombinasikan menjadi :
LANGKAH-7.B : Untuk setiap bentuk prima yang telah ditandai dengan 'v', beri tanda minterm yang dicakup oleh bentuk prima tersebut dengan tanda 'v' (di baris bawah setelah tanda '*'). Hasil Penyelesaian Langkah-7.B :
LANGKAH-7.C : Periksa apakah masih ada minterm yang belum memiliki tanda 'v' (artinya, belum dicakup oleh bentuk prima terpilih). Jika ada, pilih dari bentuk prima yang tersisa yang mencakup sebanyak mungkin minterm tersebut. Beri tanda 'v' untuk setiap bentuk prima yang dipilih itu serta minterm yang dicakupnya. LANGKAH-7.D : Ulangi langkah 7.C sampai seluruh minterm sudah dicakup oleh bentuk prima Hasil Penyelesaian Langkah - 7.C dan 7.D : Sampai tahap ini, masih ada minterm yang belum tercakup dalam bentuk prima terpilih, yaitu 3, 8, 10. Untuk mencakup minterm tersebut, kita pilih bentuk prima (8,10) dan (1,3) karena mencakup minterm 3, 8 dan 10 sekaligus.
LANGKAH-6 : Ambil semua bentuk prima yang tidak bertanda '√'. Buatlah tabel baru yang memperlihatkan minterm dari ekspresi Boolean semula yang dicakup oleh bentuk prima tersebut (tandai dengan 'x').
38
Saputra, Penerapan Metode Quine-Mc Cluskey Untuk Menyederhanakan Fungsi Boolean 4.
Sekarang, semua minterm sudah tercakup dalam bentuk prima terpilih. Bentuk prima yang terpilih adalah : 1, 9 yang bersesuaian dengan term x’y’z 4, 6 yang bersesuaian dengan term w'xz' 7,15 yang bersesuaian dengan term xyz 8,9,10,11 yang bersesuaian dengan term wx’ Dari langkah – langkah penyederhanaan di atas, hasil minimisasi fungsi Boolean dalam bentuk SOP: f (w, x, y, z) = ∑ (1, 4, 6, 7, 8, 9, 10, 11, 15) adalah f (w, x, y, z) = x’y’z + w'xz' + xyz + wx’. Misalkan input fungsi dalam bentuk POS dengan nomor–nomor maxterm yang sama dengan nomor – nomor minterm pada contoh sebelumnya. f (w, x, y, z) = (1, 4, 6, 7, 8, 9, 10, 11, 15) Langkah – langkah dan hasil penyederhanaan sama dengan penyederhanaan dalam bentuk SOP, yaitu menghasilkan bentuk prima terpilih (1,9), (4,6), (7,15), dan (8,9,10,11). Perbedaannya hanya terletak pada bentuk output. Bentuk prima terpilih diubah ke bentuk POS (sama dengan bentuk input). 1, 9 yang bersesuaian dengan term (x+y+z') 4, 6 yang bersesuaian dengan term (w+x’+z) 7,15 yang bersesuaian dengan term (x’+y’+z’) 8,9,10,11 yang bersesuaian dengan term (w’+x ) Dengan demikian, hasil minimisasi fungsi Boolean dalam bentuk POS adalah: f(w, x, y, z) = (x+y+z')(w + x' + z(x’+y’+z’) (w’+x )
Hasil penyederhanaan, didapat : f(w, x, y, z) = y z' + x z' + w x' + w y'.
Gambar 7. Proses Penyederhanaan Fungsi Boolean (Pengujian-1) Tahapan – tahapan proses penyederhanaan yang dihasilkan adalah sebagai berikut: penyederhanaan fungsi boolean f(w, x, y, z) = ∑ (2, 4, 6, 8, 9, 10, 11, 12, 13, 14) dengan metode Quine-McCluskey LANGKAH - 1 : Nyatakan tiap minterm dalam n peubah menjadi string bit biner yang panjangnya n. Hasil Penyelesaian Langkah - 1 :
Gambar 8. Hasil Penyelesaian Langkah 1 LANGKAH - 2 : Kelompokkan tiap minterm berdasarkan jumlah '1' yang dimilikinya. Hasil Penyelesaian Langkah - 2 :
4.2 Pengujian Pertama Sebagai contoh, penulis meng-input data sebagai berikut. 1. Bentuk fungsi input : SOP (sum-ofproduct) 2. Banyak peubah (variabel) = 4 buah, yaitu w, x, y dan z. 3. Input nomor minterm : 2;4;6;8;9;10;11;12;13;14.
Gambar 9 Hasil Penyelesaian Langkah 2 LANGKAH - 3 : Kombinasikan minterm dalam n peubah dengan kelompok lain yang jumlah '1'nya berbeda satu, sehingga diperoleh bentuk prima (prime-implicant) yang terdiri dari n-1 peubah. minterm yang dikombinasikan diberi tanda 'v' 39
Jurnal Teknologi dan Sistem Informasi, Volume 2, Nomor 1, Desember 2015, hlm 31-41 LANGKAH - 4 : Kombinasikan minterm dalam n - 1 peubah dengan kelompok lain yang jumlah '1'-nya berbeda satu, sehingga diperoleh bentuk prima yang terdiri dari n-2 peubah. LANGKAH - 5 : Teruskan langkah 4 sampai diperoleh bentuk prima yang sesederhana mungkin. Hasil Penyelesaian Langkah - 3, 4 dan 5 : Dikombinasikan menjadi :
Hasil Penyelesaian Langkah - 7 dan 7.A :
Gambar 12. Hasil penyelesaian langkah 7A LANGKAH - 7.B : Untuk setiap bentuk prima yang telah ditandai dengan 'v', beri tanda minterm yang dicakup oleh bentuk prima tersebut dengan tanda 'v' (di baris bawah setelah tanda '*'). Hasil Penyelesaian Langkah - 7.B :
Gambar 10. Hasil Penyelesaian Langkah 3, 4, 5 LANGKAH - 6 : Ambil semua bentuk prima yang tidak bertanda 'v'. Buatlah tabel baru yang memperlihatkan minterm dari ekspresi Boolean semula yang dicakup oleh bentuk prima tersebut (tandai dengan 'x'). Hasil Penyelesaian Langkah - 6 :
Gambar 13. Hasil Penyelesaian Langkah 7B LANGKAH - 7.C : Periksa apakah masih ada minterm yang belum memiliki tanda 'v' (artinya, belum dicakup oleh bentuk prima terpilih). Jika ada, pilih dari bentuk prima yang tersisa yang mencakup sebanyak mungkin minterm tersebut. Beri tanda 'v' untuk setiap bentuk prima yang dipilih itu serta minterm yang dicakupnya. LANGKAH - 7.D : Ulangi langkah 7.C sampai seluruh minterm sudah dicakup oleh bentuk prima Hasil Penyelesaian Langkah - 7.C dan 7.D :
Gambar 11. Hasil Penyelesaian Langkah 6 LANGKAH - 7 : Pilih bentuk prima yang memiliki jumlah literal paling sedikit namun mencakup sebanyak mungkin minterm dari ekspresi Boolean semula. Hal ini dapat dilakukan dengan cara berikut : LANGKAH - 7.A : Tandai kolom-kolom yang mempunyai satu buah tanda 'x' dengan tanda '*', lalu beri tanda 'v' di sebelah kiri bentuk prima yang mencakup minterm yang mempunyai tanda '*' tersebut. Bentuk prima ini telah dipilih untuk fungsi Boolean sederhana.
Gambar 5.8 Hasil penyelesaian langkah 7C dan 7D Dengan demikian, fungsi Boolean hasil penyederhanaan adalah : f(w, x, y, z) = y z' + x z' + w x' + w y' 40
Saputra, Penerapan Metode Quine-Mc Cluskey Untuk Menyederhanakan Fungsi Boolean 5. KESIMPULAN dan SARAN
1.
2.
3.
4.
DAFTAR PUSTAKA
Setelah menyelesaikan perancangan sistem penerapan metode Quine McCluskey untuk menyederhanakan fungsi Boolean maka dapat diambil kesimpulan sebagai berikut : Sistem yang penulis rancang hanya mampu menyederhanakan fungsi Boolean dalam bentuk penjumlahan dari hasil kali dan perkalian dari hasil jumlah. Jumlah fungsi Boolean yang dapat disederhanakan dengan sistem ini baru 10 variabel. Sistem ini akan memberikan penjelasan setiap tahap-tahap penyederhanaan sehingga mahasiswa/pengguna dapat dengan muda memahami proses penyederhanaan fungsi Boolean. Metode Quine McCluskey lebih mudah dan cepat bila dikerjakan dengan menggunakan sistem komputer (program)
Adhav Vitthal, Buchade Amar, Pune, Maharashtra, India, 2009, Modified Quine-McCluskey Method. Susi Kartika Handayani Putria, 2005, Penyederhanaan Fungsi Boolean Meng Gunakan Metode Peta Karnaugh Dan Quine Mc.Cluskey Untuk Membentuk Rangkaian Logika. Arisah, 2009, Aljabar Boolean. B. Gunawan Sudarsono, 2012, Logika Matematika. Mila Ramadiana Harahap, Giva Andriana Mutiara, Bambang Pujdjoatmojo,2012, Aplikasi Pembelajaran Matematika Diskrit (Karnaugh Map) Sebagai Alat Bantu Pengajaran. P.W. Chandana Prasad, Azam Beg, Ashutosh Kumar Singh, 2009, Effect of Quine-McCluskey Simplification on Boolean Space Complexity, Jurnal,CITISIA. Rinaldi Munir, 2005, Matematika Diskrit, Informatika Bandung. Rinaldi Munir, 2007, Matematika Diskrit, Informatika Bandung. Safrina Amanah Sitepu, 2009, Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital. saludin muis, 2012, Teknik Digital Dasar. Slamet Winardi, F. Belo Sebastio Domingos, 2012, Rancang Bangun Software Pembelajaran Interaktif Dasar Digital. Wawan Setiawan, 2000, Pengantar Sistem Digital.
Beberapa saran yang mungkin dapat membantu dalam pengembangan sistem penyederhanaan fungsi Boolean ini yaitu: 1.
2.
Sistem ini agar dikembangkan lagi sehingga dapat diakses melalui media online dan juga HP Pemahaman proses penyederhanaan dapat dikembangkan dengan menambahkan animasi proses penjelasan yang dibangun dengan aplikasi Macromedia Flash.
41
