5. RELASI DAN FUNGSI. Gambar 5.1

5. RELASI DAN FUNGSI 5.1 Relasi atau Pemetaan Cara memasangkan anggota A ke anggota B

A

B

Gambar 5.1 

Hasil Kali Kartesian Misalkan A dan B adalah himpunan-himpunan. Hasil kali Kartesian A dengan B (simbol A x B) adalah himpunan semua pasangan berurutan (a, b) dengan a  A dan b  B. A x B  {(a, b) | a  A, b  B)} Secara umum, hasil kali Kartesian A1, A2, …, An didefinisikan sebagai : A1 x A2 x …. x An = {(a1, a2 ,..., an ) | a1  A1, a2  A2 ,..., an  An } Contoh : Misalkan : A = {a, b, c}; B = {1, 2, 3} Hitunglah : A x B Penyelesaian : A x B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3)} Relasi biner atau hubungan biner (binary relation) dari A ke B ialah suatu himpunan bagian dari A x B. Jika R adalah suatu relasi biner dari A ke B dan jika pasangan terurut (a, b) ada di dalam R, maka dapat dikatakan bahwa unsur a berhubungan dengan unsur b. Contoh : A = {a, b, c, d} B = {1, 2, 3} R = {(a, 1), (b, 3), (c, 1), (c, 3), (d, 2)} merupakan suatu relasi biner dari A ke B. a

A B C D

1 √

2

1 b

√ √

√ √

Tabel 5.1

3

2 c 3 d

Gambar 5.2

Pada Gambar 5.1, dengan baris tabel menunjukkan unsur-unsur himpunan A dan kolom tabel menunjukkan unsur-unsur himpunan B. Tanda cek menandakan bahwa unsur di dalam baris yang mengandung petak itu berhubungan dengan unsur di dalam kolom. Relasi R juga dapat digambarkan dalam Gambar 5.2, dengan titik sebelah kiri Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 1

menggambarkan unsur-unsur himpunan A, dan himpunan B di titik sebelah kanan. Tanda panah menunjukkan bahwa unsur terkait di A berhubungan dengan unsur di B. Relasi terner (ternary relation) digunakan untuk menyatakan hubungan antara pasangan ganda tiga, dan relasi kuarterner (quarternary relation)untuk menyatakan hubungan antara pasangan-pasangan ganda empat, begitu seterusnya. Relasi antar 2 himpunan  binary Relasi antar 3 himpunan  Ternary Relasi antar 4 himpunan  Quarternary Relasi antar n himpunan  n-ary 

Relasi pada Himpunan Misalkan A dan B adalah himpunan-himpunan. Suatu Relasi (biner) R dari A ke B adalah himpunan bagian dari A x B. Jika (a, b)  A x B dan a berelasi dengan b, dituliskan a R b. Jika a tidak berelasi dengan b dituliskan a R b. a

1

b

2

c

3 A

A x B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), (c, 1), (c, 2), (c, 3)} R = {(a, 1), (b, 1), (b, 2)}

B

Gambar 5.2 Relasi n-ary = subset dari A1 x A2 x … x An A1 x A2 x..... An  {(a1, a2 ,..., an ) | ai  Ai } 5.2 Operasi pada Relasi Biner Misalkan R dan S adalah dua buah relasi dari himpunan A ke himpunan B, maka : 

Irisan R  S{(a, b) | (a, b)  R,&(a, b)  S} Contoh : A = {-1, 0, 1} B = {0, 1} Relasi R dan S dari himpunan A ke himpunan B adalah sebagai berikut : R = {(-1, 0), (-1, 1), (0, 1)} S = {(0, 0), (1, 1), (-1, 1)} Carilah R  S Penyelesaian : R  S = {(-1, 1)}



Union R  S  {(a, b) | (a, b)  R, atau (a, b)  S} R  S = {(-1, 0), (-1, 1), (0, 1), (0, 0), (1, 1)}



R–S R  S  {(a, b) | (a, b)  R dan (a, b)  S}

Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 2



R S R  S  (R  S )  (R  S )

Contoh : Didefinisikan relasi R {( x, y) x  A dan y  B dan x  y adalah kelipatan 2 yang tidak nol} .

