POSET & LATTICE

Himpunan terurut parsial yang dikenal dengan istilah poset, merupakan konsep yang sangat penting yang mendasari lattice.

Sebelum  sampai  pada  pendefinisian  poset,  anda  diingatkan  kembali  pada definisi relasi biner serta sifat-sifatnya.

Definisi 3.1.1

Misalkan A dan B adalah himpunan-himpunan  tak kosong. Hasilkali  Cartes dari A dan B dinotasikan dengan A x B adalah himpunan A x B = {(x,y) ; x

∈A, y ∈B}

Contoh 1:

Diketahui himpunan A = {1,2,3} dan B = {a,b}. Hasil kali Cartes dari A dan B

adalah

A x B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}, dan hasil kali Cartes dari B dan A

adalah B x A = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}

Definisi 3.1.2

Misalkan A dan B adalah himpunan-himpunan tak kosong. Setiap himpunan bagian tak kosong dari  A x B disebut relasi biner (atau secara singkat disebut relasi) dari A ke B.

Jika R adalah relasi dari A ke B dan (x,y) ∈ R, maka pernyataan “x berelasi dengan y” dinotasikan dengan x R y.

Dalam matematika, relasi seringkali dinotasikan dengan symbol khusus yang bukan merupakan huruf dari abjad latin. Contoh yang paling umum adalah relasi “lebih besar dari” untuk himpunan bilangan real. Relasi ini dinotasikan oleh yang dapat dipandang sebagai nama suatu himpunan dengan elemen- elemennya berupa pasangan terurut. Jika   a dan b adalah dua bilangan real

sedemikian  hingga a > b, maka dikatakan bahwa (a,b) ∈ >. Lebih tepatnya

relasi > adalah

> = {(x,y) ; x,y adalah bilangan real dan x > y}

Sifat-sifat relasi biner

Ada beberapa sifat relasi biner yang penting untuk diketahui yakni sifat refleksif, simetris, transitif, dan antisimetris.

Definisi 3.1.3

Misalkan R adalah relasi pada A (relasi dari A ke A). R dikatakan refleksif jika untuk setiap x∈ A, maka (x,x) ∈ R.

Contoh 2:

Diketahui A = {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5} Suatu relasi R didefinisikan sebagai berikut :

R = {(x,y); x,y ∈A, xy > 0}

Periksa apakah R refleksif atau tidak. Penyelesaian

Ambil x = 0 (0∈ A). Karena 0.0 = 0, maka (0,0)∉ R.

Dengan demikian ada x ∈ A sedemikian hingga (x,x)∉ R. Ini berarti bahwa R tidak refleksif.

Soal latihan

Diketahui B = {1,2,3,4,5}. Relasi R didfinisikan sebagai berikut

R = {(x,y); x,y ∈B, xy > 0}

Periksa apakah R refleksif atau tidak.

Definisi 3.1.4

Misalkan R adalah relasi pada A. R dikatakan simetris jika untuk setiap x, y ∈

A dengan xRy, maka yRx. Contoh 3:

Diketahui A = {–2, –1, 0, 1, 2} Relasi R didefinisikan sebagai berikut

R = {(x,y); x,y ∈A, xy > 0}

Periksa apakah R simetris atau tidak. Penyelesaian

A x A =  {(–2,–2), (–2,–1), (–2,0), (–2,1), (–2, 2), (–1,–2), (–1,–1), (–1,0), (–1,1), (–1,

2), (0, –2), (0, –1), (0, 0), (0,1), (0,2), (1,–2), (1, –1), (1,0), (1,1), (1,2), (2,2), (2, –1), (2,0), (2,1), (2,2)}

Karena R = {(x,y); x,y ∈A, xy > 0}, maka kita nyatakan sebagai berikut :

R = {(–2,–2), (–2,–1), (–1,–2), (–1,–1), (1,1), (1,2), (2,1), (2,2) }

Dari sini jelas terlihat bahwa untuk setiap (x,y) ∈R berlaku (y,x) ∈R. Dengan kata lain  untuk setiap x,y ∈A dengan xRy, berlaku yRx. Jadi R adalah sebuah

relasi yang simetris.

Latihan soal

Diketahui A = {–2, –1, 0, 1, 2} Relasi R didefinisikan sebagai berikut

R = {(x,y); x,y ∈A, x ≤ y}

Periksa apakah R simetris atau tidak.

