Soal dan Pembahasan – Relasi dalam Matematika Diskrit

Berikut ini telah disediakan sejumlah soal dan pembahasan mengenai konsep relasi yang diperdalam pada matematika diskrit. Semoga dapat dijadikan acuan untuk menambah pemahaman dan pengalaman belajar terkait materi yang bersangkutan.

Terminologi dan definisi berikut barangkali dapat membantu dalam menyelesaikan masalah-masalah yang berkaitan dengan relasi.

Terminologi dan Definisi: Relasi

Relasi adalah aturan yang mengaitkan elemen satu himpunan ke elemen himpunan yang lain. Secara spesifik, relasi biner $R$ merupakan subhimpunan dari $A \times B,$ yaitu $R \subseteq A \times B.$ $R$ juga boleh berupa himpunan kosong, artinya tidak ada elemen yang dikaitkan sama sekali. 

Definisi: Relasi Refleksif dan Irefleksif

Suatu relasi $R$ pada himpunan $A$ dikatakan refleksif jika $(x, x) \in R$ untuk setiap $x \in A.$ Suatu relasi $R$ pada himpunan $A$ dikatakan irefleksif jika $(x, x) \notin R$ untuk setiap $x \in A.$ Perhatikan bahwa negasi (lawan) dari refleksif bukan irefleksif.

Definisi: Relasi Simetris dan Asimetris

Suatu relasi $R$ pada himpunan $A$ dikatakan simetris jika $(x, y) \in R$ mengimplikasikan $(y, x) \in R$ untuk suatu $x, y \in A.$ Sebaliknya, $R$ dikatakan asimetris (tidak simetris) jika terdapat $(x, y) \in R,$ tetapi $(y, x) \notin R$ untuk suatu $x, y \in A.$ Perhatikan bahwa negasi (lawan) dari simetris adalah asimetris.

Definisi: Relasi Antisimetris

Suatu relasi $R$ pada himpunan $A$ dikatakan antisimetris jika $(x, y) \in R$ dan $(y, x) \in R$ mengimplikasikan $x = y$ untuk suatu $x, y \in A.$ 

Definisi: Kelas Kesetaraan

Suatu relasi $R$ pada himpunan $A$ merupakan relasi kesetaraan (relasi ekuivalensi) jika $R$ refleksif, simetris, dan sekaligus transitif.

Definisi: Relasi Pengurutan Parsial

Suatu relasi $R$ pada himpunan $A$ merupakan relasi pengurutan parsial jika $R$ refleksif, antisimetris, dan sekaligus transitif.

Baca: Soal dan Pembahasan – Relasi dan Fungsi


Artikel ini ditulis berdasarkan beberapa sumber, termasuk sumber berbahasa Inggris. Salah satu sumber yang digunakan adalah buku “Discrete Mathematics and Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.

$$\begin{array}{ccc} \hline \text{No.} & \text{Bahasa Indonesia} & \text{Bahasa Inggris} \\ \hline 1. & \text{Refleksif} & \text{Reflexive} \\ 2. & \text{Simetris (Setangkup)} & \text{Symmetric} \\ 3. & \text{Antisimetris (Tolak-setangkup)} & \text{Antisymmetric} \\ 4. & \text{Transitif (Menghantar)} & \text{Transitive} \\ 5. & \text{Irefleksif}  & \text{Irreflexive} \\ 6. & \text{Asimetris} & \text{Asymmetric} \\ 7. & \text{Relasi Kesetaraan (Relasi Ekuivalensi)} & \text{Equivalence Relation} \\ 8. & \text{Klosur} & \text{Closure} \\ 9. & \text{Kelas Kesetaraan (Kelas Ekuivalensi)} & \text{Equivalence Class} \\ 10. & \text{Relasi Pengurutan Parsial} & \text{Partial Order Relation} \\ 11. & \text{Contoh Penyangkal} & \text{Counterexample} \\ \hline \end{array}$$


Quote by Nadiem Makarim

Semua orang bisa mencuri idemu, tetapi tidak semua orang bisa mengeksekusi ide itu sebaik dirimu.

Bagian Pilihan Ganda

Soal Nomor 1

Misalkan $P = \{2, 3, 5\}$ dan $Q = \{2, 4, 5, 6, 8, 10, 12\}.$ Jika didefinisikan relasi $R$ dari $P$ ke $Q$ dengan $(p, q) \in R$ jika $p$ habis membagi $q,$ maka banyak anggota $R$ adalah $\cdots \cdot$
A. $8$                      C. $10$                    E. $13$
B. $9$                      D. $12$

Pembahasan

Perhatikan bahwa kita perlu memilih $p \in P$ dan $q \in Q$ sehingga $p$ habis membagi $q.$ Diketahui:

  1. $2$ habis membagi $2, 4, 6, 8, 10,$ dan $12.$
  2. $3$ habis membagi $6$ dan $12.$
  3. $5$ habis membagi $5$ dan $10.$

Jadi, kita peroleh
$$\begin{aligned} R & = \{(2, 2), (2, 4), (2, 6), (2,8), (2, 10), \\ & (2, 12), (3, 6), (3, 12), (5, 5), (5, 10)\} \end{aligned}$$Dari sini, kita ketahui bahwa anggota $R$ ada sebanyak $\boxed{10}$
(Jawaban C)

[collapse]

Soal Nomor 2

Perhatikan tabel berikut.
$R$ adalah relasi yang menghubungkan nama siswa dan mata pelajaran yang disukainya sesuai dengan tabel di atas, yakni

$$\begin{aligned} R & = \{(\text{Jessica, Matematika}), (\text{Jessica, Fisika}), \\ & (\text{Wesley, Matematika}), (\text{Wesley, Kimia}), \\ & (\text{Vilsen, Kimia}), (\text{Mirabel, Seni Budaya})\} \end{aligned}$$Pernyataan berikut yang tidak tepat adalah $\cdots \cdot$
A. $\text{Jessica}~R~\text{Fisika}$
B. $\text{Vilsen}~\cancel{R}~\text{Seni Budaya}$
C. $\text{(Mirabel, Seni Budaya)}\in R$
D. $\text{(Wesley, Kimia)}\notin R$
E. $\text{(Vilsen, Matematika)}\notin R$

Pembahasan

Cek Opsi A:
Tepat bahwa $\text{Jessica}$ dihubungkan dengan $\text{Fisika}$ oleh relasi $R.$
Cek Opsi B:
Tepat bahwa $\text{Vilsen}$ tidak dihubungkan dengan $\text{Seni Budaya}$ oleh relasi $R.$
Cek Opsi C:
Tepat bahwa $\text{(Mirabel, Seni Budaya)}$ bukan anggota $R.$
Cek Opsi D:
Tidak tepat. Seharusnya $\text{(Wesley, Kimia)}$ adalah anggota $R.$
Cek Opsi E:
Tepat bahwa $\text{(Vilsen, Matematika)}$ bukan anggota $R.$
(Jawaban D)

[collapse]

Soal Nomor 3

Misalkan $R$ adalah relasi pada $A = \{3, 4, 6, 7, 9, 11\}$ yang didefinisikan oleh $(x, y) \in R$ jika $x$ adalah bilangan prima dan $y$ adalah bilangan komposit. Sesuai dengan definisi tersebut, banyak anggota $R$ adalah $\cdots \cdot$
A. $7$                    C. $9$                    E. $12$
B. $8$                    D. $11$

Pembahasan

Bilangan prima (bilangan yang hanya memiliki 2 faktor) mencakup: $3, 7,$ dan $11,$ sedangkan bilangan komposit (bilangan yang memiliki lebih dari 2 faktor) mencakup $4, 6,$ dan $9.$ Oleh karena itu, pasangan terurut $(x, y)$ yang memenuhi kondisi sebagai anggota $R$ adalah $(3, 4), (3, 6), (3, 9), (7, 4), (7, 6),$ $(7, 9), (11, 4), (11, 6),$ dan $(11, 9).$ Jadi, banyak anggota $R$ adalah $\boxed{9}$
(Jawaban C)

[collapse]

Soal Nomor 4

Pernyataan berikut yang tidak tepat mengenai relasi $R$ pada himpunan $A = \{1, 2, 3\}$ ke $B = \{2, 3, 4, 5\}$ adalah $\cdots \cdot$

  1. Relasi $R$ boleh saja tidak memiliki anggota, artinya relasi tersebut tidak memetakan semua anggota $A$ sama sekali terhadap anggota $B$
  2. Anggota relasi $R$ dalam bentuk pasangan berurut paling banyak ada $12$
  3. $(3, 1)$ adalah salah satu anggota relasi $R$ yang mungkin
  4. Relasi $R$ hanya boleh memasangkan tepat satu anggota $A$ ke tepat satu anggota $B$
  5. $(3, 3)$ tidak termasuk anggota relasi $R$ yang mungkin karena seharusnya relasi tidak boleh memasangkan anggota $A$ ke anggota $B$ yang nilainya sama (atau ke dirinya sendiri)

Pembahasan

Cek opsi A:
Tidak tepat. Relasi apa pun minimal memiliki 1 anggota pasangan berurut. Dengan kata lain, ada yang dipasangkan oleh relasi tersebut.
Cek opsi B:
Tepat. Perhatikan bahwa $|A| = 3$ dan $|B| = 4$ sehingga pasangan terurut yang menjadi anggota $R$ paling banyak ada $3 \times 4 = 12.$
Cek opsi C:
Tidak tepat. $(3, 1)$ artinya memasangkan $3$ ke $1,$ padahal $1$ bukan merupakan anggota $B.$
Cek opsi D:
Tidak tepat. Secara umum, relasi boleh memasangkan anggota apa pun di domain ke anggota apa pun di kodomain tanpa ada aturan/syarat tertentu.
Cek opsi E:
Tidak tepat. Secara umum, relasi boleh memasangkan anggota apa pun di domain ke anggota apa pun di kodomain tanpa ada aturan/syarat tertentu. Jadi, $(3, 3)$ juga dapat menjadi anggota relasi $R.$ 
(Jawaban B)

[collapse]

Baca: Soal dan Pembahasan – Himpunan (Tingkat SMP/Sederajat) 

Soal Nomor 5

Banyaknya relasi yang mungkin dari himpunan $A$ ke himpunan $B$ jika $A$ memiliki 4 anggota dan $B$ memiliki 3 anggota adalah $\cdots \cdot$
A. $16$                          D. $4.096$
B. $64$                           E. $16.384$
C. $1.024$

Pembahasan

Menurut definisi, relasi yang mungkin dari himpunan $A$ ke himpunan $B$ adalah himpunan bagian dari $A \times B$ (perkalian kartesian). Karena $|A| = 4$ dan $|B| = 3,$ maka $|A \times B| = 4 \times 3 = 12.$ Sekarang, kita tinggal mencari banyak himpunan bagian dari $A \times B.$
Banyaknya himpunan bagian dari himpunan yang beranggotakan $n$ elemen adalah $2^n.$ Dengan demikian, jika $|A \times B| = 12,$ maka banyak himpunan bagiannya adalah $2^{12} = 4.096.$ Jadi, ada sebanyak $\boxed{4.096}$ relasi yang mungkin terbentuk dari pemasangan dua himpunan tersebut.
Catatan: Secara umum, banyaknya relasi pada himpunan yang beranggotakan $n$ elemen adalah $2^{n^2}.$
(Jawaban D)

[collapse]

Soal Nomor 6

Diberikan dua himpunan $C = \{5, 10, 15, 20\}$ dan $D = \{5, 10\}.$ Diketahui relasi $R$ yang menghubungkan $C$ ke $D$ dengan $R = \{(5, 5), (5, 10), (10, 10)\}.$ Aturan relasi $R$ yang mungkin adalah $\cdots \cdot$

  1. $(c, d) \in R$ jika $c$ merupakan faktor dari $d$
  2. $(c, d) \in R$ jika $c$ merupakan kelipatan dari $d$
  3. $(c, d) \in R$ jika $c = 2d$
  4. $(c, d) \in R$ jika $d = 2c$
  5. $(c, d) \in R$ jika $c + d = 5k$ untuk $k \in \mathbb{Z}$

