studi metode quine-mccluskey untuk ...repository.usu.ac.id/bitstream/123456789/14128/1/09e...suku...

Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

STUDI METODE QUINE-McCLUSKEY UNTUK MENYEDERHANAKAN

RANGKAIAN DIGITAL

S A F R I N A A M A N A H S I T E P U

0 3 0 8 2 3 0 4 2

DEPARTEMEN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SUMATERA UTARA

MEDAN

2009



RANGKAIAN DIGITAL

SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains

S A F R I N A A M A N A H S I T E P U

0 3 0 8 2 3 0 4 2

DEPARTEMEN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SUMATERA UTARA

MEDAN

2009


PERSETUJUAN

Judul : STUDI METODE QUINE-McCLUSKEY UNTUK

MENYEDERHANAKAN RANGKAIAN DIGITAL

Kategori : SKRIPSI

Nama : S A F R I N A A M A N A H S I T E P U

Nomor Induk Mahasiswa : 0 3 0 8 2 3 0 4 2

Program Studi : SARJANA (S1) MATEMATIK

Departemen : MATEMATIKA

Fakultas : MATEMATIKA DAN ILMU PEGETAHUAN

ALAM (FMIPA) UNIVERSITAS SUMATERA

UTARA

Diluluskan

Medan,

Komisi Pembimbing

Pembimbing 2 Pembimbing 1

Drs.Sawaluddin, M.IT Drs. Bambang Irawan, M.Sc NIP.132206398 NIP.130535480

Diketahui/Disetujui oleh Departemen Matematikan FMIPA USU

Dr. Saib Suwilo, M.Sc Nip 131796149


PERNYATAAN


RANGKAIAN DIGITAL

SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa

kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, 28 Maret 2009

S A F R I N A A M A N A H S I T E P U 0 3 0 8 2 3 0 4 2


A B S T R A K

Dalam sistem penyederhanaan fungsi Boolean rangkaian digital, metode aljabar dan metode Kornaugh‘ Map hanya mampu menyederhanakan fungsi Boolean dengan jumlah variabel maksimun 4 (empat) variabel. Karena itu disimulasikan metode Quine-McCluskey yang mampu menyerderhanakan fungsi Boolean rangkaian digital dengan lebih dari 4 (empat) variabel. Metode ini merupakan metode tabulasi dengan dua langkah utama yaitu pencarian prime implicant (implikan utama) dan penentuan prime implicant (implikan utama) inti.


D A F T A R I S I

Halaman Persetujuan ................................................................................................................. ii Abstrak ...................................................................................................................... iii Abstract ..................................................................................................................... iv Daftar Isi .................................................................................................................... v Daftar Tabel .............................................................................................................. vi Daftar Istilah ............................................................................................................. vii Bab 1 PENDAHULUAN

1.1 Latar Belakang ......................................................................................... 1 1.2 Perumusan Masalah .................................................................................. 1 1.3 Tujuan ...................................................................................................... 1 1.4 Pembatasan Masalah ................................................................................ 2 1.5 Metodologi Penelitian............................................................................... 2 1.6 Kontribusi Penelitian ................................................................................ 2 1.7 Tinjauan Pustaka ...................................................................................... 2

BAB 2 LANDASAN TEORI

2.1 Aljabar Boolean ...................................................................................... 4 2.1.1 Definisi Aljabar Boolean ........................................................................ 4 2.2 Aljabar Boolean Dua Nilai ...................................................................... 5 2.3 Prinsip Dualitas ...................................................................................... 7 2.4 Sifat-sifat Aljabar Boolean ..................................................................... 8 2.5 Fungsi Boolean ....................................................................................... 9 2.6 Fungsi Komplemen .............................................................................. 11 2.7 Bentuk Kanonik .................................................................................... 13 2.8 Konversi Antar Bentuk Kanonik ........................................................... 16 2.9 Bentuk Baku ......................................................................................... 16 2.10 Penyederhanaan Fungsi Boolean........................................................... 17 2.11 Aplikasi Aljabar Boolean ...................................................................... 18 2.11.1 Rangkaian Digital ................................................................................. 18

Bab 3 PEMBAHASAN

3.1 Metode Quine-McCluskey .................................................................... 22 3.2 Menyederhanakan Fungsi Tunggal ....................................................... 24 3.2 Keunggulan dan Kelemahan Metode Quine-McCluskey

KESIMPULAN DAN SARAN 4.1 Kesimpulan .......................................................................................... 33 4.2 Saran .................................................................................................... 33

D A F T A R P U S T A K A


DAFTAR TABEL

2.1 Tabel Operator Biner dalam Perkalian dan Penjumlahan ................... 5 2.2 Tabel Hukum Distributif ........................................................................ 6 2.3 Tabel Fungsi f(x,y,z) = x y’z ............................................................ 9 2.4 Tabel Fungsi f(x,y,z) = x’y’z + x’y z + x y’

dan Fungsi g(x, y, z) = x’z + x y’ .................................................. 9 2.5 Tabel Minterm dan Maxterm 2 (dua) Variabel .................................. 12 2.6 Tabel Minterm dan Maxterm 3 (tiga) Variabel .................................. 12 2.7 Tabel Fungsi f(x,y,z) dalam bentuk Kanonik SOP dan POS .............. 13 2.8 Tabel Gerbang (Gate) Rangkaian Logika Dasar ................................ 17 3.1 Tabel Kebenaran Suatu Fungsi dengan don’t Care ............................ 21 3.2 Tabel Proses Reduksi Tabulasi ............................................................ 22 3.3 Tabel Reduksi Esensial ......................................................................... 25 3.4 Tabel Tereduksi Non Esensial .............................................................. 25 3.5 Tabel Ekspresi Logis Dalam Pilihan Tereduksi .................................. 26 3.6 Tabel Reduksi Fungsi Boolean Tunggal .............................................. 27 3.7 Tabel Reduksi Fungsi Boolean Jamak ............................................... 29


D A F T A R I S T I L A H

Fundamental Product : Suatu perkalian Boolean yang merupakan

sebuah literal, atau perkalian dari 2 (dua) atau

lebih literal, dengan ketentuan tidak ada dua

literal yang mengandung variabel yang sama.

Karnaugh Map : Metode Grafik Untuk mnyederhanakan

Fungsi Boolean rangkaian digital. Metode ini

diperkenalkan oleh Maurice Karnaugh pada

tahun 1953.

Literal : Suatu Variabel Boolean atau Komplemennya.

Literal Lengkap : Suatu Variabel yang mewakili dari tiap suku.

Maximum Term (Maxterm) : Suku penjumlahan Boolean yang memuat

seluruh variabel. Maxterm juga sering disebut

sebagai suku penjumlahan fundamental.

