Definisi 1. Relasi biner R antara A dan B adalah himpunan bagian dari A x B. A x B = {(a, b) a A dan b B}

RELASI

A. Pendahuluan

Definisi 1. Relasi biner R antara A dan B adalah himpunan bagian dari A x B. A x B = {(a, b)|a ∈ A dan b ∈ B}. ■ Apabila (a, b) ∈ R, maka a dihubungkan dengan b oleh relasi R, ditulis a R

 b. b. Jika tidak, dalam hal ini (a, b) ∉ R, maka ditulis a R Contoh 1. Misalkan A = {1, 2, 3} dan B = {a, b, c}. Maka A x B = {(1, a), (1, b), (1, c), ..., (3, c)} Misalkan di definisikan R = {(1, a), (2, a), (3, c)}, maka (1, a) ∈ R, ditulis 1

 c. ■ R a. Sementara (1, c) ∉ R, ditulis 1 R Contoh 2. Misalkan K = {2, 3, 4} dan L = {2, 4, 6, 8, 9, 16}. Misalkan pula relasi R dari K ke L didefinisikan sebagai berikut: “ (k, l) ∈ R jika k habis membagi l. Tentukan anggota R. Penyelesaian: R = {(2, 2), (2, 4), (2, 6), (2, 8), (2, 16), (3, 6), (3, 9), (4, 4), (4, 8), (4, 16)} Jelas bahwa R ⊆ (K x L)

Definisi 2. Relasi pada himpunan A adalah relasi dari A ke A itu sendiri dalam hal ini AxA.■

1 | Matematika Diskrit Email: [email protected] Web: aswhat.wodpress.com

B. Representasi Relasi

Ada beberapa macam representasi suatu relasi. Beberapa diantaranya adalah direpresentasikan ke dalam bentuk tabel, matriks, diagram panah, dan graph berarah. Pada kesempatan kali ini, hanya akan dibahas representasi graph ke dalam bentuk matriks dan graph berarah.

1. Representasi relasi dalam bentuk matriks Aturan: Misalkan R adalah suatu relasi dari A = {a1, a2, ..., am} ke B = {b1, b2, ..., bn}. Matriks relasi dari A ke B, ditulis M(R) = [aij].

b1

b2 ... an

a1  m11 m12 M(R )  a2  m21 m22  ...  ... ...  am mm1 mm 2

... m1 n   1, jika (ai , a j )  R  ... m2n  dengan mij    0, jika (ai , a j )  R ... ...   ... mmn 

Contoh 3. Perhatikan kembali Contoh 1. Representasi matriks dari relasi R tersebut adalah sebagai berikut:

 (1, a) (1, b) (1, c )   1 0 0 M (R )  (2, a) (2, b) (2, c )   1 0 0  ∎     (3, a) (3, b) (3, c ) 0 0 1

2. Representasi relasi dalam bentuk graph berarah Aturan: Misalkan diketahui himpunan A dan B dengan relasi R dari A ke B. Tiap elemen yang berbeda dari himpunan A dan B dituliskan dalam bentuk titik/noktah/vertex sementara relasi dari A ke B dinyatakan oleh garis berarah / edge.

2 | Matematika Diskrit Email: [email protected] Web: aswhat.wodpress.com

Contoh 4. Perhatikan kembali Contoh 1. Representasi graph berarah dari relasi R tersebut adalah sebagai berikut:

Gambar 1.

Meskipun tidak ada ketentuan umum, namun pada dasarnya bentuk relasi yang direpresentasikan ke dalam bentuk graph berarah adalah relasi yang terjadi pada himpunan A itu sendiri (A x A).

C. Relasi Invers dan Komposisi Relasi

Definisi 3. Misalkan R adalah relasi dari A ke B. Invers dari relasi R, ditulis R-1, adalah relasi dari B ke A yang didefinisikan sebagai R -1 = {(b, a)|dengan (a, b) ∈ R}.∎

Contoh 5. Perhatikan kembali Contoh 1. Invsers dari relasi R adalah: R-1 = {(a, 1), (a, 2), (c, 3)}. ∎

Definisi 4. Misalkan R adalah relasi dari A ke B, dan S adalah relasi dari B ke C. Komposisi R dan S, ditulis S o R, adalah relasi dari A ke C yang didefinisikan sebagai S o R = {(a, c) | a ∈ A, c ∈ C; untuk beberapa b ∈ B; (a, b) ∈ R; dan (b, c) ∈ S}. ∎

Contoh 6. Diketahui A = {1, 2, 3}, B = {2, 4, 6, 8}, dan C = {s, t, u}. 3 | Matematika Diskrit Email: [email protected] Web: aswhat.wodpress.com

