Relasi & Fungsi Kuliah Matematika Diskrit 20 April 2006
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
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 } Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Contoh:
Misalkan : A = {a, b, c}; B = {1, 2, 3} Tentukan : 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)}
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Relasi pada Himpunan
Adalah cara memasangkan anggota suatu himpunan ke anggota himpunan yg lain. Contoh relasi:
A
B
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Relasi Biner
Relasi biner atau hubungan biner (binary relation) dari A ke B ialah suatu himpunan bagian dari A x B. Jika (a, b) A x B, maka a berelasi dengan b, dituliskan a R b. Jika a tidak berelasi dengan b dituliskan a R 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} A x B = {(a,1),(a,2),(a,3),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3), (d,1),(d,2),(d,3)} R = {(a, 1), (b, 3), (c, 1), (c, 3), (d, 2)} A x B, merupakan suatu relasi biner dari A ke B.
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Contoh:
1 A
2
3
√
B C
√
D
√ √
√
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. Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Cara penggambaran yang lain: a 1 b 2 c 3 d
Titik sebelah kiri 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.
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Domain dan Range
Domain dari suatu relasi adalah himpunan yg terdiri dari elemen2 pertama pd pasangan (a, b) R. Range dari suatu relasi adalah himpunan yg terdiri dari elemen2 kedua pd pasangan (a, b) R. Jika R = {(a, b)| a A, b B}, mk domain dari R merupakan himpunan bagian dari A, dan range dari R merupakan himpunan bagian dari B. Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Relasi antara lebih dr 2 himpunan
Relasi terner (ternary relation) menyatakan hubungan antara pasangan tiga himpunan, dan relasi kuarterner (quarternary relation)untuk menyatakan hubungan antara pasanganpasangan empat himpunan, dan seterusnya. Relasi antar 2 himpunan binary Relasi antar 3 himpunan ternary Relasi antar 4 himpunan quarternary Relasi antar n himpunan n-ary Relasi n-ary = subset dari A1 x A2 x … x An A1 x A2 x … x An = {(a1, a2, …, an)| ai Ai}
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Invers Relasi
Jika R = {(a, b)| a A, b B}, maka invers dari relasi R, disimbolkan dengan R-1, adalah {(b, a)| b B, a A}
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Operasi pada Relasi Misalkan R dan S adalah dua buah relasi dari himpunan A ke himpunan B. Terdapat 4 macam operasi yang bisa dikenakan terhadap R dan S:
Irisan Gabungan Selisih Beda simetris Pusat Pengembangan Pendidikan Universitas Gadjah Mada
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)} Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Gabungan
R S = {(a,b)|(a,b)R atau (a,b)S} Contoh : A = {-1, 0, 1} B = {0, 1} Relasi R dan S dari himpunan A ke himpunan B: R = {(-1, 0), (-1, 1), (0, 1)} S = {(0, 0), (1, 1), (-1, 1)} Carilah R S . Penyelesaian: R S = {(-1, 0), (-1, 1), (0, 1), (0, 0), (1, 1)}
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Selisih dan beda simetris
Selisih relasi R dan S: R – S = {(a,b)|(a,b)R & (a,b) ∉ S}
Beda simetris relasi R dan S: R + S = (R S) – (R S)
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Sifat Relasi
Beberapa sifat relasi R :
Refleksif, anti-refleksif relasi pada himpuna yg sama (A ke A) Simetris, anti-simetris Transitif
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Refleksif
Relasi biner pada himpunan A disebut refleksif jika a R a berlaku a A, atau (a, a) R utk setiap a A. Contoh: A = {1, 2, 3} R = {(1, 1), (2, 2), (3, 3)} Maka R memiliki sifat refleksif. Relasi R dikatakan tidak refleksif jika terdapat a A di mana a R a Relasi R dikatakan anti-refleksif jika utk semua a A maka a R a Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Simetris
Relasi biner pada himpunan A disebut refleksif jika berlaku a R b maka b R a, utk setiap a, b A. Dengan cara lain: jika (a, b) R maka (b, a) R utk setiap a, b A. Relasi R dikatakan tidak simetris jika terdapat a, b A yang memiliki sifat a R b tetapi b R a. Relasi R dikatakan anti-simetris jika utk semua a, b A berlaku jika a R b dan b R a maka a = b Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Transitif
Relasi biner pada himpunan A disebut transitif jika berlaku a R b dan b R c maka a R c, utk setiap a, b, c A. Dengan cara lain: jika (a, b) R dan (b, c) R maka (a, c) R utk setiap a, b, c A.
Pusat Pengembangan Pendidikan Universitas Gadjah Mada
Relasi ekuivalensi
Adalah 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 relasi ekuivalensi? Dapat dilihat dari tabel relasi. Pusat Pengembangan Pendidikan Universitas Gadjah Mada