Minimum Term (Minterm) : Suku perkalian Boolean yang memuat seluruh

variabel. Minterm juga sering disebut sebagai

suku perkalian fundamental.

Prime Implicant (Implikan Utama) : Suku Perkalian yang diperoleh dari

pengkombinasian 2 (dua) buah minterm dan

tidak dapat dikombinasikan lagi dengan

minterm yang lain.

Product Of Sum Boolean : Perkalian dari suku-suku penjumlahan

Boolean

Sum Of Product Booean : Penjumlahan dari suku-suku perkalian

Boolean

Prosedur Covering : Prosedur Penentuan Prime implicant

(implikan utama) Inti yang mencakup sluruh

minterm pada fungsi Boolean

Suku don’t care : Kombinasi nilai masukan rangkaian yang

tidak mempunyai nilai keluaran sehingga

dapat diabaikan.


BAB 1

P E N D A H U L U A N

1.1 Latar Belakang

Dalam perancangan suatu rangkaian digital diperlukan adanya penyederhanaan untuk

memperoleh jumlah gerbang logika minimum ketika mengimplementasikan Fungsi

Boolean rangkaian, karena semakin sedikit jumlah gerbang yang digunakan, akan

menekan biaya dalam pembuatan rangkaian tersebut.

Adapun penyederhanaan rangkaian digital dapat dilakukan dengan

menggunakan sifat-sifat dari Aljabar Boolean, akan tetapi membutuhkan waktu yang

lama, sementara hasil yang diperoleh belum tentu merupakan Fungsi Boolean

rangkaian yang paling sederhana.

Sedangkan metode tabulasi Quine-McCluskey dapat digunakan untuk variabel

Fungsi yang lebih dari empat. Kelebihan lain dari metode ini yaitu dapat

menyederhanakan Fungsi Boolean rangkaian mulai dari 2 (dua) variabel sampai ke n

variabel, dan juga lebih mudah untuk mengimplementasikannya ke dalam sebuah

program Komputer dikarenakan langkah-langkah dalam metode ini lebih sistematis.

Dengan demikian waktu yang diperlukan untuk menyederhanakan sebuah Fungsi

Boolean akan semakin singkat.


1.2 Perumusan Masalah

Berdasarkan latar belakang di atas, yang menjadi permasalahan dalam Tugas Akhir ini

adalah bagaimana cara menyederhanakan suatu rangkaian digital dengan

menggunakan metode Quine-McCluskey.

1.3 Tujuan

Adapun tujuan penelitian ini adalah untuk mempelajari/memahami cara

menyederhanakan suatu rangkaian digital yang rumit dengan menggunakan metode

Quine-McCluskey.

1.4 Pembatasan Masalah

Agar pembahasan tidak menyimpang dari pokok permasalahan, penulis membatasi

permasalahan hanya pada teori dan studi kasus dari metode Quine-McCluskey dalam

penyederhanaan rangkaian digital.

1.5 Metodologi Penelitian

Adapun metode yang digunakan adalah sebagai berikut:

1. Menggunakan metode Quine-McCluskey untuk menyederhanakan Fungsi

Boolean.

2. Mengimplementasikan Fungsi Boolean yang sederhana ke gerbang logika.

1.6 Kontribusi Penelitian


Memahami proses penyederhanaan Fungsi Boolean suatu rangkaian digital dengan

menggunakan metode Quine-McCluskey.

BAB 2

L A N D A S A N T E O R I

2.1 Aljabar Boolean

Seorang ahli matematika dari Inggris, George Boole (1815-1864) pada tahun 1854

memaparkan aturan-aturan dasar logika dalam bukunya yang berjudul An

Investigation of the Laws of Thought, on Which Are Founded the Mathematical

Theorities of Logic and Probabilities, yang kemudian dikenal sebagai logika Boolean.

Boole 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. Dewasa

ini aljabar Boolean telah menjadi dasar teknologi Komputer digital. Saat ini aljabar

Boolean digunakan secara luas dalam perancangan rangkaian.

2.1.1 Definisi Aljabar Boolean

Aljabar Boolean adalah aljabar yang terdiri atas suatu himpunan B dengan 2 (dua)

operator biner yang didefinisikan pada himpunan tersebut, yaitu: + (penjumlahan) dan

• (perkalian). Sehingga untuk setiap x, y, z ∈ B berlaku aksioma atau postulat

sebagai berikut:

1. Closure : (i). x + y ∈ B

(ii). x • y ∈ B


2. Identitas : (i). Ada elemen tunggal 0 ∈ B, sedemikian hingga

berlaku: x + 0 = 0 + x = x

(ii). Ada elemen tunggal 0 ∈ B, sedemikian hingga

berlaku: x • 1 = 1 • x = 1

3. Komutatif : (i). x + y = y + x

(ii). x • y = y • x

4. Distributif : (i). x • (y + z) = (x • y) + (x • z)

(ii). x + (y • z) = (x + y) • (x + z)

(iii). (x • y) + z = (x + z) • (y + z)

5. Komplemen : Untuk setiap x ∈ B, terdapat elemen tunggal x’∈ B

sedemikian hingga berlaku: x + x’= 1 dan x • x’= 0

6. Terdapat sedikitnya 2 (dua) buah elemen, x dan y ∈ B , sedemikian

hingga berlaku : x ≠ y.

7. Idempoten : (i). x • x = x

(ii). x + x = x

8. Asosiatif : (i). x + (y + z) = (x + y) + z

(ii). x • (y • z) = (x • y) • z

Kecuali aksioma 7 dan 8, ke enam aksioma pertama disebut Postulat Huntington,

karena diformulasikan secara formal oleh E.V Huntington.

Untuk mempunyai sebuah aljabar Boolean, harus memperlihatkan:

1. Elemen himpunan B

2. Kaidah/aturan operasi untuk 2 (dua) operator biner


3. Himpunan B, bersama-sama dengan 2 (dua) operator tersebut, memenuhi

postulat Huntington.

2.2 Aljabar Boolean Dua Nilai

Aljabar Boolean 2 (dua) nilai didefinisikan pada sebuah himpunan dengan 2 (dua)

buah elemen, yaitu: B = {0,1}, dengan kaidah untuk operator biner + (penjumlahan)

dan • (perkalian), ditunjukkan pada Tabel 2.1.

Tabel 2.1 Operator Biner untuk Perkalian dan Penjumlahan Logika

x y x • y x Y x + y

0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1

Harus ditunjukkan bahwa postulat Huntington benar untuk himpunan B = {0,1} dan

2 (dua) operator biner yang didefinisikan di atas.

1. Closure, jelas dari Tabel karena hasil tiap operasi adalah 0 dan 1 ∈ B

2. Dari Tabel terlihat bahwa: (i). 0 + 1 = 1 + 0 = 1

