152
Mathematical Aspects of Logic Programming Semantics
noted, interpretations will be three-valued, and therefore I P here means I P,3
ordered using the knowledge ordering introduced in Section 1.3.2.
5.2.1 Fitting Operators Revisited
We begin with an alternative characterization of the Fitting operator,
which is amenable to generalization in various logics. It involves a program
transformation which we will introduce next. Later on in Section 5.4, we will
consider further generalizations of Fitting operators, called Fitting-style operators, see Definition 5.4.9.
Let P be a program and suppose that A ∈ B P is the head of some clause
in ground(P ). Now let {A ← body i | i ∈ Λ} be the set of all clauses with head
o
A in ground(P ), where Λ is a suitable index set. We call A ←
body i
o
i∈Λ
the pseudo-clause associated with A, we call body A =
body i the body
i∈Λ
of the pseudo-clause, and we call A its head . As a matter of notation, we
may sometimes denote body i by C i , and hence we may sometimes denote by
o
o
A ←
C i or even more simply by A ← C i the pseudo-clause associated
i∈Λ
with A.
Notice that the family {body i | i ∈ Λ} of bodies may be denumerable and
o
that
body i is formal at this stage. Nevertheless, we next assign truth
i∈Λ
values to bodies of pseudo-clauses with respect to an interpretation in certain three-valued logics
8 and in more generality in Theorem 5.5.1 and in Seco
tion 7.6. If
body i is such a body, then body i is a (finite) conjunction for
i∈Λ
any i and can be evaluated as usual by means of truth tables for conjunction.
We will consider three different conjunctions and two different disjunctions,
all as given by the truth tables in Table 5.1 on Page 153. Note that ∧ 1 and ∨ 1
are exactly the conjunction and disjunction from Kleene’s strong three-valued
logic, specified earlier as a sublogic of Belnap’s logic in Table 1.1, and already
employed in Section 2.4 in evaluating truth values of clause bodies.
With respect to ∨ 1 , a disjunction p ∨ 1 q is false if and only if both p and
q are false, is true if and only if one of p and q is true, and is undefined
otherwise. We use this as a definition of truth values for bodies of pseudoclauses. Therefore, with respect to ∨ 1 :
o
the body
body i of a pseudo-clause is false if and only if
i∈Λ
all of the body i are false, is true if and only if one of the body i
is true, and is undefined otherwise.
With respect to ∨ 2 , a disjunction p ∨ 2 q is false if and only if both p and q
are false, is undefined if one of p and q is undefined, and is true otherwise.
Therefore, with respect to ∨ 2 :
o
the body
body i of a pseudo-clause is false if and only if
i∈Λ
8 Strictly speaking, we discuss different truth tables for logical connectives – or rather
different connectives – over three truth values over the same underlying language. It will be
convenient to think in terms of different logics, however.
Mathematical Aspects of Logic Programming Semantics
noted, interpretations will be three-valued, and therefore I P here means I P,3
ordered using the knowledge ordering introduced in Section 1.3.2.
5.2.1 Fitting Operators Revisited
We begin with an alternative characterization of the Fitting operator,
which is amenable to generalization in various logics. It involves a program
transformation which we will introduce next. Later on in Section 5.4, we will
consider further generalizations of Fitting operators, called Fitting-style operators, see Definition 5.4.9.
Let P be a program and suppose that A ∈ B P is the head of some clause
in ground(P ). Now let {A ← body i | i ∈ Λ} be the set of all clauses with head
o
A in ground(P ), where Λ is a suitable index set. We call A ←
body i
o
i∈Λ
the pseudo-clause associated with A, we call body A =
body i the body
i∈Λ
of the pseudo-clause, and we call A its head . As a matter of notation, we
may sometimes denote body i by C i , and hence we may sometimes denote by
o
o
A ←
C i or even more simply by A ← C i the pseudo-clause associated
i∈Λ
with A.
Notice that the family {body i | i ∈ Λ} of bodies may be denumerable and
o
that
body i is formal at this stage. Nevertheless, we next assign truth
i∈Λ
values to bodies of pseudo-clauses with respect to an interpretation in certain three-valued logics
8 and in more generality in Theorem 5.5.1 and in Seco
tion 7.6. If
body i is such a body, then body i is a (finite) conjunction for
i∈Λ
any i and can be evaluated as usual by means of truth tables for conjunction.
We will consider three different conjunctions and two different disjunctions,
all as given by the truth tables in Table 5.1 on Page 153. Note that ∧ 1 and ∨ 1
are exactly the conjunction and disjunction from Kleene’s strong three-valued
logic, specified earlier as a sublogic of Belnap’s logic in Table 1.1, and already
employed in Section 2.4 in evaluating truth values of clause bodies.
With respect to ∨ 1 , a disjunction p ∨ 1 q is false if and only if both p and
q are false, is true if and only if one of p and q is true, and is undefined
otherwise. We use this as a definition of truth values for bodies of pseudoclauses. Therefore, with respect to ∨ 1 :
o
the body
body i of a pseudo-clause is false if and only if
i∈Λ
all of the body i are false, is true if and only if one of the body i
is true, and is undefined otherwise.
With respect to ∨ 2 , a disjunction p ∨ 2 q is false if and only if both p and q
are false, is undefined if one of p and q is undefined, and is true otherwise.
Therefore, with respect to ∨ 2 :
o
the body
body i of a pseudo-clause is false if and only if
i∈Λ
8 Strictly speaking, we discuss different truth tables for logical connectives – or rather
different connectives – over three truth values over the same underlying language. It will be
convenient to think in terms of different logics, however.