CPSC 312 — Functional and Logic Programming
Project #2 – should be well underway…. Practice exam questions on web page.
“Once you replace negative thoughts with positive ones, you’ll start having positive results.”
Willie Nelson, 2006 in “The Tao of Willie”
CPSC 312 — Lecture 31 1 / 24
©D. Poole 2021
Plan
Since Midterm
difference lists, definite clause grammars and natural language interfaces to databases
computer algebra and calculus
Triples are universal representations of relations, and are the basis for RDF, and knowledge graphs
URIs provide constants that have standard meanings Ontologies define the meaning of symbols used in information systems. These can be big (e.g., SNOMED-CT is a medical ontology of clinical terms that defines over 350,000 concepts in multiple languages). https: //www.snomed.org/snomed-ct/five-step-briefing
You should know what the following mean: RDF, URI, rdf:type, rdfs:subClassOf, rdfs:domain, rdfs:range
Today
Complete Knowledge Assumption and Negation as failure
CPSC 312 — Lecture 31 2 / 24
©D. Poole 2021
Clicker Question
RDF-schema provides a vocabulary for classes and properties. RDF-schema has a syntax for domain and range of a property. schema.org does not use rdfs:domain and rdfs:range. Why?
A The scheme.org designers didn’t know about it even though they used other terminology from RDF-schema
B The scheme.org designers didn’t care about domains and ranges because they just wanted to define a vocabulary.
C schema.org does not define anything, and so does not need domain and ranges
D The scheme.org designers did not want the meaning associated with RDF-schema’s domain and range.
©D. Poole 2021
CPSC 312 — Lecture 31 3 / 24
Limitations
Suppose you had a database using the relation: enrolled (S , C )
which is true when student S is enrolled in course C. Can you define the relation:
empty course(C)
which is true when course C has no students enrolled in it?
Why? or Why not?
empty course(C) doesn’t logically follow from a set of enrolled relation because there are always models where someone is enrolled in a course!
CPSC 312 — Lecture 31 4 / 24
©D. Poole 2021
Complete Knowledge Assumption (CKA)
Often you want to assume that your knowledge is complete. Everything not known to be true is false.
Example: you can state what switches are up and the system can infer that the other switches are down.
Example: assume that a database of TA hours is complete. The definite clause language is monotonic: adding clauses
can’t invalidate a previous conclusion.
Under the complete knowledge assumption, the system is non-monotonic: adding clauses can invalidate a previous conclusion.
The complete knowledge assumption is sometimes called the closed world assumption.
CPSC 312 — Lecture 31 5 / 24
©D. Poole 2021
Completion of a knowledge base
Suppose the rules for atom a are a :- b1.
.
a :- bn.
equivalent logical formula a ← b1 ∨ . . . ∨ bn.
“aistrueifb1 or…orbn”
Under the Complete Knowledge Assumption, if a is true, one
of the bi must be true: a → b1 ∨ . . . ∨ bn.
“a implies b1 or … or bn”
Under the CKA, the clauses for a mean Clark’s completion:
a ↔ b1 ∨ . . . ∨ bn “aistrueifandonlyifb1 or…orbn”
CPSC 312 — Lecture 31 6 / 24
©D. Poole 2021
Clark’s Completion of a KB
Clark’s completion of a knowledge base consists of the completion of every atom.
An atom h with no clauses, has the completion h ↔ false.
“h is false”.
You can interpret negations in the body of clauses.
\+ h
means that h is false under the complete knowledge assumption
This is negation as failure.
CPSC 312 — Lecture 31
7 / 24
©D. Poole 2021
Negation as failure example (naf.pl)
p:-q, \+r. p :- s.
q:- \+s.
r :- \+ t.
t.
s :- w.
©D. Poole 2021
CPSC 312 — Lecture 31 8 / 24
Bottom-up negation as failure interpreter
C := {}; repeat
either
select r ∈ KB such that
ris“h:-b1, …,bm” bi ∈ C for all i, and
h ∈/ C ;
C := C ∪ {h} or
select h such that for every rule “h :- b1, …, bm” ∈ KB either for some bi, \+ bi ∈ C
orsomebi= \+gandg∈C C := C ∪ { \+ h}
until no more selections are possible
©D. Poole 2021
CPSC 312 — Lecture 31 9 / 24
Negation as failure example (naf.pl)
p:-q, \+r. p :- s.
q:- \+s.
r :- \+ t.
t.
s :- w.
©D. Poole 2021
CPSC 312 — Lecture 31 10 / 24
Box Model of Negation-as-failure
\+ a Call
Fail
a
Exit
Retry
©D. Poole 2021
CPSC 312 — Lecture 31 11 / 24
Top-Down negation as failure proof procedure
If the proof for h fails, you can conclude Failure can be defined recursively:
Suppose you have rules for atom h: h :- b1
.
h :- bn
If every body bi fails, h fails.
\+ h.
A body fails if one of the conjuncts in the body fails. Special case: if there are no rules for h then h fails
CPSC 312 — Lecture 31
12 / 24
©D. Poole 2021
Example: default reasoning about resorts (beach.pl)
A resort is on the beach or away from the beach.
A resort is away from the beach unless it says it is on a beach.
away from beach :- \+ on beach.
If we are told the resort is on the beach, we would expect that resort users would have access to the beach.
If they have access to a beach, we would expect them to be able to swim at the beach.
beach access :- on beach, \+ ab beach access.
swim at beach :- beach access, \+ ab swim at beach.
ab swim at beach :- enclosed bay, big city, \+ ab no swim
ab no swim :- in BC, \+ ab BC beaches. http://cs.ubc.ca/~poole/cs312/2021/prolog/beach.pl
CPSC 312 — Lecture 31 13 / 24
©D. Poole 2021
Negation as Failure and the Unique Names Assumption
Suppose a knowledge base contains the single fact about p: p(a).
What happens to the query \+ p(b)?
What does this mean about the relationship between a and b?
With negation as faulure, Prolog assumes the unique names assumption: different ground (variable-free) terms denote different individuals.
In “Pure Prolog” without negation-as-failure (and related concepts, e.g., counting) a qery logically follows if it follows whether names are unique or not.
CPSC 312 — Lecture 31 14 / 24
©D. Poole 2021
Unique Names Assumption
Suppose the only clauses for enrolled are enrolled (sam, cs 222)
enrolled (chris , cs 222)
enrolled (sam, cs 873)
To conclude ¬enrolled(chris,cs873), what do we need to assume?
All other enrolled facts are false Inequalities:
sam ̸= chris ∧ cs873 ̸= cs222
The unique names assumption (UNA) is the assumption that
distinct ground terms denote different individuals.
CPSC 312 — Lecture 31 15 / 24
©D. Poole 2021
Clark Normal Form
The Clark normal form of the clause p(t1,…,tk) ← B.
is the clause
p(V1,…,Vk) ← ∃W1 …∃Wm V1 = t1, …, Vk = tk, B.
where
V1, . . . , Vk are k variables that did not appear in the original clause
W1, . . . , Wm are the original variables in the clause. When the clause is an atomic clause, B is true.
Often can be simplified by replacing ∃W V = W ∧ p(W ) with P(V).
CPSC 312 — Lecture 31 16 / 24
©D. Poole 2021
Clark normal form
For the clauses student (mary ).
student(sam).
student(X) ← undergrad(X). the Clark normal form is
student(V) ← V = mary.
student(V ) ← V = sam. student(V)←∃X V =X∧undergrad(X).
©D. Poole 2021
CPSC 312 — Lecture 31 17 / 24
Clark’s Completion
Suppose all of the clauses for p are put into Clark normal form, with the same set of introduced variables, giving
p(V1,…,Vk) ← B1. .
p(V1,…,Vk) ← Bn. which is equivalent to
p(V1,…,Vk)←B1 ∨…∨Bn.
Clark’s completion of predicate p is the equivalence
∀V1…∀Vk p(V1,…,Vk)↔B1 ∨…∨Bn
If there are no clauses for p, the completion results in
∀V1 …∀Vk p(V1,…,Vk) ↔ false
Clark’s completion of a knowledge base consists of the completion of every predicate symbol along the unique names assumption.
©D. Poole 2021
CPSC 312 — Lecture 31 18 / 24
Clark normal form
For the clauses student (mary ).
student(sam).
student(X) ← undergrad(X). the Clark normal form is
student(V) ← V = mary.
student(V ) ← V = sam. student(V)←∃X V =X∧undergrad(X).
which is equivalent to
student(V)←V =mary∨V =sam∨∃X V =X∧undergrad(X).
The completion of the student predicate is ∀V student(V)↔V =mary∨V =sam
∨ ∃X V = X ∧ undergrad(X).
©D. Poole 2021
CPSC 312 — Lecture 31 19 / 24
Completion Example
Consider the recursive definition:
passed each([],St,MinPass). passed each([C|R],St,MinPass) ←
passed (St , C , MinPass ),
passed each(R,St,MinPass).
In Clark normal form, this can be written as
passed each(L,S,M) :- L = []. passed each(L,S,M)←
∃C ∃R L = [C|R], passed(S,C,M), passed each(R,S,M). Here we renamed the variables as appropriate. Thus, Clark’s
completion of passed each is
∀L∀S ∀M passed each(L,S,M)↔L=[]∨
∃C ∃R L = [C|R], passed(S,C,M), passed each(R,S,M).
©D. Poole 2021
CPSC 312 — Lecture 31 20 / 24
Clark’s Completion of a KB
Clark’s completion of a knowledge base consists of the completion of every predicate.
The completion of an n-ary predicate p with no clauses is p(V1,…,Vn) ↔ false.
You can interpret negations in the body of clauses. \+ a means a is false under the complete knowledge
assumption. \+ a is replaced by ¬a in the completion. This is negation as failure.
CPSC 312 — Lecture 31 21 / 24
©D. Poole 2021
Defining empty course
Given database of:
course(C) that is true if C is a course
enrolled(S,C) that is true if student S is enrolled in course C.
Define empty course(C) that is true if there are no students enrolled in course C.
Using negation as failure, empty course(C) can be defined by empty course(C) ← course(C), \+ has enrollment(C). has enrollment(C) ← enrolled(S,C).
The completion of this is:
∀C empty course(C) ⇐⇒ course(C), ¬has enrollment(C). ∀C has enrollment(C) ⇐⇒ ∃S enrolled(S,C).
CPSC 312 — Lecture 31 22 / 24
©D. Poole 2021
Problem Cases
p :- p.
r:- \+r.
a:- \+b. b :- \+ a.
c:- \+d. d :- c.
It isn’t clear what the semantics should be. Prolog goes into an infinite loop.
Avoid cycles!
CPSC 312 — Lecture 31
23 / 24
©D. Poole 2021
Problematic Cases
p(X) :- \+ q(X) q(X) :- \+ r(X) r (a)
?- p(X).
What is the answer?
How can this be implemented?
CPSC 312 — Lecture 31
24 / 24
©D. Poole 2021