(ii). 1 • 0 = 0 • 1 = 0

yang memenuhi elemen identitas 0 dan 1

3. Hukum komutatif jelas terpenuhi.

4. (i). Hukum distributif:

x • (y + z) = (x • y) + (x • z) dipenuhi, dapat ditunjukkan pada

Tabel 2.2.


Tabel 2.2 Kebenaran Hukum Distributif

x y z y + z x • (y + z) x • y x • z (x • y) + (x • z)

0 0 0 0 0 0 0 0

0 0 1 1 0 0 0 0

0 1 0 1 0 0 0 0

0 1 1 1 0 0 0 0

1 0 0 0 0 0 0 0

1 0 1 1 1 0 1 1

1 1 0 1 1 1 1 1

1 1 1 1 1 1 1 1

(ii). Hukum distributif: x + (y • z) = (x + y) • (x + z)

dapat ditunjukkan dengan membuat Tabel kebenaran seperti (i).

5. Tabel komplemen memperlihatkan bahwa:

(i). x + x’ = 1, karena 0 + 0’ = 0 + 1 = 1

(ii). x • x’ = 0, karena 0 • 0’ = 0 • 1 = 0

6. Postulat 6 dipenuhi karena aljabar Boolean dua nilai memiliki 2 (dua) buah

elemen yang berbeda yaitu 1 dan 0.

2.3 Prinsip Dualitas

Dualitas adalah padanan dual ekspresi Boolean yang diperoleh dengan cara:

• mempertukarkan + ↔ •, dan


• mempertukarkan 1 ↔ 0

Contoh:

Ekspresi Dualitas x + x = x x • x = x Idempoten x + 1 = x x • 0 = 0 Identitas

x•(y + z)=(x • y)+(x • z) x+(y • z)=(x + y)•(x + z)

2.4 Sifat-Sifat Aljabar Boolean

1. Hukum Identitas:

(i). x + 0 = x

(ii). x • 1 = x

2. Hukum Idempoten:

(i). x • x = x

(ii). x + x = x

3. Hukum Komplemen:

(i). x + x = 1

(ii). x • x = 0

4. Hukum Dominan:

(i). x • 0 = 0

(ii). x + 1 = 1

5. Hukum Involusi:

(i). x = x

6. Hukum Absorbsi (Penyerapan):

(i). x • y + x • y = x

7. Hukum Komutatif:

(i). x + y = y + x

(ii). x • y = y • x

8. Hukum Asosiatif:

(i). x+(y + z)=(x + y)+ z

(ii). x•(y • z)=(x • y)• z

9. Hukum Distributif:

(i). x+(y • z)=(x + y)•(x + z)

(ii). x•(y + z)=(x • y)+(x • z)

10. Hukum De Morgan:

(i). (x + y) = x • y

(ii). (x • y) = x + y

Kadang-kadang untuk menyederhanakan penulisan, dituliskan x • y sebagai xy.


Contoh dari sifat-sifat aljabar Boolean:

1. Buktikan bahwa: x + x’y = x + y

Bukti:

x + x’y = (x + x y) + x’y (Absorbsi)

= x + (x y + x’y) (Asosiatif)

= x + (x + x’) y (Distributif)

= x + 1 . y (Komplemen)

= x + y (Identitas)

2. Buktikan bahwa: x (x’+ y) = x y

Bukti:

x (x’ + y) = x x’ + x y (Distributif)

= 0 + x y (Komplemen)

= x y (Identitas)

2.5 Fungsi Boolean

Pada aljabar Boolean 2 (dua) nilai, jika nilai B = {0,1}, maka variabel x disebut

variabel Boolean atau variabel biner. Fungsi Boolean atau disebut juga Fungsi biner

adalah ekspresi yang dibentuk dari variabel biner, 2 (dua) operator biner + dan •,


operator komplemen (‘), tanda kurung ( ), dan tanda sama dengan (=). Setiap variabel

Boolean, termasuk komplemennya disebut literal.

Contoh-contoh Fungsi Boolean:

1. f (x) = x

2. f (x,y) = x’y + x y’ + y’

3. f (x,y) = x’y’

4. f (x,y) = (x + y)’

5. f (x,y,z) = x y’ z

Dari contoh-contoh ke lima Fungsi Boolean tersebut, Fungsi 5 di atas yaitu:

f (x,y,z)= x y’z terdiri atas 3 (tiga) literal x,y’ dan z.

Andaikan Fungsi tersebut mempunyai harga 1 (satu) untuk x = 1, y = 0, dan z = 1.

Dengan demikian dapatlah dibuat Tabel kebenaran dari Fungsi:

f(x,y,z)= x y’z, pada Tabel 2.3.

Tabel 2.3 Kebenaran dari Fungsi f(x,y,z)= x y’z x y z f(x,y,z)= x y’z

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 1

1 1 0 0

1 1 1 0

Fungsi Boolean tidak unik, artinya 2 (dua) buah Fungsi yang ekspresi aljabarnya

berbeda, mungkin saja merupakan 2 (dua) buah yang sama karena keduanya

mempunyai nilai yang sama pada Tabel kebenaran. Sebagai contoh:

Fungsi f(x,y,z)= x’y’z + x’yz + xy’ dan Fungsi g(x,y,z)= x’z + xy’ adalah 2

(dua) buah Fungsi Boolean yang sama. Lihat Tabel 2.4.

Tabel 2.4 Fungsi Boolean yang mempunyai nilai yang sama


x y z f(x,y,z) g(x,y,z)

0 0 0 0 0

0 0 1 1 1

0 1 0 0 0

0 1 1 1 1

1 0 0 1 1

1 0 1 1 1

1 1 0 0 0

1 1 1 0 0

Karena Fungsi Boolean tidaklah unik, dapatlah ditemukan 2 (dua) buah ekspresi

Boolean yang menunjukkan Fungsi yang sama, yaitu dengan cara manipulasi aljabar.

Perhatikan contoh berikut ini: f(x,y,z) = x’y’z + x’y z + x y’

= x’z (y’+ y) + x y’

= x’z (1) + x y’

= x’z + x y’

2.6 Fungsi Komplemen

Fungsi komplemen dari suatu Fungsi F, dapat dicari dengan menukarkan nilai 0

menjadi 1, dan sebaliknya nilai 1 menjadi 0.

Ada 2 (dua) cara yang dapat digunakan untuk membentuk Fungsi komplemen:

1. Menggunakan Hukum De Morgan.

Untuk 2 (dua) variabel, x1 dan x2 (x1 + x2)’ = x1’ x2’ dan dualnya; (x1 . x2)’ = x1’ + x2’

Untuk 2 (dua) variabel, x1,x2 , dan x3 (x1 + x2 + x3)’ = (x1 + y)’

