MATEMATIKA DISKRIT

RELASIMATEMATIKA DISKRITTUJUANMahasiswa dapat memahamiRelasi dan Sifat sifatnyaRelasi n - ary dan AplikasinyaRepresentasi RelasiKlosur dari RelasiRelasi EkivalensiUrutan Parsial2RELASI DAN SIFAT-SIFATNYA3MATEMATIKA DISKRIT3Relasi dan Sifat-sifatnyaUntuk himpunan A dan B, Cartesian product, atau cross product, dari A dan B dinotasikan dengan A X B adalah himpunanA X B = {(a, b) | a A, b B}43.1DEFINISI 1Setiap anggota dari A X B, misal (a, b), disebut pasangan terurut (ordered pair), dimana a disebut komponen pertama dan b disebut komponen kedua.Sebarang dua anggota dari A X B, misal (a, b) dan (c, d), disebut sama jika dan hanya jika a = c dan b = d.Jika A, B berhingga dengan |A| = m dan |B| = n, maka berdasar pada aturan perkalian berlaku| A X B | = | A | . | B | = mn.Meskipun A X B B X A tetapi berlaku | A X B | = | B X A |.Relasi dan Sifat-sifatnyaMisal n +, n 3, dan A1, , An adalah n himpunan, maka produk lipat-n dari A1, , An adalah A1 X X An = {(a1, , an)| ai Ai, 1 i n }.53.1DEFINISI 2Sebarang (a1, , an) A1 X X An disebut ordered n-tuple.Jika (a1, , an), (b1, , bn) A1 X X An maka (a1, , an) = (b1, , bn) jika dan hanya jika ai = bi untuk semua 1 i n.Misal A = {1, 2, 3} dan B = {a, b}. Maka A X B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}B x A = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)} B x B = B2 = {(a, a), (a, b), (b, a), (b, b)}A x A = A2 = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}CONTOH 1| A X B | = 6| B X A | = 6| A X A | = 4| B X B | = 9Relasi dan Sifat-sifatnyaMisal A = {1, 2}, B = {a, b} dan C = {x, y}. Maka A X B X C dapat dinyatakan dalam bentuk diagram pohon (tree diagram) seperti gambar berikut63.1CONTOH 212(1, a)(1, b)(2, a)(2, b)(1, a, x)(1, a, x)(1, b, x)(1, b, x)(2, a, x)(2, a, x)(2, b, x)(2, b, x)Relasi dan Sifat-sifatnyaMisal A dan B sebarang himpunan. Relasi biner (binary relation) dari A ke B adalah himpunan bagian dari A X B.Relasi pada A adalah relasi dari A ke A.73.1DEFINISI 3Notasi a b digunakan untuk menyatakan bahwa (a, b) , dan a b untuk menyatakan (a, b) R.Untuk himpunan berhingga A dan B dengan | A | = m dan | B | = n, terdapat 2mn relasi dari A ke B, termasuk himpunan kosong dan A X B. Untuk B = {1, 2}, maka A = (B) = {, {1}, {2}, {1, 2}}. Relasi pada A adalahA X A = {(, ), (, {1}), (, {2}), (, {1, 2}), ({1}, ), ({1}, {1}), ({1}, {2}), ({1}, {1, 2}), ({2}, ), ({2}, {1}), ({2}, {2}), ({2}, {1, 2}), ({1, 2}, ), ({1, 2}, {1}), ({1, 2}, {2}), ({1, 2}, {1, 2})}CONTOH 3Relasi dan Sifat-sifatnyaLanjutan..Berapa banyak himpunan bagian yang mungkin dari A X A ? 83.1CONTOH 3Pandang relasi pada himpunan bilangan bulat positif berikut ini1 = {(a, b) | a b}2 = {(a, b) | a > b}3 = {(a, b) | a = b atau a = b}4 = {(a, b) | a = b}5 = {(a, b) | a = b + 1}6 = {(a, b) | a + b 3}.Manakah diantara relasi relasi tersebut yang memuat pasangan pasangan berurutan berikut: (1, 1), (1, 2), (2, 1), (1, 1), dan (2, 2)?CONTOH 4Relasi dan Sifat-sifatnya93.1DEFINISI 4Relasi pada himpunan A disebut refleksif (reflexive) jika (a, a) untuk setiap a A.Relasi pada himpunan A refleksif jika a ((a, a) )Relasi dan Sifat-sifatnya103.1DEFINISI 5Relasi pada himpunan A disebut simetris (symmetric) jika (b, a) untuk semua a, b A.Relasi pada himpunan A antisimetris jika a b ((a, b) (b, a) (a = b))Relasi pada himpunan A simetris jika a b ((a, b) (b, a) )Relasi pada himpunan A sedemikian sehingga untuk semua a, b A, jika (a, b) dan (b, a) , maka a = b disebut antisimetris (antisymmetric).Relasi dan Sifat-sifatnya113.1DEFINISI 7Misal relasi dari himpunan A ke himpunan B dan relasi dari himpunan B ke himpunan C. Komposisi dari dan adalah relasi yang memuat pasangan berurutan (a, c) dimana a A dan c C dan terdapat sebuah elemen b B sedemikian sehingga (a, b) dan (b, c) .Komposisi dan dinotasikan dengan .Relasi dan Sifat-sifatnya123.1DEFINISI 8Misal relasi pada himpunan A. Perpangkatan n, n = 1, 2, 3, , didefinisikan secara rekursif oleh1 = dan n + 1 = n .Relasi dan Sifat-sifatnya133.1TEOREMA 1 relasi pada himpunan A transitif jika dan hanya jika n untuk n = 1, 2, 3, .RELASI n ARY DAN APLIKASINYA14Relasi n - ary dan Aplikasinya153.2DEFINISI 9Misal A1, A2, , An adalah himpunan. Relasi n ary pada himpunan himpunan tersebut adalah himpunan bagian dari A1 X A2 X An. Himpunan A1, A2, , An disebut domain, dan n disebut derajat (degree).REPRESENTASI RELASI16Representasi RelasiRelasi dari dua himpunan berhingga dapat direpresentasikan dengan menggunakan matriks nol satu. Misal relasi dari himpunan A = {a1, , am} ke himpunan B = {b1, , bn}. Relasi dapat ditulis dalam bentuk matriks M = [mij], dimana

