Chapter 2
The Semantics of Logic Programs
The objective of this chapter is to introduce the central topic of study in this
work, namely, logic programs, together with several of the main issues and
questions which will be addressed in later chapters. In order to ensure that
our treatment is as self-contained as possible, we will take care to formally
define all concepts which we consider in detail here and later on. In addition, to
assist the reader, we give ample references to those topics which we encounter,
but do not treat in detail.
For the course of this and subsequent chapters, our main focus will be on
declarative semantics, and, as already noted in the Introduction, issues concerning procedural aspects will play only a minor role. In particular, in this
chapter and later in Chapter 5, we will introduce some of the best known
declarative semantics for logic programs, and we will develop a uniform treatment of them applicable not only to resolution-based logic programming, but
also to non-monotonic reasoning as well.
Frequently, a declarative semantics is given by assigning intended models to
logic programs. This is done by selecting from the set of all models for a logic
program, a subset which contains those models with some properties deemed
to be desirable depending on one’s objectives and intended applications. All
the semantics which we will discuss can be described in terms of fixed points
of operators associated with logic programs, and they are all well-established.
Our new and novel contribution in this chapter is the development of a uniform
and operator-free characterization of them.
Our first task, however, is to introduce formally some of the basic concepts
and notation which will be needed throughout the sequel.
1
2.1 Logic Programs and Their Models
2.1.1 Definition Given a first-order language L, a clause, program clause,
or rule in L is a formula of the form
(∀x 1 ) . . . (∀x l )(A ← L 1 ∧ . . . ∧ L n ),
1 We follow the presentation of semantics from [Hitzler and Wendt, 2002, Hitzler, 2003b,
Hitzler and Wendt, 2005, Hitzler, 2005, Knorr and Hitzler, 2007].
23
The Semantics of Logic Programs
The objective of this chapter is to introduce the central topic of study in this
work, namely, logic programs, together with several of the main issues and
questions which will be addressed in later chapters. In order to ensure that
our treatment is as self-contained as possible, we will take care to formally
define all concepts which we consider in detail here and later on. In addition, to
assist the reader, we give ample references to those topics which we encounter,
but do not treat in detail.
For the course of this and subsequent chapters, our main focus will be on
declarative semantics, and, as already noted in the Introduction, issues concerning procedural aspects will play only a minor role. In particular, in this
chapter and later in Chapter 5, we will introduce some of the best known
declarative semantics for logic programs, and we will develop a uniform treatment of them applicable not only to resolution-based logic programming, but
also to non-monotonic reasoning as well.
Frequently, a declarative semantics is given by assigning intended models to
logic programs. This is done by selecting from the set of all models for a logic
program, a subset which contains those models with some properties deemed
to be desirable depending on one’s objectives and intended applications. All
the semantics which we will discuss can be described in terms of fixed points
of operators associated with logic programs, and they are all well-established.
Our new and novel contribution in this chapter is the development of a uniform
and operator-free characterization of them.
Our first task, however, is to introduce formally some of the basic concepts
and notation which will be needed throughout the sequel.
1
2.1 Logic Programs and Their Models
2.1.1 Definition Given a first-order language L, a clause, program clause,
or rule in L is a formula of the form
(∀x 1 ) . . . (∀x l )(A ← L 1 ∧ . . . ∧ L n ),
1 We follow the presentation of semantics from [Hitzler and Wendt, 2002, Hitzler, 2003b,
Hitzler and Wendt, 2005, Hitzler, 2005, Knorr and Hitzler, 2007].
23