Relasi biner adalah hubungan elemen suatu himpunan ke elemen himpunan lain. Himpunan asal dinamakan dengan domain. Himpunan tujuan disebut dengan kodomain/range. Relasi biner dapat dituliskan dengan menggunakan himpunan pasangan terurut yang memiliki 2 elemen, elemen pertama merupakan elemen domain/asal dan elemen kedua merupakan elemen kodomain/tujuan.

Misalkan kita mempunyai relasi bernama $R$. Relasi ini menghubungkan himpunan $A$ (domain) ke himpunan $B$ (kodomain) maka himpunan $R$ merupakan himpunan bagian dari perkalian silang $A$ dengan $B$ ($\displaystyle{ R \subseteq A \times B }$). Jika $a$ terhubung ke $b$ maka terdapat $(a, b)$ di dalam $R$ ($\displaystyle{ \left( a , b \right) \in R }$ atau bisa dituliskan dengan $\displaystyle{ a \enspace R \enspace b }$). Jika $a$ tidak terhubung ke $b$ maka tidak terdapat $(a, b)$ di dalam $R$ ($\displaystyle{ \left( a , b \right) \notin R }$ atau bisa dituliskan $\displaystyle{ a \enspace \enclose{horizontalstrike}{R} \enspace b }$).

Terdapat jenis khusus dari relasi biner yaitu relasi biner yang menghubungkan elemen suatu himpunan ke elemen dirinya. Misalkan relasi biner yang menghubungkan elemen himpunan $A$ ke elemen himpunan $A$. Relasi ini disebut sebagai relasi pada himpunan $A$ .

# Representasi Himpunan

# Tabel

Kolom pertama berisi elemen domain dan kolom kedua berisi elemen kodomain yang terhubung dengan elemen domain pada kolom pertama baris sama.

# Diagram Panah

# Matriks

Relasi biner $R$ antara $A$ dan $B$ dapat direpresentasikan sebagai matriks dengan setiap baris mewakilkan $A$ dan setiap kolom mewakilkan $B$. Jika $\displaystyle{ a \enspace R \enspace b }$, maka entri matriks pada baris yang diwakili $a$ dan kolom yang diwakili $b$ bernilai 1. Sedangkan jika $\displaystyle{ a \enspace \enclose{horizontalstrike}{R} \enspace b }$, maka entri matriks pada baris yang diwakili $a$ dan kolom yang diwakili $b$ bernilai 0.

Secara matematis matriksnya dapat dituliskan seperti berikut:

$$\displaystyle{ M = \left. \begin{array}{cc} & \left. \begin{array}{cccc} b _{ 1 \phantom{\times x} } & b _{ 2 \phantom{\times x} } & \ldots & b _{ m \phantom{\times} } \end{array} \right. \\ \left. \begin{array}{c} a _{ 1 } \\ a _{ 2 } \\ \vdots \\ a _{ n } \end{array} \right. & \left[ \begin{array}{cccc} m _{ 1 , 1 } & m _{ 1 , 2 } & \ldots & m _{ 1 , n } \\ m _{ 2 , 1 } & m _{ 2 , 2 } & \ldots & m _{ 2 , n } \\ \vdots & \vdots & \vdots & \vdots \\ m _{ m , 1 } & m _{ m , 2 } & \ldots & m _{ m , n } \end{array} \right] \end{array} \right. }$$

$$\displaystyle{ m _{ i , j } = \left\lbrace \begin{array}{cc} 1 & \text{jika } a _{ i } \enspace R \enspace b _{ j } \\ 0 & \text{jika } a _{ i } \enspace \enclose{horizontalstrike}{R} \enspace b _{ j } \end{array} \right\rbrace }$$

# Graf Berarah

Relasi biner $R$ antara $A$ dan $B$ juga dapat direpresentasikan sebagai graf berarah. Semua elemen pada kedua himpunan digambar sebagai titik/simpul/vertex. Jika $\displaystyle{ a \enspace R \enspace b }$ maka terdapat busur/arc dari simpul $a$ menuju simpul $b$. Sedangkan jika $\displaystyle{ a \enspace \enclose{horizontalstrike}{R} \enspace b }$ maka tidak terdapat busur dari simpul $a$ menuju $b$. Jika $\displaystyle{ a \enspace R \enspace a }$ maka terdapat gelang/kalang/loop di simpul $a$.

# Relasi Inversi

