Penyederhanaan Fungsi Boolean
ini Merupakan sambungan dari Aljbar Boolean Dan Aplikasinya
2. Penyederhanaan Fungsi Boolean
Menyederhanakan fungsi Boolean artinya
mencari bentuk fungsi lain yang ekivalen tetapi dengan jumlah literal atau
operasi yang lebih sedikit. Penyederhanaan fungsi Boolean disebut juga
minimalisasi fungsi.
Contoh: f(x, y) = x’y + xy’
+ 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)
2.1 Penyederhanaan Secara Aljabar
Jumlah
literal di dalam sebuah fungsi Boolean dapat diminimumkan dengan trik
manipulasi aljabar. Metode yang tersedia adalah prosedur yang cut-and-try yang memanfaatkan postulat,
hukum-hukum dasar, dan metode manipulasi lain yang sudah dikenal.
Contoh:
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 + xz’
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
3. Penyederhanaan Rangkaian Logika
Teknik
minimisasi fungsi Boolean dengan peta Karnaugh mempunyai terapan yang sangat
penting dalam menyederhanakan rangkaian logika. Penyederhanaan rangkaian dapat
mengurangi jumlah gerbang logika yang digunakan., bahkan dapat mengurangi
jumlah kawat masukan.
4. Metode Quine-McCluskey
Metode peta
Karnaugh hanya cocok digunakan jika fungsi Boolean mempunyai jumlah peubah
paling banyak 6 buah. Jika jumlah peubah yang terlibat pada suatu fungsi
Boolean lebih dari 6 buah maka penggunaan peta Karnaugh menjadi semakin rumit,
sebab ukuran peta bertambah besar. Selain itu, metode peta Karnaugh lebih sulit
dijalankan di program komputer.
Langkah-langkah metode Quine-McCluckey untuk
menyederhanakan ekspresi Booleann dalam bentuk SOP adalah sebagai berikut :
- Nyatakan tiap minterm dalam n peubah menjadi string bit yang panjangnya n, yang dalam hal ini peubah komplemen dinyatakan dengan ‘0’, peubah yang bukan komplemen dengan ‘1’.
- Kelompokkan tiap minterm berdasarkan jumlah ‘1’ yang dimilikinya.
- Kombinasikan minterm dalam n peubah dengan kelompok lain yang jumlah ‘1’-nya berbeda satu, sehingga diperoleh bentuk prima (prime-implicant) yang terdiri dari n-1 peubah. Minterm yang dikombinasikan diberi tanda “√”.
- Kombinasikan minterm dalam n-1 peubah dengan kelompok lain yang jumlah ‘1’-nya berbeda satu, sehingga diperoleh bentuk prima yang terdiri dari n-2 peubah.
- Teruskan langkah 4 sampai diperoleh bentuk prima yang sesederhana mungkin.
- Ambil semua bentuk prima yang tidak bertanda “√”. Buatlah tabel baru yang memperlihatkan minterm dari ekspresi Boolean semula yang dicakup oleh bentuk prima tersebut (tandai dengan “x”). Setiap minterm harus dicakup oleh paling sedikit satu buah bentuk prima.
- Pilih bentuk prima yang memiliki jumlah literal paling sedikit namun mencakup sebanyak mungkin minterm dari ekspresi Boolean semula. Hal ini dapat dilakukan dengan cara berikut :
a. Tandai kolom-kolom yang mempunyai satu buah tanda
“x” dengan tanda “*”, lalu beri tanda “√” di sebelah kiri bentuk prima yang
berasosiasi dengan tanda “*” tersebut. Bentuk prima ini telah dipilih untuk
fungsi Boolean sederhana.
b. Untuk setiap bentuk prima yang telah ditandai
dengan “√”, beri tanda minterm yang dicakup oleh bentuk prima tersebut dengan
tanda “√” (di baris bawah setelah ‘*’).
c. Periksa apakah masih ada minterm yang belum
dicakup oleh bentuk prima terpilih. Jika ada, pilih dari bentuk prima yang
tersisa yang mencakup sebanyak mungkin mintermtersebut. Beri tanda “√” bentuk
prima yang dipilih itu serta minterm yang dicakupnya.
d. Ulangi langkah c sampai seluruh minterm sudah
dicakup oleh semua bentuk prima.
Metode
Quine-McCluskey biasanya digunakan untuk menyederhanakan fungsi Boolean yang
ekspresinya dalam bentuk SOP, namun metode ini dapat dimodifikasi sehingga juga
dapat digunakan untuk ekspresi dalam bentuk POS.
DAFTAR PUSTAKA
Munir,Rinaldi. Matematika Diskrit, Informatika Bandung,
2014
Comments
Post a Comment