Karnaugh MAP (K-Map)

Pokok Bahasan :
1. K-map 2 variabel
2. K-map 3 variabel
3. K-map 4 variabel
4. Penyederhanaan rangkaian dengan k-map

Tujuan Instruksional Khusus :

1.Mahasiswa dapat menerangkan dan memahami cara
membuat k-map 2, 3, 4 variabel.
2.Mahasiswa dapat menerangkan dan memahami cara
peng-cover-an minterm dalam sebuah k-map..
3.Mahasiswa dapat menyederhanakan persamaan logika
melalui metode k-map.
1
 Karnaugh Map (K-Map)

•Suatu peralatan grafis yang digunakan untuk menyederhanakan

persamaan logika atau mengkonversikan sebuah tabel kebenaran
menjadi sebuah rangkaian logika.

•Salah satu metode yang paling mudah untuk penyederhanaan

Rangkaian Logika.

2
 Karnaugh Map 2 Variabel :
( A dan B )
B 0
Tabel Kebenaran A 1

Map
0 A’B’ A’B
Value A B Y Model I
0 1

0 0 0 A’B’
1 AB’ AB
2 3

1 0 1 A’B
Map Value
2 1 0 AB’ A 0
B 1
3 1 1 AB
0 A’B’ AB’
0 2
Model II
1 A’B AB
1 3

3
Desain Pemetaan K- Map 2
Variabel

A 0
B 1

0 B’

1 B

A’ A

4
 Karnaugh Map 2 Variabel :
dengan minterm-mintermnya

y F = Σ(m0,m1) = x’y + x’y’

y
x 0 1
x y F
0 x’y’ x’y y
x 0 1 0 0 1
x 1 xy’ xy 0 1 1 0 1 1
1 0 0 1 0 0
1 1 0

5
 B B
A 0 1 A 0 1
00 1 00 1 F=AB +A′B +AB ′
F=AB ′+A’B
11 0 11 1

B B
A 0 1 A 0 1
00 1 00 1 F=AB +A′B +AB ′
F=AB ′+A’B
11 0 11 1 F=A+B

6
 Contoh : 1

B 0
Tabel Kebenaran A 1

Map
Value A B Y 0 1 0
0 2

0 0 0 1 A’B’ 1 0 1
1 3

1 0 1 0
2 1 0 0 B 0
A 1
3 1 1 1 AB
0 A’B’ 0
0 1

Jadi Y = A’B’ + AB
1 0 AB
2 3

7
 Contoh : 2

B 0
Tabel Kebenaran A 1

Map
Value A B Y 0 1 1
0 1

0 0 0 1 A’B’ 1 0 0
2 3

1 0 1 1 A’B

2 1 0 0 B 0
A 1
3 1 1 0
0 A’B’ A’B
0 1

Jadi Y = A’
1 0 0
2 3

8
 A
Catatan untuk K-Map 0 1
2 Variabel 0 1

1 AB
• 0 kotak terlingkupi = “0” (Low) 1
• 1 kotak terlingkupi = 2 variabel output
• 2 kotak terlingkupi = 1 variabel output A’B’
• 4 kotak terlingkupi = “1” (High)
• Melingkupinya harus posisi “Horisontal “ Y = AB + A’B’
atau “vertikal” , yang dilingkupi digit ”1” dan
jumlah digit “1” yang dilingkupi 2n (1,
A
2,4,8,16, ...) B 0 1

0 1 1

1 1
B’ A

Y = B’ + A
9
 Contoh 3:
Dari Tabel Kebenaran dibawah, tulis persamaan
logikanya dengan menggunakan K-map :

A 0
B 1
Map
Value A B Y 1
0 B’
0 0 0 1
1 0 1 1 1 1 1 B

2 1 0 0
A’ A
3 1 1 1 A 0
1
B

1 B’
0

Jadi Y = A’ + B 1 1 1 B

10
A’ A
 Contoh 4 :
Sederhanakan persamaan logika :
Y = A + AB’ + A’B
Menggunakan K- map :

