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)
•
• •
Propositional Theorem
Proving
• 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
•
•
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’sgrandmotheriseithertheir 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’sgrandmotheriseithertheir mother’s or their father’s mother
• Rooms adjacent to pits are breezy • Socrates is a person
All people are mortal
• Anybody’sgrandmotheriseithertheir mother’s or their father’s mother
• Rooms adjacent to pits are breezy • Socrates is a person
All people are mortal
• Anybody’sgrandmotheriseithertheir mother’s or their father’s mother
• Rooms adjacent to pits are breezy • Socrates is a person
All people are mortal
• Anybody’sgrandmotheriseithertheir mother’s or their father’s mother
• Rooms adjacent to pits are breezy • Socrates is a person
All people are mortal
• Anybody’sgrandmotheriseithertheir 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.
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
Mortal(Socrates)
On(A, B)
Brother(Richard, John) Married(father(Richard), mother(John))
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
{〈 〉,〈 〉} {〈,〉}
{〈〉→}
Socrates George
Snoopy
Mortal On
houseOf
Language Elements
Constant Symbols Predicate Symbols Function Symbols
Interpretation I Objects: ΩI
Interpretation
I( ) 2 ⌦I
I(⇡n) ✓ ⌦nI
I( n):⌦nI !⌦I
σ πn
𝜙n
• 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 = { ■, ■, ■, ■, ■ }
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) = { ⟨■⟩→■, ⟨■⟩→■, ⟨■⟩→■ }
Richard John (1157-1199) (1166-1216)
crown
person
brother brother
on head
person king
R$J left leg
left leg
crown
person
brother brother
on head
person king
R$J left leg
left leg
Objects (ΩI):
Richard, John, left leg 1, left leg 2, the crown
person
RJ
crown
person king
brother brother
on head
$
left leg
left leg
Unary Relations (Properties): being a person
being a crown
being a king
crown
on head
person
brother brother
R$J left leg
person king
left leg
Binary Relations:
two things being brothers
one thing being on the head of another
crown
person
brother brother
on head
person king
R$J
left leg
left leg
Functions:
the left leg of something
ΩI = { , , , , }
I(Richard) =
I(John) =
I(Person) = { ⟨ R ⟩, ⟨ J ⟩ } I(King) = { ⟨ J ⟩ } I(Crown) = { ⟨ ⟩ } I(Brother) = { ⟨ , ⟩, ⟨ I(OnHead) = { ⟨ , J ⟩ } I(leftLegOf) = { ⟨ R ⟩ →
, ⟩ }
R
J
R
J
R
J
J
R
, ⟨J ⟩→ }
ΩI = { , , , , }
I(Richard) =
I(John) =
I(Person) = { ⟨ R ⟩, ⟨ J ⟩ } I(King) = { ⟨ J ⟩ } I(Crown) = { ⟨ ⟩ } I(Brother) = { ⟨ , ⟩, ⟨ I(OnHead) = { ⟨ , J ⟩ } I(leftLegOf) = { ⟨ R ⟩ →
, ⟩ }
R
J
J
R
J
J
R
, ⟨J ⟩→ }
ΩI = { , , , , }
I(Richard) =
I(John) =
I(Person) = { ⟨ R ⟩, ⟨ J ⟩ } I(King) = { ⟨ J ⟩ } I(Crown) = { ⟨ ⟩ } I(Brother) = { ⟨ , ⟩, ⟨ I(OnHead) = { ⟨ , J ⟩ } I(leftLegOf) = { ⟨ R ⟩ →
, ⟩ }
R
J
R
J
J
R
, ⟨J ⟩→ }
ΩI = { , , , , }
I(Richard) =
I(John) =
I(Person) = { ⟨ R ⟩, ⟨ J ⟩ } I(King) = { ⟨ J ⟩ } I(Crown) = { ⟨ ⟩ } I(Brother) = { ⟨ , ⟩, ⟨ I(OnHead) = { ⟨ , J ⟩ } I(leftLegOf) = { ⟨ R ⟩ →
, ⟩ }
R
J
R
J
R
J
J
R
, ⟨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
• Amodel(possibleworld)satisfiesa 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)
• Aninterpretationsatisfiesasentenceifit makes the sentence true
• Rooms adjacent to pits are breezy
• Socrates is a person All people are mortal
• Anybody’sgrandmotheriseithertheir mother’s or their father’s mother
• Rooms adjacent to pits are breezy
• Socrates is a person All people are mortal
• Anybody’sgrandmotheriseithertheir mother’s or their father’s mother
Person(Socrates)
• Rooms adjacent to pits are breezy
• Socrates is a person All people are mortal
• Anybody’sgrandmotheriseithertheir mother’s or their father’s mother
Person(Socrates)
True in I if ⟨I(Socrates)⟩ ∈ I(Person)
• Rooms adjacent to pits are breezy
• Socrates is a person All people are mortal
• Anybody’sgrandmotheriseithertheir 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φistrueifφistrueinevery extended interpretation
∀x King(x) ⇒ Person(x)
crown
person
brother brother
on head
person king
R$J left leg
left leg
Objects (ΩI):
Richard, John, left leg 1, left leg 2, the crown
∀x King(x) ⇒ Person(x)
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
brother brother
on head
crown
person
person king
R$J left leg
left leg
Objects (ΩI):
Richard, John, left leg 1, left leg 2, the crown
∀x King(x) ⇒ Person(x) Richard is a king ⇒ Richard is a person
true true
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
∀x King(x) ⇒ Person(x) Richard is a king ⇒ Richard is a person
false
true true
True
True
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
John is a king ⇒ John is a person false
Richard’s left leg is a king ⇒ Richard’s left leg is
false
True True
True
false
True! True
True
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) Richard is a king ⇒ Richard is a person
false
true true
John is a king ⇒ John is a person false
Richard’s left leg is a king ⇒ Richard’s left leg is
false
True True
True
false
Universal Quantification
• Syntax: ∀x φ
• Semantics: φ is true for every object x
• Extended interpretation maps every variable to an object in the domain
• ∀xφistrueifφistrueinevery 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)
∀x King(x) ∧ Person(x)
Richard is a king ∧ Richard is a person
John is a king ∧ John is a person
False!
False True
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
False the crown is a king ∧ the crown is a person False
False
Rule: ∀x King(x) ⇒ Person(x)
Probably false statement:
∀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φistrueifφistrueinsome 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φistrueifφistrueinsome 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
∀x Person(x) ⇒ ∃y Person(y) ∧ Loves(x,y)
Someone is loved by everyone
∃x Person(x) ∧ ∀y Person(y) ⇒ Loves(y,x)
Nested Quantifiers Everyone (every person) loves someone
∀x Person(x) ⇒ ∃y Person(y) ∧ Loves(x,y) Someone is loved by everyone
∃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β:α⊨β
• Everymodelofαisalsoamodelofβ
• Whenever α is true, so is β
• β is true in every world consistent with α
• Models(α) ⊆ Models(β) • β logically follows from α
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
• #ofobjectsintheworldfrom1to∞
• 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(⋅,⋅)
Constant symbols: { R, J } Relation symbol: P(⋅,⋅)
ΩI = { ●1 } I(R) = ●1
I(J) = ●1 I(P) = { }
RJ
1
Constant symbols: { R, J } Relation symbol: P(⋅,⋅)
ΩI = { ●1 }
I(R) = ●1
I(J) = ●1
I(P) = { ⟨●1,●1⟩}
RJ
1
Constant symbols: { R, J } Relation symbol: P(⋅,⋅)
ΩI = { ●1 }
1 interpretation of R and J 2 interpretations of P
2 possible interpretations
Constant symbols: { R, J } Relation symbol: P(⋅,⋅)
ΩI = { ●1, ●2 } I(R) = ●1
I(J) = ●2
I(P) = …
RJ
1
2
22=4 interpretations of R and J 222=16 interpretations of P
64 possible interpretations
Constant symbols: { R, J } Relation symbol: P(⋅,⋅)
ΩI = { ●1, ●2, ●3 } I(R) = ●1
I(J) = ●2
I(P) = …
RJ
3
1
2
32=9 interpretations of R and J 232=29=512 interpretations of P 4608 possible interpretations
Constant symbols: { R, J } Relation symbol: P(⋅,⋅)
ΩI = { ●1, ●2, ●3, ●4 } I(R) = ●1
I(J) = ●2
I(P) = …
RJ
3
1
2
4
1,048,576 possible interpretations
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
• proving
• Can’t do model checking
• Look for inference rules, do theorem
For next time: AIMA Ch 9