=

S = {( x, y) x  y adalah kelipatan 3 yang tidak nol} A = B = {2, 3, 4, 5, 6, 7} Tentukan A  B, A  B, A - B, B - A, A  B ! Penyelesaian : R = {(2, 4), (4, 2), (3, 5), (5, 3), (4, 6), (5, 7), (7, 5), (2, 6), (6, 2), (3, 7), (7, 3)} S = {(2, 5), (5, 2), (3, 6), (6, 3), (4, 7), (7, 4)} R S  Ø R  S  {{(2, 4), (4, 2), (3, 5), (5, 3), (4, 6), (5, 7), (7, 5), (2, 6), (6, 2), (3, 7), (7, 3), (2, 5), (5, 2), (3, 6), (6, 3), (4, 7), (7, 4)} R-S=R S–R=S R S  R S 5.3 Sifat Relasi pada Himpunan 1.

Relasi biner pada himpunan A disebut Refleksif jika a R a a  R . R a b c d e

a 1

b

c

d

e

1 1 1 1

Tabel 5.2 Warna hitam menunjukkan refleksif. Tidak refleksif  jika a  A , a R A Anti Refleksif  jika a  A , a R a Contoh : A = {1, 2, 3, 4, 5} R = {(a, b) | a habis dibagi b} Apakah R termasuk relasi refleksif ? Penyelesaian : R 1 2 3 4

1 1

2 1 1

3 1

4 1

5 1

1 1


5

1

Tabel 5.3 Dari tabel diatas, dapat dibuktikan bahwa R memenuhi sifat refleksif. 2.

Relasi biner pada himpunan (a, b)  R maka (b, a)  R, a, b  A Atau a R b maka b R a, a, b  A R a b c d e

a 1

b

A

c

disebut

d

simetris

jika

e 1

1 1

1

Tabel 5.4 Apabila (a, b  A)aRb  bRa disebut Tidak Simetris Apabila (a, b  A)(aRb dan bRa)  a  b disebut Anti Simetris 3.

Relasi biner pada himpunan A disebut Transitif jika ada (a, b)  R , dan (b, c)  R maka (a, c)  R . Atau a R b dan b R c maka a R c. R

a

a

b

c

d

e

1

1

1

1

1

1

1

1

1

b c d

1

e

Tabel 5.5 Daerah yang diarsir merupakan daerah-daerah transitif. 5.4 Relasi Ekuivalensi dan Partisi Relasi ekuivalensi yaitu relasi yang memiliki sifat refleksif, simetris, dan transitif. Contoh : A = {a, b, c, d, e, f} Didefinisikan relasi R = {(a, a), (a, b), (b, a), (b, b), (c, c), (d, d), (d, e), (d, f), (e, d), (e, e), (e, f), (f, d), (f, e), (f, f)}. Apakah R termasuk dalam ekuivalensi ? Penyelesaian : R a b c d e

a 1 1

b 1 1

c

d

e

f

1 1

1 1

1 1

1


f

1

1

1

Tabel 5.6 5.5 Partisi Partisi adalah koleksi himpunan bagian dari A yaitu A1, A2, ….An dengan sifat : (i).

A1  A 2  ...  A n  A

(ii). A1  A 2  Ø i  j  himpunan saling asing yang masing-masing partisi saling berelasi. Relasi ekuivalensi pada himpunan A akan membentuk suatu partisi. Contoh 1 : Partisi = {{a, b}, {c}, {d, e, f}} Sebutkan partisi yang dapat disajikan ? Note : Setiap relasi ekuivalensi pasti memiliki partisi. Penyelesaian :

  {ab, c, def } Contoh 2 : A = {1, 2, 3, 4} π = {{1}, {2}, {3}, {4]} Penyelesaian : 1 2 3 4

1 1

2

3

4

1 1 1

Tabel 5.7 Contoh 3 :

  {ac, df , be} Penyelesaian :

ac = (a, a), (a, c), (c, c),(c, a) df = (d, d), (d, f), (f, f), (f, d) be = (b, b), (b, e), (e, e), (f, e) Tidak termasuk dalam ekuivalensi, karena tidak transitif

a b c d e f

a 1

B

c 1

1 1

d

e

f

1 1 1

1

1

1 1

1

Tabel 5.8 Contoh 4 : Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 5

1

A = Himpunan bilangan Cacah ; n adalah bilangan Asli. Didefinisikan relasi R  {(a, b) a dan b jika dibagi n mempunyai nilai yang sama}  a mod n = b mod n. Ambil n = 4. Penyelesaian : 1).

