Matematika Diskrit

22

2.12. Relasi Ekivalen Definisi : Sebuah relasi pada sebuah himpunan A disebut relasi ekivalen jika dan hanya jika relasi tersebut bersifat refleksif, simetris dan transitif. Dua elemen yang dihubungkan dengan relasi ekivalen disebut ekivalen. Contoh 35: Misal himpunan A adalah himpunan string kata dalam kosa kata bahasa Indonesia. R adalah relasi pada himpunan A, dimana untuk Aba ∈, , a R b (a berelasi dengan b) jika dan hanya jika l(a) = l(b), dimana l(x) adalah panjang kata x. Apakah R adalah relasi ekivalen?

(i) Syarat relasi R pada himpunan A disebut refleksif : jika (a, a) ∈ R untuk setiap a ∈ A ......(*)

Karena untuk setiap string kata a berlaku l(a) = l(a), maka syarat (*) terpenuhi, sehingga R bersifat refleksif

(ii) Syarat R bersifat simetris :

jika untuk semua a, b ∈ A, jika (a, b) ∈ R, maka (b, a) ∈ R ...(**) Karena untuk setiap string kata a, b berlaku : jika l(a)=l(b), maka l(b) = l(a), maka syarat (**) terpenuhi, sehingga R bersifat simetris.

(iii) Syarat R bersifat transitif:

jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk a, b, c ∈ A ..(***) Karena untuk setiap string kata a, b, c berlaku : jika l(a) = l(b) dan l(b) = l(c), maka l(a) = l(c), maka syarat (***) terpenuhi, sehingga R bersifat transitif.

Jadi R adalah relasi ekivalen

2.12.1. Klas Ekivalen Misal A adalah himpunan semua mahasiswa yang merupakan lulusan dari berbagai SMU. Misal relasi R pada A adalah semua pasangan (x, y) dimana x dan y adalah lulusan dari SMU yang sama. Untuk seorang mahasiswa x, kita dapat membentuk himpunan semua mahasiswa yang ekivalen dengan x. Himpunan tersebut terdiri dari semua mahasiswa yang lulus dari SMU yang sama dengan x. Himpunan ini disebut klas ekivalen dari relasi R. Misal R adalah relasi ekivalen pada himpunan A. himpunan semua elemen yang mempunyai relasi dengan elemen a ( Aa∈ ) disebut klas ekivalen dari a. Klas ekivalen dari a berdasarkan relasi R dinotasikan dengan [ ]Ra . Jika R adalah relasi ekivalen pada himpunan A, klas ekivalen dari elemen a adalah : [ ] ( ){ }Rsasa R ∈= ,

ZK Abdurahman Baizal

Sekolah Tinggi Teknologi Telkom

Matematika Diskrit

23

Jika , maka b disebut representative dari klas ekivalen. [ ]Rab∈Contoh : Kita lihat lagi contoh 2,

( ){ }bababaR −=== atau , adalah relasi pada himpunan bilangan bulat A

Klas ekivalen dari sebuah bilangan integer tertentu dalam relasi ekivalen R adalah : [ ] { }aaa R ,−= contoh : [ ]R7 = {-7, 7}, [ = {-5, 5}, ]R5− [ ]R0 = {0}

2.13. Partial Ordering Sebuah relasi R pada sebuah himpunan S disebut partial order jika relasi ini bersifat bersifat refleksif, antisimetris, dan transitif. Pasangan dari himpunan S bersama dengan sebuah partial order R disebut partially ordered set (poset) atau himpunan terurut parsial, dinotasikan dengan (S, R). Contoh 37. Tunjukkan bahwa relasi lebih besar atau sama dengan adalah partial order pada himpunan bilangan bulat!

R dapat kita definisikan sebagai ( ){ }babaR ≥= , (i) Untuk semua bilangan bulat tentu saja berlaku , yang artinya untuk semua

bilangan bulat a, maka (a, a) aa ≥

R∈ . Sehingga R bersifat refleksif (ii) Jika berlaku dan , maka tentu a = b, yang artinya (a, b) dan (b, a) aa ≥ ab ≥ R∈

→ (a = b). Sehingga R bersifat antisimetris (iii)Jika dan maka , yang berarti jika (a, b) dan (b, c) ba ≥ ab ≥ ca ≥ R∈ maka (a,

c) R∈ . Sehingga R bersifat transitif.

Karena R bersifat refleksif, antisimetris dan transitif, maka R adalah Partial Order. Contoh 38. Z+ = himpunan bilangan bulat positif | = relasi habis membagi

Apakah (Z+, | ) adalah poset?

