RELASI KESETARAAN DAN PARSIAL

RELASI KESETARAAN DAN PARSIAL

Sebelum kita masuk ke materi relasi kesetaraan dan parsial, saya akan membahas terlebih dahulu pengertian relasi. Secara sederhana, relasi dapat diartikan sebagai hubungan. Hubungan yang dimaksud di sini adalah hubungan antara daerah asal (domain) dan daerah kawan (kodomain). Kedua jenis daerah akan dijelaskan kemudian. Sedangkan fungsi adalah relasi yang memasangkan setiap anggota himpunan daerah asal tepat satu ke himpunan daerah kawannya.
            Pada relasi, tidak ada aturan khusus untuk memasangkan setiap anggota himpunan daerah asal ke daerah kawan. Aturan hanya terikat atas pernyataan relasi tersebut. Setiap anggota himpunan daerah asal boleh mempunyai pasangan lebih dari satu atau boleh juga tidak memiliki pasangan. Berdasarkan uraian singkat mengenai pengertian relasi di atas, maka relasi akan dinyatakan setara dan parsial apabila memenuhi sifat – sifat dari relasi.

      A.  Sifat – Sifat Relasi

1. Refleksif (reflexive)

Suatu relasi R pada himpunan A dinamakan bersifat refleksif jika (a, a) ∈ R untuk setiap a ∈ A. Dengan kata lain, suatu relasi R pada himpunan A dikatakan tidak refleksif jika ada a ∈ A sedemikian sehingga (a, a) ∉ R.

Contoh 1 :

Misalkan A = {1, 2, 3, 4}, dan relasi R adalah relasi ‘≤’ yang didefinisikan pada himpunan A, maka

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

Terlihat bahwa (1, 1), (2, 2), (3, 3), (4, 4) merupakan unsur dari R. Dengan demikian R dinamakan bersifat refleksif.

Contoh 2 :

Misalkan A = {2, 3, 4, 8, 9, 15}.

Jika kita definisikan relasi R pada himpunan A dengan aturan :

(a, b) ∈ R jika a faktor prima dari b

Perhatikan bahwa (4, 4) ∉ R .

Jadi, jelas bahwa R tidak bersifat refleksif.

Sifat refleksif memberi beberapa ciri khas dalam penyajian suatu relasi, yaitu :

• Relasi yang bersifat refleksif mempunyai matriks yang unsur diagonal utamanya semua bernilai 1, atau m_ii = 1, untuk i = 1, 2, …, n,

• Relasi yang bersifat refleksif jika disajikan dalam bentuk graf berarah maka pada graf tersebut senantiasa ditemukan loop setiap simpulnya.

2. Simetri (symmetric) dan Anti Simetri (antisymmetric)

Suatu relasi R pada himpunan A dinamakan bersifat simetri jika (a, b) ∈ R, untuk setiap a, b ∈ A, maka (b, a) ∈ R. Suatu relasi R pada himpunan A dikatakan tidak simetri jika (a, b) ∈ R sementara itu (b, a) ∉ R.

Suatu relasi R pada himpunan A dikatakan anti simetri jika untuk setiap a, b ∈ A, (a, b) ∈ R dan (b, a) ∈ R berlaku hanya jika a = b. Perhatikanlah bahwa istilah simetri dan anti simetri tidaklah berlawanan, karena suatu relasi dapat memiliki kedua sifat itu sekaligus. Namun, relasi tidak dapat memiliki kedua sifat tersebut sekaligus jika ia mengandung beberapa pasangan terurut berbentuk (a, b) yang mana a ≠ b.

Contoh 1 :

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

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

Periksa apakah relasi R bersifat simetri !

Misalkan a R b maka (a – b) ∈ Z, Sementara itu jelas bahwa (b – a) ∈ Z.

Dengan demikian R bersifat simetri.

Contoh 2 :

Tunjukan bahwa relasi ‘≤’ merupakan pada himpunan Z. bersifat anti simetri

Jelas bahwa jika a ≤ b dan b ≤ a berarti a = b.

Jadi relasi ‘≤’ bersifat anti simetri.

Contoh 3 :

Relasi “habis membagi” pada himpunan bilangan bulat asli N merupakan contoh relasi yang tidak simetri karena jika a habis membagi b, b tidak habis membagi a, kecuali jika a = b. Sementara itu, relasi “habis membagi” merupakan relasi yang anti simetri karena jika a habis membagi b dan b habis membagi a maka a = b.