a mob a  a mod n  aRa  refleksif

2).

jika a mod 4  b mod 4 (aRb )   simetris maka b mod 4  a mod 4 (bRa )

3).

jika a mod 4  b mod 4 (aRb )  b mod 4  c mod 4 (bRc )  transitif a mod 4  c mod a (aRb ) 

Termasuk dalam Ekuivalensi karena mengandung refleksif, simetris dan transitif. Misalkan π1 dan π2 keduanya sekatan himpunan A. Misalkan pada R1 dan R2 masing-masing adalah relasi kesetearaan padanannya. Maka π1 dikatakan lebih halus (refinement) dari π2 dilambangkan π1  π2 jika R1  R2. Dengan kata lain, jika π1 sebuah penghalusan dari π2, maka sembarang dua unsur di dalam blok yang sama dalam π1 juga pasti di dalam blok yang sama dengan π2. Contoh 5 : Himpunan A = {a, b, c, d, e} Misalkan : π1 = partisi yang dihasilkan oleh relasi ekuivalensi R1 π 2 = partisi yang dihasilkan oleh relasi ekuivalensi R2 Didefinisikan :  1 {a, bc, d , e}

 2  {abc, de}

 3  {ab, cd , e} a b c d e

a 1

B 1 1

c

d

a

e

1 1 1 1

a b c

B 1 1

c 1

d

e

1

b

1

1

1

c

1

1

1

d

1

1

e

1

1

R2

R1

a 1 1

a

b 1

c

d

1

1

e


d e

1

1 1

Tabel 5.9 Tabel 5.10

R3

Tabel 5.11 π1  π2  Benar, karena R1  R2 (lihat blok yang dilingkari) π1  π3  Tidak π3  π2  Tidak 5.6 Operasi antar Partisi Didefinisikan : π1 * π2 = π3 yaitu relasi yang digenerate oleh R1  R2 Contoh : A = {a, b, c, d, e}  1 {a, bc, d , e}

 2  {abc, de}  3  {ab, cd , e} Berapakah : π1* π2, π1* π3, π2* π3 Penyelesaian : π1* π2 = {a, bc, d , e} π1* π3 = {a, b, c, d , e} π2* π3 = {ab, b, c, d , e} 5.7 Relasi Terurut Sebagian dan Lattice Definisi : Relasi R pada himpunan A yang mempunyai sifat refleksif, anti simetris dan transitif maka disebut “Partial Ordering Relations”. Contoh 1 : A = {0, 1, 2, 3, 4,…} R = Relasi disimbolkan dengan “ ≤ ” Maka disebut (A, R) disebut himpunan terurut sebagian (Partial Ordering Set)  POSET. 5.12

1 2 3 4

1 1

2 1 1

3 1 1 1

4 1 1 1 1

Tabel


Diagram Hasse nya adalah : 4 3 2 1

Gambar 5.2 Contoh 2 : (B, S) POSET

E

E

a b c d e

a 1

b 1 1

c 1 1 1

d 1

1

e 1 1 1 1 1

C

C

D

D

 diagram Hasse B

B

A

A

Tabel 5.13

Gambar 5.3

Gambar 5.4

Relasi terurut bisa dilambangkan dengan ≤ Bila relasi biner itu berupa suatu relasi pengurutan parsial, sajian grafik bisa lebih disederhanakan. Karena relasi bersifat refleksif, maka panah-panah yang ada dapat dihilangkan (lihat Gambar 5.4) POSET dapat digambarkan dalam suatu diagram yang dikenal dengan diagram Hasse. Jika a ≤ b maka digram Hasse nya : b

a

