PENYEDERHANAAN FUNGSI BOOLEAN DENGAN ALJABAR DAN METODE PETA KARNAUGH PDF

Preview

Summary

PENYEDERHANAAN FUNGSI BOOLEAN DENGAN ALJABAR DAN METODE PETA KARNAUGH MAKALAH Diajukan untuk memenuhi salah satu tugas Mata Kuliah Matematika Diskrit yang diampu oleh bapak Drs. H. Eka Fitrajaya Rahman, M.T. Dwi Fitria Al Husaeni 1903480 PENDIDIKAN ILMU KOMPUTER FAKULTAS PENDIDIKAN MATEMATIKA DAN IL...

Description

PENYEDERHANAAN FUNGSI BOOLEAN DENGAN ALJABAR DAN METODE PETA KARNAUGH MAKALAH Diajukan untuk memenuhi salah satu tugas Mata Kuliah Matematika Diskrit yang diampu oleh bapak Drs. H. Eka Fitrajaya Rahman, M.T.

Dwi Fitria Al Husaeni 1903480

PENDIDIKAN ILMU KOMPUTER FAKULTAS PENDIDIKAN MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS PENDIDIKAN INDONESIA 2020

KATA PENGANTAR Pertama-tama segala puji dan syukur penyusun panjatkan kepada Allah SWT. Tuhan semesta alam karena berkat rahmat, ridho serta inayah-Nya, penyusun dapat menyelesaikan penyusunan makalah yang berjudul “Penyederhanaan Fungsi Boolean Dengan Aljabar Dan Metode Peta Karnaugh” ini tepat pada waktu yang telah ditentukan. Makalah ini memberikan sedikit pemahaman mengenai cara menyederhanakan fungsi aljabar baik itu secara aljabar maupun dengan menggunakan metode peta karnugh (K-map). Penyusun sangat menyadari bahwa makalah ini jauh dari kata sempurna, namun penyusun berharap bahwa dengan diselesaikannya makalah ini dapat memberikan manfaat, dan juga dapat menembah ilmu pengetahuan mengenai materi yang dibahas dalam makalah ini bagi penyusun sendiri khususnya dan bagi para pembaca makalah ini pada umumnya. Setiap kritik dan saran dari pembaca yang sekiranya dapat bersifat membangun dan memberikan kebaikan bagi makalah ini sangat penyusun nantikan.

Terima kasih yang sebesar-besarnya penyusun ucapkan.

Penyusun

DAFTAR ISI

KATA PENGANTAR ................................................................................................................... 1 DAFTAR ISI.................................................................................................................................. 2 MATERI ........................................................................................................................................ 3 A. Penyederhanaan Fungsi Boolean Secara Aljabar ................................................................ 3 B. Penyederhanaan Fungsi Boolean Menggunakan Peta Karnaugh......................................... 6 1.

Bentuk peta Karnaugh ...................................................................................................... 6

2.

Pembagian Wilayah pada peta Karnaugh....................................................................... 13

3.

Teknik minimasi fungsi Boolean dengan peta Karnaugh .............................................. 19

PENUTUP .................................................................................................................................... 27 DAFTAR PUSTAKA .................................................................................................................. 28

MATERI A. Penyederhanaan Fungsi Boolean Secara Aljabar Jumlah literal di dalam sebuah fungsi Boolean dapat diminimumkan dengan trik manipulasi aljabar. Tidak ada urutan khusus yang harus diikuti yang akan menjamin menuju ke jawaban akhir. Metode yang tersedia adalah prosedur cut-and-try uang memanfaatkan postulat, hukum-hukum dasar dan metode manipulasi lain yang sudah dikenal. Rumus pada aljabar Boolean 1)

Tertutup

a) a + b ∈ B b) a ⋅ b ∈ B

2)

Asosiatif

a) a + ( b + c ) = ( a + b ) + c b) a ∙ ( b ∙ c )

3)

=(a∙b)∙c

Indentitas

a) Jika 0 ∈ B, maka ∀ 𝑎 ∈ 𝐵 berlaku a + 0 = 0 + a = a

, 0 = elemen zero

b) Jika 1 ∈ B, maka ∀ 𝑎 ∈ 𝐵 berlaku a ∙ 1 = 1 ∙ a = a

