Matdis — Bab 4

Relasi dan Fungsi

Dari relasi biner, sifat-sifatnya, relasi ekivalensi dan pengurutan parsial, hingga fungsi injektif, surjektif, dan bijektif.

Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 4. — Rosen, Discrete Mathematics, 8th ed., Ch. 9.

Mengapa Relasi & Fungsi Penting?

Analogi: buku alamat. "Siapa tinggal di kota mana" adalah sebuah relasi — satu orang bisa punya banyak alamat, satu kota bisa dihuni banyak orang. Tetapi "berapa NIK seseorang" adalah fungsi: setiap orang memetakan ke tepat satu nilai.

Perbedaan sederhana itu adalah inti perancangan basis data. Relasi many-to-many butuh tabel penghubung; relasi one-to-one boleh digabung jadi satu tabel. Salah membedakan keduanya melahirkan skema yang duplikatif dan sulit dipelihara.

Sifat-sifat relasi juga langsung terpakai: relasi ekivalensi (refleksif, simetris, transitif) memecah data menjadi kelompok yang saling lepas — dasar operasi GROUP BY. Relasi terurut parsial menentukan urutan kompilasi modul dan penjadwalan tugas yang saling bergantung.

Analogi: Relasi sebagai Database Join

Relasi biner R ⊆ A × B adalah tabel database dengan dua kolom (a,b). Operasi pada relasi seperti komposisi R∘S mirip SQL JOIN. Fungsi adalah relasi istimewa di mana setiap elemen domain punya tepat satu pasangan — seperti foreign key constraint yang strict.

1. Relasi Biner

Definisi (Relasi Biner)

Relasi biner R dari himpunan A ke B adalah subset dari produk kartesian A × B. Ditulis aRb atau (a,b) ∈ R.

Contoh Relasi

≤ pada ℤ: {(a,b) | a ≤ b}
"ayah dari" pada himpunan orang
R = {(1,1),(1,2),(2,3)} ⊆ {1,2,3}²
"congruent mod n" pada ℤ

Representasi

Daftar pasangan: {(a,b), ...}
Matriks relasi: M[i][j]=1 jika (i,j)∈R
Graf berarah (digraph): simpul=elemen, busur=(a,b)∈R

2. Sifat-Sifat Relasi pada Himpunan

Empat Sifat Kunci Relasi

Refleksif

∀a ∈ A: (a,a) ∈ R

Setiap elemen berhubungan dengan dirinya sendiri.

Contoh: ≤, =, |, kongruensi mod n.

Simetris

∀a,b: (a,b)∈R → (b,a)∈R

Jika a berhubungan dengan b, maka b berhubungan dengan a.

Contoh: =, "saudara dari", kongruensi mod n.

Antisimetris

∀a,b: (a,b)∈R ∧ (b,a)∈R → a=b

Jika aRb dan bRa, maka a = b.

Contoh: ≤, ≥, | (pembagi).

Transitif

∀a,b,c: (a,b)∈R ∧ (b,c)∈R → (a,c)∈R

Relasi "berantai": aRb dan bRc berarti aRc.

Contoh: <, ≤, subset ⊆, divisibility.

Pemeriksa Sifat Relasi Interaktif (Domain {1,2,3})

Pasangan relasi saat ini:

(1,1) (2,2) (3,3) (1,2) (2,1)

Relasi R = { (1,1),(2,2),(3,3),(1,2),(2,1) } pada {1,2,3}

Refleksif: YA ✓

(1,1),(2,2),(3,3) semua ada

Simetris: YA ✓

Antisimetris: TIDAK ✗

Transitif: YA ✓

Relasi Ekivalensi: YA ✓

Refleksif + Simetris + Transitif

Urutan Parsial (Poset): TIDAK

Refleksif + Antisimetris + Transitif

3. Relasi Ekivalensi & Kelas Ekivalensi

Kelas Ekivalensi

Jika R adalah relasi ekivalensi pada A, maka kelas ekivalensi dari a adalah:

[a] = {x ∈ A | xRa}

Properti Kelas Ekivalensi

[a] = [b] jika dan hanya jika aRb
[a] ≠ [b] berarti [a] ∩ [b] = ∅
Kelas-kelas ekivalensi membentuk partisi A

Contoh: Kongruensi mod 3

[0] = {...,-3,0,3,6,...}

[1] = {...,-2,1,4,7,...}

[2] = {...,-1,2,5,8,...}

Diagram Hasse: Poset {1,2,3,4,6,12} dengan Divisibility

Poset ({1,2,3,4,6,12}, |). Garis = "dibagi oleh". 1 adalah minimum (bottom), 12 adalah maximum (top).

