Relasi dan Fungsi Ira Prasetyaningrum
Relasi • Terdapat dua himpunan X dan Y, Cartesian product XxY adalah himpunan dari semua pasangan terurut (x,y) dimana x∈X dan y∈Y – XxY = {(x, y) | x∈X dan y∈Y}
• Contoh : – X = {A,B} – Y = {1,2,3} – Cross Product
XxY = {(A,1),(A,2),(A,3),(B,1),(B,2),(B,3)} • Karena merupakan relasi antara dua himpunan, maka disebut relasi biner.
Relasi Misalkan A dan B himpunan. Suatu relasi biner dari subhimpunan dari A×B.
A
ke
B
adalah
• Untuk relasi biner R berlaku R ⊆ A×B. • Digunakan notasi aRb untuk menyatakan (a,b)∈R dan aRb untuk menyatakan (a,b)∉R. • Jika (a, b) merupakan anggota R, a dikatakan berelasi dengan b oleh R. – Contoh: X = {1, 2, 3} and Y = {a, b} – R = {(1,a), (1,b), (2,b), (3,a)} adalah relasi antara X dan Y
Contoh Misalkan O himpunan orang, A himpunan angkutan kota, dan N relasi yang mendeskripsikan siapa yang menaiki angkot tertentu. O = {Aang, Bida, Charlie, Dina}, A = {Cicaheum-Ledeng (CL), Kelapa-Dago (KD), Stasiun-Sadang Serang (SS)} N = {(Aang, CL), (Bida, CL), (Bida, KD), (Charlie, SS)} Artinya Aang naik Cicaheum-Ledeng, Bida naik Cicaheum-Ledeng dan Kelapa-Dago, Charlie naik Stasiun-Sadang Serang, dan Dina tidak menaiki salah satu dari angkot
Relasi pada Himpunan Definisi. Suatu relasi pada himpunan A adalah relasi dari A ke A. Relasi pada himpunan A adalah subhimpunan dari A×A. Contoh 2. Misalkan A = {1, 2, 3, 4}. Himpunan terurut manakah yang terdapat dalam relasi(1, 2),(1, 3),(1, 4),(2, 3), (2, 4),(3, 4)} R = {(a, b) | a < b} ?
Contoh 2… 1 2
1 2
R 1 2
3 4
3 4
3 4
1
2
3
4
X
X
X
X
X X
Contoh • X = {1, 3, 4, 7, 9, 12, 16} and Y = {1, 2, 4, 8, 9} • Didefinisikan R1 = {(x, y) | x ∈ X, y ∈ Y, and x = y2} • Maka R1 = {(?, ?), …} • Didefinisikan R2 = {(x, y) | x ∈ X, y ∈ Y, and x2 = y} • Maka R2 = ?
Contoh • X = {1, 3, 4, 7, 9, 12, 16} and Y = {1, 2, 4, 8, 9} • Didefinisikan R1 = {(x, y) | x ∈ X, y ∈ Y, and x = y2} • Maka R1 = {(1, 1), (4, 2), (16, 4)} • Didefinisikan R2 = {(x, y) | x ∈ X, y ∈ Y, and x2 = y} • Maka R2 = {(1, 1), (3, 9)}
Banyaknya Relasi pada Himpunan
Ada berapa relasi berbeda yang dapat didefinisikan pada himpunan A dengan n anggota? Suatu relasi pada A adalah subhimpunan dari A×A. Ada berapa anggota A×A ? Terdapat n2 anggota A×A Ada berapa subhimpunan dari A×A? Banyaknya subhimpunan yang dapat dibentuk dari suatu himpunan dengan m anggota adalah 2m. 2 n Jadi, ada 2 subhimpunan dapat dibentuk dari A×A.
Sifat Relasi (refleksif) Definisi. Relasi R pada himpunan A disebut refleksif jika (a,a)∈R untuk setiap anggota a∈A. Relasi R pada himpunan A tidak refleksif jika ada a∈R sedemikian sehingga (a,a) ∉ R Apakah relasi berikut 4} refleksif? R = {(1, 1), (1, 2), (2, 3), pada (3, 3),{1, (4, 2, 4)}T3, idak. R = {(1, 1), (2, 2), (2, 3), (3, 3), (4, 4)}Ya. R = {(1, 1), (2, 2), (3, 3)} Tidak.
Sifat Relasi (simetris)
Definisi. • Relasi R pada himpunan A disebut simetris / (symmetric) jika (a,b)∈R maka (b,a)∈R untuk a,b ∈ A
• Relasi R adalah antisymmetric pada himp A sedemikian sehingga (a,b) ∈R maka (b,a) ∈ R hanya jika a = b untuk a,b ∈ A – atau
• jika untuk semua a,b ∈ A sedemikian sehingga a≠b, jika (a,b) ∈R maka (b,a) ∉R
Simetris dan Antisimetris • Definisi tersebut menyatakan bahwa relasi R pada himpunan A bukan antisimetris jika ada elemen berbeda a dan b sedemikian sehingga (a,b) ∈R maka (b,a) ∈ R • Istilah simetris dan antisimetris tidaklah berlawanan, karena suatu relasi dapat memiliki kedua sifat itu sekaligus. • Namun relasi tidak dapat memiliki kedua sifat tersebut sekaligus jika ia mengandung beberapa pasangan terurut berbentuk (a,b) yang mana a≠b
Sifat Relasi (transitif) Definisi. Relasi R pada himpunan A disebut transitif jika setiap kali (a,b)∈R dan (b,c)∈R, maka (a,c)∈R untuk a,b,c∈A. Apakah relasi berikut pada {1, 2, 3, 4} transitif? R = {(1, 1), (1, 2), (2, 2), (2, 1), (3, 3)}
Ya.
R = {(1, 3), (3, 2), (2, 1)}
Tidak.
R = {(2, 4), (4, 3), (2, 3), (4, 1)}
Tidak.
Contoh • Misalkan R adalah Relasi pada X = {1,2,3,4} yang didefinisikan oleh (x,y)∈R jika x<=y x,y ∈ X. • R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4 ),(4,4)} • Relasi R adalah refleksif • (antisymmetric) (2,3) ∈ R tetapi (3,2) ∉ R • Transitif
Contoh • Merupakan Transitif
Contoh • Apakah Relasi pada Himpunan A = {1,2,3,4} adalah Refleksif, symmetric, antisymmetric dan transitif ? • R1 = {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1) (4,4)} • R2 = {(1,1) (1,2) (2,1)} • R3 = {(1,1) (1,2) (1,4) (2,1) (2,2) (3,3) (4,1) (4,4)} • R4 = {(2,1) (3,1) (3,2) (4,1) (4,2) (4,3)} • R5 = {(1,1) (1,2) (1,3) (1,4) (2,2) (2,3) (2,4) (3,3) (3,4) (4,4)} • R6 = {(3,4)}
Jawab • • • • • •
R1 = R2 = symmetric R3 = refleksif, symmetric R4 = antisymmetric, transitif R5 = refleksif, antisymmetric, transitif R6 = antisymmetric, transitif
Soal Relasi pada himpunan integer • R1 = {(a,b) | a ≤ b } • R2 = {(a,b) | a > b} • R3 = {(a,b) | a = b atau a = -b} • R4 = {(a,b) | a=b } • R5 = {(a,b) | a = b+1 } • R6 = {(a,b) | a + b = 3 }
Jawab • • • • • •
R1 = refleksif, antisimetris, transitif R2 = antisimetris, transitif R3 = refleksif, simetris, transitif R4 = refleksif, simetris, transitif R5 = antisimetris R6 = simetris
Mengkombinasi Relasi Relasi adalah himpunan, sehingga operasi himpunan dapat diaplikasikan . Jika ada dua relasi R1 dan R2, dan keduanya dari himpunan A ke himpunan B, maka terdapat kombinasi R1 ∪ R2, R1 ∩ R2, atau R1 – R2
Mengkombinasi Relasi • Contoh : • A = {1,2,3} B = {1,2,3,4}. Relasi R1 = {(1,1) (2,2) (3,3)} dan • R2 = {(1,1) (1,2) (1,3) (1,4)} jika dikombinasikan akan mendapatkan • R1 ∪ R2 = {(1,1) (1,2) (1,3) (1,4) (2,2) (3,3)} • R1 ∩ R2 = {(1,1)} • R1 – R2 = {(2,2) (3,3)} R2 – R1 = {(1,2) (1,3) (1,4)}
Mengkombinasikan Relasi • R1 adalah relasi dari X ke Y • R2 adalah relasi dari Y ke Z • Komposisi dari R1 dan R2, dinyatakan dengan R2 o R1 adalah relasi dari X ke Z didefinisikan dengan {(x, z) | (x, y)∈ R1 dan (y, z)∈ R2 untuk beberapa y ∈ Y} • Contoh : – R1 = {(1, 2), (3, 6)} – R2 = {(2, u), (6, v)} – Maka R2 o R1 = {(1, u), (3, v)}
Contoh 4 Misalkan D dan S relasi pada A = {1, 2, 3, 4}. D = {(a, b) | b = 5 - a} “b sama dengan (5 – a)” S = {(a, b) | a < b} “a lebih kecil dari b” D = {(1, 4), (2, 3), (3, 2), (4, 1)} (2, 4), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)} S = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} D memetakan suatu anggota a ke anggota (5 – a), S°D = { dan setelah itu S memetakan (5 – a) pada semua anggota yang lebih besar dari (5 – a), yang menghasilkan S°D = {(a,b) | b > 5 – a} atau S°D = {(a,b) | a + b >
Kuasa dari Relasi Definisi. Misalkan R relasi pada himpunan A. Kuasa Rn, n = 1, 2, 3, …, didefinisikan secara induktif R1 = R Rn+1 = Rn°R Dengan kata lain: Rn = R°R° … °R (sebanyak n kali) Teorema. Relasi R pada A transitif jika dan hanya jika Rn ⊆ R untuk setiap bilangan bulat positif n
Contoh : • Misalkan R = {(1,1), (2,1) (3,2) (4,3). Cari Rn n = 1,2,3,4, ... • R2 = R o R maka diperoleh R2 = {(1,1), (2,1), (3,1), (4,2)}, • R3 = R2 o R R3 = {(1,1), (2,1), (3,1), (4,1)}, • R4 = {(1,1), (2,1), (3,1), (4,1)} = R3 • Rn = R3 untuk n = 5, 6, 7, . . .
Representasi Relasi Beberapa cara untuk merepresentasikan relasi: e.g., pasangan terurut. Dua cara lain: matriks nol-satu dan graf berarah (digraf). Jika R relasi dari A = {a1, a2, …, am} ke B = {b1, b2, …, bn}, maka R dapat direpresentasikan oleh matriks nol-satu MR = [mij] dengan mij = 1, jika (ai,bj)∈R, dan mij = 0, jika (ai,bj)∉R. M merupakan matriks berukuran mxn
Contoh : • • • • • •
A = {1,2,3} B = {1,2,3,4} C = {0,1,2} R = {(1,1), (1,4), (2,3), (3,1), (3,4)} S ={(1,0), (2,0), (3,1), (3,2), (4,1)} S o R = {(1,0), (1,1) R (2,1) (2,2) (3,0) S (3,1)}
1 2 3
1 2 3 4
0 1 2
Matematika Diskrit
Fungsi
Fungsi • Fungsi merupakan jenis khusus pada relasi Definisi Fungsi : • Misalkan terdapat himpunan A dan B. Relasi biner f dari A ke B merupakan suatu fungsi jika setiap elemen di dalam A dihubungkan dengan tepat satu elemen di dalam B. Jika f adalah fungsi dari A ke B kita menuliskan f:AÆB yang artinya f memetakan A ke B • Nama lain fungsi adalah pemetaan atau transformasi • Ditulis f(a) = b
Fungsi • Himpunan A disebut daerah asal (domain) dari f • Himpunan B disebut daerah hasil (codomain) dari f • Himpunan yang berisi semua nilai pemetaan f disebut range (jelajah)
• Range dari f = { b | b = f(a) untuk beberapa x ∈A} – Example: – Dom(f) = X = {a, b, c, d}, – Rng(f) = {1, 3, 5}
Contoh • • • •
Daerah asal A = {1,2,3} B = {u,v,w} f = {(1,u),(2,v),(3,w)} Æ fungsi f = {(1,u),(2,u),(3,v)} Æ fungsi f = {{(1,u),(2,u),(1,w)} Æ bukan fungsi
Contoh
fungsi Æ 1 intersection
Bukan fungsi Æ melanggar pada saat > 1
Fungsi One-to-one (satu ke satu) • Fungsi f dikatakan satu ke satu (one-toone) atau 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)1 maka a 2 implikasinya adalah a = b b c
3 4
Properties of Functions •f(Linda) = Moscow •f(Max) = Boston •f(Kathy) = Hong Kong •f(Peter) = Boston •Is f one-to-one? •No, Max and Peter are mapped onto the same element of the image.
g(Linda) = Moscow g(Max) = Boston g(Kathy) = Hong Kong g(Peter) = New York Is g one-to-one? Yes, each element is assigned a unique element of the image.
Contoh • Misalkan f : Z Æ Z. Tentukan apakah f(x)=x2 + 1 dan f(x) = x – 1 merupakan fungsi one to one ? • f(x)=x2 + 1 bukan fungsi one to one karena f(2) = f(-2) = 5 • F(x) = x – 1 adalah fungsi one to one
Contoh – Fungsi f(x) = 2x dari himp bil real • Æ fungsi one-to-one
– Fungsi f(x) = x2 • Æ bukan one-to-one,
karena untuk setiap bil real x f(x) = f(-x).
Fungsi Onto • Fungsi f dikatakan onto atau surjektif jika setiap elemen himp B merupakan bayangan dari satu atau lebih elemen himpunan A. • Dengan kata lain seluruh elemen B merupakan range dari f • Fungsi f disebut fungsi pada himpunan B
Onto ? One to One ?
a
1
b
2
c
3
a b
1
c
2
4 d
3
Onto ? One to One ? a b c d
1
a
2
b
3
c
4
d
1 2 3 4
Jawaban • • • •
One to one Onto One to one dan Onto Bukan One to one dan Onto
Fungsi Bijektif (Bijective) Fungsi f : X→ Y bijektif ⇔ f adalah one-to-one dan onto
–Contoh • Fungsi linear f(x) = ax + b • Fungsi f(x) = x3
Properties of Functions Linda
Boston
Max
New York
Kathy
Hong Kong
Peter
Moscow
•Is f injective? •No. •Is f surjective? •No. •Is f bijective? •No.
Properties of Functions Linda
Boston
Max
New York
Kathy
Hong Kong
Peter
Moscow
Paul
•Is f injective? •No. •Is f surjective? •Yes. •Is f bijective? •No.
Properties of Functions Linda
Boston
Max
New York
Kathy
Hong Kong
Peter
Moscow Lübeck
•Is f injective? •Yes. •Is f surjective? •No. •Is f bijective? •No.
Properties of Functions Linda
Boston
Max
New York
Kathy
Hong Kong
Peter
Moscow Lübeck
•Is f injective? •No! f is not even a function!
Properties of Functions
Linda
Boston
Max
New York
Kathy
Hong Kong
Peter
Moscow
Helena
Lübeck
•Is f injective? •Yes. •Is f surjective? •Yes. •Is f bijective? •Yes.
Fungsi Invers • Terdapat sebuah fungsi y =f(x), fungsi inverse f –1 adalah himpunan {(y,x) | y =f(x)}. • Fungsi one to one sering dinamakan juga fungsi invertible (dapat dibalikkan) • Fungsi bukan one to one sering dinamakan juga fungsi not invertible (tidak dapat dibalikkan)
Inversion Example:
The inverse function f-1 is given by:
f(Linda) = Moscow f(Max) = Boston f(Kathy) = Hong Kong f(Peter) = Lübeck f(Helena) = New York
f-1(Moscow) = Linda f-1(Boston) = Max f-1(Hong Kong) = Kathy f-1(Lübeck) = Peter f-1(New York) = Helena
Clearly, f is bijective.
Inversion is only possible for bijections (= invertible functions)
Inversion Linda
Boston
f
Max
New York
f-1
Kathy
Hong Kong
Peter
Moscow
Helena
Lübeck
•f-1:C→P is no function, because it is not defined for all elements of C and assigns two images to the pre-image New York.
Contoh : • Daerah asal A = {1,2,3} • Daerah asal B = {u,v,w} • F = {(1,u),(2,w),(3,v)} – Adalah fungsi one-to-one – Invers f-1 = {(u,1),(w,2),(v,3)}
Contoh : • Tentukan invers dari f(x) = x – 1 • Fungsi f(x) = x – 1 adalah fungsi one to one, jadi mempunyai invers • f(x) = x – 1 • y=x–1 • x=y+1 • Maka fungsi invers f-1(x) = x + 1
Contoh • Tentukan fungsi invers f(x) = x2 + 1 • Fungsi f(x) = x2 + 1 bukan fungsi one to one sehingga tidak memiliki fungsi invers
Komposisi fungsi • Terdapat dua fungsi g : X → Y dan f : Y → Z, komposisi f ◦ g didefinisikan sebagai berikut : • f ◦ g (x) = f(g(x)) untuk setiap x ∈ X • Contoh : – g(x) = x2 -1, – f(x) = 3x + 5. – g ◦ f(x) = g(f(x)) = g(3x + 5) = (3x + 5)2 - 1
• Komposisi fungsi memenuhi hokum assosiatif : f ◦ (g ◦h) = (f ◦ g) ◦ h tetapi tidak memenuhi hukum komutatif : f ◦ g ≠ g ◦ f.
Composition •The composition of two functions g:A→B and f:B→C, denoted by f°g, is defined by •(f°g)(a) = f(g(a)) •This means that • first, function g is applied to element a∈A, mapping it onto an element of B, • then, function f is applied to this element of B, mapping it onto an element of C. • Therefore, the composite function maps from A to C.
Composition
•Example: •f(x) = 7x – 4, g(x) = 3x, •f:R→R, g:R→R •(f°g)(5) = f(g(5)) = f(15) = 105 – 4 = 101 •(f°g)(x) = f(g(x)) = f(3x) = 21x - 4
Composition •Composition of a function and its inverse: •(f-1°f)(x) = f-1(f(x)) = x •The composition of a function and its inverse is the identity function i(x) = x.
Graphs •The graph of a function f:A→B is the set of ordered pairs {(a, b) | a∈A and f(a) = b}. •The graph is a subset of A×B that can be used to visualize f in a two-dimensional coordinate system.
Floor and Ceiling Functions •The floor and ceiling functions map the real numbers onto the integers (R→Z). •The floor function assigns to r∈R the largest z∈Z with z≤r, denoted by ⎣r⎦. •Examples: ⎣2.3⎦ = 2, ⎣2⎦ = 2, ⎣0.5⎦ = 0, ⎣-3.5⎦ = -4 •The ceiling function assigns to r∈R the smallest z∈Z with z≥r, denoted by ⎡r⎤. •Examples: ⎡2.3⎤ = 3, ⎡2⎤ = 2, ⎡0.5⎤ = 1, ⎡-3.5⎤ = -3
