Matematika Diskrit: Hubungan dan Himpunan

Materi Kuliah Matematika Diskrit

• Mata kuliah: Matematika Diskrit
• Kode mata kuliah: MATH6198051
• Periode efektif: September 2022

Hubungan (Relations)

• Hubungan biner dari himpunan A ke himpunan B adalah himpunan bagian dari A × B.
• Hubungan biner dari A ke B adalah himpunan R dari pasangan terurut, di mana elemen pertama dari setiap pasangan terurut berasal dari A dan elemen kedua berasal dari B.
• Notasi aRb untuk menunjukkan bahwa (a, b) ∈ R dan a ⊈ b untuk menunjukkan bahwa (a, b) ∉ R.
• Lebih lanjut, ketika (a, b) termasuk dalam R, a dikatakan terkait dengan b oleh R.
• Hubungan biner merepresentasikan hubungan antara elemen-elemen dua himpunan.

Sub Topik

• Hubungan
• Sifat-sifat Hubungan
• Hubungan Kesamaan
• Pengurutan Parsial
• Merepresentasikan Hubungan

Tujuan Pembelajaran

• Menganalisis Hubungan dan Himpunan Terurut Parsial
• Menentukan apakah suatu hubungan bersifat refleksif, simetris, dan transitif.
• Mencari hubungan kesamaan dan kelas kesamaan.
• Menentukan urutan parsial, elemen maksimal, elemen minimal, elemen terbesar, dan elemen terkecil dari himpunan terurut parsial.
• Memahami cara merepresentasikan hubungan menggunakan matriks dan diagram digraf.

Sifat-sifat Hubungan

• • Refleksif: Dalam konteks relasi, dibilang refleksif jika elemen dari suatu himpunan A berhubungan dengan dirinya sendiri. Secara formal, ini dinyatakan dengan (a, a) ∈ R untuk semua a yang merupakan anggota dari himpunan A. Ini berarti bahwa setiap elemen dalam himpunan tersebut memiliki hubungan yang refleksif terhadap dirinya sendiri. Misalnya, dalam relasi "sama dengan", setiap angka adalah sama dengan dirinya sendiri.
  • Simetris: Sebuah relasi dikatakan simetris jika untuk setiap pasangan elemen a dan b dalam himpunan A, jika a berhubungan dengan b (dinyatakan dengan (a, b) ∈ R), maka b juga harus berhubungan dengan a (yaitu, (b, a) ∈ R). Ini menunjukkan bahwa arah dari relasi tidak menimbulkan perbedaan dalam hasil; contoh yang baik adalah relasi "kawan" di mana jika A adalah kawan B, maka B juga adalah kawan A.
  • Transitif: Relasi memiliki sifat transitif jika, untuk setiap elemen a, b, dan c dalam himpunan A, apabila a berhubungan dengan b dan b berhubungan dengan c (dinyatakan dengan (a, b) ∈ R dan (b, c) ∈ R), maka a akan otomatis berhubungan dengan c (yaitu, (a, c) ∈ R). Ini menciptakan rantai hubungan yang menghubungkan elemen-elemen tersebut. Contohnya, jika A adalah lebih besar dari B dan B lebih besar dari C, maka A juga lebih besar dari C.
  • Antisimetris: Sebuah relasi disebut antisimetris jika, untuk setiap elemen a dan b dalam himpunan A, pada situasi di mana (a, b) ∈ R dan juga (b, a) ∈ R, dapat disimpulkan bahwa a harus sama dengan b. Dengan kata lain, tidak boleh ada dua elemen berbeda yang saling berhubungan satu sama lain dalam arah yang berlawanan. Contoh dari relasi ini bisa ditemui pada relasi "lebih besar dari atau sama dengan" dalam angka, di mana jika x lebih besar dari atau sama dengan y dan y juga lebih besar dari atau sama dengan x, maka x dan y haruslah sama.

Hubungan Kesamaan

• Relasi pada himpunan A disebut relasi kesetaraan jika bersifat refleksif, simetris, dan transitif.
• Dua elemen a dan b yang terkait oleh relasi kesetaraan disebut ekivalen.
• Notasi a ~ b sering digunakan untuk menunjukkan bahwa a dan b adalah elemen ekivalen sehubungan dengan relasi kesetaraan tertentu.

Contoh

• Contoh 1: Relasi pada himpunan bilangan riil sedemikian rupa sehingga aRb jika dan hanya jika a − b adalah bilangan bulat.
• Contoh 2: Relasi pada himpunan bilangan riil sedemikian rupa sehingga xRy jika dan hanya jika |x − y| < 1.

Kelas Kesamaan

• Kelas kesamaan dari elemen a ∈ A adalah a] = {s | (a, s) ∈ R}.
• Jika b ∈ [a], maka b disebut representasi dari kelas kesamaan ini.

Lattices

• Himpunan terurut parsial di mana setiap pasangan elemen memiliki batas atas terkecil dan batas bawah terbesar disebut kisi.

Merepresentasikan Hubungan Menggunakan Matriks

• Umumnya, matriks cocok digunakan untuk merepresentasikan hubungan dalam program komputer.
• Misalnya, misalkan R adalah hubungan dari A = {a1, a2,..., am} ke B = {b1, b2,..., bn}.
• Hubungan R dapat direpresentasikan oleh matriks MR = [mij], di mana mij = 1 jika (a₁, bj) ∈ R dan mij = 0 jika (a₁, bj) ∉ R.

Merepresentasikan Hubungan Menggunakan Diagram Digraf

• Digraf terdiri dari himpunan simpul V dan himpunan sisi E dari pasangan terurut elemen-elemen V.
• Simpul a disebut simpul awal sisi (a, b), dan simpul b disebut simpul terminal dari sisi ini.