grup permutasi dan grup siklis -...

43
Grup Permutasi dan Grup Siklis Winita Sulandari

Upload: buinhi

Post on 07-Mar-2019

315 views

Category:

Documents


8 download

TRANSCRIPT

Grup Permutasi dan Grup Siklis

Winita Sulandari

Grup Permutasi

• Suatu Permutasi dari suatu himpunan berhingga S yang tidak kosong, dinyatakan sebagai suatu pemetaan bijektif dari himpunan S pada dirinya sendiri.

3

Definisi Fungsi

Suatu fungsi f dari A ke B adalah suatu

aturan yang memetakan setiap elemen

A ke tepat satu elemen B, ditulis:

f : A → B

Jika f memetakan a ∈ A ke b ∈ B, ditulis

f(a) = b A Bf

a b)a(f

4

Fungsi satu-satu dan onto

1. Fungsi f : A → B dikatakan satu-satu, jhj, jika

f(a)=f(b), maka a=b.

2. Fungsi f : A → B dikatakan onto, jhj, untuk setiap

b∈B, ada a∈A sedemikian sehingga b = f(a)

3

2

1

4

3

2

1

4

3

2

1

3

2

1

A AB Bf f

11 onto

5

Fungsi Komposisi

Jika f dan g adalah fungsi-fungsi dengan f : A → B

dan g : B → C, maka ada fungsi dari A ke C.

Fungsi dari A ke C adalah fungsi komposisi yang

terdiri dari f diikuti g, ditulis: (gf)(a) = g(f(a)) = c,

dengan a ∈ A dan c ∈ C.

gambar: A B Cf g

)a)(fg(

a )a(f ))a(f(gc

6

Definisi Permutasi

Suatu permutasi pada A adalah fungsi

dari A ke A yang sekaligus satu-satu

dan onto, ditulis

AA:f11

onto

7

Contoh 1

Diberikan A = { 1, 2, 3, 4, 5 }.

f adalah permutasi yang digambarkan sebagai:

atau

f ditulis dalam notasi baku sebagai berikut :

15

34

53

22

41

13524

54321f

1 2 3 4 5

1 2 3 4 5

A Af

8

Dari: dapat diartikan bahwa:

f(1) = 4

f(2) = 2

f(3) = 5

f(4) = 3

f(5) = 1

13524

54321f

9

Komposisi Permutasi (Teorema)

Jika f dan g permutasi-permutasi pada

A, maka fg juga permutasi pada A.

( ) AA:gf11

onto

10

Contoh 2

Misalkan dan

Maka f g =

sehingga (fg)(1) = f(g(1)) = f(3) = 5

(fg)(5) = f(g(5)) = f(1) = 4, dsb.

Jadi f g =

13524

54321f

12453

54321g

13524

54321

12453

54321

42315

54321

11

GRUP SIMETRIK

Diberikan A adalah himpunan berhingga

{1,2,3, …,n}.

Grup semua permutasi untuk A disebut

grup simetrik pada n huruf, dan

ditunjukkan dengan Sn.

Perhatikan bahwa Sn mempunyai n! =

n(n-1)(n-2)…(3)(2)(1).

Teorema 2.4.2

Karakteristik atau orde dari grup Sn adalah n!.

13

Contoh:

Diberikan himpunan A = {1,2,3}.

Contoh grup simetri A(S) = S3 , order A(S) 3! = 6 elemen.

Didaftar permutasi-permutasi untuk A sbb:

312321

,213321

123321

,132321

231321

,321321

32

21

1o

14

Dapat ditunjukkan

α0 α1 α2 β1 β2 β3

α0 α0 α1 α2 β1 β2 β3

α1 α1 α2 α0 β3 β1 β2

α2 α2 α0 α1 β2 β3 β1

β1 β1 β2 β3 α0 α1 α2

β2 β2 β3 β1 α2 α0 α1

β3 β3 β1 β2 α1 α2 α0

15

Perhatikan bahwa grup simetrik tersebut di atas

tidaklah komutatif (contoh grup berhingga yang

tidak komutatif)

Jadi S3 mempunyai tingkat (order) minimal

untuk sembarang grup yang tidak komutatif.

Soal latihan

1.

Hitunglah komposisi sebagai berikut:

a) f g b) g f c) f-1

d) g-1 e) f –1 g-1 f) (f g)-1

1 2 3 4 1 2 3 4

2 1 4 3 3 1 4 2f dan g

2.

Hitung

a) f g b) g-1 f-1 c) (g f )-1

d) f g2 e) f g2

