Kecerdasan Artifisial

Pertemuan 10

Logika Predikat (First-Order Logic)

Mata Kuliah: Kecerdasan Artifisial (AI401) | 3 SKS

🎯 Capaian Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

  1. Menjelaskan keterbatasan logika proposisional
  2. Memahami sintaks FOL: konstanta, variabel, predikat, fungsi, kuantor
  3. Merepresentasikan pengetahuan dalam logika predikat
  4. Menerapkan kuantor universal (βˆ€) dan eksistensial (βˆƒ)
  5. Melakukan proses unifikasi dan menemukan MGU
  6. Menerapkan forward chaining dan backward chaining

πŸ“‹ Agenda Hari Ini

Bagian 1

  • Keterbatasan Logika Proposisional
  • Sintaks FOL
  • Kuantor (βˆ€ dan βˆƒ)
  • Representasi Pengetahuan

Bagian 2

  • Unifikasi dan MGU
  • Forward Chaining
  • Backward Chaining
  • Aplikasi: Expert Systems

πŸ”™ Recap: Logika Proposisional

Pada Pertemuan 9, kita mempelajari:

  • Proposisi sebagai unit dasar (P, Q, R)
  • Konnektif logika: Β¬, ∧, ∨, β‡’, ⇔
  • Inferensi: Modus Ponens, Resolution
  • CNF dan pembuktian

⚠️ Tapi... logika proposisional punya keterbatasan besar!

⚠️ Keterbatasan Logika Proposisional

Masalah: "Semua tentara harus berani"

Logika Proposisional

P₁ β‡’ Q₁ (Adi berani)

Pβ‚‚ β‡’ Qβ‚‚ (Budi berani)

P₃ β‡’ Q₃ (Citra berani)

... ∞ proposisi!

Logika Predikat ⭐

βˆ€x [Tentara(x) β‡’ Berani(x)]


Satu kalimat untuk semua!

Tiga Keterbatasan Utama

Keterbatasan Penjelasan Solusi FOL
Tidak ada objek Tidak bisa merujuk pada "Drone Alpha-7" Konstanta, variabel
Tidak ada relasi Tidak bisa menyatakan "X lebih cepat dari Y" Predikat n-ary
Tidak ada kuantifikasi Tidak bisa menyatakan "semua" atau "ada" Kuantor βˆ€, βˆƒ

πŸ“ First-Order Logic (FOL)

Logika Predikat (FOL) adalah perluasan logika proposisional yang menambahkan kemampuan merepresentasikan objek, properti, relasi, dan kuantifikasi.

Disebut juga:

  • First-Order Logic (FOL)
  • First-Order Predicate Calculus
  • Predicate Logic

🧱 Elemen Sintaks FOL

Elemen Sintaks FOL

Gambar 2.1: Elemen-elemen sintaks First-Order Logic

Konstanta dan Variabel

πŸ“Œ Konstanta

Merujuk pada objek spesifik

  • Adi, Budi
  • DroneAlpha7
  • Jakarta
  • Skuadron11

❓ Variabel

Placeholder untuk objek belum ditentukan

  • x, y, z
  • Digunakan dengan kuantor
  • Dapat di-substitusi

Predikat (Predicates)

Predikat menyatakan properti atau relasi antar objek.
Jenis Contoh Arti
Unary (1 argumen) Pilot(Adi) Adi adalah pilot
Binary (2 argumen) LebihCepat(x, y) x lebih cepat dari y
Ternary (3 argumen) Dikirim(x, y, z) x dikirim dari y ke z

Fungsi (Functions)

Fungsi memetakan objek ke objek lain. Hasilnya adalah term, bukan nilai kebenaran.
Fungsi Contoh Hasil
komandanDari(x) komandanDari(Adi) objek (orang)
markasSkuadron(s) markasSkuadron(Skuadron11) objek (lokasi)

⚠️ Predikat vs Fungsi: Predikat β†’ nilai kebenaran (true/false). Fungsi β†’ objek.

Term

Term adalah ekspresi yang merujuk pada objek.

Definisi rekursif:

  1. Setiap konstanta adalah term β†’ Adi
  2. Setiap variabel adalah term β†’ x
  3. Fungsi diterapkan pada term β†’ komandanDari(Adi)
  4. Fungsi bersarang β†’ markasSkuadron(komandanDari(x))

Kalimat Atomik dan Kompleks

Kalimat Atomik

  • Pilot(Adi)
  • Menembak(DroneA, TargetB)
  • komandanDari(Adi) = Budi

Kalimat Kompleks

  • Pilot(Adi) ∧ Berani(Adi)
  • Β¬Musuh(X, Y)
  • Pilot(x) β‡’ Terlatih(x)