A 0 A 0
B 1 B 1

1 B’ 1 B’
0 0

1 1 1 B 1 1 1 B

A’ A A’ A

Jadi Y = A + B

11
 Karnaugh Map 3 Variabel :
( A, B dan C )
Tabel Kebenaran
Model I
Map
Value A B C Y BC
A 00 01 11 10
0 0 0 0 A’B’C’ A’B’C A’BC A’BC’
0 0 1 3 2
1 0 0 1
1 AB’C’ AB’C ABC ABC’
2 0 1 0 4 5 7 6

3 0 1 1 Model II Map Value

AB
4 1 0 0 C 00 01 11 10
5 1 0 1 0 A’B’C’
0
A’BC’
2
ABC’
6
AB’C’
4

6 1 1 0 1 A’B’C A’BC ABC AB’C

1 3 7 5

7 1 1 1
12
 Tabel Kebenaran
Map
Value A B C Y
Model III Model IV
0 0 0 0
1 0 0 1
C A
AB 0 1 BC 0 1
2 0 1 0
A’B’C’ A’B’C A’B’C’ AB’C’
3 0 1 1 00
0 1
00
0 4

A’BC’ A’BC A’B’C AB’C

4 1 0 0 01
2 3
01
1 5

ABC’ ABC A’BC ABC

5 1 0 1 11
6 7
11
3 7

AB’C’ AB’C A’BC’ ABC’

6 1 1 0 10
4 5
10
2 6

7 1 1 1
Map Value
13
 Desain Pemetaan K- Map 3
Variabel

C’

BC
A 00 01 11 10

0 A’
1 A

B’ B

14
 Catatan untuk K- Map
3 Variabel
A 00 01 11 10
• 0 kotak terlingkupi = “0” (Low)
• 1 kotak terlingkupi = 3 variabel output 0 1
• 2 kotak terlingkupi = 2 variabel output
1
•
•
4 kotak terlingkupi = 1 variabel output
8 kotak terlingkupi = “1” (High)
1 1
• Melingkupinya harus posisi “Horisontal “
atau “vertikal” , yang dilingkupi digit ”1” dan
jumlah digit “1” yang dilingkupi 2n (1, 2, 4,
Y = AB’C’ + A’BC + A’BC’
8, ... )
00 01 11 10
A
0 1 1
A
1
1 1
BC00 01 11 10
A
0 1 1 B’
1
1 1
15
 Contoh pengcoveran
AB A
C 00 01 11 10
ab
0
c 00 01 11 10
C 1 0 0 0 1 0
1 0 1 1 1
B
cout = ab + bc + ac

A
ab
0 0 1 1
G(A,B,C) = A c 00 01 11 10
C 0 0 1 1 0 0 0 1 1
B 1 0 0 1 1
f=a
A
1 0 0 1
F(A,B,C) = Σm(0,4,5,7) = AC + B’C’
C 0 0 1 1
B

16
 A B C F
BC 0 0 0 0
00 01 11 10 0 0 1 1
A
00 1 0 1 0
0
1
1
0
1
1
0
11 1 1 1 1 0 0 1
1 0 1 1
1 1 0 1
+
1 1 1 1

F=AB’C’ +AB ′C +ABC +ABC ′ + A’B’C + A’BC’

BC
00 01 11 10
A
00 1 0 1
1 1 1 1 1 F=A+B ′C +BC ′

F=AB’C’ +AB ′C +ABC +ABC ′ + A’B’C + A’BC’

17
 Contoh 1 :
Tabel Kebenaran Diketahui Tabel Kebenaran seperti disamping :
Map Cari persamaan logikanya :
Value A B C Y
0 0 0 0 1
BC
1 0 0 1 1 A 00 01 11 10

2 0 1 0 0 0 1 1 A’B’

1
3 0 1 1 0 1 1 1 AB

4 1 0 0 0 AC
5 1 0 1 1
6 1 1 0 1 Jadi Y = AC + AB + A’B’

7 1 1 1 1
18
Contoh 2 :

