7 0 148 KB
Tugas Matematika Diskrit Oleh: Kelompok 5 1. Amalia Fitri (RSA1C213006) 2. Novrike Mulyawati (RSA1C213016) 3. Reza Putra Wardana (RSA1C213028) 4. Yolanda Fitria (RSA1C213003) Program Studi: Pendidikan Matematika PGMIPA-U
Homomorfisma Letis dan Letis Khusus
Homomorfisma Letis Definisi : Misalkan
( L, ,1 1 ,)1
dan
( M , 2 ,2 ,) 2
→
adalah letis. Fungsi f: L
M
(a, b) L
dinamakan homomorfisma letis jika
f (a 1 b) f (a ) 2 f (b)
berlaku:
dan
f (a 1 b) f (a ) 2 f (b) Khususnya jika f 1-1 dan pada, maka f dikatakan isomorfisma letis, sedangkan L dan M disebut isomorfik. Teorema 6 : Misalkan f : L
→
M adalah homomorfisma letis. Jika
a 1 b, maka f ( a ) 2 f (b)
Jika f homomorfisma letis, maka f “mengawetkan urutan”. Dapat terjadi suatu fungsi f : L → M yang 1-1 pada dan mengawetkan urutan, tapi f -1 tidak.
Contoh
( L, )
Dik: Misalkan
letis dengan L = {1, 2, 3, 4, 6,12} didefinisikan:
a 1 b
b habis dibagi a dan
a 2 b a b
Dit: Periksa apakah
6
12
→
f:L
2
f mengawetkan urutan atau tidak −1 f mengawetkan urutan atau tidak
3
L dengan f(x) = x ,
x
∈
1
L homomofisma letis atau bukan
Penyelesaian:
3
L1
1
Diagram Hasse a 1 b b habis dibagi a
4
Diagram Hasse a 2 b a b
L2
12
2
6
1 4 3 2 1
(1, 2) L
Ambil
akan diperiksa apakah berlaku f (a 1 b) f (a ) 2 f (b) f ( a 1 b ) f ( a ) 2 f (b ) dan f (a 1 b) f (a ) 2 f (b)
L1 Lihat diagram
f (1 1 2)
L2
f (1)
1
Lihat diagram
f (1) 2 f (2)
1 *2 2 1
f (a 1 b) f (a) 2 f (b)
f ( x) x maka f (1) 1
,
L1 Lihat diagram
L2 Lihat diagram
f (1 1 2)
f (1) 2 f (2)
f ( 4)
12 2
4
(a,b) L
Karena 2
terdapat
3
f ( a 1 b ) f ( a ) 2 f (b )
maka L bukan homomorfisma letis.
a 1 b f ( a ) 2 f (b ) (1, 2) L
Ambil 1 1 2 f (1) 2 f (2)
1 1 2 1 2 2 (1, 3) L
Ambil
Ambil
( 2, 4) L 1 1 3 f (1) 2 f (3)
2 1 4 f ( 2) 2 f ( 4) 1 1 3 1 2 3
2 1 4 2 2 4 a, b L
Dengan cara yang sama dapat dibuktikan f mengawetkan urutan. 3
( 2,1) L Ambil a 1 b f ( a ) 2 f (b )
2 1 1 f (2) 2 f (1)
2 1 1 2 2 1
f -1 tidak mengawetkan urutan.
Letis Khusus Definisi :
berlaku
a 1 b f ( a ) 2 f (b )
Misalkan L letis. L disebut terbatas dibawah jika ada elemen L yang dilambangkan 0 sehingga
0 ≤ a,
∀ a ∈ L . Sebaliknya L disebut terbatas diatas jika terdapat elemen di L
yang dilambangkan l sehingga a ≤ 1, ∀ a ∈ L . L dikatakan terbatas jika L terbatas dibawah dan L terbatas diatas. Catatan penting berkenaan dengan 0 dan 1 dalam sebuah letis terbatas, yaitu: a b
Sebagai akibat langsung dari sifat antisimetris, elemen 0 dan 1 (jika ada) adalah tunggal. ∀ a ∈ L berlaku: 0 * a = a l*a=a 0⨁a=0
c
l⨁a=1
Definisi : Misalkan L adalah letis terbatas dan a
L, b
L disebut komplemen dari a jika a * b
b a0
= 0 dan d
a⨁b=1
Pernyataan “b komplemen dari a” dilambangkan dengan b = a'
e 1
Jika setiap elemen dari L mempunyai komplemen, maka L disebut berkomplemen. Contoh Dik: Diagram letis L adalah sebagai berikut:
Dit: Periksalah a b
Apakah letis L terbatas Apakah letis L adalah letis yang mempunyai komplemen
Penyelesaian: a
Akan diperiksa apakah letis L terbatas, berarti letis L terbatas dibawah dan diatas. Syarat:
Letis L terbatas dibawah: ∀ a ∈ L berlaku 0 ≤ a b, c, d dimisalkan a
a *b a 0
(0 b )
a *c a 0
(0 c )
a * d a 0 (0 d ) Karena ∀ a ∈ L berlaku 0 ≤ a maka L terbatas dibawah.
Letis L terbatas diatas: ∀ a ∈ L berlaku a ≤ 1 b, c, d dimisalkan a b e e 1 (b 1)
c e e 1 (c 1)
d e e 1 (d 1) Karena ∀ a ∈ L berlaku a ≤ 1 maka L terbatas diatas.
b
L adalah letis terbatas.
Akan diperiksa bahwa L adalah letis yang mempunyai komplemen. Syarat : a * b = 0 dan
a⨁b=1
a *b a 0
a b e 1
a *c a 0
a c e 1
a*d a 0
ad e 1
b*c a 0
bc e 1
b*d a 0
b d e 1
c*d a 0
cd e 1
b*e a 0
be e 1
c *e a 0
ce e 1
d *e a 0
d e e 1
a, b L
Karena
terdapat
a *b 0
dan
a b 1
maka L adalah letis yang berkomplemen.
Letis Distributif
c
Definisi : Letis L disebut distributif jika
a, b, c
∈L
berlaku:
b a0
i d a * (b ⨁ c) = (a * b) ⨁ (a * c) dan ii a ⨁ (b * c) = (a ⨁ b) * (a ⨁ c) e 1
Contoh Dik: Letis L = {a,b,c,d,e} dengan diagram hassenya sebagai berikut:
Dit: Teliti apakah L distributif atau tidak? Penyelesaian: Ambil a, b, c ∈ L akan diperiksa apakah berlaku i a * (b ⨁ c) = (a * b) ⨁ (a * c) dan ii a ⨁ (b * c) = (a ⨁ b) * (a ⨁ c) Bukti:
z
i
a * (b ⨁ c) = (a * b) ⨁ (a * c) a*e = a ⨁ a tidak ada = a
Karena a * (b ⨁ c) ≠ (a * b) ⨁ (a * c), maka L tidak distributif.
y
x
Contoh Dik: Misalkan L adalah letis dengan diagram hasse berikut:
Dit: Periksa apakah L distributif atau tidak? Penyelesaian: x, y , z L
Ambil
akan diperiksa apakah berlaku:
i a * (b ⨁ c) = (a * b) ⨁ (a * c) dan ii a ⨁ (b * c) = (a ⨁ b) * (a ⨁ c) Bukti: x * ( y z) ( x * y) ( x * z )
i x*z
x x
x
x
x * ( y z) ( x * y) ( x * z)
Maka x ( y * z) ( x y) * ( x z)
ii
x y y
y*z
y
x ( y * z) ( x y) * ( x z)
Maka x, y , z L x * ( y z) ( x * y) ( x * z) x ( y * z ) ( x y) * ( x z) Karena berlaku dan L adalah letis distributif.
Teorema 7 Setiap rantai adalah letis distributif. Teorema 8 Hasil kali cartes dua letis distributif adalah letis distributif. Teorema 9 a, b, c L
Misalkan L adalah letis distributif maka
berlaku:
( a * b a * c ) (a b a c) b c
.