LOGIKA ORDE PERTAMA (FIRST-ORDER LOGIC)

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

Contoh kasus :

Misalkan terdapat pernyataan-pernyataan sebagai berikut :

1. Fajar adalah seorang mahasiswa
2. Fajar masuk Jurusan Elektro
3. Setiap mahasiswa elektro pasti mahasiswa Teknik
4. Kalkulus adalah matakuliah yang sulit
5. Setiap mahasiswa teknik pasti akan suka kalkulus atau akan membencinya
6. Setiap mahasiswa pasti akan suka terhadap suatu matakuliah
7. Mahasiswa yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti tidak   suka terhadap matakuliah tersebut
8. Fajar tidak pernah hadir kuliah matakuliah kalkulus

Maka harus terlebih dahulu diubah ke dalam bentuk klausa sebagai berikut :

1. Mahasiswa (Fajar)
2. Elektro (Fajar)
3. Elektro (x1) v Teknik (v1)
4. Sulit (Kalkulus)
5. Teknik (x2) v suka (x2, Kalkulus) v benci (x2, Kalkulus)
6. Suka (x3, f1 (x3))
7. Mahasiswa (x4) v ¬ sulit (y1) v hadir (x4, y1) v ¬ suka (x4, y1)
8. Hadir (Fajar, Kalkulus)

ppt:
https://drive.google.com/open?id=14nKEFh1Ck8g0w1ebjaYB31S9Jl8Ukk9V

sumber:
https://niftakul.wordpress.com/2017/10/19/logika-orde-pertama-first-order-logic/

Bos, J. 2006], LogAnswer [Furbach, U., et. al. 2009].

Russel, Stuart, Artificial Intelligence : a modern Approach, pearson, 2011.

Ebook Artifical Intelligence A Modern Approach(3rd Edition).

Pengetahuan dan Penalaran

1. KNOWLADGE BASE AGENT

Agen Berbasis Pengetahuan, Knowledge Base (KB) menyatakan apa yang “diketahui” oleh si agent Pendekatan deklaratif membangun agent: “beritahu” informasi yang relevan, simpan dalam KB. Agen dapat ditanya (atau bertanya diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB. Maka sebuah agen berbasis pengetahuan harus bisa mereprentasikan world, state, action, dst. Menerima informasi baru (dan meng-update representasinya). Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property).  Menyimpulkan action apa yang perlu diambil. 

Agen Berbasis Pengetahuan atau Knowledge Base (KB) merupakan Himpunan representasi fakta yang diketahui tentang lingkungannya. Tiap fakta disebut sebagai sentence. Fakta tersebut dinyatakan dalam bahasa formal sehingga bisa diolah, menambahkan sentence baru ke KB. Inference Engine merupakan menentukan fakta baru yang dapat diturunkan dari pengetahuan yang sudah ada dalam KB. 

Agen Berbasis Pengetahuan dalam representasi, agent dapat dipandang dari knowledge level. Apa saja informasi yang diketahui? Misal sebuah robot “mengetahui” bahwa gedung B di antara gedung A dan gedung C. Agent dapat dipandang dari implementation level Bagaimana representasi informasi yang diketahuinya? Logical sentence di_antara(gdB, gdA, gdC). Natural language “Gedung B ada di antara gedung A dan gedung C”. 

Agen Berbasis Pengetahuan, pilihan representasi berpengaruh terhadap apa yang bisa dilakukan inference engine. Pada pendekatan deklaratif programmer memberitahu agent informasi tentang environment. Kalau informasi kurang, agen bisa melengkapinya sendiri. Jika dibandingkan dengan pendekatan prosedural programmer secara eksplisit memrogram agen untuk bertindak. Sehingga bagaimana jika program tidak benar, maka akan besar kemungkinan menyebabkan kesalahan. 

Agen Berbasis Pengetahuan, permasalahannya adalah bagaimana representasi yang tepat, sehingga ada dua hal yang harus diperhatikan expressive bisa menyatakan fakta tentang environment, Tractable bisa mengolah/ memproses inference engine (dengan cepat). Knowledge merupakan power atau kekuatan dari pemrograman secara deklaratif. Representasi dan penalaran membentuk suatu Intelligence.

2.DASAR LOGIKA PROPOSISI

–         Proposisi adalah ekspresi yangmengandung variabel (yaitu variableproposisional) berupa pernyataan danoperator (yaitu operator logika) sebagaikonektor.

–         Pernyataan (Statement) adalah kalimatdeklaratif yang memiliki nilai kebenaran (True dan False)

–         Syntactics Rule (AturanSintaktik) adalah aturan yang diperlukan untuk mengkombinasikan antarapropositions dan propositional connectives untuk menghasilkan sentences(kalimat logika). Dapat dibuat alurnya sebagai berikut Propositions + Propositional Connectives à Sentences Propositional connective yang digunakan: Not, And, Or, If-Then,If-Then-Else, dan If-And-Only-If

–         Interpretasi adalah pemberiannilai kebenaran (true atau false) pada setiap symbol proposisi dari suatukalimat logika.

–         Semantic Rule (Aturan Semantik)adalah suatu aturan yang digunakan untuk menentukan “truth value” dari suatusentence.

