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.
Sintak dan semantik logika orde
pertama
Syntax pada FOL: Elemen dasar
• Constants KingJohn, 2, NUS,...
• Predicates Brother, >,...
• Functions Sqrt, LeftLegOf,...
• Variables x, y, a, b,...
• Connectives , , , ,
• Equality =
• Quantifiers ,
Kalimat Atom
Atomic sentence = predicate
(term1,...,termn) or term1 = term2
Term = function (term1,...,termn)
or constant or variable
•Misal:Brother(KingJohn,RichardTheLionheart>(Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn)))
12/10/2012
6
First-
Kalimat Komplek
• Kalimat komplek dibuat dari
kalimat atommenggunakan konektivitas
S, S1 S2, S1 S2, S1 S2, S1
S2,
Misal: Sibling(KingJohn,Richard)
Sibling(Richard,KingJohn)
>(1,2) ≤ (1,2)
>(1,2) >(1,2)
Universal Quantifier
Definisi: Jika suatu 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 Universal Quantifier
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)’
Contoh:
“Semua Gajah mempunyai
belalai”Jika G adalah gajahdan B adalah belalai maka ditulis dalam kuantor
universal menjadi , dibaca “Jika x adalah Gajah maka, x mempunyai
belalai”.Belum bisa dibuktikan secara predikat karena jumlah gajah bisa banyak
bisa sajacuma satu, maka diperluas menjadi , dibaca “Untuk semua x, jika x
seekor gajah, maka x mempunyai belalai”.
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 Existential Quantifier 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)’
Transformasi Pernyataan Kedalam
FormulaFirst-Order
Langkah-langkahmen-transformasi
penyataan kedalam formula First-Order adalah sebagai berikut:
1. Buat penafsiran mengenaipernyataan
tersebut
2. Tentukan dan deklarasikanpredikat-predikat
yang digunakan
3. Tentukan quantifier yangdiperlukan
Hal yang perludiperhatikan adalah
penafsiran atau cara pandang kita dalam menafsirkanpernyataan tersebut.
Penafsiran yang berbeda akan menghasilkan
formula yang berbeda. Kadang dalammentransformasikan sebuah pernyataan
kedalam formula first-order diperlukanquantifier lebih dari satu.
Pembuktian pada Logika
First-Order
Pembuktian LogikaFirst-Order
hampir sama dengan pembuktan pada Logika Proposisi. Hanya saja padaLogika
First-Order pembuktian menggunakan Aturan Inferensi lebih mungkin
untukdilakukan.
Contoh:
Buktikan bahwa “Setiap manusia
pasti mati. Sayuti adalahmanusia, Karenanya Sayuti pasti mati.”
Jawab:
Misal dideklarasikanpredikat
berikut:
MAN(x) :x adalah manusia
MORTAL(x) :x pasti mati
Maka pernyataan padasoal menjadi:
P1 :(x) (MAN(x) MORTAL(x))
P2 :MAN(Sayuti)
Untuk membuktikanbahwa kesimpulan
“Sayuti pasti mati”harus dibuktian bahwa MORTAL(Sayuti) adalah konsekuensi
logis dari P1dan P2. Maka;
Dilakukan pembuktianlangsung:
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
Persoalan Logika First-Order
dalam AI
Logika First-Order digunakan
dalam ilmu IntelejensiBuatan sebagai Representasi Pengetahuan. Persolan yang
ada memiliki pernyataanlebih kompleks lagi tapi dapat diselesaikan dengan
Pelacakan Terbalik(Backward)
Contoh:
Diberikanpernyataan sebagai
berikut:
1. Andi adalah seorang mahasiswa
2. Andi masuk jurusan Informatika
3. Setiap mahasiswa Informatikapasti
mahasiswa Teknik
4. Kalkulus adalah matakuliah yangsulit
5. Setiap mahasiswa teknik pastiakan suka
kalkulus atau akan membencinya
6. Setiap mahasiswa pasti akansuka terhadap
suatu matakuliah
7. Mahasiswa yang tidak pernahhadir pada
kuliah matakuliah sulit, maka mereka pasti tidak suka terhadapmatakuliah
tersebut
8. Andi tidak pernah hadir kuliahmatakuliah
kalkulus.
Buktikan Apakah Andi suka
matakuliah kalkulus?
Jawab:
Ubah pernyataan menjadi bentuk
formula:
1. Mahasiswa(Andi)
2. Informatika(Andi)
3. x: Informatika(x)Teknik(x)
4. sulit(kalkulus)
5. x: Teknik(x)suka(x, kalkulus) benci(x, kalkulus)
6. x: y: suka(x,y)
7. x: y: mahasiswa(x)sulit(y)hadir(x,y)
suka(x,y)
8. hadir(Andi,kalkulus)
Pernyataan Apakah Andi suka
matakuliah kalkulus = suka(Andi,kalkulus)
ARGUMEN PADA LOGIKA PREDIKAT
Validitas sebuah argumen dapat
dibuktikan dengan contoh yang mirip dengan contoh 1. perhatikan contoh argumen
berikut:
Contoh 2:
1. Semua mahasiswa pasti pandai
2. Badu seorang mahasiswa
3. Dengan demikian, Badu pandai
Secara nalar, kebanyakkan orang
akan menilai bahwa argumen di atas mempunyai validitas yang kuat. Akan tetapi,
saat validitas tersebut ingin dibuktikan dengan logika proposisional, ternyata
tidak bisa diselesaikan. Pembuktiannya dapat dilakukan dengan mengikuti
prosedur logika proposisional dengan menentukan terlebih dahulu
proposisi-proposisinya :
A = Semua mahasiswa pasti pandai
B = Badu seorang mahasiswa
C = Badu pasti pandai
Selanjutnya akan menjadi seperti
berikut :
A
B
_____
:. C
Dalam ekspresi logika : (A ˄
B)=>C
Dalam bentuk ekspresi logika
diatas, tidak ada hukum-hukum logika proposisional yang dapat digunakan untuk membuktikan validitas argumen tersebut
karena tidak ada yang mampu menghubungkan antara ketiga proposisi yang
digunakan diatas. Atau tidak mungkin suatu kesimpulan yang berbeda dapat dihasilkan dari premis-premis yang berbeda.
Dengan kata lain, tidak mungkin suatu kesimpulan berupa C dapat dihasilkan dari
premis A dan premis B.
Jika argumen diatas masih ingin
dibuktikan dengan logika proposisional, maka kalimatnya harus diperbaiki. Misal
seperti berikut:
Contoh 3:
1. Jika Badu seorang mahasiswa, maka ia
pasti pandai
2. Badu seorang mahasiswa
3. Dengan demikian, ia pasti pandai
Jika diubah dalam bentuk ekspresi
logika :
1. B=>C premis 1
2. B premis 2
3. C kesimpulan
Atau dapat juga ditulis :
[(B=>C) ˄ B] => C
Dalam logika proposisional,
ekspresi logika diatas sudah benar karena kesimpulan diambil dari premispremis.
Persoalan yang terjadi adalah pernyataan tersebut tidak sepenuhnya mampu
menangkap ide pada argumen yang pertama yaitu “Semua mahasiswa pandai”. Ide
pada pernyataan tersebut tidak tertangkap pada argumen kedua karena hanya mampu
menunjuk seorang mahasiswa yaitu Badu, bukan semua mahasiswa. Persoalan lain
juga terjadi, yakni kesulitan menentukan objek. Misalnya orang yang dimaksudkan
jika diganti dengan kata ganti orang. Perhatikan pernyataan-pernyataan pada
contoh argumen berikut:
Contoh 4:
1. Jika Badu seorang mahasiswa, maka ia
pasti pandai
2. Dewi seorang mahasiswa
3. Dengan demikian, ia pasti pandai
http://aditya291296.blogspot.co.id/2017/10/pencarian-berbentuk-heuristik-search.html
Comments
Post a Comment