Gambar 5.5 Note : Panah dihilangkan !! Contoh : S = {a, b, c, d, e, f, g, h, i, j, k} POSET (S, R)


j

k

h

i

f

g

c

d

b

e

a

Gambar 5.6 Penyelesaian : R a b c d e f g h i j k

a 1

b 0 1

C 1 0 1

d 1 0 0 1

e 0 0 0 0 1

f 1 1 1 0 0 1

g 1 0 0 1 1 0 1

h 1 1 1 1 1 1 1 1

i 1 1 1 1 1 1 1 0 1

j 1 1 1 1 1 1 1 1 1 1

k 1 1 1 1 1 1 1 1 1 0 1

Tabel 5.14 Pada POSET (S, R) didefinisikan : 1.

Maksimal  elemen a adalah elemen maksimal dari POSET (S, R), yaitu jika tidak ada b anggota S yang lebih besar dari a. Dari Gambar 5.6, maka nilai maksimalnya adalah {j, k}.

2.

Minimal  elemen a adalah elemen minimal dari POSET (S, R), yaitu jika tidak ada b anggota S yang lebih kecil dari a. Dari Gambar 5.6, maka nilai minmalnya adalah {b, a, c}.

3.

Cover  a  S disebut cover dari b jika tidak ada c  S sehingga b  c  a . Note : bias lebih dari satu atau bisa juga tunggal.

4.

Batas Atas (BA)  Elemen a  S disebut batas atas dari 2 elemen b dan c jika a  b dan a  c . Batas atas b dan e dari Gambar 5.6 adalah {f, g, h, i, j, k}. Dan batas atas a dan b dari contoh diatas adalah {h, i, j, k}.


5.

Batas Bawah (BB)  Elemen a  S disebut batas bawah dari 2 elemen b dan c jika a  b dan a  c . Dari Gambar 5.6, unsur-unsur a, b, c, d, e, f, g semuanya merupakan bb dari h dan i

6.

Batas atas terkecil (bat)  a adalah bat dari b dan c jika tidak ada lagi BA yang lebih kecil dari a  bat tidak selalu tunggal. Bat c dan d dari Gambar 5.6 adalah {h, i}. bat c dan a dari contoh diatas adalah {c}.

7.

Batas bawah terkecil (bbt)  a adalah bbt dari b dan c jika tidak ada lagi bb yang kebih besar dari a. Nilai bbt tidak selalu tunggal.

5.8 Lattice, Chain dan Antichain 

Lattice Lattice adalah POSET dari sifat setiap 2 elemen mempunyai bat dan bb tunggal.

Contoh : E

4

bat dari b dan a adalah b bbt dari b dan d adalah e

C

3

D

2 B

1

A

0

Gambar 5.7

Gambar 5.8 h

e

d

a

f

j

bat dari a dan g adalah h bbt dari a dan g adalah b

c

b

Gambar 5.9 Note : Lattice tidak harus b kecil dari c tetapi harus mempunyai bat dan bbt tunggal. Theorema : Jika (A, R1) adalah POSET dan (B, R2) juga POSET. Misal : C = A x B Didefinisikan relasi R3 pada C sebagai berikut : Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 10

((a1 , b1 ), (a 2 , b 2 ))  R 3 jika (a 1 , a 2 )  R 1 dan (b1 , b 2 )  R 2 Buktikan bahwa (C, R3) = POSET !  membuktikan bahwa (C, R3) merupakan relasi terurut sebagian, artinya memiliki refleksif, anti simetris, dan transitif. Bukti : 1.

Refleksif Artinya :

(a 1 , a 1 )  R 1

 (A, R1)  POSET

(b1 , b1 )  R 2

 (B, R2)  POSET

Maka ((a 1 , b1 ), (a 1 , b1 ))  R 3  benar  Refleksif Atau dapat juga didefinisikan : Karena (A, R1) = POSET  (a 1 , a 1 )  R 1 ,  a 1  A (B1, R2)= POSET  (b1 , b1 )  R 2 ,  b1  B

((a 1 , b1 )(a1 , b1 ))  R 3 2.

