Matematika Diskrit : Sifat-Sifat Relasi

📋 Daftar Isi

Refleksif (reflexive)

Relasi R pada himpunan A disebut refleksif jika (a, a) ∈ R untuk setiap a ∈ A.

Relasi R pada himpunan A tidak refleksif jika ada a ∈ A sedemikian sehingga (a, a) ∉ R.

Perhatikan bahwa relasi yang irrefleksif bukan berarti tidak refleksif. Relasi irrefleksif jika jika (a, a) ∉ R untuk setiap a ∈ A

Contoh

Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka :

Relasi R = {(1, 1), (1, 3), (2, 1), (2, 2), (3, 3), (4, 2), (4, 3), (4, 4) } bersifat refleksif karena terdapat elemen relasi yang berbentuk (a, a), yaitu (1, 1), (2, 2), (3, 3), dan (4, 4)
Relasi R = {(1, 1), (2, 2), (2, 3), (4, 2), (4, 3), (4, 4) } tidak bersifat refleksif karena (3, 3) ∉ A

Relasi yang bersifat refleksif mempunyai matriks yang elemen diagonal utamanya semua bernilai 1, atau m_i_i = 1, untuk i = 1, 2, …, n

\[ \begin{vmatrix} 1 & \space & \space & \space & \space \\ \space & 1 & \space & \space & \space \\ & \space & \ddots & \space & \space \\ & \space & \space & 1 & \space \\ & & & & 1\\ \end{vmatrix} \]

Graf berarah dari relasi yang bersifat refleksif dicirikan adanya gelang pada setiap simpulnya.

Menghantar (transitive)

Relasi R pada himpunan A disebut menghantar jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk a, b, c ∈ A.

Relasi yang bersifat menghantar tidak mempunyai ciri khusus pada matriks representasinya

Sifat menghantar pada graf berarah ditunjukkan oleh : jika ada busur dari a ke b dan dari b ke c, maka juga terdapat busur berarah dari a ke c

Contoh

Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka :
R = { (2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3) } bersifat menghantar.

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)

R = { (1, 1), (2, 3), (2, 4), (4, 2) } tidak manghantar karena (2, 4) dan (4, 2) ∈ R, tetapi (2, 2) ∉ R, begitu juga (4, 2) dan (2, 3) ∈ R, tetapi (4, 3) ∉ R.

Relasi R = { (1, 1), (2, 2), (3, 3), (4, 4) } jelas menghantar

Relasi R = { (1, 2), (3, 4) } menghantar karena tidak ada (a, b) ∈ R dan (b, c) ∈ R sedemikian sehingga (a, c) ∈ R.

Relasi yang hanya berisi satu elemen seperti R = {(4, 5)} selalu menghantar.

Setangkup (symmetric) dan Tolak-Setangkup (antisymmetric)

Relasi R pada himpunan A disebut setangkup jika (a, b) ∈ R, maka (b, a) ∈ R untuk a, b ∈ A.

Relasi R pada himpunan A tidak setangkup jika (a, b) ∈ R sedemikian sehingga (b, a) ∉ R.

Relasi R pada himpunan A sedemikian sehingga (a, b) ∈ R dan (b, a) ∈ R hanya jika a = b untuk a, b ∈ A disebut tolak-setangkup.

Relasi R pada himpunan A tidak tolak-setangkup jika ada elemen berbeda a dan b sedemikian sehingga (a, b) ∈ R dan (b, a) ∈ R.

Relasi yang tidak setangkup bukan berarti tolak-setangkup

Contoh

Misalkan A = {1, 2, 3, 4}, dan relasi R di bawah ini didefinisikan pada himpunan A, maka :

Relasi R = { (1, 1), (1, 2), (2, 1), (2, 2), (2, 4), (4, 2), (4, 4) } bersifat setangkup karena jika (a, b) ∈ R maka (b, a) juga ∈ R. Di sini (1, 2) dan (2, 1) ∈ R, begitu juga (2, 4) dan (4, 2) ∈ R.
Relasi R = { (1, 1), (2, 3), (2, 4), (4, 2) } tidak setangkup karena (2, 3) ∈ R, tetapi (3, 2) ∉ R.
Relasi R = { (1, 1), (2, 2), (3, 3) } tolak-setangkup karena 1 = 1 dan (1, 1) ∈ R, 2 = 2 dan (2, 2) ∈ R, dan 3 = 3 dan (3, 3) ∈ R. Perhatikan bahwa R juga setangkup.
Relasi R = { (1, 1), (1, 2), (2, 2), (2, 3) } tolak-setangkup karena (1, 1) ∈ R dan 1 = 1 dan, (2, 2) ∈ R dan 2 = 2 dan. Perhatikan bahwa R tidak setangkup.
Relasi R = {(1, 1), (2, 4), (3, 3), (4, 2) } tidak tolak-setangkup karena 2 ≠ 4 tetapi (2, 4) dan (4, 2) anggota R.
Relasi R = {(1, 2), (2, 3), (1, 3) } tidak setangkup tetapi tolak-setangkup.
Relasi R = {(1, 1), (2, 2), (2, 3), (3, 2), (4, 2), (4, 4)} tidak setangkup dan tidak tolak-setangkup. R tidak setangkup karena (4, 2) ∈ R tetapi (2, 4) ∉ R. R tidak tolak-setangkup karena (2, 3) ∈ R dan (3, 2) ∈ R tetapi 2 ≠ 3.

Relasi yang bersifat setangkup mempunyai matriks yang 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 :

Sedangkan graf berarah dari relasi yang bersifat setangkup dicirikan oleh: jika ada busur dari a ke b, maka juga ada busur dari b ke a.

Matriks dari relasi tolak-setangkup mempunyai sifat yaitu jika m_ij = 1 dengan i ≠ j, maka m_ji = 0. Dengan kata lain, matriks dari relasi tolak-setangkup adalah jika salah satu dari m_ij = 0 atau m_ji = 0 bila i ≠ j

Sedangkan graf berarah dari relasi yang bersifat tolak-setangkup dicirikan oleh: jika dan hanya jika tidak pernah ada dua busur dalam arah berlawanan antara dua simpul berbeda