Diketahui Persamaan Boolean :

D = A’BC + A’BC’ + ABC’ + ABC + AB’C
Sederhanakan dengan metode K-map
A’BC
A BC 00 01 11 10

0 1 1 A’BC’

1
1 1 1 ABC’

AB’C ABC

BC 00 01 11 10
A
0 1 1 B
1
1 1 1
AC
Jadi D = B + AC
19
 Karnaugh Map 4 Variabel :
Tabel Kebenaran
( A, B, C dan D )
Map
A B C D Y CD
Valu
e AB 00 01 11 10
0 0 0 0 0 A’B’C’D’ A’B’C’D A’B’CD A’B’CD’
00 0 1 3 2

1 0 0 0 1
A’BC’D’ A’BC’D A’BCD A’BCD’
2 0 0 1 0 01 4 5 7 6
Model 1
11 ABC’D’ ABC’D ABCD ABCD’
3 0 0 1 1
12 13 15 14
4 0 1 0 0
5 0 1 0 1 10 AB’C’D’
8
AB’C’D
9
AB’CD
11
AB’CD’
10

6 0 1 1 0 AB
7 0 1 1 1 CD 00 01 11 10
8 1 0 0 0 A’B’C’D’ A’BC’D’ ABC’D’ AB’C’D’
00 0 4 12 8
9 1 0 0 1
A’B’C’D A’BC’D ABC’D AB’C’D
10 1 0 1 0 01 1 5 13 9

11 1 0 1 1 Model 2
11 A’B’CD A’BCD ABCD AB’CD
12 1 1 0 0 3 7 15 11

13 1 1 0 1 10 A’B’CD’
2
A’BCD’
6
ABCD’
14
AB’CD’
10
14 1 1 1 0
20
15 1 1 1 1
Dengan wxyz input

21
 Desain Pemetaan K- Map 4
Variabel

A’ A
AB
CD 00 01 11 10

00
C’
01
D D’
11
C
10

B’

22
 Catatan untuk K-Map
4 Variabel AB
CD 00 01 11 10
00 1 1 1 1
• 0 kotak terlingkupi = “0” (Low) AC’
• 1 kotak terlingkupi = 4 variabel output 01 1 1 1 1
• 2 kotak terlingkupi = 3 variabel output
• 4 kotak terlingkupi = 2 variabel output 11 1 1 A’
• 8 kotak terlingkupi = 1 variabel output
10
• 16 kotak terlingkupi = “1” (High) 1 1 1 1 ACD’
• Melingkupinya harus posisi “Horisontal “
atau “vertikal” , yang dilingkupi digit ”1” dan
jumlah digit “1” yang dilingkupi 2n ( 1,2, 4, 8, AB
16, ... ) CD 00 01 11 10
00 1 1 B’C’
01 1 1
11 1
10
1
A’BCD ABCD’ 23
 Contoh pengcoveran :
A A A
0 0 0 0 1 0 0 0 0 1 1 1

1 0 0 0 0 1 0 0 0 0 1 1
D D D
1 1 0 1 0 0 1 0 0 0 0 0
C C C
1 1 0 0 0 0 0 1 0 0 1 0
B B B

K-map untuk LT K-map untuk EQ K-map untuk GT

LT = A' B' D + A' C + B' C D

EQ = A'B'C'D' + A'BC'D + ABCD + AB'CD’
GT = B C' D' + A C' + A B D'

24
 Contoh pengcoveran :

CD F= A′BC ′+A′CD ′+ABC

00 01 11 10 +AB ′C′D ′+ABC ′+AB ′C
AB
00 0 0 0 1
01 1 1 0 1
11 1 1 1 1
10 1 0 1 1 F=BC ′+CD ′+ AC+ AD ′

25
 Contoh 1
• F(A,B,C,D) =
Σm(0,2,3,5,6,7,8,10,11,14,15)
F=
C + A’BD + B’D’

A 1111
0111
1 0 0 1

0 1 0 0
D
C
1 1 1 1 D
C A
1000
1 1 1 1 0000 B
B
Kalau digambarkan dengan system coordinate

