Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 2.6 Relasi dan Graf

Subbagian Pratinjau Bagian

Selidiki!
Perhatikan tiga roda putar di bawah ini.
🔗
Tiga roda putar
Jika Anda dan seorang teman masing-masing memilih roda putar yang berbeda lalu memutarnya, kita dapat mempertimbangkan sembilan hasil yang mungkin. Sebagai contoh, untuk roda putar \(A\) dan \(B\text{,}\) hasilnya adalah
\begin{equation*} (2,1), (2,6), (2,8), (4,1), (4,6), (4,8), (9,1), (9,6), (9,8)\text{.} \end{equation*}
Hal ini menunjukkan bahwa roda putar \(A\) akan menang lima dari sembilan kali.
🔗
Bandingkan kombinasi roda putar lainnya. Roda putar manakah yang terbaik?
🔗
🔗
Pada bagian ini, kita akan mempelajari generalisasi graf yang disebut relasi. Kita akan melihat bagaimana relasi dapat direpresentasikan oleh graf dan bagaimana graf dapat digunakan untuk merepresentasikan relasi. Kita juga akan mempertimbangkan beberapa sifat yang mungkin dimiliki relasi dan bagaimana sifat-sifat tersebut dapat digunakan untuk mengklasifikasikan relasi ke dalam berbagai jenis.
🔗

Lembar Kerja Aktivitas Pratinjau

Dalam suatu bulan, beberapa tanggal lebih mirip satu sama lain daripada tanggal lainnya. Sebagai contoh, tanggal 3 lebih menyerupai tanggal 24 daripada tanggal 15. Apa yang mungkin dimaksud dengan pernyataan ini? Kita akan mempelajari dua penafsiran yang membuatnya benar.
🔗
1.
Kita mengatakan bahwa dua bilangan antara 1 dan 31 berelasi, ditulis \(a \sim b\text{,}\) jika selisihnya merupakan kelipatan 7. Sebagai contoh, \(3 \sim 24\) karena \(24-3 = 3\cdot 7\text{,}\) tetapi \(3 \not\sim 15\) karena \(15-3 = 12\text{,}\) yang bukan kelipatan 7.
🔗
(a)
Manakah di antara pernyataan berikut yang benar? Dengan kata lain, pasangan bilangan manakah yang berelasi menurut definisi di atas?
🔗
🔗
🔗
(b)
Manakah di antara pernyataan berikut yang benar tentang relasi \(\sim\) dalam kasus ini?
🔗
  • \(a \sim a\) untuk setiap bilangan \(a\)
    🔗
    🔗
  • \(a \not\sim a\) untuk setiap bilangan \(a\)
    🔗
    🔗
  • Untuk setiap bilangan \(a\) dan \(b\text{,}\) jika \(a \sim b\text{,}\) maka \(b \sim a\)
    🔗
    🔗
  • Untuk setiap bilangan \(a\) dan \(b\text{,}\) jika \(a \sim b\) dan \(b \sim a\text{,}\) maka \(a = b\)
    🔗
    🔗
  • Untuk setiap bilangan \(a\) dan \(b\text{,}\) jika \(a \sim b\) dan \(b \sim c\text{,}\) maka \(a \sim c\)
    🔗
    🔗
🔗
🔗
(c)
Kita akan menulis \([a]\) untuk himpunan semua bilangan yang berelasi dengan \(a\text{.}\) Sebagai contoh, \([7] = \{7, 14, 21, 28\}\text{.}\) Tentukan masing-masing himpunan berikut:
🔗
🔗
Adakah bilangan yang berada dalam lebih dari satu himpunan \([a]\) di atas?
🔗
🔗
🔗
2.
Jika Anda membagi kelipatan 7 dengan 7, hasilnya adalah bilangan bulat. Jika membagi bilangan lain dengan 7, Anda dapat menuliskan hasilnya sebagai desimal atau sebagai hasil bagi dan sisa. Sebagai contoh, \(19 \div 7\) menghasilkan \(2\) dengan sisa 5 karena kita dapat menulis \(19 = 2\cdot 7 + 5\text{.}\) Sisa ini disebut residu modulo. Dalam pemrograman Python (dan banyak bahasa lain), operator modulo ditulis sebagai %. Sebagai contoh, 19 % 7 adalah 5. Cobalah untuk beberapa bilangan.
🔗
(a)
Tentukan semua bilangan \(a\) antara 1 dan 31 yang kongruen dengan \(5 \mod 7\text{.}\) Artinya, tentukan semua \(a\) sedemikian sehingga a % 7 = 5.
🔗
🔗
(b)
Karena operasi modulo merupakan fungsi, setiap bilangan memiliki tepat satu residu modulo 7. Artinya, kelas-kelas residu mempartisi bilangan 1 sampai 31: setiap bilangan berada dalam tepat satu himpunan bilangan dengan residu tertentu. Kita telah menemukan himpunan untuk residu 5. Tentukan himpunan-himpunan lainnya.
🔗
🔗
🔗
(c)
Kita dapat menggunakan nilai-nilai residu modulo untuk mendefinisikan relasi pada bilangan 1 sampai 31. Kita mengatakan bahwa \(a \sim b\) jika a % 7 = b % 7. Dengan kata lain, dua bilangan berelasi jika keduanya berada dalam himpunan yang sama pada partisi yang ditemukan di atas.
🔗
Manakah di antara pernyataan berikut yang benar? Dengan kata lain, pasangan bilangan manakah yang berelasi menurut relasi modulus ini?
🔗
🔗
🔗
🔗
🔗
🔗

Subbagian Relasi secara Umum

Graf merupakan salah satu cara untuk merepresentasikan hubungan di antara berbagai objek. Kita telah melihat cara menggunakan graf untuk merepresentasikan orang-orang yang berteman, kelas-kelas yang jadwalnya bertabrakan, atau stasiun radio yang terlalu berdekatan untuk menggunakan frekuensi yang sama. Namun, tidak semua cara menghubungkan berbagai hal dapat direpresentasikan oleh graf. Pada bagian ini, kita akan membahas konsep relasi yang lebih umum dan melihat hubungannya dengan graf.
🔗
Perhatikan contoh relasi antara mahasiswa dan mata kuliah yang berlaku ketika seorang mahasiswa mengikuti mata kuliah tersebut (pada semester tertentu). Ini merupakan relasi antara dua himpunan berbeda (mahasiswa dan mata kuliah). Jika kita menggunakan graf untuk menggambarkan relasi ini, graf tersebut bersifat bipartit karena dua mahasiswa tidak pernah saling berelasi dan dua mata kuliah juga tidak pernah saling berelasi.
🔗
Graf sebenarnya terdiri atas himpunan simpul dan himpunan sisi: \(G = (V, E)\text{;}\) setiap anggota himpunan \(E\) merupakan subhimpunan dua unsur dari \(V\text{.}\) Jika kita ingin menonjolkan sifat bipartit graf, kita dapat membagi \(V\) menjadi dua himpunannya dan menulis \(G = ((A, B), E)\text{.}\) Dalam notasi ini, agar graf bersifat bipartit, setiap sisi harus berupa pasangan \((a,b)\text{,}\) dengan \(a\) anggota \(A\) dan \(b\) anggota \(B\text{.}\) Dengan kata lain, setiap sisi merupakan anggota hasil kali Kartesius dari \(A\) dan \(B\text{,}\) yang ditulis
\begin{equation*} A \times B = \{(a,b) \st a \in A,~b \in B\}. \end{equation*}
(Cara lain menyatakannya adalah bahwa \(A \times B\) merupakan “himpunan semua pasangan terurut yang terdiri atas anggota \(A\) dan \(B\text{.}\)”)
🔗

