Relasi | Materi Mata Kuliah Matematika Diskrit

1.1 Pengantar

Hubungan(relationship), antara elemen himpunan dengan elemen himpunan lainnya sering dijumpai pada banyak masalah. Misalnya hubungan antara mahasiswa dengan mata kuliah yang diambil, hubungan antara bilangan genap dan bilangan yang habis dibagi 2 dan sebagainya. Di dalam bidang ilmu komputer, dapat dicontohkan hubungan antara program komputer dengan peubah yang digunakan, hubungan antara bahasa pemrograman dengan pernyataan (statement) yang sah, hubungan antara plaintext dan chipertext pada bidang kriptografi dan sebagainya (Munir,2001).

Hubungan antara elemen himpunan dengan elemen himpunan lain dinyatakan dengan struktur yang disebut relasi.

1.2 Relasi&Product Cartesian

Definisi 1.1 : untuk setiap himpunan A,B £, Perkalian kartesian (Cartesian Product) dari himpunan A dan B adalah A x B dimana {(a,b)| a A, bB}

Dapat dikatakan bahwa elemen-elemen dari AxB merupakan himpunan pasangan berurutan (order pairs). Untuk (a,b) dan (c,d) AxB maka (a,b) = (c,d) jika dan hanya jika a = c dan b = d .

Definisi 1.2 : Relasi biner R antara AxB adalah himpunan bagian dari AxB. Dinotasikan sebagai R(AxB).

Jika (a,b) R, digunakan notasi aRb yang artinya a dihubungkan dengan b oleh R, dan jika (a,b)

R, maka digunakan notasi a

b yang artinya a tidak dihubungkan dengan b oleh relasi R.

Himpunan A disebut daerah asal (domain) dari R dan himpunan B disebut daerah hasil (range) dari R.

Jika A,B adalah himpunan berhingga maka perkalian AxB menghasilkan himpunan pasangan terurut yang jumlah anggotanya adalah |A|.|B| .

Definisi 1.3 : Relasi pada himpunan A adalah relasi dari AxA

Dengan kata lain relasi pada himpunan A adalah himpunan bagian dari AxA

Contoh-contoh :

1. Misalkan A={Amir,Budi,Cecep} adalah himpunan nama mahasiswa dan B={INF0421,INF0422,INF0423,INF0424} adalah himpunan kode matkul di Manajemen Informatika, berapa jumlah anggota yang terbentuk dari AxB?

2. Misalkan P={2,4,8,9,15} dan Q={2,3,4}. Jika didefinisikan relasi R dari P ke Q dengan (p,q)R jika p habis dibagi q , bagaimana bentuk relasinya?

3. Tentukan x,y,z jika (2x,x+y,x-y-2z) = (4,-1,3)

4. Anggap A={1,2}. Tentukan a. A² dan b. A³

5. Misalkan A={1,2} dan B = {a,b}. Tunjukkan apakah pernyataan dibawah ini sama dengan AxB ?

a. E=[{1,a},{1,b},{2,a},{2,b}] c. G=[(1,a),(1,b),(2,a),(b,2)]

b. F=[{a,1}{a,2}{b,1}{b,2}] d. H=[(1,a), (2,a), (1,b), (2,b)]

6. Diberikan A={1,2},B={x,y,z} dan C={3,4}. Tentukan AxBxC dan n(AxBxC)

1.3 Representasi Relasi

Selain dengan himpunan pasangan terurut, ada banyak cara untuk merepresentasikan relasi biner. Disini hanya disajikan tiga cara yang lazim yaitu, table, matriks dan graf berarah.

Representasi relasi dengan table

Jika relasi direpresentasikan dengan table, maka kolom pertama table menyatakan daerah asal, sedangkan kolom kedua menyatakan daerah hasil

Sebagai contoh :

Table 1.3

A	B
Amir	INF0422
Amir	INF0421
Budi	INF0221
Budi	INF0422
Cecep	INF0421