26
 A
AB
Contoh 2 : Diketahui Tabel Kebenaran , CD
cari persamaan logikanya. 00 01 11 10
00 0 1
Map
A B C D Y
Value
01 1 1
0 0 0 0 0 0 D
1 0 0 0 1 0 C
11 3 1 1 1
2 0 0 1 0 1
3 0 0 1 1 1
10
2 1 1
4 0 1 0 0 0
5 0 1 0 1 0 AB A B
CD 00 01 11 10
6 0 1 1 0 1
7 0 1 1 1 1 00 1 ABC’D’
8 1 0 0 0 0
9 1 0 0 1 1
01 1 D
10 1 0 1 0 0 11 1 1 1
11 1 0 1 1 1 C 10
12 1 1 0 0 1
1 1 AB’D
13 1 1 0 1 0 A’C
B
14 1 1 1 0 0
Jadi Y = A’C + AB’D + ABC’D’ 27
15 1 1 1 1 0
 W
WX
YZ 00 01 11 10 Contoh 3 : Lingkarilah dan
Tulis Persamaan Logikanya.
00 1 1
01 1
Z
11 1 1 1 1
Y WXZ’
10
1
W
WX
X YZ 00 01 11 10
00 1 1
W’X’Y’Z’
01 1
Z
YZ
Y
11 1 1 1 1
10
1
Y WX’Z

Jadi M = W’X’Y’Z’ + WXZ’ + WXX’Z + YZ

28
 Physical Implementasi
° Step 1: Truth table
A B C D
° Step 2: K-map
° Step 3: Minimized sum-of-
products
° Step 4: Implementasi dengan
EQ gates
A
1 0 0 0

0 1 0 0
D
0 0 1 0
C
0 0 0 1
B

K-map untuk EQ 29
 Poin-poin penggunaan K-map
• Buat persamaan ke • Tulis persamaan
bentuk SOP (melalui logika hasil peng-
tabel kebenaran). coveran.
• Minterm-mintermnya
masukkan ke k-map (
sesuaikan jumlah kotak
atau variabel input).
• Lingkari (pe-ngcover-
an) yang benar.

30
 Don’t Care
• Kondisi don’t care merupakan kondisi dimana ada beberapa
kombinasi variable input yang tidak selalu dapat dinyatakan nilai
outputnya.

• Keadaan dimana nilai outputnya tersebut bisa berlogic ‘1’ atau

berlogic ‘0’ yang disimbulkan dengan “X” atau “d”.

• Kegunaan dari kondisi don’t care pada penyederhanaan fungsi

dapat dinyatakan pada fakta bahwa dapat diset dengan logic ‘1’
atau logic ‘0’, berdasar kegunaannya untuk format kelompok
logic ‘1’ yang lebih besar.

31
 Karnaugh maps: don’t cares (cont’d)
• f(A,B,C,D) = Σ m(1,3,5,7,9) + d(6,12,13)
– f = A'D + B'C'D tanpa don't cares
– f = A’D + C’D dengan don't cares
A B C D f
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0 A
0 0 1 1 1
0 1 0 0 0 0 0 X 0
0 1 0 1 1
0 1 1 0 X 1 1 X 1
+
0 +
1 1 1 1 D
1 0 0 0 0 1 1 0 0
1 0 0 1 1 C
1 0 1 0 0 0 X 0 0
1 0 1 1 0 B
1 1 0 0 X
1 1 0 1 X
1 1 1 0 0
1 1 1 1 0
32
 Pengcoveran dengan Don’t Cares

CD
00 01 11 10
AB
00 0 1 0 0
01 x x x 1 F=A′C′D+B+AC
11 1 1 1 x
10 x 0 1 1

