aplikasi teori grup dalam mengklasifikasikan mini … fileaplikasi teori grup dala}i...

$: APLIKASI TEORI GRUP DALAM MENGKLASIFIKASIKAN MINI … fileAPLIKASI TEORI GRUP DALA}I .\'IENGKLASTF-IKASIKAN N{INI-SUDOKU bcscrta pcrangkat yang diperlukan (bila ada). Dcngan dcrr-rikian$
i

APLIKASI TEORI GRUP DALAM MENGKLASIFIKASIKAN

MINI-SUDOKU

MAKALAH

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Sains

Program Studi Matematika

Oleh:

Andrea Mira Sorta Hutadjulu

133114028

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2017

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ii

APPLICATION OF GROUP THEORY IN CLASSIFYING MINI-SUDOKU

PAPER

Presented as Partial Fulfillment of the

Requirements to Obtain the Degree of Sarjana Sains

Mathematics Study Program

Written by:

Andrea Mira Sorta Hutadjulu

Student ID: 133114028

MATHEMATICS STUDY PROGRAMDEPARTMENT OF MATHEMATICS

FACULTY OF SCIENCE AND TECHNOLOGY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2017


v

HALAMAN PERSEMBAHAN

“Akan hal ini aku yakin sepenuhnya yaitu Ia, yang memulai pekerjaan

yang baik di antara kamu, akan meneruskannya sampai pada akhirnya pada hari Kristus Yesus”

“Do not be afraid I’m with you, I have called you each by name”

Karya ini dipersembahkan untuk

Tuhan Yesus Kristus dan Bunda Maria yang

senantiasa memberkati dan menyertaiku,

kedua orang tua tercinta, Jesse Hutadjulu dan Regina Manurung,

adik tersayang, Sondang Hutadjulu,

dan saudara/i keluarga besar dari kedua orang tua terkasih.


vi

ABSTRAK

Makalah ini membahas Mini-Sudoku berukuran yang memiliki blok

berukuran . Aturan Satu dalam mini-Sudoku berbunyi: Setiap baris, setiap

kolom, dan setiap blok berisi tepat satu angka 1 sampai dengan 4. Makalah ini

membahas pengelompokkan mini-Sudoku yang benar-benar berbeda.Dua mini-

Sudoku dikatakan sama atau ekivalen jika mini-Sudoku yang satu dapat

dihasilkan dari mini-Sudoku yang lain dengan menerapkan simetri-simetri pada

mini-Sudoku tersebut. Menukarkan dua baris atau kolom pada mini-Sudoku,

merefleksikanmini-Sudoku, dan melakukan pelabelan-ulang pada mini-Sudoku

adalah cara-cara untuk menghasilkan dua mini-Sudoku yang ekivalen.Dengan

menggunakan Teori Grup dapat ditentukan pengelompokkan mini-Sudoku yang

benar-benar berbeda, sehingga mini-Sudoku dapat dikelompokkan dalam 2 kelas

ekivalensi yang berbeda.


vii

ABSTRACT

This paper discusses grid mini-Sudoku that contains subgrids

(blocks). The Rule of One of mini-Sudoku says: each row, each column and each

block must contain every digit from 1 to 4 exactly once. This paper discusses

classification of mini-Sudokus that are essentially different. Two mini-Sudokus

are essentially the same or equivalent if one mini-Sudoku can be obtained from

the other by applying mini-Sudokusymmetries. Switching two rows or columns in

mini-Sudoku, reflecting mini-Sudoku,and relabeling mini-Sudoku are the ways to

obtain two equivalent mini-Sudokus. By using Group Theory, it can be defined

the classification of mini-Sudokus that are essentially different, such that mini-

Sudokus can be classified into 2 equivalence classes.


--!

