�ݺ�ߣ

ABSTRAK

Dalam sistem penyederhanaan fungsi Boolean, metode aljabar dan metode peta
karnaugh sangat sulit untuk menyederhanakan fungsi Boolean dengan jumlah
variabel maksimum 4(empat) variabel. Karena itu disimulasikan metode Quine-
McCluskey yang mampu menyederhanakan fungsi Boolean dengan lebih dari
4(empat) variabel. Maka dari itu untuk menyelesaikan masalah penyederhanaan
fungsi boolean digunakan metode Quine-McCluskey. Metode ini merupakan
metode tabulasi dengan dua langkah utama yaitu pencarian prime implicant
(implikan utama) dan penentuan prime implicant (implikan utama) inti.

Kata kunci : fungsi Boolean, metode Quine-Mccluskey, prime implicant

PENDAHULUAN
1. Latar Belakang
Aljabar Boolean, sebagai salah satu cabang matematika, pertama kali
dikemukakan seorang matematikawan Inggris, George Boole, pada tahun 1854.
Boole melihat bahwa himpunan dan logika proposisi mempunyai sifat –sifat yang
serupa. Dalam buku The Law of Thought, Boole memaparkan aturan-aturan dasar
logika (yang kemudian dikenal sebagai Logika Boolean). Aturan dasar logika ini
membentuk struktur matematika yang disebut aljabar Boolean. Pada tahun 1938,
Claude Shannon memperlihatkan penggunaan aljabar Boolean untuk merancang
sirkuit yang menerima masukkan 0 dan 1 dan menghasilkan keluaran juga 0 dan
1. Aljabar Boolean telah menjadi dasar teknologi komputer digital karena
rangkaian elektronik di dalam komputer juga bekerja dengan metode operasi bit, 0
dan 1. Saat ini aljabar Boolean digunakan secara luas dalam perancangan
rangkaian pensaklaran, rangkaian digital, dan rangkaian IC (integrated circuit)
komputer.
Definisi dari sebuah Aljabar Boolean adalah sebuah sistem aljabar yang
terdiri atas himpunan semesta S bersama dengan dua buah operasi yaitu :
penjumlahan/addition (+) dan perkalian/multiplication ( . ). Aturan-aturan yang
ada pada aljabar boolean pada intinya adalah pembentukan persamaan yang
menggunakan beberapa jenis operator (OR, AND, dan Negasi) sehingga aljabar
boolean merupakan alat matematis yang cocok untuk keperluan analisis rangkaian

logika. Untuk mendapatkan rangkaian logika maka diperlukannya metode-metode
penyederhanaan agar fungsi booleannya menghasilkan fungsi yang sederhana
sehingga dapat membentuk rangkaian logika.
Fungsi Boolean seringkali mengandung operasi-operasi yang tidak perlu,
literal atau suku-suku yang berlebihan. Oleh karena itu, diperlukan
penyerderhanaan fungsi Boolean. Menyederhanakan fungsi Boolean sama artinya
mencari bentuk fungsi yang ekivalen tetapi dengan jumlah literal atau operasi
yang lebih sedikit. Dalam pembuatan sirkuit elektronik bentuk yang terbaik ini
dimaksudkan untuk memperoleh biaya minimum dalam pembuatan sirkuit
elektronik dan menghasilkan kinerja yang cepat dalam pengoperasian.
Penyelesain 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 juga lebih sederhana (menggunakan jumlah
gerbang logika lebih sedikit). Ada tiga metode yang dapat digunakan untuk
menyederhanakan fungsi Boolean :
1. Secara aljabar, menggunakan hukum-hukum aljabar Boolean.
2. Metode Peta Karnaugh.
3. Metode Quine-McCluskey.
Penyederhanaan secara Aljabar, dilakukan dengan memodifikasi persamaan
Boolean dimana dalam penyederhanaannya menggunakan teorema / aksioma
dualitas untuk membuat bentuk yang paling sederhana. Salah satu cara yang dapat
digunakan adalah memanipulasi Aljabar Boolean. Karena metode Aljabar
Boolean bersifat trial and error, maka penyederhanaan dengan metode aljabar ini
tidak digunakan dalam kasus nyata. Metode yang paling banyak digunakan adalah
Peta Karnaugh dimana cara menggambarkannya dengan sejumlah kotak
berbentuk persegi panjang yang berisi minimal term (minterm) dari fungsi
booleannya dan banyaknya kotak bergantung pada banyaknya jumlah input dari
fungsi tersebut. Metode lain yang digunakan adalah metode Quine-McCluskey
atau biasa disebut dengan metode tabulasi.

