1.1. PENGENALAN LOGIKA ORDE PERTAMA (FIRST ORDER LOGIC)
First order logic adalah sebuah bahasa formal yang digunakan
di ilmu matematika, philosophy, bahasa dan ilmu computer. Disebut juga kalkulus
predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang
tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat
dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan
(well form). Kalkulus predikat bisa menganalisakan kalimat-kalimat ke dalam
subjek dan argumen dalam berbagai cara yang berbeda-beda, yang pada akhirnya
kalkulus predikat bisa digunakan untuk memecahkan problem of multiple
generality (masalah dalam berbagai keadaan umum) yang telah membingungkan
sebagian besar ahli-ahli logika abad pertengahan. Dengan menggunakan logika
predikat ini, untuk pertama kalinya, para ahli-ahli logika bisa memberikan
quantifier yang cukup umum untuk merepresentasikan semua argumen yang terdapat
pada natural language.
Pemanfaatan FOL untuk merepresentasikan fakta adalah salah
satu teknik dasar yang sudah sejak lama dipakai untuk dapat mengkodekan bahasa
alami ke dalam bentuk formal. Dengan menggunakan FOL, diharapkan fakta (dan
juga pertanyaan) dapat direpresentasikan secara tepatke dalam konteksnya
masing-masing, sehingga jawaban akhir yang dikembalikan kepada pengguna adalah
jawaban yang tingkat kesasihannya (validity, di dalamnya mencakup consistency
dan informativeness) sangat tinggi. Jika kita berbicara mengenai logika
predikat, maka patut diperhatikan bahwa pada tahun 1879, filsuf berkebangsaan
Jerman yang bernama Gottlob Frege menerbitkan sebuah risalat yang luar biasa,
yang berjudul the Begriffsschrift (“Concept Script”). Monograp yang brilian ini
dianggap sebagai asal muasal dari teori logika modern. Akan tetapi, dalam
risalat milik Friege ini masih terdapat banyak kekurangan dalam beberapa bagian
dan janggal dalam penotasiannnya. Walaupun demikian, penemuan Frege ini tetap
diakui. Selain penemuan dari Frege, formulasi dari logika predikat yang sering
digunakan sekarang adalah firstorder logic atau yang biasa dikenal dengan
kalkulus predikat yang tercatat dalam Principle of Theorical Logic yang ditulis
oleh David Hilbert dan Wilhelm Ackerman pada tahun 1928. First order logic dalam
hal ini merupakan dasar pendiri logika matematika modern.
Di sini hanya akan disediakan beberapa poin penting yang
membedakan kalkulus predikat dengan logika Aristotle. Beberapa poin tersebut
diantaranya:
Di dalam kalkulus predikat didefinisikan bahwa subjek adalah
hanya sebuah individu tidak pernah merupakan sekelompok individu. Karena subjek
dalam kalkulus predikat ini hanyalah sebuah individu, maka subjek di sini lebih
umum untuk disebutkan sebagai individual. Kalkulus predikat memakai banyak
simbol-simbol khusus untuk menotasikan sesuatu. Huruf kecil a, b, c, d, …, z
digunakan untuk menyatakan individual. Huruf kapital M, N, P, Q, R, … digunakan
untuk menyatakan predikat. Jika terdapat notasi seperti Ma, maka dikatakan
bahwa a adalah argument untuk M. Selain huruf kecil dan huruf kapital, kalkulus
predikat juga menggunakan beberapa simbol khusus untuk menotasikan
operator-operator logika. Beberapa simbol khusus itu adalah: ∧ ∨ ~ ⊃ ≡
Sebuah formula adalah ekpresi yang memiliki arti dan
dibangun oleh atom-atomnya dan digabungkan dengan menggunakan operatoroperator
logika. Kalkulus predikat memiliki kapabilitas yang besar dalam mengekspresikan
suatu hal. Banyak pernyataan dalam natural language yang bisa direpresentasikan
dengan baik oleh kalkulus predikat. Hal inilah yang kurang dimiliki oleh logika
Aristoteles.
Dalam first-order logic yang paling utama adalah bahwa dunia
berisi objek-objek yaitu identitas (ciri-ciri individu) dan sifat (properties)
yang membedakan mereka dengan objek yang lain. Diantara objek tersebut, akan
dibuat bermacam-macam relasi. Beberapa relasi adalah fungsi yaitu hubungan
dimana hanya ada satu nilai untuk satu input. Jadi pada first-order logic
mengasumsikan “world” memuat :
·
Objek : hal-hal yang berhubungan
dengan identitas individu, misalnya : manusia, rumah, teori-teori, warna,
mobil, dan lain-lain.
·
Sifat (properties): sifat benda yang
membedakannya dari benda lain, misalnya: merah, bulat, tipis, dan lain-lain
·
Relasi : hubungan antara benda yang
satu dengan benda yang lainnya, misalnya: lebih besar dari, lebih kecil dari,
memiliki, terjadi setelah, dan lain-lain.
·
Fungsi (Functions): merupakan subset
dari hubungan di mana hanya ada satu “nilai” untuk setiap “input” yang
diberikan, misalnya: ayah dari, teman baik, dan lain-lain.
First Order Logic sangat penting dalam ilmu matematika,
filsafat, kecerdasan buatan, karena ruang lingkupnya, sebab keberadaan manusia
sehari-hari selalu berhubungan dengan obyek dan hubungan antar manusia sendiri.
Sehingga kita tidak dapat menyangkal bahwa dunia ini terdiri dari obyek dan
hubungan (relasi).
1.2. SINTAK DAN SEMANTIK LOGIKA ORDE PERTAMA
·
Model
Sebuah model adalah sebuah situasi yang menjelaskan hal-hal
yang menjadi konteks pembicaraan. Untuk membentuk sebuah model, diperlukan
adanya kosa-kata (vocabularies), yaitu daftar istilah yang membentuk model
tersebut. Sebuah kosa-kata berisikan topik pembicaraan dan bahasa (simbol) yang
digunakan dalam pembicaraan. Dalam contoh kalimat‘ayah dan anto makan sepiring
nasi’, akan terdapat kosa-kata sebagai berikut: {(ayah,1), (anto,0),(makan,2),
(nasi,1)}. Dalam kosa-kata ini akan terlihat bagaimana relasi antara fakta
atauvariabel yang satu dengan lainnya di dalam representasi. Perlu dibedakan
antara fakta (sebuah konstanta / non-binding variable), dengan variabel yang
dapat menampung sebuah fakta (binding variable). Dalam contoh, relasi ‘makan’
menjelaskan bahwa aktivitas tersebut dapat terjadi jika melibatkan dua
konstanta (relasi biner yang memiliki arity2). Angka 1 menjelaskan bahwa
terjadi relasi tunggal (arity1), yang dapat diisikan (binding) dengan sebuah
konstanta. Angka 0 menjelaskan sebuah konstanta, dan bukan merupakan relasi.
·
Syntax
FOL: Elemen-Elemen Dasar
Elemen-elemen dasar FOL:
Constants : KingJohn, 2, UB, ITS, UI, Malang, Depok , . . .
Predicates : Brother , >, Loves, Membenci , Mengajar , .
. .
Functions : Sqrt , LeftLegOf , Ayah, . . .
Variables : x , y , a, b, . . .
Connectives : ∧ ∨ ¬ ⇒ ⇔
Equality : =
Quantifiers : ∀ ∃
·
Syntax FOL
: Kalimat Atomic
Definisi atomic sentence : predicate(term1, , termn) atau
term1 = term2
Definisi term :
function(term1, , termn) atau constant atau
variable
Contoh :
Brother (KingJohn, RichardTheLionheart )
> (Length(LeftLegOf (Richard)), Length(LeftLegOf
(KingJohn)))
·
Syntax FOL
: Kalimat Kompleks
Kalimat kompleks complex sentence terdiri dari sentence yang
digabungkan dengan connective.
Definisi complex sentence : ¬S, S1∧ S2, S1∨ S2, S1 ⇒ S2, S1 ⇔ S2
Contoh :
Sibling(KingJohn, Richard ) ⇒ Sibling(Richard , KingJohn)
>(1, 2) ∨ ≤(1,
2)
>(1, 2) ∧ ¬>(1,
2)
Belajar (x , SC) ⇒ Mengerti(x
, AI)
·
Semantics
FOL : Truth & Model
Sama halnya dengan. Proposisi Logic (PL), sebuah kalimat FOL
bisa juga dikatakan true terhadap sebuah model.
Namun, sebuah kalimat bisa diinterpretasikan banyak cara
dalam sebuah model.
Model berisi :
Objects : elemen-elemen di dalam dunia (domain elements).
Relations : hubungan antara elemen-elemen tersebut.
Sebuah interpretasi mendefinisikan referent (“yang
dipetakan”)
Constant symbols → objects
Predicate symbols → relations
Function symbols → functional relations
·
Kemungkinan
Model & Interpretasi
Entailment , validity , satisfiability , dll. Didefinisikan
untuk semua kemungkinan interpretasi dari semua kemungkinan model!
Kalau mau dijabarkan semua kemungkinannya: For each number
of domain elements n from 1 to ∞ For each k -ary predicate Pk in the vocabulary
For each possible k -ary relation on n objects For each constant symbol C in
the vocabulary For each choice of referent for C from n objects . .
Menentukan entailment berdasarkan truth-table? mustahil!
Biasanya ada satu interpretasi yang “dimaksudkan” → intended
interpretation.
·
Quantifier
Selain penggunaan predikat, First Order Logic juga
menawarkan quantifier untuk membuat kalimat logika yang lebih sederhana. Ada 2
jenis quantifier, yaitu universal dan existential. Quatifier ini berlaku
terhadap parameter yang muncul di sebuah kalimat masih dalam bentuk variabel.
Universal quantifier terhadap sebuah variabel x (disimbolkan dengan ∀x) berarti bahwa kalimat tersebut berlaku untuk setiap obyek
x, sedangkan existential quantifier (disimbolkan dengan ∃x) berarti berlaku untuk sebagian obyek saja.
Contoh: Menggunakan definisi untuk p(x), r(x), dan q(x,y),
berikut adalah kalimat-kalimat logika dengan menggunakan quantifier dan
artinya:
·
∀x(p(x) Λ r(rabu) → q(x,merah-putih)) : untuk setiap x, jika
x adalah seorang siswa kelas II SD dan pada hari Rabu maka x akan mengenakan
seragam merah-putih.
·
∃x(p(x) → ¬q(x,merah-putih)) : ada x, jika x adalah seorang
siswa kelas II SD maka x tidak mengenakan seragam merah putih.
·
Universal
Quantifier
Dalam logika predikat , quantifieri universal merupakan
jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “diberi”
atau “untuk semua”. Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi
oleh setiapanggota dari domain wacana. Dalam istilah lain, itu adalah predikasi
dari properti atau hubungan dengan setiap anggota domain. Ini menegaskanbahwa
predikat dalam lingkup dari quantifier universal benar dari setiap nilai dari
variabel predikat .
Hal ini biasanya dilambangkan dengan berbalik A (∀) operator logika simbol, yang bila digunakan bersama-sama
dengan variabel predikat, disebut quantifier universal (“∀x”, “∀ (x)”, atau kadang-kadang dengan “(x) “saja).
Kuantifikasi Universal berbeda dari kuantifikasi eksistensial (“ada ada”), yang
menegaskan bahwa properti atau relasi hanya berlaku untuk setidaknya satu
anggota dari domain.
Contoh 1 :
(∀x) (x + x = 2x)
“untuk setiap x (dimana x adalah suatu bilangan), kalimat x
+ x = 2x adalah benar.”
Contoh 2 :
(∀x) (p) (Jika x adalah seekor kelinci -> x adalah
binatang).
Kebalikan kalimat “bukan kelinci adalah binatang” ditulis :
(∀x) (p) (Jika x adalah seekor kelinci -> ~x adalah
binatang)
dan dibaca :
– “setiap kelinci adalah bukan binatang”
“semua kelinci adalah bukan binantang”
·
Existential
Quantifier
Dalam logika predikat , suatu quantifier eksistensial adalah
jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “ada ada,”
“ada setidaknya satu,” atau “untuk beberapa.” Ini mengungkapkan bahwa fungsi
proposisi dapat dipenuhi oleh setidaknya satu anggota dari domain wacana .
Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan
setidaknya satu anggota dari domain. Ini menegaskan bahwa predikat dalamlingkup
dari quantifier eksistensial adalah benar dari setidaknya satu nilai
darivariabel predikat .
Hal ini biasanya dilambangkan dengan E berubah (∃) operator logika simbol, yang bila digunakan bersama-sama
dengan variabel predikat, disebut quantifier eksistensial (“∃x” atau “∃(x)”) Kuantifikasi eksistensial.
Contoh 1 :
(∃x) (x . x = 1)
Dibaca : “terdapat x yang bila dikalikan dengan dirinya
sendiri hasilnya sama dengan 1.”
Contoh 2 :
(∃x) (panda(x) ∧ nama(Clyde))
Dibaca : “beberapa panda bernama Clyde”.
Contoh 3 :
(∀x) (jerapah(x) -> berkaki empat(x))
Dibaca : “semua jerapah berkaki empat”.
Universal quantifier dapat diekspresikan sebagai konjungsi.
(∃x) (jerapahh(x) ∧ berkaki
tiga(x))
Dibaca : “ada jerapah yang berkaki tiga”
Existensial quantifier dapat diekspresikan sebagai disjungsi
dari
urutan ai. P(a1) ∨ P(a2) ∨ P(a3) …∨ P(aN)
1.3. PENGGUNAAN LOGIKA ORDE PERTAMA
1.
Assertions and queries in
first-order logic.
2.
The kinship domain.
3.
Numbers, sets, and lists.
1.4. REKAYASA PENGETAHUAN PADA LOGIKA ORDE PERTAMA
1.
Identify the task.
2.
Assemble the relevant knowledge.
3.
Decide on a vocabulary of
predicates, functions, and constants.
4.
Encode general knowledge about the
domain
5.
Encode a description of the specific
problem instance.
6.
Pose queries to the inference
procedure and get answers.
7.
Debug the knowledge base.
1.5. LOGIKA PROPOSISI VS INFERENSI LOGIKA ORDE PERTAMA
Contoh Permasalahan
Pembuktian Logika Proposisi
Setiap manusia pasti mati. Karena Sayuti adalah manusia,
maka dia pastimati.
Secara intuisi kalimattersebut bernilai Benar. Berdasarkan
logika proposisi kalimat tersebut dapat
disimbolkan sebagai:
p : Setiap manusia pasti mati
q : Sayuti adalah manusia
r : Sayuti pasti mati
Berdasarkan kerangka berfikir Logika Proposisi bukanlah
konsekuensi Logis dari pdan q. Pernyataan
‘Setiap manusia pasti mati’ mengandung pernyataan Himpunan,
yaitu Himpunan ‘manusia’, dimana
individu yang merupakan bagian dari himpunan manusia
jumlahnya tidak terhingga. Sedangkan
pernyataan ‘Sayuti adalah manusia’ secara implisit
menyatakan anggota dari himpunan ‘manusia’/
universal of discourse.
Struktur sepertidiatas tidak dikenali oleh Logika Proposisi,
karena apabila ingin membuktikan
kebenaran dari pernyataan ‘Setiap manusiapasti masti’ maka
harus dicari nilai kebenaran dari seluruh
elemen himpunan manusia yang jumlahnya tak terhingga. Ini
tidak mungkin dilakukan.
Untuk mengatasi permasalahan diatas diperlukan kerangka
berfikir lain selain Logika Proposisi yaitu
Logika First-Order (Kalkulus Predikat). Maka dapat
didefinisikan bahwa Logika First-Order adalah
perluasan dari konsep Logika Proposisi untuk mengatasi permasalahan
yang tidak dapat dipecahkan
melalui kerangka berfikir Logika Proposisi dengan penambahan
3 komponen logika yaitu: Term
(suku), Predicate dan Quantifier.
Pembuktian pada Logika First-Order
Pembuktian Logika First-Order hampir sama dengan pembuktian
pada Logika Proposisi. Hanya saja
pada Logika First-Order pembuktian menggunakan Aturan
Inferensi lebih mungkin untuk dilakukan.
Contoh:
Buktikan bahwa “Setiap manusia pasti mati. Sayuti adalah
manusia, Karenanya Sayuti pasti mati.”
Jawab:
Misal dideklarasikan predikat berikut:
MAN(x) adalah manusia
MORTAL(x) pasti mati
Maka pernyataan pada soal menjadi:
P1
:(x) (MAN(x) MORTAL(x))
P2
:MAN(Sayuti)
Untuk membuktikan bahwa kesimpulan “Sayuti pasti mati”harus
dibuktian bahwa MORTAL(Sayuti)
adalah konsekuensi logis dari P1dan P2. Maka;
Dilakukan pembuktian langsung:
P1P2 : (x)
(MAN(x) MORTAL(x)) MAN(Sayuti)
Karena (MAN(x) MORTAL(x)) bernilai Benar untuk semua x
maka;
(MAN(Sayuti) MORTAL(Sayuti)) juga Benar
(x) (MAN(x)MORTAL(x))
MAN(Sayuti)
(MAN(Sayuti)MORTAL(Sayuti))
MORTAL(Sayuti)
Premis P1
Premis P2
Langkah 1 dan 2
P1: x Sayuti
1.6. UNIFIKASI DAN LIFTING
Unifikasi adalah usaha untuk mencoba membuat dua ekspresi
menjadi identik (mempersatukan keduanya) dengan mencari substitusi-substitusi
tertentu untuk mengikuti peubah-peubah dalam ekspresi mereka tersebut.
Unifikasi merupakan suatu prosedur sistematik untuk memperoleh peubah-peubah
instan dalam wffs. Ketika nilai kebenaran predikat adalah sebuah fungsi dari
nilai-nilai yang diasumsikan dengan argumen mereka, keinstanan terkontrol dari
nilai-nilai selanjutnya yang menyediakan cara memvalidasi nilai-nilai kebenaran
pernyataan yang berisi predikat. Unifikasi merupakan dasar atas kebanyakan strategi
inferensi dalam Kecerdasan Buatan. Sedangkan dasar dari unifikasi adalah
substitusi.
Suatu substitusi (substitution) adalah suatu himpunan
penetapan istilah-istilah kepada peubah, tanpa ada peubah yang ditetapkan lebih
dari satu istilah. Sebagai pengetahuan jantung dari eksekusi Prolog, adalah
mekanisme unifikasi.
Aturan-aturan unifikasi :
1.
Dua atom (konstanta atau peubah)
adalah identik.
2.
Dua daftar identik, atau ekspresi
dikonversi ke dalam satu buah daftar.
3.
Sebuah konstanta dan satu peubah
terikat dipersatukan, sehingga peubah menjadi terikat kepada konstanta.
4.
Sebuah peubah tak terikat
diperssatukan dengan sebuah peubah terikat.
5.
Sebuah peubah terikat dipersatukan
dengan sebuah konstanta jika pengikatan pada peubah terikat dengan konstanta
tidak ada konflik.
6.
Dua peubah tidak terikat disatukan.
Jika peubah yang satu lainnya menjadi terikat dalam upa-urutan langkah
unifikasi, yang lainnya juga menjadi terikat ke atom yang sama (peubah atau
konstanta).
7.
Dua peubah terikat disatukan jika
keduanya terikat (mungkin melalui pengikatan tengah) ke atom yang sama (peubah
atau konstanta).
1.7. FORWARD & BACKWARD CHAINING
·
FORWARD
CHAINING
Forward chaining merupakan metode inferensi yang melakukan
penalaran dari suatu masalah kepada solusinya. Jika klausa premis sesuai dengan
situasi (bernilai TRUE), maka proses akan menyatakan konklusi. Forward chaining
adalah data-driven karena inferensi dimulai dengan informasi yang tersedia dan
baru konklusi diperoleh. Jika suatu aplikasi menghasilkan tree yang lebar dan
tidak dalam, maka gunakan forward chaining.
Contoh :
Terdapat 10 aturan yang tersimpan dalam basis pengetahuan
yaitu :
R1 : if A and B then C
R2 : if C then D
R3 : if A and E then F
R4 : if A then G
R5 : if F and G then D
R6 : if G and E then H
R7 : if C and H then I
R8 : if I and A then J
R9 : if G then J
R10 : if J then K
Fakta awal yang diberikan hanya A dan E, ingin membuktikan
apakah K bernilai benar.
·
BACKWARD
CHAINING
Menggunakan pendekatan goal-driven, dimulai dari harapan apa
yang akan terjadi (hipotesis) dan kemudian mencari bukti yang mendukung (atau
berlawanan) dengan harapan kita. Sering hal ini memerlukan perumusan dan
pengujian hipotesis sementara. Jika suatu aplikasi menghasilkan tree yang
sempit dan cukup dalam, maka gunakan backward chaining.
1.8. RESOLUSI LOGIKA PREDIKAT
Resolusi pada logika predikat pada dasarnya sama dengan
resolusi pada logika proposisi, hanya saja ditambah
dengan unifikasi.Pada logika predikat, prosedur untuk membuktikan
pernyataan P dengan beberapa pernyataan F yang telah diketahui, dengan
menggunakan resolusi, dapat dilakukan melalui algoritma sebagai berikut :
1.
Konversikan semua proposisi F ke
bentuk klausa
2.
Negasikan P, dan konversikan hasil
negasi tersebut ke bentuk klausa.Tambahkan kehimpunan klausa yang
telah ada pada langkah
3.
Kerjakan hingga terjadi kontradiksi
atau proses tidak mengalami kemajuan :
·
Seleksi 2 klausa sebagai klausa
parent
·
Bandingkan (resolve) secara
bersama-sama. Klausa hasil resolve tersebut resolvent. Jika ada pasangan
literal T dan ¬T2 sedemikian hingga keduanya dapat dilakukan unifikasi, maka
salah satu T1 dan T2 disebut sebagai complementary literal. Jika ada lebih dari
1 complementary literal, maka hanya sepasang yang dapat meninggalkan resolvent
·
Jika resolvent berupa klausa kosong,
maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah
ada
Sumber :