Keterangan 2.6.1.

Ada satu hal halus yang perlu kita tunjukkan: graf bipartit yang telah dideskripsikan sebenarnya memiliki sisi berarah dari \(A\) ke \(B\) karena kita mempertimbangkan pasangan terurut. Menurut definisi graf kita, sisi merupakan subhimpunan dua unsur dari himpunan simpul, sedangkan subhimpunan tidak terurut. Selama \(A\) dan \(B\) saling lepas, tidak ada kerancuan. Namun, kita akan menjumpai relasi ketika \(A\) dan \(B\) berbagi beberapa anggota, sementara urutan tetap penting. Kita akan segera membahasnya lebih lanjut.
🔗
🔗
Contoh ini menggambarkan dengan tepat apa yang dimaksud dengan relasi biner secara umum. Berikut definisi cermatnya.
🔗

Definisi 2.6.2.

Sebuah relasi biner adalah himpunan pasangan terurut. Kita mengatakan bahwa relasi biner tersebut merupakan relasi pada himpunan \(A\) dan \(B\) jika pasangan-pasangan terurutnya membentuk subhimpunan dari \(A \times B\text{.}\) Kita mengatakan bahwa relasi biner tersebut merupakan relasi pada himpunan \(A\) jika pasangan-pasangan terurutnya membentuk subhimpunan dari \(A \times A\text{.}\)
🔗
🔗
Perhatikan bahwa \(A \times A\) adalah himpunan semua pasangan terurut yang kedua koordinatnya merupakan anggota \(A\text{.}\)
🔗

Contoh 2.6.3.

Perhatikan himpunan mahasiswa \(A\) dan himpunan mata kuliah \(B\text{.}\) Misalkan \(A = \{\text{Al, Bob, Cat, Dirk, Eva}\}\) dan \(B = \{\text{Kalkulus, Matematika Diskret, Statistika}\}\text{.}\) Semua mahasiswa kecuali Dirk mengikuti Kalkulus, Bob dan Eva mengikuti Matematika Diskret, sedangkan Al, Cat, dan Dirk mengikuti Statistika.
🔗
Kita dapat mendefinisikan relasi \(T\) berupa “mengikuti” antara \(A\) dan \(B\text{,}\) yang berlaku bagi seorang mahasiswa dan suatu mata kuliah tepat ketika mahasiswa tersebut mengikuti mata kuliah itu. Tuliskan relasi ini sebagai subhimpunan dari \(A\times B\) dan gambarlah graf bipartitnya.
🔗
Penyelesaian.
Untuk menuliskan relasi tersebut secara tepat, kita cukup memberikan himpunan pasangan terurut:
\begin{align*} T = \{\amp (\text{Al}, \text{Kalkulus}), (\text{Al}, \text{Statistika}),\\ \amp (\text{Bob}, \text{Kalkulus}), (\text{Bob}, \text{Matematika Diskret})\\ \amp (\text{Cat}, \text{Kalkulus}), (\text{Cat}, \text{Statistika})\\ \amp (\text{Dirk}, \text{Statistika})\\ \amp (\text{Eva}, \text{Kalkulus}), (\text{Eva}, \text{Matematika Diskret})\} \end{align*}
Kita dapat menggambar relasi ini sebagai graf bipartit:
🔗
Graf bipartit yang merepresentasikan relasi “mengikuti”.
🔗
🔗

Contoh 2.6.4.

Perhatikan relasi \(M\) berupa “merupakan kelipatan dari” pada himpunan \(A = \{1,2,3,4,5,6\}\text{.}\) Tuliskan relasi ini sebagai himpunan pasangan terurut. Apakah relasi ini membentuk graf?
🔗
Penyelesaian.
Pertama, mari kita pikirkan anggota mana yang seharusnya berelasi dan mana yang tidak. Kita mengetahui bahwa \(6\) merupakan kelipatan dari \(2\text{,}\) sehingga relasi berlaku bagi pasangan \((6,2)\text{.}\) Namun, \(6\) bukan kelipatan dari \(4\text{,}\) sehingga pasangan \((6,4)\) tidak memenuhi relasi tersebut. Lebih tepatnya, kita mengatakan bahwa \((6,2) \in M\text{,}\) tetapi \((6,4) \notin M\text{.}\)
🔗
Mari kita cantumkan semua anggota \(M\text{:}\)
\begin{align*} M = \{\amp(1,1), (2,1), (2,2), (3,1), (3,3), (4,1), (4,2), (4,4), \\ \amp (5,1), (5,5), (6,1), (6,2), (6,3), (6,6)\}\text{.} \end{align*}
Relasi ini bukan graf karena dua alasan: pertama, anggota-anggota berelasi dengan dirinya sendiri; kedua, urutan anggota dalam relasi tidak simetris (misalnya, \(6\) berelasi dengan \(2\text{,}\) tetapi \(2\) tidak berelasi dengan \(6\)).
🔗
Namun, kita masih dapat menggambar sesuatu yang menyerupai graf untuk menggambarkan relasi ini. Karena arah relasi penting, kita akan memiliki sisi berarah. Sifat ini saja akan menghasilkan graf berarah. Karena simpul dapat memiliki sisi menuju dirinya sendiri, struktur tersebut kita sebut multigraf; jadi relasi ini dapat dipandang sebagai multigraf berarah.
🔗
Multigraf berarah untuk relasi “merupakan kelipatan dari” pada himpunan 1, 2, 3, 4, 5, 6
🔗
🔗
Relasi biner \(R\) pada himpunan \(A\) dan \(B\) selalu dapat “dibalik” untuk menghasilkan relasi pada himpunan \(B\) dan \(A\text{.}\) Artinya, \(R\) menyatakan bagaimana anggota \(A\) berelasi dengan anggota \(B\text{;}\) anggota \(B\) tersebut berelasi dengan anggota \(A\text{,}\) hanya saja secara invers (terbalik). Relasi baru ini kita sebut invers dari \(R\text{.}\)
🔗

Definisi 2.6.5.