Relasi Inversi dari Relasi R dinotasikan dengan $\displaystyle{ R ^{ {-1 } } }$ . Relasi $\displaystyle{ R ^{ {-1 } } }$ dapat dibentuk dengan membalik semua pasangan terurut di relasi $\displaystyle{ R }$. Representasi matriks dari relasi $\displaystyle{ R ^{ {-1 } } }$ merupakan transpose dari representasi matriks relasi $R$. Representasi graf relasi $\displaystyle{ R ^{ {-1 } } }$ merupakan graf dari relasi $\displaystyle{ R }$ dengan semua busur arahnya dibalik.

# Operasi Himpunan pada Relasi

Karena relasi pada dasarnya adalah himpunan maka relasi juga dapat dikenai operasi himpunan seperti irisan, gabungan, pengurangan, beda setangkup, dll.

Gabungan relasi juga dapat dituliskan sebagai operasi matriks:

$$\displaystyle{ M _{ R \cup S } = M _{ R } \vee M _{ S } }$$

Operasi $\displaystyle{ \vee }$ (disjungsi) pada matriks akan menghasilkan matriks dengan setiap entri adalah disjungsi entri pada matriks pertama dan kedua pada posisi yang sama.

Ini juga bisa dilakukan pada irisan relasi:

$$\displaystyle{ M _{ R \cap S } = M _{ R } \wedge M _{ S } }$$

# Komposisi

Misalkan $R$ adalah relasi antara $A$ dan $B$. $S$ adalah relasi antara $B$ dan $C$. Komposisi relasi $R$ ke $S$ menghasilkan relasi dari $A$ ke $C$ melalui $B$ sebagai perantara. Komposisi relasi $R$ ke $S$ dinotasikan sebagai $\displaystyle{ S \circ R }$ . Ingat urutannya dibalik karena komposisi dibaca dari kanan.

Komposisi relasi $R$ dan $S$ juga dapat dituliskan sebagai operasi perkalian matriks khusus:

$$\displaystyle{ M _{ S \circ R } = M _{ R } . M _{ S } }$$

Operator $\displaystyle{ . }$ sama dengan perkalian matriks biasa. Bedangan perkalian diubah menjadi $\displaystyle{ \wedge }$ (konjungsi) dan penjumlahan diubah menjadi $\displaystyle{ \vee }$ (disjungsi).

Sebuah relasi dapat dikomposisikan dengan dirinya berkali-kali. $\displaystyle{ R ^{ n } }$ berarti relasi $R$ dikomposisikan dengan dirinya sendiri sebanyak $n$ kali.

$$\displaystyle{ \begin{aligned}R ^{ n } = \underbrace{ R \circ R \circ \ldots \circ R } _{ \displaystyle n \text{ kali} } \\ M _{ R ^{ n } } = M _{ R } ^{ \left[ n \right] }\end{aligned} }$$

# Sifat Relasi

# Refleksif

Suatu relasi disebut refleksif jika semua anggota himpunan berelasi dengan dirinya sendiri. Matriks relasi yang bersifat refleksif ditandai dengan semua entri di diagonal utama bernilai 1. Graf dari relasi yang bersifat refleksif ditandai dengan semua simpul memiliki gelang.

Terdapat juga sifat irrefleksif. Sifat ini merupakan kebalikan dari sifat refleksif. Suatu relasi disebut irrefleksif jika semua anggota himpunan tidak ada yang berelasi dengan dirinya sendiri. Matriks relasi yang bersifat irrefleksif ditandai denga semua entri di diagonal utama bernilai 0. Grafik dari relasi ini ditandai dengan tidak adanya simpul yang memiliki gelang.

# Setangkup

Sebuah relasi disebut setangkup/simetri jika untuk semua $a$ yang berelasi dengan $b$ maka $b$ juga harus berelasi dengan $a$. Matriks dari relasi setangkup mempunyai sifat setangkup. Graf dari relasi setangkup ditandai dengan semua simpul yang berelasi dihubungkan oleh 2 busur yang berlawanan arah. Dengan kata lain, tidak ada 2 simpul yang hanya dihubungkan oleh satu busur searah. Namun, dua simpul boleh tidak memiliki busur sama sekali.

Relasi yang tidak memiliki relasi $\displaystyle{ a }$ dengan $\displaystyle{ b }$ ($\displaystyle{ a \ne b }$) jelas setangkup.

# Tolak-Setangkup