Pembahasan

Cek Opsi A:
Tepat. Dapat diperiksa bahwa $(5, 5), (5, 10),$ dan $(10, 10)$ adalah tiga anggota $R$ yang memenuhi kondisi ini.
Cek Opsi B:
Tidak tepat karena ditemukan sangkalan, yaitu $5$ bukan kelipatan dari $10.$
Cek Opsi C:
Tidak tepat karena ditemukan sangkalan, yaitu untuk $(5, 10),$ tidak berlaku $5 = 2(10).$
Cek Opsi D:
Tidak tepat karena ditemukan sangkalan, yaitu untuk $(5, 5),$ tidak berlaku $5 = 2(5).$
Cek Opsi E:
Tidak tepat karena jika demikian aturannya, maka seharusnya anggota $R$ lebih banyak dari itu, salah satunya adalah $(5, 15).$
(Jawaban A)

[collapse]

Soal Nomor 7

Misalkan terdapat relasi $R$ yang menghubungkan himpunan $A = \{1, 2, 3, 4, 5\}$ ke himpunan $B = \{2, 3, 5, 7\}$ dengan $R = \{(1, 2), (2, 3), (2, 7), (3, 5), (5, 7)\}.$ Representasi relasi $R$ dengan menggunakan matriks yang barisnya mewakili anggota domain, sedangkan kolomnya mewakili anggota kodomain (sesuai urutan bilangan), adalah $\cdots \cdot$
A. $\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$

B. $\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$

C. $\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$

D. $\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$

E. $\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$

Pembahasan

Perhatikan bahwa $R$ menghubungkan $A$ ke $B$ sehingga $A$ merupakan domain, sedangkan $B$ merupakan kodomain. Karena $|A| = 5$ dan $|B| = 4,$ maka matriks yang dibuat berordo $5 \times 4$ (5 baris dan 4 kolom). Posisikan anggota-anggota domain dan kodomain di luar matriks tersebut seperti di bawah. Karena $(1, 2) \in R,$ maka tuliskan entri $1$ di posisi yang bersesuaian. Begitu juga dengan $(2, 3), (2, 7), (3, 5),$ dan $(5, 7). $
Sisanya yang lain diberi entri $0.$
Jadi, matriks yang merepresentasikan relasi $R$ tersebut adalah $\boxed{\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}}$
(Jawaban A)

[collapse]

Baca: Soal dan Pembahasan – Matriks, Determinan, dan Invers Matriks 

Soal Nomor 8

Perhatikan beberapa pernyataan berikut.

  1. $A$ memiliki anak bernama $Z.$
  2. $B$ adalah ayah dari $Y.$
  3. $X$ memiliki seorang ibu yang bernama $C.$
  4. $D$ dan $E$ adalah orang tua dari $V.$
  5. $F$ adalah anak dari $U.$

Jika $R$ adalah relasi “orang tua dari”, maka anggota $R^{-1}$ yang sesuai berdasarkan pernyataan di atas jika dituliskan dalam notasi himpunan adalah $\cdots \cdot$

  1. $\{(Z, A), (Y, B), (X, C), (V, D),$ $(V, E), (F, U)\}$
  2. $\{(A, Z), (B, Y), (C, X), (D, V),$ $(E, V), (U, F)\}$
  3. $\{(Z, A), (Y, B), (C, X), (V, D),$ $(V, E), (U, F)\}$
  4. $\{(Z, A), (Y, B), (X, C), (D, V),$ $(E, V), (F, U)\}$
  5. $\{(V, D), (V, E)\}$

Pembahasan

Karena $R$ menyatakan relasi “orang tua dari”, $R^{-1}$ sebaliknya, yaitu relasi “anak dari”. Jadi, jika $x$ adalah anak dari $y,$ maka $(x, y) \in R^{-1}.$

  1. Pernyataan 1: $Z$ adalah anak dari $A$ sehingga ditulis $(Z, A).$
  2. Pernyataan 2: $Y$ adalah anak dari $B$ sehingga ditulis $(Y, B).$
  3. Pernyataan 3: $X$ adalah anak dari $C$ sehingga ditulis $(X, C).$
  4. Pernyataan 4: $V$ adalah anak dari $D$ dan $V$ juga adalah anak dari $E$ sehingga ditulis $(V, D)$ dan $(V, E).$
  5. Pernyataan 5: $F$ adalah anak dari $U$ sehingga ditulis $(F, U).$

Dengan demikian, $$\boxed{R^{-1} = \{(Z, A), (Y, B), (X, C), (V, D), (V, E), (F, U)\}}$$(Jawaban A)

[collapse]

Soal Nomor 9

Diketahui dua himpunan $X = \{2, 4, 6, 8, 10\}$ dan $Y = \{1, 4, 10, 12\}.$ Jika didefinisikan relasi $R$ dari $X$ ke $Y$ dengan $(x, y) \in R$ dengan syarat $x > y,$ maka invers dari relasi $R$, yakni $R^{-1},$ beranggotakan pasangan terurut berikut, kecuali $\cdots \cdot$
A. $(1, 2)$                      D. $(10, 4)$
B. $(1, 6)$                      E. $(1, 10)$
C. $(4, 6)$

Pembahasan

Sesuai dengan definisi relasi $R$ yang diberikan, kita peroleh bahwa $R = \{(2, 1), (4, 1), (6, 1),$ $(6, 4), (8, 1), (8, 4),$ $(10, 1), (10, 4)\}.$
Dari sini, kita dapatkan anggota $R^{-1}$ dengan menukar posisi pasangan terurut masing-masing, yaitu $R^{-1} = \{(1, 2), (1, 4), (1, 6),$ $(4, 6), (1, 8), (4, 8),$ $(1, 10), \color{red}{(4, 10)}\}.$
Jadi, pasangan terurut yang bukan merupakan anggota $R^{-1}$ berdasarkan opsi jawaban yang diberikan adalah $\boxed{(10, 4)},$ yang seharusnya $(4, 10).$
(Jawaban D)

[collapse]

Baca: Soal dan Pembahasan – Himpunan (Soal Cerita) Tingkat Lanjut 

Soal Nomor 10

Misalkan $A = \{1, 3, 5\}$ dan $B = \{2, 4, 6, 8\}.$ Relasi $R_1 = \{(1, 2), (3, 4), (5, 8)\}$ dan relasi $R_2 = \{(3, 2), (3, 4), (3, 8), (5, 6), (5, 8)\}$ adalah relasi dari $A$ ke $B.$ Pernyataan yang salah terkait operasi dari kedua relasi tersebut adalah $\cdots \cdot$

  1. $R_1 \cap R_2 = \{(3, 4), (5, 8)\}$
  2. $R_1 \cup R_2 = \{(1, 2), (3, 2), (3, 4),$ $(3, 8), (5, 6), (5, 8)\}$
  3. $R_1-R_2 = \{(1,2)\}$
  4. $R_2-R_1 = \{(3, 2), (3, 8), (5, 6)\}$
  5. $R_1 \oplus R_2 = \{(1, 2), (3, 2)\}$

Pembahasan

Cek opsi A:
$R_1 \cap R_2$ menyatakan relasi yang setiap anggotanya adalah anggota $R_1$ sekaligus $R_2.$ Karena $(3, 4), (5, 8) \in R_1, R_2,$ maka benar bahwa $R_1 \cap R_2 = \{(3, 4), (5, 8)\}.$
Cek opsi B:
$R_1 \cup R_2$ menyatakan relasi yang setiap anggotanya adalah anggota $R_1$ atau $R_2.$ Ambil setiap anggota yang ada pada $R_1$ atau $R_2$ sehingga dapat diketahui bahwa benar $R_1 \cup R_2 = \{(1, 2), (3, 2), (3, 4), (3, 8),$ $(5, 6), (5, 8)\}.$
Cek opsi C:
$R_1-R_2$ menyatakan relasi yang anggotanya dari $R_1,$ tetapi bukan anggota $R_2.$ Tampak bahwa $(1, 2) \in R_1,$ tetapi $(1, 2) \notin R_2.$ Jadi, benar bahwa $R_1-R_2 = \{(1,2)\}.$
Cek opsi D:
$R_2-R_1$ menyatakan relasi yang anggotanya dari $R_2,$ tetapi bukan anggota $R_1.$ Tampak bahwa $(3, 2), (3, 8), (5, 6) \in R_2,$ tetapi $(3, 2), (3, 8), (5, 6) \notin R_1.$ Jadi, benar bahwa $R_2-R_1 = \{(3, 2), (3, 8), (5, 6)\}.$
Cek opsi E:
$R_1 \oplus R_2$ (operasi beda simetris) menyatakan himpunan yang anggotanya pada $R_1$ atau $R_2,$ tetapi tidak pada keduanya. Di sini diketahui bahwa $(3, 4), (5, 8) \in R_1, R_2$ sehingga anggota $R_1 \oplus R_2$ adalah $(1, 2), (3, 2), (3, 8),$ dan $(5, 6).$
Jadi, pernyataan pada opsi E tidak tepat. Seharusnya, ada pasangan terurut lain yang menjadi anggota $R_1 \oplus R_2.$
(Jawaban E)

[collapse]

Soal Nomor 11

Misalkan $R$ adalah relasi $\{(1, 2), (1, 3), (2, 3), (2, 4), (3, 1)\}$ dan $S$ adalah relasi $\{(2, 1), (3, 1), (3, 2), (4, 2), (4, 3)\}.$ Dengan demikian, $S \circ R = \cdots \cdot$

  1. $S \circ R = \{(1, 1), (1, 2), (2, 1), (2, 2),$ $(3, 2)\}$
  2. $S \circ R = \{(1, 2), (2, 1), (2, 3), (3, 2)\}$
  3. $S \circ R = \{(1, 1), (1, 2), (2, 1), (2, 2),$ $(2, 3)\}$
  4. $S \circ R = \{(1, 1), (2, 1), (2, 3), (3, 4)\}$
  5. $S \circ R = \{(1, 1), (2, 2), (3, 3), (4, 4)\}$

Pembahasan

$S \circ R$ menyatakan komposisi relasi $R$ dan $S.$ Komposisi kedua relasi tersebut dapat diperagakan dengan menggunakan diagram panah seperti berikut.
Perhatikan panah-panah yang menghubungkan bagan himpunan paling kiri dan paling kanan. Keterhubungan panah pada diagram di atas menunjukkan bahwa $$\boxed{S \circ R = \{(1, 1), (1, 2), (2, 1), (2, 2), (2, 3)\}}$$(Jawaban C)

[collapse]

Soal Nomor 12

Misalkan relasi $R_1$ dan $R_2$ pada himpunan $A$ berturut-turut dinyatakan oleh matriks $M_{R_1} = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}$ dan $M_{R_2} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix}.$ Matriks yang menyatakan $R_2 \circ R_1$ adalah $\cdots \cdot$
A. $M_{R_2~\circ~R_1} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix}$
B. $M_{R_2~\circ~R_1} = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \end{pmatrix}$
C. $M_{R_2~\circ~R_1} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}$
D. $M_{R_2~\circ~R_1} = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}$
E. $M_{R_2~\circ~R_1} = \begin{pmatrix} 0 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix}$

Pembahasan