Definisi 3.1.5.

Misalkan R adalah relasi pada A. R dikatakan transitif  jika untuk setiap x, y , z∈ A dengan xRy dan yRz, maka xRz.

Contoh 4:

Diketahui A = {–1, 0, 1} Relasi R didefinisikan sebagai berikut

R = {(x,y); x,y ∈A, x ≤ y}

Periksa apakah R transitif atau tidak. Penyelesaian

A x A =  {(–1,–1), (–1,0), (–1,1), (0, –1), (0, 0), (0,1), (1, –1), (1,0), (1,1)}

Karena R = {(x,y); x,y ∈A, x ≤ y}dan R merupakan himpunan bagian dari A x

A, maka R dapat dinyatakan sebagai berikut

R = {(–1,–1), (–1,0), (–1,1),  (0, 0), (0,1), (1, –1)}

Dari sini jelas terlihat bahwa untuk setiap x, y , z ∈ A dengan xRy dan yRz, maka xRz. Dengan demikian R adalah relasi yang transitif.

Latihan soal

Diketahui A = {a,b,c} Relasi R didefinisikan sebagai berikut

R = {(a,b), (c,b), (b,a), (a,c)}. Periksa apakah R transitif atau tidak.

Definisi 3.1.6.

Misalkan R adalah relasi pada A. R dikatakan antisimetris  jika untuk setiap x, y ∈ A dengan xRy dan yRx, maka x = y.

Contoh 5:

Diketahui A = {–2, –1, 0, 1, 2} Relasi R didefinisikan sebagai berikut

R = {(x,y); x,y ∈A, y =  x }

Periksa apakah R antisimetris atau tidak. Penyelesaian

A x A =   {(–2,–2), (–2,–1), (–2,0), (–2,1), (–2, 2), (–1,–2), (–1,–1), (–1,0), (–1,1), (–1, 2), (0, –2), (0, –1), (0, 0), (0,1), (0,2), (1,–2), (1, –1), (1,0), (1,1), (1,2), (2,2), (2, –1), (2,0), (2,1), (2,2)}

Karena R = {(x,y); x,y ∈A, y =  x }, dan R merupakan himpunan bagian dari A

x A maka R dapat kita nyatakan sebagai berikut : R = {(–2,2), (–1,1), (0,0), (1,1), (2,2) }

Dari sini jelas terlihat  bahwa  untuk  setiap  x, y ∈ A dengan  xRy dan yRx,

berlaku x = y. Dengan demikian R adalah relasi antisimetris.

Latihan soal

Diketahui A = {a,b,c} Relasi R didefinisikan sebagai berikut

R = {(a,b), (b,a), (a,c), (c,a), (b,c), (c,a)} Periksa apakah R antisimetris atau tidak.

Definisi 3.1.7.

Himpunan P dengan relasi R pada P dinamakan poset jika R memenuhi sifat refleksif, antisimetris, dan transitif.

Contoh 6:

Misalkan  Z adalah  himpunan  semua  bilangan  bulat  positif.  Relasi  ≤ (lebih kecil  atau  sama  dengan)   adalah  sebuah  relasi  pada  Z.  Periksa  apakah himpunan  Z dengan relasi ≤ atau dinotasikan  (Z, ≤) merupakan  poset atau bukan.

Penyelesaian

Ada tiga sifat yang harus diperiksa yaitu refleksif, antisimetris, dan transitif. a.   Karena untuk setiap x ∈ Z berlaku x ≤ x, maka sifat refleksif dipenuhi.

b.  Karena untuk setiap x,y ∈ Z dengan  x ≤ y dan y ≤ x, berarti bahwa x =

y, maka sifat antisimetris dipenuhi.

c.   Karena untuk setiap a,b,c ∈ Z dengan   a ≤ b dan b ≤ c, berlaku a ≤ c maka sifat transitif dipenuhi.

Karena tiga sifat terpenuhi, maka (Z, ≤) merupakan poset.

Latihan Soal

1.   Misalkan  Z  adalah  himpunan  semua  bilangan  bulat  positif.  Periksa apakah relasi  < pada Z merupakan poset atau bukan.

2.   Periksa  apakah  (Z+,  │)  merupakan   poset  atau  bukan.  Z+    adalah himpunan  bilangan  bulat  positif.  Relasi    x│y   adalah  relasi  y habis

dibagi x, untuk setiap x, y ∈ Z+.