[Type text]

Pertemuan Minggu Ke-1PENGANTAR LOGIKA

2.1. DEFINISI PERNYATAANYang disebut sebagai pernyataan (statement) adalah sekumpulan simbol yang

memiliki nilai kebenaran, yaitu benar atau salah dan tidak mungkin kedua-duanya. Kadang-

kadang, pernyataan disebut juga sebagai kalimat terbuka.

Contoh :

(a). Ibukota Perancis adalah Paris

(b). Jika x > 2 maka x+3 < 5

(c). Apa kabar?

(d). Letakkan buku itu di meja!

Pada contoh di atas, (a) dan (b) adalah pernyataan sebab keduanya memiliki nilai

kebenaran ((a) benar dan (b) salah) sedangkan (c) dan (d) bukan merupakan pernyataan sebab

keduanya tidak memiliki nilai kebenaran (tidak bisa ditentukan benar atau salah).

Pernyataan dapat dibedakan menjadi dua yaitu pernyataan tunggal dan pernyataan tidak tunggal. Pernyataan tunggal adalah pernyataan yang hanya terdiri dari satu pernyataan

sedangkan pernyataan tidak tunggal adalah pernyataan yang tersusun dari dua atau lebih

pernyataan tunggal yang dihubungkan oleh kata hubung.

Contoh pernyataan tunggal

Hari ini hujan deras

Perancis menang melawan Argentina dalam final Piala Dunia 2002

PASCAL lebih sulit dipelajari daripada BASIC

Contoh pernyataan tidak tunggal

Andi belajar Fisika Listrik dan Kalkulus

1

[Type text]

Jika x>3 maka x+1 >4

Terdapat mahasiswa yang suka musik dan olahraga.

2.2. TABEL KEBENARANNegasi (Not)

Negasi dari pernyataan P adalah merupakan ingkaran dan pernyataan P. Negasi dari

pernyataan P dinyatakan dengan not P.

Nilai kebenaran dari negasi dinyatakan dalam tabel nilai kebenaran di bawah ini.

P Not P

B S

S B

Konjungsi (And)Sembarang dua pernyataan dapat digabungkan oleh kata dan (and) dan membentuk

konjungsi, sehingga akan berbentuk P and Q.Nilai kebenaran dari konjungsi dinyatakan dalam tabel nilai kebenaran di bawah ini.

P Q P AND Q

B B B

B S S

S B S

S S S

Contoh 1.

Misalkan P : Hujan sedang turun dan Q : Udara dingin maka pernyAtaan P and Q adalah

pernyataan : Hujan sedang turun dan udara dingin

Contoh 2.

a. Paris ada di Perancis dan 2+2 = 5

b. Paris ada di Inggris dan 2+2 = 4

c. Paris ada di Inggris dan 2+2 = 5

2

[Type text]

d. Paris ada di Perancis dan 2+2 = 4

Dari keempat contoh di atas, hanya pernyataan (d) yang bernilai benar. Ketiga pernyataan

yang lain bernilai salah sebab sekurang-kurangnya terdapat satu pernyataan yang salah.

Disjungsi (Or)Sebarang dua pernyataan dapat digabungkan oleh kata atau (or) dan membentuk

disjungsi, sehingga akan berbentuk P or Q.Nilai kebenaran dari konjungsi dinyatakan dalam tabel nilai kebenaran di bawah ini.

P Q P OR Q

B B B

B S B

S B B

S S S

Contoh 1.

Misalkan P : Hujan sedang turun dan Q : Udara dingin maka pernyataan P or Q adalah

pernyataan : Hujan sedang turun atau udara dingin

Contoh 2.

a. Paris ada di Perancis atau 2+2 = 5

b. Paris ada di Inggris atau 2+2 = 4

c. Paris ada di Inggris atau 2+2 = 5

d. Paris ada di Perancis atau 2+2 = 4

Dari keempat contoh di atas, hanya pernyataan (c) yang bernilai salah. Ketiga pernyataan

yang lain bernilai benar sebab sekurang-kurangnya terdapat satu pernyataan yang benar.

Implikasi (If-Then)Implikasi dari pernyataan P dan Q dituliskan sebagai : if P then Q.

Nilai kebenaran dari implikasi dinyatakan dalam tabel di bawah ini.

P Q IF P THEN Q

3

[Type text]

B B B

B S S

S B B

S S B

Contoh 1.

Misalkan P : Hujan sedang turun dan Q : Udara dingin maka pernyataan if P then Q

adalah pernyataan : Jika hujan sedang turun maka udara dingin

Contoh 2.

a. Jika Paris ada di Perancis maka 2+2 = 5

b. Jika Paris ada di Inggris maka 2+2 = 4

c. Jika Paris ada di Inggris maka 2+2 = 5

d. Jika Paris ada di Perancis maka 2+2 = 4

Dari keempat contoh di atas, hanya pernyataan (a) yang bernilai salah. Ketiga pernyataan

yang lain bernilai benar.

Bi-Implikasi (If and only if)Bi-implikasi dari pernyataan P dan Q dituliskan sebagai : P if and only if Q.

Nilai kebenaran dari implikasi dinyatakan dalam tabel di bawah ini.

4

[Type text]

P Q P IF AND ONLY IF Q

B B B

B S S

S B S

S S B

Contoh 1.

Misalkan P : Hujan sedang turun dan Q : Udara dingin maka pernyataan P if and only if Q

adalah pernyataan : Hujan sedang turun jika dan hanya jika udara dingin

Contoh 2.

a. Paris ada di Perancis jika dan hanya jika 2+2 = 5

b. Paris ada di Inggris jika dan hanya jika 2+2 = 4

c. Paris ada di Inggris jika dan hanya jika 2+2 = 5

d. Paris ada di Perancis jika dan hanya jika 2+2 = 4

Dari keempat contoh di atas, pernyataan (a) dan (b) bernilai salah sedangkan (c) dan (d)

bernilai benar.

If – Then – ElseTabel nilai kebenarannya adalah :

P Q R IF P THEN Q ELSE R

B B B B

B B S B

B S B S

B S S S

S B B B

S B S S

S S B B

S S S S

2.3. VALIDITAS PERNYATAAN

5

[Type text]

InterpretasiInterpretasi I adalah pemasangan nilai kebenaran (B atau S) pada setiap simbol

pernyataan.

Contoh 1.

Misalkan diketahui pernyataan : P or not Q

I1 : P B

Q S

Adalah sebuah interpretasi untuk pernyataan di atas.

Contoh 2.

Misalkan diketahui pernyataan : P if and only if (Q and R)

I1 : P S

Q S

R B

Adalah sebuah interpretasi untuk pernyataan di atas.

I2 : P B

R S

Adalah bukan sebuah interpretasi untuk pernyataan di atas.

Definisi Valid /Tautologi dan KontradiksiSuatu pernyataan P disebut valid/tautologi bila untuk sebarang interpretasi, P selalu

bernilai benar.

Suatu pernyataan P disebut kontradiksi bila untuk sebarang interpretasi, P selalu bernilai

salah.

6

[Type text]

2.4. MENENTUKAN VALIDITAS SUATU PERNYATAANUntuk menyelidiki validitas suatu pernyataan, terdapat 3 metoda yang bisa digunakan

yaitu :

1. tabel kebenaran (truth table)

2. pohon semantik (semantic tree)

3. pengandaian (proof by falsification)

Berikut ini, masing-masing metoda tersebut akan dibicarakan.

Tabel Kebenaran (Truth Table)Sesuai namanya, metoda ini menggunakan tabel kebenaran untuk menyelidiki validitas

suatu pernyataan. Penggunaannya akan ditunjukkan dengan contoh-contoh di bawah ini.

Contoh 1.

Tunjukkan bahwa pernyataan P or not (P and Q) adalah valid

P Q P and Q not (P and Q) P or not (P and Q)

B B B S B

B S S B B

S B S B B

S S S B B

Terlihat bahwa kolom terakhir tabel kebenaran di ats selalu bernilai benar. Disimpulkan

bahwa pernyataan P or not (P and Q) adalah valid

7

[Type text]

Contoh 2.

Dengan tabel kebenaran, selidiki validitas pernyataan P and (Q or R)

P Q R Q or R P and (Q or R)

B B B B B

B B S B B

B S B B B

B S S S S

S B B B S

S B S B S

S S B B S

S S S S S

Ternyata kolom terakhir dari tabel kebenaran di atas tidak selalu bernilai benar. Jadi

disimpulkan bahwa pernyataan di atas tidak valid.

Pohon Semantik (Semantic Tree)Contoh 1

Tunjukkan bahwa pernyataan P or not (P and Q) adalah valid

1

P benar P salah

B Q benar Q salah

B B

Dari pohon semantik di atas terlihat, untuk kemungkinan pertama yaitu P benar, tidak

perlu dibuat percabangan sebab bila P benar maka pernyataan akan selalu bernilai benar.

Untuk kemungkinan kedua (P salah dan Q benar) dan ketiga (P salah dan Q salah), pernyataan

tetap bernilai benar. Disimpulkan bahwa pernyataan di atas adalah valid sebab selalu benar

untuk sebarang interpretasi.

Contoh 2.

8

[Type text]

Tunjukkan bahwa pernyataan If (if P then Q) then (if not P then not Q) adalah valid

1

P benar P salah

BQ benar Q salah

S B

Dari pohon semantik di atas terlihat, untuk kemungkinan pertama yaitu P benar, tidak

perlu dibuat percabangan sebab bila P benar maka pernyataan akan selalu bernilai benar.

Untuk kemungkinan kedua (P salah dan Q benar) dan ketiga (P salah dan Q salah), pernyataan

tetap bernilai benar. Disimpulkan bahwa pernyataan di atas adalah tidak valid sebab ada yang

bernilai salah untuk sebarang interpretasi.

Pengandaian (Proof By Falsification)Dengan metoda ini, pertama kali justru pernyataan diandaikan tidak valid. Setelah itu

masing-masing simbol pernyataan diselidiki nilai kebenarannya. Bila ternyata terjadi kontradiksi,

berarti pengandaian semula (pengandaian bahwa pernyataan tidak valid) adalah salah dan

yang benar adalah bahwa pernyataan tersebut adalah valid.

Contoh 1.

Dengan pengandaian, selidiki validitas pernyataan P or not (P and Q).

P or not (P and Q) diandaikan S

S B B

Untuk disjungsi, nilai kebenaran S akan terjadi hanya kalau kedua pernyataan yang

dihubungkan juga bernilai salah. Setelah masing-masing simbol pernyataan diselidiki nilai

kebenarannya, terlihat bahwa ternyata terjadi kontradiksi sebab P memiliki nilai kebenaran B

dan S, jadi pengandaian semula salah. Pernyataan tersebut valid.

9

BS

[Type text]

Contoh 2.

Dengan pengandaian, selidiki validitas pernyataan :

(If P then not Q )if and only if not (P and Q)

Untuk bi-implikasi, nilai kebenaran S akan terjadi bila kedua pernyataan yang

dihubungkan memiliki nilai kebenaran yang tidak sama sehingga terdapat dua kemungkinan

nilai salah yaitu B if and only if S dan S if and only if B. Kedua kemungkinan tersebut harus

diselidiki validitasnya.

Kemungkinan 1 : B if and only if S

(If P then not Q )if and only if not (P and Q) diandaikan S

B S

B B B B

Setelah masing-masing simbol pernyataan diselidiki nilai kebenarannya, terlihat bahwa

ternyata terjadi kontradiksi sebab Q memiliki nilai kebenaran B dan S, jadi pengandaian semula

salah. Pernyataan tersebut valid.

Kemungkinan 2 : S if and only if B

(If P then not Q )if and only if not (P and Q) diandaikan S

S B

B S S B S

Setelah masing-masing simbol pernyataan diselidiki nilai kebenarannya, terlihat bahwa

ternyata terjadi kontradiksi sebab Q memiliki nilai kebenaran B dan S, jadi pengandaian semula

salah. Pernyataan tersebut valid.

Soal-soal LatihanSelidiki validitas pernyataan-pernyataan di abwah ini !

10

BS

SB

[Type text]

1. (if P then Q) or (if Q then P)

2. not Q or not [(if P then not Q) and P]

3. (if P then not Q) if and only if (P and Q)

4. [if P then (if Q then R)] if and only if [ (if P then R) and (if Q then R)]

5. [if (P or Q) then R] if and only if [(if P then R) and (if Q then R)]

2.5. ALJABAR PERNYATAANDefinisi Ekuivalen

Dua pernyataan disebut ekuivalen (kadang disebut ekuivalen secara logika) bila

keduanya memiliki tabel kebenaran yang identik.

Jika pernyataan P ekuivalen dengan pernyataan Q maka dituliskan dengan :

P QContoh 1.

Akan diselidiki apakah : not (P and Q) not P or not Q

P Q P and Q not (P and Q)

B B B S

B S S B

S B S B

S S S B

P Q not P not Q not P or not Q

B B S S S

B S S B B

S B B S B

S S B B B

Kolom terakhir kedua tabel di atas menunjukkan hasil yang identik. Disimpulkan bahwa :

not (P and Q) not P or not Q

Contoh 2.

Akan diselidiki apakah : P or Q not (not P and not Q)

P Q P or Q

11

[Type text]

B B B

B S B

S B B

S S S

P Q not P not Q not P and not Q not (not P and not Q)

B B S S S B

B S S B S B

S B B S S B

S S B B B S

Kolom terakhir kedua tabel di atas menunjukkan hasil yang identik. Disimpulkan bahwa :

P or Q not (not P and not Q)

Beberapa Hukum Aljabar Pernyataan Idempoten

(1a). P or P P (1b). P and P P

asosiatif

(2a). (P or Q) or RP or (Q or R) (2b). (P and Q) and RP and (Q and R)

komutatif

(3a). P or Q Q or P (3b). P and Q Q and P

distributif

(4a). P or (Q and R) (P or Q) and (P or R)

(4b). P and (Q or R) (P and Q) or (P and R)

identitas

(5a). P or S P (5b). P and B P

(6a). P or B B (6b). P and S S

komplemen

(7a). P or not P B (7b). P and not P S

(8a). not (not P) P (8b). not B S, not S B

12

[Type text]

De Morgan

(9a). not (P or Q) not P and not Q

(9b). not (P and Q) not P or not Q

Hukum-hukum aljabar pernyataan tersebut dapat digunakan untuk menunjukkan

ekuivalensi dua pernyataan.

Contoh 1.

Buktikan (P or Q ) and not P not P and Q

(P or Q ) and not P not P and (P or Q) (komutatif)

(not P and P) or (not P and Q) (distributif)

S or (not P and Q) (komplemen)

not P and Q (identitas)

Contoh 2.

Buktikan P or (P and Q) P

P or (P and Q) (P and B) or (P and Q) (identitas)

P and (B or Q) (distributif)

P and B (identitas)

P (identitas)

13

[Type text]

Soal-soal Latihan

Dengan hukum aljabar pernyataan, buktikan ekuivalensi ini.

1. not (P or Q) or (not P and Q) not P

2. P and (P or Q) P

3. P and (not P or Q) P and Q

4. (P and Q) or not P not P or Q

2.6. NEGASI DARI BEBERAPA KATA HUBUNG not (not P) P

not (P and Q) not P or not Q

not (P or Q) not P and not Q

not (if P then Q) P and not Q

not (P if and only if Q) P if and only if not Q not P if and only if Q

Contoh 1.

Negasi dari pernyataan : Andi tidak mempelajari Kalkulus adalah :

Andi mempelajari Kalkulus

Contoh 2.

Negasi dari pernyataan Andi mempelajari Kalkulus dan Manajemen adalah :

Andi tidak mempelajari Kalkulus atau tidak mempelajari manajemen

Contoh 3.

Negasi dari pernyataan Andi mempelajari Kalkulus atau Manajemen adalah :

Andi tidak mempelajari Kalkulus dan tidak mempelajari manajemen.

Contoh 4.

Negasi dari pernyataan Jika Andi belajar Kalkulus maka Andi belajar Manajemen adalah

:

Andi belajar Kalkulus dan tidak belajar Manajemen

