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

STUDI METODE QUINE-McCLUSKEY UNTUK MENYEDERHANAKAN RANGKAIAN DIGITAL

SAFRINA AMANAH

SITEPU

030823042

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009

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


SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains

SAFRINA AMANAH

SITEPU

030823042

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

:SAFRINA AMANAH

Nomor Induk Mahasiswa

:030823042

Program Studi

: SARJANA (S1) MATEMATIK

Departemen

: MATEMATIKA

Fakultas

: MATEMATIKA DAN ILMU PEGETAHUAN

SITEPU

ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan Medan,

Komisi Pembimbing

Pembimbing 2

Drs.Sawaluddin, M.IT NIP.132206398

Pembimbing 1

Drs. Bambang Irawan, M.Sc NIP.130535480

Diketahui/Disetujui oleh Departemen Matematikan FMIPA USU

Dr. Saib Suwilo, M.Sc Nip 131796149


PERNYATAAN


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

SAFRINA AMANAH SITEPU 030823042


ABSTRAK

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.


DAFTAR

ISI

Halaman Persetujuan ................................................................................................................. ii Abstrak ...................................................................................................................... iii Abstract ..................................................................................................................... iv Daftar Isi .................................................................................................................... v Daftar Tabel .............................................................................................................. vi Daftar Istilah............................................................................................................. vii Bab 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7

PENDAHULUAN Latar Belakang ......................................................................................... 1 Perumusan Masalah .................................................................................. 1 Tujuan ...................................................................................................... 1 Pembatasan Masalah ................................................................................ 2 Metodologi Penelitian............................................................................... 2 Kontribusi Penelitian ................................................................................ 2 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 3.1 3.2 3.2

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

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


DAFTAR TABEL

2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 3.1 3.2 3.3 3.4 3.5 3.6 3.7

Tabel Operator Biner dalam Perkalian dan Penjumlahan ................... 5 Tabel Hukum Distributif........................................................................ 6 Tabel Fungsi f(x,y,z) = x y’z ............................................................ 9 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 Tabel Minterm dan Maxterm 2 (dua) Variabel .................................. 12 Tabel Minterm dan Maxterm 3 (tiga) Variabel .................................. 12 Tabel Fungsi f(x,y,z) dalam bentuk Kanonik SOP dan POS .............. 13 Tabel Gerbang (Gate) Rangkaian Logika Dasar ................................ 17 Tabel Kebenaran Suatu Fungsi dengan don’t Care ............................ 21 Tabel Proses Reduksi Tabulasi ............................................................ 22 Tabel Reduksi Esensial......................................................................... 25 Tabel Tereduksi Non Esensial.............................................................. 25 Tabel Ekspresi Logis Dalam Pilihan Tereduksi .................................. 26 Tabel Reduksi Fungsi Boolean Tunggal .............................................. 27 Tabel Reduksi Fungsi Boolean Jamak ............................................... 29


DAFTAR ISTILAH 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

PENDAHULUAN

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

LANDASAN TEORI

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.

7.

Terdapat sedikitnya 2 (dua) buah elemen, x dan y ∈ B , sedemikian hingga berlaku

: x ≠ y.

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. Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

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.

3.

5.

Hukum Identitas: (i). x + 0 = x

(i). x • x = x

(ii). x • 1 = x

(ii). x + x = x

Hukum Komplemen:

9.

4. Hukum Dominan:

(i). x + x = 1

(i). x • 0 = 0

(ii). x • x = 0

(ii). x + 1 = 1

Hukum Involusi: (i). x = x

7.

2. Hukum Idempoten:

Hukum Komutatif:

6. Hukum Absorbsi (Penyerapan): (i). x • y + x • y = x 8. Hukum Asosiatif:

(i). x + y = y + x

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

(ii). x • y = y • x

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

Hukum Distributif:

10. Hukum De Morgan:

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

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

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

(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

2.

=

(x + x y) + x’y

(Absorbsi)

=

x + (x y + x’y)

(Asosiatif)

=

x + (x + x’) y

(Distributif)

=

x + 1 . y

(Komplemen)

=

x + y

(Identitas)

Buktikan bahwa: x (x’+ y) = x y Bukti: x (x’ + y)

2.5

=

x x’ + x y

(Distributif)

=

0 + x y

(Komplemen)

=

x y

(Identitas)

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 Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

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)