Misal: x2 + x3 = y = x1’ . y’


= x1’ (x2 + x3)’

= x1’ x2’ x3’

Untuk n variabel, x1, x2, . . ., xn (x1 + x2 +. . . .+ xn)’ = x1’, x2’, . . . . xn’ dan dualnya: (x1 . x2 . . . . . xn)’ = x1’ + x2’ + . . . . + xn’

Contoh:

Fungsi komplemen f‘(x,y,z) dari Fungsi f(x,y,z) = x(y’z’+ y z) adalah: f‘(x,y,z) = (x(y’z’+ yz))’

= x’+ (y’z’+ yz)’

= x’+ (y’z’)’ . (yz)’

= x’+ (y + z ). (y’ +z’)

2. Menggunakan prinsip dualitas.

Cari dual dari “f “ lalu komplemenkan setiap literalnya.

Misalnya untuk Fungsi yang sama: f(x,y,z) = x(y’z’+ y z)

Dual dari: f: x +(y’+ z’).(y + z) Komplemen tiap literalnya adalah: x’+ (y + z) . (y’+z’) = f‘ Jadi; f‘(x,y,z)= x’+(y + z).(y’+ z’)

2.7 Bentuk Kanonik

Beberapa Fungsi Boolean mungkin mempunyai ekspresi aljabar yang berbeda, tetapi

sebenarnya nilai Fungsinya sama. Sebagai contoh:


f (x, y) = x’ y’ dan g (x, y) = (x + y)’ adalah dua buah Fungsi yang sama.

Contoh lain: f(x,y,z)= x’y’z + x y’z’+ x y z

dan g(x,y,z)=(x+y+z)(x+y’+z)(x+y’+z’)(x’+y+z’)(x’+y’+z)

adalah 2 (dua) buah Fungsi yang sama.

Fungsi pertama f, tampil dalam bentuk penjumlahan dari hasil kali, sedangkan Fungsi

yang ke dua g, muncul sebagai bentuk perkalian dari hasil penjumlahan. Setiap suku

(term) mengandung literal yang lengkap (x,y,z). Fungsi Boolean yang dinyatakan

sebagai jumlah dari hasil kali (SOP) dan hasil kali dari jumlah (POS), dengan setiap

sukunya mengandung literal lengkap, disebut dalam bentuk kanonik.

Ada 2 (dua) macam bentuk kanonik:

1. Minterm atau sum-of- product (SOP)

2. Maxterm atau product-of-sum (POS)

Minterm dan Maxterm dari 2 (dua) variabel biner ditunjukkan pada Tabel 2.5.

Tabel 2.5 Minterm dan Maxterm dari 2 (dua) Variabel

x

y Minterm Maxterm

Suku Lambang Suku Lambang 0 0 x’y’ m0 x + y M0

0 1 x’y m1 x + y’ M1

1 0 x y’ m2 x’+ y M2

1 1 x y m3 x’+ y’ M3

Minterm dan Maxterm dari 3 (tiga) variabel biner ditunjukkan pada Tabel 2.6.

Tabel 2.6 Minterm dan Maxterm dalam 3 (tiga) Variabel x y z Minterm Maxterm


Suku Lambang Suku Lambang 0 0 0 x’y’z’ m0 x + y + z M0

0 0 1 x’y’z m1 x + y + z’ M1

0 1 0 x’yz’ m2 x + y’+ z M2

0 1 1 x’y z m3 x + y’+z’ M3

1 0 0 x y’z’ m4 x’+ y + z M4

1 0 1 x y’z m5 x’+ y +z’ M5

1 1 0 x y z’ m6 x’+ y’+ z M6

1 1 1 x y z m7 x’+ y’+z’ M7

Suatu Fungsi Boolean dapat dibentuk secara aljabar dari Tabel kebenaran yang

diketahui dengan membentuk minterm dari setiap kombinasinya.

Untuk membentuk minterm, tinjau kombinasi variabel-variabel yang menghasilkan

nilai 1. Kombinasi 001, 100 dan 111 ditulis sebagai:

x’y’z, x y’z’, dan x y z.

Untuk membentuk maxterm, tinjau kombinasi variabel-variabel yang menghasilkan

nilai 0. Kombinasi 000, 010, 101 dan 110 ditulis sebagai: (x + y + z), (x + y’+ z), (x’+ y + z’) dan (x’+ y’+ z’).

Contoh:

Tinjau Fungsi Boolean yang diekspresikan dalam Tabel 2.7. Nyatakan Fungsi tersebut

dalam bentuk Kanonik SOP dan POS.

Tabel 2.7: Fungsi f(x,y,z) 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

Jawab:

1. SOP: Tinjau kombinasi variabel yang menghasilkan nilai 1 f(x, y, z) = x’ y’ z + x y’ z’ + x y z

atau dalam bentuk lain,

f(x, y, z) = m1 + m4 + m7 = ∑ (1, 4, 7)

2. POS: Tinjau kombinasi variabel yang menghasilkan nilai 0 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)

Notasi ∑ dan ∏ berguna untuk menyingkat penulisan ekspresi bentuk SOP dan

POS.

2.8 Konversi Antar Bentuk Kanonik

Misal: f adalah Fungsi Boolean dalam bentuk SOP:

f (x, y, z) = ∑ (1, 4, 5, 6, 7) dan

f‘ adalah komplemen dari f f‘ (x, y, z) = ∑ (0, 2, 3) = m0 + m2 + m3

Dengan menggunakan hukum de Morgan, dapat memperoleh Fungsi f dalam bentuk

POS: f’ (x, y, z) = (f’(x, y, z))’ = (m0 + m2 + m3)’

= m0’. m2’. m3’

= (x’y’z’)’ (x’y z’)’ (x’y z)’

= (x + y + z) (x + y’+ z) (x + y’+ z’)

= M0 M2 M3

= ∏(0, 2, 3)

Jadi mj’ = Mj


2.9 Bentuk Baku

2 (Dua) bentuk kanonik adalah bentuk dasar yang diperoleh dengan membaca Fungsi

dari Tabel kebenaran. Bentuk ini umumnya sangat jarang muncul, karena setiap suku

di dalam bentuk kanonik harus mengandung literal atau variabel yang lengkap, baik

dalam bentuk normal (x) atau dalam bentuk komplemennya (x’). Cara lain untuk

mengekspresikan Fungsi Boolean adalah bentuk baku (standard). Pada bentuk ini,

suku-suku yang membentuk Fungsi dapat mengandung 1 (satu), 2 (dua), atau

sejumlah literal. 2 (Dua) tipe bentuk baku adalah bentuk baku SOP dan bentuk baku

POS.

Contoh: f (x, y, z) = y’ + x y + x’ y z f (x, y, z) = x (y’ + z) (x’ + y + z’)

