1.

RELASI
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, b B}
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 R 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
pasangan terurut yang jumlah anggotanya adalah |A|.|B| .
Definisi 1.3 : Relasi pada himpunan A adalah relasi dari AxA
1

himpunan

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. A2 dan b. A3

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
Amir
Amir
Budi
Budi
Cecep

B
INF0422
INF0421
INF0221
INF0422
INF0421

Representasi relasi dengan matriks

Misalkan R adalah relasi dari A = {a1, a2, . . .,am} dan B = {b1, b2, . . .,bn}, relasi R
dapat disajikan dengan matriks M = [mij]

a
a
M
:
a

m
m

m
m
:
m

11

12

21

22

m1

m2

...
...
:
...

m
m
:
m

1n

2n

mn

Yang dalam hal ini

1, (a , b ) R
0, (a , b ) R

m
ij

Dengan kata lain, elemen matriks pada posisi (i,j) bernilai 1 jika a i dihubungkan
dengan bj dan bernilai 0 jika ai tidak dihubungkan dengan bj.
Relasi R pada table 1.3 dapat dinyatakan dengan matriks
0
1

1
1
0

0
0
0

1
0

yang dalam hal ini, a1 = Amir, a2 = Budi, a3 = Cecep, dan b1 = 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

direpresentasikan dengan graf berarah pada gambar berikut :

himpunan

{a,b,c,d}.

Sifat-sifat dari relasi biner

1. 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) R
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 mii = 1, untuk i = 1,2,...,n
1

Sedangkan graf berarah dari relasi yang bersifat refleksif dicirikan dengan adanya
gelang pada setiap simpulnya.
2. Setangkup (symmetric)
Relasi R pada himpunan A disebut setangkup jika untuk semua a,b

A, jika (a,b)

R. Sebaliknya, R disebut tak setangkup(antisymmetric) jika

untuk a,b A, jika (a,b) R dan a b maka (b,a) R
R, 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

R maka (b,a) juga R, disini (1,2) dan (2,1) R, begitu juga (2,4)
dan (4,2) R
(a,b)

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

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) R

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 mij = mji, untuk i = 1,2,...,n
1
0
1
0
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 A.
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)
R.
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 R1 dan R2 masing masing adalah relasi dari himpunan A ke himpunan
B, maka R1 R2 , R1 R2 , R1 - R2, R1 R2 juga adalah relasi dari A ke B.
Contoh 2.10.
Misalkan A = { a, b, c } dan B = { a, b, c, d }. Relasi R 1 = { (a,a), (b,b), (c,c), dan
relasi R2 = { (a,a), (a,b), (a,c), (a,d) } adalah relasi dari A ke B. kita dapat
mengkombinasikan ke dua buah relasi tersebut untuk memperoleh
R1 R2

= { (a,a) }

R1 R2

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

R1 - R 2

= { (b,b), (c,c) }

R2 R1 = { (a,b), (a,c), (a,d) }

R1 R2

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

Jika relasi R1 dan R2 masing masing dinyatakan dengan matriks MR1 dan MR2,
maka matriks yang menyatakan gabungan dan irisan dari kedua relasi tersebut
adalah
MR1 R2 = MR1 R2 dan MR1 R2 = MR1 R2

Yang dalam hal ini, operator berarti atau dan berarti dan.
Contoh 2.11.
Misalkan bahwa relasi R1 dan R2 pada himpunan A dinyatakan oleh matriks
1
R1 1
1

0
0
1

1
0

dan

0
R2 0
1

1
1
0

1
0

Maka matriks yang menyatakan MR1 R2 dan MR1 R2 adalah

M R1 R 2 M R1 M R 2

M R1 R 2 M R1 M R 2

1 1
1 1
1 1

0
1

0
0
1

0
0
0

0
1
0

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 R1 dan R2 masing masing dinyatakan dengan matriks M R1 dan M

R2

maka matriks yang menyatakan komposisi dari kedua relasi tersebut adalah
MR1 o R2 = MR1 . MR2
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 R1 dan R2 pada himpunan A dinyatakan oleh metrics
1
R1 1
0

1
0

0
0

dan

0
R2 0
1

1
0
0

1
1

Maka matriks yang menyatakan R1 o R2 adalah

M R1R 2 M R1 M R 2

2.6

(1 0) (0 0) (1 1) (1 1) (0 0) (1 0) (1 0) (0 1) (1 1)
(1 0) (1 0) (0 1) (1 1) (1 0) (0 0) (1 0) (1 1) (0 1)
(0 0) (0 0) (0 1) (0 1) (0 0) (0 0) (0 0) (0 1) (0 1)

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 A1, A2, .An adalah himpunan. Relasi n-ary R pada himpunan
himpunan tersebut adalah himpunan bagian dari A1 x A2 x x An, atau dengan
rotasi R A1 x, A2 x, .x An. himpunan A1, A2, .An disebut 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 },

