3.2 RelasiKita tulis kembali definisi perkalian kartesian. Perkalian kartesian (cartesian product) dari himpunan A dan B adalah himpunan yang elemennya semua pasangan terurut (order pairs) yang mungkin terbentuk dengan komponen pertama dari himpunan A dan komponen kedua dari himpunan B.

Relasi antara himpunan A dan B –disebut relasi biner- didefinisikan sebahai berikut:

Jika (a, b) R, kita gunakan notasi a R b yang artinya a dihubungkan dengah b oleh R, dan jika (a, b) R, kita gunakan notasi a R b yang artinya a tidak dihubungkan oleh b oleh relasi R. Himpunan A disebut daerah asal (domain) dari R, dan himpunan B disebut daerah hasil (range atau codomain) dari R.

Contoh 3.11Misalkan A = {Amir, Budi, Cecep} adalah himpunan nama mahasiswa, dan B = (IF221, IF251, IF342, IF323} adalah himpunan kode mata kuliah di Jurusan Teknik Informatika. Perkalian kartesian antara A dan B menghasilkan himpunan pasangan terurut yang jumlah anggotanya adalah |A|.|B| = 3 . 4 = 12 buah, yaitu

A x B = {(Amir, IF221), (Amir, IF251), (Amir, IF342), (Amir, IF323),(Budi, IF221), (Budi, IF251), (Budi, IF342), (Budi, IF323),( Cecep, IF221), (Cecep, IF251), (Cecep, IF342), (Cecep, IF323)}

Misalhan R adalah relasi yang menyatakan mata kuliah yang oleh mahasiswa pada Semester Ganjil, yaitu

R = {(Amir, IF251), (Amir, IF323), (Budi, IF221), (Budi, IF251), (Cecep, IF323)}

Kita dapat melihat bahwa R (A x B), A adalah daerah asal R, dan B adalah daerah hasil R. Oleh karena (Amir, IF251) R, kita dapat menuliskan Amir R IF251, tetapi (Amir, IF342) R sehingga kita menuliskan Amir R IF342.

Contoh 3.12Misalkan P = {2, 3, 4} dan Q = {2, 4, 8, 9, 15}. Jika kita definisikan relasi R dari P dan Q dengan

(p, q) R jika p habis membagi q

Maka kita peroleh

R = {(2,2), (2,4), (4,4), (2,8), (4,8), (3,9), (3,15)}

