BAB 5 POSET dan LATTICE

MATEMATIKA DISKRIT

BAB 5 POSET dan LATTICE 1. Himpunan Urut Parsial Suatu relasi R pada himpunan S dikatakan urut parsial pada S, jika R bersifat : 1. Refleksif, yaitu a R a, untuk setiap a Є s 2. Anti simetris, yaitu a R b dan b R a maka a = b 3. Transitif, yaitu jika a R b dan b R c maka a R c. Himpunan S berikut dengan urut parsial pada S dikatakan himpunan urut parsial atau POSET (Partially Ordered Set) Relasi urutan yang paling dikenal, disebut urutan usual, adalah relasi ≤ (kurang dari atau sama dengan) pada N atau secara lebih umum pada subset dari R. karena alasan ini, sebuah relasi urutan parsial biasanya dinotasikan oleh ≤; dan a≤b dibaca “a mendahului b”. Dalam kasus ini, juga dituliskan: ab (dibaca “a secara kuat diahului b”) jika b
BY : SRI ESTI

MATEMATIKA DISKRIT

a. A ⊆ A, untuk setiap A Є S b. Jika A ⊆ B dan B ⊆ A maka A = B c. Jika A ⊆ B dan B ⊆ C maka A ⊆ C 2. Misal N himpunan bilangan-bilangan positif. Sebut “a membagi b” ditulis a|b, jika terdapat sebuah bilangan bulat c sedemikian sehingga ac = b. Contoh : 2|4, 3|12, 7|21, dsb. Tunjukkan bahwa pembagian adalah pengurutan parsial dai N, yaitu tunjukkan bahwa: a) a│a

b) jika a│b dan b│a maka a = b

c) jika a│a dan b│c maka a│c

Jawab: a. Karena a.1 = a, maka a│a b. Anggap a│b dan b│a, misal b = ra dan a = sb. Maka b = rsb sehingga rs =1. Karena r dan s adalah bilangan bulat positif maka r =1 dan s = 1. Dengan demikian a = b c. Anggap a│b dan b│c, misal b = ra dan c = sb. Maka c = sra sehingga a│b b) 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. a. Karena setiap bilangan bulat = dirinya sendiri  refleksif b. Karena a  b dan b  a kecuali a = b  antisimetris c. Jika a  b dan b  c maka a  c  transitif. Latihan soal: 1. Misalkan bilangan-bilangan bulat positif N = {1, 2, 3, …} diurutkan dengan relasi dapat dibagi : a. Isilah simbol yang tepat, <, > atau || (tidak dapat dibandingkan) antara setiap pasangan dari bilangan-bilangan : (1) 2 … 8

(2) 18 … 24

(3) 9 … 3

(4) 5 … 15

BY : SRI ESTI

MATEMATIKA DISKRIT

b. Nyatakan apakah masing-masing sub-sub himpunan dari N adalah terurut secara linier: a. [24, 2, 6]

b. [3, 15, 5]

c. [15, 5, 30]

d. [2, 8, 32, 4]

e. [1, 2, 3,…]

f. [7]

2. Misalkan V = {a, b, c, d, e} terurut menurut diagram berikut. Sisipkan simbol yang tepat, <, >, atau || setiap pasangan dari elemen-elemen : a. a … c

b. b … c

c. d … a

d. c … d

a b d

c e

3. Misalkan S = {1, 2, 3}. Tuliskan himpunan urut parsial dari R pada S. 4. Misalkan R = {(1, 1), (1, 2), (2, 2), (1, 3), (3, 1), (3, 3)}. Apakah R adalah himpunan urut parsial pada A = {1, 2, 3, 4}. 5. Misalkan R = {(1, 1), (2, 2)}. Apakah R adalah suatu himpunan urut parsial pada A = {1, 2}

2. Diagram Poset Misal S adalah suatu himpunan urut parsial. Sebut a dalam S adalah suatu yang mendahului dari b atau b sesudah a ditulis a ≤ b jika a < b tetapi tidak ada elemen dari S yang terletak diantara a dan b, jadi tidak ada X dalam S sedemikian sehingga a < X < b. Misal S adalah suatu POSET yang hingga. Maka urut pada S adalah diketahui secara lengkap jika kita mengetahui semua pasangan a, b, S sedemikiansehingga a≤b jadi

