05 penyederhanaan fungsi boole

PenyederhanaanFungsi Boolean

Penyederhanaan Fungsi Boolean

Contoh.f(x, y) = x’y + x’y’ + y’disederhanakan menjadif(x, y) = x’ + y’

Penyederhanaan fungsi Boolean dapat dilakukandengan 3 cara:1. Secara aljabar2. Menggunakan Peta Karnaugh3. Menggunakan metode Quine Mc Cluskey

(metode Tabulasi)

Penyederhanaan secara Aljabar1. f(x, y) = x + x’y

= (x + x’)(x + y) = 1 ⋅ (x + y ) = x + y

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

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

Peta Karnaugh

a. Peta Karnaugh dengan dua peubah

b. Peta Karnough dengan tiga peubah

Peta KarnaughContoh.Diberikan tabel kebenaran, gambarkan Peta Karnaugh.

Peta Karnaugh

c. Peta dengan empat peubah

Peta KarnaughContoh. Diberikan tabel kebenaran, gambarkan

Peta Karnaugh.

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

1. Pasangan 1 buah bertetangga

Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz’Hasil Penyederhanaan: f(w, x, y, z) = wxy

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Bukti secara aljabar:f(w, x, y, z) = wxyz + wxyz’

= wxy(z + z’)= wxy(1)= wxy

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

2. Kuad: empat buah 1 yang bertetangga

Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’

Hasil penyederhanaan: f(w, x, y, z) = wx

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Bukti secara aljabar:f(w, x, y, z) = wxy’ + wxy

= wx(y’ + y)= wx(1)= wx

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Contoh lain:

Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wx’y’z’ + wx’y’z

Hasil penyederhanaan: f(w, x, y, z) = wy’

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

3. Oktet: delapan buah 1 yang bertetangga

Sebelum disederhanakan: f(a, b, c, d) = wxy’z’ + wxy’z + wxyz + wxyz’ +

wx’y’z’ + wx’y’z + wx’yz + wx’yz’

Hasil penyederhanaan: f(w, x, y, z) = w

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Bukti secara aljabar:f(w, x, y, z) = wy’ + wy

= w(y’ + y)= w

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

ContohSederhanakan fungsi Boolean f(x, y, z) = x’yz + xy’z’ + xyz + xyz’. Jawab:

Peta Karnaugh untuk fungsi tersebut adalah:

Hasil penyederhanaan: f(x, y, z) = yz + xz’

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

ContohAndaikan suatu tabel kebenaran telah diterjemah-kan ke dalam Peta Karnaugh. Sederhanakan fungsiBoolean yang bersesuaian sesederhana mungkin

Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = wy’ + yz’ + w’x’z

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

ContohMinimisasi fungsi Boolean yang bersesuaiandengan Peta Karnaugh di bawah ini.

Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = w + xy’z

Teknik Minimasi Fungsi Boolean dengan Peta KarnoughJika penyelesaian Contoh sebelumnya adalahseperti di bawah ini:

maka fungsi Boolean hasil penyederhanaan adalahf(w, x, y, z) = w + w’xy’z (jumlah literal = 5)yang ternyata masih belum sederhana dibandingkanf(w, x, y, z) = w + xy’z (jumlah literal = 4).

Teknik Minimasi Fungsi Boolean dengan Peta KarnoughContoh. (Penggulungan/rolling) Sederhanakan fungsi Boolean yang bersesuaiandengan Peta Karnaugh di bawah ini.

Jawab: f(w, x, y, z) = xy’z’ + xyz’ ==> belum sederhana

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Penyelesaian yang lebih minimal:

f(w, x, y, z) = xz’ ===> lebih sederhana

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Contoh: (Kelompok berlebihan) Sederhanakan fungsi Boolean yang bersesuaiandengan Peta Karnaugh di bawah ini.

Jawab: f(w, x, y, z) = xy’z + wxz + wyz → masih belumsederhana.

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Penyelesaian yang lebih minimal:

f(w, x, y, z) = xy’z + wyz ===> lebih sederhana

