逻辑编程与Prolog第二版：基础与实践

需积分: 11 92 浏览量更新于2024-07-17 收藏 2.35MB PDF 举报

《逻辑、编程与Prolog（第二版）》是一本由Ulf Nilsson和Jan Maluszynski合著的著作，首次出版于1990年，并在1995年推出了第二版。该书版权于2000年11月回归作者。本书的核心内容涵盖了逻辑、编程和Prolog语言的基础理论，特别适合人工智能领域的学习者和研究者。在第一部分“基础”中，作者首先介绍了逻辑公式的基础概念（第1章）。他们讨论了逻辑公式的形式结构，包括基本的逻辑运算符如否定、联结词以及命题的组合方式。理解这些概念对于构建和解析复杂的逻辑推理至关重要。接着，作者探讨了公式的语义（第1.2节），即如何将逻辑表达式赋予实际的意义。这包括解释变量、常量、以及函数如何在不同的上下文中解读。这部分强调了逻辑表达式的实际应用，而非仅仅停留在符号层面。然后，作者深入讨论了模型和逻辑蕴涵（第1.3节）。模型是逻辑系统中的抽象表示，用来表示可能的世界状态。逻辑蕴涵则描述了当一个公式可以从另一个公式推导出来时，它们之间的关系。这是逻辑推理的核心，它帮助读者理解如何从已知事实推出新的结论。第1.4节讲述了逻辑推理，即通过逻辑规则进行推论的过程。这里涉及的方法包括演绎推理，从普遍原理推导出特定实例，以及归纳推理，从个别案例总结一般规律。Prolog语言就是基于这样的推理机制，被设计用于自动化解决问题。此外，由于版权问题，本书规定了使用限制：个人只能下载和打印文本，但不得进行任何形式的修改，同时必须保留版权声明。纸质形式的复制和分发仅限于非营利目的，电子形式的存储和分发则被禁止。读者可以通过书的官方网站（<http://www.ida.liu.se/~ulfni/lpp>）获取更新信息和补充材料，或直接联系作者获取更多信息。《逻辑、编程与Prolog（第二版）》是一本实用且深入的教材，对理解逻辑基础、掌握编程技巧以及学习Prolog语言有着重要的指导作用。通过阅读这本书，读者能够建立起坚实的逻辑思维框架，并探索人工智能领域中Prolog语言的独特魅力。

4 Chapter 1: Preliminaries

which permits inferring (iii) from (i)and(ii) — must be carefully formalized. Such

problems have been studied in the ﬁeld of mathematical logic. This chapter surveys

basic logical concepts that are used later on in the book to relate logic programming

and logic. (For basic set theoretic notions see Appendix B.)

The ﬁrst concept considered is that of logic formulas which provide a formalized syn-

tax for writing sentences like (i)–(iii ). Such sentences refer to individuals in some

world and to relations between those individuals. Therefore the starting point is an

assumption about the alphabet of the language. It must include:

• symbols for denoting individuals (e.g. the symbol tom may be used to denote

the person Tom of our example). Such symbols will be called constants;

• symbols for denoting relations (loves, mother, child of ). Such symbols are called

predicate symbols.

Every predicate symbol has an associated natural number, called its arity. The relation

named by an n-ary predicate symbol is a set of n-tuples of individuals; in the example

above the predicate symbol loves denotes a set of pairs of persons, including the pair

Mary and Tom, denoted by the constants mary and tom.

With the alphabet of constants, predicate symbols and some auxiliary characters,

sentences of natural language like “Mary loves Tom” can be formalized as formulas

like loves(mary, tom).

The formal language should also provide the possibility of expressing sentences like

(i) which refers to all elements of the described “world”. This sentence says that “for

all individuals X and Y, if X is a mother and Y is a child of X then X loves Y”. For

this purpose, the language of logic introduces the symbol of universal quantiﬁer “∀”

(toberead“forevery”or“forall”)andthealphabetofvariables. A variable is a

symbol that refers to an unspeciﬁed individual, like X and Y above. Now the sentences

(i)–(iii) can be formalized accordingly:

∀X (∀Y ((mother(X) ∧child of (Y,X)) ⊃ loves(X, Y ))) (1)

mother(mary) ∧ child of (tom, mary)(2)

loves(mary, tom)(3)

The symbols “∧”and“⊃” are examples of logical connectives which are used to com-

bine logic formulas — “∧” reads “and” and is called conjunction whereas “⊃” is called

implication and corresponds to the “if-then” construction above. Parentheses are used