Diberikan relasi biner \(R\text{,}\) definisikan \(R\inv\) sebagai invers dari \(R\text{,}\) yaitu himpunan
\begin{equation*} R\inv = \{(b,a) \st (a,b) \in R\}\text{.} \end{equation*}
🔗
🔗
Relasi \(T\) dari Contoh 2.6.3 menyatakan bahwa seorang mahasiswa mengikuti mata kuliah tertentu. Relasi invers \(T\inv\) menyatakan bahwa suatu mata kuliah diikuti oleh mahasiswa tertentu. Sebagai contoh, \((\text{Kalkulus}, \text{Al})\) merupakan anggota \(T\inv\text{.}\) Secara grafis, gambarnya tidak akan berbeda, meskipun kita dapat menempatkan himpunan mata kuliah di atas dan mahasiswa di bawah.
🔗
Relasi \(M\) dari Contoh 2.6.4 menyatakan, misalnya, bahwa \(6\) merupakan kelipatan dari \(2\) karena \((6,2) \in M\text{.}\) Untuk inversnya, kita memiliki \((2,6) \in M\inv\text{,}\) yang berarti \(2\) merupakan faktor dari \(6\text{.}\) Dalam contoh ini, kita telah merepresentasikan relasi sebagai multigraf berarah. Graf inversnya akan tampak persis sama, tetapi semua panah mengarah ke arah yang berlawanan.
🔗
Cara lain untuk membuat relasi baru adalah menggabungkan dua relasi. Misalkan, selain relasi “mengikuti” dari Contoh 2.6.3, kita mendefinisikan relasi “diajar oleh” yang memasangkan setiap mata kuliah dengan pengajarnya. Misalkan Profesor X mengajar Kalkulus. Dalam hal itu, karena Al mengikuti Kalkulus dan Kalkulus diajar oleh Profesor X, kita dapat menyimpulkan bahwa Al mengikuti mata kuliah yang diajar Profesor X.
🔗

Definisi 2.6.6.

Misalkan \(R\) merupakan relasi dari himpunan \(A\) ke \(B\) dan \(S\) merupakan relasi dari \(B\) ke \(C\text{.}\) Komposisi \(R\) dan \(S\) adalah
\begin{equation*} S \circ R = \{(a,c) \in A \times C \st (a,b) \in R \text{ dan } (b,c) \in S \text{ untuk suatu } b \in B\} \end{equation*}
🔗
🔗
Perhatikan urutan penulisan kedua relasi: \(S \circ R\text{,}\) bukan \(R \circ S\text{.}\) Alasan kita menulisnya demikian (yang mungkin tampak terbalik) adalah agar sesuai dengan notasi yang lazim untuk komposisi fungsi. Sebenarnya, fungsi tidak lain adalah jenis relasi tertentu!
🔗

Contoh 2.6.7.

Tuliskan relasi \(P \circ T\text{,}\) yaitu komposisi relasi dari Contoh 2.6.3 dan relasi
\begin{gather*} P = \{(\text{Kalkulus}, \text{Prof. X}), (\text{Matematika Diskret}, \text{Prof. L}),\\ \qquad (\text{Statistika}, \text{Prof. X}), (\text{Statistika}, \text{Prof. S})\}. \end{gather*}
Perhatikan bahwa di sini kita menyatakan mata kuliah Statistika diajar bersama oleh Profesor X dan S.
🔗
Penyelesaian.
Relasi yang kita cari adalah relasi antara mahasiswa dan profesor. Kita dapat memulai dari setiap anggota \(T\) dan memperluasnya dengan mengikuti mata kuliah menuju profesornya melalui \(P\text{.}\) Sebagai contoh, mulai dari Cat dan perhatikan bahwa \((\text{Cat}, \text{Kalkulus}) \in T\text{.}\) Sekarang perhatikan dengan apa Kalkulus berelasi melalui \(P\text{:}\) \((\text{Kalkulus}, \text{Prof. X}) \in P \text{.}\) Jadi, kita dapat menggabungkan keduanya untuk menyimpulkan bahwa \((\text{Cat}, \text{Prof. X}) \in P \circ T\text{.}\)
🔗
Pendekatan alternatif adalah mempertimbangkan pasangan mahasiswa dan profesor yang dihubungkan oleh mata kuliah yang sama. Apakah pasangan \((\text{Al}, \text{Prof. L})\) merupakan anggota komposisi? Tidak, karena tidak ada mata kuliah yang sekaligus diikuti Al dan diajar Profesor L. Di sisi lain, kita dapat menyimpulkan bahwa \((\text{Al}, \text{Prof. X}) \in P \circ T\) karena terdapat mata kuliah yang sama. Mata kuliah tersebut dapat berupa Kalkulus atau Statistika (banyaknya langkah perantara yang sama tidak menjadi persoalan, asalkan terdapat setidaknya satu).
🔗
Berikut relasi lengkapnya:
\begin{align*} P \circ T = \{\amp (\text{Al}, \text{Prof. X}), (\text{Al}, \text{Prof. S}), (\text{Bob}, \text{Prof. X}), (\text{Bob}, \text{Prof. L}), \\ \amp (\text{Cat}, \text{Prof. X}), (\text{Cat}, \text{Prof. S}), (\text{Dirk}, \text{Prof. X}), (\text{Dirk}, \text{Prof. S}),\\ \amp (\text{Eva}, \text{Prof. X}), (\text{Eva}, \text{Prof. L})\} \end{align*}
🔗
🔗
🔗
Sesuatu yang menarik sering terjadi ketika suatu relasi dikomposisikan dengan inversnya. Anda mungkin pernah melihat hal serupa untuk fungsi dalam kalkulus atau aljabar: \(f(x) = e^x\) memiliki fungsi invers \(f\inv(x) = \ln(x)\text{,}\) dan kita mengetahui bahwa \(f(f\inv(x)) = e^{\ln(x)} = x\text{.}\) Namun, fungsi adalah relasi yang setiap “masukan”-nya memiliki tepat satu “keluaran”, sehingga tidak mengherankan bahwa komposisi dengan invers hanya menghasilkan fungsi identitas. Jika masukan dapat memiliki beberapa keluaran dan keluaran dapat memiliki beberapa masukan, kita memperoleh sesuatu yang lebih.
🔗

Contoh 2.6.8.

Deskripsikan relasi \(T\inv \circ T\) (menggunakan relasi \(T\) yang telah kita kenal dari Contoh 2.6.3). Apa yang dinyatakan relasi ini tentang mahasiswa dan mata kuliah?
🔗
Penyelesaian.
Dengan mengikuti relasi tersebut, kita dapat memulai dengan menyatakan bahwa Al mengikuti Kalkulus dan Kalkulus diikuti oleh Al, sehingga Al berelasi dengan Al. Namun, Kalkulus juga diikuti oleh Bob, sehingga kini Al juga berelasi dengan Bob. Apakah Bob juga berelasi dengan Al? Ya, karena Bob mengikuti Kalkulus dan Kalkulus diikuti oleh Al.
🔗
Komposisi tersebut menyatakan pasangan mahasiswa mana yang mengikuti setidaknya satu mata kuliah yang sama. Ini mencakup hampir semua pasangan mahasiswa, kecuali Dirk tidak berelasi dengan Bob atau Eva karena keduanya tidak mengikuti Statistika, sedangkan Statistika adalah satu-satunya mata kuliah yang diikuti Dirk.
🔗
Alih-alih menuliskan relasi tersebut (yang hampir mencakup seluruh \(A \times A\)), berikut representasi grafnya.
🔗
Graf yang merepresentasikan komposisi T dan inversnya.
Meskipun di sini kita menggambar multigraf berarah, panah yang mengarah ke kedua arah berarti bahwa sebenarnya kita cukup menggambar multigraf.
🔗
🔗
🔗
🔗

