Kecerdasan Buatan (KI092301)
First-Order Logic Chastine Fatichah Teknik Informatika Institut Teknologi Sepuluh Nopember November 2012
12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
1 / 17
Pokok Bahasan • • • • •
Mengapa FOL? Syntax dan semantics pada FOL Penggunaan FOL Wumpus world pada FOL Knowledge engineering pada FOL
12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
2
Logika Propositional Logika propositional adalah declarative Logika propositional mengijinkan informasi partial/disjunctive/negated – (tidak seperti struktur data dan database)
Logika propositional merupakan compositional:
– meaning of B1,1 P1,2 is derived from meaning of B1,1 and of P1,2
Arti pada logika propositional context-independent
– (tidak seperti natural language, dimana arti tergantung context)
Logika propositional mempunyai kekuatan ekspresif terbatas – (tidak seperti natural language) – Misal: tidak bisa seperti kamliat "pits cause breezes in adjacent squares“ • Kecuali dengan menulis satu kalimat pada setiap square 12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
3
First-order logic • Logika propositional mengasumsikan dunia dengan fakta-fakta, • First-order logic (seperti natural language) mengasumsikan dunia berisi – Objects: people, houses, numbers, colors, baseball games, wars, … – Relations: red, round, prime, brother of, bigger than, part of, comes between, … – Functions: father of, best friend, one more than, plus, … 12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
4
Syntax pada FOL: Elemen dasar • • • • • • •
Constants Predicates Functions Variables Connectives Equality Quantifiers
12/10/2012
KingJohn, 2, NUS,... Brother, >,... Sqrt, LeftLegOf,... x, y, a, b,... , , , , = ,
First-Order Logic @ Kecerdasan Buatan (KI092301)
5
Kamliat 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
First-Order Logic @ Kecerdasan Buatan (KI092301)
6
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) 12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
7
Contoh: Model untuk FOL
12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
8
Universal quantification •
<sentence>
Everyone at NUS is smart: x At(x,NUS) Smart(x) • x P bernilai true di sebuah model m iff P bernilai benar dengan x di setiap obyek pada model • Equaivalensi conjunction pada instantiations pada P ... 12/10/2012
At(KingJohn,NUS) Smart(KingJohn) At(Richard,NUS) Smart(Richard) At(NUS,NUS) Smart(NUS)
First-Order Logic @ Kecerdasan Buatan (KI092301)
9
Kesalahan umum yang harus dihindari • adalah konektvitas utama dengan • Kesalahan umum: menggunakan sebagai konektivitas utama dengan : x At(x,NUS) Smart(x) artinya “Everyone is at NUS and everyone is smart”
12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
10
Existential quantification • <sentence>
• Someone at NUS is smart: • x At(x,NUS) Smart(x)$ • x P bernilai benar pada sebuah model m iff P adalah benar dengan x di beberapa obyek pada model • Equivalensi disjunction pada instantiations pada P At(KingJohn,NUS) Smart(KingJohn) At(Richard,NUS) Smart(Richard) At(NUS,NUS) Smart(NUS) ...
12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
11
Kesalahan umum yang harus dihindari • adalah konektivitas utama dengan • Kesalahan umum: menggunakan sebagai konektifitas utama dengan : x At(x,NUS) Smart(x) bernilai benar jika ada seseorang yang tidak di NUS!
12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
12
Properti pada quantifiers • x y is the same as y x • x y is the same as y x • x y is not the same as y x • x y Loves(x,y) – “There is a person who loves everyone in the world”
• y x Loves(x,y)
– “Everyone in the world is loved by at least one person”
• Quantifier duality: • x Likes(x,IceCream) • x Likes(x,Broccoli)
12/10/2012
x Likes(x,IceCream) x Likes(x,Broccoli)
First-Order Logic @ Kecerdasan Buatan (KI092301)
13
Equality • term1 = term2 bernilai benar dalam interpretasi jika dan hanya jika term1 dan term2 merefer ke obyek yang sama • Misal: pendefinisian Sibling pada term pada Parent: x,y Sibling(x,y) [(x = y) m,f (m = f) Parent(m,x) Parent(f,x) Parent(m,y) Parent(f,y)]
12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
14
Penggunaan FOL • Brothers are siblings x,y Brother(x,y) Sibling(x,y)
• One's mother is one's female parent m,c Mother(c) = m (Female(m) Parent(m,c))
• “Sibling” is symmetric x,y Sibling(x,y) Sibling(y,x)
12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
15
Latihan First-order logic • • • •
Some students took French in spring 2001 Every student who takes French passes it Only one student took Greek in spring 2001 The best score in Greek is always higher than the best score in French • Every person who byus a policy is smart • No person buys an expensive policy • There is an agent who sells policies only to people who are not insured 12/10/2012
First-Order Logic @ Kecerdasan Buatan (KI092301)
16
Sumber : 1.Slide perkuliahan Stuart Russell's (Berkeley) http://aima.cs.berkeley.edu/
12/10/2012
Logical Agents @ Kecerdasan Buatan (KI092301)
17