BY : SRI ESTI

MATEMATIKA DISKRIT

relasi ≤ pada S. Sehingga x
12

18

4

6

9

2

3 1

2. Misal B = {a, b, c, d, e}. Gambar diagramnya yang didefinisikan suatu urut parsial pada B dengan cara alfabetis. Jadi d ≤ b, d ≤ a, e ≤ a, dst. Penyelesaian : a b

c d

e BY : SRI ESTI

MATEMATIKA DISKRIT

3. Diagram suatu himpunan urut linier yang hingga yaitu suatu chain hingga yang terdiri dari sebuah path yang sederhana. Seperti contoh pada gambar berikut yang menunjukkan diagram dari suatu chain dengan 5 elemen. Y U Z Y X Latihan Soal: 1. Terdapat 7 partisi dari m = 5 : 5, 3-2, 2-2-1, 1-1-1-1-1, 4-1, 3-1-1, 2-1-1-1 Gambarlah diagram dari partisi bulat m = 5 2. Misalkan D = {1, 2, 3, 4, 6, 9, 12, 18, 36}. Gambarlah diagram posetnya dalam urut “x membagi y”. 3. Perhatikan himpunan B = {a, b, c} dan himpunan P merupakan semua subset dari B. gambarkan diagram untuk elemen-elemen dari P. 4. Perhatikan himpunan D = {1, 2, 3, 4, 5} yang terurut secara linier seperti gambar berikut: 1

5

2

4

gambarkan diagram untuk urutan invers dalam D

3

3. Supremum dan Infimum Misal A adalah subset dari Poset S. Sebuah elemen M pada S dikatakan batas atas dari A jika M melampaui setiap elemen dari A jadi jika setiap x Є A, diperoleh

BY : SRI ESTI

MATEMATIKA DISKRIT

x≤M Jika suatu batas atas dari A mendahului setiap batas atas lain dari A maka dikatakan batas atas terkecil atau SUPREMUM dari A dinotasikan dengan sup (A) atau sup (a1, …, an) Dengan cara yang sama, sebuah elemen m dalam Poset S dikatakan sebuah batas bawah dari A jika m mendahului setiap elemen dari A, yaitu, m adalah sebuah batas bawah jika untuk setiap x dalam A kita dapatkan m ≤ y. Jika batas bawah dari A melampaui setiap batas bawah dari A maka disebut batas bawah terbesar atau INFIMUM dari A dan dinotasikan dengan inf (A) atau inf (a1, …, an) sub A dan inf A masing-masing adalah unik jika mereka ada. Jika A mempunyai sebuah batas atas kita mengatakan A terbatas di atas, dan jika A mempunyai sebuah batas bawah, kita mengatakan A terbatas di bawah. Dan khususnya, A terbatas jika ia mempunyai sebuah batas atas dan batas bawah. Misal a,b Є Poset (A, ≤) 1) c Є A, c = batas atas dari a & b bila dan hanya bila a ≤ c & b ≤ c. c Є A, c = batas atas terkecil/b.a.t (Least Upper Bound (LUB)) dari a & b bila dan hanya bila : a) c batas atas dari a & b, b) Jika d batas atas dari a & b yang lain, maka c ≤ d. 2) c Є A, c = batas bawah dari a & b bila dan hanya bila c ≤ a & c ≤ b. c Є A, c = batas bawah terbesar (Greatest Lower Bound (GLB)) dari a & b bila dan hanya bila : a). c batas bawah dari a & b, b). Jika d batas bawah dari a & b yang lain, maka d ≤ c Dalam suatu Poset, LUB tidak selalu ada. Tetapi jika LUB ada, maka LUB tersebut tunggal. Hal yang sama, juga berlaku pada GLB.

BY : SRI ESTI

MATEMATIKA DISKRIT

Contoh Soal: 1. Misal A = { a, b, c, d, e, f, g, h, i }. Relasi Partial Order didefinisikan pada himpunan A atau (A, ≤) dalam diagram Posset di bawah ini. Carilah elemen maksimal, minimal, terbesar dan terkecil !

2. Misalkan V ={a, b, c, d ,e, f ,g} terurut seperti gambardan misalkan X = {c, d, e} a. Tentukan batas atas dan batas bawah dari X b. Tentukan sup(X) dan inf(X) f

