28
Mathematical Aspects of Logic Programming Semantics
Indeed, many authors even define a logic program to be a set of propositional
clauses, with the advantage that notation can be considerably eased in some
places. For many of the example programs which we will discuss later, we will
also take advantage of this simpler notation, as in the following.
2.1.7 Program Let P be the following program.
p ← ¬q
q ← ¬p
Then B P = {p, q} and ground(P ) = P . Preinterpretations play no role in this
case.
We now come to the fundamental notions of interpretation and model
for programs. Interpretations and models as defined next are the particular
forms of Definitions 1.2.7 and 1.2.8 that we will use henceforth in studying
the semantics of programs.
2.1.8 Definition Let P be a program, let J be a preinterpretation for P
with domain D, and let T be a logic. An interpretation or valuation for P
(based on J) with values in T is an interpretation or valuation defined on
B P,J with values in T . An interpretation I for P is a model for P if I(C) = t
for each clause C ∈ ground J (P ). As in Definition 1.2.8, we sometimes refer
to valuations, interpretations, and models for P based on J as J-valuations,
J-interpretations, and J-models, respectively.
We will in future use the notation I P,J,2 for the set of all two-valued interpretations for P based on J. As usual, reference to the preinterpretation
J will often be omitted if it is fixed and understood. Similarly, the number
2 will be omitted if it is understood, and hence the set of all two-valued interpretations for P based on a given, fixed preinterpretation J will often be
denoted by I P,2 or just by I P . Similar comments apply to the set I P,J,3 of
all three-valued interpretations for P based on J and to the set I P,J,4 of all
four-valued interpretations for P based on J.
The three sets just defined have the order-theoretic structure described in
Theorem 1.3.4 relative to the orders we discussed in Chapter 1. In particular,
I P,2 can be identified with the power set of B P .
With these structures in place, we are now ready to begin the main subject
of our study in this chapter, namely, the semantics of logic programs.
2.2 Supported Models
As already noted, a declarative semantics for logic programs is usually
given by selecting models for the programs which satisfy certain desirable
Mathematical Aspects of Logic Programming Semantics
Indeed, many authors even define a logic program to be a set of propositional
clauses, with the advantage that notation can be considerably eased in some
places. For many of the example programs which we will discuss later, we will
also take advantage of this simpler notation, as in the following.
2.1.7 Program Let P be the following program.
p ← ¬q
q ← ¬p
Then B P = {p, q} and ground(P ) = P . Preinterpretations play no role in this
case.
We now come to the fundamental notions of interpretation and model
for programs. Interpretations and models as defined next are the particular
forms of Definitions 1.2.7 and 1.2.8 that we will use henceforth in studying
the semantics of programs.
2.1.8 Definition Let P be a program, let J be a preinterpretation for P
with domain D, and let T be a logic. An interpretation or valuation for P
(based on J) with values in T is an interpretation or valuation defined on
B P,J with values in T . An interpretation I for P is a model for P if I(C) = t
for each clause C ∈ ground J (P ). As in Definition 1.2.8, we sometimes refer
to valuations, interpretations, and models for P based on J as J-valuations,
J-interpretations, and J-models, respectively.
We will in future use the notation I P,J,2 for the set of all two-valued interpretations for P based on J. As usual, reference to the preinterpretation
J will often be omitted if it is fixed and understood. Similarly, the number
2 will be omitted if it is understood, and hence the set of all two-valued interpretations for P based on a given, fixed preinterpretation J will often be
denoted by I P,2 or just by I P . Similar comments apply to the set I P,J,3 of
all three-valued interpretations for P based on J and to the set I P,J,4 of all
four-valued interpretations for P based on J.
The three sets just defined have the order-theoretic structure described in
Theorem 1.3.4 relative to the orders we discussed in Chapter 1. In particular,
I P,2 can be identified with the power set of B P .
With these structures in place, we are now ready to begin the main subject
of our study in this chapter, namely, the semantics of logic programs.
2.2 Supported Models
As already noted, a declarative semantics for logic programs is usually
given by selecting models for the programs which satisfy certain desirable