Pada prakteknya, fungsi boolean yang jumlah variabelnya kurang dari
empat dapat dengan mudah disederhanakan menggunakan metode Aljabar dan
Peta Karnaugh. Sedangkan fungsi boolean yang jumlah variabelnya lebih dari
empat, kedua metode diatas sering kali menghasilkan penyederhanaan fungsi yang
bentuknya tidak sederhana. Metode Quine-McCluskey lebih tepat untuk
menyelesaikan kasus ini. Penyederhanaan dengan menggunakan metode Quine
McCluskey dilakukan dengan cara menyatakan variabel komplemen dengan 0
variabel bukan komplemen dengan 1 dari bentuk baku fungsi booleannya, setelah
itu mengkelompokan suku-suku berdasarkan jumlah 1 lalu mengkombinasikan
suku-suku tersebut dengan kelompok lain yang jumlah 1-nya berbeda satu
sehingga diperoleh bentuk prime yang sederhana untuk mencari prime implicant
serta memilih prime implicant yang mempunyai jumlah literal paling sedikit.
Dari uraian di atas, penulis ingin mengggunakan metode Quine-McCluskey
untuk menyederhanakan fungsi Boolean dengan judul “Menyederhanakan
Fungsi Boolean dengan Menggunakan Metode Quine-McCluskey”.

2. Rumusan Masalah
Berdasarkan latar belakang diatas, masalah yang akan dibahas adalah:
Bagaimana cara menyederhanakan fungsi Boolean dengan menggunakan metode
Quine-McCluskey ?

3. Tujuan
Tujuan penulisan pada makalah ini adalah untuk menyelesaikan masalah
penyederhanaan fungsi boolean dengan menggunakan metode Quine-McCluskey.

4. Batasan Masalah
Batasan masalah dalam penulisan Seminar Matematika ini adalah sebagai
berikut : Bentuk baku fungsi boolean yang digunakan adalah Sum Of Product
(SOP).

KAJIAN PUSTAKA
1. Aljabar Boolean
Aljabar Boolean dapat didefinisikan secara abstrak dalam beberapa cara.
Cara yang paling umum adalah dengan menspesifikasikan unsur-unsur
pembentuknya dan operasi-operasi yang menyertainya.
Misalkan terdapat :
- Dua operator biner: + dan
- Sebuah operator uner: ‟.
- B : himpunan yang didefinisikan pada opeartor +, , dan ‟
- 0 dan 1 adalah dua elemen yang berbeda dari B. Maka, tupel
(B, +, , ‟)
disebut aljabar Boolean jika untuk setiap a, b, c B berlaku aksioma-aksioma
atau postulat Huntington berikut:
1. Identitas
2. Komutatif
3. Distributif
4. Komplemen
Terdapat perbedaan antara aljabar Boolean dengan aljabar biasa untuk aritmatika
bilangan riil :
1. hukum distributif yang kedua, a + (b c) = (a + b) (a + c), benar untuk aljabar
Boolean, tetapi tidak benar untuk aljabar biasa.
2. Aljabar Boolean tidak memiliki kebalikan perkalian atau kebalikan
penjumlahan
3. Aksioma nomor 4 mendefinisikan operator yang dinamakan komplemen yang
tidak tersedia pada aljabar biasa.
4. Aljabar biasa memperlakukan himpunan bilangan riil dengan elemen yang
tidak berhinggga banyaknya. Sedangkan aljabar Boolean memperlakukan
himpunan elemen B yang sampai sekarang belum didefenisikan, tetapi pada
aljabar Boolean dua-nilai, B didefenisikan sebagai himpunan dengan hanya dua
nilai, 0 dan 1.

Berhubung elemen-elemen B tidak didefenisikan nilainya (kita bebas
menentukan anggota-anggota B), maka untuk mempunyai sebuah aljabar Boolean,
kita 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 diatas.

