程序代写代做代考 chain CSC242: Introduction to Artificial Intelligence

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