Matriks yang menyatakan $R_2 \circ R_1$ adalah $M_{R_2~\circ~R_1} = M_{R_1} \cdot M_{R_2}.$ Operator $\cdot$ sama seperti operator perkalian matriks seperti biasanya, tetapi dengan mengganti tanda kali dengan $\land$ dan tanda tambah dengan $\lor.$
$$\begin{aligned} M_{R_2~\circ~R_1} & = M_{R_1} \cdot M_{R_2} \\ & = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix} \\ & = \begin{pmatrix} (1 \land 1) \lor (0 \land 1) \lor (1 \land 1) & (1 \land 1) \lor (0 \land 0) \lor (1 \land 0) & (1 \land 1) \lor (0 \land 1) \lor (1 \land 1) \\ (1 \land 1) \lor (1 \land 0) \lor (0 \land 1) & (1 \land 1) \lor (1 \land 0) \lor (0 \land 0) & (1 \land 1) \lor (1 \land 1) \lor (0 \land 1) \\ (0 \land 1) \lor (0 \land 1) \lor (0 \land 1) & (0 \land 1) \lor (0 \land 0) \lor (0 \land 0) & (0 \land 1) \lor (0 \land 1) \lor (0 \land 1) \end{pmatrix} \\ & = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix} \end{aligned}$$Jadi, matriks yang menyatakan $R_2 \circ R_1$ adalah $\boxed{M_{R_2~\circ~R_1} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix}}$
(Jawaban A)

[collapse]

Soal Nomor 13

Dari relasi di bawah ini, manakah relasi yang refleksif pada himpunan bilangan bulat positif $\mathbb{N}$?
A. $R: x~\text{lebih kecil dari}~y$
B. $S: x + y = 7$
C. $T: 2x + y = 10$
D. $U: x -y = 0$
E. $V: x~\text{faktor prima dari}~y$

Pembahasan

Relasi $R$ pada himpunan $A$ disebut refleksif jika $(a, a) \in R$ untuk setiap $a \in A.$ Dengan kata lain, setiap anggota domain (daerah asal) akan dipetakan/dipasangkan ke dirinya sendiri oleh relasi $R$ yang memiliki sifat tersebut.
Cek opsi A:
$R: x~\text{lebih kecil dari}~y$ tidak refleksif karena terdapat $x \in \mathbb{N}$ yang mengakibatkan $(x, x) \notin R,$ misalnya $(3, 3).$ Jelas bahwa $3$ tidak lebih kecil dari dirinya sendiri.
Cek opsi B:
$S: x + y = 7$ tidak refleksif karena terdapat $x \in \mathbb{N}$ yang mengakibatkan $(x, x) \notin R,$ misalnya $(3, 3).$ Jelas bahwa $3 + 3 \neq 7.$
Cek opsi C:
$T: 2x + y = 10$ tidak refleksif karena terdapat $x \in \mathbb{N}$ yang mengakibatkan $(x, x) \notin R,$ misalnya $(3, 3).$ Jelas bahwa $2(3) + 3 \neq 10.$
Cek opsi D:
$U: x -y = 0$ (ekuivalen dengan $U: x = y$) refleksif karena semua $x \in \mathbb{N}$ memenuhi $(x, x) \in R.$ Dengan kata lain, relasi $U$ dengan syarat $x = y$ memasangkan suatu bilangan bulat positif terhadap dirinya sendiri.
Cek opsi E:
$V: x~\text{faktor prima dari}~y$ tidak refleksif karena terdapat $x \in \mathbb{N}$ yang mengakibatkan $(x, x) \notin R,$ misalnya $(4, 4).$ Jelas bahwa $4$ bukan faktor prima dari $4.$
(Jawaban D)

[collapse]

Baca: Soal dan Pembahasan – Himpunan (Soal Non-cerita) 

Soal Nomor 14

Relasi berikut yang bersifat simetris adalah $\cdots \cdot$
A. relasi “ibu dari”
B. relasi “menyukai”
C. relasi “habis dibagi oleh”
D. relasi “faktor prima dari”
E. relasi “saudara dari”

Pembahasan

Relasi yang bersifat simetris mencirikan pasangan berurutnya tetap menjadi anggota relasi meskipun posisinya dibalik. Secara matematis, jika terdapat relasi $R$ dengan $(x, y) \in R,$ maka $(y, x) \in R.$
Cek opsi A:
Relasi “ibu dari” tidak bersifat simetris. Jika A adalah ibu dari B, maka jelas B bukanlah ibu dari A.
Cek opsi B:
Relasi “menyukai” juga tidak bersifat simetris. Jika A menyukai B, belum tentu B menyukai A.
Cek opsi C:
Relasi “habis dibagi oleh” juga tidak bersifat simetris. Sebagai contoh, 4 habis dibagi oleh 8, tetapi 8 tidak habis dibagi oleh 4.
Cek opsi D:
Relasi “faktor prima dari” juga tidak bersifat simetris. Sebagai contoh, 5 faktor prima dari 10, tetapi 10 bukan faktor prima dari 5.
Cek opsi E:
Relasi “saudara dari” bersifat simetris. Jika A adalah saudara dari B, maka jelas bahwa B juga adalah saudara dari A.
(Jawaban E)

[collapse]

Soal Nomor 15

Perhatikan diagram panah yang merepresentasikan relasi $R$ yang didefinisikan pada himpunan $\{1, 2, 3, 4, 5\}$ berikut.
Pernyataan berikut yang tepat terkait relasi di atas adalah $\cdots \cdot$

  1. Relasi $R$ bersifat refleksif
  2. Relasi $R$ bersifat simetris
  3. Relasi $R$ bersifat antisimetris
  4. Relasi $R$ bersifat transitif
  5. Setiap anggota domain dipasangkan terhadap dua anggota kodomain oleh $R$

Pembahasan

Cek opsi A:
Relasi $R$ seharusnya tidak refleksif karena terdapat anggota domain yang tidak dipasangkan ke dirinya sendiri. Dengan kata lain, $R$ tidak refleksif karena $(1, 1), (2, 2), (3, 3), (4, 4) \notin R.$
Cek opsi B:
Relasi $R$ simetris. Dapat diperhatikan bahwa untuk setiap $(x, y) \in R,$ maka $(y, x) \in R.$
Cek opsi C:
Relasi $R$ seharusnya tidak antisimetris karena terdapat $(x, y) \in R$ sedemikian sehingga $(y, x) \in R$ untuk $x \neq y$, misalnya $(1, 2) \in R$ dan $(2, 1) \in R,$ padahal $1 \neq 2.$
Cek opsi D:
Relasi $R$ seharusnya tidak transitif karena ada beberapa 3 pasangan berurut yang melanggar syarat sifat tersebut. Sebagai contoh, $(1, 2), (2, 1) \in R,$ tetapi $(1, 1) \notin R.$ 
Cek opsi E:
Ada satu anggota domain yang tidak dipasangkan terhadap dua anggota kodomain oleh $R,$ yaitu $1$ (hanya dipasangkan ke $2$). Jadi, pernyataan pada opsi E tidak tepat.
(Jawaban B)

[collapse]

Baca Juga: Materi, Soal, dan Pembahasan – Himpunan Ganda

Bagian Uraian

Soal Nomor 1

Tuliskan anggota dari relasi $R$ pada $\{1, 2, 3, 4\}$ yang didefinisikan oleh $(x, y) \in R$ jika $x^2 \ge y.$

Pembahasan

Adapun pasangan terurut $(x, y)$ yang memenuhi kondisi $x^2 \ge y$ dengan $x, y \in \{1, 2, 3, 4\}$ adalah sebagai berikut.
$$\begin{array}{|c|c|} \hline x & x^2 & y & (x, y) \\ \hline 1 & 1 & 1 & (1, 1) \\ 2 & 4 & 1 & (2, 1)  \\ 2 & 4 & 2 & (2, 2) \\ 2 & 4 & 3 & (2, 3) \\ 2 & 4 & 4 & (2, 4) \\ 3 & 9 & 1  & (3, 1) \\ 3 & 9 & 2 & (3, 2) \\ 3 & 9 & 3 & (3, 3) \\ 3 & 9 & 4 & (3, 4) \\ 4 & 16 & 1  & (4, 1) \\ 4 & 16 & 2 & (4, 2) \\ 4 & 16 & 3 & (4, 3) \\ 4 & 16 & 4 & (4, 4) \\ \hline \end{array}$$Jadi, banyak anggota dari relasi $R$ adalah $\boxed{13}$

[collapse]

Soal Nomor 2

Nyatakan relasi $R = \{(1, 2), (2, 1), (3, 3), (1, 1), (2, 3)\}$ pada $A = \{1, 2, 3\}$ dalam bentuk tabel, matriks, dan graf berarah.

Pembahasan

Perhatikan bahwa relasi $R$ didefinisikan hanya pada sebuah himpunan, yaitu dari $A$ ke $A.$
Representasi relasi $R$ dalam bentuk tabel adalah sebagai berikut.
$$\begin{array}{|c|c|} \hline A & A \\ \hline 1 & 2 \\ 2 & 1 \\ 3 & 3 \\ 1 & 1 \\ 2 & 3 \\ \hline \end{array}$$Representasi relasi $R$ dalam bentuk matriks adalah sebagai berikut.
Representasi relasi $R$ dalam bentuk graf berarah adalah sebagai berikut.

[collapse]

Baca: Soal dan Pembahasan – Matriks, Determinan, dan Invers Matriks Versi HOTS dan Olimpiade

Soal Nomor 3

Misalkan $R = \{(1, 2), (2, 3), (3, 4)\}$ dan $S = \{(1, 1), (1, 2), (2, 1), (2, 2),$ $(2, 3), (3, 1), (3, 2), (3, 4)\}$ adalah relasi dari $\{1, 2, 3\}$ ke $\{1, 2, 3, 4\}.$ Tentukan:
a. $R \cup S$
b. $R \cap S$
c. $R-S$
d. $S-R$
e. $R \oplus S$

Pembahasan

Cek opsi A:
$R \cup S$ menyatakan relasi yang setiap anggotanya adalah anggota $R$ atau $S.$ Ambil setiap anggota yang ada pada $R$ atau $S$ sehingga dapat diketahui bahwa benar $R \cup S = \{(1, 1), (1, 2), (2, 1), (2, 2),$ $(2, 3), (3, 1), (3, 2), (3, 4)\}.$
Cek opsi B:

$R_1 \cap R_2$ menyatakan relasi yang setiap anggotanya adalah anggota $R_1$ sekaligus $R_2.$ Karena $(1, 2), (2, 3), (3, 4) \in R, S,$ maka $R \cap S = \{(1, 2), (2, 3), (3, 4)\}.$
Cek opsi C:
$R-S$ menyatakan relasi yang anggotanya dari $R,$ tetapi bukan anggota $S.$ Tampak bahwa tidak ada anggota $R$ yang demikian. Setiap anggota $R$ ternyata juga merupakan anggota $S.$ Oleh karena itu, $R-S = \{ \}$ atau $R-S = \emptyset.$
Cek opsi D:
$S-R$ menyatakan relasi yang anggotanya dari $S,$ tetapi bukan anggota $R.$ Tampak bahwa $(1, 1), (2, 1), (2, 2), (3, 1), (3, 2) \in S,$ tetapi kelimanya bukan anggota $R.$ Jadi, $S-R = \{(1, 1), (2, 1), (2, 2),$ $(3, 1), (3, 2)\}.$
Cek opsi E:
$R \oplus S$ (operasi beda simetris) menyatakan himpunan yang anggotanya pada $R$ atau $S,$ tetapi tidak pada keduanya. Sudah diketahui bahwa $R \cap S = \{(1, 2), (2, 3), (3, 4)\}$ sehingga $R \oplus S = \{(1, 1), (2, 1),$ $(2, 2), (3, 1), (3, 2)\}.$  

[collapse]

Soal Nomor 4

Misalkan matriks yang menyatakan relasi $R_1$ dan $R_2$ pada himpunan $A$ berturut-turut dinyatakan oleh matriks $M_{R1} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ dan $M_{R2} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}.$ Tentukan:

  1. matriks yang menyatakan relasi $R_1 \cup R_2;$
  2. matriks yang menyatakan relasi $R_1 \cap R_2.$