Contoh 5.

14

[Type text]

Negasi dari pernyataan Andi belajar Kalkulus jika dan hanya jika Andi belajar

Manajemen adalah :

Andi belajar Kalkulus jika dan hanya jika Andi tidak belajar Manajemen

Andi tidak belajar Kalkulus jika dan hanya jika Andi belajar Manajemen.

Soal-soal Latihan

Tentukan negasi dari masing-masing pernyataan di bawah ini.

1. Jika dia belajar, dia akan lulus

2. Dino akan berenang jika dan hanya jika tidak hujan

3. Jika cuaca bersalju, dia tidak akan mengendarai mobilnya.

2.7. KUANTORyang disebut kuantor adalah simbol dalam logika yang digunakan untuk menyatakan

jumlah. Terdapat dua macam kuantor yaitu kuantor eksistensial dan kuantor universal.

Kuantor Eksistensial

Notasi : (x A), P

Dibaca : Terdapat x elemen A, sedemikian sehingga memiliki sifat P

Contoh 1.

(x R), x + 3 > 10

Dibaca : Terdapat x elemen bilangan real, sedemikian sehingga x + 30 > 10

Contoh 2.

(x N), x + 30 < -100

Dibaca : Terdapat x elemen bilangan asli, sedemikian sehingga x + 30 < -100

Kuantor Universal

Notasi : (x A), P

Dibaca : Untuk setiap x elemen A, berlaku sifat P

15

[Type text]

Contoh 1.

(x R), x + 0 = x

Dibaca : Untuk setiap x elemen bilangan real, berlaku x + 0 = x

Contoh 2.

(x R), x2 > 0

Dibaca : Untuk setiap x elemen bilangan real, berlaku x2 > 0

Negasi dari Kuantor

not ((x A), P) ( x A), not P

not ((x A), P) ( x A), not P

Contoh 1.

Negasi dari pernyataan Terdapat mahasiswa yang berambut keriting adalah :

Semua mahasiswa berambut tidak keriting

Contoh 2.

Negasi dari pernyataan : Semua mahasiswa menyukai kuliah Basis Data adalah:

Terdapat mahasiswa yang tidak menyukai kuliah Basis Data .

Contoh 3

Negasi dari pernyataan :Jika menjelang ujian, semua pealjaran dipelajari oleh Ani adalah :

Saat ini menjelang ujian dan terdapat pelajaran yang tidak dipelajari Ani

16

[Type text]

Contoh 4.

Negasi dari pernyataan Setiap mahasiswa menyukai musik atau olah raga adalah :

Terdapat mahasiswa yang tidak menyukai musik dan tidak menyukai olah raga.

Contoh 5.

Negasi dari pernyataan Terdapat mahasiswa yang menyukai musik dan olah raga adalah :

Setiap mahasiswa tidak menyukai musik atau tidak menyukai olah raga.

Soal-soal Latihan

Tentukan negasi dari masing-masing pernyataan di bawah ini.

1. (x N) (x + 3 = 10)

2. (x N) (x + 7 > 10)

3. (x R) (x+10 > 20)

4. Jika dosen tidak hadir, beberapa mahasiswa tidak mengerjakan tugas mereka

5. Setiap mahasiswa mengerjakan tugas mereka dan dosen hadir

6. Beberapa mahasiswa tidak mengerjakan tugas mereka atau dosen tidak hadir

2.8. ARGUMEN

Argumen adalah penegasan suatu kesimpulan (disebut konklusi) dari beberapa

pernyataan yang telah diketahui nilai kebenarannya (disebut premis).

Konklusi disimbolkan dengan Q, premis disimbolkan dengan P1, P2, …, Pn.

Suatu argumen dituliskan dengan :

P1, P2,…, Pn Q

Contoh 1.

P, if P then Q Q adalah sebuah argumen.

P dan if P then Q disebut premis sedangkan Q disebut konklusi.

Contoh 2.

If P then Q, If Q then R If P then R adalah sebuah argumen

17

[Type text]

If P then Q dan If Q then R adalah premis sedangkan If P then R disebut konklusi.

Validitas Argumen

Suatu argumen P1, P2,…, Pn Q adalah valid bila pernyataan :

If [ P1 and P2 and… and P3] then Q

adalah valid

Contoh 1.

Tentukan validitas argumen If P then Q, If Q then R If P then R

Untuk menyeldiki validitas argumen tersebut, argumen harus diubah menjadi sebuah

pernyataan yang berbentuk :

If [ If P then Q and If Q then R] then If P then R

Jika pernyataan tersebut valid maka argumen adalah valid dan bila pernyataan tidak

valid maka argumen juga tidak valid.

If [ If P then Q and If Q then R] then If P then R diandaikan S

B B B S

B S B S

Karena terjadi kontradiksi berarti pernyataan tersebut valid. Disimpulkan bahwa

argumen If P then Q, If Q then R If P then R juga valid.

Contoh 2.

Tentukan validitas argumen di bawah ini

Jika 7 lebih kecil dari 4, maka 7 adalah bukanbilangan prima

7 tidak lebih kecil dari 4

18

B S

[Type text]

7 adalah bilangan prima

Jika P : 7 lebih kecil dari 4 dan Q : 7 adalah bilangan prima, maka argumen di atas

dapat dituliskan sebagai :

If P then not Q, not P Q

Untuk menyeldiki validitas argumen tersebut, argumen harus diubah menjadi sebuah

pernyataan yang berbentuk :

If [ If P then not Q and not P] then Q

Jika pernyataan tersebut valid maka argumen adalah valid dan bila pernyataan tidak

valid maka argumen juga tidak valid.

If [ If P then not Q and not P] then Q diandaikan S

B B

B B

S B/S S S

Karena ada yang tidak terjadi kontradiksi berarti pernyataan tersebut tidak valid.

Disimpulkan bahwa argumen If P then not Q, not P Q juga tidak valid.

19

[Type text]

Soal-soal Latihan

Tentukan validitas argumen-argumen di bawah ini.

1. Jika 5 bilangan prima, maka 5 adalah bukan pembagi dari 15

5 adalah pembagi dari 15

5 bukan bilangan prima

2. Jika hari hujan, maka Ali akan sakit

Hari ini tidak hujan

Ali tidak sakit

20

[Type text]

Pertemuan Minggu Ke-2TEORI HIMPUNAN

Konsep himpunan adalah salah satu konsep mendasar dalam semua cabang ilmu

matematika

1.1. DEFINISI HIMPUNANHimpunan adalah setiap daftar, kumpulan atau kelas objek-objek yang didefinisikan

secara jelas. Objek-objek dalam himpunan dapat berupa apa saja dan disebut sebagai elemen

atau anggota suatu himpunan.

Meskipun nantinya akan dipelajari himpunan sebagai kesatuan-kesatuan yang abstrak,

di bawah ini disajikan contoh-contoh khusus mengenai himpunan.

Contoh 1 : Bilangan 1,3,5,7,9

Contoh 2 : Bilangan ganjil positif yang lebih kecil dari 10

Contoh 3 : Andi, Beni, Cici, Dita

Contoh 4 : Mahasiswa yang tidak masuk kuliah hari ini

Dengan memperhatikan contoh-contoh di atas, dapat dilihat bahwa himpunan dapat

didefinisikan dengan dua cara yaitu :

1. Mendaftar anggota-anggotanya (contoh 1 dan 3)

2. Mendefinisikan aturan atau sifat dari angoota-anggotanya (contoh 2 dan 4)

1.2. NOTASI HIMPUNANHimpunan selalu dinyatakan dengan huruf besar misalnya himpunan A, B, X, Y dan

sebagainya. Elemen atau anggota suatu himpunan dinyatakan dengan huruf kecil, misalnya a,

b, x, y dan sebagainya. Elemen-elemen tersebut ditulis dalam tanda kurung kurawal { }.

Contoh :

A = {1,3,5,7,9,11}

21

[Type text]

B = {xx bilangan ganjil positif dan x < 12}

Jika suatu objek x adalah elemen dari himpunan A, maka A mengandung x sebagai

salah satu elemennya dan dinotasikan dengan :

X A ( dibaca : x termasuk/di dalam himpunan A)

1.3. KESAMAAN DUA HIMPUNANDua himpunan dikatakan sama bila keduanya memiliki elemen yang sama

Contoh :

- Jika A = {3,4} dana B = {4,3} maka A=B

- Jika P = {1,2,3} dan Q = {3,3,2,1,1} maka P=Q

- Jika M = {5,6,7} dan N = {6,7} maka M N

1.4. HIMPUNAN BAGIANHimpunan A disebut himpunan bagian dari himpunan B bila A tercakup dalam B.

Terdapat dua macam simbol untuk himpunan bagian yaitu :

- A B : A adalah himpunan bagian dari B, jadi setiap elemen A adalah elemen B

juga. Tetap ada kemungkinan bahwa A=B

- A B : A adalah himpunan bagian sejati dari B, jadi setiap elemen A adalah

elemen B juga tetapi A B

Teorema Himpunan Bagian1. untuk sebarang himpunan A berlaku A S

2. untuk sebarang himpunan A berlaku A A

3. jika A B dan B C maka A C

4. A=B jika dan hanya jika A B dan B A

1.5. OPERASI HIMPUNANGabungan (Union)

22

[Type text]

Gabungan dua himpunan A dan B, disimbolkan A B, adalah himpunan yang elemen-

elemennya merupakan elemen A atau elemen B.

A B = {x x A atau x B}

Contoh : Jika diketahui A = { xx real, x < -2} dan B = { xx real, x > 5} maka

A B = {x x real, x <-2 atau x >5}

Irisan (Intersection)Irisan dua himpunan A dan B, disimbolkan A B, adalah himpunan yang elemen-

elemennya merupakan elemen A dan elemen B.

A B = {x x A dan x B}

Contoh : Jika diketahui A = { xx real, x > -2} dan B = { xx real, x > 5} maka

A B = {x x real, x > -2 dan x >5} = {x x real, x >5}

Komplemen Absolut dan Komplemen RelatifKomplemen absolut (secara singkat disebut komplemen) dari himpunan A, disimbolkan

A’, adalah himpunan yang memuat elemen-elemen S (himpunan semesta) yang bukan

merupakan elemen himpunan A

Komplemen relatif dari dua himpunan A dan B, disimbolkan A\B adalah himpunan yang

memuat elemen-elemen A yang bukan merupakan elemen B.

Contoh : Jika diketahui S = {1,2,3,4,5,6}, A = {1,2,3,4} dan B = {1,3,5} maka

A’ = {5,6}, B’ = {2,4,6}, A\B = {2,4}, B\A = {5}

Hukum-hukum Yang Berlaku pada Operasi Himpunan Idempoten

(1a). A A = A (1b). A A = A

asosiatif

(2a). (A B) C = A(BC) (2b). (A B) C = A(BC)

23

[Type text]

komutatif

(3a). A B = B A (3b). A B = B A

distributif

(4a). A (B C) = (AB) (AC)

(4b). A (B C) = (AB) (AC)

identitas

(5a). A = A (5b). A S= A

(6A). A S = S (6b). A = S

involusi

(7a). (A’)’ = A

komplemen

(8a). A A’ = A (8b). A A’ =

(9a). S’ = (9b). ‘ = S

De Morgan

(10a). (A B)’ = A’ B’ (10b). (A B)’ = A’ B’

1.6. HIMPUNAN BERHINGGA DAN TAK BERHINGGAHimpunan dapat berhingga dapat pula tak berhingga. Secara intuitif, himpunan disebut

berhingga bila terdiri dari sejumlah tertentu elemen yang berbeda. Artinya, bila elemen yang

berbeda dari himpunan ini dihitung, maka proses penghitungannya dapat berakhir. Bila tidak

demikian, maka himpunannya adalah tak berhingga.

Contoh himpunan berhingga :

a. A = {x x ganjil dan -5 < x < 10}

b. B = {y y bilangan bulat dan y2 + 1 = 10}

c. C = {t t gunung di dunia}

24

[Type text]

Contoh himpunan tak berhingga :

a. P = {p p bilangan real, 2<p<20}

b. R = {r r bilangan bulat, r+2 >4}

Bila A adalah sebuah himpunan berhingga maka banyak elemen dari A disimbolkan

dengan n(A).

Contoh :

a. A = {x x bil.bulat, -5<x<4} = { -4, -3,- 2, -1, 0, 1, 2, 3} n(A) = 8

b. B = {y y bilangan bulat, y2 + 1 = 10} = {-3, 3} n(B) = 2

Jika diketahui bahwa A, B dan C adalah himpunan-himpunan berhingga maka berlaku :

1. A B dan A B adalah himpunan berhingga dan

n (A B) = n(A) + n(B) – n(A B)

2. Jika A dan B saling lepas maka A B adalah berhingga dan

n (A B) = n(A) + n(B)

3. A B C adalah himpunan berhingga dan

n (ABC) = n(A) + n(B) +n(C) – n(AB) – n(AC) – n(BC) + n(ABC)

Contoh 1.

Pada suatu pertemuan hadir 22 pria dan 18 wanita. Berapa orang keseluruhan yang

hadir pada pertemuan tersebut?

Misalkan P = {pria yang hadir} dan W = {wanita yang hadir} maka P dan W adalah

dua himpunan yang saling lepas dan diketahui bahwa n(P)=22 dan n(W) = 18

sehingga n(PW) = n(P) + n(W) = 22 + 18 = 40

Contoh 2.

Di sebuah perusahaan daur ulang terdapat 32 orang yang bertugas mengumpulkan

kertas atau botol, 30 orang mengumpulkan kertas dan 14 orang mengumpulkan botol.

Tentukan banyaknya orang yang :

a. Mengumpulkan kertas dan botol

b. Mengumpulkan kertas saja

c. Mengumpulkan botol saja

25

[Type text]

Misalkan K = {pengumpul kertas} n(K) = 30

B = {pengumpul botol} n(B) = 14

(KB) = {pengumpul kertas atau botol} n(KB) = 32

a. pengumpul kertas dan botol = K B

n (KB) = n(K) + n(B) – n(KB) = 30 + 14 – 32 = 12

b. pengumpul kertas saja = K\B

n(K\B) = n(K) – n(KB) = 30 – 12 = 18

c. pengumpul botol saja = B\K

n(B\K) = n(B) – n(KB) = 14 – 12 = 2

1.7. SOAL-SOAL LATIHAN

1. Pada himpunan semesta mahasiswa diketahui himpunan-himpunan berikut :

A = {mahasiswa Teknik Informatika}

B = {mahasiswa semester 3}

C = {mahasiswa yang berkacamata}

Tentukan anggota dari masing-masing himpunan di bawah ini :

a. AB c. B\C e. (AB)\C’

b. AC d. B’ f. B\ (AC)

2. Pada himpunan semesta mahasiswa diketahui himpunan-himpunan berikut :

P = {mahasiswa Teknik Informatika}

Q = {mahasiswa yang suka membaca}

R = {mahasiswa yang menyukai musik}

Tuliskan himpunan yang anggotanya adalah :

a. mahasiswa Teknik Informatika yang tidak menyukai musik

b. mahasiswa Teknik Informatika yang menyukai musik dan suka membaca

c. mahasiswa Teknik Informatika yang suka membaca atau musik

3. Pada himpunan bilangan real diketahui A={x -3<x<4}, B={x x 2}. Tentukan :

a. AB c. A’ e. A\B

26

[Type text]

b. AB d. B’ f. B\ A

4. Pada himpunan bilangan real diketahui A = {x-3 < x < 4} dan B={x -6 x 2}.

Tentukan :

a. AB c. A’ e. A\B

b. AB d. B’ f. B\ A

5. 10 keluarga ditanyai, hewan apa yang mereka pelihara di rumah. Ternyata 6 keluarga

memelihara anjing, 4 keluarga memelihara kucing, 2 keluarga tidak memelihara anjing

maupun kucing. Tentukan banyak keluarga yang memelihara anjing dan kucing.

6. Pada sekumpulan mahasiswa Teknik Informatika di suatu kelas ditanyakan bahasa

