FUNGSI & RELASI

A.  FUNGSI

Fungsi merupakan relasi yang  mempunyai syarat  setiap anggota dari   daerah  definisi (domain)  mempunyai pasangan tepat satu  anggota dari daerah Hasil (codomain). Diberikan  dua himpunan  A dan B,  relasi biner  f  dari  himpunan A  ke B merupakan suatu   fungsi   jika   setiap   elemen   di dalam   himpunan   A   mempunyai pasangan  tepat satu  elemen  himpunan  B. Apabila  f  adalah  fungsi dari  himpunan A  ke  B  maka  notasi  fungsinya:

f :  A → B

Himpunan A  disebut  daerah  definisi(domain)  dan  himpunan  B  disebut  daerah hasil (codomain).  Untuk x ∈ A  dan  y ∈B  maka  rumus  fungsí  1)  dapat dinyatakan sbb:

x → y = f(x)

Terapan  Fungsi

ü  Formula pengisian nilai dalam bahasa pemrograman  dinyatakan dengan assignment Contoh  diberikan rumusan fungsi  f(x)  =  x2 +1 , f(x) = x +1 , apabila tidak didefinisikan secara   khusus tentang daerah definisi   maka   daerah definisi dan   daerah hasil adalah himpunan Himpunan bilangan riil misal R. Dalam himpunan pasangan terurut fungsi  didefinisikan  sbb:

f  = { (x1, x2}/ x ∈ R }

ü  Kode  program ( source  code). Fungsi yang dispesifikasikan  dalam bahasa Pascal:

Function      abs(x: integer): integer; Begin

If x < 0 then

abs := -x

else

abs := x;

end;

Contoh:

Relasi f = {(1,a),(2,b),(3,c) }dari himpunan A ke B, {1,2,3} ∈ A dan {a,b,c}∈ B merupa- kan fungsi karena Relasi f memasangkan tepat satu anggota himpunan A dengan anggota himpunan B.

Keterangan :

f(1) = a, f (2) = b dan f (3) = c

dari contoh tersebut himpunan A disebut daerah definisi dan himpunan B seba-gai daerah hasil.

Jenis Fungsi

Ditinjau pada daerah hasil atau bayangan fungsi dibedakan atas fungsi injektif (injective), surjektif (surjective) dan bijeksi (bijection).

·         Fungsi injektif (injective)

Fungsi f dikatakan one-to-one atau injektif (injective) apabila a dan b anggota himpunan A maka f(a) ≠ f(b) bilamana a ≠ b untuk f(a) dan f(b) anggota himpunan B.

·         Fungsi surjektif (surjective)

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

·         Fungsi bijeksi (bijection)

Fungsi f dikatakan berkorespodensi satu-satu atau bijeksi(bijection) apabila ia fungsi one-to-one dan surjective.

Fungsi Invers

Apabila f merupakan fungsi berkorespondensi satu-satu dari himpunan A ke himpunan B maka fungsi tersebut mempunyai invers yaitu f -1(y) = x , untuk x ∈ A dan y ∈ B, f -1 merupakan invers dari fungsi f.

Komposisi fungsi

Komposisi dari dua fungsi f dan g dinyatakan f_°g, f merupakan fungsi yang memetakan anggota himpunan A ke himpunan B dan fungsi g memetakan anggota himpunan B ke himpunan C. Fungsi dari himpunan A ke himpunan C didefinisikan f_° g(x) = f( g(x)), x ∈ A

Beberapa Fungsi Khusus

Beberapa fungsi khusus yang sering digunakan dalam bahasa pemrograman seperti fungsi floor, ceiling, modulo, faktorial, perpangkatan dan logaritmik.

1.      Fungsi floor dan ceiling

Fungsi ini diperlukan untuk membulatkan ke bawah dan keatas. Fungsi floor diperlukan untuk membulatkan nilai pecahan kebawah, misalkan x bilangan riil maka bilangan floor dilambangkan ⎣x⎦. Fungsi ceiling diperlukan untuk membulatkan nilai pecahan keatas dan dilambangkan ⎡x⎤.