Notasi: A x B = {(a, b) |a A dan B

DEFINISI 3.2. Relasi biner R antara A dan B adalah himpunan bagian dari A x B.

Notasi: R (A x B).

B Q

A P

Gambar 3.1 diagram panah masing-masing untuk (a) Contoh 3.11 dan (b) Contoh 3.12

Dengan kata lain, relasi pada himpunan A adalah himpunan bagian dari A x A.

Contoh 3.13

Misalkan R adalah relasi pada A = {2, 3, 4, 8, 9} yang didefinisikan oleh (x, y) R jika x adalah factor prima dari y. Maka

R = {(2,2), (2,4), (2,8), (3,3), (3,9)}

3.3 Representasi Relasi

3.3.1 Representasi Relasi dengan Tabel

Relasi biner dapat direpresentasikan sebagai tabel. Kolom pertama tabel menyatakan daerah asal, sedangkan kolom kedua menyatakan daerah hasil.

Relasi R pada Contoh 3.11 dapat dinyatakan dengan Tabel 3.1, sedangkan relasi R pada Contoh 3.12 dinyatakan dengan Tabel 3.2

Amir

Budi

Cecep

IF221

IF251

IF342

IF323

2

3

4

24

89

15

DEFINISI 3.3. Relasi pada himpunan A adalah relasi dari A x A.

Tabel 3.1 Tabel 3.2

A

B

2242433

24488915

3.3.2 Representasi Relasi dengan Matriks

Misalkan R adalah relasi dari A = {a1 , a2 ,…,am} dan B = {b1 , b2 ,…,bn}. Relasi R dapat disajikan

dengan matriks M = [mij],

M=

a1

a2

⋮am[

b1b2 ⋯ bn

m11m12 ⋯ m1n

m21m22 … m2n

⋮ ⋮ ⋮ ⋮mm1mm2 ⋯ mmm

]Yang dalam hal ini

mij={1 , (ai ,b j )∈R

0 , (bi , b j )∉R

Dengan katalain, elemen matriks pada posisi (i, j) bernilai 1 jika a i dihubungkan dengan b j, bernilai 0

jika a i tidak dihubungkan b j. Matriks representasi relasi merupakan contoh matriks zero-zone.

3.3.3 Representasi Relasi dengan Graft Berarah

Relasi pada sebuah himpunan dapat dapat direpresentasikan secara grafis dengan graf berarah (directed graph atau digraph). Tiap elemen himpunan dinyatakan dengan sebuah titik (disebut juga simpul atau vertex), dan setiap pasangan berurut dinyatakan dengan busur (arc) yang arahnya

A B

AmirAmirBudiBudi

Cecep

IF251IF323IF221IF251IF323

ditunjukkan dengan sebuah panah. Dengan kata lain, jika (a, b) R, maka sebuah busur dibuat dari simpul a ke simpul b. Simpul a disebut simpul asal (initial vertex) dan simpul b disebut simpul tujuan (terminal vertex).

Sebagai contoh, misalkan R = {(a, a), (a, b), (b, a), (b, c), (b, d), (c, a), (c, b), (d, b)} adalah relasi pada himpunan {a, b, c, d}. R dipresentasikan dengan graf berarah. Perhatikan bahwa a mempunyai busur ke simpul a lagi. Busur yang mempunyai simpul asal sama dengan simpul tujuan dinamakan kalang (loop)

3.4 Relasi Inversi

Contoh 3.14Misalkan P = {2, 3, 4} dan Q = {2, 4, 8, 9, 15}. Jika kita definisikan relasi R dari P ke Q dengan

(p,q) R jika p habis membagi q

Maka kita peroleh

R = {(2,2), (2,4), (4,4), (2,8), (4,8), (3,9), (3,15)}

R−1 adalah invers dari R, yaitu relasi dari Q ke P dengan

(q,p) R−1 jika q adalah kelipatan dari p

maka kita peroleh

R−1 = {(2,2), (4,2), (4,4), (8,2), (8,4), (9,3), (15,3)}

Jika M adalah matriks yang mempresentasikan relasi R,

M=[1 10 00 1

1 0 00 1 11 0 0]

maka matriks yang mempresentasikan relasi R−1, misalkan N, diperoleh dengan melakukan transpose

terhadap matriks M,

N=M T=[1 0 01 0 11 0 10 1 00 1 0

]

DEFINISI 3.4. Misalkan R adalah relasi dari himpunan A ke himpunan B. Inversi dan relasi R, dilambangakan dengan R−1, adalah relasi dari B ke A yang didefinisikan oleh

R−1={(b ,a)∨(a ,b)∈ R }

3.5 Mengkombinasikan RelasiKarena relasi biner merupakan himpunan pasangan terurut, maka operasi himpunan seperti irisan, gabungan, selisih, dan beda setangkup antara dua relasi atau lebih juga berlaku. Hasil operasi tersebut

juga berupa relasi. Dengan kata lain, jika R1 dan R2 masing-masing adalah relasi dari himpunan A ke

B, maka operasi R1∩R2 ,R1∪R2 ,R1−R2 ,R1⨁ R2 juga adalah relasi dari A ke B.

Contoh 3.15

Misalkan A = {a, b, c} dan B {a, b, c, d}. Relasi R1 = {(a, a), (b, b), (c, c)} dan relasi R2 = {(a, b),

(a,c),(a, d)} adalah relasi dari A ke B. Kita dapat mengkombinasikan kedua buah relasi tersebut untuk memperoleh:

R1∩R2={ (a ,a ) }R1∪R2={ (a ,a ) , (a ,b ) , (c , c ) , (a ,b ) , (a , c ) , (a ,d)}R1−R2={(b ,b ) , (c , c )}R2−R1={(a ,b ) , (a , c ) , (a ,d ) }R1⨁ R2={ (b ,b ) , (c ,c ) , (a ,b ) , (a , c ) , (a ,d )}

3.6 Komposisi Relasi

Dengan kata lain, menurut Definisi 3.5, kita menerapkan relasi R lebih dahulu, baru kemudianrelasi S.

Contoh 3.17Misalkan R = {(1, 2), (1, 6), (2, 4), (3, 4), (3, 6), (3, 8)} adalah relasi dari himpunan {1, 2, 3} ke himpunan {2, 4, 6, 8} dan S {2, u), (4, s), (4, t), (6, t), (8, u)} adalah relasi dari himpunan {2, 4, 6, 8} ke himpunan {s, t, u}. Maka komposisi relasi R dan S adalah

S o R = {(1, u), (1, t), (2, s), (2, t), (3, s), (3, t), (3,u)}

Komposisi relasi R dan S lebih jelas lagi jika diperagakan dengan diagram panah (Gambar 3.3)

DEFINISI 3.5. Misalkan R adalah relasi dari himpunan A ke himpunan B, dan S adalah relasi dari himpunan B ke himpunan C. Komposisi R dan S, dinotasikan dengan S o R, adalah relasi dari A ke C yang didefinisikan oleh

So R={(a , c )|a∈ A ,c∈C ,danuntuk beberapab∈B , (a ,b )∈Rdan (b ,c )∈S }

1

2

3

2

4

6

8

s

t

u

Gambar 3.3 Diagram panah yang memperlihatkan komposisi relasi R dan S pada Contoh 3.17.

3.7 Sifat-sifat Relasi1. Refleksif (reflexive)

Contoh 3.20Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka(a) Relasi R = {(1, 1), (1, 3), (2, 1), (2, 2), (3, 3), (4, 2), (4, 3), (4, 4)} bersifat refleksif karena terdapat elemen relasi yang berbentuk (a, a), yaitu (1, 1), (2, 2), (3, 3), 4, 4).(b) Relasi R = {(1, 1), (2, 2), (2, 3), (4, 2), (4, 3), (4, 4)} tidak bersifat refleksif karena (3, 3) R.

