Poset dan Latice

POSET ( Partially Ordered Set )

Himpunan Terurut Parsial

Definisi

                     POSET adalah  Suatu relasi biner R pada himpunan S (R: S ® S) dikatakan partially order (terurut sebagian) jika relasi tersebut bersifat reflektif, anti simetri dan transitif. Himpunan S bersama relasi R disebut poset. Jadi (S,R) poset jika relasi R pada S reflektif, anti simetri dan transitif. 

1. Reflexive dengan syarat a R a untuk setiap a є P.

2. Antisymmetric dengan syarat a R b dan b R a maka a = b.

3. Transitive dengan syarat a R b dan b R c maka a R c

Ilustrasi

Misalkan A sebuah himpunan bilangan bulat positif dan R sebuah relasi biner pada 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.

KONSEP-KONSEP DI DALAM POSET :

1. Upper Bound (ub) atau batas atas,
2. supremum atau least upper bound (lub) atau batas atas terkecil,
3. lower bound (lb) atau batas bawah,
4. infimum atau great lower bound (glb) atau batas bawah terbesar.

UPPER BOUND : Misalkan (S, £) poset, H Ì S, unsur  Î S adalah upper bound atau batas atas dari himpunan H bila h £ untuk setiap h Î H.

SUPREMUM : Bila (S, £) poset, H Ì S, l Î S adalah supremum himpunan H jika l batas atas terkecil (least upper bound = lub) dari H, atau dengan kata lain : l batas atas H, dan tidak ada  batas atas lain H sehingga  £ l.

LOWER BOUND : Bila (S, £) poset, himpunan K Ì S, unsur  Î S adalah lower bound atau batas bawah dari himpunan K bila  £ k untuk setiap k  K. Suatu unsur c dinamakan suatu batas  bawah (lower bound) bagi a dan b jika c £ a dan c £ b. Dan suatu unsur c dikatakan sebagai suatu batas bawah terbesar (greatest lower bound = GLB) bagi a dan b jika c adalah suatu batas bawah bagi a dan b dan jika tak ada batas bawah lain d bagi a dan b yang bersifat c £ d.

     (dalam contoh diatas)

• Misal: B1 = { b, c } merupakan himpunan.bagian dari A.

Maka Upper Bound dari B1 adalah  f , h , i , j.

LUB ( B1 ) = f

• Misal: B2 = { h, i } merupakan himpunan bagian dari A.

Maka Lower Bound dari B2 = a , b , c , d , e , f dan g.

GLB ( B2 ) = f , g.

INFIMUM : Bila (S, £) poset, himpunan K Ì S, m Î S adalah infimum himpunan K jika m batas bawah terbesar (greatest lower bound = glb) dari K, atau dengan kata lain : m  batas bawah K, dan tidak ada  batas bawah lain K sehingga m £.

Diagram Poset

Misalkan S adalah suatau himpunan urut parsial.  Jika a dalam S adalah suatu yang mendahului dari B sesedah a ditulis a ≤ b jika a < b tetapi tidak ada elemen dari S yang terletak di antara a dan b, jadi tidak ada X dalam S sedemikian sehingga a < X < b.

Misalkan S adalah suatu poset yang hingga .maka urut pada S adalah diketahui secara lengkap jika kita mengetahui semua pasangan a,b dalam s sedemikian sehingga a ≤ b jadi relasi ≤ pada S . Sehingga x < y jika dan hanya jika terdapat elemen x = a_o  ,a₁ ,….a_m = y sedemikian sehingga a_1-I ≤ a_i untuk i=1 ,…m.

Menurut diagram dari suatu Poset S yang sehingga kita artikan suatu graph berarah dimana vertex adalah merupakan elemen dari S dan akan terdapat busur yang menghubungkan a dan b jika a ≤ b dalam S ( dalam mengabarkan suati arah panah dari a ke b, kita kadang-kadang menempatkan b lebih tinggi dari pada a dalam diagram dan garis dari a ke b mengarah ke atas ). Pada diagram s, terdapat suatu path bearah dari suatu vertex x ke vertex y jika dan hanya x < y. Juga tidak terdapat sebarang cycle dalam diagram S karena urut relasinya adalah anti simetris .

1.4 Titik Extrem Dari Poset

Misalkan ( A, £ ) sebuah himpunan terurut parsial. Suatu unsur a di dalam A dinamakan Unsur Maksimum (maximal elements) jika tidak ada unsur b didalam A yang bersifat a ¹ b dan a £ b.

Suatu unsur a di dalam A dinamakan unsur minimum ( minimal element ) jika tidak ada unsur b didalam A yang bersifat a ¹ b dan b £ a.

 

 

L ATTICES

Pengertian

                lattice adalah sebuah poset  yang setiap himpunan bagiannya {a,b} memiliki dua elemen yaitu a least upper bound dan a greatest lower bound. Kita notasikan least upper bound (LUB) ({a,b}) dengan a b dan kita sebut join antara a dan b, sedangkan greatest lower bound (GLB) ({a,b}) dengan a b dan disebut meet antara a dan b. struktur lattice sering terlihat dalam perhitungan dan aplikasi matematika.

Operasi Lattice :

            avb = lub {a,b}   dan   a^b = glb {a,b}

  SIFAT-SIFAT Lattice:  

 ~ Komutatif

avb = bva dan a^b = b^a

~ Asosiatif

(av b) v c = a v (b vc) dan (a ^ b) ^ c = a ^(b ^ c)

~Absorbsi

a v (a ^ b) = a dan a ^(avb) = a

~Idempoten

ava = a dan a ^ a = a        

• www.mti.ugm.ac.id/~adji/courses/resources/lectures/DiscMath/POSET.doc
• www.elearning.gunadarma.ac.id/.../bab5-poset&lattice.pdf
• Suryadi,H.S.1993.Aljabar logika dan himpunan.jakarta : universitas gunadarma.
• www.repository.binus.ac.id/content/K0144/K014466564.doc
• Http://staff.ui.ac.id/internal/130422587/material/MATEMATIKA.pdf
• www.repository.binus.ac.id/content/K0362/K036217648.ppt