Pembahasan

Jika relasi $R_1$ dan $R_2$ berturut-turut dinyatakan oleh matriks $M_{R1}$ dan $M_{R2},$ maka matriks yang menyatakan gabungan dan irisan dari kedua relasi tersebut adalah 
$$\begin{aligned} M_{R1 \cup R2} & = M_{R1} \lor M_{R2} \\ M_{R1 \cap R2} & = M_{R1} \land M_{R2} \end{aligned}$$yang dalam hal ini, operator $\lor$ berarti “atau” dan operator $\land$ berarti “dan”.
Jawaban a)
Pada $M_{R1} \lor M_{R2},$ kita menggunakan operasi $\lor$ pada setiap entri yang bersesuaian. Hasil operasi bernilai $1$ jika minimal salah satu operan bernilai $1.$ Selain itu, nilainya $0.$
$$\begin{aligned} M_{R1 \cup R2} & = M_{R1} \lor M_{R2} \\ & = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \lor \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix} \\ & = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}  \end{aligned}$$Jadi, matriks yang menyatakan relasi $R_1 \cup R_2$ adalah $\boxed{\begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}}$
Jawaban b)
Pada $M_{R1} \land M_{R2},$ kita menggunakan operasi $\land$ pada setiap entri yang bersesuaian. Hasil operasi bernilai $1$ jika kedua operan bernilai $1.$ Selain itu, nilainya $0.$
$$\begin{aligned} M_{R1 \cap R2} & = M_{R1} \land M_{R2} \\ & = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \lor \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix} \\ & = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix} \end{aligned}$$Jadi, matriks yang menyatakan relasi $R_1 \cap R_2$ adalah $\boxed{\begin{pmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}}$

[collapse]

Soal Nomor 5

Misalkan $R$ adalah relasi pada himpunan laki-laki yang terdiri dari pasangan $(a, b)$ yang dalam hal ini $a$ adalah ayah dari $b.$ Misalkan $S$ adalah relasi pada himpunan laki-laki yang terdiri dari pasangan $(a, b)$ yang dalam hal ini $a$ dan $b$ adalah saudara kandung. Nyatakan $R \circ S$ dan $S \circ R.$

Pembahasan

Jawaban a)
Dengan menyesuaikan notasi yang dipakai, kita misalkan $(a, b) \in S$ dan $(b, c) \in R.$ Karena $a$ dan $b$ saudara kandung, sedangkan $b$ adalah ayah dari $c,$ maka $a$ adalah paman dari $c.$ Oleh karena itu, komposisi relasi $R \circ S$ dinyatakan oleh
$$R \circ S = \{(a, c) \mid a~\text{paman dari}~c,~\text{untuk beberapa}~b, (a, b) \in S, (b, c) \in R\}$$Jawaban b)
Dengan menyesuaikan notasi yang dipakai, kita misalkan $(a, b) \in R$ dan $(b, c) \in S.$ Karena $a$ adalah ayah dari $b,$ sedangkan $b$ dan $c$ adalah saudara kandung, maka $a$ adalah ayah dari $c$ juga. Oleh karena itu, komposisi relasi $S \circ R$ dinyatakan oleh
$$S \circ R = \{(a, c) \mid a~\text{ayah dari}~c,~\text{untuk beberapa}~b, (a, b) \in R, (b, c) \in S\}$$

[collapse]

Soal Nomor 6

Misalkan $A = \{1, 2, 3, 4\}.$ Diketahui $R = \{(1, 1), (2, 3), (4, 4), (2, 1)\}$ adalah relasi pada himpunan $A.$

  1. Dari keempat sifat ini: refleksif, simetris, antisimetris, dan transitif, manakah sifat yang dimiliki oleh relasi $R$? Jelaskan alasannya.
  2. Nyatakan hasil operasi $R^2$ sebagai himpunan pasangan berurut.

Pembahasan

Jawaban a)

  1. Relasi $R$ tidak refleksif karena tidak memuat pasangan berurut $(1, 1)$ dan $(3, 3).$
  2. Relasi $R$ tidak simetris. Salah satu alasannya adalah $(2, 3) \in R,$ tetapi $(3, 2) \notin R.$
  3. Relasi $R$ antisimetris karena semua pasangan $(x, y) \in R$ memenuhi $(y, x) \notin R$ untuk $x \neq y.$
  4. Relasi $R$ transitif karena $(\color{red}{2}, 1) \in R$ dan $(1, \color{red}{1}) \in R,$ berakibat $(2, 1) \in R.$

Jawaban b)
Operasi komposisi $R^2 = R \circ R$ akan lebih mudah ditentukan hasilnya jika menggunakan bantuan diagram panah seperti di bawah.

Berdasarkan diagram di atas, tampak bahwa $\boxed{R^2 = \{(1, 1), (2, 1), (4, 4)\}}$

[collapse]

Soal Nomor 7

Sebuah relasi $R$ yang didefinisikan pada sebuah himpunan yang beranggotakan $4$ elemen disajikan dalam matriks $M_R$ berikut.
$$M_R = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix}$$Tentukan apakah relasi tersebut refleksif/tidak, simetris/tidak, antisimetris/tidak, dan transitif/tidak.

Pembahasan

Perhatikan sketsa berikut.

  1. $R$ tidak refleksif karena tidak semua entri/elemen diagonal utama matriks $M$ bernilai $1.$
  2. $R$ simetris (setangkup). Hal ini dapat dilihat dari matriks yang simetris dari segi entri pada bagian atas dan bawah diagonal utama (yang diberi garis merah).
  3. $R$ tidak antisimetris (tidak tolak-setangkup) karena terdapat pasangan entri matriks yang tidak memenuhi syarat. Salah satunya adalah $m_{12} = m_{21} = 1.$ Seharusnya salah satunya harus bernilai $0$ untuk memenuhi syarat antisimetris.
  4. $R$ tidak transitif (tidak menghantar) karena terdapat pasangan tiga entri matriks yang tidak memenuhi syarat. Salah satunya adalah $m_{23} = m_{32} = 1,$ tetapi $m_{22} \neq 1.$

[collapse]

Soal Nomor 8

Sebuah relasi $R$ yang didefinisikan pada sebuah himpunan yang beranggotakan $4$ elemen disajikan dalam matriks $M_R$ berikut.
$$M_R = \begin{pmatrix} a & 1 & 0 & 1 \\ b & c & 1 & 1 \\ d & e & f & 0 \\ g & h & i & j \end{pmatrix}$$Tentukan nilai $a, b, c, d, e, f, g, h, i,$ dan $j$ agar relasi tersebut bersifat:
a. refleksif,
b. simetris,
c. antisimetris.

Pembahasan

Jawaban a)
Matriks yang merepresentasikan relasi yang refleksif memiliki diagonal yang semua entrinya bernilai $1.$ Jadi, agar relasi $R$ bersifat refleksif, nilai $a = c = f = j = 1,$ sedangkan nilai variabel lainnya bebas ($0$ atau $1$).
Jawaban b)
Matriks yang merepresentasikan relasi yang simetris adalah matriks simetris, yaitu matriks yang entri-entrinya simetris secara diagonal atau juga bisa diartikan sebagai matriks yang transposnya sama dengan dirinya sendiri. Jadi, agar relasi $R$ bersifat simetris, nilai $b = e = g = h = 1$ dan $d = i = 0,$ sedangkan variabel yang letaknya di diagonal utama, yaitu $a, c, f, j,$ bernilai bebas ($0$ atau $1$).
Jawaban c)
Matriks yang merepresentasikan relasi yang antisimetris memiliki sifat, yaitu jika $m_{ij} = 1$ dengan $i \neq j$ (entrinya tidak terletak di diagonal utama), maka $m_{ji} = 0.$ Dengan kata lain, matriks pada relasi antisimetris adalah matriks yang memenuhi $m_{ij} = 0$ atau $m_{ji} = 0$ (salah satu atau kedua kondisi ini terpenuhi) untuk $i \neq j.$
Perhatikan bahwa pada matriks $M_R$ di atas:

  1. $m_{12} = 1$ sehingga $m_{21} = b = 0.$
  2. $m_{13} = 0$ sehingga $m_{31} = d = 0~\text{atau}~1.$
  3. $m_{14} = 1$ sehingga $m_{41} = g = 0.$
  4. $m_{23} = 1$ sehingga $m_{32} = e = 0.$
  5. $m_{24} = 1$ sehingga $m_{42} = h = 0.$
  6. $m_{34} = 0$ sehingga $m_{43} = i = 0~\text{atau}~1.$

Untuk variabel di diagonal utama, yaitu $a, c, f, j,$ bernilai bebas ($0$ atau $1$).

[collapse]

Soal Nomor 9

Diketahui dua relasi, $R$ dan $S,$ yang masing-masing didefinisikan pada himpunan $\{a, b, c, d\}.$ Masing-masing relasi direpresentasikan oleh graf berarah berikut.
Tentukan apakah $R$ dan $S$ refleksif, simetris, antisimetris, dan transitif. Jelaskan alasannya.

Pembahasan

Perhatikan graf berarah yang merepresentasikan relasi $R$ (kiri).

  1. $R$ tidak refleksif karena simpul $a, c,$ dan $d$ tidak memiliki gelang (loop). 
  2. $R$ tidak simetris karena dari simpul $b$ ke $a$ ada sisi berarah, sedangkan dari $a$ ke $b$ tidak ada. Begitu juga dari $b$ ke $c,$ dari $c$ ke $d,$ dan dari $d$ ke $a.$
  3. $R$ tidak antisimetris karena dari simpul $d$ ke $b$ ada sisi berarah, dan dari simpul $b$ ke $d$ juga ada, padahal $b \neq d.$
  4. $R$ tidak transitif karena ada pasangan tiga unsur yang tidak memenuhi kriteria transitif. Salah satunya adalah ada sisi dari $b$ ke $d$ dan dari $d$ ke $c,$ tetapi tidak ada sisi dari $b$ ke $c.$

Perhatikan graf berarah yang merepresentasikan relasi $S$ (kanan).

  1. $S$ tidak refleksif karena simpul $a$ dan $d$ tidak memiliki gelang (loop). 
  2. $S$ tidak simetris karena dari simpul $b$ ke $a$ ada sisi berarah, sedangkan dari $a$ ke $b$ tidak ada. Begitu juga dari $b$ ke $c$ dan dari $c$ ke $d.$
  3. $S$ tidak antisimetris karena dari simpul $d$ ke $a$ ada sisi berarah, dan dari simpul $a$ ke $d$ juga ada, padahal $a \neq d.$
  4. $S$ tidak transitif karena ada pasangan tiga unsur yang tidak memenuhi kriteria transitif. Salah satunya adalah ada sisi dari $b$ ke $a$ dan dari $a$ ke $c,$ tetapi tidak ada sisi dari $b$ ke $c.$
    [collapse]

Soal Nomor 10

Misalkan $R$ adalah relasi pada himpunan URL (Uniform Resource Locator) atau alamat situs sedemikian sehingga $x~R~y$ jika dan hanya jika alamat situs pada $x$ sama dengan alamat situs pada $y.$ Tunjukkan bahwa $R$ adalah relasi kesetaraan.

Pembahasan

