20
Mathematical Aspects of Logic Programming Semantics
write ¬L ∈ I if A ∈ I. Using these observations, we now say that a literal L
is true in I if L ∈ I, that L is false in I if ¬L ∈ I, and that L is undefined
in I otherwise. Notice that these facts depend on, and indeed are equivalent
to, defining the negation operator ¬ from T HREE into itself by means of
Table 1.1, so that ¬(t) = f , ¬(f ) = t, and ¬(u) = u.
Finally, we note that four-valued interpretations can be treated in the same
sort of way as we have just handled three-valued interpretations by including
inconsistent signed sets in the discussion, but we omit the details of this as
we have no need of them.
1.3.4 Operators on Spaces of Valuations
As we have seen, an ordering on a space T of truth values induces an
ordering on the corresponding spaces I(X, T ). Similarly, various connectives
defined on T induce operators defined on I(X, T ), and we close this chapter
by briefly discussing these next. They will be considered further in Chapter 3.
In fact, we concentrate on Belnap’s four-valued logic, in which the truth
set is FOU R and the connectives are determined by the truth table, Table 1.1. Since classical two-valued logic and Kleene’s strong three-valued logic
are sublogics of FOU R, they are subsumed in our discussion of FOU R and
therefore need not be considered separately.
The first of these operators arises through negation, and is the operator mapping I(X, T ) into itself, and still denoted by ¬, in which (¬v)(x) =
¬(v(x)) for each x ∈ X, where v is an arbitrary element of I(X, T ).
Likewise, the connectives ∨ and ∧ determine (binary) operators mapping
I(X, T ) × I(X, T ) into I(X, T ) defined by (u ∨ v)(x) = u(x) ∨ v(x) and
(u ∧ v)(x) = u(x) ∧ v(x), for each x ∈ X, where u and v are arbitrary elements
of I(X, T ). We note that the overloading of the symbols ∨ and ∧ should not
cause any difficulties. Of course, one can similarly deal with other connectives
such as → and ↔.
If v 1 , v 2 ∈ I(X, T ) satisfy the conditions v 1 [ t v 2 , v 1 (x) = f and v 2 (x) = t
for some x, then it is clear that ¬v 1 [ t ¬v 2 . Hence, ¬ is not monotonic in this
case. Thus, ¬ is not order continuous in the truth orderings [ t . It is, however,
order continuous in the orderings [ k , as we shall see in Chapter 3, where we
also consider the continuity of the other operators ∨ and ∧.
The following observation is just one of the many interesting properties
possessed by I(X, T ) when we take T to be the logic FOU R, as we are
currently doing.
1.3.7 Proposition The operators ∨ and ∧ are monotonic in each argument.
Proof: Given v ∈ I(X, T ), it must be shown that the mappings u � → u ∨ v
and u � → v ∨ u are both monotonic, and, since ∨ is commutative, it suffices
to show that either is monotonic. It is straightforward to check this from the
truth table, Table 1.1, and the Hasse diagram for FOU R, Figure 1.1, and we
omit details. Precisely the same comments apply also to the operator ∧. •
Mathematical Aspects of Logic Programming Semantics
write ¬L ∈ I if A ∈ I. Using these observations, we now say that a literal L
is true in I if L ∈ I, that L is false in I if ¬L ∈ I, and that L is undefined
in I otherwise. Notice that these facts depend on, and indeed are equivalent
to, defining the negation operator ¬ from T HREE into itself by means of
Table 1.1, so that ¬(t) = f , ¬(f ) = t, and ¬(u) = u.
Finally, we note that four-valued interpretations can be treated in the same
sort of way as we have just handled three-valued interpretations by including
inconsistent signed sets in the discussion, but we omit the details of this as
we have no need of them.
1.3.4 Operators on Spaces of Valuations
As we have seen, an ordering on a space T of truth values induces an
ordering on the corresponding spaces I(X, T ). Similarly, various connectives
defined on T induce operators defined on I(X, T ), and we close this chapter
by briefly discussing these next. They will be considered further in Chapter 3.
In fact, we concentrate on Belnap’s four-valued logic, in which the truth
set is FOU R and the connectives are determined by the truth table, Table 1.1. Since classical two-valued logic and Kleene’s strong three-valued logic
are sublogics of FOU R, they are subsumed in our discussion of FOU R and
therefore need not be considered separately.
The first of these operators arises through negation, and is the operator mapping I(X, T ) into itself, and still denoted by ¬, in which (¬v)(x) =
¬(v(x)) for each x ∈ X, where v is an arbitrary element of I(X, T ).
Likewise, the connectives ∨ and ∧ determine (binary) operators mapping
I(X, T ) × I(X, T ) into I(X, T ) defined by (u ∨ v)(x) = u(x) ∨ v(x) and
(u ∧ v)(x) = u(x) ∧ v(x), for each x ∈ X, where u and v are arbitrary elements
of I(X, T ). We note that the overloading of the symbols ∨ and ∧ should not
cause any difficulties. Of course, one can similarly deal with other connectives
such as → and ↔.
If v 1 , v 2 ∈ I(X, T ) satisfy the conditions v 1 [ t v 2 , v 1 (x) = f and v 2 (x) = t
for some x, then it is clear that ¬v 1 [ t ¬v 2 . Hence, ¬ is not monotonic in this
case. Thus, ¬ is not order continuous in the truth orderings [ t . It is, however,
order continuous in the orderings [ k , as we shall see in Chapter 3, where we
also consider the continuity of the other operators ∨ and ∧.
The following observation is just one of the many interesting properties
possessed by I(X, T ) when we take T to be the logic FOU R, as we are
currently doing.
1.3.7 Proposition The operators ∨ and ∧ are monotonic in each argument.
Proof: Given v ∈ I(X, T ), it must be shown that the mappings u � → u ∨ v
and u � → v ∨ u are both monotonic, and, since ∨ is commutative, it suffices
to show that either is monotonic. It is straightforward to check this from the
truth table, Table 1.1, and the Hasse diagram for FOU R, Figure 1.1, and we
omit details. Precisely the same comments apply also to the operator ∧. •