3. Transitif (transitive)

Suatu relasi R pada himpunan A dinamakan bersifat transitif jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk a, b, c ∈ A.

Contoh 1 :

Misalkan A = { 2, 3, 4, 5, 6, 7, 8, 9}, dan relasi R didefinisikan oleh :

a R b jika dan hanya jikan a membagi b, dimana a, b ∈ A,

Dengan memperhatikan definisi relasi R pada himpunan A, maka :

R = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 4), (4, 8)}

Ketika (2, 4) ∈ R dan (4, 8 ) ∈ R terlihat bahwa (2, 8 ) ∈ R.

Dengan demikian R bersifat transitif.

Contoh 2 :

R merupakan relasi pada himpunan bilangan asli N yang didefinisikan oleh :

R : a + b = 5, a, b ∈ A,

Dengan memperhatikan definisi relasi R pada himpunan A, maka :

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

Perhatika bawa (1, 4) ∈ R dan (4, 1) ∈ R , tetapi (1, 1) ∉ R.

Dengan demikian R tidak bersifat transitif. Sifat transitif memberikan beberapa ciri khas dalam penyajian suatu relasi, yaitu : sifat transitif pada graf berarah ditunjukkan oleh :

Jika ada busur dari a ke b dan busur dari b ke c, maka juga terdapat busu berarah dari a ke c. Pada saat menyajikan suatu relasi transitif dalam bentuk matriks, relasi transitif tidak mempunyai ciri khusus pada matriks representasinya.

           B.  Relasi Kesetaraan dan Parsial

1.    Relasi Kesetaraan

Pengertian : Relasi R pada himpunan A disebut relasi kesetaraan (equivalence relation) jika ia refleksif, setangkup dan menghantar. Secara intuitif, di dalam relasi kesetaraan, dua benda berhubungan jika keduanya memiliki beberapa sifat yang sama atau memenuhi beberapa persyaratan yang sama. Dua elemen yang dihubungkan dengan relasi kesetaraan dinamakan setara (equivalent).

Contoh:

      A = himpunan mahasiswa, R relasi pada A:

      (a, b) Î R jika a satu angkatan dengan b.

      R refleksif: setiap mahasiswa  seangkatan dengan dirinya sendiri

      R setangkup: jika a seangkatan dengan b, maka b pasti seangkatan dengan a.

      R menghantar:  jika a seangkatan dengan b dan b seangkatan dengan c, maka pastilah a seangkatan dengan c.   

Dengan demikian, R adalah relasi kesetaraan.

2.    Relasi Parsial

Pengertian : Relasi R pada himpunan S dikatakan relasi pengurutan parsial (partial ordering relation) jika ia refleksif, tolak-setangkup, dan menghantar. Himpunan S bersama-sama dengan relasi R disebut himpunan terurut secara parsial (partially ordered set, atau poset), dan dilambangkan dengan (S, R).

Contoh 1 :

Relasi ³ pada himpunan bilangan bulat adalah relasi pengurutan parsial.

      Alasan:

      Relasi ³ refleksif, karena a ³ a untuk setiap bilangan bulat a;

     

      Relasi ³ tolak-setangkup, karena jika a ³ b dan b ³ a, maka a = b;

     

      Relasi  ³ menghantar, karena jika a ³ b dan b ³ c maka a ³ c.

Contoh 2 :

Relasi “habis membagi” pada himpunan bilangan bulat adalah relasi pengurutan parsial.

      Alasan: relasi “habis membagi” bersifat refleksif, tolak-setangkup, dan menghantar.

Secara intuitif, di dalam relasi pengurutan parsial, dua buah benda saling berhubungan jika salah satunya lebih kecil (lebih besar) daripada, atau lebih rendah (lebih tinggi) daripada lainnya menurut sifat atau kriteria tertentu.

Istilah pengurutan menyatakan bahwa benda-benda di dalam himpunan tersebut dirutkan berdasarkan sifat atau kriteria tersebut.          

Ada juga kemungkinan dua buah benda di dalam himpunan tidak berhubungan dalam suatu relasi pengurutan parsial. Dalam hal demikian, kita tidak dapat membandingkan keduanya sehingga tidak dapat diidentifikasi mana yang lebih besar atau lebih kecil. Itulah alasan digunakan istilah pengurutan parsial atau pengurutan tak-lengkap.