to disambiguate the language.

Another connective which will be used frequently is that for expressing negation.

It is denoted by “¬” (with reading “not”). For example the sentence “Tom does not

love Mary” can be formalized as the formula:

¬loves(tom, mary)

In what follows the symbol “∃” is also sometimes used. It is called the existential quan-

tiﬁer and reads “there exists”. The existential quantiﬁer makes it possible to express

the fact that, in the world under consideration, there exists at least one individual

www.aibbt.com 让未来触手可及

1.1 Logic Formulas 5

which is in a certain relation with some other individuals. For example the sentence

“Mary has a child” can be formalized as the formula:

∃X child of (X, mary)

On occasion the logical connectives “∨”and“↔” are used. They formalize the con-

nectives “or” and “if and only if” (“iﬀ”).

So far individuals have been represented only by constants. However it is often

the case that in the world under consideration, some “individuals” are “composed

objects”. For instance, in some world it may be necessary to discuss relations between

families as well as relations between persons. In this case it would be desirable to

refer to a given family by a construction composed of the constants identifying the

members of the family (actually what is needed is a function that constructs a family

from its members). The language of logic oﬀers means of solving this problem. It is

assumed that its alphabet contains symbols called functors that represent functions

over object domains. Every functor has assigned a natural number called its arity,

which determines the number of arguments of the function. The constants can be

seen as 0-ary functors. Assume now that there is a ternary

functor family, a binary

functor child and a constant none. The family consisting of the parents Bill and Mary

and children Tom and Alice can now be represented by the construction:

family(bill, mary, child(tom, child (alice, none)))

Such a construction is called a compound term.

The above informal discussion based on examples of simple declarative sentences gives

motivation for introducing basic constructs of the language of symbolic logic. The kind

of logic used here is called predicate logic. Next a formal deﬁnition of this language

is given. For the moment we specify only the form of allowed sentences, while the

meaning of the language will be discussed separately. Thus the deﬁnition covers only

the syntax of the language separated from its semantics.

From the syntactic point of view logic formulas are ﬁnite sequences of symbols such

as variables, functors and predicate symbols. There are inﬁnitely many of them and

therefore the symbols are usually represented by ﬁnite strings of primitive characters.

The representation employed in this book usually conforms to that speciﬁed in the

ISO standard of the programming language Prolog (1995). Thus, the alphabet of the

language of predicate logic consists of the following classes of symbols:

• variables which will be written as alphanumeric identiﬁers beginning with capital

letters (sometimes subscriped). Examples of variables are X,Xs,Y,X

,...;

• constants which are numerals or alphanumeric identiﬁers beginning with lower-

case letters. Examples of constants are x, alf ,none,17,...;

• functors which are alphanumeric identiﬁers beginning with lower-case letters

and with an associated arity > 0. To emphasize the arity n of a functor f it is

sometimes written in the form f/n;

Usually the terms nullary, unary, binary and ternary are used instead of 0-ary, 1-ary, 2-ary and

3-ary.

www.aibbt.com 让未来触手可及

6 Chapter 1: Preliminaries

• predicate symbols which are usually alphanumeric identiﬁers starting with lower-

case letters and with an associated arity ≥ 0. The notation p/n is used also for

predicate symbols;

• logical connectives which are ∧ (conjunction), ¬ (negation), ↔ (logical equiva-

lence), ⊃ (implication) and ∨ (disjunction);

• quantiﬁers — ∀ (universal) and ∃ (existential);

• auxiliary symbols like parentheses and commas.

No syntactic distinction will be imposed between constants, functors and predicate

symbols. However, as a notational convention we use a,b,c,... (with or without

adornments) to denote constants and X,Y,Z,... to denote variables. Functors are

denoted f,g,h,... and p,q,r,... are used to denote predicate symbols. Constants

are sometimes viewed as nullary functors. Notice also that the sets of functors and

predicate symbols may contain identical identiﬁers with diﬀerent arities.

Sentences of natural language consist of words where objects of the described world

are represented by nouns. In the formalized language of predicate logic objects will

be represented by strings called terms whose syntax is deﬁned as follows:

Deﬁnition 1.1 (Terms) The set T of terms over a given alphabet A is the smallest

set such that:

• any constant in A is in T ;

• any variable in A is in T ;

• if f/n is a functor in A and t

,...,t

∈T then f(t

,...,t

) ∈T.

In this book terms are typically denoted by s and t.

In natural language only certain combinations of words are meaningful sentences.

The counterpart of sentences in predicate logic are special constructs built from terms.