, 1 = elemen unit

4)

Komutatif

a) a + b = b + a b) a ∙ b = b ∙ a

5)

Distributif

a) a ∙ ( b + c ) = a ∙ b + a ∙ c b) ( a + b ) ∙ c = a ∙ c + b ∙ c c) a + ( b ∙ c ) = ( a + b) ( a + c ) d) ( a ∙ b ) + c = ( a + c ) ( b + c)

6)

Idempoten (Sama kuat)

Untuk ∀ 𝑎 ∈ 𝐵 berlaku: a) a + a = a b) a ∙ a = a

7)

Komplemen

Untuk ∀ 𝑎 ∈ 𝐵 dan 𝑎’ ∈ 𝐵 maka a) a + a’ = 1 b) a ∙ a’ = 0

8)

Boundednes (dominasi)

a) a + 1 = 1 b) a ∙ 0 = 0

9)

Absorbsi (penyerapan)

a) a + (a ∙ b) = a b) a ∙ (a + b) = a

10) Involusi a) ( aʼ )ʼ = a

11) Hukum 0/1 a) 0’ = 1 b) 1’ = 0

12) De Morgan a) ( a + b )’ = a’ ∙ b’ b) ( a ∙ b )’ = a’ + b’

Sederhanakan fungsi-fungsi Boolean berikut ini: a. 𝑓 (𝑥, 𝑦) = 𝑥 + (𝑥 ′ 𝑦) Penyelesaian:

𝑓 (𝑥, 𝑦)

= 𝑥 + (𝑥 ′ 𝑦) = (𝑥 + 𝑥 ′ )(𝑥 + 𝑦)

hukum distributive

= 1 (𝑥 + 𝑦)

hukum komplemen

= 𝑥+𝑦

hukum identitas

b. 𝑓 (𝑥, 𝑦) = 𝑥(𝑥 ′ + 𝑦) Penyelesaian: 𝑓 (𝑥, 𝑦)

= 𝑥 (𝑥 ′ + 𝑦) = (𝑥 ∙ 𝑥 ′ ) + (𝑥 ∙ 𝑦)

hukum distributive

= 0 + (𝑥 ∙ 𝑦)

hukum komplemen

= 𝑥𝑦

hukum identitas

c. 𝑓 (𝑥, 𝑦, 𝑧) = 𝑥 ′ 𝑦 ′ 𝑧 + 𝑥 ′ 𝑦𝑧 + 𝑥𝑦′ Penyelesaian: 𝑓 (𝑥, 𝑦, 𝑧) = 𝑥 ′ 𝑦 ′ 𝑧 + 𝑥 ′ 𝑦𝑧 + 𝑥𝑦′ = 𝑥 ′ 𝑧(𝑦 ′ + 𝑦) + 𝑥𝑦′

hukum distributive

= 𝑥 ′ 𝑧(1) + 𝑥𝑦′

hukum komplemen

= 𝑥′𝑧 + 𝑥𝑦′

hukum identitas

d. 𝑓 (𝑥, 𝑦, 𝑧) = 𝑥𝑧 ′ + 𝑦 ′ 𝑧 + 𝑥𝑦𝑧 ′ Penyelesaian: 𝑓 (𝑥, 𝑦, 𝑧) = 𝑥𝑧 ′ + 𝑦 ′ 𝑧 + 𝑥𝑦𝑧′ = 𝑥𝑧 ′ ∙ 1 + 𝑦 ′ 𝑧 + 𝑥𝑦𝑧′

hukum identitas

= 𝑥𝑧 ′ (1 + 𝑦) + 𝑦′𝑧

hukum distributif

= 𝑥𝑧 ′ ∙ 1 + 𝑦′𝑧

hukum dominasi

= 𝑥𝑧 ′ + 𝑦′𝑧

hukum identitas

e. 𝑓 (𝑥, 𝑦, 𝑧) = (𝑥 + 𝑧 ′ )(𝑦 ′ + 𝑧)(𝑥 + 𝑦 + 𝑧′) Penyelesaian: 𝑓 (𝑥, 𝑦, 𝑧) = (𝑥 + 𝑧 ′ )(𝑦 ′ + 𝑧)(𝑥 + 𝑦 + 𝑧 ′ ) = (𝑥+𝑧 ′ )1(𝑦 ′ + 𝑧)(𝑥 + 𝑦 + 𝑧 ′ )