Anti Simetris Misal ((a 1 , b1 ), (a 2 , b 2 ))  R 3 Artinya : (a 1 , a 2 )  R 1  (a 2 , a 1 )  R 1

(b1 , b 2 )  R 2  (b 2 , b1 )  R 2 ((a 2 , b 2 ), (a 1 , b1 ))  R 3 3.

Transitif Misal : ((a 1 , b1 ) (a 2 , b 2 ))  R 3 dan

((a 2 , b 2 ) (a 3 , b 3 ))  R 3

(a 1 , a 2 )  R 1   dan ( b1 , b 2 )  R 2 

(a 2 , a 3 )  R 1  (a 1 , a 3 )  R 1 (b 2 , b 3 )  R 2  (b 2 , b 3 )  R 2

((a 1 , b1 ), (a 3 , b 3 ))  R 3 Kesimpulan : (C, R3) = POSET  Terbukti


Contoh : Misal : A = {a, b, c, d} B = { ,  } Dengan (A, ) sebagai berikut : d b

c a

Gambar 5.9 Dan ( B,  ) sebagai berikut : α

β

Gambar 5.10 C = A x B = {(a, α), (a, β), (b, α), (b, β), (c, α), (c, β), (d, α), (d, β)} Maka (C, R3) adalah : (d, β) (b, β)

(c, β)

(d, α) (a, β) (c, α)

(b, α) (a, α)

Gambar 5.11 

Chain

Definisi : Dalam POSET (S, ≤), C subset S disebut Chain jika setiap 2 elemen di C dapat dibandingkan (jika setiap a, b  C maka berlaku a ≤ b atau b ≤ a) sedangkan |C| disebut panjang chain. Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 12

e

S = {a, b, c, d, e} {a, b, d}  bukan Chain karena b dan d tidak bias dibandingkan. {a, d, e}  Chain

c d b

a

Gambar 5.12 

Anti Chain

Definisi : Dalam suatu POSET (S, ≤) himpunan bagian A dari S disebut Anti Chain jika tidak ada a dan b sebagai a ≤ b atau b ≤ a. Contoh : {c, d}, {b, d}, {a} Theorema : Jika (S, ≤) adalah POSET dan S mempunyai panjang rantai (Chain) terpanjang = n, maka S dapat dibuat partisi yang terdiri atas n buah Anti Chain yang saling asing. 1.

Basis Induksi Untuk n = 1 tidak ada elemen yang dihasilkan karena elemen hanya satu dan elemen tersebut merupakan Anti Chain.

2.

Asumsikan -

Panjang rantai terpanjang di POSET = n-1

-

S = POSET

-

M = elemen maksimum di S

-

Sehingga POSET : (S-M, ≤)

-

Tidak ada panjang Chain di S-M

-

Jika Chain terpanjang S-M < n-1, M harus terdiri dari dua atau lebih elemen yang merupakan anggota Chain yang sama dan hal itu tidak mungkin.

-

Sehingga Chain terpanjang di S-M adalah n-1

-

Sehingga S-M bisa dipartisi menjadi n-1 disjoint anti chain.

-

Kemudian S dapat dipartisi menjadi n disjoint anti chain.

Bukti Theorema diatas adalah  Dibuktikan dengan induksi matematika : 1.

untuk n = 1 Tidak ada 2 elemen yang dapat dibandingkan (Anti Chain). Jadi pada S dapat dibuat 1 buah Anti Chain yaitu S itu sendiri.


Misal benar untuk (n-1) akan dibuktikan kebenarnnya untuk (n) artinya : (P ≤ n) : POSET yang panjang Chain terpanjang = n

2.

Misal M = Himpunan semua elemen maksimum dari P  M adalah Anti Chain. (P-M, ≤) : POSET dengan panjang Chain terpanjang = n-1. Menurut hipotesis (P-M) terdiri dari (n-1) Anti Chain. P = (P-M)  M terdiri dari (n-1) + 1 = n. j

i

Mempunyai panjang Chain = 4 Anti Chain theorema = 4

h

g

f

e d b

a

Gambar 5.13 Anti Chain pada gambar tersebut adalah : Maksimum j

i

h

g

f

e d

c

