Banyak hal yang dibicarakan berkaitan dengan relasi. Dalam kehidupan sehari-hari kita mengenal istilah relasi bisnis, relasi pertemanan, relasi antara dosen-mahasiswa yang disebut perwalian atau juga perkuliahan, produsen-distributor, distributor-konsumen, dll. Ada banyak relasi yang mungkin terbentuk antar dua himpunan yang sama, contoh: antara mahasiswa dan matakuliah, dapat dibentuk relasi pengambilan matakuliah, bisa juga dibentuk relasi nilai matakuliah, serta dapat juga dibentuk relasi biaya matakuliah. Relasi juga bisa berarti keterhubungan atau keterkaitan antar dua objek atau lebih. Dalam bab ini akan dibicarakan definisi relasi beserta sifat-sifatnya, cara penyajian relasi, yang menjadi titik penting dari bab ini adalah relasi ekivalen dan kelas ekivalen yang akan membentuk partisi, dan relasi terurut parsial dan diagram Hasse.
Relasi dan Sifatnya
1. Pengertian Relasi
Definisi 1 (Hasil Kali Kartesian)
Hasil kali kartesian antara himpunan A dan himpunan B, ditulis AxB adalah semua pasangan terurut (a, b) untuk a ∈ A dan b ∈ B.
Contoh 1
Jika A = {1, 2, 3} dan B = {a, b}, maka AxB = {(1, a), (2, a), (3, a), (1, b), (2, b), (3, b)}
Banyaknya himpunan yang terlibat dalam operasi ini mempengaruhi nama operasinya, jika operasi tersebut hanya melibatkan dua himpunan, disebut operasi biner.
Definisi 1 (Hasil Kali Kartesian)
Hasil kali kartesian antara himpunan A dan himpunan B, ditulis AxB adalah semua pasangan terurut (a, b) untuk a ∈ A dan b ∈ B.
Contoh 1
Jika A = {1, 2, 3} dan B = {a, b}, maka AxB = {(1, a), (2, a), (3, a), (1, b), (2, b), (3, b)}
Banyaknya himpunan yang terlibat dalam operasi ini mempengaruhi nama operasinya, jika operasi tersebut hanya melibatkan dua himpunan, disebut operasi biner.
Definisi 2 (Relasi)
Relasi, dilambangkan dengan huruf besar R, adalah Subset dari hasil kali Cartesian (Cartesian product). Jika (x, y) ∈ R, maka x berelasi dengan y. {x ∈ A| (x, y) ∈ R untuk suatu y ∈ B} disebut domain dari R. Sedangkan Range dari R= {y ∈ B| (x, y) ∈ R untuk suatu x ∈ A}.
Relasi, dilambangkan dengan huruf besar R, adalah Subset dari hasil kali Cartesian (Cartesian product). Jika (x, y) ∈ R, maka x berelasi dengan y. {x ∈ A| (x, y) ∈ R untuk suatu y ∈ B} disebut domain dari R. Sedangkan Range dari R= {y ∈ B| (x, y) ∈ R untuk suatu x ∈ A}.
Contoh 2
Pada contoh 1, kita dapat membuat relasi:
R1 = {(1, a), (1, b)}
R2 = {(1, a), (2, a), (3, a)}
R3 = {(1, b), (2, b), (1, a}
R4 = {(1, a), (2, a), (3, a), (1, b), (2, b), (3, b)}
R5 = ∅
R6={(a, 1), (2, a)}
Himpunan pasangan terurut R1, R2, R3, R4, R5, merupakan subset dari AxB, dan membentuk suatu relasi, tetapi R6 bukan relasi dari AxB, karena (a, 1)∉AxB.
Sebuah pasangan terurut menjadi anggota relasi R1, ditulis: (1, a) ∈ R1 atau 1 R1 a. Dan jika (2, a) bukan anggota relasi R1, ditulis:
(2,a)∉ R1 atau 2 R1 a.
Pada contoh 1, kita dapat membuat relasi:
R1 = {(1, a), (1, b)}
R2 = {(1, a), (2, a), (3, a)}
R3 = {(1, b), (2, b), (1, a}
R4 = {(1, a), (2, a), (3, a), (1, b), (2, b), (3, b)}
R5 = ∅
R6={(a, 1), (2, a)}
Himpunan pasangan terurut R1, R2, R3, R4, R5, merupakan subset dari AxB, dan membentuk suatu relasi, tetapi R6 bukan relasi dari AxB, karena (a, 1)∉AxB.
Sebuah pasangan terurut menjadi anggota relasi R1, ditulis: (1, a) ∈ R1 atau 1 R1 a. Dan jika (2, a) bukan anggota relasi R1, ditulis:
(2,a)∉ R1 atau 2 R1 a.
Definisi 3 (Relasi biner atas satu himpunan A)
Relasi biner atas himpunan A adalah relasi biner dari A ke A. Relasi yang demikian ini, seringkali muncul dalam kehidupan seharihari, di dalam kalkulus I, kita kenal relasi dari R ke R, dari bilangan riil ke bilangan riil.
Contoh 3
Masing-masing relasi berikut adalah relasi biner atas bilangan bulat (Z):
R1 = {(a, b)| a ≥ b, dan a, b ∈Z}
R2 = {(a, b)| a < b, dan a, b ∈ Z}
R3 = {(a, b)| a=b atau a=-b, dan a, b ∈Z}
R4 = {(a, b)| a=b, dan a, b ∈ Z}
R5 = {(a, b)| a = b+1, dan a, b ∈Z}
R6 = {(a, b)| a + b ≤ 3, dan a, b ∈ Z}
R7 = {(a, b)| a|b, dan a, b ∈ Z, dan b≠0}
Relasi biner atas himpunan A adalah relasi biner dari A ke A. Relasi yang demikian ini, seringkali muncul dalam kehidupan seharihari, di dalam kalkulus I, kita kenal relasi dari R ke R, dari bilangan riil ke bilangan riil.
Contoh 3
Masing-masing relasi berikut adalah relasi biner atas bilangan bulat (Z):
R1 = {(a, b)| a ≥ b, dan a, b ∈Z}
R2 = {(a, b)| a < b, dan a, b ∈ Z}
R3 = {(a, b)| a=b atau a=-b, dan a, b ∈Z}
R4 = {(a, b)| a=b, dan a, b ∈ Z}
R5 = {(a, b)| a = b+1, dan a, b ∈Z}
R6 = {(a, b)| a + b ≤ 3, dan a, b ∈ Z}
R7 = {(a, b)| a|b, dan a, b ∈ Z, dan b≠0}
contoh 4
D={a, b, c}
℘(D)={∅, {a}, {b}, {c}, {a, b}, {a, c}, {b,c}, {a, b, c}}
℘(D)={∅, {a}, {b}, {c}, {a, b}, {a, c}, {b,c}, {a, b, c}}
2. Operasi Relasi
Karena relasi merupakan himpunan, maka operasi pada himpunan juga berlaku dalam relasi:
1. Operasi ∩ (intersection)
2. Operasi ∪ (union)
3. Operasi ⊕ (symmetric difference)
4. Operasi – (difference)
5. Operasi komplemen (komplemen relative terhadap Cartesian product)
Karena relasi merupakan himpunan, maka operasi pada himpunan juga berlaku dalam relasi:
1. Operasi ∩ (intersection)
2. Operasi ∪ (union)
3. Operasi ⊕ (symmetric difference)
4. Operasi – (difference)
5. Operasi komplemen (komplemen relative terhadap Cartesian product)
Contoh 5
Jika A = {1, 2, 5, 6}, R1 = {(1, 1), (2, 2), (5, 5), (6, 6), (2, 5)} dan R2 = {(1, 1), (2, 2), (2, 5), (1, 2), (1, 6), (5, 6)}, maka:
R1 ∩ R2 = {(1, 1), (2, 2), (2, 5)}
R1 ∪ R2 = {(1, 1), (2, 2), (5, 5), (6, 6), (2, 5), (1, 2), (1, 6), (5,6)}
R1 ⊕ R2 = {(5, 5), (6, 6), (1, 2), (1, 6), (5, 6)}
R1 – R2 = {(5, 5), (6, 6)}
(R1 ∪ R2)C = AxA – (R1 ∪ R2) = {(1, 5), (2, 1), (2, 6), (5, 1), (5, 2), (6, 1), (6, 2), (6, 5)}
Jika A = {1, 2, 5, 6}, R1 = {(1, 1), (2, 2), (5, 5), (6, 6), (2, 5)} dan R2 = {(1, 1), (2, 2), (2, 5), (1, 2), (1, 6), (5, 6)}, maka:
R1 ∩ R2 = {(1, 1), (2, 2), (2, 5)}
R1 ∪ R2 = {(1, 1), (2, 2), (5, 5), (6, 6), (2, 5), (1, 2), (1, 6), (5,6)}
R1 ⊕ R2 = {(5, 5), (6, 6), (1, 2), (1, 6), (5, 6)}
R1 – R2 = {(5, 5), (6, 6)}
(R1 ∪ R2)C = AxA – (R1 ∪ R2) = {(1, 5), (2, 1), (2, 6), (5, 1), (5, 2), (6, 1), (6, 2), (6, 5)}
Operasi komposisi, merupakan gabungan dari dua buah relasi yang harus memenuhi syarat tertentu, yaitu jika R1 relasi dari A ke A dan R2 relasi dari A ke A, maka relasi komposisi R1 dan R2, dinyatakan oleh R2°R1 berarti relasi R1 diteruskan oleh relasi R2. Syarat tersebut adalah jika (a, b) ∈ R1 dan (b, c) ∈ R2, maka (a, c) ∈ R2°R1.
Contoh 6
Dengan menggunakan contoh 5, didapat:
R2°R1 = {(1, 1), (1, 2), (1, 6), (2, 2), (2, 5), (5, 6), (2, 6)}
Yang diperoleh dengan cara:
Jika A = {1, 2, 5, 6}, R1 = {(1, 1), (2, 2), (5, 5), (6, 6), (2, 5)} dan R2 = {(1, 1), (2, 2), (2, 5), (1, 2), (1, 6), (5, 6)}, maka:
R1 R2 R2°R1 R1 R2 R2°R1
(1, 1) (1, 1) (1, 1) (2, 2) (1, 1) -
(1, 1) (2, 2) - (2, 2) (2, 2) (2, 2)
(1, 1) (2, 5) - (2, 2) (2, 5) (2, 5)
(1, 1) (1, 2) (1, 2) (2, 2) (1, 2) -
(1, 1) (1, 6) (1, 6) (2, 2) (1, 6) -
(1, 1) (5, 6) - (2, 2) (5, 6) -
Dengan menggunakan contoh 5, didapat:
R2°R1 = {(1, 1), (1, 2), (1, 6), (2, 2), (2, 5), (5, 6), (2, 6)}
Yang diperoleh dengan cara:
Jika A = {1, 2, 5, 6}, R1 = {(1, 1), (2, 2), (5, 5), (6, 6), (2, 5)} dan R2 = {(1, 1), (2, 2), (2, 5), (1, 2), (1, 6), (5, 6)}, maka:
R1 R2 R2°R1 R1 R2 R2°R1
(1, 1) (1, 1) (1, 1) (2, 2) (1, 1) -
(1, 1) (2, 2) - (2, 2) (2, 2) (2, 2)
(1, 1) (2, 5) - (2, 2) (2, 5) (2, 5)
(1, 1) (1, 2) (1, 2) (2, 2) (1, 2) -
(1, 1) (1, 6) (1, 6) (2, 2) (1, 6) -
(1, 1) (5, 6) - (2, 2) (5, 6) -
R1 R2 R2°R1 R1 R2 R2°R1
(5, 5) (1, 1) - (6, 6) (1, 1) -
(5, 5) (2, 2) - (6, 6) (2, 2) -
(5, 5) (2, 5) - (6, 6) (2, 5) -
(5, 5) (1, 2) - (6, 6) (1, 2) -
(5, 5) (1, 6) - (6, 6) (1, 6) -
(5, 5) (5, 6) (5, 6) (6, 6) (5, 6) -
(5, 5) (1, 1) - (6, 6) (1, 1) -
(5, 5) (2, 2) - (6, 6) (2, 2) -
(5, 5) (2, 5) - (6, 6) (2, 5) -
(5, 5) (1, 2) - (6, 6) (1, 2) -
(5, 5) (1, 6) - (6, 6) (1, 6) -
(5, 5) (5, 6) (5, 6) (6, 6) (5, 6) -
R1 R2 R2°R1
(2, 5) (1, 1) -
(2, 5) (2, 2) -
(2, 5) (2, 5) -
(2, 5) (1, 2) -
(2, 5) (1, 6) -
(2, 5) (5, 6) (2, 6)
(2, 5) (1, 1) -
(2, 5) (2, 2) -
(2, 5) (2, 5) -
(2, 5) (1, 2) -
(2, 5) (1, 6) -
(2, 5) (5, 6) (2, 6)
Sedangkan R1°R2 = {(1,1), (2, 2), (2, 5), (1, 2), (1, 5), (1,6), (5,6)}
Yang didapat dari rincian berikut:
R2 R1 R1°R2 R2 R1 R1°R2
(1, 1) (1, 1) (1, 1) (2, 2) (1, 1) -
(1, 1) (2, 2) - (2, 2) (2, 2) (2, 2)
(1, 1) (5, 5) - (2, 2) (5, 5) -
(1, 1) (6, 6) - (2, 2) (6, 6) -
(1, 1) (2, 5) - (2, 2) (2, 5) (2, 5)
R2 R1 R1°R2 R2 R1 R1°R2
(1, 1) (1, 1) (1, 1) (2, 2) (1, 1) -
(1, 1) (2, 2) - (2, 2) (2, 2) (2, 2)
(1, 1) (5, 5) - (2, 2) (5, 5) -
(1, 1) (6, 6) - (2, 2) (6, 6) -
(1, 1) (2, 5) - (2, 2) (2, 5) (2, 5)
R2 R1 R1°R2 R2 R1 R1°R2
(2, 5) (1, 1) - (1, 2) (1, 1) -
(2, 5) (2, 2) - (1, 2) (2, 2) (1, 2)
(2, 5) (5, 5) (2, 5) (1, 2) (5, 5) -
(2, 5) (6, 6) - (1, 2) (6, 6) -
(2, 5) (2, 5) - (1, 2) (2, 5) (1, 5)
(2, 5) (1, 1) - (1, 2) (1, 1) -
(2, 5) (2, 2) - (1, 2) (2, 2) (1, 2)
(2, 5) (5, 5) (2, 5) (1, 2) (5, 5) -
(2, 5) (6, 6) - (1, 2) (6, 6) -
(2, 5) (2, 5) - (1, 2) (2, 5) (1, 5)
R2 R1 R1°R2 R2 R1 R1°R2
(1, 6) (1, 1) - (5, 6) (1, 1) -
(1, 6) (2, 2) - (5, 6) (2, 2) -
(1, 6) (5, 5) - (5, 6) (5, 5) -
(1, 6) (6, 6) (1, 6) (5, 6) (6, 6) (5, 6)
(1, 6) (2, 5) - (5, 6) (2, 5) -
(1, 6) (1, 1) - (5, 6) (1, 1) -
(1, 6) (2, 2) - (5, 6) (2, 2) -
(1, 6) (5, 5) - (5, 6) (5, 5) -
(1, 6) (6, 6) (1, 6) (5, 6) (6, 6) (5, 6)
(1, 6) (2, 5) - (5, 6) (2, 5) -
Tentunya operasi komposisi ini tidak hanya berlaku pada relasi atas satu himpunan saja, melainkan dapat pula digunakan untuk relasi yang melibatkan dua himpunan. Jika S relasi dari himpunan A ke himpunan B, dan R relasi dari himpunan B ke himpunan C, maka R°S, komposisi S diteruskan ke R adalah jika (a,b)∈S, dan (b,c)∈R, maka (a, c) ∈ R°S.
3. Sifat Relasi
Sifat relasi:
1. Reflexive: ∀a ∈ A, maka (a, a)∈R
2. Symmetry: ∀a, b ∈ A, jika (a, b) ∈ R → (b, a)∈R
3. Antisymmetry: ∀ a, b ∈ A, jika (a, b) ∈ R ∧ a ≠ b → (b, a) ∉ R {ini setara dengan (a,b) ∈ R ∧ (b,a) ∈ R → a=b}
4. Transitivity: ∀ a, b, c ∈ A, jika (a, b) ∈ R ∧ (b, c) ∈ R → (a, c)∈R
Sifat relasi:
1. Reflexive: ∀a ∈ A, maka (a, a)∈R
2. Symmetry: ∀a, b ∈ A, jika (a, b) ∈ R → (b, a)∈R
3. Antisymmetry: ∀ a, b ∈ A, jika (a, b) ∈ R ∧ a ≠ b → (b, a) ∉ R {ini setara dengan (a,b) ∈ R ∧ (b,a) ∈ R → a=b}
4. Transitivity: ∀ a, b, c ∈ A, jika (a, b) ∈ R ∧ (b, c) ∈ R → (a, c)∈R
Sifat simetri dan antisimetri tidak saling berlawanan, boleh jadi suatu relasi bersifat tidak simetri dan sekaligus tidak antisimetri, tetapi tidak mungkin suatu relasi sekaligus bersifat simetri dan antisimetri.
Perbedaan antara symmetry dan variasinya
1. Symmetry : ∀ a, b ∈A berlaku aRb → bRa
2. Nonsymmetry : ∃ a, b ∈ A berlaku (a,b)∈R ∧ (b,a) ∉ R
3. Non antisymmetry : ∃ a, b ∈ A berlaku (a,b)∈R ∧ (b,a)∈R∧(a≠b)
4. Antisymmetry : ∀ a, b ∈ A berlaku (a,b) ∈ R ∧ (b,a) ∈ R → a=b
Perbedaan antara symmetry dan variasinya
1. Symmetry : ∀ a, b ∈A berlaku aRb → bRa
2. Nonsymmetry : ∃ a, b ∈ A berlaku (a,b)∈R ∧ (b,a) ∉ R
3. Non antisymmetry : ∃ a, b ∈ A berlaku (a,b)∈R ∧ (b,a)∈R∧(a≠b)
4. Antisymmetry : ∀ a, b ∈ A berlaku (a,b) ∈ R ∧ (b,a) ∈ R → a=b
Contoh 9:
Jika A = {1, 2, 3, 4}, berikut diberikan relasi atas A:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2,2), (3, 3), (4, 1), (4,4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3),
(3,4), (4, 4)}
R6 = {(3, 4)}
R7 = {(1, 1)}
R8 = {(1, 1), (1, 2), (3, 4), (4, 3)}
Manakah dari kedelapan relasi di atas yang masing-masing bersifat: refleksif, simetri, anti simetri, transitif, dan yang bukan simetri sekaligus bukan antisimetri.
Jawab:
Pada relasi-relasi di atas yang bersifat refleksif adalah: R3, dan R5.
R1 tidak refleksif karena (3, 3)∉R1.
Relasi yang bersifat simetri: R2, R3, dan R7.
Relasi yang bersifat antisimetri: R4, R5, R6, dan R7.
Relasi yang bersifat transitif: R5, R6, dan R7.
Untuk melihat R3 tidak bersifat transitif, dapat menggunakan tabel berikut:
Jika A = {1, 2, 3, 4}, berikut diberikan relasi atas A:
R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2,2), (3, 3), (4, 1), (4,4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3),
(3,4), (4, 4)}
R6 = {(3, 4)}
R7 = {(1, 1)}
R8 = {(1, 1), (1, 2), (3, 4), (4, 3)}
Manakah dari kedelapan relasi di atas yang masing-masing bersifat: refleksif, simetri, anti simetri, transitif, dan yang bukan simetri sekaligus bukan antisimetri.
Jawab:
Pada relasi-relasi di atas yang bersifat refleksif adalah: R3, dan R5.
R1 tidak refleksif karena (3, 3)∉R1.
Relasi yang bersifat simetri: R2, R3, dan R7.
Relasi yang bersifat antisimetri: R4, R5, R6, dan R7.
Relasi yang bersifat transitif: R5, R6, dan R7.
Untuk melihat R3 tidak bersifat transitif, dapat menggunakan tabel berikut:
(a,b) (b,c) (a,c) Keterangan
(1,1) (1,2) (1,2) Anggota R3
(1,2) (2,2) (1,2) Anggota R3
(1,4) (4,1) (1,1) Anggota R3
(2,1) (1,4) (2,4) Bukan anggota R3
(2,2) (2,1) (2,1) Anggota R3
(1,1) (1,2) (1,2) Anggota R3
(1,2) (2,2) (1,2) Anggota R3
(1,4) (4,1) (1,1) Anggota R3
(2,1) (1,4) (2,4) Bukan anggota R3
(2,2) (2,1) (2,1) Anggota R3
Untuk melihat R5 bersifat transitif, lihat tabel berikut:
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2,2), (2,3), (2,4), (3, 3), (3, 4),(4, 4)}
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2,2), (2,3), (2,4), (3, 3), (3, 4),(4, 4)}
(a,b) (b,c) (a,c) Keterangan
(1,1) (1,2) (1,2) Anggota R5
(1,2) (2,2) (1,2) Anggota R5
(1,3) (3,3) (1,3) Anggota R5
(1,4) (4,1) (1,1) Anggota R5
(2,2) (2,4) (2,4) Bukan anggota R3
(2,3) (2,1) (2,1) Anggota R3
(2,4)
(3,3)
(3,4)
(4,4)
(1,1) (1,2) (1,2) Anggota R5
(1,2) (2,2) (1,2) Anggota R5
(1,3) (3,3) (1,3) Anggota R5
(1,4) (4,1) (1,1) Anggota R5
(2,2) (2,4) (2,4) Bukan anggota R3
(2,3) (2,1) (2,1) Anggota R3
(2,4)
(3,3)
(3,4)
(4,4)
Relasi yang bukan simetri dan bukan pula antisimetri: R1, dan R8.