Logika proposisi memiliki bentuk berupa kalimat deklaratif (atau pernyataan). Proposisi didefinisikan sebagai kalimat deklaratif yang memiliki hanya satu nilai kebenaran yaitu benar saja, salah saja, tetapi tidak keduanya, benar sekaligus salah. Pada umumnya bentuk proposisi adalah kalimat berita yang bisa ditentukan nilai kebenarannya (benar/salah).

Metode forward Chaining

Kadang disebut:data-driven karena inference engine menggunakan informasi yang ditentukan oleh user untuk memindahkan ke seluruh jaringan dari logika ‘AND’ dan ‘OR’ sampai sebuah terminal ditentukan sebagai objek. Bila inference engine tidak dapat menentukan objek maka akan meminta informasi lain. Aturan (Rule) di mana menentukan objek, membentuk path (lintasan) yang mengarah ke objek. Oleh karena itu, hanya satu cara untuk mencapai satu objek adalah memenuhi semua aturan.

Metode backward Chaining

Merupakan kebalikan dari forward chaining dimana mulai dengan sebuah hipotesa (sebuah objek) dan meminta informasi untuk meyakinkan atau mengabaikan. Backward chaining inference engine sering disebut: ‘Object-Driven/Goal-Driven‘.

Contoh forward dan backward chaining dikutip dari Idhawati Hestiningsih

R1 : IF suku bunga turun THEN harga obligasi naik
R2 : IF suku bunga naik THEN harga obligasi turun
R3 : IF suku bunga tidak berubah THEN harga obligasi tidak berubah
R4 : IF dolar naik THEN suku bunga turun
R5 : IF dolar turun THEN suku bunga naik
R6 : IF harga obligasi turun THEN beli obligasi

Apabila diketahui bahwa dolar turun, maka untuk memutuskan apakah akan membeli obligasi atau tidak dapat ditunjukkan sebagai berikut :

Forward Chaining

Dari fakta dolar turun, berdasarkan Rule 5, diperoleh konklusi suku bunga naik. Dari Rule 2
suku bunga naik menyebabkan harga obligasi turun. Dengan Rule 6, jika harga obligasi turun,
maka kesimpulan yang diambil adalah membeli obligasi.
Backward Chaining

Dari solusi yaitu membeli obligasi, dengan menggunakan Rule 6 diperoleh anteseden harga
obligasi turun. Dari Rule 2 dibuktikan harga obligasi turun bernilai benar jika suku bunga naik
bernilai benar . Dari Rule 5 suku bunga naik bernilai memang bernilai benar karena diketahui
fakta dolar turun.

Validitas dan Inkonsistensi

Pada pembahasan kaliini kita ingin mengetahui kapan suatu formula dikatakan valid pada logikaproposional? Pada penjelasan diatas kita telah dibiasakan dengan formula logikayang berasal dari transformasi kalimat deklaratif. Komposisi atau Kombinasibeberapa kalimat deklaratif yang valid akan menghasilkan formula yang validjuga.

Suatu formuladikatakan Valid jika dan hanya jika formula tersebut Tautologi. Dan formuladisebut Invalid jika dan hanya jika tidak valid.

Suatu formula disebut Inkonsistenjika dan hanya jika formula tersebut kontradiksi. Dan formula disebut Konsistenjika dan hanya jika tidak Inkonsisten.

Pernyataan berikut iniadalah implikasi dari definisi diatas:

Formula adalah Valid jika dan hanya jika Negasinya InkonsistenFormula adalah Inkonsisten jika dan hanya jika Negasinya ValidFormula adalah Invalid jika dan hanya jika ada interpretasi yang menyebabkannya salah.Formula adalah Konsisten jika dan hanya jika ada interpretasi yang menyebabkannya benarJika formula adalah Valid, maka formula tersebut Konsisten tetapi tidak sebaliknyaJika formula adalah Inkonsisten, maka formula tersebut Invalid, tetapi tidak untuk sebaliknya.

Contoh:

Dengan menggunakan tabel kebenarn, kitadapat menyimpulkan bahwa:

1. Formula adalah inkonsisten, yang juga invalid
2. Formula adalah valid, yang juga konsisten
3. Formula adalah invalid, yang juga konsiste

sumber:

https://ichsanapriyandiblog.wordpress.com/2017/10/12/pengetahuan-berbasis-agen/

http://yogipratama97.blogspot.com/2016/10/pengenalan-logical-agents.html

HEURISTIC SEARCH

Pencarian berbentuk Heuristik (Heuristic Search)

• Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness).
• Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
• Jenis-jenis Heuristic Searching:
– Generate and Test.
– Hill Climbing.
– Best First Search.
– Means-EndAnlysis, Constraint Satisfaction, dll.


Strategi pencarian berbentuk / heuristik search strategy   


Teknik Dasar Pencarian adalah proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space). Pencarian atau pelacakan merupakan salah satu teknik untuk menyelesaikan permasalahan AI. Teknik pencarian terbagi atas dua teknik, yaitu pencarian buta (blind search) dan pencarian heuristik (heuristic search).


