CPSC 312 — Functional and Logic Programming
Assignment 5 is available
Midterm #3 next week — more details on web site soon
“Contrariwise,” continued Tweedledee, “if it was so, it might be; and if it were so, it would be; but as it isn’t, it ain’t. That’s logic.”
– Lewis Carroll, Through the Looking-Glass
CPSC 312 — Lecture 23 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.
Syntax of Datalog: Predicate symbols, constants, variables, queries.
Semantics of Datalog: Interpretations, variable assignments, models, logical consequence.
CPSC 312 — Lecture 23 2 / 26
©D. Poole 2021
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 23 3 / 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 23 4 / 26
©D. Poole 2021
Clicker Question
Suppose we have an interpretation I with domain D = {, , , v, }.
and φ(c) = v and φ(d) = v.
Which of the following is not true:
A Every statement that is true about d is true about c.
B c and d refer to two things with the same name
C There is one individual with two different names
D c could be replaced by d in all clauses and the same clauses would be true in I
©D. Poole 2021
CPSC 312 — Lecture 23 5 / 26
Clicker Question
Given a knowledge base KB, if an answer that is false in the intended interpretation is returned (given a sound and complete proof procedure). Which of the following is true
A One of the clauses in KB must be false in the intended interpretation
B There are too many irrelevant facts that confused the system
C The intended interpretation is a model of KB.
D None of the above.
©D. Poole 2021
CPSC 312 — Lecture 23 6 / 26
Clicker Question
Given a knowledge base KB, if g is true in the intended interpretation, and g is not given as an answer (assuming a sound and complete proof procedure that halts), which of the following is true
A One of the clauses in KB must be false in the intended interpretation
B g is false in another model of KB
C The intended interpretation is not a model of KB
D All of the above
E None of the above.
©D. Poole 2021
CPSC 312 — Lecture 23 7 / 26
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 23 8 / 26
Variables
A variable assignment is a function from variables into the domain.
Given an interpretation and a variable assignment, each term denotes an individual and
each clause is either true or false.
A clause containing variables is true in an interpretation if it is true for all variable assignments.
This means variables are universally quantified in the scope of a clause.
CPSC 312 — Lecture 23 9 / 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 (given by an assignment of values to variables in the query), or
no (or false) if no instance is a logical consequence of KB.
CPSC 312 — Lecture 23 10 / 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,r023). no
?− in(kim,B). in(kim,r123)
in(kim,cs building)
©D. Poole 2021
CPSC 312 — Lecture 23 11 / 26
Anonymous variable
In Prolog, is the anonymous variable.
It is a logical variable where all instances are a different variable.
in queries means we don’t care about the value of a variable
Singleton variables in a clause are often an error. Use instead.
CPSC 312 — Lecture 23 12 / 26
©D. Poole 2021
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 23 13 / 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 23 14 / 26
% connected to(X , Y ) is true if component X is connected to Y % so electricity will flow from Y to X
connected connected connected connected connected connected
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).
?−connectedto(X,W). =⇒ X=w0,W=w1,…
=⇒ W = w1
=⇒ no
=⇒ Y = w2, Y = w4, Y = p1
©D. Poole 2021
CPSC 312 — Lecture 23 15 / 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 23 16 / 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 23 17 / 26
©D. Poole 2021
Function Symbols
Often we want to refer to individuals in terms of components. Examples: 4:55 p.m. English sentences. A classlist.
We extend the notion of term. So that a term can be
a variable
a constant
of form f(t1,…,tn) where f is a function symbol and the ti
are terms.
CPSC 312 — Lecture 23 18 / 26
©D. Poole 2021
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 (specified by φ)
predicate symbols denote relations (specified by π)
in an interpretation and with a variable assignment, term
f(t1,…,tn) denotes an individual in the domain. Also specified by φ (constant is just a special case).
The semantics is otherwise unchanged.
Prolog functions are like Haskell constructors (defined with data in Haskell).
CPSC 312 — Lecture 23 19 / 26
©D. Poole 2021
Example: dates (dates.pl)
Suppose we want to refer to dates, e.g., December 25, 1971 Use ce(Y,M,D) where Y is the year, M is the month and D
is the day of the month. (ce is for “common era”). ce(·) can only be used as part of an atom:
% born(Person,Date) is true if Person was born on Date
born(justin,ce(1971,dec,25)).
born(pierre,ce(1919,oct,18)).
born(ella_mai,ce(1994,nov,3)).
born(shawn_mendez, ce(1998,aug,8)).
Define before(D1,D2) which is true when date D1 is before date D2. (You may use infix predicate < where X < Y is true if X is less than Y).
Add bce(y, m, d) for before common era, e,g,. bce(55, mar, 15) is the ides of March, 55BCE.
Given born(Person, Date) information, write older(P1, P2). CPSC 312 — Lecture 23 20 / 26
©D. Poole 2021
Clicker Question
foo(a,X,X)
A must be an atom
B must be a term
C Prolog cannot tell if it is a term or atom
D Prologcantellifitisatermoranatombywhereit appears in a clause.
©D. Poole 2021
CPSC 312 — Lecture 23 21 / 26
Clicker Question
If foo(a,X,X) appears as foo(a,X,X) :- bar(X).
For an interpretation I
A foo(a,X,X) denotes an individual in I
B foo(a,X,X) is true or false in I
C foo(a,X,X) denotes an individual in I only given a
variable assignment
D foo(a,X,X) is true or false in I only given a variable assignment
©D. Poole 2021
CPSC 312 — Lecture 23 22 / 26
Clicker Question
If foo(a,X,X) appears as noon(foo(a,X,X),17) :- bar(X).
For an interpretation I
A foo(a,X,X) denotes an individual in I
B foo(a,X,X) is true or false in I
C foo(a,X,X) denotes an individual in I only given a
variable assignment
D foo(a,X,X) is true or false in I only given a variable assignment
©D. Poole 2021
CPSC 312 — Lecture 23 23 / 26
Working with terms (myis.pl)
Prolog has a predicate ’is’, so that is(N,E)
usually written N is E
is true when expression E evaluates to number N. E must not contain variables when called.
Prolog has predicate number(N) that is true if N is a number. Define myis(N,E) that is true if arithmetic expression E has
value the number N.
’myis’ can be made into an infix operator by declaring: :- op(700, xfx, myis).
CPSC 312 — Lecture 23 24 / 26
©D. Poole 2021
Lists (mylist.pl)
A list is an ordered sequence of elements. Let’s use
the constant empty to denote the empty list, and
the function cons(H,T) to denote the list with first element H
and rest-of-list T.
These are not built-in.
The list containing jan, feb and mar is
cons(jan, cons(feb, cons(mar, empty))) member(E,L) is true if E is and element of list L.
append(X,Y,Z) is true if list Z contains the elements of list X followed by the elements of list Y .
append(empty,Z,Z). append(cons(A,X),Y,cons(A,Z)) :- append(X,Y,Z).
CPSC 312 — Lecture 23 25 / 26
©D. Poole 2021
Syntactic Sugar for Lists (lists.pl)
The empty list is [ ]
The list with first element H and the rest of the list T is
[H | T].
[···a··· | []] written as [···a···].
[···a··· | [···b···]] written as [···a··· ,···b···].
Examples
member(X,L) is true if X is an element of list L
append(A,B,C) is true if C contains the elements of A followed by the elements of B
numeq(X,L,N) is true if N is the number of instances of X in L.
sum(L,N) is true if N is the sum of the elements of L reverse(L,R) is true if R is the reverse of list L.
CPSC 312 — Lecture 23 26 / 26
©D. Poole 2021