Posset & Latice

Poset ( Partially ordered set)

Definisi

Poset atau partially ordered set atau juga diesbut himpunan terurut parasial merupakan suatu relasi dimana ia mepunyai 3 sifat yang harus terpenuhi agar bisa disebut poset yaitu sifat refleksif, antisimetris dan transitif.

Misalkan :

Misalkan A sebuah himpunan bilangan bulat positif dan R sebuah relasi yang menuju ke A sehingga menjadi ( a,b ) ada di dalam R jika a membagi habis b.

- Karena jika a membagi habis b, berarti b tidak akan membagi habis a kecual a samadengan b (a=b). Sehingga relasi ini merupakan relasi antisimetris.

- Karena setiap bilangan bulat membagi habis dengan angkanya sendiri, maka relasinya menggambarkan sebuaH relasi refleksif.

- Karena a membagi habis b dan b akan membagi habis c, maka berarti a juga akan bbisa membagi habis c, oleh karena itu bisa juga merupakan sifat transitif.

Dengan demikian, relasi diatas merupakan poset atau himpunan terurut parsial.

Contoh –contoh ilustrasi yang lain :

(a) Misal § adalah sebarang kelas dari himpunan. Relasi antara himpunan “mengandung” atau “C” merupakan uurutan parsial pada S karena :

- ACA, untuk setiap A € S

- Jika ACB dan BCA maka itu berarti A=B

- Jika ACB dan BCC maka ACC

(b) Misal N himpunan bilangan bilangan positif. Sebut “a membagi b” ditulis a|b, jika terdapat sebuah bilangan bulat c sedemikian rupa sehingga ac+b.

Contoh : 2|4, 3|12, 7|21 dan sebagainya.

Relasi dapat dibagi tersebut adalah urut parsial pada N.

(c) Relasi “ ≤ ” juga suatu urut parsial pada bilangan positif N (jelas ≤ adalah suatu urut parsial pada sebarang sub himpunan bilangan riil ).

Relasi tersebut kadang kadang diebut urut biasa pada N. Biasanya dinotasikan relasi urut parsial dengan α dengan “ a α b “ (dibaca a mendahului b). Berhubungan dengan notasi ini, digunakan notasi tambahan sebagai berikut :

a < b artinya a ≤ b dan a ≠ b baca “ a benar benar medahului b”

b ≥ a artinya a ≤ b dibaca “b sesudah a”

b > a artinya a < b dibaca “ b benar benar sesudah a”

Dua elemen a dan b dalam poste dikatakan “dapaty dibandingkan” jika

a α b atau b α a jadi jika satu mendahuluinya yang lainnya, jika tidak a dan b dikatakan “tidak dapat dibandingkan” sebagai contoh : bilangan bulat 3 dan 5 pada contoh (b) adalah tidak dapat dibandingkan satu dengan yang lainnya.

Kata “urutan” digunakan dalam mendefinisikan himpunan rut parsial pada A karena beberapa elemen dalam A tidak perlu “dapat dibandingkan”. Dalam hal jika setiap pasangan elemen dalam poset A adalah dapat dibandingkan maka A dikatakan “urut total” atau “urut linier” dan A dikatakan suatu chain, contohnya adalah bilangan biangan bulat positif N dengan urut ≤ adalah himpunan urut linier.

Jika S dan T adalah himpunan himpunan urut linier maka himpuna perkaliannya ( S x T ) dapat menjadi himpuna urutan linier jika dipenuhi :

(a,b) α (a’,b’) jika a α a’ atau jika a ‘ a’ dan b α b’ urut tersebut dapat dikatakan urut Lexico Graphical pada S x T karena urut similar ddengan cara menyusun kata kata dalam kamus.

Sebarang sub himpunan A dari satu poset S adalah urut parsial dengan urut pada S karena untuk sebarang a, b, € A misal a ≤ b sebagai elemen dari A sama halnya sebagai a ≤ b elemen S. Dengan catatan bahwa sub himpunan S dapat merupakan urutan linier walaupun S bukan merupakan urutan Linier. Sebagai contoh [2,4,16,64] adalah suatu sub himpunan urut linier ddari himpunan urutan bukan linier pada N ( kumpulan kumpulan bilangan bulat positif ) dengan urutan “dapat dibagi”.

Diagram Hasse

Diagram hasse adalah sebuah diagram sederhana yang digunakan untuk menggambarkan relasi parsial order set alias POSET.

Bila relasi itu merupakan sebuah relasi parsial sajian grafik dapat 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)

Contoh yang lain :

Jika A = {1,2,3,4,12}. Anggap pengurutan parsial dari pembagian pada himpunan A jika a dan b € A, a ≤ b dan hanya jika a/b. Gambarkan diagram hasse poset ( A,≤ ) !

SUPREMUM DAN INFIMUM

Misal A adalah sub himpunan dari poset S sebuah elemen M pada S dikatakan batas atas dari A jika M didahului setiap elemen dari A jadi jika setiap x € A, diperoleh

X ≤M

Jika suatu batas atas dari A mendahului setiap batas atas yang lain dari A maka dikatakan SUPREMUM dari A dinotasikan dengan

Sup (A).

Kita juga dapat menuliskan sup (a1,...........,an) sebagai pengganti sup (A) jika A terdiri dari elemen elemen a sampai ke n.