Representasi relasi dengan matriks

Misalkan R adalah relasi dari A = {a₁, a₂, . . .,a_m} dan B = {b₁, b₂, . . .,b_n}, relasi R dapat disajikan dengan matriks M = [m_ij]

Yang dalam hal ini

Dengan kata lain, elemen matriks pada posisi (i,j) bernilai 1 jika a_i dihubungkan dengan b_j dan bernilai 0 jika a_i tidak dihubungkan dengan b_j.

Relasi R pada table 1.3 dapat dinyatakan dengan matriks

yang dalam hal ini, a₁= Amir, a₂ = Budi, a₃ = Cecep, dan b₁ = INF0221

Representasi relasi dengan graf berarah

Representasi dengan graph berarah (directed graph atau digraph) merupakan representasi relasi secara grafis (graph akan dibahas pada bab tersendiri). Tiap elemen himpunan dinyatakan dengan sebuah titik (simpul atau vertek), dan tiap pasangan berurutan dinyatakan dengan busur atau (arc) yang arahnya ditunjukkan dengan sebuah panah. Dengan kata lain, jika (a,b) R, maka sebuah busur dibuat dari simpul a ke simpul b. Simpul a disebut simpul asal (initial vertek) dan simpul b disebut simpul tujuan (terminal vertek).

Pasangan terurut (a,a) dinyatakan dengan busur dari simpul a ke simpul a sendiri. Busur semacam ini disebut gelang atau kalang (loop). Sebagai contoh misalnya R = {(a,a),(a,b),(b,a),(b,c),(b,d), (c,a),(c,d),(d,b)}adalah relasi pada himpunan {a,b,c,d}. R direpresentasikan dengan graf berarah pada gambar berikut :

Sifat-sifat dari relasi biner

Refleksif (reflexive)

Relasi R pada himpunan A disebut refleksif jika (a,a) R untuk setiap a A

Contoh 1:

Misalkan A = {1,2,3,4}, dan relasi R dibawah ini didefinisikan pada himpunan A, maka

a. R = {(1,1),(1,3),(2,1),(2,2),(3,3),(4,2),(4,3),(4,4)} bersifat refleksif karena terdapat elemen relasi yang berbentuk (a,a), yaitu (1,1),(2,2),(3,3),dan (4,4).

b. R = {(1,1),(2,2),(2,3),(4,2),(4,3),(4,4)} tidak bersifat reflektif karena (3,3)

Contoh 2 :

Relasi ”habis dibagi” pada himpunan bilangan bulat positif bersifat refleksif karena setiap bilangan bulat positif habis dibagi dengan dirinya sendiri, sehingga (a,a) R untuk setiap a A.

Ditinjau dari representasi relasi, relasi bersifat refleksif mempunyai matriks yang elemen diagonal utamanya semua bernilai 1, atau m_ii = 1, untuk i = 1,2,...,n

Sedangkan graf berarah dari relasi yang bersifat refleksif dicirikan dengan adanya gelang pada setiap simpulnya.

Setangkup (symmetric)

Relasi R pada himpunan A disebut setangkup jika untuk semua a,b A, jika (a,b) R, maka (b,a) R. Sebaliknya, R disebut tak setangkup(antisymmetric) jika untuk a,b A, jika (a,b) R dan ab maka (b,a)

Contoh 1:

Misalkan A={1,2,3,4} dan relasi R dibawah ini didefinisikan pada himpunan A, maka,

a. R = {(1,1),(1,2),(2,1),(2,2),(2,4),(4,2),(4,4)} bersifat setangkup karena jika (a,b) R maka (b,a) juga R, disini (1,2) dan (2,1) R, begitu juga (2,4) dan (4,2) R

b. R = {(1,1),(2,3),(2,4),(4,2)}tidak bersifat setangkup karena (3,2)

Contoh 2 :

