Materi MatDis (Matematika Diskrit) : Permutasi dan Kombinasi

PERMUTASI Permutasi adalah jumlah urutan berbeda dari pengaturan objek-objek. Permutasi merupakan bentuk khusus aplikasi aturan perkalian. Misalkan jumlah objek adalah n, maka urutan pertama dipilih dari n objek, urutan kedua dipilih dari n – 1 objek, urutan ketiga dipilih dari n – 2 objek, begitu seterusnya dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian, permutasi dari n objek adalah n(n – 1) (n – 2) . . . (2)(1) = n! Menurut kaidah perkalian, ada sebanyak n(n – 1) (n – 2) . . . (n – (r – 1)) buah susunan berbeda dari penyusunan r objek yang dipilih dari n objek. Jumlah susunan berbeda dari pemilihan r objek yang diambil dari n objek disebut permutasi-r, dilambangkan dengan P(n, r), yaitu P(n, r) = n(n – 1)(n – 2). . . (n – (r – 1)) = n!/(n-r)! Menurut persamaan tersebut, jumlah cara memasukkan 6 buah bola yang berbeda warnanya ke dalam 3 buah kotak adalah P(6, 3) = 6!/(6 - 3)! = 120 dan jumlah kemungkinan urutan 2 dari 3 elemen himpunan A = {a, b, c} adalah P(3, 2) = 3!/(3 – 2)! = 6. Permutasi r dari n objek adalah jumlah kemungkinan urutan r buah objek yang dipilih dari n buah objek, dengan r ≤ n, yang dalam hal ini, pada setiap kemungkinan urutan tidak ada objek yang sama. Bila r = n, maka P(n, n) = n!/(n-n)! = n!/0! = n!/1 = n! Contoh : Berapa banyak “kata” yang terbentuk dari kata “BOSAN”? Penyelesaian : Anggap setiap huruf di dalam kata “BOSAN” sebagai bola yang berbeda warnanya dan 5 buah kotak yang akan diisi dengan 1 bola pada setiap kotak. Cara 1 : (5)(4)(3)(2)(1) = 120 buah kata Cara 2 : P(5, 5) = 5! = 120 buah kata Berapa banyak cara mengurutkan nama 25 orang mahasiswa? Penyelesaian : Analogikan dengan mengisi 25 kotak dengan 25 bola huruf berbeda, setiap kotak diisi dengan 1 bola. Jadi, jumlah cara pengurutan nama mahasiswa sama dengan jumlah susunan 25 bola ke dalam 25 kotak, yaitu P(25, 25) = 25! Tiga buah ujian dilakukan dalam suatu periode enam hari (Senin sampai Sabtu). Berapa banyak pengaturan jadwal yang dapat dilakukan sehingga tidak ada dua ujian atau lebih yang dilakukan pada hari yang sama. Penyelesaian : Cara 1 (dengan kaidah perkalian) : sama seperti menempatkan 3 bola (ujian) berbeda ke dalam enam kotak (hari). Ujian pertama dapat ditempatkan pada salah satu dari enam hari; Ujian kedua dapat ditempatkan pada salah satu dari lima hari; Ujian ketiga dapat ditempatkan pada salah satu dari empat hari; Jumlah pengaturan jadwal ujian = (6)(5)(4) = 120 Cara 2 (dengan rumus permutasi) : P(6, 3) = 6! / (6 – 3)! = 120 Sebuah bioskop mempunyai jajaran kursi yang disusun per baris. Tiap baris terdiri dari 6 tempat kursi. Jika dua orang akan duduk, berapa banyak pengaturan tempat duduk yang mungkin pada suatu baris? Penyelesaian : Orang pertama mempunyai 6 pilihan kursi dan orang kedua mempunyai 5 pilihan kursi. Jadi, jumlah pengaturan tempat duduk = (6)(5) = 30 atau P(6, 2) = 6! / 4! = (6)(5) = 30 cara Berapa banyak string yang dapat dibentuk yang terdiri dari 4 huruf berbeda dan diikuti dengan 3 angka yang berbeda pula? Penyelesaian : Ada P(26, 4) cara mengisi posisi 4 huruf dan P(10, 3) cara untuk mengisi posisi 3 buah angka. Karena string disusun oleh 4 huruf dan 3 angka, maka jumlah string yang dapat dibuat adalah P(26, 4) x P(10, 3) = 258.336.000 KOMBINASI Bentuk khusus dari permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan. Urutan acb, bca dan acb dianggap sama dan dihitung sekali. Secara umum, jumlah cara memasukkan r buah bola yang berwarna sama ke dalam n buah kotak adalah (n(n-1)(n-2)...(n-(r-1)))/r! = n!/r!(n-r)! Rumus n!/r!(n-r)! Disebut rumus kombinasi-r dan dilambangkan dengan C(n, r) atau (n¦r). Jadi, C(n, r) = n!/r!(n-r)! C(n, r) sering dibaca “n diambil r”, artinya r objek diambil dari n buah objek. Kombinasi r elemen dari n elemen adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen. Dapat juga dibuktikan dengan cara membentuk permutasi-r dari n elemen. Mula-mula hitung kombinasi-r , yaitu C(n , r), kemudian urutkan elemen-elemen di dalam setiap kombinasi-r. Pengurutan ini dapat dilakukan dengan P(r, r) cara. Dengan demikian, permutasi-r dari n elemen adalah P(n, r) = C(n, r) P(r, r) Dari persamaan di atas kita peroleh C(n, r) = (P(n,r))/(P(r,r)) = (n!/(n-r)!)/r!(r-r)! = n!/r!(n-r)! Contoh : Berapa banyak cara menyusun menu nasi goreng tiga kali seminggu untuk sarapan pagi? Penyelesaian : Bayangkan tiga kali menu nasi goreng sebagai tiga buah bola dan tujuh hari dalam seminggu sebagai 7 buah kotak. Persoalan ini sama dengan menempatkan 3 buah bola ke dalam 7 buah kotak. Banyaknya pengaturan jadwal menu nasi goreng adalah C(7, 3) = 7!/3!4! = 35 cara. String biner yang panjangnya 32 bit disusun oleh angka 1 atau 0. Berapa banyak string biner yang tepat berisi 7 buat bit 1? Penyelesaian : Analogikan 7 bit 1 sebagai 7 buah bola dan 32 posisi bit sebagai 32 buah kotak. Persoalan ini sama dengan memasukkan 7 bola ke dalam 32 kotak, sisanya kosong (0). Banyak string biner yang terbentuk adalah C(32, 7). Sebuah koin yang mempunyai sisi A dan sisi B dilempar ke atas sebanyak empat kali. Berapakah jumlah kemungkinan munculnya sisi A sebanyak tiga kali? Penyelesaian : Ini adalah persoalan dari kombinasi karena kita tidak mementingkan kapan sisi A tersebut muncul. Jadi, jumlah kemungkinan munculnya sisi A sebanyak tiga kali adalah C(4, 3) = 4. Tiga buah apartemen A, B dan C disewakan untuk mahasiswa. Tiap unit apartemen dapat menampung 3 atau 4 orang mahasiswa. Berapa jumlah cara menyewakan apartemen kepada 10 orang mahasiswa? Penyelesaian : Andaikan apartemen A, B, C ditempati masing-masing oleh 4, 3 dan 3 orang mahasiswa. Jumlah cara menyewakan = C(10, 4) x C(6, 3) x C(3, 3) Andaikan apartemen A, B, C ditempati masing-masing oleh 3, 4 dan 3 orang mahasiswa. Jumlah cara menyewakan = C(10, 3) x C(7, 4) x C(3, 3) Andaikan apartemen A, B, C ditempati masing-masing oleh 3, 3 dan 4 orang mahasiswa. Jumlah cara menyewakan = C(10, 3) x C(7, 3) x C(4, 4) Total seluruh cara menyewakan = C(10, 4)C(6, 3) + C(10, 3)C(7, 4) + C(10, 3)C(7, 3) = 3C(10, 4)C(6, 3). PERMUTASI DAN KOMBINASI BENTUK UMUM P(n;n_1,n_2, ... , n_k) = (P(n,n))/(n_1 !n_(2!…n_k !) ) = n!/(n_1 !n_(2!…n_k !) ) Persamaan ini diterapkan untuk menghitung pengaturan (atau pengurutan) n buah objek dari himpunan ganda S (himpunan S terdiri dari n buah objek yang tidak perlu semuanya berbeda). Persamaan tersebut dinamakan permutasi bentuk umum (generalized permutation) terhadap S. C(n;n_1,n_2, ... , n_k) = C(n, n_1) C(n - n_1, n_2) C(n - n_1 - n_2, n_3) . . . C(n - n_1 - n_2 - . . . - n_(k-1), n_k) = n!/(n_(1 ) !(n- n_1 )!) (n-n_(1 ) )!/(n_2 !(n- n_1- n_2 )!) (n- n_1- n_2 )!/(n_3 !(n- n_1- n_2- n_k )!) . . . ((n- n_1- n_2- n_(k-1) )! )/(n_k !(n- n_1- n_2-…- n_(k-1)- n_k )!) = n!/(n_1 !n_(2!…n_k !) ) Persamaan ini dinamakan kombinasi bentuk umum (generalized combination). Kita dapat melihat bahwa tidak ada perbedaan antara permutasi bentuk umum dengan kombinasi bentuk umum. Keduanya dapat dihitung dengan rumus yang sama. Jadi, apabila S adalah himpunan ganda dengan n buah objek yang di dalamnya terdiri atas k jenis objek berbeda dan tiap objek memiliki multiplisitas n_1, n_2, . . ., n_k (jumlah objek seluruhnya n_1 + n_2 + . . . + n_k = n), maka jumlah cara menyusun seluruh objek adalah : P(n;n_1,n_2, ... , n_k) = C(n;n_1,n_2, ... , n_k) = n!/(n_1 !n_(2!…n_k !) ) Contoh : 12 lembar karton akan diwarnai sehingga 3 diantaranya berwarna hijau, 2 berwarna merah, 2 berwarna kuning dan sisanya berwarna biru. Berapa jumlah cara pengecatan? Penyelesaian : Diketahui n_1 = 3, n_2 = 2, n_3 = 2, n_4 = 5 dan n_(1 )+ n_2 + n_3 + n_4 = 3 + 2 + 2 + 5 = 12 Jumlah cara pengecatan = P(12; 3, 2, 2, 5) = (P(12,12))/((3!)(2!)(2!)(5!)) = 12!/((3!)(2!)(2!)(5!)) = 166320 cara 12 buah lampu berwarna (4 merah, 3 putih dan 5 biru) dipasang pada 18 buah soket dalam sebuah baris (sisanya 6 buah soket dibiarkan kosong). Berapa jumlah cara pengaturan lampu? Penyelesaian : Diketahui, n = 18; n_1 = 4, n_2 = 3, n_3 = 5 dan n_(4 )= 6 (socket kosong) Jumlah cara pengaturan lampu = P(18; 4, 3, 5, 6) = 18!/((4!)(3!)(5!)(6!)) cara Berapa banyak cara membagikan delapan buah buku berbeda kepada 3 orang mahasiswa, bila Billy mendapat empat buah buku dan Andi serta Toni masing-masing memperoleh 2 buah buku. Penyelesaian : Diketahui n = 8, n_1 = 4, n_2 = 2, n_3 = 2 dan n_(1 )+ n_2 + n_3 = 4 + 2 + 2 = 8 Jadi, jumlah cara membagi seluruh buku = 8!/((4!)(2!)(2!)) = 420 cara KOMBINASI DENGAN PENGULANGAN Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak. Jika masing – masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkan bola ke dalam kotak adalah C(n, r). Jika masing -masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola ke dalam kotak adalah C(n + r – 1, r). C(n + r – 1, r) adalah jumlah kombinasi yang membolehkan adanya pengulangan elemen, yaitu dari n buah objek kita akan mengambil r buah objek, dengan pengulangan diperbolehkan. Pembuktian rumus kombinasi dengan pengulangan tidak disertakan di sini. Perhatikan bahwa C(n + r – 1, r) = C(n + r – 1, n – 1). Contoh : Toko roti ”Enak” menjual 8 jenis roti. Berapa jumlah cara mengambil 1 lusin roti (1 lusin = 12 buah) Penyelesaian : Analogikan 8 jenis roti sebagai 8 kotak. Kita akan mendistribusikan 12 roti itu ke dalam 8 kotak. Setiap kotak mungkin berisi lebih dari 1 buah roti. Di sini n = 8 dan r = 12, maka jumlah cara memilih 12 buah roti itu sama dengan jumlah cara memasukkan 12 buah roti ke dalam 8, yaitu sebanyak C(8 + 12 – 1, 12) = C(19, 12) cara. Andaikan terdapat kumpulan bola yang berwarna merah, biru dan hijau. Jumlah bola dari masing – masing warna paling sedikit jumlahnya 8 buah. Berapa banyak cara memilih 8 buah bola (tanda ada batasan warna)? Berapa banyak cara memilih 8 buahbola jika paling sedikit 1 bola dari masing – masing warna terwakili? Penyelesaian : n = 3, r = 8, maka C(n + r – 1, r) = C(3 + 8 – 1, 8) = C(10, 8) = 45 Ambil terlebih dulu 1 bola dari masing – masing warna, kemudian ambil 5 boal sisanya. Jumlah cara seluruhnya adalah C(3 + 5 – 1, 5) = C(7, 5) = 21 cara. Tiga buah dadu dilempar bersamaan. Berapa banyaknya hasil berbeda yang mungkin? Penyelesaian : C(6 + 3 – 1, 3) = C(8, 3) = 56.

