xx
Introduction
This book is concerned with the theory of logic programming languages
or, in other words, with their syntax and their semantics, especially the latter.
Very briefly, syntax in this context deals with formal grammar and automated
deduction, as discussed earlier; semantics, as usual, is occupied with meaning.
We will discuss semantics in more detail next. However, it should be observed
straightaway that the semantics of logic programming languages is complicated in a way which is peculiar to them by the introduction of negation into
their syntax. The manner in which one handles negation is important, and
it is worth remarking that its development in logic programming has been
much influenced by the development of negation in non-monotonic reasoning,
a subject familiar in the field of artificial intelligence. Therefore, it will be
helpful to say a little about negation in these terms before describing in detail the precise objectives of the book and its contents. This is because our
treatment of negation and semantics, see Chapter 2, is partly guided by these
considerations and also because negation and semantics are central themes of
the book.
Non-monotonic reasoning came into existence as a result of the desire to
capture certain aspects of human commonsense reasoning based on the observation that, in many situations occurring in everyday life, humans can reach
conclusions under incomplete or uncertain knowledge. More formally, it is typically the case that more facts can be derived from given facts or knowledge
when using commonsense reasoning than is the case when first-order logic is
employed. This has the consequence that some conclusions already made may
have to be withdrawn when more facts become known. By contrast, classical
logics such as propositional or predicate logic are monotonic in that whenever
a formula F is entailed by a theory or set of formulas Γ, then Γ ∪ {G} still
entails F , for any formula G.
The non-monotonic aspect of commonsense reasoning, however, has turned
out to be rather difficult to formalize in a satisfactory way. Early work in
this area was mainly based on three entirely different approaches
2 : John
McCarthy’s circumscription, see [McCarthy, 1977, McCarthy, 1980]; Robert
Moore’s autoepistemic logic, see [Moore, 1984, Moore, 1985]; and Ray Reiter’s default logic, see [Reiter, 1980]. In fact, Prolog naturally includes some
features which can be viewed as being non-monotonic: if the system can prove
that a certain fact A does not follow from a given knowledge base, or program,
then A is considered to be false and hence ¬A is considered to be true. However, by adding the fact A to the program, we can now prove A, and thus we
have to retract the earlier conclusion ¬A. (Note that the negation occurring
in ¬A should not necessarily be taken here to be the negation encountered,
say, in first-order logic, but rather it symbolizes negation as (finite) failure to
prove A, as introduced in [Clark, 1978].)
2 See [Gabbay et al., 1994] for an excellent account of some of the main approaches to
non-monotonic reasoning including discussions of their advantages and drawbacks, and of
the validity of the intuitions underlying non-monotonic reasoning. Introductory textbooks
are [Antoniou, 1996, Berzati, 2007, Makinson, 2005].
Introduction
This book is concerned with the theory of logic programming languages
or, in other words, with their syntax and their semantics, especially the latter.
Very briefly, syntax in this context deals with formal grammar and automated
deduction, as discussed earlier; semantics, as usual, is occupied with meaning.
We will discuss semantics in more detail next. However, it should be observed
straightaway that the semantics of logic programming languages is complicated in a way which is peculiar to them by the introduction of negation into
their syntax. The manner in which one handles negation is important, and
it is worth remarking that its development in logic programming has been
much influenced by the development of negation in non-monotonic reasoning,
a subject familiar in the field of artificial intelligence. Therefore, it will be
helpful to say a little about negation in these terms before describing in detail the precise objectives of the book and its contents. This is because our
treatment of negation and semantics, see Chapter 2, is partly guided by these
considerations and also because negation and semantics are central themes of
the book.
Non-monotonic reasoning came into existence as a result of the desire to
capture certain aspects of human commonsense reasoning based on the observation that, in many situations occurring in everyday life, humans can reach
conclusions under incomplete or uncertain knowledge. More formally, it is typically the case that more facts can be derived from given facts or knowledge
when using commonsense reasoning than is the case when first-order logic is
employed. This has the consequence that some conclusions already made may
have to be withdrawn when more facts become known. By contrast, classical
logics such as propositional or predicate logic are monotonic in that whenever
a formula F is entailed by a theory or set of formulas Γ, then Γ ∪ {G} still
entails F , for any formula G.
The non-monotonic aspect of commonsense reasoning, however, has turned
out to be rather difficult to formalize in a satisfactory way. Early work in
this area was mainly based on three entirely different approaches
2 : John
McCarthy’s circumscription, see [McCarthy, 1977, McCarthy, 1980]; Robert
Moore’s autoepistemic logic, see [Moore, 1984, Moore, 1985]; and Ray Reiter’s default logic, see [Reiter, 1980]. In fact, Prolog naturally includes some
features which can be viewed as being non-monotonic: if the system can prove
that a certain fact A does not follow from a given knowledge base, or program,
then A is considered to be false and hence ¬A is considered to be true. However, by adding the fact A to the program, we can now prove A, and thus we
have to retract the earlier conclusion ¬A. (Note that the negation occurring
in ¬A should not necessarily be taken here to be the negation encountered,
say, in first-order logic, but rather it symbolizes negation as (finite) failure to
prove A, as introduced in [Clark, 1978].)
2 See [Gabbay et al., 1994] for an excellent account of some of the main approaches to
non-monotonic reasoning including discussions of their advantages and drawbacks, and of
the validity of the intuitions underlying non-monotonic reasoning. Introductory textbooks
are [Antoniou, 1996, Berzati, 2007, Makinson, 2005].