Relasi kesetaraan (equivalence relation) adalah relasi yang bersifat refleksif, simetris, dan transitif secara sekaligus. Ini artinya, kita harus menunjukkan bahwa $R$ memiliki ketiga sifat tersebut agar dapat digolongkan sebagai relasi kesetaraan.

  1. $R$ refleksif karena jelas bahwa setiap alamat situs sama dengan dirinya sendiri atau secara matematis disimbolkan sebagai $(x, x) \in R.$
  2. $R$ simetris karena jika alamat situs pada $x$ sama dengan alamat situs pada $y,$ maka alamat situs pada $y$ juga pasti sama dengan alamat situs pada $x.$ Secara matematis disimbolkan sebagai $(x, y) \in R \Rightarrow (y, x) \in R.$
  3. $R$ transitif karena jika alamat situs pada $x$ sama dengan alamat situs pada $y$ dan alamat situs pada $y$ sama dengan alamat situs pada $z,$ maka alamat situs pada $x$ sama dengan alamat situs pada $z.$ Secara matematis disimbolkan sebagai $$(x, y) \in R \land (y, z) \in R \Rightarrow (x, z) \in R.$$

Jadi, $R$ memiliki ketiga sifat itu sekaligus sehingga terbukti bahwa $R$ merupakan relasi kesetaraan.

[collapse]

Soal Nomor 11

Manakah relasi pada himpunan orang berikut ini yang merupakan relasi kesetaraan?

  1. {$(a, b) \mid a$ dan $b$ berumur sama}
  2. {$(a, b) \mid a$ dan $b$ berbicara dengan bahasa yang sama}
  3. {$(a, b) \mid a$ dan $b$ pernah bertemu}
  4. {$(a, b) \mid a$ dan $b$ mempunyai orang tua yang sama}
  5. {$(a, b) \mid a$ menyukai $b$}

Pembahasan

Relasi kesetaraan (equivalence relation) adalah relasi yang bersifat refleksif, simetris, dan transitif secara sekaligus. Ini artinya, kita harus menunjukkan bahwa setiap relasi tersebut memiliki ketiga sifat ini agar dapat digolongkan sebagai relasi kesetaraan.
Jawaban a)
Diberikan relasi $R =~${$(a, b) \mid a$ dan $b$ berumur sama}.

  1. $R$ refleksif karena setiap orang pasti memiliki umur yang sama terhadap dirinya sendiri.
  2. $R$ simetris karena jika $a$ memiliki umur yang sama dengan $b,$ maka $b$ juga pasti memiliki umur yang sama dengan $a.$
  3. $R$ transitif karena jika $a$ dan $b$ memiliki umur yang sama, kemudian $b$ dan $c$ juga memiliki umur yang sama, maka haruslah $a$ dan $c$ memiliki umur yang sama.

Karena tiga sifat tersebut terpenuhi, maka relasi tersebut merupakan relasi kesetaraan.
Jawaban b)
Diberikan relasi $S =~${$(a, b) \mid a$ dan $b$ berbicara dengan bahasa yang sama}.

  1. $S$ refleksif karena setiap orang pasti berbicara dengan bahasa yang sama terhadap dirinya sendiri.
  2. $S$ simetris karena jika $a$ berbicara dengan bahasa yang sama kepada $b,$ maka $b$ juga pasti berbicara dengan bahasa yang sama kepada $a.$
  3. $S$ transitif karena jika $a$ dan $b$ berbicara dengan bahasa yang sama, kemudian $b$ dan $c$ juga berbicara dengan bahasa yang sama, maka $a$ dan $c$ juga berbicara dengan bahasa yang sama.

Karena tiga sifat tersebut terpenuhi, maka relasi tersebut merupakan relasi kesetaraan.
Jawaban c)
Diberikan relasi $T =~${$(a, b) \mid a$ dan $b$ pernah bertemu}.

  1. $T$ refleksif karena setiap orang pasti pernah bertemu dengan dirinya sendiri.
  2. $T$ simetris karena jika $a$ pernah bertemu dengan $b,$ maka $b$ juga pasti pernah bertemu dengan $a.$
  3. $T$ tidak transitif karena jika $a$ dan $b$ pernah bertemu, kemudian $b$ dan $c$ juga pernah bertemu, maka belum tentu $a$ dan $c$ pernah bertemu.

Karena ada satu sifat yang tidak terpenuhi, maka relasi tersebut bukan merupakan relasi kesetaraan.
Jawaban d)
Diberikan relasi $U =~${$(a, b) \mid a$ dan $b$ mempunyai orang tua yang sama}.

  1. $U$ refleksif karena setiap orang pasti memiliki orang tua yang sama terhadap dirinya sendiri.
  2. $U$ simetris karena jika $a$ memiliki orang tua yang sama dengan $b,$ maka $b$ juga pasti memiliki orang tua yang sama dengan $a.$
  3. $U$ transitif karena jika $a$ memiliki orang tua yang sama dengan $b,$ kemudian $b$ memiliki orang tua yang sama dengan $c,$ maka pastilah $a$ memiliki orang tua yang sama dengan $c.$ Dengan kata lain, $a, b, c$ adalah saudara kandung.

Karena tiga sifat tersebut terpenuhi, maka relasi tersebut merupakan relasi kesetaraan.
Jawaban e)

Diberikan relasi $V =~${$(a, b) \mid a$ menyukai $b$}.

  1. $V$ refleksif karena setiap orang, dipandang secara ideal dan normal, pasti menyukai dirinya sendiri.
  2. $V$ tidak simetris karena jika $a$ menyukai $b,$ belum tentu $b$ menyukai $a.$
  3. $V$ tidak transitif karena jika $a$ menyukai $b$ dan $b$ menyukai $c,$ maka belum tentu $a$ menyukai $c.$

Karena ada dua sifat yang tidak terpenuhi, maka relasi tersebut bukan merupakan relasi kesetaraan.

[collapse]

Soal Nomor 12

Misalkan $R$ adalah relasi pada himpunan pasangan berurut dari bilangan bulat positif sedemikian sehingga $((a, b), (c, d)) \in R$ jika dan hanya jika $ad = bc.$ Tunjukkan bahwa $R$ adalah relasi kesetaraan.

Pembahasan

Relasi kesetaraan (equivalence relation) adalah relasi yang bersifat refleksif, simetris, dan transitif secara sekaligus. Ini artinya, kita harus menunjukkan bahwa $R$ memiliki ketiga sifat tersebut agar dapat digolongkan sebagai relasi kesetaraan.

  1. $R$ refleksif. Perhatikan bahwa $((a, b), (a, b)) \in R$ karena persamaan $ab = ba$ adalah pernyataan yang bernilai benar. 
  2. $R$ simetris. Jika $((a, b), (c, d)) \in R,$ maka $((c, d), (a, b)) \in R$ karena $cb = da$ ekuivalen dengan $ad = bc.$ 
  3. $R$ transitif. Jika $((a, b), (c, d)) \in R$ dan $((c, d), (e, f)) \in R$ sehingga $ad = bc$ dan $cf = de,$ maka $((a, b), (e, f)) \in R$ karena berlaku $af = be.$ Hal ini dapat diketahui dari kedua persamaan awal.
    $$\begin{aligned} cf = de & \Rightarrow c = \dfrac{de}{f} \\ ad & = b\color{red}{c} \\ ad & = b\left(\dfrac{de}{f}\right) \\ a\color{blue}{d}f & = b\color{blue}{d}e \\ af & = be \end{aligned}$$

Jadi, $R$ memiliki ketiga sifat itu sekaligus sehingga terbukti bahwa $R$ merupakan relasi kesetaraan.

[collapse]

Soal Nomor 13

Manakah relasi yang disajikan dengan matriks berikut yang merupakan relasi pengurutan parsial?
a. $\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$
b. $\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}$
c. $\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix}$

Pembahasan

Relasi pengurutan parsial (partial order relation) didefinisikan sebagai relasi yang bersifat refleksif, antisimetris, dan transitif secara sekaligus.
Jawaban a)
Misalkan relasinya $R$ dengan matriks representasinya adalah $M_R = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.$

  1. $R$ refleksif karena semua entri pada diagonal utama matriksnya bernilai $1.$
  2. $R$ antisimetris yang ditunjukkan oleh nilai $m_{ij} \neq m_{ji}$ ketika salah satunya bernilai $1,$ yaitu $m_{12} = 1, m_{21} = 0$ dan $m_{13} = 0, m_{31} = 1.$
  3. $R$ tidak transitif. Perhatikan bahwa $m_{21} = m_{13} = 1,$ tetapi $m_{23} = 0.$

Karena ada satu sifat yang tidak terpenuhi, maka relasi tersebut tidak termasuk relasi pengurutan parsial.
Jawaban b)
Misalkan relasinya $S$ dengan matriks representasinya adalah $M_S = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}.$

  1. $S$ refleksif karena semua entri pada diagonal utama matriksnya bernilai $1.$
  2. $S$ antisimetris yang ditunjukkan oleh nilai $m_{ij} \neq m_{ji}$ ketika salah satunya bernilai $1,$ yaitu $m_{13} = 1, m_{31} = 0.$
  3. $S$ transitif. Syarat jika $(a, b) \in R$ dan $(b, c) \in R,$ maka $(a, c) \in R$ terpenuhi.

Karena semua sifat terpenuhi, maka relasi tersebut termasuk relasi pengurutan parsial.
Jawaban c)
Misalkan relasinya $T$ dengan matriks representasinya adalah $M_T = \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix}.$

  1. $T$ refleksif karena semua entri pada diagonal utama matriksnya bernilai $1.$
  2. $T$ antisimetris yang ditunjukkan oleh nilai $m_{ij} \neq m_{ji}$ ketika salah satunya bernilai $1,$ yaitu sebagai berikut.
    $$\begin{array}{c|c} \hline m_{13} = 0 & m_{31} = 1 \\ m_{23} = 1 & m_{32} = 0 \\ m_{14} = 0 & m_{41} = 1 \\ m_{24} = 0 & m_{42} = 1 \\ m_{34} = 1 & m_{43} = 0 \\ \hline \end{array}$$
  3. $T$ tidak transitif. Salah satu pasangan tiga entri dalam matriks yang tidak memenuhi adalah $a_{13} = a_{34} = 1,$ tetapi $a_{14} = 0.$

Karena ada satu sifat yang tidak terpenuhi, maka relasi tersebut tidak termasuk relasi pengurutan parsial.

[collapse]

Soal Nomor 14

Manakah dari ekspresi berikut ini yang merupakan poset (partially ordered set)?
a. $(\mathbb{Z}, =)$
b. $(\mathbb{Z}, \neq)$
c. $(\mathbb{Z}, <)$

Pembahasan

Relasi $R$ pada himpunan $S$ dikatakan relasi pengurutan parsial (partial order relation) jika relasi itu refleksif, antisimetris, dan transitif. Himpunan $S$ bersama-sama dengan relasi $R$ tersebut dinamakan himpunan terurut secara parsial (partially ordered set atau poset). Untuk menunjukkan bahwa suatu himpunan bersamaan dengan relasinya termasuk poset, kita harus menunjukkan bahwa relasi itu memenuhi ketiga sifat: refleksif, antisimetris, dan transitif.
Jawaban a)
Notasi $(\mathbb{Z}, =)$ menyatakan himpunan bilangan bulat dengan relasi $R$, yaitu $(a, b) \in \mathbb{Z}$ jika dan hanya jika $a = b.$

  1. $R$ refleksif karena setiap anggota himpunan bilangan bulat dipetakan ke dirinya sendiri menurut aturan relasi $a = b.$
  2. $R$ antisimetris karena $(a, b) \in R$ dan $(b, a) \in R$ mengakibatkan $a = b.$ Sekadar tambahan, $R$ juga bersifat simetris karena jika $(a, b) \in R,$ maka $(b, a) \in R,$ mengingat bahwa $a = b$ ekuivalen dengan $b = a.$
  3. $R$ transitif. Jika $a = b$ dan $b = c,$ maka $a = c.$