hukum identitas

= (𝑥 + 𝑧 ′ )(1 + 𝑦)(𝑦 ′ + 𝑧)

hukum distributif

= (𝑥 + 𝑧 ′ )1(𝑦 ′ + 𝑧)

hukum dominasi

= (𝑥 + 𝑧 ′ )(𝑦 ′ + 𝑧)

hukum identitas

𝑎𝑡𝑎𝑢 𝑑𝑎𝑝𝑎𝑡 𝑎𝑛𝑑𝑎 ℎ𝑖𝑡𝑢𝑛𝑔 𝑑𝑒𝑛𝑔𝑎𝑛 𝑚𝑒𝑛𝑔𝑔𝑢𝑛𝑎𝑘𝑎𝑛 𝑑𝑢𝑎𝑙𝑖𝑡𝑎𝑠 𝑑𝑎𝑟𝑖 𝑓𝑢𝑛𝑔𝑠𝑖 𝑛𝑜𝑚𝑜𝑟 (𝑑).

B. Penyederhanaan Fungsi Boolean Menggunakan Peta Karnaugh Metode peta Karnaugh (atau K-map) merupakan metode grafis untuk menyederhanakan fungsi Boolean. Peta Karnaugh adalah sebuah diagram/peta yang terbentuk dari kotak-kotak yang beririsan. Tiap kotak mempresentasikan sebuah minterm. Tiap kotak dikatakan bertetangga jika minterm-minterm yang merepresentasikannya berbeda hanya 1 buah literal. Peta Karnaugh merupakan sebuah metode untuk menyederhanakan fungsi Boolean atau untuk mendapatkan fungsi Boolean yang paling sederhana dari sebuah tabel kebenaran. 1. Bentuk peta Karnaugh a. Peta Karnaugh dengan dua peubah Bentuk sederhana nya pada peta karnaugh dua peubah adalah

Misalnya terdapat fungsi Boolean dengan peubah x dan y (f (x, y)), maka 

Baris untuk peubah x dan kolom untuk peubah y



Baris pertama nilai 0 (x’)



Baris kedua nilai 1 (x)



Kolom pertama nilai 0 (y’)



Kolom kedua dengan 1 (y)

Penyajian 1

m0

m1

m2

m3

Penyajian 2 y 0 x

1

0 x’ y’

x’ y

1 x y’

xy

Penyajian 3 y’ x’ x’ y’ x

x y’

y x’ y xy

Perhatikan bahwa dua kotak yang bertetangga hanya berbeda satu literal. Kotak x’y’ dan x’y misalnya, hanya berbeda pada literal kedua (y’ dan y), sedangkan literal pertama sama (yaitu x). jika minterm pada setiap kotak direpresentasikan dengan string biner, maka dua kotak yang bertetangga hanya berbeda 1 bit (contohnya 00 dan 01, pada kedua kotak tersebut hanya berbeda satu bit yaitu pada bit kedua).

Contoh 1: Gambarkan peta Karnaugh untuk f (x, y) = xy + x’y

Penyelesaian: Peubah tanpa komplemen dinyatakan sebagai 1 dan peubah dengan komplemen dinyatakan sebagai 0, sehingga xy dinyatakan sebagai 11 dan x’y dinyatakan sebagai 01. Kotak-kotak yang merepresentasikan minterm 11 dan 01 diisi dengan 1, sedangkan kotak-kotak yang tidak terpakai diisi dengan 0. Hasil pemetaan:

y

x

0

1

0 0

1

1 0

1

Contoh 2: Diberikan tabel kebenaran di bawah ini. Petakan fungsi dengan tabel kebenaran tersebut kedalam peta Karnaugh.

x

y

f (x, y)

0

0

0

0

1

0

1

0

1

1

1

1

Penyelesaian: Tinjau hanya nilai fungsi yang memberikan 1. Fungsi Boolean yang merepresentasikan tabel kebenaran adalah f (x, y) = xy’ + xy. Tempatkan 1 di dalam kotak di peta Karnaugh untuk kombinasi nilai x dan y yang bersesuaian (dalam hal ini 1 0 dan 1 1) y