pemrograman apa yang mereka kuasai, PASCAL (P) atau BASIC (B). Jawaban yang

diperoleh adalah, 65 orang mahasiswa menguasai PASCAL, 15 orang tidak menguasai

PASCAL, 16 orang menguasai BASIC, 5 orang tidak menguasai PASCAL dan BASIC.

Tentukan banyak mahasiswa yang :

a. ada di kelas tersebut

b. menguasai PASCAL dan BASIC

c. hanya menguasai PASCAL

Pertemuan Minggu Ke-327

[Type text]

R E L A S I

3.1. PERKALIAN HIMPUNAN DAN PASANGAN BERURUTANPerkalian Himpunan

Perkalian dua himpunan didefinisikan sebagai berikut :

A x B = (x,y) (x A) dan (y B)}

Pasangan Berurutan

Pasagan berurutan berisi dua objek dengan urutan tetap. Dua pasanagan

berurutan disebut sama bila memenuhi :

(x,y) = (u,v) jika dan hanya jika ((x=u) dan (y=v))

3.2. DEFINISI RELASI

Relasi dari himpunan A ke himpunan B adalah himpunan bagian R dari A x B.

Jika a A dan b B maka :

a berelasi dengan b disimbolkan dengan a R b dan hal ini berarti bahwa (a,b) R

a tidak berelasi dengan b disimbolkan dengan a R b dan hal ini berarti bahwa (a,b) R.

Contoh 1.

Bila diketahui A={a,b,c} dan B = {1,2} maka di bawah ini adalah relasi-relasi dari A ke B.

a. R1 = {(a,1), (a,2) (c,2)}

b. R2 = {(a,2), (c,2)}

c. R3 = {(b,1)}

Karena relasi R adalah himpunan bagian dari A x B maka banyak relasi dari A ke B adalah

= 2n(A).n(B).

Contoh 2.

28

[Type text]

Bila diketahui A={a,b,c} dan B = {1,2} maka n(A) = 3 dan n(B) =2 sehingga banyak relasi

dari A ke B adalah 23.2. = 26 = 64.

3.3. INVERS

Invers dari relasi R, disimbolkan dengan R-1 adalah relasi dari B ke A dan memenuhi

sifat :

R-1 = {(b,a) (a,b) R}

Contoh

Invers dari relasi-relasi pada contoh 1 adalah :

a. R1-1 = {(1,a), (2,a) (2,c)}