1 2 3 4 1 2 3 4

3 4 1 2 4 3 1 2f dan g

Perkalian Langsung

• Apabila terdapat dua buah grup G1 dan G2 maka dapat dibentuk grup baru dari kedua grup tersebut

• produk Cartesius dari dua himpunan A dan B yang dinyatakan dengan

AxB = {(ai, bi) / ai A, bi B}.

Teorema 2.5.2

Bila G dan H dua buah grup maka produk Cartesius G x H dengan operasi :

( gi , hi ) (gj , hj ) = (gi gj , hi hj )

untuk setiap (gi , hi ) dan (gj , hj ) G x H

maka G x H merupakan grup dan disebut perkalian langsung (direct product) dari G dan H.

• Perhatikan operasi dalam grup

• Contoh: 1

Dalam perkalian langsung Z x Z karena Z merupakan grup terhadap operasi + maka operasi dalam Z x Z berlaku sama. Misalkan (a,b) dan (c,d) unsur dalam Z x Z maka (a,b)(c,d) = (a + c,b + d) Z x Z.

Contoh 2:

Misal grup ( Z3 , + ) dan grup permutasi (S2 ,)

Z3 x S2 = { (1,i), (2,i), (3,i), (1,(1 2)),(2,(1 2)),(3,(1 2))}

sedang operasi unsur-unsurnya sebagai berikut:

Misal,

