Relasi Terurut Sebagian (POSET)


Relasi sering digunakan untuk mengurutkan elemen-elemen di dalam himpunan. Misalnya, elemen-elemen di dalam himpunan bilangan bulat terurut oleh relasi \leq (lebih kecil dari atau sama dengan). Karena elemen-elemen tersebut terurut berdasarkan relasi \leq, maka jika diberikan sebuah elemen bilangan bulat, kita dapat menentukan bilangan bulat berikutnya atau bilangan bulat sebelumnya.

Secara intuitif, di dalam relasi pengurutan parsial, istilah pengurutan berarti 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 itu sendiri memang menyatakan bahwa benda-benda di dalam himpunan tersebut diurutkan berdasarkan sifat atau criteria tersebut. Akan tetapi, ada juga kemungkinan dua buah benda di dalam himpunan tidak berhubungan dalam suatu relasi pengurutan parsial. Dalam hal demikian, kita tidak dapat mmbandingkan keduanya sehingga tidak dapat diidentifikasi mana yang lebih besar atau lebih kecil. Oleh karena itulah digunakan istilah pengurutan parsial atau pengurutan tidak-lengkap. Secara formal didefinisikan sebagai berikut.

Definisi

Jika R relasi pada A dan R memenuhi sifat :

  1. Reflektif, yaitu \forall a \in A berlaku (a,a) \in R
  2. Antisimetri, yaitu \forall a,b \in A(a,b) \in R dan (b,a) \in R berakibat a = b
  3. Transitif, yaitu \forall a,b,c \in A(a,b) \in R dan (b,c) \in R berakibat (a,c) \in R

Maka relasi R pada A tersebut mendefinisikan suatu urutan parsial (partial order).

Contoh 1 :

Periksa apakah relasi “x habis membagi y” pada himpunan A = {1, 2, 3, 4, 6} merupakan Relasi Terurut Sebagian.

Sebelumnya kita harus mendaftarkan terlebih dahulu anggota R yang memenuhi relasi diatas. R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (6, 6)}. Setelah itu kita harus selidiki apakah ketiga sifat pada Definisi diatas ada pada relasi R ini.

  1. Reflektif

    (1, 1), (2, 2), (3, 3), (4, 4), dan (6, 6) \in R untuk setiap elemen di A.

    Berdasarkan definisi Transitif, maka R bersifat transitif

  2. Antisimetri

    Berdasarkan Definisi maka berlaku (a, b) \in R dan (b, a) \in R berakibat a = b untuk setiap a, b \in A. Dan untuk a \neq b berlaku (a, b) \in R tetapi (b, a) bukan elemen R

  3. Transitif

    Jelas bersifat transitif, silahkan dicek sendiri.

Contoh 2 :

Misalkan S \subseteq \mathbb{N} dan relasi “\leq” menyatakan urutan kurang dari. Apakah relasi “\leq” pada S merupakan terurut sebagian ?

Relasi \leq bersifat transitif karena untuk setiap a \in S berlaku a \leq a. Kemudian untuk sifat antisimetri juga berlaku pada relasi ini karena a \leq b dan b \leq a jika a = b dan selain itu a \leq b tetapi b \leq a jika a \neq b. Untuk sifat yang ketiga yaitu sifat transitif juga berlaku karena jika a \leq b dan b \leq c maka a \leq c untuk a, b, c \in S. Jadi relasi “\leq” termasuk terurut sebgaian.

Sumber :

Bahri, S., 2006, Logika dan Himpunan, Universitas Mataram, Mataram.

Munir, R., 2009, Matematika Diskrit, Informatika, Bandung.

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s