Matdis — Bab 2
Himpunan (Sets)
Konsep fundamental koleksi objek yang tidak berulang — notasi, operasi, dan hukum-hukum himpunan yang menjadi dasar struktur data dan keamanan sistem.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 2. — Rosen, Discrete Mathematics, 8th ed., Ch. 2.
Mengapa Himpunan Itu Penting?
Analogi: lemari arsip. Himpunan adalah "map" yang mengumpulkan berkas berdasarkan kriteria tertentu. Yang menarik bukan mapnya, melainkan operasi antar map: berkas apa yang ada di kedua map (irisan), gabungan keduanya (union), atau yang ada di map A tapi tidak di B (selisih).
Operasi itu persis yang dilakukan mesin basis data setiap hari. INNER JOIN adalah irisan, UNION adalah gabungan, NOT IN adalah selisih. Menguasai hukum himpunan berarti bisa menulis ulang query jadi bentuk yang lebih cepat tanpa mengubah hasilnya.
Kardinalitas juga jadi alat menghitung: "berapa banyak kata sandi 8 karakter yang mungkin?" adalah pertanyaan tentang ukuran sebuah himpunan — dan jawabannya menentukan apakah menebak satu per satu itu realistis atau tidak.
Analogi: Himpunan sebagai Container di Programming
Himpunan adalah versi matematis dari Set<T> di Java, Python, atau C++. Union = a | b, Intersect = a & b, Difference = a - b. Bit vector representation (bitmask) adalah implementasi ultra-efisien O(1) untuk himpunan kecil — sama persis cara CPU modern merepresentasikan flag dan permission sets.
1. Definisi, Notasi & Kardinalitas
Definisi (Himpunan)
Himpunan adalah kumpulan objek yang terdefinisi dengan baik (well-defined), tidak berulang, tanpa urutan. Objek dalam himpunan disebut anggota (element) atau unsur.
Notasi Daftar (Roster)
A = {1, 2, 3, 4, 5}
B = {a, e, i, o, u}
∅ = {} (himpunan kosong)
Notasi Pembentuk Himpunan
{x | x ∈ ℤ, x > 0} = ℤ⁺
{x | x² < 10, x ∈ ℕ}
= {0, 1, 2, 3}
Kardinalitas dan Himpunan Khusus
| Simbol | Nama | Deskripsi |
|---|---|---|
| |A|, #A | Kardinalitas | Jumlah elemen dalam A |
| ∅ atau {} | Himpunan Kosong | |∅| = 0, subset setiap himpunan |
| 𝒫(A) | Himpunan Kuasa | Semua subset A; |𝒫(A)| = 2^|A| |
| A × B | Produk Kartesian | Semua pasangan (a,b); |A×B| = |A|·|B| |
| U | Himpunan Semesta | Semua objek yang dipertimbangkan |
Himpunan Bilangan Standar
ℕ = {0,1,2,3,...} — asli
ℤ = {...,-1,0,1,...} — bulat
ℚ — rasional (p/q)
ℝ — real
ℂ — kompleks
ℤ_n = {0,...,n-1} — modular
2. Relasi Antar Himpunan
Subset & Superset
A ⊆ B: ∀x (x ∈ A → x ∈ B)
A ⊂ B: A ⊆ B ∧ A ≠ B (proper)
∅ ⊆ A (selalu benar)
A ⊆ A (refleksif)
Kesamaan Himpunan
A = B ↔ (A ⊆ B) ∧ (B ⊆ A)
Cara membuktikan A = B: tunjukkan A ⊆ B (ambil x ∈ A, buktikan x ∈ B) dan B ⊆ A.
3. Operasi Himpunan
Lima Operasi Utama
Union: A ∪ B
{x | x ∈ A ∨ x ∈ B}
Interseksi: A ∩ B
{x | x ∈ A ∧ x ∈ B}
Selisih: A − B
{x | x ∈ A ∧ x ∉ B}
Komplemen: Ā
{x ∈ U | x ∉ A}
Beda Simetris: A ⊕ B = (A−B) ∪ (B−A)
{x | (x ∈ A ∨ x ∈ B) ∧ ¬(x ∈ A ∧ x ∈ B)}
Dipakai untuk sinkronisasi data: mencari berkas yang berbeda antara dua salinan folder.
Demo Interaktif: Operasi Himpunan
A = {1,2,3,4,5}, B = {3,4,5,6,7}, U = {1,...,10}
A ∪ B =
{ 1, 2, 3, 4, 5, 6, 7 }
Kardinalitas: 7
Diagram Venn: Union dan Interseksi
A = {1,2,3,4,5}, B = {3,4,5,6,7}. Irisan A ∩ B = {3,4,5} berwarna kuning.
4. Hukum-Hukum Himpunan
Hukum Himpunan (Analog Logika Proposisional)
De Morgan
(A ∪ B)' = A' ∩ B'
(A ∩ B)' = A' ∪ B'
Komutatif
A ∪ B = B ∪ A
A ∩ B = B ∩ A
Asosiatif
(A∪B)∪C = A∪(B∪C)
(A∩B)∩C = A∩(B∩C)
Distributif
A∪(B∩C) = (A∪B)∩(A∪C)
A∩(B∪C) = (A∩B)∪(A∩C)
Identitas
A ∪ ∅ = A A ∩ U = A
Dominasi
A ∪ U = U A ∩ ∅ = ∅
Idempoten
A ∪ A = A A ∩ A = A
Absorpsi
A ∪ (A∩B) = A
A ∩ (A∪B) = A
Komplemen
A ∪ A' = U A ∩ A' = ∅
(A')' = A ∅' = U
Dualitas
Setiap hukum memiliki dual: ganti ∪↔∩ dan ∅↔U.
5. Prinsip Inklusi-Eksklusi
Teorema (PIE)
Untuk menghitung |A ∪ B| tanpa menghitung dua kali:
|A ∪ B| = |A| + |B| − |A ∩ B|
Generalisasi tiga himpunan:
|A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|
Demo Inklusi-Eksklusi Interaktif
|A ∪ B| = 30 + 25 − 10 = 45
6. Partisi, Multiset & Himpunan di Komputer
Partisi
Koleksi {A₁, A₂,...,Aₙ} adalah partisi dari A jika:
- Aᵢ ≠ ∅ untuk semua i
- Aᵢ ∩ Aⱼ = ∅ untuk i ≠ j (disjoint)
- A₁ ∪ A₂ ∪ ... ∪ Aₙ = A
Contoh: genap/ganjil adalah partisi ℤ.
Multiset
Himpunan yang memperbolehkan pengulangan anggota.
{a, a, b, c, c, c}
Multiplisitas: a×2, b×1, c×3. Dipakai untuk menghitung frekuensi kata pada pengolahan teks.
Representasi Bit Vector (Himpunan di Komputer)
Untuk himpunan subset dari {1,...,n}, representasikan sebagai bitmask: posisi ke-i = 1 jika elemen i ada, 0 jika tidak.
A = 10110 = {1, 3, 4}
B = 11010 = {1, 2, 4}
A ∪ B = A | B = 11110 = {1, 2, 3, 4}
A ∩ B = A & B = 10010 = {1, 4}
A − B = A & ~B = 00100 = {3}
Semua operasi di atas = O(1) menggunakan operasi bitwise CPU. Dipakai mesin pencari untuk menggabungkan hasil filter dengan cepat.
Visualisasi SMIL: Operasi Beranimasi
7. Prinsip Dualitas & Penerapan
Himpunan di Dunia Nyata
Aljabar Relasional: Seluruh SQL dibangun di atas operasi himpunan. UNION, INTERSECT, dan EXCEPT adalah gabungan, irisan, dan selisih. Hukum De Morgan dipakai optimizer untuk menulis ulang predikat NOT (A OR B) menjadi NOT A AND NOT B.
Himpunan Bit (Bitset): Himpunan bagian dari semesta berukuran ≤ 64 dapat diwakili satu bilangan 64-bit. Gabungan menjadi operasi OR, irisan menjadi AND, komplemen menjadi NOT — semuanya satu instruksi CPU. Teknik ini dipakai mesin pencari untuk menggabungkan hasil filter dengan sangat cepat.
Prinsip Inklusi-Eksklusi: Menghitung "berapa pengguna yang membuka aplikasi A atau B" bukan sekadar menjumlahkan keduanya — yang memakai keduanya akan terhitung dua kali. Rumus |A ∪ B| = |A| + |B| − |A ∩ B| adalah koreksi standar di analitik.
Grup dan Struktur Aljabar: Himpunan yang dilengkapi operasi menghasilkan struktur baru. ℤₙ = {0,…,n−1} dengan penjumlahan modulo n membentuk grup — fondasi aritmetika modular yang dibahas pada Bab Teori Bilangan.
8. Contoh Soal & Pembahasan
Soal 1: Operasi Himpunan
Diberikan A={1,2,3,4}, B={2,4,6,8}, C={1,3,5,7}. Hitung (A ∩ B) ∪ C.
Soal 2: Himpunan Kuasa
Tentukan 𝒫({a, b, c}) dan kardinalitasnya.
Soal 3: Inklusi-Eksklusi
Di kelas 100 mahasiswa: 60 belajar Kalkulus, 45 belajar Aljabar Linier, 20 keduanya. Berapa yang belajar setidaknya satu?
Soal 4: De Morgan Himpunan
Buktikan (A ∪ B)' = A' ∩ B' menggunakan definisi.
Soal 5: Partisi
Apakah {{1,3,5}, {2,4,6}, {7,8,9,10}{'}}'} merupakan partisi dari {1,...,10}?
Soal 6: Produk Kartesian & Kardinalitas
Sebuah sistem memakai kata sandi 8 karakter dari himpunan S = {a…z, A…Z, 0…9}. Nyatakan ruang kata sandi sebagai produk kartesius, lalu hitung kardinalitasnya.
9. Himpunan Tak Berhingga & Kardinalitas Cantor
Kardinalitas Himpunan Tak Berhingga
Cantor membuktikan bahwa tidak semua himpunan tak berhingga "sama besar". Himpunan countable vs uncountable:
Countably Infinite (ℵ₀)
- ℕ = {0,1,2,...}, ℤ, ℚ
- Bisa dibuat korespondensi bijektif dengan ℕ
- Himpunan program komputer (string berhingga)
Uncountably Infinite (ℵ₁)
- ℝ, interval (0,1), 𝒫(ℕ)
- Cantor diagonal: ℝ lebih "besar" dari ℕ
- Implikasi: ada fungsi yang tidak dapat diprogram!
Argumen Pencacahan: Kekuatan Tak Terduga
Sebagian besar fungsi tidak punya program pendek. Ada 2^(2ⁿ) fungsi Boolean dari n bit ke 1 bit, sementara program yang panjangnya di bawah L bit jumlahnya hanya 2^L. Karena 2^(2ⁿ) jauh melampaui 2^L, hampir semua fungsi tidak bisa diringkas jadi program pendek — sebuah fakta yang dibuktikan tanpa menunjuk satu contoh pun.
Tidak semua berkas bisa dikompresi. Argumen yang sama membuktikan tidak ada kompresor lossless yang memperkecil semua masukan: pemetaan dari 2ⁿ berkas ke berkas yang lebih pendek tidak mungkin injektif (prinsip sarang merpati).
Terhitung vs tak terhitung. Himpunan semua program komputer bersifat terhitung (countable), sedangkan himpunan semua fungsi ℕ → {0,1} tidak terhitung. Konsekuensinya mendasar: ada fungsi yang tidak mungkin dihitung program mana pun — inti dari masalah ketakterputusan.
Rangkuman: Hukum Himpunan vs Hukum Logika (Dualitas)
| Himpunan | Logika |
|---|---|
| A ∪ B | p ∨ q |
| A ∩ B | p ∧ q |
| A' (komplemen) | ¬p |
| ∅ (kosong) | F (False) |
| U (semesta) | T (True) |
| (A∪B)' = A'∩B' | ¬(p∨q) ≡ ¬p∧¬q |
Prinsip Dualitas: setiap hukum himpunan punya dual — ganti ∪↔∩, ∅↔U. Sama persis seperti dualitas di logika proposisional.
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Referensi: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 2 — Himpunan.
MUDAH Soal Dasar Konsep Tunggal
H-M1: Union & Intersection
Diketahui A = {1,2,3,4} dan B = {3,4,5,6}. Tentukan A ∪ B, A ∩ B, dan |A ∪ B|.
H-M2: Komplemen
Semesta U = {1,2,3,4,5,6,7,8} dan A = {2,4,6,8}. Tentukan A' (komplemen A).
H-M3: Subset & Power Set
Apakah {1,3} ⊆ {1,2,3,4}? Berapa kardinalitas power set P({a,b,c})?
H-M4: Difference (Selisih)
Diketahui A = {1,2,3,4,5}, B = {4,5,6,7}. Hitung A − B dan B − A.
SEDANG Aplikasi Konsep dengan Twist
H-S1: Inklusi-Eksklusi 3 Himpunan
Survei 100 mahasiswa: 60 suka Python, 45 suka Java, 30 suka C++. 20 suka Python&Java, 15 suka Java&C++, 10 suka Python&C++. 5 suka ketiganya. Berapa yang suka setidaknya satu bahasa?
H-S2: De Morgan & Simplifikasi
Sederhanakan ekspresi: (A ∪ B)' ∩ C menggunakan hukum De Morgan.
H-S3: Cartesian Product
Diketahui A = {1,2} dan B = {a,b,c}. Tentukan A × B dan |A × B|.
H-S4: Symmetric Difference
Tentukan A ⊕ B (symmetric difference) jika A = {1,2,3,4} dan B = {3,4,5,6}. Buktikan A ⊕ B = (A−B) ∪ (B−A).
SULIT Soal Kompleks Butuh Strategi
H-H1: Partisi Himpunan
Diberikan himpunan S = {1,2,3,4,5,6}. Tunjukkan bahwa P = {{1,2},{3,4},{5,6}} adalah partisi valid. Berapa banyak partisi dari S menjadi 2 subset tak-kosong (Bell number B₃ terapan)?
H-H2: Himpunan Tak Terhingga & Countability
Apakah himpunan bilangan genap E = {0,2,4,6,...} equipotent dengan ℕ = {0,1,2,3,...}? Konstruksi bijeksi f: ℕ → E. Apa implikasinya untuk |E| vs |ℕ|?
H-H3: Prinsip Inklusi-Eksklusi + Fungsi Surjektif
Berapa banyak fungsi surjektif dari A = {1,2,3,4} ke B = {a,b,c}? Gunakan prinsip inklusi-eksklusi.
TERINTEGRASI Himpunan + Probabilitas & Kombinatorika
H-T1: Himpunan + Probabilitas — Peluang Elemen Acak
Himpunan A = {1,2,3,4,5} dan B = {4,5,6,7,8} berada dalam semesta U = {1,...,10}. Sebuah elemen dipilih acak seragam dari U. Hitung P(A∪B), P(A∩B), dan P(A|B).
H-T2: Himpunan + Kombinatorika — Kardinalitas Subset
Sebuah panitia dipilih dari himpunan K = {k₁,...,k₈} (8 orang). Berapa banyak subset berukuran tepat 3 yang bisa dibentuk? Berapa di antaranya yang memuat k₁ DAN k₂?
H-T3: Himpunan + Teori Bilangan — Kardinalitas Himpunan Polinomial
Misalkan P adalah himpunan semua polinomial berderajat ≤ n−1 yang koefisiennya diambil dari ℤ_q = {0,…,q−1}. Jika q = 7 dan n = 4, berapa |P|? Apakah P ⊆ ℤ? Jelaskan.