4. Fungsi: Definisi & Jenis

Definisi (Fungsi)

Fungsi f: A → B adalah relasi di mana setiap elemen a ∈ A (domain) berhubungan dengan tepat satu elemen b ∈ B (kodomain). Ditulis f(a) = b.

Domain (A)

Himpunan input. Setiap a ∈ A harus punya nilai f(a).

Kodomain (B)

Himpunan output yang mungkin. f(a) ∈ B untuk semua a.

Range/Image

Subset B yang benar-benar tercapai: {f(a) | a ∈ A}.

Tiga Jenis Fungsi (Injektif, Surjektif, Bijektif)

Bijektif (Korespondensi 1-1)

Bijektif: injektif dan surjektif sekaligus. Inversibel!

f(1) = 3

f(2) = 1

f(3) = 2

Injektif

f(a)=f(b) → a=b

Tidak ada dua input yang menghasilkan output yang sama.

Surjektif

∀b ∃a: f(a)=b

Setiap elemen kodomain tercapai oleh minimal satu input.

Bijektif

Injektif + Surjektif

Korespondensi satu-satu sempurna. Selalu punya invers.

5. Komposisi & Invers Fungsi

Komposisi dan Invers

Komposisi: (g ∘ f)(x) = g(f(x))

Terapkan f dahulu, lalu g. Syarat: range(f) ⊆ domain(g).

f: ℝ→ℝ, f(x)=2x+1
g: ℝ→ℝ, g(x)=x²
(g∘f)(x) = (2x+1)²

Invers: f⁻¹ ada ↔ f bijektif

f⁻¹: B→A sehingga f⁻¹(f(x))=x dan f(f⁻¹(y))=y.

f(x)=3x+2 → f⁻¹(y)=(y-2)/3

RSA: Enkripsi E dan dekripsi D adalah invers satu sama lain.

Visualisasi SMIL: Komposisi Fungsi f then g

6. Fungsi Rekursif

Tiga Fungsi Rekursif Penting

Faktorial

0! = 1
n! = n · (n-1)!

Dipakai dalam rumus permutasi, kombinasi, dan teorema binomial.

Fibonacci

F(0)=0, F(1)=1
F(n)=F(n-1)+F(n-2)

