Peta Karnaugh
10.1
PENDAHULUAN
Metode
Peta Karnaugh atau K-map merupakan metode grafis untuk menyederhanakan fungsi
bolean. Metode ini ditemukan Maurice Karnaugh pada tahun 1953. Peta karnaugh
adalah sebuah diagram yang terbentuk dari kotak-kotak tiap kotak
merepresentasikan minterm. Tiap kotak dikatakan bertetangga jika
minterm-minterm yang merepresentasikannya berbeda hanya 1 buah litaral.
Peta
Karnaugh dapat dibentuk dari fungsi boolean yang dispesifikasikan dengan
ekspresi boolean maupun fungsi yang dipresentasikan dengan tabel kebenaran.
10.2
Peta Karnaugh Dua Peubah
Dua
peubah dalam fungsi boolean adalah x dan y. Baris pada peta Karnaugh untuk
peubah x dan kolom untuk y. Baris pertama diidentifikasi nilai 0 (menyatakan
x’), sedangkan baris kedua dengan 1 (menyatakan x). Kolom pertama diidentifikasi
0 (menyetakan y’) sedangkan kolom kedua dengan 1 (menyatakan y).
|
|
m0 |
m1 |
x 0 |
x’y’ |
x’y |
|
|
m2 |
m3 |
1 |
xy’ |
xy |
10.3
Peta dengan tiga peubah
Fungsi Boolean dengan tiga peubah memiliki jumlah kotak 23 = 8.
Baris pada peta Karnaugh untuk peubah x dan kolom untuk peubah yz. Perhatikan
urutan mi-nya, urutan disusun sedemikian rupa sehingga setiap dua
kotak yang bertetangga hanya berbeda 1 bit.
|
|
|
|
|
|
|
|
yz 00 |
01 |
11 |
10 |
|
|
m0 |
m1 |
m3 |
m2 |
|
x
0 |
x’y’z’ |
x’y’z |
x’yz |
x’yz’ |
|
|
m4 |
m5 |
m7 |
m6 |
|
1 |
xy’z’ |
xy’z |
xyz |
xyz’ |
Contoh.
Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
|
x |
y |
Z |
f(x,
y, z) |
|
|
||
|
0 |
0 |
0 |
0 |
|
|
||
|
0 |
0 |
1 |
0 |
|
|
||
|
0 |
1 |
0 |
1 |
|
|
||
|
0 |
1 |
1 |
0 |
|
|
||
|
1 |
0 |
0 |
0 |
|
|
||
|
1 |
0 |
1 |
0 |
|
|
||
|
1 |
1 |
0 |
1 |
|
|
||
|
1 |
1 |
1 |
1 |
|
|
||
|
|
yz 00 |
01 |
11 |
10 |
|
||
|
x 0 |
0 |
0 |
0 |
1 |
|
||
|
1 |
0 |
0 |
1 |
1 |
|
||
|
|
|
|
|
|
|
||
10.4
Peta Karnaugh Empat Peubah
Empat peubah
dalam fungsi boolean adalah w, x, y, z. Jumlah kotak menjadi 16 buah.
Perhatikan urutan mi-nya. Baris pada peta karnaugh untuk peubah wx
dan kolom untuk peubah yz.
|
|
|
|
|
|
|
|
yz 00 |
01 |
11 |
10 |
|
|
m0 |
m1 |
m3 |
m2 |
wx 00 |
w’x’y’z’ |
w’x’y’z |
w’x’yz |
w’x’yz’ |
|
|
|
m4 |
m5 |
m7 |
m6 |
|
01 |
w’xy’z’ |
w’xy’z |
w’xyz |
w’xyz’ |
|
|
m12 |
m13 |
m15 |
m14 |
|
11 |
wxy’z’ |
wxy’z |
wxyz |
wxyz’ |
|
|
m8 |
m9 |
m11 |
m10 |
|
10 |
wx’y’z’ |
wx’y’z |
wx’yz |
wx’yz’ |
Contoh.
Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
|
w |
x |
y |
z |
f(w,
x, y, z) |
|
|
|
0 |
0 |
0 |
0 |
0 |
|
|
|
0 |
0 |
0 |
1 |
1 |
|
|
|
0 |
0 |
1 |
0 |
0 |
|
|
|
0 |
0 |
1 |
1 |
0 |
|
|
|
0 |
1 |
0 |
0 |
0 |
|
|
|
0 |
1 |
0 |
1 |
0 |
|
|
|
0 |
1 |
1 |
0 |
1 |
|
|
|
0 |
1 |
1 |
1 |
1 |
|
|
|
1 |
0 |
0 |
0 |
0 |
|
|
|
1 |
0 |
0 |
1 |
0 |
|
|
|
1 |
0 |
1 |
0 |
0 |
|
|
|
1 |
0 |
1 |
1 |
0 |
|
|
|
1 |
1 |
0 |
0 |
0 |
|
|
|
1 |
1 |
0 |
1 |
0 |
|
|
|
1 |
1 |
1 |
0 |
1 |
|
|
|
1 |
1 |
1 |
1 |
0 |
|
|
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
1 |
0 |
1 |
|
01 |
0 |
0 |
1 |
1 |
|
11 |
0 |
0 |
0 |
1 |
|
10 |
0 |
0 |
0 |
0 |
10.5
Teknik minimisasi fungsi boolean dengan peta karnaugh
1.
Pasangan: dua buah 1 yang bertetangga
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
01 |
0 |
0 |
0 |
0 |
|
11 |
0 |
0 |
1 |
1 |
|
10 |
0 |
0 |
0 |
0 |
Sebelum disederhanakan: f(w, x,
y, z) = wxyz + wxyz’
Hasil Penyederhanaan:
f(w, x, y, z)
= wxy
Bukti secara aljabar:
f(w,
x, y, z) = wxyz + wxyz’
= wxy(z + z’)
= wxy(1)
= wxy
2. Kuad: empat buah 1 yang bertetangga
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
01 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
|
10 |
0 |
0 |
0 |
0 |
Sebelum disederhanakan: f(w, x,
y, z) = wxy’z’ + wxy’z + wxyz
+ wxyz’
Hasil penyederhanaan:
f(w, x, y, z)
= wx
Bukti
secara aljabar:
f(w,
x, y, z) = wxy’ + wxy
= wx(z’ + z)
= wx(1)
= wx
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
01 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
|
10 |
0 |
0 |
0 |
0 |
Contoh lain:
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
01 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
0 |
|
10 |
1 |
1 |
0 |
0 |
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 buah1 yang bertetangga
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
01 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
|
10 |
1 |
1 |
1 |
1 |
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
Bukti secara aljabar:
f(w, x,
y, z) = wy’ + wy
= w(y’ + y)
= w
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
01 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
|
10 |
1 |
1 |
1 |
1 |
Contoh 5.11. Sederhanakan fungsi Boolean f(x,
y, z) = x’yz + xy’z’
+ xyz + xyz’.
Jawab:
Peta Karnaugh untuk fungsi
tersebut adalah:
|
|
yz 00 |
01 |
11 |
10 |
|
|
|
|
1 |
|
|
|
1 |
|
1 |
1 |
Hasil penyederhanaan: f(x, y,
z)
= yz + xz’
Contoh 5.12. Andaikan suatu tabel kebenaran telah
diterjemahkan ke dalam Peta Karnaugh. Sederhanakan fungsi Boolean yang
bersesuaian sesederhana mungkin.
|
|
yz 00 |
01 |
11 |
10 |
|
|
0 |
1 |
1 |
1 |
|
01 |
0 |
0 |
0 |
1 |
|
|
1 |
1 |
0 |
1 |
|
10 |
1 |
1 |
0 |
1 |
Jawab:
(lihat Peta Karnaugh) f(w,
x, y, z) = wy’ + yz’ + w’x’z
Contoh 5.13.
Minimisasi fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah
ini.
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
|
10 |
1 |
1 |
1 |
1 |
Jawab:
(lihat Peta Karnaugh) f(w,
x, y, z) = w + xy’z
Jika
penyelesaian Contoh 5.13 adalah seperti di bawah ini:
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
|
10 |
1 |
1 |
1 |
1 |
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).
Contoh 5.14. (Penggulungan/rolling) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta
Karnaugh di bawah ini.
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
|
11 |
1 |
0 |
0 |
1 |
|
10 |
0 |
0 |
0 |
0 |
Jawab: f(w, x,
y, z) = xy’z’ + xyz’
==> belum sederhana
Penyelesaian yang lebih minimal:
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
|
10 |
0 |
0 |
0 |
0 |
f(w, x, y, z) = xz’ ===>
lebih sederhana
Contoh 5.15: (Kelompok berlebihan) Sederhanakan
fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
0 |
|
10 |
0 |
0 |
1 |
0 |
Jawab:
f(w, x,
y, z) = xy’z + wxz
+ wyz
®
masih belum sederhana.
Penyelesaian
yang lebih minimal:
|
|
yz 00 |
01 |
11 |
10 |
|
wx 00 |
0 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
0 |
|
10 |
0 |
0 |
1 |
0 |
f(w, x, y, z) = xy’z + wyz ===> lebih sederhana
Contoh 5.16.
Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di
bawah ini.
|
|
cd 00 |
01 |
11 |
10 |
|
ab 00 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
|
|
1 |
1 |
1 |
1 |
|
10 |
0 |
1 |
1 |
1 |
Jawab:
(lihat Peta Karnaugh di atas) f(a,
b, c, d) = ab + ad
+ ac + bcd
Contoh 5.17. 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
Peta Karnaugh untuk fungsi
tersebut adalah:
|
|
yz 00 |
01 |
11 |
10 |
|
|
|
1 |
1 |
1 |
|
1 |
|
1 |
1 |
|
Hasil penyederhanaan:
f(x, y, z) = z
+ x’yz’
1
Peta
Karnaugh untuk lima peubah
000
001 011 010
110 111 101
100
|
00 |
m0 |
m1 |
m3 |
m2 |
m6 |
m7 |
m5 |
m4 |
|
01 |
m8 |
m9 |
m11 |
m10 |
m14 |
m15 |
m13 |
m12 |
|
11 |
m24 |
m25 |
m27 |
m26 |
m30 |
m31 |
m29 |
m28 |
|
10 |
m16 |
m17 |
m19 |
m18 |
m22 |
m23 |
m21 |
m20 |
|
|
|
|
|
|
|
|
|
|
Garis
pencerminan
Contoh 5.21. (Contoh penggunaan Peta 5 peubah)
Carilah fungsi sederhana dari f(v,
w, x, y, z) = S
(0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)
Jawab:
Peta Karnaugh dari fungsi
tersebut adalah:
|
|
|
xyz 000 |
001 |
011 |
010 |
110 |
111 |
101 |
100 |
|
|
|
vw 00 |
1 |
|
|
1 |
1 |
|
|
1 |
|
|
|
01 |
|
1 |
1 |
|
|
1 |
1 |
|
|
|
|
11 |
|
1 |
1 |
|
|
1 |
1 |
|
|
|
|
10 |
|
1 |
|
|
|
|
1 |
|
|
Jadi f(v, w,
x, y, z) = wz + v’w’z’
+ vy’z
Komentar
Posting Komentar