Anti Chain 4 (yang saling asing) Maksimum 1 = i, j, f Maksimum 2 = g, h Maksimum 3 = d, e, c Maksimum 4 = a, b Chain terpanjang = 4 a, d, g, i atau b, d, g, i

b

a

Gambar 5.14 Minimal j

i

h

g

f

Minimum 1 = a, b, e, c Minimum 2 = d, f Minimum 3 = g, h Minimum 4 = i, j

e d

c a

b

Gambar 5.15 Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 14

5.9 Fungsi

fungsi

relasi Gambar 5.16

Gambar 5.17

Fungsi  semua anggota A (domain) dikawankan tepat hanya satu anggota A (kodomain). F  A  B, a  A b  B, a  (b)

bukan fungsi fungsi

Gambar 5.18

Gambar 5.19

5.10 Penyajian Fungsi A

B

1

a

A = {1, 2, 3, 4} B = {a, b, c}

2

b

3 c 4

Gambar 5.20 Dapat disajikan dengan : 1. 1 2 3 4

2. a 1 0 1 0

b 0 1 0 1

c 0 0 0 0

= = = =

1 1 1 1

A 1 2 3 4

B a b c d

Tabel 5.16 Fungsi jika Rowsum Tabel 5.15 Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 15

5.11 Macam – Macam Fungsi 1.

Surjektif (onto)  fungsi pada onto  fungsi dimana setiap anggota di B memiliki kawan di A. A  B A

B

1

a

2

b

3 c 4

Gambar 5.21 2.

Injektif (fungsi satu – satu) A

B a

1

b

2

c 3

d

4

e

Gambar 5.22 3.

Bijektif (berkorespondensi satu-satu) A

B a

1

b

2

c 3

d

4

Gambar 5.23 Bila dan hanya bila fungsi tersebut injektif dan sekaligus surjektif. 5.12 Pigeon Hole Principle 

Jika jumlah merpati > jumlah kotak merpati, maka ada satu kotak merpati yang terisi lebih dari satu merpati.



Jika A dan B dua himpunan berhingga dengan | A | > | B | maka untuk setiap fungsi F = A  B pasti terdapat ai dan aj di A sehingga F(ai) = F (aj) atau untuk setiap fungsi F = A  B terdapat k buah elemen a1, a2, … ak  A sehingga F (an) = F (a1) = … = F (ak) dengan K = A / B






Misal : A = {1, 2, 3, 4, 5}

| A | = 5 ; k = 5/3

B = {a, b, c}

|B|=3;k=2

A

B

1

a

2 b 3 c 4 5

Gambar 5.24 5.13 Penjadwalan Dipunyai n buah job dan p buah prosssor yang “identik”. Yang dimaksud dengan “identik” adalah prosessor bisa mengerjakan job apa saja. Tujuan dilakukannya penjadwalan adalah untuk meminimalkan “idle time”. Idle time adalah waktu menganggur yang tidak disengaja. Contoh : Terdapat 7 buah task atau job (T1, T2, …., T7) dengan 3 buah prosessor P1P2P3 yang digambarkan sebagai berikut : T4/2

T1/2

T1 ≤ T3 ≤ T4 T2 ≤ T3 ≤ T4 : : T2 ≤ T3 ≤ T7 Ada 8 cara, dihitung dari 2 x 1 x 4 = 8

T5/2 T6/4 T3/1 T7/1

T2/2

Gambar 5.25 Penyelesaian: P1

P2

T1

T3

T4

T7

2

1

2

1

T2

T5

2

2

Total waktu = 7 Idle time = 7

T6 P3

4

Gambar 5.26 Pusat Pengembangan Pendidikan - Universitas Gadjah Mada 17

Contoh 2 : Diketahui 6 task dengan 2 prosessor sebagai berikut : T1/10

T4/5

T6/9

T5/5

T2/9

T3/9

Gambar 5.27 Penyelesaian : Solusi : P1

P2

T1

T4

T6

10

5

9

T2

T5

T6

5

9

9

Total waktu = 24 Idle time = 1

Gambar 5.28


5. RELASI DAN FUNGSI. Gambar 5.1

Recommend Documents