Information Technology Reference
In-Depth Information
Let
X
be a set of ground atoms (i.e. all atoms constructed with the predicate in Herband base of
a logic program). The body of a rule of the form (1) is satisfied by
X
if
}
X
{
a
m
+
1
,...,
a
n
=
∅
{
}⊆
and
a
1
,...,
a
m
X
. A rule with a non-empty head is satisfied by
X
if either its body is not
∈
satisfied by
X
,or
a
0
X
. A constraint is satisfied by
X
if its body is not satisfied by
X
.
Since logic programs unify declarative and procedural representations of knowledge, one way
to reason is by using Horn clauses, backward reasoning and selective linear definite clause
(SLD) resolution. The
reduct
of a program is a possibility to generate answer sets. Given an
arbitrary program,
X
, is the definite
Π
Π
Π
and a set of ground atoms,
X
, the reduct of
w.r.t.
X
,
program obtained from the set of all ground instances of
by:
1. deleting all the rules that have a naf-literal not
a
in the body where
a
Π
∈
X
, and
2. removing all naf-literals in the bodies of the remaining rules.
A set of ground atoms
X
is an answer set of a program
Π
, if it satisfies the following conditions:
Π
Π
1. If
is a definite program, then
X
is a minimal set of atoms that satisfies all the rules in
.
X
is a definite
program, and its answer set is defined in the first item (cf. Baral et al. (2010)).
The other advantage of ASP is that the order of program rules does not matter and the order
of subgoals in a rule is also not relevant. For an example, if we have the famous problem
"3-colorability", where we have a map and we want to check whether 3 colors (blue, yellow
and red) are sufficient to color a map. Amap is represented by a graph, with facts about nodes
and edges.
vertex(a), vertex(b), edge(a,b).
Every vertex must be colored with exactly one color:
color(V,r) :- vertex(V), not color(V,b), not color(V,y).
color(V,b) :- vertex(V), not color(V,r), not color(V,y).
color(V,y) :- vertex(V), not color(V,b), not color(V,r).
No adjacent vertices may be colored with the same color
:- vertex(V), vertex(U), edge(V,U), col(C), color(V,C), color(U,C).
Of course, we need to say what colors are:
col(r).
col(b).
col(y).
After running this programwe will get all possible coloring cases to color the whole map with
three different colors. The other advantage of ASP that the order of program rules does not a
matter and the order of subgoals in a rule does not a matter also.
X
. (Recall that
2. If
Π
is not a definite program, then
X
is the answer set of
Π
Π
2.1.1 Logic programming with ordered disjunction
Logic programming can be extended to allow us to represent new options for problems in the
head of the rules. ASP gives us this ability by the way of ordered disjunctions. Using ASP
under specific conditions reasoning from most preferred answer sets gives optimal problem
solutions. Through logical programs with ordered disjunction (LPODs), such as normal logic
programs we are able to express incomplete and defeasible knowledge through the use of
default negation, they allow us to represent performances among intended properties of
problem solutions which depend on the current context. It is possible to use the degree
of satisfaction of a rule to define a preference relation on answer sets. We will present an
alternative on game-theoretic grounds in section 4. Brewka (2002) defines a rule as having
Search WWH ::
Custom Search