2. 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. 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 ganda-3 (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.
Contoh. Contoh-contoh fungsi Boolean yang lain:
1. f(x) = x
2. f(x, y) = x‟y + xy‟+ y‟
3. f(x, y) = x‟ y‟
4. f(x, y) = (x + y)‟
5. f(x, y, z) = xyz‟
Setiap peubah di dalam fungsi Boolean, termasuk dalam bentuk
komplemennya, disebut literal. Contoh: Fungsi h(x, y, z) = xyz‟ pada contoh di
atas terdiri dari 3 buah literal, yaitu x, y, dan z‟. Fungsi tersebut berharga 1 jika
x = 1, y = 1, z = 0 sebab
h(1, 1, 0) = 1 · 1 · 0‟ = (1 · 1) · 1 = 1 · 1 = 1

dan berharga 0 untuk harga x, y, dan z lainnya. 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 dengan 0 lagi, dan 2 baris
terakhir dengan 1.
3. Untuk peubah ketiga, isi kolom ketiga secara berselang-seling dengan 0 dan 1
mulai dari baris pertama sampai baris terakhir.
Contoh. Diketahui fungsi Booelan f(x, y, z) = xy z‟, nyatakan h dalam tabel
kebenaran.
Penyelesaian:
Tabel 3.1
x y z f(x, y, z) = xy z‟
0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 0

1 1 0 1

1 1 1 0

3. Bentuk Baku

Pada bentuk ini, suku-suku yang membentuk fungsi dapat mengandung satu,
dua, atau sejumlah literal. Dua tipe bentuk baku adalah bentuk baku SOP dan
bentuk baku POS. 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)

4. Aplikasi Aljabar Boolean
Aljabar Boolean memiliki aplikasi yang luas dalam bidang keteknikan,
antara lain:
1. Jaringan pensaklaran (switching network)
2. Sirkuit Elektronik

5. Penyederhanaan Fungsi Boolean

Ada tiga metode yang dapat digunakan untuk menyederhanakan fungsi
Boolean :
1. Secara aljabar, menggunakan hukum-hukum aljabar Boolean,
Contoh : sederhanakanlah fungsi Boolean f(x, y, z) = xz’ + y’z + xyz’
Penyelesaian :
f(x, y, z) = xz’ + y’z + xyz’
= xz’ · 1 + y’z + xyz’ (Hukum identitas)
= xz’ (1 + y) + y’z (Hukum distributif)
= xz’ · 1 + y’z (Hukum dominansi)
= xz’ + y’z (Hukum identitas)
Pada soal diatas fungsi Boolean diminimumkan dengan trik manipulasi
aljabar dengan prosedur yang cut-and-try yang memanfaatkan postulat, hukum-
hukum dasar, dan metode manipulasi lain yang sudah dikenal. Untuk tiga variabel
saja hukum yang dipakai sudah tiga. Bagaimana untuk enam varibel ke atas?
Terlebih lagi tidak ada aturan khusus yang harus diikuti yang akan menjamin
menuju ke jawaban akhir. Maka metode aljabar hanya cocok untuk

menyederhanakan fungsi Boolean yang jumlah variabelnya kecil misalnya 4
variabel dan akan sangat sulit bila variabelnya lebih dari 4.

2. Metode peta Karnaugh,
Contoh : carilah fungsi sederhana dari f(v, w, x, y, z) = ∑ (0, 2, 4, 6, 9, 11,
13, 15, 17, 21, 25, 27, 29, 31).
Penyelesaian :
Peta Karnaugh dari fungsi tersebut adalah :
xyz
vw 000 001 110 010 110 111 101 100
00 1 0 0 1 1 0 0 1
01 0 1 1 0 0 1 1 0
11 0 1 1 0 0 1 1 0
10 0 1 0 0 0 0 1 0

