TUGAS
STRUKTUR DISKRIT LANJUT
“Penyederhanaan Fungsi Boolean dengan Metode Peta Karnaugh”


 







NAMA : ANNISA NURIKA
NIM : 09021181419127
IF. 3A (2014)


TEKNIK INFORMATIKA
FAKULTAS ILMU KOMPUTER
UNIVERSITAS SRIWIJAYA
2015





Penyederhanaan Fungsi Boolean

Metode Peta Karnaugh

Metode Peta Karnaugh (atau K-map) merupakan metode grafis untuk menyederhanakan fungsi Boolean. Metode ini ditemukan oleh Maurice Karnaugh pada tahun 1953. Peta Karnaugh adalah sebuah diagram / peta yang terbentuk dari kotak – kotak (berbentuk bujursangkar) yang bersisian. Tiap kotak merepresentasikan sebuah minterm. Tiap kotak dikatakan bertetangga jika minterm – minterm yang merepresentasikannya berbeda hanya 1 buah literal.
Peta Karnaugh dapat dibentuk dari fungsi Boolean yang dispesifikasikan dengan ekspresi Boolean maupun fungsi yang direpresentasikan dengan tabel kebenaran.

a. Peta Karnaugh dengan Dua Peubah

Misalkan dua peubah di dalam fungsi Boolean adalah x dan y. Baris pada peta Karnaugh untuk peubah x dan kolom untuk peubah y. Baris pertama diidentifikasi nilai 0 (menyatakan x’), sedangkan baris kedua dengan 1 (menyatakan x). Kolom pertama diidentifikasi nilai 0 (menyatakan y’), sedangkan kolom kedua dengan 1 (menyatakan y). Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian. Berikut terdapat tiga cara yang lazim digunakan sejumlah literatur dalam menggambarkan peta Karnaugh untuk dua peubah.

mo
m1
m2
m3
  
Gambar 1. Penyajian 1 - Peta Karnaugh dengan 2 peubah



Gambar 2. Penyajian 2 - Peta Karnaugh dengan 2 peubah


Gambar 3. Penyajian 3 - Peta Karnaugh dengan 2 peubah

Perhatikan bahwa dua kotak yang bertetangga pada peta Karnaugh hanya berbeda satu bit atau satu literal.

b. Peta Karnaugh dengan Tiga Peubah

Untuk fungsi Boolean dengan tiga peubah (misalkan x, y dan z), jumlah kotak di dalam peta Karnaugh meningkat menjadi 23 = 8. Baris pada peta Karnaugh untuk peubah x dan kolom untuk peubah yz. Baris pertama diidentifikasi nilai 0 (menyatakan x’), sedangkan baris kedua dengan 1 (menyatakan x). Kolom pertama diidentifikasi nilai 00 (menyatakan x’y’), kolom kedua diidentifikasi nilai 01 (menyatakan xy’), kolom ketiga diidentifikasi 11 (menyatakan xy). Perhatikanlah bahwa antara satu kolom dengan kolom berikutnya hanya berbeda satu bit. Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian.



Gambar 4. Peta Karnaugh dengan 3 peubah



c. Peta Karnaugh dengan Empat Peubah

Misalkan empat peubah di dalam fungsi Boolean adalah w, x, y dan z. Jumlah kotak di dalam peta Karnaugh meningkat menjadi 24 = 16. Baris pada peta Karnaugh untuk peubah wx dan kolom untuk peubah yz. Baris pertama diidentifikasi nilai 00 (menyatakan w’x’), baris kedua dengan 01 (menyatakan w’x), baris ketiga dengan 11 (menyatakan wx) dan baris keempat dengan 10 (menyatakan wx’). Kolom pertama diidentifikasi nilai 00 (menyatakan y’z’), kolom kedua diidentifikasi nilai 01 (menyatakan yz’), kolom ketiga diidentifikasi nilai 11 (menyatakan yz), sedangkan kolom keempat diidentifikasi dengan nilai 00 (menyatakan yz’). Setiap kotak merepresentasikan minterm dari kombinasi baris dan kolom yang bersesuaian.



Gambar 5. Peta Karnaugh dengan 4 peubah

Contoh 1: Diberikan tabel kebenaran, gambarkan Peta Karnaugh.




Contoh 2 : Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
 


Teknik Minimisasi Fungsi Boolean dengan Peta Karnaugh
1. Pasangan: dua buah 1 yang bertetangga


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

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

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’

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