resume materi relasi : matematika diskrit
RELASI
Pengertian Relasi
Berdasarkan pengertian uraian di atas dan dari
contoh, maka jika p(a,b) bernilai benar dikatakan bahwa “a
berelasi dengan b” dan dinyatakan sebagai a R b. Sebaliknya
jika p(a,b) bernilai tidak benar (salah) dikatakan bahwa “a tidak
berelasi dengan b” dan dinyatakan sebagai aR b Dengan demikian suatu relasi R
membutuhkan adanya suatu fungsi pernyataan p(a,b) yang
mendefinisikan suatu relasi dari A ke B.
Ada penulis yang menyebut fungsi pernyataan p(x,y) sebagai
relasi.
Definisi
Jika A dan B adalah dua himpunan sembarang, maka suatu relasi R
dari A ke B adalah sembarang subset dari A x B, termasuk himpunan kosong.
Yaitu R Í A x B. Relasi R ini
dinyatakan sebagai :
R = { (a,b) / a berelasi
dengan b }
= { (a b) / a R b }
Relasi R dari himpunan A ke
himpunan B juga dikatakan sebagai Relasi binair yaitu suatu
cara untuk menentukan pasangan (a,b) dalam A x B, sehingga
dikatakan “a berelasi dengan b” ditulis a R b atau
(a,b) Î R . Jika dikatakan “a tidak berelasi dengan b”
ditulis aR b atau (a,b) Ï R. Relasi dari himpunan A ke
himpunan A (ke dirinya sendiri) disebut relasi pada A atau a
R a.
Relasi R dikatakan “determinatif”
pada A jika untuk setiap a dan b berada
dalam A. Misalkan A = himpunan bilangan-bilangan
alam, maka relasi “kelipatan” adalah relasi yang determinatif. Sedangkan
relasi “mencintai” adalah tidak determinatif, sebab pernyataan “9 mencintai
3” tidak bernilai benar atau bernilai salah. Dalam hal ini yang dibicarakan
adalah relasi-relasi yang determinatif saja.
Suatu relasi juga didefinisikan antara
anggota-anggota diberlainan himpunan. Misalkan R suatu relasi
dari A ke B. Jadi R adalah
himpunan pasagan- pasangan elemen-elemen (a,b) dimana a A dan bB, dan Rmerupakan himpunan bagian dari A x B.
Domain (daerah asal) dari relasi R adalah
himpunan dari semua elemen-elemen pertama dalam pasangan-pasangan terurut
didalam R, yaitu :
D = { a / a A, (a, b) R }
Jangkauan/range dari relasi R terdiri
atas semua elemen-elemen kedua yang muncul dalam pasangan-pasangan terurut dalam R,
yaitu
E = { b / bB, (a, b) R }
Jadi domain suatu relasi dari A ke B
ditulis D , merupakan himpunan bagian dari A yaitu D Í Adan
jangkauan dari R ditulis E adalah himpunan bagian dari B, yaitu E Í B.
Contoh :
Diketahui : A = {1, 2, 3,
4}, B = {a, b, c} .
Maka R = {(2, a),
(3, c), (4, a)} adalah suatu relasi.
|
Perhatikan
bahwa R Í A x B
Domain dari R = D =
{2, 3, 4}
Jangkauan dari R = E =
{a, c}
Contoh :
Misalkan
relasi R dalam bilangan-bilangan riil didefinisikan oleh
kalimat terbuka “4x2 + 9y2 = 36”. Relasi Rditunjukkan
pada diagram koordinat R # x R # dibawah
ini :
R# adalah
himpunan semua bilangan-bilangan riil. Domain dari R adalah
selang tertutup [-3, 3] dan jangkauan dari R adalah selang
tertutup [-2, 2].
Untuk
setiap pasangan dua himpunan A dan himpunan B,
selalu berlaku A Í B atau A Ë B atau
sebaliknya.
Perkawinan
merupakan suatu relasi dari himpunan Pria (=P) ke himpunan wanita (=W) dalam
semesta himpunan orang-orang. Jika ada seorang pria P makaberlaku bahwa P
telah menikah dengan W atauP tidak menikah dengan W.
Kalimat
“x lebih kecil dari y” ditulis x < y adalah
suatu relasi pada himpunan bilangan-bilangan riil. Jika diberikan pasangan
terurut (x,y) maka selalu berlaku x < y atau x </ y atau
juga sebaliknya.
Misalkan R suatu
relasi dari A = {1, 2, 3} ke B = {a, b}
dengan R = {(1, a), (1, b),(3,a)},
maka 1Ra, 2b, 3Ra dan 3b
Relasi R dapat
ditunjukkan dengan diagram koordinat A x B berikut
ini :
A x B = {(1, a), (1, b),
(2, a), (2, b), (3, a), (3, b)}
R Í A x B
R = {(1, a), (1, b), (3, a)}
Ambil
himpunan A = {1, 2, 3} seperti di atas. Relasi R pada A adalah
himpunan semua pasangan dalam A x A.
Disini R = A x A.
Relasi Identitas
Relasi identitas pada himpunan A ditulis IA atau A adalah himpunan pasangan-pasangan (a, a) dengan a A, ditulis IA = {(a, a) /a A}. Relasi identitas ini juga
disebut relasi diagonal, sebab anggota-anggota dari relasinya merupakan
diagonal dari diagram koordinatnya.
Misalkan A =
{1, 2, 3}
A x A = {(1, 1), (1, 2), (1,
3), (2, 1), (2, 2), (2, 3),(3, 1),
(3, 2), (3, 3)}
IA =
{(1, 1), (2, 2), (3, 3)}
Relasi Kosong
Relasi kosong dari himpuanan A ditulis , adalah himpunan kosong dari A x A .
Dimaksud relasi disini adalah himpunan kosong dari A x A.
Contoh :
A = maka A x A =
R suatu relasi dari A ke A adalah R Í A x A
R =
Relasi Invers
Misalkan R suatu relasi dari himpunan A ke
himpunan B. Invers dari R ditulis adalah suatu relasi dari himpunan B ke
himpunan A, sedemikian hingga tiap pasangan terurut pada jika urutan anggota-anggotanya dibalik
merupakan anggota dari R.
Jadi = {(b,a) / (a,b) Î R}
Contoh :
Relasi R pada A = {1, 2, 3}
didefinisikan sebagai R = {(1, 2), (1, 3), (2, 3)},
maka = {(2, 1), (3, 1), (3, 2)}
Representasi Relasi
Suatu relasi dapat presentasikan dalam berbagai cara, diantaranya
melalui grafik pada bidang XOY, tabel, melalui matriks dan melalui graf.
Penyajian
dalam bentuk grafik
Misal R suatu relasi dari A ke B. Himpunan A digambarkan pada
sumbu mendatar X dan himpunan B digambarkan pada sumbu tegak y yang memotong
sumbu x di titik 0. Setiap pasangan terurut di A x B dinyatakan oleh satu
titik pada bidang XOY. Dengan demikian R adalah himpunan titik-titik (a,b)
pada bidang XOY dimana (a,b) R.
Contoh 1 :
Relasi R dari A =
{a, b, c, d, e} ke B = {1, 2, 4} didefinisikan sebagai
berikut: R =
{(a,1),(a,4),(b,2),(c,2),(c,4),(d,1)}.
Jawab:
Grafik R dinyatakan
oleh titik-titik hitam pada grafik di atas.
Contoh 2 :
Relasi R1 ,
R2 dan R3 pada himpunan bilangan-bilangan riel R diberikan oleh: 2
2
a). R1 = {(x,y)
/ +y0}
b). R2 = {(x,y)
/+ 1}
c). R3 = {(x,y)
/ +16}
Jawab:
a). Grafik
R1 daerah yang diarsir adalah :
b). Grafik R2,
daerah yang diarsir adalah :
c). Grafik R3 daerah
yang diarsir adalah sebagai berikut :
Representasi relasi dengan table
Jika relasi direpresentasikan dengan table, maka kolom pertama
table menyatakan daerah asal, sedangkan kolom kedua menyatakan daerah hasil
Sebagai contoh :
Table 1.3
Representasi relasi dengan matriks
Misalkan R adalah relasi dari A = {a1, a2,
. . .,am} dan B = {b1, b2, . . .,bn},
relasi R dapat disajikan dengan matriks M = [mij]
Yang dalam hal ini :
Dengan kata lain, elemen matriks pada posisi (i,j) bernilai 1
jika ai dihubungkan dengan bj dan bernilai 0
jika ai tidak dihubungkan dengan bj.
Relasi R pada table 1 dapat dinyatakan dengan matriks :
yang dalam hal ini, a1 = Amir, a2 =
Budi, a3 = Cecep, dan b1 = INF0221
Representasi relasi dengan graf berarah
Representasi dengan
graph berarah (directed graph atau digraph) merupakan representasi relasi
secara grafis (graph akan dibahas pada bab tersendiri). Tiap elemen himpunan
dinyatakan dengan sebuah titik (simpul atau vertek), dan tiap pasangan
berurutan dinyatakan dengan busur atau (arc) yang arahnya ditunjukkan
dengan sebuah panah. Dengan kata lain, jika (a,b) R, maka sebuah busur dibuat dari simpul a
ke simpul b. Simpul a disebut simpul asal (initial vertek) dan simpul b
disebut simpul tujuan (terminal vertek).
Pasangan terurut
(a,a) dinyatakan dengan busur dari simpul a ke simpul a sendiri. Busur
semacam ini disebut gelang atau kalang (loop). Sebagai contoh
misalnya 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}. R direpresentasikan dengan graf berarah pada gambar
berikut :
Sifat-sifat dari relasi biner
1.
Refleksif (reflexive)
Relasi R pada himpunan A disebut
refleksif jika (a,a) R untuk setiap a A
Contoh 1:
Misalkan A = {1,2,3,4}, dan relasi R
dibawah ini didefinisikan pada himpunan A, maka
a. 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).
b. R =
{(1,1),(2,2),(2,3),(4,2),(4,3),(4,4)} tidak bersifat reflektif karena
(3,3) R
Contoh 2 :
Relasi ”habis dibagi” pada himpunan
bilangan bulat positif bersifat refleksif karena setiap bilangan bulat
positif habis dibagi dengan dirinya sendiri, sehingga (a,a) R untuk setiap a A.
Ditinjau dari representasi relasi, relasi
bersifat refleksif mempunyai matriks yang elemen diagonal utamanya semua
bernilai 1, atau mii = 1, untuk i = 1,2,...,n
Sedangkan graf berarah dari relasi yang bersifat refleksif dicirikan
dengan adanya gelang pada setiap simpulnya.
2. Setangkup (symmetric)
Relasi R pada himpunan A disebut
setangkup jika untuk semua a,b A, jika (a,b) R, maka (b,a) R. Sebaliknya, R disebut tak setangkup(antisymmetric) jika untuk
a,b A, jika (a,b) R dan ab maka (b,a) R
Contoh 1:
Misalkan A={1,2,3,4} dan relasi R dibawah
ini didefinisikan pada himpunan A, maka,
a. 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, disini (1,2) dan (2,1) R, begitu juga (2,4) dan (4,2) R
b. R
= {(1,1),(2,3),(2,4),(4,2)}tidak bersifat setangkup karena (3,2) R
Contoh 2 :
Relasi ”habis dibagi” pada himpunan
bilangan bulat positif tidak bersifat setangkup karena jika
a habis dibagi b , b tidak habis dibagi a, kecuali jika a=b. Sebagai contoh,
2 habis membagi 1 tetapi 1 tidak habis membagi 2, karena itu (a,b) R tetapi (b,a) R
Ditinjau dari representasi relasi, relasi
yang bersifat setangkup mempunyai matriks yang elemen-elemen dibawah diagonal
utama merupakan pencerminan dari elemen-elemen diatas diagonal utama, atau mij =
mji, 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.
3. Menghantar
(transitif)
Relasi R pada himpunan A disebut
menghantar bilamana (a,b) R dan (b,c) R, maka (a,c) R, untuk a, b, c A.
Contoh
:
Misalkan A = { 1, 2,
3, 4 }, dan relasi R di bawah ini didefinisikan pada himpunan A, maka
a. R = { (2,1),
(3,1), (3,2), (4,1), (4,2), (4,3) }bersifat menghantar. Lihat pada table
berikut :
b. R
= { (1,1), (2,3), (2,4), (4,2) } maka tidak bersifat menghantar karena (2,4)
dan (4,2) R, tetapi (2,2) R, begitu juga (4,2) dan (2,3) R, tetapi (4,3) R.contoh : Relasi "habis dibagi" pada himpunan
bilangan bulat positif menghantar. misalkan bahwa a habis membagi b dan b
habis membagi c. Maka terdapat bilangan positif m dan n sedemikian sehingga a
= mb dan b = nc. Disini a = mnc, sehingga a habis membagi c. Jadi relasi
"habis membagi" bersifat menghantar.Ditinjau dari representasi
relasi, relasi yang bersifat menghantar tidak mempunyai ciri khusus pada
matrik representasinya. Tetapi yang bersifat 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.
Mengkombinasi Relasi
Karena relasi biner
merupakan himpunan pasangan terurut, maka operasi himpunan seperti irisan,
gabungan, selisih dan beda setangkup antara dua relasi atau lebih juga
berlaku. Hasil operasi tersebut juga berupa relasi. Dengan kata lain, jika R1 dan
R2
masing – masing adalah relasi dari himpunan A ke himpunan B, maka R1 R2 , R1 R2 ,
R1 - R2, R1 R2 juga adalah relasi
dari A ke B.
Contoh :
Misalkan A = { a, b,
c } dan B = { a, b, c, d }. Relasi R1 = { (a,a), (b,b),
(c,c), dan relasi R2 = { (a,a), (a,b), (a,c), (a,d) } adalah
relasi dari A ke B. kita dapat mengkombinasikan ke dua buah relasi tersebut
untuk memperoleh
R1 R2
= { (a,a) }
R1 R2 =
{ (a,a), (b,b), (c,c), (a,b), (a,c), (a,d) }
R1 -
R2 =
{ (b,b), (c,c) }
R2 –
R1
= { (a,b), (a,c), (a,d) }
R1 R2
= { (b,b), (c,c), (a,b), (a,c), (a,d) }
Jika relasi R1 dan
R2 masing – masing dinyatakan dengan matriks MR1 dan
MR2, maka matriks yang menyatakan gabungan dan irisan dari kedua
relasi tersebut adalah
MR1R2 = MR1R2 dan MR1R2 = MR1R2
Yang dalam hal ini,
operator “” berarti “atau” dan “” berarti “dan”.
Contoh :
Misalkan bahwa
relasi R1 dan R2 pada himpunan A dinyatakan
oleh matriks
dan
Maka matriks yang
menyatakan MR1R2 dan MR1R2 adalah
Komposisi Relasi
Cara lain
mengkombinasikan relasi adalah mengkomposisikan dua buah relasi atau lebih.
Komposisi relasi analog dengan komposisi fungsi.
Misalkan R adalah
relasi dari himpunan A ke himpunan B, dan S adalah relasi dari himpunan B ke
himpunan C. komposisi R dan S, dinotasikan dengan R o S, adalah relasi dari A
ke C yang didefinisikan oleh
R o S = { (a,c)}│
a A, c C, dan untuk beberapa b B, (a,b) R dan (b,c) S }
Contoh :
Misalkan R = {
(1,2), (1,6), (2,4), (3,4), (3,6), (3,8) } adalah relasi dari himpunan { 1,
2, 3 } ke himpunan { 2, 4, 6, 8 } dan S = { (2,u), (4,s), (4,t), (6,t), (8,u)
} adalah relasi dari { 2, 4, 6 } ke himpunan { s, t, u }. Maka komposisi
relasi R dan S adalah R o S = { (1,u), (1,t), (2,s), (2,t), (3,s), (3,t),
(3,u) }
Jika relasi R1 dan
R2 masing – masing dinyatakan dengan matriks MR1 dan
M R2, maka matriks yang menyatakan komposisi dari kedua
relasi tersebut adalah
MR1 o R2 =
MR1 . MR2
Yang dalam hal ini
operator “.” Sama seperti pada perkalian matriks biasa, tetapi dengan
mengganti tanda kali dengan “” dan tanda tambah dengan “”.
Contoh :
Misalkan bahwa
relasi R1 dan R2 pada himpunan A dinyatakan
oleh matrik :
dan
Maka matriks yang
menyatakan R1 o R2 adalah
|
Komentar
Posting Komentar