Subbagian Sifat-Sifat Relasi

Mulai saat ini, kita hanya akan mempertimbangkan relasi pada satu himpunan (jadi, dari suatu himpunan ke dirinya sendiri). Untuk membantu memahami relasi-relasi ini, mari kita perhatikan beberapa sifat dasar yang mungkin dimiliki atau tidak dimiliki suatu relasi.
🔗

Definisi 2.6.9. Refleksif, Simetris, dan Transitif.

Misalkan \(R\) merupakan relasi pada himpunan \(A\text{.}\) Kita mengatakan bahwa
  • \(R\) bersifat refleksif jika \((a,a) \in R\) untuk semua \(a \in A\text{.}\)
    🔗
    🔗
  • \(R\) bersifat simetris jika, untuk semua \(a, b \in A\text{,}\) apabila \((a,b) \in R\text{,}\) maka \((b,a) \in R\text{.}\)
    🔗
    🔗
  • \(R\) bersifat transitif jika, untuk semua \(a, b,c \in A\text{,}\) apabila \((a,b) \in R\) dan \((b,c) \in R\text{,}\) maka \((a,c)\in R\text{.}\)
    🔗
    🔗
🔗
🔗
Mari kita telaah setiap sifat ini dengan cermat.
🔗
Akan membantu jika kita mempertimbangkan beberapa contoh standar relasi pada himpunan. Sebagian besar relasi di sini akan ditulis menggunakan notasi infiks, yang berarti simbol relasi ditempatkan di antara dua objek yang direlasikan. Sebagai contoh, relasi kurang dari hampir selalu ditulis sebagai \(2 \lt 6\text{,}\) bukan \((2,6) \in \lt\text{.}\)
🔗

Contoh 2.6.10. Relasi refleksif dan nonrefleksif.

Suatu relasi bersifat refleksif ketika setiap anggota berelasi dengan dirinya sendiri. Relasi-relasi berikut bersifat refleksif:
  • Relasi “kurang dari atau sama dengan” pada setiap himpunan bilangan. Apakah \(3 \le 3\text{?}\) Lebih penting lagi, apakah setiap bilangan tidak lebih besar daripada dirinya sendiri? Karena jawabannya ya, relasi ini bersifat refleksif.
    🔗
    🔗
  • Relasi “berselisih paling banyak 3”, yang berlaku bagi dua bilangan \(a\) dan \(b\) jika \(|a-b| \le 3\text{.}\) Untuk membuktikan bahwa relasi ini refleksif, cukup perhatikan bahwa \(|a-a| = 0 \le 3\text{.}\)
    🔗
    🔗
  • Relasi “merupakan kelipatan dari” dari Contoh 2.6.4. Perhatikan bahwa multigraf berarah untuk relasi ini memiliki gelang pada setiap simpul.
    🔗
    🔗
🔗
Namun, relasi-relasi berikut tidak refleksif:
  • Relasi “berjumlah nol”, yang berlaku bagi bilangan \(a\) dan \(b\) jika \(a+b = 0\text{.}\) Perhatikan bahwa meskipun \(0 + 0 = 0\text{,}\) sehingga \((0,0)\) merupakan anggota relasi, setiap bilangan lainnya tidak berelasi dengan dirinya sendiri.
    🔗
    🔗
  • Setiap relasi yang dideskripsikan oleh graf. Ingat, graf tidak dapat memiliki sisi yang kembali membentuk gelang pada satu simpul, sehingga relasi sisi pada graf tidak refleksif. (Multigraf dapat bersifat refleksif ataupun tidak.)
    🔗
    🔗
🔗
🔗
Jika tidak ada anggota yang berelasi dengan dirinya sendiri (seperti pada relasi sisi suatu graf), relasi tersebut disebut irefleksif. Tentu saja, beberapa relasi tidak refleksif maupun irefleksif.
🔗
Memeriksa bahwa suatu relasi refleksif relatif mudah. Dua sifat lainnya dirumuskan sebagai implikasi, sehingga sedikit lebih rumit.
🔗

Contoh 2.6.11. Relasi simetris dan nonsimetris.

Pada dasarnya, relasi simetris berlaku “dua arah.” Lebih tepatnya, jika \(a\) berelasi dengan \(b\text{,}\) maka \(b\) juga berelasi dengan \(a\text{.}\)
🔗
Relasi-relasi berikut bersifat simetris.
  • Relasi “berselisih paling banyak 3”: jika \(|a-b| \le 3\text{,}\) maka \(|b-a| \le 3\text{.}\)
    🔗
    🔗
  • Relasi “berjumlah nol”: jika \(a+b = 0\text{,}\) tentu \(b + a = 0\text{.}\)
    🔗
    🔗
  • Untuk setiap graf, relasi sisi bersifat simetris. Tentu saja, untuk graf berarah, hal ini biasanya tidak benar.
    🔗
    🔗
🔗
Di sisi lain, relasi-relasi berikut tidak simetris.
  • \(\le\) tidak simetris. Untuk membuktikan bahwa suatu relasi tidak simetris, kita cukup menemukan \(a\) dan \(b\) sedemikian sehingga \(a \le b\text{,}\) tetapi \(b \not\le a\text{.}\) Memang, \(3 \le 4\text{,}\) tetapi \(4 \not\le 3\text{.}\) Terbukti.
    🔗
    🔗
  • Relasi “merupakan kelipatan dari” tidak simetris. \(6\) merupakan kelipatan dari \(2\text{,}\) tetapi \(2\) bukan kelipatan dari \(6\text{.}\)
    🔗
    🔗
🔗
🔗
Relasi yang tidak simetris dapat bersifat antisimetris, yang berarti bahwa satu-satunya keadaan ketika \((a,b)\) dan \((b,a)\) keduanya berada dalam relasi adalah ketika \(a = b\text{.}\) Perhatikan bahwa terdapat relasi yang tidak simetris maupun antisimetris.
🔗
Dalam bahasa relasi invers, suatu relasi simetris jika dan hanya jika relasi tersebut sama dengan inversnya.
🔗

Contoh 2.6.12. Relasi transitif dan nontransitif.