2.10 Penyederhanaan Fungsi Boolean

Fungsi Boolean dapat disederhanakan dalam 3 (tiga) cara:

1. Secara aljabar, dengan menggunakan rumus atau aksioma yang berlaku pada

Fungsi Boolean

2. Menggunakan Peta Karnaugh

3. Menggunakan metode Quine-McCluskey (metode Tabulasi)

2.11 Aplikasi Aljabar Boolean

Aljabar Boolean memiliki aplikasi yang luas antara lain di bidang jaringan

pensaklaran (switching) dan rangkaian digital.


2.11.1 Rangkaian Digital

Rangkaian digital elektronik biasanya dimodelkan dalam gerbang logika. Ada 3 (tiga)

macam gerbang dasar: AND, OR dan NOT. Rangkaian yang dibentuk oleh gerbang

logika disebut rangkaian logika. Dapat dilihat pada Gambar 1.a, 1.b, dan 1.c.

xy

xy

xy

x + y

Gambar 1.a Gerbang AND dua masukan Gambar 1.b Gerbang OR dua masukan

x x'

Gambar 1.c Gerbang NOT (inverter)

Selain gerbang dasar tersebut di atas, masih terdapat gerbang logika turunan, yaitu

NAND, NOR, XOR, dan XNOR. Dapat dilihat pada Gambar 1.d, 1.e, 1.f, dan 1.g.

xy

(xy)'

xy

(x + y)'

Gambar 1.d Gerbang NAND Gambar 1.e Gerbang NOR


xy

x + y

xy

(x + y)'

Gambar 1.f Gerbang XOR Gambar 1.g Gerbang XNOR

Adapun Tabel kebenaran dari Rangkaian Logika dasar dapat dilihat pada Tabel 2.8.

Tabel 2.8 Gerbang (Gate) Rangkaian Logika Dasar

AND x x.y y OR x x+y y NOT x x NAND x (x.y) y

x y x.y 0 0 0 0 1 0 1 0 0 1 1 1

x y x+y 0 0 0 0 1 1 1 0 1 1 1 1

x x 0 1 1 0

x y (x.y) 0 0 1 0 1 1 1 0 1 1 1 0

x y (x+y) 0 0 1 0 1 0


NOR x (x+y) y XOR x x y y

XNOR x x y) y

Contoh:

Nyatakan Fungsi Boolean berikut ke dalam rangkaian logika. f (x,y,z) = x y + x’y

Jawab:

a. Langkah I:

x

xy xy

y

x'x' y

xy + x' y

b. Langkah II:

1 0 0 1 1 0

x y x y 0 0 0 0 1 1 1 0 1 1 1 0

x y (x y ) 0 0 1 0 1 0 1 0 0 1 1 1


xy xy

x'x' y

xy + x' y

c. Langkah III:

xy xy

x'x' y

xy + x' y

BAB 3

P E M B A H A S A N

3.1 Metode Quine-McCluskey (Tabulasi)

Untuk Fungsi Boolean yang mempunyai lebih dari 6 (enam) variabel, digunakan

metode Quine-McCluskey. Metode ini disebut juga metode Tabulasi.

Langkah-langkah:

1. Nyatakan tiap minterm dalam n variabel menjadi string bit yang panjangnya n

2. Kelompokkan tiap minterm berdasarkan jumlah nilai 1 yang dimilikinya.


3. Kombinasikan minterm dalam n variabel dengan kelompok lain yang jumlah

nilai 1-nya berbeda 1 (satu), sehingga diperoleh prime implicant (implikan

utama) yang terdiri dari n-1 variabel. Minterm yang dikombinasikan diberi

tanda (√).

4. Kombinasikan minterm dalam n-1 variabel dengan kelompok lain yang jumlah

nilai 1-nya berbeda 1 (satu), sehingga diperoleh prime implicant (implikan

utama) yang terdiri dari n-2 variabel.

5. Ulangi langkah 4 (empat) sampai diperoleh prime implicant (implikan utama)

yang paling sederhana.

6. Ambil semua prime implicant (implikan utama) yang tidak bertanda (√).

Buatlah Tabel baru yang memperlihatkan minterm dari ekspresi Boolean semula

yang dicakup oleh prime implicant (implikan utama) tersebut, tandai dengan (x).

Setiap minterm harus dicakup oleh paling sedikit 1 (satu) buah prime implicant

(implikan utama).

7. Pilih prime implicant (implikan utama) yang memiliki jumlah literal paling

sedikit namun mencakup sebanyak mungkin minterm dari ekspresi Boolean

semula, yaitu dengan cara:

a. Tandai kolom-kolom yang mempunyai satu buah tanda (x) dengan tanda

(*), lalu beri tanda (√) di sebelah kiri prime implicant (implikan utama)

yang berasosiasi dengan tanda asterisk (*) tersebut. Prime implicant

(implikan utama) ini telah dipilih untuk Fungsi Boolean sederhana.

b. Untuk setiap prime implicant (implikan utama) yang telah ditandai dengan

(√), beri tanda minterm yang dicakup oleh prime implicant (implikan

utama) tersebut dengan tanda (√).

c. Periksa apakah masih ada minterm yang belum dapat dicakup oleh prime

implicant (implikan utama) terpilih. Jika ada, maka pilih dari prime

implicant (implikan utama) yang tersisa yang mencakup sebanyak

mungkin minterm. Beri tanda (√) prime implicant (implikan utama) yang

dipilih itu serta minterm yang dicakupnya.


d. Ulangi langkah c sampai seluruh minterm sudah dicakup oleh semua

prime implicant (implikan utama).

Pendekatan otomatis untuk menyederhanakan ekspresi Boolean biasa digunakan

pada Fungsi dengan keluaran tunggal atau jamak. Metode tabulasi atau juga dikenal

dengan metode Quine-McCluskey, membentuk perkalian yang berbeda pada 1 (satu)

variabel secara berturut-turut, dan kemudian dihasilkan himpunan suku tereduksi yang

dapat mencakup semua Fungsi keluaran. Proses ini lebih mudah diimplementasikan

pada komputer daripada metode peta, dan hasil suku-suku reduksinya dapat digunakan

oleh lebih dari 1 (satu) Fungsi.

3.2 Menyederhanakan Fungsi Tunggal

Tabel kebenaran pada Tabel 3.1. menggambarkan f yang merupakan Fungsi 4 (empat)

variabel x,y,z, dan w, yang menyertakan 3 (tiga) don’t care (= d). Proses reduksi

secara Tabel dimulai dengan mengelompokkan minterm berdasarkan jumlah nilai 1-

nya. Minterm 0000, tidak mempunyai nilai 1, sehingga dijadikan grup tersendiri.

Minterm 0001,0010,0100, dan 1000 mempunyai nilai 1 tunggal, tetapi hanya minterm

