EECS 3401 — AI and Logic Prog. — Lecture 3
Adapted from slides of Prof. Yves Lesperance
Vitaliy Batusov
vbatusov@cse.yorku.ca
York University
September 21, 2020
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 1 / 58
EECS 3401
Continued from Lecture 2
Required reading: Russell & Norvig, Chapter 8 Optional reading: same, Chapter 7
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 2 / 58
Recap
We want to represent knowledge
We are using First-Order Logic (FOL)
FOL consists of Syntax and Semantics
Syntax — how to form sentences
a formal grammar
Semantics — how to give sentences meaning
map syntactic constructs to set-theoretic constructs
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 3 / 58
FOL Syntax
We will need symbols to represent
constants variables functions predicates
a, b, cat, client17 X , Y , Parent
weight(·), sum(·, ·, ·), common parent(·, ·) heavy(·), siblings(·,·,·), greater than(·,·)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 4 / 58
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)isaterm1
Think: term = expression that denotes an object
1notice induction
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 5 / 58
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
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 6 / 58
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 3 September 21, 2020 7 / 58
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 3 September 21, 2020 8 / 58
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 3 September 21, 2020 9 / 58
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 3 September 21, 2020 10 / 58
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 3 September 21, 2020 11 / 58
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 3 September 21, 2020 12 / 58
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 3 September 21, 2020 13 / 58
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 3 September 21, 2020 14 / 58
Symbols, Terms, and Notation
Given a language L and an interpretation I = ⟨D, Φ, Ψ, ν⟩, c is a constant symbol and also a term,
but I(c) is an object in D
X is a variable symbol and also a term,
but I(X) is an object in D
f(·,·) is a function symbol, f(c,X) is a term,
but I(f(c,X)) is an object in D
p(·,·) is a predicate symbol, p(c,X) is an atom,
but I(p(c,X)) is either True or False Can also write I(c) as cI — looks less cumbersome
So, c is a term, but cI is the object it refers to according to I
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 15 / 58
FOL Semantics — Interpreting Terms
Given a language L and an interpretation I = ⟨D, Φ, Ψ, ν⟩, Constant c denotes an individual
cI =Φ(c)∈D Variable X denotes an individual
XI =ν(X)∈D
A complex term f (t1 , . . . , tk ) denotes an individual
(f(t1,…,tk))I = Φ(f)(t1I,…,tkI) ∈ 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 3 September 21, 2020 16 / 58
FOL Semantics — Interpreting Formulas
Given a language L and an interpretation I = ⟨D, Φ, Ψ, ν⟩, An atom p(t1,…,tk) has the truth value
(p(t1,…,tk))I = Ψ(p)(t1I,…,tkI) ∈ {True,False}
A more intuitive way:
For each k-ary predicate symbol p, I supplies a set pI ⊆ Dk, i.e., some set of k-tuples over D. Then, if the tuple of individuals (t1I,…,tkI) is in this set pI, then the atom is true in I.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 17 / 58
FOL Semantics — Interpreting Complex Formulas
(¬φ)I is True if and only if φI is False
(φ1∧…∧φn)I isTrueifeveryφIi (1≤i≤n)isTrue,andFalse
otherwise
(φ1∨…∨φn)I isTrueifatleastoneofφIi (1≤i≤n)isTrue.If
all are false, then the conjunction is False.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 18 / 58
FOL Semantics — Formulas with Quantifiers
(∃X(φ))I is True if
there exists an object d ∈ D
such that φI′ is True,
where I′ = ⟨D,Φ,Ψ,ν[X/d]⟩
I′ is exactly like I except its variable assignment ν maps the variable X to that special d ∈ D
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 19 / 58
FOL Semantics — Formulas with Quantifiers
(∀X(φ))I is True if
for every object d ∈ D,
φI′ is True,
where I′ = ⟨D,Φ,Ψ,ν[X/d]⟩
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 20 / 58
Example
Consider the statement
∀X(happy(X)) “everybody is happy”
Is this a true statement in the following interpretation I?
I: D={bob,jack,fred} Ψ(happy)(bob) = True Ψ(happy)(jack) = True Ψ(happy)(fred) = False
Test happy(X) under all I′ = ⟨D,Φ,Ψ,ν[X/d]⟩, d ∈ D
for ν[X/bob] : for ν[X/jack] : for ν[X/fred] :
(happy(X))I′ = Ψ(happy)(bob) = True (happy(X))I′ = Ψ(happy)(jack) = True (happy(X))I′ = Ψ(happy)(fred) = False
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU)
EECS 3401 Lecture 3 September 21, 2020 21 / 58
Example — Blocks World
Environment
Language
Constants a, b, c, e Functions none
Predicates on(·, ·) above(·, ·)
clear (·) ontable (·)
B
A
C
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU)
EECS 3401 Lecture 3 September 21, 2020 22 / 58
E
Example — Blocks World
Language
Constants a, b, c, e
A possible interpretation I1 D = {A,B,C,E}
Φ(a) = A, Φ(b) = B, Φ(c) = C, Φ(e) = E
Ψ(on) = {(A,B),(B,C)}, Ψ(above) = {(A,B),(B,C),(A,C)}, Ψ(clear) = {A,E}, Ψ(ontable) = {C,E}
Predicates
on(·, ·) above(·, ·) clear (·) ontable (·)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU)
EECS 3401 Lecture 3
September 21, 2020
23 / 58
Example — Blocks World
Environment
A possible interpretation I1 D = {A,B,C,E}
Φ(a) = A, Φ(b) = B, Φ(c) = C, Φ(e) = E
Ψ(on) = {(A,B),(B,C)}, Ψ(above) = {(A,B),(B,C),(A,C)}, Ψ(clear) = {A,E}, Ψ(ontable) = {C,E}
B
A
C
E
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU)
EECS 3401 Lecture 3
September 21, 2020 24 / 58
Example — Blocks World
Interpretation I1 D = {A,B,C,E}
Φ(a) = A, Φ(b) = B, Φ(c) = C, Φ(e) = E
Ψ(on) = {(A,B),(B,C)}, Ψ(above) = {(A,B),(B,C),(A,C)}, Ψ(clear) = {A,E}, Ψ(ontable) = {C,E}
Let’s see what holds in I1 ∀X∀Y(on(X,Y) → above(X,Y))
checkX =A,Y =B —ok check X = B,Y = C — ok
∀X∀Y(above(X,Y) → on(X,Y))
checkX =A,Y =B —ok check X = B,Y = C — ok check X = A, Y = C
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU)
EECS 3401 Lecture 3
September 21, 2020 25 / 58
Example — Blocks World
Interpretation I1 D = {A,B,C,E}
Φ(a) = A, Φ(b) = B, Φ(c) = C, Φ(e) = E
Ψ(on) = {(A,B),(B,C)}, Ψ(above) = {(A,B),(B,C),(A,C)}, Ψ(clear) = {A,E}, Ψ(ontable) = {C,E}
∀X∃Y(clear(X)∨on(Y,X))
checkX =A—ok
check X = C , Y = B — ok …
∃Y∀X(clear(X)∨on(Y,X))
check Y = A – no! (X = C) check Y = C– no! (X = B) checkY =E –no! (X =B) checkY =B–no! (X =B)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU)
EECS 3401 Lecture 3
September 21, 2020 26 / 58
Knowledge Bases and Their Models
KB:
on(b,c) clear(e)
Various models:
A
B
B
A
C
E
B
C
E
C
E
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 27 / 58
Models
A formula φ may be true or false in a given interpretation I IfaformulaφistrueinI,wesaythatI isamodelofφ
Written: I |= φ (I satisfies φ)
A knowledge base (KB) is a set of formulas (axioms)
If I |= φ for every φ ∈ KB, then I |= KB “I is a model of the knowledge base”
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 28 / 58
The Purpose of Models
When we create a knowledge base (a set of logical axioms), we intend that the real world (i.e., our set-theoretic abstraction of it) is one of its models
If it is, then every statement in the KB is true in the real world
Thus, when reasoning in the KB, we can derive true statements about the real world
Note: not every thing that is true in reality need be contained in the KB. KB’s are typically incomplete in this sense.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 29 / 58
Models Support Reasoning
Suppose some formula φ is not a part of our KB, but is nevertheless true in every model of the KB, i.e.,
for every I such that I |= KB, we also get I |= φ
We say that φ is a logical consequence of the KB (“KB entails φ”)
Since the real world is a model of the KB, then φ must be true in the real world
Thus, entailment is a way of finding new true facts that were not mentioned in the KB
Ponder: if the KB does not entail φ, does it mean that φ is false?
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 30 / 58
Example of Entailment
elephant (clyde )
The individual denoted by the symbol clyde is in the set denoted by the symbol elephant
teacup(cup) cup is a teacup
A unary predicate p always denotes (is interpreted as) a set pI of individuals. Asserting a unary predicate to hold for a term t means that the individual tI denoted by that term belongs to the set pI. Formally, we defined pI to be an indicator function. Seen in the above sense, the indicator function returns true or false depending on whether the individual is in the set pI.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 31 / 58
Example of Entailment
∀X∀Y(elephant(X)∧teacup(Y)→larger than(X,Y))
For every pair of individuals: if the first is an elephant and the second is a teacup, then the pair of objects are related to each other by the larger than relation.
For pairs of individuals who are not elephants and teacups, the formula is immediately true.
Recall: A → B stands for ¬A∨B
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 32 / 58
Example of Entailment
∀X∀Y(larger than(X,Y) → ¬fits in(X,Y))
For every pair of individuals: if X is larger than Y (the pair is in the larger than relation), then we cannot have that X fits inside Y (the pair cannot be in the fits in relation)
(The intersection of the relations larger than and fits in is the empty set)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 33 / 58
Example of Entailment
D×D
fits in
¬fits in
larger than
elephant × teacup ⟨clyde, cup⟩
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 34 / 58
Example of Entailment
If an interpretation satisfies the KB, then the set of pairs
elephant × teacup must be a subset of larger than, which is disjoint from fits in
Therefore, ⟨clyde,cup⟩ must be in the complement of the set fits in Therefore, ¬fits in(clyde,cup) must be true in every model of the KB Therefore,
¬fits in(clyde,cup)
is a logical consequence of the above assertions.
New knowledge!
Well, not technically new. This statement does not appear explicitly in the KB, but it is contained in (is entailed by) the statements that do
In the same sense, Euclid’s axioms contain the Pythagoras’ Theorem
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 35 / 58
Interpretations and Models
The more sentences in the KB, the fewer models (satisfying interpretations) there are
The more axioms you write down, the “closer” you get to the “real world”, because each sentence in the KB rules out certain unintended or unwanted models
This is called axiomatizing the domain
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 36 / 58
Knowledge Representation
Knowledge Representation is the area of AI that focuses on how to represent information about an application domain
An important aspect is specifying the concepts and relations of interest and how they relate — the domain’s ontology
Many large ontologies have been created
Cyc General-purpose ontology, more than 1 millon terms
DBpedia represents the content of Wikipedia in a formal language SNOMED CT medical terms
KR is the basis of the Semantic Web, which seeks to make information on the web machine-processable
Important application is ontology-based data access Tools for building ontologies (Prot ́eg ́e)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 37 / 58
Knowledge Representation Formalisms
Many formal languages for representing information
FOL is quite expressive, but checking entailment in FOL is undecidable in general
Description logics are decidable fragments of FOL for KR and reasoning. Concepts are organized in a hierarchy
OWL (Web Ontology Language) is a family of description logics standardized by the W3C
Reasoners have been developed for such formalisms (RACER, FACT++)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 38 / 58
End of lecture
Next time: Logic programming and Prolog
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 3 September 21, 2020 39 / 58