Contoh:

Nilai fungsi floor seperti :

⎣4.6⎦. = 4 ; ⎣12.7⎦. = 12; ⎣-0.25⎦. = -1

Nilai fungsi ceiling seperti :

⎡4.6⎤.= 5 ; ⎡12.7⎤.=13 ; ⎡-0.25⎤. = 0

2.      Fungsi Modulo

Fungsi modulo adalah fungsi dengan operator mod, misalkan b sembarang bilangan bulat dan m bilangan bulat positip maka b mod m emberikan sisa pembagian bilangan bulat apabila b dibagi dengan m .

Contoh 1:

15 mod 4 = 3 ( 3 menyatakan sisa pembagian 15 dibagi 4 )

8 mod 2 = 0 ( 0 menyatakan bahwa 8 habis dibagi 2, tidak ada sisa)

Contoh 2:

Misal f adalah fungsi dari X untuk X ={1, 2, 3 } ke X, yang didefinisikan oleh f(x) = 4x mod 5 tuliskan himpunan pasangan terurut yang terjadi.

x = 1,    f(1) = 4 .1 mod 5 = 4

x = 2,    f(2) = 4 .2 mod 5 = 3

x = 3,    f(3) = 4 .3 mod 5 = 2

3.      Fungsi hash

Misalkan dipunyai sel-sel pada memori komputer yang diberi indek dari 0 sampai dengan 10. Akan disimpan dan menyelamatkan bilangan bulat non negatif dalam sel tersebut. Salah satu pendekatan adalah menggunakan fungsi hash ( hash function). Fungsi ini akan mengambil butir data untuk disimpan atau diselamatkan serta mengurutkan untuk diletakkan pada lokasi yang ditentukan. Untuk menyimpan atau mengambil bilangan n pilihan pertama untuk lokasi n mod 11 dengan fungsi hash sebagai berikut: h(n) = n mod 11

4.      Fungsi faktorial

Untuk sembarang bilangan bulat non negatif n, faktorial dari n dilambangkan dengan n.

Contoh:

1! = 1

2! = 2.(2-1) = 2

3! = 3. (3-1) (3-2) = 6

dst

n! = n. (n-1) !

Fungsi dan algoritma Rekursif

Prosedur berulang (recursive prosedure) adalah prosedur yang berjalan sendiri sedangkan algoritma rekursif merupakan algoritma yang mengandung presedur rekursif. dibawah ini di berikan ilustrasi bagamana menghitung n! dengan algoritma rekursif lihat contoh berikut:

Input : n, sebuah bilangan bulat lebih besar dari 0

output: n!

prosedure faktorial(n)

if n = 0 then

return(1)

return(n*faktorial(n-1))

end factorial

Maksud algoritma tersebut akan dihitung n! untuk beberapa nilai n yang di inputkan

Apabila n = 0, maka statemen baris 3 menyakan nilai 1,

Apabila n = 1, maka perhitungan berlanjut ke statemen baris 4 (karena n≠0) disini akan dilakukan proses penghitungan (n-1)!.n = 0!.1= 1.1 =1

Apabila n = 1, maka perhitungan berlanjut ke statemen baris 4 (karena n≠0) disini akan dilakukan proses penghitungan nilai 1 ! yaitu (n-1)!.n = 0!.1= 1.1 =1

Apabila n = 2, maka proses perhitungan ke statemen baris 4 (karena n≠0) disini akan dilakukan proses penghitungan 2! yaitu (n-1)!.n = 1!.2 = 1.2 = 2 dst.Proses akan berhenti apabila data yang diinputkan sudah terealisasi,

B.  RELASI

Relasi antara himpunan A dan himpunan B didefinisikan sebagai cara pengawanan anggota himpunan A dengan anggota himpunan B ilustrasi grafis dapat dilihat sbb:

Relasi biner

