136
Mathematical Aspects of Logic Programming Semantics
not immediately carry over to the case of multivalued mappings T without
additional assumptions. One such simple, though rather strong, condition is
the following: for each x ∈ X, assume that T (x) has a least element M x and
that M x ≤ M y whenever x ≤ y. To see that this suffices, suppose that x is
any fixed point of T , and construct the orbit (x n ) of T by setting x 0 = ⊥ and
x n+1 = M xn for each n. Then (x n ) converges to a fixed point x. Noting that
⊥ ≤ x and that M x ≤ x, we see that x n ≤ x for all n. Hence, x ≤ x.
4.14 An Alternative to Multivalued Mappings
As already noted earlier, multivalued mappings arise naturally as semantic
operators in relation to disjunctive logic programs. However, William Rounds
and Guo-Qiang Zhang have shown that the use of multivalued mappings in this
context can be avoided by employing single-valued mappings defined on power
domains instead (we refer the reader to [Stoltenberg-Hansen et al., 1994] for
details of power domains). In fact, this observation is part of a considerable
programme of research undertaken by the authors just mentioned in the application of domain theory to logic programming. Since their work complements
that presented here, we intend to make a few remarks about a couple of aspects
of it, and it is convenient to do this next.
The starting point of this programme of work is the observation that domains and logic are strongly related [Zhang, 1991] and that this relationship
may be used as a foundation for a theory of logic programming based on domain theory. In [Zhang and Rounds, 1997a, Zhang and Rounds, 1997b] and
[Rounds and Zhang, 2001], Rounds and Zhang use power domains to develop
a domain-theoretic view of default logic, which they call power defaults. Indeed, in this framework logic programs can be viewed in a rather simple way
as default theories in the sense of [Reiter, 1980]. Default theories constitute
an important formalism in the area of non-monotonic reasoning, and we refer the reader to [Bidoit and Froideveaux, 1991, Gelfond and Lifschitz, 1991,
Bochman, 1995, Lifschitz, 2001] and to the references contained in these papers for an interesting discussion of the relationship between default logic and
logic programs. Indeed, from this point of view, the standard models of a disjunctive program, such as the stable model, correspond to extensions in default
logic: in short, truth in a model corresponds to default theorem. Furthermore,
Rounds and Zhang [Rounds and Zhang, 2001, Zhang and Rounds, 1997a,
Zhang and Rounds, 1997b, Zhang and Rounds, 2001] study a version of default reasoning from the domain-theoretic point of view. In particular, they
focus on the Smyth powerdomain by making the observation that the Smyth
powerdomain can be used to model non-monotonicity. This results, for example, in the implementation of a non-monotonic reasoning system, see
[Klavins et al., 1998], which bears a significant relationship to other answer
Mathematical Aspects of Logic Programming Semantics
not immediately carry over to the case of multivalued mappings T without
additional assumptions. One such simple, though rather strong, condition is
the following: for each x ∈ X, assume that T (x) has a least element M x and
that M x ≤ M y whenever x ≤ y. To see that this suffices, suppose that x is
any fixed point of T , and construct the orbit (x n ) of T by setting x 0 = ⊥ and
x n+1 = M xn for each n. Then (x n ) converges to a fixed point x. Noting that
⊥ ≤ x and that M x ≤ x, we see that x n ≤ x for all n. Hence, x ≤ x.
4.14 An Alternative to Multivalued Mappings
As already noted earlier, multivalued mappings arise naturally as semantic
operators in relation to disjunctive logic programs. However, William Rounds
and Guo-Qiang Zhang have shown that the use of multivalued mappings in this
context can be avoided by employing single-valued mappings defined on power
domains instead (we refer the reader to [Stoltenberg-Hansen et al., 1994] for
details of power domains). In fact, this observation is part of a considerable
programme of research undertaken by the authors just mentioned in the application of domain theory to logic programming. Since their work complements
that presented here, we intend to make a few remarks about a couple of aspects
of it, and it is convenient to do this next.
The starting point of this programme of work is the observation that domains and logic are strongly related [Zhang, 1991] and that this relationship
may be used as a foundation for a theory of logic programming based on domain theory. In [Zhang and Rounds, 1997a, Zhang and Rounds, 1997b] and
[Rounds and Zhang, 2001], Rounds and Zhang use power domains to develop
a domain-theoretic view of default logic, which they call power defaults. Indeed, in this framework logic programs can be viewed in a rather simple way
as default theories in the sense of [Reiter, 1980]. Default theories constitute
an important formalism in the area of non-monotonic reasoning, and we refer the reader to [Bidoit and Froideveaux, 1991, Gelfond and Lifschitz, 1991,
Bochman, 1995, Lifschitz, 2001] and to the references contained in these papers for an interesting discussion of the relationship between default logic and
logic programs. Indeed, from this point of view, the standard models of a disjunctive program, such as the stable model, correspond to extensions in default
logic: in short, truth in a model corresponds to default theorem. Furthermore,
Rounds and Zhang [Rounds and Zhang, 2001, Zhang and Rounds, 1997a,
Zhang and Rounds, 1997b, Zhang and Rounds, 2001] study a version of default reasoning from the domain-theoretic point of view. In particular, they
focus on the Smyth powerdomain by making the observation that the Smyth
powerdomain can be used to model non-monotonicity. This results, for example, in the implementation of a non-monotonic reasoning system, see
[Klavins et al., 1998], which bears a significant relationship to other answer