b. R2-1= {(2,a), (2,c}

c. R3-1 = {(1,b)}

3.4. BEBERAPA JENIS RELASIRelasi Refleksif

Suatu relasi R disebut refleksif bila untuk setiap a A berlaku a R a ( a berelasi dengan

a)

Jadi, suatu relasi disebut tidak refleksif bila terdapat a A sedemikan sehingga a tidak

berelasi dengan a.

Contoh :

Diketahui himpunan A = {1,2,3}

a. R1 = {(1,1), (1,2), (1,3), (3,3)}

b. R2 = {(1,1), (1,2), (2,1), (2,2), (3,3)}

c. R3 = {(1,1), (1,2), (2,2), (2,3)}

Pada contoh di atas, R1 tidak refleksif sebab (2,2) R1. R3 juga tidak refleksif

sebab (3,3) R3. R2 refleksif sebab (1,1), (2,2) dan (3,3) R2

Relasi SimetrisSuatu relasi R disebut simetris bila memenuhi sifat berikut ini :

Jika a R b maka b R a

29

[Type text]

Suatu relasi disebut tidak simetris bila terdapat (a, b) R tetapi (b,a) R.

Contoh :

Diketahui himpunan A = {1,2,3}

a. R1 = {(1,1), (1,2), (1,3), (3,3)}

b. R2 = {(1,1), (1,2), (2,1), (2,2), (3,3)}

c. R3 = {(1,1), (1,2), (2,2), (2,3)}

Pada contoh di atas, R1 tidak simetris sebab (1,2) R1 tetapi (2,1) R1. . R3 juga

tidak simetris sebab (1,2) R3 tetapi (2,1) R3. R2 simetris.

Relasi Anti - SimetrisSuatu relasi R disebut anti/ tidak simetris bila memenuhi sifat berikut ini : Jika a R b dan b R a maka a=bSuatu relasi disebut tidak anti simetris bila terdapat (a,b) R dan (b,a) R tetapi a b

Contoh :

Diketahui himpunan A = {1,2,3}

a. R1 = {(1,1), (1,2), (1,3), (3,3)}

b. R2 = {(1,1), (1,2), (2,1), (2,2), (3,3)}

c. R3 = {(1,1), (1,2), (2,2), (2,3)}

Pada contoh di atas, R2 tidak antisimetris sebab (1,2) R2 dan (2,1) R2 dan 1

2. R1 dan R3 anti simetris.

30

[Type text]

Relasi TransitifSuatu relasi R disebut transitif bila memenuhi sifat berikut ini : Jika a R b dan b R c maka a R cSuatu relasi disebut tidak transitif bila terdapat (a,b) dan (b,c) di dalam R tetapi (a,c) tidak di

dalam R

Contoh :

Diketahui himpunan A = {1,2,3}

a. R1 = {(1,1), (1,2), (1,3), (3,3)}

b. R2 = {(1,1), (1,2), (2,1), (2,2), (3,3)}

c. R3 = {(1,1), (1,2), (2,2), (2,3)}

Pada contoh di atas, R3 tidak transitif sebab (1,2) R3 dan (2,3) R3 tetapi (1,3)

R3. R1 dan R2 transitif

Relasi EkuivalenSuatu relasi R disebut ekuivalen bila R sekaligus refleksif, simetris dan transitif.

Contoh :

R adalah relasi pada himpunan bilangan bulat dan didefinisikan :

a R b = (a-b) habis dibagi 3Apakah R relasi ekuivalen ?

Jika R relasi ekuivalen maka R harus refleksif, simetris dan transitif.

o Refleksif a R a

a R a = (a-a) habis dibagi 3 (benar)

Jadi,R adalah relasi yang refleksif

o Simetris Jika A R b maka b R a

a R b = (a-b) habis dibagi 3

b R a = (b-a) habis dibagi 3 = -(a-b) habis dibagi 3

Jika (a-b) habis dibagi 3 maka (b-a) juga habis dibagi 3. Jadi R adalah relasi

yang simetris

o Transitif Jika a R b dan b R c maka a R c

a R b = (a-b) habis dibagi 3

31

[Type text]

b R c = (b-c) habis dibagi 3

a R c = (a-c) habis dibagi 3 = (a-b) + (b-c) habis dibagi 3

Jika (a-b) dan (b-c) habis dibagi 3 maka (a-c) juga habis dibagi 3. Jadi, R adalah

relasi yang transitif.

Karena R adalah relasi yang refleksif, simetris dan transitif maka R ekuivalen.

Soal-soal Latihan 1. Diketahui A = {red, blue, white, brown, black, green, yellow} dan B={bilangan bulat

positif}. Relasi R adalah A x B dan (a,b) R jika dan hanya jika a adalah kata-kata

dan b adalah jumlah konsonan dalam kata tersebut. Tentukan R.

2. Diketahui A = {red, blue, white, brown, black, green, yellow} dan B={bilangan bulat

positif}. Relasi R adalah A x B dan (a,b) R jika dan hanya jika a adalah kata-kata

dan b adalah jumlah vokal dalam kata tersebut.Tentukan R.

3. Diketahui A = {1,2,3,4,5,6} dan B={bilangan bulat positif}. Relasi R adalah A x B dan

(a,b) R jika dan hanya jika b = a +4.Tentukan R.

4. Diketahui A = {1,2,3,4,5,6} dan B={1,3,5,7,9}. Relasi R adalah A x B dan (a,b) R jika

dan hanya jika a < b.Tentukan R.

Untuk masing-masing relasi, tentukan apakah refleksif, simetris, antisimetris dan

ekuivalen.

5. A = {1,2,3,4} dan R = {(1,1), (2,2), (2,3), (3,2), (4,2), (4,4)}

6. B = {garis pada bidang 2 dimensi} dan a R b = a tegak lurus b

7. C = {himpunan buku di perpustakaan} dan a R b = a lebih tebal dari b

32

[Type text]

Pertemuan Minggu Ke-4F U N G S I

4.1. DEFINISI FUNGSISuatu himpunan bagian f dari A x B (perkalian himpunan A dan B) disebut fungsi dari A

ke B jika setiap anggota A muncul hanya satu kali sebagai koordinat pertama pasangan terurut

di f :

Perhatikan bahwa ada beberapa cara untuk mendefinisikan fungsi. Ada yang

mendefinisikan sebagai aturan yang memasangkan setiap anggota A dengan tepat satu

anggota B. Dalam diktat ini fungsi didefinisikan sebagai suatu relasi sedemikian hingga tidak ada dua anggota berbeda yang memiliki elemen pertama yang sama. Dalam pengertian

lebih lanjut fungsi didefinisikan sedikit berbeda dari yang didiskusikan dalam buku ini.

Jika f menyatakan pemasangan ini (juga himpunan bagian dari A x B) maka ditulis f : A

B (baca : f adalah fungsi dari A ke dalam B). Anggota B yang menjadi pasangan a oleh f

dinyatakan sebagai b = f(a), yang berarti (a,b) f.

4.2. DOMAIN, KODOMAIN, RANGEHimpunan A disebut domain (daerah asal) dari fungsi f atau Dom(f) atau D(f). B disebut kodomain (daerah kawan) dari f atau Cod(f) atau C(f). Jika a A maka

anggota B yang menjadi pasangan a disebut image (bayangan) a oleh f dan dinyatakan b = f(a) (baca : f dari a).

Sedang himpunan semua anggota B yang menjadi pasangan a disebut range (daerah

hasil) fungsi f atau Ran(f) atau f(A). Perhatian : Bedakan antara f(a) dengan f(A). Ingat bahwa

range f, yaitu f(A) adalah subset dari B atau f(A) B. Sedang perbedaan antara definisi fungsi

yang digunakan dalam diktat ini dengan definisi fungsi yang lebih lanjut terletak pada domain f.

Pada definisi di atas, D(f) = A, sedang pada definisi yang lebih lanjut, D(f) X. Suatu fungsi f

dengan D(f) = x sering disebut terdefinisi pada X

Contoh 1 :

33

[Type text]

Ditentukan A = {1, 2, 3, 4} dan B = {5,6,7}

Didefinisikan fungsi f : A B sebagai f(1) = 5, f(2) = 7, f(3) = 5, f(4) = 5

a. Nyatakan fungsi f sebagi pasangan terurut

b. Tentukan range f.

a. .f = {(1, 5), (2, 7), (3, 5), (4, 5)}

b. Range f = {5, 7}

4.3. FUNGSI YANG SAMAJika f dan g adalah fungsi yang sama didefinisikan pada domain D maka fungsi f dan g

dikatakan sama (ditulis: f = g) jika dan hanya jika f(a) = f(g) untuk setiap a D.Dengan kata lain : Dua buah fungsi f dan g dikatakan sama jika dan hanya jika D(f) = D(g) dan f(x) = g(x)

untuk semua x dalam domain yang bersangkutan.

Contoh 2 :

Apakah fungsi f(x) = x2 yang didefinisikan pada himpunan bilangan real R# sama dengan

fungsi g(x) = x2 yang didefinisikan pada himpunan bilangan kompleks C?

Fungsi f(x) g(x) karena domain kedua fungsi itu tidak sama.

Contoh 3 :

Jika f : R# R# dan g : R# R# serta f didefinisikan sebagai f(x) = x2, sedang g didefinisikan

sebagai g(y) = y2, apakah f dan g fungsi yang sama ?

Fungsi f dan g merupakan fungsi yang sama, karena domain rumus fungsinya yang

sama. Perhatikan bahwa x dan y hanya merupakan variabel saja (dummy variables)

4.4. MACAM-MACAM FUNGSIFungsi Onto (Fungsi Surjektif)

Suatu fungsi f dari himpunan A ke himpunan B dikatakan fungsi onto (fungsi kepada)

jika dan hanya jika range f sama dengan B atau f(A) = B

Fungsi f yang bukan fungsi onto dikatakan fungsi into (fungsi ke dalam). Yaitu apabila

Ran(f) B atau Ran(f) merupakan himpunan bagian sejati dari B.

34

[Type text]

Contoh 4 :Ditentukan fungsi g : P P yang didefinisikan sebagi diagram panah berikut ini :

1 1

2 2

A A

Apakah fungsi g merupakan fungsi onto ?

Fungsi g bukan merupakan fungsi onto karena g(p) = {2} A merupakan subset dari P

Contoh 5 :

Ditentukan A = {1, 2, 3, 4} dan B = {5, 6, 7}. Didefinisikan fungsi

f : A B sebagi f(1) = 5, f(2) = 7, f(3) = 5, f(4) = 6. Apakah f merupakan fungsi onto ?

Ya, karena f(A) = B

Fungsi Satu-Satu (Fungsi Injektif)Fungsi f disebut fungsi satu-satu jika dan hanya jika tidak ada anggota yang berbeda di

A mempunyai bayangan yang sama. Jelasnya f : A B fungsi satu-satu jika dan hanya jika f(a)

= f(a’) maka a = a’. Pernyataan ini ekivalen dengan jika a a’ maka f(a) f(a’)

Contoh 6 :

Ditentukan fungsi g : A A yang didefinisikan sebagai diagram panah berikut :

1 1

2 2

3 3

A A

Apakah fungsi g merupakan fungsi satu-satu ?

35

[Type text]

Fungsi g bukan merupakan fungsi satu-satu karena g(a) = g(c) = b, padahal a c

Fungsi Bijektif (Korespondensi Satu-Satu)Fungsi f disebut fungsi bijektif jika dan hanya jika fungsi f sekaligus merupakan fungsi

onto (surjektif) dan fungsi satu-satu (injektif)

Ada yang menyebut fungsi bijektif sebagai korespondensi satu-satu.

Contoh 7 :

Ditentukan fungsi g : A A yang didefinisikan sebagai diagram panah berikut :

1 1

2 2

3 3

A A

Apakah fungsi g merupakan fungsi bijektif ?

Ya, karena fungsi g merupakan fungsi surjektif, yaitu g(A) = A dan juga merupakan

fungsi injektif, yaitu setiap anggota A yang berbeda mempunyai bayangan berbeda.

Contoh 8 :Apakah fungsi f yang memetakan setiap negara dengan benderanya merupakan fungsi

satu-satu ?

Ya, karena fungsi f merupakan fungsi surjektif dan juga fungsi injektif, setiap negara

mempunyai benderanya sendiri, negara yang berbeda mempunyai bendera yang

berbeda.

Fungsi IdentitasA adalah sebarang himpunan. Fungsi f pada A disebut fungsi identitas jika dan hanya

jika f mengawankan setiap anggota A dengan dirinya sendiri. Jelasnya f : A A dan f

dirumuskan sebagai f(x) = x maka f disebut fungsi identitas. Fungsi identitas ini biasanya dinyatakan sebagai I.

36

[Type text]

Contoh 9 :

Gambarkan diagram panah fungsi identitas I yang didefinisikan pada A = {a, b, c, d, e}

berikut :

a a

b b

c c

d d

e e

A A

Fungsi KonstanFungsi f pada A ke B disebut fungsi konstan jika dan hanya jika hanya satu anggota B

menjadi pasangan dari setiap anggota A. Dengan kata lain, f : A B konstan jika dan hanya

jika range f hanya mempunyai satu anggota.

Contoh 10 :

Jika A = {1, 2, 3} dan B = {a, b, c}, buatlah diagram panah untuk fungsi konstan dari A ke

B. Ada berapa macam fungsi konstan yang dapat dibuat.

Ada 3 macam fungsi konstan yang dapat dibuat.

1 a

2 b

3 c

A B

1 a

37

[Type text]

2 b

3 c

A B

1 a

2 b

3 c

A B

38

[Type text]

4.5. KOMPOSISI FUNGSI (PERKALIAN FUNGSI)Ditentukan f adalah fungsi dari A ke B dan g adalah fungsi dari B (kodomain dari f) ke C.

Maka fungsi {(a,c)|ada elemen b B sedemikian hingga (a,b) f dan (b,c) g} dari A ke C

disebut komposisi fungsi atau perkalian fungsi f dan g dan dinyatakan sebagai (gof) atau (gf)

Jelasnya, jika , f : A B dan g : B C maka didefinisikan fungsi

(gof) : A C dengan (gof)(a) g(f(a))

Perkalian himpunan f dan g dapat diilustrasikan sebagai diagram berikut ini :

f g

gof

Contoh :Ditentukan f : A B dan g : B C didefinisikan oleh diagram

a p u

b q v

c r w

A B C

Carilah (gof)(a), (gof)(b), (gof)(c)

(gof)(a) g(f(a)) = g(q) = w

(gof)(b) g(f(b)) = g(p) = w

(gof)(c) g(f(c)) = g(p) = v

Sifat Asosiatif Komposisi Fungsi

39

A B C

[Type text]

Jika f adalah fungsi dari A ke B, g adalah fungsi dari B ke C dan h adalah fungsi dari C

ke D, maka :

ho(gof) = (hog)of

Sifat asosiatif perkalian fungsi ini dapat ditunjukkan dengan diagram

1. Dibentuk perkalian fungsi gof : A C, lalu fungsi ho(gof) : A D

f g h

A B C D

gof

ho(gof)

2. Kita bentuk perkalian fungsi hog : B D, lalu fungsi (hog)of : A D

f g h

A B C D

gof

ho(gof)

Perkalian fungsi ho(gof) dan (hog)of adalah fungsi A ke D

4.6. INVERS SUATU FUNGSIDitentukan f adalah suatu fungsi dari A ke B. Jika f : A B merupakan fungsi satu-satu

dan juga merupakan fungsi onto maka untuk setiap b B, invers dari b, yaitu f –1(b) merupakan

himpunan yang terdiri dari hanya satu anggota A, sebab setiap anggota B mempunyai kawan f –

1(b) yang tunggal di A.

Karena itu f –1 merupakan fungsi B ke A, yang ditulis f –1 : B A, dan f –1 merupakan

fungsi invers dari f.

40

[Type text]

Jadi f –1 : B A merupakan fungsi invers f jika dan hanya jika f : A B merupakan

fungsi satu-satu dan onto.

Contoh :Jika f : P Q didefinisikan sebagai diagram panah berikut ini :

Apakah f mempunyai fungsi invers ?

a f

b p

c q

P Q

Karena f(a) = q dan f(c) = q maka f bukan fungsi satu-satu, walaupun merupakan

fungsi onto maka f tidak mempunyai fungsi invers.

Contoh :

Jika f : A B didefinisikan sebagai diagram panah berikut ini :

Apakah f mempunyai fungsi invers ? Buat diagram panahnya.

a f p

b q

c r

A B

41

[Type text]

Karena f merupakan fungsi satu-satu dan onto maka f mempunyai fungsi invers, yang

diagramnya :

p f a

q b

r c

A B

Soal-soal LatihanUntuk masing-masing fungsi, tentukan apakah injektif dan surjektif

1. f (x) = x2, x bilangan real

2. g (t) = t3, t bilangan real

3. h(z) = log z, z bilangan real

Untuk masing-masing fungsi, tentukan fog dan gof.

4. f(x) = 4x + 7, g(x) = 5x2 –3

5. f(x) = 4-x2, g(x) = 6x2+8

1. f (x) = x2, x bilangan real

a. Fungsi f injektif jika dan hanya jika f(a) = f(a’) maka a = a’. Pernyataan ini ekivalen

dengan jika a a’ maka f(a) f(a’)

Untuk sembarang/setiap x1,x2 anggota bilangan real, jika f(x1) = f(x2)

maka x1 =x2

f(x1) = f(x2)

x12 = x2

2

x12 - x2

2 = 0

a2-b2 = (a+b)(a-b)

x12 - x2

2 = (x1 + x2 )(x1 - x2

)= 0

x1 + x2 = 0 , x1 - x2 = 0, x1 = x2

x1 = -x2 ≠ x2 , artinya ada x1 ≠ x2 jadi fungsi f tidak injektif

b. fungsi onto (fungsi surjektif/ kepada) jika dan hanya jika range f sama dengan B atau

f(A) = B

f (x) = x2, x bilangan real

42

[Type text]

f fungsi surjektif jika untuk setiap f(x) bilangan real dapat ditemukan/ ada x bilangan real

sehingga

f (x) = x2= y

x = √ y , jika y bil.real maka √ y bil. Real

artinya ada x bil. Real sehingga x=√ y juga bil. real, jadi f fungsi surjektif.

43

[Type text]

Pertemuan Minggu Ke-5Induksi Matematika

Induksi Matematika adalah cara standar dalam membuktikan bahwa sebuah pernyataan tertentu berlaku untuk setiap bilangan asli. Pembuktian dengan cara ini terdiri dari dua langkah, yaitu:

1. Menunjukkan bahwa pernyataan itu berlaku untuk bilangan 1 suku ke satu.2.`Menunjukkan bahwa jika pernyataan itu berlaku untuk bilangan n, maka pernyataan itu

juga berlaku untuk bilangan n + 1.

Misalkan akan dibuktikan suatu pernyataan bahwa jumlah n bilangan asli pertama, yaitu 1+2+:::+n, adalah sama dengan n(n+1)/2 . Untuk membuktikan bahwa pernyataan itu berlaku untuk setiap bilangan asli, langkah-langkah yang dilakukan adalah sebagai berikut:1. Menunjukkan bahwa pernyataan tersebut benar untuk n = 1. Jelas sekali bahwa jumlah 1

bilangan asli pertama adalah 1(1+1)/2 = 1. Jadi pernyataan tersebut adalah benar untuk n = 1.

2. Menunjukkan bahwa jika pernyataan tersebut benar untuk n = k, maka pernyataan tersebut juga benar untuk n = k+1. Hal ini bisa dilakukan dengan cara:

- Mengasumsikan bahwa pernyataan tersebut benar untuk n = k, yaitu 1 + 2 + ::: + k = k(k + 1)/2

- Menambahkan k + 1 pada kedua ruas, yaitu 1 + 2 + ::: + k + (k + 1) =k(k + 1)/2 + (k + 1)

- Dengan menggunakan manipulasi aljabar, diperoleh k(k + 1)/2 + (k + 1) = k(k + 1)/2 + 2(k + 1)/2 = (k + 1)(k + 2)/2 = (k + 1)((k + 1) + 1)/2

- Dengan demikian 1 + 2 + ::: + k + (k + 1) =(k + 1)((k + 1) + 1)/2

- Jadi pernyataan tersebut benar untuk n = k + 1.

3. Dengan induksi matematika dapat disimpulkan bahwa pernyataan tersebut berlaku untuk setiap bilangan asli n.

Secara formal Induksi Matematika ini bisa didefinisikan sebagai berikut.

44

[Type text]

Defnisi 1.1Misalkan untuk setiap bilangan asli n kita mempunyai pernyataan P(n) yangbisa benar atau salah. Misalkan

1. P(1) benar.2. Jika P(n) benar, maka P(n + 1) benar.

Sehingga P(n) benar untuk setiap bilangan asli n.Langkah 1 disebut dengan Langkah Dasar, sedangkan Langkah 2 disebut dengan Langkah Induktif.

Jika pada Langkah Induktif yang diasumsikan adalah pernyataan P(i) benar untuk setiap bilangan i n, maka perumusan induksi matematika seperti ini disebut Bentuk Kuat Induksi Matematika.

Contoh 1.1Gunakan induksi matematika untuk membuktikan bahwa

n! 2n-1

untuk setiap n = 1; 2; :::.1. Akan ditunjukkan bahwa n! 2n-1 benar untuk n = 1. Jelas sekali bahwa 1! = 1 1 = 20= 21-1.

2. Asumsikan bahwa n! 2n-1 adalah benar untuk n = k. Akan ditunjukkan bahwa n! 2n-1 juga benar untuk n = k + 1, yaitu (k + 1) ! 2(k+1)-1

(k + 1)! = (k + 1)(k!)K! 2k-1

K=1.2.3...K+1= 2,3,4,... 2K+1 2 (k + 1)(k!) 2.(2k-1) 21.2k-1

= 21+(k-1)

= 2(k+1)-1

Terbukti bahwa (k+1) 2(k+1)-1. Karena Langkah Dasar dan Langkah Induktif terbukti, maka dapat disimpulkan bahwa

n! 2n-1

untuk setiap n = 1; 2; …..

Contoh 1.2Gunakan induksi matematika untuk membuktikan bahwa 5n - 1 dapat dibagi 4 untuk setiap n = 1; 2; ….

1. Akan ditunjukkan bahwa 5n - 1habis dibagi 4 untuk n = 1. Jelas sekali bahwa 51-1 = 5 - 1 = 4 habis dibagi 4.

2. Asumsikan bahwa 5n - 1 habis dibagi 4 untuk n = k, yaitu 5k - 1 habis dibagi 4. Akan ditunjukkan bahwa 5n - 1 juga habis dibagi 4 untuk n = k + 1, yaitu 5k+1 - 1 habis dibagi 4.

5k+1 - 1 = 5.5k- 1 = (1 + 4) 5k- 1

45

[Type text]

=1. 5k + 4. 5k- 1 = (5k- 1) + 4.5k

Berdasarkan asumsi, 5k- 1 habis dibagi 4. Sedangkan 4.5k juga habis dibagi 4. Dengan demikian 5k+1-1 habis dibagi 4. Karena Langkah Dasar dan Langkah Induktif terbukti, maka dapat disimpulkan bahwa 5n- 1 dapat dibagi 4 untuk setiap n = 1; 2;…

Latihan

Gunakan induksi matematika untuk membuktikan persamaan berikut ini benaruntuk setiap bilangan asli n.

1.1 .2 + 2 .3+ 3 . 4 +……….+ n (n+1 ) = n (n+1)(n+2 )

3

2. 1 .1(1! ) + 2 (2! )+…. .+ n (n! ) =(n+1 )! 1

3.12 - 22 + 32 - …… +( -1 )n+1 n2 =(−1 )n+1 n(n+1 )

2

4.13+23+33+…. .+ n3 =[ n (n+1)

2 ]2

Gunakan induksi matematika untuk membuktikan pertidaksamaan berikutini.

5. 2 n +1 ≤ 2n untuk n = 3,4,….

6. (1+x )n ≥ 1+ nx untuk x -1 dan n = 1,2,3,…

Gunakan induksi matematika untuk membuktikan pernyataan berikut ini.7. 11n – 6 habis dibagi 5, untuk n = 1,2,…8. 6.7n – 2.3n habis dibagi 4, untuk n = 1,2,….

46

[Type text]

Pertemuan Minggu Ke-6ALJABAR BOOLEAN

5.1. DEFINISI DAN SIFAT-SIFATAljabar boolean adalah suatu himpunan dengan dua operasi biner (yang disimbolkan

dengan tanda “+” dan “ * “) dan sebuah operasi komplementer (yang disimbolkan dengan tanda

‘) yang memenuhi :

Hukum klosur (tertutup)Bila a dan b adalah elemen aljabar boolean maka a+b, a*b dan a’ juga adalah elemen

aljabar boolean

Hukum komutatifa + b = b + a a*b = b*a

Hukum distributifa + (b*c) = (a+b) * (a+c)

a * (b+c) = (a*b) + (a+c)

Hukum identitasa + 0 = a a * 1 = a

Hukum Komplemena + a’ = 1 a * a’ = 0

Elemen 0 disebut sebagai elemen nol (besarnyat tidak selalu sama dengan nol) dan

elemen 1 disebut sebagai elemen unit (besarnya tidak selalu sama dengan satu).

Contoh 1 B = {0,1}, didefinisikan 1’ = 0 dan 0’ = 1. Operasi + dan * didefinisikan dengan tabel di bawah

ini. Akan diselidiki apakah (B, +, *, ‘, 0, 1) adalah suatu aljabar boolean !

+ 0 1 * 0 1

0 0 1 0 0 0

1 1 1 1 0 1

47

[Type text]

Untuk membuktikkan bahwa B adalah aljabar boolean, harus ditunjukkan bahwa untuk setiap elemen himpunan B

berlaku a + b, a * b dan a’ juga merupakan elemen himpunan B.

dari definisi diketahui bahwa 1’ = 0 dan 0’ = 1 sehingga terbukti bahwa bila a adalah

elemen B maka a’ juga merupakan elemen b.

dari definisi terlihat bahwa :

1 + 1 = 1

1 + 0 = 0 + 1 = 1

0 + 0 = 0

terbukti bahwa bila a dan b adalah elemen B maka a + b juga elemen B

dari definisi terlihat bahwa :

1 * 1 = 1

1 * 0 = 0 * 1 = 0

0 * 0 = 0

terbukti bahwa bila a dan b adalah elemen B maka a * b juga elemen B

Dari pembuktian-pembuktian tersebut dapat disimpulkan bahwa himpunan B dengan operasi +, * dan ‘ adalah suatu aljabar boolean.

Contoh :

Diketahui D = {1,2,4,5,10,20} dan didefinisikan operasi-operasi sebagai berikut :

a+b = kelipatan persekutuan terkecil dari a dan b

Contoh :

2+4 = kelipatan persekutuan terkecil dari 2 dan 4 = 4

2+5 = kelipatan persekutuan terkecil dari 2 dan 5 = 10

4+10 = kelipatan persekutuan terkecil dari 4 dan 10 = 20

a*b = faktor persekutuan terbesar dari a dan b

Contoh :

2*4 = faktor persekutuan terbesar dari 2 dan 4 = 2

2*5 = faktor persekutuan terbesar dari 2 dan 5 = 1

48

[Type text]

4*10 = faktor persekutuan terbesar dari 4 dan 10 = 2

a’ = 20/a

Akan diselidiki apakah untuk setiap elemen a dan b yang termasuk dalam himpunan D berlaku bahwa a+b, a*b

dan a’ juga termasuk dalam himpunan D

+ 1 2 4 5 10 20 * 1 2 4 5 10 20

1 1 2 4 5 10 20 1 1 1 1 1 1 1

2 2 2 4 10 10 20 2 1 2 2 1 2 2

4 4 4 4 20 20 20 4 1 2 4 1 2 4

5 5 10 20 5 10 20 5 1 1 1 5 5 5

10 10 10 20 10 10 20 10 1 2 2 5 10 10

20 20 20 20 20 20 20 20 1 2 4 5 10 20

a 1 2 4 5 10 20

a’=20/

a

20 10 5 4 2 1

Dari ketiga tabel di atas terlihat bahwa untuk setiap elemen a dan b yang termasuk

dalam himpunan D, berlaku bahwa a+b, a*b dan a’ juga termasuk dalam D. Oleh sebab itu D

adalah sebuah aljabar boolean.

Dari tabel-taebl tersebut juga dapat dilihat bahwa elemen nol bagi aljabar boolaen ini

adalah 1 (0) sedangkan elemen unit adalah 20(1).

Bila C adalah suatu himpunan bagian dari aljabar boolean B, C akan disebut sub-aljabar bila C juga merupakan aljabar boolean.

49

[Type text]

5.2. DUALITASDual dari sebuah pernyataan P adalah sebuah pernyataan yang diperoleh dengan mengganti tanda + dengan

tanda * (dan sebaliknya), dan mengganti elemen nol yang disimbolkan sebagai 0 dengan elemen unit yang

disimbolkan sebagai 1 (dan sebaliknya) pada pernyataan P.

Contoh :

Dual dari pernyataan P : (a * 1)(0 + a’) = 0 adalah P’: (a + 0)+(1 * a’) = 1

Dual dari pernyataan P : a + a’b = a + b adalah P’: a * (a’ + b) = a * b

Teorema dualitas :

Dual dari sebuah teorema adalah juga sebuah teorema.

5.3. HUKUM-HUKUM DASAR ALJABAR BOOLEANHukum identitas

a + 0 = a a * 1 = a

Hukum Komplemena + a’ = 1 a * a’ = 0

Dalam aljabar boolean berlaku hukum-hukum berikut ini. Perlu diperhatikan bahwa pada

masing-masing hukum, bagian (a) dan bagian (b) adalah saling dual.

1. hukum idempoten

(1a). a+a = a (1b). a*a = a

2. hukum keterbatasan

(2a). a+1 = 1 (2b). a*0 = 0

3. hukum absorpsi

(3a). a+(a*b) = a (3b). a*(a+b) = a

4. hukum asosiatif

(4a). (a+b) + c = a + (b+c) (4b). (a*b) * c = a * (b*c)

5. hukum komplementer

(5a). 0’ = 1 (5b). 1’ = 0

6. hukum De Morgan

50

[Type text]

(6a). (a+b)’ = a’ * b’ (6b). (a*b)’ = a’ + b’

7. hukum involusi

(7a). (a’)’ = a

Bukti dari beberapa hukum dasar aljabar boolean di sajikan di bawah ini.

1. Idempoten :a. a + a = a

Bukti : a = a + 0 identitas,kompl.

= a + ( a * a’ ) distributif

= ( a + a ) * ( a + a’ ) komplemen

= ( a + a ) * 1 identitas

= a + a terbukti identitas

atauBukti : a + a = ( a + a ) * 1 identitas

= ( a + a ) * ( a + a’ ) komplemen

= a + ( a * a’ ) distributif

= a + 0 komplemen

= a identitas

b. a * a = a

Bukti : a * a = a * a + 0 identitas

= a * a + a * a’ komplemen

= a * ( a + a’ ) distributif

= a * 1 komplemen

= a identitas

2. Keterbatasan :a. a + 1 = 1

Bukti : a + 1 = a + ( a + a’ ) komplemen

= ( a + a ) + a’ asosiatif

= a + a’ idempoten

= 1 komplemen

b. a * 0 = 0

Bukti : a * 0 = a * ( a * a’ ) komplemen

51

[Type text]

= ( a * a ) * a’ asosiatif

= a * a’ idempoten

= 0 komplemen

3. Absorbsi :a. a + ( a * b ) = a

Bukti : a + ( a * b ) = ( a * 1 ) + ( a * b ) identitas

= a * ( 1 + b ) distributif

= a * 1 keterbatasan

= a identitas

b. a * ( a + b ) = a

Bukti : a * ( a + b ) = ( a * a ) + ( a * b ) distributif

= a + ( a * b ) idempoten

= ( a * 1 ) + ( a * b ) identitas

= a * ( 1 + b ) distributif

= a * 1 keterbatasan

= a identitas

Soal-soal Latihan Sesuai dengan definisi dan hukum yang berlaku dalam aljabar boolean, buktikan :

1. (a+b)’ = a’*b’

2. (a*b)’ = a’ + b’

5.4. EKSPRESI BOOLEANEkspresi boolean adalah suatu ekspresi (pernyataan) yang tersusun dari variabel-

variabel boolean dan operasi-operasi boolean

Contoh :

E : (x + y + z’)’ + ((x’+y’)’ +z)

E : ((x’yz’ + y)’ + xy”)

52

[Type text]

5.5. LITERALLiteral adalah suatu variabel atau komplemen dari suatu variabel

Contoh : x,x’, a, a’

Perhatikan bahwa xdan x’ merupakan variabel yang sama (yaitu variabel x) tetapi

merupakan literal yang berbeda (yaitu literal x dan literal x’).

5.6. PERKALIAN DASARYang disebut sebagai perkalian dasar adalah :

Sebuah literal atau

Perkalian dua atau lebih literal dimana tidak ada dua buah literal dengan variabel

yang sama

Contoh :

y, xz’, y’z, x’y’z adalah merupakan perkalian dasar

xy’x’z bukan merupakan perkalian dasar sebab terdapat dua literal dengan variabel

yang sama (yaitu literal x dan x’)

1 (elemen unit) bukan merupakan perkalian dasar sebab tidak memiliki satupun

literal .

Setiap perkalian boolean selalu dapat direduksi/ disederhanakan menjadi bentuk nol

atau bentuk perkalian dasar.

Contoh :

xyx’z = xx’yz = 0yz = 0

xyzy = xyyz = xyz

xyz’xyx = xxxyyz’ = xyz’

xxxxyyyzzzz=xyz

x’xxxyyyzzzz=0

53

[Type text]

5.7 Bentuk KanonikFungsi Boolean yang dinyat sebagai jumlah dari hasil kali atau hasil kali dari jumlah, dengan

setiap suku mengandung literal lengkap disebut bentuk kanonik.

Ada dua macam bentuk kanonik :

1. Minterm atau sum of product (SOP)

2. Maxterm atau product of sum (POS)

Minterm dan maxterm dari dua peubah biner ditunjukkan pada tabel berikut :

x y Minterm Maxterm

Suku Lambang Suku Lambang

0 0 X’y’ M0 X+y M0

0 1 X’y M1 X+y’ M1

1 0 Xy’ M2 X’+y M2

1 1 Xy M3 X’+y’ M3

Minterm dan maxterm dari tiga peubah biner ditunjukkan pada tabel berikut :

x y z Minterm Maxterm

Suku Lambang Suku Lambang

0 0 0 X’y’z’ M0 X+y+z M0

0 0 1 X’y’z M1 X+y+z’ M1

0 1 0 X’yz’ M2 X+y’+z M2

0 1 1 X’yz M3 X+y’+z’ M3

1 0 0 Xy’z’ M4 X’+y+z M4

1 0 1 Xy’z M5 X’+y+z’ M5

1 1 0 Xyz’ M6 X’+y’+z M6

1 1 1 Xyz M7 X’+y’+z’ M7

54

[Type text]

55

[Type text]

5.7. JUMLAH DARI PERKALIAN (SUM OF PRODUCT – SOP)Suatu ekspresi boolean E disebut jumlah dari perkalian bila E adalah :

Sebuah perkalian dasar atau

Jumlah dari dua atau lebih perkalian dasar dimana tidak ada dua suku yang tercakup

oleh suku lainnya.

Contoh :

E1 = x’y’z adalah jumlah dari perkalian (SOP)

E2 = xz + x’yz + xyz’ adalah jumlah dari perkalian

E3 = xz’ + y’z + xyz’ adalah bukan jumlah dari perkalian sebab suku pertama (yaitu xz’)

tercakup pada suku ketiga (yaitu xyz’)

Langkah-langkah yang harus dilakukan untuk mengubah sebarang ekspresi boolean E

menjadi bentuk jumlah dari perkalian adalah :

1. Gunakan hukum De Morgan dan hukum involusi untuk mengubah ekspresi, supaya operasi

komplemen hanya berlaku pada satu variabel. Setelah langkah ini, E hanya akan terdiri dari

penjumlahan dan perkalian literal.

2. Gunakan hukum distributif untuk mengubah E menjadi bentuk penjumlahan perkalian

3. Gunakan hukum komutatif, idempoten dan komplemen untuk mengubah masing-masing

perkalian dalam E menjadi 0 (bentuk nol) atau perkalian dasar. Terakhir, gunakan hukum

absorpsi untuk mengubahnya menjadi bentuk jumlah dari perkalian.

Contoh :

Ubahlah E = [(ab)’c]’ [(a’+c)(b’+c’)]’ menjadi bentuk jumlah dari perkalian

Langkah 1

Perhatikan bahwa (a+b)’ = a’*b’ dan (a*b)’ = a’+b’. Sehingga ekspresi di atas dapat

diubah menjadi :

E = [((ab)’)’ + c’] [(a’+c)’ + (b’+c’)’]

= [(ab) + c’] [ac’ + bc]

Langkah 2

E = abac’ + abbc + ac’c’ + bcc’

56

[Type text]

Langkah 3

E = abc’ + abc + ac’ + 0

E = [abc’ + ac’] + abc

E = [ac’ (b+1)] + abc

E = ac’ + abc

Atau E = abc’ + abc + ac’= ab(c’+c) + ac’ = ab+ ac’

5.8. BENTUK LENGKAPSuatu bentuk jumlah dari perkalian disebut bentuk lengkap bila setiap suku terdiri dari

variabel yang lengkap.

Contoh :

1. E (a,b,c) = ac’ + abc adalah bukan bentuk lengkap sebab suku pertama hanya terdiri

dari variabel a dan c

2. E (a,b,c) = abc + ab’c’ + a’b’c’ adalah bentuk lengkap sebab setiap suku terdiri dari

variabel yang lengkap.

Setiap bentuk jumlah dari perkalian selalu dapat diubah menjadi bentuk lengkap.

Contoh :

E (a,b,c) = abc’ + bc’ + a’b

= abc’ + (a+a’) bc’ + a’b (c+c’)

= abc’ + abc’ + a’bc’ + a’bc + a’bc’

= abc’ + a’bc’ + a’bc

5.9 Bentuk POS (Product of Sum)Untuk membentuk SOP, tinjau kombinasi peubah-peubah yang menghasilkan nilai 1 sedangkan untuk membentuk POS, tinjau kombinasi peubah-peubah yang menghasilkan nilai 0. Perhatikan contoh berikut! Contoh:Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS!

x y z f(x, y, z)0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

0 1 0 0 1 0 0 1

57

[Type text]

Solusi:a. SOP

• Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 1 :001, 100, dan 111

• Fungsi Booleannya dalam bentuk kanonik SOP adalah: f(x, y, z) = x’y’z + xy’z’ + xyz

• Atau dengan menggunakan lambang (minterm),f(x, y, z) = m1 + m4 + m7 = å (1, 4, 7)

b. POS• Kombinasi nilai-nilai peubah yang menghasilkan nilai fungsi sama dengan 0 :

000, 010, 011, 101, dan 110 • Fungsi Booleannya dalam bentuk kanonik POS adalah

f(x, y, z) = (x + y + z)(x + y’+ z)(x + y’+ z’)(x’+ y + z’)(x’+ y’+ z)• Atau dengan menggunakan lambang (maxterm) 

f(x, y, z) = M0 M2 M3 M5 M6 = Õ(0, 2, 3, 5, 6) Jika kalian perhatikan bentuuk SOP dan POS pada contoh di atas, literal (masih ingatkah kalian apa itu literal?) yang membentuk fungsi Boolean tersebut selalu lengkap jumlahnya. Jika fungsi Boolean yang dimaksud adalah fungsi Boolean 3 variabel (x, y, z) maka setiap literalnyapun selalu lengkap. Bagimana jika kita menemukan fungsi Boolean yang tidak dalam bentuk SOP ataupun POS maka untuk membentuk fungsi Boolean tersebut menjadi bentuk kanonik SOP dan POS. Salah satu cara yang dapat digunakan untuk mengubahnya menjadi bentuk SOP atau POS adalah dengan cara melengkapi literalnya. Perhatikan contoh berikut.

Contoh:Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS!f(x, y, z) = x + y’z

SOPx = x(y + y’) = xy + xy’ = xy (z + z’) + xy’(z + z’) = xyz + xyz’ + xy’z + xy’z’y’z = y’z (x + x’) = xy’z + x’y’zf(x, y, z) = x + y’z = (xyz + xyz’ + xy’z + xy’z’) + (xy’z + x’y’z) = xyz + xyz’ + xy’z + xy’z’ + x’y’z f(x, y, z) = m7 + m6 + m5 + m4 + m1 = S (1,4,5,6,7)

POSf(x, y, z) = x + y’z = (x + y’)(x + z) (Hk Distributif) x + y’ = x + y’ + zz’ = (x + y’ + z)(x + y’ + z’) x + z = x + z + yy = (x + y + z)(x + y’ + z)

f(x,y,z) = (x +y’+ z)(x +y’+ z’)(x + y + z)(x + y’ + z) = (x +y+ z)(x +y’ + z)(x + y’ + z’) f(x, y, z) = M0M2M3 = Õ(0, 2, 3)

Jika kalian perhatikan dengan seksama, pada saat bentuk SOP telah ditemukan maka secara langsung bentuk POS juga ditemukan. Coba perhatikan SOP f(x, y, z) = S (1,4,5,6,7) dan POS f(x, y, z) = Õ(0, 2, 3), apa yang dapat kalian simpulakan dari kedua bentuk tersebut?___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Sembarang fungsi Boolean dapat disederhanakan dengan beberapa cara, diantaranya secara aljabar (menggunakan hukum-hukum aljabar yang berlaku pada aljabar Boolean), Peta Karnaugh.

58

[Type text]

Studi Kasusa. Jika f(x) = S (1,4,5,6,7), tentukan peta karnaugh dari fungsi Boolean tersebut!

Sebelum membuat peta karnaughnya, kita tentukan terlebih dahulu tabel kebenaran dari fungsi tersebut. Bentuuk fungsi Boolean dalam kasus ini adalah …… sehingga nilai dari m1, m4, m5, m6, dan m7 pada tabel adalah …..Lengkapi tabel kebenarannya kemudian ubah ke dalam bentuk peta karnaugh!

x y z suku f(x,y,z)0 0 0 m0 0

0 0 1 m1 …..0 1 0 m2 …..0 1 1 m3 …..1 0 0 m4 …..1 0 1 m5 …..1 1 0 m6 …..1 1 1 m7 …..

Tabel kebenaran Peta Karnaugh

b. Jika diketahui tabel kebenaran dari sebuah fungsi Boolean berikut, ubahlah tabel tersebut menjadi 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

Tabel kebenaran Peta Karnaugh

c. Jika diketahui sebuah peta karanaugh dari sembarang fungsi boolean, lengakpi penyederhanaan fungsi bollean dengan peta karnaug yag sudah dibuat dalam bentuk SOP!(Kelompok)

59

[Type text]

Peta Karnaugh

100 …….110 ……. ___ ___1 0 …….x z’ ……..

f(x,y,z) = xz’ + …..

Fakta:1. f(x,y,z) = x’y’z + x’yz + xy’z’ + xyz’

merupakan fungsi boolan sebelum disederhakan. Coba kalian tunjukan darimana fungsi tersebut didapatkan!________________________________________________________________________________________________________________________________

2. Jumlah literal pada fungsi tersebut adalah________________________________

3. Jumlah Literal setelah fungsi tersebut disederhanakan adalah _____________

Penyederhanaan Fungsi Boolean dalam bentuk SOP

Pada kasus bagian (c) apa yang dapat kalian simpulkan dari penyederhanaan fungsi Boolean! Diskusikan dengan kelompok kalian dan tulislah kesimpulan tersebut!_________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

Bagian A (Individu)1. Nyatakan tabel kebenaran di bawah ini dalam bentuk kanonik SOP dan POS berikut:

a.x y z f(x, y, z)

b.x y z f(x, y, z)

60

[Type text]

00001111

00110011

01010101

11001010

00001111

00110011

01010101

10011011

61

[Type text]

2. Jika diketahui fungsi bolean berikut:a. f(x,y,z) = y’(xz’ + z)b. f(x,y,z) = y(x’z + x)c. f(x,y,z) = x’y’z + xy’ +z’ Nyatakan masing-masing fungsi Boolean tersebut dalam bentukl SOP dan POS!

3. Jika diketahui tabel kebenaran dari sebuah fungsi Boolean berikut, ubahlah tabel tersebut menjadi peta karnaugh!

a.x y z f(x, y, z)00001111

00110011

01010101

11001010

b.x y z f(x, y, z)00001111

00110011

01010101

10011011

Bagian B (Kelompok)1. Tentukan bentuk sederhana (dalam bentuk SOP) dari fungsi Boolean dengan menggunakan peta Karnaugh

jika diketahui tabel kebenarannya berikut ini:

a.x y z f(x, y, z)00001111

00110011

01010101

11001010

b.x y z f(x, y, z)00001111

00110011

01010101

10011011

2. Tentukan bentuk sederhana (dalam bentuk POS) dari fungsi Boolean dengan menggunakan peta Karnaugh jika diketahui tabel kebenarannya berikut ini:

a.x y z f(x, y, z)

b.x y z f(x, y, z)

62

[Type text]

00001111

00110011

01010101

11001010

00001111

00110011

01010101

10011011

3. Sederhanakanlah fungsi Boolean berikut ini dengan metoda Peta Karnaugh dalam bentuk SOP.a. f(w, x, y, z) = S (1, 2, 3, 7, 9, 11, 12, 13, 14, 15)b. F(w,x,y,z) = ∑ (2, 3, 4, 5, 6, 7 , 9 , 11)c. f(w,x,y,z) = wx’ + wxy’z’ + wxyz’ + x’z’

Soal-soal Latihan Tentukan bentuk lengkap masing-masing jumlah dari perkalian di bawah ini.

1. E = b’c’ + ac’ + ab

2. E = z(x’+y) + y’

3. E = (x’+y)’ + x’y

5.9. EKSPRESI BOOLEAN MINIMAL Untuk semua jumlah dari perkalian E didefinisikan : EL = banyak literal dn ES = banyak

suku.

Contoh :

- Jika E = xy’z + x’’z’ + yz’ + x maka EL = 3+2+2+1=8, ES =4

- Jika E = x’y’z + xyz + y + yz’ + x’z maka EL = 11, ES = 5

- Jika E = xyt’ + x’y’zt + xz’t maka EL = 10, ES = 3

Ekspresi F dikatakan lebih sederhana dari pada ekspresi E bila FL < EL dan FS <ES. .

Ekspresi F disebut sebagai bentuk minimal bila tidak ada bentuk lain yang lebih

sederhana dari pada F.

5.10. PRIME IMPLICANTSP disebut sebagai prime implicants dari ekspresi E jika memenuhi sifat :

P + E = E

Dimana P adalah perkalian dasar dan E adalah jumlah dari perkalian.

63

[Type text]

Contoh :

Akan diselidiki apakah P = xz’ adalah prime implicants dari ekspresi E=xy’+xyz’+x’yz’.

Harus dibuktikan apakah P + E = E (syarat prime implicants).

P + E = xz’ + xy’ + xyz’ + x’yz’

= xz’ (y+y’) + xy’ (z+z’) + xyz’ + x’yz’

= xyz’ + xy’z’ + xy’z + xy’z’ + xyz’ + x’yz’

= xyz’ + xyz’ + xy’z’ + xy’z’ + xy’z + x’yz’

= xyz’ + xy’z’ + xy’z + x’yz’

= xyz’ + xy’(z’+z) + x’yz’

= xyz’ + xy’+ x’yz’

= xy’ + xyz’ + x’yz’ = E

Karena P + E = E maka P adalah prime implicants dari E.

Teorema

Bentuk minimal adalah jumlahan dari prime implicants

Soal-soal Latihan Selidiki, apakah P merupakan prime implicants dari E

1. P = xy’, E = xy’ + xyz’ + x’yz’

2. P = y’t, E = xy + y’t + x’yz’ + xy’zt’

3. P = xz, E = xy + y’t + x’yz’ +xy’zt’

4. P = xt, E = xy + y’t + x’yz’ +xy’zt’

Pertemuan Minggu Ke-7

5.11. MENENTUKAN BENTUK MINIMAL DENGAN ALGORITMATerdapat beberapa metoda yang dikenal untuk menentukan bentuk minimal dari suatu

ekspresi boolean diantaranya adalah dengan algoritma dan Peta Karnaugh. Algoritma

penentuan bentuk minimal akan dibicarakan pada bagian ini sedangkan peta Karnaugh

dibicarakan pada bagian selanjutnya.

64

[Type text]

Prinsip yang digunakan dalam algoritma penentuan bentuk minmal ekspresi boolean

adalah konsensus (biasa disimbolkan dengan Q). Konsensus hanya ada pada dua perkalian

dasar yang memiliki tepat hanya satu pasang literal. Konsensus diperoleh dengan

menghilangkan literal yang berpasangan tersebut.

Contoh 1 :

Jika P1 = xy’ dan P2 = yzt. Terlihat bahwa pada kedua perkalian dasar tersebut terdapat

tepat satu pasang literal yaitu y dan y’ maka Q = xzt.

Contoh 2 :

Jika P1 = x’y’ dan P2 = xy’zt. Terlihat bahwa pada kedua perkalian dasar tersebut

terdapat tepat satu pasang literal yaitu x dan x’ maka Q = y’zt

Contoh 3 :

Jika P1 = x’y’t dan P2 = yzt’. Terlihat bahwa pada kedua perkalian dasar tersebut

terdapat dua pasang literal yaitu y dan y’, t dan t’ , sehingga tidak memiliki konsensus.

Contoh 4 :

Jika P1 = x’y’t dan P2 = y’zt. Terlihat bahwa pada kedua perkalian dasar tersebut tidak

terdapat literal yang berpasangan sehingga tidak memiliki konsensus.

Dengan algoritma, pertama kali akan ditentukan terlebih dahulu jumlahan prime

implicants dari ekspresi boolean tersebut kemudian baru dilakukan penentuan penentuan

bentuk miimal.

Algoritma penentuan jumlahan prime implicants adalah :

1. Hapus suku yang mencakup suku yang lain

2. Tambahkan konsensus

3. Ulangi kedua langkah di atas sampai tidak bisa diulang kembali

Algoritma penentuan bentuk minimal adalah :

1. Ubah masing-masing suku dalam jumlahan prime implicants menjadi bentuk lengkap

2. Hapus suku yang bisa direduksi dengan suku yang lain.

Contoh 1:

65

[Type text]

Dengan menggunakan algoritma, tentukan bentuk minimal dari ekspresi boolean : E =

xy’ + x’y’ + x’y

Menentukan jumlahan prime implicants :

E = xy’ + x’y’ + x’y (tidak ada suku yang mencakup suku yang lain)

= xy’ + x’y’ + x’y + y’ (tambahkan konsensus suku I dan II)

= x’y’ + x’y + y’ (hapus suku I yang mencakup suku IV)

= x’y’ + x’y + y’ + x’ (tambahkan konsensus suku I dan II)

= x’y + y’ + x’ (hapus suku I yang mencakup suku IV)

= x’y + y’ + x’ + x’ (tambahkan konsensus suku I dan II)

= y’ + x’ + x’ (hapus suku I yang mencakup suku IV)

= y’ + x’ (hapus suku III)

Menentukan bentuk minimal :

y’ = (x+x’) y’ = xy’ + x’y’

x’ = x’ (y+y’) = x’y + x’y’

Terlihat bahwa kedua suku dari jumlahan prime implicants tersebut tidak ada yang bisa

direduksi sehingga jumlahan prime implicantas tersebut sekaligus adalah bentuk minimal.

Jadi E = xy’ + x’y’ + x’y = y’ + x’

Contoh 2.

Dengan menggunakan algoritma, tentukan bentuk minimal dari ekspresi boolean : E =

xyz + xyz’ + x’yz’ + x’y’z’ + x’y’z

Menentukan jumlahan prime implicants

E = xyz + xyz’ + x’yz’+ x’y’z’ + x’y’z

= xyz + xyz’ + x’yz’+ x’y’z’ + x’y’z + xy (konsensus suku I dan II)

= xyz’ + x’yz‘+ x’y’z’ + x’y’z + xy (hapus suku I)

= xyz’ + x’yz’+ x’y’z’ + x’y’z + xy + yz’ (konsensus suku I dan II)

= x’yz’+ x’y’z’ + x’y’z + xy + yz’ (hapus suku I)

= x’yz’+ x’y’z’ + x’y’z + xy + yz’ + x’z’ (konsensus suku I dan II)

66

[Type text]

= x’y’z’ + x’y’z + xy + yz’ + x’z’ (hapus suku I)

= x’y’z’ + x’y’z + xy + yz’ + x’z’ + x’y’ (konsensus suku I dan II)

= x’y’z + xy + yz’ + x’z’ + x’y’ (hapus suku I)

= xy + yz’ + x’z’ + x’y’ (hapus suku I)

Menentukan bentuk minimal xy + yz’ + x’z’ + x’y’

xy = xy (z+z’) = xyz + xyz’

yz’ = (x+x’) yz’ = xyz’ + x’yz’ (xyz’ dan x’yz’ dapat direduksi)

x’z’ = x’(y+y’) z’ = x’yz’ + x’y’z’ (x’yz’ dan x’y’z’ dapat direduksi)

x’y’ = x’y’ (z+z’) = x’y’z + x’y’z’

Terlihat bahwa suku kedua atau suku ketiga salah satu dapat direduksi dengan suku

yang lain sehingga jumlahan prime implicants tersebut belum merupakan bentuk minimal.

Bentuk minimal dari ekspresi boolean di atas hanya terdiri dari 3 suku yaitu :

E = xyz + xyz’ + x’yz + x’y’z’ + x’y’z = xy + x’z’ + x’y’ atau

E = xyz + xyz’ + x’yz + x’y’z’ + x’y’z = xy + yz’ + x’y’

5.12. MENENTUKAN BENTUK MINIMAL DENGAN PETA KARNAUGHPrinsip yang digunakan dalam metoda peta karnaugh adalah prinsip adjacent.

Definisi AdjacentDua perkalian dasar P1 dan P2 dikatakan adjacent bila keduanya terdiri dari variabel

yang sama dan berbeda hanya tepat satu literal.

Penjumlahan dua perkalian dasar yang adjacent akan menghasilkan perkalian dasar

juga, dimana jumlah variabel akan berkurang satu.

Contoh :

Jika diketahui P1 = xyz’ dan P2 = xy’z’ maka P1 dan P2 adalah adjacent sebab keduanya

terdiri variabel yang sama (yaitu x, y dan z) dan berbeda tepat satu literal (y dan y’).

P1 + P2 = xyz’ + xy’z’ = xz’ (y+y’) = xz’

Peta Karnaugh Dua Variabel

67

[Type text]

Peta Karnaugh untuk dua variabel disajikan di bawah ini. Bagian yang diarsir

menunjukkan perkalian dasar yang adjacent.

y y’ y y’ y y’

x xy xy’ x x

x’ x’y x’y’ x’ x’

Penggunaan peta Karnaugh untuk menentukan bentuk minimal dari suatu bentuk jumlah

dari perkalian dengan dua variabel dilakukan dengan langkah-langkah sebagai berikut :

Tuliskan setiap suku dari bentuk jumlah dari perkalian pada kotak yang sesuai

Tandai kotak-kotak yang adjacent dimulai dari 2 kotak (bila ada) kemudian 1 kotak

Periksa, apakah banyaknya tanda sudah minimal

Tuliskan bentuk minimal yang sesuai.

Contoh 1

E = xy + xy’

Bila digambarkan dalam peta Karnaugh, jumlah dari perkalian E akan berbentuk :

y y’

x

x’

Pada bagan di atas, kotak yang ditandai adalah masing-masing suku dari E. Dari bagan

tersebut terlihat bahwa daerah yang diarsir menutup daerah adjacent x, yaitu bentuk minimal

sekaligus prime implicants dari E.

Jadi E = xy + xy’ = x

Contoh 2

E = xy + x’y + x’y’

Bila digambarkan dalam peta Karnaugh, jumlah dari perkalian E akan berbentuk :

y y’

x

x’

68

[Type text]

Pada bagan di atas, kotak yang ditandai adalah masing-masing suku dari E. Dari bagan

tersebut terlihat bahwa daerah yang diarsir menutup daerah adjacent x’ (horisontal) dan daerah

adjacent y (vertikal), yaitu bentuk minimal sekaligus prime implicants dari E.

Jadi E = xy + x’y + x’y’ = x’ + y

Peta Karnaugh Tiga VariabelPeta Karnaugh untuk tiga variabel disajikan di bawah ini. Bagian yang diarsir

menunjukkan perkalian dasar yang adjacent.

yz yz’ y’z’ y’z yz yz’ y’z’ y’z

x x

x’ x’

yz yz’ y’z’ y’z

x

x’

Penggunaan peta Karnaugh untuk menentukan bentuk minimal dari suatu bentuk jumlah

dari perkalian dengan tiga variabel dilakukan dengan langkah-langkah sebagai berikut :

Tuliskan setiap suku dari bentuk jumlah dari perkalian pada kotak yang sesuai

Tandai kotak-kotak yang adjacent dimulai dari 4 kotak (bila ada), 2 kotak (bila ada)

kemudian 1 kotak

Periksa, apakah banyaknya tanda sudah minimal

Tuliskan bentuk minimal yang sesuai.

Contoh 1.

E = xyz + xyz’ + x’yz’ + x’y’z

Bila digambarkan dalam peta Karnaugh, jumlah dari perkalian E akan berbentuk :

yz yz’ y’z’ y’z

x

x’

Tampak pada bagan di atas, daerah yang diarsir (yang merupakan suku-suku sari E)

menutup daerah adjacent xy (horisontal) dan yz’ (vertikal) ditambah dengan daerah x’y’z.

69

[Type text]

Jadi, E = xyz + xyz’ + x’yz’ + x’y’z = xy + yz’ + x’y’z

Contoh 2.

E = xyz + xyz’ + xy’z + x’yz + x’y’z

Bila digambarkan dalam peta Karnaugh, jumlah dari perkalian E akan berbentuk :

yz yz’ y’z’ y’z

x

x’

Tampak pada bagan di atas, daerah yang diarsir (yang merupakan suku-suku sari E)

menutup daerah adjacent xy (horisontal) dan z (4 kotak di tepi).

Jadi, E = xyz + xyz’ + xy’z + x’yz + x’y’z = xy + z

Contoh 3.

E = xyz + xyz’ + x’yz’ + x’y’z’ + x’y’z

Bila digambarkan dalam peta Karnaugh, jumlah dari perkalian E akan berbentuk :

yz yz’ y’z’ y’z

x

x’

Pada bagan di atas, daerah yang diarsir menutupi daerah adjacent xy (horisontal atas),

yz’ (vertikal), x’z’ (horisontal bawah kiri) dan x’y’ (horisontal bawah kanan). Perlu diperhatikan

bahwa sebenarnya banyaknya tanda belum minimal sehingga harus diubah menjadi :

yz yz

’

y’z’ y’z yz yz’ y’z’ y’z

x x

x’ x’

Sehingga bentuk minimal untuk pernyataan boolean tersebut ada dua yaitu :

E = xy + x’z’ + x’y’ atau E = xy + yz’ + x’y’

Peta Karnaugh Empat VariabelPeta Karnaugh untuk empat variabel disajikan di bawah ini. Bagian yang diarsir

menunjukkan perkalian dasar yang adjacent.

70

[Type text]

zt zt’ z’t’ z’t zt zt’ z’t’ z’t

xy xy

xy' xy'

x’y’ x’y’

x’y x’y

zt zt’ z’t’ z’t zt zt’ z’t’ z’t

Xy xy

Xy’ Xy’

x’y’ x’y’

x’y x’y

Penggunaan peta Karnaugh untuk menentukan bentuk minimal dari suatu bentuk jumlah

dari perkalian dengan empat variabel dilakukan dengan langkah-langkah sebagai berikut :

Tuliskan setiap suku dari bentuk jumlah dari perkalian pada kotak yang sesuai

Tandai kotak-kotak yang adjacent dimulai dari 8 kotak (bila ada), 4 kotak (bila ada), 2

kotak (bila ada) kemudian 1 kotak

Periksa, apakah banyaknya tanda sudah minimal

Tuliskan bentuk minimal yang sesuai.

Contoh 1 :

Bentuk minimal dari pernyataan boolean yang ditunjukkan dengan peta Karnaugh :

zt zt’ z’t’ z’t

xy

xy'

x’y’

x’y

adalah : E = y’ +xzt’

Contoh 2 :

Bentuk minimal dari pernyataan boolean yang ditunjukkan dengan peta Karnaugh :

zt zt’ z’t’ z’t

xy

71

[Type text]

xy'

x’y’

x’y

adalah : E = yt + x’y’ + y’zt’

LATIHANDengan menggunakan peta Karnaugh, tentukan bentuk minimal dari masing-masing

ekspresi boolean di bawah ini.

1. E = xy + x’y’

2. E = xy’ + x’y’ + x’y

3. E = xyz + x’yz + xy’z + x’y’z + xyz’ + xy’z’

4. E = x’yz + x’yz’ + xyz’ + xy’z’ + xy’z

5.

zt zt’ z’t’ z’t

xy

xy'

x’y’

x’y

6.

zt zt’ z’t’ z’t

xy

xy'

x’y’

x’y

7.

zt zt’ z’t’ z’t

xy

xy'

x’y’

x’y

72

[Type text]

UTS

Pertemuan Minggu Ke-8 (file ppt 89)

Pertemuan Minggu Ke-9 (file ppt 89)

73

[Type text]

Pertemuan Minggu Ke-10Teori Graf

Graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatukan objek yang dinyatakan sebagai noktah, bulatan atau titik. Sedangkan hubungan antara objek dinyatakan dengan garis.

Sebagai contohnya pada Gambar 6.1 adalah sebuah peta jaringan jalan raya yang menghubungkan sejumlah kota di Propinsi Jawa Tengah. Sesungguhnya peta tersebut adalah sebuah graf, yang dalam hal ini kota dinyatakan sebagai bulatan sedangkan jalan dinyatakan sebagai garis. Dengan diberikannya peta tersebut, dapat mengetahui adanya lintasan dua buah kota.

Gambar 8.1 Jaringan jalan raya di Propinsi Jawa Tengah

Sejarah GrafPermasalahn jembatan Königsberg pada tahun 1739 adalah masalah yang pertama kali

menggunakan graf. Di Königsberg (sebelah timur Prussia), yang sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai. Terdapat tujuh jembatan yang menghubungkan daratan yang dibelah oleh sungai tersebut (Gambar 8.2(a)). Masalah jembatan Königsberg adalah : apakah mungkin melalui ketujuh jembatan itu masing-masing tepat satukali, dan kembali ke tempat semula ? Sebagian penduduk kota sepakat bahwa memang tidak mungkin melalui setiap jembatan itu hanya sekali dan kembali lagi ke tempat asal mula keberangkatannya, tetapi mereka tidak dapat menjelaskannya mengapa demikian jawabannya, kecuali dengan cara coba-coba.

74

[Type text]

Gambar 8.2 (a) Jembatan Königsberg, dan (b) graf yang merepresentasikan jembatan Königsberg

Tahun 1736, seorang matematikawan Swiss, L. Euler, adalah orang pertama yang berhasil menemukan jawaban masalah ini ke dalam graf. Daratan (titik-titik yang dihubungkan oleh jembatan dinyatakan sebagai titik (noktah) – yang disebut simpul (vertex)- dan jembatan dinyatakan sebgaai garis yang disebut sisi (edge). Setiap titik diberi label huruf A, B, C, dan D. graf yang dibuat oleh Euler diperlihatkan pada Gambar 8.2(b).

Jawaban yang dikemukakan Euler ialah : orang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya genap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh, simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. karena tidak semua simpul berderajat genap, maka tidak mungkin dilakukan perjalanan berupa sirkuit (yang dinamakan sirkuit Euler) pada graf tersebut.

Definisi GrafGraf G didefinisikan sebagai pasangan himpunan (V, E) yang dalam hal ini :

V = himpunan berhingga dan tidak kosong dari simpul-simpul (vertices atau node)

= {v1 , v2 , . . .. .. . ., vn }danE = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul.

= {e1 , e2 , . . .. .. . ., en }

atau dapat ditulis singkat notasi G = (V, E).

Simpul pada graf dapat dinomori dengan huruf, seperti v, w, …, dengan bilangan asli 1, 2, 3, …. Atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul vi dengan simpul vj

dinyatakan dengan pasangan (vi, vj) atau dengan lambang e1, e2, … Dengan kata lain, jika e adalah sisi yang menghubungkan simpul vi dengan simpul vj, maka e dapat ditulis sebagai berikut :e = (vi, vj)

Secara geometri graf digambarkan sebagai kumpulan noktah (simpul) di dalam bidang dwimatra yang dihubungkan dengan sekumpulan garis (sisi).

75

[Type text]

Gambar 8.3Tiga buah graf (a) graf sederhana, (b) graf ganda, dan

(c) graf semu

Contoh 8.1Gambar 8.3 memperlihatkan tiga buah graf yaitu G1, G2 dan G3. G1 adalah graf dengan himpunan simpul V dan himpunan sisi E adalah :V = { 1, 2, 3, 4 }E = { (1,2), (1,3), (2,3), (2,4), (3,4) }

G2 adalah graf dengan himpunan simpul V dan himpunan sisi E adalah :V = { 1, 2, 3, 4 }E = { (1,2), (2,3), (1,3), (1,3), (1,3), (2,4), (3,4), (3,4) } → himpunan ganda

= { e1, e2, e3, e4, e5, e6, e7 }

G3 adalah graf dengan himpunan simpul V dan himpunan sisi E adalah :V = { 1, 2, 3, 4 }V = { (1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4), (3,3) } → himpunan ganda

= { e1, e2, e3, e4, e5, e6, e7, e8 }

Pada G2, sisi e3 = (1,3) dan sisi e4 = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungkan dua simpul yang sama, yaitu simpul 1 dan simpul 3. Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop) karena berawal dan berakhir pada simpul yang sama.

Jenis-Jenis GrafPengelompokkan graf berdasarkan tidak adanya gelang atau sisi ganda pada suatu graf, yaitu :

Graf Sederhana (simple graph)Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 6.2(a) adalah contoh graf yang sederhana yang mempresentasikan jaringan komputer.

Graf Tak-sederhana (unsimple-graph)Graf yang mengadung sisi ganda atau gelang dinamakan graf tak sederhana (unsimple graph).

76

[Type text]

Macam graf tak-sederhana Graf ganda (multigraph), graf yang mengadung sisi ganda. G2 pada

Gambar 6.3 (b) adalah contoh graf ganda Graf semu, graf yang mengandung gelang. G3 adalah graf semu

(termasuk bila memiliki sisi ganda sekalipun).Graf semu lebih umum daripada graf ganda, karena sisi pada graf semu dapat terhubung ke dirinya sendiri.

Jumlah simpul pada graf disebut sebagai kardinalitas graf, dan dinyatakan dengan n = | V |, dan jumlah sisi dinyatakan dengan m = | E |.

Berdasarkan jumlah simpul pada suatu graf, yaitu :Graf Berhingga (limited graph)

Graf berhingga adalah graf yang jumlah simpulnya, n. berhingga. Dua buah graf pada Gambar 8.3 adalah contoh graf yang berhingga.

Graf Tak-Berhingga (unlimited graph)Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.

Gambar 8.4 Dua buah graf yang tak-berhingga

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis, yaitu :

Graf Tak-Berarah (undirected graph)Graf yang sisinya tidak mempunyai orientasi arah disebut dengan graf tak-berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (vj,vk) = (vk, vj) adalah sisi yang sama.

Graf Berarah (directed graph atau digraph)Graf yang setiap sisinya diberi orientasi arah disebut sebagai graf berarah. Sisi berarah disebut dengan busur (arc). Pada graf berarah (vj,vk) dan (vk, vj) menyatakan dua buah busur yang berbeda, dengan kata lain (vj,vk) ≠ (vk, vj). Untuk busur (vj,vk), simpul vj dinamakan simpul asal (initial vertex) dan simpul vk dinamakan simpul terminal (terminal vertex).

77

[Type text]

Gambar 8.5 (a) graf berarah, (b) graf-ganda berarah

Definisi graf dapat diperluas sehingga mencakup graf-ganda berarah (Gambar 6.8 (b)).

Jenis Sisi Sisi ganda dibolehkan Sisi gelang dibolehkan

Graf sederhana Tak-berarah Tidak Tidak

Graf ganda Tak-berarah Ya Tidak

Graf semu Tak-berarah Ya Ya

Graf berarah Berarah Tidak Ya

Graf-ganda

berarah

Berarah Ya Ya

Tabel 8.1 meringkas perluasan definisi graf.

Terminologi Graft

Gambar 8.6 Tiga buah graf G1, G2 dan G3

78

[Type text]

Terminologi (istilah) yang berkaitan dengan graf ialah : Ketetanggaan (adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung. Secara formal dinyatakan :vj bertetangga dengan vk jika ∀ e ∈ E sedemikian sehingga e = (vj, vk).Contoh 8.2pada Gambar 8.6(a), simpul 1 bertetangga dengan simpul 2 dan 3 tetapi tidak bertetangga dengan simpul 4.

Bersisian (incidency)Untuk sembarang sisi e = (vj, vk) dikatakanE bersisian dengan simpul vj, atauE bersisian dengan simpul vk.

Contoh 8.3Pada Gambar86.6(a), sisi (2, 3) bersisian dengan simpul 2 dan simpul 3, sisi (2, 4) bersisian dengan simpul 2 dan simpul 4, tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

Simpul Terpencil (isolated Vertex)Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya. Atau, dapat juga dinyatakan bahwa simpul terpencil adalah simpul yang tidak satupun bertetangga dengan simpul-simpul lain.Contoh 8.4Pada Gambar 8.6 (c), simpul 5 adalah simpul terpencil.

Graf KosongDefinisi graf dinyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi sebuah graf dimungkan tidak mempunyai sisi satu buahpun, tetapi simpulnya harus ada, minimal satu. Graf yang himpunan sisinya merupakan himpunan kosong disebut sebagai graf kosong (null graph atau empty graph) dan ditulis sebagai Nn, yang dalam hal ini n adalah jumlah simpul.Contoh 8.5Graf pada Gambar 8.7 adalah graf N5.

Gambar 8.7 Graf Kosong

Derajat (Degree)

79

[Type text]

Derajat suatu simpul adalah jumlah sisi yang besisian dengan simpul tersebut.Notasi : d(v)

Contoh 6.6Pada Gambar 8.6(a),d(1) = d(4) = 2d(2) = d(3) = 3Simpul terpencil adalah simpul dengan d(v) = 0. pada gambar 6.6(c), d(5) = 0.

Simpul yang mempunyai gelang dihitung mempunyai dua buah sisi yang bersisian dengannya. Jadi graf pada Gambar 8.6(b), d(2) = 4. secar a umum, jika terdapat g buah gelang dan e buah sisi bukan-gelang yang bersisian dengan simpul v, maka derajat simpul v adalahd(v) = 2g + e (8.1)

Alasan mengapa gelang mengkontribusikan dua untuk derajat simpulnya adalah karena gelang direpresentasikan sebagai (v, v), dan simpul v bersisian dua kali pada sisi (v, v)Simpul yang berderajat satu disebut anting-anting (pendant vertex). Pada graf berarah, pengertian derajat dibedakan menjadi 2 macam :din(v) = derajat-masuk (in-degree) = jumlah busur yang masuk ke dalam simpul vdout(v) = derajat-keluar (out-degree) = jumlah busur yang keluar dari simpul v

dan d(v) = din(v) + dout(v) (8.2)

Contoh 8.7Pada Gambar 8.5 adin(1) = 2; dout(1) = 1din(2) = 2; dout(2) = 3din(3) = 2; dout(3) = 1din(4) = 1; dout(3) = 2

Pada graf beararah G = (V, E) berlaku hubungan∑

v∈Vd in(v )=∑

v∈Vdout (v )=E

Lemma Jabat TanganJumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graf tersebut. Dengan kata lain, jika G = (V, E) maka :∑

v ∈Vd ( v )=2E

(8.3)

Dengan catatan : nilai 2E selalu bernilai genap. Lemma ini dikenal dengan lemma jabat tangan (handshaking lemma). Hal ini disebabkan oleh setiap sisi dihitung dua kali, yaitu pada ujung kiri sebagai bagian dari simpul kiri dan pada ujung kanan dihitung sebagai bagian dari simpul kanan. Layaknya orang yang sedang berjabat tangan, maka jumlah tangan yang berjabatan adalah genap dan jumlah tangan yang berjabatan adalah dua kali jumlah jabatan tangan yang terjadi. Catatlah bahwa Lemma 8.1 juga benar untuk graf berarah, yang dalam hal ini d(v)=din(v)+dout(v).

80

[Type text]

Contoh 8.8Jumlah derajat seluruh simpul pada graf Gambar 8.6(a) adalah:d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10

= 2 X jumlah sisi = 2 x 5

Contoh 8.9Diketahui graf dengan lima buah simpul. Dapatkah menggambar graf tersebut jika derajat masing-masing simpul adalah :(a) 2, 3, 1, 1, 2(b) 2, 3, 3, 4, 4Jawab(a) Tidak dapat, karena jumlah derajat semua simpulnya ganjil (2+3+1+1+2 = 9).(b) Dapat karena jumlah derajat simpulnya genap (2 + 3 + 3 + 4 + 4 = 16). Salah

satu kemungkinan graf yang dapat digambarkan ditujukkan pada Gambar 8.8. Grafnya bukan graf sederhana.

Gambar 8.8 Graf dengan derajat setiap simpul masing-masing 2, 3, 3, 4, 4

Akibat dari Lemma 8.1 diatas adalah dapat diturunkan teorema sbb:Teorema 8.1Untuk sembarang graf G, banyaknya simpul yang berderajat ganjil selalu genap.

81

[Type text]

BuktiMisalkan V1 dan V2 masing-masing adalah himpunan simpul yang berderajat genap dan berderajat ganjil pada graf G = (V, E). persamaam (8.4) dapat ditulis sebagai∑

v∈V 1

d ( v )+ ∑v∈V 2

d ( v )=2E

Karena d(v) genap untuk v∈V 1 , maka rumus pertama dari ruas kiri persamaam selalu bernilai genap. Ruas kanan persamaan 8.4 juga bernilai genap. Nilai genap pada ruas kanan hanya benar bila suku kedua dari ruas kiri juga harus genap agar.

genap + genap = genap

Karena d(v) ganjil untuk v∈V 2 , maka banyaknya simpul v di dalam V2 harus genap agar jumlah seluruh derajatnya bernilai genap. Jadi, banyaknya simpul yang berderajat ganjil selalu genap.

Lintasan (Path)

Lintasan dari simpul vp ke vq dalam G ialah rangkaian simpul v p , vi1 , vi 2 , . .. ,v im , vq

sehingga ((v p ,vi 1) , (v i1 ,vi 2 ) , . .. , (vim ,vq)adalah sisi-sisi dalam graf G. Lintasan sederhana (simple path)

Adalah lintasan dengan semua sisi yangdilalui hanya satu kali. Lintasan elementer(elementary path)

Merupakan lintasan dengan semua simpul yang dilalui hanya muncul satu kali, kecuali , mungkin simpul pertama dan simpul terakhir.

Lintasan tertutup (closed path)Lintasan yang berawal dan berakhir pada simpul yang sama

Lintasan terbuka (open walk)Lintasan yang berawal dan berakhir pada simpul yang tidak sama

Contoh 8.10Pada Gambar 8.6(a).Lintasan 1, 2, 4, 3 adalah lintasan elementer, juga lintasan sederhna, juga lintasan terbukaLintasan 1, 2, 4, 3, 1 adalah lintasan elementer, juga lintasan sederhana, juga lintasan tertutup.Lintasan 1, 2, 4, 3, 2 bukan lintasan elementer, tetapi lintasan terbuka dan lintasan sederhana

Panjang lintasanAdalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada Gambar 8.6(a) memiliki panjang 3.

Penulisan lintasan dengan notasi v p , vi1 , vi 2 , . .. ,v im , vq hanya benar untuk graf sederhana karena (vij, vik) menyatakan sisi yang unik. Notasi tersebut akan menimbulkan keraguan pada graf yang memiliki sisi ganda sebab bila (vij, vik) adalah sisi ganda maka timbul kerancuan sisi dimana yang dilalui. Untuk menghindari kerancuan tersebut, maka nama sisi harus disebutkan. Karena itu, untuk graf yang mengandung sisi ganda,penulisan lintasan adalah berselang-seling

antara simpul dan sis yang dilalui : v p ,e1 ,v i1 ,e2 ,v i 2 , . .. , v im , em+1 . Jadi untuk

82

[Type text]

contoh yang terakhir, bila sisi ganda yang dilalui adalah sisi e1, maka penulisan lintasan yang benar adalah : 1, e1, 2, e4 ,3.

Siklus (Cycle) atau Sirkuit (Circuit)Lintasan elementer dengan simpul pertama sama dengan simpul terakhir disebut sirkuit atau siklus. Pada Gambar 8.6(a), 1, 2, 3 , 1 adalah sebuah sirkuit. Panjang sirkuit

Adalah jumlah sisi dalam sirkuit tersebut.lintasan 1, 2, 3, 1 pada Gambar 8.6(a) memiliki panjang 3.

Sirkuit sederhana (simple path)Adalah sirkuit dengan semua sisi yang dilalui hanya satu kali.

Sirkuit Elementer (elementary path)Adalah sirkuit dengan semua simpul yang dilalui hanya stau kali.

Contoh 8.11Pada Gambar 8.6(a), 1, 2, 3, 1 adalah sirkuit sederhana, juga sirkuit elementer, sedangkan 1, 2, 4, 3, 2, 1 bukan sirkuit sederhana, juga bukan sirkuit elementer.

Terhubung (Connecterd)Dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1 ke v2. Graf tak-berarah G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul vi dan vj (yang juga harus berarti ada lintasan dari vj ke vi). Jika tidak, maka G disebut graf tak-terhubung (disconnected graph). Sebagai perjanjian, setiap simpul terhubung dengan dirinya sendiri. Jadi, graf yang hanya terdiri dari satu simpul saja (tidak ada sisi), juga dikatakan graf terhubung. G1 dan G2 pada Gambar 8.6 adalah graf terhubung, sedangkan G3 tidak. Graf pada gambar 8.9 juga adalah contoh graf yang tak-terhubung.

Gambar 8.9 Graf tak-berarah tidak terhubung

Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung “(graf tidak berarah dari G diperoleh dengan menghilangkan arahnya).Dua simpul, u dan v, pada graf berarah disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u. Pada Gambar 8.10(a), simpul 1 dan simpul 3 terhubung kuat karena terdapat lintasan dari 1 ke 2 ( yaitu 1, 2), begitu juga terdapat lintasan dari 2 ke 1 (yaitu 2, 1).Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly connected). Pada Gambar

83

[Type text]

8.10(a), simpul 1 dan simpul 3 terhubung lemah karena hanya terdapat lintasan dari 1 ke 3 (yaitu 1, 2, 3), tetapi tidak ada lintasan 3 ke 1.Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah) dan G diperoleh dengan menghilangkan arahnya.

Gambar 8.10 (a) graf berarah terhubung lemah

(b) graf berarah terhubung kuat

Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terdapat lintasan dari simpul u ke simpul v, demikian juga dari simpul v ke u.dengan kata lain, setiap pasang simpul u dan v di G terhubung kuat. Kalau tidak, G disebut graf terhubung lemah. Graf pada Gambar 8.10 (b) adalah graf terhubung kuat, sedangkan graf pada Gambar 8.11 adalah graf terhubung lemah.

84

[Type text]

Pohon (tree)Pohon adalah graf yang terhubung yang tidak mempunyai sirkuit.Contoh 8.12Tiga buah graf pada Gambar 8.11 adalah pohon.

Gambar 8.11 Tiga buah pohon

Upagraf (Subgraph) dan Komplemen UpagrafMisalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf (subgraph) dari G jika V1 ⊆ V dan E1 ⊆ E (Gambar 8.12(b)).Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E – E1 dan V2 adalah himpunan simpul yang angggota-anggotanya E2 bersisian dengannya (Gambar 8.12(c)).

Gambar 8.12 (a) Graf G1, (b) Sebuah upagraf dari G1, dan (c) komplemen dari upagraf yang bersesuaian.

Jika graf tak terhubung, maka graf tersebut terdiri atas beberapa komponen. Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G. pada Gambar 6.13 di bawah ini, Graf G mempunyai 4 buah komponen. Graf terhubung hanya terdiri dari satu komponen.

Gambar 8.13 Graf G yang mempunyai 4 buah komponen

85

[Type text]

Pada graf berarah, komponen terhubung kuat (stringly connected component) adalah jumlah maksimum upagraf yang terhubung kuat. Graf pada Gambar 8.14 di bawah ini mempunyai 2 buah komponen terhubung kuat, yaitu upagraf dengan simpul 1, 2, 3 dan upagraf yang hanya mempunyai satu simpul, 6.

Gambar86.14 Graf berarah G yang mempunyai 2 buah komponen terhubung kuat

Upagraf Rentang (Spanning Subgraph)Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 = V (yaitu G1

mengandung semua simpul dari G).

Contoh 8.13Pada Gambar 6.15, G1 adalah upagraf rentang dari G, tetapi G2 bukan upagraf rentang dari G karena G2 tidak mengandung simpul G.

Gambar 8.15 (a) graf G, (b) upagraf rentang dari G, dan (c) bukan upagraf rentang

dari G

Cut-SetCut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.

Contoh 8.14Pada Gambar 8.16, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung. Himpunan {(1,2), (2,5)} juag adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set, tetapi {(1,2), (2,5), (4,5) } bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set.

86

[Type text]

Gambar 8.16 {(1,4), (1,5), (2,4), (2,3)} adalah cut-set

Cut-set berperan besar dalam jaringan komunikasi dan jaringan transportasi. Misalkan keenam simpul pada Gambar 8.17 menyatakan enam kota yang dihubungkan dengan saluran telepon (sisi).

Graf berbobot (Weighted Gaph)Graf berbobot adalah graf yang setiap sisinya diberi harga (bobot). Bobot pada tiap sisi graf dapat menyatakan jarak antara dua buah kota, biaya perjalanan antara dua buah kota, waktu tempuh pesan (message) dari sebuah simpul komunikasi ke simpul komunikasi lainnya, ongkos produksi, dan sebagainya. Gambar 8.17 adalah contoh graf berbobot.

Gambar 8.17 Graf berbobot

Pertemuan Minggu Ke-11

Beberapa Aplikasi GrafLintasan Terpendek (Shortest Path)

Persoalan mencari lintasan terpendek di dalam graf merupakan persoalan yang klasik. Kata ‘terpendek’ pada persoalan lintasan terpendek berarti minimisasi dari bobot pada suatu lintasan graf.Terdapat beberapa jenis persoalan lintasan etrpendek, antara lain : Lintasan terpendek antara du abuah simpul tertentu Lintasan terpendek antara semua simpul Lintasan terpendek dari simpul tertentu ke semua simpul yang lain Lintasan terpendek antara dua buah simpul yang melalui beberap simpul

tertentu.

Pada dasarnya, jenis persoalan 1 mirip dengan persoalan 3, karena pencarian lintasan terpendek pada jenis persoalan 3 dapat dihentikan bila simpul yang dikehendaki sudah diketemukan lintasan terpendeknya. Namun kita menggunakan persoalan 3

87

[Type text]

Uraian persoalanDiberikan graf berbobot G = (V, E) dan sebuah simpul a. tentukan lintasan terpendek dari a k setiap simpul lainnya di G. Asumsi yang dibuat adalah bahwa semau sisi berbobot positif.

Gambar 8.18 Graf yang digunakan sebagai contoh lintasan terpendek

Lintasan terpendek dari simpul 1 ke semua simpul lain diberikan pada tabel di bawah ini.

Simpul Asal Simpul tujuan Lintasan Terpendek Jarak1 3 1 → 3 10

1 4 1 → 3 → 4 25

1 2 1 → 3 → 4 → 2 45

1 5 1 → 5 45

1 6 Tidak ada -

Misalkan sebuah graf berbobot dengan n buah simpul dinyatakan dengan matriks ketetanggan M = [mij] yang dalam hal ini.Mij = bobot sisi (i, j) (pada graf tak-berarah mij = mji)Mii = 0mij = ∞, jika tidak ada sisi dari simpul i ke simpul jSelain matrik M, juga menggunakan larik S = [si] yang dalam hal inisi = 1, jika simpul i termasuk ke dalam lintasan terpendeksi = 0, jika simpul i tidak termasuk ke dalam lintasan terpendekDan larik/label D = [di] yang dalam hal ini.di = panjang lintasan dari simpul awal s ke simpul i

Algoritma Lintasan Terpendek DijkstraLangkah 0 (inisialisasi)inisialisasi si = 0 dan di = mai untuk i = 1, 2, …, n

Langkah 1 : Isi sa dengan 1 (karena simpul a adalah simpul asal lintasan terpendek, jadi

sudah pasti terpilih) Isi da dengan ∞ (tidak ada lintasan terpendek dari simpul a ke a)

88

[Type text]

Langkah 2, 3, …, n-1 : Cari j sedemikian sehingga s1=0 dan d1 = min {d1, d2, …, dn} Psi sj dengan 1 Perbaharui di, untuk i = 1, 2, 3, …, n dengan : di (baru)

= min {d,(lama), dj +mji}.

J = 1 2 3 4 5 6

I = 1 0 50 10 40 45 ∞

2 ∞ 0 15 ∞ 10 ∞

3 20 ∞ 0 15 ∞ ∞

4 ∞ 20 ∞ 0 35 ∞

5 ∞ ∞ ∞ 30 0 ∞

6 ∞ ∞ ∞ 3 ∞ 0

Perhitungan lintasan terpendek dari simpul awal a = 1 ke semua simpul lainnya ditabulasikan sebagai berikut :

Lelaran Simpul

yang

dipilih

lintasan S D

1 2 3 4 5 6 1 2 3 4 5 6

Inisial - - 0 0 0 0 0 0 0 50 1 40 45 ∞

(1,2) (1,3) (1,4) (1,5) (1,6)

1 1 1 1 0 0 0 0 0 ∞ 50 10 40 45 ∞

(1,2) (1,3) (1,4) (1,5) (1,6)

2 3 1,3 1 0 1 0 0 0 ∞ 50 10 25 45 ∞

(1,2) (1,3) (1, 3,

4)

(1,5) (1,6)

3 4 1,3,4 1 0 1 1 0 0 ∞ 45 10 25 45 ∞

(1, 3, 4, 2) (1,3) (1, 3,

4)

(1,5) (1,6)

4 2 1,3,4,2 1 1 1 1 0 0 ∞ 45 10 25 45 ∞

(1, 3, 4, 2) (1,3) (1, 3,

4)

(1,5) (1,6)

5 5 1,5 1 1 1 1 1 0 ∞ 45 10 25 45 ∞

(1, 3, 4, 2) (1,3) (1, 3,

4)

(1,5) (1,6)

(Keterangan : Angka-angka di dalam tanda kurung menyatakan lintasan terpendek dari 1 ke simpul tersebut)

Jadi lintasan terpendel dari1 ke 3 adalah 1, 3 dengan panjang = 10

89

[Type text]

1 ke 4 adalah 1, 3, 4 dengan jarak 251 ke 2 adalah 1, 3, 4, 2 dengan jarak = 451 ke 5 adalah 1, 5 dengan jarak = 451 ke 6 tidak ada

Contoh8 6.15Tinjau graf berarah pada Gambar 8.19 yang menyatakan jarak beberapa kota di Amerika Serikat.

Gambar 8.19 Graf berarah dari sebuah peta ASMatriks ketetanggan M sebagai berikut :

J = i 2 3 4 5 6 7 8 9

I = 1 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞

2 300 ∞ ∞ ∞ ∞ ∞ ∞ ∞

3 1000 800 0 ∞ ∞ ∞ ∞ ∞

4 ∞ ∞ 1200 0 ∞ ∞ ∞ ∞

5 ∞ ∞ ∞ 1500 0 250 ∞ ∞

6 ∞ ∞ ∞ 1000 ∞ 0 900 1400

7 ∞ ∞ ∞ ∞ ∞ ∞ 0 1000

8 1700 ∞ ∞ ∞ ∞ ∞ ∞ 0

90

[Type text]

Lel

era

n

Simpu

l yang

dipilih

Lintas

an

S D

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 33

56

Inisi

al

- - 0 0 0 0 0 0 0 0 ∞ ∞ ∞ 15

00

0 25

0

∞ ∞

1 5 5 0 0 0 0 1 0 0 0 ∞ ∞ ∞ 15

00

∞ 25

0

∞ ∞

2 6 5, 6 0 0 0 0 1 1 0 0 ∞ ∞ ∞ 12

50

∞ 25

0

11

50

16

50

3 7 5, 6, 7 0 0 0 0 1 1 1 0 ∞ ∞ ∞ 12

50

∞ 25

0

11

50

16

50

4 4 5, 6, 4 0 0 0 1 1 1 1 0 ∞ ∞ 24

50

12

50

∞ 25

0

11

50

16

50

5 8 5, 6, 8 0 0 0 1 1 1 1 1 33

50

∞ 24

50

12

50

∞ 25

0

11

50

16

50

6 3 5, 6,

4, 3

0 0 1 1 1 1 1 1 33

50

∞ 24

50

12

50

∞ 25

0

11

50

16

50

7 2 5, 6,

4, 3, 2

0 1 1 1 1 1 1 1 33

50

32

50

24

50

12

50

∞ 25

0

11

50

16

50

Jadi lintasan terpendek dari :5 ke 6 adalah 5, 6 dengan panjang = 2505 ke 7 adalah 5, 6, 7 dengan jarak = 11505 ke 4 adalah 5, 6, 8 dengan jarak = 12505 ke 8 adalah 5, 6, 8 dengan jarak = 16505 ke 3 adalah 5, 6, 4, 3, dengan jarak = 24505 ke 2 adalah 5, 6, 4, 3, 2 dengan jarak = 32505 ke 1 adalah 5, 6, 8, 1 dengan jarak = 3350

Persoalan Perjalanan Pedagang (Travelling Salesperson Problem – TSP)Nama persoalan ini diilhami oleh masalah seorang pedgang yang akan mengunjungi sejumlah kota, yaitu dengan menentukan sirkuit terpendek yang harus dilalui oleh sebuah pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan.

Sirkuit HamiltonYaitu sirkuit yang mengunjungi setiap titiknya tepat 1 kali kecuali titik awal = titik akhir dan

tidak harus melalui semua garis.Jika graf G mempunyai sirkuit hamilton maka G mempunyai subgrup H dengan sifat sbb :a. H terhubungb. H memuat semua titik Gc. H mempunyai jumlah garis = jumlah titikd. Setiap titik dalam H mempunyai derajat 2.

Persoalan Tukang Pos Cina (Chinese Postman Problem)

91

[Type text]

Persoalan ini pertama kali dikemukakan oleh Mei Gan pada tahun 1962. masalahnya adalah seorang tukang pos akan mengantar surat ke alamat-alamat sepanjang jalan di suatu daerah.bagaimana ia merencanakan rute perjalanannya supaya ia melewati setiap jalan tepat sekali dan kembali lagi ke tempat asal keberangkatannya.

Sirkuit EulerMisal G adalah graf, sirkuit euler G adalah sirkuit dimana setiap titik dalam G muncul paling

sedikit sekali dan setiap garis dalam G muncul tepat satu kali.Graf G mempunyai sirkuit euler jika hanya jika semua titik dalam G berderajat genap.

Gambar8.20 Graf untuk persoalan CPP dan TSP

Latihan 1. Dalam sebuah pesta, sepuluh orang saling berjabat tangan. Tiap orang hanya berjabat

tangan satu kali dengan orang lainnya. Hitung jumlah jabat tangan yang terjadi ( Modelkan persoalan ini ke dalam graf)

2. Tunjukkan bahwa derajat maksimum sembarang simpul pada graf sederhana dengan n simpul adalah n-1.

3. Tiga pasang suami istri yang seang menempuh perjalanan sampai ke sebuah sungai. Disitu mereka menemukan sebuah perahu kecil yang hanya bisa membawa tidak lebih dri dua orang setiap kali menyeberang. Penyeberangan sungai dirumitkan oleh kenyataan bahwa para suami sangat pencemburu dan tidak mau meninggalkan istri-istri mereka jika ada lelaki lain. Buatlah sebuah graf untuk menunjukkan bagaimana penyeberangan itu bisa dilakukan.

92

[Type text]

Pertemuan Minggu Ke-12Pewarnaan Graf (file pdf)Pertemuan Minggu Ke-13 & 14Pohon Biner (file pdf)

93