πŸ’‘ Konnektif (Β¬, ∧, ∨, β‡’, ⇔) sama seperti logika proposisional!

βˆ€ Kuantor Universal

βˆ€x P(x) β€” "Untuk semua x, P(x) berlaku"

Contoh:

  • βˆ€x [Tentara(x) β‡’ Berani(x)]
    "Semua tentara berani"
  • βˆ€x [Drone(x) β‡’ PunyaSensor(x)]
    "Semua drone punya sensor"

πŸ“Œ Pola umum: βˆ€x [Kategori(x) β‡’ Properti(x)]

Gunakan implikasi (β‡’), bukan konjungsi (∧)!

⚠️ Kesalahan Umum: βˆ€ dengan ∧

βœ… Benar

βˆ€x [Tentara(x) β‡’ Berani(x)]

"Jika x tentara, maka x berani"

❌ Salah

βˆ€x [Tentara(x) ∧ Berani(x)]

"Semua objek di dunia adalah tentara DAN berani" β€” termasuk meja, kucing, dll!

βˆƒ Kuantor Eksistensial

βˆƒx P(x) β€” "Ada setidaknya satu x sedemikian sehingga P(x)"

Contoh:

  • βˆƒx [KapalSelam(x) ∧ DiPerairan(x, Natuna)]
    "Ada kapal selam di perairan Natuna"

πŸ“Œ Pola umum: βˆƒx [Kategori(x) ∧ Properti(x)]

Gunakan konjungsi (∧), bukan implikasi (β‡’)!

⚠️ Kesalahan Umum: βˆƒ dengan β‡’

βœ… Benar

βˆƒx [KapalSelam(x) ∧ DiNatuna(x)]

"Ada objek yang kapal selam DAN di Natuna"

❌ Misleading

βˆƒx [KapalSelam(x) β‡’ DiNatuna(x)]

Terpenuhi oleh apapun yang bukan kapal selam!

πŸ”„ Kuantor Bersarang

Urutan kuantor sangat penting!

FOL Arti
βˆ€x βˆƒy Suka(x,y) Setiap orang menyukai setidaknya satu orang
βˆƒx βˆ€y Suka(x,y) Ada satu orang yang menyukai semua orang
βˆ€x βˆ€y Suka(x,y) Semua orang menyukai semua orang
βˆƒx βˆƒy Suka(x,y) Ada seseorang yang menyukai seseorang

⚠️ βˆ€x βˆƒy β‰  βˆƒy βˆ€x β€” pada βˆ€x βˆƒy, y bisa berbeda untuk setiap x!

πŸ”— Hubungan Antar Kuantor

Kuantor saling terhubung melalui negasi:

βˆ€x P(x) ≑ Β¬βˆƒx Β¬P(x)

βˆƒx P(x) ≑ Β¬βˆ€x Β¬P(x)

Kalimat Ekuivalen
Β¬βˆ€x Lulus(x) βˆƒx Β¬Lulus(x) β€” "Ada yang tidak lulus"
Β¬βˆƒx Sempurna(x) βˆ€x Β¬Sempurna(x) β€” "Semua tidak sempurna"

πŸ“ Pola Representasi Umum

Kalimat Natural Pola FOL
Semua X adalah Y βˆ€x [X(x) β‡’ Y(x)]
Ada X yang Y βˆƒx [X(x) ∧ Y(x)]
Tidak ada X yang Y βˆ€x [X(x) β‡’ Β¬Y(x)]
Hanya X yang Y βˆ€x [Y(x) β‡’ X(x)]

πŸ’‘ "Hanya X yang Y" β†’ implikasi dibalik: Y β‡’ X

πŸŽ–οΈ Contoh: Domain Militer

Knowledge Base:

1. Pilot(Adi)
2. Perwira(Adi)
3. Pangkat(Adi, Kapten)
4. DiSkuadron(Adi, Skuadron11)
5. βˆ€x [Pilot(x) β‡’ Terlatih(x)]
6. βˆ€x [Perwira(x) β‡’ βˆƒy [Memimpin(x, y)]]

Dengan KB ini, kita bisa menyimpulkan: Terlatih(Adi) βœ…

πŸ”— Unifikasi (Unification)

Unifikasi adalah proses menemukan substitusi variabel yang membuat dua ekspresi logika menjadi identik.

Substitusi ΞΈ: pemetaan variabel ke term

  • ΞΈ = {x/Adi} berarti "ganti x dengan Adi"

Contoh Unifikasi

Proses Unifikasi
Ekspresi 1 Ekspresi 2 Hasil
Pilot(x) Pilot(Adi) ΞΈ = {x/Adi} βœ…
Suka(x, y) Suka(Adi, Budi) ΞΈ = {x/Adi, y/Budi} βœ…
Pilot(Adi) Pilot(Budi) GAGAL ❌

