Pengetahuan dan Penalaran : Logika Orde Pertama (First-Order Logic)

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