satriawae

Relasi Ekivalen dan Relasi Terurut

by on Sep.20, 2010, under Matematika Diskret

Sebuah relasi pada himpunan A dinamakan relasi ekivalen jika relasi tersebut refleksif, simetri dan transitif. Dua unsur yang berelasi ekivalen disebut equivalent. Sedangkan sebuah relasi R pada himpunan S dikatakan relasi terurut parsial jika relasi tersebut bersifat refleksif, antisimetri dan transitif. Sebuah himpunan S yang dilengkapi dengan sebuah relasi R yang terurut parsial, himpunan tersebut dinamakan himpunan terurut parsial (partially ordering set – blog post), Notasi : (S, R).

Berikut adalah contoh Relasi Ekivalen

Contoh :

Misalkan R merupakan relasi pada sebuah Z,

yang dinyatakan oleh :

a R b jika dan hanya jika a = b atau a = – b .

Periksa, apakah relasi tersebut merupakan relasi ekivalen !

• Jelas bahwa a = a, dengan kata lain jika a R a untuk setiap a Z .

Jadi R merupakan relasi refleksif.

• Jika a = ±b dan b = ± c, ini mengakibatkan a = ± c. Dengan kata lain jika

a R b maka b R c maka a R c.

Dengan demikian R merupakan relasi transitif.

• Jika a = b atau a = – b maka b = a atau b = – a, dengan kata lain jika

a R b maka b R a.

Jadi R merupakan relasi simetri.

Dengan demikian R merupakan relasi ekivalen.

Contoh :

Misalkan R merupakan relasi pada sebuah himpunan Riil, yang dinyatakan oleh :

a R b jika dan hanya jika a b ∈ Z.

Periksa, apakah relasi tersebut merupakan relasi ekivalen !

Untuk setiap a ∈ Rill maka a a = 0 ∈ bilangan bulat, oleh karena itu R bersifat refleksif.

Misalkan a R b maka (a b) ∈ Z, jelas bahwa (b a) ∈ Z. Dengan demikian R bersifat simetri.

Jika a R b dan b R c artinya (a b), (b c) ∈ Z maka

(a c) = (a b) + (b c) juga merupakan bilangan bulat.

Oleh karena itu a R c. Jadi R bersifat transitif.

Dengan demikian R merupakan relasi ekivalen.

Contoh :

Misalkan m adalah bilangan bulat yang lebih besar dari 1.

Tunjukan bahwa Relasi

R = {(a,b) | a b (mod m)} merupakan relasi ekivalen

pada himpunan bilangan bulat.

Ingat bahwa a b (mod m) jika dan hanya jika m membagi a – b .

Karena a – a = 0 dapat dibagi oleh m, yaitu 0 = 0 m.

Oleh karena itu, a a (mod m) , sehingga R bersifat refleksif.

a – b dapat dibagi oleh m sehingga a – b = km, untuk suatu k ∈ Z Ini mengakibatkan                     b – a = –km. Jadi relasi tersebut simetri

Misalkan a b (mod m) dan b c (mod m),

sehingga a – b dan b – c dapat dibagi oleh m, atau

a – b = km dan b – c = lm untuk suatu k, l∈ Z

Dengan menjumlahkan keduanya :

a – c = (a – b) + (b – c) = (k + l) m, maka a c (mod m),

Ini menunjukan bahwa relasi tersebut transitif.

Dengan demikian R merupakan relasi ekivalen.

Misalkan R adalah relasi ekivalen pada himpunan A. Semua unsur himpunan yang relasi dengan suatu unsure a di A dinamakan kelas ekivalen dari a.

Kelas ekivalen dari a terhadap relasi R dinotasikan oleh [a]R. Jika hanya ada satu relasi pada himpuanan tersebut, notainya adalah [a].

Contoh :

Tentukan kelas ekivalen 0, 1, –2, dan –3 pada relasi modul kongruen 4!

[0] = { . . . , – 12, – 8, – 4, 0, 4, 8, 12, . . . }

[1] = { . . . , – 11, – 7, – 3, 1, 5, 9, . . . }

[–2] = { . . . , – 10, – 6, – 2, 2, 6, 10, . . . }

[–3] = { . . . , – 11, – 7, – 3, 1, 5, 9, . . . }

Sebuah relasi R pada himpunan S dikatakan relasi terurut parsial jika relasi tersebut bersifat refleksif, antisimetri dan transitif. Sebuah himpunan S yang dilengkapi dengan sebuah relasi R yang terurut parsial, himpunan tersebut dinamakan himpunan terurut parsial (partially ordering set – poset), Notasi : (S, R).

Contoh :

Tunjukan bahwa relasi ‘≤’ merupakan relasi terurut pada Z.

Karena a a untuk setiap a ∈ Z, maka relasi ‘≤’ bersifat refleksi.

Jika a b dan b a berarti a = a. Jadi relasi ‘≤’ bersifat antisimetri.

Jika a b dan b c berarti a c. Jadi relasi ‘≤’ bersifat transitif.

Dengan demikian relasi ‘≤’ merupakan relasi terurut pada Z.

Setiap unsur dalam poset (S, ρ) dikatakan comparable (dapat dibandingkan) jika a ρ b atau b ρ a untuk setiap a, b ∈ S. Selanjutnya, Jika (S, ρ) merupakan sebuah poset dan setiap dua unsur dalam S adalah comparable, maka S dinamakan Totally Ordered Set (Himpunan terurut total) atau Chain, sedangkan ρ dinamakan urutan total.

Contoh :

1. ( N, ≤ ) merupakan toset.

2. ( N, | ) bukan toset karena tak comparable.

Jika (S, ρ) adalah sebuah toset dan setiap subset tak kosong dari S paling sedikit memiliki satu unsur, maka (S, ρ) dinamakan Well-ordered Set (himpunan terurut dengan baik).

Setiap himpunan terurut parsial dapat disajikan dalam bentuk diagram Hasse. Langkah-langkah dalam menggambar digram Hasse dari suatu poset adalah :

• Gambarkan relasi urutan dalam bentuk directed graph.

• Hapus semua loop (karena refleksif)

• Hapus semua lintasan transitif

Be Sociable, Share!
:, ,

Leave a Reply

*

This blog is kept spam free by WP-SpamFree.

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Visit our friends!

A few highly recommended friends...

Archives

All entries, chronologically...