Relasi dan Fungsi

Matematika Diskrit

Relasi Relasi antara Ayah dan anak, Ibu dengan

anak, dll Dalam aritmatika: Relasi “Lebih besar” atau

“Lebih kecil” digunakan untuk membandingkan dua buah bilangan yang berbeda

Binary Relation/Relation = relasi antara 2 objek

Relasi dalam himpuanan Relasi dari himpunan A ke himpunan B, artinya Memetakan setiap anggota pada himpunan A (x

∈ A) dengan anggota pada himpunan B (y ∈ B) Relasi antara himpunan A dan himpunan B juga

merupakan himpunan, yaitu himpunan yang berisi pasangan berurutan yang mengikuti aturan tertentu, contoh (x,y) ∈ R

Relasi biner R antara himpunan A dan B merupakan himpunan bagian dari cartesian product A × B atau R ⊆ (A × B)

Notasi Relasi antara dua buah objek dinyatakan

dengan himpunan pasangan berurutan(x,y) ∈ R

contoh: relasi F adalah relasi ayah dengan anaknya, maka:F = {(x,y)|x adalah ayah dari y}

xRy dapat dibaca: x memiliki hubungan R dengan y

Contoh Humpunan A : himpunan nama orang A={Via, Andre, Ita}

Himpunan B : himpunan nama makanan B={es krim, coklat, permen}

Relasi makanan kesukaan (R) dari himpunan A dan B adalah:

Contoh

via

Andre

Ita

permen

coklat

es krim

A BR

R : Relasi dengan nama “ Makanan Kesukaan “Relasi R dalam A artinya domain dan kodomainnya adalah A

Cara menyatakan relasi Diagaram panah Himpunan pasangan berurutan Diagram Cartesius Tabel Matriks Graph Berarah

Cara menyatakan relasi

via

Andre

Ita

permen

coklat

es krim

permencoklatEs krim

• R={(x,y)|x menyukai y; x ∈ A dan y ∈ B}

A BR• Diagram Panah

Cara menyatakan relasi Himpunan pasangan berurutan

R={(Via,permen) , (Via,coklat) , (Andre,coklat) , (Andre,es krim) , (Ita,es krim)}

Diagram Kartesius

via andre ita

permen

coklat

es krim

Cara menyatakan relasi Tabel

Nama MakananVia PermenVia CoklatAndre CoklatAndre Es KrimIta Es Krim

Cara menyatakan relasi Matriks

Baris = domain Kolom = kodomain

100110011

ItaAndreVia

Perm

en C

okla

tEs

krim

permen

coklat Es krim

Via 1 1 0

Andre 0 1 1

Ita 0 0 1

Cara menyatakan relasi Graph berarah

hanya untuk merepresentasikan relasi pada satu himpunan (bukan antara dua himpuanan).

Tiap unsur himpunan dinyatakan dengan sebuah titik (disebut juga simpul atau vertex)

Tiap pasangan terurut dinyatakan dengan busur (arc). Jika (a, b) ∈ R, maka sebuah busur dibuat dari simpul a

ke simpul b. Simpul a disebut simpul asal (initial vertex) simpul b disebut simpul tujuan (terminal vertex) Pasangan terurut (a, a) dinyatakan dengan busur dari

simpul a ke simpul a sendiri. Busur semacam itu disebut loop

Cara menyatakan relasi Contoh graph berarah

Misalkan R = {(a, b), (b, c), (b, d), (c, c) (c, a), (c, d), (d, b)} adalah relasi pada himpunan {a, b, c, d}.

Latihan 1 Z = {1,2,3,4}; R = {(x,y)|x > y ; x ∈ Z dan y ∈ Z} Nyatakan relasi tersbut dalam bentuk

Himpunan pasangan berurutan Matrix Graf

Sifat- sifat relasiREFLEKSIF (REFLEXIVE)TRANSITIF (TRANSITIVE) SIMETRIK (SYMMETRIC)ASIMETRIK (ASYMMETRIC)EQUVALENTPOSET

Refleksif Sebuah relasi dikatakan refleksif jika

sedikitnya: x ∈ A, xRx

Minimal

Transitif Sebuah relasi dikatakan bersifat transitif jika: xRy , yRz => xRz ; (x,y, z) ∈ A Contoh:

R = {(a,d),(d,e),(a,e)}

Simetrik Sebuah relasi dikatakan bersifat simetris jika: xRy, berlaku pula yRx untuk (x dan y) ∈ A Cotoh:

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

Asimetrik Relasi asimetrik adalah kebalikan dari relasi

simetrik Artinya (a,b) ∈ R, (b,a) ∉ R Contohnya R = {(a,b), (a,c), (c,d)}

Equivalen Sebuah relasi R dikatakan equivalen jika

memenuhi syarat: Refelksif Simeteris Transitif

Partially Order Set (Poset) Sebuah relasi R dikatakan terurut sebagian

(POSET) jika memenuhi syarat: Refleksif Antisimetri Transitif

Latihan 2

A={1,2,3,4} Sebutkan sifat untuk relasi < pada himpunan A !

Apakah relasi berikut asimetris, transitif?R = {(1,2),(3,4),(2,3),(3,3)}

Apakah R = {(a,a),(a,b),(a,c),(b,b),(b,a),(c,c)} refleksif?

Operasi dalam relasi Operasi himpunan seperti irisan, gabungan,

selisih, dan penjumlahan (beda setangkup) juga berlaku pada relasi

Jika R1 dan R2 masing-masing merupakan relasi dari himpuna A ke himpunan B, maka R1 ∩ R2, R1 ∪ R2, R1 – R2, dan R1 ⊕ R2 juga adalah relasi dari A ke B.

Contoh operasi relasi Misalkan A = {a, b, c} dan B = {a, b, c, d}.

Relasi R1 = {(a, a), (b, b), (c, c)} Relasi R2 = {(a, a), (a, b), (a, c), (a, d)} Maka : 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)}

Operasi dalam bentuk matriks Misalkan bahwa relasi R1 dan R2 pada

himpunan A dinyatakan oleh matriks

Maka:

Komposisi relasi Misalkan

R adalah relasi dari himpunan A ke himpunan B T adalah relasi dari himpunan B ke himpunan C.

Komposisi R dan T, dinotasikan dengan T ο R, adalah relasi dari A ke C yang didefinisikan oleh :

T ο R = {(a, c) a ∈ A, c ∈ C, dan untuk suatu b ∈ B sehingga (a, b) ∈ R dan (b, c) ∈ T }

Komposisi relasi Misalkan, A = {a, b, c}, B = {2, 4, 6, 8} dan C

= {s, t, u} Relasi dari A ke B didefinisikan oleh :

R = {(a, 2), (a, 6), (b, 4), (c, 4), (c, 6), (c, 8)} Relasi dari B ke C didefisikan oleh :

T = {(2, u), (4, s), (4, t), (6, t), (8, u)} Maka komposisi relasi R dan T adalah

T o R= {(a, u), (a, t), (b, s), (b, t), (c, s), (c, t), (c, u)}

Komposisi relasi T o R = {(a,u), (a,t), (b,s), (b,t), (c,s), (c,t),

(c,u)}