Relasi

RELASI

Hubungan antara anggota-anggota himpunan direpresentasikan dengan menggunakan struktur yang disebut relasi. Untuk mendeskripsikan relasi antara anggota-anggota dua himpunan A dan B, dapat digunakan pasangan terurut dengan anggota pertamanya diambil dari A dan anggota keduanya diambil dari B. Karena ini merupakan relasi antara dua himpunan, maka disebut relasi biner.

Misalkan A dan B himpunan. Suatu relasi biner dari A ke B adalah subhimpunan dari A´B.

n  Untuk relasi biner R berlaku R  AxB.

n  Digunakan notasi aRb untuk menyatakan (a,b)ϵR dan aRb untuk menyatakan (a,b) R.

n  Jika (a, b) merupakan anggota R, a dikatakan berelasi  dengan b oleh R.

Contoh 1 :

Misalkan O himpunan orang, A himpunan angkutan kota, dan N relasi yang mendeskripsikan siapa yang menaiki angkot tertentu.

O = {Budi, Adi, Malik, Wandi},

A = {gejayan-malioboro (GM), tugu-kaliurang (TK), amplas-terminal (AT)}

N = {(budi, GM), (adi, GM), (adi, TK), (malik, AT)}

Artinya budi naik angkot ke gejayan-malioboro, adi naik angkot gejayan-malioboro, adi naik angkot tugu-kaliurang, malik naik angkot amplas-terminal dan wandi tidak menaiki salah satu dari angkot tersebut.

FUNGSI RELASI

Fungsi f dari A ke B memasangkan tepat satu anggota B pada setiap anggota A. Graf dari f adalah himpunan pasangan terurut (a,b) sehingga b = f(a). Karena graf dari f merupakan subhimpunan dari AxB, maka graf merupakan relasi dari A ke B. Untuk setiap aϵA, terdapat tepat satu pasangan terurut di dalam graf dengan a sebagai anggota pertama. Sebaliknya, jika R suatu relasi dari A ke B sehingga setiap anggota A merupakan anggota pertama dari tepat satu pasangan terurut di R, maka dapat didefinisikan suatu fungsi dengan R sebagai grafnya.Ini dilakukan dengan memasangkan pada setiap anggota aϵA tepat satu bϵB sehingga (a,b)ϵR.Relasi adalah perumuman dari fungsi.

RELASI PADA HIMPUNAN

Suatu relasi pada himpunan A adalah relasi dari A ke A. Relasi pada himpunan A adalah subhimpunan dari AxA.

Contoh 2.

Misalkan A = {1, 2, 3, 4}.  Himpunan terurut manakah yang terdapat dalam relasi

R = {(a, b) | a < b}

Solusi. R = {(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)}

                                                            

         

 

R	1	2	3	4
1		x	x	x
2			x	x
3				x
4

Banyaknya subhimpunan yang dapat dibentuk dari suatu himpunan dengan m anggota adalah 2^m.  Jadi, ada 2ⁿ² subhimpunan dapat dibentuk dari AxA. Sehingga, dapat didefinisikan 2n2 relasi berbeda pada A.

SIFAT RELASI

1.    Relasi R pada himpunan A disebut refleksif jika (a,a)ϵR untuk setiap anggota aϵA.

Apakah relasi berikut pada {1, 2, 3, 4} refleksif

R = {(1, 1), (1, 2), (2, 3), (3, 3), (4, 4)}   tidak

R = {(1, 1), (2, 2), (2, 3), (3, 3), (4, 4)}   ya

R = {(1, 1), (2, 2), (3, 3)}                    tidak

Relasi R pada himpunan A disebut simetris jika (b,a)ϵR setiap kali (a,b)ϵR untuk setiap a,bϵA.

Relasi R pada himpunan A disebut antisimetris jika a = b setiap kali (a,b)ϵR dan (b,a)ϵR.

Contoh :

Apakah relasi berikut pada {1, 2, 3, 4} 

simetris atau antisimetris?

R = {(1, 1), (1, 2), (2, 1), (3, 3), (4, 4)}           simetris

R = {(1, 1)}                                                     simetris dan antisimetris

R = {(1, 3), (3, 2), (2, 1)}                                antisimetris

R = {(4, 4), (3, 3), (1, 4)}                                antisimetris

2.    Relasi R pada himpunan A disebut transitif jika setiap kali (a,b)ϵR dan (b,c)ϵR, maka (a,c)ϵR untuk a,b,cϵA.

Apakah relasi berikut pada {1, 2, 3, 4} transitif?

