05 Penyederhanaan Fungsi Boole 6m193i
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report 2z6p3t
Overview 5o1f4z
& View 05 Penyederhanaan Fungsi Boole as PDF for free.
More details 6z3438
- Words: 2,627
- Pages: 72
Penyederhanaan Fungsi Boolean
Penyederhanaan Fungsi Boolean Contoh. f(x, y) = x’y + x’y’ + y’ disederhanakan menjadi f(x, y) = x’ + y’ Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara: 1. Secara aljabar 2. Menggunakan Peta Karnaugh 3. Menggunakan metode Quine Mc Cluskey (metode Tabulasi)
Penyederhanaan secara Aljabar 1. 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 Karnaugh Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
Peta Karnaugh c. Peta dengan empat peubah
Peta Karnaugh Contoh. 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
Contoh Sederhanakan 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
Contoh Andaikan suatu tabel kebenaran telah diterjemahkan ke dalam Peta Karnaugh. Sederhanakan fungsi Boolean 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
Contoh Minimisasi fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = w + xy’z
Teknik Minimasi Fungsi Boolean dengan Peta Karnough
Jika penyelesaian Contoh seperti di bawah ini:
sebelumnya
adalah
maka fungsi Boolean hasil penyederhanaan adalah f(w, x, y, z) = w + w’xy’z (jumlah literal = 5) yang ternyata masih belum sederhana dibandingkan f(w, x, y, z) = w + xy’z (jumlah literal = 4).
Teknik Minimasi Fungsi Boolean dengan Peta Karnough
Contoh. (Penggulungan/rolling) Sederhanakan fungsi Boolean yang bersesuaian dengan 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 bersesuaian dengan Peta Karnaugh di bawah ini.
Jawab: f(w, x, y, z) = xy’z + wxz + wyz → masih belum sederhana.
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 Karnough
Contoh Sederhanakan fungsi Boolean yang bersesuaian dengan 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
Contoh Minimisasi fungsi Boolean f(x, y, z) = x’z + x’y + xy’z + yz Jawab: x’z = x’z(y + y’) = x’yz + x’y’z x’y = x’y(z + z’) = x’yz + x’yz’ yz = yz(x + x’) = xyz + x’yz f(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 Karnough
Contoh (Contoh penggunaan Peta 5 peubah) Carilah fungsi sederhana dari f(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: Jadi f(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) sebelum diminimisasikan adalah seperti di bawah ini:
Teknik Minimasi Fungsi Boolean dengan Peta Karnough
Teknik Minimasi Fungsi Boolean dengan Peta Karnough
Contoh Berbagai sistem digital menggunakan kode binary coded decimal (BCD). Diberikan Tabel dibawah untuk konversi 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 Tabulasi
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 variabel secara berturut-turut, dan kemudian dihasilkan himpunan suku terreduksi yang dapat mencakup semua fungsi keluaran. Proses ini lebih mudah diimplementasikan pada komputer daripada metode peta, dan hasil sukusuku reduksinya dapat digunakan oleh lebih dari 1 fungsi.
Menyederhanakan fungsi tunggal
Tabel kebenaran pada Gambar 5.1 menggambarkan F yang merupakan fungsi 4 variabel A,B,C, dan D, yang menyertakan 3 don’t care. 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 1, sehingga minterm ini dijadikan grup lain.
Menyederhanakan fungsi tunggal
Gambar 5.1 Tabel kebenaran suatu fungsi dengan don’t care
Menyederhanakan fungsi tunggal
Grup berikutnya adalah minterm dengan dua nilai 1, dan ada 6 kemungkinan minterm yang mempunyai 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 minterm yang menghasilkan keluaran 1 dan mempunyai tiga nilai 1, yaitu 0111, 1011, dan 1110. Akhirnya grup yang beranggotakan empat nilai 1 ada satu minterm, dan merupakan grup terakhir.
Menyederhanakan fungsi tunggal
Untuk tabel kebenaran yang lebih besar, proses dapat berlanjut terus. Grup dikelompokkan lagi sehingga grup yang berbeda tepat 1 jumlah nilai 1-nya dapat digabung, seperti Gambar 5.2a berikut ini. Langkah berikutnya dalam proses reduksi adalah membentuk sebuah konsensus antara setiap pasang grup bertetangga untuk semua suku dengan beda nilai 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 tercakup oleh suku yang lain, sehingga dapat dieliminasi. Secara aljabar, teorema tersebut dapat dibuktikan sebagai berikut:
Menyederhanakan fungsi tunggal
Teorema konsensus dualitasnya:
juga
mempunyai
bentuk
Menyederhanakan fungsi tunggal
Ide dari penerapan konsensus pada reduksi tabulasi adalah untuk mengambil keuntungan dari sifat invers dari aljabar Boole, mirip seperti yang dipergunakan pada peta Karnaugh. Misalnya, 0000 dan 0001 berbeda nilainya pada variabel D, sehingga 000_ dimasukkan dalam daftar pada bagian atas tabel reduksi seperti terlihat pada Gambar 5.2b di atas. Tanda garis bawah menunjukkan posisi variabel yang dieliminasi, dalam contoh ini D.
Menyederhanakan fungsi tunggal
Minterm 0000 dan 0001 pada Gambar a diatas ditandai dengan cek (3) untuk menunjukkan bahwa entri ini sudah tercakup pada tabel reduksi. Setelah semua suku pada grup pertama disilangkan dengan semua suku pada grup kedua, kemudian beralih untuk membentuk konsensus antara grup kedua dan ketiga. Ada kemungkinan bahwa beberapa suku tidak dapat dikombinasi menjadi suku yang lebih kecil kare-na berbeda pada lebih dari 1 variabel.
Menyederhanakan fungsi tunggal
Contohnya, suku 0001 dan 0011 dapat dikombinasi menjadi suku lebih kecil 00_1 namun 0001 dan 0110 tidak dapat dikombinasi karena berbeda pada 3 variabel. Sekali suku sudah ditandai dengan 3, suku tersebut masih dapat dipergunakan untuk proses reduksi karena sifat idempotens. Tujuan dari langkah dalam proses ini adalah untuk menemukan semua kemungkinan suku terreduksi, sehingga kita dapat menemukan himpunan terkecil suku yang masuk dalam fungsi pada langkah berikutnya
Menyederhanakan fungsi tunggal
Proses berlanjut untuk grup-grup sisanya. Setiap suku yang tidak tercakup dalam pengelompokkan konsensus ditandai dengan asteris (*) untuk menunjukkan bahwa ini adalah suku prime implicant. Pada Gambar 5.2a diatas terlihat bahwa setelah reduksi pertama semua minterm sudah terpakai sehingga tidak ada prime implicant.
Menyederhanakan fungsi tunggal
Setelah reduksi pertama, kita dapat melanjutkan untuk iterasi berikutnya. Dua suku dapat dikombinasi jika keduanya hanya berbeda 1 variabel saja. Garis bawah harus pada posisi yang sama. Entri pertama pada Gambar 5.2b diatas mempunyai garis bawah pada kolom paling kanan, sehingga tidak ada entri pada grup kedua yang cocok.
Menyederhanakan fungsi tunggal
Dalam penyusunan tabel reduksi pada Gambar 5.2c, prime implicant dari tabel sebelumnya (Gambar 5.2b) tidak diikutkan. Proses berlanjut sampai hanya tersisa prime implicant. Pada contoh ini, proses berhenti setelah reduksi kedua dan menghasilkan 3 suku tersisa sebagai prime implicant seperti pada Gambar 5.2c. Setiap prime implicant dikumpulkan untuk menyusun 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 Gambar 5.2 b. Suku 00_1 dan 01_1 dikombinasi menjadi suku 0__1 seperti tertera pada 5.2c. Proses terus lengkap.
terlanjut
hingga
reduksi
kedua
Menyederhanakan fungsi tunggal
Untuk meminimalkan suku-suku yang digunakan, disusun tabel pilihan seperti pada Gambar dibawah ini. Setiap prime implicant dibuat 1 baris dalam table 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 dan mintermnya ditandai dengan *.
Menyederhanakan fungsi tunggal
Misalnya, prime implicant 000_ tandai pada kolom minterm 0001. Beberapa prime implicant mencakup beberapa minterm, 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 dengan yang menunjukkan bahwa prime implicant ini adalah esensial dan harus digunakan atau masuk dalam persamaan akhir.
Menyederhanakan fungsi tunggal
Menyederhanakan fungsi tunggal
Contoh prime implicant esensial adalah 011_ , 101_ , dan _1_1. Prime implicant esensial dapat mencakup lebih dari satu minterm. Untuk itu dibuatlah tabel pilihan terreduksi yang tidak menyertakan prime implicant esensial dan mintermnya, seperti pada Gambar di bawah. Tabel pilihan terreduksi dapat berisi prime implicant esensial 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 terreduksi membentuk himpunan pilihan, yang digunakan untuk mendapatkan 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 membentuk persamaan minimal untuk F, yang terdiri atas prime implicant esensial dan prime implicant pilihan pada himpunan 2 (Persamaan berikut).
Menyederhanakan fungsi tunggal
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 dalam himpunan pilihan pada Gambar di atas. Ekspresi logis ditulis untuk setiap kolom pada tabel pilihan terreduksi seperti berikut:
Menyederhanakan fungsi tunggal
Untuk mencari himpunan yang mencakup semua kolom, prime implicant dikelompokkan sehingga paling tidak setiap kolom ditandai sekali. Ini berarti bahwa relasi berikut harus terpenuhi, dengan G adalah adalah suku dalam tabel pilihan terreduksi:
Menyederhanakan fungsi tunggal
Dengan menerapkan sifat-sifat aljabar Boole didapat:
Setiap suku dalam persamaan ini menyatakan himpunan prime implicant yang mencakup suku-suku dalam tabel pilihan terreduksi. Suku terkecil (Y ) merupakan himpunan prime implicant (0 1) terkecil yang mencakup suku-suku tersisa. Hasil akhir yang didapat sama seperti cara sebelumnya:
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 sukusuku yang dapat digunakan bersama, dan kemudian memilih himpunan terkecil yang mencakup seluruh fungsi.
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 ini adalah:
Menyederhanakan fungsi Jamak
Irisan dibentuk dengan membuat semua kombinasi fungsi seperti berikut:
Menyederhanakan fungsi Jamak
Dengan menggunakan metode reduksi yang dijelaskan sebelumnya, dapat disusun prime implicant untuk masing-masing fungsi:
Menyederhanakan fungsi Jamak
Daftar prime implicant direduksi dengan mengeliminasi prime implicant 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 F1ataupun F2. Demikian seterusnya, sehingga didapat:
Menyederhanakan fungsi Jamak
Kemudian dapat disusun tabel pilihan keluaran jamak seperti pada Gambar dibawah. Baris berisi prime implicant dan kolom menunjukkan minterm yang harus tercantum pada masing-masing fungsi.
Menyederhanakan fungsi Jamak
Baris akan diisi dengan × jika prime implicant yang bersangkutan tidak dapat digunakan pada fungsi di kolom-kolom yang bersangkutan. Misalnya, prime implicant 000 digunakan oleh fungsi F0 tetapi tidak digunakan oleh fungsi F1 maupun F2, sehingga daerah perpotongan baris 000 dan kolom F1 dan F2 diisi ×.
Menyederhanakan fungsi Jamak
Bentuk minimal dari persamaan keluaran didapat dengan cara yang mirip dengan proses reduksi tabular. Kita mulai dengan prime implicant esensial.
Menyederhanakan fungsi Jamak
Misalnya, minterm m0 pada fungsi F0 hanya dicakup oleh prime implicant 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 nonesensial yang tersisa.
Menyederhanakan fungsi Jamak
Cara menentukan himpunan terkecil dari prime implicant yang mencakup semua fungsi adalah dengan cara yang sudah dijelaskan pada bagian sebelumnya. Tanda asterisk pada Gambar di atas adalah prime implicant esensial. Pada kasus ini, hanya ada satu prime implicant nonesensial (11_) yang tersisa, tetapi semua mintermnya sudah terwakili oleh prime implicant esensial, sehingga tidak perlu dibuat tabel reduksi. Persamaan terreduksinya menjadi:
Menyederhanakan fungsi Jamak
Penyederhanaan Fungsi Boolean Contoh. f(x, y) = x’y + x’y’ + y’ disederhanakan menjadi f(x, y) = x’ + y’ Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara: 1. Secara aljabar 2. Menggunakan Peta Karnaugh 3. Menggunakan metode Quine Mc Cluskey (metode Tabulasi)
Penyederhanaan secara Aljabar 1. 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 Karnaugh Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
Peta Karnaugh c. Peta dengan empat peubah
Peta Karnaugh Contoh. 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
Contoh Sederhanakan 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
Contoh Andaikan suatu tabel kebenaran telah diterjemahkan ke dalam Peta Karnaugh. Sederhanakan fungsi Boolean 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
Contoh Minimisasi fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = w + xy’z
Teknik Minimasi Fungsi Boolean dengan Peta Karnough
Jika penyelesaian Contoh seperti di bawah ini:
sebelumnya
adalah
maka fungsi Boolean hasil penyederhanaan adalah f(w, x, y, z) = w + w’xy’z (jumlah literal = 5) yang ternyata masih belum sederhana dibandingkan f(w, x, y, z) = w + xy’z (jumlah literal = 4).
Teknik Minimasi Fungsi Boolean dengan Peta Karnough
Contoh. (Penggulungan/rolling) Sederhanakan fungsi Boolean yang bersesuaian dengan 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 bersesuaian dengan Peta Karnaugh di bawah ini.
Jawab: f(w, x, y, z) = xy’z + wxz + wyz → masih belum sederhana.
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 Karnough
Contoh Sederhanakan fungsi Boolean yang bersesuaian dengan 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
Contoh Minimisasi fungsi Boolean f(x, y, z) = x’z + x’y + xy’z + yz Jawab: x’z = x’z(y + y’) = x’yz + x’y’z x’y = x’y(z + z’) = x’yz + x’yz’ yz = yz(x + x’) = xyz + x’yz f(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 Karnough
Contoh (Contoh penggunaan Peta 5 peubah) Carilah fungsi sederhana dari f(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: Jadi f(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) sebelum diminimisasikan adalah seperti di bawah ini:
Teknik Minimasi Fungsi Boolean dengan Peta Karnough
Teknik Minimasi Fungsi Boolean dengan Peta Karnough
Contoh Berbagai sistem digital menggunakan kode binary coded decimal (BCD). Diberikan Tabel dibawah untuk konversi 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 Tabulasi
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 variabel secara berturut-turut, dan kemudian dihasilkan himpunan suku terreduksi yang dapat mencakup semua fungsi keluaran. Proses ini lebih mudah diimplementasikan pada komputer daripada metode peta, dan hasil sukusuku reduksinya dapat digunakan oleh lebih dari 1 fungsi.
Menyederhanakan fungsi tunggal
Tabel kebenaran pada Gambar 5.1 menggambarkan F yang merupakan fungsi 4 variabel A,B,C, dan D, yang menyertakan 3 don’t care. 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 1, sehingga minterm ini dijadikan grup lain.
Menyederhanakan fungsi tunggal
Gambar 5.1 Tabel kebenaran suatu fungsi dengan don’t care
Menyederhanakan fungsi tunggal
Grup berikutnya adalah minterm dengan dua nilai 1, dan ada 6 kemungkinan minterm yang mempunyai 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 minterm yang menghasilkan keluaran 1 dan mempunyai tiga nilai 1, yaitu 0111, 1011, dan 1110. Akhirnya grup yang beranggotakan empat nilai 1 ada satu minterm, dan merupakan grup terakhir.
Menyederhanakan fungsi tunggal
Untuk tabel kebenaran yang lebih besar, proses dapat berlanjut terus. Grup dikelompokkan lagi sehingga grup yang berbeda tepat 1 jumlah nilai 1-nya dapat digabung, seperti Gambar 5.2a berikut ini. Langkah berikutnya dalam proses reduksi adalah membentuk sebuah konsensus antara setiap pasang grup bertetangga untuk semua suku dengan beda nilai 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 tercakup oleh suku yang lain, sehingga dapat dieliminasi. Secara aljabar, teorema tersebut dapat dibuktikan sebagai berikut:
Menyederhanakan fungsi tunggal
Teorema konsensus dualitasnya:
juga
mempunyai
bentuk
Menyederhanakan fungsi tunggal
Ide dari penerapan konsensus pada reduksi tabulasi adalah untuk mengambil keuntungan dari sifat invers dari aljabar Boole, mirip seperti yang dipergunakan pada peta Karnaugh. Misalnya, 0000 dan 0001 berbeda nilainya pada variabel D, sehingga 000_ dimasukkan dalam daftar pada bagian atas tabel reduksi seperti terlihat pada Gambar 5.2b di atas. Tanda garis bawah menunjukkan posisi variabel yang dieliminasi, dalam contoh ini D.
Menyederhanakan fungsi tunggal
Minterm 0000 dan 0001 pada Gambar a diatas ditandai dengan cek (3) untuk menunjukkan bahwa entri ini sudah tercakup pada tabel reduksi. Setelah semua suku pada grup pertama disilangkan dengan semua suku pada grup kedua, kemudian beralih untuk membentuk konsensus antara grup kedua dan ketiga. Ada kemungkinan bahwa beberapa suku tidak dapat dikombinasi menjadi suku yang lebih kecil kare-na berbeda pada lebih dari 1 variabel.
Menyederhanakan fungsi tunggal
Contohnya, suku 0001 dan 0011 dapat dikombinasi menjadi suku lebih kecil 00_1 namun 0001 dan 0110 tidak dapat dikombinasi karena berbeda pada 3 variabel. Sekali suku sudah ditandai dengan 3, suku tersebut masih dapat dipergunakan untuk proses reduksi karena sifat idempotens. Tujuan dari langkah dalam proses ini adalah untuk menemukan semua kemungkinan suku terreduksi, sehingga kita dapat menemukan himpunan terkecil suku yang masuk dalam fungsi pada langkah berikutnya
Menyederhanakan fungsi tunggal
Proses berlanjut untuk grup-grup sisanya. Setiap suku yang tidak tercakup dalam pengelompokkan konsensus ditandai dengan asteris (*) untuk menunjukkan bahwa ini adalah suku prime implicant. Pada Gambar 5.2a diatas terlihat bahwa setelah reduksi pertama semua minterm sudah terpakai sehingga tidak ada prime implicant.
Menyederhanakan fungsi tunggal
Setelah reduksi pertama, kita dapat melanjutkan untuk iterasi berikutnya. Dua suku dapat dikombinasi jika keduanya hanya berbeda 1 variabel saja. Garis bawah harus pada posisi yang sama. Entri pertama pada Gambar 5.2b diatas mempunyai garis bawah pada kolom paling kanan, sehingga tidak ada entri pada grup kedua yang cocok.
Menyederhanakan fungsi tunggal
Dalam penyusunan tabel reduksi pada Gambar 5.2c, prime implicant dari tabel sebelumnya (Gambar 5.2b) tidak diikutkan. Proses berlanjut sampai hanya tersisa prime implicant. Pada contoh ini, proses berhenti setelah reduksi kedua dan menghasilkan 3 suku tersisa sebagai prime implicant seperti pada Gambar 5.2c. Setiap prime implicant dikumpulkan untuk menyusun 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 Gambar 5.2 b. Suku 00_1 dan 01_1 dikombinasi menjadi suku 0__1 seperti tertera pada 5.2c. Proses terus lengkap.
terlanjut
hingga
reduksi
kedua
Menyederhanakan fungsi tunggal
Untuk meminimalkan suku-suku yang digunakan, disusun tabel pilihan seperti pada Gambar dibawah ini. Setiap prime implicant dibuat 1 baris dalam table 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 dan mintermnya ditandai dengan *.
Menyederhanakan fungsi tunggal
Misalnya, prime implicant 000_ tandai pada kolom minterm 0001. Beberapa prime implicant mencakup beberapa minterm, 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 dengan yang menunjukkan bahwa prime implicant ini adalah esensial dan harus digunakan atau masuk dalam persamaan akhir.
Menyederhanakan fungsi tunggal
Menyederhanakan fungsi tunggal
Contoh prime implicant esensial adalah 011_ , 101_ , dan _1_1. Prime implicant esensial dapat mencakup lebih dari satu minterm. Untuk itu dibuatlah tabel pilihan terreduksi yang tidak menyertakan prime implicant esensial dan mintermnya, seperti pada Gambar di bawah. Tabel pilihan terreduksi dapat berisi prime implicant esensial 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 terreduksi membentuk himpunan pilihan, yang digunakan untuk mendapatkan 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 membentuk persamaan minimal untuk F, yang terdiri atas prime implicant esensial dan prime implicant pilihan pada himpunan 2 (Persamaan berikut).
Menyederhanakan fungsi tunggal
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 dalam himpunan pilihan pada Gambar di atas. Ekspresi logis ditulis untuk setiap kolom pada tabel pilihan terreduksi seperti berikut:
Menyederhanakan fungsi tunggal
Untuk mencari himpunan yang mencakup semua kolom, prime implicant dikelompokkan sehingga paling tidak setiap kolom ditandai sekali. Ini berarti bahwa relasi berikut harus terpenuhi, dengan G adalah adalah suku dalam tabel pilihan terreduksi:
Menyederhanakan fungsi tunggal
Dengan menerapkan sifat-sifat aljabar Boole didapat:
Setiap suku dalam persamaan ini menyatakan himpunan prime implicant yang mencakup suku-suku dalam tabel pilihan terreduksi. Suku terkecil (Y ) merupakan himpunan prime implicant (0 1) terkecil yang mencakup suku-suku tersisa. Hasil akhir yang didapat sama seperti cara sebelumnya:
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 sukusuku yang dapat digunakan bersama, dan kemudian memilih himpunan terkecil yang mencakup seluruh fungsi.
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 ini adalah:
Menyederhanakan fungsi Jamak
Irisan dibentuk dengan membuat semua kombinasi fungsi seperti berikut:
Menyederhanakan fungsi Jamak
Dengan menggunakan metode reduksi yang dijelaskan sebelumnya, dapat disusun prime implicant untuk masing-masing fungsi:
Menyederhanakan fungsi Jamak
Daftar prime implicant direduksi dengan mengeliminasi prime implicant 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 F1ataupun F2. Demikian seterusnya, sehingga didapat:
Menyederhanakan fungsi Jamak
Kemudian dapat disusun tabel pilihan keluaran jamak seperti pada Gambar dibawah. Baris berisi prime implicant dan kolom menunjukkan minterm yang harus tercantum pada masing-masing fungsi.
Menyederhanakan fungsi Jamak
Baris akan diisi dengan × jika prime implicant yang bersangkutan tidak dapat digunakan pada fungsi di kolom-kolom yang bersangkutan. Misalnya, prime implicant 000 digunakan oleh fungsi F0 tetapi tidak digunakan oleh fungsi F1 maupun F2, sehingga daerah perpotongan baris 000 dan kolom F1 dan F2 diisi ×.
Menyederhanakan fungsi Jamak
Bentuk minimal dari persamaan keluaran didapat dengan cara yang mirip dengan proses reduksi tabular. Kita mulai dengan prime implicant esensial.
Menyederhanakan fungsi Jamak
Misalnya, minterm m0 pada fungsi F0 hanya dicakup oleh prime implicant 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 nonesensial yang tersisa.
Menyederhanakan fungsi Jamak
Cara menentukan himpunan terkecil dari prime implicant yang mencakup semua fungsi adalah dengan cara yang sudah dijelaskan pada bagian sebelumnya. Tanda asterisk pada Gambar di atas adalah prime implicant esensial. Pada kasus ini, hanya ada satu prime implicant nonesensial (11_) yang tersisa, tetapi semua mintermnya sudah terwakili oleh prime implicant esensial, sehingga tidak perlu dibuat tabel reduksi. Persamaan terreduksinya menjadi:
Menyederhanakan fungsi Jamak
Related Documents c2h70
05 Penyederhanaan Fungsi Boole 6m193i
December 2019 13
Penyederhanaan Diagram Kotak y61h
April 2020 16
Makalah Aljabar Boole Arin 4z2h5k
December 2019 33
Problemas Boole 1 39605h
August 2020 0
Manual Boole Deusto Dte 2kh1b
June 2021 0