INF-104 Matematika Diskrit

Relasi dan Fungsi

INF-104 Matematika Diskrit Relasi dan Fungsi

[email protected] Jurusan Informatika FMIPA Unsyiah

March 10, 2014

[email protected]

INF-104 Matematika Diskrit

Relasi dan Fungsi

Fungsi Onto Fungsi Khusus Prinsip Pigeonhole Komposisi Fungsi dan Fungsi Invers

Definisi Suatu fungsi f : A → B disebut pada (onto) atau surjektif (surjective) jika f (A) = B, yaitu jika untuk semua b ∈ B ada sekurang-kurangnya satu a ∈ A dengan f (a) = b. Contoh Fungsi f : R → R yang didefinisikan dengan f (x) = x3 adalah fungsi onto karena jika r adalah bilangan real di kodomain f √ √ maka bilangan real 3 r ada di domain f sehingga f ( 3 r) = r. Jadi kodomain dari f = R = jangkauan dari f . Fungsi g : R → R yang didefinisikan dengan g(x) = x2 bukanlah fungsi onto karena tidak ada bilangan real negatif yang muncul di jangkauan f .

[email protected]


Relasi dan Fungsi


Contoh Misalkan A = {1, 2, 3, 4} dan B = {x, y, z}. Fungsi f1 = {(1, x), (2, y), (3, y), (4, z)} dan f2 = {(1, x), (2, x), (3, y), (4, z)} adalah fungsi-fungsi onto dari A ke B; g = {(1, x), (2, x), (3, x), (4, y)} adalah fungsi dari A ke B tetapi bukan fungsi onto karena g(A) = {x, y} ⊂ B

[email protected]


Relasi dan Fungsi


Jika A, B adalah himpunan-himpunan yang berhingga, jika f : A → B adalah fungsi onto dari A ke B maka |A| ≥ |B|. Jika A, B adalah himpunan-himpunan yang berhingga dengan |A| = m dan |B| = n maka ada sebanyak n X

k

(−1)

k=0

n n−k

(n − k)m

fungsi onto dari A ke B. Jika |A| = m ≥ 2 dan |B| = 2 maka ada sebanyak 2m − 2 fungsi onto dari A ke B.

[email protected]


Relasi dan Fungsi


Contoh Misalkan A = {1, 2, 3, 4, 5, 6, 7} dan B = {w, x, y, z}. Dengan menerapkan formula di atas dengan m = 7 dan n = 4, kita dapatkan bahwa ada sebanyak 4 X k (−1) k=0

4 4−k

(4 − k)7 = 8400

fungsi onto dari A ke B.

[email protected]


Relasi dan Fungsi


Definisi Untuk sebarang himpunan tak-kosong A, B, sebarang fungsi f : A × A → B disebut operasi biner (binary operation) pada A. Jika B ⊆ A maka operasi biner dikatakan tertutup pada A atau sering juga disebut A tertutup di bawah f . Definisi Suatu fungsi g : A → A dikatakan operasi uner (unary) atau monary pada A. Definisi Misalkan f : A × A → B adalah suatu operasi biner pada A. 1

f disebut komutatif jika f (a, b) = f (b, a) untuk semua (a, b) ∈ A × A.

2

Bila B ⊆ A yaitu f tertutup disebut assosiatif jika untuk semua a, b, c ∈ A, f (f (a, b), c) = f (a, f (b, c)). [email protected]


Relasi dan Fungsi


Contoh 1 Fungsi f : Z × Z → Z yang didefinisikan oleh f (a, b) = a − b adalah operasi biner tertutup pada Z. 2

3

4

Jika g : Z+ × Z+ → Z adalah fungsi dimana g(a, b) = a − b adalah operasi biner pada Z+ tetapi tidak tertutup. Sebagai contoh, perhatikan bahwa 3, 7 ∈ Z+ tetapi g(3, 7) = 3 − 7 = −4 ∈ / Z+ . Fungsi h : R+ → R+ didefinisikan oleh h(a) = 1/a adalah operasi uner pada R+ . Didefinisikan operasi biner tertutup f : Z × Z → Z oleh f (a, b) = a + b3ab. Karena penjumlahan dan perkalian bilangan bulat adalah operasi biner komutatif maka diperoleh f (a, b) = a + b3ab = b + a3ba = f (b, a), [email protected] sehingga f adalah komutatif. INF-104 Matematika Diskrit