Jika \(a\) berelasi dengan \(b\) dan \(b\) berelasi dengan \(c\text{,}\) apakah itu berarti \(a\) berelasi dengan \(c\text{?}\) Jika hal ini benar untuk semua \(a\text{,}\) \(b\text{,}\) dan \(c\text{,}\) relasi tersebut disebut transitif.
🔗
Berikut beberapa relasi transitif.
  • \(\le\text{.}\) Misalkan \(a \le b\) dan \(b \le c\text{.}\) Jelas bahwa \(a \le c\text{.}\)
    🔗
    🔗
  • Relasi “merupakan kelipatan dari”. Relasi ini cocok untuk dibuktikan: Misalkan \(a\) merupakan kelipatan dari \(b\) dan \(b\) merupakan kelipatan dari \(c\text{.}\) Maka \(a = bk\) untuk suatu bilangan bulat \(k\) dan \(b = cj\) untuk suatu bilangan bulat \(j\text{.}\) Dengan substitusi, \(a = cjk\text{,}\) sehingga \(a\) merupakan kelipatan dari \(c\text{.}\)
    🔗
    🔗
🔗
Namun, relasi-relasi berikut tidak transitif.
  • Relasi “berselisih paling banyak 3” tidak transitif. Kita cukup menemukan tiga bilangan yang gagal memenuhi syarat tersebut. Bagaimana dengan \(1\text{,}\) \(3\text{,}\) dan \(5\text{?}\) Di sini selisih \(1\) dan \(3\) paling banyak 3, begitu pula selisih \(3\) dan \(5\text{,}\) tetapi \(|1 - 5| = 4\text{,}\) sehingga relasi tidak berlaku bagi \((1,5)\text{.}\)
    🔗
    🔗
  • Relasi “berjumlah nol” tidak transitif. Perhatikan bahwa kita tidak pernah menyatakan \(a\text{,}\) \(b\text{,}\) dan \(c\) harus berupa bilangan yang berbeda. Misalkan \(a = 5\text{,}\) \(b = -5\text{,}\) dan \(c = 5\text{.}\) Maka \(a+b = 0\) dan \(b + c = 0\text{,}\) sehingga relasi berlaku bagi \((a,b)\) dan \((b,c)\text{.}\) Namun, \(a + c = 10\text{,}\) sehingga relasi tidak berlaku bagi \((a,c)\text{.}\)
    🔗
    🔗
🔗
Relasi sisi suatu graf dapat bersifat transitif atau tidak. Bagaimanakah bentuk graf jika relasi sisinya transitif?
🔗
🔗
🔗

Subbagian Relasi Ekuivalensi

Sekarang kita akan melakukan sesuatu yang sangat lazim dalam matematika: Kita akan mengamati jenis relasi yang paling umum, mempertimbangkan sifat-sifatnya, kemudian mengklasifikasikan relasi lain yang juga memiliki sifat-sifat tersebut sebagai kelas relasi tertentu.
🔗
Relasi yang paling kita kenal adalah kesamaan. Sifat relasi apa saja yang dimiliki relasi kesamaan? Tentu setiap objek sama dengan dirinya sendiri, sehingga kesamaan bersifat refleksif. Jika \(a = b\text{,}\) maka \(b = a\text{,}\) sehingga kesamaan bersifat simetris. Jika \(a = b\) dan \(b = c\text{,}\) maka \(a = c\text{,}\) sehingga kesamaan bersifat transitif.
🔗
Relasi lain apa yang bersifat refleksif, simetris, dan transitif? Tepat relasi-relasi yang berperilaku seperti kesamaan. Relasi demikian disebut relasi ekuivalensi.
🔗

Definisi 2.6.13. Relasi Ekuivalensi.

Relasi yang refleksif, simetris, dan transitif disebut relasi ekuivalensi.
🔗
🔗

Catatan 2.6.14.

Contoh lain jenis relasi yang dimodelkan menurut relasi klasik adalah urutan parsial. Relasi ini refleksif, antisimetris, dan transitif, sama seperti relasi kurang dari atau sama dengan. Mungkin Anda telah memperhatikan bahwa relasi subhimpunan, yang ditulis \(\subseteq\text{,}\) terasa sangat mirip dengan \(\le\text{.}\) Hal ini karena \(\subseteq\) juga merupakan urutan parsial. Demikian pula relasi “merupakan kelipatan dari” yang kita lihat di atas.
🔗
Ada banyak hal menarik yang dapat kita katakan tentang urutan parsial dan himpunan yang diurutkannya secara parsial, yang disebut himpunan terurut parsial atau poset. Pembahasan itu kita simpan untuk kesempatan lain.
🔗
🔗
Tidak satu pun contoh yang telah kita bahas sejauh ini dalam bagian ini merupakan relasi ekuivalensi, tetapi relasi ekuivalensi muncul di mana-mana dalam matematika. Relasi ini begitu umum sehingga mudah terlewatkan sebagai sesuatu yang layak dibahas. Mari kita lihat beberapa contoh.
🔗

Contoh 2.6.15.

Buktikan bahwa relasi \(\equiv_2\text{,}\) yang berlaku bagi dua bilangan bulat jika selisihnya genap, merupakan relasi ekuivalensi. Artinya, \(a \equiv_2 b\) jika dan hanya jika \(b-a = 2k\) untuk suatu bilangan bulat \(k\text{.}\)
🔗
Penyelesaian.
Kita cukup memeriksa tiga sifat yang disyaratkan.
  1. \(\equiv_2\) bersifat refleksif: untuk setiap bilangan bulat \(a\text{,}\) kita memiliki \(a - a = 0\) dan \(0 = 2k\) untuk \(k = 0\text{,}\) sehingga \(a \equiv_2 a\text{.}\)
    🔗
    🔗
  2. \(\equiv_2\) bersifat simetris: Tetapkan sembarang bilangan bulat \(a\) dan \(b\text{,}\) lalu asumsikan \(a \equiv_2 b\text{.}\) Ini berarti \(b-a = 2k\) untuk suatu bilangan bulat \(k\text{.}\) Bagaimana dengan \(a - b\text{?}\) Kita memiliki \(a-b = 2(-k)\text{,}\) dan \(-k\) merupakan bilangan bulat, sehingga \(b \equiv_2 a\text{.}\)
    🔗
    🔗
  3. \(\equiv_2\) bersifat transitif: Tetapkan sembarang bilangan bulat \(a\text{,}\) \(b\text{,}\) dan \(c\text{,}\) lalu asumsikan \(a \equiv_2 b\) dan \(b \equiv_2 c\text{.}\) Ini berarti \(b-a = 2k\) dan \(c-b = 2j\) untuk beberapa bilangan bulat \(k\) dan \(j\text{.}\) Bagaimana dengan \(c - a\text{?}\) Kita memiliki
    \begin{equation*} c - a = (c- b) + (b - a) = 2k+2j = 2(k+j)\text{.} \end{equation*}
    Karena \(k+j\) merupakan bilangan bulat, kita memperoleh \(a \equiv_2 c\) sebagaimana diperlukan.
    🔗
    🔗
🔗
🔗
🔗

Contoh 2.6.16.