Diberikan R suatu relasi dari A ke B, dengan R = {(1, 2), (1, 6), (2, 4), (3, 4), (3, 6), (3, 8)}. Sedangkan S adalah suatu relasi dari B ke C, dengan S = {(2, u), (4, s), (4, t), (6, t), (8, u)}. a. Tentukan invers dari R dan S b. Tentukan S o R dan R o S Penyelesaian: a. R-1 = {(2, 1), (6, 1), (4, 2), (4, 3), (6, 3), (8, 3)} S-1 = {(u, 2), (s, 4), (t, 4), (t, 6), (u, 8)} b. S o R = {(1, u), (1, t), (2, s), (2, t), (3, s), (3, t), (3, u)} RoS=∅∎

Apabila relasi R dan S dinyatakan dalam bentuk matriks MR dan MS, maka matriks yang menyatakan komposisi dari kedua relasi tersebut adalah hasil perkalian matriks antara MR dengan MS, ditulis MSoR = MR . MS. Contoh 7. Misalkan diketahui relasi R dan S dinyatakan dalam bentuk matriks berikut:

0 1 0   1 0 1   R  1 1 0 dan S  0 0 1      1 0 1 0 0 0 Maktriks yang menyatakan S o R adalah sebagai berikut:

 1 0 1 0 1 0  1 1 1 S o R   1 1 0 x 0 0 1  0 1 1       0 0 0  1 0 1 0 0 0

D. Sifat-Sifat Relasi

Ada 3 sifat relasi yang penting untuk diketahui yaitu refleksif, simetri dan antisimetri, serta transitif.

4 | Matematika Diskrit Email: [email protected] Web: aswhat.wodpress.com

Definisi 5. Relasi R pada himpunan A disebut refleksif apabila (a, a) ∈ R ∀ a ∈ A. ∎

Contoh 8. Misalkan A = {1, 2, 3, 4}. Misalkan didefinisikan suatu relasi R dan S pada himpunan A, dengan R = {(1, 1), (1, 3), (2, 1), (2, 2), (3, 3), (4, 2), (4, 3), (4, 4)} dan S = {(1, 1), (2, 2), (2, 3), (4, 2), (4, 3), (4, 4)}. Perhatikan bahwa relasi R bersifat refleksif karena (1, 1), (2, 2), (3, 3) dan (4, 4) berada di R. Sementara S tidak bersifat transitif karena terdapat (3, 3) yang tidak beradadi S. ∎

Definisi 6. Relasi R pada himpunan A disebut symetri apabila (a, b) ∈ R maka (b, a) ∈ R untuk semua a dan b ∈ R. Sedangkan R disebut antisymetri apabila (a, b) ∈ R dan (b, a) ∈ R berakibat a = b untuk semua a dan b ∈ R. ∎

Contoh 9. Misalkan A = {1, 2, 3, 4}. a. Relasi R1 = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 4), (3, 1), (4, 2)} adalah symetri. b. Relasi R2 = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (4, 2)} adalah tidak symetri karena (1, 3) ∈ R2 tetapi (3, 1) ∉ R2. c. Relasi R3 = {(1, 1), (2, 2), (3, 3)} adalah antisymetri. Perhatikan pula bahwa R3 juga symetri. ∎ Suatu matriks yang merupakan representasi dari suatu relasi yang bersifat symetri maka elemen matriks yang berada di bawah diagonal utama merupakan pencerminan dari elemen-elemen yang ada di atas diagonal utama. Sedangkan representasi graph berarah dari relasi yang bersifat symetri ditandai dengan adanya garis berarah dari a ke b dan juga dari b ke a.

5 | Matematika Diskrit Email: [email protected] Web: aswhat.wodpress.com

Definisi 7. Relasi R pada himpunan A disebut transitif apabila (a, b) ∈ R dan (b, c) ∈ R maka (a, c) ∈ R untuk semua a, b, c, ∈ A. ∎

Contoh 10. Misalkan A = {1, 2, 3, 4} a. R1 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} bersifat transitif b. R2 = {(1, 1), (2, 3), (2, 4), (4, 2)} tidak transitif karena (2, 4) dan (4, 2) berada di R2 tetapi (2, 2) bukan elemen di R2. ∎ Dari ketiga sifat tersebut, dapat dikatakan bahwa suatu relasi bisa saja memiliki ketiga sifat sekaligus atau sama sekali tidak memiliki salah satu dari ketiga sifat tersebut.

Definisi 8. Relasi R pada himpunan A disebut relasi ekivalen apabila relasi tersebut bersifat refleksif, simetri, dan transitif. Sementara relasi R dikatakan kompatibel apabila relasi tersebut memenuhi refleksif dan simetri tetapi tidak harus transitif. ∎

6 | Matematika Diskrit Email: [email protected] Web: aswhat.wodpress.com