PETA KARNAUGH
TUJUAN I.
2. 3. 4. 5.
Dengan suatu fungsi (yang ditentukan dengan lengkap atau tidak lengkap) dari tiga sampai enam variabel, letakkan pada peta Karnaugh. Fungsi tersebut mungkin diberikan dalam bentuk minterm, maksterm atau bentuk aljabar. Tentukan implikan prima mendasar dari suatu fungsi pada sebuah peta. Dapatkan bentuk jumlah hasil minimum atau hasil jumlah minimum suatu fungsi dari peta tersebut. Tentukan semua implikan prima suatu fungsi dari sebuah peta. Pahamilah hubungan antara operasi yang dilakukan dengan menggunakan peta dan operasi aljabar yang berkorespondensi.
PETUNJUKBELAJAR Dalam unit ini kita akan mempelajari peta Karnaugh* Diucapkan "kar-no" * Hampir setiap jenis penghitungan aljabar yang telah kita lakukan selama ini dapat dibantu dengan menggunakan peta ini, asalkan bilangan variabelnya kecil. I.
Pelajarilah Bagian 6.1 Bentuk Minimum dari Fungsi Switching. (a) Tentukan jumlah hasil minimum. (b) Tentukan hasil jumlah minimum. (c) Kerjakan Soal 6.3.
2.
Pelaj~rilah Bagian 6.2, Peta Karnaugh Variabel-2 dan 3 (a) Gambarlahtabel kebenaranyang ada pada peta. Kemudian simpulkan dua pasangan I pada peta itu dan tulislah bentuk F yang disederhanakan.
~
o 0 o I I 0 I
160
I
I
i
i
i
I I
0 I
~ 01
f :
1
+---1 1
ILLJ F
I
I
F=
Sekarang sederhanakanF secaraaljabar dan buktikanlah bahwajawaban anda benar. (b) F(a, b, c) digambarkansepertidi bawah ini. Carilah tabel kebenaranuntuk F. a bc'\... 0
o
o o .1.....F
a b
c
o o o o I I I I
0 I 0 I 0 I 0 I
0 0 I I 0 0 I I
I
F
r--
(c) Gambarlah fungsi berikut ini pada peta Karnaugh seperti di bawah ini :
F1(R. S, 1)= Lm(O,
I, 5, 6)
FiR, S. 1)= I1M(2, 3, 4, 7)
-
o 00
I
01 11 10
I
Mengapa kedua peta tersebut sarna ? (d) Gambarlah fungsi berikut ini pada peta yang ada : (x, y, z) = z'+ x'z + yz
161
Jangan membuat perluasan minterm atau tabel kebenaran sebelum memplotkan,
o 00 01 11 10
(e) Untuk peta variabel-3, kotak manakah yang berbatasan dengan kotak 2 ?
(f)
Teorema apa yang digunakan ketika dua term pada kotak yang berdekatan dikombinasikan ?
(g) Hukum aljabar Boolean apa yang membenarkan dengan menggunakan bilangan I yang ada pada peta dalam dua atau lebih kesimpulan ?
(h) Masing-masing solusi berikut ini tidak minimum.
f = 00' + OOc III
g = a' + 00
ICD
10
Dalam setiap kasus, ubahlah simpulan pada peta sehingga diperoleh solusi minimum.
162
(i) Kerjakan SoaI 6.5.
(j) Carilah dua kaIimatjumlah-hasil minimumuntuk fungsi G yang diplotkan sebagai berikut,
00
0
I
00
1
01
OCffl 01
I
II 10
II
I
10 G
3.
0
G=
'
1
G= G
Pelajarilah Bagian 6.3, Peta Kam~ugh 4-Variabel.
(a) Perhatikan lokasi minterm pada peta 3 dan 4 variabel (Gambar. 6-3(b) dan 6-10). Ingat susunan ini. Hal ini akan banyak menghemat waktu ketika and a memplotkan peta Kamaugh. Susunan di atas valid untuk susunan variabel yang ada. Jika kita memberi label pad a peta seperti yang tampak di bawah ini, isilah temp at minterm tersebut : CD
BC A A~ 00 I 01 I II I 10 o
--
-.
..
.-
I
I
163
(e) Ketikakita mengkombinasikandua bilangan 1yang berdekatanpada sebuah peta, hal ini berkorespondensi dengan penerapan teorem~ xy'+ xy = x untuk menghapus variabel di mana dua term tersebut berbeda. Jadi, pengikatan dua bilangan 1 yang ditunjukkan pada peta di bawah ini sarna dengan inengkombinasikan minterm yang berkorespondensi secara aljabar : ab cd 00
II
01
10
1
00
a'b'c'd+ ab'c'd
01 III
1 I 1 I
I
=b'c'd
(Term b'c'd dapat dibacasecara langsungdari peta karena ia terbentang dari kolom pertama sampai
I
kolom terakhir
101
I
I 1 I
I
(b') dan karena ia berada pada baris kedua (c'd).)
Ikatkan dua pasangan lain dari bilangan 1 yang berdekatan pada peta di atas dan sebutkan persamaan aljabar .dari pengikatan term ini. Sekarang bacalah ikatan tersebut secara langsung dari peta dan periksalah aIjabar anda.
(t) Ketika kita mengkombinasikanempat bilangan I yang berdekatan pada suatu peta (emp,atbilangan pada sebuah baris atau empat bilangan pada suatu kotak) persamaan ini mengaplikasikan xy + xy'= x ti~a kali : Cd
II
10
00
1
01
1 1
1
111 1
1
IIII 10
a'b'<;d + a'b'cd' + ab'cd + ab'cd' = a'b'c + ab'c = b'c
165
-
Ikatlah empat bilangan I yang lain pada peta di atas dan sebutkan persamaan aljabamya.
(g) Uptuk masing-masing peta berikut ini, ikatlah bilangan term minimum yang akan menutupi semua bilangan I. ab c,
vv
I
I I
v.
..
I
I
I
I
.v
ab c,
I
I
I
I
I
I I
-- -- -- .-
I
I
I
I
I I
(Untuk setiap bagian yang barus anda ikatkan dua kelompok bilangan I dan dua kelompok dua bilangan 1.) Tulislah kalimatjumlah basil minimum untuk I. dan 12 dari peta diatas. 1.= 12= (b) Mengapa tidak memungkinkanuntuk mengkombinasikanmin term 3 atau 6 bersama dibandingkan 2, 4, 8, dst. ?
(i) Perhatikan prosedur untuk menderivasikan basil jumlah minimum dari peta tersebut. Anda mungkin akan melakukan lebib sedikit kesalahanjika and, menuliskan f' sebagai jumlah basil terlebib dahulu dan kemudian mengkomplementasikannya seperti digambarkan oleb contob dalam Gambar 6-14. KeIjakan Soal 6.8 dan 6.13.
166
4.
Pelajarilah Bagian 6.4, Penentuan Kalimat Min~mumDengan Menggunakan Implikan Prima Mendasar. (a) Untuk peta pada Gambar 6-15, tulislah tiga implikan F selain yang telah tertera. Untuk peta yang sarna, apakah ac'd' adalah implikan prima dari F ? Mengapa atau mengapa tidak ?
(b) Untuk peta yang ada, adakah term yang mengkaitkan implikan prima? Mengapa atau mengapa tidak.? B CD""-.. 00
4
01
II
10
00 01 II 10
5.
Pelajarilah Gambar 6-18 dengan seksama dan kemudian jawablah pertanyaan berikut ini untuk peta yang diberikan di bawah ini :
--
CD I
10
-. 14
I
12
-1 8 1
11 13
..
1 7
1
1 6
110
167
(a) Berapa kali bilangan I berdekatan dengan mo ? (b) Apakah semua bilangan I ini ditutupi oleh implikan prima tunggal ? (c) Oari jawaban anda pada (b), dapatkah anda menentukan jika B'C' adalah esensial ?
(d) Berapa kali bilangan I yang berdekatan dengan m9 ? (e) Apakah semua bilangan I ini tertutupi oleh sebuah implikan pnma tunggal ? (f)
Oari jawaban anda pada (e), apakah B'C' esensial ?
(g) Berapa kali bilangan I berdekatan dengan m7 ? (h) Mengapa A'C esensial ?
(i) Carilah dua implikan prima mendasar yang lain dan sebutkan mintenn mana yang membuat mereka esensial.
6.
(a) Bagaimana anda menentukan jika suatu implikan prima itu esensial dengan menggunakan peta Kamaugh ?
(b) Untuk peta berikut ini, mengapa A'B' tidak esensial ? Mengapa BO' esensial ?
--
--
1
1
1
Apakah BC' esensial ? Mengapa ?
1
1
1
Apakah B'CO esensial ? Mengapa ?
1
Apakah A'D' esensial ? Mengapa ?
Carilah jumlah hasil minimum.
168
AB ... -CD I
I
1
--
1 1
1
(c)
Kerjakan Latihan Terprogram 6.1.
(d) Tulislah semua bilangan I dan X yang berdekatanden~an 10. AB CD vv I
'"
10
14
XI
I
II
IV
112
8
Xu
9
3.
17
liS
2
1 6
XI4
III 10
Mengapa A'C' merupakan implikan prima esensial ? Tulislah semua bilangan I dan X yang berdekatan dengan 115,
Berdasarkan pada daftar tersebut, mengapa anda tidak mendap~tkan implikan esensial yang meliputi 115? Apakah ini berarti bahwa tidak ada implikan prima esensial yang meliputi 115 ?
Implikan prima esensial yang mana yang meliputi III ? Dapatkah anda menemukan implikan prima esensial yang meliputi 112? Jelaskan. Carilah dua implikan prima yang meliputi
112,
Berilah dua kalimat minimum untuk F.
169
7.
(e)
Kerjakan Soal 6.9.
(f)
Jika anda mempunyai copy program Logik£lAid™ yang dapat dipakai, gunakan model tutorial peta Kamaugh untuk membantu anda mempelajari mencari solusi minimum dari peta Karnaugh. Program ini akan mengecek ketja anda pada setiap langkah untuk meyakinkan bahwa anda mengikatkan term-term dalam susunan yang benar. Program ini juga akan memeriksa jawaban akhir anda. Kerjakan Soal 6.10 dengan menggunakan tutor peta Karnaugh.
(a) Dalam Contoh 4, halaman 98, kita menderivasikan fungsi berikut ini :
Z
= L m(O,3,6,9) + L d(lO,II,12,13,14,15)
Plotkan Z pada peta yang ada dengan menggunakan X untuk mewakili term yang tidak dipedulikan. AB CD
--
--
--
-
I
I
(b) Tunjukkan bahwa jumlah hasil minimum adalah
Z
= A'B'C'D'+
B'CD + AD + BCD'
Manakah dari empat minterm yang tidak dipedulikan ditempatkan nilai 1 ketika membentuk solusi anda ?
170
(c) Tunjukkan bahwa hasil penjumlahan minimum untuk Z adalah Z = (b'+ C)(B'+ D')(A'+ D)(A + C + D')(B + C'+ D) Manakah term yang tidak dipedulikan pada Z yang ditempatkan nilai 1 ketika membentuk solusi anda ? (d) Kerjakan Soal 6.14 dan 6.15.
8.
Pelajarilah Bagian 6.5 Peta Kamaugh Variabel-5 dan 6. (a) Gambar di bawah ini menunjukkanpeta 5-variabel tiga dimensi. Plotkan 1 dan ikatkan pada peta dua dimensi yang berkorespondensi,dan berikan kalimat jumlah hasil minimum untuk fungsi tersebut.
F= (b) Pada peta 5-variabel (Gambar 6-21), berapakah lima minterm yang berdekatan dengan minterm 24 ? (c) Kerjakan semua contoh~ontoh dalam bagian ini dengan hati-hati dan yakinkan bahwa anda memahami semua langkah-Iangkahnya. 171
-
-
-
-
-
(d) Dua solusi minimum diberikan untuk Gambar 6-24. Ada solusi jumlah hasil minimum ketiga . Berapa itu ?
(e) Bacalah materi pada peta 6-variabel untuk mendapatkan ide dasar; namun keccikapan dalam menderivasikan solusi minimum dari peta 6-variabel tidak diperlukan untuk menyelesaikan uji kesiapan. (Catatan : Kecakapan dalam menyelesaikan peta 5-variabel diperlukan.)
(t) Kerjakan Latihan Terprogram 6.2.
(g)
DE
c 00
01
11
10
A
110
Carilah tiga bilangan 1 dan X yang berdekatan dengan' 118,Dapatkah semucmyaini diikatkan dengan ikatan tunggal ?
Carilah 1 dan X yang berdekatan dengan 124,Ikatlah implikan prima esensial yang meliputi 124,
Carilah 1 dan X yang berdekatan dengan 13'Ikatlah implikan prima esensial yang meliputi 13' Dapatkah anda mendapatkan implikan prima esensial yang meliputi 122? Jelaskan. 172
Carilah dan ikatlah dua lagi implikan prima esensial. Carilah tiga jalan untuk menutupi sisa 1 pada peta tersebut dan berilah solusi minimum yang berkorespondensi. (h) Jika anda mempunyai program LogicAid yang dapat dipakai, kerjakan Soal 6.28 dan 6.36 dengan menggunakan tutor peta Kamaugh. 9.
Pelajarilah Bagian 6.6 Kegunaan Lain dari Peta Kamaugh. Kembalilah ke Gambar 6-8 dan catatlah bahwa term konsensus ada jika ada dua implikan prima yang berdekatan tapi tidak nonoverlaping. Telitilah bagaimana prinsip ini diaplikasikan dalam Gambar 6-27.
10. Kerjakan Soal 6.25, 6.27, 6.29, 6.16, dan 6.17(a). Ketika menderivasikan solusi miriimumdari peta tersebut, selalu menuliskanterlebih dahulu implikant prima esensial. Jika tidak, seringkali anda tidak mendapatkan solusi minimum. Lagi pula, yakinlah bahwa anda dapat menemukan semua implikan prima dari peta tersebut (lihat Soal 6.25 (b).) II. Lihatlah kembali tujuan unit ini dan tempuhlah uji kesiapan.
PETAKARNAUGH Fungsi switching biasanya dapat disederhanakan dengan menggunakan teknik aljabar yang dideskripsikan pada Unit 3 dan 4. Namun demikian, dua masalah muncul ketika prosedur aljabar digunakan : I.
Prosedur tersebut sulit diterapkan dengan cara yang sistematik.
2.
Suiit untuk mengatakan kapan anda telah sampai pada solusi minimum.
Metode peta Kamaugh yang dipelajari dalam unit ini dan prosedur QuineMcCluskey yang dipelajari dalam Unit 7 mengatasi kesulitan-kesulitan tersebut dengan memberikan metode yang sistematik untuk menyederhanakan dan menghitung fungsi switching dengan tiga atau empat variabel, namun dapat diperluas ke fungsi lima, enam, atau lebih variabel. Biasanya, anda akan menemukan metode peta Karnaugh lebih cepat dan lebih mudah untuk diaplikasikan daripada metode penyederhanaan lain. 173
6.1 BENTUKMINIMUMFUNGSISWITCHING Ketika sebuah fungsi dinyatakan dengan menggunakan gerbang AND dan OR, biaya merealisasikan fungsi tersebut secara langsung dihubungkan dengan bilangan gerbang dan input gerbang yang digunakan. Teknik peta Kamaugh yang dikembangkan dalam u¥1itini secara langsung menuju biaya minimum jaringan dua-tingkat yang terdiri dari gerbang AND dan OR. Suatu kalimat yang terdiri dari jumlah hasil term yang berkorespondensi secara langsung ke jaringan dua tingkat yang terdiri dari kelompok gerbang AND yang memasuki gerbang OR tunggal (lihat Gambar 2-5, misalnya). Demikian pula kalimat hasil jumlah yang berkorespondensi dengan jaringan dua tingkat yang terdiri dari gerbang OR yang memasuki gerbang AND tunggal (lihat Gambar 2-6, misalnya). Oleh karenanya, untuk menemukan biaya jaringan gerbang AND-OR dua tingkat, kita harus mencari kalimat minimum dalam bentuk jumlah-hasil dan hasil-jumlah. Kalimatjumlah-hasil minimum untuk suatu fungsi ditentukan sebagai jumlah hasil term yang (a) mempunyai jurnlah term minimum, dan (b) semua kalimat yang mempunyai bilangan term minimum, mempunyai bilangan literal minimum. Jumlah hasil minimum berkoresponden secara langsung dengan jaringan gerbang dua tingkat minimum yang mempunyai (a) bilangan gerbang minimum dan (b) bilangan input gerbang minimum. Tidak seperti perluasan minterm untuk suatu fungsi, jumlah hasil minimum tidak harus unik; yaitu, fungsi yang ada mungkin mempunyai dua bentuk jumlah-hasil minimum, masing-masing dengan bilangan term yang sarna dan bilangan literal yang sarna. Dengan perluasan minterm, bentukjurnlah hasil minimumseringkalidapat dieproleh dengan prosedur berikut ini :
1.
Kombinasikan term-term dengan menggunakan XY' + XY = X. Kerjakan berulang-ulang untuk menghapus sebanyak mungkin literal. Term yang ada dapat digunakan lebih dari satu kali karena X + X = X.
2.
Hapuslah term redundan dengan menggunakan teorema konsensus atau teorema yang lain.
Sialnya, hasil dari prosedur di atas dapat tergantung pada susunan di mana term dikombinasikan atau dihilangkan sehingga kalimat akhir yang diperoleh tidak selalu minimum. 174
CONTOH : Carilah kalimat jumlah-hasil minimum ~ntuk
F(a, b, c) = L m(O, 1, 2, 5, 6, 7)
F
= a'Va'b'C
+ a'be' + ab'c + abc' + abc
= a'b' +
(6-1)
Tak satupun dari term pada kaliamt di atas dapat dihapuskan dengan konsensus. Namun demikian, mengkombinasikan term dengan eara yang berbeda membawa ke jumlah hasil minimum seeara langsung : F
= a'b'e' =
+ a'b'e + a'be' + ab'e + abc' + abe
'v/
a'b'
+
~be'
+
ae
(6-2)
Kalimat hasil-jumlah minimum untuk suatu fungsi didefinisikan sebagai hasil jumlah term yang (a) mempunyai bilangan faktor minimum, dan (b) dari semua kalimatnya yang mempunyai bilangan faktor yang sarna, mempunyai jumlah literal minimum. Tidak seperti perluasan maksterm, bentuk hasil jum1ah . minimum suatu fungsi tidak selalu unik. Dengan perluasan maksterm, hasil jumlah minimum seringkali dapat diperoleh dengan prosedur yang sarna dengan yang digunakan dalam kasus jumlah-hasil minimum,. keeuali bahwa teorema (X + Y)(X + Y') = X digunakanuntuk mengkombinasikanterm-term. CONTOH : (A+B' +C+D'XA+B' +C'+D'XA+B'+C' +DXA '+B'+C' +DXA+B+C'+DXA '+B+C'+D)
= (A
+ B'+ D')
(A + B'+C')
= (A + B'+ D')
(A + B'+ C')
(B'+C'+D)
(B+C'+D)
~ (C'+D)
dihilangkan dengan konsensus
= (A
+ B'+D')(C'+D)
(6-3)
175
--
6.2 PETAKARNAUGH 2 VARIABEL DAN3 VARIABEL Seperti halnya tabel kebenaran, peta Karnaugh suatu fungsi menentukan nilai fungsi untuk setiap kombinasi nilai variabel independen. Peta Karnaugh 2-variabel ditunjukkan seperti di bawah ini. Nilai satu variabel ditulis melintasi puncak peta, dan nilai variabel yang lain ditulis pada sisi sebelah kiri. Masingrnasing kotak pada peta berkorespondensi dengan sepasang nilai untuk A dan B seprrti terlihat di bawah ini.
A B"-
0 A=I.B=O
A = 0, B = I
A=I.B=I
Gambar 6-1 menunjukkan tabel kebenaran untuk fungsi F dan peta Karnaugh
'yang berkorespondensi. Perhatikan bahwa nilai F untuk A = B = a diplotkan pada kotak sebelah kiri atas dan isian peta yang lain diplotkan dengan cara yang sama alam Gambar 6-I(b). Setiap I pada peta berkorespondensi dengan minterm F. Kita dapat membaca minterm dari peta tersebut seperti halnya kita membacanya dari tabel kebenaran. Sebuah 1 pada kotak 00 dalam Gambar 6-1(c) menunjukkan bahwa A'B' adalah minterm dari F. Oemikian pula sebuah I pada kotak al menunjukkan bahwa A'B adalah suatu minterm. Minterm dalam kotak yang berdekatan pada peta tersebut dapat dikombinasikan karena mereka hanya berbeda satu variabel. Jadi, A'B' dan A'B berkombinasi untuk membentuk A', dan hal ini ditunjukkan dengan mengikat I yang berkorespondensi pada peta tersebut, lihat gambar 6-I(d).
176
BA
A
F 1 1 0 0
AB
o0 o 1 1 0 1 1
B~
B 1
01 1 I 0
1 I 0
_
A'S
1
0
I
0
I
A'B' +A'S =.4'.
F=A'B' +A'B
(a)
(b)
0 o
1
III
1
0
JI
0
F=A'
(c)
(d)
Gambar 6-2 menunjukkan tabel kebenaran 3-variabel dan peta Karnaugh yang berkorespondensi. Nilai satu variabel (A) ditulis melintasi puncak peta, dan nilai dua variabel yang lain (B, C) ditulis sepanjang sisi peta. Baris-baris yang diberi label secara berurutan 00, 0 I, 11, 10sehingga nilai dalam baris yang berdekatan hanya berbeda satu variabel. Untuk setiap kombinasi nilai variabel, nilai F dibaca dari tabel kebenaran dan diplotkan dalam kotak pada peta yang tepat. Misalnya, untuk kombinasi input ABC
dan BC
=
= 0 I.
= 00 I,
nilai F
= 0 diplotkan dalam kotak di mana A = 0 = 110, F = I diplotkan dalam kotak A
Untuk kombinasi ABC I, BC = 10.
Gambar 6-2 Tabel Kebenaran dan Peta Karnaugh untuk Fungsi 3-variabel ABC o o o o I I I I
0 0 I I 0 0 I I
F 0 I 0 I 0 I 0 I
(a)
o o I I I o I o
A BC ABC = DOl.F=O
---, 00
0
III
1
10
0 -::i-ASC
= liD, F = I
(b)
.177
-
-
Gambar 6-3 menunjukkanlokasi minterm pada peta 3-variabel.Minterm dalamkotak yangberdekatanpadapetatersebuthanyaberbedasatu variabeldan oleh karenanya dapat dikombinasikan dengan menggunakan teorema XY' + XY = X. Misalnya, minterm 011 (a~c) berdekatan dengan tiga minterm di mana ia dapat dikombinasikan- 001 (a'b'c), 01O(a'bc'),dan 111(abc).Lagi pula untuk kotak di mana secara fisik berdekatan,baris puncak dan paling bawah didefinisikan sebagai baris yang berdekatan karena minterm yang brekorespondensi dalam baris ini hanya berbeda satu variabel. Jadi 000 dan 010 itu berdekatan, dan demikian pula 100 dan 110.
Gambar 6-3 Tempat Minterm 3-variabel Peta Karnaugh A
BC
0
I
BC
00 000 100 01 091 101
100 is
0
I
00
0
4
011
I I 5
adjacent
III
0l1111
I I to 110
IOI
10
2 6 IICiliJ
(b) Notasi desimal (a) Notasi Binary
Dengan perluasan minterm suatu fungsi, ia dapat diplotkan pada sebuah peta dengan menempatkan I dalam kotak yang berkorespondensi dengan minterm fungsi tersebut dan 0 pada kotak yang lainnya ( 0 dapat dihilangkan jika dikehendaki). Gambar 6-4 menunjukkan plot dari F(a,b,c)
= ml
+ m3 + ms' Jika
F diberikan sebagai perluasan maksterm, peta tersebut diplotkan dengan menempatkan 0 dalam kotak yang berkorespondensi dengan maksterm dan kemudianmengisikotak-kotakyang lain dengan I. Jadi, F(a, b, c) = MoM2M4' M6M7 memberikan peta yang sarna seperti pada Gambar 6-4.
178
a be 00 01
° °0 °4 1I
15
II I 1 3
°7
10 ° 2 °6 Gambar 6-4 Peta Karnaugh dari F(a,b,e)
= m(1, 3. 5)=
M(O,2.4,6,7)
Gambar 6-5 menggambarkan bagaimana hasil term dapat diplotkan pada peta Karnaugh. Untuk memplotkan term b, 1 dimasukkan dalam empat kotak pada peta di mana b
= I.
Term be' adalah 1 bila b=1 dan e = 0, sehingga 1
dimasukkan dalam dua kotak dalam baris be = baris 10 . Term ae' adalah 1 bila a = I dan e = 0, sehingga 1 dimasukkan dalam kolom a = I pada baris di mana e = 0.
a
b 00
ocm 01
01.
--
. '
II rows btheseI in
=
< II10III I (1
II 11 '\JII b
10
I'
I /1 bc.
1
c=O in these rows
'I
ac,
Gambar 6-5 Peta Karnaugh untuk Term Hasil.
179
-
-
Jika suatu fungsi diberikan dalam bentuk aljabar, tidak perlu memperluasnya ke minterm sebelum memplotkannya pada peta. Jika kalimat aljabar dikonversikan pada bentuk jumlah hasil, maka masing-masing term hasH dapat diplotkan seeara langsung sebagai sebuah kelompok 1 pada peta tersebut. Misalnya,
f (a, b, c) = abc' + b'e + a' kita tidak akan memplotkan peta sebagai berikut: l.
Term abc' adalah I bila a=1 dan be=1O a 0 I sehingga kita letakkan 1 pada kotak yang be berkorespondensi dengan kolom a= 1 dan 00 1 baris' be= 10
2.
Term b'e sarna dengan 1 bila be=OI, 01 11 sehingga kita tempatkan 1 pada kedua kotak baris be= 01 11 I }
3.
Term a' adalah 1 jika a=O, sehingga kita menempatkan 1 pada semua bans kolom a=O } 10 I I
(Perhatikan : Karena sudah ada I pada kotak abe = 00 I, kita tidak perlu meletakkan I yang kedua di sini karena x + x = x.) Gambar 6-6 menggambarkan bagaimana kalimat yang disederhanakan untuk suatu fungsi dapat diderivasikan dengan menggunakan peta Karnaugh. Fungsi yang disederhanakan terlebih dahulu diplotkan pada peta Karnaugh dalam Gambar 6-6(a). Term dalam kotak yang berdekatan pada peta tersebut hanya berbeda satu variabel dan dapat dikombinasikan dengan menggunakan teorema XY' + Xy = X. Jadi a'b'e dan a'be dikombinasikan untuk membentuk a'e, dan a'b'e dan ab'e dikombinasikan untuk membentuk b'e seperti terlihat dalam Gambar 6-6(b). Suatu ikatan sekeliling kelompok minterm yang menunjukkan bahwa term ini telah dikombinasikan. Term yang diikatkan dapat dibaea seeara langsung dari peta. Jadi, untuk Gambar 6-6(b), term T( ada pada kolom a=O(a') dan merentang
baris di mana e=I, sehinggaT ( = a'e. Perhatikanbahwab telahdihapuskarena dua mintermpada TI berbedapada variabelb. Demikianpula term T2 ada pada baris be=OI sehingga T2 = b'e, dan a telah dihapus karena T2 merentang pada kolom a = 0 dan a=l. Jadi, bentukjumlah hasil minimum untuk F adalah a'e + b'e. 180
a
a be""-
0
bc' 00
0
QO
01
TI"
=abc+abc =ac
II
T, =-o'b'c+ob'c =b'c
01
,
II
10
10
F = tm( I. 3. 5) (a) Plot of mintenns
F=o'c+b'c (b) Simplified fonn of F
Gambar 6-6 Penyederhanaan
Fungsi 3-variabel
(a) Plot minterm (b) Bentuk yang disederhanakan dari F
Peta untuk komplemen F (Gambar 6-7) dibentuk dengan mengganti 0 dengan I dan 1 dengan 0 pada peta F. Untuk menyederhanakan F', perhatikan bahwa term pada baris paling atas dikombinasikan untuk membentuk b'e' dan term-term pada baris paling bawah berkombinasi untuk membentuk be'. Karena b'e' dan be' hanya berbeda satu variabel, baris atas dan baris bawah kemudian dapat dikombinasikan untuk membentuk kelompok yang terdiri dari empat 1, jadi menghilangkan dua variabel dan meninggalkan Tl=e', Bilangan 1 yang lainnya ~rkombinasi seperti terlihat untuk membentuk T2=ab, sehingga bentuk jumlah hasil minimum untuk F' adalah e' + ab.
181
TI =b'c' +bc' =c'
Gambar 6-7 Komplemen Peta pada Gambar 6-6(a)
Peta Kamaugh juga dapat menggambarkan teorema dasar dari aljabar Boolean, Gambar 6-8 menggambarkan teorema konsensus, XY + X'Z + YZ = XY + X'Z. Perhatikan bahwa term konsensus (YZ) adalah term redundan karena I-nya ditutupi oleh dua term lain.
x
X
YZ
0
00
. 01 If x:
1 11 A
01
yz (consensuslennl
II 11m 10
1
10
xy xy + x' z + yz
=xy
+ x' :
Gambar 6-8 Peta Karnaugh yang menggambarkan
Teorema Konsensus.
Jika sebuah fungsi mempunyai dua bentuk jumlah hasil minimum atau lebih, 182
semua bentuk ini dapat ditentukan dari sebuah peta. Gambar 6-9 menunjukkan dua solusi minimum untuk F = m(O, I, 2, 5, 6, 7).
F=a'b' +bc' +ac
F=a'c' +b'c+ab
Gambar 6-9 Fungsi dengan Dua Bentuk Minimum.
6.3 PETAKARNAUGH 4 VARIABEL Gambar 6-10 menunjukkan tempat minterm pada peta 4-variabel. Masingmasing minterm ditempatkan berdekatan dengan empat term di mana ia dapat dikombinasikan. Misalnya, m5(0101) dapat berkombinasi dengan m1(OOOl), mi01OO), m7(0111), atau m13(l101) karena ia hanya berbeda satu variabel dari masing-masing minterm lain. Definisi kotak yang berdekatan hams diperluas sehingga tidak hanya baris paling atas dan bawah saja seperti dalam peta 3variabel, namun juga kolom pertama dan kolom terakhir adalah berdekatan. Hal ini memerlukan penomoran kolom secara berurutan 00, 01, 11, 10, sehingga minterm ° dan 8, 1 dan 9, dan s~terusnya, adalah kotak berdekatan.
183
--
-.
..
I
1
1
1
.
1
1
1
I
1
)
1
CD
.-
1 1
1
Gambar 6-10 Tempat Minterm pada Peta Karnaugh 4-Variabel.
Sekarang kita akan memplot kalimat 4-variabel berikut ini pada peta kamaugh (Gambar 6-11) : (a, b, e, d)= aed + a'b + d'
Q'b d' Qed
Gambar 6-11 Plot dari acd + a'b + d'
=
Term pertama adalah I bila a = c d = 1, sehingga kita menempatkan dua kotak yang berada pada kolom a = 1 dan bans cd = 11. Term a'b adalah 1 bila
ab = 01, sehingga kita menempatkan empat bilangan I pada kolom ab = 01. Akhimya, d' adalah 1 bila d=O,sehingga kita menempatkan delapan 1 dalam dua baris di mana d = O. (1 rangkap tidak diplotkan karena I + I = I.) 184
. -..
-.--..----
-
Berikutnya kita akan menyederhanakan fungsi
1 dan 2
yang ada pada Gambar
6-12. Karena fungsi tersebut ditentukan dalam bentuk minten:n, kita dapat menentukan tempat I pada peta dengan merujuk pada Gambar 6-10. Setelah memplotkan peta. kemudian kita dapat mengkombinasikan kelompok I yang berdekatan. Minterm dapat ditentukan dalam kelompok 2, 4,atau 8 untuk menghapus variabel I, 2, atau 3, secara berurutan. Dalam Gambar 6-12(a) pasangan I dalam kolom ab =00 dan juga baris d=1 mewakili a'b'd. Kelompok empat I dalam kolom b I dan baris c=O mewakili be'.
=
Dalam Gambar 6-12(b), perhatikan bahwa empat sudut I merentangkan kolom b=O dan baris d=O, dan oleh karenanya dapat dikombinasikan untuk membentuk term b'd'. Kelompok delapan I menutupi baris-baris di mana c=I, dan oleh karenanya mewakili mewakili term c. Pasangan I yang diikatkan pada peta mewakili term a'bd karena term ini ada dalam kolom ab=Ol dan merentang sampai baris d= I.
Db
cd
00
""-
01
11
oo a'b'd
01
10
1 \.
(iJ
1
I
be'
1
-... .11
ab'cd'
10
I.
= Im(
I. 3. 4. 5. 10. 12. 13)
=be' +a'b'd+ab'cd'
h = Im(O. 2. 3. 5. 6. 7. 8. 10. II. 14. 15) =c+b'd.' +a'bd
(a)
(b)
Gambar 6-12 Penyederhanaan
Fungsi 4-Variab-eI,
Metode peta Karnaugh dengan mudah diperluas ke fungsi term yang tidak dipedulikan. Minterm yang diperlukan ditunjukkan dengan bilangan I paeJapeta. dan minterm yang tidak dipedulikan ditunjukkan dengan X. Ketika memilih term 185
--
--
untuk membentuk jumlah hasil minimum, semua bilangan 1 harns ditutup, namun X hanya digunakan jika mereka menyederhanakan kalimat yang dihasilkan. Oalam Gambar 6-13, term yang tidak dipedulikan saja yang digunakan dalam membentuk kalimat yang disederhanakan adalah 13.
cd
~b
--
-.
I
(1
1
1
1
I
f
.. ,
.-
X X
1)
X
= I,m(1,3,S,7,9) = d'd + c'd
+ I,d(6,12,13)
Gambar 6-13 Penyederhanaan Fungsi Yang Tidak Ditentukan Secara Lengkap.
Gunakan peta Kamaugh untuk mencari bentuk jumlah hasil minimum untuk fungsi yang telah digambarkan dalam Gambar 6-1, 6-6, dan 6-12. Hasil jumlah minimum dapat juga diperoleh dari peta peta. Karena ° dari adalah I-nya
.
., maka
jumlah hasil minimum untuk dapatditentukandenganmengikat° padapeta .komplemen dari jumlah hasil minimum untuk adalah jumlah hasil minimum untuk . Contoh berikut ini menggambarkan prosedur ini untuk f
= x'z'
.
+ wyz + w'y'z'+
x'y
Lebih dahulu, 1 pada diplotkan dalam Gambar 6-14. Kemudian dari 0, f' = y'z + wxz' + w'xy dan hasil jumlah minimum untuk adalah
= (y
186
+ z')(w'+ x'+ z)(w + x' + y')
Gambar 6-14.
6.4 PENENTUANKALIMATMINIMUMDENGANMENGGUNAKAN IMPLIKANPRIMAMENDASAR Setiap I tunggal atau kelompok I yang dapat dikombinasikan bersama pada sebuah peta fungsi F mewakili term hasil yang disebut implikan F.f 3Lihat Bagian 7.1 untuk definisi implikan.formal dan implik~ prima. f Beberapa implikan F ditunjukkan dalam Gambar 6-15. Implikan-term hasil disebut implikan prima jika ia tidak dapat dikombinasikan dengan term lain untuk menghapus sebuah variabel. Dalam Gambar 6-15, a'b'e, a'ed', dan ae' adalah implikan prima karena. mereka tidak dapat dikombinasikan dengan term lain untuk menghilangkan sebuab variabel. Di pihak lain, a'b'e'd' bukan merupakan implikan prima karena ia dapat dikombinasikan dengan a'b'ed'. abc' maupun ab'e' bukan merupakan implikan prima karena term ini berkombinasi bersama untuk membentuk ae'. ab cd a'b'c'd'-
l}
ac'
01
ab'c' abc'
a'bc'
Gambar
6- 15
II
l' F a'cd' 187
-
-
Semua implikan prima dari suatu fungsi dapat diperoleh dari peta Karnaugh. Suatu bilangan I tunggal pada sebuah peta mewakili implikan prima jika tidak berdekatan dengan bilangan 1 yang lain. Dua bilangan 1 yang berdekatan pada sebuah peta membentuk suatu implikan prima jika mereka tidak berada dalam kelompok yang berisi delapan bilangan I, dan seterusnya. K:alimatjumlah-hasil minimum untuk suatu fungsi terdisi"dari beberapa (tidak perlu semua) implikan prima dari suatu fungsi. Dengan kata lain, kali~at jumlahhasil yang berisi sebuah term yang bukan implikan prima tidak dapat menjadi minimum. Ini benar karena jika sebuah term non-prima ada, kalimatnya dapat disederhanakan dengan mengkombinasikan term non-prima dengan minterm tambahan. Untuk menemukanjumlah hasil minimum dari sebuah peta, kita hams mencari bilangan implikan prima minimum yang menutupi semua bilangan 1 pada peta. Fungsi yang diplotkan dalam Gambar 6-16 mempunyai enam implikan prima. Tiga dari implikan prima ini menutupi semua bilangan I pada peta, dan solusi minimum-nya adalah jumlah dari tiga implikan prima ini. Ikatan yang diberi bayang-bayang mewakili implikan prima yang bukan merupakan bagian dari solusi minimum.
ab cd"'" 00 a'c'd
01
11
10
1
00 , 01 11 R"lJ
Minimum solution: F = a' b'd + be' + DC All prime implicaots: a'b'd. be'. ac.a'c'd. ab. b'cd I
I
101
I
,....-:
Irri
(; ..
I
I\.ttJ
"-b'Cd
Gambar 6-16 Penentuan semua Implikan Prima
Ketika menuliskan semua implikan prima dari peta tersebut, perhatikan bahwa seringkali ada implikan prima yang tidak termasuk dalam jumlah hasil minimum. Meskipun semua bilangan 1 dalam suatu term telah ditutupi dengan implikan prima, term tersebut masih merupakan implikan prima asalkan tidak termasuk dalam kelompok yang lebih besar dari I. Misalnya, dalam Gambar 6-16, a'c'd meiupakan implikan prima karena tidak dapat dikombinasikan dengan bilangan 188
_.
d..
_..
.
1 lainnya untuk menghilangkan variabel yang lain. Namun, abd bukan merupakan implikan prima ia tidak dapat dikombinasikan dengan dua bilangan 1 lainnya untuk membentuk ab. Term -b'cd juga merupakan implikan primameskipun kedua bilangan I-nya telah ditutupi dengan implikan prima yang lain. Dalam proses menemukan implikan prima, term yang tidak dipedulikan diperlakukan sarna seperti bilangan I. Namun, suatu implikan prima yang keseluruhannya terdiri dari term yang tidak dipedulikan tidak pemah dapat menjadi bagian dari solusi minimum. Karena semua implikan prima suatu fungsi biasanya tidak diperlukan dalam membentuk jumlah hasil minimum, maka diperlukan prosedur yang sistematik untuk memilih implikan prima. Jika implikan prima dipilih dari peta dapa urutan yang salah, solusi non-minimum dapat menghasilkan. Misalnya, dalam Gambar 6-17, jika CD dipilihpertama kali, maka BD, B'C, dan AC diperlukan untuk menutupi bilangan ! lainnya, dan solusinya berisi empat term. Namun, jika implikan prima yang ditunjuk dalam Gambar 6-17(b) dipilih terlebih dahulu, semua bilangan 1 ditutup dan CD tidak diperlukan.
AB CD
--
10
00 r'IJI .)
1 ." \ 1 D
'"
..
1
1
1
1
1
1
1
.
'ms
011
C;r
-.
I !,'"I
--.... 1 II
-
--
I 1 .. !l
r--,
: +
1 1
\ 1 I 1 II I"U ,- \-.:.:
f=CD,+BD+B'C+AC
f=BD+B'C+AC (b)
(a) Gambar
6- J 7
Perhatikan bahwa beberapa minterm pada peta Gambar 6-17(a) dapat ditutup dengan satu implikan prima tunggal. Misalnya, m2 hanya ditutup dengan satu implikan prima, implikan prima tersebut dikatakan esensiaVmendasar dan hams meliputi jumlah hasil minimum. Jadi, B'C adalah merupakan implikan prima esensial karena m2 tidak ditutupi oleh implikan prima lainnya. Namun, CD tidak 189
---
--
-
,
- -
esensi<J.Ikarena masing-masing bilangan I pada CO dapat ditutup oleh implikan prima lainnya. Satu-satunya implikan prima yang menutupi ms adalah BO, sehingga BO esensial. Oemikian pula, AC esensial karena tidak ada implikan prima lainnya yang menutupi m14. Oalam eontoh ini, jika kita memilih semua implikan prima esensial, semua bilangan 1 pada peta tersebut ditutup dan implikan prima ,non-esensial CO tidak diperlukan. Seeara umum, untuk menemukan jumlah hasil minimum dari suatu peta, pertama kali kita harns mengikat semua implikan prima esensial. Salah satu eara untuk meneari implikan prima esensial pada sebuah peta adalah seeara sederhana melihat pada pada masing masing bilangan I pada peta yang belum tertutupi , dan memeriksa berapa implikan prima menutupi bilangan I tersebut. Jika hanya ada satu implikan prima yang menutupi bilangan 1, implikan prima tersebut adalah esensial. Jika ada dua atau lebih implikan prima yang menutupi yang menutupi bilangan 1, kita tidak dapat mengatakan apakah implikan prima ini esensial atau tidak tanpa pengeeekan selanjutnya. Untuk masalah sederhana, kita dapat menempatkan implikanprima esensial dengan eara ini "dengan pemeriksaan" dari masing-masing bilangan 1 pada peta tersebut. Misalnya, dalam Gambar 6-16, m4 hanya ditutupi dengan implikan prima be', dan m10hanya ditutupi dengan implikan prima ae. Semua bilangan 1 lainnya pada peta tersebut ditutupi oleh dua implikan prima; oleh karenanya, satu-satunya implikan prima esensial adalah be' dan ae. Untuk peta yang lebih rumit, terutama untuk peta dengan lima atau lebih variabel, kita memerlukan pendekatan yang lebih sistematik untuk menemukan implikan prima esensial. Ketika memeriksa sebuah minterm untuk melihat apakah ia hanya ditutupi oleh hanya satu implikan prima, kita harus melihat pada semua kotak yang berdekatan dengan minterm tersebut. Jika minterm yang ada dan semua bilangan 1 yang berdekatan dengannya ditutupi oleh sebuah term tunggal, kemudian term tersebut merupakan implikan prima esensial. Pernyataan ini dibuktikan dalam Lampiran C.l. o Jika semua bilangan 1 yang berdekatan dengan minterm yang ada tidak ditutupi olah sebuah term tunggal, maka ada dua atau lebih implikan prima yang menutupi minterm tersebut dan kita tidak dapat mengatakan apakah implikan prima ini esensial atau tidak tanpa pengeeekan lebih lanjut. Gambar 6-18 menggambarkan prinsip ini. Bilangan 1 yang berdekatan untuk minterm mo(lo) adalah II' 12, dan 14' Karena tidak ada term tunggal yang menutupi empat bilangan I ini, maka tidak ada implikan prima esensial yang muneul. Bilangan I yang berdekatan untuk II adalah 10dan Is, sehingga term yang menutupi tiga bilangan I (A'C') 190
adalah implikan prima esensial. Karena hanya I yang berdekatan dengan 12 adalah 10, maka A'B'D' juga merupakan term esensial. Karena bilangan I yang berdekatan dengan 17 (15 dan 115)tidak ditutupi dengan sebuah term tunggal, baik A'BD maupun BCD bukan esensial pada poin ini. Namun, Karena satusatunya bilangan I yang berdekatan dengan III adalah 115'maka ACD adalah esensial. Untuk menyelesaikan solusi minimum, salah satu implikan non-esensial diperlukan. A'BD maupun BCD dapat dipilih. Solusi finalnya adalah
ACD
6
14
10
Gambar 6-J8 Perhatikan: Bilangan I yang diberi bayang-bayang berwama merah ditutupi oleh hanya satu implikan prima. Kesemua bilangan 1 lainnya ditutupi oleh paling tidak dua implikan prima. Jika sebuah minterm yang tidak dipedulikan ada pada peta etrsebut, kita tidak hams memeriksanya untuk melihat apakah ia ditutupi oleh satu atau lebih implikan prima. Namun demikian, ketika memeriksa sebuah bilangan I untuk yang berdekatan dengan I, kita perlakukan term yang tidak dipedulikan yang berdekatan seolah-olah mereka adalah 1 karena term yang tidak dipedulikan dapat dikombinasikan dengan I dalam proses pembentukan implikan prima. Prosedur berikut ini kemudian dapat digunakan untuk mendapatkanjumlah hasil minimum dari peta Kamaugh : I.
Pilihlah sebuah minterm (a I) yang' belum ditutupi.
191
------
2.
Carilah I dan X yang berdekatan dengan minterm tersebut. (Periksalah kotak yang berdekatan dengan n pada peta n-variabel.)
3.
Jika sebuah term tunggal menutupi minterm tersebut dan semua bilangan 1 dan X yang berdekatan, maka term tersebut merupakan implikan prima esensial, maka pilihlah term tersebut. (Perhatikan bahwa term yang tidak dipedulikan diperlakukan seperti 1 dalam langkah 2 dan 3 namun bukan pada langkah 1.)
4
UIangiiah langkah-IangkahI, 2, dan ~salmapi semua implikan prima esensial terpilih.
5.
Carilah rangkaian implikan prima minimum yang menutupi bilangan llainnya pada peta tersebut. (Jika ada lebih dari satu rangkaian semacam itu, pilihlah satu rangkaian ~engan jumlah literal minimum.)
Gambar 6-19 memberikan "flowchart" untuk prosedur ini.
192
Pilihlah sebuah bilangan 1 yang belum ditutup.
Carilah semua bilangan 1 dan X yang berdekatan.
Term tersebut adalah implikan prima esensial. lkatlah.
TIDAK
VA Carilah rangkaian impIikan prima minim"" yang menUlU: bilangan satu IaJmya pada
{
Perhatikan: semua impllkan prima esenslal telah ditentukan pada poin. Ini.
petaI_but.
Gambar 6-19. Flowchart untuk menentukan Jumlah Hasil Minimum Dengan Menggunakan Peta Kamaugh
193
Contoh berikut ini (Gambar 6-20) menggambarkan prosedur di atas. Dimulai dengan 14, kita lihat bahwa 1 dan X yang berdekatan (Xo' 15' dan 16) tidak ditutupi oleh sebuah term tunggal, sehingga tidak ada implikan prima esensial yang muncul. Namun demikian, 16 dan bilangan 1 dan X yang berdekatan (14 dan X7) d~tutup oleh A'B, sehingga A'B merupakan implikan prima esensial. Berikutnya, dengan melihat pada 113,kita lihat bahwa I dan X yang berdekatan (15' 19, Idan XIS) tidak ditutupi oleh term tunggal, sehingga tidak ada implikan prima esensial yang muncul. Demikian pula, pemeriksaan term-term yang berdekatan dengan Is dan 19menunjukkan tidak adanya implikan prima esensial. Namun demikian, 110hanya mempunyai Is yang berdekatan dengannya, sehingga AB'D' adalah implikan prima esensial karena ia menutupi 110dan Is' Setelah terlebih dahulu memilih implikan prima esensial, sekarang kita memilih AC'D karena ia menutupi 1 yang lain pada peta tersebut.
Gambar 6-20 Keterangan : Bilangan I yang diberi bayangan ditutupi oleh hanya satu implikan prima.
Pemilihan susunan yang bijaksana di mana minterm yang terpilih (langkah I) mengurangi jumlah kerja yang dibutuhkan dalam mengaplikasikan prosedur di atas. Seperti halnya yang akan kita saksikan pada bagian berikutnya, prosedur ini terutama bermanfaat untuk memperoleh solusi minimum untuk soal 5 dan 6-variabel.
194
6.5 PETAKARNAUGH 5 DAN6 VARIABEL Suatu peta 5-variabel dapat disusun dalam tiga dimensi dengan menempatkan peta 4-variabel pada puncak variabel yang kedua. Term pada lapisan paling bawah diberi nomor 0 sampai 15 dan term yang berkorespondensi pada lapisan yang paling atas diberi nomor 16 sampai 31, sehingga term-term pada lapisan yang terbawah berisi A' dan term yang ada pada lapisan yang paling atas berisi A. Untuk mewakili peta dalam dua dimensi, kita akan membagi masing-masing kotak dalam peta 4-variabel dengan garis diagonal dan meletakkan term-term pada lapisan terbawah berada di bawah garis dan term-term pada lapisan di atas berada di atas garis diagonal tersebut (Gambar 6-21). Suatu representasi pilihan harus membuat dua lapisan sisi demi sisi seperti dalam Gambar 6-29, tapi kebanyakan orang yang mencari kedekatan lebih sulit untuk melihat kapan bentuk ini digunakan. Term-term pada lapisan atas dan bawah berkombinasi seperti. term-term pada peta 4-variabel. Lagi pula, dua term pada kotak yang sarna yang dipisahkan dengan garis diagonal hanya berbeda satu variabel dan dapat dikombinasikan. Namun demikian, beberapa term yang secara fisik muncul berdekatan tidak dapat dikombinasikan. Misalnya term 0 dan 20 tidak berdekatan karena mereka muncul pada kolom yang berbeda dan pada lapisan yang berbeda. Masing-masing term dapat berdekatan tepat dengan lima term lain, empat term pada lapisan yang sarna dan satu term pada lapisan yang lain (Gambar 6-22). Ketika mengecek kedekatan, masing-masing term hams dicek pada lima kotak yang mungkin berdekatan.
195
Term-Ierm ini lidak berlcombinasi karena mereka berada pada lapisan yang berbeda dan kolom yang berbeda (mereka berbeda pada 2 variabel).
8 lerm ini' berkombinasi unluk memberikan BO' (B dari kolom lerakhir dan 0' dari dua baris di alas; A dihapus karena 4 lerm berada pada lapisan alas dan 4 lerm pada lapisan bawah.)
A 110
4 lerm ini (2lerm dari lapisan alas dan 2 lerm dari lapisan bawah) berkombinasi unluk memberikan COE (C dari dua kolom di lengah dan DE dari baris lersebul).
2 lerm pada lapisan alas berkombina.~i unluk memberikan
Gambar 6-21 Peta Karnaugh 5-variabel
DE
c 00
01
A 110
Gambar 6-22
196
II
10
AB'OE.
Dua contoh minimalisasi Gambar 6-23 adalah peta dari F(A, B. C, D. E)
5-variabel
dengan menggunakan
= L m(O,4,5, 13,15,20,21,22,23,24,26,28,30,31)
BC DE'
peta.
to
11
Shaded I's are used to select essential prime implicants.
Gambar 6-23
Implikan prima PI dipilih pertama kali karena semua bilangan 1 yang berdekatan dengan minterm ° ditutup olah PI' Implikan prima P2 selanjutnya dipilih karena semua bilangan I yang berdekatan dengan minterm 24 ditutup oleh P2. Semua bilangan I yang lain pada peta tersebut dapat ditutup paling tidak oleh dua implikan prima yang berbeda, sehingga kita meneruskan dengan percobaan. Setelah beberapa percobaan, akan menjadi jelas bahwa bilangan 1 yang tersisa dapat ditutup oleh tiga implikan prima. Jika kita memilih implikan prima P3 dan P4 lebih lanjut, dua bilangan I yang ada dapat ditutup oleh dua kelompok bilangan 4 yang berbeda. Solusi minimum yang dihasilkan adalah
F
= A'B'D' PI
+ ABE' + ACD + A'BCE +
{
AB'C atau AB'CD'
}
197
Gambar 6-24 adalah peta dari F(A, B. C. D, E)
=L m(O, I, 3, 8, 9,
14, 15, 16, 17, 19, 25, 27, 31)
Semua bilangan 1 yang berdekatan dengan ml6 ditutup dengan PI' sehingga memilih PI terlebihdahulu. Semua bilangan 1 yang berdekatan dengan m3 ditutup dengan P2 ' sehingga P2 dipilih berikutnya. Semua bilangan I yang berdekatan dengan mg ditutup dengan P3, sehingga P3 dipilih. Karena ml4 hanya berdekatan dengan m15,P4juga esensial. Tidak ada implikan prima yang lebih esensial, dan bilangan 1 yang lainnya dapat ditutup dengan dua term P5 dan (1-9-17-25) atau (17-19-25-27). Solusi akhimya adalah C'D'E
F
= B'C'D'+
B'C'E + A'C'D'+
A'BCD + ABDE +
{ PI
P2
P3
P4
atau AC'E
}
P5
Peta 6-variabel dapat disusun dalam tiga dimensi dengan membandingkan empat peta 4-variabel. Plotkan nilai AB pada lapisan dan nilai-nilai CD dan EF pada baris dan kolom pada setiap lapisan. Tempatkan AB =00 ke lapisan bawah, AB
= 01 pada
lapisan kedua, AB
= 11 ke lapisan
ketiga, dan AB
= 10 ke lapisan
paling atas. Kemudian term lapisan yang berdekatan hanya berbeda pada satu variabel. (Dalam hal ini lapisan atas dan bawah berdekatan.) Peta 6-variabel dapat ditulis dalam dua dimensi dengan membagi masing-masing kotak dari peta 4-variabel menjadi empat bagian seperti terlihat di bawah. Minterm 0-15 diplotkan dalam lapisan bawah (Iapisan 00), 16-31 pada lapisan berikutnya (01), 32-47 pada lapisan atas (10), dan 48-63 pada lapisan ketiga (11).
198
Gambar 6-24
Lapisan "Ketiga"
~
Lapisan "AlaS"
'>~"'-
Lapisan"Kedua"
~
Lapisan "Bawah"
199
AS I~
I~I
Gambar 6-25 Peta 6-Variabel
Gambar 6-25 menunjukkan contoh 6-variabel. Perhatikan bahwa term-term dalam kolom (atau baris) berdekatan hanya jika mereka berada pada lapisan yang berdekatan. Term 1 pada lapisan kedua adalah A'BC'D'E'. Term 2 merentang pacta lapisan kedua dan ketiga dan term tersebut adalah BCE'F'. Term 3 pada lapisan ketiga adalah ABEF. Term 4 merentang ke semua empat lapisan , menghapuskan A dan B. Term 4 adalah D'EF'. Dua bilangan 1 yang lainnya pada peta tersebut tidak mengkombinasikan term lainnya. Mereka tidak berdekatan dengan term yang terdekat karena term-term ini berada pada lapisan yang berbeda.
6.6 KEGUNAAN LAINDARIPETAKARNAUGH Banyak operasi yang dapat dilakukan dengan menggunakan tabel kebenaran atau secara aljabar dapat dilakukan dengan menggunakan peta Karnaugh. Jika kita memplotkan sebuah kalimat untuk F pada sebuah peta, kita dapat membaca perluasan minterm dan makstermnya untuk F dan untuk F'. Dari peta gambar 6-14, perluasan minterm untuk f adalah 200
f
=L
m(O, 2, 3, 4,8,10,
II, 15)
dan karena rnasing-rnasing 0 OOrkorespondensi dengan rnaksterm, rnaka perluasan rninterm f adalah
f = II MO, 5, 6, 7,9, 12, 13, 14) Kita dapat rnernbuktikanbahwa dua fungsi adalah sarna dengan rnemplotkan rnereka pada peta dan dengan rnenunjukkan bahwa rnereka rnernpunyai peta Karnaugh yang sarna. Kita dapat rnelakukan operasi AND (atau operasi OR) pada dua fungsi dengan rneng-AND-kan (atau (OR) 1 dan 0 yang rnuncul dalarn posisi yang OOrkorespondensipada peta rnereka. Prosedur ini valid karena ia ekuivalen dengan rnelakukan operasi yang sarna pada taOOIkebenaran untuk fungsi tersebut. Suatu peta Karnaugh dapat rnembantu rnemfaktorkan sebuiah kalirnat. Perneriksaan peta rnengungkapkan term-term yang rnempunyai satu atau lebih variabel secara urnurn. Untuk peta berikut ini, dua term pada kolom pertama rnernpunyai B'B' secara urnum; dua term pada sudut kanan bawah mempunyai AC secara urnurn. 01
11
10
1 1O~ Gambar 6-26
Ketika rnenyederhanakan sebuah fungsi secara aljabar, peta Karnaugh dapat digunakan sebagai panduan dalam rnenentukan langkah apa yang diambil. Misalnya, pertirnbangkan fungsi F = ABCD + B'CDE + A 'B' + BCE' 201
Dari peta tersebut (Gambar 6-27), kita lihat bahwa untuk mendapatkan solusi minimum kita harns menambah term ACDE. Kita dapat melakukan hal ini dengan menggunakan teorema konsensus : F
= ABCD T
+ B'CDE + A'B' + BCE~+ ACDE T /'
Tambahkan term ini
Kemudian dua term ini dapat dihilangkan.
Gambar 6-27
Seperti yang dapat kita lihat dari peta tersebut, kaliamt di atas sekarang berisi dua term redundan, ABCD dan B' cde. Term ini dapat dih,ilangkandengan menggunakan teorema konsensus yang memberikan solusi minimum F = A'B' + BCE' + ACDE
202
.
.
.-
...
..--...
6.7 BENTUKLAINDARIPETAKARNAUGH Selain memberi label sisi-sisi peta Kamaugh dengan 0 dan 1, kebanyakan orang lebih suka menggunakan lebel seperti yang terlihat pada: Gambar 6-28. Untuk setengah dari peta yang diberi label A, A = 1; dan untuk setengah yang lain , A = o. variabellainnyamempunyaipenerjemahanyangsarna.Sebuahpeta yang diberi label dengan cara seperti ini kadang-kadang ditunjuk sebagai diagram Veitch. II'.khususnya bermanfaat untuk memplotkan fungsi yang diberikan dalam bentuk aljabar lebih dari bentuk minterm dan maksterm. Namun demikian, ketika menggunakan peta Kamaugh untuk memecahkan soal jaringan berurutan (Unit 12 sampai 17), pemakaian 0 dan 1 untuk memberi label peta tersebut lebih enak.
A
B Gambar 6-28 Diagram Veitch
Dua bentuk aJtematif untuk peta 5-variabel dipakai di sini. Satu bentuk secara sederhana terdiri dari dua peta 4-variabel bersisi-sisian seperti dalam Gambar 6-29(a). Suatu modifikasi dari bentuk ini ada:tah menggunakan peta "bayangan cermin" seperti pada Gambar 6-29(b). Dalam peta ini, kolom pertama dan ke-delapan "berdekatan", seperti kolom kedua dan ke tujuh, kolom ketiga dan ke-enam, dan kolom ke-empat dan ke-lima. Fungsi yang sama diplotkan pada kedua peta ini. Demikian pula, peta 6-variabel dapat representasikan sebagai peta 4-variabel yang disusun da:tam kotak.
203
A
/'-------//"
01, II
10
nr
BC
00 01
. 8
....."
II \ \ 10
I1R
tE 10I
I
I
IfI\l
10
I
I
A =0
I
I
I
D{
A= I
-,..-
-,..C
C
(al
(b)
F=D'E' +B'C'D' + BCE+A'BC'E' + ACDE
Gambar 6-29 Bentuk lain dari Peta Karnaugh 5- Variabel.
LATiHANTERPROGRAM 6.1 Tutuplah jawaban dari latihan ini dengan selembar kertas dan geserlah ke bawah ketika anda memeriksa jawaban anda. Tulislah jawaban andcipada tempat yang diberikansebelum melihat jawaban yang benar. 50al : Tentukan jumlah hasil minimum dan hasil jumlah minimum untuk f
= b'e'd'
+ bed + aed'+ a'b'e + a'be'd
Terlebih dahulu, plotkan peta tersebut untuk f.
I
I
204
Jawaban :
I
1
1 1
.
.
1
I
1
1
1 1
1
(a) Minterm yang berdekatan dengan mo pada peta di atas adalah dan (b) Carilah implikan prima esensial yang berisi mo dan ikatlah. (c) Minterm dan
yang berdekatan
dengan
mo adalah
(d) Adakah implikan prima esensial yang berisi ml ? (e) Carilah implikan prima esensial dan ikatlah.
Jawaban (a) m2 dan mg
(b)
(c) m2 dan m7
(e)
(d) Tidak
205
-
Ikatlah bilangan 1 yang lainnya dengan menggunakan minImum.
bilangan pengikat
Dua bentuk jumlah hasil minimum yang memungkinkan untuk f adalah
dan
f=
f=
Jawab :
a' cd
f = b'd' + a'bd + abc +
atau a'b'c J I
Selanjutnya, ktia akan mencari hasil jumlah minimum untuk f. Dimulai dengan memplotkan peta tersebut untuk f'. Ikatlah semua implikan prima esensial dari f' dan tunjukkan minterm mana yang membuat masing-masing minterm tersebut esen sial.
)
I ) f' 206
Jawaban :
Esensial karena m I
Esensial karena mil
Esensial karena m6
Ikatlah bilangan I lainnya dan tulislah jumlah hasil minimum untuk f.
r= Sehingga jumlah hasil minimum untuk f adalah
f=
Jawaban akhir : r =b'c'd + a'bd' + ab'd + abc' f =(b + c + d')(a + b' + d)(a'+ b + d')(a'+ b'+ c)
207
-
-
LATiHANTERPROGRAM 6.2 Soal : Tentukan kalimat jumlah hasil minimum untuk I(a,b,c,d,e)
= (a'+
c + d)(a'+ b + e)(a+ c'+ e')(c +d+e')
(b + c +d'+e)(a'+ b'+ c +. e')
Langkah pertama dalam solusi ini adalah memplotkan peta untuk f. Karena f diberikan dalam bentuk jumlah hasil, maka lebih mudah terlebih dahulu memplotkan untuk f' dan kemudian mengkomplemenkan peta tersebut. Tulislah f' sebagai jumlah hasil : f'=
Sekarang plotkanlah peta untuk f'. (Perhatikan bahwa ada tiga term pada "lapisan atas", satu term pada "lapisan bawah" dan dua term yang terbentang di antara dua lapisan.) Selanjutnya konversikan peta anda untuk f' ke peta untuk f.
c de
00
11
01
a 1/0
f'
208
f
10
Jawaban :
f
f'
Langkah selanjutnya adalah menentukan implikan prima esensial f. (a) Mengapa a'd'e'
merupakan implikan prima esensial ?
(b) Minterm manakah yang berdekatan dengan m]? ml9 ?
yang berdekatan dengan
(c) Adakah implikan prima esensial yang menutupi m] dan m19? (d) Adakah implikan prima esensial yang menu~upi m21 ? (e) Ikatlah implikan prima esensial yang telah anda temukan. Kemudian carilah dua implikan prima esensial lagi dan ikatlah mereka.
209
Jawaban : (a) Ia menutupi mo dan kedua minterm yang berdekatan. (b) ml9 dan mil; m3 dan mZ3 (c) Tidak (d) Ya (e)
(a) Mengapa tidak ada implikan prima esensial yang menutupi mil ? (b) Mengapa tidak ada implikan prima esensial yang menutupi mZ8 ?
Karena tidak ada implikan prima yang lebih esensial, maka ikatlah jumlah term minimum yang menutupi bilangan 1 yang lain .
Jawaban: (a) Semua yang dekat dengan I pada mil (m3, mw) tidak dapat ditutup dengan satu pengelompokan. (b) Semua yang dekat dengan I pada mZ8(mIZ' m30, mZ9)tidak dapat ditutup dengan satu pengelompokan. 210
Perhatikan : Ada lima cara lain yang memungkinkan untuk mengikat bilangan 1 yang masih tersisa.
Tulislah dua kalimat jumlah hasil minimum yang berbeda untuk f.
f= f= Jawaban :
a;:~
f = a'd'e'+ ace + a'ce' + bde'+ {
bee'
+ }
{
b'c'de + a'e'de b'c'de + a'bc'd ab'de + a'c'de
}
211
SOAL 6.3 Sebuah perusahaan kecil mempunyai 100 saham, dan masing-masing saham atas nama pemiliknya mewakili satu suara pada pertemuan para pemegang saham. Mr. Clay memiliki 30 saham, dan Mr.. Drake memiliki 40 saham. Mayoritas dua per tiga diperlukan untuk mengesahkan pertemuan pemegang saham. Setiap empat pemegang saham mempunyai tombol yang bila dia tutup berarti ia bersuara "ya" untuk semua sahamnya dan terbuka berarti ia bersuara "tidak". Suatu sirkuit switching harus didisain untuk menyalakan lampu ketika dilakukan pemilihan. (a) Derivasikan tabel kebenaran un tuk fungsi output (Z). (b) Tulislah perluasan minterm untuk Z dan sederhanakan secara aljabar ke dalam bentuk hasil jumlah minimum. (c) Tulislah perluasan maksterm untuk Z dan sederhanakan secara aljabar ke dalam bentuk jumlah hasil minimum. (d) Periksalah untuk melihatjawaban anda pada (c) apakah ekuivalen dengan jawaban (b). (e) Disainlah jaringan switching minimum dan jaringan gerbang AND-OR minimum untuk merealisasikan Z.
6.4. Sebuah pesawat udara menggunakan dua komputer "ground-based" dan satu komputer "on-board" untuk mengontrol mesin pendorong sebagai pembuat rangkaian yang benar:Juga ada kontrol pendorong manual yang akan memutar kontrol pendorong secara langsung ke komputer "on board" bila pesawat tersebut tidak dapat kontak dengan stasiun di darat. Jika pendorong manual mati (logika 0), maka pendorongnya akan menyala jika paling tidak dua dari tiga komputer mengeluarkan logika I. Jika pendorong manual itu menyala (logika I), maka pendorong tersebut akan menyala jika komputer "on board" mengeluarkan logika I. Buatlah A mewakili tombol pedorong manual, B mewakili output komputer "on board", dan C serta D mewakili output dua komputer "ground." (a) Derivasikan tabel kebenaranuntuk fungsi output Z yaitu I jika pendorong menyala. (b) Tuli"slahperluasan minterm untuk Z dan sederhanakan secara aljabar ke dalam bentuk jumlah hasil minimum. 212
(c) Tulislah perluasan maksterm untuk Z dan sederhanakan secara aljabar ke dalam bentuk jumlah hasil minimum. (d) Periksalah untuk melihat apakahjawaban anda pada (c) ekuivalen dengan jawaban untuk (b). (e) Disainlah jaringan gerbang AND-OR minimum untuk mewujudkan Z. 6.5
Carilah jumlah hasil minimum untuk masing-masing fungsi dengan menggunakan peta Karnaugh. (a)
f.(a, b, c)
= m.
+ m3 + m4 + m6
(b) fid, e, f) = L m(l, 4, 5, 7) (c) fir, s, t) = r't'+ rs + rs (d) f4(x, y, z) = M. M7
·
6.6
Kerjakan Soal 6.5 untuk soal berikut ini : (a)
f.(a, b, c)
=
mJ + m4 + ms + m6
(b) f2(d, e, f) = TIM(O,2, 4, 7) (c) f3(r, s, t) = r's't'+ rt + st + rst' 6.7
(a) Plotkan fungsi berikut ini pada peta Kamaugh. (Jangan memperluas ke bentuk minterm sebelum memplotkan.) F =(A, B, C, D) = A'B' + CD'+ ABC + A'B'CD'+ ABC'D (b) Carilah jumlah hasil minimum. (c) Carilah jumlah hasil minimum.
6.8
Kerjakan Soa16.7 untuk F(A, B, C, D) = B'C' + A'BD + ABCD' + B'C.
6.9
Carilah kalimatjumlah hasil minimum untuk masing masing fungsi berikut 1m.
-
(a) f(a, b, c, d) (b)
f(a,
b, c, d)
(c) f(a, b, c, d) (d)
f(a,
b. c. d)
= = = =
I.m(O, 1, 2, 4, 6, 7, 8, 9, 13, 15) TIM(l, 2, 4, 9, 11 ) Lm(O, 1, 5, 8, 12, 14, 15)+ L,d(2,7,11) TIM(Q, 1, 4, 5, 10, 11, 12) TID(3,8,14) 213
6.10 Carilah kalimat jumlah hasil minimum untuk masing-masing fungsi berikut 1m:
= Un(O, 2, 3, 4, 7, 8, 14)
(a)
f(a, b, c, d)
(b)
f(a, b, c, d) = Un(1, 2, 4, 15 ) + L d(O, 3, 14 )
(c)
f(a, b, C, d)
9, 15)
(d)
f(a,
8) n D(3, 8, 14)
= nM(1, 2, 3,4, b, c, d) = nM(O, 2,4,6,
6.11 Carilah kalimat jumlah hasil minimum untuk : (a) m (0, 2, 3, 5, 6, 7, II, 12, 13) (b) m(2, 4, 8) + d(O, 3, 7) (c) m (1, 5, 6, 7, 13) + d(8, 4) 6.12 Suatu jaringan logika merealisasikan fungsi F (a, b, c, d) = a'b' + a' cd + ac'd + ab'd'l. Dengaq mengasumsikan bahwa a =c tidak pemah ada ketika b = d = I, carilah kalimat yang disederhanakan untuk F. 6.13 Suatu jaringan switching mempunyai dua input kontrol (CI' C2), dua input data (XI' X2), dan satu output (Z). Jaringan yang menampilkan operasi logika AND, OR, EQU (ekuivalensi), atau XOR (eksklusif-OR) pada dua input data. Fungsi yang dilakukan tergantung pada input kontrol :
CI
C2
0 0 1 1
0 1 0 1
I
Fungsi yang ditampilkan oleh Jaringan AND OR EQU XOR
(a) Derivasikan tabel kebenaran untuk Z. (b) Gunakan peta Kamaugh untuk mencari jaringan gerbang AND-OR untuk merea1isasikanZ.
214
6. 14 Untuk peta yang diberikan di bawah ini : (a) Carilah jumlah hasil minimum untuk fl' (b) Carilah hasil jumlah minimum untuk f 2' ab
"-
cd
--
I
I
--
--
ab
--
"-
cd
X
I
1
1
X
1
1
1
X
1
X
I
1
X
X
1
1
0
1
0
1
1
1
X
0
0
1
0
6.15 Carilah jumlah hasil minimum untuk F. Garisbawahilah implikan prima esensial pada jawaban anda. ab
"-
cd I
-- -. .. 1
1
X
1
X
1
1 I
6.16 Dengan F
= AB'D
X
1
.
1 1
1
+ A'B + A'C + CD
(a) Gunakan peta Karnaugh untuk mencari kalimat maksterm untuk F (buatlah jawaban anda daIam notasi desimaI dan aIfabetik. (b) Gunakan peta Karnaugh untuk mencari bentuk jumlah hasil minimum untuk F'. (c) Carilah jumlah hasil minimum untuk F. 215
(d) Dengan peta untuk F, kita dapat mencari peta dual untuk F dengan mengkomplementasikan semua bilangan ° dan 1 pada peta dan juga mengkomplementasikan semua bilangan ° dan I pada kepala kolom dan baris. Gunakan metode ini untuk mencari bentuk jumlah hasil minimum untuk FD.(Hati-hatilahketika membacapeta FDkarena kepala kolom dan baris tidak akan berada pada urutan seperti biasanya.) Periksalah secara aljabar bahwa kaliamt anda untuk FD benar.
6.17 Carilahjumlah hasil minimum untuk kalimatdi bawah ini. Kemudian buatlah mintermtertentuyangtidakdipedulikandan periksalahbahwajumlah hasil minimumnya tidak berubah. Sekarang mulailah kembali dengan kalimat asli dan carilah masing-masing minterm tunggal yang dapat dibuat menjadi tidak dipedulikan tanpa mengubah jumlah hasil minimum. (a) F(A, B, C, D) (b)
F(A, B, C, D)
= A'C' + B'C + ACD' + BC'D, minterm 5 = A'BD + AC'D + AB' + BCD + A'C'D', minterm 7
6.18 Carilah semua kalimat jumlah hasil minimum yang memungkinkan untuk masing-masing fungsi : (a)
f(a, b, c)
=nM
(b)
f(d, e, f)
= L m(l, 6) + d(O, 3, 5)
(c)
f(P, q, r)
= (p + q' + r)(p'+ q + r')
(d)
f(s, t, u)
= L m(l, 2, 3) + L d(O, 5, 7)
(e)
f(a, b, c)
= n M(3,
(t)
f(d, e, f)
=
(2, 3, 4)
4)
L m(l, 4, 6) + L d(O,2, i)
6.19 Carilah kalimat jumlah hasil minimum dan hasil jumlah minimum untuk masing-masing fungsi : (a) f(A,B,C,D) (b)
216
=A'B'
f(A, B, C, D)
+ A'B'C'+ A'BD'+ AC'D + A'BD + AB'CD'
= n m(O,2, 10, II, 12, 14, 15)· n D (5,7)
6.20 Dengan mengasumsikan bahwa input ABCD = 0101, ABCD = 1001, ABCD = 1011 tidak pemah ada. carilah kalimat yang disederhanakan untuk F
= A'BC'D
+ A'B'D + A'CD + ABD + ABC
6.21 Untuk masing-masing fungsi berikut ini, carilah implikan prima esensial dan kemudian carilah semua kalimat jumlah hasil minimum :
= L mO, 5, 6, 7, II, 13, 15) (b) f(w, x, y, z) = II m(O,3,5,7,8,9,IO,12,13)+ dO,6,II,14)
(a)
f(a, h, c, d)
= L m(O, I,
3, 7, 8, 9, 13, 15)+ L d(2, II). . (a) Carilah semua implikan prima. (b) Carilah semua implikan prima esensial dan katakan mengapa masingmasing implikan prima tersebut esensial. (c) Carilah kalimat jumlah hasil minimum untuk F.
6.22 DenganF
6.23 Carilah semua implikan prima esensial untuk masing-masing fungsi yang diplotkan pada halaman 141. 6.24 Carilah implikan prima untuk masing-masingfungsi yang diplotkan dibawah 1m:
F
G
217
6.25
F(a,b,c,d,e)
= L m(0,3,4,5,6,7,8,12,13,14,16,21,23,24,29,31)
(a) Carilah implikan prima esensial dengan menggunakan peta Kamaugh dan tunjukkan mengapa masing-masing implikan prima yang dipilih adalah esensial (ada 4 implikan prima esensial). (b) Carilah semua implikan prima dengan menggunakan peta Kamaugh (ada 9, semuanya).
6.26
F(a,b,c,d,e)
= L m(0,1,4,5,9,1O,11,'12,14,18,20,21,22,25,26,28)
(a) Carilah implikan prima esensial dengan menggunakan peta Kamaugh, dan tunjukkan mengapa masing-masing implikan prima yang dipilih adalah esensial (ada 4 implikan prima esensial). (b) Carilah semua implikan prima dengan menggunakan peta Karnaugh (ada 13 semuanya).
6.27
F(A,B, C, D, E) = L m(0,2,6,7,8,1O,11,12,13,14,
16,18,19,20,30)
+
L d(4,
9, 21) Carilah kalimat jumlah hasil minimum untuk F. Garis bawahilah implikan prima esensial pada kalimat ini. 6.28 Kerjakan Soal 6.27 dengan F(A,B,
C, D, E)
= L m(0,1,2,6,7,9,1O,15,16,18,20,21,27,30) + L d(3,4,11,
12, 19)
6.29 F(A,B,C,D,E)
= n M(3,6,7,8,9,10,18,20,21
,22,23,25,26,28,29,30)
Carilahkalimatjumlah hasil minimumuntukF. Garis bawahilahimplikan prima esensialpada kalimatini. 6.30 Kerjakan Soal 6.29 dengan F(A,B,C,D,E) = n M(2,3,4,8,9;10;14,15,16,18,19,20,23,24,30,31)
218
6.31 Carilah hasil jumlah minimum untuk : (a)
F(a,b,c,d,e)
= L m(1,2,3,4,5,6,25,26,27,28,29,30,31)
(b)
F(a,b,c,d,e)
= L m(1,5,12,13,14,16,17,21,23,24,30,31) +
L d(O,2,3,4)
6.32 Dengan menggunakan peta Kamaugh 6-variabel, carilah ka1imat jumlah hasil minimum untuk masing-masing fungsi berikut ini.
(a) G
= C'E'F
(b) H
= A 'B'CDF'
+ DEF + AD'E'F'+ BC'E'F + AD'EF' + A 'CD + A 'B 'CD'E + BCDF'
6.33 Carilah kalimat jumlah hasil minimum untuk masing-masing fungsj berikut ini. Garis bawahilah implikan prima esensia1 pada jawaban anda. (a)
f(a,b,c,d,e)
= L m(O,I,3,4,6,7,8,IO,11,15,16, +
(b)
18,19,24,25,28,29,31)
L d(5,9,30)
f(a,b,c,d,e) = L m(1,3,5,8,9,15,16,20,21,23,27,28,31)
6.34 Carilah kalimat hasil jumlah minimum untuk masing-masing fungsi berikut InI. (a)
F(v,w,x,y,z)
= L m(4,5,8,9,12,13,18,20,21,22,25,28,30,31)
(b) F(a,b,c,d,e)"= n M (2,4,5,6,8,10,12,13,16,17,18,22,23,24) n D(O,11,30,31)
6.35 Sederhanakanlah kalimat berikut ini dengan terlebih dahulu menggunakan peta Kamaugh kemudian dengan menggunakan a1jabarBoolean. Gunakan peta sebagai pedoman untuk menentukan teorema mana yang diaplikasikan pada term tertentu untuk penyederhanaan aljabar. F = a'b'c' + a'c'd + bcd + aabc + ab'
219
-
6.36 F(V, ~X,Y,Z)
220
--
= n M(O,3,6,9,1l,19,20,24,25,26,27,28,29,30)
n D(1,2,12,13)
(a)
Carilah dua kalimat jumlah hasil minimum untuk F.
(b)
Garis bawahilah implikan prima esensialpadajawaban andadan katakan mengapa masing-masing implikan prima tersebut esensial.