jika (a, a) ∈ R untuk setiap a ∈ A ......(*) (i) Syarat relasi R pada himpunan A disebut refleksif :

jika (a, a) ∈ R untuk setiap a ∈ A ......(*) Kita bisa melihat bahwa a habis membagi a (a | a) untuk semua bilangan bulat positif, maka syarat (*) terpenuhi, sehingga R bersifat refleksif

(ii) Syarat R bersifat simetris : jika untuk semua a, b ∈ A, (a, b) ∈ R dan (b, a) ∈ R hanya jika a = b.

Jika a dan b bilangan bulat positif dengan a | b dan b | a, maka tentulah a = b, sehingga syarat (**) terpenuhi, dengan demikian R bersifat antisimetris

ZK Abdurahman Baizal

Sekolah Tinggi Teknologi Telkom

Matematika Diskrit

24

(iii) Syarat R bersifat transitif:

jika (a, b) ∈ R dan (b, c) ∈ R, maka (a, c) ∈ R, untuk a, b, c ∈ A ..(***) Misal a|b dan b|c, maka terdapat bilangan bulat positif k dan l sedemikian hingga b = ak dan c = bl, dengan demikian c = a(kl), sehingga a | c . Jadi syarat (***) terpenuhi, dengan demikian R Bersifat transitif

Jadi R bersifat refleksif, antisimetris, transitif sehingga R adalah partial order dan (Z+, | ) adalah poset.

Dalam poset, menyatakan bahwa ba π ( ) Rba ∈, . Jika a dan b alemen dari poset

, tidak harus atau . ( π,S ) ba π ab πContoh : Dalam (Z+, | ), 2 tidak mempunyai relasi dengan 3, dan 3 juga tidak mempunyai relasi dengan 2 Definisi : Elemen-elemen a dan b dari sebuah poset ( )π,S disebut comparable jika berlaku ba π atau . ab π Jika a dan b adalah elemen-elemen dari S sedemikain hingga ba π dan , a dan b disebut incomparable.

ab π

Contoh 39. Dalam poset (Z+, | ), apakah bilangan 3 dan 9 comparable? Apakah 5 dan 7 comparable? Bilangan 3 dan 9 comparable, karena 3 | 9. Bilangan 5 dan 7 incomparable, karena 5 | 7 dan 7 | 5. Definisi : Jika adalah sebuah poset dan setiap dua elemen dari S adalah comparable, S disebut total order atau linier order.

( π,S )

)Contoh : Poset adalah total order karena untuk setiap bilangan bulat a, b, maka berlaku

