Logika Informatika : Sifat Kalimat, Pohon Semantik, dan Pengujian 2 Kalimat, beserta Contoh Soal

Matematika Diskrit : Relasi, Sifat Relasi, dan Contoh Soal

Definisi Relasi

Relasi biner R antara himpunan A dan B adalah himpunan bagian dari perkalian kartesian A x B.

Notasi



A disebut daerah asal (domain) dari R
B disebut daerah hasil (codomain) dari R

Contoh

Misalkan P={2,3,4} dan Q={2,4,8,9,15}. Jika kita definisikan relasi R dari P dan Q dengan

Relasi pada himpunan A adalah relasi A x A

Contoh

Misalkan R adalah relasi pada A ={2,3,4,8,9} yang didefinisikan oleh



maka R = {(2,2),(2,4),(2,8),(3,3),(3,9)}

Representasi Relasi

Matriks

Misalkan R adalah relasi dari



Relasi R dapat disajikan dengan matriks berikut:

            

Contoh

Misalkan P={2,3,4} dan Q={2,4,8,9,15}. Maka

Sehingga relasi dapat dituliskan:

Didapat:

Latihan 1

Diberikan A = {1,2,3} dan B = {a,b,c}. Relasi A dan B adalah

R = {(1,a),(1,b),(2,b),(3,a),(3,b),(3,c)}

Representasikan relasi di atas dalam bentuk matriks.

Relasi Inversi

Misalkan R adalah relasi dari himpunan A ke B. Inversi dari relasi R, dilambangkan dengan R^-1 , adalah relasi dari B ke A yang didefinisikan berikut 

Representasi matriks dari R^-1 adalah transpose dari representasi matriks untuk R

Contoh

Misalkan P={2,3,4} dan Q={2,4,8,9,15}. Jika kita definisikan relasi R dari P dan Q dengan

maka 

R^-1 dapat didefinisikan: 

maka 

Sifat-sifat Relasi

Refleksif

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

Contoh:

Misalkan A = {1,2,3} dan relasi R = {(1,1), (1,3), (2,2), (2,1), (2,3), (3,3)} adalah relasi refleksif.

Latihan 2

Diberikan relasi R didefinisikan pada himpunan bilangan bulat positif sebagai berikut

• Apakah relasi ini refleksif ? 

Setangkup (symmetric) 

Relasi R pada himpunan A disebut setangkup jika

Contoh

Misalkan A = {1,2,3,4} dan relasi R didefinisikan sebagai R = {(1,1),(1,2),(2,1),(2,3),(3,2),(4,4)}. Maka R adalah relasi setangkup.

Tolak setangkup (antisymmetric) 

Relasi R pada himpunan A disebut tolak setangkup jika

Contoh: 

Misalkan A = {1,2,3} dan relasi R didefinisikan sebagai R = {(1,1),(2,2),(1,2)}. 

Maka R adalah relasi tolak setangkup.

Latihan 3

Misalkan A = {1,2,3,4} dan relasi R didefinisikan sebagai

R : x + y = 5 untuk x,y anggota A.

• Apakah R adalah relasi setangkup? 
• Apakah R adalah relasi tolak setangkup?

Menghantar (transitive) 

Relasi R pada himpunan A disebut transitive jika

Contoh: 

Misalkan A = {1,2,3,4} dan relasi R didefinisikan sebagai R = {(1,2),(1,3),(2,3),(3,4),(1,4),(2,4)}.

Maka R adalah relasi transitive.

Kesetaraan (equivalence relation)

Relasi R pada himpunan A disebut relasi kesetaraan jika ia reflektif, setangkup, dan menghantar.

 

Contoh

Jika A = {1,2,3,4} dan relasi R didefinisikan sebagai R = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4)}. Maka R adalah relasi kesetaraan.