0001 yang menghasilkan nilai 1, sehingga minterm ini dijadikan grup lain.

Tabel 3.1 Kebenaran suatu Fungsi dengan don’t care

x y z w f

0 0 0 0 d

0 0 0 1 1

0 0 1 0 0

0 0 1 1 1

0 1 0 0 0

0 1 0 1 1


0 1 1 0 1

0 1 1 1 1

1 0 0 0 0

1 0 0 1 0

1 0 1 0 1

1 0 1 1 d

1 1 0 0 0

1 1 0 1 1

1 1 1 0 0

1 1 1 1 d

Grup berikutnya adalah minterm dengan 2 (dua) nilai 1, dan ada 6 (enam)

kemungkinan minterm yang mempunyai 2 (dua) nilai 1, yang dapat masuk dalam grup

ini. Hanya minterm 0011,0101,0110, dan 1010 yang menghasilkan keluaran 1,

sehingga minterm inilah yang masuk dalam grup.

Ada 3 (tiga) minterm yang menghasilkan keluaran 1 dan mempunyai 3 (tiga)

nilai 1, yaitu 0111, 1011, dan 1110. Akhirnya grup yang beranggotakan 4 (empat)

nilai 1 ada satu minterm, dan merupakan grup terakhir.

Untuk Tabel kebenaran yang lebih besar, proses dapat berlanjut terus. Grup

dikelompokkan lagi sehingga grup yang berbeda tepat 1 (satu) jumlah nilai 1-nya

dapat digabung, seperti Tabel 3.2.a. Langkah berikutnya dalam proses reduksi adalah

membentuk sebuah konsensus antara setiap pasang grup bertetangga untuk semua

suku dengan beda nilai tepat 1 (satu) variabel saja.


Tabel 3.2: Proses Reduksi Tabulasi

Keadaan awal Setelah Reduksi I Setelah Reduksi II

x y z w x y Z w x y z w

0 0 0 0 √ 0 0 0 - * 0 - - 1 *

0 0 0 1 √ 0 0 - 1 √ - - 1 1 *

0 0 1 1 √ 0 - 0 1 √ - 1 - 1 *

0 1 0 1 √ 0 - 1 1 √ (c)

0 1 1 0 √ - 0 1 1 √

1 0 1 0 √ 0 1 - 1 √

0 1 1 1 √ - 1 0 1 √

1 0 1 1 √ 0 1 1 - *

1 1 0 1 √ 1 0 1 - *

1 1 1 1 √ - 1 1 1 √

(a) 1 - 1 1 √

1 1 - 1 √

(b)

Secara aljabar, teorema tersebut dapat dibuktikan sebagai berikut: 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 + x y z + x z + x y z

= x y (1 + z) + x z (1 + y)

= x y + x z

Dengan menggunakan Teorema konsensus diperolehlah bentuk dualitasnya: (x + y) (x + z) (y + z) = (x + y) (x + z)

Ide dari penerapan konsensus pada reduksi tabulasi adalah untuk mengambil

keuntungan dari sifat invers dari aljabar Boolean. Misalnya, 0000 dan 0001 berbeda

nilainya pada variabel w, sehingga 000_ dimasukkan dalam daftar pada bagian atas

Tabel reduksi seperti terlihat pada Tabel 3.2.b. Tanda garis bawah menunjukkan posisi

variabel yang dieliminasi, dalam contoh ini w.


Minterm 0000 dan 0001 pada Tabel 3.2.a ditandai dengan cek (√) untuk

menunjukkan bahwa entri ini sudah tercakup pada Tabel reduksi. Setelah semua suku

pada grup pertama disilangkan dengan semua suku pada grup ke dua, kemudian

beralih untuk membentuk konsensus antara grup ke dua dan ke tiga. Ada

kemungkinan bahwa beberapa suku tidak dapat dikombinasi menjadi suku yang lebih

kecil karena berbeda pada lebih dari 1 (satu) variabel.

Contohnya, suku 0001 dan 0011 dapat dikombinasi menjadi suku lebih kecil

00_1 namun 0001 dan 0110 tidak dapat dikombinasi karena berbeda pada 3 (tiga)

variabel. Sekali suku sudah ditandai dengan (√), suku tersebut masih dapat

dipergunakan untuk proses reduksi karena sifat idempotens. Tujuan dari langkah

dalam proses ini adalah untuk menemukan semua kemungkinan suku tereduksi,

sehingga dapat menemukan himpunan terkecil suku yang masuk dalam Fungsi pada

langkah berikutnya.

Proses berlanjut untuk grup-grup sisanya. Setiap suku yang tidak tercakup dalam

pengelompokan konsensus ditandai dengan asterisk (*) untuk menunjukkan bahwa ini

adalah suku prime implicant (implikan utama). Pada Tabel 3.2.a. terlihat bahwa

setelah reduksi pertama semua minterm sudah terpakai sehingga tidak ada prime

implicant (implikan utama).

Setelah reduksi pertama, dapat melanjutkan untuk literasi berikutnya, jika

keduanya hanya berbeda 1 (satu) variabel saja, maka 2 (dua) suku dapat

dikombinasikaan. Garis bawah harus pada posisi yang sama. Entri pertama pada Tabel

3.2.b. mempunyai garis bawah pada kolom paling kanan, sehingga tidak ada entri

pada grup ke dua yang cocok.

Dalam penyusunan Tabel reduksi pada Tabel 3.2.c. prime implicant (implikan

utama) dari Tabel sebelumnya (Tabel 3.2.b) tidak diikutkan. Proses berlanjut sampai

hanya tersisa prime implicant (implikan utama). Pada contoh ini, proses berhenti

setelah reduksi ke dua dan menghasilkan 3 (tiga) suku tersisa sebagai prime implicant


(implikan utama) seperti pada Tabel 3.2.c. Setiap prime implicant (implikan utama)

dikumpulkan untuk menyusun Fungsi, walaupun belum minimal.

Oleh karena itu entri ini ditandai dengan asterisk (*), yang menunjukkan bahwa

suku ini adalah prime implicant (implikan utama) dan tidak dapat direduksi lagi.

Beralih ke grup ke dua dan ke tiga pada Tabel 3.2.b. Suku 00_1 dan 01_1 dikombinasi

menjadi suku 0_ _1 seperti tertera pada Tabel 3.2.c. Proses terus berlanjut hingga

reduksi ke dua lengkap.

Untuk meminimalkan suku-suku yang digunakan, disusun Tabel pilihan seperti

pada Tabel 3.3. Setiap prime implicant (implikan utama) dibuat 1 (satu) baris dalam

Tabel pilihan dan kolom berisi minterm dari Fungsi asli yang harus dicakup. Kondisi