Relasi ”habis dibagi” pada himpunan bilangan bulat positif tidak bersifat setangkup karena jika a habis dibagi b , b tidak habis dibagi a, kecuali jika a=b. Sebagai contoh, 2 habis membagi 1 tetapi 1 tidak habis membagi 2, karena itu (a,b) R tetapi (b,a)

Ditinjau dari representasi relasi, relasi yang bersifat setangkup mempunyai matriks yang elemen-elemen dibawah diagonal utama merupakan pencerminan dari elemen-elemen diatas diagonal utama, atau m_ij = m_ji, untuk i = 1,2,...,n

Sedangkan graf berarah dari relasi yang bersifat setangkup dicirikan oleh: jika ada busur dari a ke b, maka juga ada busur dari b ke a.

3. Menghantar (transitif)

Relasi R pada himpunan A disebut menghantar bilamana (a,b)

R dan (b,c)

R, maka (a,c)

R, untuk a, b, c

Contoh 2.8.

Misalkan A = { 1, 2, 3, 4 }, dan relasi R di bawah ini didefinisikan pada himpunan A, maka

a. R = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }bersifat menghantar. Lihat pada table berikut :

Pasangan berbentuk

(a,b) (b,c) (a,c)

(3,2) (2,1) (3,1)

(4,2) (2,1) (4,1)

(4,3) (3,1) (4,1)

(4,3) (3,2) (4,2)

b. R = { (1,1), (2,3), (2,4), (4,2) } maka tidak bersifat menghantar karena (2,4) dan (4,2)

R, tetapi (2,2)

R, begitu juga (4,2) dan (2,3)

R, tetapi (4,3)

Contoh 2.9.

Relasi “habis dibagi” pada himpunan bilangan bulat positif bersifat menghantar. Misalkan bahwa a habis membagi b dan b habis membagi c. maka terdapat bilangan positif m dan n sedemikian sehingga a = mb dan b = nc. Disini a = mnc, sehingga a habis membagi c. jadi, relasi “habis membagi” bersifat menghantar.

Ditinjau dari representasi relasi, relasi yang bersifat menghantar tidak mempunyai ciri khusus pada matriks representasinya. Tetapi sifat menghantar pada graf berarah ditunjukan oleh: jika ada busur dari a ke b dan dari b ke c, maka juga terdapat busur berarah dari a ke c.

2.4 Mengkombinasikan Relasi

Karena relasi biner merupakan himpunan pasangan terurut, maka operasi himpunan seperti irisan, gabungan, selisih dan beda setangkup antara dua relasi atau lebih juga berlaku. Hasil operasi tersebut juga berupa relasi. Dengan kata lain, jika R₁ dan R₂ masing – masing adalah relasi dari himpunan A ke himpunan B, maka R₁

R₂ , R₁

R₂, R₁ - R_2,R₁

R₂juga adalah relasi dari A ke B.

Contoh 2.10.

Misalkan A = { a, b, c } dan B = { a, b, c, d }. Relasi R₁ = { (a,a), (b,b), (c,c), dan relasi R₂ = { (a,a), (a,b), (a,c), (a,d) } adalah relasi dari A ke B. kita dapat mengkombinasikan ke dua buah relasi tersebut untuk memperoleh

R₁

R₂ = { (a,a) }

R₁

R₂= { (a,a), (b,b), (c,c), (a,b), (a,c), (a,d) }

R₁ - R₂= { (b,b), (c,c) }

R₂ – R₁ = { (a,b), (a,c), (a,d) }

R₁

R₂ = { (b,b), (c,c), (a,b), (a,c), (a,d) }

Jika relasi R₁ dan R₂ masing – masing dinyatakan dengan matriks M_R1 dan M_R2, maka matriks yang menyatakan gabungan dan irisan dari kedua relasi tersebut adalah

M_R1R2= M_R1R2 dan M_R1R2= M_R1R2

Yang dalam hal ini, operator “

” berarti “atau” dan “

” berarti “dan”.

Contoh 2.11.

Misalkan bahwa relasi R₁dan R₂ pada himpunan A dinyatakan oleh matriks

dan

Maka matriks yang menyatakan M_R1R2dan M_R1R2adalah

2.5 Komposisi Relasi

Cara lain mengkombinasikan relasi adalah mengkomposisikan dua buah relasi atau lebih. Komposisi relasi analog dengan komposisi fungsi.

Definisi 2.3.

Misalkan R adalah relasi dari himpunan A ke himpunan B, dan S adalah relasi dari himpunan B ke himpunan C. komposisi R dan S, dinotasikan dengan R o S, adalah relasi dari A ke C yang didefinisikan oleh

R o S = { (a,c)}│ a

A, c

C, dan untuk beberapa b

B, (a,b)

R dan (b,c)

S }