LEN{BAR P[,RNYATAAtr"

PL BLIK,\SI KAR\'A II-i\IIAH U\TUK KEPE\]-I\CAN AKADENIIS

Yang bcrtancla tan_ean di bau'ah ini. sa1,a nrahasisua Ultivcrsitas Sanata Dharma:

N:rnra : Anclrca Nlira Sorta I IutacljLrlLr

Nll\{ :133114028

Dcrrii pcngembangan ilmu pcngctahuan, saya meubcrikan kepada Pcrpustakaan

Univcrsitas Sanata Dharma karya ilmiah saya yang bcriLrdr-rl:

APLIKASI TEORI GRUP DALA}I .\'IENGKLASTF-IKASIKAN

N{INI-SUDOKU

bcscrta pcrangkat yang diperlukan (bila ada). Dcngan dcrr-rikian saya membcrikan

kcpada Pcrpustakaan Llniversitas Sanata Dhanra untuk urcrtvimpan. mcngalihkan

kc dalanr bcntr-rk mcdia larn" nren-gclolanva dalanr bcntuk pangkalan data.

mcndistribusikannya sccara tcrbatas. dan nrempublikasikan di intcrnct atau media

lainnya untuk kcpentingan akadcmis tanpa pcrlLr minta izin clari saya ataupun

n-ientberikan ro1-alty kepada saya sclanra tctap mencantumkan nama saya scbagai

penulis.

Demikian pernyataan ini saya buat dengan scbcnar-bcnantl-a.

Dibuat di Yogyakarta

Pada tan-ugal 2.1 Januari 2018

Yang mcnvatakan

Andrca Mira Sorta Hutad;ulu

viii


PERNYATAAN KEASLIAN KARYA

Saya menyatakandengan sesungguhnya bahwa makalah yang saya tulis ini tidak

memuat karyaorang lain, kecuali yang telah disebutkan dalam kutipan dan daftar

pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, 2l lammi 201 8

Penulis

MAndrea Mira Sorta Hutadjulu

IX


x

KATA PENGANTAR

Puji dan syukur kepada Tuhan Yang Maha Esa, atas berkat dan rahmat yang

diberikan sehingga penulis dapat menyelesaikan makalah ini.

Makalah ini disusun sebagai salah satu syarat untuk memperoleh gelar Sarjana

Sains dari Program Studi Matematika, Fakultas Sains dan Teknologi, Universitas

Sanata Dharma.Banyak tantangan dalam penulisan makalah ini.Namun demikian,

dengan penyertaan Tuhan Yesus dan dukungan dari berbagai pihak, akhirnya

makalah ini dapat diselesaikan. Untuk itu, penulis ingin mengucapkan terima

kasih kepada:

1. Bapak Sudi Mungkasi, S.Si., M.Math.Sc., Ph.D. selaku Dekan Fakultas

Sains dan Teknologi.

2. Bapak YG. Hartono, S.Si., M.Sc., Ph.D. selaku Ketua Program Studi

Matematika.

3. Romo Prof. Dr. Frans Susilo, SJ., selaku dosen pembimbing yang dengan

sabar dan penuh semangat dalam membimbing penulisan makalah ini.

4. Ibu M. V. Any Herawati, S.Si., M.Si. selakuDosen Pembimbing

Akademik.

5. Bapak Ir. Ig. Aris Dwiatmoko, M.Sc., Bapak Dr. rer. nat. Herry P.

Suryawan, S.Si., M.Si., dan Ibu Lusia Krismiyati Budiasih, S.Si., M.Si.

selaku dosen Program Studi Matematika yang telah memberikan ilmu-

ilmu yang sangat berguna dalam masa perkuliahan dan dalam penulisan

makalah.

6. Kedua orang tua dan adik yang selalu mendoakan dan mendukung penulis

dalam menyusun makalah.

7. Teman-teman Program Studi Matematika, Inge, Melisa, Ambar, Yui,

Ditha, Yuni, Tia, Bintang, Sari, Ezra, Sisca, Yola, Agung, Andre, Dion,

Lya, Laras, Natali, Rey, Wahyu, Indra, dan Kristo yang telah memotivasi,

menghibur, dan menjadi sahabat yang luar biasa dalam mengisi hari-hari

perkuliahan. Terimakasih banyak atas kekompakkan dan kebersamaannya.


xi

8. Kakak dan adik angkatan Program Studi Matematika yang telah membantu

dan memotivasi. Terima kasih banyak atas bantuan dan dukungannya.

9. Teman-teman dan sahabat PSM Cantus Firmus, khususnya Ayu, Dhani,

Gia, Ria, Sasha, Ocha, Dea, Jalu, Martin, dan Tamara yang telah

memotivasi, mendukung dan menghibur selama proses penyusunan

makalah dan selama masa perkuliahan. Terima kasih banyak atas

kekompakkan, dorongan, dan suara merdunya.

10. Yosia, Tegar, Nilla, Gina, Meldy, dan Mufidah atas motivasi dan

dukungan dalam proses penyusunan makalah ini.

11. Pihak-pihak lain yang tidak dapat disebutkan satu per satu atas dukungan

dan bantuannya selama penulisan makalah ini.

Semoga segala bentuk perhatian, dukungan, dan bantuan yang telah diberikan

akan mendapatkan balasan dari Tuhan Yesus Kristus. Penulis menyadari dan

meminta maaf atas kekurangan-kekurangan dalam penulisan makalah ini.Oleh

karena itu, penulis mengharapkan kritik dan saran demi penyempurnaan

makalah ini.Penulis berharap bahwa makalah ini dapat bermanfaat bagi para

pembaca.


xii

DAFTAR ISI

APLIKASI TEORI GRUP DALAM MENGKLASIFIKASIKAN MINI-

SUDOKU ................................................................................................................. i

APPLICATION OF GROUP THEORY IN CLASSIFYING MINI-SUDOKU .... ii

HALAMAN PERSETUJUAN PEMBIMBING .................................................... iii

HALAMAN PENGESAHAN ................................................................................ iv

HALAMAN PERSEMBAHAN ............................................................................. v

ABSTRAK ............................................................................................................. vi

ABSTRACT .......................................................................................................... vii

LEMBAR PERNYATAAN PERSETUJUAN .................................................... viii

PERNYATAAN KEASLIAN KARYA ................................................................ ix

KATA PENGANTAR ............................................................................................ x

DAFTAR ISI ......................................................................................................... xii

BAB I PENDAHULUAN ................................................................................... 1

A. Latar Belakang Masalah ............................................................................... 1

B. Rumusan Masalah ........................................................................................ 4

C. Batasan Masalah........................................................................................... 4

D. Tujuan Penulisan .......................................................................................... 4

E. Metode Penulisan ......................................................................................... 4

F. Manfaat Penulisan ........................................................................................ 5

G. Sistematika Penulisan .................................................................................. 5

BAB II TEORI GRUP ........................................................................................ 7

A. Himpunan ..................................................................................................... 7

B. Relasi .......................................................................................................... 12

C. Fungsi ......................................................................................................... 18


xiii

D. Grup ........................................................................................................... 27

BAB III MINI-SUDOKU DAN KLASIFIKASINYA ..................................... 52

A. Mini-Sudoku .............................................................................................. 52

B. Simetri Baris dan Simetri Kolom ............................................................... 54

C. Simetri Persegi ........................................................................................... 60

D. Simetri Pelabelan-Ulang ............................................................................ 64

E. Dua Kelas Ekivalensi Mini-Sudoku ........................................................... 65

BAB IV PENUTUP .......................................................................................... 69

A. Kesimpulan ................................................................................................ 69

B. Saran ........................................................................................................... 70

DAFTAR PUSTAKA ........................................................................................... 71


1

BAB I

PENDAHULUAN

A. Latar Belakang Masalah

Dewasa ini Sudoku merupakan salah satu permainan yang digemari banyak

kalangan di seluruh dunia.Kata Sudoku berasal dari bahasa Jepang, tetapi

permainan ini tidak ditemukan di Jepang, melainkan berawal di Swis kemudian

melalui Amerika sampai ke Jepang.

Dua ribu tahun yang lalu di China telah terdapatsebuah permainan yang

disebut Magic Square. Permainan tersebut memiliki permasalahan dalam hal

numerik dan posisi, yaitu setiap baris, kolom dan diagonalnya harus berisi

bilangan-bilangan yang sama banyak jumlahnya.

Gambar 1.1Magic Square

Kemudian Magic Square tersebar sampai ke Eropa melalui orang-orang Arab

yang membawa berita tentang penemuan-penemuan di China.

Matematikawan besar yang berasal dari Swiss, Leonhard Euler, merupakan

orang pertama yang menciptakan permainanyang sekarang kita sebut

Sudoku.Pada awalnya Euler mengembangkan dasar-dasar Sudoku yang

disebutnyaRoman Squaresatau LatinSquaresdengan menggunakan huruf-huruf

untuk mengisi setiap kotak.Iamenghilangkan aturan dari Magic Square yaitusetiap

baris, kolom dan diagonalnya berisi bilangan-bilangan yang sama jumlahnya dan

mengubahnya menjadi sebuah permainanpermutasi. Empat huruf pertama dari

abjad Yunani yaitu , , , dikombinasikan dengan empat huruf pertama dari


2

abjad Latin yaitu A, B, C, D sedemikian sehingga setiap huruf Yunani dan Latin

muncul satu kali dalam setiap baris dan kolom seperti pada Gambar 2. Permainan

tersebut untuk pertama kali dipublikasikan pada tahun 1782 di Verhandelingen

uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen 9.

Gambar 1.2 Euler’s Graeco-Latin Square

Konsep Euler tersebut kemudian dikembangkan oleh Howard Garnes menjadi

persegi berukuran 9 9 dengan persegi bagian (blok) berukuran 3 3 di mana

setiap baris dan kolom harus memuat tepat satu bilangan. Howard Garnes

menyebut permainan tersebut Number Place, dan diterbitkan pertama kali dalam

Dell Puzzle Magazine pada tahun 1979 di New York.

Tidak membutuhkan waktu yang lama, permainantersebut sampai ke Jepang

dan mengalami transformasi final menjadi Sudoku. Dalam bahasa Jepang Number

Place diterjemahkan menjadi suuji wa dokushin ni kagiru yang berarti “bilangan-

bilangan harus muncul tepat satu kali” dan disingkat menjadi Su Doku. Untuk

pertama kalinya pada tahun 1984 majalah Monthly Nikolist menerbitkan

permainan Sudoku. Orang Jepang menambahkan elemen lain pada permainan

Sudoku, yaitu menetapkan peraturan baru bahwa pola kotak-kotak yang sudah

terisi bilangan harus simetris, tidak acak. Mereka juga menetapkan bahwa paling

sedikit 32 dari 81 persegi harus sudah terisi bilangan pada awalnya untuk

memberikan tingkat kesulitan yang layak.


3

Gambar 1.3 Sudoku

Dalam permainan Sudoku berukuran 9 9 dan blok berukuran 3 3, pemain

akan mengisi setiap baris, setiap kolom, dan setiap blok dengan tepat satu

bilangan 1 sampai dengan 9. Ketika setiap baris, kolom, dan blok telah terisi

penuh, maka dapat dikatakan persegi berukuran 9 9 tersebut merupakan

Sudoku.

Pada Sudoku berukuran 9 9, Felgenhauer dan Jarvis ( )menemukan

ada 5524751496156892842531225600 5.525 1027

Sudoku, kemudian Russell

dan Jarvis ( )menemukan ada 5,472,730,538 Sudoku yang benar-benar

berbeda. Tidak hanya terbatas pada ukuran 9 9, Sudoku dapat dibuat berukuran

n2 n

2. Pada Makalah ini akan dibahas Sudoku berukuran 4 4 atau biasa disebut

mini-Sudoku.

Mini-Sudoku berukuran 4 4 memiliki blok berukuran 2 2 seperti pada

Gambar 4.

Gambar 1.4 Mini-Sudoku

Aturannya adalah setiap baris, setiap kolom, dan setiap blok berisi tepat satu

angka 1 sampai dengan 4. Mini-Sudoku ini akan menjadi permainan yang sangat


4

menarik secara matematis dalam berbagai cara, yang kemudian menimbulkan

pertanyaan seperti: Bagaimana cara menyelesaikan permainan tersebut? Berapa

banyak mini-Sudoku yang benar-benar berbeda? Dua mini-Sudoku dikatakan

sama atau ekivalen jika mini-Sudoku yang satu dapat dihasilkan dari mini-Sudoku

yang lain dengan menerapkan beberapa langkah seperti menukarkan dua baris

atau kolom, atau merotasi mini-Sudoku 90° searah jarum jam, atau melakukan

pelabelan-ulang pada entri-entri (misalkan mengganti setiap angka 4 dengan

angka 3 dan setiap angka 3 dengan angka 4). Permainan ini memiliki kombinasi

yang menarik, baik sebagai obyek matematik maupun sebagai obyek

logika.Landasan utama pembahasan ini adalah Teori Grup. Secara khusus, konsep

Aksi Grup pada himpunan akan memberikan definisi yang tepat mengenai dua

mini-Sudoku pada dasarnya sama atau ekivalen.

B. Rumusan Masalah

1. Bagaimana membedakan mini-Sudoku yang benar-benar berbeda?

2. Bagaimana cara mengklasifikasikan mini-Sudoku?

C. Batasan Masalah

Makalah ini membahas Sudoku berukuran atau disebut mini-

Sudoku.Akan dicari dua mini-Sudoku benar-benar berbeda dengan menggunakan

metode-metode yang ada dalam Teori Grup.

D. Tujuan Penulisan

1. Untuk memahami mini-Sudoku yang benar-benar berbeda.

2. Untuk memahami cara mengklasifikasikan mini-Sudoku.

E. Metode Penulisan

Metode penulisan yang digunakan dalam makalah ini adalah studi pustaka

dari buku-buku dan jurnal yang berkaitan dengan mini-Sudoku dan Teori Grup.


5

F. Manfaat Penulisan

Makalah ini dapat memberi pengetahuan mengenai langkah-langkah untuk

mengetahui apakah dua mini-Sudoku pada dasarnya sama atau ekivalen.

G. Sistematika Penulisan

Sistematika penulisan tugas akhir ini adalah sebagai berikut:

BAB I PENDAHULUAN

A. Latar Belakang Masalah

B. Rumusan Masalah

C. Batasan Masalah

D. Tujuan Penulisan

E. Metode Penulisan

F. Manfaat Penulisan

G. Sistematika Penulisan

BAB II TEORI GRUP

A. Himpunan

B. Relasi

C. Fungsi

D. Grup

BAB III MINI-SUDOKU DAN KLASIFIKASINYA

A. Mini-Sudoku

B. Simetri Baris dan Simetri Kolom

C. Simetri Persegi

D. Simetri Pelabelan-Ulang

E. Dua Kelas Ekivalensi Mini-Sudoku


6

BAB IV PENUTUP

A. Kesimpulan

B. Saran

DAFTAR PUSTAKA


7

BAB II

TEORI GRUP

Dalam bab ini dibahas pengertian-pengertian dasar yang akan digunakan

dalam pembahasan selanjutnya, yaitu: Himpunan, Relasi, Fungsi, dan Grup.

A. Himpunan

Konsep himpunan dalam matematika biasanya dilambangkan dengan huruf

besar, misalnya A, B, C, dst. Obyek-obyek yang merupakan anggota dari suatu

himpunan disebut anggota atau elemen dari himpunan itu, dan dilambangkan

dengan huruf kecil, misalnya a,b,x,y,dst. Himpunan semua objek yang termasuk

lingkup pembicaraan disebut himpunan semesta atau semesta wacana, yang

dilambangkan dengan U atau X.

Himpunan biasanya disajikan dengan lambang tertentu sebagai berikut:

adalah himpunan semua bilangan asli (bilangan bulat positif).

adalah himpunan semua bilangan bulat.

adalah himpunan semua blangan rasional.

adalah himpunan semua bilangan real.

adalah himpunan semua bilangan kompleks.

Apabila suatu objek x merupakan anggota dari himpunan A, maka hal itu kita

nyatakan dengan notasi

x∈A

dan apabila objek y tidak merupakan anggota dari himpunan A, maka hal itu kita

nyatakan dengan notasi

y A

Ada beberapacara untuk menyatakan himpunan, yaitu: cara daftar, cara

syarat keanggotaan, dan fungsi karakteristik.


8

Cara pertama, dengan cara daftar, yaitu menyatakan suatu himpunan dengan

menuliskan satu per satu lambang anggota-anggotanya di antara tanda kurung

kurawal, dan setiap dua anggota dipisahkan dengan tanda koma.

Contoh 2.1

* +

* +

* +

* +

Cara kedua, dengancara syarat keanggotaan, yaitu dengan menuliskan syarat

keanggotaan himpunan yang dinyatakan.Syarat keanggotaan ini harus terdefinisi

dengan jelas, artinya suatu obyek harus dapat ditentukan dengan tegas, merupakan

anggota himpunan itu atau tidak.

Contoh 2.2

* +

* +

* +

* ∈ +

Cara lain untuk menyatakan suatu himpunan ialah dengan menggunakan apa

yang disebut fungsi karakteristik, yaitu suatu fungsi dari himpunan semesta X ke

himpunan {0, 1}. Suatu himpunan A dalam semestaX dapat dinyatakan dengan

fungsi karakteristik

* +

yang didefinisikan dengan aturan

( ) { ∈

untuk setiap x∈X.

1. Himpunan Kosong dan Himpunan Bagian

Suatu himpunan tidak selalu memiliki anggota.Bisa saja suatu himpunan

tidak memuat anggota.Himpunan semacam itu disebut himpunan kosong dan


9

dilambangkan dengan ∅ atau {}.Suatu himpunan yang hanya memuat satu elemen

saja disebut himpunan elemen tunggal (singleton).

Suatu himpunan A dalam semesta X dikatakan merupakan himpunan bagian

(subhimpunan) dari himpunan B, dengan notasi

A ⊆ B,

jika dan hanya jika setiap anggota dari himpunan A juga merupakan anggota dari

himpunan B. Jadi

A⊆B jhj (∀x∈A) x∈ A⟹x∈B

Dua buah himpunan A dan B dikatakan sama, dengan notasi

A=B,

jika dan hanya jika setiap anggota himpunan A adalah anggota himpunan B dan

sebaliknya setiap anggota himpunan B adalah anggota himpunan A. Dengan

perkataan lain,

A=B

jika dan hanya jika

A⊆BdanB⊆A.

Contoh 2.3

Jika * +dan * +, maka A= B, sebab akar-

akar persamaan adalah x=2 atau x=3.

2. Operasi Himpunan

Operasi himpunan adalah aturan untuk menghasilkan himpunan dari satu atau

lebih himpunan yang diketahui.Operasi dengan satu himpunan disebut operasi

uner, sedangkan operasi dengan dua himpunan disebut operasi biner. Berikut akan

dibahas enam buah operasi himpunan, yaitu komplemen, gabungan, irisan, selisih,

simetrik, dan darab Cartesius. Operasi komplemen merupakan operasi uner,


10

sedangkan gabungan, irisan, selisih, simetrik, dan darab Cartesius merupakan

operasi biner.

Definisi 2.1.1

Misalkan S adalah suatu himpunan semesta, maka komplemen himpunan A

dengan notasiAc adalah himpunan semua anggota himpunan semesta S yang bukan

merupakan anggota A, atau dapat ditulis sebagai berikut:

* ∈ +.

Definisi 2.1.2

Gabungan dua buah himpunan A dan B, dengan notasi

A∪B,

adalah himpunan semua elemen dalam semesta yang merupakan anggota

himpunan A atau himpunan B, yaitu

∪ * ∈ ∈ +.

Definisi 2.1.3

Irisan dua buah himpunan A dan B, dengan notasi

A∩B

adalah himpunan semua anggota himpunan A yang sekaligus anggota himpunan

B, yaitu

∩ * ∈ ∈ +.

Bila ∩ ∅, maka A dan B disebut dua buah himpunan yang saling asing

atau saling lepas. Misalnya, himpunan A dan komplemennya adalah saling asing,

sebab

∩ * ∈ ∈ + * ∈ + ∅.

Bila ∩ ∅, maka A dan B disebut dua buah himpunan yang beririsan

atau berpotongan.


11

Definisi 2.1.4

Selisih dua buah himpunan A dan B, dengan notasi

adalahhimpunan semua elemen dalam semesta yang merupakan anggota

himpunan A dan bukan anggota himpunan B, yaitu

* ∈ +.

Definisi 2.1.5

Selisih simetrik dua buah himpunanA dan B, dengan notasi

adalah himpunan semua elemen dalam semesta yang merupakan anggota

himpunan

A Batau himpunan B A, yaitu

( ) ∪ ( ).

Definisi 2.1.6

Darab Cartesius dua buah himpunan A dan B, dengan notasi

adalah himpunan semua pasangan terurut (x,y) dengan x∈A dan y∈B, yaitu

*( ) ∈ ∈ +.

Contoh 2.4

Misalnya A= {1, 2, 3, 4} dan B= {1, 3, 5}. Maka

∪ * + ∩ * +

* +

* +

* +

*( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )+


12

*( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )+

B. Relasi

Pada umumnya, relasi terjadi antara elemen-elemen dalam suatu himpunan

dengan elemen-elemen dalam himpunan lainnya. Misalnya diketahui dua buah

himpunan bilangan * +dan * +, dan relasi “lebih besar atau

sama dengan” antara elemen-elemen dalam himpunan X dengan elemen-elemen

dalam himpunan Y.

1. Relasi Biner

Suatu relasi R antara elemen-elemen dalam himpunan X dengan elemen-

elemen dalam himpunan Y dapat dinyatakan sebagai himpunan pasangan terurut

(x, y) di mana elemen x∈Xberelasi dengan elemen y∈ Y, yaitu

*( ) ∈ ∈ +.

Misalnya relasi R (lebih besar atau sama dengan) dalam contoh di atas dapat

dinyatakan sebagai himpunan pasangan terurut sebagai berikut:

*( ) ( ) ( )+.

Jelas bahwa relasi R antara elemen-elemen dalam himpunan X dengan

elemen-elemen dalam himpunan Y tersebut merupakan himpunan bagian dari

darab Cartesius X ×Y.Sebaliknya, setiap himpunan bagian dari darab Cartesius X

×Ydapat dipandang sebagai suatu relasi antara elemen-elemen dalam himpunan X

dengan elemen-elemen dalam himpunan Y. Relasi antara elemen-elemen dalam

dua buah himpunan seperti contoh di atas biasanya disebut relasi biner.

Secara matematis, relasi biner R antara elemen-elemen dalam himpunan X

dengan elemen-elemen dalam himpunan Y didefinisikan sebagai himpunan bagian

dari darab Cartesius X×Y, yaitu

⊆ .

Relasi R antara elemen-elemen dalam himpunan X dengan elemen-elemen

dalam himpunan Y seringkali juga disebut relasi R dari himpunan X ke himpunan


13

Y. Jika elemen x∈X berelasi R dengan elemen y ∈ Y, maka hal itu dinyatakan

dengan lambang

(x, y) ∈R

atau kadang-kadang dengan lambang

xRy.

Sebaliknya, jika elemen x∈X tidak berelasi dengan elemen y∈Y, maka hal itu

dinyatakan dengan lambang

(x, y) R

atau kadang-kadang dengan lambang

xRy.

Misalnya untuk relasi R (lebih besar atau sama dengan) dalam contoh di atas,

pasangan terurut (3,2) ∈R, yang juga dapat dinyatakan dengan lambang 3R2, atau

biasanya dengan lambang 3≥2.

Jika R adalah suatu relasi biner dari himpunan X ke himpunan Y, maka

domain dari R, yang dinotasikan dengan domR, adalah himpunan semua elemen

dalam X yang berelasi dengan suatu elemen dalam Y, yaitu

* ∈ ( ∈ ) ( ) ∈ +.

Range dari R, yang dinotasikan dengan ran R, adalah himpunan semua

elemen dari Y yang berelasi dengan suatu elemen dari X, yaitu

* ∈ ( ∈ ) ( ) ∈ +.

Jika X=Y, maka relasi R itu merupakan himpunan bagian dari X× X, yaitu

⊆ , dan disebut relasi pada himpunanX. Himpunan X yang dilengkapi

dengan suatu relasi R pada himpunan X itu biasanya disajikan dengan pasangan

terurut (X, R).

Contoh 2.5

Antara elemen-elemen dalam himpunan * + dan

elemen-elemen dalam himpunan * + didefinisikan relasi R, yaitu xRy

jika dan hanya jika elemen ∈ habis dibagi oleh ∈ . Maka R={(3,3), (4,4),

(5,5), (6,3), (6,6), (8,4), (9,3), (10,5)}. Perhatikan bahwa ( ) ∈ sebab 6∈X

habis dibagi oleh 3∈Y, sedangkan (3,4) R sebab ∈ tidak habis dibagi oleh


14

∈ . Domain dari relasi R tersebut adalah domR= {3, 4, 5, 6, 8, 9, 10},

sedangkan range dari relasi R tersebut adalah ranR= {3, 4, 5, 6}.

Relasi R antara elemen-elemen dalam himpunan berhingga

* + dengan elemen-elemen dalam himpunan berhingga

* + dapat dinyatakan dalam suatu matriks berukuran m×n sebagai

berikut

(

)

di mana

{

untuk dan .

Contoh 2.6

Misalnya diketahui dua buah himpunan * + dan * +,

dan relasi “lebih besar atau sama dengan” antara elemen-elemen dalam himpunan

X dengan elemen-elemen dalam himpunan Y. Matriks dari relasi R tersebuat

adalah

(

)

2. Invers dari Relasi Biner

Bila R adalah relasi biner antara elemen-elemen dalam himpunan X dengan

elemen-elemen dalam himpunan Y (relasi dari himpunan X ke himpunan Y), maka

invers darirelasi R, dengan notasi , adalah relasi antara elemen-elemen dalam

himpunan Y dengan elemen-elemen dalam himpunan X (relasi dari himpunan Y ke

himpunan X) dengan ( ) ∈ bila dan hanya bila ( ) ∈ . Jadi,

*( ) ∈ ∈ ( ) ∈ +.


15

Matriks dari relasi adalah transpos dari matriks relasi R. Untuk setiap

relasi R dari himpunan Xke himpunan Yberlaku( ) =R, sebab

( ) *( ) ∈ ∈ ( ) ∈ +

*( ) ∈ ∈ ( ) ∈ +

.

Contoh 2.7

Relasi “lebih besar atau sama dengan” (dilambangkan dengan R) antara

elemen-elemen dalam himpunan X= {1, 2, 3} dengan elemen-elemen dalam

himpunan Y= {2, 3, 4} adalah R= {(2,2), (3,2),(3,3)}, dan inversnya adalah =

{(2,2), (2,3), (3,3)}. Matriks dari relasi R tersebut adalah

(

).

Sedangkan matriks dari relasi inversnya adalah

(

).

3. Relasi-relasi khusus

Akan dibahas relasi-relasi khusus yang didefinisikan pada suatu himpunan.

Definisi 2.2.1

Misalkan ⊆ adalah suatu relasi pada himpunan X. Relasi R itu

dikatakan bersifat refleksifbila dan hanya bila

( ) ∈

untuk setiap ∈ . Dengan perkataan lain, relasi R pada himpunan X bersifat

refleksif jika setiap elemen dalam XberelasiR dengan dirinya sendiri.


16

Definisi 2.2.2

Relasi R pada himpunan X dikatakan bersifat simetrik bila dan hanya bila

Jika (x,y) ∈R, maka (y,x) ∈R

untuk setiap x dan ∈ . Dengan perkataan lain, relasi R pada himpunan X

bersifat simetrik apabila untuk setiap x dan y∈X berlaku jika x berelasi R dengan

y, maka y berelasi R dengan x.

Relasi R pada himpunan X dikatakan bersifat antisimetrik bila dan hanya bila

Jika (x,y) ∈R dan (y,x) ∈ R, maka x=y

untuk setiap x dan y ∈X. Dengan perkataan lain, relasi R pada himpunan X bersifat

antisimetrik apabila untuk setiap x dan y∈X berlaku jika x berelasi R dengan y dan

y berelasi R dengan x, maka x=y.

Definisi 2.2.3

Relasi R pada himpunan X dikatakan bersifat transitif bila dan hanya bila

Jika (x,y) ∈R dan (y,z) ∈R, maka (x,z) ∈R

untuk setiap x, y, dan z ∈X. Dengan perkataan lain, relasi R pada himpunan X

bersifat transitif apabila untuk setiap x,y, dan z∈Xberlaku jika x berelasi R dengan

y dan y berelasi R dengan z, maka x berelasi R dengan z.

Definisi 2.2.4

Suatu relasi R yang sekaligus bersifat reflektif, simetrik, dan transitif disebut

relasi ekivalensi.Relasi R yang bersifat refleksif dan simetrik disebut relasi

kompatibilitas.Sedangkan relasi R yang bersifat refleksif, antisimetrik, dan

transitif disebut relasi urutan parsial. Suatu himpunan X yang dilengkapi dengan

suatu relasi urutan parsial R disebut himpunan terurut parsial (partially ordered

set, disingkat poset). Relasi urutan parsial R dalam suatu poset seringkali disajikan

dengan lambang ≤, dan (x,y) ∈R disajikan dengan lambang x≤y.


17

4. Relasi Ekivalensi dan Partisi

Relasi ekivalensi memegang peranan penting dalam matematika, karena relasi

ekivalensi yang terdefinisi pada suatu himpunan akan mengakibatkan suatu

klasifikasi tertentu pada himpunan itu.

Definisi 2.2.5

Misalkan R adalah suatu relasi ekivalensi pada himpunan X. Jika x dan y

adalah dua buah elemen dalam X dan (x,y) ∈R, maka dikatakan bahwa kedua

elemen itu adalah ekivalen. Jika a∈X, maka himpunan semua elemen dalam X

yang ekivalen dengan a disebut kelas ekivalensi yang dibangkitkan oleh elemen a

dan relasi R. Karena relasi R itu bersifat refleksif, maka (a, a) ∈R, yang berarti

bahwa a sendiri termuat dalam kelas ekivalensi tersebut. Kelas ekivalensi yang

dibangkitkan oleh elemen a dan relasi R dilambangkan dengan , yaitu

* ∈ ( ) ∈ +.

Kelas ekivalensi tersebut memuat a dan memuat semua elemen dalam X

yang ekivalen dengan a. Dengan perkataan lain, a ∈ untuk setiap a∈X. Jadi,

untuk setiap a∈X kelas ekivalensi adalah himpunan bagian takkosong dari X.

Keluarga semua kelas ekivalensi dalam himpunan X yang dibangkitkan oleh relasi

ekivalensi R disajikan dengan lambang X/R, yaitu

X ∕R = { | a∈X}

Definisi 2.2.6

Partisidari suatu himpunan adalah keluarga berhingga himpunan-himpunan

bagian Ai(i = 1, 2, …,n) dari A yang memenuhi:

1. Ai ∅ untuk setiap i = 1, 2, …,n, yaitu setiap himpunan bagian Ai tidak

kosong.

2. Ai ∩Aj ∅untuk setiap i dan j dengan i j, yaitu setiap dua buah himpunan

bagian yang tidak sama adalah saling lepas (atau secara ekivalen, jika dua

buah himpunan bagian beririsan, maka kedua himpunan bagian itu adalah

sama).


18

3. ⋃ =A, yaitu gabungan semua himpunan bagian itu adalah himpunan

A.

Perhatikan bahwa suatu himpunan dapat mempunyai lebih dari satu partisi,

seperti ditunjukkan pada Gambar 2.1.

A

Gambar 2.1Dua buah partisi yang berbeda dari himpunan A.

Contoh 2.8

Misalkan A = {1,2,3,4,5,6,7,8,9,10}. Keluarga himpunan-himpunan bagian

dari A, yaitu {{1,3,4}, {2,7,8,9}, {5,6,10}} adalah suatu partisi dari A.

Demikian pula {{1,2}, {3,4,6}, {5,7,10}, {8,9}}.

C. Fungsi

Suatu fungsi adalah relasi khusus f antara elemen-elemen dalam suatu

himpunan X dengan elemen-elemen dalam himpunan Y. Kekhususannya terletak

dalam dua hal, yaitu:

(1) Setiap elemen dalam himpunan X berelasi dengan suatu elemen dalam

himpunan Y.

(2) Elemen dalam himpunan Y yang berelasi dengan elemen dari himpunan

X itu adalah tunggal.

Kedua sifat khusus tersebut dapat dinyatakan dalam suatu kalimat, yaitu:

Untuk setiap elemen dalam himpunan X terdapat dengan tunggal elemen dalam

himpunan Yyang berelasi dengannya. Relasi khusus semacam itu disebut

Cjklkjojojkhjfjfyyyytuygui

Cjklkjojojkhjfjfyyyytuygui

AIUIYDIUASYUIAHFSUYAAFADSF A


19

fungsi(atau seringkali juga disebut pemetaan) dari himpunan X ke himpunan Y,

dan disajikan dengan lambang:

f :X Y.

Himpunan X disebut domain dari fungsi f dan dilambangkan dengan dom f,

sedangkan himpunan Y disebut kodomain dari fungsi f dan dilambangkan dengan

kod f. Jika x∈X, maka elemen y∈Y yang berelasi dengan elemen x itu disebut

bayangan (atau peta) dari x oleh fungsi f, atau nilai dari fungsi f di x, dan

dilambangkan dengan

y =f(x).

Elemen x∈X itu disebut argumen dari fungsi f, seringkali juga disebut

variabel bebas, sedangkan y∈Y yang merupakan bayangan dari x itu disebut

variabel takbebas (karena nilainya tergantung dari x). Bayangan dari elemen x∈X

oleh fungsi f itu seringkali juga disajikan dengan lambang

( ).

Jika y∈Y, maka elemen x∈X sedemikian sehingga y =f(x) disebut

prabayangan (atau prapeta) dari y dan dilambangkan dengan

( )

Bayangan setiap elemen dari domain suatu fungsi selalu ada dan tunggal,

sedangkan prabayangan dari suatu elemen dalam kodomain suatu fungsi belum

tentu ada dan kalaupun ada prabayangan itu belum tentu tunggal.Pada umumnya,

prabayangan dari suatu elemen dalam kodomain suatu fungsi adalah suatu

himpunan (dapat berupa himpunan kosong, atau himpunan elemen tunggal, atau

himpunan yang memuat lebih dri satu elemen), sedangkan bayangan dari setiap

elemen dalam domain suatu fungsi adalah satu elemen (yang dapat juga

dipandang sebagai suatu himpunan dengan elemen tunggal).

1. Kesamaan Dua Buah Fungsi

Jika adalah suatu fungsi, maka himpunan semua elemen dalam

kodomain Y yang merupakan bayangan dari suatu elemen dalam domain X disebut


20

kisaran dari fungsi f dan dinyatakan dengan notasi ( ). Jadi kisaran dari fungsi f

adalah

( ) * ∈ ( ) ( )+.

Kisaran ( ) merupakan himpunan bagian dari kodomain Y, yaitu ( ) ⊆ .

Dua buah fungsi dan g dikatakan sama, yaitu f =g, jika dan

hanya jika f(x) =g(x) untuk setiap x ∈ X.

2. Fungsi-Fungsi Khusus

Ada beberapa fungsi khusus yang akan dibahas berikut ini.

a. Fungsi Injektif

Suatu fungsi disebut fungsi (pemetaan) injektif jika dan hanya jika

untuk setiap ∈X berlaku apabila f( ) =f( ) maka , yaitu bila dua

elemen dalam domain mempunyai bayangan yang sama, maka kedua elemen itu

adalah elemen yang sama. Secara simbolis:

fadalah fungsi injektif jhj (∀ ∈X) f( ) =f( ) ⟹ .

Secara ekivalen, juga dapat dinyatakan bahwa:

fadalah fungsi injektifjhj (∀ ∈X) ⟹f( ) f( ).

yaitu bila dua elemen dalam domain adalah dua elemen yang tidak sama, maka

bayangan kedua elemen itu juga tidak sama.

b. Fungsi Surjektif

Suatu fungsi f disebut fungsi (pemetaan) surjektif jika dan hanya jika

kisaran dari fungsi f tersebut sama dengan kodomain dari fungsi f , yaitu f(X) =Y.

Dengan perkataan lain, fungsi f adalah fungsi surjektif jika dan hanya jika

untuk setiap y∈Y terdapat ∈ sedemikian sehingga ( ), yaitu setiap

elemen dalam kodomain mempunyai prabayangan. Secara simbolis:


21

fadalah fungsi surjektifjhj (∀ ∈ )( ∈ ) ( ).

c. Fungsi Bijektif

Suatu fungsi f: X Y disebut fungsi (pemetaan) bijektif jika dan hanya jika

fungsi f tersebut adalah fungsi yang injektif dan sekaligus surjektif. Maka pada

suatu fungsi bijektif, setiap elemen dalam domain mempunyai tepat satu

bayangan, dan setiap elemen dalam dalam kodomain juga mempunyai tepat satu

prabayangan.Oleh karena itu, fungsi bijektif seringkali juga disebut korespondensi

satu-satu. Dua buah himpunan X dan Y dikatakan ekipoten, dengan notasi X ≃Y,

jika dan hanya jika terdapat korespondensi satu-satu antara kedua himpunan itu,

yaitu terdapat suatu fungsi sedemikian sehingga f adalah fungsi bijektif.

Contoh 2.9

Fungsi , dimana adalah himpunan semua bilangan real, dengan

( ) untuk setiap ∈ , adalah fungsi yang injektif dan surjektif dan

oleh karenanya merupakan fungsi bijektif.

(a) Fungsi adalah fungsi injektif, sebab bila ( ) ( ), yaitu

, maka , sehingga . Jadi bila elemen domain

mempunyai bayangan yang sama, maka kedua elemen itu adalah elemen yang

sama.

(b) Fungsi adalah fungsi surjektif, sebab untuk setiap elemen y ∈ (kodomain)

terdapat

∈ (domain), sedemikian sehingga ( )

.

/ . Jadi setiap elemen dalam kodomain

mempunyai prabayangan.

Definisi 2.3.1

Himpunan berhingga adalah himpunan kosong atau himpunan yang

berkorespondensi satu-satu dengan himpunan * + untuk suatu bilangan

bulat positif k. Banyaknya anggota dari suatu himpunan berhingga A dinyatakan


22

dengan lambang . Jika ∅ adalah himpunan kosong, maka ∅ . Jika

himpunan berhingga A berkorespondensi satu-satu dengan himpunan

* +, maka , yaitu banyaknya anggota himpunan A adalah k

elemen.

Contoh 2.10

Jika * +

* +,maka .

Teorema 2.1

Jika dua buah himpunan berhingga A dan B saling asing, maka

∪ .

Bukti:

Diketahui A dan B himpunan berhingga dan saling asing, dan misalkan

dan ,yaitu terdapat fungsi bijektif f dan sedemikian sehingga

* + dan * +. Didefinisikan relasi ∪

* +sebagai berikut:

( ) { ( ) ∈

( ) ∈

Akan ditunjukkan bahwa adalah suatu fungsi.

Ambil sebarang , ∈ ∪ .

- Kasus 1: Jika ∈ , dengan , menggunakan syarat pertama dari

definisi fungsi maka ( ) ( )dan ( ) ( ). Karena adalah

fungsi, dan , maka ( ) ( ).

Jadi ( ) ( ).

- Kasus 2: Jika ∈ , dengan , menggunakan syarat pertama dari

definisi fungsimaka ( ) ( )dan ( ) ( ). Karena

adalah fungsi, dan , maka ( ) ( ). Jadi ( ) ( ).


23

- Kasus 3:Jika ∈ dan ∈ , maka karena dan saling asing,

sehingga implikasi ( ) ( ) benar karena konsekuennya

benar.

- Kasus 4:Jika ∈ dan ∈ , maka karena dan saling asing,

sehingga implikasi ( ) ( ) benar karena konsekuennya

benar.

Akan diperlihatkan bahwa h adalah fungsi bijektif.

Ambil sebarang dan ∈ ∪ sedemikian sehingga ( ) ( ).

(i) Jika ∈ , maka ( ) ( ) mengakibatkan ( ) ( ). Karena f

injektif, maka .

(ii) Jika ∈ , maka ( ) ( ) mengakibatkan ( )

( ), sehingga ( ) ( ). Karena injektif, maka .

(iii) Jika ∈ dan ∈ ,maka karena dan saling asing. Karena

∈ , maka ( ) ( ) ≤ . Karena ∈ , maka ( )

( ) . Jadi ( ) ( ).

(iv) Jika ∈ dan ∈ , maka karena dan saling asing. Karena

∈ , maka ( ) ( ) . Karena ∈ , maka ( )

( ) ≤ . Jadi ( ) ( ).

Jadi terbukti h injektif.

Ambil sebarang ∈ * +.

(i) Jika ≤ ≤ , maka ∈ Karena f surjektif, maka terdapat ∈

sedemikian sehingga ( ) . Jadi, terdapat ∈ ∪ sedemikian

sehingga ( ) ( ) .

(ii) Jika ≤ ≤ ,maka ≤ sehingga ∈ . Karena

surjektif, maka terdapat ∈ sedemikian sehingga ( ) .Jadi,

terdapat ∈ ∪ sedemikian sehingga ( ) ( )

( ) .

Jadi terbukti h surjektif.


24

Dengan demikian terdapat fungsi bijektif

∪ * +sehingga

∪ .∎

3. Fungsi Invers

a. Invers dari Fungsi

Jika f adalah suatu fungsi, maka invers dari fungsi f, yaitu , adalah

suatu relasi dari himpunan Yke himpunan X dengan aturan:

(y,x) ∈ jika dan hanya jika ( )

untuk setiap ∈ dan ∈ . Jelas bahwa relasi itu belum tentu

merupakan fungsi.

b. Fungsi Invers

Teorema 2.2 memberikan syarat perlu dan cukup agar invers dari suatu fungsi

juga merupakan fungsi, yang disebut fungsi invers.

Teorema 2.2

Jika f: X Y adalah suatu fungsi, maka merupakan fungsi jika dan hanya

jika f adalah suatu fungsi bijektif. Lagipula tersebut juga merupakan fungsi

bijektif.

Bukti:

Jika adalah fungsi, maka untuk setiap y ∈ Y ada elemen ∈

sedemikian sehingga ( ), berarti untuk setiap y ∈ Y ada elemen x ∈

Xsedemikian sehingga y= f(x). Jadif adalah fungsi yang surjektif. Untuk ∈X,

jika f( ) ( ) ∈ , maka ( )dan

( ). Karena


25

adalah fungsi, maka ( )adalah elemen tunggal dalam Xsehingga . Jadi

f adalah fungsi yang injektif. Terbukti bahwa f: X Y adalah suatu fungsi bijektif.

Selanjutnya, misalkan f: X Y adalah suatu fungsi yang bijektif. Karena f

surjektif, maka untuk setiap ∈ ada elemen ∈ sedemikian sehingga y=f-

(x), berarti untuk setiap ∈ ada elemen ∈ sedemikian sehingga

( ), yaitu setiap elemen dalam Y berelasi dengan suatu elemen dalam X

dengan relasi . Untuk ∈ , misalkan ( ) dan ( ),

sehingga ( )dan

( ). Jika maka ( ) ( ).

Karena f adalah fungsi yang injektif, maka akibatnya , sehingga

( ) ( ) . Jadi elemen-elemen dalam Y berelasi dengan elemen

tunggal dalam X dengan relasi tersebut.Dengan demikian terbukti bahwa

adalah suatu fungsi.

Karena adalah fungsi, maka untuk setiap ∈ ada ∈

sedemikian sehingga y = f(x), yaitu ( ). Jadi adalah fungsi

surjektif.Untuk ∈ , misalkan ( ) dan ( ) . Maka

( )dan ( ). Jika ( ) ( ), maka . Karena f

adalah fungsi, maka haruslah ( ) ( ), sehingga . Jadi

adalah fungsi injektif.Dengan demikian terbukti bahwa tersebut adalah fungsi

yang bijektif.∎

4. Komposisi Fungsi

Dua buah fungsi dengan cara tertentu dapat dioperasikan sehingga

menghasilkan fungsi baru. Operasi itu disebut komposisi fungsi.

Definisi 2.3.2


26

Jika diberikan dua buah fungsi dan , maka komposisi

kedua fungsi tersebut didefinisikan sebagai fungsi g dengan aturan

( )( ) ( ( ))

untuk setiap ∈ . Untuk fungsi f dan tersebut di atas, tidak

didefinisikan, kecuali jika X=Y=Z, yaitu jika dan .

Komposisi kedua fungsi tersebut adalah fungsi-fungsi dan

.

Karena adalah fungsi, maka setiap ∈ mempunyai bayangan

tunggal ( ) ∈ , dan karena adalah fungsi, maka ( ) ∈

mempunyai bayangan tunggal ( ( )) ∈ , maka setiap ∈ mempunyai

bayangan tunggal ( )( ) ( ( )) ∈ . Jadi adalah fungsi.

Contoh 2.11

Misalkan X = {1,2,3,4,5}, Y = {a,b,c,d}, Z = {5,7,8,9,1}. Diberikan dua buah

fungsi f :X Y dan g :Y Z yaituf = {(1,c), (2,a), (3,d), (4,a), (5,b)} dan g = {(a,8),

(b,5), (c,9), (d,1)}.

Maka komposisi kedua fungsi tersebut adalah fungsi di

mana

( ) ( ) ( ( )) ( )

( ) ( ) ( ( )) ( )

( ) ( ) ( ( )) ( )

( ) ( ) ( ( )) ( )

( ) ( ) ( ( )) ( )

yaitu *( ) ( ) ( ) ( ) ( )+.


27

D. Grup

1. Operasi

Operasi merupakan konsep matematika yang penting.Operasi yang sering

digunakan, yaitu penjumlahan, pengurangan, perkalian, dan pembagian.Secara

matematis, operasi dalam suatu himpunan dapat didefinisikan sebagai berikut.

Definisi 2.4.1

Diberikan himpunan tak kosongA. Operasi pada himpunan A adalah

fungsi .Operasi tersebut merupakan operasi biner.

Contoh 2.12

Misalkan adalah himpunan semua bilangan bulat. Operasi + (penjumlahan)

pada merupakan operasi biner, sebab operasi + dapat dinyatakan sebagai fungsi

(pemetaan) dari yaitu untuk setiap (a,b) ∈ maka a+b∈ ,sebab

jumlah dua bilangan bulat adalah suatu bilangan bulat pula.Pembagian pada

bukan merupakan operasi biner pada , sebab ada (a,b) ∈ sedemikian

sehingga (a : b) , misalnya (3,4) ∈ dan (3 : 4) .

Untuk menyatakan sebuah himpunan A dan operasi yang didefinisikan pada

himpunan tersebut, dapat ditulis ( ).

2. Sifat-sifat Operasi

Misalkan A himpunan tak kosong, dan operasi didefinisikan pada A. Hasil

operasi (a,b) atau menggunakan notasi biasa a b dapat disingkat menjadi ab

dengan pengertian bukanlah operasi perkalian biasa.Didefinisikan beberapa sifat

operasi sebagai berikut.

Definisi 2.4.2


28

Diberikan himpunan tak kosong Adan A.

(i) Operasi bersifatkomutatif pada A jika untuk setiap ∈ .

(ii) Operasi bersifatasosiatif pada A jika ( ) ( ) untuk setiap

∈ .

(iii) HimpunanA memuat elemen identitas untuk jika terdapat e∈Asedemikian

sehinggaa e = a dan e a = a untuk setiap a∈A.

(iv) Sebuah elemen a∈A memiliki invers di A terhadap jika ada b∈Asedemikian

sehingga (dimana eadalah elemen identitas yang

didefinisikan di (iii)).

3. Grup

Definisi 2.4.3

Misalkan himpunan G tak kosong dan operasi didefinisikan pada G.

Pasangan (G, ) disebut grup jika memenuhi:

(i) Operasi bersifat asosiatif pada G.

(ii) HimpunanG memuat elemen identitas untuk yang dilambangkan dengan

.

(iii) Setiap elemen dalam G memiliki invers terhadap . Invers dari ∈

dilambangkan dengan ∈ .

Jika operasi memenuhi sifat komutatif, maka (G, ) disebutgrup Abel.

Contoh 2.13

Diberikan himpunan * +. Akan ditunjukkan bahwa ( ) adalah grup

Abel terhadap operasi perkalian biasa.

Operasi bersifat tertutup pada himpunan G:

∈

∈

∈

∈ .


29

(i) Operasi bersifat asosiatif pada ,karena operasi perkalian biasa bersifat

asosiatif pada himpunan bilangan real.

(ii) G memuat elemen identitas ( ) untuk operasi .

Untuk ∈ , maka dan

( ) ( ) .

Untuk ∈ , maka dan .

(iii) Setiap elemen di G memiliki invers di terhadap .

Untuk ∈ , maka ( ) , sehingga ( ) .

Untuk ∈ , maka , sehingga ( ) .

(iv) Operasi bersifat komutatifpada , karena operasi perkalian biasa bersifat

komutatif pada himpunan bilangan real.

Jadi ( ) merupakan grup Abel.

Definisi 2.4.4

Diberikan G adalah himpunan berhingga dan ( ) merupakan grup.Tabel

Cayley dari ( ) adalah tabel yang label baris-baris dan kolom-kolomnya

bersesuaian dengan elemen-elemen di G dan entri dari barisdari elemena dan

kolom dari elemen badalah hasil operasi .

Contoh 2.14

Diberikan himpunan * + yang merupakan grup terhadap operasi

perkalian biasa. Hasil dari operasi perkalian dengan menggunakan Tabel Cayley

adalah

Definisi 2.4.5


30

Diberikan bilangan bulat ndengan . Untuk setiap bilangan bulata,

didefinisikan a(modn) sebagaisisa tak negatif yang kurang dari njikaa dibagi n.

Contoh 2.15

( ) ( )( ) ( )

( )( ) .

Himpunan * + disebuthimpunanbilangan bulat modulo n.

Didefinisikan penjumlahan modulo n, dilambangkan , pada yaitu

( )(modn). Untuk membuktikan bahwa merupakan grup, harus dipastikan

bahwa merupakan operasi pada himpunan . Untuk setiap a,b∈ , (a +

b)(modn) adalah sisa tak negatif yang kurang dari n jika dibagin. Maka

∈ . Dengan demikian merupakan operasi pada . Tabel Cayley

untuk ( )dapat ditulis sebagai berikut:

Bilangan 0 merupakan elemen identitas, 0 juga merupakan invers untuk 0, dan

invers dari elemen tak nola adalah n asebab ( ) n(modn) = 0.

Untuk setiap ∈ ,akan diperlihatkan bahwa

( ) ( ). Dengan operasi penjumlahan biasa di , misalkan

diberikan algoritma pembagi dengan x, y ∈ dan ≤ .

Maka . Misalkan dengan ∈ dan ≤ ,

sehingga . Dengan demikian ( ) .


31

Dapat juga dicari ∈ dimana dengan 0 ≤ <n, dan

∈ dimana dengan 0 ≤ <n, sehingga ( ) .

Untuk memperlihatkan bahwa , perhatikan persamaan berikut dan pernyataan

bahwa operasi penjumlahan biasa bersifat komutatif dan asosiatif pada :

( ) ( ) ( ) ( ) ( ) .

( ) ( ) ( ) ( ) ( ) .

Tetapi di , ( ) ( ), sehingga didapat

,yaitu( ) ( ) Jadi operasi bersifat asosiatif pada

.

Dengan demikian ( ) adalah grup untuk setiap bilangan

bulatn>1.Grup ( ) merupakan grup Abel karena dalam .

Contoh 2.16

Tabel Cayley grup Abel ( )adalah sebagai berikut:

Elemen identitas untuk operasi pada adalah 0. Setiap elemen memiliki

invers, yaitu , 5, , , , .

Teorema 2.3

Misalkan G merupakan grup dengan operasi .

(i) Terdapat tepat satu elemen di G yang merupakan elemen identitas.

(ii) Untuk setiap elemen a∈Gterdapattepat satu elemen dari G yang merupakan

invers dari a.


32

Bukti:

Diasumsikan G adalah grup dengan operasi .

(i) Karena G adalah grup, maka ada elemen ∈ yang merupakan elemen

identitas.Misalkan umerupakan elemenlain dari G yang juga merupakan

elemen identitas. Akan ditunjukkan bahwa e = u.Karena e adalah elemen

identitas, maka e u=u. Demikian pula, karena uelemen identitas,

makae u=e, sehinggae=e u=u. Jadie=u. Dengan demikian terdapat tepat

satu elemen dari G yang merupakan elemen identitas.

(ii) Diberikan ∈ . Karena G adalah grup, maka ada ∈ sedemikian

sehingga . Misalkan ada elemen lain, yaitu ∈ dengan

. Akan ditunjukkan bahwa b=c. Karena , maka

( ) . Karena , maka ( )

. Karena ( ) ( ) , maka b=c. Oleh karena itu ada tepat satu

elemen di G yang merupakan invers daria.∎

Diberikan dua grup (G, •) dan (H, ⊕). Notasi • dan ⊕ digunakan untuk

menekankan bahwa kedua operasi mungkin tidak sama. Dari kedua grup G dan

Hitu dapat dibentuk grup .

Teorema 2.4

Himpunan *( ) ∈ ∈ + merupakan grup dengan operasi

yang didefinisikan sebagai berikut: (a,b) (c, d) = (a•c, b⊕d).

GrupG×H disebut grup perkalian langsung dari grupG dan grup H.

Bukti:

Akan dibuktikan bahwa *( ) ∈ ∈ + merupakan grup

dengan operasi yang didefinisikan di atas.

(i) Diberikan ∈ dan ∈ . Maka

(( ) ( )) ( ) ( ⊕ ) ( )

(( ) ( ⊕ ) ⊕ )

( ( ) ⊕ ( ⊕ ))


33

( ) ( ⊕ )

( ) (( ) ( )).

Jadi operasi bersifat asosiatif pada .

(ii) Diberikan ( ) ∈ . Misal merupakan elemen identitas di G dan

merupakan elemen identitas di H, maka( ) ∈ dan

( ) ( ) ( ⊕ ) ( )dan

( ) ( ) ( ⊕ ) ( ).

Jadi ( ) merupakan elemen identitas dalam .

(iii) Diberikan ( ) ∈ . Maka ada ∈ sedemikian sehingga

,dan ada ∈ sedemikian sehingga

⊕ ⊕ . Maka( ) ∈ dan

( ) ( ) ( ⊕ ) ( )dan

( ) ( ) ( ⊕ ) ( ).

Jadi ( ) ∈ adalah invers dari ( ) ∈ .

Terbukti( ) merupakan grup.∎

Contoh 2.17

Misal untuk grup ( )dapat dibentuk grup

*( ) ( ) ( ) ( )+. Tabel Cayley untuk operasi di

adalah sebagai berikut:

Elemen identitas adalah (0, 0) dan setiap elemen memiliki tepat satu invers,

yaitu( ) ( ) ( ) ( ), ( ) ( ) dan( ) ( ).


34

4. Sifat-sifat Aljabar dalam Grup

Ada beberapa teorema yang memperlihatkansifat-sifat aljabar dalam grup.

Teorema 2.5

Misal G adalah grup, maka

(i) Untuk setiap ∈G, ( ) .

(ii) Untuk setiap ∈G, ( ) .

Bukti:

(i) Asumsikan a∈G. Karena G adalah grup, maka terdapat elemen identitas

∈G, dan ∈ G sedemikian sehingga dan .

Jadiamerupakan invers untuk elemen , yaitu( ) .

(ii) Asumsikan a, b∈G, maka ∈G. Menggunakan sifat asosiatif diperoleh

(ab)( ) ( ) ( ) . Dengan cara yang

sama, ( )( ) ( ) ( ) . Jadi

merupakan invers dari ab,yaitu( ) . ∎

Teorema 2.6

Misal G adalah grup, dan a, b, c ∈G, maka berlaku Hukum Kanselasi, yaitu

(i) Jika ab= ac, maka b = c.

(ii) Jika ba=ca, maka b= c.

Bukti:

(i) Diketahui a, b, c∈G. Misalkan ab= ac, maka ( ) ( ),

sehingga . Jadi .

(ii) Diketahui a, b, c∈G. Misalkan ba= ca, maka ( ) ( ) ,

sehingga . Jadi .∎

Definisi 2.4.6

Misalkan G adalah grup, a∈G, dan n∈ .


35

{

⏟

⏟ ( )

Contoh 2.18

Diberikan grup , dimana menggunakan operasi penjumlahan biasa

dan menggunakan operasi perkalian biasa.

( ) (

) (

).

( ) ( ) ( ).

( ) ( ).

Definisi 2.4.7

Diberikan grup G dan elemen a∈G. Bilangan bulat positif

terkecilnsedemikian sehingga , disebut order dari a, dinotasikan dengan

ord(a). Jika tidak ada bilangan bulat positif n yang memenuhi ,

makadikatakan a mempunyai order tak hingga.

Contoh 2.19

Diberikan grup ( ) dan a = 3. Akan dicari bilangan bulat positif

terkeciln, sedemikian sehingga , yaitu

( )( ) (3 sebanyak nsuku)

Bilangan bulat positif terkeciln yang membuat 3n habis dibagi 7adalahn = 7. Oleh

karena itu, ord(3) = 7.


36

5. Grup Bagian

Akan didefinisikan bahwa himpunan bagian dari suatu grup yang juga

merupakan grup disebut grup bagian (subgrup).

Definisi 2.4.8

Misal G adalah grup.Himpunan bagian tak kosong H⊆Gdisebut grup bagian

(subgrup)dari G jika dan hanya jika H juga merupakan grup dengan operasi yang

sama yang didefinisikan di G.

Teorema 2.7

Diberikan ( ) adalah grup dan H⊆G. Himpunan bagianH merupakan grup

bagian dari G jika dan hanya jika

(i) Htak kosong.

(ii) H tertutup terhadap operasi diG: (∀ ∈ ) ∈ .

(iii) H tertutup terhadap invers: (∀ ∈ ) ∈ .

Bukti:

( ) Asumsikan H adalah grup bagian dari G. Dari definisi grup bagian, terdapat

himpunan tak kosong H. Juga dari H merupakan grup bagian, operasi di G pasti

merupakan operasi pada H, maka H tertutup terhadap operasi di G. Sehingga

setiap elemen di H pasti memiliki invers di H agar H menjadi grup, jadi H tertutup

terhadap invers.

(←) Diberikan H yang memenuhi tiga sifat di atas.Akan ditunjukkan bahwa H

adalah grup bagian dari G, yaituH adalah grup dengan operasi di G.

Karena operasi bersifat asosiatif pada grup G dan H⊆G, maka operasi

tersebut pasti bersifat asosiatif pada H, dan dari (iii) setiap elemen di H memiliki

invers di H. Harus dibuktikan bahwa Hmemiliki elemen identitas terhadap operasi

.

Karena H tak kosong, maka ada ∈ . Dari (iii) terdapat ∈ . Dari (ii)

∈ , atau ∈ . Untuk setiap ∈ , , maka

merupakan elemen identitas di dalam H. JadiH adalah grup dengan operasi di

G, makaH merupakan grup bagian dari G. ∎


37

Contoh 2.20

Diberikan grup ( ). Apakah himpunan H = {0, 4, 8, 12} merupakan

grup bagian dari ( )?

JelasH ∅.Tabel Cayley elemen-elemen 0, 4, 8, 12 dengan operasi :

Terlihat bahwaH tertutupterhadap . Setiap elemen memiliki invers dalam

H yaitu dan . Jadi, H tertutup terhadap

invers.Dengan Teorema 2.7, H merupakan grup bagian dari .

6. Koset

Dalam pembahasan di bawah ini, G adalah grup dan H adalah grup bagian

dari G.

Definisi 2.4.9

Untuk setiap a∈G, himpunan * ∈ +disebutkoset kiridari H di G

dan * ∈ + disebut koset kanan dari H di G.

Contoh 2.21

Diberikan grup ( ), dan * + adalah grup bagian dari G.

Koset-koset kiri dari H di G adalah:

* + * + * + * +

* + * + * + * +

* + * + * + * +.


38

Teorema 2.8

Misalkan G adalah grup dan H adalah grup bagian dari G.

(i) Untuk setiap a∈G, .

(ii) Untuk setiap a, b∈G, berlaku atau ∩ ∅.

(iii) ⋃ ∈ G.

Bukti:

(i) Misalkan a∈G. Akan ditunjukkan bahwa koset memiliki kardinalitas yang

sama dengan H. Akan dicari fungsi bijektif dari Hke .

Didefinisikan dengan ( ) untuk setiap ∈ .

Untuk menunjukkan bahwa f injektif, dimisalkan ∈ dengan ( )

( ), yaitu . Karena ∈ , dengan hukum kanselasi diperoleh

. Jadi f fungsi injektif.

Untuk menunjukkan bahwa f surjektif, dimisalkan ∈ . Maka

untuk suatu ∈ . Selanjutnya ( ) . Jadi f surjektif.Dengan

demikian f bijektif.Jadi .

(ii) Akan dibuktikan: jika ∩ ∅maka .

Ambil sebarang ∈ , sehingga untuk suatu ∈ . Karena

∩ ∅, maka ada ∈ ∩ , sehingga dan

untuk suatu ∈ . Maka

( )

( ).

Karena k, h, q∈H dengan H adalah grup bagian dari G, maka ∈ .

Berarti ( ) ∈ . Jadi ⊆ .

Ambil sebarang ∈ , sehingga untuk suatu ∈ . Karena

∩ ∅, maka ada ∈ ∩ , sehingga dan

untuk suatu ∈ . Maka

( )

( ) .


39

Karena h, k, q∈H dengan H adalah grup bagian dari G, maka ∈ .

Berarti ( ) ∈ . Jadi ⊆ .

Karena ⊆ dan ⊆ , maka .

(iii) Diketahui ∈ . Untuk setiap ∈ , ,sehingga ∈ . Jadi

⊆ ⋃ ∈ . Karena setiap koset adalah himpunan bagian dari G,

maka⋃ ∈ ⊆ . Dengan demikian ⋃ ∈ .∎

Definisi 2.4.10

Diberikan grup . Grup bagian Hdalam disebutnormal jika koset kiri sama

dengan koset kanan, yaitu jika untuk setiap ∈ . Dilambangkan

dengan .

Contoh 2.22

Dengan menggunakan Contoh 2.21, koset-koset kanan dari H di G adalah:

* + * + * + * +

* + * + * + * +

* + * + * + * +.

Karena koset kirisama dengan koset kanan, maka H adalah grup bagian normal

dari G.

7. Homomorfisma

Definisi 2.4.11

Diberikan dua grup (G, ) dan (K, ⊗).Fungsi f : G K disebut homomorfisma

(grup) jika ( ) ( )⨂ ( ) untuk setiap ∈ Jika homorfisma f

bijektif dari G ke K, maka f disebut isomorfisma (grup),danG dan

Kdikatakanisomorfis, dengan lambang .

Contoh 2.23

Fungsi yang didefinisikan dengan ( ) ( ) merupakan

homomorfisma darigrup ( )ke grup( ).

Misalkan ∈ . Maka


40

, ∈ , ≤

, ∈ , ≤ sehingga

( ) ( ) ( ) ( )

( ) ( )( ) ( ) ( ) ( ) ( ).

Jadi ( ) ( ) ( ), maka f adalah homomorfisma.

8. Grup Khusus

Ada beberapa grup-grup khusus yang akan dijelaskan dibawah ini.

a. Grup Permutasi

Definisi 2.4.12

Diberikan himpunan tak kosong A. Permutasi dariA adalah fungsi bijektif

dari A ke A.

Contoh 2.24

Misalkan himpunan bilangan bulat . Fungsi f : didefinisikan dari

( ) (penjumlahan biasa) adalah permutasi dari . Harus ditunjukkan

bahwa fungsi fbijektif.

Misalkan ∈ dengan ( ) ( ). Dari definisi fdiperoleh ,

sehingga didapat . Jadif adalah fungsi injektif.

Misalkan untuk setiap ∈ , terdapat elemen ∈ dengan ( )

, karena ( ) ( ) ( ) .Oleh karena itu f adalah fungsi

surjektif. Jadi fungsi f bijektif,sehingga fungsi f adalah permutasi dari .

Teorema 2.9

Untuk setiap himpunan tak kosong A, himpunan

{ adalah permutasi dari A}

adalah grup dengan operasi komposisi fungsi. Grup disebut Grup Simetrik pada

A.


41

Bukti:

Diberikan himpunan tak kosong A, dan adalah himpunan semua permutasi

dari A. Jika ∈ , makaf dan merupakan permutasi dari A, ( ) ⊆

( ),sehingga terdefinisi sebagai fungsi dari A ke A. Kemudian karena

fungsi f dan merupakan fungsi yang bijektif, maka juga fungsi yang

bijektif. Jadi ∈ .

Akan ditunjukkan merupakan grup terhadap operasi komposisi fungsi

dengan menggunakan definisi Grup.

(i) Misalkan ∈ dan ∈ . Maka

( ( ))( ) (( )( )) . ( ( ))/ ( )( ( )) (( ) )( ).

Dengan demikian terbukti operasi komposisi fungsi bersifat asosiatifpada .

(ii) Fungsi dengan ( ) untuk setiap ∈ adalah fungsi bijektif.

Jadi ∈ . Untuk setiap ∈ dan ∈ berlaku

( )( ) ( ( )) ( )dan ( )( ) ( ( )) ( ).

Jadi . Dengan demikian ∈ merupakan elemen identitas

terhadap operasi komposisi fungsi.

(iii) Akan ditunjukkan bahwa setiap ∈ memiliki invers. Didefinisikan fungsi

dengan ( ) jika dan hanya jika ( )

Akan ditunjukkan bahwa terdefinisi dengan baik. Karena f surjektif, maka

untuk setiap ∈ , ada ∈ dengan ( ). Jika ada dua elemen

∈ dimana ( ) dan ( ) , ini mengatakan bahwa ( )

( ). Karena f injektif, maka . Jadi adalah fungsi dari A ke A.

Jika ada ∈ dengan ( ) ( ) , maka ( ) dan ( )

.Karenaf merupakan fungsi,maka . Oleh karena itu injektif.Misalkan

∈ , maka ( ) ∈ sehingga ( ) . Maka surjektif.Dengan

demikian bijektif.Jadi ∈ .

Akan ditunjukkan bahwa adalah invers dari f.Misal ∈ , maka ada ∈

dengan ( ) dan ( ) . Tetapi jika ( )maka ( ) ,

sehingga

( )( ) ( ( )) ( ) ( )dan


42

( )( ) ( ( )) ( ) ( ).

Karena , maka merupakan invers dari f. Oleh karena itu

setiap elemen dari memiliki invers di .Jadi merupakan grup terhadap

operasi komposisi fungsi.∎

Definisi 2.4.13

Suatu grup bagian dari grup Simetrik untuk himpunan tak kosong A,

disebut grup permutasi.

Contoh 2.25

Diberikan himpunan semua bilangan real .Fungsif :

didefinisikan ( ) untuk setiap ∈ adalah fungsi yang bijektif, maka ∈

.Misal * +, dengan ε adalah fungsi identitas pada , maka ⊆ . Akan

ditunjukkan bahwa G grup bagian dari dengan menggunakan tabel Cayley.

Jelas bahwa G merupakan himpunan tak kosong, dan dari tabel ditunjukkan

bahwa G tertutup terhadap operasi komposisi fungsi dan invers.Jadi G adalah grup

bagian dari sehinggaG merupakan grup permutasi.

Contoh 2.26

Grup Simetrik adalah grup semua permutasi dari himpunan * +,

dengan elemen-elemen:

.

/ .

/

.

/ .

/


43

.

/ .

/

.

/ .

/

.

/ .

/

.

/ .

/

.

/ .

/

.

/ .

/

.

/ .

/

.

/ .

/

.

/ .

/

.

/ .

/

Tabel Cayley dari grup tersebut dengan operasi komposisi fungsi adalah

sebagai berikut:


44


45

Perhatikanpersegi dengan titik sudut 1, 2, 3, 4.Unsur-unsur dapat

ditafsirkan sebagai rotasi searah jarum jam dari persegi tersebut mengelilingi titik

pusatnya.

Sebelum rotasi Sesudah rotasi

: rotasi ( )

: rotasi9

: rotasi18

: rotasi 27

Gambar 2.2 Rotasi persegi searah jarum jam

1 2

3 4

1 2

3 4

1 2

3 4

3 1

4 2

4 3

2 1

1 2

3 4

1 2

3 4

2 4

1 3


46

Unsur-unsur dapat ditafsirkan sebagai refleksi terhadap sumbu

dan diagonalpersegi tersebut.

Sebelum refleksi Sesudah refleksi

: Refleksi terhadap

sumbumendatar

: Refleksi terhadap

sumbutegak

: Refleksi terhadap

diagonal utama

: Refleksi terhadap

antidiagonal

Gambar 2.3 Refleksipersegi terhadap sumbu dan diagonal

1 2

3 4

1 2

3 4

3 4

1 2

2 1

4 3

1 2

3 4

1 2

3 4

1 3

2 4

4 2

3 1


47

Himpunan * + merupakan grup bagian dari grup

simetrik

* +:

(i) Tebel Cayley dari himpunan dengan operasi komposisi fungsi adalah

sebagai berikut:

Jadi bersifat tertutup terhadap operasi komposisi fungsidi .

(ii) Setiap elemen di memiliki invers di , yaitu:

.

Jadi T tertutup terhadap invers.

Jadi merupakan grup bagian dari grup simetrik .

Grup bagian tersebut disebut Grup Dihedral berorde 8,dandilambangkan dengan

.

Simetri dari sebuah bangun datar adalah fungsi dari ke yang membawa

bangun itu ke dirinya sendiri dan mempertahankan jarak.Contoh: segitiga

mempunyai simetri, yaitu 3 rotasi dan 3 refleksi, sedangkan persegi mempunyai

simetri, yaitu 4 rotasi dan 4 refleksi.Himpunan semua simetri dari suatu

bangundatar merupakan grup terhadap operasi komposisi fungsi.Grup


48

Dihedral adalah grup berorde yang terdiri dari semua simetri bangun datar

berbentuk segibanyak beraturan.

Teorema 2.10(Teorema Lagrange)

Jika G grup berhingga, dan H adalah grup bagian dari G, maka |H| habis

membagi |G|.

Bukti:

Diasumsikan G adalah grup berhingga dan H adalah grup bagian dari G. Dari

Teorema 2.8, ⋃ ∈ . Karena G berhingga, maka

∪ ∪ ∪

Manurut Teorema 2.8, setiap dua koset adalahsama atau saling asing. Oleh

karena itu dapat dihilangkan koset yang berulang, sehingga terdapat gabungan

koset saling asing

∪ ∪ ∪ dimana ≤ .

Dengan Teorema 2.1 dan Teorema 2.8, diperoleh

Karena r adalah bilangan bulat positif, maka dapat disimpulkan habis

membagi . ∎

Definisi 2.4.14

Diberikan grup G dengan elemen identitas , grup bagian Hdari G, dan grup

bagian normal , dengan ∩ * +. GrupG disebut perkalian semi-

langsungdari dan , dengan notasi ,

jika * ∈ ∈ +.

Contoh 2.27


49

Akan ditunjukkan bahwa grup simetrik

{ .

/ .

/ .

/ .

/

.

/ .

/}

dengan elemen identitas merupakan perkalian semi-langsung darihimpunan

* +dan * + dimana ∩ * +.

(i) Akan dibuktikan bahwa merupakan grup bagian dari .

Tabel Cayley dari himpunan dengan operasi komposisi fungsi adalah

sebagai berikut:

Jadi bersifat tertutup terhadap operasi komposisi fungsi di .

Setiap elemen di memiliki invers di , yaitu:

Jadi tertutup terhadap invers.


Akan dibuktikan bahwa merupakan grup bagian dari .

Tabel Cayley dari himpunan dengan operasi komposisi fungsi adalah

sebagai berikut:

Jadi bersifat tertutup terhadap operasi komposisi fungsi di .

Setiap elemen di memiliki invers di , yaitu:


50

Jadi tertutup terhadap invers.


(ii) Dengan menggunakan Definisi 2.4.10, akan ditunjukkan bahwa normal.

* +

* +

* +

* +

* +

* +

Karena koset kiri sama dengan koset kanan, maka grup bagian normal.

(iii) Dengan menggunakan tabel Cayley, diperoleh adalah sebagai berikut:

Dari tabel Cayley tersebut dapat dilihat bahwa .

Jadi, merupakan perkalian semi-langsung dari dan .

b. Aksi Grup Pada Himpunan

Definisi 2.4.15

Diberikan grup G dan himpunan S. Grup G dikatakan beraksi pada

himpunanSjika terdapat fungsi

yaitu(∀ ∈ )(∀ ∈ ) ( ) ∈ yang memenuhi

(i) untuk setiap s ∈ S (dimana e adalah elemen identitas dari grup G).

(ii) ( ) ( )untuk setiap ∈ dan ∈ .


51

Contoh 2.28

Diberikan merupakan grup permutasi dari suatu himpunanX. Maka

beraksi pada , dengan definisi

( )untuk setiap ∈ dan ∈ .

(i) Untuk elemen identitas ∈ dan ∈ , berlaku ( ) .

(ii) Untuk setiap ∈ dan ∈ , berlaku

( ) ( )( ) ( ( )) ( ( )) ( ).


52

BAB III

MINI-SUDOKUDAN KLASIFIKASINYA

A. Mini-Sudoku

Sudoku adalah suatu permainan yang berpola dengan aturan yang telah

ditetapkan.Pada umumnya Sudoku merupakan persegiyang terdiri dari kotak

dan persegi bagianyang terdiri dari kotak yang harus diisi dengan angka 1

sampai dengan 9 pada setiap baris dan kolomnya.Sudoku telah dikembangkan

dalam berbagai bentuk dan ukuran.Sudoku tidak hanya dapat diisi dengan angka,

tetapi juga dapat diisi dengan huruf, warna, bentuk atau apapun.Pada Makalah ini

akan dibahas Sudoku yang terdiri dari kotak, yang biasa disebut mini-

Sudoku.

Ada beberapa istilah yang sering digunakan dalam mini-Sudoku.Seluruh area

terdiri dari baris dan kolom yang memisahkan setiap kotak menjadi individu dari

mini-Sudoku. Pada mini-Sudokuberukuran , sebuah wilayah berukuran

disebut persegi bagian (blok) yang juga diisi dengan tepat satu angka 1 sampai

4.Aturan Satu dalam mini-Sudokuberbunyi:Setiap baris, setiap kolom, dan

setiap blok berisi tepat satu angka 1 sampai dengan 4.

Proses pemecahan mini-Sudoku adalah mengisi kotak kosong. Kadang-

kadang cukup jelas angka berapa yang harus diisikan. Penggemar yang menikmati

pemecahan mini-Sudoku secara manual dapat memilih diantara banyak taktik,

namun ada dua cara dasar yang dapat digunakan untuk memecahkannya. Pertama,

mencari kotak yang kosong yang paling terbatas, yaitu baris, kolom, atau blok

yang sudah cukup banyak terisi. Dengan cara pertama, kemungkinan untuk

mengisi angka yang salah akan diperkecil. Kedua, mencari di mana angka tertentu

dapat ditemukan di kolom, baris, atau blok tertentu, misalnya angka 3 lebih tepat

untuk diisi pada baris ke 2, karena angka 3 sudah berada pada baris 1 dan 3.Jika

salah dalam mengisi persegi-persegi tersebut, maka mini-Sudoku menjadi tidak

terpecahkan. Untuk memperbaikinya, pemain harus mundur untuk


53

menemukan dimana letak kesalahannya. Kesalahan biasa terjadi karena

kemungkinan lain terabaikan.

Misalnya diberikan mini-Sudoku berukuran 4 × 4 sebagai berikut:

Dengan menggunakan AturanSatu, ada banyak cara untuk mengisi mini-Sudoku

tersebut. Salah satu cara adalah dengan dengan mengisiblokkiri atas dengan 1, 2,

3, dan 4. Tetapi blok tersebut dapat diisi dengan banyak cara. Ada 4! = 24 cara

untuk mengisi blok tersebut. Pastikan bahwa blok pertama itu telah terisi seperti

berikut:

Kotak-kotak lainnya ditentukan oleh Aturan Satudan pilihan entri untuk dua

kotak yang ditandai dengan *. Dua kotak tersebut dapat diisi secara bebas,tetapi

angkanya harus berbeda, sehingga ada 4 3 = 12 cara untuk memilih angka untuk

mengisinya.

Berikut adalah 12 kemungkinan mengisi sisa kotak kosong pada contoh di

atas:


54

Untuk memudahkan dalam pembahasan, 12 kemungkinan tersebut diberi

label , , , , , , , , , , , dan . Ada 24 cara untuk

mengisiblok kiri atas. Kemudian ada 12 cara untuk mengisi blok sisanya. Jadi ada

cara berbeda untuk mengisi mini-Sudoku.

B. Simetri Baris dan Simetri Kolom

Apakah 12 mini-Sudoku di atas benar-benarberbeda satu sama lain? Dengan

menukarkan dua kolom terakhir pada akan dihasilkan . Demikian pula

dengan menukarkan dua baris terbawah akan dihasilkan . Jadi, mini-

Sudoku berbeda hanya karena pertukaran baris dan/atau

kolom.Mini-Sudoku tersebut pada dasarnyasama, ataudapat dikatakan mereka

ekivalen.Sama halnya, dan juga ekivalen.

Tetapi apakah dan ekivalen atau apakah dan ekivalen?Harus

dipahami terlebih dahulu apa yang dimaksud dengan “ekivalen” dan untuk itu

diperlukan pemahaman mengenai himpunan Simetri mini-Sudoku.Dengan

menukarkan dua baris mini-Sudoku bagian bawah akandihasilkan mini-Sudoku

yang lain. Operasi pertukaran dua baris itu disebutsimetri mini-Sudoku, yang

merupakan fungsi bijektif dari himpunan semua mini-Sudoku ke dirinya sendiri.

Jika simetri mini-Sudoku tersebut dinotasikan dengan , maka ( ) ,

( ) , ( ) , dan seterusnya. Pertukaran dua kolom terakhir dari

mini-Sudoku juga adalah simetri mini-Sudoku, yang dinotasikan dengan .


55

Mengkomposisikan dua simetri akan menghasilkan simetri yang lain. Sebagai

contoh, menukarkan dua baris bawah, dilanjutkan menukarkan dua kolom

terakhir, juga merupakan simetrimini-Sudoku, yang dapat ditulis sebagai .

Simetri yang tidak mengubah semua mini-Sudoku disebut simetri identitas, dan

dinotasikan dengan id.Setiap simetri memiliki simetri invers ,sedemikian

sehingga id. Sebagai contoh, ,sebabdengan menukar dua

baris bawah mini-Sudoku dua kali, akan dihasilkan mini-Sudoku semula. Untuk

setiap tiga simetri mini-Sudoku berlaku( ) ( ), karena komposisi

fungsi bersifat asosiatif.Jadi himpunan semua simetri mini-Sudoku adalah grup

terhadap komposisi simetri (fungsi).

Jika K adalah suatu grup simetri mini-Sudoku (yaitugrup bagian dari grup

semua simetri mini-Sudoku), maka dua mini-SudokuX dan Ydikatakanekivalen-

Kjikamini-Sudoku yang satu dapat diperoleh dari yang lain dengan

menggunakansuatu simetri di K, yaitu ( ) untuk suatu ∈K. Karena K adalah

grup dengan elemen identitas ∈ , maka untuk setiap mini-Sudoku berlaku

( ). Jadi relasi tersebut bersifat refleksif. Karena K adalah grup, maka

setiap ∈ memiliki invers, yaitu ∈ . Akibatnya untuk setiap mini-Sudoku

X dan Y berlaku jika ( )untuk suatu ∈ ,maka ada ∈ sedemikian

sehingga ( ) ( ( )) ( )( ) ( ) . Jadi relasi tersebut

bersifat simetrik.Misalkan X berelasi dengan Y, berarti ada ∈ sedemikian

sehingga ( ),danY berelasi dengan Z, berarti ada ∈ sedemikian

sehingga ( ). Maka ( ) ( ( )) ( )( ) ( ) di

mana ∈ , yaitu berelasi dengan .Dengan demikian relasi tersebut

bersifat transitif.Jadi relasiini merupakan relasi ekivalensi.Himpunan semua mini-

Sudoku yang ekivalen-KdenganX disebut kelas ekivalen-Kyang memuatX. Setiap

mini-Sudoku termuat dalam kelas ekivalensi-Ktertentu.Dapat dikatakan bahwa

grup K beraksi pada himpunan mini-Sudoku.

Jika diberikan suatumini-Sudoku,dengan mudah dapatdibentuk mini-Sudoku

yang baru.Sebagai contoh, baris pertama ditukar dengan baris kedua dan dua baris

bagian bawah tidak diubah. Contoh lain, baris 1 dipindahke baris 3, baris 3 ke

baris 2, baris 2 ke baris 4, dan baris 4 ke baris 1.


56

Karena ada 4 baris dalam mini-Sudoku, maka himpunan simetri baris dapat

dipandang sebagai grup bagianR dari grup simetrik .Tetapi tidak semua

permutasi baris merupakan simetrimini-Sudoku. Sebagai contoh, permutasi yang

mengubah baris 1 ke baris 2, baris 2 ke baris 3,baris 3 ke baris 1dan baris ke 4

tetap, akan mengubah menjadi

yang bukanmini-Sudoku. Dengan demikian R isomorfis dengan suatu grup

bagian sejatidari .

Grup bagian sejati tersebut adalah grup dihedral , yaitu grup semua

simetridari suatu persegi. Dengan melihat gambar persegi dibawah ini yang titik-

titik sudutnya adalah baris-baris dari mini-Sudoku terlihat bahwa R isomorfis

dengan grup dihedral .

Grup terdiri dari 8 simetri yaitu: 4 rotasi masing-masing dengan sudut

rotasi dan ,dan 4 refleksiterhadap sumbu yang ditunjukkan oleh

garis putus-putus pada gambar di atas.Dengan demikian, menukar dua baris

teratas dari mini-Sudokubersesuaian denganmerefleksi persegi di atas terhadap

sumbu diagonal yangmelalui titik sudut Baris 3 dan Baris 4. Rotasi searah

jarum jam dari persegi di atas bersesuaian dengan simetri mini-Sudoku yang

mengubah Baris 1 ke Baris 3, Baris 3 ke Baris 2, Baris 2 ke Baris 4 dan Baris 4 ke

Baris 1. Rotasi searah jarum jam bersesuaian dengan simetri mini-Sudoku

Baris 1

Baris 4 Baris 2

Baris 3


57

yang mengubah Baris 1 ke Baris 2, Baris 2 ke Baris 1, Baris 3 ke Baris 4,

danBaris 4 ke Baris 3.

Dengan mengganti kata baris menjadi kata kolom, akan dihasilkan grup

simetri kolom mini-Sudoku dengan notasi C, yang juga isomorfis dengan . Jika

∈ dan ∈ , maka menerapkan kemudian vpada mini-Sudoku akan

memberikan hasil yang sama dengan menerapkan v kemudian . Dengan kata lain

simetri baris komutatifdengan simetri kolom.Denganmengkombinasikan 8 simetri

baris dan 8 simetri kolomakan didapatkan 64 simetri berbeda yang membentuk

grup perkalian langsung R×Cyang isomorfis dengan .

Mini-Sudoku dan adalah ekivalen-C tetapi tidak ekivalen-R, sebab

diperoleh dari dengan menukar dua kolom terakhir pada , tetapi dengan

menukarkan dua baris pada tidak dapat dihasilkan , dan sebaliknya.Mini-

Sudoku dan adalah ekivalen-R tetapi tidak ekivalen-C, sebab

diperoleh dari dengan menukar dua baris terakhir pada ,tetapi dengan

menukarkan dua kolom pada tidak dapat dihasilkan ,dan sebaliknya. Mini-

Sudoku termuat dalam kelasekivalen-R×C yang sama. Begitu

pula dengan dan .

Akan ditunjukkan bahwa tidak ekivalen-R×Cdengan atau , yaitu tidak

ada kombinasi simetri baris dan kolom yang menghasilkan atau


58

jikaditerapkan pada .Untuk itu setiap baris dan kolom dari mini-

Sudokudikaitkan dengan suatu partisi dari himpunan * + yaitu:

{* + * +} {* + * +} {* + * +}.

Notasi { } berarti diperbolehkan untuk menukar urutan angka-angkanya.

Contohnya, {* + * +}, {* + * +}, {* + * +}, dan

{* + * +}semuanya merupakan cara berbeda untuk menulis .

Partisi yang dikaitkan dengan suatu baris atau kolom adalah{* + *

+}dengan entri-entri dari baris atau kolom yang bersangkutan dimasukkan untuk

mengganti .Contohnya, setiap baris berkaitan dengan , dan setiap kolom

berkaitan dengan . Setiap baris berkaitan dengan , tetapi kolom-

kolom berkaitan dengan berturut-turut dari kiri ke kanan. Baris-

baris berkaitan dengan berturut-turut dari atas ke bawah, tetapi setiap

baris berkaitan dengan .

Untuk sembarang mini-SudokuX, dengan menerapkan Aturan Satumini-

Sudoku pada dua blok bagian atas berakibat bahwa partisi yang berkaitan dengan

Baris 1 dengan Baris 2 adalah sama. Begitu pula untuk Baris 3 dan Baris 4,

Kolom 1 dan Kolom 2, dan Kolom 3 dan Kolom 4. Jadi, Xberkaitan dengan dua

partisi baris dan dua partisi kolom,sehingga terbentuk pasangan terurut , - dari

pasangan(tidak terurut) dari partisi-partisi,yang disebut tipe partisi dari X.Entri

pertama berisi dua partisi baris, dan entri kedua berisi dua partisi kolom.

Contohnya,

, - (* + * +),, - (* + * +) , - (* + * +)

dimana(* + * +) sama dengan (* + * +), tetapi (* + * +) tidak

sama dengan (* + * +). Secara khusus, , - , - , - , -,

, - , - , - , -, dan , - , - , - , -.

Partisi tersebut berguna karena menunjukkan bagaimana perubahannya

terhadap simetrimini-Sudoku yang diterapkan. Contohnya, dengan menerapkan 8

simetri baris di R pada kolom pertama dari , yaitu:

1. Mengubah Baris 1 ke Baris 4, Baris 4 ke Baris 1, Baris 2 ke Baris 3, Baris

3 ke Baris 1.


59


4 ke Baris 2.

3. Mengubah Baris 3 ke Baris 4, Baris 4 ke Baris 3, kemudian Baris 1 dan

Baris 2 tetap.

4. Mengubah Baris 1 ke Baris 2, Baris 2 ke Baris 1, kemudian Baris 3 dan

Baris 4 tetap.


4 ke Baris 1.


4 ke Baris 3.


3 ke Baris 1.

8. Baris 1, Baris 2, Baris 3, dan Baris 4 tetap.

maka dihasilkan 8 kolom berbeda:

Namun, masing-masing kolom ituberkaitan dengan partisi yang sama, yaitu

. Jadi, partisi kolom invarian terhadap simetri baris, dan demikian pula partisi

baris invarian terhadap simetri kolom.Partisi kolom hanya dipermutasi oleh

simetri kolom, dan partisi baris hanya dipermutasi oleh simetri baris.

Dengan demikian diperoleh aturan seperti berikut:

Aturan 1: Jika mini-Sudoku X dan Yekivalen-R C, maka tipe partisi dari X

dan Y adalah sama, yaitu , - , -.

Karena tipe partisi , , dan berbeda, maka di antara ketiga mini-

Sudoku tersebut tidak ada yang ekivalen-R C.

Dalam hal ini terdapat koleksi objek-objek (dalam kasus ini mini-Sudoku)

dan konsep ekivalensi, seringkali dari aksi suatu grup (dalam kasus ini grup

R×C).Tujuannya adalah untuk menentukan objek-objek mana yang


60

ekivalen.Strategi umum untuk masalah tersebut adalah mengaitkan suatu invarian

(sesuatu yang sama untuk objek-objek yang ekivalen) ke setiap objek. Tipe partisi

adalah invarian untuk mini-Sudoku, seperti dinyatakan oleh Aturan 1.Invarian

yang ideal mudah dikomputasikan dan dapat menentukan secara lengkap apakah

dua objek ekivalen atau tidak (dalam hal ini dikatakan bahwa invarian itu

lengkap).

Ketika mendefinisikan konsep“tipe partisi”, hal itu dilakukan dengan hati-

hati, untuk memastikan bahwa tipe partisi adalah invarian.Secara khusus,, - perlu

didefinisikan sebagai pasangan terurut dari pasangan yang tidak terurut. Misalnya

diberikan

Perhatikan bahwa dan ekivalen-R× C,karena yang satu dapat diperoleh

dari yang laindengan cara menukarkan dua kolom kiri dan dua kolom kanan.

Aturan 1memastikan bahwa D dan memiliki tipe partisi yang sama, yaitu

, - (* + * +) , -. Seandainya, - didefinisikan sebagai pasangan

terurut dari pasangan yang terurut,tidak akan diperolehkesamaan yang diinginkan,

yaitu , - , -.

C. Simetri Persegi

Mini-Sudoku memiliki bentuk persegi dan setiap simetri dari persegi adalah

juga simetri dari mini-Sudoku.


61

Sebagai contoh, refleksi mini-Sudoku terhadap sumbu mendatarakan

menghasilkan mini-Sudoku yang lain. Tetapi simetri ini adalah simetri baris yang

menukarkan baris 1 dengan baris 4, dan baris 2 dengan baris 3.Demikian

pula,refleksi mini-Sudoku terhadap sumbu tegakadalah simetri kolom.Bagaimana

refleksiterhadap diagonal?Misalkan adalah refleksimini-Sudoku terhadap

diagonal utama (dari kiri atas ke kanan bawah). Sebagai contoh,refleksi terhadap

diagonal utama dari adalah seperti berikut

Karena, ( )- (* + * +), maka mini-Sudoku tersebut tidak ekivalen-

R× C dengan . Dengan kata lain, simetri bukan anggotaR×C. Karena ,

maka , dan * + merupakan grup simetri mini-Sudoku yang

isomorfis dengan .

Rotasi searah jarum jam adalah hasil dari refleksi terhadapdiagonal

utamadilanjutkanrefleksi terhadap sumbu tegak. Menerapkan dua refleksi tersebut

dengan urutan sebaliknya akan menghasilkan rotasi . Jadi, rotasi dan

adalah komposisi dan simetri di R×C. Rotasi adalah komposisi

refleksiterhadap sumbu mendatardan refleksi terhadap sumbu tegak (dengan salah

satu urutan). Jadi, rotasi ini berada di R×C. Secara khusus, rotasi tersebut adalah

hasil dari membalikkan urutan baris dan kolom. Contohnya,rotasi sebesar ,

dan searah jarum jam akan menghasilkan mini-Sudoku:

dengantipe partisi , - , - = (* + * +) dan , - = (* + * +). Karena

, -= (* + * +), baik maupun tidak ekivalen- dengan . Ini berarti

simetri yang bersesuaian, yaitu rotasi 90° dan 270°, tidak berada di .Mini-


62

Sudoku dapat diperoleh dari dengan membalikkan urutan dari baris dan

kolom:

Masih ada satu simetri di yang belum didiskusikan, yaitu refleksi terhadap

sumbu diagonal yang lain (dari kanan atas ke kiri bawah), yang dilambangkan

dengan .Diketahui tipe partisi dari , - (* + * +) Tipe

partisidari ( )adalah, ( )- (* + * +). Maka ( ) tidak ekivalen-R

Cdengan . Tetapi ( ) dapat diperolehdari dengan rotasi 180°(refleksi

terhadap sumbu mendatar kemudian sumbu tegak) kemudian refleksi terhadap

diagonal utama :

Jadi simetri tidak berada di tetapi dapat disusun dari simetri di dan

.

Perhatikan bahwa menukar baris dan kolom dari setiap mini-

Sudoku.Refleksi mengubah baris 1 menjadi kolom 1, baris 2 menjadi kolom 2,

dan seterusnya.Hal ini berarti bahwa menukar simetri baris dan simetri

kolom.Contohnya, jika ∈ adalah simetri baris yang menukarkan baris 1 dan

baris 2, maka adalah simetri kolom yang menukarkan kolom 1 dan

kolom 2. Persamaan ini dapat ditulissebagai , yang menunjukkan bahwa

walaupun tidak komutatif dengan elemen-elemen dari R×C,tetapi menghasilkan

pertukaran baris dan kolom.Akibatnya, tiap simetri yang dapat diperoleh dengan

komposisi dan elemen-elemen dariR×C dalam urutan apapun dapat ditulis dalam

bentuk dengan ∈ . Simetri itu juga dapat ditulis dalam bentuk dengan


63

∈ dimana dan adalahsama, kecualidalam hal penggantian baris dan

kolom.

Terdapat 64 simetri di R ×C, dan 64 simetri lainnyadengan

bentuk dimana ∈ . Dalam kategori kedua terdapat rotasi 90° dan rotasi

270°, serta refleksi terhadap sumbu diagonal. Simetri-simetri ini membentuk grup

Hdengan order 128. Karena tidak komutatif dengan semuaelemen dari R × C,

makaH bukanlah perkalian langsung dari R×Cdan * +.

TetapiHmerupakanperkalian semi-langsung darikedua grup tersebut, yaitu:

( ) .

Dua mini-Sudoku X dan Y adalah ekivalen-H jika yang satu dapat diperoleh

dari yang lain dengan menerapkan suatu simetri di H.

Karena grup H beraksi pada mini-Sudoku, maka grup H juga beraksi pada

tipe-tipe partisi dari mini-Sudoku. Berdasarkan Aturan 1, simetri di H yang juga

di R×C, membiarkan tipe-tipe partisi tidak berubah. Karena menukar baris dan

kolom dari mini-Sudoku, simetri ini menukar partisi baris dan partisi kolom yang

berkaitan dari setiap tipe partisi. Contohnya, Karena , - (* + * + ),

maka , ( )- (* + * +).

Mengingat sifat dari simetri , dapat dikatakan ( ) adalah transpos dari X

dan , ( )-adalah transpos dari , -. Jadi dapat digunakan notasi , - , ( )-,di

mana, - diperoleh dari , - dengan menukar kedua komponennya. Jika mini-

Sudoku X dan Y adalah ekivalen-H, maka X adalah ekivalen-R ×C denganY atau

dengan ( ). Karena itu dapat dikatakan bahwa , - dan , - adalah ekivalen-H

jika , - , -atau , - , - . Didefinisikan , - adalah kelas ekivalen- dari

, -. Sekarang terdapat dua ekivalen-H, yaitu ekivalen-H dari mini-Sudoku dan

ekivalen-H dari tipe partisi. Dengan Aturan 1, diperoleh

Aturan 2: Jika mini-Sudoku X dan Y ekivalen-H, maka , - , - .

Karena , - (* + * +), , -

(* + * +), dan

, - (* + * +), maka di antara ketigamini-Sudoku tidak ada

yang ekivalen-H.


64

D. Simetri Pelabelan-Ulang

Masih ada satu cara untuk menghasilkan mini-Sudoku darimini-Sudoku yang

diberikan, yaitu dengan carapelabelan-ulang (relabeling), yang dilakukandengan

menerapkan permutasi padahimpunan * +. Misalnyadengan menukar angka

1 dan 2 pada mini-Sudoku akandihasilkan:

Karena , - (* + * +), maka tidak ekivalen-Hdengan , sehingga

simetri pelabelan-ulang dengan menukarkan angka 1 dan 2 ini, tidak berada di H.

Karena ada permutasi yang berbeda dari himpunan * +yang

membentuk grup , maka terdapat grupLyang bersesuaian,yaitu grup simetri

pelabelan ulang dari mini-Sudoku, yang isomorfis dengan .

Simetri pelabelan-ulang menukar urutan dari partisi dan . Contohnya,

menukarkan 1 dan 2 akan membawa ke , ke dan ke . Maka dari itu,

simetri pelabelan-ulang ini membawa

[ ] (* + * +) ke [ ] (* + * +).

Contoh lainnya, misalkan simetri pelabelan-ulang ∈ yang memetakan 2 ke

3, 3 ke 4, 4 ke 2, dan 1 tetap, yaitu .

/. Simetri ini akan

mengubah ke , ke dan ke .Masing-masing dari permutasi dan

berasal dari 4 simetri pelabelan-ulang di L. Maka dua tipe partisi dikatakan

ekivalen-L jika salah satu dapat diperoleh dari yang lain dengan suatu permutasi

dari dan . Tidak ada elemen dari H yang memiliki pengaruh yang sama pada

semua mini-Sudoku seperti simetri pelabelan-ulang .

/. Ambil

mini-Sudoku dengan tipe partisi (* + * +),misalnya . Kemudian yang

beraksi pada mini-Sudoku tersebut akan menghasilkan mini-Sudoku dengan tipe

partisi (* + * +). Dari Aturan 2, mini-Sudoku baru ini tidak ekivalen-


65

Hdengan mini-Sudoku semula, jadi tidak berada di H. Semua simetri di Ltidak

berada di H,kecuali simetri identitas.Hal itu dibuktikan sebagai berikut.

Jika ∈ dan ∈ , maka menerapkan terlebih dahulu kemudian

menerapkan , memberikan hasil yang sama dengan menerapkan terlebih

dahulu kemudian menerapkan , dengan kata lain . Jadi jika ∈ ∩ ,

maka berada di pusat dari L, yaitu ( ) * ∈ (∀ ∈ ) +. TetapiL

isomorfis dengan , yang pusatnya hanya berisi elemen identitas.

E. Dua Kelas Ekivalensi Mini-Sudoku

Karena simetri pelabelan-ulang komutatif dengan simetri di H, maka

mengombinasikan semua simetri mini-Sudoku akan menghasilkan sebuah grup

yang isomorfisdengan perkalian langsung dari H dan L. Oleh karena itu,

didefinisikanGrup Simetri mini-Sudoku,yaitu grup .

Grup ini memiliki order . Karena G

memuat semua simetri mini-Sudoku,maka mengatakan mini-Sudoku X dan Y

adalah ekivalen-G dapat diganti dengan mengatakan bahwa kedua mini-Sudoku

tersebut adalah ekivalen.

Misal M adalah himpunan dari 16 sel dari persegi berukuran . Maka

mini-Sudoku adalah fungsi * + yang memenuhi Aturan Satu.

Elemen ∈ yang beraksi pada mini-Sudoku mengirimkan ke . GrupH

adalah grup bagian dari grup ,yaitu grup semua fungsi bijektif dari M ke

dirinya sendiri, dan elemen ∈ yang beraksi pada mini-Sudoku mengirimkan

ke . Grup Htelah dipilih secara hati-hati,sehingga tetap

memenuhiAturan Satu.Karena itu dapat dikatakan bahwa setiap elemen dari

Hmengawetkan mini-Sudoku.Kebalikannya juga benar,yaitu setiap elemen dari

yang mengawetkan mini-Sudoku berada di H. Jadi, G merupakan himpunan

semua simetri mini-Sudoku yang dapat diperoleh dari permutasi sel dan permutasi

label.

Seperti grup H dan L, grup G beraksi pada mini-Sudoku dan juga pada tipe

partisi. Didefinisikan , - adalah kelas ekivalen-Gdari , -. Dengan kata lain,

, - , - jika dan hanya jika , - ekivalen-Ldengan, - atau dengan, -


66

Aturan 3: Jika mini-Sudoku X dan Y ekivalen, maka , - , - .

Sekarang dapat dilihat apakah adalah ekivalen. Jika sebuah mini-

Sudoku X ekivalen dengan , maka (denganAturan 3),, - adalah

(* + * +), (* + * +), (* + * +), (* + * +), (* + * +)

atau (* + * +).Jadi bukan atau , jadi tidak ekivalen dengankedua

mini-Sudoku tersebut.

Jika X ekivalen dengan , maka (denganAturan 3), - adalah (* + * +),

(* + * +), (* + * +), (* + * +), (* + * +) atau

(* + * +). Karena , - (* + * +), mungkin bahwa dan

ekivalen. Jika kedua mini-Sudoku ini benar ekivalen, maka tipe partisi dari dan

menyarankan bagaimana membuat simetri yang dapat membawa yang satu ke

yang lain. Harus ada simetri pelabelan-ulang yang menukarkan dan , kemudian

dikomposisikan dengan , dan mungkin dikomposisikan dengan simetri baris dan

kolom:

, - (* + * +) (* + * +) (* + * +) , -.

Kenyataannya, dengan memilih simetri pelabelan-ulang ∈ yang

menukarkan 2 dan 3, tidak diperlukan simetri baris dan kolom:

Hal tersebut menunjukkan bahwa dan adalah ekivalen, dan karena itu

, , , , , , , dan berada dalam kelas ekivalensi yang sama.

Karena dan tidak ekivalen, harus ada kelas ekivalensi kedua yang

memuat , , , dan .

Teorema 3.1

Terdapat tepat dua kelas ekivalensi dari mini-Sudoku, yaitu:

Semuamini-Sudoku dengan tipe partisi:

(* + * +) (* + * +)(* + * +)


67

(* + * +) (* + * +)(* + * +)

Semuamini-Sudoku dengan tipe partisi:

(* + * +) (* + * +)(* + * +)

(* + * +) (* + * +)(* + * +)

Bukti:

Telah diperlihatkan bahwa terdapat sekurang-kurangnya dua kelas ekivalensi yang

berbeda.Misal X adalah mini-Sudoku. Dengan menerapkan simetri pelabelan-

ulang yang sesuai, bagian kiri atas dari X dapat disusun sebagai berikut

.

JadiX ekivalen dengan satu dari 12 mini-Sudoku , , , , , , , ,

, , , dan . Dari pembahasan di atas, X ekivalen dengan salah satu atau

. Jika X ekivalen dengan , maka tipe partisinya adalah seperti yang

digambarkan pada , dan jika X ekivalen dengan , maka tipe partisinya adalah

seperti yang digambarkan pada . ∎

Terdapat tepat 24 mini-Sudoku yang ekivalen-Ldengan masing-masing dari

, , , , , , , , , , dan , maka dari itu ada

mini-Sudoku di dan mini-Sudoku di .

Karena tipe partisi yang berada pada masing-masing kelas ekivalensi sudah

diketahui, maka kebalikan dari Aturan 3 juga berlaku, yaitu mini-Sudoku X dan

Yadalah ekivalen jika dan hanya jika , - dan , - ekivalen.

Perhatikan bahwa mini-Sudoku , , dan memiliki dua atau empat

entri yang berbeda pada diagonal utama, sedangkan mini-Sudoku , , , ,

, , dan memiliki tepat tiga entri berbeda pada diagonal utama. Karena

setiap mini-Sudoku ekivalen-Ldengan salah satu dari 12 itu, dan jumlah entri yang

berbeda pada diagonal utama tidak berubah oleh simetri pelabelan-ulang, dapat

diketahuisuatu mini-Sudoku X berbeda di kelas ekivalensiyang mana. Jika X

memiliki dua atau empat entri yang berbeda pada diagonal utama, maka

Xekivalen-Ldengan , , atau , sehinggaX berada di . Jika X memiliki

tiga entri berbeda pada diagonal utama, maka X ekivalen-Ldengan salah satu dari


68

, , , , , , , , sehinggaX berada di . Oleh karena itu, entri dari

diagonal utamaX cukup untuk menentukan kelas ekivalensi dari X.


69

BAB IV

PENUTUP

A. Kesimpulan

Mini-Sudoku adalah permainan Sudoku berukuran dengan blok

berukuran yang mengikuti Aturan Satu, yaitu setiap baris, setiap kolom,

dan setiap blok berisi tepat satu angka 1 sampai dengan 4. Terdapat banyak cara

berbeda untuk mengisi mini-Sudoku, tetapi tidak semua cara itu menghasilkan

mini-Sudoku yang benar-benar berbeda. Operasi pertukaran dua baris atau kolom,

refleksi mini-Sudoku, dan melakukan pelabelan-ulangpada mini-Sudoku

merupakan simetri-simetri mini-Sudoku.Himpunan semua simetri mini-Sudoku

adalah grup terhadap komposisi simetri (fungsi).

Himpunan simetri baris mini-Sudoku dapat dipandang sebagai grup bagian

dari grup simetrik dan himpunan semua simetri kolom mini-Sudoku dapat

dipandang sebagai grup bagian C dari grup simetrik . Dua mini-Sudoku dan

adalah ekivalen- jika mini-Sudoku yang satu dapat diperoleh dari mini-

Sudoku yang lain dengan menggunakan suatu simetri di . Setiap baris dan

kolom mini-Sudoku dikaitkan dengan suatu partisi dari himpunan * +.

Dengan menerapkan Aturan Satu pada dua blok bagian atas dari mini-

Sudokuberakibat bahwa dua partisi baris dan dua partisi kolom adalah sama,

sehingga membentuk pasangan terurut, - dari pasangan tidak terurut dari partisi-

partisi, yang disebut tipe partisidari . Jika mini-Sudoku dan ekivalen- ,

maka tipe partisi dari dan adalah sama, yaitu , - , -.

Setiap simetri dari persegi adalah simetri mini-Sudoku. Dengan

merefleksikan mini-Sudoku terhadap sumbu mendatar akan menghasilkan mini-

Sudoku yang lain, begitu pula dengan sumbu tegak. Hasil refleksi terhadap

diagonal utama,yang dilambangkan dengan ,tidak ekivalen- dengan mini-

Sudoku semula, tetapi tiap simetri dapat diperoleh dengan komposisi dan

elemen-elemen dari dalam urutan apapun sehingga membentuk grup ,

yaitu ( ) dimana * +. Dua mini-Sudoku dikatakan

ekivalen-Hjika mini-Sudoku yang satu dapat diperoleh dari mini-Sudoku yang


70

lain dengan menerapkan suatu simetri di . Sifat dari simetri diagonal utama juga

dapat dikatakan transpos dari suatu mini-Sudoku. Jika mini-Sudoku X dan Y

adalah ekivalen-H, maka ekivalen- dengan atau dengan ( ), begitu

pula dengan tipe partisinya. Didefinisikan , - adalah kelas ekivalen-Hdari , -.

Jika mini-Sudoku dan ekivalen- , maka, - , - .

Dengan menerapkan permutasi pada himpunan * +akan menghasilkan

mini-Sudoku lain yang disebut pelabelan-ulang. Terdapat 24 permutasi yang

berbeda dari himpunan * + yang membentuk grup , maka terdapat grup

Lyang bersesuaianyaitu grup simetri pelabelan-ulang mini-Sudoku. Simetri

pelabelan-ulang menukarkan urutan partisi-partisi. Semua simetri pelabelan-ulang

tidak berada di H kecuali simetri identitas, tetapi bersifat komutatif dengan simetri

di H, maka mengkombinasikan semua simetri mini-Sudoku akan menghasilkan

sebuah Grup Simetri Mini-Sudoku, yaitu grup . Karena G memuat

semua simetri mini-Sudoku, maka mengatakan mini-Sudoku X dan Y adalah

ekivalen-G dapat diganti dengan mengatakan bahwa kedua mini-Sudoku tersebut

adalah ekivalen.Grup merupakan himpunan semua simetri mini-Sudoku yang

dapat diperoleh dari permutasi sel dan permutasi label.Didefinisikan , - adalah

kelas ekivalen- dari , -. Dengan kata lain , - , - jika dan hanya jika , -

ekivalen-L dengan , - atau dengan , - . Jika mini-Sudoku X dan Y ekivalen,

maka , - , - . Terdapat tepat dua kelas ekivalensi dari mini-Sudoku, yaitu:

Semua mini-Sudoku dengan tipe partisi:

(* + * +) (* + * +)(* + * +)

(* + * +) (* + * +)(* + * +)

Semua mini-Sudoku dengan tipe partisi:

(* + * +) (* + * +)(* + * +)

(* + * +)(* + * +)(* + * +)

B. Saran

Dalam makalah ini, penulis hanya membahas ekivalensi pada mini-

Sudoku.Masih banyak hal yang dapat dibahas mengenai mini-Sudoku, misalnya

menentukan kelas ekivalensi Sudoku berukuran .


71

DAFTAR PUSTAKA

Arcos, C., et al. (2010). Mini-Sudokus and Groups.Mathematics Magazine, 83

(2): 111-122.

Davis, Tom. (2008). The Mathematics of Sudoku.

http://www.geometer.org/mathcircles/sudoku.pdf.Diakses pada 26

September 2016.

Delahaye, J. P. (2006). The Science behind Sudoku.ScientificAmerican, 294 (6):

80-87.

Dummit, D. S., dan Foote, R. M. (1991). Abstract Algebra. Englewood Cliffs: A

Simon & Schuster Company.

Eaton, Nancy. (2007). Introduction to Mathematical

Rigor.www.math.uri.edu/~eaton/NotesChapt6(3).pdf.Diakses pada 22

Juni 2017.

Felgenhauer, B., dan Jarvis, F. (2006). Mathematics of Sudoku I. Mathematical

Spectrum, 39 (1): 15-22.

Fraleigh, John B. (2003). A First Course In Abstract Algebra. New York: Addison

Wesley.

Gallian, Joseph A. (2010).Contemporary Abstract Algebra.Belmont: Brooks/Cole.

Hirofumi, Fujiwara. (2005). Dragon Sudoku.http://www.sudokudragon.com.

Diakses pada 11 Oktober 2016.

Miller, C. C. (2013). Essentials of Modern Algebra.Dulles: Mercury Learning and

Information.

Russell, E., dan Jarvis, F. (2006).Mathematics of Sudoku II.Mathematical

Spectrum, 39 (2): 54-58.

Susilo, Frans. (2012). Landasan Matematika. Yogyakarta: Graha Ilmu.


http://www.geometer.org/mathcircles/sudoku.pdf

http://www.math.uri.edu/~eaton/NotesChapt6(3).pdf

http://www.sudokudragon.com/

aplikasi teori grup dalam mengklasifikasikan mini … fileaplikasi teori grup dala}i...

Documents