3/12/20181

First Order Logic (FOL)?• Proposional Logic bermanfaat, tetapi :– Terbatas– Menganggap “world” hanya mengandungfakta-fakta.• Pada Proposional Logic, setiap simbol tidakmempunyai hubungan dengan yang lain, contoh :– John owns a car: C– John owns a bike: B– John owns a car or a bike: C v B

3/12/20182

First Order Logic (FOL)?• Oleh karena itu, dikembangkanPredicate Logic.–Predicate Logic yang sederhana adalahFirst Order Logic (FOL).– FOL seperti natural languageFirst Order Logic (FOL)?• Ada element baru :–Predicates : objects, properties, relationships–Quantifiers : ∀(for all), ∃ (there exists)• Contoh :

∀x on(x;table) ⇒ fruit(x)quantifier variabel konstantapredikat

3/12/20183

First Order Logic (FOL)• FOL menganggap “world” mengandung:– ObjectsSesuatu yang berhubungan dengan identitas individu– PropertiesMilik/ sifat dari object yang membedakannya denganobject yang lain.– RelationsHubungan antara sesama object.– Functions Adalah relations yang hanya memiliki 1 nilai untuksetiap object. Contoh 1 FOL• Objects :Pelajar, bangunan, buku, UKM, bilangan, warna, hari, …• Relations :Kakak dari, lebih besar dari, di atas, terjadi sebelum, …• Properties : biru, oval, ganjil, besar, …• Functions :Ayah dari, babak final dari, satu lebih dari, kaki kiri dari, …

3/12/20184

Contoh 2 FOL• Objects:Wheel, door, body, engine, seat, car, passenger, driver• Relations:Inside(car, passenger), Beside(driver, passenger)• Properties: Color(car), IsOpen(door), IsOn(engine)• Functions:ColorOf(car) Contoh 1 FOLSatu tambah dua sama dengan tiga.• Objects : Satu,dua,tiga, satu tambah dua.• Relations : Sama dengan• Properties : -• Functions : Tambah.

3/12/20185

Contoh 2 FOLKotak yang bersebelahan dengan wumphus akansmell/bau.• Objects : Wumphus, kotak.• Relations : Bersebelahan• Properties : Bau• Functions : -FOL Syntax• Simbol konstanta :– Mengenai objek yang sama dengan interpretasi yang sama– Contoh : Mary, 4, Green, A, B, …• Simbol Predikat :– Mengenai hubungan yang khusus dalam model, yang memetakan individu kedalam “truth value”.– Contoh : greater(5,3), warna(rumput, hijau)• Simbol Fungsi :– Memetakan antara individu dengan individu yang berhubungan (one-one relation)– Contoh : ayah_dari(Mary) = John, warna(Langit) = Biru

3/12/20186

FOL Syntax• Variables : Sebagai pengganti nama dari suatu object.Contoh : (x, y, a, b,… ∀x)– Cat(x) ⇒ Mammal(x) if x is a cat then x is a mammal.• Logic connectives : – not (~)– and (∧)– or (∨)– implies (⇒)– equivalent (⇔)FOL Syntax• Quantifiers : Merupakan keterangan mengenai sifat object.–∀ (universal) : ∀x, for any x, …– ∃ (existential) : ∃x, there is a x, …• Equality : =–Contoh : Father(John) = Henry

3/12/20187

Syntax FOL: Kalimat atom• Sebuah kalimat atom dibentuk dari simbolpredikat. predikat(obyek_1 [,obyek_2,obyek_3,…,obyek_n]).• Contoh :– saudara_dari(richard, john)Arti : “Saudara dari Richard adalah John”– berbadan(anjing(hitam),besar)Arti : “Anjing hitam berbadan besar”.Syntax FOL: Kalimat kompleks• Menggabungkan atomic sentences dengan“connective”.• Contoh :– suka(alisa, icecream) ∧ suka(bobi, icecream)– married (bill, hillary) ⇒ married (hillary, bill)

3/12/20188

Universal Quantifiers• Arti ∀ : “untuk semua” atau “for any”• (∀x)P(x) : P memegang “semua nilai”dari x dalam domain yang berhubungandengan variabel tersebut.• Contoh : – “All ducks are birds”∀ Duck(x) ⇒ Bird(x)– Salah, jika :∀ Duck(x) ∧ Bird(x) Catatan :Biasanya menggunakanconnective “implies”(⇒)Existential Quantifiers• Arti ∃ : “satu/ sedikit”• (∃ x)P(x) : P memegang “beberapa nilai” dari x dalam domain yang berhubungan denganvariabel tersebut. • Contoh : – “There is a professor with blue eyes”∃ x Professor(x) ∧ BlueEyes(x)– Salah, jika :∃ x Professor(x) ⇒ BlueEyes(x)Catatan :Biasanya menggunakanconnective “and”(∧)

