LATTICE

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 ab dan kita sebut join antara a dan b, sedangkan greatest lower bound (GLB) ({a,b}) dengan ab 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= L1L2 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) = (a11 a2, b1b2)

            (a1,b1)  (a2,b2) = (a11 a2, b1b2)

dengan demikian L adalah lattices.

Contoh 1

Pada himpunan S yang beranggotakan a dan b

-          ab = 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(ab) = f(a) f(b) dan f(ab)= 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 0L, maka

a a’= I          a a’’ = I

a a’= 0         a a’’ = 0

dengan aturan distribusi didapat

            a’ = a’ 0 = a’ (aa’’)

    = (a a’) (a’ a’’)

                = I  (a’ a’’)

                = a’  a’’

juga

            a’’ = a’’ 0 = a’’ (aa’)

     = (a a’’) (a’ a’’)

                 = I  (a’ a’’)

                 = a’  a’’

sehingga dapat dikatakan bahwa a’ = a’’.