13
Order and Logic
1.3.1 Remark Much of the theory of logic programming semantics is concerned with sets of valuations. It is important, therefore, to have convenient
notation for valuations and to have ways of representing them, which both
facilitate discussion and also allow easy passage backwards and forwards between the different representations employed. There are three ways of handling valuations, which are commonly used in the literature on the subject
and which we adopt also. Having these three forms available will, in certain
places, greatly increase readability and reduce technical difficulty.
First, when considering general structures such as orderings or topologies
on I(X, T ), the easiest way is to think of valuations as mappings, and this
we will usually do. Thus, in the main, our future use of the term valuation
will refer to mappings whose domain is a set of atoms (or ground instances of
atoms) and whose codomain is a set T of truth values.
Second, when T is a small set containing two, three, or four elements,
say, it is convenient to identify a valuation with the (ordered) tuple of sets
on which it takes the various truth values in T , as discussed in Section 1.3.2.
This is by far the most frequently used representation, and, in common with
most authors, we will in future usually employ the term interpretation when
thinking in these terms. Thus, as we progress, more and more we employ the
terminology interpretation instead of valuation, use the standard notation I,
K, etc. to denote interpretations, and adopt the notation described at the end
of Section 2.1 for sets of interpretations.
Third, there is yet another representation frequently used for interpretations when T is the set T HREE, namely, signed sets as discussed in Section 1.3.3. This form is particularly expressive, as we shall see in Chapter 2,
when one wants to discuss the truth value of conjunctions of literals in relation
to T HREE.
1.3.1 Ordered Spaces of Valuations in General
Usually, the set T of truth values carries an order, ≤, in which (T , ≤)
is perhaps a complete partial order, complete upper semi-lattice, complete
lattice, or Scott domain, with bottom element ⊥, say, or even a bilattice
19
when equipped with two compatible orderings. When T carries an ordering,
≤, we can define the corresponding pointwise ordering on I(X, T ), denoted
by [, in which v 1 [ v 2 if and only if v 1 (x) ≤ v 2 (x) for all x ∈ X.
It is routine to check that the ordering [ is in fact a partial order if ≤ is
one. Moreover, if T has a bottom element, ⊥, then the valuation which maps
each x in X to ⊥ serves as a bottom element in I(X, T ), and we may denote
this valuation simply by ⊥ again, without causing confusion. Finally, if (T , ≤)
is a Scott domain, we shall say that a valuation v in I(X, T ) is finite if v(x) is
19 A (complete) bilattice is a set D carrying two partial orders in each of which D is a
(complete) lattice. In addition, the two orderings are required to interact with each other
so as to obtain various distributive laws.
Order and Logic
1.3.1 Remark Much of the theory of logic programming semantics is concerned with sets of valuations. It is important, therefore, to have convenient
notation for valuations and to have ways of representing them, which both
facilitate discussion and also allow easy passage backwards and forwards between the different representations employed. There are three ways of handling valuations, which are commonly used in the literature on the subject
and which we adopt also. Having these three forms available will, in certain
places, greatly increase readability and reduce technical difficulty.
First, when considering general structures such as orderings or topologies
on I(X, T ), the easiest way is to think of valuations as mappings, and this
we will usually do. Thus, in the main, our future use of the term valuation
will refer to mappings whose domain is a set of atoms (or ground instances of
atoms) and whose codomain is a set T of truth values.
Second, when T is a small set containing two, three, or four elements,
say, it is convenient to identify a valuation with the (ordered) tuple of sets
on which it takes the various truth values in T , as discussed in Section 1.3.2.
This is by far the most frequently used representation, and, in common with
most authors, we will in future usually employ the term interpretation when
thinking in these terms. Thus, as we progress, more and more we employ the
terminology interpretation instead of valuation, use the standard notation I,
K, etc. to denote interpretations, and adopt the notation described at the end
of Section 2.1 for sets of interpretations.
Third, there is yet another representation frequently used for interpretations when T is the set T HREE, namely, signed sets as discussed in Section 1.3.3. This form is particularly expressive, as we shall see in Chapter 2,
when one wants to discuss the truth value of conjunctions of literals in relation
to T HREE.
1.3.1 Ordered Spaces of Valuations in General
Usually, the set T of truth values carries an order, ≤, in which (T , ≤)
is perhaps a complete partial order, complete upper semi-lattice, complete
lattice, or Scott domain, with bottom element ⊥, say, or even a bilattice
19
when equipped with two compatible orderings. When T carries an ordering,
≤, we can define the corresponding pointwise ordering on I(X, T ), denoted
by [, in which v 1 [ v 2 if and only if v 1 (x) ≤ v 2 (x) for all x ∈ X.
It is routine to check that the ordering [ is in fact a partial order if ≤ is
one. Moreover, if T has a bottom element, ⊥, then the valuation which maps
each x in X to ⊥ serves as a bottom element in I(X, T ), and we may denote
this valuation simply by ⊥ again, without causing confusion. Finally, if (T , ≤)
is a Scott domain, we shall say that a valuation v in I(X, T ) is finite if v(x) is
19 A (complete) bilattice is a set D carrying two partial orders in each of which D is a
(complete) lattice. In addition, the two orderings are required to interact with each other
so as to obtain various distributive laws.