Contoh 2.12.

Misalkan R = { (1,2), (1,6), (2,4), (3,4), (3,6), (3,8) } adalah relasi dari himpunan { 1, 2, 3 } ke himpunan { 2, 4, 6, 8 } dan S = { (2,u), (4,s), (4,t), (6,t), (8,u) } adalah relasi dari { 2, 4, 6 } ke himpunan { s, t, u }. Maka komposisi relasi R dan S adalah R o S = { (1,u), (1,t), (2,s), (2,t), (3,s), (3,t), (3,u) }

Jika relasi R₁dan R₂ masing – masing dinyatakan dengan matriks M_R1 dan M _R2, maka matriks yang menyatakan komposisi dari kedua relasi tersebut adalah

M_{R1 o R2}= M_R1. M_R2

Yang dalam hal ini operator “.” Sama seperti pada perkalian matriks biasa, tetapi dengan mengganti tanda kali dengan “

” dan tanda tambah dengan “

”.

Contoh 2.13.

Misalkan bahwa relasi R₁dan R₂ pada himpunan A dinyatakan oleh metrics

dan

Maka matriks yang menyatakan R₁o R₂adalah

2.6 Relasi n-ary

Relasi biner hanya menghubungkan antara dua buah himpunan. Relasi yang lebih umum menghubungkan lebih dari dua buah himpunan. Relasi tersebut dinamakan relasi n-ary (baca: ener). Jika n = 2, maka relasinya dinamakan relasi biner (bi = 2). Relasi n-ary mempunyai terapan penting didalam basisdata.

Definisi 2.4.

Misalkan A₁, A₂, ….A_n adalah himpunan. Relasi n-ary R pada himpunan – himpunan tersebut adalah himpunan bagian dari A₁ x A₂ x … x A_n, atau dengan rotasi R

A₁ x, A₂ x, ….x A_n. himpunan A₁, A₂, ….A_ndisebut daerah asal relasi dan n disebut derajat.

Contoh 2.14.

Misalkan

NIM = { 13598011, 13598014, 13598015, 13598019, 13598021, 13598025 }

Nama = { Amir, Santi, Irwan, Ahmad, Cecep, Hamdan }

MatKul = { Matematika Diskrit, Algoritma, Struktur Data, Arsitektur Komputer }

Nilai = { A, B, C, D, E }

Berturut – turut adalh himpunan Nomor Induk Mahasiswa, himpunan nama – nama mahasiswa, himpunan nama – nama mata kuliah, dan himpunan nilai mata kuliah. Relasi MHS yang terdiri dari 4-tupel (NIM, Nama, MatKul, Nilai) mempresentasikan hubungan antara nomor induk mahasiswa, namanya, mata kuliah yang diakbilnya, dan nilai mata kuliah. Satu contoh relasi yang bernam MHS adalah

MHS = { 13598011, Amir, Matematika Diskrit, A },

{ 13598011, Amir, Arsitektur Komputer, B },

{ 13598014, Santi, Arsitektur Komputer, D },

{ 13598015, Irwan, Algoritma, C },