2. Setangkup (symemetric) dan Tolak-setangkup (antisymmetric)

Contoh 3.23Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini di definisikan pada himpunan A, maka(a) Relasi R = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 4), (4, 2), (4, 4)} bersifat setangkup karena jika(a, b) R maka (b, a) juga R. Di sini (1, 2) dan (2, 1) R, begitu juga (2, 4) dan (4, 2) R.(b) Relasi R = {(1, 1), (2, 3), (2, 4), (4, 2)} tidak setangkup karena (2, 3) R, tetapi (3, 2) R.(c) Relasi R = {(1, 1), (2, 2), (3, 3) tolak-setangkup karena (1, 1) R dan 1 = 1, (2, 2) R dan 2 = 2, (3, 3) R dan 3 = 3. Perhatikan bahwa R juga setangkup.(d) Relasi R = {(1, 1), (1, 2), (2, 2), (2, 3)} tolak-setangkup karena (1, 1) R dan 1 = 1 dan, (2, 2)

1

2

3

2

4

6

8

s

t

u

DEFINISI 3.6. Relasi R pada himpunan A disebut refleksif jika (a, a) R untuk setiap a A.

DEFINISI 3.7. Relasi R pada himpunan A disebut setangkup jika (a, b) R, maka (b, a) R, untuk semua a, b A.

DEFINISI 3.7. Relasi R pada himpunan A disebut tolak-setangkup jika (a, b) R, dan(b, a) R maka a = b, untuk semua a, b A.

R dan 2 = 2. Perhatikan bahwa R tidak setangkup.(e) Relasi R = {(1, 1), (2, 4), (3, 3), (4, 2)} tidak tolak-setangkup karena 2 ≠ 4 tetapi (2, 4) dan (4, 2) anggota R. Relasi R pada (a) dan (b) di atas juga tidak tolak-setangkup.(f) Relasi R = {(1, 2), (2, 3), (1, 3)} tidak setangkup tetapi tolak-setangkup.

3. Menghantar (transitive)

Contoh 3.26Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka(a) R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} bersifat menghantar. Periksa dengan membuat tabel berikut:

Pasangan Terbentuk

(a, b) (b, c) (a, c)(3, 2)(4, 2)(4, 3)(4,3)

(2, 1)(2, 1)(3, 1)(3,2)

(3, 1)(4, 1)(4, 1)(4,2)

