24
Mathematical Aspects of Logic Programming Semantics
where l, n ∈ N; A is an atom in L; L 1 , . . . , L n are literals in L; and x 1 , . . . , x l
are all the variable symbols occurring in the formula. We will follow common
practice and abbreviate such a clause by writing simply
A ← L 1 , . . . , L n ,
so that the universal quantifiers are understood, and the conjunction symbol
∧ is replaced by a comma. The atom A is called the head of the clause, and
the conjunction L 1 , . . . , L n is called the body of the clause; the literals L i ,
i = 1, . . . , n, in the body L 1 , . . . , L n are called body literals. If a body literal
L is an atom B, say, then we say that B occurs positively in the body of the
clause. If L is a negated atom ¬B, then we say that B occurs negatively in
the body of the clause. By an abuse of notation, we allow n = 0, by which we
mean that the body can be empty, and in this case the clause A ←, or simply
A, is also called a unit clause or a fact. It will sometimes be convenient to
further abbreviate a clause by writing
A ← body,
wherein body denotes the body of the clause. Furthermore, we will use body
not only to denote a conjunction of literals, but also to denote the corresponding set containing these literals. This further abuse of notation will substantially ease matters in some places and will not cause confusion. Note that in
doing this, we are ignoring the ordering of the literals in clause bodies. This will
not matter most of the time, since we are not much concerned with procedural
matters, as already noted, and for this reason we often denote a typical clause
by A ← A 1 , . . . , A n , ¬B 1 , . . . , ¬B k , say, where all the A i , i = 1, . . . , n, and all
the B j , j = 1, . . . , k, are atoms in L. Notice that we allow ourselves a bit of
latitude in the subscripts we employ in writing down clauses, and, for example,
the roles of n in the clause just considered and in the clause A ← L 1 , . . . , L n
above are not identical in general, unless there are no negated atoms present,
of course.
A normal logic program is a finite set of clauses. A definite logic program
is a normal logic program in which no negation symbols occur. The term
program will subsequently always mean a normal program. Definite programs
are sometimes called positive programs, and obviously every definite program
is a normal program. A propositional logic program is a program in which all
predicate symbols are of arity zero.
•
In most cases, the underlying first-order language, or simply the underlying
language, L P of a program P will not be given explicitly, but will be understood to be the (first-order) language generated by the constant, variable,
function, and predicate symbols occurring in P . However, when P does not
contain any constant symbols, we add one to L P , so that the underlying language always contains at least one constant symbol. Propositional programs
Mathematical Aspects of Logic Programming Semantics
where l, n ∈ N; A is an atom in L; L 1 , . . . , L n are literals in L; and x 1 , . . . , x l
are all the variable symbols occurring in the formula. We will follow common
practice and abbreviate such a clause by writing simply
A ← L 1 , . . . , L n ,
so that the universal quantifiers are understood, and the conjunction symbol
∧ is replaced by a comma. The atom A is called the head of the clause, and
the conjunction L 1 , . . . , L n is called the body of the clause; the literals L i ,
i = 1, . . . , n, in the body L 1 , . . . , L n are called body literals. If a body literal
L is an atom B, say, then we say that B occurs positively in the body of the
clause. If L is a negated atom ¬B, then we say that B occurs negatively in
the body of the clause. By an abuse of notation, we allow n = 0, by which we
mean that the body can be empty, and in this case the clause A ←, or simply
A, is also called a unit clause or a fact. It will sometimes be convenient to
further abbreviate a clause by writing
A ← body,
wherein body denotes the body of the clause. Furthermore, we will use body
not only to denote a conjunction of literals, but also to denote the corresponding set containing these literals. This further abuse of notation will substantially ease matters in some places and will not cause confusion. Note that in
doing this, we are ignoring the ordering of the literals in clause bodies. This will
not matter most of the time, since we are not much concerned with procedural
matters, as already noted, and for this reason we often denote a typical clause
by A ← A 1 , . . . , A n , ¬B 1 , . . . , ¬B k , say, where all the A i , i = 1, . . . , n, and all
the B j , j = 1, . . . , k, are atoms in L. Notice that we allow ourselves a bit of
latitude in the subscripts we employ in writing down clauses, and, for example,
the roles of n in the clause just considered and in the clause A ← L 1 , . . . , L n
above are not identical in general, unless there are no negated atoms present,
of course.
A normal logic program is a finite set of clauses. A definite logic program
is a normal logic program in which no negation symbols occur. The term
program will subsequently always mean a normal program. Definite programs
are sometimes called positive programs, and obviously every definite program
is a normal program. A propositional logic program is a program in which all
predicate symbols are of arity zero.
•
In most cases, the underlying first-order language, or simply the underlying
language, L P of a program P will not be given explicitly, but will be understood to be the (first-order) language generated by the constant, variable,
function, and predicate symbols occurring in P . However, when P does not
contain any constant symbols, we add one to L P , so that the underlying language always contains at least one constant symbol. Propositional programs