Kita sebut dua graf “ekuivalen-barisan-derajat” jika keduanya memiliki barisan derajat yang sama. Apakah ini merupakan relasi ekuivalensi?
🔗
Penyelesaian.
Ya. Jelas bahwa setiap graf memiliki barisan derajat yang sama dengan dirinya sendiri, sehingga relasi ini refleksif. Jika \(G_1\) memiliki barisan derajat yang sama dengan \(G_2\text{,}\) maka \(G_2\) memiliki barisan derajat yang sama dengan \(G_1\text{,}\) sehingga relasi ini simetris. Terakhir, jika \(G_1\) memiliki barisan derajat yang sama dengan \(G_2\text{,}\) yang memiliki barisan derajat yang sama dengan \(G_3\text{,}\) ketiganya memiliki barisan derajat yang sama. Jadi, \(G_1\) memiliki barisan derajat yang sama dengan \(G_3\) (yakni, relasi ini transitif).
🔗
🔗
🔗
Contoh ini hampir terlalu jelas. Hal itu karena kita mengatakan dua objek berelasi jika suatu sifat yang terdefinisi dengan baik dari kedua objek tersebut sama, sedangkan kesamaan memenuhi sifat-sifat relasi ekuivalensi. Tujuan kita selanjutnya adalah memahami hal ini dengan lebih baik dan melihat bahwa sifat inilah yang tepatnya menghasilkan relasi ekuivalensi.
🔗
🔗

Subbagian Kelas Ekuivalensi dan Partisi

Diberikan relasi apa pun \(R\text{,}\) kita dapat mengamati himpunan anggota yang berelasi dengan suatu anggota tertentu. Untuk relasi “mengikuti”, kita dapat menanyakan mata kuliah apa yang diikuti Al (yakni, mata kuliah yang berelasi dengan Al). Untuk relasi “merupakan kelipatan dari”, kita dapat menanyakan bilangan apa saja yang membagi 6. Salah satu cara mempelajari relasi adalah mempelajari himpunan objek yang berelasi dengan setiap anggota.
🔗

Definisi 2.6.17.

Misalkan \(R\) merupakan relasi pada himpunan \(A\text{,}\) dan \(a\) merupakan anggota \(A\text{.}\) Kelas relasi dari \(a\text{,}\) yang ditulis \([a]\text{,}\) adalah himpunan semua anggota \(b\) sedemikian sehingga \((a,b) \in R\) (himpunan \(b\) yang berelasi dengan \(a\) melalui \(R\)). Artinya,
\begin{equation*} [a] = \{b \in A \st (a,b) \in R\}\text{.} \end{equation*}
🔗
Jika \(R\) merupakan relasi ekuivalensi, kelas-kelas relasinya disebut kelas ekuivalensi.
🔗
🔗

Contoh 2.6.18.

Tentukan kelas-kelas relasi untuk relasi “merupakan kelipatan dari” pada himpunan \(A = \{1,2,3,4,5,6\}\text{.}\)
🔗
Penyelesaian.
Terdapat enam kelas relasi karena setiap anggota memiliki kelas relasi. Kelas-kelas tersebut adalah:
\begin{align*} [1] = \amp \{1\}\\ [2] = \amp \{1,2\}\\ [3] = \amp \{1,3\}\\ [4] = \amp \{1,2,4\}\\ [5] = \amp \{1,5\}\\ [6] = \amp \{1,2,3,6\}. \end{align*}
Sebagai contoh, kita memperoleh \([4]\) dengan mempertimbangkan semua pasangan \((4,b)\) yang memenuhi relasi: 4 merupakan kelipatan dari 1, 2, dan 4, sehingga bilangan-bilangan tersebut merupakan nilai \(b\) yang mungkin.
🔗
Lihat kembali multigraf berarah untuk relasi ini yang ditunjukkan dalam penyelesaian Contoh 2.6.4. Apakah kelas-kelas relasinya? Kelas-kelas itu tidak lain adalah tetangga setiap simpul (dengan tetangga ditentukan dengan mengikuti arah panah yang benar).
🔗
🔗
🔗

Contoh 2.6.19.

Tentukan kelas-kelas ekuivalensi untuk relasi \(\equiv_2\) pada bilangan bulat.
🔗
Penyelesaian.
Oh tidak! Himpunan kita tak hingga, jadi apakah kita akan memiliki tak hingga banyak kelas relasi? Baiklah, sebaiknya kita mulai...
🔗
Bilangan apa saja yang berelasi dengan 1? Ingat, kita mencari bilangan bulat yang selisihnya dengan 1 merupakan kelipatan 2. Jadi, 3 pasti termasuk. Demikian pula 5, 7, -1, -3, dan seterusnya—semua bilangan ganjil? Ya, karena selisih setiap dua bilangan ganjil adalah genap. Kita juga dapat mengatakan bahwa selisih setiap dua bilangan genap adalah genap, sehingga kelas ekuivalensi 2 akan memuat semua bilangan genap. Sejauh ini kita memperoleh:
\begin{align*} [1] = \amp \{\ldots, -3, -1, 1, 3, 5, \ldots\}\\ [2] = \amp \{\ldots, -4, -2, 0, 2, 4, 6, \ldots\} \end{align*}
🔗
Sebenarnya, tampaknya kita sudah selesai. Meskipun \([3]\text{,}\) \([4]\text{,}\) \([5]\text{,}\) dan seterusnya semuanya merupakan kelas ekuivalensi yang sah, anggota-anggota yang berelasi dengan \(3\) tepat sama dengan anggota-anggota yang berelasi dengan \(1\) karena \(1 \equiv_2 3\text{.}\) Hal ini terjadi karena relasinya transitif! Jika \(3 \equiv_2 b\text{,}\) kita mengetahui bahwa \(1 \equiv_2 b\text{.}\)
🔗
Jadi, kita memiliki tepat dua kelas ekuivalensi. Setiap bilangan bulat berada dalam tepat satu dari kedua kelas ekuivalensi ini, dan kelas ekuivalensi setiap bilangan bulat tepat merupakan kelas yang memuatnya.
🔗
🔗
🔗
Cermati kedua contoh di atas. Untuk relasi “merupakan kelipatan dari”, yang BUKAN relasi ekuivalensi, beberapa anggota termasuk dalam lebih dari satu kelas relasi yang berbeda. Namun, untuk \(\equiv_2\text{,}\) yang merupakan relasi ekuivalensi, setiap anggota berada dalam tepat satu kelas ekuivalensi. Hal ini bukan kebetulan. Untuk memahaminya, kita akan mendefinisikan istilah baru.
🔗

Definisi 2.6.20.

Diberikan himpunan tak kosong \(A\text{,}\) sebuah partisi dari \(A\) adalah himpunan \(P\) yang beranggotakan subhimpunan tak kosong dari \(A\) sedemikian sehingga setiap anggota \(A\) berada dalam tepat satu anggota \(P\text{.}\)
🔗
🔗
Definisi tersebut melibatkan banyak simbol dan himpunan. Namun, sebenarnya tidak rumit: Partisi adalah cara memecah suatu himpunan menjadi subhimpunan saling lepas yang menutupi seluruh himpunan. Subhimpunan saling lepas berarti tidak ada anggota yang berada dalam lebih dari satu subhimpunan. Subhimpunan menutupi himpunan berarti setiap anggota berada dalam setidaknya satu subhimpunan.
🔗