don’t care tidak perlu dicakup sehingga tidak dimasukkan dalam daftar. Setiap kotak

yang sesuai dengan prime implicant (implikan utama) dan mintermnya ditandai

dengan asterisk (*).

Misalnya, prime implicant (implikan utama) 000_ tandai pada kolom minterm

0001. Beberapa prime implicant (implikan utama) mencakup beberapa minterm,

seperti 0_ _1 akan mencakup 4 (empat) minterm.

Setelah semua kotak dicek, carilah kolom yang hanya berisi 1 (satu) tanda cek.

Tanda cek tunggal pada kolom berarti hanya ada 1 (satu) prime implicant (implikan

utama) yang mencakup minterm tersebut, dan prime implicant (implikan utama) yang

mencakup minterm tersebut ditandai dengan yang menunjukkan bahwa prime

implicant (implikan utama) ini adalah esensial dan harus digunakan atau masuk dalam

persamaan akhir.

Tabel 3.3: Reduksi Esensial

Prime implicant

(implikan utama)

Minterm

0001 0001 0101 0110 0111 1010 1101

000_ √

*011_ √ √

*101_ √

0_ _1 √ √ √ √


_ _11 √ √

*_1_1 √ √ √

Contoh prime implicant (implikan utama) esensial adalah 011_, 101_, dan _1_1.

Prime implicant (implikan utama) esensial dapat mencakup lebih dari satu minterm.

Untuk itu dibuatlah Tabel pilihan tereduksi yang tidak menyertakan prime implicant

(implikan utama) esensial dan mintermnya, seperti pada Tabel 3.4. Tabel pilihan

tereduksi dapat berisi prime implicant (implikan utama) esensial yang kemudian

dikenai proses reduksi lagi, sampai Tabel pilihan tereduksi hanya berisi prime

implicant (implikan utama) non esensial.

Tabel 3.4. Tereduksi Non Esensial

Himpunan minterm

Himpunan 1

Himpunan 2

Pilihan 0001 0011

000_

0_ _1

x 000_ √

_ _11

y 0_ _1 √ √

z _ _11 √

Sisa prime implicant (implikan utama) dalam Tabel pilihan tereduksi membentuk

himpunan pilihan, yang digunakan untuk mendapatkan himpunan minimal. Seperti

pada Tabel 3.4. ada 2 (dua) himpunan prime implicant (implikan utama) yang

menampung 2 (dua) minterm sisa. Karena himpunan 2 (dua) adalah suku paling

sederhana, maka suku inilah yang dipilih untuk membentuk persamaan minimal untuk

F, yang terdiri atas prime implicant (implikan utama) esensial dan prime implicant

(implikan utama) pilihan pada himpunan 2 (dua). (Persamaan berikut): F = x y z + x y z + y w + x w

Selain menggunakan cara visual untuk mendapatkan himpunan dari himpunan pilihan,

dapat juga dilakukan proses secara algoritmis. Proses dimulai dengan menyatakan

persamaan yang mencakup semua prime implicant (implikan utama) dalam himpunan

pilihan pada Tabel 3.4. Ekspresi logis ditulis untuk setiap kolom pada Tabel pilihan

tereduksi seperti Tabel 3.5.


Tabel 3.5 Ekspresi Logis Dalam Pilihan Tereduksi

Kolom Penjumlahan 0001 (x + y)

0011 (y + z)

Untuk mencari himpunan yang mencakup semua kolom, prime implicant (implikan

utama) dikelompokkan sehingga paling tidak setiap kolom ditandai sekali. Ini berarti

bahwa relasi berikut harus terpenuhi, dengan F adalah suku dalam Tabel pilihan

tereduksi: F = (x + y) (y + z)

Dengan menerapkan sifat-sifat aljabar Boolean didapat: F = (x + y) (y + z) = x y + x z + y + y z = x z + y

Setiap suku dalam persamaan ini menyatakan himpunan prime implicant (implikan

utama) yang mencakup suku-suku dalam Tabel pilihan tereduksi. Suku terkecil (y)

merupakan himpunan prime implicant (implikan utama), (0 1) terkecil yang

mencakup suku-suku tersisa. Hasil akhir yang di dapat sama seperti cara sebelumnya: F = x y z + x y z + y w + x w

3.3 Menyederhanakan Fungsi Jamak

Metode reduksi Tabel digunakan untuk mereduksi Fungsi Boolean tunggal. Namun

demikian cara ini juga dapat dipergunakan untuk mereduksi Fungsi jamak yang

menggunakan variabel yang sama, untuk menghasilkan persamaan kolektif yang kecil.

Metode berikut menggunakan cara dengan mencari irisan dari semua kemungkinan

kombinasi dari suku-suku yang dapat digunakan bersama, dan kemudian memilih

himpunan terkecil yang mencakup seluruh Fungsi.

Sebagai contoh kita gunakan Tabel kebenaran yang ada pada Tabel 3.6. yang

menunjukkan 3 (tiga) Fungsi dengan 3 (tiga) variabel. Notasi ini menunjukkan

minterm yang indeksnya 1 (satu) menurut Tabel kebenaran.


Bentuk lengkap persamaan Boolean dari kasus ini adalah: F0 (x, y, z) = m0 + m3 + m7

F1 (x, y, z) = m1 + m3 + m4 + m6 + m7

F2 (x, y, z) = m2 + m3 + m6 + m7

Irisan dibentuk dengan membuat semua kombinasi Fungsi seperti berikut: F0,1 (x, y, z) = m3 + m7

F0,2 (x, y, z) = m3 + m7

F1,2 (x, y, z) = m3 + m6 + m7

F0,1,2 (x, y, z) = m3 + m7

Tabel 3.6 Reduksi Fungsi Boolean Tunggal

Minterm X Y Z F0 F1 F2

m0 0 0 0

m1 0 0 1

m2 0 1 0

m3 0 1 1

m4 1 0 0

m5 1 0 1

m6 1 1 0

m7 1 1 1

1 0 0

0 1 0

0 0 1

1 1 1

0 1 0

0 0 0

0 1 1

1 1 1

Dengan menggunakan metode reduksi yang dijelaskan sebelumnya, dapat disusun

prime implicant (implikan utama) untuk masing-masing Fungsi.

Fungsi Prime implicant (implikan utama) F0 000, _11

F1 0_1, 1_0, _11, 11_

F2 _1_

F0,1 _11

F0,2 _11

F1,2 _11, 11_

F0,1,2 _11

Daftar prime implicant (implikan utama) direduksi dengan mengeliminasi

prime implicant (implikan utama) yang sudah tercantum pada Fungsi dengan orde


yang lebih tinggi. Misalnya, _11 muncul di F0,1,2, sehingga tidak perlu dicantumkan

