2. matematika diskrit - relasi

8/2/2019 2. Matematika Diskrit - Relasi

1/22

Matematika Diskrit

Relasi


2/22

Definisi

Definisi 1

n-pasangan terurut(a1, a2, ..., an) adalahsekumpulan anggota terurut yang memiliki a1

sebagai anggota pertama, a2 sebagai anggotakedua, ... dan an sebagai anggota ke-n.

3Matematika Diskrit | Relasi | oleh: Onggo Wiryawan | @_Onggo


3/22

Definisi

Definisi 2

Misalkan A dan B suatu himpunan.

Hasil kali Cartesian dari A dan B, dinotasikan

dengan A B, adalah himpunan dari seluruhpasangan terurut (a, b), dengan a A dan b B.

Sehingga,

A B = {(a,b) | a A b B}



4/22

Definisi

Contoh

Misalkan A = {1, 2} dan B = {a, b, c}.

A B = {(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)}

Catatan

A B B A



5/22

Definisi

Definisi

Misalkan A dan B suatu himpunan.

Suatu relasi biner dari A ke B adalah

subhimpunan dari A B. Artinya, suatu relasi biner dari A ke B adalah

sebuah himpunan R berupa pasangan terurut

yang anggota pertamanya berasal dari A, dananggota keduanya berasal dari B.



6/22

Definisi

Notasi

a R b

(a,b) R

a direlasikan ke b oleh relasi R.

Contoh

A = {0, 1, 2}, B = {a, b}, lalu didefinisikan bahwa

{(0,a), (0,b), (1,a), (2,b)},ini berarti 0 berrelasi dengan a, tapi 2 tidakberrelasi dengan a.



7/22

Definisi

Contoh

A adalah himpunan kota di Indonesia.B adalah himpunan pulau di Indonesia.

Didefinisikan relasi R dimana (a,b) adalah anggota Rjika kota a berada di pulau b.

Beberapa contoh anggota R adalah :(Lampung, Sumatera),

(Samarinda, Kalimantan),(Cirebon, Jawa),(Mataram, Lombok)



8/22

Definisi

Relasi dapat direpresentasikan dengan gambar,

atau tabel.

Contoh

A = {0, 1, 2}, B = {a, b}, jika {(0,a), (0,b), (1,a), (2,b)},


0

1

2

a

b

R a b

0

1

2


9/22

Definisi

Definisi

Suatu relasi pada suatu himpunan A adalah suatu relasidari A ke A.

Fungsi sebagai Relasi Jika R adalah suatu relasi dari A ke B sedemikian

sehingga setiapanggota di A adalah anggotapertama dari pasangan terurut pada R, maka R

adalah suatu fungsi. Dengan memasangkan suatu aanggota dari A ke tepat suatu b anggota dari Bsedemikian sehingga (a,b) R.



10/22

Sifat Relasi

Definisi

Suatu relasi R pada suatu himpunan A disebutrefleksifjika (a,a) R untuk a A.



11/22

Sifat Relasi

Contoh

Perhatikan relasi-relasi berikut pada himpunan {1, 2, 3,4}

R1 = {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)} R2 = {(1,1), (1,2), (2,1)}

R3 = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}

R4 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3),

(3,4), (4,4)}Dari kelima relasi tersebut, hanya R3 dan R4 yangmerupakan relasi refleksif.



12/22

Sifat Relasi

Definisi

Suatu relasi R pada suatu himpunan A disebutsimetrisjika (b,a) R jika (a,b) R untuk a, b

A. Suatu relasi R pada suatu himpunan A disebut

antisimetrisjika (a,b) R dan (b,a) R hanyajika a = b untuk a, b A.



13/22

Sifat Relasi

Contoh

Perhatikan relasi-relasi berikut untuk suatuhimpunan bilangan bulat

R1= {(a,b) | a b}

R2 = {(a,b) | a = b}

R3 = {(a,b) | a = b + 1}

Dari ketiga relasi tersebut, hanya R2 yangmerupakan relasi simetris. Sedangkan relasi R1, R2dan R3 merupakan relasi antisimetris.



14/22

Sifat Relasi

Definisi

Suatu relasi R pada suatu himpunan A disebuttransitifjika (a,b) R dan (b,c) R maka (a,c) R

untuk a, b, c A.



15/22

Sifat Relasi

Contoh

Perhatikan relasi-relasi berikut untuk suatuhimpunan bilangan bulat

R1= {(a,b) | a b} R2 = {(a,b) | a = b}

R3 = {(a,b) | a = b + 1}

Dari ketiga relasi tersebut, hanya R2 yangmerupakan relasi simetris. Sedangkan relasi R1, R2dan R3 merupakan relasi antisimetris.



16/22

Sifat Relasi

Contoh

R1 = {(1, 1), (1,2), (2,1), (2, 2), (3,4), (4,1), (4, 4)}

R2 = {(1, 1), (1, 2), (2,1)}

R3 = {(1, 1), (1,2), (1,4), (2,1), (2,2), (3, 3), (4,1), (4, 4)}

R4 = {(2, 1), (3,1), (3, 2), (4,1), (4, 2), (4, 3)}

R5 = {(1, 1), (1, 2), (1, 3), (1,4), (2, 2), (2, 3), (2,4), (3,

3), (3,4), (4, 4)}R6 = {(3, 4)}.



17/22

Sifat Relasi

Contoh

Refleksifadalah

R3 = {(1, 1), (1,2), (1,4), (2,1), (2,2), (3, 3), (4,1), (4, 4)}

R5 = {(1, 1), (1, 2), (1, 3), (1,4), (2, 2), (2, 3), (2,4), (3,3), (3,4), (4, 4)}



18/22

Sifat Relasi

Contoh

Simetris adalah

R2 = {(1, 1), (1, 2), (2,1)}

R3 = {(1, 1), (1,2), (1,4), (2,1), (2,2), (3, 3), (4,1), (4, 4)}



19/22

Sifat Relasi

Contoh

AntiSimetris adalah

R4 = {(2, 1), (3,1), (3, 2), (4,1), (4, 2), (4, 3)}

R5 = {(1, 1), (1, 2), (1, 3), (1,4), (2, 2), (2, 3), (2,4), (3,3), (3,4), (4, 4)}

R6 = {(3, 4)}.



20/22

Sifat Relasi

Contoh

Transitifadalah

R4 = {(2, 1), (3,1), (3, 2), (4,1), (4, 2), (4, 3)}

R5 = {(1, 1), (1, 2), (1, 3), (1,4), (2, 2), (2, 3), (2,4), (3,3), (3,4), (4, 4)}

R6 = {(3, 4)}



21/22

Sifat Relasi

ContohR1 = {(a, b) | a < b}(refleksif, antisimetris, transitif)R2 = {(a, b) | a > b}

(antisimetris , transitif)R3 = {(a, b) | a = b atau a = -b}(refleksif, simetris , transitif)R4 = {(a, b) | a = b}(refleksif, simetris, antisimetris , transitif)

R5 = {(a, b) | a = b + 1}(antisimetris)R6 = {(a, b) | a + b < 3}(simetris)



22/22

Latihan

1. Misal A = {1, 2, 3, 4, 5}, B = {0, 3, 6}, tentukan

a. A B c. A B

b. A B d. B A

2. Misal A dan B adalah himpunan, buktikana. (A B) A

b. A (A B)

c. (A B) A

Matematika Diskrit | Relasi | oleh: Onggo Wiryawan | @_Onggo 23

2. matematika diskrit - relasi

Documents