$$$$

Bab 2. Relasi

Daftar Isi

• 2.1 Relasi
• 2.2 Representasi Relasi
• 2.3 Sifat-sifat Relasi
• 2.4 Relasi Invers
• 2.5 Mengkombinasikan Relasi
• 2.6 Komposisi Relasi

---

2.1 Relasi

Relasi biner antara dua himpunan adalah sebuah himpunan yang terdiri dari pasangan terurut yang dibentuk dari dua anggota himpunan terkait.

DEFINISI 2.1
Relasi biner

$R$ dari himpunan hingga

$A$ ke himpunan hingga

$B$ adalah himpunan bagian (subset) dari

$A\times B$ atau dalam notasi

$R\subseteq A\times B$.

Dengan kata lain relasi biner

$R$ dari

$A$ ke

$B$ adalah sebuah himpunan yang anggota-anggotanya adalah pasangan terurut dimana elemen pertama dari setiap pasangan terurut tersebut didapatkan dari anggota

$A$ dan elemen keduanya didapatkan dari anggota

$B$.

Kita menggunakan notasi

$aRb$ untuk menuliskan

$(a,b)\in R$ yang artinya

$a$ dihubungkan ke

$b$ oleh

$R$. Notasi

$a\text{cancel}Rb$ digunakan untuk menuliskan

$(a,b)\notin R$ yang artinya

$a$ tidak dihubungkan ke

$b$ oleh

$R$.

Relasi biner sering disebut hanya sebagai relasi saja. Selanjutnya kita akan menggunakan kata relasi untuk merujuk relasi biner.

Contoh 2.1.1
Misalkan

$A$ adalah himpunan dari mahasiswa-mahasiswa dalam sebuah kelas jurusan Teknik Informatika yang terdiri dari Amir, Budi, dan Cecep. Lalu, misalkan

$B$ adalah himpunan dari mata-mata kuliah yang terdiri dari IT101, IT201, IT221, dan IT231.
Maka,

$A=\{\text{Amir},\text{Budi},\text{Cecep}\}$ dan

$B=\{\text{CS101},\text{IT201},\text{IT221},\text{IT231}\}$. Dan,