These are called formulas or well-formed formulas (wﬀ ) and their syntax is deﬁned as

follows:

Deﬁnition 1.2 (Formulas) Let T be the set of terms over the alphabet A.Theset

F of wﬀ (with respect to A) is the smallest set such that:

• if p/n is a predicate symbol in A and t

,...,t

∈T then p(t

,...,t

) ∈F;

• if F and G ∈Fthen so are (¬F ), (F ∧G), (F ∨ G), (F ⊃ G)and(F ↔ G);

• if F ∈Fand X is a variable in A then (∀XF)and(∃XF) ∈F.

Formulas of the form p(t

,...,t

) are called atomic formulas (or simply atoms).

In order to adopt a syntax similar to that of Prolog, formulas in the form (F ⊃ G)

are instead written in the form (G ← F ). To simplify the notation parentheses will be

removed whenever possible. To avoid ambiguity it will be assumed that the connectives

www.aibbt.com 让未来触手可及

1.2 Semantics of Formulas 7

have a binding-order where ¬, ∀ and ∃ bind stronger than ∨, which in turn binds

stronger than ∧ followed by ⊃ (i.e. ←) and ﬁnally ↔.Thus(a ← ((¬b) ∧ c)) will

be simpliﬁed into a ←¬b ∧ c. Sometimes binary functors and predicate symbols are

written in inﬁx notation (e.g. 2 ≤ 3).

Let F be a formula. An occurrence of the variable X in F is said to be bound

either if the occurrence follows directly after a quantiﬁer or if it appears inside the

subformula which follows directly after “∀X”or“∃X”. Otherwise the occurrence is

said to be free. A formula with no free occurrences of variables is said to be closed.A

formula/term which contains no variables is called ground.

Let X

,...,X

be all variables that occur free in a formula F . The closed formula

of the form ∀X

(...(∀X

F ) ...) is called the universal closure of F and is denoted

∀ F . Similarly, ∃ F is called the existential closure of F and denotes the formula F

closed under existential quantiﬁcation.

1.2 Semantics of Formulas

The previous section introduced the language of formulas as a formalization of a class

of declarative statements of natural language. Such sentences refer to some “world”

and may be true or false in this world. The meaning of a logic formula is also deﬁned

relative to an “abstract world” called an (algebraic) structure and is also either true or

false. In other words, to deﬁne the meaning of formulas, a formal connection between

the language and a structure must be established. This section discusses the notions

underlying this idea.

As stated above declarative statements refer to individuals, and concern relations

and functions on individuals. Thus the mathematical abstraction of the “world”, called

a structure, is a nonempty set of individuals (called the domain) with a number of

relations and functions deﬁned on this domain. For example the structure referred

to by the sentences (i)–(iii ) may be an abstraction of the world shown in Figure 1.1.

Its domain consists of three individuals — Mary, John and Tom. Moreover, three

relations will be considered on this set: a unary relation, “. . . is a mother”, and two

binary relations, “... is a child of ...” and “... loves ...”. For the sake of simplicity

it is assumed that there are no functions in the structure.

The building blocks of the language of formulas are constants, functors and pred-

icate symbols. The link between the language and the structure is established as

follows:

Deﬁnition 1.3 (Interpretation) An interpretation = of an alphabet A is a non-

empty domain D (sometimes denoted |=|) and a mapping that associates:

• each constant c ∈Awith an element c

∈D;

• each n-ary functor f ∈Awith a function f

: D

→D;

• each n-ary predicate symbol p ∈Awith a relation p

⊆D×···×D

| {z }

The interpretation of constants, functors and predicate symbols provides a basis for

assigning truth values to formulas of the language. The meaning of a formula will be

www.aibbt.com 让未来触手可及

剩余293页未读，继续阅读

Liang2000_ok

粉丝: 0
资源: 23

逻辑编程与Prolog第二版：基础与实践

Logic.Programming.with.Prolog

Logic_Programming_with_Prolog

Logic.Programming.In.Prolog.Using.The.ISO.Standard

逻辑，编程和序言，第二版Logic, Programming and Prolog, Second Edition

prolog.rar_logic programming_prolog_prolog intelligence_人工智能_人工智

序言和逻辑程序设计Prolog and Logic Programming

An Introduction to Logic Programming through Prolog

prolog.rar_pdf_programming_prolog_software

HPL: Vol. IV: Functional and Logic Programming Languages

通过Prolog进行逻辑编程的简介An Introduction to Logic Programming Through Prolog

最新资源