2.6

=

x’y’z + x’y z + x y’

=

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

=

x’z (1) + x y’

=

x’z + x y’

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’ Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

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

2.

=

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

=

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

=

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

=

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

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: Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

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 Minterm x

Maxterm

y

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

=

M0 M2 M3

=

∏(0, 2, 3)

(x’y z)’

Jadi mj’ = Mj Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

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.

x y

x

xy

y

Gambar 1.a Gerbang AND dua masukan

x+ y

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.

x y

(xy)'

Gambar 1.d Gerbang NAND

x y

(x + y)'

Gambar 1.e Gerbang NOR


x

x

x+ y

y

(x + y)'

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

OR

NOT

NAND

x y

x y

x.y

x+y

x

x

x y

(x.y)

x 0 0 1 1

y 0 1 0 1

x 0 0 1 1

y 0 1 0 1

x 0 1

x 1 0

x 0 0 1 1

y 0 1 0 1

x 0 0

y 0 1

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

(x.y) 1 1 1 0

(x+y) 1 0


1 1 NOR

x y

(x+y)

XOR

x y

x y

XNOR

x y)

x y

0 1

x 0 0 1 1

y 0 1 0 1

x 0 0 1 1

y 0 1 0 1

0 0

x

y 0 1 1 0

(x y ) 1 0 0 1

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

Jawab: a.

Langkah I:

x y

xy xy + x' y

x y

b.

x'

x' y

Langkah II:


x y

xy xy + x' y x'

c.

x' y

Langkah III:

x y

xy xy + x' y x'

x' y

BAB 3

PEMBAHASAN

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 1nya. 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. Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

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

√

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

√

1

-

1

1

√

1

1

-

1

√

(a)

(c)

(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 y + x z

x z (1 + y)

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

Minterm 0001

0001

0101

0110

0111

√

√

1101

√

*011_

√

*101_ 0_ _1

1010

√

√

√

√


√

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

Pilihan

0001 0011

x

000_

√

y

0_ _1

√

z

_ _11

Himpunan 1 000_

Himpunan 2 0_

_1

_ _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. Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

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

=

m3 + m7

F0,1,2

(x, y, z)

Tabel 3.6 Reduksi Fungsi Boolean Tunggal F0 F1 F2

Minterm

X

Y

Z

m0

0

0

0

1

0

0

m1

0

0

1

0

1

0

m2

0

1

0

0

0

1

m3

0

1

1

1

1

1

m4

1

0

0

0

1

0

m5

1

0

1

0

0

0

m6

1

1

0

0

1

1

m7

1

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 Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

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

m₀

m₃

m₇

*0_1

x

x

X

*1_0

x

x

X

*_1 _

x

x

X

*11_

x

x

X

√

√

Utama F₀ F₁ F₁ F₂

F₁,₂

F₀,₁,₂

F₀(x,y,z)

*000

*_11

√

m₁ X √

X

F₁(x,y,z)

m₃ x √

x √

m₄ x

m₆ x

m₇ x

√

√

x

x

x

√

√ √

m₂

F₂(x,y,z) m₃

m₆

m₇

x

x

x

X

x

x

x

X

√

√

√

√

√

√

x

x

x

√


X

√

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

=

x z + x z + y z

F₂ (x, y, z)

=

y

F₁ (x, y, z)

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. Kesulitankesulitan ini dapat diatasi oleh metoda tabulasi yang diajukan oleh Quine dan disempurnakan oleh McCluskey, dan karena itu disebut metoda Quine-McCluskey. Safrina Amanah Sitepu : Studi Metode Quine-McCluskey Untuk Menyederhanakan Rangkaian Digital, 2009. USU Repository © 2009

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

KESIMPULAN DAN SARAN

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.



DAFTAR PUSTAKA

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 MENYEDERHANAKAN RANGKAIAN DIGITAL S A F R I N A A M A N A H S I T E P U

Recommend Documents