relasi dan fungsi (2013)
TRANSCRIPT
-
8/18/2019 Relasi Dan Fungsi (2013)
1/107
Matriks, Relasi, dan Fungsi
Matematika Diskrit
1
-
8/18/2019 Relasi Dan Fungsi (2013)
2/107
2
Matriks
• Matriks adalah adalah susunan skalar elemen-elemen dalam bentuk baris dan kolom.
• Matriks A yang berukuran dari m baris dan n kolom (m × n)adalah:
=
mnmm
n
n
aaa
aaa
aaa
A
21
22221
11211
• Matriks bujursangkar adalah matriks yang berukuran n × n.
• Dalam praktek, kita lazim menuliskan matriks dengan notasi
ringkas A !aij".
Contoh 1. Di ba#ah ini adalah matriks yang berukuran $ × %:
=
&11$
%'&
*'2
A
-
8/18/2019 Relasi Dan Fungsi (2013)
3/107
$
• Matriks simetri adalah matriks yang aij a ji untuk setiap i dan j.
Contoh 2. Di ba#ah ini adalah +ontoh matriks simetri.
−
−
&2$%
2*
$$
%2
• Matriks zero-one (*1) adalah matriks yang setiap elemennyahanya bernilai * atau 1.
Contoh 3. Di ba#ah ini adalah +ontoh matriks *1:
1**1
****
111*
*11*
-
8/18/2019 Relasi Dan Fungsi (2013)
4/107
%
Relasi
• elasi biner R antara himpunan A dan B adalah himpunan bagian dari A × B.
• otasi: R ⊆ ( A × B).
• a R b adalah notasi untuk (a, b) ∈ R, yang artinya a dihubungankan dengan b oleh R
• a R b adalah notasi untuk (a, b) ∉ R, yang artinya a tidakdihubungkan oleh b oleh relasi R.
• /impunan A disebut daerah asal (domain) dari R, danhimpunan B disebut daerah hasil (range) dari R.
-
8/18/2019 Relasi Dan Fungsi (2013)
5/107
'
Contoh 3. Misalkan
A 0mir, udi, 3e+ep4, B 056221, 562'1, 56$%2, 56$2$4
A × B 0(mir, 56221), (mir, 562'1), (mir, 56$%2),(mir, 56$2$), (udi, 56221), (udi, 562'1),(udi, 56$%2), (udi, 56$2$), (3e+ep, 56221),
(3e+ep, 562'1), (3e+ep, 56$%2), (3e+ep, 56$2$) 4
Misalkan R adalah relasi yang menyatakan mata kuliah yangdiambil oleh mahasis#a pada 7emester 8anjil, yaitu
R 0(mir, 562'1), (mir, 56$2$), (udi, 56221),
(udi, 562'1), (3e+ep, 56$2$) 4
- Dapat dilihat bah#a R ⊆ ( A × B),- A adalah daerah asal R, dan B adalah daerah hasil R.
- (mir, 562'1) ∈ R atau mir R 562'1
- (mir, 56$%2) ∉ R atau mir R 56$%2.
-
8/18/2019 Relasi Dan Fungsi (2013)
6/107
Contoh 4. Misalkan P 02, $, %4 dan Q 02, %, &, 9, 1'4. ika
kita de;inisikan relasi R dari P ke Q dengan
( p, q) ∈ R jika p habis membagi q
maka kita peroleh
R 0(2, 2), (2, %), (%, %), (2, &), (%, &), ($, 9), ($, 1') 4
• elasi pada sebuah himpunan adalah relasi yang khusus
• elasi pada himpunan A adalah relasi dari A × A. • elasi pada himpunan A adalah himpunan bagian dari A × A.
-
8/18/2019 Relasi Dan Fungsi (2013)
7/107
Contoh 5. Misalkan R adalah relasi pada A 02, $, %, &, 94 yangdide;inisikan oleh ( x, y) ∈ R jika x adalah ;aktor prima dari y.Maka
R 0(2, 2), (2, %), (2, &), ($, $), ($, 9)4
-
8/18/2019 Relasi Dan Fungsi (2013)
8/107
&
Representasi Relasi
1. Representasi Relasi dengan Diagram Panah
mir
udi
3e+ep
56221
562'1
56$%2
56$2$
2
$
%
2
%
&
9
1'
2
$
%
&
9
2
$
%
&
9
A B
P
Q A A
-
8/18/2019 Relasi Dan Fungsi (2013)
9/107
9
. Representasi Relasi dengan Tabel
•
-
8/18/2019 Relasi Dan Fungsi (2013)
10/107
1*
3. Representasi Relasi dengan Matriks
• Misalkan R adalah relasi dari A 0a1, a2, =, am4 dan B 0b
1, b
2, =, b
n4.
• elasi R dapat disajikan dengan matriks M !mij",
b1 b2 … bn
M
mnmm
n
n
mmmm
mmm
mmm
a
a
a
21
22221
11211
2
1
yang dalam hal ini
∉
∈=
Rba
Rbam
ji
ji
ij),(,*
),(,1
-
8/18/2019 Relasi Dan Fungsi (2013)
11/107
11
Contoh 6. elasi R pada 3ontoh $ dapat dinyatakan dengan
matriks
1***
**111*1*
dalam hal ini, a1 mir, a2 udi, a$ 3e+ep, dan b1 56221,b2 562'1, b$ 56$%2, dan b% 56$2$.
elasi R pada 3ontoh % dapat dinyatakan dengan matriks
**11*
11***
**111
yang dalam hal ini, a1 2, a2 $, a$ %, dan b1 2, b2 %, b$ &,
b% 9, b' 1'.
-
8/18/2019 Relasi Dan Fungsi (2013)
12/107
12
4. Representasi Relasi dengan Graf Berarah
• elasi pada sebuah himpunan dapat direpresentasikan se+ara
gra;is dengan graf berarah (directed graph atau digraph)• 8ra; berarah tidak dide;inisikan untuk merepresentasikan
relasi dari suatu himpunan ke himpunan lain.
• >iap elemen himpunan dinyatakan dengan sebuah titik
(disebut juga simpul atau vertex), dan tiap pasangan terurutdinyatakan dengan busur (arc)
• ika (a, b) ∈ R, maka sebuah busur dibuat dari simpul a kesimpul b. 7impul a disebut simpul asal (initial vertex) dan
simpul b disebut simpul tujuan (terminal vertex).
• ?asangan terurut (a, a) dinyatakan dengan busur dari simpula ke simpul a sendiri. usur sema+am itu disebut gelang ataukalang (loop).
-
8/18/2019 Relasi Dan Fungsi (2013)
13/107
1$
Contoh 7. Misalkan R 0(a, a), (a, b), (b, a), (b, c), (b, d ), (c, a),
(c, d ), (d , b)4 adalah relasi pada himpunan 0a, b, c, d 4.
R direpresentasikan dengan gra; berarah sbb:
a b
c d
-
8/18/2019 Relasi Dan Fungsi (2013)
14/107
1%
ifat!sifat Relasi "iner
• elasi biner yang dide;inisikan pada sebuah himpunanmempunyai beberapa si;at.
1.Refleksif (reflexive)
• elasi R pada himpunan A disebut refleksif jika (a, a) ∈ R untuk setiap a ∈ A.
• elasi R pada himpunan A tidak re;leksi; jika ada a ∈ A sedemikian sehingga (a, a) ∉ R.
-
8/18/2019 Relasi Dan Fungsi (2013)
15/107
1'
Contoh #. Misalkan A 01, 2, $, %4, dan relasi R di ba#ah ini
dide;inisikan pada himpunan A, maka
(a) elasi R 0(1, 1), (1, $), (2, 1), (2, 2), ($, $), (%, 2), (%, $),(%, %) 4 bersi;at re;leksi; karena terdapat elemen relasi yang
berbentuk (a, a), yaitu (1, 1), (2, 2), ($, $), dan (%, %).
(b) elasi R 0(1, 1), (2, 2), (2, $), (%, 2), (%, $), (%, %) 4 tidak
bersi;at re;leksi; karena ($, $) ∉ R.
Contoh $. elasi @habis membagiA pada himpunan bilangan bulat positi; bersi;at re;leksi; karena setiap bilangan bulat positi; habis
dibagi dengan dirinya sendiri, sehingga (a, a)∈ R untuk setiap a ∈ .
Contoh 1%. >iga buah relasi di ba#ah ini menyatakan relasi padahimpunan bilangan bulat positi; &.
R : x lebih besar dari y, : x B y ', ! : $ x B y 1*
>idak satupun dari ketiga relasi di atas yang re;leksi; karena,
misalkan (2, 2) bukan anggota R, , maupun ! .
-
8/18/2019 Relasi Dan Fungsi (2013)
16/107
1
• elasi yang bersi;at re;leksi; mempunyai matriks yangelemen diagonal utamanya semua bernilai 1, atau mii 1,
untuk i 1, 2, =, n,
1
1
1
1
• 8ra; berarah dari relasi yang bersi;at re;leksi; di+irikanadanya gelang pada setiap simpulnya.
-
8/18/2019 Relasi Dan Fungsi (2013)
17/107
1
2. Menghantar (tran"itive)
• elasi R pada himpunan A disebut menghantar jika (a, b) ∈
R dan (b, c)∈
R, maka (a, c)∈
R, untuk a, b, c ∈
A.
-
8/18/2019 Relasi Dan Fungsi (2013)
18/107
1&
Contoh 11. Misalkan A 01, 2, $, %4, dan relasi R di ba#ah ini
dide;inisikan pada himpunan A, maka
(a) R 0(2, 1), ($, 1), ($, 2), (%, 1), (%, 2), (%, $) 4 bersi;at
menghantar. Cihat tabel berikut:
?asangan berbentuk
(a, b) (b, c) (a, c)
($, 2) (2, 1) ($, 1)
(%, 2) (2, 1) (%, 1)(%, $) ($, 1) (%, 1)
(%, $) ($, 2) (%, 2)
(b) R 0(1, 1), (2, $), (2, %), (%, 2) 4 tidak manghantar karena
(2, %) dan (%, 2) ∈ R, tetapi (2, 2) ∉ R, begitu juga (%, 2) dan(2, $) ∈ R, tetapi (%, $) ∉ R.
(+) elasi R 0(1, 1), (2, 2), ($, $), (%, %) 4 jelas menghantar
(d) elasi R 0(1, 2), ($, %)4 menghantar karena tidak ada
(a, b) ∈ R dan (b, c) ∈ R sedemikian sehingga (a, c) ∈ R.
elasi yang hanya berisi satu elemen seperti R 0(%, ')4 selalumenghantar.
-
8/18/2019 Relasi Dan Fungsi (2013)
19/107
19
-
8/18/2019 Relasi Dan Fungsi (2013)
20/107
2*
•elasi yang bersi;at menghantar tidak mempunyai +iri khusus pada matriks representasinya
• 7i;at menghantar pada gra; berarah ditunjukkan oleh: jikaada busur dari a ke b dan dari b ke c, maka juga terdapat
busur berarah dari a ke c.
-
8/18/2019 Relasi Dan Fungsi (2013)
21/107
21
3. etangkup ( "ymmetric) dan tolak!setangkup (anti"ymmetric)
• elasi R pada himpunan A disebut setangkup jika (a, b) ∈ R,maka (b, a) ∈ R untuk a, b ∈ A.
• elasi R pada himpunan A tidak setangkup jika (a, b) ∈ R sedemikian sehingga (b, a) ∉ R.
• elasi R pada himpunan A sedemikian sehingga (a, b) ∈ R dan (b, a) ∈ R hanya jika a b untuk a, b ∈ A disebut tolak!setangkup.
• elasi R pada himpunan A tidak tolak-setangkup jika adaelemen berbeda a dan b sedemikian sehingga (a, b) ∈ R dan(b, a) ∈ R.
-
8/18/2019 Relasi Dan Fungsi (2013)
22/107
• Contoh 14. Misalkan A = {1, 2, 3,4}, dan relasi R di bawah inididefnisikan pada himpunan A, maka
• Relasi R = {1, 1!, 1, 2!, 2, 1!, 2, 2!,2, 4!, 4, 2!, 4, 4! } bersi"atsetangkup karena #ika a, b! ∈ R
maka b, a! #uga ∈ R$ Di sini 1, 2! dan2, 1! ∈ R, begitu #uga 2, 4! dan 4,2! ∈ R$
22
-
8/18/2019 Relasi Dan Fungsi (2013)
23/107
• Relasi R = {1, 1!, 2, 3!, 2, 4!, 4, 2!} tidak setangkup karena 2, 3! ∈ R,tetapi 3, 2! ∉ R$
2$
-
8/18/2019 Relasi Dan Fungsi (2013)
24/107
• Relasi R = {1, 1!, 2, 2!, 3, 3! }t%lak&setangkup karena 1 = 1 dan 1,1! ∈ R, 2 = 2 dan 2, 2! ∈ R, dan 3 =3 dan 3, 3! ∈ R$ 'erhatikan bahwa R
#uga setangkup$
2%
-
8/18/2019 Relasi Dan Fungsi (2013)
25/107
• Relasi R = {1, 1!, 1, 2!, 2, 2!, 2, 3!} t%lak&setangkup karena 1, 1! ∈ R dan 1 = 1 dan, 2, 2! ∈ R dan 2 = 2dan$ 'erhatikan bahwa R tidaksetangkup$
()*+&-MM.*R+/• *+D(0 -MM.*R+/
2'
-
8/18/2019 Relasi Dan Fungsi (2013)
26/107
• Relasi R = {1, 1!, 2, 4!, 3, 3!, 4, 2!} tidak t%lak&setangkup karena 2 ≠ 4tetapi 2, 4! dan 4, 2! angg%ta R$
Relasi R pada a! dan b! di atas #ugatidak t%lak&setangkup$
2
-
8/18/2019 Relasi Dan Fungsi (2013)
27/107
• Relasi R = {1, 2!, 2, 3!, 1, 3! }tidak setangkup tetapi t%lak&setangkup$
2
-
8/18/2019 Relasi Dan Fungsi (2013)
28/107
• Relasi R = {1, 1!, 2, 2!, 2, 3!, 3,2!, 4, 2!, 4, 4!} tidak setangkup dantidak t%lak&setangkup$ R tidak
setangkup karena 4, 2! ∈ R tetapi 2,4! ∉ R$ R tidak t%lak&setangkupkarena 2, 3! ∈ R dan 3, 2! ∈ R tetap
2 ≠ 3$
2&
-
8/18/2019 Relasi Dan Fungsi (2013)
29/107
29
-
8/18/2019 Relasi Dan Fungsi (2013)
30/107
$*
Contoh 15. elasi @habis membagiA pada himpunan bilangan bulat
positi; tidak setangkup karena jika a habis membagi b, b tidak
habis membagi a, ke+uali jika a b. 7ebagai +ontoh, 2 habis
membagi %, tetapi % tidak habis membagi 2.
-
8/18/2019 Relasi Dan Fungsi (2013)
31/107
$1
• elasi yang bersi;at setangkup mempunyai matriks yang
elemen-elemen di ba#ah diagonal utama merupakan
pen+erminan dari elemen-elemen di atas diagonal utama, ataumij m ji 1, untuk i 1, 2, =, n :
*
1
*
1
• 7edangkan gra; berarah dari relasi yang bersi;at setangkup
di+irikan oleh: jika ada busur dari a ke b, maka juga ada busur dari b ke a.
-
8/18/2019 Relasi Dan Fungsi (2013)
32/107
$2
• Matriks dari relasi tolak-setangkup mempunyai si;at yaitu
jika mij 1 dengan i ≠ j, maka m ji *. Dengan kata lain,matriks dari relasi tolak-setangkup adalah jika salah satu dari
mij * atau m ji * bila i ≠ j :
*
1
1*
*
1
• 7edangkan gra; berarah dari relasi yang bersi;at tolak-setangkup di+irikan oleh: jika dan hanya jika tidak pernah
ada dua busur dalam arah berla#anan antara dua simpul
berbeda.
-
8/18/2019 Relasi Dan Fungsi (2013)
33/107
$$
Relasi 'n(ersi
• Misalkan R adalah relasi dari himpunan A ke himpunan B.5nEers dari relasi R, dilambangkan dengan R
F1, adalah relasi
dari B ke A yang dide;inisikan oleh
R F1
0(b, a) G (a, b) ∈ R 4
-
8/18/2019 Relasi Dan Fungsi (2013)
34/107
$%
Contoh 17. Misalkan P 02, $, %4 dan Q 02, %, &, 9, 1'4. ika
kita de;inisikan relasi R dari P ke Q dengan
( p, q) ∈ R jika p habis membagi q
maka kita peroleh
R 0(2, 2), (2, %), (%, %), (2, &), (%, &), ($, 9), ($, 1') 4
F1 adalah inver" dari relasi R, yaitu relasi dari Q ke P dengan
(q, p) ∈ R F1 jika q adalah kelipatan dari p
maka kita peroleh
-
8/18/2019 Relasi Dan Fungsi (2013)
35/107
$'
ika M adalah matriks yang merepresentasikan relasi R,
M
**11*
11***
**111
maka matriks yang merepresentasikan relasi R F1
, misalkan # ,
diperoleh dengan melakukan tran"po"e terhadap matriks M ,
# M !
*1*
*1*
1*1
1*1
**1
-
8/18/2019 Relasi Dan Fungsi (2013)
36/107
$
Mengkombinasikan Relasi
•
-
8/18/2019 Relasi Dan Fungsi (2013)
37/107
$
Contoh 1#. Misalkan A 0a, b, c4 dan B 0a, b, c, d 4.
elasi R1 0(a, a), (b, b), (c, c)4
elasi R2 0(a, a), (a, b), (a, c), (a, d )4
R1 ∩ R2 0(a, a)4
R1 ∪ R2 0(a, a), (b, b), (c, c), (a, b), (a, c), (a, d )4 R1 − R2 0(b, b), (c, c)4 R2 − R1 0(a, b), (a, c), (a, d )4 R1 ⊕ R2 0(b, b), (c, c), (a, b), (a, c), (a, d )4
-
8/18/2019 Relasi Dan Fungsi (2013)
38/107
$&
• ika relasi R1 dan R
2 masing-masing dinyatakan dengan
matriks M R1 dan M R2, maka matriks yang menyatakan
gabungan dan irisan dari kedua relasi tersebut adalah
M R1 ∪ R2 M R1 ∨ M R2 dan M R1 ∩ R2 M R1 ∧ M R2
-
8/18/2019 Relasi Dan Fungsi (2013)
39/107
$9
Contoh 1$. Misalkan bah#a relasi R1 dan R2 pada himpunan A
dinyatakan oleh matriks
R1
*11
1*1
**1
dan R2
**1
11*
*1*
maka
M R1 ∪ R2 M R1 ∨ M R2
*11
111
*11
M R1 ∩ R2 M R1 ∧ M R2
**1
1**
***
-
8/18/2019 Relasi Dan Fungsi (2013)
40/107
%*
)omposisi Relasi
• Misalkan R adalah relasi dari himpunan A ke himpunan B,dan adalah relasi dari himpunan B ke himpunan $ .
-
8/18/2019 Relasi Dan Fungsi (2013)
41/107
%1
Contoh 2%. Misalkan
R 0(1, 2), (1, ), (2, %), ($, %), ($, ), ($, &)4
adalah relasi dari himpunan 01, 2, $4 ke himpunan 02, %, , &4 dan
0(2, %), (%, "), (%, t ), (, t ), (&, %)4
adalah relasi dari himpunan 02, %, , &4 ke himpunan 0 ", t , %4.
Maka komposisi relasi R dan adalah
ο R 0(1, %), (1, t ), (2, "), (2, t ), ($, "), ($, t ), ($, %) 4
-
8/18/2019 Relasi Dan Fungsi (2013)
42/107
%2
-
8/18/2019 Relasi Dan Fungsi (2013)
43/107
%$
• ika relasi R1 dan R2 masing-masing dinyatakan denganmatriks M R1 dan M R2, maka matriks yang menyatakan
komposisi dari kedua relasi tersebut adalah
M R2 ο R1 M R1 ⋅ M R2
yang dalam hal ini operator @.A sama seperti pada perkalian
matriks biasa, tetapi dengan mengganti tanda kali dengan @∧Adan tanda tambah dengan @∨A.
C 21 i lk b h l i d d hi
-
8/18/2019 Relasi Dan Fungsi (2013)
44/107
%%
Contoh 21. Misalkan bah#a relasi R1 dan R2 pada himpunan A
dinyatakan oleh matriks
R1
****11
1*1
dan R2
1*11**
*1*
maka matriks yang menyatakan R2 ο R1 adalah
M R2 ο R1 M R1 . M R2
∧∧∨∧∨∧∧∨∧∨∧
∧∧∨∧∨∧∧∨∧∨∧
∧∧∨∧∨∧∧∨∧∨∧
)**()**()**()1*()1*()**()**(
)*1()**()*1()11()1*()*1()*1(
)*1()*1()**()11()11()**()*1(
***
11*
111
-
8/18/2019 Relasi Dan Fungsi (2013)
45/107
%'
Relasi n!ary
• elasi biner hanya menghubungkan antara dua buahhimpunan.
• elasi yang lebih umum menghubungkan lebih dari dua buahhimpunan. elasi tersebut dinamakan relasi n-ary (ba+a:
ener).
• ika n 2, maka relasinya dinamakan relasi biner (bi 2).elasi n-ary mempunyai terapan penting di dalam basisdata.
• Misalkan A1, A2, =, An adalah himpunan. elasi n-ary R pada himpunan-himpunan tersebut adalah himpunan bagian
dari A1 × A2 × = × An , atau dengan notasi R ⊆ A1 × A2 × =× An. /impunan A1, A2, =, An disebut daerah asal relasi dan n disebut *erajat.
-
8/18/2019 Relasi Dan Fungsi (2013)
46/107
%
Contoh 22. Misalkan
#&M 01$'9&*11, 1$'9&*1%, 1$'9&*1', 1$'9&*19,
1$'9&*21, 1$'9&*2'4 #ama 0mir, 7anti, 5r#an, hmad, 3e+ep, /amdan4 Mat'%l 0Matematika Diskrit, lgoritma, 7truktur Data,
rsitektur
-
8/18/2019 Relasi Dan Fungsi (2013)
47/107
%
7atu +ontoh relasi yang bernama M( adalah
M( 0(1$'9&*11, mir, Matematika Diskrit, ),
(1$'9&*11, mir, rsitektur
-
8/18/2019 Relasi Dan Fungsi (2013)
48/107
%&
elasi M( di atas juga dapat ditulis dalam bentuk >abel:
5M ama Mat
-
8/18/2019 Relasi Dan Fungsi (2013)
49/107
%9
• asisdata (databa"e) adalah kumpulan tabel.
• 7alah satu model basisdata adalah mo*el basis*ata relasional (relational databa"e). Model basisdata ini
didasarkan pada konsep relasi n-ary.
• ?ada basisdata relasional, satu tabel menyatakan satu relasi.7etiap kolom pada tabel disebut atribut. Daerah asal dari
atribut adalah himpunan tempat semua anggota atribut
tersebut berada.
• 7etiap tabel pada basisdata diimplementasikan se+ara ;isiksebagai sebuah file.
• 7atu baris data pada tabel menyatakan sebuah record , dansetiap atribut menyatakan sebuah field .
• 7e+ara ;isik basisdata adalah kumpulan file, sedangkan file adalah kumpulan record , setiap record terdiri atas sejumlah
field .
• tribut khusus pada tabel yang mengidenti;ikasikan se+araunik elemen relasi disebut kun+i ()ey).
I i dil k k h d b i d dil k k d
-
8/18/2019 Relasi Dan Fungsi (2013)
50/107
'*
• Iperasi yang dilakukan terhadap basisdata dilakukan dengan perintah pertanyaan yang disebut q%ery.
• 3ontoh q%ery:@tampilkan semua mahasis#a yang mengambil mata kuliahMatematika DiskritA
@tampilkan da;tar nilai mahasis#a dengan 5M 1$'9&*1'A
@tampilkan da;tar mahasis#a yang terdiri atas 5M dan mata
kuliah yang diambilA
• Q%ery terhadap basisdata relasional dapat dinyatakan se+araabstrak dengan operasi pada relasi n-ary.
• da beberapa operasi yang dapat digunakan, diantaranyaadalah seleksi, proyeksi, dan join.
-
8/18/2019 Relasi Dan Fungsi (2013)
51/107
'1
eleksi
Iperasi seleksi memilih baris tertentu dari suatu tabel yang
memenuhi persyaratan tertentu.
Iperator: σ
Contoh 23. Misalkan untuk relasi M/7 kita ingin menampilkan
da;tar mahasis#a yang mengambil mata kuliah Matematik Diskrit.
Iperasi seleksinya adalahσMatkulAMatematika DiskritA (M/7)
/asil: (1$'9&*11, mir, Matematika Diskrit, ) dan
(1$'9&*2', /amdan, Matematika Diskrit, )
-
8/18/2019 Relasi Dan Fungsi (2013)
52/107
'2
Proyeksi
Iperasi proyeksi memilih kolom tertentu dari suatu tabel. ika ada
beberapa baris yang sama nilainya, maka hanya diambil satu kali.
Iperator: π
Contoh 24. Iperasi proyeksi
π ama, Matabel $.'. 7edangkan operasi proyeksi
π 5M, ama (M/7)
menghasilkan >abel $..
T b l 3 5 T b l 3 6
-
8/18/2019 Relasi Dan Fungsi (2013)
53/107
'$
Tabel 3.5 Tabel 3.6
ama Mat
-
8/18/2019 Relasi Dan Fungsi (2013)
54/107
'%
Iperasi join menggabungkan dua buah tabel menjadi satu bila
kedua tabel mempunyai atribut yang sama.
Iperator: τ
Contoh 25. Misalkan relasi M(* dinyatakan dengan >abel $.
dan relasi M(+ dinyatakan dengan >abel $.&.
Iperasi join
τ 5M, ama(M/71, M/72)
menghasilkan >abel $.9.
Tabel 3.7 Tabel 3.#
5M ama < 5M ama Mat
-
8/18/2019 Relasi Dan Fungsi (2013)
55/107
''
,ungsi
• Misalkan A dan B himpunan.elasi biner f dari A ke B merupakan suatu ;ungsi jika "etiap
elemen di dalam A dihubungkan dengan tepat satu elemen di
dalam B.
ika f adalah ;ungsi dari A ke B kita menuliskan
f : A → B yang artinya f memetakan A ke B.
• A disebut *aerah asal (domain) dari f dan B disebut *aerahhasil (codomain) dari f .
• ama lain untuk ;ungsi adalah pemetaan atau transformasi.
•
-
8/18/2019 Relasi Dan Fungsi (2013)
56/107
'
• ika f (a) b, maka b dinamakan ba-angan (image) dari a dan a dinamakan pra!ba-angan ( pre-image) dari b.
• /impunan yang berisi semua nilai pemetaan f disebut jelajah (range) dari f . ?erhatikan bah#a jelajah dari f adalahhimpunan bagian (mungkin proper "%b"et ) dari B.
a b
A B
f
-
8/18/2019 Relasi Dan Fungsi (2013)
57/107
'
• 6ungsi adalah relasi yang khusus:1. >iap elemen di dalam himpunan A harus digunakan oleh
prosedur atau kaidah yang mende;inisikan f .
2. 6rasa @dihubungkan dengan tepat satu elemen di dalam BA
berarti bah#a jika (a, b) ∈ f dan (a, c) ∈ f , maka b c.
• 6ungsi dapat dispesi;ikasikan dalam berbagai bentuk,
-
8/18/2019 Relasi Dan Fungsi (2013)
58/107
'&
diantaranya:
1. /impunan pasangan terurut.
7eperti pada relasi.
2. 6ormula pengisian nilai (a""ignment ).
3ontoh: f ( x) 2 x B 1*, f ( x) x2, dan f ( x) 1 x.
$.
-
8/18/2019 Relasi Dan Fungsi (2013)
59/107
'9
Contoh 26. elasi
f 0(1, %), (2, v), ($, ,)4
dari A 01, 2, $4 ke B 0%, v, ,4 adalah ;ungsi dari A ke B. Di sini
(1) %, f (2) v, dan f ($) ,. Daerah asal dari f adalah A dan daerahhasil adalah B. elajah dari f adalah 0%, v, ,4, yang dalam hal ini sama
dengan himpunan .
Contoh 27. elasi
f 0(1, %), (2, %), ($, v)4
dari A 01, 2, $4 ke B 0%, v, ,4 adalah ;ungsi dari A ke B, meskipun
% merupakan bayangan dari dua elemen A. Daerah asal ;ungsi adalah
, daerah hasilnya adalah B, dan jelajah ;ungsi adalah 0%, v4.
-
8/18/2019 Relasi Dan Fungsi (2013)
60/107
*
Contoh 2#. elasi
f 0(1, %), (2, v), ($, ,)4
dari A 01, 2, $, %4 ke B 0%, v, ,4 bukan ;ungsi, karena tidak semua
elemen A dipetakan ke B.
Contoh 2$. elasi
f 0(1, %), (1, v), (2, v), ($, ,)4
dari A 01, 2, $4 ke B 0%, v, ,4 bukan ;ungsi, karena 1 dipetakan ke
dua buah elemen B, yaitu % dan v.
Contoh 3%. Misalkan f : → dide;inisikan oleh f ( x) x2. Daerahasal dan daerah hasil dari f adalah himpunan bilangan bulat, dan jelajah
dari f adalah himpunan bilangan bulat tidak-negati;.
-
8/18/2019 Relasi Dan Fungsi (2013)
61/107
1
• 6ungsi f dikatakan satu!ke!satu (one-to-one) atau injektif (injective) jika tidak ada dua elemen himpunan A yang
memiliki bayangan sama.
a 1
A B
2
3
4
5
b
c
d
-
8/18/2019 Relasi Dan Fungsi (2013)
62/107
2
Contoh 31. elasi
f 0(1, ,), (2, %), ($, v)4
dari A 01, 2, $4 ke B 0%, v, , x4 adalah ;ungsi satu-ke-satu,
>etapi relasi
f 0(1, %), (2, %), ($, v)4
dari A 01, 2, $4 ke B 0%, v, ,4 bukan ;ungsi satu-ke-satu,
karena f (1) f (2) %.
-
8/18/2019 Relasi Dan Fungsi (2013)
63/107
$
Contoh 32. Misalkan f : → . >entukan apakah f ( x) x2 B 1 dan( x) x F 1 merupakan ;ungsi satu-ke-satuK
?enyelesaian:(i) f ( x) x
2 B 1 bukan ;ungsi satu-ke-satu, karena untuk dua x
yang bernilai mutlak sama tetapi tandanya berbeda nilai
;ungsinya sama, misalnya f (2) f (-2) ' padahal F2 ≠ 2.
(ii) f ( x) x F 1 adalah ;ungsi satu-ke-satu karena untuk a ≠ b,a F 1 ≠ b F 1.
Misalnya untuk x 2, f (2) 1 dan untuk x -2, f (-2) -$.
-
8/18/2019 Relasi Dan Fungsi (2013)
64/107
%
• 6ungsi f dikatakan dipetakan pa*a (onto) atau surjektif ( "%rjective) jika setiap elemen himpunan B merupakan
bayangan dari satu atau lebih elemen himpunan A.
• Dengan kata lain seluruh elemen B merupakan jelajah dari f .6ungsi f disebut ;ungsi pada himpunan B.
a 1
A B
2
3
b
c
d
-
8/18/2019 Relasi Dan Fungsi (2013)
65/107
'
Contoh 33. elasi
f 0(1, %), (2, %), ($, v)4
dari A 01, 2, $4 ke B 0%, v, ,4 bukan ;ungsi pada karena ,
tidak termasuk jelajah dari f .
elasi
f 0(1, ,), (2, %), ($, v)4
dari A 01, 2, $4 ke B 0%, v, ,4 merupakan ;ungsi pada karena
semua anggota B merupakan jelajah dari f .
-
8/18/2019 Relasi Dan Fungsi (2013)
66/107
Contoh 34. Misalkan f : → . >entukan apakah f ( x) x2 B 1 dan
( x) x F 1 merupakan ;ungsi padaK?enyelesaian:
(i) f ( x) x2 B 1 bukan ;ungsi pada, karena tidak semua nilai
bilangan bulat merupakan jelajah dari f .
(ii) f ( x) x F 1 adalah ;ungsi pada karena untuk setiap bilangan bulat y, selalu ada nilai x yang memenuhi, yaitu y x F 1 akan
dipenuhi untuk x y B 1.
-
8/18/2019 Relasi Dan Fungsi (2013)
67/107
• 6ungsi f dikatakan berkorespon*en satu!ke!satu ataubijeksi (bijection) jika ia ;ungsi satu-ke-satu dan juga ;ungsi
pada.
Contoh 35. elasi
f 0(1, %), (2, ,), ($, v)4
dari A 01, 2, $4 ke B 0%, v, ,4 adalah ;ungsi yang
berkoresponden satu-ke-satu, karena f adalah ;ungsi satu-ke-satu
maupun ;ungsi pada.
Contoh 36. 6ungsi f ( x) x F 1 merupakan ;ungsi yang
-
8/18/2019 Relasi Dan Fungsi (2013)
68/107
&
berkoresponden satu-ke-satu, karena f adalah ;ungsi satu-ke-satu
maupun ;ungsi pada.
6ungsi satu-ke-satu, 6ungsi pada, bukan pada bukan satu-ke-satu
uka ;ungsi satu-ke-satu ukan ;ungsi
maupun pada
a
1
AB
2
3b
c 4
a1
AB
2
3
b
c
c d
a 1
A B
2
3
b
c
c d 4
a 1
A B
2
3
b
c
c d 4
-
8/18/2019 Relasi Dan Fungsi (2013)
69/107
9
• ika f adalah ;ungsi berkoresponden satu-ke-satu dari A ke B,maka kita dapat menemukan balikan (inver") dari f .
• alikan ;ungsi dilambangkan dengan f F1. Misalkan a adalahanggota himpunan A dan b adalah anggota himpunan B,
maka f-1
(b) a jika f (a) b.
• 6ungsi yang berkoresponden satu-ke-satu sering dinamakan juga ;ungsi yang invertible (dapat dibalikkan), karena kita
dapat mende;inisikan ;ungsi balikannya. 7ebuah ;ungsi
dikatakan not invertible (tidak dapat dibalikkan) jika ia bukan
;ungsi yang berkoresponden satu-ke-satu, karena ;ungsi balikannya tidak ada.
Contoh 37 elasi
-
8/18/2019 Relasi Dan Fungsi (2013)
70/107
*
Contoh 37. elasi
f 0(1, %), (2, ,), ($, v)4
dari A 01, 2, $4 ke B 0%, v, ,4 adalah ;ungsi yang
berkoresponden satu-ke-satu. alikan ;ungsi f adalah
f-1
0(%, 1), (,, 2), (v, $)4
adi, f adalah ;ungsi invertible.
Contoh 3#. >entukan balikan ;ungsi f ( x) x F 1.
?enyelesaian:
6ungsi f ( x) x F 1 adalah ;ungsi yang berkoresponden satu-ke-
satu, jadi balikan ;ungsi tersebut ada.
Misalkan f ( x) y, sehingga y x F 1, maka x y B 1. adi, balikan
;ungsi balikannya adalah f
-1
( y) y B1.
-
8/18/2019 Relasi Dan Fungsi (2013)
71/107
1
Contoh 3$. >entukan balikan ;ungsi f ( x) x2 B 1.
?enyelesaian:Dari 3ontoh $.%1 dan $.%% kita sudah menyimpulkan bah#a f ( x)
F 1 bukan ;ungsi yang berkoresponden satu-ke-satu, sehingga
;ungsi balikannya tidak ada. adi, f ( x) x2 B 1 adalah ;unsgi yang
not invertible.
-
8/18/2019 Relasi Dan Fungsi (2013)
72/107
2
)omposisi *ari *ua buah fungsi.
Misalkan g adalah ;ungsi dari himpunan A ke himpunan B, dan
adalah ;ungsi dari himpunan B ke himpunan $ .
-
8/18/2019 Relasi Dan Fungsi (2013)
73/107
$
Contoh 4%. Diberikan ;ungsi
g 0(1, %), (2, %), ($, v)4
yang memetakan A 01, 2, $4 ke B 0%, v, ,4, dan ;ungsi
f 0(%, y), (v x), (,, z )4
yang memetakan B 0%, v, ,4 ke $ 0 x, y, z 4. 6ungsi komposisi
dari A ke $ adalah
f ο g 0(1, y), (2, y), ($, x) 4
Contoh 41. Diberikan ;ungsi f ( x) x F 1 dan g ( x) x2 B 1.
>entukan f ο g dan g ο f . ?enyelesaian:
(i) ( f ο g )( x) f ( g ( x)) f ( x2 B 1) x2 B 1 F 1 x2.(ii) ( g ο f )( x) g ( f ( x)) g ( x F 1) ( x F1)2 B 1 x2 - 2 x B 2.
"eberapa ,ungsi )husus
-
8/18/2019 Relasi Dan Fungsi (2013)
74/107
%
"eberapa ,ungsi )husus
1. ,ungsi !loor *an "eiling
Misalkan x adalah bilangan riil, berarti x berada di antara dua bilangan bulat.
6ungsi floor dari L:
x menyatakan nilai bilangan bulat terbesar yang lebih ke+ilatau sama dengan x
6ungsi ceiling dari x:
x menyatakan bilangan bulat terke+il yang lebih besar atausama dengan x
Dengan kata lain, ;ungsi floor membulatkan x ke ba#ah,
sedangkan ;ungsi ceiling membulatkan x ke atas.
Contoh 42. eberapa +ontoh nilai ;ungsi floor dan ceiling:
-
8/18/2019 Relasi Dan Fungsi (2013)
75/107
'
Contoh 42. eberapa +ontoh nilai ;ungsi floor dan ceiling :
$.' $ $.' %
*.' * *.' 1%.& % %.& ' F *.' F 1 F *.' * F$.' F % F$.' F $
Contoh 42. Di dalam komputer, data dikodekan dalam untaian
byte, satu byte terdiri atas & bit. ika panjang data 12' bit, maka
umlah byte yang diperlukan untuk merepresentasikan data adalah
12'& 1 byte. ?erhatikanlah bah#a 1 × & 12& bit, sehinggauntuk byte yang terakhir perlu ditambahkan $ bit ekstra agar satu
byte tetap & bit (bit ekstra yang ditambahkan untuk menggenapi &
bit disebut padding bit").
2 ,ungsi mo*ulo
-
8/18/2019 Relasi Dan Fungsi (2013)
76/107
2. ,ungsi mo*ulo
Misalkan a adalah sembarang bilangan bulat dan m adalah
bilangan bulat positi;.
a mod m memberikan sisa pembagian bilangan bulat bila a
dibagi dengan m
a mod m r sedemikian sehingga a mq B r , dengan * ≤ r m.
Contoh 43. eberapa +ontoh ;ungsi modulo
2' mod %1' mod % *
$12 mod %' 12
* mod ' '
F2' mod $ (sebab F2' ⋅ (F%) B $ )
3. ,ungsi ,aktorial
-
8/18/2019 Relasi Dan Fungsi (2013)
77/107
>×−×××
==
*,)1(.21
*,1
nnn
nn
4. ,ungsi /ksponensial
>×××
== *,
*,1
naaa
na
n
n
Nntuk kasus perpangkatan negati;,
n
n
aa
1=−
5. ,ungsi 0ogaritmik
6ungsi logaritmik berbentuk
x y a log= ↔ x a y
,ungsi Rekursif
-
8/18/2019 Relasi Dan Fungsi (2013)
78/107
&
• 6ungsi f dikatakan ;ungsi rekursi; jika de;inisi ;ungsinyamenga+u pada dirinya sendiri.
3ontoh: n 1 × 2 × = × (n F 1) × n (n 1) × n.
>−×
==
*,)1(
*,1
nnn
nn
6ungsi rekursi; disusun oleh dua bagian:
(a) Ba"i"
agian yang berisi nilai a#al yang tidak menga+u pada dirinyasendiri. agian ini juga sekaligus menghentikan de;inisi
rekursi;.
(b) Re)%ren"
agian ini mende;inisikan argumen ;ungsi dalam terminologi
dirinya sendiri. 7etiap kali ;ungsi menga+u pada dirinya sendiri,
argumen dari ;ungsi harus lebih dekat ke nilai a#al (basis).
• 3ontoh de;inisi rekursi; dari ;aktorial:(a) basis:
-
8/18/2019 Relasi Dan Fungsi (2013)
79/107
9
(a) basis:
n 1 , jika n *
(b) rekurens:
n n × (n -1) , jika n O *
' dihitung dengan langkah berikut:
(1) ' ' × % (rekurens)(2) % % × $($) $ $ × 2(%) 2 2 × 1(') 1 1 × *() * 1
(P) * 1
('P) 1 1 × * 1 × 1 1(%P) 2 2 × 1 2 × 1 2($P) $ $ × 2 $ × 2 (2P) % % × $ % × 2%(1P) ' ' × % ' × 2% 12*
adi, ' 12*.
-
8/18/2019 Relasi Dan Fungsi (2013)
80/107
&*
Contoh 44. Di ba#ah ini adalah +ontoh-+ontoh ;ungsi rekursi; lainnya:
1.
≠+−
==
*,)1(2
*,*)(
2 x x x /
x x /
2. 6ungsi 3hebyseE
>−−−
=
=
=
1,),2(),1(2
1,
*,1
),(
n xn! xn x!
n x
n
xn!
$. 6ungsi ;ibona++i:
>−+−
=
=
=
1,)2()1(
1,1
*,*
)(
nn f n f
n
n
n f
R l i 0 t
-
8/18/2019 Relasi Dan Fungsi (2013)
81/107
Relasi 0esetaraan
DEFINISI. Relasi R pada himpunan A disebut relasi kesetaraan
equivalence relation! #ika ia reeksi",setangkup dan menghantar$
&1
-
8/18/2019 Relasi Dan Fungsi (2013)
82/107
• eara intuiti", di dalam relasi
kesetaraan, dua bendaberhubungan #ika keduanamemiliki beberapa si"at ang samaatau memenuhi beberapapersaratan ang sama$
• Dua elemen ang dihubungkandengan relasi kesetaraandinamakan setara equivalent !$
&2
• /%nt%h
-
8/18/2019 Relasi Dan Fungsi (2013)
83/107
/%nt%h
( = himpunan mahasiswa, R relasi pada (
a, b!∈
R #ika a satu angkatan dengan b$
R reeksi" setiap mahasiswa seangkatandengan dirina sendiri
R setangkup #ika a seangkatan dengan b,maka b pasti seangkatan dengan a$
R menghantar #ika a seangkatan dengan b dan b seangkatan dengan c, maka pastilah
a seangkatan dengan c$
Dengan demikian, R adalah relasi kesetaraan$
&$
-
8/18/2019 Relasi Dan Fungsi (2013)
84/107
Relasi Pengurutan
Parsial DEFINISI. Relasi R pada himpunan S dikatakan relasi pengurutan parsial partial ordering relation! #ika ia reeksi",
t%lak&setangkup, dan menghantar$
5impunan S bersama&sama dengan relasi
R disebut himpunan terurut secaraparsial partially ordered set , atau poset !, dan dilambangkan dengan S, R!$
&%
/%nt%h Relasi ≥ pada himpunan bilangan
-
8/18/2019 Relasi Dan Fungsi (2013)
85/107
p p gbulat adalah relasi pengurutan parsial$
(lasanRelasi ≥ reeksi", karena a ≥ a untuk setiapbilangan bulat a;
Relasi ≥ t%lak&setangkup, karena #ika a ≥ b dan b ≥ a, maka a = b;
Relasi ≥ menghantar, karena #ika a ≥ b dan b ≥ c maka a ≥ c$
&'
-
8/18/2019 Relasi Dan Fungsi (2013)
86/107
/%nt%h Relasi 6habis membagi7
pada himpunan bilangan bulatadalah relasi pengurutan parsial$
(lasan relasi 6habis membagi7bersi"at reeksi", t%lak&setangkup,dan menghantar$
&
-
8/18/2019 Relasi Dan Fungsi (2013)
87/107
• eara intuiti", di dalam relasipengurutan parsial, dua buahbenda saling berhubungan #ikasalah satuna && lebih keil lebih
besar! daripada,& atau lebih rendah lebih tinggi!
daripada lainna menurut si"at
atau kriteria tertentu$
&
• +stilah pengurutan menatakan bahwa
-
8/18/2019 Relasi Dan Fungsi (2013)
88/107
+stilah pengurutan menatakan bahwabenda&benda di dalam himpunan tersebutdirutkan berdasarkan si"at atau kriteria
tersebut$
• (da #uga kemungkinan dua buah benda didalam himpunan tidak berhubungan dalam
suatu relasi pengurutan parsial$ Dalam haldemikian, kita tidak dapat membandingkankeduana sehingga tidak dapat diidentifkasimana ang lebih besar atau lebih keil$
• +tulah alasan digunakan istilah pengurutanparsial atau pengurutan tak&lengkap
&&
-
8/18/2019 Relasi Dan Fungsi (2013)
89/107
0l%sur Relasi closure of relation!
• /%nt%h 1 Relasi R = {1, 1!, 1, 3!,2, 3!, 3, 2!} pada himpunan A = {1,2, 3} tidak reeksi"$
• 8agaimana membuat relasi reeksi"ang sesedikit mungkin dan
mengandung R9
&9
• *ambahkan 2 2! dan 3 3! ke dalam R
-
8/18/2019 Relasi Dan Fungsi (2013)
90/107
• *ambahkan 2, 2! dan 3, 3! ke dalam R karena dua elemen relasi ini ang
belum terdapat di dalam R!
• Relasi baru, S, mengandung R, aitu
S = {1, 1!, 1, 3!, (2 2!, 2, 3!,
3, 2!, (" "! }
• Relasi S disebut klosur re#eksi$ reexive closure! dari R$
9*
-
8/18/2019 Relasi Dan Fungsi (2013)
91/107
• /%nt%h 2 Relasi R = {1, 3!, 1, 2!,
2, 1!, 3, 2!, 3, 3!} padahimpunan A = {1, 2, 3} tidaksetangkup$
• 8agaimana membuat relasisetangkup ang sesedikit mungkin
dan mengandung R9
91
• *ambahkan 3 1! dan 2 3! ke dalam R
-
8/18/2019 Relasi Dan Fungsi (2013)
92/107
*ambahkan 3, 1! dan 2, 3! ke dalam R
karena dua elemen relasi ini ang belum
terdapat di dalam S agar S men#adisetangkup!$
• Relasi baru, S, mengandung R
S = {1, 3!, 3, 1!, 1, 2!, 2, 1!, 3, 2!, 2,3!, 3, 3!}
• Relasi S disebut klosur setangkup symmetric closure! dari R$
92
Mi lk R d l h l i d
-
8/18/2019 Relasi Dan Fungsi (2013)
93/107
• Misalkan R adalah relasi padahimpunan A$ R dapat memiliki atau
tidak memiliki si"at P, sepertireeksi", setangkup, ataumenghantar$ ;ika terdapat relasi S
dengan si"at P ang mengandung R sedemikian sehingga S adalahhimpunan bagian dari setiap relasidengan si"at P ang mengandungR, maka S disebut klosur closure!atau tutupan dari R 3?$
9$
-
8/18/2019 Relasi Dan Fungsi (2013)
94/107
0l%sur Reeksi" • Misalkan R adalah sebuah relasi pada
himpunan A$
• 0l%sur reeksi" dari R adalah R ∪ ∆,ang dalam hal ini ∆ = {a, a! @ a ∈
A}$
9%
/ t h R {1 1! 1 3! 2 3! 3 2!}
-
8/18/2019 Relasi Dan Fungsi (2013)
95/107
• /%nt%h R = {1, 1!, 1, 3!, 2, 3!, 3, 2!}adalah relasi pada A = {1, 2, 3}
maka ∆ = {1, 1!, 2, 2!, 3, 3!},
sehingga kl%sur reeksi" dari R adalah
R ∪ ∆ = {1, 1!, 1, 3!, 2, 3!, 3, 2!} ∪ {1, 1!, 2, 2!, 3, 3!}
= {1, 1!, 1, 3!, 2, 2!, 2, 3!, 3, 2!, 3, 3!}
9'
• Contoh% Misalkan R adalah relasi
-
8/18/2019 Relasi Dan Fungsi (2013)
96/107
Contoh% Misalkan R adalah relasi
{a, b! @ a ≠ b}
pada himpunan bilangan bulat$
0l%sur reeksi" dari R adalah
R ∪ ∆ = {a, b! @ a ≠ b} ∪
{a, a! @ a ∈ &}
= {a, b! @ a, b ∈ &}
9
-
8/18/2019 Relasi Dan Fungsi (2013)
97/107
0l%sur setangkup• Misalkan R adalah sebuah relasi pada
himpunan A$
• 0l%sur setangkup dari R adalah R ∪ R&1, dengan R&1 = {b, a! @ a, b! a ∈ R}$
9
• /%nt%h R = {1, 3!, 1, 2!, 2, 1!, 3, 2!,
-
8/18/2019 Relasi Dan Fungsi (2013)
98/107
3, 3!} adalah relasi pada A = {1, 2, 3},
maka
R&1 = {3, 1!, 2, 1!, 1, 2!, 2, 3!, 3, 3!}
sehingga kl%sur setangkup dari R adalah
R ∪ R&1 = {1, 3!, 1, 2!, 2, 1!, 3, 2!, 3, 3!} ∪
{3, 1!, 2, 1!, 1, 2!, 2, 3!, 3, 3!}
= {1, 3!, 3, 1!, 1, 2!, 2, 1!, 3, 2!, 2, 3!, 3, 3!}
9&
-
8/18/2019 Relasi Dan Fungsi (2013)
99/107
• /%nt%h Misalkan R adalah relasi
{a, b! @ a habis membagi b}pada himpunan bilangan bulat$
0l%sur setangkup dari R adalah
R ∪ R&1 = {a, b! @ a habis membagib} ∪ {b, a! @ b habis membagi a}
= {a, b! @ a habis membagi b atau b habis membagi a}
99
-
8/18/2019 Relasi Dan Fungsi (2013)
100/107
0l%sur menghantar• 'embentukan kl%sur menghantar lebih sulit
daripada dua buah kl%sur sebelumna$
• /%nt%h R = {1, 2!, 1, 4!, 2, 1!, 3, 2!}
adalah relasi A = {1, 2, 3, 4}$R tidak transiti" karena tidak mengandungsemua pasangan a, c! sedemikian sehinggaa, b! dan b, c! di dalam R$
'asangan a, c! ang tidak terdapat di dalamR adalah 1, 1!, 2, 2!, 2, 4!, dan 3, 1!$
1**
-
8/18/2019 Relasi Dan Fungsi (2013)
101/107
• 'enambahan semua pasangan ini kedalam R sehingga men#adi
S = {1, 2!, 1, 4!, 2, 1!, 3, 2!, 1, 1!,
2, 2!, 2, 4!, 3, 1!}
tidak menghasilkan relasi ang bersi"atmenghantar karena, misalna terdapat3, 1! ∈ S dan 1, 4! ∈ S, tetapi 3, 4! ∉ S$
1*1
-
8/18/2019 Relasi Dan Fungsi (2013)
102/107
•
0%sur menghantar dari R adalah
RA = R2 ∪ R3 ∪ B ∪ Rn
• ;ika MR adalah matriks angmerepresentasikan R pada sebuahhimpunan dengan n elemen, makamatriks kl%sur menghantar RA adalah
1*2
=Q R M M R ∨ "2!
R M ∨ "$!
R M ∨ = ∨ "!n
R M
Misalkan R 0(1, 1), (1, $), (2, 2), ($, 1), ($, 2)4 adalah relasi pada himpunan 01, 2, $4. >entukan
klosur menghantar dari R.
-
8/18/2019 Relasi Dan Fungsi (2013)
103/107
1*$
?enyelesaian:
Matriks yang merepresentasikan relasi R adalah
M R
*11
*1*1*1
Maka, matriks klosur menghantar dari R adalah
=Q R M M R ∨ "2!
R M ∨ "$!
R M
-
8/18/2019 Relasi Dan Fungsi (2013)
104/107
(plikasi kl%sur
menghantar• 0l%sur menghantar menggambarkanbagaimana pesan dapat dikirim darisatu k%ta ke k%ta lain baik melalui
hubungan k%munikasi langsung ataumelalui k%ta antara sebanakmungkin
-
8/18/2019 Relasi Dan Fungsi (2013)
105/107
•
Misalkan #aringan k%mputermempunai pusat data di ;akarta,8andung, urabaa, Medan,Makassar, dan 0upang$
• Misalkan R adalah relasi angmengandung a, b! #ika terdapat
saluran telep%n dari k%taa ke k%ta
b$
1*'
-
8/18/2019 Relasi Dan Fungsi (2013)
106/107
1*
B a n d u n g
J a k a r t a S u r a b a y a
M e d a n
M a k a s s a r
K u p a n g
• 0arena tidak semua link langsung dari satuk t k k t l i k i i d t d i
-
8/18/2019 Relasi Dan Fungsi (2013)
107/107
k%ta ke k%ta lain, maka pengiriman data dari ;akarta ke urabaa tidak dapat dilakukan
seara langsung$
• Relasi R tidak menghantar karena ia tidakmengandung semua pasangan pusat data
ang dapat dihubungkan baik link langsungatau tidak langsung!$
• 0l%sur menghantar adalah relasi ang paling
minimal ang berisi semua pasangan pusatdata ang mempunai link langsung atau tidaklangsung dan mengandung R$