Muncul dalam analisis algoritma GCD (lca: Lamé's theorem).

Ackermann

A(0,n)=n+1
A(m,0)=A(m-1,1)
A(m,n)=A(m-1,A(m,n-1))

Tidak primitif rekursif — tumbuh lebih cepat dari semua fungsi primitif rekursif.

7. Penerapan Relasi & Fungsi

Dari Teori ke Sistem Nyata

Model Data Relasional: Sebuah tabel adalah relasi dalam pengertian bab ini — himpunan bagian dari hasil kali kartesius antar domain kolom. Operasi JOIN adalah komposisi relasi, dan kunci primer menjamin pemetaan bersifat fungsi (setiap baris tepat satu nilai kunci).

Relasi Ekivalensi & Partisi: "Mahasiswa dengan angkatan sama" bersifat refleksif, simetris, dan transitif, sehingga membagi populasi menjadi kelas-kelas yang saling lepas dan mencakup semuanya. Inilah yang dilakukan GROUP BY dan algoritma union-find.

Terurut Parsial & Penjadwalan: Relasi "harus dikerjakan sebelum" bersifat terurut parsial. Pengurutan topologis atasnya menghasilkan urutan build pada Make, resolusi dependensi paket, dan penjadwalan proyek.

Injektif, Surjektif, Bijektif: Fungsi hash bersifat surjektif tapi tidak injektif — itulah sebabnya collision pasti ada (prinsip sarang merpati). Sebaliknya, fungsi yang bijektif punya invers, dan hanya fungsi bijektif yang aman dipakai untuk pengkodean bolak-balik seperti Base64.

8. Contoh Soal & Pembahasan

Soal 1: Sifat Relasi

R = {(1,1),(1,2),(2,2),(2,3),(3,3),(1,3)} pada {1,2,3}. Apakah refleksif, simetris, antisimetris, transitif?

Soal 2: Kelas Ekivalensi

Tentukan kelas ekivalensi [2] untuk relasi kongruensi mod 4 pada ℤ.

Soal 3: Injektif/Surjektif

f: ℝ → ℝ, f(x) = x³. Apakah injektif? Surjektif? Bijektif?

Soal 4: Komposisi

f(x) = 2x+1, g(x) = x². Hitung (g∘f)(3) dan (f∘g)(3).

Soal 5: RSA sebagai Fungsi

Jelaskan mengapa enkripsi RSA E_pk dan dekripsi D_sk adalah fungsi bijektif yang saling invers.

8. Representasi Matriks & Komposisi Relasi

Matriks Relasi

Relasi R ⊆ {1,2,3}² dapat direpresentasikan sebagai matriks M_R dimana M[i][j]=1 jika (i,j)∈R.

Deteksi Sifat dari Matriks

Refleksif: Diagonal utama = semua 1
Simetris: M = Mᵀ (simetris terhadap diagonal)
Antisimetris: M ∩ Mᵀ ⊆ I (identitas)

Komposisi Relasi

R∘S menggunakan perkalian matriks boolean:

M_{R∘S}[i][j] = OR_k(M_R[i][k] AND M_S[k][j])

Sama dengan matriks perkalian, dengan + = OR, × = AND.

Poset & Urutan Total

Urutan Parsial (Poset)

Refleksif + Antisimetris + Transitif.

Contoh: (𝒫(A), ⊆), (ℕ, |), (ℤ, ≤).

Hasse diagram = representasi visual kompak.

Urutan Total (Rantai)

Poset di mana setiap dua elemen bisa dibandingkan.

Contoh: (ℤ, ≤) — semua bilangan bulat terurut.

Topological sort menghasilkan urutan total dari poset.

Rangkuman Sifat Relasi

Tipe	Refleksif	Simetris	Antisimetris	Transitif
Ekivalensi	✓	✓	—	✓
Urutan Parsial	✓	—	✓	✓
Urutan Ketat	✗	—	✓	✓

← 3. Induksi 5. Kombinatorika →

Munir, R. (2020). Matematika Diskrit, Edisi 7, Penerbit Informatika ITB, Bab 4. — Rosen, K. H. (2019). Discrete Mathematics and Its Applications, 8th ed., Ch. 9.

Bank Soal Multi-Kompleksitas & Kasus Terintegrasi

Ref: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 4.

Mudah

1. Tentukan apakah R = {(1,1),(2,2),(3,3),(1,2),(2,1)} pada A={1,2,3} merupakan relasi ekivalensi.

2. Apakah f: ℤ→ℤ dengan f(x)=2x adalah injektif? Surjektif?

3. Gambarkan diagram Hasse untuk relasi "habis membagi" pada {1,2,3,6}.

4. Tentukan kelas ekivalensi [2] untuk R={(a,b): a≡b mod 3} pada {1,2,3,4,5,6}.

Sedang

1. Buktikan: Jika R adalah relasi ekivalensi pada A, maka kelas-kelas ekivalensi membentuk partisi A.

2. Tentukan apakah fungsi h: ℤ_n → ℤ_n dengan h(x) = ax mod n (gcd(a,n)=1) adalah bijeksi. Mengapa ini penting untuk kriptografi?

3. Berikan contoh relasi yang transitif tapi tidak simetris dan tidak antisimetris.

4. Fungsi f: A→B dan g: B→C keduanya bijektif. Buktikan g∘f adalah bijektif.

Sulit

1. Buktikan: Fungsi hash kriptografis ideal H: {0,1}* → {0,1}²⁵⁶ tidak bisa injektif. Jelaskan konsekuensinya terhadap collision resistance.

2. Konstruksi Hasse diagram untuk poset (P({1,2,3}), ⊆). Identifikasi: elemen minimal, maksimal, infimum dan supremum dari {{1}, {2}}.

3. Relasi ekivalensi R pada ℤ: aRb ⟺ a ≡ b (mod n). Buktikan ℤ/nℤ dengan operasi [a]+[b]=[a+b] dan [a]·[b]=[ab] membentuk ring. Kapan ℤ/nℤ adalah field?

Kasus Terintegrasi (2+ Topik)

Relasi Ekivalensi + Partisi + Crypto Group

Relasi kongruensi mod 7 pada ℤ membentuk 7 kelas ekivalensi. Tunjukkan bahwa (ℤ/7ℤ\{[0]}, ·) adalah grup. Tentukan orde setiap elemen dan hubungkannya dengan Fermat's Little Theorem.

Fungsi Hash + Injektif/Surjektif

SHA-3 (Keccak) adalah fungsi H: {0,1}* → {0,1}²⁵⁶. Klasifikasikan sifat injektif/surjektifnya. Jelaskan mengapa preimage resistance, second preimage resistance, dan collision resistance adalah properti berbeda.

Poset + Lattice + Pengurutan Topologis

Himpunan pembagi dari 36 diurutkan oleh relasi "membagi" (a ≼ b ⟺ a | b). Gambarkan diagram Hasse-nya, tunjukkan bahwa poset ini adalah lattice, lalu jelaskan apa arti operasi meet dan join di sini.