Relasi dan Fungsi


Definisi Misalkan f : A × A → B adalah suatu operasi biner pada A. Suatu elemen x ∈ A disebut identitas (atau elemen identitas) untuk f jika f (a, x) = f (x, a) = a, untuk semua a ∈ A. Contoh 1 Perhatikan operasi biner tertutup f : Z × Z → Z, dimana f (a, b) = a + b. Disini bilangan bulat 0 adalah suatu identitas karena f (a, 0) = a + 0 = 0 + a = f (0, a) = a, untuk setiap bilangan bulat a. 2

Misalkan A = {1, 2, 3, 4, 5, 6, 7}, dan misalkan g : A × A → A adalah operasi biner tertutup yang didefinisikan oleh g(a, b) = min{a, b} yaitu minimum atau terkecil antara a, b. Operasi biner ini adalah komutatif dan assosiatif, dan untuk sebarang a ∈ A kita dapatkan g(a, 7) = min{a, 7} = a = min{7, a} = g(7, a). Jadi 7 [email protected] adalah elemen identitas untukINF-104 g. Matematika Diskrit

Relasi dan Fungsi


Teorema Misalkan f : A × A → B adalah operasi biner. Jika f memiliki suatu identitas maka identitas tersebut unik.

[email protected]


Relasi dan Fungsi


Definisi Jika m burung merpati menempati n lubang sarang dan m > n maka sekurang-kurangnya ada satu lubang sarang ditempati oleh dua atau lebih merpati. Contoh Suatu kantor mempekerjakan 13 orang pegawai maka ada sekurang-kurangnya dua orang yang memiliki bulan kelahiran yang sama. Dalam hal ini, kita punya 13 merpati (pegawai) dan 12 lubang sarang (bulan dalam setahun). Contoh Larry kembali dari tempat cuci otomat dengan 12 pasang kaus kaki dalam tas binatu (masing-masing pasangan memiliki warna yang berbeda). Mengambil kaus kaki dari tas secara acak, maka dia harus menarik paling banyak 13 kaos kaki untuk mendapatkan pasangan yang cocok. [email protected] INF-104 Matematika Diskrit

Relasi dan Fungsi


Contoh Sebuah file berisi 500000 kata dimana masing-masing kata terdiri dari paling banyak empat huruf kecil. Mungkinkah kata-kata dalam file tersebut semua berbeda? Dari aturan jumlah dan hasilkali, jumlah kata yang berbeda yang mungkin adalah 264 + 263 + 262 + 26 = 475254. Dengan 475254 kata sebagai pigeonhole dan 500000 kata dalam file sebagai merpati, ini berarti bahwa setidaknya ada satu kata diulang di dalam file.

[email protected]


Relasi dan Fungsi


Contoh Misalkan S ⊂ Z+ , dimana |S| = 37, maka S memuat dua elemen yang memiliki sisa yang sama bila dibagi dengan 36. Disini pigeon adalah 37 bilangan bulat positif dalam S. Berdasarkan algoritma pembagian maka untuk sebarang bilangan bulat positif n dibagi dengan 36, terdapat suatu hasilbagi unik q dan sisa unik r dimana n = 36q + r, 0 ≤ r < 36. Jadi 36 kemungkinan nilai r merupakan pigeonhole, sehingga berdasarkan prinsip pigeonhole ada sekurang-kurangnya dua elemen dari S yang memiliki sisa yang sama bila dibagi dengan 36.

[email protected]


Relasi dan Fungsi