R = {(1, 1), (1, 2), (2, 2), (2, 1), (3, 3)} ya

R = {(1, 3), (3, 2), (2, 1)}                    tidak

R = {(2, 4), (4, 3), (2, 3), (4, 1)}         tidak

MENGHITUNG RELASI

Relasi pada A adalah subhimpunan dari AxA, yang memuat n² anggota. Jadi, relasi yang berbeda pada A dapat dibangun dengan memilih subhimpunan yang berbeda dari n² anggota, sehingga terdapat 2ⁿ² relasi. Namun, suatu relasi refleksif harus memuat n anggota (a,a) untuk setiap aϵA.

Konsekuensinya, kita hanya dapat memilih di antara n² – n = n(n – 1) anggota untuk membangun relasi refleksif, sehingga terdapat 2n(n – 1) relasi.

KOMBINASI RELASI

Relasi adalah himpunan, sehingga operasi himpunan dapat diaplikasikan. Jika ada dua relasi R₁ dan R₂, dan keduanya dari himpunan A ke himpunan B, maka terdapat kombinasi R₁  R₂, R₁  R₂, atau R₁ – R₂  yang  merupakan suatu relasi dari A ke B. Misalkan R relasi dari A ke B dan S relasi dari B ke C. Komposisi dari R dan S adalah relasi yang memuat himpunan terurut (a,c), dengan aϵA, cϵC, di mana terdapat anggota bϵB sehingga (a,b)ϵR dan (b,c)ϵS. Komposisi dari R dan S dinotasikan oleh S°R. Jika relasi R memuat pasangan (a, b) dan relasi S memuat pasangan (b,c), maka S_°R memuat pasangan (a,c).

Contoh 4.

Misalkan D dan S relasi pada A = {1, 2, 3, 4}.

D = {(a, b) | b = 5 - a}             “b sama dengan (5 – a)”

S = {(a, b) | a < b}                   “a lebih kecil dari b”

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

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

S_°D = {(2.4) (3,3) (3,4) (4,2) (4,4) (4,4)}

D memetakan suatu anggota a ke anggota (5 – a), dan setelah itu S memetakan (5 – a) pada semua anggota yang lebih besar dari (5 – a), yang menghasilkan

S°D = {(a,b) | b > 5 – a} atau S°D = {(a,b) | a + b > 5}.

Kuasa dari Relasi

Misalkan R relasi pada himpunan A. Kuasa Rn, n = 1, 2, 3, …, didefinisikan secara induktif

R¹ = R

Rⁿ⁺¹ = Rⁿ_°R

Dengan kata lain:

Rⁿ = R_°R_{° … °}R  (sebanyak n kali)

Relasi R pada A transitif jika dan hanya jika Rⁿ R untuk setiap bilangan bulat positif n.

Representasi Relasi

Beberapa cara untuk merepresentasikan relasi: pasangan terurut.

Dua cara:

matriks nol-satu dan graf beraraf (digraf).

Jika R relasi dari A = {a₁, a₂, …, a_m} ke B =
{b₁, b₂, …, b_n}, maka R dapat direpresentasikan oleh  matriks nol-satu M_R = [m_ij] dengan

            m_ij = 1,  jika (a_i,b_j)ϵR, dan

            m_ij = 0,  jika (a_i,b_j) R.

Contoh.

Bagaimana merepresentasikan relasi
R = {(2, 1), (3, 1), (3, 2)} sebagai matriks nol-satu

Matriks M_R diberikan oleh 

Sifat Matriks Representasi Relasi

Matriks yang merepresentasikan relasi refleksif? Setiap elemen diagonal dari matriks M_ref haruslah 1.

Matriks yang merepresentasikan relasi simetris? Matriksnya juga simetri, yaitu M_R = (M_R)^t.

 matriks simetri, relasi simetris.

                                     

 matriks tak-simetri, relasi tak-simetris

Digraf

Graf berarah (atau digraf) memuat himpunan titik (atau vertex)  V dan himpunan E yang terdiri dari pasangan terurut dari anggota-anggota V yang disebut sisi (atau arc). Vertex a disebut vertex awal dari sisi (a,b), dan vertex b disebut vertex akhir dari sisi ini. Kita dapat menggunakan panah untuk mengilustrasikan digraf.

Representasi Relasi dengan Digraf

Contoh: Ilustrasikan digraph dengan V = {a, b, c, d},
E = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}.

Sisi dalam bentuk (b, b) disebut loop.