(b) R = {(1, 1), (2, 3), (2, 4), (4, 2)} tidak menghantar karena (2, 4) dan (4, 2) R, tetapi (2, 2) R, begitu juga (4, 2) dan (2, 3) R, tetapi (4, 3) R.(c) R = {(1, 1), (2, 2), (3, 3), (4, 4)} jelas menghantar (tunjukkan!).(d) R = {(1, 2), (3, 4) menghantar karena tidak ada (a, b) R dan (b, c) R sedemikian sehingga (a, c) R.(e) Relasi yang hanya berisi satu elemen seperti R = {(4, 5)} selalu menghantar (alasannya sama seperti jawaban (d) di atas.

3.8 Relasi Kesetaraan

Sebagai contoh, misalkan R adalah relasi pada himpunan mahasiswa sedemikian sehingga(a, b) R jika a satu angkatan dengan b. Karena setiap mahasiswa seangkatan dengan dirinya sendiri, maka R jelas reflestif. Perhatikan, jika a seangkatan dengan b, maka b pasti seangkatan dengan a. Jadin R setangkup. Selanjutnya, jika a seangkatan dengan b dan b seangkatan dengan c, maka pastilah a seangkatan dengan c. Jelas, R bersifat menghantar. Dengan demikian, R adalah relasi kesetaraan.

DEFINISI 3.9. Relasi R pada himpunan A disebut menghantar jika (a, b) R dan (b, c) R, maka (a, c) R, untuk semua a, b, c A.

DEFINISI 3.10. Relasi R pada himpunan A disebut relasi kesetaraan (equivalence relation) jika ia reflektif, setangkup dan menghantar.

3.9 Relasi Pengurutan Parsial

Relasi ≥ pada himpunan bilangan bulat adalah relasi pengurutan parsial. Hal ini dijelaskan sebagai berikut: Karena a ≥ a untuk setiap bilangan bulat a, relasi ≥ refleksif. Relasi ≥ tolak-setangkup karena jika a ≥ b dan b ≥ a, maka a = b. Relasi ≥ menghantar, karena jika a ≥ b dan b ≥ c, maka a ≥ c.

3.10 Klosur RelasiMisalkan R adalah relasi yang tidak refleksif. Kita dapat membuat relasi baru yang mengandung R sedemikian sehingga relasi baru tersebut menjadi refleksif. Relasi baru tersebut haruslah relasi terkecil yang mengandung R. Sebagai contoh, relasi R = {(1, 1), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3)} pada himpunan A = {1, 2, 3} tidak refleksif.Bagaiman membuat relasi refleksi, yang sesedikit mungkin dan mengandung R? Untuk melakukan hal ini, kita hanya perlu menambahkan (2, 2) dan (3, 3) ke dalam R karena dua elemen relasi ini yang belum terdapat di dalam R. Relasi baru yang terbentuk, dilambangkan dengan S, mengandung R, yaitu

S = {(1, 1), (1, 3), (2, 2), (2, 3), (3, 2), (3, 3)}

Sekarang, S bersifat refleksif. Relasi S disebut klosur reflektif (reflexive closure) dari R. Sembarang relasi lain yang mengandung R harus juga membuat (2, 2) dan (3, 3). Catat juga bahwa S adalah himpuanan bagian dari sembarang relasi refleksif lain yang memuat R.

Ada tiga jenis klosur dan cara-cara membentuk ketiga klosur tersebut dijelaskan di bawah ini.

Klosur Refleksif (reflexive closure)Misalkan R adalah sebuah relasi pada himpunan A. Klosur refleksif dari R adalah R∪∆, yang dalam hal ini ∆ = {(a, a) | a A}. Pada contoh kita di atas, R = {(1, 1), (1, 3), (2, 3), (3, 2)}

adalah relasi pada himpunan A = {1, 2, 3}, maka ∆ = {(1, 1), (2, 2), (3, 3)}, sehingga klosur refleksif dari R adalah

R∪∆={(1 ,1 ) , (1 ,3 ) , (2 ,3 ) , (3 ,2 ) }∪ {(1 ,1 ) , (2 ,2 ) , (3 ,3 ) } ¿{(1 ,1 ) , (1 ,3 ) , (2,2 ) ,(2,3) ,(3 ,2) ,(3 ,3)}

Contoh 3.31

Misalkan R adalah relasi {(a, b) | a ≠ b} pada himpunan bilangan bulat. Maka, klosur refleksi dari R adalah

R∪∆={(a ,b)∨a≠b }∪{(a ,a )|aZ }= {(a ,b )|a ,b Z }

Klosur Setangkup (symmetric closure)Misalkan R adalah relasi pada himpunan A. Klosur setangkup dari R adalah R∪R−1, yang dalam hal

DEFINISI 3.11. Relasi R pada himpunan S dikatakan relasi pengurutan parsial (partial ordering relation) jika ia refleksif, tolak-setangkup, dan menghantar. Himpunan S bersama-sama dengan relasi R disebut himpunan terurut secara parsial (partially orderer set, atau poset) dan dilambangkan dengan (S, R).

ini R1 = {(b, a) | (a, b) R}. Pada contoh kita diatas, R = {(1, 3), (1, 2), (2, 1), (3, 2), (3, 3)} adalah

relasi pada himpunan A = {1, 2, 3}, maka R−1 = {(3, 1), (2, 1), (1, 2), (2, 3), (3, 3)} sehingga klosur

setangkup dari R adalah

R∪R−1={(1 ,3 ) , (1 ,2 ) , (2 ,1 ) , (3 ,2 ) , (3 ,3 )∩{(3 ,1) ,(2 ,1) ,(1 ,2) ,(2 ,3), (3 ,3)} ¿{(1 ,3 ) , (3 ,1 ) , (1 ,2 ) , (2 ,1 ) , (3 ,2 ) , (2 ,3 ) ,(3 ,3)}

Contoh 3.32Misalkan R adalah relasi {(a, b) | a habis mebagi b} pada himpunan bilangan bulat. Maka, klosur stangkup dari R adalah

R∪R−1= {(a ,b )|ah abismembagi b }∪ {(b ,a )|bhabismembagi a } ¿ {(a ,b )|ahabismembagi bataub habismembagi a }

Klosur Menghantar (transitive closure)Pembentukan klosur menghantar lebih sulit daripada 2dua buah klosur seblelumnya. Sebagai contoh, misalkan R = {(1, 2), (1, 4), (2, 1), (3, 2)} adalah relasi pada himpunan A = {1, 2, 3}. Relasi ini tidak transitif karena tidak mengandung semua pasangan (a, c) sedemikian sehingga (a, b) dan (b, c) di dalam R. Pasangan (a, c) yang tidak terdapat di dalam R adalah (1, 1), (2, 2), (2, 4), dan (3, 1). Pembentukan semua pasangan ini ke dalam R sehingga menjadi

S = {(1, 2), (1, 4), (2, 1), (3, 2), (1, 1), (2, 2), (2, 4), (3, 1)}

Tidsk menghasilkan relasi yang bersifat menghantar karena, misalnya terdapat (3, 1) S dan(1, 4) S, tetapi (3, 4) S.

Ingatlah bahwaRn=R o Ro…o R. Bukti untuk teorema inti tidak ditulis disini dan dapat ditemukan

di dalam [ROS03].

Dari lemma ini kita dapat menunjukkan bahwa klosur menghantar dari R adalah

R¿=R∪R2∪R3∪…Rn

Karena terdapat lintasan di dalam R¿ antara dua simpul jika dan hanya jika terdapat lintasan antara

simpul-simpul ini di dalam Ri, untuk i positif dengan I ≤ n.

TEAOREMA 3.1. Klosur menghantar dari relasi R adalah

¿ R¿¿n=1¿∞Rn

LEMMA 3.1. Misalkan A adalah himpunan dengan n elemen, dan R adalah relasi pada himpunan A. Jika terdapat lintasan dengan panjang minimal 1 di dalam R dan a ke b, maka lintasan semacam itu panjangnya tidak melebihi n.

JikaMR adalah matriks yang mempresentasikan relasi R pada sebuah himpunan dengan n elemen,

maka matriks klosur menghatar R¿ adalah

MR ¿=MR∨MR[2]∨MR

[3]∨…∨MR[n]

Contoh 3.33Misalkan R = {(1, 1), (1, 3), (2, 2), (3, 1), (3, 2)} adalah relasi pada himpunan A = {1, 2, 3}. Tentukan klosur menghantar dari R.

Penyelesaian:Matriks yang mempresentasikan relasi R adalah

MR=[1 0 10 1 01 1 0]

Maka, matriks klosur menghanra dari R adalah

MR ¿=MR∨MR[2]∨MR

[3]

Karena

MR[2]=M R. MR=[1 1 1

0 1 01 1 1]danMR

[3 ]=MR[2] . MR=[1 1 1

0 1 01 1 1 ]

maka

MR ¿=[1 0 10 1 01 1 1]∨[1 1 1

0 1 01 1 1 ]∨[1 1 1

0 1 01 1 1 ]=[1 1 1

0 1 01 1 1]

Dengan demikian R¿ = {(1, 1), (1, 2), (1, 3), (2, 2), (3, 1), (3, 2), (3, 3)}

3.11 Relasi n-ary

Contoh 3.34Misalkan

NIM = {13598011, 13598014, 13598015, 13598019, 13598021, 13598025}Nama = {Amir, Santi, Irwan, Ahmad, Cecep, Hamdan}

DEFINISI 3.12. Misalkan A1 , A2 ,…, An adalah himpunan. Relasi n-ary Rpad himpunan-

himpunan tersenut adalah himpunan bagian dari A1 x A2 x…x An, atau dengan notasi R

A1 x A2 x…x An. Himpunan A1 , A2 ,…, An disebut daerah asal (domain) relasi dan n disebut derajat.

MatKul = {Matematika Diskrit, Algoritma, Struktur Data, Arsitektur Komputer}Nilai = (A, B, C, D, E}

Berturut-turut adalah himpunan Nomor Induk Mahasiswa, himpunan nama-nama mahasiswa, himpunan nama-nama matakuliah, dan himpunan nilai mata kuliah. Relasi MHS yang terdiri dari 5-tupel (NIM, Nama, Matkul, Nilai) mempresentasikan hubungan antara nomor induk mahasiswa, namanya, mata kuliah yang diambilnya, dan nilai mata kuliah,

MHS⊆NIM x Nama xMatKul x Nilai

Satu lagi contoh relasi yang bernama MHS adalahMHS = {(13598011, Amir, Matematika Diskrit, A), (13598011, Amir, Arsitektur Komputer, B), (13598014, Santi, Arsitektur Komputer, D), (13598015, Irwan, Algoritma, C), (13598015, Irwan, Struktur Data, C), (13598015, Irwan, Arsitektur Komputer, B), (13598019, Ahmad, Algoritma, E), (13598021, Cecep, Algoritma, A), (13598021, Cecep, Arsitektur Komputer, B), (13598025, Hamdan, Matematika Diskrit, B), (13598025, Hamdan, Algoritma, A), (13598025, Hamdan, Struktur Data, C), (13598025, Hamdan, Arsitektur Komputer, B)}

Relasi MHS di atas juga dapat ditulis dalam bentuk Tabel 3.4

Tabel 3.4

NIM Nama MatKul Nilai13598011135980111359801413598015135980151359801513598019135980211359802113598025135980251359802513598025

AmirAmirSantiIrwanIrwanIrwanAhmadCecepCecepHamdanHamdanHamdanHamdan

Matematika DiskritArsitektur KomputerAlgoritmaAlgoritmaStruktur DataArsitektur KomputerAlgoritmaAlgoritmaArsitektur KomputerMatematika DiskritAlgoritmaStruktur DataArsitektur Komputer

ABDCCBEBBBACB

3.12 Fungsi

DEFINISI 3.13. Misalkan A dan B himpunan. Relasi biner f dan A ke B merupakan suatu fungsi jika setiap elemen di dalam A dihunungkan dengan tepat satu elemen di dalam B.Jika f adalah fungsi dari A ke B kita menuliskan

f: A → B

yang artinya f memetakan A ke B.

Nama lain untuk fungsi adalah pemetaan atau transformasi. Kita menuliskan f(a) = b jika elemen a di dalam A dihubungkan dengan elemen b di dalam B. Himpunan A disebut daerah asal (domain) dari f dan himpunan B disebut daerah hasil (codomain) dari f. Jika f(a) = b, maka b dinamakan bayangan (image) dari a dan a dinamakan pra-bayangan (pre-image) dari b. Himpunan yang berisi semua nilai pemetaan f disebut jelajah (range) dari f. Perhatikan bahwa jelajah f adalah himpunan bagian (mungkin proper subset) dari B. Gambar 3.5 mempresentasikan fungsi dari A ke B.

Gambar 3.5 Fungsi f memetakan A ke B

Fungsi adalah relasi yang khusus. Kekhususan ini tercakup pada dua hal penting [DOE85]:

1. Tiap elemen di dalam himpunan A, yang merupakan daerah asal f, harus digunakan oleh prosedur atau kaidah yang mendefinisikan f.

2. Frasa “dihubungkan dengan tepat satu elemen didalam B” berarti bahwa jika(a,b) f dan (a,c) f, maka b = c.

Fungsi dapat dispesifikasikan dalam berbagai bentuk, diantaranya:

1. Himpunan pasangan terurut.Ingatlah bahwa fungsi adalah relasi, sedangakn relasi biasanya dinyatakan sebagai himpunan pasangan terurut.

2. Formula pengisian nilai (assignment).Di dalam kuliah aljabar atau kalkulus, fungsi dispesifikasikan dalam bentuk rumus pengisian

nilai (assignment), misalnya f(x) = 2x + 10, f(x) = x2, dan f(x) = 1/x. Jika himpunan daerah

asal maupun daerah hasil fungsi tidak dinyatakan secara spesifik, maka diasumsikan daerah asal fungsi adalah R dan daerah hasilnya juga R. Dalam himpunan pasangan terurut kita

mendefinisikan fungsi sebagai f = {(x , x2) | x R}.

3. Kata-kata.Fungsi dapat dinyatakan secara eksplisit dalam rangkaian kata-kata. Misalnya “f adalah fungsi yang memetakan jumlah bit 1 di dalam suatu string biner”.

4. Kode program (source code).Fungsi dispesifikasikan dalam bentuk kode program computer. Misalnya dalam Bahasa

A B

f

a b

Pascal, fungsi yang mengembalikan nilai mutlak dari sebuah bilangan bulat x, yaitu |x|, ditulis sebagai berikut:

Function abs (x : integer) : Integer;Begin If x < o then abs := -x else abs := x;end;

Dalam asal dari fungsi abs di atas secara jelas dinyatakan himpunan bilangan bulat (integer), dan daerah hasilnya juga himpunan bilangan bulat.

Contoh 3.37Relasi f = {(1,u), (2,v), (3,w)} dari A = {1, 2, 3} ke B = {u, v, w} adalah fungsi dari A ke B. Di sini f(1) = u, f(2) = v, dan f(3) = w. Daerah asal dari f adalah A dan daerah hasil adalah B. Jelajah dari f adalah {u ,v ,w}, yang dalam hal ini sama dengan himpunan B.

Gambar 3.6 mengilustrasikan Fungsi satu-ke-satu.

DEFINISI 3.14. Fungsi f dikatakan satu-ke-satu (one-to-one) atau injektif (injective) jika tidak ada dua elemen himpunan A yang memiliki bayangan sama. Dengan kata lain, jika a dan b adalah anggota himpunan A, maka f(a) ≠ f(b) bilamana a ≠ b. Jika f(a) = f(b) maka implikasinya adalah a =b.

A B

abcd

12345

DEFINISI 3.14. Fungsi f dikatakan pada (onto) atau surjektif (surjective) jika setiap elemen himpunan B merupakan bayangan dari satu atau lebih elemen himpunan A.Dengan kata lain seluruh elemen B merupakan jelajah dari f. Fungsi f disebut fungsi pada himpunan B.

Gambar 3.7 mengilustrasikan Fungsi pada

Contoh 3.45Relasi f = {(1,u), (2,u), (3,v)} dari A = {1, 2, 3} ke B {u, v, w} bukan fungsi pada karena w tidak termasuk jelajah dari f. Relasi {(1,w), (2,u), (3,v)} dari A = {1, 2, 3} ke B {u ,v ,w} merupakan fungsi pada karena semua anggota B merupakan jelajah dari f.

Contoh 3.47Relasi f = {(1,u), (2,w), (3,v)} dari A = {1, 2, 3} ke B = {u, v, w} adalah fungsi yang berkorespondensatu-ke-satu, karena f adalah fungsi satu-ke-satu maupun fungsi pada.

Gambar 3.8 memperlihatkan perbedaan antara fungsi satu-ke-satu tetapi bukan pada, fungsi pada tetapi bukan satu-ke-satu, bukan fungsi satu-ke-satu maupun fungsi pada, dan bukan fungsi.

A B

abcd

123

DEFINISI 3.14. Fungsi f berkoresponden satu-ke-satu atau bijeksi (bijection) jika ia fungsi satu-ke-satu dan juga fungsi pada.

Fungsi satu-ke-satu, Fungsi pada,bukan pada bukan satu-ke-satu

A B A B

Bukan fungsi satu-ke-satu Bukan fungsimaupun pada

A B A B

abc

1234

abcd

123

Gambar 3.8 Perbedaan empat tipe korespondensi

3.13 Fungsi InversiJika f adalah fungsi berkorespondensi satu-ke-satu dari A ke B, maka kita dapat menemukan balikan

atau inverse (invers) dari f. Fungsi inverse dari f dilambangkan dengan f−1. Misalkan a adalah

anggota himpunan A dan b adalah anggota himpunan B, maka f−1(b) = a f(a) = b. Gambar 3.9

memperlihatkan diagram panah yang menggambarkan f−1 sebagai inverse fungsi f.

Gambar 3.9 Fungsi f−1 sebagai fungsi f

Contoh 3.47Relasi f = {(1,u), (2,w), (3,v)} dari A = {1, 2, 3} ke B = {u, v, w} adalah fungsi yang berkoresponden

satu-ke-satu. Inversi fungsi f adalah f−1 = {(u,1), (w,2), (v,3)}. Jadi, f adalah fungsi invertible.

3.14 Komposisi FungsiKarena fungsi merupakan bentuk khusus dari relasi, kita juga dapat melakukan komposisi dari dua buah fungsi. Misalkan g adalah fungsi dari himpunan A ke himpunan B, dan f adalah fungsi dari himpunan B ke himpunan C. Komposisi f dan g, dinotasikan dengan f o g, adalah fungsi dari A ke C yang didefinisikan oleh

(f o g)(a) = f(g(a))

Fungsi satu-ke-satu, Fungsi pada,bukan pada bukan satu-ke-satu

A B A B

Bukan fungsi satu-ke-satu Bukan fungsimaupun pada

A B A B

abcd

1234

abcd

1234

f (a)

f−1(b)

a b

Dengan kata lain, f o g adalah fungsi yang memetakan nilai dari g(a) ke f.Gambar 3.10 mengilustrasikan komposisi dua buah fungsi.

Gambar 3.10 Komposisi dua buah fungsi

Contoh 3.52Diberikan fungsi g = {(1,u), (2,u), (3,v)} yang memetakan A = {1, 2, 3} ke B = {u, v, w}, dan fungsi f = {(u,y), (v,x), (w,z)} yang memetakan B = {u ,v ,w} ke C = {x, y, z}. Fungsi komposisi dari A ke C adalah

f o g = {(1,y), (2,y), (3,x)}

3.15 Beberapa Fungsi KhususBagian ini memberikan beberapa fungsi yang dipakai di dalam ilmu komputer, yaitu fungsi floor, ceiling, modulo, factorial, perpangkatan, dan logaritmik.

1. Fungsi Floor dan CeilingMisalkan x adalah bilangan riil, berarti x berada diantara dua bilangan bulat. Fungsi floor dari x, dilambangkan dengan ⌊ x ⌋ dan fungsi ceiling dari x dilambangkan dengan ⌈ x ⌉ . Definisi kedua fungsi tersebut adalah:

⌊ x ⌋ menyatakan nilai bilangan bulat terbesar yang lebih kecil atau sama dengan x.

⌈ x ⌉ menyatakan bilangan bulat terkecil yang lebih besar atau sama dengan x.

Dengan kata lain, fungsi floor membulatkan x ke bawah, sedangan fungsi ceiling membulatkan x ke atas.

Contoh 3.53Beberapa contoh nilai fungsi floor dan ceiling:

⌊¿ ⌈ ¿⌊¿ ⌈ ¿⌊¿ ⌈ 4.8 ⌉=5⌊¿ ⌈ ¿⌊−3.5 ⌋=−4 ⌈ ¿

2. Fungsi Modulo

(f o g)(a)

A B C g(a) f(g(a))

ag(a) f(g(a))

Misalkan a adalah sembarang bilangan bulat dan m adalah bilangan bulat positif. Fungsi modulo adalah fungsi dengan operator mod, yang dalam hal ini:

a mod m memberikan sisa pembagian bilangan bulat bila a dibagi dengan m

Secara lebih rinci, a mod m = r sedemikian sehingga a = mq + r, dengan 0 ≤ r < m. Lebih jauh mengenai aritmetika modulo dibicarakan di dalam Bab 5.

Contoh 3.55Beberapa contoh fungsi modulo

25 mod 7 = 415 mod 4 = 33612 mod 45 = 120 mod 5 = 0-25 mod 7 = 3 (sebab -25 = 7 . (-4)+3)

3. Fungsi FaktorialUntuk sembarangan bilangan bulat tidak-negatif n, factorial dari n, dilambangkan dengan n!, didefinisikan sebagai

n !={ 1 , n=01 x 2x….x (n−1 ) , n>0

Contoh 3.57Beberapa contoh fungsi factorial

0! = 11! = 14! = 1 . 2 .5! = 1 . 2 . 3 . 4 . 5 = 120

4. Fungsi Eksponensial dan LogaritmikFungsi eksponensial berbentuk

an={ 1, n=0a x ax… x a⏟ , n>0

n

Untuk kasus perpangkatan negatif,

a−n= 1

an

Fungsi logaritmik berbentuk

y ¿a log x↔ x=a y

Contoh 3.58Beberapa contoh fungsi eksponensial dan logaritmik

43=4 .4 .4=64

4−3= 164

4 log64=3karena64=43

⌊¿¿

3.16 Fungsi RekursifTinjau kembali fungsi untuk menghitung factorial dari bilangan bulat tak-negatif n yang didefinisikan sebagai berikut:

n !={ 1 , n=01 x 2x….x (n−1 ) xn ,n>0

Sebagai contoh,0! = 11! = 12! = 1 x 23! = 1 x 2 x 34! = 1 x 2 x 3 x 4

Sekarang coba perhatikan bahwa factorial dari n dapat didefinisikan dalam terminology factorial juga:0! = 11! = 1 x 0!2! = 2 x 1!3! = 3 x 2!4! = 4 x 3!

Nyatakanlah, bahwa untuk n > 0 kita melihat bahwa

n! = 1 x 2 x … x (n −¿ 1) x n = (n −¿ 1)! x n.

Dengan menggunakan notasi matematika, maka n! didefinisikan dalam hubungan rekursif sebagai berikut:

n !={ 1 , n=0nx (n−1 )! , n>0

Jika kita misalkan f(n) = n!, maka fungsi factorial di atas dapat juga ditulis sebagai

f (n)={ 1 , n=0n x f (n−1 ) , n>0

Kita dapat melihat bahwa dalam proses perhitungan factorial bilangan tak-negatif n terdapat definisi factorial itu sendiri. Cara pendefinisian seperti itu, yang mendefinisikan sebuah objek dalam terminology dirinya sendiri dinamakan definisi rekursif.

Nama lain dari fungsi rekursif adalah relasi rekursif (recurrence relation). Ingatlah bahwa fungsi adalah bentuk khusus dari relasi.

Fungsi rekursif disusun oleh dua bagian:

(a) BasisBagian yang berisi nilai awal yang tidak mengacu pada dirinya sendiri. Bagian ini juga sekaligus menghentikan definisi rekursif (dan memberikan sebuah nilai yang terdefinisi pada fungsi rekursif).

(b) RekuensBagian ini mendefinisikan argument fungsi dalam terminology dirinya sendiri. Setiap kali fungsi mengacu pada dirinya sendiri, argument dari fungsi harus lebih dekat ke nilai awal (basis).

Tinjau kembali perhitungan n! secara rekursif. Dengan mengingat kembali definisi rekursif dari factorial:

(a) basis:n! = 1 ,jika n = 0

(b) rekuens:n! = n x (n -1)! ,jika n > 0

maka 5! dihitung dengan langkah berikut:(1) 5! = 5 x 4! (rekuens)(2) 4! = 4 x 3!(3) 3! = 3 x 2!(4) 2! = 2 x 1!(5) 1! = 1 x 0!(6) 0! = 1

Pada baris (6) kita memperoleh nilai yang terdefinisi secara langsung dan bukan factorial dari bilangan lainnya. Dengan melakukan runut-balik (backtrack) dari baris (6) ke baris (1), kita mendapatkan nilai pada setiap baris untuk menghitung hasil pada baris sebelumnya:

DEFINISI 3.15. Fungsi f dikatakan fungsi rekursif jika definisi fungsinya mengacu pada dirinya sendiri.

(6’) 0! = 1(5’) 1! = 1 x 0! = 1 x 1 = 1(4’) 2! = 2 x 1! = 2 x 1 = 2(3’) 3! = 3 x 2! = 3 x 2 = 6(2’) 4! = 4 x 3! = 4 x 6 = 24(1’) 5! = 5 x 4! = 5 x 24 = 120

Jadi, 5! = 120.

Contoh 3.59Di bawah ini adalah contoh-contoh fungsi rekursif lainnya:

1. F ( x )={ 0 ,n=02 F ( x−1 )+x2 , x ≠0

2. Fungsi Chebysev

T (n , x )={ 1 , n=00 ,n=1

2 xT (n−1 , x )−T (n−2 , x ) , n>1

Fungsi Chebysev di atas mempunyai dua buah basis, yaitu jika n = 0 dan n = 1.

3. Fungsi Fibonancci:

f (n)={ 0 , n=01 , n=1

f (n−1 )+f (n−2 ) , n>1