Oleh karena itu, $R$ merupakan relasi pengurutan parsial sehingga himpunan $(\mathbb{Z}, =)$ merupakan poset.
Jawaban b)
Notasi $(\mathbb{Z}, \neq)$ menyatakan himpunan bilangan bulat dengan relasi $R$, yaitu $(a, b) \in \mathbb{Z}$ jika dan hanya jika $a \neq b.$

  1. $R$ tidak refleksif karena setiap anggota himpunan bilangan bulat tidak dipetakan ke dirinya sendiri menurut aturan relasi $a \neq b.$
  2. $R$ tidak antisimetris karena akan ditemukan $(a, b) \in R$ sehingga $(b, a) \in R.$
  3. $R$ transitif. Jika $a \neq b$ dan $b \neq c,$ maka $a \neq c.$

Oleh karena itu, $R$ bukan merupakan relasi pengurutan parsial sehingga himpunan $(\mathbb{Z}, \neq)$ bukan merupakan poset.
Jawaban c)
Notasi $(\mathbb{Z}, <)$ menyatakan himpunan bilangan bulat dengan relasi $R$, yaitu $(a, b) \in \mathbb{Z}$ jika dan hanya jika $a < b.$

  1. $R$ tidak refleksif karena setiap anggota himpunan bilangan bulat tidak dipetakan ke dirinya sendiri. Ini dikarenakan tidak mungkin suatu bilangan bulat kurang dari dirinya sendiri.
  2. $R$ antisimetris karena tidak akan ditemukan $(a, b) \in R$ sehingga $(b, a) \in R.$
  3. $R$ transitif. Jika $a < b$ dan $b < c,$ maka $a < c.$

Oleh karena itu, $R$ bukan merupakan relasi pengurutan parsial sehingga himpunan $(\mathbb{Z}, <)$ bukan merupakan poset.

[collapse]

Soal Nomor 15

Misalkan $R$ suatu relasi pada himpunan bilangan bulat dengan $(m, n) \in R$ jika dan hanya jika $(m + n)$ habis dibagi $3.$

  1. Apakah $R$ suatu relasi refleksif?
  2. Apakah $R$ suatu relasi simetris?
  3. Apakah $R$ suatu relasi transitif?

Jelaskan.

Pembahasan

Jawaban a)
$R$ tidak refleksif karena terdapat suatu bilangan bulat $m$ sedemikian sehingga $(m, m) \notin R.$ Salah satunya adalah $m = 1$ karena $1+1 = 2$ tidak habis dibagi $3.$
Jawaban b)
$R$ simetris yang menandakan bahwa untuk setiap bilangan bulat $(m, n)$ yang memenuhi $(m, n) \in R,$ maka $(n, m) \in R.$ Ini dikarenakan eksistensi sifat komutatif penjumlahan $(m + n) = (n + m).$ Jika $(m + n)$ habis dibagi $3,$ maka $(n + m)$ juga demikian.
Jawaban c)
$R$ tidak transitif karena terdapat bilangan bulat $m, n, p$ sedemikian sehingga $(m, n) \in R$ dan $(n, p) \in R,$ tetapi $(m, p) \notin R.$ Salah satunya adalah $m = 2, n = 4,$ dan $p = 5.$ Perhatikan bahwa $(m, n) = (2, 4) \in R$ karena $6$ habis dibagi $3$ dan $(n, p) = (4, 5) \in R$ karena $9$ habis dibagi $3,$ tetapi $(2, 5) \notin R$ karena $7$ tidak habis dibagi $3.$

[collapse]

Soal Nomor 16

Misalkan $R = \{(0, 1), (1, 1), (1, 2),$ $(2, 0), (2, 2)\}$ adalah relasi pada himpunan $\{0, 1, 2, 3\}.$ Tentukan klosur refleksif dan klosur simetris dari $R.$

Pembahasan

Klosur refleksif diartikan sebagai relasi yang memuat semua pasangan berurut sehingga $R$ menjadi bersifat refleksif. Dalam hal ini, $R$ akan menjadi himpunan bagian dari relasi tersebut.
Perhatikan bahwa $R$ tidak refleksif karena ada anggota domain yang tidak memetakan ke dirinya sendiri, yaitu $0$ dan $3.$ Oleh karena itu, pasangan berurut yang perlu ditambahkan sebagai anggota adalah $(0, 0)$ dan $(3, 3).$ Dengan demikian, klosur refleksif dari $R$ adalah $S_1 = \{(0, 0), (0, 1), (1, 1),$ $(1, 2), (2, 0), (2, 2), (3, 3)\}.$


Klosur simetris diartikan sebagai relasi yang memuat semua pasangan berurut sehingga $R$ menjadi bersifat simetris. Dalam hal ini, $R$ akan menjadi himpunan bagian dari relasi tersebut.
Perhatikan bahwa $R$ tidak simetris karena ada $(x, y) \in \{1, 2, 3, 4\}$ sehingga $(y, x) \notin \{1, 2, 3, 4\},$ yaitu $(0, 1),$ $(1, 2),$ dan $(2, 0).$ Oleh karena itu, pasangan berurut yang perlu ditambahkan sebagai anggota adalah $(1, 0), (2, 1),$ dan $(0, 2).$ Dengan demikian, klosur simetris dari $R$ adalah $S_2 = \{(0, 0), (0, 1), (0, 2), (1,1),$ $(1, 2), (2, 0), (2, 1), (2, 2)\}.$

[collapse]

Soal Nomor 17

Misalkan relasi $R$ pada himpunan $A$ dinyatakan dengan matriks $M_R.$ Tunjukkan bahwa matriks yang merepresentasikan klosur simetris adalah $M_R \lor M^T_R.$

Pembahasan

Menurut definisi, klosur simetris $S$ dari relasi $R$ pada himpunan $A$ diberikan oleh
$$S = R \cup \{(y, x) \mid (x, y) \in R\}.$$Perhatikan bahwa invers dari $R$, ditulis $R^{-1}$ didefinisikan sebagai
$$R^{-1} = \{(y, x) \mid (x, y) \in R\}.$$Oleh karena itu, kita peroleh bahwa $S = R \cup R^{-1}$ yang bila dinyatakan dalam bentuk matriks, ditulis
$$M_S = M_R \lor M^T_R$$dengan $M^T_R$ menyatakan transpos dari matriks $M_R.$
Jadi, terbukti bahwa matriks yang merepresentasikan klosur simetris adalah $\boxed{M_R \lor M^T_R}$

[collapse]

Soal Nomor 18

Temukan klosur transitif dari relasi $\{(2, 1), (2, 3), (3, 1),$ $(3, 4), (4, 1), (4, 3)\}$ pada himpunan $\{1, 2, 3, 4\}.$

Pembahasan

Matriks yang merepresentasikan relasi $R$ adalah
$$M_R = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}.$$Karena relasi $R$ pada himpunan yang beranggotakan $4$ elemen, maka matriks klosur transitif dari $R$ adalah
$$M_{R^*} = M_R \lor M_R^2 \lor M_R^3 \lor M_R^4.$$Perhatikan bahwa
$$\begin{aligned} M_R^2 & = M_R \cdot M_R \\ & = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} \\ & = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \\ M_R^3 & = M_R^2 \cdot M_R \\ & = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} \\ & = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} = M_R \\ M_R^4 & = M_R^3 \cdot M_R \\ & = M_R \cdot M_R \\ & = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \end{aligned}$$Dengan demikian, didapat
$$\begin{aligned} M_{R^*} & = M_R \lor M_R^2 \lor M_R^3 \lor M_R^4 \\ & = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} \lor \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \lor \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} \lor \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix} \\ & = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix} \end{aligned}$$Jadi, klosur transitif dari $R$ adalah $$\boxed{R^* = \{(2,1), (2,3), (2, 4), (3, 1), (3, 3), (3, 4), (4, 1), (4, 3), (4, 4)\}}$$

[collapse]

Soal Nomor 19

Relasi $R$ pada himpunan $A$ dikatakan bersifat irefleksif (irreflexive) jika untuk setiap $a \in A,$ berlaku bahwa $(a, a) \notin R.$ Dengan kata lain, $R$ dikatakan irefleksif jika tidak ada anggota $A$ yang berpasangan dengan dirinya sendiri. Tuliskan notasi kuantor (quantifier) yang merepresentasikan definisi relasi yang irefleksif.

Pembahasan

Suatu relasi $R$ pada himpunan $A$ dikatakan bersifat irefleksif jika untuk setiap anggota $a \in A,$ berlaku bahwa $(a, a) \notin R.$ Frasa “Untuk setiap anggota” dapat dituliskan secara matematis dengan menggunakan notasi kuantor universal $\forall$ (baca: untuk semua/setiap). Jadi, $(a, a) \notin R$ untuk setiap $a \in A$ dapat ditulis dengan notasi berikut.
$$\boxed{\forall A \in A: (a, a) \notin R}$$

[collapse]

Soal Nomor 20

Relasi $R$ pada himpunan $A$ dikatakan bersifat irefleksif (irreflexive) jika untuk setiap $a \in A,$ berlaku bahwa $(a, a) \notin R.$ Tuliskan contoh relasi yang irefleksif yang himpunannya adalah sebagai berikut.
a. Himpunan orang-orang.
b. Himpunan bilangan bulat.

Pembahasan

Jawaban a)
Misalkan $x, y$ adalah anggota berbeda dari himpunan orang-orang.

  1. Didefinisikan relasi $R$ pada himpunan tersebut, yaitu $(x, y) \in R$ jika $x$ menikah dengan $y.$ Jelas bahwa tidak mungkin ada orang yang menikah dengan dirinya sendiri sehingga $(x, x) \notin R.$
  2. Didefinisikan relasi $R$ pada himpunan tersebut, yaitu $(x, y) \in R$ jika $x$ melakukan operasi transplantasi ginjal terhadap $y.$ Jelas bahwa tidak mungkin ada orang yang bisa melakukan operasi medis tersebut terhadap dirinya sendiri sehingga $(x, x) \notin R.$

Jawaban b)
Misalkan $x, y$ adalah anggota berbeda dari himpunan bilangan bulat.

  1. Didefinisikan relasi $R$ pada himpunan tersebut, yaitu $(x, y) \in R$ jika $x < y.$ Jelas bahwa $x$ dan $y$ pasti berbeda sehingga $(x, x) \notin R.$
  2. Didefinisikan relasi $R$ pada himpunan tersebut, yaitu $(x, y) \in R$ jika $x$ adalah faktor negatif dari bilangan bulat positif $y.$ Jelas bahwa $x$ dan $y$ pasti berbeda. Sebagai contoh, ambil $y = 5$ sehingga faktor negatifnya adalah $-5$ dan $-1.$ Dari sini, kita tahu bahwa $(x, x) \notin R.$

 

[collapse]

Soal Nomor 21

Relasi $R$ pada himpunan $A$ dikatakan bersifat irefleksif (irreflexive) jika untuk setiap $a \in A,$ berlaku bahwa $(a, a) \notin R.$ Dengan kata lain, $R$ dikatakan irefleksif jika tidak ada anggota $A$ yang berpasangan dengan dirinya sendiri. Jelaskan apakah ada relasi yang tidak bersifat refleksif dan tidak bersifat irefleksif sekaligus. Berikan contohnya.

Pembahasan

Suatu relasi $R$ pada himpunan $A$ dikatakan bersifat refleksif jika untuk setiap $a \in A,$ berlaku bahwa $(a, a) \in R.$ Apabila sama sekali tidak ada yang berpasangan dengan dirinya sendiri, $R$ dikatakan bersifat irefleksif. Dari sini, kita dapat memberi kesimpulan bahwa ADA relasi yang tidak bersifat refleksif dan juga tidak bersifat irefleksif.
Contohnya, $R = \{(1, 1), (1, 2)\}$ pada himpunan $A = \{1, 2\}.$ $R$ tidak refleksif karena $(2, 2) \notin R.$ $R$ juga tidak irefleksif karena $(1, 1) \in R.$

[collapse]

Soal Nomor 22