x

0

1

0 0

0

1 1

1

b. Peta Karnaugh dengan tiga peubah

Untuk fungsi Boolean dengan tiga peubah (misalnya x, y dan z), jumlah kotak di dalam peta Karnough meningkat menjadi 23 = 8. Baris pada peta karnaugh untuk perubah x dan kolom untuk peubah yz. 

Baris pertama diidentifikasi nilai 0 (menyatakan x’)



Baris kedua dengan 1 (menyatakan x)



Kolom pertama diidentifikasi nilai 00 (menyatakan x’y’)



Kolom kedua diidentifikasi nilai 01 (menyatakan xy’)



kolom ketiga diidentifikasi nilai 11 (menyatakan xy)



Kolom keempat diidentifikasi nilai 10 (menyatakan xy’). yz m0

m1

m3 m2

m4

m5

m7 m6

00

01

11

10

x 0 x’y’z’ x’y’z x’yz x’yz’ 1 xy’z’

xy’z

xyz

xyz’

Perhatikan urutan dari mi –nya. Urutan disusun sedemikian rupa sehingga setiap dua kotak yang bertetangga hanya berbeda satu bit. Contoh 1: 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

Penyelesaian: Tinjau hanya nilai fungsi yang memberikan 1. Fungsi Boolean yang merepresentasikan tabel kebenaran adalah f (x, y) = x’y’z + xy’z’ + xy’z + xyz. Tempatkan 1 di dalam kotak di peta Karnaugh untuk kombinasi nilai x dan y yang bersesuaian (dalam hal ini 001, 100, 101 dan 111): yz 00

01

11

10

x 0

0

0

0

1

1

0

0

1

1

Contoh 2: Gambarkan peta Karnaugh untuk f (x, y, z) = x’yz’ + xyz’ + xyz Penyelesaian: x’yz’ → dalam bentuk biner: 010 xyz’ → dalam bentuk biner: 110 xyz → dalam bentuk biner: 111 kotak-kotak yang merepresentasikan minterm 010, 110 dan 111 dengan 1, sedangkan kotak-kotak yang tidak terpakai diisi dengan 0.

yz 00

01

11

10

x 0

0

0

0

1

1

0

0

1

1

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 pertama diidentifikasi nilai 00 (menyatakan w’x’)



Baris kedua dengan 01 (menyatakan w’x)



Kolom pertama diidentifikasi nilai 00 (menyatakan y’z’)



Kolom kedua diidentifikasi nilai 01 (menyatakan yz’)



Kolom ketiga diidentifikasi nilai 11 (menyatakan yz)



Kolom keempat diidentifikasi nilai 10 (menyatakan yz’)

yz m0

m1

m3

m2

m4

m5

m7

m6

00

01

11

10

wx 00 w’x’y’z’ w’x’y’z w’x’yz w’x’yz’

m12 m13 m15 m14

01 w’xy’z’

w’xy’z

w’xyz

w’xyz’

m8

11 wxy’z’

wxy’z

wxyz

wxyz’

10 wx’y’z’

wx’y’z

wx’yz

wx’yz’

m9

m11 m10

Perhatikan urutan dari mi-nya. Urutan disusun sedemikan rupa sehingga setiap dua kotak yang bertetangga hanya berbeda satu bit.

Contoh 1: Diberikan fungsi Boolean yang direpresentasikan dengan tabel kebenaran dibawah ini. Petakan tabel tersebut ke 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

Penyelesaian: Tinjau hanya nilai fungsi yang memberikan 1. Fungsi Boolean yang merepresentasikan tabel kebenaran adalah f (w, x, y, z) = w’x’y’z + w’xyz’ + w’xyz + wxyz’. Hasil pemetaan tabel ke peta karnaugh: yz 00

01

11

10

0

1

0

1

01

0

0

1

1

11

0

0

0

1

10

0

0

0

0

wx

00

2. Pembagian Wilayah pada peta Karnaugh Pembagian wilayah pada metode ini bergantung pada bentuk baku yang digunakan. Berikut dijelaskan pembagian wilayah peta Karnaugh jika menggunakan bentuk baku SOP. 

