Materi MatDis (Matematika Diskrit) : Relasi & Fungsi

Relasi Relasi antara himpunan A dan B disebut relasi biner didefinisikan sebagai berikut : Relasi biner R antara A dan B adalah himpunan bagian dari A x B. Notasi : R ⊆(A x B). Jika (a, b) ∈ R, kita gunakan notasi a R b yang artinya a dihubungkan dengan b oleh R, dan jika (a, b) ∉ R, kita gunakan notasi a Ɍ b yang artinya a tidak dihubungkan oleh b oleh relasi R. Himpunan A disebut daerah asal (domain) dari R dan himpunan B disebut daerah hasil (range atau codomain) dari R. Contoh : Misalkan A = {Amir, Budi, Cecep} adalah himpunan nama mahasiswa dan B = {IF221, IF251, IF342,IF323} adalah himpunan kode mata kuliah di Jurusan Teknik Informatika. Perkalian kartesian antara A dan B menghasilkan himpunan pasangan terurut yang jumlah anggotanya adalah | A | . | B | = 3 . 4 = 12 buah, yaitu A x B = {(Amir, IF221), (Amir, IF251), (Amir, IF342), (Amir, IF323), (Budi, IF221), (Budi, IF251), (Budi, IF342), (Budi, IF323), (Cecep, IF221), (Cecep, IF251), (Cecep, IF342), (Cecep, IF323)} Misalkan R adalah relasi yang menyatakan mata kuliah yang diambill oleh mahasiswa pada Semester Ganjil, yaitu R = {(Amir, IF251), (Amir, IF323), (Budi, IF221), (Budi, IF251), (Cecep, IF323)} Kita dapat melihat bahwa R⊆ ( A x B ), A adalah daerah asal R dan B adalah daerah hasil R. Oleh karena (Amir, IF251) ∈ R, kita dapat menuliskan Amir R IF251 tetapi (Amir, IF342) ∉ R sehingga kita menuliskan Amir Ɍ IF342. Misalkan P = {2, 3, 4} dan Q = {2, 4, 8, 9, 15}. Jika kita definisikan relasi R dari P ke Q dengan (p, q) ∈ R jika p habis membagi q. Maka kita peroleh R = {(2, 2), (2, 4), (4, 4), (2, 8), (4, 8), (3, 9), (3, 15)} Relasi pada himpunan A adalah relasi dari A x A. Dengan kata lain, relasi pada himpunan A adalah himpunan bagian dari A x A. Contoh : Misalkan R adalah relasi pada A = {2, 3, 4, 8, 9} yang didefinisikan oleh (x, y) ∈ R jika x adalah faktor prima dari y. Maka R = {(2, 2), (2, 4), (2, 8), (3, 3), (3, 9)} Representasi Relasi Disajikan 3 cara yang lazim dipakai untuk mempresentasikan relasi, yaitu dengan tabel, matriks dan graf berarah. Representasi Relasi dengan Tabel Kolom pertama tabel menyatakan daerah asal sedangkan kolom kedua menyatakan daerah hasil. Kita tidak mempresentasikan relasi pada sebuah himpunan dengan tabel karena tidak lazim dilakukan. Representasi Relasi dengan Matriks Representasi Relasi dengan Graf Berarah Tiap elemen himpunan dinyatakan dengan sebuah titik (disebut juga simpul atau vertex) dan tiap pasangan terurut dinyatakan dengan busur (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 vertex) dan simpul b disebut simpul tujuan (terminal vertex). Pasangan terurut (a, a) dinyatakan dengan busur dari simpul a ke simpul a sendiri. Busur semacam itu disebut gelang atau kalang (loop). Relasi Inversi Jika R adalah relasi pada himpunan orang-orang di mana (a, b) ∈ jika a adalah ayah dari b, maka kita dapat membuat kebalikan relasinya , yaitu (b, a) yang menyatakan b adalah anak dari a. Relasi baru tersebut dinamakan inversi dari relasi semula. Begitu pula relasi “lebih besar dari” mempunyai inversi “lebih kecil dari”, relasi “lebih tua dari” mempunyai inversi “lebih muda dari”. Secara umum, jika diberikan relasi R dari himpunan A ke himpunan B, kita bisa mendefinisikan relasi baru dari B ke A dengan cara membalik urutan dari setiap pasangan terurut di dalam R. Definisi Relasi inversi adalah sebagai berikut : Misalkan R adalah relasi dari himpunan A ke himpunan B. Inversi dari relasi R, dilambangkan dengan R-1, adalah relasi dari B ke A yang didefinisikan oleh R-1 = {(b, a) | (a, b) ∈ R } Contoh : Misalkan P = {2, 3, 4} dan Q = {2, 4, 8, 9, 15}. Jika kita definisikan relasi R dari P ke Q dengan (p, q) ∈ R jika p habis membagi q Maka kita peroleh R = {(2, 2), (2, 4), (4, 4), (2, 8), (4, 8), (3, 9), (3, 15)} R-1 adalah invers dari relasi R, yaitu relasi dari Q ke P dengan (q, p) ∈ R-1 jika q adalah kelipatan dari p Maka kita peroleh R-1 = {(2, 2), (4, 2), (4, 4), (8, 2), (8, 4), (9, 3), (15, 3)} 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 operasi R1 ∩ R2, R1 ∪ R2, R1 – R2 dan R1 ⊕ R2 juga adalah relasi dari A ke B. Contoh : Misalkan A = {a, b, c} dan B = {a, b, c, d}. Relasi R1 = {(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 kedua buah relasi tersebut untuk memperoleh : R1 ∩ R2 = {(a, a)} R1 ∪ R2 = {(a, a), (b, b), (c, c), (a, b), (a, c), (a, d)} R1 – R2 = {(b, b), (c, c)} R2 – R1 = {(a, b), (a, c), (a, d)} R1 ⊕ R2 = {(b, b), (c, c), (a, b), (a, c), (a, d)} Komposisi Relasi Cara lain mengkombinasikan relasi adalah dengan mengkomposisikan dua buah relasi atau lebih. Definisi dari komposis dua buah relasi didefinisikan sebagai berikut. 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 S o R, adalah relasi dari A ke C yang didefinisikan oleh S o R = {(a, c) | a ∈ A, c ∈ C, dan untuk beberapa b ∈ B, (a, b) ∈ R dan (b, c) ∈ S} Dengan kata lain, kita menerapkan relasi R lebih dahulu baru kemudian relasi S. Contoh : 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 himpunan {2, 4, 6, 8} ke himpunan {s, t, u}. Maka komposisi relasi R dan S adalah S o R = {(1, u), (1, t), (2, s), (2, t), (3, s), (3, t), (3, u)} Sifat – sifat Relasi Relasi pada sebuah himpunan adalah kasus yang paling sering dijumpai. Relasi ini mempunyai beberapa sifat. Sifat-sifat yang paling penting didefinisikann di bawah ini Refleksif (reflexive) Relasi R pada himpunan A disebut refleksif jika (a, a) ∈ R untuk setiap a ∈ A. Dengan kata lain, bahwa di dalam relasi refleksif setiap elemen di dalam A berhubungan dengan dirinya sendiri. Menyatakan bahwa relasi R pada himpunan A tidak refleksif jika ada a ∈ A sedemikian sehingga (a, a) ∉ R. Contoh : Misalkan A = {1, 2, 3, 4} dan relasi R di bawah ini didefnisikan pada himpunan A, maka Relasi 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). Relasi R = {(1, 1), (2, 2), (2, 3), (4, 2), (4, 3), (4, 4)} tidak bersifat refleksif karena (3, 3) ∉ R. Relasi “habis membagi” pada himpunan bilangan bulat positif bersifat refleksif karena setiap bilangan bulat positif selalu habis membagi dirinya sendiri, sehingga (a, a) ∈ R untuk setiap a ∈ A. Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif N. R : x lebih besar dari y, S : x + y = 5, T : 3x + y = 10 Tidak satupun dari ketiga relasi di atas yang refleksif karena, misalkan (2, 2) bukan anggota R, S maupun T. Setangkup (symmetric) dan Tolak-setangkup (antisymmetric) Relasi R pada himpunan A disebut setangkup jika (a, b) ∈ R, maka (b, a) ∈ R, untuk semua a, b ∈ A. Relasi R pada himpunan A disebut tolak-setangkup jika (a, b) ∈ R dan (b, a) ∈ R maka a = b, untuk semua a, b ∈ A. Istilah setangkup dan tolak-setangkup 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. Contoh : Misalkan A = {1, 2, 3, 4} dan relasi R di bawah ini didefinisikan pada himpunan A, maka Relasi 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. Di sini (1, 2) dan (2, 1) ∈ R, begitu juga (2, 4) dan (4, 2) ∈ R. Relasi R = {(1, 1), (2, 3), (2, 4), (4, 2)} tidak setangkup karena (2, 3) ∈ R, tetapi (3, 2) ∉ R. Relasi R = {(1, 1), (2, 2), (3, 3)} tolak-setangkup karena (1, 1) ∈ R dan 1 = 1, (2, 2) ∈ R dan 2 = 2, (3, 3) ∈ R dan 3 = 3. Perhatikan bahwa R juga setangkup. Relasi R = {(1, 1), (1, 2), (2, 2), (2, 3)} tolak-setangkup karena (1, 1) ∈ R dan 1 = 1 dan (2, 2) ∈ R dan 2 = 2 dan perhatikan bahwa R tidak setangkup. Relasi R = {(1, 1), (2, 4), (3, 3), (4, 2)} tidak tolak-setangkup karena 2 ≠ 4 tetapi (2, 4) dan (4, 2) anggota R. Relasi R pada (a) dan (b) di atas juga tidak tolak-setangkup. Relasi R = {(1, 2), (2, 3), (1, 3)} tidak setangkup tetapi tolak-setangkup. Relasi “habis membagi” pada himpunan bilangan bulat positif tidak setangkup karena jika a habis membagi b, b tidak habis membagi a, kecuali jika a = b. Sebagai contoh, 2 habis membagi 4, tetapi 4 tidak habis membagi 2. Karena itu, (2, 4) ∈ R tetapi (4, 2) ∉ R. Relasi “habis membagi” tolak setangkup karena jika a habis membagi b dan b habis membagi a maka a = b. Sebagai contoh, 4 habis membagi 4. Karena itu, (4, 4) ∈ R dan 4 = 4. Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif N. R : x lebih besar dari y, S : x + y = 6, T : 3x + y = 10 R bukan relasi setangkup karena, misalkan 5 lebih besar dari 3 tetapi 3 tidak lebih besar dari 5. S relasi setangkup karena (4, 2) dan (2, 4) adalah anggota S. T tidak setangkup karena, misalkan (3, 1) adalah anggota T tetapi (1, 3) bukan anggota T. S bukan relasi tolak-setangkup karena, misalkan (4, 2) ∈ S tetapi 4 ≠ 2. Relasi R dan T keduanya tolak-setangkup. Menghantar (transitive) Relasi R pada himpunan A disebut menghantar jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk semua a, b, c ∈ A. Contoh : Misalkan A = {1, 2, 3, 4} dan relasi R di bawah ini didefinisikan pada himpunan A, maka R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} bersifat menghantar. R = {(1, 1), (2, 3), (2, 4), (4, 2)} tidak menghantar karena (2, 4) dan (4, 2) ∈ R, tetapi (2, 2) ∉ R, begitu juga (4, 2) dan (2, 3) ∈ R, tetapi (4, 3) ∉ R. Relasi R = {(1, 1), (2, 2), (3, 3), (4, 4)} jelas menghantar. Relasi R = {(1, 2), (3, 4)} menghantar karena tidak ada (a, b) ∈ R dan (b, c) ∈ R sedemikian sehingga (a, c) ∈ R. Relsi yang hanya berisi satu elemen seperti R = {(4, 5)} selalu menghantar. Relasi “habis membagi” 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 b = ma dan c = nb. Di sini c = nma, sehingga a habis membagi c. Jadi, relasi “habis membagi” bersifat menghantar. Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif N. R : x lebih besar dari y, S : x + y = 6, T : 3x + y = 10 R adalah relasi menghantar karena jika x > y dan y > z maka x > z. S tidak menghantar karena, misalkan (4, 2) dan (2, 4) adalah anggota S tetapi (4, 4) ∉ S. Sebaliknya, T = {(1, 7), (2, 4), (3, 1)} tidak menghantar. Suatu relasi dapat mengandung beberapa sifat sekaligus atau sama sekali tidak mengandung sifat apa pun sama sekali. Contoh : Misalkan R adalah relasi yang didefinisikan pada himpunan bilangan bulat (integer) yang dalam hal ini (x, y) ∈ R jika x adalah kelipatan dari y. Tentukan apakah R refleksif, setangkup, tolak-setangkup dan/atau menghantar dengan menyebutkan masing-masing alasannya. Penyelesaian: Berdasarkan pernyataan “(x, y) ∈ R jika x adalah kelipatan dari y“ kita dapat menuliskannya sebagai x = ky, yang dalam hal ini k = 0, 1, 2, ... Jadi (x, y) = (kx, y) ∈ R. R bersifat refleksif, tolak-setangkup dan menghantar tetapi R tidak setangkup: R refleksif sebab untuk k = 1, (y, y) ∈ R. Misalnya (4, 4), (5, 5), dst adalah ∈ R. R tidak setangkup sebab x ≥ y sehingga tidak mungkin y adalah kelipatan dari x kecuali jika x = y. R tolak-setangkup karena (x, y) ∈ R dan (y, x) ∈ R jika x = y. R menghantarsebab jika x = ky dan y = mz, maka di sini x = kmz, sehingga x juga kelipatan z. Contohnya jika (8, 4) ∈ R dan (4, 2) ∈ R, maka (8, 2) ∈ R. Fungsi Misalkan A dan B himpunan. 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 untuk fungsi adalah pemetaan atau transformasi. Kita menuliskan f(a) = b jika elemen a di dalam A dihubungkan dengan elemen b di dalam B. himpunan A disebut daerah asal (domain) dari f dan himpunan B disebut daerah hasil (codomain) dari f. Jika f(a) = b, maka b dinamakan bayangan (image) dari a dan a dinamakan pra-bayangan (pre-image) dari b. Himpunan yang berisi semua nilai pemetaan f disebut jelajah (range) dari f. Perhatikan bahwa jelajah dari f adalah himpunan bagian (mungkin proper subset) dari B. Merepresentasikan fungsi dari A ke B. Contoh : Relasi f = {(1, u), (2, v), (3, w)} dari A = {1, 2, 3} ke B = {u, v, w} adalah fungsi dari A ke B. Di sini f(1) = u, f(2) = v dan f(3) = w. Daerah asal dari f adalah A dan daerah hasil adalah B. Jelajah dari f adalah {u, v, w} yang dalam hal ini sama dengan himpunan B. 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. Daerah asal fungsi adalah A, daerah hasilnya adalah B dan jelajah fungsi adalah {u, v} Relasi f = {(1, u), (2, v), (3, w)} dari A = {1, 2, 3, 4} ke B = {u, v, w} bukan fungsi karena tidak semua elemen A dipetakan ke B. Relasi f = {(1, u), (1, v), (2, v), (3, w)} dari A = {1, 2, 3} ke B = {u, v, w} bukan fungsi karena 1 dipetakan ke dua buah elemen B yaitu u dan v. Misalkan f : Z → Z didefinisikan oleh f(x) = x2 . Daerah asal dan daerah hasil dari f adalah himpunan bilangan bulat dan jelajah dari f adalah himpunan bilangan bulat tidak-negatif (karena kuadrat dari sembarang bilangan bulat tidak mungkin negatif). Misalkan A adalah himpunan mahasiswa di ITB. Manakah dari pemetaan berikut yang mendefinisikan sebuah fungsi pada himpunan A? Setiap mahasiswa memetakan NIM (Nomor Induk Mahasiswa). Setiap mahasiswa memetakan nomor handphone-nya. Setiap mahasiswa memetakan dosen walinya. Setiap mahasiswa memetakan anaknya. Penyelesaian : Ya, karena setiap mahasiswa hanya mempunyai satu buah NIM. Tidak, karena ada mahasiswa yang mempunyai lebih dari satu nomor HP atau tidak mempunyai HP sama sekali. Ya, karena setiap mahasiswa hanya mempunyai 1 orang dosen wali. Tidak, jika ada mahasiswa yang belum menikah. Berdasarkan bayangannya, fungsi dibedakan menjadi 3 : Fungsi satu-ke-satu (one-to-one) 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. jika f(a) = f(b) maka implikasinya adalah a = b. Contoh : 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. Misalkan f : Z → Z. Tentukan apakah f(x) = x2 + 1 dan f(x) = x2 – 1 merupakan fungsi satu-ke-satu? Penyelesaian : f(x) = x2 + 1 bukan fungsi satu-ke-satu karena untuk dua x yang bernilai mutlak sama tetapi tandanya berbeda nilai fungsinya sama, misalnya f(2) = f(-2) = 5 padahal -2 ≠ 2. f(x) = x – 1 adalah fungsi satu-ke-satu karena untuk a ≠ b, a – 1 ≠ b – 1. Misalnya untuk x = 2, f(2) = 1 dan untuk x = -2, f(-2) = -3. Fungsi pada (onto) Fungsi f dikatakan pada (onto) atau surjektif (surjective) jika setiap elemen himpunan B merupakan bayangan dari satu atau lebih elemen himpunan A. Dengan kata lain seluruh elemen B merupakan jelajah dari f. Fungsi f disebut fungsi pada himpunan B. Contoh : 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 jelajah 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 anggota B merupakan jelajah dari f. Misalkan f : Z → Z. Tentukan apakah f(x) = x2 + 1 dan f(x) = x – 1 merupakan fungsi pada? Penyelesaian : f(x) = x2 + 1 bukan fungsi pada, karena tidak semua nilai bilangan bulat merupakan jelajah dari f. Misalnya tidak ada nilai x yang membuat nilai fungsi sama dengan 0, yaitu x2 + 1 = 0 tidak dipenuhi untuk nilai x berapapun. f(x) = x – 1 adalah fungsi pada karena untuk setiap bilangan bulat y, selalu ada nilai x yang memenuhi, yaitu y = x – 1 akan dipenuhi untuk x = y + 1. Bijeksi (bijection) Fungsi f dikatakan berkoresponden satu-ke-satu atau bijeksi (bijection) jika ia fungsi satu-ke-satu dan juga fungsi pada. Contoh : 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, karena f adalah fungsi satu-ke-satu maupun fungsi pada. Tugas : Buatlah contoh dari : Relasi kesetaraan Relasi pengurutan parsial Fungsi (Into, Onto, Bijektif) Jawab : Relasi kesetaraan A = {1, 2, 3} R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)} Refleksif : {(1, 1), (2, 2), (3, 3)} Transitif : {(1, 2), (2, 1), (1, 1), (2, 3), (3, 2), (2, 2), (3, 1), (3, 2), (1, 3), (3, 3)} Simetris : {(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)} Relasi pengurutan parsial A = {1, 2, 3} R = {(1, 1), (2, 3), (2, 2), (3, 1), (3, 3), (2, 1)} Refleksif : {(1, 1), (2, 2), (3, 3)} Transitif : {(2, 3), (3, 1), (2, 1)} Antisimetris : {(2, 3), (3, 1), (2, 1)}