程序代写代做代考 data structure flex chain database First-Order Logic

First-Order Logic

CISC 6525
Artificial Intelligence
First-Order Logic

Russell & Norvig, Chapter 8

Outline
Why FOL?
Syntax and semantics of FOL
Using FOL
Wumpus world in FOL
Knowledge engineering in FOL

Last Week: Propositional Logic
Propositions; Syntax, Semantics

Entailment: α ╞  iff M(α)  M()
Model checking for Wumpus world

KB ╞ g iff M(KB)  M(g)

Inference: α ├i  = sentence  can be derived from α (sound?, complete?)
Resolution: show KBα unsatisfiable
Horn clauses; Back/Forward Chaining

Propositional Logic: Pros & Cons
 Propositional logic is declarative
 Propositional logic allows partial/disjunctive/negated information
(unlike many data structures and databases)
Propositional logic is compositional:
meaning of B1,1  P1,2 is derived from meaning of B1,1 and of P1,2

 Meaning in propositional logic is context-independent
(unlike natural language, where meaning depends on context)

 Propositional logic has very limited expressive power
(unlike natural language)
E.g., cannot say “pits cause breezes in adjacent squares“
except by writing one sentence for each square

First-order logic
Whereas propositional logic assumes the world contains facts,

first-order logic (like natural language) assumes the world contains
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, …

Syntax of FOL: Basic elements
Constants KingJohn, 2, NUS,…
Predicates Brother, >,…
Functions Sqrt, LeftLegOf,…
Variables x, y, a, b,…
Connectives , , , , 
Equality =
Quantifiers , 

Atomic sentences
Atomic sentence  predicate (term1,…,termn) or term1 = term2

Term  function (term1,…,termn) or constant
or variable

E.g.,
Brother( KingJohn, RichardTheLionheart )
E.g.,

>( Length( LeftLegOf( Richard) ),
Length( LeftLegOf( KingJohn) ) )

Complex sentences
Complex sentences are made from atomic sentences using connectives

S, S1  S2, S1  S2, S1  S2, S1  S2,

E.g.,
Sibling( KingJohn, Richard ) 
Sibling( Richard, KingJohn )
E.g.,

>( 1, 2 )  ≤ ( 1, 2)
>( 1,2 )   >( 1, 2)

Truth in first-order logic
Sentences are true with respect to a model and an interpretation

Model contains objects (domain elements) and relations among them

Interpretation specifies referents for

constant symbols → objects
predicate symbols → relations
function symbols → functional relations

An atomic sentence predicate(term1,…,termn) is true

iff the objects referred to by term1,…,termn
are in the relation referred to by predicate

Models for FOL: Example

Universal quantification

Everyone at Fordham is smart:
x At(x, Fordham )  Smart(x)

x P is true in a model m iff P is true with x being each possible object in the model

Roughly speaking, equivalent to the conjunction of instantiations of P

At(KingJohn,Fordham)  Smart(KingJohn)
 At(Richard, Fordham)  Smart(Richard)
 At(Fordham,Fordham)  Smart(Fordham)
 …

A common mistake to avoid

Typically,  is the main connective with 

Common mistake: using  as the main connective with  –

x At(x,Fordham)  Smart(x)

means “Everyone is at Fordham and everyone is smart”

Existential quantification

Someone at Fordham is smart:
x At(x,Fordham)  Smart(x)

x P is true in a model m iff P is true with x being some possible object in the model

Roughly speaking, equivalent to the disjunction of instantiations of P

At(KingJohn,Fordham)  Smart(KingJohn)
 At(Richard, Fordham)  Smart(Richard)
 At(Fordham,Fordham)  Smart(Fordham)
 …

Another common mistake to avoid

Typically,  is the main connective with 

Common mistake: using  as the main connective with  –

x At(x,Fordham)  Smart(x)

is true if there is anyone who is not at Fordham!

Properties of 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: each can be expressed using the other

x Likes(x,IceCream) x Likes(x,IceCream)
x Likes(x,Broccoli) x Likes(x,Broccoli)

Equality
term1 = term2 is true under a given interpretation if and only if term1 and term2 refer to the same object

E.g.,
definition of Sibling in terms of Parent:

x,y Sibling(x,y)  [(x = y)   m, f  (m = f) 
Parent( m, x )  Parent( f, x ) 
Parent( m, y )  Parent( f, y ) ]

Using FOL
The kinship domain:
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)

