Belajar Math - Relasi & Fungsi
Domain, range, refleksif, simetris, transitif, dan fungsi injective, surjective, bijective — konsep ini muncul dalam hashing, map/reduce, encoding Base64, dan analisis apakah fungsi kode kalian memetakan input ke output secara unik dan reversible.
#Pendahuluan
Setelah di episode 7 kita menguasai operasi himpunan — union, intersection, difference — pada episode ini kita mempelajari relasi dan fungsi: bagaimana objek dari dua himpunan saling berhubungan. Relasi adalah "hubungan antara elemen" dari dua himpunan, dan fungsi adalah relasi khusus di mana setiap input punya tepat satu output.
Mengapa ini penting untuk programmer? Karena hashing adalah fungsi (injective yang diinginkan), map/reduce adalah operasi fungsi komposisi, Base64 encoding adalah bijection (reversible), dan analisis apakah fungsi kalian memetakan input ke output secara unik dan reversible adalah pertanyaan fundamental dalam desain sistem.
#Relasi (Relation)
#Definisi
Relasi R dari himpunan A ke himpunan B adalah subset dari Cartesian product A × B. Artinya, R adalah kumpulan pasangan (a, b) di mana a ∈ A dan b ∈ B:
A = {1, 2, 3, 4}
B = {2, 4, 6, 8}
# Relasi "a adalah pembagi dari b"
R = {(a, b) for a in A for b in B if b % a == 0}
print(f"Relasi pembagi:")
for pair in sorted(R):
print(f" {pair[0]} | {pair[1]}")#Sifat Relasi
Relasi di atashim A memiliki sifat-sifat penting:
#Refleksif
R refleksif jika (a, a) ∈ R untuk semua a ∈ A:
# Relasi "sama dengan" adalah refleksif
A = {1, 2, 3}
equal = {(a, a) for a in A}
print(f"Refleksif? {all((a, a) in equal for a in A)}") # True#Simetris
R simetris jika (a, b) ∈ R maka (b, a) ∈ R:
# Relasi "berteman" adalah simetris
friendships = {("Alice", "Bob"), ("Bob", "Alice"), ("Charlie", "Diana")}
is_symmetric = all((b, a) in friendships for a, b in friendships)
print(f"Simetris? {is_symmetric}") # True#Transitif
R transitif jika (a, b) ∈ R dan (b, c) ∈ R maka (a, c) ∈ R:
# Relasi "lebih kecil dari" adalah transitif
pairs = {(1, 2), (2, 3), (1, 3)}
is_transitive = all(
(a, c) in pairs
for a, b in pairs
for b2, c in pairs
if b == b2
)
print(f"Transitif? {is_transitive}") # True#Fungsi (Function)
#Definisi
Fungsi f: A → B adalah relasi di mana setiap a ∈ A dipetakan ke tepat satu b ∈ B. Ini berarti:
- Total: setiap input punya output.
- Unik: setiap input punya tepat satu output (bukan dua).
# Fungsi valid: setiap input → tepat satu output
def kuadrat(x: int) -> int:
return x ** 2
# Bukan fungsi: satu input → multiple output
# def tidak_valid(x):
# return [x, -x] # ini bukan fungsi matematika
# Bukan fungsi: input tidak punya output
# def tidak_total(x):
# if x > 0:
# return x
# # x ≤ 0 tidak punya output — bukan fungsi total#Sifat Fungsi
#Injective (One-to-One)
Fungsi injective: setiap output punya tepat satu input yang menghasilkannya. Tidak ada dua input yang menghasilkan output sama:
def injective_test(f, domain):
"""Cek apakah fungsi injective pada domain."""
outputs = [f(x) for x in domain]
return len(outputs) == len(set(outputs))
# f(x) = 2x — injective
print(f"f(x)=2x injective? {injective_test(lambda x: 2*x, range(10))}") # True
# f(x) = x² — tidak injective (x=2 dan x=-2 sama)
print(f"f(x)=x² injective? {injective_test(lambda x: x**2, range(-5, 6))}") # False#Surjective (Onto)
Fungsi surjective: setiap elemen di codomain punya setidak satu preimage. Tidak ada output yang "kosong" tidak terpakai:
def surjective_test(f, domain, codomain):
"""Cek apakah fungsi surjective."""
covered = set(f(x) for x in domain)
return codomain <= covered
# f(x) = x mod 3 surjective ke {0, 1, 2}
print(f"Mod 3 onto? {surjective_test(lambda x: x % 3, range(10), {0, 1, 2})}") # True
# f(x) = x mod 3 TIDAK surjective ke {0, 1, 2, 3}
print(f"Mod 3 onto {0,1,2,3}? {surjective_test(lambda x: x % 3, range(10), {0, 1, 2, 3})}") # False#Bijective (One-to-One dan Onto)
Fungsi bijective adalah injective sekaligus surjective — setiap input unik dan setiap output terpakai. Artinya fungsi reversible:
def f(x):
return (x + 3) % 5 # f: {0,1,2,3,4} → {0,1,2,3,4}
def f_inverse(y):
return (y - 3) % 5 # inverse — membalik fungsi
# Verifikasi bijective
domain = set(range(5))
outputs = {f(x) for x in domain}
is_injective = len([f(x) for x in domain]) == len(set(f(x) for x in domain))
is_surjective = domain == outputs
print(f"f injective? {is_injective}") # True
print(f"f surjective? {is_surjective}") # True
print(f"f bijective? {is_injective and is_surjective}") # True
# Verifikasi inverse
for x in domain:
assert f_inverse(f(x)) == x, f"Failed for x={x}"
print("Inverse verified!")#Aplikasi dalam Programming
#Hashing → Injective yang Diinginkan
Hash function idealnya injective — hash berbeda untuk input berbeda. Dalam praktik, karena output terbatas (misal 256 bit untuk SHA-256), terjadi collision (dua input sama hash). Ini relates ke pigeonhole principle yang akan dibahas di episode 12.
import hashlib
# SHA-256 — injective dalam praktik (collision sangat jarang)
inputs = ["hello", "world", "python", "math"]
hashes = []
for inp in inputs:
h = hashlib.sha256(inp.encode()).hexdigest()[:16]
hashes.append(h)
print(f" sha256('{inp}') = {h}")
# Collision jarang — tetapi mungkin secara teori
print(f"Semua hash unik? {len(hashes) == len(set(hashes))}")#Map/Reduce → Komposisi Fungsi
from functools import reduce
# Map: apply fungsi ke setiap elemen — f(g(x))
data = [1, 2, 3, 4, 5]
mapped = list(map(lambda x: x ** 2, data))
print(f"Map x²: {mapped}")
# Reduce: gabung elemen dengan fungsi biner
total = reduce(lambda a, b: a + b, data)
print(f"Reduce +: {total}")
# Komposisi: map → filter → reduce
result = reduce(
lambda a, b: a + b,
filter(
lambda x: x % 2 == 0,
map(lambda x: x ** 2, data)
)
)
print(f"Map x² → filter genap → reduce +: {result}")
# 4 + 16 = 20#Base64 Encoding → Bijective
Base64 adalah bijection — encoding dan decoding reversible tanpa kehilangan informasi:
import base64
original = "Hello, Matematika!"
encoded = base64.b64encode(original.encode()).decode()
decoded = base64.b64decode(encoded.encode()).decode()
print(f"Original: {original}")
print(f"Encoded: {encoded}")
print(f"Decoded: {decoded}")
print(f"Reversible? {original == decoded}") # True — bijectiveTip
Ketika mendesain API atau interface, tanyakan: apakah fungsi ini injective (output unik untuk input berbeda)? surjective (semua output mungkin)? bijective (reversible)? Jawaban atas pertanyaan ini menentukan apakah kalian bisa invert fungsi, mendeteksi duplikat, atau memulihkan data.
#Penutup
Inti yang harus dibawa pulang:
- Relasi adalah hubungan antara elemen dua himpunan; fungsi adalah relasi khusus: setiap input → tepat satu output.
- Sifat relasi: refleksif (a R a), simetris (a R b → b R a), transitif (a R b ∧ b R c → a R c).
- Sifat fungsi: injective (output unik), surjective (semua output terpakai), bijective (keduanya — reversible).
- Hashing menginginkan injective; map/reduce adalah komposisi fungsi; Base64 adalah bijection.
Di episode 9 selanjutnya kita akan mempelajari proof techniques (bukti matematika) — direct proof, proof by contradiction, contrapositive, dan mathematical induction. Relasi dan fungsi yang baru kalian pelajari akan menjadi subjek dari beberapa bukti ini — terutama induction yang berkaitan erat dengan rekursi dalam kode!