( 2, i) ( (3,(1 2)) = ( 2 + 3, i (1 2)) = ( 2, (1 2 ))

• Apabila G dan H dua grup berhingga , maka orde dari G x H yaitu G x H = G.H

Latihan soal

1. Bila grup G mempunyai unsur identitas i dan grup H mempunyai unsur identitas e buktikan {( gi, e) / gi G } dan { (i, hi ) hi H } merupakan subgrup dari G x H

2. Tuliskan semua unsur dari grup S3 x Z2 dan tentukan subgrup yang mungkin dalam

S3 x Z2.

Latihan soal

3. Hitunglah perkalian unsur-unsur sebagai berikut

a. ((123),2)((23),3) dalam S3 x Z5

b. (2,3)(-1,5) dalam Q x Q* dimana Q* adalah himpunan bilangan rasional tanpa unsur nol.

25

GRUP SIKLIS

Himpunan dengan anggota-anggota berbentuk

membentuk suatu grup siklik, a sebagai elemen pembangun atau penghasil atau “generator”, biasa ditulis G = <a>.

njijika,aaa

njijika,aaadan,eaa

dengan1n,,3,2,1,0i,a

njiji

jijin0

i

GRUP SIKLIS

Definisi 2.6.1

Suatu grup G dan suatu unsur g G, jika grup G dapat dinyatakan sebagai

G = { gn / n Z },

maka g dikatakan pembangun dari grup G dan grup G disebut grup siklis, biasanya dinotasikan G = <g>

Perlu diingat...

definisi grup siklis G = { gn / n Z } digunakan operasi perkalian, tetapi apabila grup G dengan operasi penjumlahan, maka definisi grup siklis menjadi

G = { n g / n Z } = <g >

28

Contoh:

1. Misalnya untuk n = 6, grup itu ialah

G = { e , a , a2 , a3 , a4 , a5 }

Grup semacam ini biasa dinyatakan dengan C6, yaitu

grup siklis berorder 6, ( |G| = 6 )

Grup siklis berorde n dinyatakan dengan Cn.

2. Himpunan bilangan-bilangan bulat modulo n dengan

operasi penjumlahan modulo n merupakan suatu

grup siklis.

29

‣ Misalkan G = Z6 = { 0 , 1 , 2 , 3 , 4 , 5 },

adalah grup siklik dengan elemen pembangunnya 1,

G = <1>, sebab:

10 = 0, 13 = 3,

11 = 1, 14 = 4,

12 = 2, 15 = 5.

‣ dapat juga dibangun oleh 5, G = <5>,

sebab: 50 = 0,

51 = 5,

52 = 5 + 5 = 4,

53 = 5 + 5 + 5 = 3,

54 = 5 + 5 + 5 + 5 = 2,

55 = 5 + 5 + 5 +5 + 5 = 1.

‣ Apakah masih ada unsur pembangun lainnya?

3. (Z,+) adalah grup siklis dengan unsur pembangun 1 dan -1.

4. 3Z merupakan subgrup siklis yang dibangun oleh 3, sehingga 3Z = <3>

31

5. Himpunan operasi simetri dari bangun kitiran ini

terdiri dari rotasi dengan titik pusat O, dengan

sudut rotasi 90o, 180o, 270o, dan 360o

Jika (O,90o)=S, maka

(O,180o)=S2, (O,270o)=S3,

dan (O,360o)=I

O

Jadi G = { I , S , S2 , S3 } merupakan grup siklis dengan pembangun S, G = <S>, dan order G sama dengan 4

Tentukan order dan invers dari S, S2, dan S3.

32

6. Perhatikan segi-5 beraturan dengan pusat O dan

sudut-sudut rotasi 72o, 144o, 216o, 288o, dan 360o.

Jika (O,72o)=S, maka

(O,144o)=S2, (O,216o)=S3, (O,288o)=S4, dan (O,360o)=I

Sehingga { I , S , S2 , S3 , S4 } merupakan suatu grup siklis dengan order 5.

Tampak pula, bahwa |S| = 5, |S2| = 5, |S3| = 5, |S4| = 5

Disamping S, maka S2, S3, dan S4 dapat menjadi pembangun.

O o72

1

2

3

4

5

Orde dari grup siklis

Bila G grup siklis dibangun oleh unsur g, maka orde G adalah sama dengan orde dari unsur pembangunnya yaitu ( g )

Lemma 2.6.2

Bila G suatu grup , g G maka

H = { g n / n Z }

merupakan subgrup terkecil dalam G yang dibangun oleh unsur g

Lemma 2.6.3

Setiap grup siklis G = <g> adalah grup abel

Lemma 2.6.5

Subgrup dari grup siklis adalah siklis

Lemma 2.6.7

Dua grup siklis dengan orde yang sama akan berkorespondensi 1 - 1

Contoh

• Z =<1> = <-1> dan 3Z subgrupdari Z dengan 3Z = <3> = <-3>.

jika didefinisikan

f: Z 3Z

n Z, berlaku f(n) = 3n 3Z,

maka

• f bersifat pada, karena bila diambil sebarang x 3Z haruslah x = 3m, untuk suatu m Z. Ini berarti ada m Z sedemikian hingga f(m) = x = 3m atau f pemetaan pada.

• f juga pemetaan 1-1, karena bila diambil unsur f(n) = f(m) maka diperoleh 3n = 3m atau n=m.

• Mengingat f pemetaan pada dan 1-1, maka f korespondensi 1-1.

Lemma 2.6.8

Bila G suatu grup sebarang, g G dan misalkan n , m Z sehingga gn = 1 dan juga

gm = 1, maka gd = 1 di mana d = (m, n). Khususnya bila gs = 1 untuk suatu s Z, maka orde dari g membagi s. Dalam hal ini d = (m,n) dimaksudkan d merupakan pembagi persekutuan terbesar dari m dan n

Lemma 2.6.9

Misalkan G = < g > dengan n unsur, dan misalkan h = gs, s Z adalah unsur dalam G, maka h akan membangun subgrup siklis H dalam G yang berorde n/d, di mana d membagi persekutuan terbesar dari n dan s atau d = (n , s ).

Contoh

• Grup (Z12,+) adalah grup siklis dan Z12=<1>=<5> =<7>=<11>

• misal diambil 3 Z12, karena 3 = (3,12) maka H=<3>={0,3,6,9} subgrup dari Z12 dengan orde 12/3 = 4

• misal diambil 4 Z12, karena 4 = (4,12) maka H=<4>={0,4,8} subgrup dari Z12 dengan orde 12/4 = 3

• Bagaimana dengan 5? H=<5>= Z12

FPB dari 3 dan 12

Menentukan unsur pembangun

Apabila g membangun grup siklis berhingga G berorde n, maka pembangun lainnya dari G adalah unsur-unsur berbentuk gs, di mana s relatif prim dengan n, atau (s,n) = 1.

Contoh

• Tentukan semua subgrup yg mungkin dari Z18

Diperoleh:

• Unsur pembangun Z18 adalah 1,5,7,11

• Subgrup dengan orde terbesar dibangun oleh unsur 2, dengan orde 18/2 =9, sehingga <2> = {0,2,4,6,8,10,12,14,16}

• Selanjutnya mencari semua subgrup dalam <2>

• Menentukan unsur pembangun dari <2>, berupa 2h dg h relatif prim dg orde <2>, yaitu 9. diperoleh h = 1,2,4,5,7,8 sehingga <2>=<4>=<10>=<14>=<16>

• Unsur yg tdk membangun <2> adalah 6 dan 12, sehingga

<6> = {0,6,12} =<12> subgrup dr <2>