Materi MatDis (Matematika Diskret) : Induksi Matematika

Metode pembuktian untuk proposisi perihal bilangan bulat adalah induksi matematika. Induksi matematika merupakan teknik pembuktian yang baku di dalam matematika. Melalui induksi matematika kita dapat mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas. Proposisi Perihal Bilangan Bulat Proposisi ini mengkaitkan suatu masalah yang dihubungkan dengan bilangan bulat. Contoh : Kita ingin menemukan rumus jumlah dari n buah bilangan ganjil positif yang pertama. Misalnya untuk n = 1, 2, 3, 4, 5, kita mengamati jumlah n bilangan ganjil positif pertama adalah n = 1 → 1 = 1 n = 2 → 1 + 3 = 4 n = 3 → 1 + 3 + 5 = 9 n = 4 → 1 + 3 + 5 + 7 = 16 n = 5 → 1 + 3 + 5 + 7 + 9 = 25 Setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Untuk semua n ≥ 1, n3 + 2n adalah kelipatan 3. Untuk membayar biaya pos sebesar n sen dolar (n ≥ 8) selalu dapat digunakan hanya perangko 3 sen dan 5 sen dolar. Di dalam sebuah pesta, setiap tamu berjabat tangan dengan tamu lainnya hanya sekali. Jika ada n orang tamu maka jumlah jabat tangan yang terjadi adalah n(n – 1)/2 . Banyaknya himpunan bagian yang dapat dibentuk dari sebuah himpunan yang beranggotakan n elemen adalah 2n. Proposisi – proposisi semacam di ataslah yang dapat dibuktikan dengan induksi matematika. Cara pembuktian dengan induksi matematika : Prinsip Induksi Sederhana Prinsip induksi sederhana berbunyi sebagai berikut : Misalkan p(n) adalah proposisi perihal bilangan bulat positif dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Untuk membuktikan proposisi ini, kita hanya perlu menunjukkan bahwa : p(1) benar, dan jika p(n) benar, maka p(n + 1) juga benar untuk setiap n ≥ 1. Sehingga p(n) benar untuk semua bilangan bulat positif n. Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah induksi. Langkah induksi berisi asumsi (andaian) yang menyatakan bahwa p(n) benar. Asumsi tersebut dinamakan hipotesis induksi. Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Basis induksi digunakan untuk memperlihatkan bahwa pernyataan tersebut benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil. Kemudian kita harus memperlihatkan bahwa implikasi p(n) → p(n + 1) benar untuk setiap bilangan bulat positif. Untuk membuktikan implikasi tersebut benar untuk setiap bilangan bulat positif n, kita perlu menunjukkan bahwa p(n + 1) tidak mungkin salah bila p(n) benar. Hal ini diselesaikan dengan cara memperlihatkan bahwa berdasarkan hipotesis p(n) benar maka p(n + 1) juga harus benar. Perhatikan bahwa dalam induksi matematika kita tidak mengasumsikan bahwa p(n) benar untuk semua bilangan bulat positif. Kita hanya memperlihatkan bahwa jika diasumsikan p(n) benar, maka p(n + 1) juga benar untuk setiap n positif. Pembuktian dengan induksi matematika mirip dapat kita ilustrasikan dengan fenomena yang dikenal dengan efek domino. Sejumlah batu domino diletakkan berdiri dengan jarak ruang yang sama satu sama lain. Untuk merebahkan semua batu domino, kita hanya perlu mendorong domino 1 ke kanan. Jika domino 1 di dorong ke kanan, ia akan mendorong domino 2, domino 2 mendorong domino 3, begitu seterusnya sehingga semua batu domino rebah ke kanan. Contoh : Tunjukkan bahwa untuk n ≥ 1, 1 + 2 + 3 + ... + n = n (n + 1) / 2 melalui induksi matematika. Penyelesaian : Andaikan bahwa p(n) menyatakan proposisi bahwa untuk n ≥ 1, jumlah n bilangan bulat positif pertama adalah n (n + 1) / 2, yaitu 1 + 2 + 3 + ... + n = n (n + 1) / 2. Kita harus membuktikan kebenaran proposisi ini dengan dua langkah induksi sebagai berikut : Basis induksi : p(1) benar, karena untuk n = 1 kita peroleh 1 = 1 (1 + 1) / 2 = 1 (2) / 2 = 2/2 = 1 Langkah induksi : Misalkan p(n) benar, yaitu mengasumsikan bahwa 1 + 2 + 3 + ... + n = n(n + 1)/2 Adalah benar (hipotesis induksi). Kita harus memperlihatkan bahwa p(n + 1) juga benar, yaitu 1 + 2 + 3 + ... + n + (n + 1) = (1 + 2 + 3 + ... + n) + (n + 1) = [n (n + 1)/2 ] + (n + 1) = [ (n2 + n)/2 ] + (n + 1) = [ (n2 + n )/2 ] + [ (2n + 2)/2 ] = (n2 + 3n + 2)/2 = (n + 1)(n + 2)/2 = (n + 1) [ (n + 1) + 1]/2 Karena langkah (a) dan (b) tealh dibuktikan benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ≥ 1, 1 + 2 + 3 + ... + n = n (n + 1)/2. Prinsip Induksi yang Dirampatkan Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ≥ n0 . Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa : p(n0) benar, dan jika p(n) benar maka p(n + 1) benar untuk setiap n ≥ n0, sehingga p(n) benar untuk semua bilangan bulat n ≥ n0. Contoh : Buktikan dengan induksi matematika bahwa 3n < n! Untuk n bilangan bulat positif yang lebih besar dari 6. Penyelesaian : Misalkan p(n) adalah proposisi bahwa 3n < n! Untuk n bilangan bulat positif yang lebih besar dari 6. Basis induksi : p(7) benar, karena 37 = 2187 dan 7! = 5040 Langkah induksi : Misalkan bahwa p(n) benar, yaitu asumsikan bahwa 3n < n! Adalah benar. Kita harus menunjukkan bahwa p(n + 1) juga benar, yaitu 3n+1 < (n + 1)!. Hal ini ditunjukkan sebagai berikut : 3n+1 < (n+1)! 3.3n < (n+1) . n! 3n . 3/(n+1) < n! Menurut hipotesis induksi, 3n < n!, sedangkan untuk n > 6, nilai 3?(n+1) < 1, sehingga 3/(n+1) akan memperkecil nilai di ruas kiri persamaan. Efek nettonya, 3n . 3/(n+1) < n! Jelas benar. Karena langkah (a) dan (b) sudah ditunjukkan benar, maka terbukti bahwa 3n < n! untuk n bilangan bulat positif lebih besar dari 6. Prinsip Induksi Kuat Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n ≥ n0. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa : p(n0) benar, dan jika p(n0), p(n0+1), ..., p(n) benar, maka p(n+1) juga benar untuk setiap bilangan bulat n ≥ n0, sehingga p(n) benar untuk semua bilangan bulat n ≥ n0. Versi induksi yang lebih kuat ini mirip dengan induksi sederhana, kecuali bahwa pada langkah 2 kita mengambil hipotesis induksi yang lebih kuat bahwa semua pernyataan p(1), p(2), ..., p(n) adalah benar daripada hipotesis yang menyatakan bahwa p(n) benar (pada induksi sederhana). Prinsip induksi kuat memungkinkan kita mencapai kesimpulan yang sama meskipun memberlakukan andaian yang lebih banyak. Contoh : Bilangan bulat positif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri. Kita ingin membuktikan bahwa setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih ) bilangan prima. Buktikan dengan prinsip induksi kuat. Penyelesaian : Misalkan p(n) adalah proposisi bahwa setiap bilangan bulat positif n (n ≥ 2 ) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Basis induksi : p(2) benar, karena 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri. Langkah induksi. Misalkan p(n) benar, yaitu asumsikan bahwa bilangan 2, 3, ..., n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima (hipotesis induksi). Kita perlu menunjukkan bahwa p(n + 1) benar, yaitu n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima. Hal ini ditunjukkan sebagai berikut : jika n + 1 sendiri bilangan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Jika n + 1 bukan bilangan prima, maka terdapat bilangan bulat positif a yang membagi habis n + 1 tanpa sisa. Dengan kata lain, (n + 1)/ a = b atau (n + 1) = ab yang dalam hal ini, 2 ≤ a ≤ b ≤ n. Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Ini berarti, n + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n + 1 = ab. Karena langkah (a) dan (b) sudah ditunjukkan benar, maka terbukti bahwa setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Bentuk Induksi Secara Umum Bentuk induksi secara umum dapat dituliskan sebagai berikut : Misalkan X terurut dengan baik oleh “<”, dan p(x) adalah pernyataan perihal elemen x dari X. Kita ingin membuktikan bahwa p(x) benar untuk semua x ∈ X. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa: p(x0) benar, yang dalam hal ini x0 adalah elemen terkecil di dalam X, dan jika p(y) benar untuk y < x, maka p(x) juga benar untuk setiap x > x0 di dalam X, sehingga p(x) benar untuk semua x ∈ X. TUGAS : Buktikan bahwa : 1. p(n) : 1 + 4 + 7 + ... + (3n – 2) = (n (3n-1))/2 2. p(n) : 1 + 2 + 22 + 23 + ... + 2n = 2n+1 – 1 3. p(n) : 1.2 + 2.3 + 3.4 + ... + n (n+1) = ([n(n+1)(n+2)])/3 Penyelesaian : 1. p(n) : 1 + 4 + 7 + ... + (3n – 2) = (n (3n-1))/2 p(n+1) : 1 + 4 + 7 + ... + (3n – 2) + (3(n+1)-2) = ((n+1)(3(n+1)-1))/2 (n (3n-1))/2 + (3n+3-2) = ((n+1)(3n+3-1))/2 (n (3n-1))/2 + (3n +1) = ((n+1)(3n+2))/2 (n (3n-1)+2(3n+1))/2 = ((n+1)(3n+2))/2 (3n^2-n+6n+2)/2 = ((n+1)(3n+2))/2 (3n^2+5n+2)/2 = ((n+1)(3n+2))/2 ((3n+2)(n+1))/2 = ((n+1)(3n+2))/2 TERBUKTI 2. p(n) : 1 + 2 + 22 + 23 + ... + 2n = 2n+1 – 1 p(n+1) : 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = (1 + 2 + 22 + 23 + ... + 2n ) + 2n+1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = ( 2n+1 – 1 ) + 2n+1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = ( 2n+1 + 2n+1 ) - 1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = ( 2 . 2n+1 ) - 1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = 2n+2 -1 1 + 2 + 22 + 23 + ... + 2n + 2n+1 = 2(n+1)+1 - 1 1 + 2 + 22 + 23 + ... + 2n = 2n+1 – 1 TERBUKTI 3. p(n) : 1.2 + 2.3 + 3.4 + ... + n (n+1) = ([n(n+1)(n+2)])/3 p(n+1) : 1.2 + 2.3 + 3.4 + ... + n (n+1) + (n+1)+(n+1+1) = ([(n+1)(n+2)(n+3)])/3 ([n(n+1)(n+2)])/3 + (n+1)(n+2) = ([(n+1)(n+2)(n+3)])/3 (n[(n+1)(n+2)]=3[(n+1)(n+2)])/3 = ([(n+1)(n+2)(n+3)])/3 ((n+1)(n+2)(n+3))/3 = ([(n+1)(n+2)(n+3)])/3 TERBUKTI

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