Dosen : ESSY MALAYS SARI SAKTI
First-Order
Logic (Predicat Logic / Predicat Calculus)
• Objects: sesuatu dengan identitas individual (people, houses, colors, …)
• Properties: sifat yang membedakannya dari object yang
lain (red, circle, …)
• Relations: hubungan antar object (brother of, bigger
than, part of, ...)
• Functions: relation yang mempunyai satu nilai (father
of, best friend, …)
Contoh: One plus two
equals three.
Gambar 4.5 The Syntax of First-Order Logic (with
equality) in BNF (BackusNaur
Form)
Inferensi
Dalam Kalkulus Predikat
1. Inference Rules Involving Quantifiers
SUBST(θ, a): untuk
menotasikan hasil dari pengaplikasian operasi subsitusi è
terhadap sentence a.
SUBST({x/Sam,
y/Pam}, Likes(x,y)) = Likes(Sam,
Pam).
2. Universal Elimination:
untuk setiap sentence
a,
variabel v, dan ground term (term
yang tidak berisi
variabel) g :
Dari "x Likes(x, IceCream) dapat digunakan substitusi {x/Ben} dan melakukan
inferensi bahwa Likes(Ben,
IceCream)
3. Existential Elimination: untuk
setiap sentence a, variabel v, dan simbol
konstanta k
yang tidak tampak
dimanapun di dalam basis pengetahuan:
Dari $x Kill(x,
Victim), kita dapat menyimpulkan Kill{Murderer,
Victim}, selama
Murderer tidak
tidak tampak dimanapun di dalam basis pengetahuan.
4. Existential Introduction: untuk
setiap sentence a, variabel v yang tidak terjadi pada
a, dan
ground term g yang terjadi pada a:
Dari Likes(Jerry,
IceCream) kita dapat menyimpulkan $x Likes(x,
IceCream).
Contoh bagaimana
menggunakan aturan inferensi dalam pembuktian.
The
law says that it is a crime for an American to sell weapons to hostile nations.
The
country Nono, an enemy of America, has some missiles, and all of its missiles
were
sold to it by Colonel West, who is American.
Buktikan bahwa West
adalah seorang penjahat atau criminal. Pertama representasikan
fakta dalam kalkulus
predikat, kemudian tunjukan bukti sebagai urutan aplikasi inference
rules.
Proses pembuktian dengan
pengaplikasian aturan inferensi kalkulus predikat
Proses pembuktian di
atas dapat dilakukan menggunakan teknik searching dimana:
Initial
State : Knowledge Base (sentences 1-9)
Operators
: Applicable inference rules
Goal test
: Knowledge Base yang berisi Criminal(West)
Tetapi diperlukan
program yang sangat pintar untuk menemukan bukti tanpa menelusuri
jalur yang salah.
4.2.2 Generalized Modus Ponens
Generalisasi Modus
Ponens memerlukan:
• And-Introduction
• Universal Elimination
• Modus Ponens
Contoh:
Missile(M1)
Owns(Nono,M1)
" x Missile(x)^Owns(Nono, x) =>Selles(west, Nono, x)
dan meng-infer dalam
satu langkah suatu sentence baru, yaitu:
Sells(West,Nono,M1)
dari tiga sentence di
atas, anggaplah selain Nono, setiap negara mempunyai M1:
"y Owns(y,M1)
Untuk atomic sentences pi, pi’, dan
q, dimana terdapat substitution θ sedemikian
hingga
SUBST(θ,pi’) =
SUBST(θ,pi), untuk semua i :
Terdapat n+1
premise untuk aturan ini: n atomic sentences pi’ dan
satu implikasi. Terdapat satu conclusion (kesimpulan):
hasil pengaplikasian substitusi terhadap consequent
q. Sebagai contoh dengan West dan missile:
Unification
(Unifikasi)
Secara formal unification
dituliskan:
UNIFY(p,q)
= θ dimana
SUBST(θ,p) = SUBST(θ,q)
θ disebut unifer
dari dua sentences tersebut. Kita akan mengilustrasikan unification dalam konteks dari suatu contoh. Misalkan
kita punya aturan
Knows(John,x)
=> Hates(John,x) : yang berarti (“John hates everyone he
knows”)
Misalkan knowledge base
kita berisi sentences sebagai berikut :
Knows(John,Jane)
Knows(y,Leonid)
Knows(y,mother(y))
Knows(x,Elizabeth)
Pelaksanaan unifikasi premise
atau antecedent dari aturan terhadap setiap sentence dalam
knowledge base akan
memberikan :
UNIFY(Knows(John,x),
Knows(John,Jane)) = {x/Jane}
UNIFY(Knows(John,x),
Knows(y,Leonid)) = {x/Lenoid,y/John}
UNIFY(Knows(John,x),
Knows(y,mother(y))) = { y/John,x/Mother(John)}
UNIFY(Knows(John,x),
Knows(x,Elizabeth)) = fail
Unifikasi terakhir fail
(gagal) karena x tidak dapat bernilai John dan bernilai Elizabeth
pada waktu yang sama.
Tetapi secara intuitif, dari fakta-fakta bahwa John membenci
setiap orang yang dia
kenal dan setiap orang mengenal Elizabeth, kita akan dapat menginferensi
bahwa John membenci Elizabeth. Tidak
masalah jika sentence yang terdapat dalam knowledge
base tersebut adalah Knows(x,Elizabeth) atau Knows(y,Elizabeth).
UNIFY(Knows(John,x1), Knows(x2,Elizabeth))
= {x1/Elizabeth, x/John}
Tetapi jika terdapat
suatu substitusi seperti di atas, maka terdapat tak berhingga substitusi
yang lain, seperti:
UNIFY(Knows(John,x),
Knows(y,z)) = {y/John, x/z}
or {y/John, x/z,
w/Freda}
or {y/John, x/John,
z/John} …
Kita tegaskan bahwa
UNIFY mengembalikan Most General Unifer (MGU), yang
merupakan substitusi
yang membuat komitmen paling sedikit memuat variable.
Daftar Pustaka
- Suyanto, ST.2008.Intelijensia Buatan.Bandung