Pembagian wilayah 2 peubah



Pembagian wilayah 3 peubah



Pembagian wilayah 4 peubah

Pada gambar di atas menuntukan bahwa Kolom 1 merupakan wilayah A’ dan B’ sehingga kolom 1 diberi judul 00. Hal ini dikarenakan pada bentuk SOP (Sum of Product) sebuah komplemen bernilai 0 dan 1 untuk bukan komplemen. Begitu juga pada kolom 2 yang merupakan wilayah A’ dan B diberi judul 01. Kolom 3 yang merupakan wilayah A dan B diberi judul 11 dan kolom 4 yang merupakan wilayah A dan B’ diberi judul 10. Pemberian judul pada masing-masing kolom dilakukan untuk memudahkan penentuan kolom.

Contoh: Diketahui tabel kebenaran sebagi berikut.

A

B

C

Y

Urutan keluaran

0

0

0

0

0

0

0

1

1

1

0

1

0

0

2

0

1

1

0

3

1

0

0

0

4

1

0

1

0

5

1

1

0

1

6

1

1

1

1

7

Langkah-langkah: 1) Perhatikan nilai logika keluaran dan urutannya pada tabel kebenaran di atas. 2) Masukkan nilai logika keluaran ke dalam peta karnaugh sesuai urutannya, sehingga diperoleh peta karnaugh sebagai berikut

3) Lakukan pengelompokan pada nilai logika 1 (satu):

4) Dengan menentukan irisan wilayah dari pengelompokan, nilai maka diperoleh: Pengelompokkan 1: A · B Pengelompokan 2: A’ · B’ · C Fungsi Boolean bentuk SOP 𝑌 = 𝐴 ∙ 𝐵 + 𝐴′ ∙ 𝐵 ′ ∙ 𝐶

Contoh lainnya untuk 4 peubah: A

B

C

D

Y

Urutan Keluaran

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

0

1

2

0

0

1

1

1

3

0

1

0

0

0

4

0

1

0

1

0

5

0

1

1

0

1

6

0

1

1

1

1

7

1

0

0

0

1

8

1

0

0

1

0

9

1

0

1

0

1

10

1

0

1

1

0

11

1

1

0

0

1

12

1

1

0

1

0

13

1

1

1

0

1

14

1

1

1

1

0

15

Memasukan nilai logika keluaran sesuai urutannya:

Mengelompokkan nilai logika satu (1):

Diperoleh: Pengelompokan 1: A’ ∙ C Pengelompokan 2: C ∙ D’ Pengelompokan 3: A ∙ C’ ∙ D’

Pengelompokan 4: B’ ∙ C’ ∙ D’ Fungsi Boolean bentuk SOP: 𝑌 = 𝐴′ ∙ C + C ∙ D′ + 𝐴 ∙ C′ ∙ D′ + 𝐵 ′ ∙ C′ ∙ D′ Penggunakan peta Karnaugh untuk bentu POST. Caranya sama seperti bentuk SOP hanya saja pembagian wilayah dan pengelompokan nilainya berkebalikan. Kolom 1 merupakan wilayah A dan B sehingga kolom 1 diberi judul 00. Hal ini karena dalam bentuk POS nilai komplemen bernilai 1 dan tanpa komplemen bernilai 0. Kolom 2 merupakan wilayah A dan B’ diberi judul 01. Kolom 3 wilayah A’ dan B’ diberi judul 11. Kolom 4 yang merupakan wilayah A’ dan B diberi judul 10. Pemberian judul pada masing-masing kolom dilakukan untuk memudahkan penentuan wilayah kolom. Pada metode POS pengelompokan dilakukan pada nilai logika 0 (nol).

3. Teknik minimasi fungsi Boolean dengan peta Karnaugh Penggunaan peta karnaugh dalam penyederhanaan fungsi Boolean dilakukan dengan cara menggabungkan kotak-kotak yag bernilai 1 dan saling bersisian. Kelompok kotak yang bernilai 1 dapat membentuk pasangan (dua), kuad (empat), dan octet (delapan). 1. Pasangan: dua buah 1 yang bertetangga yz 00

01

11

10