Fungsi minimasi: f(v, w, x, y, z) = wz + v’w’z’ + vy’z
Pada soal diatas peta Karnaugh untuk lima variabel dibuat dengan anggapan
ada dua buah peta empat variabel yang disambungkan, demikian juga untuk enam
variabel. Untuk fungsi Boolean 6 variabel pengerjaan penyederhanaan dengan
peta Karnaugh sudah mulai rumit. Bagaimana untuk variabel 6 ke atas ? Maka
akan semakin rumit, sebab ukuran peta bertambah besar. Selain itu, metode peta
Karnaugh lebih sulit diprogram dengan komputer karena diperlukan pengamatan
visual untuk mengidentifikasi minterm-minterm yang akan dikelompokkan.
Untuk itu diperlukan metode penyerderhanaan yang lain yang dapat
diprogram dan dapat digunakan untuk fungsi Boolean dengan sembarang jumlah
peubah. Metode alternatif tersebut adalah metode Quine-McCluskey (yang akan
dibahas oleh penulis pada Bab Pembahasan).

PEMBAHASAN

Metode Quine-McCluskey
Metode peta Karnaugh hanya cocok digunakan jika fungsi Boolean
mempunyai jumlah peubah paling banyak 6 peubah. Jika jumlah peubah yang
terlibat pada suatu fungsi Boolean lebih dari 6 buah maka penggunaan peta
Karnaugh menjadi semakin rumit, sebab ukuran peta bertambah besar. Selain itu,
metode peta Karnaugh lebih sulit diprogram dengan komputer karena diperlukan
pengamatan visual untuk mengidentifikasi minterm-minterm yang akan
dikelompokkan. Untuk itu diperlukan metode penyederhanaan yang lain yang
dapat diprogram dan dapat digunakan fungsi Boolean dengan sembarang jumlah
peubah. Metode alternatif tersebut adalah metode Quine-McCluskey yang
dikembangkan oleh W.V.Quine dan E.J.McCluskey pada tahun 1950.
Penyederhanaan menggunakan metode Quine-McCluskey memberikan hasil
yang pasti. Metode ini digunakan untuk mempresentasikan minimasi ekspresi
fungsi boolean, dan menyediakan sebuah prosedur sistematis untuk membangun
semua Prime Implicant dan kemudian mengambil sebuah set minimum dari prime
yang ada.
Langkah-langkah metode Quine-McCluskey untuk menyederhanakan fungsi
Boolean dalam bentuk SOP terbagi dalam dua bagian, yaitu :
1. Menentukan term-term sebagai kandidat (Prime Implicant), dengan langkah-
langkah sebagai berikut :
a. Terlebih dahulu buatlah tabel kebenaran
b. Nyatakan tiap minterm (desimal) dalam n variabel menjadi string bit yang
panjangnya n, yang dalam hal ini variabel komplemen dinyatakan dengan
„0‟, variabel yang bukan komplemen dengan „1‟.
c. Kelompokkan tiap minterm berdasarkan jumlah „1‟ yang dimilikinya.
d. Kombinasikan minterm dalam n variabel dengan kelompok yang lain yang
jumlah „1‟-nya berbeda satu, sehingga diperoleh bentuk prima (prime-
implicant) yang terdiri dari n-1 variabel. Minterm yang dikombinasikan
diberi tanda “√”.

e. Kombinasikan minterm dalam n-1 variabel dengan kelompok lain yang
jumlah „1‟-nya berbeda satu, sehingga diperoleh bentuk prima yang terdiri
dari n-2 variabel.
f. Teruskan langkah diatas sampai diperoleh bentuk prima yang sesederhana
mungkin.
2. Memilih prime implicant untuk mendapatkan ekspresi dengan jumlah literal
paling sedikit. Langkah-langkahnya :
g. Ambil semua bentuk prima yang tidak bertanda “√”. Buatlah tabel baru
yang memperlihatkan minterm dari fungsi Boolean semula yang dicakup
oleh bentuk prima tersebut (tandai dengan “×”). Setiap minterm harus
dicakup oleh paling sedikit satu buah bentuk prima.
h. Pilih bentuk prima yang memiliki jumlah literal paling sedikit namun
mencakup sebanyak mungkin minterm dari fungsi Boolean semula.
Metode Quine-McCluskey biasanya digunakan untuk menyederhanakan
fungsi Boolean yang ekspresinya dalam bentuk SOP, namun metode ini dapat
dimodifikasi sehingga juga dapat digunakan untuk ekspresi dalam dalam bentuk
POS. Contoh dibawah ini akan mengilustrasikan penggunaan metode Quine-
McCluskey untuk menyederhanakan fungsi Boolean dalam bentuk SOP.