Apakah relasi yang bersifat asimetris (tidak simetris) juga pasti bersifat antisimetris? Apakah relasi yang bersifat antisimetris juga pasti bersifat asimetris? Jelaskan alasannya.

Pembahasan

Perhatikan penjelasan istilah simetris, asimetris, dan antisimetris berikut.

  1. Suatu relasi $R$ pada himpunan $A$ dikatakan simetris jika untuk setiap $a, b \in A,$ $(a, b) \in R$ mengimplikasikan $(b, a) \in R.$ Contoh: relasi “menikah dengan”.
  2. Sebaliknya, suatu relasi $R$ pada himpunan $A$ dikatakan asimetris jika untuk setiap $a, b \in A,$ $(a, b) \in R$ mengimplikasikan $(b, a) \notin R.$ Contoh: relasi “ayah dari”. Relasi yang asimetris tidak mungkin memuat anggota himpunan yang berpasangan dengan dirinya sendiri (pasti relasi itu bersifat irefleksif).
  3. Suatu relasi $R$ pada himpunan $A$ dikatakan antisimetris jika untuk setiap $a, b \in A,$ $(a, b) \in R$ dan $(b, a) \in R$ terpenuhi hanya saat $a = b.$ Contoh: relasi $\le$ pada himpunan bilangan real.

Setiap relasi yang asimetris juga pasti bersifat antisimetris (antisimetris). Namun, jika relasi antisimetris itu memuat anggota yang berpasangan dengan dirinya sendiri, yakni $(a, a),$ maka relasi tersebut bukan termasuk relasi yang asimetris.

[collapse]

Soal Nomor 23

Tunjukkan bahwa relasi $R = \emptyset$ pada himpunan kosong $S = \emptyset$ bersifat refleksif, simetris, dan transitif.

Pembahasan

Definisi:

  1. Relasi $R$ pada himpunan $A$ bersifat refleksif jika $(a, a) \in R$ untuk setiap $a \in A.$
  2. Relasi $R$ pada himpunan $A$ bersifat simetris (simetris) jika $(b, a) \in R$ ketika $(a, b) \in R.$
  3. Relasi $R$ pada himpunan $A$ bersifat transitif (transitif) jika $(a, b) \in R$ dan $(b, c) \in R$ mengimplikasikan $(a, c) \in R.$

Diberikan relasi $R = \emptyset$ pada himpunan kosong $S = \emptyset.$ Akan dibuktikan bahwa $R$ refleksif, simetris, dan transitif dengan menggunakan definisi di atas.
Sebelum itu, perlu diingat bahwa pada pernyataan majemuk berbentuk implikasi (jika $P,$ maka $Q),$ berlaku tabel kebenaran berikut.
$$\begin{array}{|c|c|c|} \hline P & Q & P \Rightarrow Q \\ \hline B & B & B \\ B & S & S \\ S & B & B \\ S & S & B \\ \hline \end{array}$$Pernyataan implikasi akan bernilai salah hanya ketika $P$ (anteseden) benar dan $Q$ (konsekuen) salah.


$R$ bersifat refleksif:
Definisi yang ekuivalen dengan relasi yang refleksif adalah: Jika $a \in A,$ maka $(a, a) \in R.$
Karena $a \in S$ bernilai salah (sebagaimana $S$ adalah himpunan kosong), maka pernyataan implikasi $(a \in S) \Rightarrow Q$ akan selalu bernilai benar tanpa menghiraukan nilai kebenaran $Q.$ Dengan mengandaikan $Q$ sebagai pernyataan $(a, a) \in R,$ maka menurut definisinya, $R$ terbukti refleksif.


$R$ bersifat simetris:
Definisi yang ekuivalen dengan relasi yang simetris adalah: Jika $(a, b) \in R,$ maka $(b, a) \in R.$
Karena $(a, b) \in R$ bernilai salah (sebagaimana $R$ adalah himpunan kosong), maka pernyataan implikasi $((a, b) \in R) \Rightarrow Q$ akan selalu bernilai benar tanpa menghiraukan nilai kebenaran $Q.$ Dengan mengandaikan $Q$ sebagai pernyataan $(b, a) \in R,$ maka menurut definisinya, $R$ terbukti simetris.


$R$ bersifat transitif:
Definisi yang ekuivalen dengan relasi yang transitif adalah: Jika $(a, b) \in R$ dan $(b, c) \in R,$ maka $(a, c) \in R.$
Karena $(a, b) \in R$ dan $(b, c) \in R$ masing-masing bernilai salah (sebagaimana $R$ adalah himpunan kosong), maka pernyataan konjungsi $(a, b) \in R$ dan $(b, c) \in R$ juga bernilai salah. Pernyataan implikasi $((a, b) \in R~\land~(b, c) \in R) \Rightarrow Q$ akan selalu bernilai benar tanpa menghiraukan nilai kebenaran $Q.$ Dengan mengandaikan $Q$ sebagai pernyataan $(a, c) \in R,$ maka menurut definisinya, $R$ terbukti transitif.

[collapse]

Soal Nomor 24

Misalkan $R$ dan $S$ adalah relasi refleksif. Buktikan bahwa $R \cap S$ dan $R\cup S$ juga merupakan relasi refleksif.

Pembahasan

Untuk membuktikan suatu relasi bersifat refleksif, harus ditunjukkan bahwa untuk setiap $x \in A,$ berlaku $(x, x)$ sebagai anggota dari relasi tersebut. Dalam kasus ini, $A$ adalah himpunan yang mendefinisikan $R$ dan $S.$
Untuk $A \cap B$:
Misalkan $x \in A.$ Karena $R$ dan $S$ refleksif, maka $(x, x) \in R$ dan $(x, x) \in S.$ Menurut definisi irisan himpunan, berlaku bahwa $(x, x) \in R \cap S.$ Jadi, terbukti bahwa $R \cap S$ refleksif karena setiap anggota himpunan $A$ dipasangkan pada dirinya sendiri.
Untuk $A \cup B$:
Misalkan $x \in A.$ Karena $R$ refleksif, maka $(x, x) \in R$ sehingga jelas bahwa $(x, x) \in R \cup S.$ Jadi, terbukti bahwa $R \cup S$ juga refleksif karena setiap anggota himpunan $A$ dipasangkan pada dirinya sendiri.

[collapse]

Soal Nomor 25

Misalkan $R$ dan $S$ adalah relasi transitif. Buktikan bahwa $R \cap S$ adalah relasi transitif, sedangkan $R \cup S$ belum tentu demikian.

Pembahasan

Definisi: 
Relasi $R$ pada himpunan $A$ dikatakan transitif (transitif) jika untuk setiap $a, b, c \in A,$ $(a, b) \in R$ dan $(b, c) \in R$ mengimplikasikan $(a, c) \in R.$


Akan dibuktikan bahwa jika $R$ dan $S$ transitif, maka $R \cap S$ transitif.
Anggap $a, b, c$ adalah sembarang anggota dari himpunan yang mendefinisikan $R$ dan $S.$ Misalkan $(a, b), (b, c) \in R \cap S$ sehingga $(a, b), (b, c) \in R$ dan $(a, b), (b, c) \in S.$ Karena $R$ dan $S$ transitif, haruslah $(a, c) \in R$ dan $(a, c) \in S.$ Akibatnya, $(a, c) \in R \cap S.$ Jadi, terbukti bahwa $R \cap S$ adalah relasi transitif.


Selanjutnya, akan dibuktikan bahwa jika $R$ dan $S$ transitif, maka $R \cup S$ belum tentu transitif.
Andaikan $R \cup S$ transitif. Kita akan menyangkalnya dengan menggunakan contoh penyangkal (counterexample). Misalkan terdapat himpunan $A = \{x, y, z\}$ dengan relasi $R = \{(x, y)\}$ dan $S = \{(y, z)\}.$ Kedua relasi ini transitif secara trivial, tetapi $R \cup S = \{(x, y), (y, z)\}$ tidak transitif menurut definisinya. Jadi, terbukti bahwa $R \cup S$ belum tentu transitif.

[collapse]

Soal Nomor 26

Buktikan bahwa jika relasi $R$ pada himpunan $A$ transitif, maka $R^n \subseteq R$ dengan $R^n$ menyatakan komposisi relasi $R$ sebanyak $n$ kali untuk $n \in \mathbb{N}.$

Pembahasan

Pembuktian akan dilakukan dengan menggunakan induksi matematika.
Misalkan $P_n$ menyatakan bahwa jika relasi $R$ pada himpunan $A$ transitif, maka $R^n \subseteq R.$

Langkah 1: Langkah Basis
Untuk $n = 1,$ $P_1$ jelas bernilai benar secara trivial, yakni $R \subseteq R.$ Basis induksi selesai.


Langkah 2: Langkah Induksi
Ambil sembarang bilangan asli $k.$ Asumsikan $P_{k}$ benar, yaitu pernyataan bahwa jika relasi $R$ pada himpunan $A$ transitif, maka $R^k \subseteq R.$ Dengan demikian, akan dibuktikan $P_{k+1}$ benar, yaitu pernyataan bahwa jika relasi $R$ pada himpunan $A$ transitif, maka $R^{k+1} \subseteq R.$ 

Misalkan $(x, y) \in R^{k+1}.$ Karena $R^{k+1} = R^k \circ R,$ akan ada elemen $z \in A$ sedemikian sehingga $(x, z) \in R^k$ dan $(z, y) \in R.$ Karena $R^k \subseteq R,$ maka $(x, z) \in R.$ Perhatikan bahwa $R$ transitif sehingga jika $(x, z) \in R$ dan $(z, y) \in R,$ maka $(x, y) \in R.$ Jadi, semua anggota $R^{k+1}$ adalah anggota $R.$ Dengan kata lain, terbukti bahwa $R^{k+1} \subseteq R.$


Menurut prinsip induksi matematika, terbukti bahwa jika relasi $R$ pada himpunan $A$ transitif, maka $R^n \subseteq R.$

[collapse]


Soal Nomor 1

Perhatikan relasi-relasi berikut pada himpunan bilangan bulat.
$$\begin{aligned} R_1 & = \{(a, b) \mid a \le b\} \\ R_2 & = \{(a, b) \mid a > b\} \\ R_3 & = \{(a, b) \mid a = b~\text{atau}~a = -b\} \\ R_4 & = \{(a, b) \mid a = b\} \\ R_5 & = \{(a, b) \mid a = b+1\} \\ R_6 & = \{(a, b) \mid a + b \le 3\} \end{aligned}$$Manakah dari masing-masing relasi tersebut yang memuat pasangan berurut $(1, 1), (1, 2),$ $(2, 1), (1, -1),$ dan $(2, 2)$?

Pembahasan

Tinjau setiap pasangan berurut dan selidiki apakah enam relasi yang diberikan memuat pasangan berurut tersebut atau tidak.

  1. Pasangan berurut $(1, 1)$ dimuat oleh $R_1, R_3, R_4,$ dan $R_6.$
  2. Pasangan berurut $(1, 2)$ dimuat oleh $R_1$ dan $R_6.$
  3. Pasangan berurut $(2, 1)$ dimuat oleh $R_2, R_5,$ dan $R_6.$
  4. Pasangan berurut $(1, -1)$ dimuat oleh $R_2, R_3,$ dan $R_6.$
  5. Pasangan berurut $(2, 2)$ dimuat oleh $R_1, R_3,$ dan $R_4.$

[collapse]

Soal Nomor 2

Diberikan himpunan $A = \{1, 2, 3\}.$ Buatlah relasi $R$ pada $A$ yang memenuhi kriteria berikut.

  1. $R$ refleksif, simetris, dan sekaligus transitif.
  2. $R$ refleksif dan simetris, tetapi tidak transitif.
  3. $R$ simetris dan transitif, tetapi tidak refleksif.
  4. $R$ refleksif dan transitif, tetapi tidak simetris.
  5. $R$ refleksif, tetapi tidak simetris dan tidak transitif.
  6. $R$ simetris, tetapi tidak refleksif dan tidak transitif.
  7. $R$ transitif, tetapi tidak refleksif dan tidak simetris.
  8. $R$ tidak refleksif, tidak simetris, dan tidak transitif.