{ 13598015, Irwan, Struktur Data, C },

{ 13598015, Irwan, Arsitektur Komputer, B },

{ 13598019, Ahmad, Algoritma, E },

{ 13598021, Cecep, Algoritma, A },

{ 13598021, Cecep, Arsitektur Komputer, B },

{ 13598025, Hamdan, Matematika Diskrit, B },

{ 13598025, Hamdan, Algoritma, A, B },

{ 13598025, Hamdan, Struktur Data, C },

{ 13598025, Hamdan, Arsitektur Komputer, B }

Relasi MHS di atas juga dapat ditulis dalam bentuk table 2.4.

Table 2.4

NIM	Nama	MatKul	Nilai
13598011 13598011 13598014 13598015 13598015 13598015 13598019 13598021 13598021 13598025 13598025 13598025 13598025	Amir Amir Santi Irwan Irwan Irwan Ahmad Cecep Cecep Hamdan Hamdan Hamdan Hamdan	Matematika Diskrit Arsitektur Komputer Arsitektur Komputer Algoritma Struktur Data Arsitektur Komputer Algoritma Algoritma Arsitektur Komputer Matematika Diskrit Algoritma Struktur Data Arsitektur Komputer	A B D C C B E A B B A C B

Basisdata (database) adalah kumpulan table. Salah satu model basisdata adalah model basisdata relasional (relation database). Pada basisdata relasional, satu tabel menyatakan satu relasi. Setiap kolom pada tabel disebut atribut. Daerah asal dari atribut adalah himpunan tempat semua anggota atribut tersebut berada. Setiap tabel pada basisdata diimplementasikan secara fisik sebagai sebuah file. Suatu baris data pada tabel menyatakan sebuah record, dan setiap atribut menyatakan sebuah file. Dengan kata lain, secara fisik basisdata adalah kumpulan file, sedangkan file adalah kumpulan record, setiap record terdiri atas sejumlah field.

Teori basisdata didasarkan pada konsep relasi n-ary. Pembahasan teori basisdata harus dilepas pada implementasi fisiknya.

Atribut khusus pada tabel yang mengidentifikasikan secara unik elemen relasi disebut kunci (key). Pada contoh 2.4 di atas, NIM merupakan kunci. Atribut nama bukan atribut kunci karena orang yang berbeda mungkin mempunyai nama yang sama.

Operasi yang dilakukan terhadap basisdata dilakukan dengan perintah pertanyaan yang disebut perintah query. Satu contoh query misalnya,

“tampilkan semua mahasiswa yang mengambil mata kuliah matematika diskrit”

“tampilkan daftar nilai mahasiswa dengan NIM = 13598015”

“tampilkan daftar mahasiswa yang terdiri atas NIM dan mata kuliah yang diambil”

Pada hakekatnya, query terhadap basisdata relasion dapat dinyatakan secara abstrak dengan oprasi pada relasi n-ary. Ada beberapa operasi yang dapat digunakan, diantaranya adalah seleksi, proyeksi, dan join.

Seleksi

Opreasi seleksi memilih baris tertentu dari suatu tabel yang memenuhi persyaratan tertentu.

Operasi:

Contoh 2.15.

Misalkan untuk relasi MHS kita ingin menampilkan daftar mahasiswa yang mengambil mata kuliah matematika diskrit. Operasi seleksinya adalah

_{MatKul = “matematika diskrit”} (MHS)

Yang menghasilkan tupel.

(13598011, Amir Matematika Diskrit, A) (13598025, Hamdan, Matematika Diskrit, B).

Proyeksi

Operasi proyeksi memiliki kolom tertentu dari suatu tabel. Jika ada beberapa baris yang sama nilainya, maka hanya diambil satu kali.

Operator:

Contoh 2.16.

Operasi proyeksi

_{nama, MatKul, nilai}(MHS)

Menghasilkan tabel 2.5. sedangkan operasi proyeksi

