EECS 3401 — AI and Logic Prog. — Lecture 2
Adapted from slides of Prof. Yves Lesperance
Vitaliy Batusov
vbatusov@cse.yorku.ca
York University
September 16, 2020
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 1 / 32
EECS 3401
Required reading: Russell & Norvig, Chapter 8 Optional reading: same, Chapter 7
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 2 / 32
Knowledge Representation
Example: understanding a children’s story How do we test understanding?
For one, the subject must be able to answer (correctly) simple questions about the story.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 3 / 32
Example: Three Little Pigs
Figure: Pigs build houses using different techniques
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 4 / 32
Example: Three Little Pigs
Figure: Wolf huffs and puffs
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 5 / 32
Example: Three Little Pigs
Why couldn’t the wolf blow down the house made of bricks?
What background knowledge are we drawing on to reach that conclusion?
Brick structures are stronger than straw and stick structures
Objects such as the wolf have physical limitations. The wolf can only blow so hard.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 6 / 32
Knowledge Representation
Operating in our world requires vast amounts of knowledge Also requires reasoning with that knowledge
It is doubtful any one of us has studied the blowing ability of wolfs But by knowing the general rules of our world, we can derive this We employ reasoning to make conclusions about the wolf
Generally, reasoning effectively compresses knowledge so we don’t need to store it as such. Without reasoning, we’d need to store unimaginably many trivial facts.
Things that can’t fit into a teacup: elephants, cars, bricks, shoes, whole coconuts, large dogs, small dogs, etc.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 7 / 32
Logical Representations
AI typically employs logical representations of knowledge
They are mathematically precise, so amenable to analysis (properties, computational complexity of inference, etc.)
They are formal languages, so can be mechanically manipulated They have a formal syntax and a formal semantics
They usually have well-developed proof theories — formal procedures for reasoning (deriving new statements from the old)
They are generally declarative, easy to extend
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 8 / 32
Model-Theoretic Semantics
Suppose our knowledge is represented by some collection of strings (sentences)
Generally, what is the meaning of a sentence?
A mapping: {set of sentences} → {features of the world}
Want to provide an interpretation of every piece of our representation
Like having an intuitive understanding of what individual statements in a program mean. If you know what the separate instructions mean, can figure out what the whole program does.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 9 / 32
Model-Theoretic Semantics
Model-theoretic semantics
is a formal characterization (in terms of set theory)
can be used to prove a wide range of properties of the representation
maps arbitrarily complex sentences of the language (logic) down into intuitive assertions about the real world
is based on notions that are very close to how we think about the real world. Thus, it provides a bridge from the syntax to an intuitive understanding of what is being asserted
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 10 / 32
Model-Theoretic Semantics
Representation
Model-Theoretic Semantics
direct map difficult
Agent’s Environment
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 11 / 32
Semantics: formal details
A set of objects
Stand for distinct identifiable objects that are important for your application
Distinguished subsets of objects — Properties Distinguished sets of tuples of objects — Relations
Distinguished functions mapping tuples of objects to objects —
Functions
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 12 / 32
Example
Try viewing the world in the terms of set theory
Objects:
students, subjects, assignments, numbers
Predicates:
difficult(subject), cs major(student)
Relations
handed in(student,assignment)
Functions:
grade(student, assignment) → number
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 13 / 32
First-Order Logic (FOL)
Syntax A grammar specifying what are the legal syntactic constructs of the representation
Semantics A formal mapping from syntactic constructs to set-theoretic assertions
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 14 / 32
FOL Syntax
Symbol = a unique artifact, no matter what it is.
Example: Unicode symbols, digits, emojis, whatever — but needs to be distinguishable from other symbols. Contrary to common usage, and for the purposes of convenience, we consider a string of characters to be a single symbol.
We will need symbols to represent:
constants variables functions1 predicates1
1These are associated with an arity, the number of arguments
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 15 / 32
FOL Syntax: building terms
A term is either a variable
a constant
an expression f(t1,…,tk) where
f is a function symbol
k is its arity
ti (for1≤i≤k)isaterm2
Think: term = expression that denotes an object
Example: if our objects are numbers, then 1 + 2 is a term that denotes 3
2notice induction
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 16 / 32
FOL Syntax: atomic formulas
An atom (or atomic formula) is an expression p(t1, . . . , tk ) where p is a predicate symbol
k is its arity
ti (1≤i≤k)isaterm
Note: constants are functions without arguments
Notation: we will use UPPER CASE for variables, lower case for everything else. (This is what Prolog does, let’s stay consistent with it)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 17 / 32
Semantic Intuition — Terms
Terms denote objects (individuals) Constants denote specific objects
bill, jane
Variables range over individuals
X — could be jane or bill or any other object in our universe Functions map tuples of objects to other objects
father(jane), mother(father(jane)), mother(X), distance between(X,Y)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 18 / 32
Semantic Intuition — Formulas
Atoms denote facts about the world (can only be true or false) father of(bill,jane) — “Bill is the father of Jane”
female (jane )
satisfied (client 15)
satisfied (C )
desires(client15, rome, week29) desires(X,Y,Z)
star rating(hotel7,4)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 19 / 32
FOL Syntax — Formulas (I)
Atoms are formulas (“atomic formulas”)
If φ is a formula, then its negation ¬φ is also a formula
¬φ is true whenever φ is false
If φ1,…,φn are formulas, then their conjunction φ1 ∧φ2 ∧…∧φn is also a formula
φ1 ∧φ2 ∧…∧φn is true whenever every φi (1 ≤ i ≤ n) is true
If φ1,…,φn are formulas, then their disjunction φ1 ∨φ2 ∨…∨φn is also a formula
φ1 ∨φ2 ∨…∨φn is true whenever at least one of φi (1 ≤ i ≤ n) is true
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 20 / 32
FOL Syntax — Formulas (II)
Recall:
∃ Existential quantifier — “There exists. . . ” ∀ Universal quantifier — “For all. . . ”
If φ is a formula, then ∃X(φ) is also a formula
Asserts that there is an object such that, if X is bound to it, φ becomes true
If φ is a formula, then ∀X(φ) is also a formula Asserts that φ is true for every single binding of X
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 21 / 32
FOL Syntax — Some useful abbreviations
Implication — “if …then …”
φ1 → φ2 means ¬φ1 ∨ φ2
Double (bi-directional) implication — “if and only if”
φ1 ↔φ2 means(φ1 →φ2)∧(φ2 →φ1)
Standard rules for connective precedence apply, i.e. φ1 ∧φ2 ∨φ3 is (φ1 ∧φ2)∨φ3
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 22 / 32
FOL Semantics
Formulas ban be built up recursively, can be arbitrarily complex Syntactically distinct formulas may be logically equivalent
∀X,Y(elephant(X)∧teacup(Y)→larger than(X,Y)) ∀X,Y(teacup(Y)∧elephant(X)→larger than(X,Y))
The purpose of semantics is to capture this equivalence and, more generally, to make sense of complex formulas
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 23 / 32
FOL Semantics
Semantics = a formal mapping from formulas to semantic entities (individuals, sets, relations and functions over individuals)
meaning : {formulas} → {set-theoretic notions}
This mapping mirrors the recursive nature of the syntax. Thus, we can give any formula (no matter how complex) a mapping to semantic entities
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 24 / 32
FOL Semantics — Formal Definition
First, we fix the language. The language L is defined by its primitive symbols: the sets F, P, V
F — a set of function symbols (inc. constants) Each symbol f ∈ F has a particular arity
P — a set of predicate and relation symbols Each symbol p ∈ P has a particular arity
V — an infinite set of variables
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 25 / 32
FOL Semantics — Formal Definition
An interpretation (structure) is a tuple ⟨D, Φ, Ψ, ν⟩, where D is a non-empty set (domain of individuals)
“universe of discourse”
Φ:F →(Dk →D)
maps every k-ary function symbol f ∈ F to a k-ary function over D
Careful: f is a symbol, Φ(f ) is the corresponding function over the domain
Ψ : P → (Dk → {true, false})
maps every k-ary predicate symbol p ∈ P to an indicator function over k-ary tuples of individuals
ν : V → D is a variable assignment function. Simply maps every variable to some domain object.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 26 / 32
Intuitions
The domain D is just a set:
craig
cat jane
100 grandhotel
(Underlined symbols denote domain individuals to avoid confusion. They are not symbols of the language)
Domains are usually infinite, but let’s use finite ones to prime our intuitions
portofino rome
7
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 27 / 32
Intuitions for Φ
Recall: Φ:F →(Dk →D)
Given a k-ary function f ∈ F and k individuals, Φ(f ) tells us what f(d1,…,dk) is.
0-ary functions (constants) are mapped to specific individuals in D Φ(client17) = craig, Φ(rome) = rome
1-ary functions are mapped to functions in D → D Φ(min quality ) = fmin quality , fmin quality (craig ) = 3 stars
2-ary functions are mapped to functions in D2 → D Φ(distance) = fdistance , fdistance (toronto, sienna) = 3256
And so on for n-ary functions
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 28 / 32
Intuitions for Ψ
Recall: Ψ : P → (Dk → {true, false})
Given a k-ary predicate p ∈ P and k individuals, Ψ(p) tells us whether the relation denoted by p holds for these particular individuals.
0-ary predicates are mapped to true or false
Ψ(rainy) = True, Ψ(sunny) = False
Unary predicates are mapped to indicator functions of subsets of D
Ψ(satisfied ) = psatisfied , psatisfied (craig ) = True
Binary predicates are mapped to indicator functions of subsets of D2 Ψ(location) = plocation, plocation(grandhotel, rome) = True, plocation(grandhotel,sienna) = False
And so on for n-ary predicates
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 29 / 32
Intuitions for ν
Only takes care of quantification. The exact mapping it specifies does not really matter, as we will see later.
Notation: ν[X/d] is a new variable assignment function, which is exactly just like ν except that it maps the variable X to the individual d. Otherwise, ν(Y) = ν[X/d](Y).
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 30 / 32
FOL Semantics
GIven a language L and an interpretation I = ⟨D, Φ, Ψ, ν⟩, Constant c denotes an individual
I(c) = Φ(c) ∈ D
Variable X denotes an individual
I(X) = ν(X) ∈ D
A complex term t = f (t1, . . . , tk ) denotes an individual
I(t) = Φ(f)(I(t1),…,I(tk)) ∈ D
We recursively find the denotation of each term and then apply the function denoted by f to get the individual.
Thus, terms always denote individuals under an interpretation I
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 31 / 32
End of lecture
Next time: FOL Semantics continued, examples of interpretations
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 2 September 16, 2020 32 / 32