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. CONTOH 1. Himpunan Z+ adalah himpunan bilangan bulat positif. Relasi (kurang atau sama dengan) adalah sebuah parsial order pada Z+ . Hal ini berlaku pula untuk relasi . Jawab : Bila (a,b) ada didalam R jika a b. Karena setiap bilangan bulat = dirinya sendiri refleksive (memantul) Karena a b dan b a kecuali a = b antisymmetris Jika a b dan b c maka a c transitive ( menghantar ).
Diagram Hasse (telah dibahas diawal) suatu relasi biner dari himpunan A ke himpunan B dapat didajikan dalam bentuk grafik maupun tabel. e e a b c d e a d d c c b c
b
d
b
e
(i)
a
a
( ii )
( iii )
Bila relasi biner itu berupa relasi pengurutan parsial, sajian grafik itu bisa lebih disederhanakan lagi. Karena relasi bersifat memantul (refleksive), kita dapat membuang panel-panel ke titik (-titik) nya sendiri. lihat gambar (i) menjadi (ii). Karena relasi bersifat menghantar (transitive), kita dapat membuang panah antar titik-titik yang dihubungkan dengan serangkaian panah. lihat gambar (ii) menjadi gambar (iii). # Representasi grafik suatu relasi pengurutan parsial yang semua tanda panahnya mengarah keatas juga dikenal sebagai : “Diagram Hasse“ bagi relasi tersebut. CONTOH 2. A = { 1,2,3,4,12 }. Anggap pengurutan parsial dari pembagian pada himpunan A jika a dan b A, a b jika dan hanya jika a / b. Gambarkan diagram Hasse Poset ( A, ). Jawab:
12
12
4
4 3
3
2
2 1
1
S = { a,b,c } dan A = P(S). Gambarkan diagram Hasse poset A dengan partial order (himpunan bagian) : (A,)
3.
Jawab : A = { , {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} {a,b,c}
{a,c} {b,c}
{a,b} {c} {a}
{b}
Dengan mudah dapat dilihat jika ( A, ) adalah sebuah poset dan ( A, ) adalah poset juga. Hasse diagram untuk ( A, ) persis sama dengan diagram ( A, ) yang dibalik diatas kebawah.
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. j
b
(dalam contoh gambar disamping), j adalah unsur maksimum, sedangkan a, b, e adalah unsur minimum.
h
i
f
g
c
d a
“ Upper Bound “ Misalkan a dan b dua unsur sembarang di dalam suatu himpunan terurut parsial ( A, ). Suatu unsur c dikatakan sebagai batas atas (upper bound) bagi a dan b jika a c dan b c. Dalam gambar: h adalah upper bound bagi f dan g. Begitu pula i dan j = upper bound bagi g.
e
Suatu unsur c dinamakan batas atas terkecil (least upper bound = LUB ) bagi a dan b jika c merupakan suatu batas atas bagi a dan b, dan tidak ada batas atas lain d bagi a dan b yang bersifat d c.
“Lower Bound “ 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.
LATTICEs Pengertian dan Notasi Sebuah lattice adalah sebuah poset (L, ) 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. Teorema 1 Jika (L1, ) dan (L2, ) adalah lattice, kemudian (L, ) adalah lattice, dimana L= L1 L2 dan partial order pada L adalah product partial order. Bukti: Kita notasikan join dan meet dalam L1 dengan 1 dan 1, secara berurutan, join dan meet pada L2 dengan 2 dan 2 secara berurutan, sehingga : (a1,b1) (a2,b2) = (a1 1 a2, b1 b2) (a1,b1) (a2,b2) = (a1 1 a2, b1 b2) dengan demikian L adalah lattices. Contoh 1 Pada himpunan S yang beranggotakan a dan b - a b = a b - ab = a b Pengertian dari a b dan a b 1. a a b; b a b, maka (a b adalah sebuah batas atas ( an upper band ) untuk a dan b). kita dapat mengatakan demikian karena dari pertidaksamaan di atas terlihat bahwa a b selalu lebih besar atau sama dengan a atau b. sehingga dapat diambil kesimpulan a b adalah yang paling besar (upper bound). 2. Jika a c dan b c, kemudian a b c maka a b adalah sebuah batas atas terendah (a least upper bound) untuk a dan b. 3. a b a dan a b b maka a b adalah sebuah batas bawah untuk a dan b ( a lower bound) untuk a dan b.
4. jika c a dan c b, kemudian c a b, maka a b adalah batas bawah terbesar (a greatest lower bound) untuk a dan b. Isomorphic Lattices Jika f: L1 L2 adalah isomorphisme dari poset (L1, 1) ke poset (L2, 2), kemudian pada teorema 4 (4.2) menerangkan bahwa L1 adalah lattice jika dan hanya jika L2 adalah lattice. Faktanya, jika a dan b adalah elemen-elemen pada L1, kemudian f(a b) = f(a) f(b) dan f(a b)= f(a) f(b). jika kedua lattice adalah isomorphic sebagai poset, kita dapat katakan keduanya adalah isomorphic lattices. teorema 2 misal L adalah Lattices, kemudian untuk setiaap a dan b dalam L (a) a b = b , jika dan hanya jika a b. bukti anggap bahwa a b = b karena a a b= b , kita dapatkan a b. sebaliknya jika a b kemudian karena b b, b adalah an upper bound untuk a dan b, oleh karena itu dengan definisi least upper bound kita peroleh a b b kareana a b adalah an upper bound, b a b, sehingga a b= b. (b) a b=a, jika dan hanya jika a b bukti : anggap bahwa a b = a karena a = a b a , kita dapatkan a a. b adalah an upper bound untuk a dan b, oleh karena itu dengan definisi greatest lower bound kita peroleh a b a kareana a b adalah a lower bound, a b a , a b= a. (c) a b=c jika dan hanya jika a b= b. Teorema 3 1. Idempotan properties. a a = a a a=a 2. Commutative properties. a b = b a a b=b a 3. Associative properties a (b c) = (a b) c a (b c) = (a b) c 4. Absorption Porperties a (a b) = a a (a b) = a Teorema 4 1. jika a b maka a c b c a c b c 2. a c dan b c jika dan hanya jika a b c 3. c a dan c b jika dan hanya jika c a b. 4. jika a b dan c d maka
a c b d a c b d teorema 6 a a’ = I dan a a’ = 0 berarti a’ adalah komplemen a, dimana I adalah elemen terbesar (greatest elemen) dan 0 adalah elemen terkecil(least elemen). Dengan demikian : 0’ = I dan I = 0’ Teorema 7 a’ = a’’ misal a’ dan a’’ adalah komplemen untuk 0 L, maka a a’= I a a’’ = I a a’= 0 a a’’ = 0 dengan aturan distribusi didapat a’ = a’ 0 = a’ (a a’’) = (a a’) (a’ a’’) = I (a’ a’’) = a’ a’’ juga a’’ = a’’ 0 = a’’ (a a’) = (a a’’) (a’ a’’) = I (a’ a’’) = a’ a’’ sehingga dapat dikatakan bahwa a’ = a’’. Contoh 2 Jika n adalah sebuah bilangan bulat positif, dan Dn adalah himpunan dari semua bilangan bulat positif pembagi n, Dn adalah sebuah Lattice berdasar dengan hubungan keterbagian. Dn = {1, 2, 3, 4, 5, 10, 20} Diagram Hasse untuk Dn 20 4
10
2
5 1