Relasi biner adalah himpunan yang anggotanya berupa pasangan terurut dengan elemen pertama merupakan elemen dari suatu himpunan daerah domain dan elemen ke dua merupakan elemen dari suatu himpunan daerah hasil. Himpunan pasangan terurut diperoleh dari perkalian kartesian (cartesian product) antara dua himpunan. Perkalian kartesian antara himpunan A dan B adalah himpunan yang elemennya semua pasangan terurut (ordered pairs) yang mungkin terbentuk dengan komponen pertama elemen himpunan A dan komponen kedua elemen himpunan B. Secara matematis dinotasikan sbb:

A x B = { (a,b) /a ∈ A dan b ∈ B }

Relasi biner R antara himpunan A dan B adalah himpunan bagian dari A x B, dinyatakan R ⊂ (A x B ). Pasangan elemen dua himpunan A dan B menjadi anggota R yaitu (a,b)∈ R, atau digunakan notasi a R b yang artinya ‘a dihubungkan dengan b oleh R’ atau dibaca ‘elemen a ∈ A berelasi dengan b∈ B’, dan jika (a,b) ∉ R digunakan notasi bRa yang artinya ‘a tidak dihubungkan dengan b oleh relasi R’ atau ‘a tidak berelasi dengan b’. Himpunan A disebut daerah asal (dominan) dari R, dan himpunan B disebut daerah hasil (range) dari R.

Contoh 1:

Misalkan P = {Jojon, Timbul, Basuki} adalah himpunan nama mahasiswa, dan Q = {SB221, SB251, SB342} adalah himpunan kode matakuliah di Jurusan sosial budaya. Urutan terakhir pada kode matakuliah bernomer ganjil menyatakan semester ganjil dan kode matakuliah urutan terakhir nomer genap menyatakan semester genap.

Maka perkalian kartesian antara himpunan P dan Q menghasilkan himpunan pasangan terurut yang jumlah anggotanya adalah |P|.|Q| = 3 . 3 = 9 buah. Perkalian tersebut adalah sebagai berikut :

P x Q = {(Jojon, SB221), (Jojon, SB 251), (Jojon, SB342), (Timbul, SB221), (Timbul, SB251), (Timbul, SB342), (Basuki,SB221), (Basuki,SB 251), (Basuki , SB342)}.

Contoh 2:

Jika R adalah relasi yang menyatakan mata kuliah yang diambil oleh maha- siswa pada Semester Ganjil , yaitu :

R = {(Jojon , SB221), ( Jojon,SB251) , (Timbul, SB221), (Timbul, SB251) }

maka

R ∈ (P x Q ), P adalah daerah asal R dan Q adalah daerah hasil R.

Karena (Jojon , SB221) ∈ R maka dapat ditulis Jojon R SB221 artinya nama mahasiswa bernama Jojon mengambil matakuliah dengan kode matakuliah SB221 dan  Jojon , SB342 ) ∉ R maka Jojon R SB252, artinya Jojon tidak mengambil matakuliah dengan kode matakuliah SB342.

Representasi relasi

Terdapat beberapa cara untuk menyajikan relasi. Diantaranya disajikan 3 cara yang lazim, yaitu tabel, matriks, graf berarah.

v  Representasi Relasi dengan Tabel

Jika relasi direpresentasikan dengan tabel, maka kolom pertama tabel menyatakan daerah asal, sedangkan kolom kedua menyatakan daerah hasil.

Relasi R pada P x Q untuk P = { Jojon, Timbul , Basuki} adalah himpunan nama mahasis wa, dan Q = {SB221, SB251, SB342} himpunan kode matakuliah dapat dinyatakan dengan Tabel berikut:

P	Q
Jojon	SB251
Jojon	SB221
Timbul	SB221
Timbul	SB251

v  Representasi Relasi dengan Matriks

Misalkan R adalah relasi dari himpunan A ={ a₁, a₂, … , a_m} dan B ={ b₁, b₂, … , b_n}, Relasi R dapat disajikan dengan matriks M = [m_ij],

