RELASI
RELASI
A.Definisi
Dalam mengenai himpunan kita sudah mengenal pasangan terurut (ordered pairs).Cara yang paling mudah menyatakan hubungan antara elemen dari dua himpunan adalah dengan himpunan pasangan terurut.Himpunan pasangan terurut diperoleh dari perkalian kartesian (Cartesian product) antara dua himpunan.
Notasi:A x B = {(a,b) | a Î A dan b
|
Relasi antara himpunan A dan B disebut relasi binerdidefenisikan sebagai berikut:
DEFENISI: Relasi biner R antara A dan B adalah himpunan bagian dari A x B
|
Notasi : R Í (A x B)
|
Jika (a,b) Î R, kita gunakan notasi a R b yang artinya a dihubungkan dengan 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.
Relasi yang didefinisikan hanya pada sebuah himpunan adalah relasi yang khusus.Definisi relasi khusus ini dikemukakan dengan defini berikut:
DEFINI|SI : Relasi pada himpunan A adalah relasi dari A x A
B.Representasi Relasi
Selain dinyatakan sebagai himpunan pasangan terurut,ada banyak cara lain untuk merepresentasikan atau menyajikan relasi. Di bawah ini disajikan 3 cara yang lazim dipakai untuk merepresentasikan relasi, yaitu dengan table,matriks,dan graf berarah.
Representasi Relasi dengan Tabel
Relasi biner dapat direpresentasikan sebagi table. Kolom pertama table menyatakan daerah asal,sedangkan kolom kedua menyatakan daerah hasil.
Relasi R pada Contoh dinyatakan dengan Tabel
Tabel
P
|
Q
|
2
2
4
2
4
3
3
|
2
4
4
8
8
9
15
|
Representasi Relasi dengan Matriks
Misalkan R adalah relasi dari A = {a1, a2, …, an} dan B ={b1, b2, …, bn}. Relasi R dapat disajikan dengan matriks M = [mij], dimana :
Dengan kata lain, elemen matriks bernilai 1 jika a¡ dihubungkan dengan bj, dan bernilai 0 jika tidak dihubungkan dengan bj.
Relasi pada contoh 1 dapat dinyatakan dengan matriks berikut :
Dalam hal ini, a1 = Andi, a2 = Beni, a3 = Caca, dan b1 = TI231, b2 = TI321, b3 = TI412, b4 = TI221.
Representasi Relasi dengan Graf Berarah
Relasi pada sebuah himpunan dapat direpresentasikan secara grafis dengan graf berarah
(directed graph atau digraph) (Graf akan dibahas secara khusus di Bab 8). Tiap elemen himpunan dinyatakan dengan sebuah titik (disebut juga simpul atau vertex), dan tiap pasangan terurut dinyatakan dengan busur (arc) yang arah 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 :
a. Representasi graf untuk relasi R = {(a,b), (a,c), (b,a), (b,c), (c,d),(a,d)}
b. Representasi graf untuk relasi R = {(2,2), (2,5), (2,7), (3,8)}
Ditunjukkan pada gambar berikut :
Setiap elemen pada himpunan A maupun himpunan B gambarkan dengan sebuah simpul (titik bulat) dan arah dari suatu elemen ke elemen yang lainnya ditunjukkan dengan sebuah panah. Representasi dengan model ini dapat dikatakan paling mudah untuk dibaca dibanding kedua representasi yang lainnya.
C.Relasi Invers
Jika R adalah relasi pada himpunan orang-orang dimana (a,b) Î jika a adalah ayah dari b,maka noni dapat membuat kebalikan relasinya, yaitu (b,a) yang menyatakan b adalah anak dari a. Relasi baru tersebut dinamakan inverse dari relasi semula. Begitu pula relasi “lebih besar dari” mempunyai inversi “lebih muda dari”.
DEFINISI:Misalkan R adalah relasi dari himpunan A ke himpunan B. Inversi dari relasi R,dilambangkan dengan R-1 adalah relasi dari B ke A uang didefinisikan oleh
R-1 = {(b,a) | (a,b) Î R }
|
Contoh
Misalkan P = {2,3,4} dan Q = {2,4,8,9,15}.Jika kita defenisikan 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 inbers dari relasi 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)}
D.Mengkombinasikan 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 R1 dan R2masing- masing adalah rlasi dari himpunan A ke himpunan B, maka operasi R1ÇR2, R1È R2,R1-R2,dan R1 Å R2 juga adalah relasi dari A ke B.
Contoh 3.14
Misalkan A = {a,b,c} dan B = {a,b,c,d}.Relasi R1 = {(a,a), (b,b), (c,c)} dan relasi R2 = {(a,a), (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), (b,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)}
E.Sifat – Sifat Relasi
1. Refleksif (reflexive)
DEFENISI : Relasi R pada himpunan A disebut refleksifjika (a,a) Î R untuk setiap a Î A
|
Contoh 3.18
Misalkan 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) dan (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 (symmetric) dan Tolak-setangkup (antisymetric)
DEFINISI Relasi R pada himpunan A disebut setangkupjika(a,b) Î R,maka (b,a) ÎR,untuk semua a,b Î A.
|
Dengan kata lain, Definisi menyatakan bahwa relasi R pada himpunan A tidak setangkup jika (a,b) Î R sedemikian sehingga (b,a) Ï R. Sebagai contoh,misalkan A adalah himpunan mahasiswa di sebuah universitas dan R adalah relasi pada A sedemikian sehingga (a,b) Î R jika dan hanya jika a satu fakultas dengan b.Jelas bahwa b juga sefakultas dengan a. Jadi,R setangkup.Contoh lain,misalkan T adalah relasi pada himpunan bilangan bulat positif sedemikiansehingga (a,b) Î T jika dan hanya jika a³ b. Jelas T tidak setangkup,karena,misalnya (6,5) Î T tetapi (5,6) Î T.
DEFINISI :Relasi R pada himpunan A disebut tolak-setangkup jika (a,b) Î R dan (b,a) ÎR maka a = b, untuk semua a,b Î A.
|
Definisi menyatakan bahwa jika (a,b) Î R, maka (b,a) Ï R kecuali a = b.
Definisi juga menyatakan bahwa relasi R pada himpunan A tidak tolak-setangkup jika ada elemen berbeda a dan b sedemikian sehingga (a,b) Î R dan (b,a)Î R.Sebagai ilustrasi,misalkan A adalah himpunan tes yang diadakan untuk masuk sebuah perusahaan (misalnya tes tertulis,tes kesehatan, tes wawancara,dsb).Misalkan R adalah relasi pada A sedemikian sehingga (a,b) Î R jika tes a dilakukan sebelum tes b.Jelas,jika tes a dilakukan sebelum tes b yang berbeda.
Dengan kata lain, (b,a) Ï R kecuali a = b.Jadi,R adalah relasi tolak-setangkup.
Contoh
Misalkan A = {1,2,3,4},dan relasi R dibawah ini didefinisikan 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.Disini (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) Î R dan 2 = 2 dan,Perhatikan bahwa R tidak setangkup.
(e) Relasi R = {(1,1),(2,4),(3,3),(4,2)} tolak-setangkup karena tetapi (2,4) dan (4,2) anggota R.Relasi R pada (a) dan (b) di atas juga
(f) Relasi R = {(1,2),(2,3),(1,3)} tidak setangkup dan tidak tolak setangkup
3. Menghantar (transitive)
DEFENISI :Relasi R pada himpunan A disebut menghantarjika (a,b) Î R dan (b,c) ÎR,maka (a,c) ÎR,untuk semua a,b,c Î A
|
Contoh
Misalkan A = {5,6,7,8}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka
(a). R={(6,5),(6,5),(7,2),(8,5),(8,6),(8,7)}bersifatmenghantar.Periksa dengan membuat table berikut:
Pasangan berbentuk
(a,b)
|
(b,c)
|
(a,c)
|
(5,6)
(8,6)
(8,7)
(8,7)
|
(6,5)
(6,5)
(7,5)
(7,6)
|
(6,5)
(8,5)
(8,5)
(8,6)
|
(b). R= {(5,5),(6,7),(6,8),(8,6)} tidak menghantar karena (6,8) dan (8,6) Î R, tetapi (6,6) Ï R, begitu juga (8,6) dan (6,7) Î R,,terapi (8,7) Ï R.
(c). Relasi R = {(5,5),(6,6),(7,7),(8,8)} jelas menghantar (tunjukkan!).
(d). Relasi R = {(5,6),(7,8)} 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 = {(8,9) selalu menghantar (alasannya sama seperti jawaban (d) di atas)
F.Relasi Kesetaraan
DEFINISI: Relasi R pada himpunan A disebut relasi kesetaraan(equivalence relation) jika ia refleksif,setangkup dan menghantar
|
Secara intuitif,didalam relasi kesetaraan,dua benda berhubungan jika keduanya memiliki beberapa sifat yang sama atau memenuhi beberapa persyaratan yang sama.
Dua elemen yang dihubungkan dengan relasi kesetaraan dinamakan setara(equivalent).Berdasarkan sifat yang dimikinya,kesetaraan tersebut dijelaskan sebagai berikut: Karena relasi bersifat setangkup,maka dua elemen yang dihubungkan relasi adalah setara, Karena relasi bersifat menghantar, maka jika a dan b setara dan b dan c setara, maka a dan c setara.
G.Relasi Pengurutan Parsial
DEFENISI : Relasi R pada himpunan S dikatakan relasi pengurutan persial (partial ordering relation) jika ia refleksif, tolak-setangkup dan menghantar. Himpunan S bersama-sama dengan relasi R disebut himpunan turut secara persial (partially ordered set atau poset), dan dilambangkan dengan (S, R).
Relasi ≥ pada himpunan bilangan bulat adalah relasi pengurutan persial. Hal ini dijelaskan sebagai berikut: Karena a ≥ a untuk setiap bilangan bulat a, relasi ≥ refleksif. Relasi ≥ tilak-setangkup, karena jika a ≥ b dan b ≥ a, maka a = b. Relasi ≥ menghantar, karena jika a ≥ b dan b ≥ c maka a ≥ c.
Relasi “habis membagi” pada himpunan bilangan bulat juga adalah relasi pengurutan persial. Hal ini dijelaskan sebagai berikut: karena setiap bilangan bulat habis membagi dirinya sendiri, relasi “habis membagi” bersifat refleksif. Relasi “habis membagi” bersifat tolak-setangkup, karena a habis membagi b berarti b tidak habis membagi a, kecuali jika a = b. Terakhir, relasi menghantar karena jika a habis membagi b, dan b habis membagi c, maka a habis membagi c.
Sumber:
- http://www.catatanrobert.com/relasi-dan-representasinya-dengan-tabel-matriks-dan-graf-berarah/
- Buku Matematika Diskrit Revisi Kelima Renaldi Munir,Penerbit INFORMATIKA
Komentar
Posting Komentar