Contoh 2.6.21.

Berikan beberapa partisi berbeda dari himpunan \(A = \{1,2,3,4,5\}\text{.}\)
🔗
Penyelesaian.
Ada begitu banyak pilihan! Salah satunya adalah:
\begin{equation*} P_1 = \{\{1,2,3\}, \{4,5\}\}\text{.} \end{equation*}
Itu merupakan partisi \(A\) menjadi dua subhimpunan. Partisi lainnya:
\begin{equation*} P_2 = \{\{1\}, \{2\}, \{3\}, \{4\}, \{5\}\}\text{.} \end{equation*}
Contoh lainnya:
\begin{equation*} P_3 = \{\{1,3,5\}, \{2,4\}\}\text{,} \end{equation*}
yang merupakan partisi menjadi bilangan ganjil dan genap. Kita juga memiliki partisi trivial:
\begin{equation*} P_4 = \{\{1,2,3,4,5\}\}\text{.} \end{equation*}
Catatan: Di dalam himpunan \(P_4\) hanya terdapat satu himpunan.
🔗
🔗
🔗
Kadang-kadang agak membingungkan untuk memandang anggota partisi sebagai subhimpunan karena partisi sendiri merupakan himpunan, dan himpunan yang beranggotakan himpunan sulit dibicarakan. Kadang-kadang kita menyebut partisi sebagai koleksi dan setiap anggotanya sebagai bagian atau blok.
🔗
Sekarang gagasan utamanya: Untuk setiap relasi ekuivalensi, kelas-kelas ekuivalensinya membentuk partisi; dan untuk setiap partisi, kita dapat mendefinisikan relasi “berada dalam subhimpunan yang sama” yang merupakan relasi ekuivalensi. Kita telah melihat bahwa kelas-kelas ekuivalensi \(\equiv_2\) membentuk partisi. Sekarang mari kita meninjau arah sebaliknya.
🔗

Contoh 2.6.22.

Definisikan relasi ekuivalensi \(\sim\) pada himpunan \(A = \{1,2,3,4,5\}\) dari partisi \(P = \{\{1,4\}, \{2,3,5\}\}\text{.}\)
🔗
Penyelesaian.
Katakan bahwa dua anggota \(A\) ekuivalen jika keduanya berada dalam anggota \(P\) yang sama. Jadi, \(1 \sim 4\) dan \(4\sim 1\text{,}\) serta \(2 \sim 3\text{,}\) \(2 \sim 5\text{,}\) \(3 \sim 5\text{,}\) \(3\sim 2\text{,}\) \(5\sim 2\text{,}\) dan \(5\sim 3\text{.}\) Tunggu. Kita juga memiliki \(1\sim 1\text{,}\) \(2\sim 2\text{,}\) dan seterusnya, karena setiap bilangan berada dalam subhimpunan yang sama dengan dirinya sendiri.
🔗
Dari pemeriksaan langsung, jelas bahwa relasi ini refleksif, simetris, dan transitif, sehingga merupakan relasi ekuivalensi.
🔗
🔗
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Perhatikan relasi \(R\) pada bilangan bulat yang berlaku bagi \(a\) dan \(b\) tepat ketika \(b-a \ge 4\text{.}\) Sebagai contoh, \((2,7) \in R\text{,}\) tetapi \((8,6) \notin R\text{.}\) Manakah di antara sifat relasi berikut yang dimiliki \(R\text{?}\)
🔗
  • \(R\) bersifat refleksif.
    🔗
  • Jika \(R\) refleksif, khususnya (2,2) akan berada dalam \(R\text{.}\) Namun, \(2-2 = 0\text{,}\) yang tidak lebih besar dari atau sama dengan 4.
  • \(R\) bersifat irefleksif.
    🔗
  • Benar. Karena tidak ada bilangan bulat yang sekurang-kurangnya empat lebih besar daripada dirinya sendiri, relasi tersebut tidak berlaku bagi anggota mana pun dengan dirinya sendiri.
  • \(R\) bersifat simetris.
    🔗
  • Jika \(R\) simetris, untuk setiap \(a\) dan \(b\) sedemikian sehingga \(b-a \ge 4\text{,}\) kita juga akan memiliki \(a-b \ge 4\text{.}\) Namun, hal ini tidak benar. Sebagai contoh, \((2,10)\) berada dalam \(R\text{,}\) tetapi \((10,2)\) tidak. (Kita tidak menggunakan selisih mutlak.)
  • \(R\) bersifat antisimetris.
    🔗
  • Benar. Tidak ada bilangan \(a\) dan \(b\) sedemikian sehingga \(b-a \ge 4\) dan \(a-b \ge 4\) keduanya berlaku. Jadi, hipotesis dalam definisi antisimetris selalu salah, yang membuat seluruh pernyataan dalam definisi tersebut benar.
  • \(R\) bersifat transitif.
    🔗
  • Benar. Jika \(b-a \ge 4\) dan \(c-b \ge 4\text{,}\) maka \(c-a = (c-b) + (b-a) \ge 4+4 = 8\text{,}\) sehingga \(c-a \ge 4\text{.}\)
🔗

2.

Tidak semua graf memiliki relasi sisi yang transitif. Namun, adakah graf yang memilikinya? Jika ada, berikan contoh dan jelaskan mengapa relasi sisinya transitif. Jika tidak ada, jelaskan alasannya.
🔗
🔗

3.

Setelah membaca bagian ini, pertanyaan apa yang Anda miliki? Ajukan setidaknya satu pertanyaan tentang bagian ini yang membuat Anda ingin tahu lebih lanjut.
🔗
🔗
🔗

Latihan Soal Latihan

1.

Tentukan relasi mana yang bersifat refleksif. Variabel \(x\text{,}\) \(y\text{,}\) \(x'\text{,}\) dan \(y'\) menyatakan bilangan bulat.
🔗
  • \(x \sim y\) jika dan hanya jika \(x + y\) ganjil.
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(x - y\) positif.
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(xy \geq 0\) .
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(x + y\) genap.
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(x + y\) positif.
    🔗
    🔗
🔗
🔗

2.

Tentukan relasi mana yang bersifat simetris. Variabel \(x\text{,}\) \(y\text{,}\) \(x'\text{,}\) dan \(y'\) menyatakan bilangan bulat.
🔗
  • \(x \sim y\) jika dan hanya jika \(x = |y|\text{.}\)
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(x + y\) ganjil.
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(xy\) positif.
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(x +2y\) positif.
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(xy\) negatif.
    🔗
    🔗
🔗
🔗

3.