Aturan Unifikasi

Kondisi Hasil Contoh
Variabel + term Berhasil Unify(x, Adi) = {x/Adi}
Konstanta = konstanta Berhasil Unify(Adi, Adi) = {}
Konstanta β‰  konstanta Gagal Unify(Adi, Budi) = FAIL
Fungsi sama, arg cocok Berhasil Unify(f(x), f(Adi)) = {x/Adi}
Occur check gagal Gagal Unify(x, f(x)) = FAIL

MGU (Most General Unifier)

MGU adalah substitusi paling umum yang membuat dua ekspresi identik β€” seminimal mungkin.

Contoh: Unifikasi Suka(x, y) dengan Suka(Adi, z)

  • θ₁ = {x/Adi, y/z} β†’ MGU βœ… (paling umum)
  • ΞΈβ‚‚ = {x/Adi, y/Budi, z/Budi} β†’ valid tapi bukan MGU

πŸ“ Latihan Unifikasi

Temukan MGU atau tentukan GAGAL:

# Ekspresi 1 Ekspresi 2 MGU
1 P(x, f(y)) P(g(z), f(z)) {x/g(z), y/z} βœ…
2 Q(x, x) Q(Adi, Budi) GAGAL ❌
3 R(x, f(x)) R(y, y) GAGAL (occur check) ❌

⏩ Forward Chaining

Forward Chaining (data-driven) dimulai dari fakta yang diketahui dan menerapkan aturan berulang kali untuk menghasilkan fakta baru.
Forward Chaining

Gambar 7.1: Proses forward chaining dari fakta ke kesimpulan

Contoh Forward Chaining

KB: Pilot(Adi), Perwira(Adi), Berpengalaman(Adi)

Aturan:

R4: βˆ€x [Pilot(x) β‡’ Terlatih(x)]
R5: βˆ€x [(Perwira(x) ∧ Terlatih(x)) β‡’ BolehMemimpin(x)]
R6: βˆ€x [(BolehMemimpin(x) ∧ Berpengalaman(x)) β‡’ KandidatKomandan(x)]

Query: KandidatKomandan(Adi)?

Langkah Aturan Fakta Baru
1 R4 {x/Adi} Terlatih(Adi)
2 R5 {x/Adi} BolehMemimpin(Adi)
3 R6 {x/Adi} KandidatKomandan(Adi) βœ…

βͺ Backward Chaining

Backward Chaining (goal-driven) dimulai dari query (goal) dan bekerja mundur mencari fakta dan aturan yang membuktikan query.
Backward Chaining

Gambar 8.1: Proses backward chaining dari goal ke fakta

Contoh Backward Chaining

Goal: KandidatKomandan(Adi)?

KandidatKomandan(Adi)          ← Goal
β”œβ”€β”€ R6: BolehMemimpin(Adi)?    ← Sub-goal 1
β”‚   β”œβ”€β”€ R5: Perwira(Adi)?      βœ… Fakta di KB
β”‚   └── R5: Terlatih(Adi)?     ← Sub-goal 1b
β”‚       └── R4: Pilot(Adi)?    βœ… Fakta di KB
β”‚       β†’ Terlatih(Adi) βœ…
β”‚   β†’ BolehMemimpin(Adi) βœ…
β”œβ”€β”€ R6: Berpengalaman(Adi)?    βœ… Fakta di KB
β†’ KandidatKomandan(Adi) βœ… TERBUKTI

βš–οΈ Forward vs Backward Chaining

Aspek Forward Chaining Backward Chaining
Arah Fakta β†’ Kesimpulan Goal β†’ Fakta
Nama lain Data-driven Goal-driven
Strategi Bottom-up Top-down
Cocok untuk Banyak query, KB kecil Satu query spesifik
Analogi "Apa yang bisa disimpulkan?" "Bagaimana membuktikan X?"

πŸ›‘οΈ Contoh: Analisis Keamanan Siber

KB: ServerWeb(S1), TerhubungInternet(S1), VersiLama(S1), ServerDB(S2), TerhubungKe(S1,S2)

R7: ServerWeb(x) ∧ TerhubungInternet(x) β‡’ DapatDiserang(x)
R8: DapatDiserang(x) ∧ VersiLama(x) β‡’ Rentan(x)
R9: Rentan(x) ∧ TerhubungKe(x,y) β‡’ TerancamLateral(y)
R10: TerancamLateral(x) ∧ ServerDB(x) β‡’ DataTerancam(x)
Langkah Fakta Baru
1DapatDiserang(S1)
2Rentan(S1)
3TerancamLateral(S2)
4DataTerancam(S2) ⚠️

