Matematika Diskrit - Hubungan
Setiap kali himpunan sedang dibahas, hubungan antara unsur himpunan adalah hal berikutnya yang muncul. Relations mungkin ada di antara objek dari set yang sama atau di antara objek dari dua atau lebih set.
Definisi dan Properti
Relasi biner R dari himpunan x ke y (ditulis sebagai $ xRy $ atau $ R (x, y) $) adalah himpunan bagian dari produk Cartesian $ x \ times y $. Jika pasangan terurut G dibalik, relasinya juga berubah.
Umumnya relasi n-ary R antara set $ A_1, \ dots, \ dan \ A_n $ adalah himpunan bagian dari produk n-ary $ A_1 \ times \ dots \ times A_n $. Kardinalitas minimum dari relasi R adalah Nol dan maksimumnya adalah $ n ^ 2 $ dalam kasus ini.
Relasi biner R pada satu himpunan A adalah himpunan bagian dari $ A \ dikali A $.
Untuk dua himpunan yang berbeda, A dan B, yang masing-masing memiliki kardinalitas m dan n , kardinalitas maksimum suatu relasi R dari A ke B adalah mn .
Domain dan Jangkauan
Jika ada dua himpunan A dan B, dan relasi R memiliki pasangan orde (x, y), maka -
Itu domaindari R, Dom (R), adalah himpunan $ \ lbrace x \: | \: (x, y) \ in R \: for \: some \: y \: in \: B \ rbrace $
Itu range dari R, Ran (R), adalah himpunan $ \ lbrace y \: | \: (x, y) \ in R \: for \: some \: x \: in \: A \ rbrace $
Contoh
Misalkan, $ A = \ lbrace 1, 2, 9 \ rbrace $ dan $ B = \ lbrace 1, 3, 7 \ rbrace $
Kasus 1 - Jika relasi R 'sama dengan' maka $ R = \ lbrace (1, 1), (3, 3) \ rbrace $
Dom (R) = $ \ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace $
Kasus 2 - Jika relasi R 'kurang dari' maka $ R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace $
Dom (R) = $ \ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace $
Kasus 3 - Jika relasi R 'lebih besar dari' maka $ R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace $
Dom (R) = $ \ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace $
Representasi Relasi menggunakan Graph
Suatu relasi dapat direpresentasikan menggunakan grafik berarah.
Jumlah simpul dalam grafik sama dengan jumlah elemen dalam himpunan yang relasinya telah ditentukan. Untuk setiap pasangan terurut (x, y) dalam relasi R, akan ada tepi berarah dari simpul 'x' ke simpul 'y'. Jika ada pasangan berurutan (x, x), maka akan terjadi self loop pada simpul 'x'.
Misalkan, ada relasi $ R = \ lbrace (1, 1), (1,2), (3, 2) \ rbrace $ pada set $ S = \ lbrace 1, 2, 3 \ rbrace $, bisa jadi diwakili oleh grafik berikut -
Jenis Relasi
Itu Empty Relation antara set X dan Y, atau di E, adalah set kosong $ \ emptyset $
Itu Full Relation antara himpunan X dan Y adalah himpunan $ X \ dikali Y $
Itu Identity Relationpada himpunan X adalah himpunan $ \ lbrace (x, x) | x \ dalam X \ rbrace $
Hubungan Invers R 'dari suatu relasi R didefinisikan sebagai - $ R' = \ lbrace (b, a) | (a, b) \ dalam R \ rbrace $
Example - Jika $ R = \ lbrace (1, 2), (2, 3) \ rbrace $ maka $ R '$ akan menjadi $ \ lbrace (2, 1), (3, 2) \ rbrace $
Relasi R pada himpunan A dipanggil Reflexive jika $ \ forall a \ in A $ terkait dengan a (aRa holding)
Example - Relasi $ R = \ lbrace (a, a), (b, b) \ rbrace $ pada set $ X = \ lbrace a, b \ rbrace $ bersifat refleksif.
Relasi R pada himpunan A dipanggil Irreflexive jika tidak ada $ a \ di A $ terkait dengan a (aRa tidak berlaku).
Example - Relasi $ R = \ lbrace (a, b), (b, a) \ rbrace $ pada set $ X = \ lbrace a, b \ rbrace $ tidak refleksif.
Relasi R pada himpunan A dipanggil Symmetric jika $ xRy $ berarti $ yRx $, $ \ untuk semua x \ dalam A $ dan $ \ untuk semua y \ dalam A $.
Example - Relasi $ R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace $ pada set $ A = \ lbrace 1, 2, 3 \ rbrace $ adalah simetris.
Relasi R pada himpunan A dipanggil Anti-Symmetric jika $ xRy $ dan $ yRx $ berarti $ x = y \: \ untuk semua x \ dalam A $ dan $ \ untuk semua y \ dalam A $.
Example - Relasi $ R = \ lbrace (x, y) \ to N | \: x \ leq y \ rbrace $ anti-simetris karena $ x \ leq y $ dan $ y \ leq x $ berarti $ x = y $ .
Relasi R pada himpunan A dipanggil Transitive jika $ xRy $ dan $ yRz $ berarti $ xRz, \ untuk semua x, y, z \ dalam A $.
Example - Relasi $ R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace $ pada set $ A = \ lbrace 1, 2, 3 \ rbrace $ bersifat transitif.
Relasi adalah Equivalence Relation jika refleksif, simetris, dan transitif.
Example - Relasi $ R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \ rbrace $ pada himpunan $ A = \ lbrace 1, 2, 3 \ rbrace $ adalah relasi ekivalen karena bersifat refleksif, simetris, dan transitif.