Introduction to Artificial Intelligence
First-order Logic
(Logic, Deduction, Knowledge Representation)
Bernhard Beckert
UNIVERSITÄT KOBLENZ–LANDAU
Wintersemester 2003/2004
B. Beckert: Einführung in die KI / KI für IM – p.1
Outline
Why first-order logic?
Syntax and semantics of first-order logic
Fun with sentences
Wumpus world in first-order logic
B. Beckert: Einführung in die KI / KI für IM – p.2
Pros and Cons of Propositional Logic
Propositional logic is declarative:
pieces of syntax correspond to facts
Propositional logic allows partial / disjunctive / negated information
(unlike most data structures and databases)
Propositional logic is compositional:
meaning of B1,1∧P1,2is derived from meaning of B1,1and 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)
Example:
Cannot say “pits cause breezes in adjacent squares”
except by writing one sentence for each square
B. Beckert: Einführung in die KI / KI für IM – p.3
Pros and Cons of Propositional Logic
Propositional logic is declarative:
pieces of syntax correspond to facts
Propositional logic allows partial / disjunctive / negated information
(unlike most data structures and databases)
Propositional logic is compositional:
meaning of B1,1∧P1,2is derived from meaning of B1,1and 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)
Example:
Cannot say “pits cause breezes in adjacent squares”
except by writing one sentence for each square
B. Beckert: Einführung in die KI / KI für IM – p.3
Pros and Cons of Propositional Logic
Propositional logic is declarative:
pieces of syntax correspond to facts
Propositional logic allows partial / disjunctive / negated information
(unlike most data structures and databases)
Propositional logic is compositional:
meaning of B1,1∧P1,2is derived from meaning of B1,1and 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)
Example:
Cannot say “pits cause breezes in adjacent squares”
except by writing one sentence for each square
B. Beckert: Einführung in die KI / KI für IM – p.3
Pros and Cons of Propositional Logic
Propositional logic is declarative:
pieces of syntax correspond to facts
Propositional logic allows partial / disjunctive / negated information
(unlike most data structures and databases)
Propositional logic is compositional:
meaning of B1,1∧P1,2is derived from meaning of B1,1and 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)
Example:
Cannot say “pits cause breezes in adjacent squares”
except by writing one sentence for each square
B. Beckert: Einführung in die KI / KI für IM – p.3
Pros and Cons of Propositional Logic
Propositional logic is declarative:
pieces of syntax correspond to facts
Propositional logic allows partial / disjunctive / negated information
(unlike most data structures and databases)
Propositional logic is compositional:
meaning of B1,1∧P1,2is derived from meaning of B1,1and 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)
Example:
Cannot say “pits cause breezes in adjacent squares”
except by writing one sentence for each square
B. Beckert: Einführung in die KI / KI für IM – p.3
First-order Logic
Propositional logic
Assumes that the world contains facts
First-order logic
Assumes that the world contains
Objects
people, houses, numbers, theories, Donald Duck, colors, centuries, . . .
Relations
red, round, prime, multistoried, . . .
brother of, bigger than, part of, has color, occurred after, owns, . . .
Functions
+, middle of, father of, one more than, beginning of, …
B. Beckert: Einführung in die KI / KI für IM – p.4
First-order Logic
Propositional logic
Assumes that the world contains facts
First-order logic
Assumes that the world contains
Objects
people, houses, numbers, theories, Donald Duck, colors, centuries, …
Relations
red, round, prime, multistoried, . . .
brother of, bigger than, part of, has color, occurred after, owns, . . .
Functions
+, middle of, father of, one more than, beginning of, …
B. Beckert: Einführung in die KI / KI für IM – p.4
First-order Logic
Propositional logic
Assumes that the world contains facts
First-order logic
Assumes that the world contains
Objects
people, houses, numbers, theories, Donald Duck, colors, centuries, …
Relations
red, round, prime, multistoried, …
brother of, bigger than, part of, has color, occurred after, owns, …
Functions
+, middle of, father of, one more than, beginning of, …
B. Beckert: Einführung in die KI / KI für IM – p.4
First-order Logic
Propositional logic
Assumes that the world contains facts
First-order logic
Assumes that the world contains
Objects
people, houses, numbers, theories, Donald Duck, colors, centuries, …
Relations
red, round, prime, multistoried, …
brother of, bigger than, part of, has color, occurred after, owns, …
Functions
+, middle of, father of, one more than, beginning of, …
B. Beckert: Einführung in die KI / KI für IM – p.4
Syntax of First-order Logic: Basic Elements
Symbols
Constants KingJohn,2,Koblenz,C,…
Note
The equality predicate is always in the vocabulary
It is written in infix notation
Term
function (term1, . . . , termn)
or
constant
or
variable
Example
Domain
A non-empty (finite or infinite) set of arbitrary elements
Interpretation
Assigns to each
– constant symbol: a domain element
– predicate symbol: a relation on the domain (of appropriate arity)
– function symbol: a function on the domain (of appropriate arity)
Interpretation
Assigns to each
– constant symbol: a domain element
– predicate symbol: a relation on the domain (of appropriate arity)
– function symbol: a function on the domain (of appropriate arity)
The truth value of a complex sentence in a model
is computed from the truth-values of its atomic sub-sentences
in the same way as in propositional logic
Example
“Everyone studying in Koblenz is smart:
∀x
|{z}
variables
(StudiesAt(x,Koblenz)⇒Smart(x))
| {z }
sentence
Intuition
∀xP is roughly equivalent to the conjunction of all instances of P
Example ∀x StudiesAt(x,Koblenz)⇒Smart(x)equivalent to:
StudiesAt(KingJohn,Koblenz)⇒Smart(KingJohn)
∧StudiesAt(Richard,Koblenz)⇒Smart(Richard)
∧StudiesAt(Koblenz,Koblenz)⇒Smart(Koblenz)
∧…
Example ∀x StudiesAt(x,Koblenz)⇒Smart(x)equivalent to:
StudiesAt(KingJohn,Koblenz)⇒Smart(KingJohn)
∧StudiesAt(Richard,Koblenz)⇒Smart(Richard)
∧StudiesAt(Koblenz,Koblenz)⇒Smart(Koblenz)
∧…
Example
Correct: ∀x(StudiesAt(x,Koblenz)⇒Smart(x))
“Everyone who studies at Koblenz is smart”
Wrong: ∀x(StudiesAt(x,Koblenz)∧Smart(x))
“Everyone studies at Koblenz and is smart”, i.e.,
“Everyone studies at Koblenz and everyone is smart”
Wrong: ∀x(StudiesAt(x,Koblenz)∧Smart(x))
“Everyone studies at Koblenz and is smart”, i.e.,
“Everyone studies at Koblenz and everyone is smart”
Example
“Someone studying in Landau is smart:
∃x
|{z}
variables
(StudiesAt(x,Landau)∧Smart(x))
| {z }
sentence
Intuition
∃xP is roughly equivalent to the disjunction of all instances of P
Example ∃x StudiesAt(x,Landau)∧Smart(x)equivalent to:
StudiesAt(KingJohn,Landau)∧Smart(KingJohn)
∨StudiesAt(Richard,Landau)∧Smart(Richard)
∨StudiesAt(Landau,Landau)∧Smart(Landau)
∨…
Example ∃x StudiesAt(x,Landau)∧Smart(x)equivalent to:
StudiesAt(KingJohn,Landau)∧Smart(KingJohn)
∨StudiesAt(Richard,Landau)∧Smart(Richard)
∨StudiesAt(Landau,Landau)∧Smart(Landau)
∨…
Example
Correct: ∃x(StudiesAt(x,Landau)∧Smart(x))
“There is someone who studies at Landau and is smart”
Wrong: ∃x(StudiesAt(x,Landau)⇒Smart(x))
“There is someone who, if he/she studies at Landau, is smart”
This is true if there is anyone not studying at Landau
Wrong: ∃x(StudiesAt(x,Landau)⇒Smart(x))
“There is someone who, if he/she studies at Landau, is smart”
This is true if there is anyone not studying at Landau
“Sibling” is symmetric
∀x,y(Sibling(x,y)⇔Sibling(y,x))
“One’s mother is one’s female parent”
∀x,y(Mother(x,y)⇔(Female(x)∧Parent(x,y)))
“A first cousin is a child of a parent’s sibling”
∀x,y(FirstCousin(x,y)⇔ ∃p,ps (Parent(p,x)∧Sibling(ps,p)∧Parent(ps,y)))
“One’s mother is one’s female parent”
∀x,y(Mother(x,y)⇔(Female(x)∧Parent(x,y)))
“A first cousin is a child of a parent’s sibling”
∀x,y(FirstCousin(x,y)⇔ ∃p,ps (Parent(p,x)∧Sibling(ps,p)∧Parent(ps,y)))
“A first cousin is a child of a parent’s sibling”
∀x,y(FirstCousin(x,y)⇔ ∃p,ps (Parent(p,x)∧Sibling(ps,p)∧Parent(ps,y)))
Examples
1=2and ∀x×(Sqrt(x),Sqrt(x)) = xare satisfiable
2=2is valid
Calculi
There are sound and complete calculi for first-order logic (e.g. resolution)
Whenever KB `α, it is also true that KB |=α
Whenever KB |=α, it is also true that KB `α
But these calculi CANNOT decide validity, entailment, etc.