33
Bentuk ilustrasi pengkoveran
A
0 X 1 0 6 prime implicants:
A'B'D, BC', AC, A'C'D, AB, B'CD
1 1 1 0
D
essential
1 0 1 1
C
0 0 1 1
minimum cover: 3 essential implicants
B
minimum cover: AC + BC' + A'B'D
A
5 prime implicants: 0 0 1 0
BD, ABC', ACD, A'BC, A'C'D
1 1 1 0
D
essential 0 1 1 1
C
0 1 0 0
minimum cover: 4 essential implicants
B
minimum cover: ABC’+ACD+A’BC+A’C’D 34
 Aplikasi K-map
Pada Rangkaian Full Adder
Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1 Metode Aljabar Boole
1 1 0 0 1
Cout +
1 1 1 1 1

S = A’B’Cin + A’BCin’ + A’BCin + ABCin

Cout = A’BCin + A B’Cin + ABCin’ + ABCin
= A’BCin + ABCin + AB’Cin + ABCin + ABCin’ + ABCin
= (A’ + A)BCin + (B’ + B)ACin + (Cin’ + Cin)AB
= 1·BCin + 1· ACin + 1· AB
= BCin + ACin + AB
35
 Aplikasi K-map
Pada Rangkaian Full Adder
Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout 1 1 1 1 1
A
+

0 0 1 0
Pengisiaan digit 1 ke K-map
B 0 1 1 1

Cin
Karnaugh Map for Cout
36
 Aplikasi K-map
Pada Rangkaian Full Adder

Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout 1 1 1 1 1
A
+

0 0 1 0
Pengcoveran pertama.
B 0 1 1 1

Cin
Cout = ACin
Karnaugh Map untuk Cout
37
 Aplikasi K-map
Pada Rangkaian Full Adder

Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout 1 1 1 1 1
A
+

0 0 1 0
Pengcoveran kedua.
B 0 1 1 1

Cin
Cout = Acin + AB
Karnaugh Map for Cout
38
 Aplikasi K-map
Pada Rangkaian Full Adder

Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout 1 1 1 1 1
A
+

0 0 1 0
Pengcoveran ketiga (seluruhnya)
B 0 1 1 1

Cin
Cout = ACin + AB + BCin
Karnaugh Map untuk Cout
39
 Aplikasi K-map
Pada Rangkaian Full Adder

Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout 1 1 1 1 1
A
+

0 1 0 1
B 1 0 1 0

Cin S = A’BCin’
Karnaugh Map untuk S
40
 Aplikasi K-map
Pada Rangkaian Full Adder

Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout 1 1 1 1 1
A
+

0 1 0 1
B 1 0 1 0

Cin S = A’BCin’ + A’B’Cin

Karnaugh Map untuk S
41
 Aplikasi K-map
Pada Rangkaian Full Adder

Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout 1 1 1 1 1
A
+

0 1 0 1
B 1 0 1 0

Cin S = A’BCin’ + A’B’Cin + ABCin

Karnaugh Map untuk S
42
 Aplikasi K-map
Pada Rangkaian Full Adder
Coba anda gambar rangkaian diagramnya ?
Cin
A B Cin S Cout
0 0 0 0 0
0 0 1 1 0
A 0 1 0 1 0
Adder S 0 1 1 0 1
B 1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
Cout 1 1 1 1 1
A
+

0 1 0 1
B 1 0 1 0

Cin S = A’BCin’ + A’B’Cin + ABCin + AB’Cin’

Karnaugh untuk S
Tidak bisa direduksi
43
Latihan Soal 1:

Gambarlah K-map untuk setiap ekspresi logika dibawah

serta sederhanakan dengan pengcoveran yang benar :

1. AB + B’C + A’B’
2. AC + AC’B + BC + B’C’
3. XY + X’Z + Y’Z’
4. XY +YZ + XZ +X’Y’

44
Latihan Soal 2 :

Gambarlah K-map untuk setiap ekspresi logika dibawah

serta sederhanakan dengan pengcoveran yang benar :

1. A(BC’ + C) + B(A + A’C)

2. (AC + AC’B). (BC + B’C’)
3. Z(XY + X’Z) . Y’Z’(X+ Z)

Catatan : cari minterm-mintermnya dulu (rubah kebentuk SOP)

45