Teknik Minimasi Fungsi Boolean dengan Peta KarnoughContohSederhanakan fungsi Boolean yang bersesuaiandengan Peta Karnaugh di bawah ini.

Jawab: (lihat Peta Karnaugh di atas) f(a, b, c, d) = ab + ad + ac + bcd

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

ContohMinimisasi fungsi Boolean f(x, y, z) = x’z + x’y + xy’z + yzJawab:x’z = x’z(y + y’) = x’yz + x’y’zx’y = x’y(z + z’) = x’yz + x’yz’yz = yz(x + x’) = xyz + x’yzf(x, y, z) = x’z + x’y + xy’z + yz

= x’yz + x’y’z + x’yz + x’yz’ + xy’z + xyz + x’yz= x’yz + x’y’z + x’yz’ + xyz + xy’z

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Peta Karnaugh untuk fungsi tersebut adalah:

Hasil penyederhanaan: f(x, y, z) = z + x’yz’

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

4. Peta Karnaugh untuk lima peubah

Teknik Minimasi Fungsi Boolean dengan Peta KarnoughContoh (Contoh penggunaan Peta 5 peubah) Carilah fungsi sederhana darif(v, w, x, y, z) = Σ (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)Jawab:

Peta Karnaugh dari fungsi tersebut adalah:Jadif(v, w, x, y, z) = wz + v’w’z’+ vy’z

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Keadaan Don’t Care

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Contoh.Diberikan Tabel dibawah ini. Minimisasi fungsi f sesederhana mungkin.

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Jawab: Peta Karnaugh dari fungsi tersebut adalah:

Hasil penyederhanaan: f(a, b, c, d) = bd + c’d’ + cd

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Contoh

Minimisasi fungsi Boolean f(x, y, z) = x’yz + x’yz’ + xy’z’ + xy’z. Gambarkan rangkaian logikanya.

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Jawab: Rangkaian logika fungsi f(x, y, z) sebelumdiminimisasikan adalah seperti di bawah ini:

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

ContohBerbagai sistem digital menggunakan kode binary coded decimal (BCD). Diberikan Tabel dibawah untukkonversi BCD ke kode Excess-3 sebagai berikut:

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

(a) f1(w, x, y, z)

f1(w, x, y, z) = w + xz + xy = w + x(y + z)

(b) f2(w, x, y, z)

f2(w, x, y, z) = xy’z’ + x’z + x’y = xy’z’ + x’(y + z)

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

(c) f3(w, x, y, z)

f3(w, x, y, z) = y’z’ + yz

(d) f4(w, x, y, z)

f4(w, x, y, z) = z’

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Metode TabulasiPendekatan otomatis untuk menyederhanakan eks-presi Boolean biasa digunakan pada fungsi dengankeluaran tunggal atau jamak.

Metode tabulasi atau juga dikenal dengan metodeQuine-McCluskey, membentuk perkalian yang ber-beda pada 1 variabel secara berturut-turut, dan ke-mudian dihasilkan himpunan suku terreduksi yang dapat mencakup semua fungsi keluaran.

Proses ini lebih mudah diimplementasikan padakomputer daripada metode peta, dan hasil suku-suku reduksinya dapat digunakan oleh lebih dari 1 fungsi.

Menyederhanakan fungsi tunggal

Tabel kebenaran pada Gambar 5.1 menggambarkanF yang merupakan fungsi 4 variabel A,B,C, dan D, yang menyertakan 3 don’t care.

Proses reduksi secara tabel dimulai dengan menge-lompokkan minterm berdasarkan jumlah nilai 1-nya.

Minterm 0000, tidak mempunyai nilai 1, sehinggadijadikan grup tersendiri.

Minterm 0001, 0010, 0100, dan 1000 mempunyai ni-lai 1 tunggal, tetapi hanya minterm 0001 yang meng-hasilkan 1, sehingga minterm ini dijadikan grup lain.

Menyederhanakan fungsi tunggal

Gambar 5.1 Tabel kebenaran suatufungsi dengan don’t care

Menyederhanakan fungsi tunggal

Grup berikutnya adalah minterm dengan dua nilai 1, dan ada 6 kemungkinan minterm yang mempunyaidua nilai 1, yang dapat masuk dalam grup ini.