3/12/20189

Aturan Quantifiers• Menukarkan posisi universal quantifiers yang tidak merubah arti : (∀x)(∀y)P(x,y) ⇔ (∀y)(∀x)P(x,y)• Menukarkan posisi existential quantifiers yang tidak merubah arti : (∃x)(∃y)P(x,y) ⇔ (∃y)(∃x)P(x,y)Aturan Quantifiers• Menukarkan posisi universals & existential yang dapat mengubah arti–Everyone likes someone: (∀x)(∃y) likes(x,y)–Someone is liked by everyone:(∃y)(∀x) likes(x,y)

3/12/201810

Hubungan antara ∀ dan ∃• Hubungan sentences yang menggunakan ∀ & ∃ menggunakanDe Morgan’s laws :– (∀x)~P(x) ⇔ ~(∃x) P(x)–~(∀x)P(x) ⇔ (∃x) ~P(x)– (∀x) P(x) ⇔ ~ (∃x) ~P(x)– (∃x) P(x) ⇔ ~(∀x) ~P(x)Menterjemahkan Bhs.Inggris ke FOL (1)• Every gardener likes the sun.– (∀x) gardener(x) ⇒ likes(x,Sun)• You can fool some of the people all of the time.–?–?

3/12/201811

Menterjemahkan Bhs.Inggris ke FOL (1)• You can fool all of the people some of the time.–?–?• All purple mushrooms are poisonous. ? Menterjemahkan Bhs.Inggris ke FOL(2)• No purple mushroom is poisonous.–?–?• There are exactly two purple mushrooms.–?

3/12/201812

Menterjemahkan Bhs.Inggris ke FOL(3)• Harry is not tall.–?• X is above Y if X is on directly on top of Y or there is a pile of one or more other objects directly on top of one another starting with X and ending with Y.–? 6. MEMBENTUK KNOWLEDGE BASE

3/12/201813

Intro• Knowledge Engineering adalah :Suatu proses membentuk knowledge base.• Tugas Knowledge Engineer :– Menyelidiki domain tertentu– Menentukan konsep-konsep penting untuk domain tersebut.– Membuat representasi formal dari object dan relasinyadalam domain.• Knowledge Acquisition : Proses knowledge engineer melakukan wawancaradengan ahli yang sebenarnya, untuk mempelajaritentang domain &untuk menghasilkan pengetahuan.Knowledge engineering vs programmingKnowledge Engineering Programming1. Choosing a logic Choosing programming language2. Building knowledge base Writing program3. Implementing proof theory Choosing/writing compiler4. Inferring new facts Running program

3/12/201814

Baik-buruknya KB• KB yang baik : Harus jelas dan benar.• Setiap sentence yang telah dibuat, harusdilakukan pengecekan mengenai :– Kebenaran– Apakah bisa digunakan/ diaplikasikan?– Apakah perlu menambahkan predikat baru untukmenjelaskan kelas dari object?– Bagaimana relasinya antar kelas?– Apakah merupakan bagian dari kelas yang besar?– Apakah memiliki sub-class?– Sifat-sifat apalagi yang dimiliki object pada kelas ini?Knowledge Engineering• Agar dalam pengembangan knowledge base terarah dengan baik danterintegrasi, ada 5 langkah metodologiyang harus dilakukan.1. Talk About2. Naming3. General Rules4. Encode the Specific Instance 5. Pose Queries to the Inference Procedure

3/12/201815

5 Langkah MetodologiKnowledge Engineering1. Talk About :Tentukan apa yang sedang dibicarakan.5 Langkah MetodologiKnowledge Engineering2. Naming : Tentukan kata baru untuk predikat, fungsi & konstanta.(Terjemahkan konsep penting dari level domain ke namalevel logika)Contoh :– Nama predikat : bigness, size– Konstanta : small, medium, largeKata baru merupakan suatu ontologi daridomain. Ontologi : suatu bagian teori dari alami(natural) yang menjadi kenyataan/ eksistansi

3/12/201816

Knowledge Engineering3. General Rules :Enkodekan peraturan pengetahuan umumtentang domain.4. Encode the Specific Instance :Enkodekan setiap masalah spesifik kedalamdomain.5. Pose Queries to the Inference Procedure : Tempatkan kemungkinan pencarian kedalamprosedur kesimpulan dan dapatkan jawabannyaContoh : Domain Rangkaian ElekronikC1

3/12/201817

Langkah Knowledge Engineering1. Talk About :Rangkaian terminal dan sinyal2. Naming : – Konstanta : X1, X2, A1, A2 dan O1– Fungsi : Type(X1)=XORType (X1,XOR)XOR(X1)– Input : X1 In1, X1 In2, X1 Out1In(1,X1), In(2,X1), Out(1,X1)– Konektivitas: Connected(Out(1,X1), In(1,X2)) C1Langkah Knowledge Engineering3.General Rules :• Jika 2 terminal dikoneksi, akan mempunyai sinyal yang sama.∀ t1,t2 Connected(t1,t2)⇒Signal(t1)=Signal(t2)• Sinyal disetiap terminal hanya ada 2 kemungkinan keadaan “On” atau “Off”.∀t Signal(t)=On ∨ Signal(t)=OffOn ≠ Off C1

