POSET (
Partially Ordered Set )
Himpunan Terurut Parsial
Definisi
Suatu relasi biner dinamakan sebagai suatu
relasi pengurutan tak lengkap atau relasi pengurutan parsial ( partial ordering
relation ) jika ia bersifat reflexive, antisymmetric, dan transitive.
Ilustrasi
Misalkan A sebuah himpunan bilangan bulat
positif dan R sebuah relasi biner pada A sedemikian rupa sehingga ( a,b ) ada
di dalam R jika a membagi habis b.
Ø Karena jika a membagi habis b berarti b
tidak membagi habis a kecuali a = b, R adalah sebuah relasi antisymmetric. (
tolak setangkup )
Ø Karena setiap bilangan bulat membagi habis
dirinya sendiri, R merupakan suatu relasi reflexive. ( memantul )
Ø Karena jika a membagi habis b, dan b
membagi habis c, maka a membagi habis c, R adalah sebuah relasi transitive. (
menghantar ).
Dengan demikian R adalah sebuah relasi pengurutan
parsial.
Secara intuitif, didalam suatu relasi
pengurutan parsial, dua benda saling berhubungan. Jika salah satunya lebih
kecil ( lebih besar ) daripada atau lebih pendek ( lebih tinggi ) daripada
lainnya menurut sifat atau kriteria tertentu.
Memang
istilah pengurutan (ordering) berarti bahwa benda-benda di dalam
himpunan itu diurutkan menurut sifat atau kriteria tersebut. Akan tetapi, juga
ada kemungkinan bahwa dua benda di dalam himpunan itu tidak berhubungan dalam
relasi pengurutan parsial. Dalam hal demikian, kita tak dapat membandingkan
keduanya dan tidak mengidentifikasi mana yang lebih kecil atau lebih rendah.
Itulah alasannya digunakan istilah “ pengurutan parsial ( partial ordering ) ”.
Himpunan
A bersama-sama dengan suatu relasi pengurutan parsial R pada A
dinamakan himpunan terurut parsial ( Partially Ordered Set ) atau
disingkat sebagai Poset, dilambangkan dengan ( A, R ).
Pengurutan
parsial paling terkenal adalah relasi £ dan ³ pada himpunan Z dan R. Untuk
alasan ini, ketika berbicara secara umum tentang sebuah pengurutan parsial R
pada himpunan A kita akan sering menggunakan symbol £
atau ³ untuk R.
Tidak ada komentar:
Posting Komentar