Kamis, 19 Oktober 2017
A. FIRST ORDE LOGIC
First-order logic itu salah satu jenis sistem formal, yang digunakan untuk membuktikan kebenaran dari sebuah pernyataan.
Dalam first-order logic, setiap pernyataan dianggap memiliki
predikat. Predikat itu dapat menghubungkan pernyataan yang satu dengan
yang lain.
Kalimat-kalimat dalam first-order-logic dibuat dengan format P( X,
Y). P adalah predikat dan X adalah subjek. Y adalah objek, yang
merupakan variabel yang opsional.
Contoh kalimatnya adalah sebagai berikut:
Kalimat asli: James makan apel.
Kalimat FOL: makan(James, apel)
Kalimat FOL dapat juga diberikan kuantor dan tanda-tanda logika lain, seperti berikut:
Kalimat asli: James suka daging dan Daisy suka sayur.
Kalimat FOL: suka(James, daging) ^ suka(Daisy, sayur)
B.SYNTAX & SEMANTIC FIRST ORDER LOGIC
Constants: KingJohn, 2, UI,Depok,...
Predicates: Brother, >,Loves,Membenci,Mengajar,...
Functions: Sqrt, LeftLegOf,Ayah,...
Variables: x, y, a, b,...
Connectives: ∧ ∨ ¬ ⇒ ⇔
Equality: = Quantifiers: ∀∃
∀ : Semua atau Seluruh
∃ : Ada atau Sebagian atau Beberapa
→ : Implikasi ( Jika .. maka .. )
↔ : Biimplikasi ( Jika .. dan .. hanya .. jika .. )
¬ : Negasi (Tidak atau bukan)
V : Disjungsi (Atau)
∧ : Konjungsi (Dan)
C.SEMANTIK
Sama halnya dg. PL, sebuah kalimat FOL 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 tsb. 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
Menentukan entailment berdasarkan truth-table mustahil! Biasanya ada satu interpretasi yang “dimaksudkan”→ intended interpretation. - Kalimat Atomik
Atomik adalah suatu pernyataan yang tidak dapat dipecah-pecah lagi.- Cristiano Ronaldo pemain bola.
- kalimat kompleks merupakan kalimat yang mempunyai lebih dari satu verba utama atau predikat karena mempunyai dua aksi, peristiwa, atau kejadian.
kalimat kompleks mempunyai ciri-ciri sebagai berikut :- Kalimat kompleks mempunyai dua buah beristiwa atau lebih.
- Kedua struktur pada kalimat kompleks dipisahkan dengan tanda koma atau konjungsi (kata penghubung).
- Kalimat kompleks mempunyai dua buah subjek dan predikat.
Shafira menyanyi di taman, burung pun bersiul dengan sangat merdu
EQUALITY
Kalimat term1 = term2 bernilai true di bawah sebuah interpretasi jhj term1 and term2
me-refer ke object yang sama.
Contoh:
Ayah(Anto) = Abdul adalah satisfiable
Anto = Abdul juga satisfiable!
Anto = Anto adalah valid.
Bisa digunakan dengan negasi untuk membedakan dua term: ∃x,y Mencintai(Anto,x)∧Mencintai(Anto,y) ∧¬(x = y) (Anto mendua!)
Definisi Sibling: ∀x,y Sibling(x,y) ⇔ (¬(x =y)∧∃m,f ¬(m=f)∧ Parent(m,x)∧Parent(f,x)∧Parent(m,y)∧Parent(f,y))
ASSERTION
Kalimat FOL yang ditambahkan ke KB disebut assertion.
Contohnya:
TELL(KB,King(John)) TELL(KB,∀x King(x) ⇒Person(x))
QUERY
Lalu, kita bisa memberikan query, atau bertanya, kepada KB (ASK).
Contohnya:
ASK(KB,King(John)) jawabannya adalah true.
ASK(KB,Person(John)) jawabannya adalah true.
ASK(KB,∃x Person(x)) jawabannya adalah{x/John}
D.Inferensi Logika Orde pertama
Inferensi
pada logika proposisi dapat dilakukan dengan menggunakan resolusi. RESOLUSI adalah
suatu aturan untuk melakukan inferensi yg dapat berjalan secara efisien dalam
suatu bentuk khusus yg disebut Conjunctive Normal Form (CNF).
• CNF ini
memiliki ciri-ciri sebagai berikut :
– Setiap
kalimat merupakan disjungsi literal
– Semua
kalimat terkonjungsi secara implisit
• Dua
atau lebih proposisi dapat digabungkan dengan menggunakan operator logika :
a. Negasi : Ø (NOT)
b. Konjungsi : Ù (AND)
c. Disjungsi : Ú (OR)
d. Implikasi : ® (IF-THEN)
e. Ekuivalen : Û
• Operator
NOT :
digunakan untuk memberikan nilai negasi (lawan) dari pernyataan yang telah ada.
• Langkah-langkah
mengubah kalimat ke dalam bentuk CNF, sebagai berikut :
>
hilangkan implikasi dan ekuivalensi
mis. X ® Y menjadi ØX Ú Y (hukum
implikasi)
X Û Y menjadi (X=>Y) Ù (Y=>X) (hukum
bi-implikasi)
(ØX Ú Y)Ù(ØY Ú X) (hukum implikasi)
>
kurangi lingkup semua negasi menjadi satu negasi saja
mis. Ø(Ø X) menjadi X (hukum negasi ganda)
Ø(X Ú Y) menjadi (ØX Ù ØY) (hukum de’Morgan)
Ø(X Ù Y) menjadi (ØX Ú ØY) (hukum de’Morgan)
> gunakan aturan
assosiatif dan distributif untuk mengkonversi menjadi conjunction of
disjunction
mis. Assosiatif : (A Ú B) Ú C = A Ú (B Ú C)
Distributif : (A Ù B) Ú C = (A Ú C) Ù (B Ú C)
E. Unifikasi
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).
F. 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. Proses penalaran
forward chaining terlihat pada gambar dibawah :
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.
Contoh
:
Seperti pada contoh forward chining, terdapat 10 aturan
yang sama pada basis pengetahuan dan fakta awal yang diberikan hanya A dan E.
ingin membuktikan apakah K bernilai benar. Proses penalaran backward chaining
terlihat pada gambar berikut :
H. RESOULUSIResolusi merupakan suatu teknik pembuktian yang lebih efisien, sebab fakta-fakta yang akan dioperasikan terlebih dahulu dibawa ke bentuk standar yang sering disebut dengan nama klausa. Pembuktian suatu pernyataan menggunakan resolusi ini dilakukan dengan cara menegasikan pernyataan tersebut, kemudian dicari kontradiksinya dari pernyataan-pernyataan yang sudah ada.
Resolusi adalah suatu aturan untuk melakukan inferensi yang dapat berjalan secara efisien dalam suatu bentuk khusus conjunctive normal form (CNF). Pada logika proposisi, prosedur untuk membuktikan proposisi P dengan beberapa aksioma F yang telah diketahui, dengan menggunakan resolusi.
Algoritma resolusi :
- Konversikan semua proposisi F ke bentuk CNF.
- Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.
- Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :
- Seleksi 2 klausa sebagai klausa parent.
- Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.
- Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.
https://www.academia.edu/960824/Analisis_Semantik_dengan_Representasi_First_Order_Logic_dalam_Sistem_Tanya_Jawab
http://randysetiawan.blog.binusian.org/2014/03/30/ai-first-order-logic/
troublemackr.blog.binusian.org/2014/03/30/first-order-logic/
http://sarahamanda12.blogspot.co.id/2017/01/inferensi-dalam-logika-order-pertama.html
http://gofagofaa.blogspot.co.id/2016/12/inferensi-dalam-logika-order-pertama.html