3/12/201818

Langkah Knowledge Engineering3.General Rules :• Koneksi merupakan suatu predikat yg komunikatif∀t1, t2 Connected(t1,t2) ⇔ Connected(t2,t1)• Gerbang OR, mempunyai keluaran “On” jika dan hanya jika salah satu masukan “On”∀g Type(g)=OR ⇒Signal(Out(1,g))=On ⇔∃n Signal(In(n,g))=On C1Langkah Knowledge Engineering3.General Rules :• Gerbang AND, mempunyai keluaran “Off” jikadan hanya jika salah satu masukan “Off”∀g Type(g)=AND ⇒ Signal(Out(1,g))=Off ⇔ ∃n Signal(In(n,g))=Off• Gerbang XOR, mempunyai keluaran “On” jikadan hanya jika masukan-masukannya berbeda.∀g Type(g)=XOR⇒Signal(Out(1,g))=On ⇔Signal(In(1,g))≠Signal(In(2,g)) C1

3/12/201819

Langkah Knowledge Engineering4. Encode the Specific Instance :Kategori Gates :– Type(X1)=XOR– Type(X2)=XOR– Type(A1)=AND– Type(A2)=AND– Type(O1)=OR Koneksi Rangkaian :Connected (Out(1,X1), In(1,X2))Connected (Out(1,X1), In(2,A2))Connected (Out(1,A2), In(1,O1))Connected (In(1,A2), In(3,C1))Connected (In(2,X1), In(2,C1))Connected (In(2,C1), In(2,A1))Connected (In(1,C1), In(1,X1))Connected (In(1,C1), In(1,A1))Connected (In(3,C1), In(2,X2))Connected (Out(1,A1), In(2,O1))Connected (Out(1,X2), Out(1,C1))Connected (Out(1,O1), Out(2,C1))Langkah Knowledge Engineering5. Pose Queries to the Inference Procedure : Kombinasi masukan bagaimana yang menyebabkankeluaran pertama C1=OFF dan keluaran keduaC1=ON ?– ∃ i1,i2,i3 Signal(In(1,C1))=i1 ∧Signal(In(2,C1))=i2 ∧ Signal(In(3,C1))=i3 ∧Signal(Out(1,C1))=Off ∧ Signal(Out(2,C1))=OnJawaban :– (i1=On ∧ i2=On ∧ i3=Off) ∨– (i1=On ∧ i2=Off ∧ i3=On) ∨– (i1=Off ∧ i2=On ∧ i3=On)

3/12/201820

Forward Chaining & Backward Chaining• Dalam membentuk knowledge base dapat dibentuk melalui aturangeneralisasi modus ponen(kesimpulan yang beralasan), dapatdigunakan melalui 2 cara :–Forward Chaining–Backward Chaining Forward Chaining & Backward Chaining• Forward Chaining :–Dimulai dari sentence dalam knowledge base yang menghasilkan konklusi, danselanjutnya konklusi menghasilkankesimpulan-kesimpulan berikutnya.–Data-driven–Harus melakukan banyak pekerjaanyang tidak berhubungan dengan goal

3/12/201821

Forward Chaining & Backward Chaining• Backward Chaining :–Dimulai dari suatu bukti/ kenyataankejadian, kemudian dicari sentence implikasinya, untuk mendapatkan suatukonklusi dan mencapai premis yang pasti.–Goal-driven–Komplesitas lebih kecil.Forward Chaining• Digunakan tiap fakta baru ditambahkan kedalamdatabase dan fakta tersebut → konklusi baru.• Fakta baru tersebut merupakan mata rantaikonklusi berikutnya.

3/12/201822

Forward Chaining• Contoh :Pada saat berkendaraan mobil, temperatur mobilnaik, apa yg akan terjadi? apa yg hrs dilakukan?RULE 1IF temperatur mobil tinggi THENmobil akan tidak berfungsiRULE 2IF mobil tidak berfungsi THENmemerlukan biaya yang besar ANDterlambat tiba ditujuanBackward Chaining• Digunakan untuk suatu tujuan (goal) pembuktian• Contoh :Mobil tidak dapat nyala/ start, apa penyebabnya?Apa batere lemah?Apakah mobil perlu di tune-up?Apakah bagian starter rusak ?RULE 1IF mobil tidak sesuai (tuned) THENbatere lemah THENmobil tidak dapat di starterRULE 2IF mobil tidak dapat di starter THENmobil tidak nyala