πŸ“ Generalized Modus Ponens

Menggabungkan Modus Ponens dengan unifikasi untuk logika predikat.

Dari p₁', pβ‚‚', ..., pβ‚™' dan (p₁ ∧ pβ‚‚ ∧ ... ∧ pβ‚™ β‡’ q)

Simpulkan: qΞΈ

dimana ΞΈ meng-unifikasi setiap pα΅’' dengan pα΅’

Contoh:

Pilot(Adi) + DiWilayah(Adi, Timur) + [Pilot(x) ∧ DiWilayah(x,w) β‡’ BisaTerbang(x,w)]

ΞΈ = {x/Adi, w/Timur} β†’ BisaTerbang(Adi, Timur)

πŸ”§ Skolemisasi

Skolemisasi adalah proses mengganti kuantor eksistensial (βˆƒ) dengan fungsi Skolem untuk konversi ke CNF.

Aturan:

  • βˆƒx tanpa βˆ€ di luar β†’ ganti x dengan konstanta Skolem
  • βˆƒy di dalam βˆ€x β†’ ganti y dengan fungsi Skolem f(x)

Contoh:

βˆ€x [Tentara(x) β‡’ βˆƒy [Senjata(y) ∧ Membawa(x,y)]]

β†’ βˆ€x [Tentara(x) β‡’ Senjata(f(x)) ∧ Membawa(x, f(x))]

f(x) = "senjata yang dibawa tentara x"

πŸ’» Aplikasi: Expert Systems

Expert System = Knowledge Base + Inference Engine
Komponen Fungsi
Knowledge Base Fakta dan aturan dalam FOL
Inference Engine Forward/backward chaining
User Interface Input/output dengan pengguna
Explanation Menjelaskan proses reasoning

πŸ•ΈοΈ Aplikasi: Knowledge Graphs

Triple (subjek, predikat, objek) β‰ˆ kalimat atomik FOL

Knowledge Graph Triple FOL Equivalent
(Adi, tipePesawat, F16) TipePesawat(Adi, F16)
(F16, buatanNegara, AS) BuatanNegara(F16, AS)
(KapalSelam, subClassOf, KapalPerang) βˆ€x [KapalSelam(x) β‡’ KapalPerang(x)]

πŸ’‘ Contoh: Google Knowledge Graph, Wikidata, Knowledge graph intelijen

🧠 Quiz Time!

Pertanyaan 1:

Pola FOL yang benar untuk "Semua pilot terlatih" adalah:

A. βˆ€x [Pilot(x) ∧ Terlatih(x)]
B. βˆƒx [Pilot(x) β‡’ Terlatih(x)]
C. βˆ€x [Pilot(x) β‡’ Terlatih(x)] βœ…
D. βˆƒx [Pilot(x) ∧ Terlatih(x)]

πŸ’‘ βˆ€ + β‡’ untuk "semua X adalah Y"

🧠 Quiz Time!

Pertanyaan 2:

Apa hasil unifikasi P(x, f(x)) dengan P(Adi, y)?

A. GAGAL β€” occur check
B. ΞΈ = {x/Adi, y/f(Adi)} βœ…
C. ΞΈ = {x/Adi, y/x}
D. ΞΈ = {x/y, f(x)/Adi}

πŸ’‘ Unifikasi argumen 1: x=Adi, lalu argumen 2: f(Adi) dengan y β†’ y=f(Adi)

🧠 Quiz Time!

Pertanyaan 3:

Metode inferensi yang dimulai dari goal dan bekerja mundur ke fakta disebut:

A. Forward Chaining
B. Backward Chaining βœ…
C. Resolution
D. Unifikasi

πŸ“ Ringkasan

Konsep Poin Kunci
FOL Perluasan logika proposisional + objek, relasi, kuantor
Elemen Konstanta, variabel, predikat, fungsi, kuantor
βˆ€ (Universal) "Untuk semua" β€” gunakan dengan β‡’
βˆƒ (Eksistensial) "Ada" β€” gunakan dengan ∧
Unifikasi Substitusi agar dua ekspresi identik
Forward Chaining Fakta β†’ aturan β†’ fakta baru (data-driven)
Backward Chaining Goal β†’ sub-goals β†’ fakta (goal-driven)

πŸ“… Pertemuan Berikutnya

Pertemuan 11: Penalaran dengan Ketidakpastian - Probabilitas

Probabilitas Bersyarat dan Teorema Bayes

  • Sumber ketidakpastian dalam AI
  • Probabilitas bersyarat
  • Teorema Bayes
  • Naive Bayes classifier

πŸ“š Referensi

  1. Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th Ed.). Pearson. Chapter 8-9
  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 10: Logika Predikat (First-Order Logic)


Ada pertanyaan?