First-Order Logic

Chastine Fatichah

Teknik Informatika

Institut Teknologi Sepuluh Nopember

November 2012

12/10/2012 1 / 17 First-Order Logic @ Kecerdasan Buatan

(KI092301)

Kecerdasan Buatan (KI092301)

Pokok Bahasan

• Mengapa FOL?

• Syntax dan semantics pada FOL

• Penggunaan FOL

• Wumpus world pada FOL

• Knowledge engineering pada FOL

12/10/2012 2 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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 3 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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 4 First-Order Logic @ Kecerdasan Buatan

(KI092301)

Syntax pada FOL: Elemen dasar

• Constants KingJohn, 2, NUS,...

• Predicates Brother, >,...

• Functions Sqrt, LeftLegOf,...

• Variables x, y, a, b,...

• Connectives , , , ,

• Equality =

• Quantifiers ,

12/10/2012 5 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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 6 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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 7 First-Order Logic @ Kecerdasan Buatan

(KI092301)

Contoh: Model untuk FOL

12/10/2012 8 First-Order Logic @ Kecerdasan Buatan

(KI092301)

Universal quantification

• <variables> <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

At(KingJohn,NUS) Smart(KingJohn)

At(Richard,NUS) Smart(Richard)

At(NUS,NUS) Smart(NUS)

...

12/10/2012 9 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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 10 First-Order Logic @ Kecerdasan Buatan

(KI092301)

Existential quantification

• <variables> <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 11 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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 12 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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,IceCream)

• x Likes(x,Broccoli) x Likes(x,Broccoli)

12/10/2012 13 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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 14 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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 15 First-Order Logic @ Kecerdasan Buatan

(KI092301)

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 16 First-Order Logic @ Kecerdasan Buatan

(KI092301)

12/10/2012 Logical Agents @ Kecerdasan Buatan

(KI092301)

17

Sumber :

1.Slide perkuliahan Stuart Russell's (Berkeley) http://aima.cs.berkeley.edu/