Relasi biner

Relasi biner adalah jenis relasi khusus dengan aritas dua. Contoh relasi biner yang khas antara lain kurang dari, sama dengan, habis membagi, lebih dari, dan sebagainya.

Contoh

Relasi biner adalah salah satu relasi yang khas dan paling sering dijumpai. Relasi ini juga memiliki beberapa sifat menarik yang akan kita bahas di sini.

Contoh relasi biner: hubungan “ayah — anak laki-laki”, pasangan “kendaraan — banyak roda”, atau yang lebih umum “objek — sifat objek”. Objeknya bisa berupa hewan, dan sifatnya banyak kaki, rata-rata lama hidup, banyak rambut di kepala, dan sebagainya.

Relasi biner R antara himpunan M₁ dan M₂ dapat didefinisikan sebagai berikut: R ⊆ M₁ × M₂. Jadi, relasi biner adalah himpunan pasangan, dan himpunan ini merupakan himpunan bagian dari hasil kali Kartesius dua himpunan tempat relasi tersebut didefinisikan. Dengan demikian, relasi “ayah — anak laki-laki” bisa berupa relasi pada himpunan semua manusia, semua penduduk Indonesia, atau semua penduduk Jakarta. Himpunannya juga bisa dibatasi dengan cara lain, misalnya relasi tersebut kita definisikan pada himpunan semua laki-laki, bukan semua manusia.

Untuk relasi biner, biasanya digunakan penulisan khusus. Alih-alih menulis (a, b) ∈ R, kita bisa menulis aRb. Misalnya, alih-alih (3, 1) ∈ >, kita bisa menulis 3 > 1. Hal yang sama berlaku untuk relasi lain. Jadi, penulisan aSb ekuivalen dengan penulisan (a, b) ∈ S.

Relasi invers

Relasi invers adalah relasi kebalikan dari relasi semula. (Hati-hati, jangan dikacaukan dengan komplemen relasi.) Apa relasi kebalikan dari relasi kurang dari? Lebih dari. Jika relasi kurang dari memuat elemen (4, 7), yaitu 4 < 7, elemen inversnya adalah kebalikannya: 7 > 4, sehingga relasi invers memuat pasangan invers (7, 4).

Jika diberikan relasi R ⊆ M₁ × M₂, relasi invers R⁻¹ dibentuk dengan mengambil semua elemen (a, b) ∈ R dan memasukkan inversnya ke dalam R⁻¹. Jadi, jika relasi R memuat elemen (a, b), relasi R⁻¹ harus memuat elemen (b, a). Sebaliknya juga berlaku: jika R⁻¹ memuat elemen (b, a), relasi R harus memuat elemen (a, b).

Secara formal, relasi R⁻¹ adalah invers dari R jika dan hanya jika berlaku:

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a,b)\in R\iff (b,a)\in R^{-1}$$

Jadi, 6 < 8 jika dan hanya jika 8 > 6. Hal yang sama berlaku untuk pasangan-pasangan lain.

Komposisi relasi

Relasi biner dapat dikomposisikan satu sama lain. Misalkan ada dua relasi: relasi pertama, R, adalah “menjadi ayah dari anak laki-lakinya”, dan relasi kedua, S, adalah “menjadi saudara laki-laki dari saudara perempuannya”. Relasi R memuat pasangan (ayah, anak laki − laki), sedangkan relasi kedua memuat pasangan (saudara laki − laki, saudara perempuan).

Sekarang kita coba mengomposisikan kedua relasi tersebut. Kita memperoleh relasi baru, yang kita beri lambang R ∘ S. Relasi ini memuat elemen (a, c) jika dan hanya jika (a, b) ∈ R dan (b, c) ∈ S. Perhatikan bahwa b muncul pada kedua elemen, sekali di tempat kedua dan sekali di tempat pertama pasangan. Elemen inilah penghubung dalam komposisi.

Contoh: R = {(Agus, Budi), (Wayan, Rizky)} dan S = {(Budi, Siti), (Budi, Dewi), (Rizky, Putri)}. Agus adalah ayah Budi, dan Wayan adalah ayah Rizky. Budi memiliki saudara perempuan Siti dan Dewi, sedangkan Rizky memiliki saudara perempuan Putri.

Sekarang kita komposisikan relasinya: R ∘ S. Kita mencari pasangan dari R yang di tempat anak laki-laki memuat orang yang tercatat sebagai saudara laki-laki dalam relasi S. Misalnya, dua pasangan berikut: (Agus, Budi) dan (Budi, Siti). Budi adalah elemen penghubung yang tidak kita perlukan lagi, dan dari nama-nama yang tersisa kita bentuk pasangan baru: (Agus, Siti). Jadi, relasi R ∘ S memuat pasangan (Agus, Siti). Budi masih memiliki satu saudara perempuan lagi, Dewi, sehingga pasangan ini juga kita tambahkan ke relasi komposisi: (Agus, Dewi). Terakhir, tersisa anak laki-laki Rizky. Ia memiliki saudara perempuan Putri. Jadi, kita memiliki dua pasangan: (Wayan, Rizky) dan (Rizky, Putri). Dari keduanya kita bentuk elemen berikutnya: (Wayan, Putri).

Hasilnya adalah relasi: R ∘ S = {(Agus, Siti), (Agus, Dewi), (Wayan, Putri)}. Apa nama yang cocok untuk relasi ini? Kemungkinan besar “menjadi ayah dari anak perempuannya”.

Sekali lagi, definisi lengkapnya:

$$(a,c)\in (R\circ S)\iff \mathrm{\exists }b(a,b)\in R\wedge (b,c)\in S$$

Catatan: kadang-kadang digunakan penulisan terbalik, artinya untuk definisi yang sama digunakan S ∘ R, bukan R ∘ S.