_{NIM, Nama}(MHS)

Menghasilkan tabel 2.6.

Tabel 2.5.

Nama	MatKul	Nilai
Amir Amir Santi Irwan Irwan Irwan Ahmad Cecep Cecep Hamdan Hamdan Hamdan Hamdan	Matematika Diskrit Arsitektur Komputer Algoritma Algoritma Struktur Data Arsitektur Komputer Algoritma Algoritma Arsitektur Komputer Matematika Diskrit Algoritma Struktur Data Arsitektur Komputer	A B D C C B E B B B A C B

Tabel 2.6.

NIM	Nama
13598011 13598014 13598015 13598019 13598021 13598025	Amir Santi Irwan Ahmad Cecep Hamdan

Join

Operasi join menggabungkan dua buah tabel menjadi satu bila kedua tabel mempunyai atribut yang sama. Sebagai contoh, suatu tabel mengandung NIM, Nama, Jenis Kelamin, dan tabel ini mengandung NIM, Nama, MatKul, Nilai. Gabungan keduanya menghasilkan tabel baru yang mengandung atribut NIM, Nama, Jenis Kelamin, MatKul, dan Nilai.

Operator:

Contoh 2.17.

Misalkan relasi MHS 1 dinyatakan dengan tabel 2.7 dan relasi MHS 2 dinyatakan dengan tabel 2.8. opersi join

_{NIM, Nam} MHS 1, MHS 2)

Menghasilkan tabel 2.9.

Tabel 2.7

NIM	Nama	JK
13598001	Hananto	L
13598002	Guntur	L
13598004	Heidi	W
13598006	Harman	L
13598007	Karim	L

Tabel 2.8

NIM	Nama	MatKul	Nilai
13598001	Hananto	Algoritma	A
13598001	Hananto	Basisdata	B
13598004	Heidi	Kalkulus I	B
13598006	Harman	Teori Bahasa	C
13598006	Harman	Agama	A
13598009	Junaidi	Statisitik	B
13598010	Farizka	Otomata	C

Tabel 2.9

NIM	Nama	JK	MatKul	Nilai
13598001	Hananto	L	Algoritma	A
13598001	Hananto	L	Basisdata	B
13598004	Heidi	W	Kalkulus I	B
13598006	Harman	L	Teori Bahasa	C
13598006	Harman	L	Agama	A

2.7 Fungsi

Fungsi adalah jenis khusus dari relasi. Definisi fungsi adalah sebagai berikut:

Definisi 2.5

Misalkan A dan B himpunan. Relasi biner f dari A ke B merupakan suatu fungsi jika untuk setiap elemen a di dalam A terdapat satu elemen tunggal b di dalam B sedemikian sehingga (a,b) Є f. kita tulis f(a)=b. Jika f adalah fungsi dari A ke B, kita menuliskan f : A à B yang artinya f memetakan A ke B.

Gambar 2.3 merepresentasikan fungsi dari A ke B.

Jika f adalah fungsi dari A ke B, A disebut daerah asal (domain) dari f dan B disebut daerah hasil ( range/codomain) dari f. Jika f(a) = b, maka b dinamakan bayangan (image) dari a dan a dinamakan prabayangan (pre-image) dari b.

Gambar 2.3 fungsi f memetakan A ke B

Contoh 2.18

Relasi

f = { (1,u),(2,v),(3,w) }

dari A = {1,2,3} ke B = {u,v,w} adalah fungsi dari A ke B. Daerah asal dari f adalah A dan daerah hasil adalah B.

Contoh 2.19.

Relasi

f = { (1,u),(2,v),(3,w)}

dari A = {1,2,3,4} ke B = {u,v,w} bukan fungsi dari A ke B, karena daerah asal dari f{1,2,3} tidak sama dengan B.

Contoh 2.20.

Relasi

f = { (1,u),(2,v),(3,w) }

