Matdis — Bab 1
Logika & Penalaran
Fondasi seluruh matematika diskrit: cara membangun, mengevaluasi, dan menyimpulkan argumen yang valid secara formal.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 1. — Rosen, Discrete Mathematics, 8th ed., Ch. 1.
Mengapa Logika Itu Penting?
Setiap kali Anda menulis if (umur >= 17 && punyaKTP), Anda sedang menulis proposisi logika. Bug paling mahal di industri perangkat lunak sering bukan salah rumus, melainkan salah logika: negasi yang keliru, kondisi yang tidak pernah bernilai benar, atau else yang tak pernah tercapai.
Contoh klasik: negasi dari "umur ≥ 17 dan punya KTP" bukanlah "umur < 17 dan tidak punya KTP", melainkan "umur < 17 atau tidak punya KTP". Itu hukum De Morgan — dan salah menerapkannya menghasilkan validasi yang bocor.
Di luar pemrograman, logika adalah tata bahasa dari pembuktian matematika. Bab ini membekali Anda membaca dan menulis bukti secara presisi — keterampilan yang dipakai di seluruh bab berikutnya.
Analogi: Bahasa Pemrograman untuk Penalaran
Logika adalah bahasa pemrograman bagi penalaran. Proposisi = variabel boolean, konektor = operator (AND/OR/NOT), aturan inferensi = fungsi transformasi kebenaran. Theorem prover (Coq, Lean 4, Isabelle/HOL) adalah "compiler" yang mengecek validitas bukti matematika — termasuk bukti keamanan TLS 1.3 yang diverifikasi menggunakan miTLS secara formal.
1. Proposisi dan Konektor Logika
Definisi (Proposisi)
Proposisi adalah pernyataan deklaratif yang memiliki nilai kebenaran tepat satu: benar (T/1) atau salah (F/0). Bukan pertanyaan, bukan perintah, bukan kalimat ambigu.
Proposisi (valid)
- "2 + 2 = 4" — Benar
- "Jakarta ibu kota Indonesia" — Benar
- "3 > 7" — Salah
- "Setiap bilangan prima adalah ganjil" — Salah (2 prima & genap)
Bukan Proposisi
- "Apakah hari ini hujan?" (pertanyaan)
- "Enkripsi pesan ini!" (perintah)
- "x + 1 = 5" (variabel bebas)
- "Ini adalah kebohongan" (paradoks)
Lima Konektor Logika Utama
| Konektor | Simbol | Dibaca | Benar jika | Python |
|---|---|---|---|---|
| Negasi | ¬p | tidak p | p salah | not p |
| Konjungsi | p ∧ q | p dan q | keduanya benar | p and q |
| Disjungsi | p ∨ q | p atau q | minimal satu benar | p or q |
| Implikasi | p → q | jika p maka q | p salah atau q benar | (not p) or q |
| Bikondisional | p ↔ q | p ikk q | p dan q sama nilai | p == q |
2. Tabel Kebenaran
Tabel Kebenaran Lengkap (2 Variabel)
| p | q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Perhatikan: implikasi p→q hanya SALAH ketika p=T dan q=F (satu-satunya pasangan yang "mengkhianati janji").
Visualisasi SMIL: Aliran Nilai Logika
p=T ∧ q=T → konjungsi T → implikasi ke q terpenuhi.
3. Tautologi, Kontradiksi & Kontingen
Tautologi
Selalu benar untuk semua nilai variabel.
p ∨ ¬p
Hukum Excluded Middle — fondasi logika klasik.
Kontradiksi
Selalu salah untuk semua nilai variabel.
p ∧ ¬p
Hukum Non-Contradiction — tidak bisa benar dan salah sekaligus.
Kontingen
Bisa benar atau salah tergantung nilai variabel.
p → q
Tidak tautologi, tidak kontradiksi.
4. Ekivalensi Logika & Hukum-Hukum
Hukum-Hukum Logika (Rinaldi Munir Edisi 7, Bab 1)
Hukum De Morgan
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Komutatif & Asosiatif
p ∧ q ≡ q ∧ p
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributif
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Identitas & Dominasi
p ∧ T ≡ p | p ∨ F ≡ p
p ∧ F ≡ F | p ∨ T ≡ T
Absorpsi & Idempoten
p ∨ (p ∧ q) ≡ p
p ∧ p ≡ p | p ∨ p ≡ p
Implikasi & Kontraposisi
p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p
Verifikasi Hukum Logika Secara Interaktif
¬(p ∧ q) ≡ ¬p ∨ ¬q
| p | q | LHS | RHS | ≡? |
|---|---|---|---|---|
| T | T | F | F | ✓ |
| T | F | T | T | ✓ |
| F | T | T | T | ✓ |
| F | F | T | T | ✓ |
Semua baris ✓ → ekivalensi logika terbukti secara exhaustive.
5. Logika Predikat & Kuantor
Kuantor Universal & Eksistensial
∀x P(x) — Kuantor Universal
"Untuk semua x dalam domain, P(x) benar."
Negasi: ¬(∀x P(x)) ≡ ∃x ¬P(x)
Untuk membuktikan salah: cukup satu counterexample.
∃x P(x) — Kuantor Eksistensial
"Ada setidaknya satu x di mana P(x) benar."
Negasi: ¬(∃x P(x)) ≡ ∀x ¬P(x)
Untuk membuktikan benar: cukup satu witness.
Demo Interaktif: Kuantor pada Domain {1,2,3,4,5}
∀x P(x): SALAH
Memenuhi: 2, 4
Counterexample: x = 1
∃x P(x): BENAR
Witness: 2
6. Argumen Valid & Aturan Inferensi
Delapan Aturan Inferensi Fundamental
Modus Ponens
p → q
p
∴ q
Hujan → basah; hujan; ∴ basah.
Modus Tollens
p → q
¬q
∴ ¬p
Hujan → basah; tidak basah; ∴ tidak hujan.
Silogisme Hipotetis
p → q; q → r
∴ p → r
Silogisme Disjungtif
p ∨ q; ¬p
∴ q
Penambahan (Addition)
p
∴ p ∨ q
Penyederhanaan
p ∧ q
∴ p
Konjungsi
p; q
∴ p ∧ q
Resolusi
p ∨ q; ¬p ∨ r
∴ q ∨ r
Dasar SAT solver, AI reasoning.
Visualisasi SMIL: Rantai Inferensi Modus Ponens
7. Kuantor Bersarang
Urutan kuantor sangat penting — menukar ∀ dan ∃ bisa mengubah nilai kebenaran secara drastis:
∀x ∃y (x + y = 0)
Untuk setiap bilangan x, ada y = -x. BENAR di ℝ.
∃y ∀x (x + y = 0)
Ada satu y yang berlaku untuk semua x. SALAH di ℝ (y tidak bisa sekaligus 1, -1, dll).
∀x ∀y (x² + y² ≥ 0)
Urutan ∀∀ simetris. BENAR di ℝ.
8. Penerapan Logika di Informatika
Dari Tabel Kebenaran ke Sistem Nyata
Penyederhanaan Kondisi Program: Ekspresi !(a && b) setara dengan !a || !b (De Morgan). Kompilator dan linter memakai ekuivalensi logika untuk menyederhanakan percabangan dan memperingatkan kondisi yang selalu benar/salah.
Basis Data: Klausa WHERE pada SQL adalah ekspresi logika predikat. Query optimizer menulis ulang predikat memakai hukum distributif dan De Morgan agar indeks bisa terpakai — hasilnya sama, kecepatannya bisa berbeda ratusan kali.
Rangkaian Digital: Gerbang AND/OR/NOT adalah realisasi fisik konektor logika. Menyederhanakan ekspresi Boolean berarti memakai lebih sedikit transistor — dibahas lebih dalam pada Bab Aljabar Boolean.
Prolog & Sistem Pakar: Bahasa Prolog menjalankan program berupa klausa Horn; eksekusinya secara harfiah adalah pencarian bukti dengan modus ponens dan resolusi.
Verifikasi Formal: Alat seperti Coq, Lean, dan Isabelle/HOL memeriksa bukti matematika baris demi baris. Program kritis (kendali penerbangan, kereta otomatis) diverifikasi dengan cara ini agar kebenarannya terjamin, bukan sekadar "lolos pengujian".
9. Contoh Soal & Pembahasan
Soal 1: Tabel Kebenaran
Tunjukkan (p → q) ≡ (¬p ∨ q) menggunakan tabel kebenaran.
Soal 2: Hukum De Morgan
Negasikan: "Semua mahasiswa lulus DAN semua server online."
Soal 3: Validitas Argumen
Valid? P1: p→q, P2: q→r, P3: ¬r. Kesimpulan: ¬p.
Soal 4: Tautologi
Buktikan [(p → q) ∧ (q → r)] → (p → r) adalah tautologi.
Soal 5: Kuantor Bersarang
Nyatakan dalam bahasa alami dan tentukan nilai kebenaran di ℤ: ∀m ∃n (m + n = 0).
Soal 6: Identifikasi Aturan Inferensi
Identifikasi aturan inferensi pada argumen berikut: "Jika program lolos semua uji, maka program dirilis. Program tidak dirilis. Simpulkan tentang hasil ujinya."
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Ref: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 1.
Mudah
1. Tentukan nilai kebenaran: (p ∧ q) ∨ ¬p untuk p=T, q=F.
2. Tuliskan kontraposisi dari: "Jika bilangan genap maka habis dibagi 2."
3. Apakah ¬(p ∨ q) ≡ ¬p ∧ ¬q? Buktikan dengan tabel kebenaran.
4. Nyatakan dalam simbol: "Semua mahasiswa informatika mengambil mata kuliah algoritma."
Sedang
1. Gunakan resolusi untuk membuktikan: Dari {p ∨ q, ¬p ∨ r, ¬q ∨ r}, simpulkan r.
2. Buktikan ekivalensi: p → (q → r) ≡ (p ∧ q) → r.
3. Nyatakan kalimat: "Ada dosen yang semua mahasiswanya lulus." Formalisasi dengan kuantor berlapis.
4. Tentukan apakah argumen ini valid: Semua algoritma rekursif memerlukan basis. Quicksort rekursif. ∴ Quicksort memerlukan basis.
Sulit
1. Buktikan: ((p → q) ∧ (q → r) ∧ ¬r) → ¬p menggunakan Hypothetical Syllogism dan Modus Tollens. Tunjukkan setiap langkah deduksi.
2. Formalisasikan dan buktikan validitas: "Jika semua key aman dan ada protocol yang menggunakan key aman, maka ada protocol yang aman." Gunakan logika predikat.
3. Buktikan: ¬∃x(P(x) ∧ Q(x)) ≡ ∀x(P(x) → ¬Q(x)). Lalu terapkan untuk menuliskan secara formal pernyataan "tidak ada bilangan prima yang genap dan lebih besar dari 2".
Kasus Terintegrasi (2+ Topik)
Gunakan BAN Logic untuk memverifikasi protokol: A → B: {Na, A}_Kb. B → A: {Na, Nb}_Ka. A → B: {Nb}_Kb. Buktikan A |≡ B |~ Nb.
Formalisasikan dan tentukan nilai kebenaran: "Untuk setiap bilangan prima p > 2, ada bilangan bulat k sehingga p = 2k + 1." Gunakan ∀, ∃, dan implikasi berantai.
Diberikan premis: (1) "Jika basis data konsisten (K) maka tidak ada transaksi gagal (¬G)"; (2) "Ada transaksi gagal"; (3) "Jika basis data konsisten maka laporan akurat (L)". Apa yang dapat dan tidak dapat disimpulkan?