Kecerdasan Artifisial

Pertemuan 09

Representasi Pengetahuan — Logika Proposisional

Mata Kuliah: Kecerdasan Artifisial (AI401) | 3 SKS

🎯 Capaian Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

  1. Menjelaskan kebutuhan representasi pengetahuan formal dalam AI
  2. Merepresentasikan pengetahuan dalam logika proposisional
  3. Mengevaluasi proposisi menggunakan tabel kebenaran
  4. Membuktikan entailment menggunakan aturan inferensi
  5. Mengonversi proposisi ke CNF dan menerapkan resolution

📋 Agenda Hari Ini

Bagian 1

  • Knowledge Base & Inference
  • Sintaks Logika Proposisional
  • Tabel Kebenaran
  • Entailment & Satisfiability

Bagian 2

  • Aturan Inferensi
  • Ekuivalensi Logika
  • Conjunctive Normal Form
  • Algoritma Resolution
  • Studi Kasus: Wumpus World

🤔 Mengapa Representasi Pengetahuan?

Pada Pertemuan 1–6, agen menyelesaikan masalah dengan pencarian.

Namun, pencarian memiliki keterbatasan:

Agen pencarian tidak bisa menalar tentang “mengapa” suatu tindakan benar — agen hanya mengeksplorasi state space.
Representasi Pengetahuan memungkinkan agen menyimpan fakta, menerapkan aturan, dan menarik kesimpulan baru secara logis.

📚 Knowledge Base & Inference Engine

Arsitektur Knowledge-Based Agent

TELL → Menambahkan fakta ke KB

ASK → Query & mendapatkan jawaban

💡 Contoh Knowledge Base

Skenario: Sistem keamanan pangkalan militer

TELL(KB, “Jika alarm aktif DAN tidak ada latihan, maka ada ancaman”)
TELL(KB, “Alarm aktif”)
TELL(KB, “Tidak ada latihan”)
ASK(KB, “Ada ancaman?”) → Ya (True)

📜 Logika Proposisional

Logika Proposisional adalah bahasa formal untuk merepresentasikan pernyataan yang bernilai True atau False.

✅ Proposisi

  • “Radar mendeteksi objek”
  • “5 + 3 = 8”
  • “Hujan turun hari ini”

❌ Bukan Proposisi

  • “Tutup pintu!” (perintah)
  • “Siapa komandannya?” (tanya)
  • “x + 2 = 5” (variabel bebas)

🔤 Simbol Proposisional

Simbol Representasi Contoh Dunia Nyata
P Simbol proposisional “Radar aktif”
Q Simbol proposisional “Ancaman terdeteksi”
True Selalu bernilai benar Tautologi
False Selalu bernilai salah Kontradiksi

🔗 Lima Konnektif Logika

Konnektif Simbol Nama Arti
Negasi ¬ NOT “bukan” / “tidak”
Konjungsi ∧ AND “dan”
Disjungsi ∨ OR “atau”
Implikasi ⇒ IMPLIES “jika…maka”
Bikonditional ⇔ IFF “jika dan hanya jika”

🔸 NOT, AND, OR

P ¬P
T F
F T

Negasi (NOT)

P Q P ∧ Q P ∨ Q
T T T T
T F F T
F T F T
F F F F

AND dan OR

💡 AND → true hanya jika keduanya true | OR → true jika minimal satu true

➡️ Implikasi (P ⇒ Q)

P Q P ⇒ Q Penjelasan
T T T Janji ditepati
T F F Janji dilanggar ❌
F T T Premis salah → true by default
F F T Premis salah → true by default
⚠️ Kunci: P ⇒ Q hanya false ketika P true tapi Q false (janji dilanggar)

🎖️ Contoh Implikasi: Pertahanan

RadarDeteksi ⇒ AktifkanSiaga

“Jika radar mendeteksi objek, maka aktifkan status siaga”

RadarDeteksi AktifkanSiaga Aturan Dilanggar?
T T Tidak ✅
T F Ya! ❌
F T Tidak ✅
F F Tidak ✅