dari A = {1,2,3 }ke B = {u,v,w} bukan fungsi dari A ke B, karena dipetakan ke dua buah elemen B, yaitu u dan v ( ingat definisi fungsi atas ).

Contoh 2.21.

Relasi

f = {(1,u),(2,u),(3,v)}

Dari A = {1,2,3} ke B = {u,v,w}adalah fungsi dari A ke B, meskipun u merupakan bayangan dari dua elemen A.

Fungsi f dikatakan satu-ke-satu (one-to-one) atau injektif (injective) jika tidak ada dua elemen himpunan A yang memiliki bayangan sama. Dengan kata lain, jika a dan b adalah anggota himpunan A, maka f(a) ≠ f(b) bilamana a ≠ b. Gambar 2.4 mengilustrasikan fungsi satu-ke-satu.

Gambar 2.4 fungsi satu-ke-satu

Contoh 2.22.

Relasi

f = {(1,w),(2,u),(3,v)}

dari A = {1,2,3} ke B = {u,v,w,x} adalah fungsi satu-ke-satu,

Relasi

f = {(1,w),(2,u),(3,v)}

dari A = {1,2,3} ke B = {u,v,w} juga fungsi satu-ke-satu, tetapi relasi f = {(1,u),(2,u),(3,v)}

dari A ={1,2,3} ke B = {u,v,w} bukan fungsi satu-ke-satu, karena f(1) = f(2)=u.

Fungsi f dikatakan dipetakan pada (onto) atau surjektif (surjective) jika setiap elemen himpunan B merupakan bayangan dari satu atau lebih elemen himpunan A. Dengan kata lain, fungsi f adalah pada bila semua elemen B merupakan daerah hasil dari f. Fungsi f disebut fungsi pada himpunan B. Gambar 2.5 mengilustrasikan fungsi pada.

Gambar 2.5 fungsi pada

Contoh 2.23.

Relasi

f = {(1,u),(2,u),(3,v)}

dari A = {1,2,3} ke B = {u,v,w} bukan fungsi pada, karena w tidak termasuk ke dalam daerah hasil dari f.

Relasi

f = {(1,w),(2,u),(3,v)}

dari A = {1,2,3} ke B = {u,v,w}merupakan fungsi pada, karena semua elemen B termasuk ke dalam daerah hasil f.

Fungsi f dikatakan berkoreponden satu-ke-satu atau bijektif (bijection) jika ia satu-ke-satu dan juga fungsi pada.

Contoh 2.24.

Relasi

f = {(1,u),(2,w),(3,v)}

dari A = {1,2,3} ke B = {u,v,w} adalah fungsi yang berkorespoden satu-ke-satu, karena f adalah fungsi satu-ke-satu maupun fungsi pada.

Gambar 2.6 memperlihatkan perbedaan antara fungsi satu-ke-satu tetapi bukan pada, fungsi pada tetapi bukan satu-ke-satu, bukan fungsi satu-ke-satu maupun fungsi pada, dan bukan fungsi.

Gambar 2.6 Perbedaan empat tipe korespondensi

Jika f adalah fungsi berkoresponden satu-ke-satu dari A ke B, maka kita dapat menemukan balikan (invers) dari f. Balikan fungsi dilambangkan dengan f ^-1. misalkan a adalah anggota himpunan A dan b adalah anggota himpunan B, maka f ^-1(b) = a jika f(a) = b.

Contoh 2.25

Relasi

f = {(1,u),(2,w),(3,v)}

dari A = {1,2,3} ke B = {u,v,w} adalah fungsi yang berkoresponden satu-ke-satu. Balikan fungsi f adalah

f ^-1= {(u,1),(w,2),(v,3)}

karena fungsi merupakan bentuk khusus dari relasi, kita juga dapat melakukan komposisi dari dua buah fungsi. Misalkan g adalah fungsi dari himpunan A ke himpuna B, dan f adalah fungsi dari himpunan B ke himpuna C. Komposisi f dan g, dinotasikan dengan f o g, adalah fungsi dari A ke C yang didefinisikan oleh