Pembahasan

Alternatif relasi $R$ pada $A$ sehingga memenuhi kriteria yang diberikan adalah sebagai berikut. Alternatif lain barangkali ada.
Jawaban a)
Buat relasi $R$ pada $A$ dengan
$$R = \{(1, 1), (2, 2), (3, 3)\}.$$Perhatikan bahwa $R$ refleksif karena memuat $(a, a)$ untuk setiap $a \in A.$ $R$ juga simetris karena $(a, b) \in R$ jika $(b, a) \in R$ dengan $a, b \in A.$ Lebih lanjut, $R$ transitif karena kondisi $(a, b) \in R$ dan $(b, c) \in R$ mengakibatkan $(a, c) \in R$ tercapai dengan $a, b, c \in A$ dan $a = b = c.$

Jawaban b)
Buat relasi $R$ pada $A$ dengan
$$R = \{(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3)\}.$$Perhatikan bahwa $R$ refleksif karena memuat $(a, a)$ untuk setiap $a \in A.$ $R$ juga simetris karena $(a, b) \in R$ jika $(b, a) \in R$ dengan $a, b \in A.$ Namun, $R$ tidak transitif karena, sebagai contoh, $(1, 2) \in R$ dan $(2, 3) \in R,$ tetapi $(1, 3) \notin R.$
Jawaban c)
Buat relasi $R$ pada $A$ dengan
$$R = \{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 1), (3, 2)\}.$$Perhatikan bahwa $R$ simetris karena $(a, b) \in R$ jika $(b, a) \in R$ dengan $a, b \in A.$ $R$ juga transitif karena $(a, c) \in R$ jika $(a, b) \in R$ dan $(b, c) \in R$ dengan $a, b, c \in A.$ Namun, $R$ tidak refleksif karena $(3, 3) \notin R.$
Jawaban d)
Buat relasi $R$ pada $A$ dengan
$$R = \{(1, 1), (1, 2), (2, 2), (3, 3)\}.$$Perhatikan bahwa $R$ refleksif karena memuat $(a, a)$ untuk setiap $a \in A.$ $R$ juga transitif karena $(a, c) \in R$ jika $(a, b) \in R$ dan $(b, c) \in R$ dengan $a, b, c \in A.$ Namun, $R$ tidak simetris karena $(1, 2) \in R,$ tetapi $(2, 1) \notin R.$
Jawaban e)
Buat relasi $R$ pada $A$ dengan
$$R = \{(1, 1), (2, 2), (3, 3), (1, 3), (3, 2)\}.$$Perhatikan bahwa $R$ refleksif karena memuat $(a, a)$ untuk setiap $a \in A.$ Namun, $R$ tidak simetris karena, sebagai contoh, $(1, 3) \in R,$ tetapi $(3, 1) \notin R.$ Lebih lanjut, $R$ tidak transitif karena $(1, 3) \in R$ dan $(3, 2) \in R,$ tetapi $(1, 2) \notin R.$
Jawaban f)
Buat relasi $R$ pada $A$ dengan
$$R = \{(1, 2),(2, 1)\}.$$Perhatikan bahwa $R$ simetris karena $(1, 2) \in R$ ketika $(2, 1) \in R.$ Namun, $R$ tidak refleksif karena $(1, 1), (2, 2), (3, 3) \notin R.$ Lebih lanjut, $R$ tidak transitif karena $(1, 2) \in R$ dan $(2, 1) \in R,$ tetapi $(1, 1) \notin R.$
Jawaban g)
Buat relasi $R$ pada $A$ dengan
$$R = \{(1, 2),(2, 3), (1, 3)\}.$$Perhatikan bahwa $R$ transitif karena $(1, 2) \in R$ dan $(2, 3) \in R$ mengakibatkan $(1, 3) \in R.$ Namun, $R$ tidak refleksif karena $(1, 1), (2, 2), (3, 3) \notin R.$ Lebih lanjut, $R$ tidak simetris karena, sebagai contoh, $(1, 2) \in R,$ tetapi $(2, 1) \notin R.$
Jawaban h)
Buat relasi $R$ pada $A$ dengan
$$R = \{(1, 2),(2, 3)\}.$$Perhatikan bahwa $R$ tidak refleksif karena $(1, 1), (2, 2), (3, 3) \notin R.$ Lebih lanjut, $R$ tidak simetris karena, sebagai contoh, $(1, 2) \in R,$ tetapi $(2, 1) \notin R.$ Terlebih lagi, $R$ tidak transitif karena $(1, 2) \in R$ dan $(2, 3) \in R,$ tetapi $(1, 3) \notin R.$

[collapse]

Soal Nomor 3

Diketahui $R$ merupakan relasi pada himpunan $A.$ Diketahui pula bahwa $R$ simetris dan antisimetris. Apakah $R$ pasti refleksif atau transitif?

Pembahasan

Karena $R$ simetris, berdasarkan definisi, $(x, y) \in R$ mengakibatkan $(y, x) \in R$ untuk suatu $x, y \in A.$ Karena $R$ antisimetris, berdasarkan definisi, $(x, y) \in R$ dan $(y, x) \in R$ mengakibatkan $x = y.$ Dari dua pernyataan tersebut, diperoleh $x = y$ untuk setiap $(x, y) \in R.$ Jadi, $R$ mengaitkan satu elemen pada $A$ ke elemen yang sama pada $A.$ Ini berarti $R$ pasti transitif karena memenuhi definisi, sedangkan $R$ belum tentu refleksif karena tidak ada jaminan bahwa $(x, x) \in R$ untuk setiap $x \in A.$ Sebagai contoh, $R = \{(1, 1), (2, 2)\}$ pada himpunan $A = \{1, 2, 3\}$ merupakan relasi simetris dan antisimetris. Dapat diperiksa bahwa $R$ transitif, tetapi tidak refleksif karena $(3, 3) \notin R.$

[collapse]

Soal Nomor 4

Berapa banyak relasi dengan kriteria berikut yang dapat dibuat pada himpunan berhingga dengan $n$ elemen?

  1. Relasi refleksif.
  2. Relasi irefleksif.
  3. Relasi simetris.
  4. Relasi refleksif sekaligus simetris.
  5. Relasi antisimetris.

Pembahasan

Jawaban a)
Misalkan diberikan himpunan berhingga $A = \{a_1, a_2, \cdots, a_n\}$ dengan $|A| = n.$ Perhatikan bahwa $|A \times A| = n \times n = n^2.$ Dari $n^2$ elemen pasangan berurut tersebut, ada sebanyak $n$ elemen yang wajib termuat dalam suatu relasi $R$ agar dikatakan refleksif, yaitu $(a_i, a_i)$ untuk setiap $i \in \{1, 2, \cdots, n\}.$ Ini berarti kita hanya perlu menentukan banyaknya subhimpunan dari $n^2-n$ elemen tersisa, yaitu $2^{n^2-n}.$

Jadi, banyak relasi refleksif yang dapat dibuat pada himpunan berhingga dengan $n$ elemen adalah $\boxed{2^{n^2-n}}$
Jawaban b)
Misalkan diberikan himpunan berhingga $A = \{a_1, a_2, \cdots, a_n\}$ dengan $|A| = n.$ Perhatikan bahwa $|A \times A| = n \times n = n^2.$ Dari $n^2$ elemen pasangan berurut tersebut, ada sebanyak $n$ elemen yang tidak boleh termuat dalam suatu relasi $R$ agar dikatakan irefleksif, yaitu $(a_i, a_i)$ untuk setiap $i \in \{1, 2, \cdots, n\}.$ Ini berarti kita hanya perlu menentukan banyaknya subhimpunan dari $n^2-n$ elemen tersisa, yaitu $2^{n^2-n}.$
Jadi, banyak relasi irefleksif yang dapat dibuat pada himpunan berhingga dengan $n$ elemen adalah $\boxed{2^{n^2-n}}$
Jawaban c)
Misalkan diberikan himpunan berhingga $A = \{a_1, a_2, \cdots, a_n\}$ dengan $|A| = n.$ Relasi $R$ pada $A$ dapat dinyatakan oleh matriks representasi berordo $n \times n$ berikut dengan aturan $a_{i, j} = 1$ jika $(a_i, a_j) \in R$ dan $a_{i, j} = 0$ jika $(a_i, a_j) \notin R$ untuk setiap $i, j \in \{1, 2, \cdots, n\}.$
Ada $n$ entri diagonal utama pada matriks representasi tersebut sehingga banyak subhimpunan yang dapat dibuat adalah $2^n.$ Ada $n^2-n$ entri tersisa. Kita hanya dapat memilih setengahnya untuk diatur nilainya ($0$ atau $1$) karena $a_{i, j} = a_{j, i}.$ Jadi, banyak subhimpunan yang dapat dibuat adalah $2^{\frac{n^2-n}{2}}.$
Dengan menggunakan aturan perkalian, banyak relasi simetris yang dapat dibuat pada himpunan berhingga dengan $n$ elemen adalah
$$\boxed{2^n \cdot 2^{\frac{n^2-n}{2}} = 2^{\frac{n(n+1)}{2}}}$$Jawaban d)
Serupa dengan jawaban c, tetapi $n$ entri diagonal pada matriks representasi tidak diperhitungkan karena wajib termuat dalam relasi $R$ agar refleksif. Dengan demikian, $n^2-n$ entri tersisa dapat diatur agar memenuhi syarat relasi simetris. Kita hanya dapat memilih setengahnya untuk diatur nilainya ($0$ atau $1$) karena $a_{i, j} = a_{j, i}.$ Jadi, banyak subhimpunan yang dapat dibuat adalah $2^{\frac{n^2-n}{2}}.$ Dengan kata lain, banyak relasi refleksif sekaligus simetris yang dapat dibuat pada himpunan berhingga dengan $n$ elemen adalah $\boxed{2^{\frac{n(n-1)}{2}}}$
Jawaban e)
Misalkan diberikan himpunan berhingga $A = \{a_1, a_2, \cdots, a_n\}$ dengan $|A| = n.$ Relasi $R$ pada $A$ dapat dinyatakan oleh matriks representasi berordo $n \times n$ berikut dengan aturan $a_{i, j} = 1$ jika $(a_i, a_j) \in R$ dan $a_{i, j} = 0$ jika $(a_i, a_j) \notin R$ untuk setiap $i, j \in \{1, 2, \cdots, n\}.$
Ada $n$ entri diagonal utama pada matriks representasi tersebut sehingga banyak subhimpunan yang dapat dibuat adalah $2^n.$ Tinjau entri matriks $a_{i, j}$ untuk suatu $i, j \in \{1, 2, \cdots, n\}.$ Ada TIGA kemungkinan yang dapat menjadi pilihan agar $R$ dijamin antisimetris.

  1. $a_{i, j} \in R,$ tetapi $a_{j, i} \notin R.$
  2. $a_{i, j} \notin R,$ tetapi $a_{j, i} \in R.$
  3. $a_{i, j} \notin R,$ tetapi $a_{j, i} \notin R.$

Dengan hanya meninjau entri di bawah diagonal utama, banyak entri yang terlibat adalah $\dfrac{n^2-n}{2} = \dfrac{n(n-1)}{2}.$ Jadi, ada $3^{\frac{n(n-1)}{2}}$ kombinasi yang mungkin. Secara keseluruhan, ada $\boxed{2^n \cdot 3^{\frac{n(n-1)}{2}}}$ relasi antisimetris yang dapat dibuat pada himpunan berhingga dengan $n$ elemen

[collapse]