Contoh Setiap subhimpunan berukuran 6 dari himpunan S = {1, 2, 3, . . . , 9} harus memuat dua unsur yang jumlahnya adalah 10. Menurut prinsip pigeonhole, dapat diidentifikasikan bahwa pigeon merupakan subhimpunan dari S yang berukuran 6, dan pigeonhole adalah subhimpunan {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. Ketika enam pigeon masuk ke pigeonhole, maka setidaknya ada satu dari pigeonhole yang berisikan dua pigeon.

[email protected]


Relasi dan Fungsi


Contoh Buktikan bahwa jika 101 bilangan bulat dipilih dari himpunan S = {1, 2, 3, · · · , 200}, maka ada dua bilangan bulat dimana satu elemen membagi elemen lainnya. Untuk setiap x ∈ S, kita dapat menulis x = 2k y dengan k > 0 dan F P B(2, y) = 1 (teorema dasar aritmatika). Kemudian y harus ganjil, sehingga diperoleh y ∈ T = {1, 3, 5, · · · , 199}, di mana |T | = 100. Karena 101 bilangan bulat dipilih dari S maka menurut prinsip pigeonhole, ada dua bilangan bulat yang berbeda bentuk a = 2m y, b = 2n y untuk beberapa y ∈ T . Jika m < n, maka a|b, jika tidak, kita memiliki m > n sehingga b|a.

[email protected]


Relasi dan Fungsi


Definisi Jika f : A → B maka f disebut bijektif (bijective) atau berkorespondensi satu-satu (one-to-one correspondence) jika f adalah satu ke satu dan onto. Contoh Jika A = {1, 2, 3, 4} dan B = {w, x, y, z} maka f = {(1, w), (2, x), (3, y), (4, z)} adalah suatu korespondensi satu-satu dari A ke B dan g = {(w, 1), (x, 2), (y, 3), (z, 4)} adalah suatu korespondensi satu-satu dari B ke A. Definisi Fungsi IA : A → A, didefinisikan oleh IA (a) = a untuk semua a ∈ A, disebut fungsi identitas (identity function) untuk A. [email protected]


Relasi dan Fungsi


Definisi Jika f, g : A → B, kita katakan bahwa f dan g adalah sama (equal) dan ditulis f = g, jika f (a) = g(a) untuk semua a ∈ A. Contoh Misalkan f : Z → Z, g : Z → Q dimana f (x) = x = g(x), untuk semua x ∈ Z maka f, g memiliki domain yang sama yaitu Z dan juga memiliki range yang sama yaitu Z akan tetapi f 6= g. Perhatikan bahwa f adalah fungsi bijektif sedangkan g adalah fungsi satu-ke-satu tetapi tidak onto. Jadi terlihat bahwa kodomain dapat membuat perbedaan.

[email protected]


Relasi dan Fungsi


Definisi Jika f : A → B dan g : B → C, kita definisikan fungsi komposit (composite function)yang dinotasikan oleh g ◦ f : A → C, dengan (g ◦ f )(a) = g(f (a)) untuk setiap a ∈ A. Contoh Misalkan A = {1, 2, 3, 4}, B = {a, b, c} dan C = {w, x, y, z} dengan f : A → B dan g : B → C yang diberikan oleh f = {(1, a), (2, a), (3, b), (4, c)} dan g = {(a, x), (b, y), (c, z)}. Untuk setiap elemen dari A kita dapatkan: (g ◦ f )(1) = g(f (1)) = g(a) = x (g ◦ f )(3) = g(f (3)) = g(b) = y (g ◦ f )(2) = g(f (2)) = g(a) = x (g ◦ f )(4) = g(f (4)) = g(c) = z Jadi g ◦ f = {(1, x), (2, x), (3, y), (4, z)}. Catatan: f ◦ g tak terdefinisi. [email protected]


Relasi dan Fungsi


Contoh Misalkan f : R → R, g : R → R yang didefinisikan oleh f (x) = x2 , g(x) = x + 5, maka (g ◦ f )(x) = g(f (x)) = g(x2 ) = x2 + 5. Juga diperoleh (f ◦ g)(x) = f (g(x)) = f (x + 5) = (x + 5)2 = x2 + 10x + 25. Dari kedua komposisi fungsi di atas kita dapatkan g ◦ f : R → R dan f ◦ g : R → R terdefinisi, tetapi (g ◦ f )(1) = 6 6= 36 = (f ◦ g)(1). Jadi walaupun kita dapat membentuk komposisi fungsi f ◦ g dan g ◦ f , kita dapatkan bahwa f ◦ g 6= g ◦ f . Dengan kata lain, komposisi fungsi tidak komutatif. [email protected]


Relasi dan Fungsi


Teorema Misalkan f : A → B dan g : B → C 1

Jika f dan g satu-ke-satu maka g ◦ f adalah satu-ke-satu.

2

Jika f dan g onto maka g ◦ f adalah onto.

Teorema Jika f : A → B, g : B → C dan h : C → D maka (h ◦ g) ◦ f = h ◦ (g ◦ f ).

[email protected]


Relasi dan Fungsi


Definisi Jika f : A → A, kita definisikan f 1 = f dan untuk n ∈ Z+ , f n = f ◦ (f n−1 ) Contoh Dengan A = {1, 2, 3, 4} dan f : A → A yang didefinisikan oleh f = {(1, 2), (2, 2), (3, 1), (4, 3)}, kita peroleh f 2 = f ◦ f = {(1, 2), (2, 2), (3, 2), (4, 1)} dan f 3 = f ◦ f 2 = f ◦ f ◦ f = {(1, 2), (2, 2), (3, 2), (4, 2)}. Coba cari f 4 , f 5 , f 6 .

[email protected]


Relasi dan Fungsi


Definisi Untuk himpunan A, B, jika R adalah relasi dari A ke B maka konversi (converse) dari R dan dinotasikan oleh Rc , adalah relasi dari B ke A yang didefinisikan oleh Rc = {(b, a)|(a, b) ∈ R}. Contoh Untuk A = {1, 2, 3} dan B = {w, x, y}, misalkan f : A → B yang diberikan oleh f = {(1, w), (2, x), (3, y)}. Maka f c = {(w, 1), (x, 2), (y, 3)} adalah fungsi dari B ke A. Kita juga peroleh bahwa f c ◦ f = IA dan f ◦ f c = IB .

[email protected]


Relasi dan Fungsi


Definisi Jika f : A → B, maka f dikatakan punya invers (invertible) jika ada suatu fungsi g : B → A sedemikian sehingga g ◦ f = IA dan f ◦ g = IB . Contoh Misalkan f, g : R → R yang didefinisikan oleh f (x) = 2x + 5, g(x) = (1/2)(x − 5). Maka (g ◦ f )(x) = g(f (x)) = g(2x + 5) = (1/2)[(2x + 5) − 5] = x, dan (f ◦ g)(x) = f (g(x)) = f ((1/2)(x − 5)) = 2[(1/2)(x − 5)] + 5 = x. Jadi f ◦ g = IR dan g ◦ f = IR . Akgibatnya f dan g keduanya adalah fungsi yang punya invers.

[email protected]


Relasi dan Fungsi


Teorema Jika suatu fungsi f : A → B punya invers dan fungsi g : B → A memenuhi g ◦ f = IA dan f ◦ g = IB maka fungsi g ini unik. Teorema Suatu fungsi f : A → B punya invers jika dan hanya jika fungsi f satu-ke-satu dan onto. Teorema Jika f : A → B, g : B → C adalah fungsi-fungsi yang punya invers maka C : A → C punya invers dan (g ◦ f )−1 = f −1 ◦ g −1 .

[email protected]


Relasi dan Fungsi


Definisi Jika f : A → B dan B1 ⊆ B maka f −1 (B1 ) = {x ∈ A|f (x) ∈ B1 }. Himpunan f −1 (B1 ) disebut prabanyangan (preimage) dari B1 di bawah f . Teorema Jika f : A → B dan B1 , B2 ⊆ B maka 1

f −1 (B1 ∩ B2 ) = f −1 (B1 ) ∩ f −1 (B2 ).

2

f −1 (B1 ∪ B2 ) = f −1 (B1 ) ∪ f −1 (B2 ).

3

f −1 (B1 ) = f −1 (B1 ).

[email protected]


Relasi dan Fungsi


Teorema Misalkan f : A → B untuk himpunan berhingga A dan B, dimana |A| = |B|. Maka pernyataan-pernyataan berikut ini ekuivalen: 1

f satu-ke-satu.

2

f onto.

3

f punya invers.

[email protected]


INF-104 Matematika Diskrit

Recommend Documents