Contoh Metode Quine-McCluskey
Berikut ini contoh kasus dengan menggunakan metode Quine McCluskey
yang akan dibahas :
Contoh : Fungsi Boolean dengan delapan variabel
f(h, g, f, e, d, c, b, a) = ∑ (18, 20, 27, 32, 44, 48, 49, 52, 53, 64, 79, 80, 84, 95,
100, 104, 105, 106, 107, 108, 142, 143, 148, 154, 158, 160 ).

berdasarkan tabel prime implicants diatas, didapatkan label-label prime implicant
terpilih. Bentuk sederhananya adalah :
f(h, g, f, e, d, c, b, a) = z = h’g’f’ed’c’ba’ + h’g’f’edc’ba + h’fe’dcb’a’ +
h’g’fed’b’ + h’gf’d’c’b’a’ + h’gf’dcba +
h’gfe’cb’a’ + h’gfe’dc’ + hg’f’e’dcb +
g’f’ed’cb’a’ + hg’f’edba’ + g’fe’d’c’b’a’ +
h’gf’ed’b’a’
Gambar rangkaian logikanya :
h g f e d c b a

PENUTUP

1. Kesimpulan

Metode Quine Mc.Cluskey menyelesaikan persamaannya dengan
menentukan minterm-minterm sebagai prime implicant dan memilih prime
implicant untuk mendapatkan ekspresi dengan jumlah literal sedikit dengan
beberapa pengulangan minimasi dari tahap penyederhanaan sebelumnya
sampai tidak dapat lagi disederhanakan dan didapat hasil maksimum
peminimasian prime implicant yang terpilih, namun metode ini sangat rumit
langkah-langkahnya contohnya saja dalam menentukan prime implicantnya
dari penyederhanaan 1 ke penyederhanaan selanjutnya selama masih dapat
disederhanakan dan akan berhenti apabila minimasi mintermnya tidak dapat
dilakukan lagi.

2. Saran

Beberapa saran untuk pengembangan penyederhanaan fungsi Boolean
dengan menggunakan metode Quine-McCluskey selanjutnya :
1. Bentuk persamaan fungsi boolean yang diimplementasikan adalah
penjumlahan dari perkalian (Sum Of Product). Diperlukan pengembangan
untuk masukan ekspresi dalam bentuk kalimat perkalian dari penjumlahan
(Product Of Sum).
2. Buatlah listing program aplikasi metode Quine-McCluskey untuk
membantu pengerjaan penyederhanaan fungsi Boolean dengan
menggunakan komputer.

DAFTAR PUSTAKA

Marc Lars Lipson, Seymor Lipschutz, “Seri Penyelesaian Soal Schaum :
Matematika Diskrit 1”, Jakarta : Salemba Teknika, Edisi 1, 2001.
Munir Rinaldi, “Matematika Diskrit”, Bandung : Informatika Bandung,
Cetakan III, 2009.
Sudijono Anas, “Pengantar Statistik Pendidikan”, Jakarta : Rajawali Pers,
Cetakan 23, 2011.

MENYEDERHANAKAN FUNGSI BOOLEAN DENGAN
MENGGUNAKAN METODE QUINE-MCCLUSKEY (QM)

Oleh :

Nama : Altio Zuhroh

NIM : 09221003

Dosen Pembimbing :

Sujinal Arifin, M.Pd

Dosen Pengampuh :

Agustiany Dumeva Putri, M.Si

JURUSAN TADRIS MATEMATIKA
FAKULTAS TARBIYAH
INSTITUT AGAMA ISLAM NEGERI RADEN FATAH
PALEMBANG
2012

�ݺ�ߣ

Menyederhanakan fungsi boolean dengan menggunakan metode quin1

Recommended

More Related Content

What's hot (20)

Viewers also liked (6)

Similar to Menyederhanakan fungsi boolean dengan menggunakan metode quin1 (20)

More from BAIDILAH Baidilah (20)

Menyederhanakan fungsi boolean dengan menggunakan metode quin1