↔️ Bikonditional (P ⇔ Q)

P ⇔ Q berarti P true jika dan hanya jika Q juga true. Keduanya harus memiliki nilai yang sama.
P Q P ⇔ Q
T T T
T F F
F T F
F F T

💡 P ⇔ Q ≡ (P ⇒ Q) ∧ (Q ⇒ P)

📊 Urutan Prioritas Operator

Prioritas Operator Nama
1 (tertinggi) ¬ Negasi
2 ∧ Konjungsi
3 ∨ Disjungsi
4 ⇒ Implikasi
5 (terendah) ⇔ Bikonditional
¬P ∧ Q ⇒ R   dibaca   ((¬P) ∧ Q) ⇒ R

🌐 Model dan Semantik

Model (m) adalah penetapan nilai kebenaran (True/False) untuk setiap simbol proposisional.

Contoh: Dengan simbol {P, Q, R}, salah satu model:

m = {P = True, Q = False, R = True}
💡 Dengan n simbol proposisional, terdapat 2n model yang mungkin.
3 simbol → 2³ = 8 model

⚊️ Entailment (⊧)

KB ⊧ α berarti: pada setiap model di mana KB bernilai true, α juga bernilai true.

Contoh:

KB = {P ∧ Q}

Apakah KB ⊧ P?

P Q P ∧ Q (KB) P (α) Cek
T T T ◄ T ✅
TFFT-
FTFF-
FFFF-

Satu-satunya model di mana KB true → P juga true. Jadi KB ⊧ P ✅

📈 Satisfiability, Validity, Unsatisfiability

Valid (Tautologi)

True di semua model

Contoh: P ∨ ¬P

Satisfiable

True di beberapa model

Contoh: P ∧ Q

Unsatisfiable (Kontradiksi)

False di semua model

Contoh: P ∧ ¬P

💡 Hubungan penting: KB ⊧ α   ⇔   (KB ∧ ¬α) adalah unsatisfiable

⚙️ Aturan Inferensi

Aturan yang menghasilkan kesimpulan baru yang valid dari premis yang diketahui.

Mengapa Penting?

  • Tabel kebenaran → eksponensial: O(2n)
  • Aturan inferensi → efisien
  • Langkah-langkah logis yang terverifikasi

Analogi

Tabel kebenaran = brute force
Aturan inferensi = bukti elegan

💡 Modus Ponens

P ⇒ Q
P

∴ Q

Contoh Pertahanan:

Premis 1: “Jika radar mendeteksi objek, maka aktifkan siaga” (RadarDeteksi ⇒ Siaga)

Premis 2: “Radar mendeteksi objek” (RadarDeteksi)

Kesimpulan: “Aktifkan siaga” (Siaga) ✅

💡 Modus Tollens

P ⇒ Q
¬Q

∴ ¬P

Contoh:

Premis 1: “Jika sistem bocor, maka alarm berbunyi” (Bocor ⇒ Alarm)

Premis 2: “Alarm tidak berbunyi” (¬Alarm)

Kesimpulan: “Sistem tidak bocor” (¬Bocor) ✅

📋 Aturan Inferensi Lainnya

Aturan Premis Kesimpulan
And-Elimination P ∧ Q P   (atau Q)
And-Introduction P,   Q P ∧ Q
Or-Introduction P P ∨ Q  (untuk sembarang Q)
Hypothetical Syllogism P ⇒ Q,   Q ⇒ R P ⇒ R
Resolution P ∨ Q,   ¬P ∨ R Q ∨ R

🔗 Contoh Rantai Inferensi

KB:

  1. IntrusionDetected ⇒ AlertSOC    (KB1)
  2. AlertSOC ⇒ ActivateFirewall    (KB2)
  3. IntrusionDetected    (KB3: fakta)

Langkah inferensi:

Step 1: Modus Ponens pada KB1 + KB3 → AlertSOC
Step 2: Modus Ponens pada KB2 + AlertSOC → ActivateFirewall

✅ KB ⊧ ActivateFirewall

⚖️ Ekuivalensi Logika Penting

