CPSC 312 — Functional and Logic Programming
Daylight saving starts this weekend (clocks change) Assignment 5 is available
A solution to Assignment 4 is posted.
What is now required is to give the greatest possible development to mathematical logic, to allow to the full the importance of relations, and then to found upon this secure basis a new philosophical logic, which may hope to borrow some of the exactitude and certainty of its mathematical foundation. If this can be successfully accomplished, there is every reason to hope that the near future will be as great an epoch in pure philosophy as the immediate past has been in the principles of mathematics. Great triumphs inspire great hopes; and pure thought may achieve, within our generation, such results as will place our time, in this respect, on a level with the greatest age of Greece.
– Bertrand Russell, Mysticism and Logic and Other Essays [1917]
CPSC 312 — Lecture 22 1 / 26
©D. Poole 2021
Since the midterm…
Done:
Syntax and semantics of propositional definite clauses
Model a simple domain using propositional definite clauses
Bottom-up proof procedure computes a consequence set using modus ponens.
Top-down proof procedure answers a query using resolution. The box model provides a way to procedurally understand the
top-down proof procedure with depth-first search.
CPSC 312 — Lecture 22 2 / 26
©D. Poole 2021
Clicker Question
In the top-down proof procedure, answer clause
yes :- happy, green, good.
can be resolved with which clause(s) in a KB (i) green :- good.
(ii) good.
(iii) sleepy :- green.
(iv) good :- nice, green.
(v) good :- happy, green. Click on:
A (i), (ii), (iv) and (v) only
B all of the clauses
C (v) only
D none of the clauses, and so the proof fails E A-D are all incorrect
©D. Poole 2021
CPSC 312 — Lecture 22 3 / 26
Clicker Question
Given Box diagram for a
call
b
fail c d
exit
retry
which of the following is not true
A a :- b must be a clause in the knowledge base B c is called when b fails
C a exits when b exits
D a fails when c fails
E one of the above is false.
©D. Poole 2021
CPSC 312 — Lecture 22 4 / 26
Today
Relations and individuals, logical variables, Datalog
CPSC 312 — Lecture 22 5 / 26
©D. Poole 2021
Syntax of Datalog
A variable starts with upper-case letter or with underscore (’ ’)
A constant is a sequence of letters, digits or underscore (’ ’) and starts with lower-case letter
or is a sequence of digits (numeral)
or is any sequence of characters between single quotes.
A predicate symbol starts with lower-case letter. A term is either a variable or a constant.
An atomic symbol (atom) is of the form p or p(t1, . . . , tn) where p is a predicate symbol and ti are terms.
CPSC 312 — Lecture 22 6 / 26
©D. Poole 2021
Syntax of Datalog (cont)
A definite clause is either
— an atomic symbol (a fact) or — a rule of the form:
a :-b1,···,bm
head body
where a and bi are atomic symbols.
[A fact is treated as a rule with an empty body (m=0).]
A knowledge base is a set of definite clauses. A query is of the form ?b1, ···, bm.
CPSC 312 — Lecture 22 7 / 26
©D. Poole 2021
Clicker Question
For the program
hghg(Xyz,hhd) :-
bbfj(Xyz,gfgf,Haa),
hhhh(Haa, ggg).
Which of the following is not true of this program. A Xyz is a variable
B hghg is a constant
C ggg is a constant
D Haa is a variable
E hhhh is a predicate symbol
©D. Poole 2021
CPSC 312 — Lecture 22 8 / 26
Semantics: General Idea
A semantics specifies the meaning of sentences in the language. An interpretation specifies:
what objects (individuals) are in the world
the correspondence between symbols in the computer and objects and relations in world
constants denote individuals
predicate symbols denote relations
CPSC 312 — Lecture 22 9 / 26
©D. Poole 2021
Formal Semantics
An interpretation is a triple I = ⟨D, φ, π⟩, where
D, the domain, is a nonempty set. Elements of D are
individuals.
φ is a mapping that assigns to each constant an element of D. Constant c denotes individual φ(c).
π is a mapping that assigns to each n-ary predicate symbol a relation: a function from D n into {TRUE, FALSE}.
CPSC 312 — Lecture 22 10 / 26
©D. Poole 2021
Example Interpretation
Constants: phone, pencil, telephone.
Predicate Symbol: noisy (unary), left of (binary).
D = {,,}.
φ(phone) = , φ(pencil) = , φ(telephone) = .
π(noisy ): π(left of ): ⟨, ⟩
⟨, ⟩ ⟨, ⟩
FALSE ⟨⟩ TRUE
FALSE
TRUE TRUE FALSE
⟨⟩ FALSE
FALSE FALSE
⟨⟩ TRUE ⟨, ⟩
FALSE ⟨, ⟩ FALSE ⟨, ⟩
⟨, ⟩ ⟨, ⟩ ⟨, ⟩
CPSC 312 — Lecture 22
11 / 26
©D. Poole 2021
Important points to note
The domain D can contain real things (entities, objects). (e.g., a person, a room, a course). D can’t necessarily be stored in a computer.
π(p) specifies whether the relation denoted by the n-ary predicate symbol p is true or false for each n-tuple of individuals.
If predicate symbol p has no arguments, then π(p) is either TRUE or FALSE.
CPSC 312 — Lecture 22 12 / 26
©D. Poole 2021
Truth in an interpretation
A constant c denotes in I the individual φ(c). Ground (variable-free) atom p(t1, . . . , tn) is
true in interpretation I if π(p)(⟨φ(t1), . . . , φ(tn)⟩) = TRUE in interpretation I and
false otherwise.
Ground clause h :- b1, . . . , bm is false in interpretation I if hisfalseinI andeachbi istrueinI,andistruein interpretation I otherwise.
CPSC 312 — Lecture 22 13 / 26
©D. Poole 2021
Example Truths
In the interpretation given before, is the following true or false?
A true
B false
C I’m not sure
noisy (phone )
noisy (telephone )
noisy (pencil )
left of(phone,pencil)
left of (phone, telephone)
noisy(phone) :- left of(phone,telephone) true noisy(pencil) :- left of(phone,telephone) true noisy(pencil) :- left of(phone,pencil) false noisy(phone) :- noisy(telephone), noisy(pencil) true
true true false true false
©D. Poole 2021
CPSC 312 — Lecture 22 14 / 26
Models and logical consequences (recall)
A knowledge base, KB, is true in interpretation I if and only if every clause in KB is true in I.
A model of a set of clauses is an interpretation in which all the clauses are true.
If KB is a set of clauses and g is a conjunction of atoms, g is a logical consequence of KB, written KB |= g, if g is true in every model of KB.
That is, KB |= g if there is no interpretation in which KB is true and g is false.
CPSC 312 — Lecture 22 15 / 26
©D. Poole 2021
User’s view of Semantics
1. Choose a task domain: intended interpretation.
2. Associate constants with individuals you want to name.
3. For each relation you want to represent, associate a predicate symbol in the language.
4. Tell the system clauses that are true in the intended interpretation: axiomatizing the domain.
5. Ask questions about the intended interpretation.
6. If KB |= g, then g must be true in the intended interpretation.
The computer doesn’t know the intended interpretation and meaning of symbols, but it is important to convey the intended interpretation in comments for other people and for you in the future.
When we say “give the intended interpretation” means specify in comments what objects exist and the mappings of steps 2 and 3.
©D. Poole 2021
CPSC 312 — Lecture 22 16 / 26
Computer’s view of semantics
The computer doesn’t have access to the intended interpretation.
All it knows is the knowledge base.
The computer can determine if a formula is a logical consequence of KB.
If KB |= g then g must be true in the intended interpretation. If KB ̸|= g then there is a model of KB in which g is false.
This could be the intended interpretation.
CPSC 312 — Lecture 22 17 / 26
©D. Poole 2021
Role of Semantics
in(kim,r123). part_of(r123,cs_building). in(X,Y) ←
kim r123 r023
part_of(Z,Y) ∧ in(X,Z).
cs_building
in( , ) part_of( , ) person( )
in(kim,cs_building) ©D. Poole 2021
CPSC 312 — Lecture 22 18 / 26
Variables
Variables are universally quantified in the scope of a clause. A variable assignment is a function from variables into the
domain.
Universal quantification means the clause is true for all variable assignments.
Given an interpretation and a variable assignment, each term denotes an individual and
each clause is either true or false.
CPSC 312 — Lecture 22 19 / 26
©D. Poole 2021
Queries and Answers
A query is a way to ask if a body is a logical consequence of the knowledge base:
?b1, ···, bm. An answer is either
an instance of the query that is a logical consequence of the knowledge base KB, or
no (or false) if no instance is a logical consequence of KB.
CPSC 312 — Lecture 22 20 / 26
©D. Poole 2021
Example Queries (simpvar.pl)
in(kim,r123).
KB = in(X,Y) :- part of(Z,Y), in(X,Z).
part of(r123,cs building).
Query Answer
?part of (r 123, B ). part of (r 123, cs building ) ?part of(r023,cs building). no
?in(kim, r 023). no
?in(kim, B ). in(kim, r 123)
in(kim,cs building)
©D. Poole 2021
CPSC 312 — Lecture 22 21 / 26
Electrical Environment
cb1
w5
outside power
circuit breaker
off
on switch
two-way switch
light
power outlet
s1
cb2
s2 w1 w2
s3
w3
w6
p2
p1
w0
w4
l1
l2
©D. Poole 2021
CPSC 312 — Lecture 22 22 / 26
Axiomatizing the Electrical Environment (elect reln.pl)
% light(L) is true if L is a light
light (l1 ). light (l2 ).
% down(S) is true if switch S is down down(s1). up(s2). up(s3).
% ok(D) is true if D is not broken ok(l1). ok(l2). ok(cb1). ok(cb2).
?light (l1 ). =⇒ yes ?light (l6 ). =⇒ no
?up(X).
=⇒ up(s2), up(s3)
©D. Poole 2021
CPSC 312 — Lecture 22 23 / 26
% connected to(X , Y ) is true if component X is connected to Y
% so electricity
connected connected connected connected connected connected
will flow from Y to X to(w0, w1) ← up(s2).
to(w0, w2) ← down(s2). to(w1, w3) ← up(s1). to(w2, w3) ← down(s1). to(w4, w3) ← up(s3). to(p1, w3).
?connected to(w0, W ). =⇒ ?connected to(w1, W ). =⇒ ?connected to(Y,w3). =⇒ ?connected to(X,W). =⇒
W = w1
no
Y = w2, Y = w4, Y = p1 X = w0,W = w1, …
©D. Poole 2021
CPSC 312 — Lecture 22 24 / 26
% lit(L) is true if the light L is lit lit(L) ← light(L), ok(L), live(L).
% live(C) is true if there is power coming into C live(Y) ←
connected to(Y,Z),
live(Z). live (outside ).
This is a recursive definition of live.
©D. Poole 2021
CPSC 312 — Lecture 22 25 / 26
Recursion and Mathematical Induction
above(X,Y) :- on(X,Y).
above(X,Y) :- on(X,Z), above(Z,Y). This can be seen as:
Recursive definition of above: prove above in terms of a base case (on) or a simpler instance of itself; or
Way to prove above by mathematical induction: the base case is when there are no blocks between X and Y , and if you can prove above when there are n blocks between them, you can prove it when there are n + 1 blocks.
CPSC 312 — Lecture 22 26 / 26
©D. Poole 2021