(f o g)(a) = f (g(a))

Contoh 2.26.

Diberikan fungsi

g = {(1,u),(2,u),(3,v)}

yang memetakan A = {1,2,3} ke B {u,v,w}, dan fungsi f = {(u,y),(v,x),(w,z)}

yang memetakan B = {u,v,w} ke C {x,y,z}. Fungsi komposisi dari A ke C adalah

f o g = {(1,y),(2,y),(3,x)}

Soal Latihan

1. A = {2,3,4} ke B = {0,1,2,3} yang dalam hal ini pasangan terurut (a,b) Є R jika dan hanya jika a > b.

2. Tuliskan anggota dari relasi R pada {1,2,3,4} yang didefinisikan oleh (x,y) Є R jika x² ≥ y.

3. Nyatakan relasi R ={(1,2),(2,1),(3,3),(1,1),(2,2)} pada X = {1,2,3} dalam bentuk tabel, matriks, dan graf berarah.

4. Untuk tiap relasi pada {1,2,3,4} berikut, tentukan apakah ia refleksif, setangkup, tak-setangkup, dan menghantar.

a) {(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

b) {(2,4),(4,2),}

c) {(1,1),(2,2),(3,3),(4,4)}

d) {(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)}

5. Tentukan apakah relasi R pada himpunan orang bersifat refleksif, setangkup, tak-setangkup, dan / atau menghantar, yang dalam hal ini (a,b) Є R jika dan hanya jika

a) a lebih tinggi daripada b

b) a dan b lahir pada hari yang sama

c) a mempunyai nama pertama yang sama dengan b

6. Misalkan R adalah relasi {(1,2),(1,3),(2,3),(2,4),(3,1)} dan S adalah relasi {(2,1),(3,1),(3,2),(4,2),(4,2)}. Tentukan S o R dan R o S.

7. Misalkan R = {(1,2),(2,3),(3,4)} dan S = {(1,1),(1,2),(2,1),(2,2),(2,3),(3,1),(3,2),(3,4)} adalah relasi dari {1,2,3} ke {1,2,3,4}. Tentukan

a). R S

b). RS

c). R – S

d). S – R

e). R S

8. Misalkan R adalah relasi pada himpunan orang yang terdiri dari pasangan (a,b) yang dalam hal ini a adalah ayah dari b. Misalkan S adalah relasi pada himpunan orang yang terdiri dari pasangan (a,b) yang dalam hal ini a dan b adalah saudara kandung. Nyatakan R o S.

9. Nyatakan pasangan terurut dari relasi pada {1,2,3} yang berkoresponden dengan matriks berikut:

a).

b).

10. Gambarkan graf berarah dari relasi yang dinyatakan oleh matriks pada soal nomor 9.

11. Misalkan bahwa relasi R dan S pada himpuna A dinyatakan oleh matriks

R =

dan S =

Tentukan matriks yang menyatakan

a). R S

b). R S

c). R o S

12. jika diberikan

g = {(1,b),(2,c),(3,a)}

adalah fungsi dari A = {1,2,3} ke B = {a,b,c,d} dan

f = {(a,x),(b,x),(c,z),(d,w)}

adalah fungsi dari B ke C = {w,x,y,z}, tuliskan f o g sebagai himpunan pasangan terurut.

13. misalkan f adalah fungsi dari X = {0,1,2,3,4,5} ke X yang didefinisikan oleh

f(x) = 4x mod 6

Tuliskan f sebagai himpunan pasangan terurut. Apakah f satu-ke-satu atau pada?

Semoga bermanfaat & terima kasih :)

_Welcome to 2lisan Cyber_

Relasi | Materi Mata Kuliah Matematika Diskrit

1 komentar:

Link

Google Search

Visitors

Noxious Project