Nama Ekuivalensi
Implication Elimination P ⇒ Q  ≡  ¬P ∨ Q
Contrapositive P ⇒ Q  ≡  ¬Q ⇒ ¬P
De Morgan 1 ¬(P ∧ Q)  ≡  ¬P ∨ ¬Q
De Morgan 2 ¬(P ∨ Q)  ≡  ¬P ∧ ¬Q
Distributive (∧ over ∨) P ∧ (Q ∨ R)  ≡  (P ∧ Q) ∨ (P ∧ R)
Distributive (∨ over ∧) P ∨ (Q ∧ R)  ≡  (P ∨ Q) ∧ (P ∨ R)
Double Negation ¬¬P  ≡  P

📝 Conjunctive Normal Form (CNF)

CNF adalah bentuk logika berupa konjungsi dari klausa, di mana setiap klausa adalah disjungsi dari literal.
(P ∨ ¬Q) ∧ (¬P ∨ R) ∧ (Q ∨ R)

3 klausa, masing-masing berisi literal yang dihubungkan OR

⚠️ CNF diperlukan sebagai input untuk algoritma Resolution

🛠️ 4 Langkah Konversi ke CNF

Step 1: Eliminasi bikonditional (⇔)
P ⇔ Q → (P ⇒ Q) ∧ (Q ⇒ P)
Step 2: Eliminasi implikasi (⇒)
P ⇒ Q → ¬P ∨ Q
Step 3: Pindahkan NOT ke dalam (De Morgan, Double Negation)
¬(P ∧ Q) → ¬P ∨ ¬Q
Step 4: Distribusi OR atas AND
P ∨ (Q ∧ R) → (P ∨ Q) ∧ (P ∨ R)

📝 Contoh Konversi CNF

Konversi: (P ⇒ Q) ∧ (Q ⇒ R)

Step 1: Tidak ada ⇔ → tetap: (P ⇒ Q) ∧ (Q ⇒ R)
Step 2: Eliminasi ⇒ → (¬P ∨ Q) ∧ (¬Q ∨ R)
Step 3: NOT sudah di level literal → tidak perlu De Morgan
Step 4: Sudah dalam bentuk konjungsi klausa → selesai
Hasil CNF: (¬P ∨ Q) ∧ (¬Q ∨ R)

⚖️ Aturan Resolution

Resolution menggabungkan dua klausa yang mengandung literal komplementer:

P ∨ Q
¬P ∨ R

Q ∨ R    (resolvent)

💡 P dan ¬P saling mengeliminasi, sisanya digabungkan dengan OR

🔎 Proof by Resolution (Refutation)

Untuk membuktikan KB ⊧ α:

  1. Tambahkan ¬α ke KB
  2. Konversi semua ke CNF
  3. Terapkan resolution berulang kali
  4. Jika dihasilkan klausa kosong (∅) → kontradiksi → KB ⊧ α terbukti!
⚠️ Prinsip: jika KB ∧ ¬α menghasilkan kontradiksi, maka α pasti benar.

🔎 Contoh Resolution

Buktikan: {P ⇒ Q, Q ⇒ R, P} ⊧ R

1. Tambah ¬R ke KB
2. Klausa CNF: C1: ¬P ∨ Q  |  C2: ¬Q ∨ R  |  C3: P  |  C4: ¬R
3. Resolve C1 + C3 (¬P dan P) → C5: Q
4. Resolve C2 + C5 (¬Q dan Q) → C6: R
5. Resolve C6 + C4 (R dan ¬R) → ∅ (klausa kosong)
Kontradiksi ditemukan! ∴ KB ⊧ R  ✅

👻 Wumpus World

Wumpus World adalah lingkungan grid 4×4 klasik untuk mendemonstrasikan penalaran logis dalam AI.
Wumpus World Grid

👻 Aturan Wumpus World

Elemen Dunia

  • 👻 Wumpus — monster
  • 🕳️ Pit — lubang jebakan
  • 🏆 Gold — emas (tujuan)

Persepsi Agen

  • 💨 Stench → Wumpus di sebelah
  • 🌊 Breeze → Pit di sebelah
  • ✨ Glitter → Gold di sel ini