Hanya minterm 0011, 0101, 0110, dan 1010 yang menghasilkan keluaran 1, sehingga minterm inilahyang masuk dalam grup.

Ada 3 minterm yang menghasilkan keluaran 1 danmempunyai tiga nilai 1, yaitu 0111, 1011, dan 1110.

Akhirnya grup yang beranggotakan empat nilai 1 adasatu minterm, dan merupakan grup terakhir.

Menyederhanakan fungsi tunggal

Untuk tabel kebenaran yang lebih besar, proses dapatberlanjut terus.

Grup dikelompokkan lagi sehingga grup yang berbedatepat 1 jumlah nilai 1-nya dapat digabung, sepertiGambar 5.2a berikut ini.

Langkah berikutnya dalam proses reduksi adalahmembentuk sebuah konsensus antara setiap pasanggrup bertetangga untuk semua suku dengan bedanilai tepat 1 variabel saja. Bentuk umum teorema adalah:

Menyederhanakan fungsi tunggal

Gambar 5.2 Proses Reduksi tabulasi

Menyederhanakan fungsi tunggal

Suku Y Z adalah tidak perlu karena sudah tercakupoleh suku yang lain, sehingga dapat dieliminasi.

Secara aljabar, teorema tersebut dapat dibuktikansebagai berikut:

Menyederhanakan fungsi tunggal

Teorema konsensus juga mempunyai bentukdualitasnya:

Menyederhanakan fungsi tunggal

Ide dari penerapan konsensus pada reduksi tabula-si adalah untuk mengambil keuntungan dari sifat in-vers dari aljabar Boole, mirip seperti yang dipergu-nakan pada peta Karnaugh.

Misalnya, 0000 dan 0001 berbeda nilainya pada va-riabel D, sehingga 000_ dimasukkan dalam daftarpada bagian atas tabel reduksi seperti terlihat padaGambar 5.2b di atas.

Tanda garis bawah menunjukkan posisi variabelyang dieliminasi, dalam contoh ini D.

Menyederhanakan fungsi tunggal

Minterm 0000 dan 0001 pada Gambar a diatasditandai dengan cek ( ) untuk menunjukkan bahwaentri ini sudah tercakup pada tabel reduksi.

Setelah semua suku pada grup pertama disilangkandengan semua suku pada grup kedua, kemudianberalih untuk membentuk konsensus antara grupkedua dan ketiga.

Ada kemungkinan bahwa beberapa suku tidakdapat dikombinasi menjadi suku yang lebih kecilkare-na berbeda pada lebih dari 1 variabel.

Menyederhanakan fungsi tunggal

Contohnya, suku 0001 dan 0011 dapat dikombinasimenjadi suku lebih kecil 00_1 namun 0001 dan0110 tidak dapat dikombinasi karena berbeda pada3 variabel.

Sekali suku sudah ditandai dengan , sukutersebut masih dapat dipergunakan untuk prosesreduksi karena sifat idempotens.

Tujuan dari langkah dalam proses ini adalah untukmenemukan semua kemungkinan suku terreduksi, sehingga kita dapat menemukan himpunan terkecilsuku yang masuk dalam fungsi pada langkahberikutnya

Menyederhanakan fungsi tunggal

Proses berlanjut untuk grup-grup sisanya.

Setiap suku yang tidak tercakup dalampengelompokkan konsensus ditandai denganasteris (*) untuk menunjukkan bahwa ini adalahsuku prime implicant.

Pada Gambar 5.2a diatas terlihat bahwa setelahreduksi pertama semua minterm sudah terpakaisehingga tidak ada prime implicant.

Menyederhanakan fungsi tunggal

Setelah reduksi pertama, kita dapat melanjutkanuntuk iterasi berikutnya.

Dua suku dapat dikombinasi jika keduanya hanyaberbeda 1 variabel saja.

Garis bawah harus pada posisi yang sama.

Entri pertama pada Gambar 5.2b diatas mempunyaigaris bawah pada kolom paling kanan, sehinggatidak ada entri pada grup kedua yang cocok.