Tentukan relasi mana yang bersifat transitif. Variabel \(x\text{,}\) \(y\text{,}\) \(x'\text{,}\) dan \(y'\) menyatakan bilangan bulat.
🔗
  • \(x \sim y\) jika dan hanya jika \(x + y\) positif.
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(x + y\) positif.
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(x + y\) genap.
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(x - y\) negatif.
    🔗
    🔗
  • \((x,y) \sim (x',y')\) jika dan hanya jika \(x+ y' = x' + y\text{.}\)
    🔗
    🔗
  • \(x \sim y\) jika dan hanya jika \(xy \geq 0\) .
    🔗
    🔗
🔗
🔗

4.

Definisikan relasi \(R_1,\ldots,R_6\) pada \({ 1,2,3,4 }\) sebagai berikut.
🔗
\(R_1=\lbrace (2,2),(2,3),(2,4),(3,2),(3,3),(3,4) \rbrace,\)
🔗
\(R_2 = \lbrace (1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\rbrace,\)
🔗
\(R_3 = \lbrace (2,4),(4,2) \rbrace\) ,
🔗
\(R_4 = \lbrace (1,2),(2,3),(3,4)\rbrace\text{,}\)
🔗
\(R_5 = \lbrace (1,1),(2,2),(3,3),(4,4)\rbrace,\)
🔗
\(R_6=\lbrace (1,3),(1,4),(2,3),(2,4),(3,1),(3,4) \rbrace,\)
🔗
Manakah di antara pernyataan berikut yang benar?
🔗
Pilih SEMUA jawaban yang benar di bawah ini.
🔗
🔗
🔗

5.

Diberikan relasi-relasi berikut pada himpunan semua orang. Pilih SEMUA jawaban yang benar dari daftar berikut:
🔗
(a) \(a\) lebih tua daripada \(b\)
🔗
🔗
(b) \(a\) dan \(b\) memiliki kakek atau nenek yang sama
🔗
🔗
(c) \(a\) memiliki nama depan yang sama dengan \(b\)
🔗
🔗
(d) \(a\) dan \(b\) lahir pada hari yang sama
🔗
🔗
🔗

6.

Diberikan relasi-relasi berikut pada himpunan semua bilangan bulat, dengan \((x,y) \in R\) jika dan hanya jika syarat yang tercantum dipenuhi. Pilih SEMUA jawaban yang benar dari daftar berikut:
🔗
(a) \(x+y = 0\)
🔗
🔗
(b) \(x - y\) merupakan bilangan bulat
🔗
🔗
(c) \(x=2y\)
🔗
🔗
(d) \(xy > 1\)
🔗
🔗
🔗
🔗

Latihan Latihan Tambahan

1.

Perhatikan relasi \(\gt\) pada himpunan \(\{1,2,\ldots,8\}\text{.}\)
🔗
(a)
Gambarlah graf berarah dari relasi \(\gt\text{.}\)
🔗
🔗
(b)
Gambarlah graf berarah untuk relasi invers \(\gt\inv\text{.}\)
🔗
🔗
(c)
Apakah relasi invers dari \(\gt\) sama dengan relasi \(\le\text{?}\) Jelaskan.
🔗
🔗
🔗

2.

Benar atau salah: untuk sembarang relasi \(R\) pada himpunan \(A\text{,}\) relasi \(R\inv\) bersifat simetris jika dan hanya jika \(R\) bersifat simetris. Berikan alasan untuk jawaban Anda.
🔗
🔗

3.

Benar atau salah: untuk sembarang relasi \(R\) pada himpunan \(A\text{,}\) komposisi \(R\) dengan inversnya, \(R\circ R\inv\text{,}\) selalu bersifat refleksif. Berikan alasan untuk jawaban Anda.
🔗
🔗

4.

Jika mungkin, temukan contoh relasi pada himpunan \(\{1,2,3,4\}\) yang bersifat refleksif dan simetris, tetapi tidak transitif. Jika relasi semacam itu ada, gambarlah multigraf berarah dari relasi tersebut dan tuliskan pasangan-pasangan terurut yang mendefinisikannya. Jelaskan jawaban Anda.
🔗
🔗

5.

Jika mungkin, temukan contoh relasi pada himpunan \(\{1,2,3,4\}\) yang bersifat refleksif dan transitif, tetapi tidak simetris. Jika relasi semacam itu ada, gambarlah multigraf berarah dari relasi tersebut dan tuliskan pasangan-pasangan terurut yang mendefinisikannya. Jelaskan jawaban Anda.
🔗
🔗

6.

Jika mungkin, temukan contoh relasi pada himpunan \(\{1,2,3,4\}\) yang bersifat simetris dan transitif, tetapi tidak refleksif. Jika relasi semacam itu ada, gambarlah multigraf berarah dari relasi tersebut dan tuliskan pasangan-pasangan terurut yang mendefinisikannya. Jelaskan jawaban Anda.
🔗
🔗

7.

Apa yang salah dalam argumen berikut, yang menyatakan bahwa setiap relasi yang simetris dan transitif pasti refleksif?
🔗
Misalkan \(R\) adalah relasi pada himpunan \(A\) yang bersifat simetris dan transitif. Karena \(R\) simetris, jika \(aRb\text{,}\) maka berlaku \(bRa\text{.}\) Karena \(R\) transitif, jika \(aRb\) dan \(bRa\text{,}\) maka berlaku \(aRa\text{.}\) Karena hal ini benar untuk semua unsur \(a\text{,}\) kita memperoleh bahwa \(aRa\) benar untuk semua \(a\) dalam \(A\text{,}\) sehingga \(R\) refleksif.
🔗
🔗
🔗

8.

Misalkan \(R\) adalah relasi ekuivalensi pada himpunan \(A = \{1,2,\ldots,6\}\text{.}\) Seperti apakah kemungkinan bentuk multigraf berarah untuk \(R\text{?}\) Berikan sedikitnya dua contoh berbeda dari relasi \(R\) semacam itu beserta grafnya untuk mengilustrasikan jawaban Anda.
🔗
🔗

9.

Perhatikan relasi \(R\) pada himpunan \(A = \{1,2,3,4,5\}\) yang didefinisikan oleh \(R = \{(1,2), (2,3), (3,4), (4,5), (5,1), (2,1), (3,1), (4,1), (5,1)\}\text{.}\) Apakah \(R\) merupakan relasi ekuivalensi? Berikan alasan untuk jawaban Anda.
🔗
Terlepas dari jawaban Anda, seperti apakah kelas-kelas relasi \([a]\) untuk \(a \in A\text{?}\) Dapatkah Anda menentukan apakah \(R\) merupakan relasi ekuivalensi berdasarkan informasi ini?
🔗
🔗

10.

Perhatikan relasi “penyendiri” pada suatu himpunan mahasiswa yang menggambarkan pertemanan dan berlaku hanya di antara setiap mahasiswa dan dirinya sendiri (yakni, tidak seorang pun berteman dengan orang lain selain dirinya sendiri). Apakah relasi ini merupakan relasi ekuivalensi? Berikan alasan untuk jawaban Anda. Jika relasi tersebut merupakan relasi ekuivalensi, seperti apakah kelas-kelas ekuivalensinya?
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik