05 penyederhanaan fungsi boole

72
Penyederhanaan Fungsi Boolean

Upload: api-3709911

Post on 07-Jun-2015

4.762 views

Category:

Documents


8 download

TRANSCRIPT

Page 1: 05 Penyederhanaan Fungsi Boole

PenyederhanaanFungsi Boolean

Page 2: 05 Penyederhanaan Fungsi Boole

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)

Page 3: 05 Penyederhanaan Fungsi Boole

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

Page 4: 05 Penyederhanaan Fungsi Boole

Peta Karnaugh

a. Peta Karnaugh dengan dua peubah

b. Peta Karnough dengan tiga peubah

Page 5: 05 Penyederhanaan Fungsi Boole

Peta KarnaughContoh.Diberikan tabel kebenaran, gambarkan Peta Karnaugh.

Page 6: 05 Penyederhanaan Fungsi Boole

Peta Karnaugh

c. Peta dengan empat peubah

Page 7: 05 Penyederhanaan Fungsi Boole

Peta KarnaughContoh. Diberikan tabel kebenaran, gambarkan

Peta Karnaugh.

Page 8: 05 Penyederhanaan Fungsi Boole

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

Page 9: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

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

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

Page 10: 05 Penyederhanaan Fungsi Boole

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

Page 11: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

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

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

Page 12: 05 Penyederhanaan Fungsi Boole

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’

Page 13: 05 Penyederhanaan Fungsi Boole

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

Page 14: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

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

= w(y’ + y)= w

Page 15: 05 Penyederhanaan Fungsi Boole

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’

Page 16: 05 Penyederhanaan Fungsi Boole

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

Page 17: 05 Penyederhanaan Fungsi Boole

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

Page 18: 05 Penyederhanaan Fungsi Boole

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

Page 19: 05 Penyederhanaan Fungsi Boole

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

Page 20: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Penyelesaian yang lebih minimal:

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

Page 21: 05 Penyederhanaan Fungsi Boole

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.

Page 22: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Penyelesaian yang lebih minimal:

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

Page 23: 05 Penyederhanaan Fungsi Boole

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

Page 24: 05 Penyederhanaan Fungsi Boole

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

Page 25: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Peta Karnaugh untuk fungsi tersebut adalah:

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

Page 26: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

4. Peta Karnaugh untuk lima peubah

Page 27: 05 Penyederhanaan Fungsi Boole

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

Page 28: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Keadaan Don’t Care

Page 29: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

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

Page 30: 05 Penyederhanaan Fungsi Boole

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

Page 31: 05 Penyederhanaan Fungsi Boole

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.

Page 32: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

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

Page 33: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Page 34: 05 Penyederhanaan Fungsi Boole

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:

Page 35: 05 Penyederhanaan Fungsi Boole

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)

Page 36: 05 Penyederhanaan Fungsi Boole

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’

Page 37: 05 Penyederhanaan Fungsi Boole

Teknik Minimasi Fungsi Boolean dengan Peta Karnough

Page 38: 05 Penyederhanaan Fungsi Boole

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.

Page 39: 05 Penyederhanaan Fungsi Boole

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.

Page 40: 05 Penyederhanaan Fungsi Boole

Menyederhanakan fungsi tunggal

Gambar 5.1 Tabel kebenaran suatufungsi dengan don’t care

Page 41: 05 Penyederhanaan Fungsi Boole

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.

Page 42: 05 Penyederhanaan Fungsi Boole

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:

Page 43: 05 Penyederhanaan Fungsi Boole

Menyederhanakan fungsi tunggal

Gambar 5.2 Proses Reduksi tabulasi

Page 44: 05 Penyederhanaan Fungsi Boole

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:

Page 45: 05 Penyederhanaan Fungsi Boole

Menyederhanakan fungsi tunggal

Teorema konsensus juga mempunyai bentukdualitasnya:

Page 46: 05 Penyederhanaan Fungsi Boole

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.

Page 47: 05 Penyederhanaan Fungsi Boole

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.

Page 48: 05 Penyederhanaan Fungsi Boole

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

Page 49: 05 Penyederhanaan Fungsi Boole

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.

Page 50: 05 Penyederhanaan Fungsi Boole

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.

Page 51: 05 Penyederhanaan Fungsi Boole

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.

Page 52: 05 Penyederhanaan Fungsi Boole

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.

Page 53: 05 Penyederhanaan Fungsi Boole

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 *.

Page 54: 05 Penyederhanaan Fungsi Boole

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.

Page 55: 05 Penyederhanaan Fungsi Boole

Menyederhanakan fungsi tunggal

Page 56: 05 Penyederhanaan Fungsi Boole

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.

Page 57: 05 Penyederhanaan Fungsi Boole

Menyederhanakan fungsi tunggal

Page 58: 05 Penyederhanaan Fungsi Boole

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

Page 59: 05 Penyederhanaan Fungsi Boole

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:

Page 60: 05 Penyederhanaan Fungsi Boole

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:

Page 61: 05 Penyederhanaan Fungsi Boole

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:

Page 62: 05 Penyederhanaan Fungsi Boole

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.

Page 63: 05 Penyederhanaan Fungsi Boole

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:

Page 64: 05 Penyederhanaan Fungsi Boole

Menyederhanakan fungsi Jamak

Irisan dibentuk dengan membuat semua kombinasifungsi seperti berikut:

Page 65: 05 Penyederhanaan Fungsi Boole

Menyederhanakan fungsi Jamak

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

Page 66: 05 Penyederhanaan Fungsi Boole

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:

Page 67: 05 Penyederhanaan Fungsi Boole

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.

Page 68: 05 Penyederhanaan Fungsi Boole

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 ×.

Page 69: 05 Penyederhanaan Fungsi Boole

Menyederhanakan fungsi Jamak

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

Kita mulai dengan prime implicant esensial.

Page 70: 05 Penyederhanaan Fungsi Boole

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.

Page 71: 05 Penyederhanaan Fungsi Boole

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:

Page 72: 05 Penyederhanaan Fungsi Boole

Menyederhanakan fungsi Jamak