Sebuah relasi disebut tolak-setangkup/anti-simetri jika untuk semua $a$ yang berelasi dengan $b$ ($\displaystyle{ a \ne b }$) maka $b$ tidak boleh berelasi dengan $a$. Dengan kata lain, untuk semua $a$ yang berelasi dengan $b$ dan $b$ berelasi dengan $a$ maka harus $a = b$ . Matriks dari relasi setangkup memiliki ciri-ciri jika $\displaystyle{ m _{ i j } = 1 }$ maka $\displaystyle{ m _{ j i } = 0 }$ dan jika $\displaystyle{ m _{ i j } = 0 }$ maka $\displaystyle{ m _{ j i } = 1 }$ dengan $\displaystyle{ i \ne j }$. Dengan kata lain, jika matriks dicerminkan oleh diagonal utama, maka seluruh entrinya berkebalikan nilai. Graf dari relasi tolak setangkup ditandai dengan semua simpul yang berelasi hanya dihubungkan oleh 1 busur saja. Dengan kata lain, tidak boleh ada 2 simpul yang dhubungkan oleh 2 busur yang berlawanan arah. Namun, 2 simpul boleh tidak memiliki busur sama sekali.

Relasi yang tidak memiliki relasi $\displaystyle{ a }$ dengan $\displaystyle{ b }$ ($\displaystyle{ a \ne b }$) jelas tolak setangkup dan setangkup. Relasi yang memiliki relasi $\displaystyle{ a }$ dengan $\displaystyle{ b }$ (dengan $\displaystyle{ a \ne b }$) maka relasi ini tidak mungkin memiliki sifat setangkup dan tolak-setangkup secara bersamaan.

# Transitif

Sebuah relasi disebut transitif jika untuk semua $a$ yang berelasi dengan $b$ dan $b$ berelasi dengan $c$ maka $a$ harus berelasi dengan $c$. Matriks relasi transitif tidak memiliki ciri khusus. Tetapi grafik relasi transitif memiliki ciri jika terdapat busur dari $a$ ke $b$ dan $b$ ke $c$ maka busur dari $a$ ke $c$ harus ada.