g e

c

d

a

b

X

Penyelesaian: a. Elemen e, f dan g “didahului” oleh setiap elemen dari X; sehingga e, f dan g adalah batas atas dari X b. Elemen a “mendahului” setiap elemen dari X; sehingga a adalah batas bawah dari X. Perhatikan bahwa b bukan sebuah batas bawah karena b tidak mendahului c; b dan c tidak comparable.

BY : SRI ESTI

MATEMATIKA DISKRIT

3. Misalkan W = {a, b, c, d, e, f} terurut seperti gambar dan misalkan Y = {b, c, d} a. Tentukan batas atas dan batas bawah dari Y b. Tentukan sup(Y) dan inf(Y) e

f

c

d b

Y

a Penyelesaian: a. Elemen e dan f didahului setiap elemen dalam Y; jadi e dan f adalah batas atas dari Y. Elemen a dan b mendahului setiap elemen dalam Y; jadi a dan b adalah batas bawah dari Y. b. Karena dua batas atas dari Y, e dan f tidak comparable, sup(Y) tidak ada. Inf(Y) = b, karena elemen b melampaui a. Latihan Soal: 1. Misalkan B = {1,2, 3, 4, 5} terurut seperti gambar : a. Carilah semua elemen minimal dari B b. Carilah semua elemen maksimal dari B

2. Misalkan D = {1, 2, 3, 4,5, 6} terurut seperti gambar, sub himpunan E = {2, 3, 4} dari D : a. Carilah batas atas dai E b. Carilah batas bawah dari E c. Apakah sup(E) ada? d. Apakah inf(E) ada?

BY : SRI ESTI

MATEMATIKA DISKRIT

3. Misalkan S = {1, 2, 3, …, 8} terurut seperti gambar dan misalkan L = {4, 5, 7}, M = {2, 3, 6} dan K = {1, 2, 4, 7} c. Tunjukkan batas-batas atas dan bawah dari L, M, dan K d. Tentukan sup(L), sup(M), sup(K) dan inf(L), inf(M), inf(K) jika ada 1

2 3

4

5 6

7 8

4. Misalkan himpunan S = {3, 6, 9, 12, 18} terurut menurut pembagian. a. Untuk subset S apakah dimana {6, 12, 18} merupakan himpunan batas-batas atas? b. Untuk subset S apakah dimana {3, 6} merupakan himpunan batas-batas bawah?

c. Lattice Berdasar konsep batas atas terkecil (b.a.t) dan batas bawah terbesar (b.b.t), didefinisikan LATTICE sebagai berikut:

BY : SRI ESTI

MATEMATIKA DISKRIT

Contoh Soal 1. Tentukan apakah Poset yang dinyatakan dengan diagram di bawah ini merupakan Lattice !

Jawab: (a). Lattice, sebab setiap dua Titik mempunyai b.a.t dan b.b.t. (b). Bukan Lattice, sebab b.a.t dari a & b tidak ada. (c). Bukan Lattice, sebab b.a.t dari c & d tidak ada, ( b ≤ a ). (d). Lattice, sebab setiap pasang titik mempunya b.a.t & b.b.t. 2. Mana dari poset-poset pada gambar berikut yang merupakan lattice? I d

c

a

I e b

o (a)

c a

I d

b o

c

d

d

b o

(b)

(c)

Jawab: (a) Lattice, sebab setiap dua Titik mempunyai b.a.t dan b.b.t. (b) Lattice, sebab setiap dua Titik mempunyai b.a.t dan b.b.t. (c) Bukan, karena {d, b} mempunyai tiga batas atas c, d, dan I, dan tidak ada salah satu dari mereka mendahului dua yang lain; jadi sup{d, b} tidak ada

BY : SRI ESTI

MATEMATIKA DISKRIT

Latihan soal: 1. Mana dari poset-poset pada gambar berikut yang merupakan lattice? 2

1

7

3

5

4

2

5 6

3

2 4

3

4

1

1 (a0

(b)

(c)

2. Mana dari poset-poset pada gambar berikut yang merupakan lattice? 6 4

5

2

3

6

6

5

5

2

4

1

1

(a)

(b)

3

4

1

2 (c)

BY : SRI ESTI