Matematika Diskrit : Relasi dan Fungsi

Bagian Satu Relasi Pada pertemuan mengenai himpunan telah dijelaskan himpunan pasangan terurut diperoleh dari perkalian kaertesian antara dua himpunan. A x B = {(a, b)| a �� A dan b} Definisi. Relasi biner R antara A dan B adalah himpunan bagian dari A x B. notasi: R ⊆ (A x B) 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}, dan B = { IF221, IF251, IF342,IF323}. Perkalian kartesian A dan B (AxB) menghasilkan 12 pasangan terurut, yaitu A x B = {(Amir, IF221), (Amir, IF251), (Amir,IF342), … , (cecep, IF323)} Misalkan R adalah relasi yang menyatakan mata kuliah yang diambil oleh mahasiswa pada semester ganjil, yaitu R = {(Amir, IF251), (Amir, IF323), (Budi, IF221), (Cecep, IF342), (Cecep, IF323)} Contoh Misalkan P = { 2, 3, 4} dan Q = {2, 4, 8, 9, 15}. Relasi R dari P ke Q dengan (p, q) �� R jika phabis membagi q Maka diperoleh R = {(2, 2), (2, 4) , (2, 8), (4, 4), (4,8), (3,9), (3,15)}.  Relasi dapat direpresentasi dengan diagram Venn dan Tabel Diagram Venn Amir Budi Cecep IF221 IF251 IF342 IF323 2 3 4 2 4 8 9 15 Tabel A B A B Amir Amir Budi Cecep Cecep IF251 IF323 IF221 IF342 IF323 2 2 2 3 3 2 4 8 9 15 4 4 4 8  Sifat-sifat Relasi 1. Refleksif Definisi, relasi R pada himpunan A disebut refleksif jika (a , a) ∈ R untuk setiap a ∈ A. Contoh: Misalkan A = {1,2,3} dan dengan R = {(1,1), (1,3), (2,1), (2,2), (3,2)} 2. Setangkup Definisi, relasi R pada himpunan A disebut setangkup jika (a, b) ∈ R, maka (b, a) ∈ R, untuk semua a,b ∈ R Contoh Misalkan A = {1,2,3} dan dengan R = {(1,1), (1,2), (2,1), (2,2), (3,2)}  Relasi n-ary Definisi, misalkan A1 , A2, … , An adalah himpunan. Relasi n-ary R pada himpunan-himpunan tersebut adalah himpunan bagian dari A1 x A2x … x An. Contoh Misalkan NIM = {132450, 132452, 132457} Nama = {Dono, Dina, Dita} MatKul = {Matematika, Algoritma, Struktur Data } Nilai = {A, B} Salah satu contoh relasi yang bernama MHS adalah NIM Nama MatKul Nilai 132450 132450 132452 132452 132457 Dono Dono Dina Dina Dita Matematika Struktur Data Algoitma Matematika Algoritma A B B A A Basisdata (database) adalah kumpulan tabel. Salah satu model basisdata adalah model basisdata relasional yang didasari oleh konsep relasi n-ary. Dimana, setiap kolom disebut atribut. Setiap tabel diimplementasikan sebagai sebuah file. Satu baris menyatakan sebuah record, dan setiap atribut menyatakan sebuah field. Operasi yang dilakukan terhadap sebuah basis data dilakukan dengan perintah pertanyaan yang disebut query, contohnya: “tampilkan semua mahasiswa yang mengambil mata kuliah matematika” “tampilkan daftar nilai mahasiswa dengan NIM = 132450” Beberapa operasi yang digunakan dalam query,diantaranya: a. Seleksi Yaitu, memilih baris tertentu dari sebuah tabel. Operator ��. Contoh. Kita ingin menampilkan daftar mahasiswa yang mengambil matakuliah Matematika. Jawab. Operasi seleksi �������������� = “Matematika”(MHS) Menghasilkan (132450, Dono, Matematika) dan (132452, Dina, Matematika) b. Proyeksi Yaitu, memilih kolom tertentu dari sebuah tabel. Operator ��. Contoh Operasi proyeksi ����������,������������ (MHS) Menghasilkan Nama MatKul Dono Dono Dina Dina Dita Matematika Struktur Data Algoitma Matematika Algoritma c. Join Yaitu, menggabungkan dua tabel menjadi satu. Operator ��. Contoh Tabel 1 tabel 2 NIM Nama MatKul NIM Nama JK 132450 132450 132452 132452 132457 Dono Dono Dina Dina Dita Matematika Struktur Data Algoitma Matematika Algoritma 132450 132452 132457 Dono Dina Dita L P P Operasi join ��NIM, Nama(MHS1, MHS2) Menghasilkan NIM Nama MatKul JK 132450 132450 132452 132452 132457 Dono Dono Dina Dina Dita Matematika Struktur Data Algoitma Matematika Algoritma L L P P P Bagian Dua Fungsi Pertama Pengertian Fungsi Misalkan A dan B adalah 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. Definisi lengkap fungsi menjadi: set pasangan urut dengan anggota-anggota set X yang dinamakan wilayah, sebagai unsur pertama, dan anggota-anggota set Y, yang dinamakan jangkauan sebagai unsur kedua, yang dihubungkan dengan suatu kaidah yang demikian sehingga tidak ada pasangan urut yang unsur pertamanya sama. Fungsi dapat dispesifikasikan dalam berbagai bentuk, diantaranya: 1. Himpunan pasangan terurut Ingat bahwa fungsi adalah relasi, relasi biasanya dinyatakan sebagai himpunan pasangan terurut. 2. Kata-kata Fungsi dapat dinyatakan secara eksplisit dalam rangkaian kata-kata. Misalnya “f adalah fungsi yang memetakan jumlah bit 1 di dalam suatu string biner”. 3. Kode program (source code) Fungsi dispesifikasikan dalam bentuk kode program komputer. Misalnya dalam Bahasa Pascal, fungsi yang mengembalikan nilai mutlak dari sebuah bilangan bulat x, yaitu |x|, ditulis sbb: Function abs (x : integer) : integer; Begin If x < 0 then Abs := -x Else Abs := x ; End; 4. Formula pengisian nilai (assignment) Seperti y = x2 – 4 yang dapat dituliskan juga f(x) = x2 – 4. Contoh Misalkan f adalah fungsi dari x = {-2, 0, 1} yang didefinisikan oleh y = 2x2 + 3. Tentukan nilai fungsi tersebut Penyelesaian y = 2x2 + 3 artinya f(x) = 2x2 + 3 Untuk x = -2 maka f(-2) = 2(-2)2 + 3 = 11 x = 0 maka f(0) = 2(0)2 + 3 = 3 x = 1 maka f(1) = 2(1)2 + 3 = 5 Bergantung pada bayangan, fungsi dibedakan menjadi: 1. Fungsi satu-ke-satu (one-to-one) atau injektif ; jika tidak ada dua elemen himpunan A yang memiliki bayangan sama. 2. Fungsi pada (onto) atau surjektif ; jika setiap elemen himpunan B merupakan bayangan dari satu atau lebih elemen himpunan A. 3. Fungsi berkoresponden satu-ke-satu atau bijeksi ; jika ia merupakan fungsi satu-ke-satu dan juga fungsi pada. Kedua Fungsi Invers Jika f adalah fungsi berkoresponden satu-ke-satu dari A ke B,maka kita dapat menemukan balikan atau invers dari f . Fungsi invers dari f dilambangkan dengan f –1. Contoh Tentukan invers dari fungsi-fungsi berikut. a. f(x) = 2x – 1 penyelesaian f(x) = 2x – 1 y = 2x – 1 y + 1 = 2x �� + 12 = x f –1(x) = �� + 12 b. f(x) = x2 + 1 penyelesaian f(x) = x2 + 1 y = x2 + 1 y – 1 = x2 ��−1 = x f –1(x) = ��−1 Ketiga Komposisi Fungsi Karena fungsi merupakan bentuk khusus dari relasi, kita dapat melakukan komposisi dari dua buah fungsi. misalkan g adalah fungsi dari A ke B, dan f adalah fungsi dari B ke C. Komposisi f dan g, dinotasikan dengan f o g, adalah fungsi dari A ke C yang di definisikan oleh. �� �� �� (a) = f(g(a)) Diberikan fungsi f(x) = 2x – 1 dan g(x) = x2 + 1 . Tentukan �� �� �� dan �� �� ��. Penyelesaian (i) (�� �� ��)(x) = f(g(x)) = f(x2 + 1) = 2(x2 + 1) – 1 = 2x2 + 2 – 1 = 2x2 + 1 (i) (�� �� ��)(x) = g(f(x)) = g(2x – 1) = (2x – 1)2 + 1 = (4x2 – 4x + 1) + 1 = 4x2 – 4x + 2