$$\begin{array}{rl}A\times B=& \{(\text{Amir},\text{TI101}),(\text{Amir},\text{TI101}),(\text{Amir},\text{TI101}),(\text{Amir},\text{TI101}),\end{array}$$

Misalkan 𝑅 adalah relasi yang menyatakan mata kuliah yang diambil oleh mahasiswa, yaitu:

$R=\{(\text{Amir},\text{IT201}),(\text{Amir},\text{IT231}),(\text{Budi},\text{IT101}),(\text{Budi},\text{IT201}),(\text{Cecep},\text{IT231})\}$.

Dapat dilihat:

• $R\subseteq A\times B$ yang berarti
  $R$ adalah relasi dari
  $A$ ke
  $B$.
• $(\text{Amir},\text{IT201})\in R$ atau
  $\text{Amir }R\text{ IT201}$.
• $(\text{Amir},\text{IT221})\notin R$ atau
  $\text{Amir}\text{cancel}R\text{ IT221}$.

Contoh 2.1.2
Misalkan

$A=\{0,1,2\}$ dan

$B=\{a,b\}$, maka himpunan

$\{(0,a),(0,b),(1,a),(2,b)\}$ adalah sebuah relasi dari

$A$ ke

$B$. Dan jika kita menamakan relasi tersebut dengan

$R$, maka

$0Ra$ tetapi

$1\text{cancel}Rb$.

Contoh 2.1.3
Misalkan

$A=\{a,b,c\}$ dan

$B=\{1,2,3\}$. Tentukan apakah himpunan-himpunan berikut adalah sebuah relasi dari

$A$ ke

$B$ :

• Apakah
  $R=\{(a,1),(b,2),(c,2)\}$ adalah relasi dari
  $A$ ke
  $B$ ?
• Apakah
  $Q=\{(1,a),(2,b)\}$ adalah relasi dari
  $A$ ke
  $B$ ?

Solusi:

• Ya, karena elemen pertama dari semua pasangan terurut anggota
  $R$ adalah anggota
  $A$ dan elemen keduanya adalah anggota
  $B$.
• Bukan, karena elemen pertama dari semua pasangan terurut anggota
  $R$ adalah anggota
  $B$ dan elemen keduanya adalah anggota
  $A$.
  $Q$ adalah relasi dari
  $B$ ke
  $A$.

Contoh 2.1.4
Misal

$P=\{2,3,4\}$ dan

$𝑄=\{2,4,8,9,15\}$. Jika sebuah relasi

$R$ dari

$P$ ke

$Q$ dengan

$(p,q)$ jika

$p$ habis membagi

$q$. Tentukan anggota-anggota relasi

$R$.

Solusi:
Karena,

• $2\in P$ habis membagi
  $2\in Q$,
  $4\in Q$, dan
  $8\in Q$, maka
  $(2,2)$,
  $(2,4)$, dan
  $(2,8)$ adalah elemen
  $R$.
• $3\in P$ habis membagi
  $9\in Q$ dan
  $15\in Q$, maka
  $(3,9)$ dan
  $(3,15)$ adalah elemen
  $R$.
• $4\in P$ habis membagi
  $4\in Q$ dan
  $8\in Q$ maka
  $(4,4)$ dan
  $(4,8)$ adalah elemen
  $R$.

Maka,

$R=\{(2,2),(2,4),(2,8),(3,9),(3,15),(4,4),(4,8)\}$.

Relasi dapat direpresentasikan dalam diagram panah.

Contoh 2.1.5
Relasi

$R=\{(0,a),(0,b),(1,a),(2,b)\}$ dari

$A=\{0,1,2\}$ ke

$B=\{a,b\}$ dapat direpresentasikan dengan diagram panah berikut:

Selain direpresentasikan dalam diagram panah, relasi juga dapat direpresentasikan dalam tabel.

Contoh 2.1.6
Relasi

$R=\{(0,a),(0,b),(1,a),(2,b)\}$ dari

$A=\{0,1,2\}$ ke

$B=\{a,b\}$ dapat direpresentasikan dengan sebuah tabel berikut:

$A$	$B$
$0$	$a$
$0$	$b$
$1$	$a$
$2$	$b$

Kolom pertama pada tabel di atas adalah elemen pertama dari pasangan terurut relasi

$R$ dan kolom kedua adalah elemen kedua dari pasangan terurut relasi

$R$.

Relasi pada Sebuah Himpunan

Relasi juga dapat didefinisikan dari suatu himpunan ke himpunan itu sendiri juga.

DEFINISI 2.2
Relasi pada sebuah himpunan

$A$ adalah relasi dari

$A$ ke

$A$.

Dengan kata lain, sebuah relasi pada himpunan

$A$ adalah subset dari

$A\times A$.

Contoh 2.1.7
Misalkan

$R$ adalah sebuah relasi pada

$A=\{2,3,4,8,9\}$ yang didefinisikan dengan

$R=\{(x,y)|x\text{ adalah faktor prima dari }y\}$. Jabarkan pasangan-pasangan anggota terurut dari

$R$.

Solusi:
Karena,

• 2 adalah faktor prima dari 2, 4, dan 8, maka
  $(2,2),(2,4),(2,8)\in R$.
• 3 adalah faktor prima dari 3 dan 9, maka
  $(3,3),(3,9)\in R$.

Sehingga,

$R=\{(2,2),(2,4),(2,8),(3,3),(3,9)\}$.

Contoh 2.1.8
Misalkan

$A=\{1,2,3,4\}$ dan

$R$ adalah sebuah relasi pada

$A$ yang didefinisikan dengan

$R=\{(a,b)|a\text{habis membagi}b\}$. Jabarkan pasangan-pasangan terurut anggota dari

$R$.

Solusi:
Karena

$(a,b)$ di dalam

$R$ jika dan hanya jika

$a$ membagi

$b$, maka

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

Relasi

$R$ direpresentasikan dalam diagram panah berikut:

2.2 Representasi Relasi

Kita telah melihat bahwa relasi dapat direpresentasikan dalam diagram panah dan juga tabel.

Contoh 2.2.1

• Relasi pad Contoh 2.1.1 direpresentgasikan dalam diagram panah dan tabel seperti berikut:

• Relasi pada Contoh 2.1.5 digambarkan dalam diagram panah dan tabel seperti berikut:

• Relasi pada Contoh 2.1.8 digambarkan dalam diagram panah dan tabel seperti berikut:

Terdapat dua cara lain untuk menrepresentasikan relasi yaitu dengan matriks dan graf berarah (directed graph).

Representasi Relasi Menggunakan Matriks

Relasi antara dua himpunan hingga dapat disajikan menggunakan matriks yang elemen-elemennya bernilai 1 atau 0. Misalkan

$R$ adalah relasi dari

$A=\{a_1,a_2,...,a_m\}$ ke

$B=\{b_1,b_2,...,b_n\}$, maka relasi

$R$ dapat direpresentasikan oleh sebuah matriks

$M_R=[m_{ij}]$, yaitu

dimana

$$m_{ij}=\{\begin{array}{ll}0,& \text{jika }(a_i,b_j)\in R\\ 1,& \text{jika }(a_i,b_j)\notin R\end{array}$$

Contoh 2.2.2
Misalkan

$A=\{1,2,3\}$,

$B=\{1,2\}$, dan

$R$ adalah relasi dari

$A$ ke

$B$ yang beranggotakan

$(a,b)$ untuk

$a\in A$,

$b\in B$, dan

$a>b$. Cari matriks representasi dari

$R$ !

Solusi:
Karena

$R=\{(2,1),(3,1),(3,2)\}$, maka matriks untuk

$R$ adalah

$$M_R=\left[\begin{array}{cc}0& 0\\ 1& 0\\ 1& 1\end{array}\right]$$

Elemen bernilai 1 pada matriks menunjukkan bahwa pasangan

$(2,1)$,

$(3,1)$, dan

$(3,2)$ terdapat di dalam

$R$. Elemen nilai 0 menujukkan tidak ada pasangan lain yang merupakan anggota

$R$.

Contoh 2.2.3
Sebut

$A=\{2,3,4\}$ dan

$B=\{2,4,8,9,15\}$. Misalkan

$R$ adalah relasi dari

$A$ ke

$B$ yang beranggotakan

$(a,b)$ untuk

$a\in A$,

$b\in B$, dimana

$a$ adalah faktor prima dari

$b$. Cari matriks representasi dari

$R$ !

Solusi:
Karena untuk setiap

$(a,b)$,

$a$ adalah faktor prima dari

$b$ maka kita dapatkan

$R=\{(2,2),(2,4),(2,8),(3,9),(3,15)\}$. Sehingga matriks untuk

$R$ adalah

$$M_R=\left[\begin{array}{ccccc}1& 1& 1& 0& 0\\ 0& 0& 0& 1& 1\\ 0& 0& 0& 0& 0\end{array}\right]$$

Representasi Relasi Menggunakan Graf Berarah

Graf berarah (directed graph atau digraph) dapat digunakan untuk merepresentasikan sebuah relasi pada sebuah himpunan. Graf berarah tidak dapat digunakan untuk merepresentasikan relasi dari suatu himpunan ke himpunan lain. Graf berarah yang merepresentasikan relasi

$R$ pada sebuah himpunan digambarkan mengikuti ketentuan-ketentuan berikut:

• Setiap elemen himpunan dinyatakan dengan sebuah titik (yang disebut juga simpul atau vertex), dan setiap pasangan terurut dinyatakan dengan busur (arc)
• Jika
  $(a,b)\in R$, maka sebuah busur dibuat dari simpul
  $a$ ke simpul
  $b$. Simpul
  $a$ disebut simpul asal (initial vertex) dan simpul
  $b$ disebut simpul tujuan (terminal vertex).
• Pasangan terurut
  $(a,a)$ dinyatakan dengan busur dari simpul
  $a$ ke simpul
  $a$ sendiri. Busur semacam ini disebut gelang (loop).

Contoh 2.2.4

Misalkan

$R=\{(a,a),(a,b),(b,a),(b,c),(b,d),(c,a),(c,d),(d,b)\}$ adalah relasi pada himpunan

$\{a,b,c,d\}$, maka

$R$ direpresentasikan dalam graf berarah berikut:

Contoh 2.2.5

Misalkan

$R=\{(1,1),(1,3),(2,1),(2,3),(2,4),(3,1),(3,2),(4,1)\}$ dalah relasi pada himpunan

$\{1,2,3,4\}$, maka

$R$ direpresentasikan dalam graf berarah berikut:

2.3. Sifat-sifat Relasi

Relasi yang didefinisikan pada sebuah himpunan mempunyai sejumlah sifat. Sifat-sifat tersebut antara lain:

• Refleksif
• Simetris
• Antisimetris
• Transitif

Refleksif

DEFINISI 2.3
Sebuah relasi,

$R$ pada himpunan

$A$ disebut refleksif jika

$(a,a)\in R$ untuk setiap

$a\in A$ . Sebaliknya, relasi

$R$ disebut tidak refleksif jika terdapat

$a\in A$ sedemikian sehingga

$(a,a)\notin R$.

Contoh 2.3.1
Misalkan

$A=\{1,2,3,4\}$. Relasi-relasi pada himpunan

$A$ berikut:

• $R_1=\{(1,1),(1,3),(2,1),(2,2),(3,3),(4,2),(4,3),(4,4)\}$ bersifat refleksif karena mengandung pasangan terurut berbentuk
  $(a,a)$ untuk semua
  $a$ di dalam
  $A$ yaitu
  $(1,1)$,
  $(2,2)$,
  $(3,3)$, dan
  $(4,4)$.
• $R_2=\{(1,1),(2,2),(2,3),(4,2),(4,3),(4,4)\}$ tidak refleksif karena
  $(3,3)\notin R$.

Contoh 2.3.2
Apakah relasi "habis membagi" pada himpunan bilangan bulat positif bersifat refleksif?

Solusi:
Karena setiap bilangan bulat positif habis dibagi dengan dirinya sendiri, sehingga terdapat

$(a,a)\in R$ untuk setiap

$a\in \mathbb{N}$. Jadi, relasi "habis membagi" bersifat refleksif.

Contoh 2.3.3
Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif

$\mathbb{N}$.

• $R_1=\{(x,y)|x>y\}$.
• $R_2=\{(x,y)|x+y=5\}$.
• $R_3=\{(x,y)|3x+y=10\}$.

Tidak satupun dari ketiga relasi di atas yang refleksif karena,

$(a,a)\notin R$ untuk

$a\in \mathbb{N}$. Sebagai contoh,

$(2,2)\notin R$.

Relasi yang bersifat refleksif mempunyai matriks yang elemen diagonal utamanya semua bernilai 1, atau

$m_{ii}=1$ untuk

$i=1,2,...,n$. Bentuk matriks dari relasi yang bersifat refleksif dapat dilihat pada Gambar 2.1.

Gambar 2.1. Bentuk Matriks dari Relasi yang Refleksif.

Graf berarah yang merepresentasikan relasi yang bersifat refleksif juga dapat diidentifikasi dengan adanya gelang pada setiap simpulnya.

Simetris

DEFINISI 2.4
Relasi

$R$ pada himpunan

$A$ disebut simetris jika

$(a,b)\in R$, maka

$(b,a)\in R$ untuk

$a,b\in A$. Sedangkan relasi

$R$ pada himpunan

$A$ disebut tidak simetris jika

$(a,b)\in R$, tetapi

$(b,a)\notin R$ untuk

$a,b\in A$.

Contoh 2.3.4
Misalkan

$A=\{1,2,3,4\}$ dan

$R$ adalah relasi pada

$A$ yang didefinisikan dengan

$R=\{(1,1),(1,2),(2,1),(2,2),(2,4),(4,2),(4,4)\}$. Tentukan apakah

$R$ simetris.

Solusi:

$R$ bersifat simetris karena jika

$(a,b)\in R$, maka

$(b,a)\in R$. Untuk pasangan terurut dengan dua elemen yang sama

$(1,1)$,

$(2,2)$, dan

$(4,4)$ sudah jelas syarat simetris terpenuhi. Untuk pasangan terurut yang dua elemennya tidak sama, kita dapat lihat

$(1,2)\in R$ dan

$(2,1)\in R$, begitu juga

$(2,4)\in R$ dan

$(4,2)\in R$ yang berarti syarat simetris terpenuhi.

Contoh 2.3.5
Misalkan

$A=\{1,2,3,4\}$. Tentukan apakah relasi-relasi pada himpunan

$A$ berikut simetris.

• $R_1=\{(1,1),(2,3),(2,4),(4,2)\}$.
• $R_2=\{(1,1),(2,2),(2,3),(3,2),(4,2),(4,4)\}$.

Solusi:

• $R_1$ tidak simetris karena
  $(2,3)\in R$ tetapi
  $(3,2)\notin R$.
• $R_2$ tidak simetris karena
  $(4,2)\in R$ tetapi
  $(2,4)\notin R$.

Contoh 2.3.6
Apakah relasi “habis membagi” pada himpunan bilangan bulat positif bersifat simetris?

Solusi:
Relasi “habis membagi” tidak simetris. Karena jika

$a$ habis membagi

$b$,

$b$ tidak habis membagi

$a$, kecuali jika

$a=b$. Sebagai contoh, 2 habis membagi 4, tetapi 4 tidak habis membagi 2. Karena itu,

$(2,4)\in R$ tetapi

$(4,2)\notin R$.

Contoh 2.3.7
Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif ℕ.

• ${𝑅}_1=\{(𝑥,𝑦)|𝑥>𝑦\}$ tidak simetris karena misalkan 5 lebih besar dari 3 tetapi 3 tidak lebih besar dari 5.
• ${𝑅}_2=\{(𝑥,𝑦)|𝑥+𝑦=5\}$ simetris karena
  $𝑥+𝑦=𝑦+𝑥=5$, sehingga jika
  $(𝑥,𝑦)\in R$ maka
  $(𝑦,𝑥)\in R$ juga.
• ${𝑅}_3=\{(𝑥,𝑦)|3𝑥+𝑦=10\}$ tidak simetris karena misalkan
  $(3,1)\in R$ tetapi
  $(1,3)\notin R$.

Relasi yang bersifat simetris mempunyai matriks yang bercirikan elemen-elemen di bawah diagonal utama merupakan pencerminan dari elemen-elemen di atas diagonal utama, atau

$m_{ij}=m_{ji}=1$, untuk

$i=1,2,...,n$. Contoh ciri matriks dari sebuah relasi yang bersifat simetris dapat dilihat pada Gambar 2.2.

Gambar 2.2. Bentuk Matriks dari Relasi yang Simetris.

Sedangkan graf berarah dari relasi yang bersifat simetris dicirikan oleh: jika terdapat busur dari

$a$ ke

$b$, maka juga terdapat busur dari

$b$ ke

$a$.

Antisimetris

DEFINISI 2.5
Relasi

$R$ pada himpunan

$A$ disebut antisimetris jika

$(a,b)\in R$ dan

$(b,a)\in R$ maka

$a=b$ untuk

$a,b\in A$.

Dengan kata lain, relasi

$R$ pada himpunan

$A$ adalah antisimetris, jika

$(a,b)\in R$ maka

$(b,a)\notin R$, kecuali ketika

$a=b$.

Contoh 2.3.8
Misalkan

$A=\{1,2,3,4\}$ dan terdapat dua relasi pada

$A$ berikut:

• $R_1=\{(1,3),(4,2),(3,3),(4,4)\}$
• $R_2=\{(1,3),(4,2),(4,4),(2,4)\}$

Tentukan apakah masing-masing relasi adalah antisimetris !

Solusi:

• $R_1$ bersifat antisimetris. Untuk pasangan terurut berelemen sama
  $(3,3)$ dan
  $(4,4)$ sudah jelas syarat antisimetris terpenuhi. Untuk pasangan terurut berelemen tidak sama syarat antisimetris juga terpenuhi:
  $(1,3)\in R$ dan
  $(3,1)\notin R$ begitu juga
  $(4,2)\in R$ dan
  $(2,4)\notin R$.

• $R_1$ tidak antisimetris, karena
  $(4,2)\in R$ dan
  $(2,4)\in R$ tetapi
  $4\ne 2$.

Contoh 2.3.9
Misalkan

$A=\{1,2,3,4\}$ dan relasi-relasi di bawah didefinisikan pada himpunan

$A$, maka:

• Relasi

  $R_1=\{(1,1),(1,2),(2,1),(2,2),(2,4),(4,2),(4,4)\}$ bersifat simetris dan tidak antisimetris, karena
  $(1,2)\in R$ dan
  $(2,1)\in R$, begitu juga
  $(2,4)\in R$ dan
  $(4,2)\in R$.

• Relasi

  $R_2=\{(1,1),(2,3),(2,4),(4,2)\}$ bersifat tidak simetris dan tidak antisimetris.
  • Tidak simetris karena
    $(2,3)\in R$, tetapi
    $(3,2)\notin R$.
  • Tidak antisimetris karena
    $(2,4)\in R$ dan
    $(4,2)\in R$ juga.

• Relasi

  $R_3=\{(1,1),(2,2),(3,3)\}$ bersifat simetris dan antisimetris, karena semua pasangan terurut dengan dua elemen sama memenuhi syarat simetris dan antisimetris.

• Relasi

  $R_4=\{(1,1),(1,2),(2,2),(2,3)\}$ tidak simetris dan antisimetris.
  • Tidak simetris karena
    $(1,2)\in R$ tetapi
    $(2,1)\notin R$ dan juga
    $(2,3)\in R$ tetapi
    $(3,2)\notin R$.
  • Antisimetris karena untuk pasangan terurut berelemen sama
    $(1,1),(2,2)\in R$ sudah jelas memenuhi syarat antisimetris, begitu juga untuk pasangan terurut tidak berelemen sama
    $(1,2)\in R$ tetapi
    $(2,1)\notin R$ dan
    $(2,3)\in R$ tetapi
    $(3,2)\notin R$.

• Relasi

  $R_5=\{(1,1),(2,4),(3,3),(4,2)\}$ simetris dan tidak antisimetris karena
  $(2,4)\in R$ dan
  $(4,2)\in R$ tetapi
  $2\ne 4$.

• Relasi

  $R_6=\{(1,1),(2,2),(2,3),(3,2),(4,2),(4,4)\}$ tidak simetris dan tidak antisimetris.
  • Tidak simetris karena
    $(4,2)\in R$ tetapi
    $(2,4)\notin R$.
  • Tidak antisimetris karena
    $(2,3)\in R$ dan
    $(3,2)\in R$ tetapi
    $2\ne 3$.

Contoh 2.3.10
Apakah relasi “habis membagi” pada himpunan bilangan bulat positif bersifat antisimetris?

Solusi:
Relasi “habis membagi” bersifat antisimetris karena jika

$a$ habis membagi

$b$ dan

$b$ habis membagi

$a$ maka

$a=b$. Sebagai contoh, 4 habis membagi 4. Karena itu,

$(4,4)\in R$ dan juga

$4=4$.

Contoh 2.3.11
Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif ℕ.

• ${𝑅}_1=\{(𝑥,𝑦)|𝑥>𝑦\}$ antisimetris karena jika
  $(x,y)\in R$ maka
  $y\ngtr x$, sehingga
  $(y,x)\notin R$.
• ${𝑅}_2=\{(𝑥,𝑦)|𝑥+𝑦=5\}$ tidak antisimetris karena jika
  $(x,y)\in R$ maka
  $(y,x)\in R$ juga.
• ${𝑅}_3=\{(𝑥,𝑦)|3𝑥+𝑦=10\}$ antisimetris karena tidak ada
  $a$ dan
  $b$ dengan
  $a\ne b$ sedemikian sehingga
  $(a,b)$ dan
  $(b,a)$ ada di
  $R_3$.

Matriks dari relasi antisimetris mempunyai sifat yaitu jika

$m_{ij}=1$ dengan

$i\ne j$, maka

$m_{ji}=0$. Contoh bentuk matriks dari sebuah relasi yang antisimetris ditunjukkan oleh Gambar 2.3.

Gambar 2.3. Bentuk Matriks dari Relasi yang Antisimetris.

Sedangkan graf berarah dari relasi yang bersifat antisimetris dicirikan oleh: tidak ada dua busur dalam arah berlawanan antara dua simpul berbeda.

Transitif

DEFINISI 2.6
Relasi

$R$ pada himpunan

$A$ disebut transitif jika untuk setiap

$(a,b)\in R$ dan

$(b,c)\in R$, maka

$(a,c)\in R$, untuk semua

$a,b,c\in A$.

Contoh 2.3.12
Misalkan

$A=\{1,2,3,4\}$. Tentukan apakah relasi-relasi berikut bersifat transitif:

• $R_1=\{(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)\}$
• $R_2=\{(1,1),(2,3),(2,4),(4,2)\}$
• $R_3=\{(1,1),(2,2),(3,3),(4,4)\}$
• $R_4=\{(1,2),(3,4)\}$

Solusi:

• Ya.

  $R_1$ bersifat transitif. Perhatikan tabel berikut:

  $(a,b)$	$(b,c)$	$(a,c)$
  $(3,2)$	$(2,1)$	$(3,1)$
  $(4,2)$	$(2,1)$	$(4,1)$
  $(4,3)$	$(3,1)$	$(4,1)$
  $(4,3)$	$(3,2)$	$(4,2)$

  Pada tabel di atas dapat dilihat syarat transitif dari relasi

  $R_1$ terpenuhi.

• Tidak.

  $R_2$ tidak bersifat transitif, karena
  $(2,4)\in R_2$ dan
  $(4,2)\in R_2$ tetapi
  $(2,2)\notin R_2$. Begitu juga,
  $(4,2)\in R_2$ dan
  $(2,3)\in R_2$ tetapi
  $(4,3)\notin R_2$.

• Ya. Relasi

  $R_3=\{(1,1),(2,2),(3,3),(4,4)\}$ jelas bersifat transitif.

• Tidak. Relasi

  $R_4$ tidak transitif karena tidak ada
  $(a,b)\in R_4$ dan
  $(b,c)\in R_4$ sedemikian sehingga
  $(a,c)\in R_4$.

Contoh 2.3.13
Apakah relasi “habis membagi” pada himpunan bilangan bulat positif bersifat transitif?

Solusi:
Misalkan

$a$ habis membagi

$b$ dan

$b$ habis membagi

$c$. Maka terdapat bilangan bulat positif

$m$ dan

$n$ sedemikian sehingga

$b=ma$ dan

$c=nb$. Sehingga,

$c=nma$, yang berarti

$a$ membagi

$c$. Jadi, relasi “habis membagi” bersifat transitif.

Contoh 2.3.14
Tiga buah relasi di bawah ini menyatakan relasi pada himpunan bilangan bulat positif ℕ.

• ${𝑅}_1=\{(𝑥,𝑦)|𝑥>𝑦\}$ bersifat transitif karena jika
  $x>y$ dan
  $y>z$, maka
  $x>z$.
• ${𝑅}_2=\{(𝑥,𝑦)|𝑥+𝑦=5\}$ tidak transitif karena
  $(4,2)$ dan
  $(2,4)$ berada di dalam
  $R_2$ tetapi
  $(4,4)\notin R_2$.
• ${𝑅}_3=\{(𝑥,𝑦)|3𝑥+𝑦=10\}$ bersifat transitif. Dapat dilihat bahwa
  $R_3=\{(1,7),(2,4),(3,1)\}$. Karena untuk
  $(1,7)$ tidak ada bentuk
  $(7,z)\in R_3$, dan untuk
  $(2,4)$ tidak ada bentuk
  $(4,z)\in R_3$, begitu juga untuk
  $(3,1)$ tidak ada bentuk
  $(1,z)\in R_3$, maka
  $R_3$ transitif.

Relasi yang bersifat transitif tidak mempunyai ciri khusus pada matriks representasinya. Sedangkan, representasi graf berarah dari relasi yang transitif dicirikan oleh: jika terdapat busur dari

$a$ ke

$b$ dan dari

$b$ ke

$c$, maka juga terdapat busur dari

$a$ ke

$c$.

2.4. Relasi Invers

DEFINISI 2.7
Misalkan

$R$ adalah sebuah relasi dari himpunan

$A$ ke himpunan

$B$ yang didefinisikan dengan

$R=\{(a,b)|a\in A,b\in B\}$. Relasi invers dari

$R$, dinotasikan dengan

$R^{-1}$, adalah relasi dari

$B$ ke

$A$ yang didefiniskan dengan:

$$R^{-1}=\{(b,a)|(a,b)\in R\}$$

Dengan kata lain, relasi invers dari relasi

$R$ adalah relasi yang didapatkan dengan menukar posisi elemen-elemen pada setiap pasangan terurut dari

$R$.

Contoh 2.4.1
Misalkan

$A=\{1,2,3\}$,

$B=\{a,b\}$, dan

$R$ adalah relasi dari

$A$ ke

$B$ yang didefinisikan dengan

$R=\{(1,a),(1,b),(3,a)\}$, maka relasi invers dari

$R$ adalah

$R^{-1}=\{(a,1),(b,1),(a,3)\}$

Contoh 2.4.2
Misalkan

$P=\{2,3,4\}$,

$Q=\{2,4,8,9,15\}$, dan

$R$ adalah relasi dari

$P$ ke

$Q$ dengan

$(p,q)\in R$ jika

$p$ habis membagi

$q$.
Tentukan

$R^{-1}$.

Solusi:
Karena

$(p,q)\in R$ jika

$p$ membagi

$q$, maka:

$$R=\{(2,2),(2,4),(2,8),(3,9),(3,15),(4,4),(4,8)\}$$

Sehingga,

$R^{-1}$ adalah adalah invers dari relasi

$R$, yaitu relasi dari

$$R^{-1}=\{(2,2),(4,2),(8,2),(9,3),(15,3),(4,4),(8,4)\}$$

Dalam bentuk matriks, relasi invers dari suatu relasi direpresentasikan oleh matriks transpos dari matriks yang merepresentasikan relasi tersebut. Misalkan sebuah relasi

$R$ direpresentasikan oleh matriks

$M_R$ maka

$R^{-1}$ dapat direpresentasikan oleh matriks

$M_R^T$ yang merupakan transpos dari matriks

$M_R$.

Contoh 2.4.3
Misalkan

$R$ adalah relasi seperti pada Contoh 2.4.2, maka representasi matriks dari

$R$ adalah:

$$M=\left[\begin{array}{ccccc}1& 1& 1& 0& 0\\ 0& 0& 0& 1& 1\\ 0& 1& 1& 0& 0\end{array}\right]$$

Sehingga matriks yang merepresentasikan relasi

$R^{-1}$ diperoleh dengan melakukan transpos terhadap matriks

$M$, yaitu:

$$\begin{array}{r}{M}^T={\left[\begin{array}{ccccc}1& 1& 1& 0& 0\\ 0& 0& 0& 1& 1\\ 0& 1& 1& 0& 0\end{array}\right]}^T=\left[\begin{array}{ccc}1& 0& 0\\ 1& 0& 1\\ 1& 0& 1\\ 0& 1& 0\\ 0& 1& 0\end{array}\right]\end{array}$$

2.5. Mengkombinasikan Relasi

Karena relasi-relasi dari himpunan

$A$ ke himpunan

$B$ adalah himpunan bagian dari

$A\times B$, maka operasi-operasi himpunan seperti irisan, gabungan, selisih, dan selisih simetri pada dua relasi dari

$A$ ke

$B$ juga berlaku.

Contoh 2.5.1

Misalkan

$A=\{1,2,3\}$ dan

$B=\{1,2,3,4\}$ dan relasi

$R_1=\{(1,1),(2,2),(3,3)\}$ dan

$R_2=\{(1,1),(1,2),(1,3),(1,4)\}$ adalah relasi-relasi dari

$A$ ke

$B$. Maka,

$R_1\cup R_2=\{(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)\}$,

$R_1\cap R_2=\{(1,1)\}$,

$R_1-R_2=\{(2,2),(3,3)\}$,

$R_2-R_1=\{(1,2),(1,3),(1,4)\}$,

$R_1\oplus R_2=\{(1,2),(1,3),(1,4),(2,2),(3,3)\}$.

2.6. Komposisi Relasi

Dua relasi dapat dikombinasikan secara komposisi.

DEFINISI 2.8
Misalkan

$R$ adalah sebuah relasi dari himpunan

$A$ ke himpunan

$B$ dan

$S$ adalah relasi dari himpunan

$B$ ke himpunan

$C$. Komposisi

$R$ dan

$S$, dinotasikan dengan

$S\circ R$, adalah relasi yang beranggotakan pasangan terurut

$(a,c)$ dimana

$a\in A$,

$c\in C$, dan terdapat sebuah elemen

$b\in B$ sedemikian sehingga

$(a,b)\in R$ dan

$(b,c)\in S$.

Komposisi

$R$ dan

$S$ dapat didefinisikan dalam notasi seperti berikut:

$$S\circ R=\{(a,c)|a\in A,c\in C,\text{ dan terdapat}b\in B\text{ dimana}(a,b)\in R\text{dan}(b,c)\in S\}$$

Contoh 2.6.1
Misalkan

$A=\{1,2,3\}$,

$B=\{2,4,6,8\}$, dan

$C=\{s,t,u\}$. Relasi

$R$ didefinisikan dengan:

$R=\{(1,2),(1,6),(2,4),(3,4),(3,6),(3,8)\}$

dan relasi

$S$ didefinisikan dengan:

$S=\{(2,u),(4,s),(4,t),(6,t),(8,u)\}$

Maka, komposisi relasi

$R$ dan

$S$ adalah:

$S\circ R=\{(1,u),(1,t),(2,s),(2,t),(3,s),(3,t),(3,u)\}$

Dalam diagram panah

$S\circ R$ direpresentasikan sebagai berikut:

Daftar Pustaka

1. Rinaldi Munir. 2016. Matematika Diskrit. Bandung, Indonesia. Informatika Bandung.
2. Kenneth H. Rosen. 2012. Discrete Mathematics and Its Applications (Seventh Edition). Amerika Serikat. McGraw-Hill.
3. Susanna S. Epp. 2018. Discrete Mathematics with Applications (Fifth Edition). Amerika Serikat. Cengage.
4. D. Suryadi H.S. 1993. Aljabar Logika & Himpunan. Indonesia. Penerbit Gunadarma.