19
Order and Logic
Notice that the difference in the form of the statements in (b) and (c) in
Theorem 1.3.6 concerning the truth ordering [ t results from the fact that [ t
is a total order in (b), but it is not a total order in (c).
In all cases we are currently considering, except one, we are working in a
complete lattice. Hence, the valuation mapping each element of X to the appropriate top element is itself a top element. The one exception is the case of
three-valued interpretations in the order [ k . In this case, it is clear that those
interpretations I = (I t , I f ) for which I t ∪ I f = X are maximal elements for
the ordering [ k . Moreover, each maximal element I = (I t , I f ) gives rise to the
two-valued interpretation I t , and, conversely, each two-valued interpretation
I gives rise to a maximal three-valued interpretation (I, X \ I). Moreover, this
correspondence is evidently one-to-one. Thus, the two-valued interpretations
can be thought of as maximal three-valued interpretations. Indeed, the maximal elements are called total interpretations, while the remaining elements
are called partial interpretations.
1.3.3 Signed Sets and Three-Valued Interpretations
As mentioned in Remark 1.3.1, there is an alternative and useful way of
thinking of three-valued interpretations relative to the ordering [ k (so that u
is the current default value in the representation of interpretations as pairs of
sets), and we consider it next.
Let X denote an arbitrary set, and form the set ¬X of symbols ¬ x for
x ∈ X. If X happens to be a set of atoms or of literals, then ¬x is meaningful;
otherwise, we are working formally. In any case, we assume that x and ¬x
are never equal. Given a subset I of X, we let ¬I denote the subset of ¬X
consisting of those ¬ x for x ∈ I. A subset of X ∪ ¬X is called a signed subset
of X and is called consistent if it does not contain both x and ¬x for any x.
Clearly, any signed subset of X has the form I
+ ∪ ¬I
− , where I
+ and I
− are
subsets of X, and is consistent if and only if I
+ and I
− are disjoint.
Every consistent signed subset I = I
+ ∪ ¬I
− of X gives rise to the threevalued interpretation (I
+ , I
− ). Then, thinking of I as this three-valued interpretation, we have I t = I
+ = {x ∈ X | x ∈ I} and I f = I
− = {x ∈ X |
¬x ∈ I}. Conversely, every three-valued interpretation I = (I t , I f ) = (I
+ , I
− )
gives rise to the consistent signed subset I
+ ∪ ¬I
− of X. Moreover, this correspondence is evidently one-to-one, and so I(X, T HREE) can be identified
with the set of all consistent signed subsets of X, and we will quite frequently
use this fact later on without further notice. Indeed, in this representation,
we have I [ k K if and only if I
+ ∪ ¬I
− ⊆ K
+ ∪ ¬K
− , and so [ k corresponds
to subset inclusion of signed subsets, and, furthermore, the bottom element is
the empty set thought of as a consistent signed subset of X.
Now let X denote a set of atoms in a first-order language L, and let I be
a three-valued interpretation viewed as a consistent signed subset of X. For
a literal L = A, where A is an atom, we write L ∈ I if A ∈ I, and we write
¬L ∈ I if ¬A ∈ I. Similarly, if L = ¬A, we write L ∈ I if ¬A ∈ I, and we
Order and Logic
Notice that the difference in the form of the statements in (b) and (c) in
Theorem 1.3.6 concerning the truth ordering [ t results from the fact that [ t
is a total order in (b), but it is not a total order in (c).
In all cases we are currently considering, except one, we are working in a
complete lattice. Hence, the valuation mapping each element of X to the appropriate top element is itself a top element. The one exception is the case of
three-valued interpretations in the order [ k . In this case, it is clear that those
interpretations I = (I t , I f ) for which I t ∪ I f = X are maximal elements for
the ordering [ k . Moreover, each maximal element I = (I t , I f ) gives rise to the
two-valued interpretation I t , and, conversely, each two-valued interpretation
I gives rise to a maximal three-valued interpretation (I, X \ I). Moreover, this
correspondence is evidently one-to-one. Thus, the two-valued interpretations
can be thought of as maximal three-valued interpretations. Indeed, the maximal elements are called total interpretations, while the remaining elements
are called partial interpretations.
1.3.3 Signed Sets and Three-Valued Interpretations
As mentioned in Remark 1.3.1, there is an alternative and useful way of
thinking of three-valued interpretations relative to the ordering [ k (so that u
is the current default value in the representation of interpretations as pairs of
sets), and we consider it next.
Let X denote an arbitrary set, and form the set ¬X of symbols ¬ x for
x ∈ X. If X happens to be a set of atoms or of literals, then ¬x is meaningful;
otherwise, we are working formally. In any case, we assume that x and ¬x
are never equal. Given a subset I of X, we let ¬I denote the subset of ¬X
consisting of those ¬ x for x ∈ I. A subset of X ∪ ¬X is called a signed subset
of X and is called consistent if it does not contain both x and ¬x for any x.
Clearly, any signed subset of X has the form I
+ ∪ ¬I
− , where I
+ and I
− are
subsets of X, and is consistent if and only if I
+ and I
− are disjoint.
Every consistent signed subset I = I
+ ∪ ¬I
− of X gives rise to the threevalued interpretation (I
+ , I
− ). Then, thinking of I as this three-valued interpretation, we have I t = I
+ = {x ∈ X | x ∈ I} and I f = I
− = {x ∈ X |
¬x ∈ I}. Conversely, every three-valued interpretation I = (I t , I f ) = (I
+ , I
− )
gives rise to the consistent signed subset I
+ ∪ ¬I
− of X. Moreover, this correspondence is evidently one-to-one, and so I(X, T HREE) can be identified
with the set of all consistent signed subsets of X, and we will quite frequently
use this fact later on without further notice. Indeed, in this representation,
we have I [ k K if and only if I
+ ∪ ¬I
− ⊆ K
+ ∪ ¬K
− , and so [ k corresponds
to subset inclusion of signed subsets, and, furthermore, the bottom element is
the empty set thought of as a consistent signed subset of X.
Now let X denote a set of atoms in a first-order language L, and let I be
a three-valued interpretation viewed as a consistent signed subset of X. For
a literal L = A, where A is an atom, we write L ∈ I if A ∈ I, and we write
¬L ∈ I if ¬A ∈ I. Similarly, if L = ¬A, we write L ∈ I if ¬A ∈ I, and we