Dimana elemen matriks yang terletak pada baris ke i dan kolom ke j bernilai 1 apabila a_i berelasi dengan b_j, dan bernilai 0 apabila a_i tidak berelasi dengan b_j.

v  Representasi Relasi dengan Graf Berarah

Representasi dengan graf berarah (directed graph atau digraph) merupakan representasi relasi secara grafis. Setiap elemen himpunan dinyatakan dengan sebuah titik (simpul atau vertex), dan tiap pasangan terurut dinyatakan dengan garis atau busur (arc) yang arahnya 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).

Contoh:

Diketahui R = {(a, a), (a, b), (b, a), (b, c), (b, d), (d , b),( c, a), (c, d)} merupakan relasi dari himpunan A = { a, b, c, d }. R direpresentasikan dengan:

R = {(a, a), (a, b), (b, a), (b, c), (b, d), (c, a), (c, d), (d, b) }

Pasangan terurut (a,a) dinyatakan dengan busur dari simpul a ke a sendiri. Busur semacam itu disebut gelang atau kalang (loop).

Sifat-Sifat Relasi Biner

a.       Refleksif (reflexive)

Relasi R pada himpunan A disebut refleksif jika (a, a) ∈ R untuk setiap a ∈ A

Contoh:

Misalkan A = {1, 2, 3, 4 }, dan relasi R dibawah ini didefinisikan pada himpunan A, maka :

(a) 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) R = { (1, 1) , (2, 2) , (4, 2) , (4, 3) , (4, 4) } tidak bersifat refleksif karena (3,3) ∈R tetapi (3,3) tidak termuat dalam R.

b.      Setangkup (Symmetric)

Relasi R pada himpunan A disebut setangkup jika untuk semua a, b ∈ A, (a, b) ∈R , maka (b, a) ∈ R. Sebaliknya, R disebut tak setangkup (anti sysmmetric) untuk a,b ∈A, jika (a, b) ∈ R dan a ≠ b, maka (b,a) ∉ R

Contoh:

Misalkan A{1, 2, 3, 4} dan relasi R dibawah ini didefinisikan pada himpunan A, maka,

(a) R = { (1, 1), (1, 2), (2, 1), (2, 2), (2, 4), (4, 2), (4, 4) } bersifat setangkup karena setiap (a, b) ∈R maka (b, a)∈ R.pada kejadian tersebut (1,2) dan (2, 1) ∈ R; (2, 4) dan (4, 2) ∈ R begitu juga (1,1),(2, 2) dan (4, 4) ∈ R .

(b) R = { (1, 1) , (2, 3) , (2, 4) , (4, 2) }tidak bersifat setangkup karena (3,2) ∉ R

c.       Menghantar (transitive)

Relasi R disebut menghantar bilamana (a, b) ∈R dan (b, c) ∈ R , maka (a, c) ∈R, untuk a, b, c ∈A.

Contoh:

Misalkan 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. Lihat tabel berikut :

Pasangan terbentuk
(a, b)	(b, c)	(a, c)
(3, 2)	(2, 1)	(3, 1)
(4, 2)	(2, 1)	(4, 1)
(4, 3)	(3, 1)	(4, 1)
(4, 3)	(3, 2)	(4, 2)

b.      R = {(1, 1), (2, 3), (2, 4), (4, 2)}tidak bersifat 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 = { (4, 3) } bersifat menghantar.

Kombinasi Relasi

Karena 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 R₁ dan R₂ masing-masing adalah relasi dari himpunan A ke himpunan B, maka R₁ ∩ R₂ , R₁∪R₂ , R₁ - R₂ dan R₁ ⊕ R₂ juga relasi dari A ke B.

Contoh:

Misalkan A = { a, b, c } dan B = { a, b, c, d} . Relasi R₁ = { (a, a), (b, b), (c, c)}dan relasi R₂ = { (a, a) , (a, b) , (a, c) , (a, d) }adalah relasi dari A ke B . Kita dapat mengkombinasikan kedua buah relasi tersebut untuk memperoleh R₁ ∩ R₂ = {(a,a)}

R₁ ∪ R₂ = {(a,a), (b,b), (c,c), (a,b), (a,c), (a,d)}

R₁ - R₂ = {(b,b), (c,c)}

R₂ - R₁ = {(a,b), (a,c), (a,d)}

R₁ ⊕ R₂ = {(b,b), (c,c), (a,b), (a,c), (a,d)}

Jika relasi R₁ dan R₂ masing-masing dinyatakan dengan matriks M_R1 dan M_R2 , maka matriks yang menyatakan gabungan dan irisan dari kedua relasi tersebut adalah

M_R1∪ R2 = M_R1 ∨ M_R2 dan M_R1∩R2 = M_R1 ∧ M_R2

dalam hal ini , operator " ∨ " berarti " atau" , " ∧ " berarti "dan".

Komposisi Relasi

Cara lain mengkombinasikan relasi adalah mengkomposisikan dua buah relasi atau lebih,. komposisi relasi analog dengan komposisi fungsi.

Misalkan R adalah relasi dari himpunan A ke himpunan B, dan S adalah relasi dari himpunan B ke C. Komposisi R dan S, dinotasikan dengan R o S, adalah relasi dari A ke C yang didefinisikan sebagai berikut :

R o S = {(a,c) | a ∈ A , c ∈ C,dan untuk beberapa b ∈B, (a, b) ∈R dan (b, c) ∈ S }

Contoh:

Diberikan 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

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

Jika relasi R₁ dan R₂ masing-masing dinyatakan dengan matriks M_R1 dan M_R2 , maka matriks yang menyatakan komposisi dari kedua relasi tersebut adalah

M_{R1o R2} = M_R21 . M_R2

Dalam hal ini operator " . " prosesnya sama seperti pada perkalian matriks biasa, tetapi tanda " . " diganti dengan tanda "∨ " dan tanda tambah " + " diganti dengan "∧".

Aplikasi Relasi

Ø  Relasi n-ary dan aplikasinya

Relasi biner hanya menghubungkan antara dua buah himpunan. Relasi yang lebih umum menghubungkan lebih dari dua buah himpunan, relasi tersebut dinamakan relasi n-ary (baca : ener). Jika n = 2, maka relasinya dinamakan relasi biner (bi = 2). Relasi n-ary mempunyai terapan penting di dalam basis data.

Misalkan A₁, A₂, …. A_n adalah himpunan. Relasi n-ary R pada himpunan-himpunan tersebut adalah himpunan bagian dari A₁ x A₂ x …. x A_n , atau dengan notasi R ⊆ A₁ x A₂ x …. x A_n .Himpunan A₁, A₂, …. A_n disebut daerah asal relasi dan n disebut derajat.

Ø  Seleksi

Operasi seleksi memilih baris tertentu dari suatu tabel yang memenuhi persyaratan tertentu yang diberi notasi σ atau Operator : σ

Contoh:

Misalkan untuk relasi MHS kita ingin menampilkan daftar mahasiswa yang mengambil mata kuliah Matematika Diskrit. Operasi Seleksinya adalah

σ _{MTK = "Matematika Diskrit"} (MhS) yang menghasilkan tupel (13598211, Bela, matematika Diskrit, A ),( 13598425, Safira, Matematika Diskrit, B ).

Ø  Proyeksi

Operasi proyeksi memilih kolom tertentu dari suatu tabel. Jika ada beberapa baris yang sama nilainya, maka hanya diambil satu kali. yang diberi notasi π atau Operator : π

Contoh 1: Operasi Proyeksi π _{Nama, MTk, Nilai} (MHS)

Contoh 2: Misalkan A = { a, b, c } dan B = { a, b, c, d}.

Relasi = { (a, a), (b, b), (c, c)}