👻 Penalaran di Wumpus World

Simbol proposisional:

  • Pi,j = ada Pit di sel (i,j)
  • Bi,j = ada Breeze di sel (i,j)

Aturan:

B1,1 ⇔ (P1,2 ∨ P2,1)

“Breeze di (1,1) jika dan hanya jika ada Pit di (1,2) atau (2,1)”

Jika kita tahu: ¬B1,1 (tidak ada breeze di 1,1)

¬B1,1 ⇒ ¬(P1,2 ∨ P2,1) ⇒ ¬P1,2 ∧ ¬P2,1

✅ Sel (1,2) dan (2,1) aman!

🎖️ Aplikasi: KB Pertahanan

Knowledge Base Sistem Keamanan Pangkalan:

KB1: PerimeterBreach ∧ ¬Drill ⇒ RealThreat
KB2: RealThreat ⇒ ActivateQRF
KB3: RealThreat ⇒ NotifyCommandCenter
KB4: PerimeterBreach  (fakta)
KB5: ¬Drill  (fakta)
Inferensi: RealThreat ✅ → ActivateQRF ✅ → NotifyCommandCenter ✅

🧠 Quiz Time!

Pertanyaan 1:

Kapan P ⇒ Q bernilai False?

A. P = False, Q = False
B. P = False, Q = True
C. P = True, Q = False ✅
D. P = True, Q = True

💡 Implikasi hanya false ketika premis true tapi konsekuen false (janji dilanggar)

🧠 Quiz Time!

Pertanyaan 2:

Aturan inferensi apa yang digunakan?
Premis: P ⇒ Q dan ¬Q → Kesimpulan: ¬P

A. Modus Ponens
B. Modus Tollens ✅
C. Hypothetical Syllogism
D. Resolution

🧠 Quiz Time!

Pertanyaan 3:

Apa hasil konversi CNF dari P ⇒ Q?

A. P ∧ Q
B. P ∨ Q
C. ¬P ∨ Q ✅
D. ¬P ∧ Q

💡 Implication Elimination: P ⇒ Q ≡ ¬P ∨ Q

🧠 Quiz Time!

Pertanyaan 4:

Dalam proof by resolution, apa yang menandakan bahwa α terbukti benar?

A. Semua klausa menjadi True
B. Dihasilkan klausa kosong (∅) ✅
C. Tidak ada resolvent baru
D. Semua literal positif

💡 Klausa kosong = kontradiksi = KB ∧ ¬α unsatisfiable = α terbukti!

📝 Ringkasan

Konsep Poin Kunci
Knowledge Base Kumpulan fakta & aturan; operasi TELL & ASK
Logika Proposisional 5 konnektif: ¬, ∧, ∨, ⇒, ⇔
Entailment KB ⊧ α jika α true di semua model di mana KB true
Aturan Inferensi Modus Ponens, Modus Tollens, Resolution, dll.
CNF Konjungsi klausa; 4 langkah konversi
Resolution Proof by refutation: KB ∧ ¬α → ∅ → terbukti

📅 Pertemuan Berikutnya

Pertemuan 10: Logika Predikat (First-Order Logic)

Representasi Pengetahuan yang Lebih Ekspresif

  • Keterbatasan logika proposisional
  • Sintaks FOL: konstanta, variabel, predikat, kuantor
  • Kuantor universal (∀) dan eksistensial (∃)
  • Unifikasi dan Most General Unifier
  • Forward & Backward Chaining

📚 Referensi

  1. Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th Ed.). Pearson. Chapter 7
  2. Poole, D.L. & Mackworth, A.K. (2023). Artificial Intelligence: Foundations of Computational Agents (3rd Ed.). Cambridge University Press. Chapter 5.
  3. CS188 Berkeley AI Materials: https://inst.eecs.berkeley.edu/~cs188/

Terima Kasih

🤖 Kecerdasan Artifisial

Pertemuan 09: Representasi Pengetahuan — Logika Proposisional


Ada pertanyaan?