Dengan cara yang sama, sebuah elemen m dalam poset S dikatakan batas bawah dari suatu sub himpunan A dari S jika m medahului setiap elemen dari A jadi jika y dalam A, maka m ≤ y jka batas bawah dari A didahului setiap batas batas dari A maka dikatakan INFIMUM dari A dan dinotasikan dengan :

Inf (A)

Atau juga

Inf (a1,a2,............,an)

Selain itu juga, supremum biasa disebut sebagai batas atas terkecil dan infimum sebagai batas bawah terbesar dan dituliskan dengan lub (A) untuk sup (A) dan glb (A) untuk inf (A).

Lattice

Misal L adalah suatu himpunan yang tidak kosong tertutup terhadap 2 buah operasi binary disebbut meet dan join yang biasa dinyatakan dengan dan . Maka L dikatakan suatu LATTICE jika axioma axioma berikut dipenuhi, dimana a, b, c adalah merupakan elemen elemen sebarang dari L :

[L1] hukum komutatif :

(1a) a b = ba (1b) a b = b a

[L2] hukum asosiatif :

(2a) (ab) c = a (bc) (2b) (ab) c = a (bc)

[L3] hukum absorpsi :

(3a) a (a b) = a (3b) a (a b) = a

Kadang kadang kita menyatakan Lattice dengan notasi (L, , ) deimana kita akan menunjukkan operasi operasi mana yang memenuhi.

Dual dari sembarang pernyataan Lattice (L, , ) didefinisakan sebagai pernyataan yang diperoleh dengan menukar dan . sebagai contoh , dual dari a (b a) = a a ≤adalah a (b a)= a a

Teorema 1 :

Misal P suatu poset sedemikian sehingga inf (a,b) dan sup (a,b) ada bentuk sebarang a, b € P dengan memisalkan

ab = inf (a,b) dan ab = sup (a,b)

sehingga kita mempunyai (P, , ) suatu Lattice selanjutnya urut parsial pada P yang dihasilkan oleh Lattice adalah sama dengan urut parsial awal pada P.

Kebalikan dari teorema diatas juga benar jadi, misal L suatu Lattice dan ≤ adalah urut parsial pada L. Maka inf (a,b) dan sup (a,b) ada untuk sebarang pasangan a, b € L dan Lattice diperoleh dari poset (L, α ) adalah Lattice awal sehingga diperoleh :

a b = sup (a,b) dan

a b = inf (a,b)

ada untuk sebarang pasangan elemen a dan b.

Teorema 2

Lattice yang terbatas

Suatu Lattice L dikatakan mempunyai batas bawah 0 jika untuk sebarang elemen x dalam L berlaku 0 ≤ x. Dengan cara yang sama, L dikatakan mempunyai batas atas I jika untuk sebarang x dalam L, berlaku x ≤ I. Maka L dikatakan terbatas jika L mempunyai batas bawah 0 dan batas atas I sehingga suatu Lattice mempunyai identitas :

a I = I, a I = a, a 0= a, a 0= 0

untuk sebarang elemen a dalam L.

Teorema 3

Lattice distributif

Suatu Lattice dikatakan atau disebut distributif jika untuk sebarang elemen a,b,c dalam L memenuhi hukum [L4] hukum distributif :

(4a) a (bc)= (ab) (ac) (4b) a(bc)= (a b) (a c)

Kita nyatakan prinsip duality pada (4a) dipenuhi jika & hanya jika (4b) dipenuhi.

Teorema 4

Misal L suatu Lattice distributif maka setiap a dalam L dapat dituliskan secara unik (kecuali untuk urutan) sebagai gabungan dari elemen irredundant join irreducible. Sebenernya teorema tersebut dapat diperluas untuk Lattice dengan panjang hingga, yaitu dimana sub-sub himpunan terurut Linier adalah hingga.

Lattice berkomplemen

Misal L adalah Lattce yang terbatas dengan batas bawah 0 dan batas atas I. Misal a sebarang elemen dari L. Sebuah elemen x dalam L dikatakan komplemen dari a jika :

a x = I dan a x = 0

Teorema 5

Misal L adalah Lattice distributif maka komplemen ada dan unik.

Pembuktian :

Misal x dan y adalah komplemen dari sebarang elemen a dan L maka :

a x = I , a y = I ,a x = 0, a y = 0

dengan menggunakan sifat distributif ,

x = x 0 = y (ay )= (xa) (ay)= I (x y ) = x y

dengan cara yang sama

y= y 0 = y (ax )= (ya) (yx)= I (y x ) = y x

sehingga menjadi

x = x y = y x = y **** jadi teorema terbukti.

Teorema 6

Misal L adalah suatu Lattice berkomplemen dengan unik komplement. Maka elemen join Irreducibel dari L selain O adalah atom atomnya

Teorema 7

Misalkan L adalah Lattice distributif berkomplemen dan hingga. Maka setiap elemen a dalam L adalah gabungan dari himpunan atom atom yang unik.

Sumber referensi :

- Sumber internet doc type dari ronald haryandi

- File doc type dari fakultas mipa UNAIR

- Buku aljabar logika dan himpunan penerbit Gunadarma oleh D. Suryadi H.S