Using FOL
The set domain:
s Set(s)  (s = {} )  (x,s2 Set(s2)  s = {x|s2})
x,s {x|s} = {}
x,s x  s  s = {x|s}
x,s x  s  [ y,s2} (s = {y|s2}  (x = y  x  s2))]
s1,s2 s1  s2  (x x  s1  x  s2)
s1,s2 (s1 = s2)  (s1  s2  s2  s1)
x,s1,s2 x  (s1  s2)  (x  s1  x  s2)
x,s1,s2 x  (s1  s2)  (x  s1  x  s2)

Suppose a wumpus-world agent is using an FOL KB and perceives a smell and a breeze (but no glitter) at t=5:

Tell( KB, Percept([Smell,Breeze,None],5) )
Ask( KB, a BestAction(a,5) )

I.e., does the KB entail some best action at t=5?

Answer: Yes, {a/Shoot} ← substitution (binding list)

Given a sentence S and a substitution σ,

Sσ denotes the result of plugging σ into S; e.g.,

S = Smarter(x,y)
σ = {x/Hillary,y/Bill}
Sσ = Smarter(Hillary,Bill)

=> Ask(KB,S) returns some/all σ such that KB╞ σ
Interacting with FOL KBs

Knowledge base for the wumpus world
Perception
t,s,b Percept([s,b,Glitter],t)  Glitter(t)

Reflex
t Glitter(t)  BestAction(Grab,t)

Deducing hidden properties
x,y,a,b Adjacent([x,y],[a,b]) 

[a,b]  { [x+1,y], [x-1,y],[x,y+1],[x,y-1 ]}

Properties of squares:
s,t At(Agent,s,t)  Breeze(t)  Breezy(s)

Squares are breezy near a pit:
Diagnostic rule—infer cause from effect

s Breezy(s)  r Adjacent(r,s)  Pit(r)
Causal rule—infer effect from cause

r Pit(r)  [s Adjacent(r,s)  Breezy(s) ]

Knowledge engineering in FOL
Identify the task
Assemble the relevant knowledge
Decide on a vocabulary of predicates,
functions, and constants
Encode general knowledge about the domain
Encode a description of the specific problem instance
Pose queries to the inference procedure and get answers
Debug the knowledge base

Summary
First-order logic:
objects and relations are semantic primitives
syntax: constants, functions, predicates, equality, quantifiers

Increased expressive power: sufficient to define wumpus world

The electronic circuits domain
One-bit full adder

The electronic circuits domain
Identify the task
Does the circuit actually add properly? (circuit verification)

Assemble the relevant knowledge
Composed of wires and gates; Types of gates (AND, OR, XOR, NOT)
Irrelevant: size, shape, color, cost of gates

Decide on a vocabulary
Alternatives:

Type(X1) = XOR
Type(X1, XOR)
XOR(X1)

The electronic circuits domain
Encode general knowledge of the domain
t1,t2 Connected(t1, t2)  Signal(t1) = Signal(t2)
t Signal(t) = 1  Signal(t) = 0
1 ≠ 0
t1,t2 Connected(t1, t2)  Connected(t2, t1)
g Type(g) = OR  Signal(Out(1,g)) = 1  n Signal(In(n,g)) = 1
g Type(g) = AND  Signal(Out(1,g)) = 0  n Signal(In(n,g)) = 0
g Type(g) = XOR  Signal(Out(1,g)) = 1  Signal(In(1,g)) ≠ Signal(In(2,g))
g Type(g) = NOT  Signal(Out(1,g)) ≠ Signal(In(1,g))

The electronic circuits domain
Encode the specific problem instance
Type(X1) = XOR Type(X2) = XOR
Type(A1) = AND Type(A2) = AND
Type(O1) = OR

Connected(Out(1,X1),In(1,X2)) Connected(In(1,C1),In(1,X1))
Connected(Out(1,X1),In(2,A2)) Connected(In(1,C1),In(1,A1))
Connected(Out(1,A2),In(1,O1)) Connected(In(2,C1),In(2,X1))
Connected(Out(1,A1),In(2,O1)) Connected(In(2,C1),In(2,A1))
Connected(Out(1,X2),Out(1,C1)) Connected(In(3,C1),In(2,X2))
Connected(Out(1,O1),Out(2,C1)) Connected(In(3,C1),In(1,A2))

The electronic circuits domain
Pose queries to the inference procedure
What are the possible sets of values of all the terminals for the adder circuit?
i1,i2,i3,o1,o2 Signal(In(1,C_1)) = i1  Signal(In(2,C1)) = i2  Signal(In(3,C1)) = i3  Signal(Out(1,C1)) = o1  Signal(Out(2,C1)) = o2

Debug the knowledge base
May have omitted assertions like 1 ≠ 0

Summary
First-order logic:
objects and relations are semantic primitives
syntax: constants, functions, predicates, equality, quantifiers

Increased expressive power: sufficient to define wumpus world