PENGETAHUAN
DAN PENALARAN: LOGIKA ORDE PERTAMA (FIRST ORDER LOGIC)
Pengenalan
logika orde pertama
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.
Dasar Logika First-Order
Logika First-Orderdigunakan untuk merepresentasikan
hal-hal yang tidak dapat direpresentasikan menggunakan LogikaProposisi.
Operator-operator yang digunakan pada Logika First-Order adalah
SIMBOL
ARTI
BENTUK
Implies / Maka / Implikasi
jika … maka …
Not / Tidak / Negasi
tidak …
And / Dan / Konjungsi
… dan …
Or / Atau / Disjungsi
… atau …
Universal Quantifier
Untuk setiap / seluruh
Existensial Quantifier
Terdapat / ada
x
Term
-
Sintak dan semantik logika orde
pertama
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
Interpretasi
Interpretasi. Sistem pakar yang dikembangkan dalam
bidang interpretasi melakukan proses pemahaman akan suatu situasi dari beberapa
informasi yang direkam.
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.
Kalimat atomik
proposisi yang hanya terdiri atas satu peryataan
dan mengacu kepada nama diri atau juka menggunakan kata ganti, maka akan
menggunakan penunjuk ini atau itu.
Kalimat kompleks
Kalimat Kompleks merupakan kalimat dengan
karakteristik memiliki lebih dari satu pola. Pada umumnya kalimat ini
disetarakan dan dianggap sebagai kalimat majemuk. Selain itu kedua pola yang
ada pada satu kalimat ini dipisahkan melalui tanda baca, kata hubung atau
terkadang tanpa menggunakan apapun. Namun meski begitu kalimat ini dapat mudah
diidentifikasi melalui bentuk strukturnya lebih dari satu predikat / peristiwa
/ keadaan.
Universal Quantifier
Definisi: Jika Asuatu ekspresi logika dan x adalah
variable, maka jika ingin menentukanbahwa A adalah bernilai benar untuk semua
nilai yang dimungkinkan untuk x,maka akan ditulis. Disini disebut
kuantoruniversal, dengan A adalah scope dari kuantor tersebut. Variabel
xdisebut terikat (bound) dengan kuantor.
Simbol UniversalQuantifier menggantikan kata
‘untuksemua’, ‘untuk seluruh’.Dan digunakan pada pembentukan formula dengan
bentuk:
(x) P(x)
(x) P(x) bernilai benar apabila predikat
P(x)bernilai benar. Formula tersebut dapat dibaca sebagai ‘Seluruh x untuk
P(x)’ atau ‘Setiap x untuk P(x)’
Existential Quantifier
Definisi: Jika Asuatu ekspresi logika dan x adalah
variable, maka jika ingin menentukanbahwa A adalah bernilai benar untuk
sekurang-kurangnya satu dari x,maka akan ditulis . Disini disebut
kuantoreksistensial, dengan A adalah scope dari kuantor tersebut. Variabel
xdisebut terikat (bound) dengan kuantor.
Simbol ExistentialQuantifier menggantikan kata
‘ada’, ‘beberapa’, ‘tidaksemua’, ‘terdapat’.Dan digunakan pada pembentukan
formula dengan bentuk:
(x) P(x)
(x) P(x) bernilai benar apabila ada x yang
menyebabkan P(x)bernilai benar. Formula tersebut dapat dibaca sebagai ‘Ada x
untuk P(x)’
Equality
Kalimat term1 =
term2 bernilai true di bawah sebuah interpretasi iff 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 ))
Penggunaan logika order pertama
Assertion
Salah satu bentukdari Assertion adalah Domain constraint dan Referential
integrity constraint. Assertion digunakan untuk mengekspresikan suatu kondisi
basis data sesuai dengan yang kita inginkan. Seperti halnya prosedur, assertion
diberikan nama tertentu sehingga bisa dibatalkan apabila ada kondisi tertentu
yang menuntut perubahan struktur basis data. Pada beberapa basis data
penggunaan kunci primer dan kunci tamu sudah cukup untuk menjaga integritas
data. Tetapi pada beberapa kasus basis data diperlukan suatu constraint ataupun
aturan yang lebih baik. Metode lain yang sering digunakan dalam pemeliharaan
integritas adalah assertion dan trigger
Syntax dari definisi assertion adalah sebagai berikut.
create assertion AssertionName check (predicate)
Ketika assertion dibuat, maka sistem akan melakukan pengecekan validitas
dari assertion yang dibuat. perubahan terhadap basis data hanya akan berlaku
ketika tidak menyalahi assertion yang telah dibuat apabila assertion yang
dibuat valid. Pengecekan validitas tersebut akan memakan biaya yang besar
terutama apabila assertion yang dibuat cukup rumit, sehingga penggunaan dan
pembuatan assertion harus dilakukan dengan hati-hati Karena itu tidak banyak
developer sistem dan DBMS yang menyediakan fasilitas seperti berikut :
Create assertion IC13 check
( ( Select min (s.status) from s ) > 4 );
Create assertion IC18 check
(not exists ( select * from P
where not ( P.Weight > 0.0 )));
Create assertion IC99 check
( not exists ( select * from P
where P.color = ‘Red’
and P.city <> ‘London’));
Create assertion IC49 check
( not exists ( select * from P, SP
where P.P# = SP.P#
and ( P.weight *
SP.Qty) > 20000));
Create assertion IC95 check
( not exists ( select * from S, SP
where S.status < 20
and S.S# = SP.S#
and SP.Qty > 500 ));
Logika proposisi vs. Inferensi Logika Orde Pertama
Logika
— Logika merupakan dasar dari semua penalaran (reasoning).
— Penalaran didasarkan pada hubungan antara
proposisi atau pernyataan (statements).
Proposisi
— PROPOSISI merupakan kalimat deklaratif yang
bernilai benar (true) atau salah (false), tetapi tidak keduanya.
— Nama lain proposisi: kalimat terbuka.
— Logika proposisi merupakan ilmu dasar untuk
mempelajari algortima dan logika, yang berperan sangat penting dalam
pemrograman.
Mengubah inferensi order pertama menjadi inferensi
proposisi
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)
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 :
- Dua atom (konstanta atau peubah) adalah identik.
- Dua daftar identik, atau ekspresi dikonversi ke dalam satu buah daftar.
- Sebuah konstanta dan satu peubah terikat dipersatukan, sehingga peubah menjadi terikat kepada konstanta.
- Sebuah peubah tak terikat dipersatukan dengan sebuah peubah terikat.
- Sebuah peubah terikat dipersatukan dengan sebuah konstanta jika pengikatan pada peubah terikat dengan konstanta tidak ada konflik.
- 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).
- Dua peubah terikat disatukan jika keduanya terikat (mungkin melalui pengikatan tengah) ke atom yang sama (peubah atau konstanta).
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 :
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.
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 :
RESOLUSI
Resolusi
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 :
(1) Konversikan semua proposisi F ke bentuk CNF.
(2) Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.
(3) Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :
a. Seleksi 2 klausa sebagai klausa parent.
b. Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.
c. Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah 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 :
(1) Konversikan semua proposisi F ke bentuk CNF.
(2) Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.
(3) Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan :
a. Seleksi 2 klausa sebagai klausa parent.
b. Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.
c. Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.
DAFTAR PUSTAKA
TUGAS PENGETAHUAN TEKNOLOGI SISTEM CERDAS
MINGGU KE-5
HERI JULIYANTO
13115135
3KA12
UNIVERSITAS GUNADARMA
Tidak ada komentar:
Posting Komentar