Penelitian yang pernah dilakukan mengenai permainan pergeseran angka dalam bentuk bintang yaitu dengan menggunakan algoritma breadth first search. Pada penelitian ini penulis menggunakan algoritma Best First Search untuk penyelesaian permainan pergeseran angka pada bentuk bintang ini. Algoritma best first search adalah salah satu algoritma pencarian heuristik yang merupakan kombinasi dari dua algoritma pencarian buta (blind search), yaitu breadth first search dan depth first.




Fungsi Heuristik


Dalam metode pencarian heuristik, digunakan suatu metode yang digunakan untukmengevaluasi keadaan-keadaan masalah individual dan menentukan seberapa jauhhal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Fungsi heuristik berbeda untuk setiap tujuan, sehingga fungsi ini sering dijadikan sebagai parameter penting dalam menyelesaikan fungsi heuristik diimplementasikan untuk mencari jarak dari dua buah verteksyang biasanya menggunakan euclidean dan manhattan distance.
Suatu fungsi heuristik dapat dikatan baik, apabila dapat memberikan biaya perkiraan yang mendekati biaya sebenarnya. semakin mendekati biaya sebenarnya, fungsi heuristik tersebut semakin baik. Dalam masalah pencarian rute terpendek dengan graph, fungsi heuristik yang dapat digunakan adalah Manhattan Distance.

1). PEMBANGKITAN dan PENGUJIAN (Generate and Test)

Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

• Algoritma :
1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).
2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang  dipilih dengan kumpulan tujuan yang diharapkan.
3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.
• Contoh : “Travelling Salesman Problem (TSP)”
*) Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya  boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota  dengan jarak antara tiap-tiap kota seperti berikut ini :

2) PENDAKIAN BUKIT (Hill Climbing)

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnyayang mungkin.

• Algoritma:
1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
b) Evaluasi keadaan baru tersebut : – Jika keadaan baru merupakan tujuan, keluar – Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. – Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.
• Contoh: TSP dengan Simple Hill Climbing Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak n!/2!(n-2)!  atau sebanyak 6 kombinasi. Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi.

3). PENCARIAN TERBAIK PERTAMA (Best-First Search)

Metode ini merupakan kombinasi dari metode depthfirst search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.

Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan : 

f’(n) = g(n) + h’(n)
• f’ = Fungsi evaluasi
• g = cost dari initial state ke current state
• h’ = prakiraan cost dari current state ke goal state
• Contoh: Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengannode A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node.

Memory-bounded A* (SMA)

adalah salah satu algoritma searching yang menjanjikan solusi yang optimal jika memori yang tersedia setidaknya sebesar jumlah node pada jalur solusi optimal. Heuristic additive digunakan sebagai biaya perkiraan agar algoritma ini dapat diimplementasikan ke dalam planning. Ada dua strategi dalam Planning, yaitu Forward Planning dan Backward Planning. Pada Forward Planning, pencarian jalur solusi akan dilakukan dari initial state menuju goal state, sementara pada Backward Planning pencarian jalur solusi akan dilakukan terbalik dari goal state menuju initial state. Planning sebagai heuristic search adalah cara yang menggabungkan heuristic search dengan planning untuk menemukan jalur solusi.

Dalam tugas akhir ini algoritma SMA dengan menggunakan heuristic additive sebagai biaya estimasi digunakan untuk menyelesaikan permasalahan planning pada studi kasus dunia balok. Pembatasan memori pada algoritma ini aka disimulasikan dalam array of node. Sistem ini akan menampilkan output berupa aksi-aksi yang dilakukan oleh sistem untuk mencapai goal state, menampilkan jumlah aksi yang dilakukan, menghitung jumlah iterasi yang diperlukan, serta menampilkan waktu proses yang dibutuhkan sistem untuk menyelesaikan problem.

Genetic Algorithm

Genetic Algorithm(atau GA) adalah teknik pencarian dalam bidang komputasi untuk menemukan solusi benar atau pendekatan untuk masalah optimasi dan pencarian. Teknik dalam GA didasarkan pada biologi evolusioner seperti pewarisan, mutasi, seleksi dan crossover.

Dalam GA biasanya ada 2 hal yang harus didefinisikan:

Representasi genetis dari domain solusi

Fungsi fitness untuk mengevaluasi solusi domain.

Hal-hal yang harus dilakukan untuk menggunakan algoritma genetika

1. Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat
2. Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan
3. Menentukan proses pembangkitan solusi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random walk.
4. Menentukan proses seleksi yang akan digunakan
5. Menentukan proses perkawinan silang (cross over) dan mutasi gen yang akan digunakan

Agen pencarian online dan lingkungan yang tidak diketahui.

Pencarian buta (uninformed/blind search) : tidak ada informasi awal yang digunakan dalam proses pencarian

Pencarian melebar pertama (Breadth – First Search) 

Pencarian mendalam pertama (Depth – First Search)



PPT:
https://drive.google.com/open?id=13kXVR3_hRoRL4d324Sfl82N0KVB06zUI

sumber:

https://shabri-prayogi.blogspot.com/2013/08/teknik-pencarian-heuristik-heuristic.html