Relasi Inversi

Misalkan R adalah relasi dari himpunan A ke himpunan B. Invers dari relasi R, dilambangkan dengan R^–1, adalah relasi dari B ke A yang didefinisikan oleh

                        R^–1 = {(b, a) | (a, b) Î R }

Contoh Misalkan 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 relasi R, yaitu relasi dari Q ke P  dengan

(q, p) Î R^–1  jika q adalah kelipatan dari p

maka kita peroleh

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.

Jika R₁ dan R₂ masing-masing adalah relasi dari himpuna A ke himpunan B, maka R₁ Ç R₂, R₁ È R₂, R₁ – R₂, dan R₁ Å R₂ juga adalah 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)}

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

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)}                         

Komposisi Relasi

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 S o R = {(a, c) ½ a Î A, c Î C, dan untuk beberapa b Î B, (a, b) Î R  dan (b, c) Î S  }Komposisi relasi R dan S lebih jelas jika diperagakan dengan diagram panah:              

Fungsi

Misalkan A dan B himpunan. Relasi biner f dari A ke B merupakan suatu fungsi jika setiap elemen di dalam A dihubungkan 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.

·         A disebut daerah asal (domain) dari f dan B disebut daerah hasil (codomain) dari f.

·         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.

·         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 dari f adalah himpunan bagian (mungkin proper subset) dari B.

MACAM-MACAM FUNGSI

FUNGSI INJEKTIF/INTO/SATU-KE-SATU

Fungsi f dikatakan satu-ke-satu (one-to-one) atau injektif (injective) jika tidak ada dua elemen himpunan A yang memiliki bayangan sama.

Contoh  Relasi

f = {(1, w), (2, u), (3, v)}

dari A = {1, 2, 3} ke B = {u, v, w, x} adalah fungsi satu-ke-satu,

Tetapi relasi

f = {(1, u), (2, u), (3, v)}

dari A = {1, 2, 3} ke B = {u, v, w} bukan fungsi satu-ke-satu, karena f(1) = f(2)  = u.         

FUNGSI SURJEKTIF/ONTO/PADA

·         Fungsi f dikatakan dipetakan 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.

Contoh  Relasi

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

f = {(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  Misalkan f : Z ® Z. Tentukan apakah f(x) = x² + 1 dan f(x) = x – 1 merupakan fungsi pada?

Penyelesaian:

(i) f(x) = x² + 1 bukan fungsi pada, karena tidak semua nilai bilangan bulat merupakan jelajah dari f.

(ii)  f(x) = x – 1 adalah fungsi pada karena untuk setiap bilangan bulat y, selalu ada nilai x yang memenuhi, yaitu y = x – 1 akan dipenuhi untuk x = y + 1.                   

FUNGSI BIJEKTIF/KORESPONDENSI SATU-SATU

Fungsi f dikatakan berkoresponden satu-ke-satu atau bijeksi (bijection) jika ia fungsi satu-ke-satu/injektif/into dan juga fungsi pada/onto/surjektif.

Contoh  Relasi

f = {(1, u), (2, w), (3, v)}

dari A = {1, 2, 3} ke B = {u, v, w} adalah fungsi yang berkoresponden satu-ke-satu, karena f adalah fungsi satu-ke-satu maupun fungsi pada.                                                                                                                              

Contoh  Fungsi f(x) = x – 1 merupakan fungsi yang berkoresponden satu-ke-satu, karena f adalah fungsi satu-ke-satu maupun fungsi pada.                                                                                                   

 Fungsi satu-ke-satu,                                   Fungsi pada,

 bukan pada                                                bukan satu-ke-satu

Buka fungsi satu-ke-satu                                         Bukan fungsi

                               maupun pada

FUNGSI INVERS

Jika f adalah fungsi berkoresponden satu-ke-satu dari A ke B, maka kita dapat menemukan balikan (invers) dari f. Balikan fungsi dilambangkan dengan f ^–1. Misalkan a adalah anggota himpunan A dan b adalah anggota himpunan B, maka f ^-1(b) = a jika f(a) = b.

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))

Contoh Diberikan 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) }                                                                                       

Contoh Diberikan fungsi f(x) = x – 1 dan g(x) = x² + 1. Tentukan f o g  dan g o f .

Penyelesaian:

(i) (f o g)(x) = f(g(x)) = f(x² + 1) = x² + 1 – 1 = x².

(ii) (g o f)(x) = g(f(x)) = g(x – 1) = (x –1)² + 1 = x²  - 2x + 2.