173.3MATRIKSmij =1 jika (ai, bj) 0 jika (ai, bj) Misal A = {1, 2, 3} dan B = {1, 2}. Andai relasi dari A ke B yang memuat (a, b) jika a A, b B, dan a > b. Representasikan relasi dalam bentuk matriks nol satu.SolusiCONTOHM = 001110Representasi RelasiRelasi refleksif jika dan hanya jika mii = 1 untuk i = 1, 2, 3, , n.Relasi simetris jika dan hanya jika M = [M]t.183.3MATRIKSMisal relasi pada himpunan yang direpresentasikan oleh matriksCONTOHM = 111011011Apakah relasi yang refleksif, simetris, atau antisimetris?Solusi

Representasi RelasiMisal 1 dan 2 relasi pada himpunan A yang direpresentasikan oleh matriks 193.3MATRIKSM1 = 101010100M2 = 100101110Tentukan matriks yang merepresentasikan 1 2 dan 1 2!

SolusiMatriks relasi dari 1 2 adalahM1 2 = M1 M2 = 10111111019Representasi Relasi203.3MATRIKSMatriks relasi dari 1 2 adalahM1 2 = M1 M2 = 100000100Representasi RelasiTentukan hasil kali Boolean dari matiks A dan B, dimana213.3DEFINISI 10Misal A = [aij] adalah matriks nol satu yang berukuran m x k dan B = [bij] adalah matriks nol satu yang berukuran k x n. Maka hasil kali Boolean dari matiks A dan B, dinotasikan dengan A B, adalah matriks m x n dengan entri ke ij adalah cij dimanacij = (ai1 b1j) (ai2 b2j) (aik bkj).CONTOHA = 100101B = 110111Representasi RelasiSisi dengan bentuk (a, a) digunakan untuk menunjukkan titik a yang kembali ke dirinya sendiri dan disebut loop.223.3DEFINISI 10Graf berarah (directed graph), atau digraph, memuat himpunan titik V, atau biasa disebut vertices, bersama dengan himpunan E yang merupakan pasangan berurutan dari elemen elemen V yang disebut dengan sisi (edges/arcs).Verteks a dari sisi (a, b) disebut initial vertex dan verteks b disebut terminal vertex dari sisi.abcdRepresentasi RelasiIlustrasikan digraph denganV = {a, b, c, d}E = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}.233.3CONTOH 5KLOSUR DARI RELASI24Klosur dari RelasiRelasi = {(1, 1), (1, 2), (2, 1), (3, 2)} pada himpunan A = {1, 2, 3} adalah relasi yang tidak refleksif. Bagaimana membentuk sebuah relasi sesedikit mungkin yang refleksif dan mengandung ? Dengan menambahkan (2, 2) dan (3, 3) ke dalam (karena dua relasi tersebut yang belum ada dalam ) maka akan terbentuk relasi baru yang refleksif dan memuat .Relasi disebut klosur refleksif (reflexive closure) dari .253.4CONTOH DEFINISI 11 Klosur refleksif dari adalah dimana = {(a, a)|a A} = {(a, b)|a b} pada himpunan bilangan bulat. Maka klosur refleksif dari adalah : = {(a, b)|a b} {(a, a)|a } = {(a, b)|a }CONTOH DEFINISI 12 Klosur simetris dari adalah 1 dimana 1 = {(b, a)|(a, b) }RELASI EKIVALENSI26Relasi Ekivalensi273.5DEFINISI Relasi pada himpunan A disebut relasi ekivalensi jika bersifat refleksif, simetris, dan transitif.DEFINISI Dua buah elemen a dan b yang terhubung dengan relasi ekivalensi disebut ekivalen.Dua buah elemen yang ekivalen dinotasikan dengan a b.Relasi EkivalensiJika b [a] maka b disebut representatif (representative) dari kelas ekivalensi283.5DEFINISI Misal relasi ekivalensi pada himpunan A. Himpunan semua elemen yang berhubungan dengan a dari A disebut kelas ekivalensi (equivalence class) dari a.Kelas ekivalensi dari a terhadap dinotasikan dengan [a]. Dengan demikian[a] = {s | (a, s) }

