CSC242 Lecture 2.4 First Order Logic
CSC242:
Introduction to
Artificial Intelligence
Lecture 2.4
Please put away all electronic devices
Announcements
• Project 2 due Sunday 1159PM
• Unit 2 Exam: One week from Thursday
(Fall Break next Mon/Tue)
Factored Representation
• Splits a state into variables (or
attributes) that can have values
• Factored states can be more or less
similar (unlike atomic states)
• Can also represent uncertainty (don’t
know value of some attribute)
Constraint Satisfaction
Problem (CSP)
• X: Set of variables { X1, …, Xn }
• D: Set of domains { D1, …, Dn }
• Each Di : set of values { v1, …, vk }
• C: Set of constraints { C1, …, Cm }
• Solution: Assign to each Xi a value from
Di such that all the Ci are satisfied
Propositional Logic
• Programming language for knowledge
• Factored representation (Boolean CSP)
• Propositions, connectives, sentences
• Possible worlds, satisfiability, models
• Entailment: α ⊨ β
• Every model of α is a model of β
• Intractable! (co-NP-complete)
• Inference rules: Soundness, Completeness
• Proof: α ⊢ β
• Searching for proofs is an alternative to
enumerating models; “can be more
efficient” (at least sometimes)
• Resolution: sound and complete inference rule
• Works on clauses (CNF); requires refutation
• Forward and backward chaining
Propositional Theorem
Proving
Forward Chaining
• Reasons forward from new facts
• Data-driven
• Done by humans—to some extent
• When to stop?
• For KBs using only definite clauses
• Sound, complete, linear time
AIMA 7.5.4
Backward Chaining
• Reasons backward from query
• Goal-directed
• Useful for answering specific questions
• For KBs using only definite clauses
• Sound, complete, linear time
AIMA 7.5.4
Propositional Inference
• Computing whether
• Model Checking
• Intractable (but see AIMA 7.6)
• Inference rules: Soundness, Completeness
• Derivation:
• Searching for proofs is an alternative to enumerating
models
• May be faster in practice
• Resolution is a sound and complete-ish inference rule
• Works on clauses (CNF), requires refutation proof
↵ |= �
↵ ` �
PL 👍
• Declarative: based on a truth relation
between sentences and possible worlds
PL 👍
• Declarative: based on a truth relation
between sentences and possible worlds
• Expressive: can represent partial
information (e.g., disjunction, negation)
PL 👍
• Declarative: based on a truth relation
between sentences and possible worlds
• Expressive: can represent partial
information (e.g., disjunction, negation)
• Compositional: the meaning of a
sentence is a function of the meanings
of its parts
PL 👎
• Model checking takes exponential time
• Theorem proving may help
PL 👎
• Model checking takes exponential time
• Theorem proving may help
• Lacks the expressive power to describe
concisely complex environments (many
objects, relationships between them)
B1,1 ⇔ (P1,2 ∨ P2,1)
B1,2 ⇔ (P1,3 ∨ P2,2 ∨ P1,1)
B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1)
B2,2 ⇔ (P2,1 ∨ P3,2 ∨ P2,3)
…
B4,4 ⇔ (P3,4 ∨ P4,3)
B1,1 ⇔ (P1,2 ∨ P2,1)
B1,2 ⇔ (P1,3 ∨ P2,2 ∨ P1,1)
B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1)
B2,2 ⇔ (P2,1 ∨ P3,2 ∨ P2,3)
…
B4,4 ⇔ (P3,4 ∨ P4,3)
“Rooms adjacent to pits are breezy”
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
Logic 2.0
• Define a language based on
propositional logic that will allow us to
say all these things
• Define entailment (“follows from”)
• Figure out how to compute what follows
from our knowledge
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
Ontology
ontology |änˈtäləjē|
noun
1 the branch of metaphysics dealing with the nature of
being.
2 a set of concepts and categories in a subject area or
domain that shows their properties and the relations
between them
ORIGIN early 18th cent.: from modern Latin ontologia,
from Greek ōn, ont- ‘being’ + -logy.
x-dictionary:r:m_en_us1264175:com.apple.dictionary.NOAD
Ontology
• Objects: people, houses, numbers, theories,
Socrates, colors, wars, …
• Relations:
• Unary (Properties): breezy, mortal, red, round,
bogus, prime, …
• n-ary: brother of, bigger than, inside, part of,
has color, occurred after, owns, above, between
• Functions: “single-valued” relations: mother of,
father of, best friend, one more than, …
Ontologies
(Factored Representations)
• Logic 1.0 (Propositional Logic)
• Identify Boolean features of the
world
• Logic 2.0:
• Identify objects, relations, and
functions in the world
Ontology (Domain of
Discourse, Conceptualization)
• Objects: people, houses, numbers, theories,
Socrates, colors, wars, …
• Relations:
• Unary (Properties): breezy, mortal, red, round,
bogus, prime, …
• n-ary: brother of, bigger than, inside, part of,
has color, occurred after, owns, above, between
• Functions: “single-valued” relations: mother of,
father of, best friend, one more than, …
A Programming
Language for Knowledge
• Syntax:
• What counts as a well-formed
statement, formula, sentence, or
program
• Semantics:
• What these statements, formulas,
sentences, or programs mean
Propositional Logic:
Proposition Symbols
• Symbols denoting propositions (things
that can be true of false)
• W1,1, Raining, Hungry, Cranky, …
denote |diˈnōt|
verb [ trans. ]
be a sign of; indicate : this mark denotes purity and quality.
• (often be denoted) stand as a name or symbol for :
the level of output per firm, denoted by X.
Constant Symbols
• Symbols denoting objects in the world
• Socrates, George, Snoopy, …
denote |diˈnōt|
verb [ trans. ]
be a sign of; indicate : this mark denotes purity and quality.
• (often be denoted) stand as a name or symbol for :
the level of output per firm, denoted by X.
Relation (Predicate)
Symbols
• Symbols denoting relations
• Mortal(⋅), Smelly(⋅), Breezy(⋅), On(⋅,⋅),
Above(⋅,⋅), Equals(⋅,⋅) a.k.a. “⋅=⋅”, …
• Arity: number of arguments
pred·i·cate
noun | ˈpredəkət |
• Logic something that is affirmed or denied concerning an
argument of a proposition.
From Latin praedicatum ‘something declared’
Function Symbols
• Symbols denoting functions
• mother(⋅), father(⋅), oneMoreThan(⋅),
hat(⋅), plus(⋅,⋅) a.k.a. “⋅+⋅”, …
• Arity: number of arguments
Symbols
• Constant symbols: Socrates, George
• Relation symbols: Mortal(⋅), On(⋅,⋅)
• Function symbols: mother(⋅), plus(⋅,⋅)
Term
• A logical expression that denotes
(refers to) an object
• Constant symbol; or
• Function symbol and tuple of terms of
appropriate arity
Socrates mother(George)
plus(1,2) a.k.a. “1+2” mother(father(George))
Atomic Sentence
• States a fact
• Predicate (relation) symbol and tuple of
terms of appropriate arity
Mortal(Socrates)
Atomic Sentence
• States a fact
• Predicate (relation) symbol and tuple of
terms of appropriate arity
Brother(Richard, John)
Married(father(Richard), mother(John))
On(A, B)
Mortal(Socrates)
Connectives
• Connect sentences into larger sentences
that can also be true or false
• Negation (not): ¬
• Conjunction (and): ∧
• Disjunction (or): ∨
• Implication (if-then): ⇒
• Biconditional (iff): ⇔
Connectives
¬On(A, B)
King(Richard) ∨ King(John)
¬King(Richard) ⇒ King(John)
Logic 2.0 (Syntax)
• Constant symbols
• Predicate (relation) symbols & arity
• Function symbols & arity
• Terms
• Atomic sentences
• Complex sentences (using connectives)
Predicate Logic
• Constant symbols
• Predicate (relation) symbols & arity
• Function symbols & arity
• Terms
• Atomic sentences
• Complex sentences (using connectives)
First-Order Predicate
Logic
• Constant symbols
• Predicate (relation) symbols & arity
• Function symbols & arity
• Terms
• Atomic sentences
• Complex sentences (using connectives)
Propositional Logic
Possible World
• Assignment of true or false to all the
atomic propositions
• A possible world satisfies a sentence if
it makes the sentence true
• “A model of the sentence”
Ontology (Domain of
Discourse, Conceptualization)
• Objects: people, houses, numbers, theories,
Socrates, colors, wars, …
• Relations:
• Unary (Properties): breezy, mortal, red, round,
bogus, prime, …
• n-ary: brother of, bigger than, inside, part of,
has color, occurred after, owns, above, between
• Functions: “single-valued” relations: mother of,
father of, best friend, one more than, …
Interpretation
Mortal
On
houseOf
{ 〈 〉, 〈 〉 }
Socrates
George
{ 〈 , 〉 }
{ 〈 〉 → }
Snoopy
Language
Elements
Interpretation I
Objects: ΩI
Constant Symbols σ
Predicate Symbols πn
Function Symbols 𝜙n
Interpretation
I(�) 2 ⌦I
I(⇡n) ✓ ⌦nI
I(�n) : ⌦
n
I ! ⌦I
• Objects: ■, ■, ■, ■, ■
• Relations: being on, being above, being
clear, being on the table
• Functions: “the block on top of me”
Constant Symbols: A, B, C, D, E
Predicate Symbols: On(⋅,⋅), Above(⋅,⋅),
OnTable(⋅), Clear(⋅)
Function Symbols: Hat(⋅)
I(A) = ■
I(B) = ■
I(C) = ■
I(D) = ■
I(E) = ■
I(On) = { ⟨■,■⟩, ⟨■,■⟩, ⟨■,■⟩ }
I(Above) = { ⟨■,■⟩, ⟨■,■⟩, ⟨■,■⟩, ⟨■,■⟩ }
I(OnTable) = { ⟨■⟩, ⟨■⟩ }
I(Clear) = { ⟨■⟩, ⟨■⟩ }
I(Hat) = { ⟨■⟩→■, ⟨■⟩→■, ⟨■⟩→■ }
ΩI = { ■, ■, ■, ■, ■ }
I(A) = ■
I(B) = ■
I(C) = ■
I(D) = ■
I(E) = ■
I(On) = { ⟨■,■⟩, ⟨■,■⟩, ⟨■,■⟩ }
I(Above) = { ⟨■,■⟩, ⟨■,■⟩, ⟨■,■⟩, ⟨■,■⟩ }
I(OnTable) = { ⟨■⟩, ⟨■⟩ }
I(Clear) = { ⟨■⟩, ⟨■⟩ }
I(Hat) = { ⟨■⟩→■, ⟨■⟩→■, ⟨■⟩→■ }
ΩI = { ■, ■, ■, ■, ■ }
John
(1166-1216)
Richard
(1157-1199)
R J
$
left leg
on headbrother
brother
person person
king
crown
left leg
R J
$
left leg
on headbrother
brother
person person
king
crown
left leg
Objects (ΩI):
Richard, John, left leg 1,
left leg 2, the crown
R J
$
left leg
on headbrother
brother
person person
king
crown
left leg
Unary Relations (Properties):
being a person
being a crown
being a king
R J
$
left leg
on headbrother
brother
person person
king
crown
left leg
Binary Relations:
two things being brothers
one thing being on the head of another
R J
$
left leg
on headbrother
brother
person person
king
crown
left leg
Functions:
the left leg of something
I(Richard) =
I(John) =
I(Person) = { ⟨ ⟩, ⟨ ⟩ }
I(King) = { ⟨ ⟩ }
I(Crown) = { ⟨ ⟩ }
I(Brother) = { ⟨ , ⟩, ⟨ , ⟩ }
I(OnHead) = { ⟨ , ⟩ }
I(leftLegOf) = { ⟨ ⟩ → ,
⟨ ⟩ → }
ΩI = { , , , , }R J
R
J
R J
J
R J J R
J
R
J
I(Richard) =
I(John) =
I(Person) = { ⟨ ⟩, ⟨ ⟩ }
I(King) = { ⟨ ⟩ }
I(Crown) = { ⟨ ⟩ }
I(Brother) = { ⟨ , ⟩, ⟨ , ⟩ }
I(OnHead) = { ⟨ , ⟩ }
I(leftLegOf) = { ⟨ ⟩ → ,
⟨ ⟩ → }
ΩI = { , , , , }R J
J
R J
R J J R
J
R
J
J
I(Richard) =
I(John) =
I(Person) = { ⟨ ⟩, ⟨ ⟩ }
I(King) = { ⟨ ⟩ }
I(Crown) = { ⟨ ⟩ }
I(Brother) = { ⟨ , ⟩, ⟨ , ⟩ }
I(OnHead) = { ⟨ , ⟩ }
I(leftLegOf) = { ⟨ ⟩ → ,
⟨ ⟩ → }
ΩI = { , , , , }R J
R J
R J J R
J
R
J
J
I(Richard) =
I(John) =
I(Person) = { ⟨ ⟩, ⟨ ⟩ }
I(King) = { ⟨ ⟩ }
I(Crown) = { ⟨ ⟩ }
I(Brother) = { ⟨ , ⟩, ⟨ , ⟩ }
I(OnHead) = { ⟨ , ⟩ }
I(leftLegOf) = { ⟨ ⟩ → ,
⟨ ⟩ → }
ΩI = { , , , , }R J
R
J
R J
R J J R
J
R
J
J
First-Order Model
(Possible World)
• Ontology (Domain of Discourse,
Conceptualization)
• Objects, relations, and functions
• Interpretation function I
• Constant symbols → Objects
• Predicate symbols → Relations (sets of tuples)
• Function symbols → Functions (mappings)
AIMA p. 290
Satisfaction
• A model (possible world) satisfies a
sentence if it makes the sentence true
• “A model of the sentence”
Terms
• Constant term c
• I(c) ∈ ΩI
• Function term f(t1, …, tn)
• I(f) = some function F
• I(ti) = some object di ∈ ΩI
• I(f(t1, …, tn)) = F(d1, …, dn)
Terms
• Constant term c
• I(c) ∈ ΩI
• Function term f(t1, …, tn)
• I(f) = some function F
• I(ti) = some object di ∈ ΩI
• I(f(t1, …, tn)) = F(d1, …, dn)
“The interpretation fixes the referent (or
denotation) of every term.”
Atomic Sentences
• Atomic sentence P(t1, …, tn)
• I(P) = some relation Φ
• I(ti) = some object di ∈ ΩI
• P(t1, …, tn) is true iff ⟨d1, …, dn⟩ ∈ Φ
Atomic Sentences
• Atomic sentence P(t1, …, tn)
• I(P) = some relation Φ
• I(ti) = some object di ∈ ΩI
• P(t1, …, tn) is true iff ⟨d1, …, dn⟩ ∈ Φ
“An atomic sentence is true in a given model if the
relation referred to by the predicate symbol holds
among the objects referred to by the arguments.”
Complex Sentences
α β ¬α α∧β α∨β α⇒β α⇔β
F F F F T T
F T T F T T F
T F F T F F
T T F T T T T
Semantics of First-Order
Logic
• Set of objects, with relations & functions
• Interpretation function
• Constant symbols → objects
• Predicate symbols → relations (tuples)
• Function symbols → functions (mappings)
• An interpretation satisfies a sentence if it
makes the sentence true
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
Person(Socrates)
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
True in I if ⟨I(Socrates)⟩ ∈ I(Person)
Person(Socrates)
• Rooms adjacent to pits are breezy
• Socrates is a person
All people are mortal
• Anybody’s grandmother is either their
mother’s or their father’s mother
All people are mortal
Every object that is a person is also mortal
For every object x, if x is a person, then
x is mortal
For every object x: Person(x)⇒Mortal(x)
Universal Quantification
• Syntax: ∀x φ
• Semantics: φ is true for every object x
• Extended interpretation maps every
variable to an object in the domain
• ∀x φ is true if φ is true in every
extended interpretation
∀x King(x) ⇒ Person(x)
R J
$
left leg
on headbrother
brother
person person
king
crown
left leg
Objects (ΩI):
Richard, John, left leg 1,
left leg 2, the crown
x → Richard
x → John
x → Richard’s left leg
x → John’s left leg
x → the crown
∀x King(x) ⇒ Person(x)
Richard is a king ⇒ Richard is a person
John is a king ⇒ John is a person
Richard’s left leg is a king ⇒ Richard’s left leg is
a person
John’s left leg is a king ⇒ John’s left leg is a
person
the crown is a king ⇒ the crown is a person
∀x King(x) ⇒ Person(x)
R J
$
left leg
on headbrother
brother
person person
king
crown
left leg
Objects (ΩI):
Richard, John, left leg 1,
left leg 2, the crown
Richard is a king ⇒ Richard is a person
John is a king ⇒ John is a person
Richard’s left leg is a king ⇒ Richard’s left leg is
a person
John’s left leg is a king ⇒ John’s left leg is a
person
the crown is a king ⇒ the crown is a person
true true
True
∀x King(x) ⇒ Person(x)
Richard is a king ⇒ Richard is a person
John is a king ⇒ John is a person
Richard’s left leg is a king ⇒ Richard’s left leg is
a person
John’s left leg is a king ⇒ John’s left leg is a
person
the crown is a king ⇒ the crown is a person
true true
false
false
false
false
True
True
True
True
True
∀x King(x) ⇒ Person(x)
Richard is a king ⇒ Richard is a person
John is a king ⇒ John is a person
Richard’s left leg is a king ⇒ Richard’s left leg is
a person
John’s left leg is a king ⇒ John’s left leg is a
person
the crown is a king ⇒ the crown is a person
true true
false
false
false
false
True
True
True
True
True
True!∀x King(x) ⇒ Person(x)
Universal Quantification
• Syntax: ∀x φ
• Semantics: φ is true for every object x
• Extended interpretation maps every
variable to an object in the domain
• ∀x φ is true if φ is true in every
extended interpretation
All people are mortal.
8x Person(x) ) Mortal(x)
Rooms adjacent to pits are breezy.
8x8y Room(x) ^ Pit(y) ^Adjacent(x, y) ) Breezy(x)
Anybody’s grandmother is either their
mother’s or their father’s mother
8x8y Grandmother(x, y) )
x = mother(mother(y)) _ x = mother(father(y)))
∀x King(x) ∧ Person(x)
Richard is a king ∧ Richard is a person
John is a king ∧ John is a person
Richard’s left leg is a king ∧ Richard’s left leg is a
person
John’s left leg is a king ∧ John’s left leg is a
person
the crown is a king ∧ the crown is a person
True
False
False
False
False
False!∀x King(x) ∧ Person(x)
Rule:
Probably false statement:
∀x King(x) ∧ Person(x)
∀x King(x) ⇒ Person(x)
Existential Quantification
• Syntax: ∃x φ
• Semantics: φ is true for some object x
• Extended interpretation maps every
variable to an object in the domain
• ∃x φ is true if φ is true in some
extended interpretation
John has a crown on his head.
9x Crown(x) ^OnHead(x, John)
John has a crown on his head.
9x Crown(x) ^OnHead(x, John)
x → Richard
x → John
x → Richard’s left leg
x → John’s left leg
x → the crown
John has a crown on his head.
9x Crown(x) ^OnHead(x, John)
x → Richard
x → John
x → Richard’s left leg
x → John’s left leg
x → the crown True
True!
Existential Quantification
• Syntax: ∃x φ
• Semantics: φ is true for some object x
• Extended interpretation maps every
variable to an object in the domain
• ∃x φ is true if φ is true in some
extended interpretation
Nested Quantifiers
Everyone (every person) loves someone
∀x Person(x) ⇒ ∃y Person(y) ∧ Loves(x,y)
Nested Quantifiers
Everyone (every person) loves someone
Someone is loved by everyone
∀x Person(x) ⇒ ∃y Person(y) ∧ Loves(x,y)
∃x Person(x) ∧ ∀y Person(y) ⇒ Loves(y,x)
Nested Quantifiers
Everyone (every person) loves someone
Someone is loved by everyone
∀x Person(x) ⇒ ∃y Person(y) ∧ Loves(x,y)
∃x Person(x) ∧ ∀y Person(y) ⇒ Loves(y,x)
Someone loves everyone
∃x Person(x) ∧ ∀y Person(y) ⇒ Loves(x,y)
∃x ∀y Person(x) ∧ Person(y) ⇒ Loves(x,y)
First-Order Predicate Logic
• Syntax:
• Constant, predicate, and function symbols
• Terms, atomic sentences, connectives
• Quantifiers and variables
• Semantics:
• Ontology of objects, relations, functions
• First-order interpretation
• Extended interpretation
• Satisfaction (sentence true in a possible world)
Entailment
• α entails β : α ⊨ β
• Every model of α is also a model of β
• Whenever α is true, so is β
• β is true in every world consistent with α
•
• β logically follows from α
Models(α) ⊆ Models(β)
Model Checking
• Given knowledge α and query β
• For every possible model I
• If α is satisfied by I
• If β is not satisfied by I
• Conclude that α ⊭ β
• Conclude that α ⊨ β
All Possible Models
• # of objects in the world from 1 to ∞
• Some constants refer to the same object
• Some objects are not referred to by any
constant (“unnamed”)
• Relations and functions defined over sets
of subsets of objects
• Variables range over all possible objects in
extended interpretations
Constant symbols: { R, J }
Relation symbol: P(⋅,⋅)
ΩI = { ●1 }
I(R) = ●1
I(J) = ●1
I(P) = { } 1
R J
Constant symbols: { R, J }
Relation symbol: P(⋅,⋅)
ΩI = { ●1 }
I(R) = ●1
I(J) = ●1
I(P) = { ⟨●1,●1⟩}
1
R J
Constant symbols: { R, J }
Relation symbol: P(⋅,⋅)
ΩI = { ●1 }
Constant symbols: { R, J }
Relation symbol: P(⋅,⋅)
1 interpretation of R and J
2 interpretations of P
2 possible interpretations
ΩI = { ●1, ●2 }
I(R) = ●1
I(J) = ●2
I(P) = …
Constant symbols: { R, J }
Relation symbol: P(⋅,⋅)
22=4 interpretations of R and J
222=16 interpretations of P
64 possible interpretations
1
R J
2
ΩI = { ●1, ●2, ●3 }
I(R) = ●1
I(J) = ●2
I(P) = … 1
R J
Constant symbols: { R, J }
Relation symbol: P(⋅,⋅)
2
32=9 interpretations of R and J
232=29=512 interpretations of P
4608 possible interpretations
3
ΩI = { ●1, ●2, ●3, ●4 }
I(R) = ●1
I(J) = ●2
I(P) = … 1
R J
Constant symbols: { R, J }
Relation symbol: P(⋅,⋅)
2
1,048,576 possible interpretations
3
4
Computing Entailment
• Number of possible models HUGE
• Possibly unbounded
Computing Entailment
• Number of possible models HUGE
• Possibly unbounded
• Can’t do model checking
Computing Entailment
• Number of possible models HUGE
• Possibly unbounded
• Can’t do model checking
• Look for inference rules, do theorem
proving
For next time:
AIMA Ch 9