Menyederhanakan fungsi tunggal

Dalam penyusunan tabel reduksi pada Gambar5.2c, prime implicant dari tabel sebelumnya(Gambar 5.2b) tidak diikutkan.

Proses berlanjut sampai hanya tersisa prime implicant.

Pada contoh ini, proses berhenti setelah reduksikedua dan menghasilkan 3 suku tersisa sebagaiprime implicant seperti pada Gambar 5.2c.

Setiap prime implicant dikumpulkan untuk menyu-sun fungsi, walaupun belum minimal.

Menyederhanakan fungsi tunggal

Oleh karena itu entri ini ditandai dengan *,yang menunjukkan bahwa suku ini adalah prime implicant dan tidak dapat direduksi lagi.

Kita beralih ke grup kedua dan ketiga pada Gambar5.2 b.

Suku 00_1 dan 01_1 dikombinasi menjadi suku0__1 seperti tertera pada 5.2c.

Proses terus terlanjut hingga reduksi kedualengkap.

Menyederhanakan fungsi tunggal

Untuk meminimalkan suku-suku yang digunakan, disusun tabel pilihan seperti pada Gambar dibawahini.

Setiap prime implicant dibuat 1 baris dalam table pilihan dan kolom berisi minterm dari fungsi asliyang harus dicakup.

Kondisi don’t care tidak perlu dicakup sehinggatidak dimasukkan dalam daftar.

Setiap kotak yang sesuai dengan prime implicantdan mintermnya ditandai dengan *.

Menyederhanakan fungsi tunggal

Misalnya, prime implicant 000_ tandai pada kolomminterm 0001.

Beberapa prime implicant mencakup beberapaminterm, seperti 0__1 akan mencakup 4 minterm.

Setelah semua kotak dicek, maka cari kolom yang hanya berisi 1 tanda cek. Tanda cek tunggal pada kolom berarti hanya ada 1 prime implicant yang mencakup minterm tersebut, dan prime implicant yang mencakup minterm tersebut di tandai denganyang menunjukkan bahwa prime implicant ini adalahesensial dan harus digunakan atau masuk dalampersamaan akhir.

Menyederhanakan fungsi tunggal

Menyederhanakan fungsi tunggalContoh prime implicant esensial adalah 011_ , 101_ , dan _1_1.

Prime implicant esensial dapat mencakup lebih darisatu minterm.

Untuk itu dibuatlah tabel pilihan terreduksi yang tidakmenyertakan prime implicant esensial danmintermnya, seperti pada Gambar di bawah.

Tabel pilihan terreduksi dapat berisi prime implicantesensial yang kemudian dikenai proses reduksi lagi, sampai tabel pilihan terreduksi hanya berisi prime implicant nonesensial.

Menyederhanakan fungsi tunggal

Menyederhanakan fungsi tunggal

Sisa prime implicant dalam tabel pilihan terreduksimembentuk himpunan pilihan, yang digunakan untukmendapatkan himpunan minimal.

Seperti pada Gambar diatas, ada 2 himpunan prime implicant yang menampung 2 minterm sisa.

Karena himpunan 2 adalah suku paling sederhana, maka suku inilah yang dipilih untuk membentukpersamaan minimal untuk F, yang terdiri atas prime implicant esensial dan prime implicant pilihan padahimpunan 2 (Persamaan berikut).

Menyederhanakan fungsi tunggal

Selain menggunakan cara visual untuk mendapat-kan himpunan dari himpunan pilihan, dapat jugadilakukan proses secara algoritmis.

Proses dimulai dengan menyatakan persamaanyang mencakup semua prime implicant dalamhimpunan pilihan pada Gambar di atas.

Ekspresi logis ditulis untuk setiap kolom pada tabelpilihan terreduksi seperti berikut:

Menyederhanakan fungsi tunggal

Untuk mencari himpunan yang mencakup semuakolom, prime implicant dikelompokkan sehinggapaling tidak setiap kolom ditandai sekali.

Ini berarti bahwa relasi berikut harus terpenuhi, dengan G adalah adalah suku dalam tabel pilihanterreduksi:

Menyederhanakan fungsi tunggal

Dengan menerapkan sifat-sifat aljabar Boole didapat:

Setiap suku dalam persamaan ini menyatakan him-punan prime implicant yang mencakup suku-sukudalam tabel pilihan terreduksi. Suku terkecil (Y ) merupakan himpunan prime implicant (0 1) terkecil yang mencakup suku-sukutersisa. Hasil akhir yang didapat sama seperti carasebelumnya:

Menyederhanakan fungsi Jamak

Metode reduksi tabel digunakan untuk mereduksifungsi Boolean tunggal.

Namun demikian cara ini juga dapat dipergunakanuntuk mereduksi fungsi jamak yang menggunakanvariabel yang sama, untuk menghasilkan persama-an kolektif yang kecil.

Metode berikut menggunakan cara dengan mencariirisan dari semua kemungkinan kombinasi dari suku-suku yang dapat digunakan bersama, dan kemudianmemilih himpunan terkecil yang mencakup seluruhfungsi.

Menyederhanakan fungsi Jamak

Sebagai contoh kita gunakan tabel kebenaran yang ada pada Gambar dibawah yang menunjukkan 3 fungsi dengan 3 variabel.

Notasi ini menunjukkan minterm yang indeksnya i menurut tabel kebenaran.

Bentuk lengkap persamaan Boolean dari kasus iniadalah:

Menyederhanakan fungsi Jamak

Irisan dibentuk dengan membuat semua kombinasifungsi seperti berikut:

Menyederhanakan fungsi Jamak

Dengan menggunakan metode reduksi yang dijelas-kan sebelumnya, dapat disusun prime implicantuntuk masing-masing fungsi:

Menyederhanakan fungsi Jamak

Daftar prime implicant direduksi dengan mengelimi-nasi prime implicant yang sudah tercantum padafungsi dengan orde yang lebih tinggi.

Misalnya, _11 muncul di F0,1,2, sehingga tidak perludicantumkan dalam fungsi yang lain.

Demikian juga, 11_ muncul di F1,2, dan tidak perludimunculkan di F1ataupun F2.

Demikian seterusnya, sehingga didapat:

Menyederhanakan fungsi Jamak

Kemudian dapat disusun tabel pilihan keluaran ja-mak seperti pada Gambar dibawah.

Baris berisi prime implicant dan kolom menunjukkanminterm yang harus tercantum pada masing-masingfungsi.

Menyederhanakan fungsi Jamak

Baris akan diisi dengan × jika prime implicant yang bersangkutan tidak dapat digunakan pada fungsi dikolom-kolom yang bersangkutan.

Misalnya, prime implicant 000 digunakan oleh fungsiF0 tetapi tidak digunakan oleh fungsi F1 maupun F2, sehingga daerah perpotongan baris 000 dan kolomF1 dan F2 diisi ×.

Menyederhanakan fungsi Jamak

Bentuk minimal dari persamaan keluaran didapatdengan cara yang mirip dengan proses reduksitabular.

Kita mulai dengan prime implicant esensial.

Menyederhanakan fungsi JamakMisalnya, minterm m0 pada fungsi F0 hanya dica-kup oleh prime implicant 000, sehingga 000 adalahesensial.

Baris yang berisi 000 kemudian dihapus dari tabel, demikian juga kolom yang berisi tanda cek padabaris tersebut.

Proses berlanjut sampai semua fungsi sudah terca-kup atau tinggal prime implicant nonesensial yang tersisa.

Menyederhanakan fungsi JamakCara menentukan himpunan terkecil dari prime implicant yang mencakup semua fungsi adalahdengan cara yang sudah dijelaskan pada bagiansebelumnya.

Tanda asterisk pada Gambar di atas adalah prime implicant esensial.

Pada kasus ini, hanya ada satu prime implicantnonesensial (11_) yang tersisa, tetapi semuamintermnya sudah terwakili oleh prime implicantesensial, sehingga tidak perlu dibuat tabel reduksi. Persamaan terreduksinya menjadi:

Menyederhanakan fungsi Jamak