Apa kursus ini, dan bagaimana menggunakannya
Ini adalah kursus kedua di Ilmu Komputer Universitas: discrete matematika diskrit — matematika objek yang dapat Anda daftarkan: pernyataan, himpunan, grafik, hitungan. Ini adalah alat pembuktian di balik algoritma, basis data dan setiap klaim yang benar secara konstruksi dalam CS.
Batasan ruang lingkup, dinyatakan sekali: kursus studi, bukan gelar; setiap masalah asli dan mandiri, dan setiap pembuktian menyebutkan strateginya.
- Unit 2.1–2.3 adalah mesin pembuktian: logika, himpunan, induksi.
- Unit 2.4–2.6 adalah mesin kombinatorial: penghitungan, grafik, probabilitas diskrit.
Kebiasaan diskrit: sebutkan strategi sebelum pembuktian — langsung, kontraposisi, kontradiksi, induksi — dan setiap identitas adalah sesuatu yang dapat Anda verifikasi pada contoh kecil terlebih dahulu.
Logika dan pembuktian
Mengapa ini penting. Logika adalah sistem tipe pembuktian: terjemahkan klaim, periksa argumen, dan pilih bentuk pembuktian sebelum menulis baris.
Gagasan, dengan gambar. Proposisi terhubung melalui ¬, ∧, ∨, →, ↔; tabel kebenaran menentukan kebenaran setiap rumus atas variabelnya ✓. Tabel ekuivalensi kunci: $p \to q \equiv \neg p \lor q$; kontraposisi $p \to q \equiv \neg q \to \neg p$; De Morgan $\neg(p \land q) \equiv \neg p \lor \neg q$ ✓. Logika predikat menambahkan kuantor $\forall x\, P(x)$ dan $\exists x\, P(x)$, dengan negasi membalikkan masing-masing.
Turunan (mengapa tiga bentuk pembuktian). Untuk membuktikan $p \to q$: bukti langsung (asumsikan $p$, turunkan $q$); kontraposisi (buktikan $\neg q \to \neg p$ — berguna ketika negatif lebih mudah ditangani); kontradiksi (asumsikan $p \land \neg q$, turunkan hal yang mustahil) ✓. Setiap bentuk mengubah tujuan menjadi asumsi yang dapat Anda komputasikan — memilih bentuk adalah memilih data Anda.
Contoh terpecahkan 1 — penerjemahan. Klaim: setiap email memiliki tepat satu alamat: $\forall e\,\exists! a\,\text{Has}(e, a)$. Negasinya mendorong $\forall$ ke $\exists$ dan menegatkan apa yang mengikuti: ada email yang tidak memiliki alamat, atau memiliki dua atau lebih ✓. Satu email seperti itu membantah klaim tersebut. Terjemahkan, negasikan, baca ulang: kebiasaan tiga langkah.
Contoh terpecahkan 2 — strategi yang dinamakan. Klaim: jika $n^2$ genap maka $n$ genap. Strategi: kontraposisi (negasi lebih ramah). Bukti: asumsikan $n$ ganjil, sehingga $n = 2k+1$; kemudian $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, ganjil ✓ — kontraposisi terbukti, sehingga klaimnya.
Kesalahan umum. Membuktikan kebalikan dari apa yang diminta (arah penting: $p \to q$ bukan $q \to p$). Mendistribusikan negasi tanpa membalik penghubung (Hukum De Morgan mengubah ∧ menjadi ∨). Menulis contoh di mana bukti universal diperlukan — sebuah contoh hanyalah pengecekan, bukan bukti.
Ringkasan. Terjemahkan → pilih bentuk (langsung / kontraposisi / kontradiksi) → tulis langkah-langkah yang beralasan; $p \to q \equiv \neg p \lor q$; De Morgan membalik; negasi menukar $\forall/\exists$; tabel kebenaran memverifikasi, pohon pembuktian mengstrukturkan.
Himpunan, fungsi, dan relasi
Mengapa hal ini penting. Himpunan adalah model data dalam matematika diskrit; fungsi adalah pipa bertipe di antaranya; relasi membawa struktur yang mendasari database dan grafik yang dibangun darinya.
Ide dasar, dengan ilustrasi. Operasi: gabungan, irisan, selisih, komplemen; himpunan kuasa $\mathcal{P}(A)$ = semua subhimpunan, $|\mathcal{P}(A)| = 2^{|A|}$ ✓. Fungsi diklasifikasikan berdasarkan panahnya: injektif (tidak ada dua input memiliki output yang sama), surjektif (setiap output tercapai), bijektif (keduanya — pasangan sempurna) ✓. Komposisi $g \circ f$ menerapkan $f$ lalu $g$; bijeksi membalikkan.
Turunan (mengapa bijeksi dapat digunakan untuk menghitung). Bijeksi memasangkan setiap elemen dari $A$ dengan tepat satu dari $B$, sehingga $|A| = |B|$ ketika ada — dan menemukan bijeksi ADALAH bukti penghitungan ✓. Itulah sebabnya jumlah subhimpunan dari himpunan $n$ berpasangan dengan string bit sepanjang $n$ (setiap elemen masuk atau tidak — satu bit per elemen), membuktikan $2^n$ tanpa perlu mendaftar ✓.
Contoh terarah 1 — klasifikasikan tiga diagram panah. $f: \mathbb{Z} \to \mathbb{Z}$ oleh $f(n) = 2n$: injektif (input berbeda → hasil berbeda, ganda) tidak surjektif (bilangan ganjil tidak tertuju) ✓; $g(n) = \lfloor n/2 \rfloor$: surjektif tidak injektif ✓; $h(n) = -n$: bijektif — inversnya sendiri ✓.
Contoh terpecahkan 2 — uji relasi. Pada $\{1,2,3\}$: $R = \{(1,1), (2,2),(3,3),(1,2),(2,1)\}$ — refleksif (semua loop), simetris (sisi datang berpasangan) dan transitif — rantai $(1,2),(2,1)$ mensyaratkan $(1,1)$ dan rantai $(2,1),(1,2)$ mensyaratkan $(2,2)$, keduanya hadir ✓. Jadi $R$ adalah relasi ekuivalensi dengan kelas $\{1,2\}$ dan $\{3\}$ — periksa setiap sifat terhadap definisi, bukan intuisi.
Kesalahan umum. Membingungkan $\in$ (anggota) dengan $\subseteq$ (himpunan bagian). Menulis $f \circ g$ untuk $g \circ f$ (komposisi dibaca dari kanan ke kiri). Menguji simetri dengan melihat satu pasangan alih-alih semua.
Ringkasan. Gabungan/irisan/selisih/komplemen; $|\mathcal{P}(A)| = 2^{|A|}$ (bijeksi dengan string bit); injektif/surjektif/bijektif oleh panah; komposisi dari kanan ke kiri; sifat relasi — refleksif, simetris, antisimetris, transitif — diuji berdasarkan definisi.
Induksi dan rekursi
Mengapa hal ini penting. Induksi adalah pembuktian kebenaran setiap perulangan dan setiap struktur data rekursif; rekursi adalah induksi yang berjalan terbalik.
Gagasan, dengan gambar. Untuk membuktikan $\forall n \ge n_0\; P(n)$: kasus dasar ($P(n_0)$) + langkah induktif (asumsikan $P(k)$ — hipotesis induksi — turunkan $P(k+1)$) ✓. Rekursi mendefinisikan $F$ oleh panggilan yang lebih kecil: faktorial $0! = 1$, $n! = n \cdot (n-1)!$ — tangga yang sama, dibangun alih-alih didaki.
Penurunan (mengapa induksi valid). Langkah membuktikan bahwa jika anak tangga $k$ berlaku maka anak tangga $k+1$ berlaku; kasus dasar membuktikan anak tangga $n_0$; pengurutan memberikan setiap anak tangga hingga sebarang $n$ — induksi adalah modus ponens berulang ✓. Deteksi kesalahan: tidak ada kasus dasar (tangga di udara), hipotesis tidak dipanggil (langkah yang membuktikan apa-apa), atau langkah dari $k$ yang mengasumsikan lebih banyak daripada $P(k)$.
Contoh terpecahkan 1 — identitas penjumlahan. Klaim: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$. Strategi: induksi. Kasus dasar $n=1$: $1 = \frac{1 \cdot 2}{2}$ ✓. Langkah: asumsikan $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$; lalu $\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$ ✓ — hipotesis digunakan, aljabar ditunjukkan, klaim tertutup.
Contoh terpecahkan 2 — bukti cacat tertangkap. Klaim bahwa semua kuda memiliki warna yang sama: basis benar secara trivial; langkah — kurangi satu kuda dari setiap sisi — gagal pada $k+1 = 2$ karena dua himpunan tumpang tindih tidak memiliki kuda ✓ — langkah harus berlaku untuk SETIAP $k$, termasuk yang terkecil; sebuah langkah yang diam-diam membutuhkan $k \ge 2$ tanpa basis $P(2)$ adalah kesalahan klasik. kesalahan.
Kesalahan umum. Mengabaikan basis — hipotesis ditambah langkah tidak membuktikan apa-apa tanpa landasan. Menggunakan $P(k+1)$ untuk membuktikan $P(k+1)$ (sirkuler). Induksi kuat dinyatakan tetapi langkah biasa ditulis — sebutkan mana dan lakukan yang.
Ringkasan. Basis + hipotesis + langkah, hipotesis disebut secara eksplisit; induksi kuat mengasumsikan semua anak tangga di bawahnya; rekursi = cermin induksi (didefinisikan ke bawah); kesalahan: basis hilang, hipotesis tidak terpakai, langkah valid hanya untuk $k$ yang besar.
Penghitungan dan kombinatorika
Mengapa ini penting. Penghitungan adalah aritmatika analisis kompleksitas: ukuran ruang keadaan, jumlah cabang, berapa banyak di balik setiap batas perulangan.
Ide, dengan gambar. Aturan penjumlahan: pilihan saling lepas ditambahkan; aturan perkalian: pilihan berurutan dikalikan ✓. Permutasi (terurut): $P(n, r) = \frac{n!}{(n-r)!}$; kombinasi (tidak terurut): $\binom{n}{r} = \frac{n!}{r!\,(n-r)!}$ ✓. Inklusi–Eksklusi: $|A \cup B| = |A| + |B| - |A \cap B|$ — tambahkan, lalu kurangi penghitungan ganda.
Turunan (mengapa rumus dibagi). Permutasi memilih dan mengatur: $n$ pilihan, lalu $n-1$, …, $r$ faktor — kalikan. Kombinasi mengidentifikasi susunan dari $r$ objek yang sama: setiap himpunan $r$ telah dihitung $r!$ kali sebagai susunan — bagi dengan $r!$ ✓. Pembagian adalah seluruh perbedaan antara pemilihan berurutan dan tak berurutan.
Contoh terpecahkan 1 — komite. Tim 3 dari 8 orang, dengan satu pemimpin yang ditunjuk: pilih tim $\binom{8}{3} = 56$, pilih pemimpin di antaranya 3 cara → $168$ ✓; atau pilih pemimpin terlebih dahulu (8) lalu 2 anggota dari 7 ($\binom{7}{2} = 21$) → $168$ — dua jalur penghitungan, satu jawaban, dan kesepakatan adalah pengecekan.
Contoh terpecahkan 2 — prinsip inkluksi-eksklusi dengan tiga himpunan. Di antara 100 siswa: 45 suka teh, 35 kopi, 30 cokelat; 12 suka teh∧kopi, 10 suka teh∧cokelat, 8 suka kopi∧cokelat; 5 ketiganya. Minimal satu: $45+35+30-12-10-8+5 = 85$ ✓ — tidak ada: $100 - 85 = 15$. Tambah tunggal, kurangi pasangan, tambahkan tripel: setiap elemen dihitung tepat sekali.
Kesalahan umum. Menambahkan di mana pilihan bersifat berurutan (jalur × kendaraan dikalikan). Menggunakan permutasi di mana urutan tidak relevan (komite adalah kombinasi). Menerapkan prinsip inklusi-eksklusi dua himpunan untuk tiga himpunan (triplet kembali dengan tanda plus).
Ringkasan. Himpunan saling lepas → tambahkan; berurutan → kalikan; $P(n,r)$ terurut, $\binom{n}{r} = P/r!$ tidak terurut; inklusi-eksklusi: + tunggal − pasangan
- triplet; hitung dengan dua cara dan bandingkan — cek jumlah kombinatorika.
Graf dan pohon
Mengapa ini penting. Graf adalah model universal — jaringan, keadaan, ketergantungan; pohon adalah mesin utama pencarian dan penyimpanan; dan lemma guncangan tangan adalah identitas wajib pertama dalam kursus.
Ide, dengan gambar. $G = (V, E)$; representasi: matriks ketetanggaan matriks (ruang $n^2$, uji sisi $O(1)$), daftar ketetanggaan ($O(|V|+|E|)$) ✓. Pohon: terhubung, tanpa siklus, $|E| = |V| - 1$ ✓. Penelusuran: (tumpukan/rekursi, penemuan komponen). (tumpukan/rekurensi, penemuan komponen).
Turunan (mengapa jabat tangan harus berlaku). Setiap sisi menyumbang 1 titik berderajat ganjil adalah genap; graf di mana semua 2 jumlah derajat: $\sum_{v} \deg(v) = 2|E|$ ✓ — implikasi langsung: jumlah verteks berderajat ganjil adalah genap; graf di mana semua $n \ge 2$ graf dengan derajat simpul berbeda tidak dapat ada (derajat $0..n-1$ tetapi 0 dan $n-1$ tidak dapat berdampingan) ✓.
Contoh terpecahkan 1 — pemilihan model. (Soal desain) pertemanan sosial (tak berarah, daftar ketetanggaan — jarang), ketergantungan tugas (berarah tak bersiklus, matriks jika kecil — uji siklus), metro kota (terbobot, antrean Dijkstra — di luar cakupan, disebut demikian) ✓ — simetri soal menentukan graf, kepadatan menentukan representasinya. representasi.
Contoh terarah 2 — aritmatika pohon. Sebuah pohon memiliki 12 titik sudut di mana 5 adalah daun (derajat 1): dengan $|E| = 11$ dan lempeng tangan, internal 7 titik sudut membawa jumlah derajat $22 - 5 = 17$ ✓ — setiap soal pohon adalah perjalanan melalui $|E| = |V| - 1$ ditambah $\sum \deg = 2|E|$.
Kesalahan umum. Melupakan penghitungan derajat 0 (titik sudut terisolasi adalah Menggagas BFS memberikan jalur terpendek pada graf berbobot (tidak — hal itu memerlukan metode berbobot). yang memerlukan metode berbobot).
tak bersiklus + $G = (V,E)$; urutan tingkat BFS / urutan komponen DFS; $|E| = |V|-1$, jumlah derajat ganjil genap; pilih model dari $\sum \deg = 2|E|$, jumlah derajat ganjil genap; pilih model dari simetri masalah.
Probabilitas diskrit
Mengapa ini penting. Algoritma acak, analisis kasus rata-rata, dan pencitraan (hashing) semuanya berjalan berdasarkan probabilitas diskrit yang presisi — penghitungan yang sama dari 2.4, sekarang pada kemungkinan yang sama besar.
Gagasan, dengan gambar. Sebuah ruang sampel $\Omega$ dari hasil-hasil yang memiliki peluang setara; kejadian adalah himpunan bagian; $P(E) = |E|/|\Omega|$ ✓. Probabilitas bersyarat $P(A \mid B) = \frac{P(A \cap B)}{P(B)}$; Teorema Bayes $P(A \mid B) = \frac{P(B \mid A) P(A)} {P(B)}$ ✓; independensi $P(A \cap B) = P(A)P(B)$.
Penurunan rumus (mengapa kondisi mempersempit dunia). Kondisi pada $B$ hanya mempertahankan hasil-$B$ dan menormalisasi bobotnya agar menjumlahkan ke 1 — pecahan dari dunia $B$ di mana $A$ juga berlaku ✓. Itu adalah seluruh pembilang/penyebut Bayes: $P(B \mid A)P(A)$ mengukur ukuran potongan $A \cap B$; $P(B)$ menskalakan ulang ke dunia $B$.
Contoh terpecahkan 1 — dadu dengan menghitung. Dua dadu adil: $\Omega$ memiliki 36 pasangan. $P(\text{sum} = 7) = 6/36 = 1/6$ (enam pasangan); $P(\text{sum} = 11) = 2/36$ ✓; $P(\text{sum} = 7 \text{ or } 11) = 8/36 = 2/9$ — penghitungan dari 2.4 melakukan seluruh pekerjaan.
Contoh terpecahkan 2 — Bayes pada tes medis. Suatu penyakit menyerang 1 %; sebuah tes memiliki sensitivitas 90 % dan spesifisitas 90 %. $P(\text{dis} \mid +) = \frac{0.9 \times 0.01}{0.9 \times 0.01 + 0.1 \times 0.99} = \frac{0.009} {0.108} = 1/12 \approx 8.3\ \%$ ✓ — aritmatika yang sama dengan MED12 §4, diturunkan di sini dari pohon: kondisi langka tetap tidak mungkin setelah bukti tidak sempurna.
Kesalahan umum. Menambahkan probabilitas bersyarat seolah-olah saling bebas (dunia pengkondisian harus merupakan satu dunia). Membingungkan $P(A \mid B)$ dengan $P(B \mid A)$ (kesalahan jaksa). Menghitung hasil dari kemungkinan berbeda sebagai sama (hanya hasil yang memiliki kemungkinan sama yang memberikan $|E|/|\Omega|$).
Ringkasan. $P = |E|/|\Omega|$ pada hasil yang memiliki kemungkinan sama; $P(A \mid B) = P(A \cap B)/P(B)$ — cabang-B dinormalisasi; Bayes menyesuaikan skala irisan antar dunia; independensi mengalikan; dadu, kartu dan tabel hash semuanya adalah masalah penghitungan di baliknya.