atau (artinya a dan b selalu comparable). ( ≤,Z

ba ≤ ab ≤Poset (Z+, | ) bukan total order karena ada elemen-elemen yang incomparable. 2.13.1.Diagram Hasse Misal didefinisikan sebuah partial order ( ){ }babaR ≤= , pada himpunan {1, 2, 3, 4}, kita dapat membuat representasinya dalam bentuk graf berarah sebagai berikut (dalam hal ini, arah panah selalu ke atas) :

ZK Abdurahman Baizal

Sekolah Tinggi Teknologi Telkom

Matematika Diskrit

25

3

4

2

1

Gambar 8 Karena partial order bersifat refleksif, maka kita tidak perlu menunjukkan loop untuk masing-masing simpul.

3

4

2

1

Gambar 9 Karena partial order bersifat transitif, kita tidak perlu menunjukkan edge yang harus disajikan karena ke-transitif-an dari partial order. Dengan demikian sisi (edge) (1, 3), (1, 4), (2, 4) dihapus.

3

4

2

1

Gambar 10 Jika kita mengasumsikan bahwa semua sisi megarah ke atas, kita tidak harus menunjukkan arah sisi.

ZK Abdurahman Baizal

Sekolah Tinggi Teknologi Telkom

Matematika Diskrit

26

3

4

2

1

Gambar 11 Diagram yang dihasilkan adalah diagram yang berisi informasi yang cukup untuk mendapatkan partial order, yang disebut dengan diagram Hasse. Langkah-langkah dalam membangun diagram Hasse :

1. Hapus loop untuk masing-masing simpul 2. Hapus semua sisi yang harus disajikan karena ke-transitif-an. Contoh, jika ada

(a, b) dan (b, c), maka hapus sisi (a, c). Jika ternyata ada (c, d), hapus (a, d) 3. Atur masing-masing sisi sedemikian hingga simpul awalnya (intial vertex-nya)

berada di bawah simpul terminal (terminal vertex). Dengan kata lain, buat agar panah mengarah ke atas.

4. Hapus semua panah. Contoh 40. Gambarkan diagram Hasse yang menyajikan partial order ( ){ }baba membagi habis , pada {1, 2, 3, 4, 6, 8, 12} Graf berarah :

Gambar 12

ZK Abdurahman Baizal

Sekolah Tinggi Teknologi Telkom

Matematika Diskrit

27

Diagram Hasse :

6

12

3

1

2

4

8

Gambar 13

Soal latihan 1. Daftarlah pasangan terurut dalam relasi R dari A = {0, 1, 2, 3, 4} ke B = {0, 1, 2, 3}

dimana ( jika dan hanya jika : )Rba ∈,a. a = b b. a > b c. a + b = 4 d. a | b

2. Relasi – relasi di bawah ini didefinisikan dalam himpunan {1, 2, 3, 4}. Periksa apakah relasi-relasi berikut bersifat refleksif, simetris, antisimetris, transitif. a. {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} b. {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4) c. {(2, 4), (4, 2)} d. {(1, 2), (2, 3), (3, 4)} e. (1, 1), (2, 2), (3, 3), (4, 4)

3. Periksa apakah relasi-relasi di bawah ini mempunyai sifat refleksif, simetris antisimetris, transitif jika relasi-relasi tersebut didefinisikan pada himpunan orang. a. a lebih tinggi daripada b b. a dan b lahir pada hari yang sama c. a mempunyai nama depan yang sama dengan b

4. Relasi-relasi di bawah ini didefinisikan pada himpunan bilangan riil. Periksa relasi-relasi berikut untuk sifat-sifat : refleksif, simetris antisimetris, transitif. a. 0=+ yxb. yx ±= c. yx 2=d. 1atau 1 == yxe. 0≥xy

5. Tentukan R-1 untuk relasi – relasi di bawah ini : a. ( ){ }babaR <= ,

b. R = ( ){ }baba membagi habis ,

ZK Abdurahman Baizal

Sekolah Tinggi Teknologi Telkom

Matematika Diskrit

28

6. a. Daftarlah semua pasangan terurut dalam relasi R = ( ){ }baba membagi habis , pada himpunan {1, 2, 3, 4, 5, 6}

b. Sajikan relasi tersebut dalam graf berarah c. Sajikan relasi tersebut dalam bentuk tabel

7. Tentukan apakah f adalah sebuah fungsi dari Z ke R jika : a. ( ) xxf ±=

b. ( ) 12 += xxf

c. ( ) ( )41

2 −= xxf

8. Tentukan apakah masing-masing fungsi di bawah ini adalah funsi satu-ke satu (one-to-one) dan/ atau fungsi onto atau bukan kedua-duanya. a. ( ) 1−= xxfb. ( ) 12 += xxfc. ( ) 3xxf =

d. ( ) 2xxf =

9. Di bawah ini adalah relasi-relasi pada himpunan orang (set of all people). Periksa apakah relasi-relasi berikut ini merupakan relasi ekivalen melalui sifat-sifat relasinya. a. ( ){ }sama berusia dan , baba

b. ( ){ }sama yang tuaorang mempunyai dan , baba

c. ( ){ }bertemupernah dan , baba 10. Misal R adalah relasi pada himpunan pasangan terurut dari bilangan bulat,

sedemikian hingga ( ) ( )( ) Rdcba ∈,,, jika dan hanya jika ad = bc. Tunjukkan bahwa R adalah relasi ekivalen.

11. Manakah di bawah ini yang merupakan poset? a. (Z, =) b. (Z, ≠) c. (Z, ≥) d. (Z, | )

12. Gambarkan diagram Hasse untuk relasi “habis membagi” pada himpunan-himpunan di bawah ini : a. {1, 2, 3, 4, 5, 6} b. {3, 5, 7, 11, 13, 16, 17} c. {2, 3, 5, 10, 15, 25} d. {1, 3, 9, 27, 81, 243}

13. Didefinisikan sebuah relasi R= {(a,b)| b kelipatan a } pada himpunan S={ 1,2,3,4,6,8,12,15 }

a. Tunjukkan bahwa (S,R) adalah poset ! b. Gambarkan diagram Hasse-nya !

14. Jika f: A B merupakan suatu fungsi. Periksa apakah fungsi dibawah ini merupakan fungsi onto dan/atau one to one atau bukan keduanya, dan jelaskan alasannya a. A, B adalah himpunan bilangan riil ; f(a) = |a|

ZK Abdurahman Baizal

Sekolah Tinggi Teknologi Telkom

Matematika Diskrit

29

b. A adalah himpunan bilangan riil , B={b|b bil riil dan b ≥ 0}; f(a) = a

ZK Abdurahman Baizal

Sekolah Tinggi Teknologi Telkom