10

{ 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

Amir

Matematika Diskrit

13598011

Amir

Arsitektur Komputer

13598014

Santi

Arsitektur Komputer

13598015

Irwan

Algoritma

13598015

Irwan

Struktur Data

13598015

Irwan

Arsitektur Komputer

13598019

Ahmad

Algoritma

13598021

Cecep

Algoritma

13598021

Cecep

Arsitektur Komputer

13598025

Hamdan

Matematika Diskrit

13598025

Hamdan

Algoritma

13598025

Hamdan

Struktur Data

13598025

Hamdan

Arsitektur Komputer

11

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

12

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
Amir

MatKul
Matematika Diskrit

Nilai
A

Amir

Arsitektur Komputer

Santi

Algoritma

Irwan

Algoritma

Irwan

Struktur Data

13

Irwan

Arsitektur Komputer

Ahmad

Algoritma

Cecep

Algoritma

Cecep

Arsitektur Komputer

Hamdan

Matematika Diskrit

Hamdan

Algoritma

Hamdan

Struktur Data

Hamdan

Arsitektur Komputer

Tabel 2.6.
NIM
13598011

Nama
Amir

13598014

Santi

13598015

Irwan

13598019

Ahmad

13598021

Cecep

13598025

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.

14

Tabel 2.7
NIM
13598001
13598002
13598004
13598006
13598007

Nama
Hananto
Guntur
Heidi
Harman
Karim

JK
L
L
W
L
L

Tabel 2.8
NIM
13598001
13598001
13598004
13598006
13598006
13598009
13598010

Nama
Hananto
Hananto
Heidi
Harman
Harman
Junaidi
Farizka

MatKul
Algoritma
Basisdata
Kalkulus I
Teori Bahasa
Agama
Statisitik
Otomata

Nilai
A
B
B
C
A
B
C

Tabel 2.9
NIM
13598001
13598001
13598004
13598006
13598006

Nama
Hananto
Hananto
Heidi
Harman
Harman

JK
L
L
W
L
L

MatKul
Algoritma
Basisdata
Kalkulus I
Teori Bahasa
Agama

Nilai
A
B
B
C
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.

15

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.

f
a

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

16

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.

a
b
c

4
5

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)}

17

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.

a
b
c

1
2
3

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.

18

Fungsi f dikatakan berkoreponden satu-ke-satu atau bijektif (bijection) jika ia satuke-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

19

Jika f adalah fungsi berkoresponden satu-ke-satu dari A ke B, maka kita dapat

-1

misalkan a adalah anggota himpunan A dan b adalah anggota himpunan B, maka f

-1

menemukan balikan (invers) dari f. Balikan fungsi dilambangkan dengan f

(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)}

20

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 x2 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

S
R S

a). R
b).

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
21

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:

101

a). 010

101

010

b). 010

010

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

111

R = 100

000

110

S = 011

001

dan

Tentukan matriks yang menyatakan

S
b). R S
a). R

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)}

22

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?

23