URUTAN PARSIAL29Urutan Parsial303.6DEFINISI Relasi pada S disebut terurut sebagian (partial ordering) jika bersifat refleksif, antisimetris, dan transitif. Himpunan S bersamaan dengan relasi terurut sebagian disebut himpunan terurut sebagian (partially ordered set POSET), dinotasikan dengan (S, ). Anggota dari S disebut elemen dari poset.Notasi a b digunakan untuk menunjukkan bahwa (a, b) pada sebarang poset (S, ). DEFINISI Dua buah elemen a dan b dari poset (S, ) disebut dapat dibandingkan (comparable) jika memenuhi a b atau b a.Dua buah elemen a dan b dari poset (S, ) disebut tidak dapat dibandingkan (incomparable) jika a b atau b a.

Urutan Parsial313.6DEFINISI Jika (S, ) adalah poset dan setiap dua elemen dari S komparabel, maka S disebut himpunan terurut total (totally ordered set) atau himpunan terurut linier (linearly ordered set), dan disebut urutan total atau urutan linier.Himpunan terurut total disebut juga rantai (chain).Urutan Parsial323.6DEFINISI (S, ) dikatakan himpunan terurut dengan baik (well ordered set) jika (S, ) adalah poset sedemikian sehingga merupakan urutan total dan setiap himpunan bagian dari S mempunyai elemen terkecil (least element)Urutan ParsialDiberikan sebarang relasi partial order yang terdefinisi pada sebuah himpunan berhingga, maka bisa digambar graf berarah (directed graph) sehingga semua sifat terpenuhi.Hal ini menunjukkan terdapat hubungan antara graf sederhana, disebut diagram Hasse, dengan relasi partial order yang didefinisikan pada himpunan berhingga.

Cara merepresentasikan poset berhingga dengan menggunakan diagram Hasse:Langkah 1.Gambar graf berarah dari posetLangkah 2.Eleminasia. semua loop pada vertexb. semua panah yang keberadaannya diimplikasikan oleh sifat transitifc. semua indikator arah pada panah.333.6DIAGRAM HASSE Urutan ParsialGambarlah diagram Hasse untuk urutan parsial {(A, B) | A B} pada himpunan kuasa (S) dimana S = {a, b, c}.

Solusi.Himpunan kuasa (S) = 343.6CONTOH{, {a},{b},{c},{a, b},{a, c},{b, c},{a, b, c}}{b}{a, c}{c}{a}{a, b, c}{b, c}{a, b}Gambar graf berarah dari posetEleminasi semua loop pada vertexEleminasi semua panah yang keberadaannya diimplikasikan oleh sifat transitifEleminasi semua indikator arah pada panahEleminasi semua panah yang keberadaannya diimplikasikan oleh sifat transitifDAFTAR PUSTAKAGrimaldi, Ralph P. 2004. Discrete and Combinatorial Mathematics. Fifth Edition. Pearson Education, Inc. USARosen, H. Kenneth. 2012. Discrete Mathematics and Its Application. Seventh Edition. McGraw Hill. New York35