Untuk menguji apakah suatu himpunan transitif kita bisa mendaftar anggota relasi yang memilki pola $\displaystyle{ \left( a , b \right) }$ dan $\displaystyle{ \left( b , c \right) }$. Kemudian kita mencari `$(a, c)$``

Relasi yang tidak memiliki $a$ yang berelasi dengan $b$ dan $b$ berelasi dengan $c$ jelas transitif.

# Klosur/Tutupan

# Klosur Refleksif

Klosur refleksif dari relasi $R$ adalah sebuah relasi paling minimal yang mengandung $R$ dan bersifat refleksif. Klosur refleksif dari relasi $R$ dilambangkan dengan $r(R)$. Misalkan relasi $R$ adalah relasi pada himpunan $A$, klosur refleksif dari $\displaystyle{ R }$ dapat dibuat dengan menggabungkan $R$ dengan relasi yang berisi $a$ dihubungkan dengan $a$ untuk semua $\displaystyle{ a \in A }$.

$$\displaystyle{ r \left( R \right) = R \cup \left\lbrace \left( a , a \right) \mid a \in A \right\rbrace }$$

# Klosur Setangkup

Klosur setangkup dari relasi $R$ adalah sebuah relasi paling minimal yang mengandung $R$ dan bersifat setangkup. Klosur setangkup dari relasi $R$ dilambangkan dengan $s(R)$. Klosur setangkup dari $R$ dapat dibentuk dengan menggabungkan $R$ dengan inversi dari $R$.

$$\displaystyle{ s \left( R \right) = R \cup R ^{ {-1 } } }$$

# Klosur Tolak Setangkup

Klosur tolak setangkup itu tidak ada.

Misalkan kita mendefinikan klosur tolak setangkup dari relasi $R$ adalah sebuah relasi paling minimal yang mengandung $R$ dan bersifat tolak setangkup. Misalkan tidak mempunyai relasi $R$ yang bersifat tidak tolak-setangkup. Alasan mengapa relasi $R$ tidak tolak-setangkup jelaslah karena ada $a$ yang berelasi dengan $b$, $b$ berelasi dengan $a$ dan $\displaystyle{ a \ne b }$. Untuk membuat relasi ini tolak-setangkup, kita harus menghapus relasi dari $a$ ke $b$ atau relasi dari $b$ ke $a$. Kita menghasilkan relasi baru yang bersifat tolak-setangkup. Relasi ini jelaslah bukan klosur tolak-setangkup dari $R$ karena relasi ini tidak mengandung relasi $R$. Ingatlah bahwa kita tadi menghapus satu elemen untuk menghasilkan relasi baru ini.

# Klosur Transitif

Klosur transitif dari relasi $R$ adalah sebuah relasi paling minimal yang mengandung $R$ dan bersifat transitif. Klosur transitif dari relasi $R$ dilambangkan dengan $R+$. Misalkan relasi $R$ adalah relasi pada himpunan $A$. Untuk menentukan klosur transitif dari relasi $R$ maka bisa menggunakan persamaan berikut:

$$\displaystyle{ \begin{aligned}R + = & \bigcup _{ i = 1 } ^{ n } R ^{ n }\end{aligned} }$$

atau

$$\displaystyle{ R + = R \cup R ^{ 1 } \cup R ^{ 2 } \cup \ldots \cup R ^{ n } }$$

atau

$$\displaystyle{ M _{ R + } = M _{ R } \vee M _{ R ^{ 1 } } \vee M _{ R ^{ 2 } } \vee \ldots \vee M _{ R ^{ n } } }$$

dengan $n$ adalah kardinalitas dari $A$.

Kebanyakan literatur mengatakan bahwa klosur transitif dari relasi $R$ dilambangkan dengan $R^*$. Terdapat sedikit literatur yang mengatakan bahwa $\displaystyle{ R ^{ \ast } }$ menyatakan klosur transitif dan refleksif dari $R$.

# Relasi Setara

Relasi setara/ekivalen adalah relasi yang memiliki sifat refleksif, transitif dan setangkup. Dua buah elemen dikatakan setara jika kedua elemen terhubung.

Kelas setara/ekivalen dari $\displaystyle{ a }$ pada himpunan $\displaystyle{ R }$ dilambangkan dengan $\displaystyle{ \left[ a \right] }$ atau $\displaystyle{ \left[ a \right] _{ R } }$. Kelas setara dari $\displaystyle{ a }$ pada himpunan $\displaystyle{ R }$ adalah himpunan yang semua elemennya setara dengan $\displaystyle{ a }$ menurut relasi $\displaystyle{ R }$. Jika dua elemen setara maka kelas setaranya juga sama.

Partisi kelas setara dari relasi $\displaystyle{ R }$ adalah partisi yang elemennya adalah semua kelas ekivalen yang mungkin dari relasi $\displaystyle{ R }$.

# Relasi Pengurutan Parsial

Relasi pengurutan parsial (partial ordering relation) adalah relasi yang memilki sifat refleksif, transitif, dan tolak-setangkup. Misalkan relasi $\displaystyle{ R }$ pada himpunan $\displaystyle{ A }$ adalah relasi pengurutan parsial maka bisa dinotasikan sebagai pasangan terurut $\displaystyle{ < A , R > }$ (Ingat himpunan ditulis pertama baru relasinya). Pasangan terurut tadi disebut dengan partially ordered set atau poset.

Relasi juga dapat dituliskan sebagai operator komparasi misalnya $\displaystyle{ \leqslant }$ (kurang dari), $\displaystyle{ \geqslant }$ (lebih dari), $\displaystyle{ {/} }$ (habis membagi)

Terdapat operator khusus untuk relasi jenis ini yaitu $\displaystyle{ = \prec }$. $\displaystyle{ a = \prec b }$ dibaca $a$ mendahului $b$ atau $b$ didahului $a$. $a$ dikatakan mendahului $b$ jika $a$ dihubungkan ke $b$.

Terdapat elemen minimal dan maksimal di dalam poset.

• Elemen minimal adalah elemen yang tidak didahului elemen apapun
• Elemen maksimal adalah elemen yang tidak mendahului elemen apapun

Terdapat juga elemen terkecil dan elemen terbesar di dalam poset.

• Elemen terkecil adalah elemen yang mendahului semua elemen
• Elemen terbesar adalah elemen yang didahului semua elemen.

Elemen minimal bisa jadi sama dengan elemen terkecil tetapi tidak selalu. Elemen maksimal bisa jadi sama dengan elemen maksimal tetapi tidak selalu.

Sebuah elemen disebut batas bawah (lower bound) dari sebuah himpunan jika elemen tersebut mendahului semua elemen pada himpunan tersebut. Batas bawah dari satu himpunan bisa berupa banyak elemen. Batas bawah terbesar (greatest lower boud) dari sebuah himpunan adalah batas bawah dari himpunan tersebut yang didahului oleh batas bawah lain. Batas bawah terbesar juga bisa saja lebih dari 1 elemen.

Sebuah elemen disebut batas atas (upper bound) dari sebuah himpunan jika elemen tersebut didahului semua elemen pada himpunan tersebut. Batas atas bisa saja lebih dari 1 elemen. Batas atas terkecil (least upper bound) dari sebuah himpunan adalah batas atas dari himpunan tersebut yang mendahului batas atas lain. Batas atas terkecil bisa jadi lebih dari 1 elemen.

# Diagram Hasse

Relasi ini dapat direpresentasikan sebagai diagram Hasse. Aturan penggambaran diagram Hasse:

• Setiap elemen digambar pada level tertentu
• Jika $a$ mendahului $b$ dan $\displaystyle{ a \ne b }$ maka $a$ berada di level yang lebih rendah daripada $b$
• Elemen minimal akan berada pada level 1
• Jika $a$ mendahului $b$ secara langsung maka digambar garis dari $a$ menuju $b$ Maksud secara langsung adalah tidak ada elemen lain dimana $a$ mendahului elemen tersebut dan elemen tersebut mendahului $b$. Ini menyebabkan $a$ berada tepat 1 level di bawah $b$.

# Urutan Total

Relasi pengurutan parsial $R$ pada himpunan $A$ disebut urutan total (total order) atau uruta liniar (linear order) jika untuk semua $a$ dan $b$ anggota $A$ maka berlaku $\displaystyle{ a = \prec b }$ atau $\displaystyle{ b = \prec a }$. Ini berarti jika kita menggambar diagram hasse urutan total maka pada setiap level hanya ada 1 elemen. Relasi total $R$ pada himpunan $A$ bisa dinotasikan sebagai pasangan terurut $\displaystyle{ \left( A , R \right) }$. Pasangan terurut ini bisa disebut sebagai himpunan terurut liniar (linearly orderer set) atau sebuah rantai (chain).

Relasi $\displaystyle{ \left( A , \leqslant \right) }$ jelas merupakan urutan total. Karena untuk semua $\displaystyle{ a }$ dan $b$ anggota $\displaystyle{ A }$ maka berlaku $\displaystyle{ a \leqslant b }$ atau $\displaystyle{ b \leqslant a }$. Relasi $\displaystyle{ \left( A , \geqslant \right) }$ juga jelas merupakan urutan total.

Sedangkan untuk $\displaystyle{ \left( P \left( A \right) , \subseteq \right) }$ hanya menjadi urutan total jika $\displaystyle{ A }$ memiliki kardinalitas 1. Karena saat kardinalitas $\displaystyle{ A }$ adalah 1 maka $\displaystyle{ P \left( A \right) = \left\lbrace \left\lbrace \right\rbrace , \left\lbrace a _{ 1 } \right\rbrace \right\rbrace }$ dan berlaku $\displaystyle{ \left\lbrace \right\rbrace \subseteq \left\lbrace a _{ 1 } \right\rbrace }$. Jika $\displaystyle{ A }$ memilki kardinalitas lebih dari 1, maka akan terdapat elemen $\displaystyle{ \left\lbrace a _{ 1 } \right\rbrace }$ dan $\displaystyle{ \left\lbrace a _{ 2 } \right\rbrace }$ yang mana $\displaystyle{ \left\lbrace a _{ 1 } \right\rbrace \not\subseteq \left\lbrace a _{ 2 } \right\rbrace }$ dan $\displaystyle{ \left\lbrace a _{ 2 } \right\rbrace \not\subseteq \left\lbrace a _{ 1 } \right\rbrace }$

# Relasi n-ary

Relasi n-ary adalah relasi antara $n$ himpunan. $n$ disebut juga derajat. Jika derajanya 2 maka disebut dengan relasi biner. Misalkan kita mempunyai relasi $R$ berderajat $n$ yang merelasikan himpunan $\displaystyle{ A _{ 1 } , A _{ 2 } , \ldots , A _{ n } }$ maka $R$ merupakan himpunan bagian dari $\displaystyle{ A _{ 1 } \times A _{ 2 } \times \ldots \times A _{ n } }$.

Berikut adalah operasi pada relasi n-ary:

• $\displaystyle{ \sigma _{ \text{predikat} } \left( R \right) }$ memilih anggota $R$ yang memenuhi predikat. Operasi ini disebut dengan seleksi.
• $\displaystyle{ \pi _{ \text{daftar kolum} } \left( R \right) }$ menampilkan relasi $R$ dengan hanya menampilkan daftar kolom. Operasi ini disebut dengan proyeksi.
• $\displaystyle{ \tau _{ \text{daftar kolom} } \left( R , S \right) }$ menggabungkan relasi $\displaystyle{ R }$ dan $\displaystyle{ R }$ dengan menggunakan daftar kolom sebagai kolom acuan. Operasi ini disebut sebagai join.g