1/25
Part III
Unit 7: The Answer Set Semantics
Mark Law
March 8th, 2018
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
2/25
Reachability in graphs
1 2
3 4
1 :
2 :
3 :
node(1..4).
edge(1, 2). edge(2, 3).
edge(3, 4). edge(4, 1).
4 :
5 :
6 :
reach(N) :- edge(1, N).
reach(N) :- reach(N2), edge(N2, N).
unreachable node :- node(N), not reach(N).
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
1. Consider the graph above. We wish to test whether every node is
“reachable” from node 1 (i.e. whether there is a path from 1 to
every node).
2. Line 1 says that there are 4 nodes in the graph (node(1..4) is
shorthand for node(1), . . . , node(4)).
Lines 2 and 3 specify the edges in the graph.
3. Lines 4 and 5 specify the concept of a node being reachable from
node 1. Line 4 is the base case that says that a node N is reachable
from 1 if there is an edge from 1 to N.
Line 5 is the recursive case, saying that a node N is reachable if
there is an edge from another reachable node to N.
4. Line 6 says that there is an unreachable node if there exists a node
for which we cannot prove reachability.
3/25
Reachability in graphs: Clark Completion
1 2
3 4
1 :
2 :
node(X)↔ X = 1 ∨ . . . ∨ X = 4.
edge(X, Y)↔ (X = 1 ∧ Y = 2)∨
(X = 2 ∧ Y = 3)∨
(X = 3 ∧ Y = 4)∨
(X = 4 ∧ Y = 1)
3 :
4 :
5 :
reach(N)↔ edge(1, N) ∨ ∃N2.(reach(N2) ∧ edge(N2, N)).
unreachable node↔ ∃N.(node(N) ∧ not reach(N)).
¬(1 = 2). . . .
What are the models of comp(P)?
Facts(P) ∪ {reach(1..4)}
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
1. Earlier in the course, you have seen the idea of the Clark
Completion (Clark 1978).
2. Our graph program has exactly one supported model (shown on the
slide). Note that Facts(P) denotes the set of atoms that occur as
facts in P. This shows that in this graph, every node is reachable
from node 1.
4/25
Reachability in graphs: Clark Completion
1 2
3 4
1 :
2 :
node(X)↔ X = 1 ∨ . . . ∨ X = 4.
edge(X, Y)↔ (X = 1 ∧ Y = 2)∨
(X = 3 ∧ Y = 4)∨
(X = 4 ∧ Y = 1)
3 :
4 :
5 :
reach(N)↔ edge(1, N) ∨ ∃N2.(reach(N2) ∧ edge(N2, N)).
unreachable node↔ ∃N.(node(N) ∧ not reach(N)).
¬(1 = 2). . . .
What are the models of comp(P)?
Facts(P) ∪ {reach(1), reach(2), unreachable node}
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
1. We can check the program by changing the graph to one which has
an unreachable node.
2. This time, the unique model of comp(P) contains
unreachable node as the nodes 3 and 4 are unreachable from 1.
5/25
Reachability in graphs: Clark Completion
1 2
3 4
1 :
2 :
node(X)↔ X = 1 ∨ . . . ∨ X = 4.
edge(X, Y)↔ (X = 1 ∧ Y = 2)∨
(X = 2 ∧ Y = 1)∨
(X = 3 ∧ Y = 4)∨
(X = 4 ∧ Y = 3)
3 :
4 :
5 :
reach(N)↔ edge(1, N) ∨ ∃N2.(reach(N2) ∧ edge(N2, N)).
unreachable node↔ ∃N.(node(N) ∧ not reach(N)).
¬(1 = 2). . . .
What are the models of comp(P)?
Facts(P) ∪ {reach(1..2), unreachable node},
Facts(P) ∪ {reach(1..4)}
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
1. In this graph, not all nodes are reachable, but there are cycles.
2. This time, there are two models of comp(P). One says that the
graph has unreachable nodes, and the other says that it does not!
3. The problem is that the Clark completion does not specify that the
base case must be reached.
4. In the remainder of this course, we will see the Answer Set
semantics, which gives a much more intuitive meaning to recursive
programs with negation as failure. We will see that our graph
program has exactly one answer set (the first model on the slide).
6/25
Part III: Overview
I Unit 7: The Answer Set Semantics
I Motivation X
I Semantics
I How does it relate to the Clark completion?
I Unit 8: Disjunction, Constraints, Choice rules and Abduction
in ASP
I Unit 9: Aggregation and Optimisation in ASP
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
In this part of the course, we will study the answer set semantics. In this
lecture, we will formalise what it means to be an answer set of a
program, and see how this relates to the other semantics you have
covered in this course so far. The next lecture will introduce ways of
expressing choice and disjunction in ASP. We will see that these
constructs are very useful for abduction in ASP. In the final lecture, we
will look at how to express aggregation and optimisation in ASP.
7/25
ASP: Overview
I In this lecture, programs are set of rules of the form:
h :- b1, . . . , bm, not c1, . . . , not cn.
Where h, b1, . . . , bm, c1, . . . , cn are all atoms (made of
predicates, functions, constants and variables as usual). Note,
ASP does not have lists!
I ASP allows other kinds of rules, which we will see next week.
I ASP is declarative – you specify the problem, not the
procedure!
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
The ASP programs we will see in this lecture are similar to the programs
you have worked with so far in the course, other than that ASP does not
allow lists. We will see next week that ASP allows for other kinds of rules
to express choice, optimisation and other concepts. One of the major
selling points of ASP is that it is declarative. Unlike in Prolog, where you
need to think about structuring your program to avoid loops, ASP
programs are declarative. In ASP, you encode the problem you are trying
to solve but you do not need to think about the procedure that is
required to solve it (this is delegated to an ASP solver).
8/25
Terminology
I A fact is a rule with an empty body.
I head(R) is the head of a rule.
I body+(R) is the set of all positive body literals in a rule.
I body−(R) is the set of all negative body literals in a rule.
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
9/25
Terminology
I The Herband base of a program is the set of all ground atoms
that can be made from predicate symbols, functions and
constants in the program.
I A Hebrand interpretation is an assignment from each element
of the Hebrand base of a program to either true or false. We
usually write an interpretation as the set of things it assigns to
true.
I A Herbrand model is a Herbrand interpretation that satisfies
every rule in the program (if it satisfies the body of a rule, it
must satisfy the head).
I A Herbrand model is said to be minimal if no subset of it is
also a model.
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
10/25
Relevant Grounding: Iterative Construction
I For any program P, ground(P) denotes the set of all ground
instances of rules in P.
I As this is usually infinite, ASP solvers compute the relevant
grounding, denoted RG(P) in this course.
1: procedure RG(P)
2: G = ∅
3: do
4:
G ′ =
{
R ∈ ground(P)
∣∣∣∣
R 6∈ G and each element of
body+(R) is the head of a rule in G
}
5: G = G ∪ G ′
6: while G ′ 6= ∅
7: return G
8: end procedure
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
The first step of solving an Answer Set Program is to transform it into an equivalent
ground program. This process is called grounding. Any program that contains at least
one function symbol and at least one constant (and at least one variable) technically
has an infinite number of ground instances. For example, consider the program:
p(f(X)) :- q(g(X)).
q(a).
You may think that there are only two important ground instances to consider here
(the fact q(a) and the rule with X substituted with a). In fact X can be substituted
with f(a), f(f(a)) and so on. As q(g(f(a))) (etc.) can never be proved given this
program, these rules are “irrelevant”. ASP solvers consider a smaller relevant
grounding. This can be computed using the algorithm on the slide (although modern
ASP grounders such as Gringo (Gebser et al 2007), use much more sophisticated
algorithms).
The idea of this simple procedure for computing the relevant grounding is to keep
adding ground instances of rules R for which every positive body literal of R occurs in
the head of a ground instance that we have already computed. Any ground rule that
contains a positive body literal that is not in the head of some other rule is irrelevant
as its body cannot be satisfied by the other rules (as its body is guaranteed to not be
satisfied, the rule is guaranteed to be satisfied).
11/25
Grounding: safety
I A rule R is safe if every variable that occurs in R occurs in
body+(R)
Are the following rules safe?
p(X) :- q(X), not r(X, Y).
p(Y) :- q(X), not r(X, X).
p(Y) :- q(X), r(X, Y).
X
X
X
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
1. In order for grounding to be possible, a simple condition must hold:
safety. A rule R is said to be unsafe if it contains a variable that
does not occur in any positive body literal of R. For an ASP
program to be grounded it must be safe (i.e. it cannot contain any
unsafe rules).
12/25
Relevant Grounding: Example
P =
1 :
2 :
3 :
4 :
node(1..2). edge(1, 1). edge(2, 2).
reach(N) :- edge(1, N).
reach(N) :- reach(N2), edge(N2, N).
unreachable node :- node(N), not reach(N).
What is RG(P)?
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(1), not reach(1).
unreachable node :- node(2), not reach(2).
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
12/25
Relevant Grounding: Example
P =
1 :
2 :
3 :
4 :
node(1..2). edge(1, 1). edge(2, 2).
reach(N) :- edge(1, N).
reach(N) :- reach(N2), edge(N2, N).
unreachable node :- node(N), not reach(N).
What is RG(P)?
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(1), not reach(1).
unreachable node :- node(2), not reach(2).
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
12/25
Relevant Grounding: Example
P =
1 :
2 :
3 :
4 :
node(1..2). edge(1, 1). edge(2, 2).
reach(N) :- edge(1, N).
reach(N) :- reach(N2), edge(N2, N).
unreachable node :- node(N), not reach(N).
What is RG(P)?
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(1), not reach(1).
unreachable node :- node(2), not reach(2).
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
12/25
Relevant Grounding: Example
P =
1 :
2 :
3 :
4 :
node(1..2). edge(1, 1). edge(2, 2).
reach(N) :- edge(1, N).
reach(N) :- reach(N2), edge(N2, N).
unreachable node :- node(N), not reach(N).
What is RG(P)?
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(1), not reach(1).
unreachable node :- node(2), not reach(2).
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
13/25
Relevant Grounding: Exercise
Please attempt Question 1 (a) (i) from the tutorial sheet.
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
14/25
Reduct
Given a ground logic program P and an interpretation X , the
reduct PX is constructed in two steps:
I Remove any rule whose body contains the negation of an
atom in X
I Delete any negation from the remaining rules
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
Given an interpretation X and ground logic program P, we can check
whether X is an answer set of P using the reduct of P with respect to X
(denoted PX ). The intuition behind the reduct is that we assume X is
“correct” and use it to interpret the negation in the program.
The first step of computing PX is to remove any rule from P whose body
contains the negation of something in X – if we assume that X is
“correct” these rule bodies are false.
The second step is to delete the negation in the remaining rules – if we
assume X is correct, then “not a” is true for any a 6∈ X .
There are many different definitions of the reduct (and answer sets). For
the fragment of ASP that we consider in this lecture (normal logic
programs), the different definitions of answer set are all equivalent. We
will use other definitions later in the course when we start using other
types of rules.
Note that this definition of the reduct is guaranteed to have a unique
minimal model (as it is a definite logic program).
14/25
Reduct
Given a ground logic program P and an interpretation X , the
reduct PX is constructed in two steps:
I Remove any rule whose body contains the negation of an
atom in X
I Delete any negation from the remaining rules
X = {heads}, P =
{
heads :- not tails.
tails :- not heads.
}
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
Given an interpretation X and ground logic program P, we can check
whether X is an answer set of P using the reduct of P with respect to X
(denoted PX ). The intuition behind the reduct is that we assume X is
“correct” and use it to interpret the negation in the program.
The first step of computing PX is to remove any rule from P whose body
contains the negation of something in X – if we assume that X is
“correct” these rule bodies are false.
The second step is to delete the negation in the remaining rules – if we
assume X is correct, then “not a” is true for any a 6∈ X .
There are many different definitions of the reduct (and answer sets). For
the fragment of ASP that we consider in this lecture (normal logic
programs), the different definitions of answer set are all equivalent. We
will use other definitions later in the course when we start using other
types of rules.
Note that this definition of the reduct is guaranteed to have a unique
minimal model (as it is a definite logic program).
14/25
Reduct
Given a ground logic program P and an interpretation X , the
reduct PX is constructed in two steps:
I Remove any rule whose body contains the negation of an
atom in X
I Delete any negation from the remaining rules
X = {heads}, P =
{
heads :- not tails.
tails :- not heads.
}
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
Given an interpretation X and ground logic program P, we can check
whether X is an answer set of P using the reduct of P with respect to X
(denoted PX ). The intuition behind the reduct is that we assume X is
“correct” and use it to interpret the negation in the program.
The first step of computing PX is to remove any rule from P whose body
contains the negation of something in X – if we assume that X is
“correct” these rule bodies are false.
The second step is to delete the negation in the remaining rules – if we
assume X is correct, then “not a” is true for any a 6∈ X .
There are many different definitions of the reduct (and answer sets). For
the fragment of ASP that we consider in this lecture (normal logic
programs), the different definitions of answer set are all equivalent. We
will use other definitions later in the course when we start using other
types of rules.
Note that this definition of the reduct is guaranteed to have a unique
minimal model (as it is a definite logic program).
14/25
Reduct
Given a ground logic program P and an interpretation X , the
reduct PX is constructed in two steps:
I Remove any rule whose body contains the negation of an
atom in X
I Delete any negation from the remaining rules
X = {heads}, P =
{
heads :- not tails.
tails :- not heads.
}
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
Given an interpretation X and ground logic program P, we can check
whether X is an answer set of P using the reduct of P with respect to X
(denoted PX ). The intuition behind the reduct is that we assume X is
“correct” and use it to interpret the negation in the program.
The first step of computing PX is to remove any rule from P whose body
contains the negation of something in X – if we assume that X is
“correct” these rule bodies are false.
The second step is to delete the negation in the remaining rules – if we
assume X is correct, then “not a” is true for any a 6∈ X .
There are many different definitions of the reduct (and answer sets). For
the fragment of ASP that we consider in this lecture (normal logic
programs), the different definitions of answer set are all equivalent. We
will use other definitions later in the course when we start using other
types of rules.
Note that this definition of the reduct is guaranteed to have a unique
minimal model (as it is a definite logic program).
15/25
Reduct: Example
X =
{
node(1..2), edge(1, 1), edge(2, 2),
reach(1), unreachable node
}
RG(P) =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(1), not reach(1).
unreachable node :- node(2), not reach(2).
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
15/25
Reduct: Example
X =
{
node(1..2), edge(1, 1), edge(2, 2),
reach(1), unreachable node
}
RG(P) =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(1), not reach(1).
unreachable node :- node(2), not reach(2).
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
15/25
Reduct: Example
X =
{
node(1..2), edge(1, 1), edge(2, 2),
reach(1), unreachable node
}
RG(P) =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(1), not reach(1).
unreachable node :- node(2), not reach(2).
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
16/25
Reduct: Exercise
Please attempt Question 1 (b) (i) from the tutorial sheet.
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
17/25
Answer Sets
An interpretation X is an answer set of a program P if and only if X is
the unique minimal model of RG(P)X (written X = M(RG(P)X ))
X = {heads}
P =
{
heads :- not tails.
tails :- not heads.
}
RG(P)X =
{
heads.
}
X = M(RG(P)X )
X ∈ AS(P)
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
In summary, the steps of checking whether X is an answer set of a
program P are:
1. Compute the relevant grounding RG(P).
2. Compute the reduct of RG(P) with respect to X .
3. Check whether X = M(RG(P)X ).
When P is a ground (propositional) program, we often omit the relevant
grounding step (RG(P) = P).
The set of all answer sets of a program P is denoted AS(P)
17/25
Answer Sets
An interpretation X is an answer set of a program P if and only if X is
the unique minimal model of RG(P)X (written X = M(RG(P)X ))
X = {tails}
P =
{
heads :- not tails.
tails :- not heads.
}
RG(P)X =
{
tails.
}
X = M(RG(P)X )
X ∈ AS(P)
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
In summary, the steps of checking whether X is an answer set of a
program P are:
1. Compute the relevant grounding RG(P).
2. Compute the reduct of RG(P) with respect to X .
3. Check whether X = M(RG(P)X ).
When P is a ground (propositional) program, we often omit the relevant
grounding step (RG(P) = P).
The set of all answer sets of a program P is denoted AS(P)
17/25
Answer Sets
An interpretation X is an answer set of a program P if and only if X is
the unique minimal model of RG(P)X (written X = M(RG(P)X ))
X = {heads, tails}
P =
{
heads :- not tails.
tails :- not heads.
}
RG(P)X =
{ }
X 6= M(RG(P)X )
X 6∈ AS(P)
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
In summary, the steps of checking whether X is an answer set of a
program P are:
1. Compute the relevant grounding RG(P).
2. Compute the reduct of RG(P) with respect to X .
3. Check whether X = M(RG(P)X ).
When P is a ground (propositional) program, we often omit the relevant
grounding step (RG(P) = P).
The set of all answer sets of a program P is denoted AS(P)
17/25
Answer Sets
An interpretation X is an answer set of a program P if and only if X is
the unique minimal model of RG(P)X (written X = M(RG(P)X ))
X = {}
P =
{
heads :- not tails.
tails :- not heads.
}
RG(P)X =
{
heads.
tails.
}
X 6= M(RG(P)X )
X 6∈ AS(P)
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
In summary, the steps of checking whether X is an answer set of a
program P are:
1. Compute the relevant grounding RG(P).
2. Compute the reduct of RG(P) with respect to X .
3. Check whether X = M(RG(P)X ).
When P is a ground (propositional) program, we often omit the relevant
grounding step (RG(P) = P).
The set of all answer sets of a program P is denoted AS(P)
18/25
Minimal model: Iterative Construction
I A definite logic program P, has a unique minimal model
M(P). It can be computed using the simple procedure below:
1: procedure M(P)
2: M = ∅
3: do
4: M ′ =
head(R)
∣∣∣∣∣∣
R ∈ P,
head(R) 6∈ M,
body(R) ⊆ M
5: M = M ∪M ′
6: while M ′ 6= ∅
7: return M
8: end procedure
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
The minimal model of any definite logic program can be computed by
starting with M as the empty set and iteratively adding to M any atom
that is the head of a rule in P whose body is already satisfied by M. In
each step, M ′ is equal to the immediate consequences TP(M). This
procedure computes the least fixpoint of TP , which you have covered
earlier in the course.
19/25
Minimal Model: Example
RG(P)X =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(2).
M(RG(P)X ) =
{
node(1..2), edge(1, 1), edge(2, 2),
}
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
19/25
Minimal Model: Example
RG(P)X =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(2).
M(RG(P)X ) =
{
node(1..2), edge(1, 1), edge(2, 2)
,
}
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
19/25
Minimal Model: Example
RG(P)X =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(2).
M(RG(P)X ) =
{
node(1..2), edge(1, 1), edge(2, 2),
reach(1), unreachable node
}
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
19/25
Minimal Model: Example
RG(P)X =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(2).
M(RG(P)X ) =
{
node(1..2), edge(1, 1), edge(2, 2),
reach(1), unreachable node
}
X = M(RG(P)X )
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
19/25
Minimal Model: Example
RG(P)X =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(2).
M(RG(P)X ) =
{
node(1..2), edge(1, 1), edge(2, 2),
reach(1), unreachable node
}
X ∈ AS(P)
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
20/25
Reachability in Graphs in ASP
X =
{
node(1..2), edge(1, 1), edge(2, 2), reach(1..2)
}
RG(P) =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(1), not reach(1).
unreachable node :- node(2), not reach(2).
M(RG(P)X ) =
{
node(1..2), edge(1, 1), edge(2, 2),
reach(1)
}
X 6∈ AS(P)
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
20/25
Reachability in Graphs in ASP
X =
{
node(1..2), edge(1, 1), edge(2, 2), reach(1..2)
}
RG(P)X =
node(1..2). edge(1, 1). edge(2, 2).
reach(1) :- edge(1, 1).
reach(1) :- reach(1), edge(1, 1).
unreachable node :- node(1), not reach(1).
unreachable node :- node(2), not reach(2).
M(RG(P)X ) =
{
node(1..2), edge(1, 1), edge(2, 2),
reach(1)
}
X 6∈ AS(P)
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
21/25
Answer Sets: Exercise
Please attempt Question 1 (c) (i) from the tutorial sheet.
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
22/25
Relationship between ASP and Clark completion
For any propositional program, A ∈ AS(P)⇒ A is a model of
comp(P).
The converse does not hold!
So what is special about answer sets?
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
We now consider the relationship between ASP and the Clark completion
that you saw earlier in the course. In this lecture, we only do this
comparison for propositional logic programs, as ASP requires programs to
be ground as a first step. All answer sets of a program P are models of
its completion comp(P).
We saw for the graphs examples though that for some programs there are
models of the completion that are not answer sets. So what is special
about answer sets?
23/25
Unfounded Sets
Given a ground program P and an interpretation I , a set U ⊆ I is
said to be an unfounded subset of I wrt P if and only if there is no
rule R such that (1)-(3) hold:
1. I satisfies body(R)
2. head(R) ∈ U
3. U ∩ body+(R) = ∅
Given any program P, the answer sets are equal to the models of
comp(P) which have no non-empty unfounded subsets wrt P.
In fact, these are the models of P that have no non-empty
unfounded subsets wrt P.
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
Answer sets can also be defined in terms of unfounded sets. Essentially subset
U of an interpretation is unfounded with respect to the program if there is no
rule R that proves anything in U without using the elements of U (in the
positive body of R).
Unfounded sets allow us to highlight the relationship between the earlier
semantics in this course and the answer set semantics. The answer sets of a
propositional program P are the models of comp(P) with no unfounded subsets
(wrt P). In fact, these are also the models of P with no non-empty unfounded
subsets wrt P.
You can think of an unfounded subset U of an interpretation I as not having
any “external support” – that is, the only way to prove any elements of U is by
using other elements of U (as the only rules with elements of U in the head
whose body is satisfied by I contain at least one element of U in their positive
body).
Consider the program:
p :- not q, r.
q :- not r.
r :- p.
The completion of this program has two models – {p,r} and {q} – but it only
has one answer sets – {q}. {p,r} is an unfounded subset of {p,r} wrt the
program. Every rule for p and r uses either p or r in the body.
24/25
Reachability in graphs and unfounded sets
1 2
3 4
1 :
2 :
3 :
node(1..4).
edge(1, 2). edge(2, 1).
edge(3, 4). edge(4, 3).
4 :
5 :
6 :
reach(N) :- edge(1, N).
reach(N) :- reach(N2), edge(N2, N).
unreachable node :- node(N), not reach(N).
I = Facts(P) ∪ {reach(1..4)}
{reach(3), reach(4)} is an unfounded subset of I wrt P. Hence
I 6∈ AS(P)
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)
25/25
Summary
I The completion of some programs can have unintuitive
models.
I Any definite program has a unique minimal model M(P)
I X ∈ AS(P)⇔ X = M(RG(P)X )
I X ∈ AS(P)⇔ X is a model of comp(RG(P)) and X has no
non-empty unfounded subsets wrt P.
Mark Law
Part III, Unit 7
(pdf built on March 8, 2018)