dalam Fungsi yang lain. Demikian juga, 11_ muncul di F1,2, dan tidak perlu

dimunculkan di F1 ataupun F2. Demikian seterusnya, sehingga didapat:

Fungsi Prime implicant (implikan utama) F0 000

F1 0_1, 1_0

F2 _1_

F0,1 Kosong

F0,2 Kosong

F1,2 11_

F0,1,2 _11

Kemudian dapat disusun Tabel pilihan keluaran jamak seperti pada Tabel 3.7.

Baris berisi prime implicant (implikan utama) dan kolom menunjukkan minterm yang

harus tercantum pada masing-masing Fungsi.

Jika prime implicant (implikan utama) yang bersangkutan tidak dapat

digunakan pada Fungsi di kolom-kolom yang bersangkutan, maka baris akan diisi

dengan (×). Misalnya, prime implicant (implikan utama) 000 digunakan oleh Fungsi F₀

tetapi tidak digunakan oleh Fungsi F₁ maupun F₂, sehingga daerah perpotongan baris

000 dan kolom F₁ dan F₂ diisi ×.

Tabel 3.7 Reduksi Fungsi Boolean Jamak

Implikan Minterm

F₀(x,y,z) F₁(x,y,z) F₂(x,y,z)

Utama m₀ m₃ m₇ m₁ m₃ m₄ m₆ m₇ m₂ m₃ m₆ m₇

F₀ *000 √

X x x x x x x x X

F₁ *0_1 x x X √ √

x x x X

F₁ *1_0 x x X

√ √ x x x X

F₂ *_1 _ x x X X x x x x √ √ √ √

F₁,₂ *11_ x x X

√ √

√ √

F₀,₁,₂ *_11 √ √ √ √ √ √


Bentuk minimal dari persamaan keluaran didapat dengan cara yang mirip dengan

proses reduksi tabular. Dimulai dengan prime implicant (implikan utama) esensial.

Misalnya, minterm m₀ pada Fungsi F₀ hanya dicakup oleh prime implicant (implikan

utama) 000, sehingga 000 adalah esensial.

Baris yang berisi 000 kemudian dihapus dari Tabel, demikian juga kolom

yang berisi tanda cek pada baris tersebut. Proses berlanjut sampai semua Fungsi sudah

tercakup atau tinggal prime implicant (implikan utama) non esensial yang tersisa.

Cara menentukan himpunan terkecil dari prime implicant (implikan

utama) yang mencakup semua Fungsi adalah dengan cara yang sudah dijelaskan pada

bagian sebelumnya. Tanda asterisk (*) pada Tabel 3.7, adalah prime implicant

(implikan utama) esensial.

Pada kasus ini, hanya ada satu prime implicant (implikan utama) non

esensial yang tersisa, tetapi semua mintermnya sudah terwakili oleh prime implicant

(implikan utama) esensial, sehingga tidak perlu dibuat Tabel reduksi. Persamaan

tereduksinya menjadi: F₀ (x, y, z) = x y z + y z

F₁ (x, y, z) = x z + x z + y z

F₂ (x, y, z) = y

3.2 Keunggulan dan Kelemahan Metode Quine-McCluskey

Untuk fungsi-fungsi dengan cacah peubah yang lebih besar dari 6, terlebih untuk

sistem dengan keluaran ganda Multiple Input Multiple Output (MIMO) di mana

beberapa keluaran harus disederhanakan secara serentak, pemakaian peta Karnaugh

menjadi sangat sulit. Disamping itu, bila suatu kotak dalam peta Karnaugh

mempunyai kemungkinan penggabungan dengan beberapa kotak berdekatan, sering

kita tak dapat segera menentukan penggabungan mana yang terbaik. Kesulitan-

kesulitan ini dapat diatasi oleh metoda tabulasi yang diajukan oleh Quine dan

disempurnakan oleh McCluskey, dan karena itu disebut metoda Quine-McCluskey.


Walaupun metoda tabulasi sedikit membosankan bila dilakukan dengan tangan

(manual), tetapi penyederhanaan metode ini sangat sistematis dan cocok untuk

penyederhanaan dengan memakai komputer digital. Tidak ada batasan untuk jumlah

peubah dan juga dapat dipakai untuk sistem dengan keluaran ganda. Tetapi fungsi

yang akan disederhanakan dengan metoda tabulasi haruslah dalam bentuk jumlah

perkalian. Bila fungsi itu masih dalam bentuk perkalian-jumlah, maka terlebih dahulu

harus diubah ke bentuk jumlah-perkalian.


BAB 4

K E S I M P U L A N D A N S A R A N

4.1 Kesimpulan

Dari hasil pembahasan yang dilakukan, dapat disimpulkan bahwa:

1. Penyederhanaan Fungsi Boolean rangkaian dalam metode Quine-McCluskey

dapat dilakukan dengan cara tabel reduksi.

2. Menetapkan suku perkalian yang tersisa sebagai prime implicant (implikan

utama).

3. Mencari prime implicant (implikan utama) inti dari implikan- implikan utama

yang diperoleh, dengan cara membentuk Tabel prime implicant (implikan

utama).

4. Menerapkan prosedur covering untuk memperoleh Fungsi Boolean yang paling

sederhana.

4.2 Saran

Adapun saran penulis dari kesimpulan pembahasan di atas, yaitu:

Contoh studi kasus pada tugas akhir ini masih terbatas pada Fungsi Boolean rangkaian

digital yang ditentukan secara lengkap. Diharapkan kepada yang berminat dapat

melanjutkan ke penyederhanaan Fungsi Boolean rangkaian yang tidak ditentukan

secara lengkap dan Fungsi Boolean rangkaian digital sampai ke n buah variabel dan n

buah minterm.


D A F T A R P U S T A K A

Hill, Fredrick J., Gerald R. Peterson., 1981, Introduction to Switching Theory &

Logical design, Third Edition, Jhon Wiley & Sons, New York.

Holdsworth, B., 1993, Digital Logic Design, Third Edition, Butterworth Heineman,

London.

Lance, Larry R., John R. Hinton, 1986, Elementary Mathematics for Computing,

Addison-Wesley Publishing Company, London.

Lee, Samuel C., Sutisno, 1994, Rangkaian Digital dan Rangkaian Logika, Erlangga,

Jakarta.

Mowle, Frederic J., 1997, A Systematic Approach to Digital Logic Design, Addison

Wesley Publishing Company, London.

Nelson, Victor P., Nagle, Troy H., 1996, Digital Logic Circuit Analysis and Design,

Prentice Hall International Inc, London.

Tarigan, Pernantin, 1995, Rangkaian Logika Digital, USU Press, Medan.

studi metode quine-mccluskey untuk ...repository.usu.ac.id/bitstream/123456789/14128/1/09e...suku...

Documents