人工智能原理与应用 教案

人工智能原理与应用

PrinciplesandApplicationofArtificialIntelligence

课程简介

本课程主要讲述人工智能的基本概念、基本方法，会用搜索算法、

推理方法和机器学习求解简单问题，如证明定理、机器推理、建造简

单的专家系统，自然语言分析和理解。

要求

工了解人工智能的提出，儿种智能观，人工智能重要的研究领域，以

及人工智能求解问题的方法与传统的数学方法的不同；

工掌握启发式搜索概念，会用搜索方法求解简单问题

人掌握归结推理方法，会用归结法证明定理，求解问题。

上掌握一种不确定推理方法，会建造带有不确定推理的专家系统。

上了解其它的推理方法；

上掌握知识的表示方法，会用来表达某一具体的场景；

工掌握机器学习概念和学习模型，会用实例学习方法进行学习，

工了解数据挖掘的过程，会用关联规则挖掘算法做数据挖掘；

L掌握自然语言理解的过程，会用基本的切分和语法分析方法做自然

语句分析；

工理解神经网络实现智能的另一种观点。掌握BP神经网的工作原理,

会用来求解（如识别）问题；

工了解遗传算法（GA）概念及如何使用遗传算法

参考资料：

《人工智能原理与应用》，张仰森，高等教育出版社

《人工智能》，蔡自兴

《人工智能原理》，石纯一黄昌宁王家钦编著，清华大学出版社

《人工智能》（上下册），陆汝铃编著，科学出版社，1996

《人工智能与知识工程》，田盛丰、黄厚宽，中国铁道出版社，1999

《高级人工智能》，史忠植，科学出版社，1998

《人工智能基础》，高济、朱森良、何钦铭，高等教育出版社，2002

第一章人工智能概述

1.1人工智能的起源与发展

＞计算机所能处理对象的改变：纯粹数值计算T非数值计算（自然语言理解、

图象语音识别、专家系统、机器博弈系统等等符号知识处理）

＞试探性搜索、启发式搜索、不确定性推理方法更符合人类思维过程。也就是

说在解决这类问题时，没有算法解或即使有算法解但在当今计算技术不能实

现。对这类问题可行的解决方法是搜索、试探，加上经验的启发式知识。这

是一种来自专门领域的经验知识，限于特定场合，经常会取得成功但又不能

保证必然成功，常能求得有关问题的满意解答。

医生一定能根据病人的症状诊断出是何种疾病吗？我们能用传统的算法设

计一个程序进行疾病诊断吗？能用传统的算法设计一个程序能理解自然语言所

组成的文档的含义吗？

以上原因促使人工智能学科的诞生。

主要经历了以下几个阶段：

/孕育期（1956年以前）一一从理论、技术和物质上奠定基础

/成长期（1956—1972）——逻辑推理机程序、跳棋程序、通用问题求解

（GPS:GeneralProblemSolver）,人工智能程序设计语言LISP/PROLOG

/发展期（1972-）——知识工程、专家系统（MYCIN,探矿系统）

/学习期

1.2什么是人工智能

1.什么是人类智能？有何特点？计算机到底能不能有人类智能？

英国数学家Turing于1950提出的著名的Turing实验。

识别、推理、联想、自学习...（人脑的智能很复杂！）

计算机到底能不能有人类智能，至今没有完整的论证（人工智能是一门正在

探索和发展的学科，至今还没有完全形成完整的理论体系。目前人工智能与人

脑的智能还相差很远）

2.什么是人工智能？

人工智能简称为AI（ArtificialIntel1igence）,是研究如何制造出智能机

器或智能系统，来模拟人类智能活动、延伸人类智能的学科。

已实现的人工智能系统：

令第一个人工智能专家系统DENDRAL,能根据有机化合物的质谱数据，推断出给

有机化合物的分子结构，该系统得到甚至超过化学专家水平。该系统是由

Stanford大学的Feigenbaum领导研制成功的。

令医疗专家系统MYCIN

令探矿专家系统PROSPECTOR

令1995年美国智能机器人驾驶汽车以55km/h速度从东部一直开到西部（机器

视觉）

令1997年国际象棋大师卡斯帕罗夫与IBM深蓝巨型机上的博弈系统对弈

令自然语言理解系统

令机器翻译系统

令机器证明系统（证明了“四色问题”、数学中的定理）

1.3AI的研究途径、方法、不同学派

1.目标：

近期目标：使机器更聪明

远期目标：探讨研制智能机

2.方法、途径

令仿生学方法：对人脑思维进行生理学模拟，通过微观方法直接模拟人脑和神

经系统的结构功能

令计算机方法：利用计算机科学的观点，从宏观上模拟人的智能活动

令数学方法：建立数学模型，利用算法求解问题

令心理学方法：建立心理学模型，利用启发式程序求解问题

3.人工智能研究的各种学派及其理论

令功能模拟，符号演绎

模拟人脑的逻辑思维，将问题和知识表示成某种逻辑网络，采用符号推

演的方法，实现搜索、推理、学习等功能。这种方法目前还在使用，人工智

能研究中的很多成果都是用该方法取得的，如定理证明，自动推理，专家系

统、博弈系统等。

采用这种方法的研究者称为心理学派或逻辑学派或符号主义，代表人物

是NILSSON,本课程就是讲解这种研究方法。

令结构模拟，神经网络计算

根据人脑的生理结构和工作机理，研究和实现计算机智能。因为人脑是

由神经细胞组成的神经网络，所以该研究途径就是用人工神经元组成的人工

神经网络模型来存储信息和知识，用神经计算（数值计算）的方法实现自学

习、联想、识别和推理功能。神经网络具有高度的并行分布性。该研究方法

适于实现图象、声音信息识别。

采用这种研究途径称为生理学派或连接主义，代表人物是Newell

令行为模拟，控制进化

这种方法模拟人在控制过程中的智能活动和行为特性（自寻优，自适应，

自学习），强调“现场AI”（situatedAI）即智能系统或智能机器能与环

境交互，能对环境进行感知从而表现出智能行为，也就是说智能行为不需要

知识从而与“符号主义”相悖。

这种方法的研究者称为行为主义、进化主义或控制论学派。代表人物是

MIT的Brooks教授。

人工智能是引起争议最多的学科之一，因而各种研究学派在发展的过程

都经历了许多挫折.

・通过什么途径有效地实现智能（如符号演绎推理,知识工程,神经网络计算,

图搜索技术,不确定推理等）.

・人工智能的研究范围问题，一般认为包括:知识表示，推理技术，自然语言

理解，知识工程，计算机视觉等许多方面.引起争议的原因，第一是由于边

界不分明，某些分支与数学有交界（如定理证明，谓词逻辑），或与语言学有

交界（如自然语言理解），或与心理学有交界（如认知模型），或与电子学机

械学有交界（如计算机视觉,机器人）.第二是由于科学的发展,各分支的内

容在不断的变化.第三，随着研究工作的深入，一些传统的观念在发生变化,

例如在历史上认为数值计算发展到符号演算是AI的一个重要特征,但在近

年的研究中，计算机视觉和机器人学的研究中又回到了数值计算的现象，

提高了数学在人工智能研究中的地位.

1.4AI的研究领域

•搜索算法：状态空间图、博弈树搜索

・推理方法：归结推理、不确定性推理

・自然语言理解：不仅能识别文字而且能理解文本含义的机器系统

・模式识别（图象与语音识别）

外界信息♦感受获取电信号-一Z特征提取

•知识工程（知识获取、知识表示、知识数据库、知识运用等一系列知识处

理技术，是以知识为中心来组织智能系统）

・神经网络技术

•专家系统

知识库推理机

・机器人

1.5人工智能求解方法的特点

・AI研究的是以符号表示的知识而不是数值数据为研究对象；

•AI中采用的启发式搜索算法(HeuristicResearchAlgorithm)而不是常

规的算法(Algorithm)

・控制结构与知识是分离的

・允许出现不正确的答案

1.6人类智能和人工智能

1.人类智能特性

感知能力思维能力反应能力

2.人工智能特性

机器感知能力机器思维能力(知识表示)机器行为能力

第二章知识表示

2.1知识及其表示

1.知识的概念

Feigenbaum认为知识是经过削减、塑造、解释和转换的信息。简单地说，知

识是经过加工的信息。

Bernstein说知识是特定领域的描述、关系和过程组成。

Hayes-Roth认为知识是事实、信念和启发式规则。

知识可从(范围，目的，有效性)加以三维描述。其中知识的范围是由具体

到一般，知识的目的是由说明到指定，知识的有效性是由确定到不确定。例如

“为了证明A-B,只需证明AA〜B是不可满足的”这种知识是一般性、指示性、

确定性的。而像“桌子有四条腿”这种知识是具体的、说明性、不确定性。

知识表示是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结

构与控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示可看

成是一组描述事物的约定，以把人类知识表示成机器能处理的数据结构。

2.人工智能系统所关心的知识

一个智能程序高水平的运行需要有关的事实知识、规则知识、控制知识和元

知识。

事实:是有关问题环境的一些事物的知识，常以“•・•是•・.”的形式出现。

如事物的分类、属性、事物间关系、科学事实、客观事实等，在知识库中属于

低层的知识。如雪是白色的、鸟有翅膀、张三李四是好朋友。

规则:是有关问题中与事物的行动、动作相联系的因果关系知识，是动态的，

常以“如果...那么...”形式出现。特别是启发式规则是属于专家提供的专门

经验知识，这种知识虽无严格解释但很有用处。

控制:是有关问题的求解步骤，技巧性知识，告诉怎么做一件事。也包括当

有多个动作同时被激活时应选哪一个动作来执行的知识。

元知识:是有关知识的知识，是知识库中的高层知识。包括怎样使用规则、

解释规则、校验规则、解释程序结构等知识。

2.2逻辑表示法

对知识通过引入谓词、函数来加以形式描述，获得有关的逻辑公式，进而以

机器内部代码表示。

设在一个房间里，有一个机器人ROBOT,一个壁室ALCOVE,一个积木块BOX,

两个桌子A和Bo机器人可把积木块BOX从一种状态变换成另一种状态。

引入谓词：

TABLE(A)表示A是桌子

EMPTYHANDED(ROBOT)表示机器人双手是空的

AT(ROBOT,A)表示机器人在A旁

HOLDS(ROBOT,BOX)表示机器人拿着积木块

ON(BOX,A)表积木块BOX在A上

2.3产生式表示法

产生式是一种知识表达方法，具有和Turing机一样的表达能力。

2.3.1事实与规则的表示

事实可看成是断言一个语言变量的值或是多个语言变量间的关系的陈述句，

语言变量的值或语言变量间的关系可以是一个词。不一定是数字。如雪是白色

的，其中雪是语言变量，其值是白色的。John喜欢Mairy，其中John、Mary是

两个语言变量，两者的关系值是喜欢。

一般使用三元组(对象，属性，值)或(关系，对象1,对象2)来表示事

实，其中对象就是语言变量，若考虑不确定性就成了四元组表示(增加可信度)。

这种表示的机器内部实现就是一个表。

如事实“老李年龄是35岁”，便写成(Lee,age,35)

事实“老李、老张是朋友”，可写成(friend,Lee,Zhang)

对于规则是表示事物间的因果关系，以下列形式表示：

condition->action

condition作为前件或模式，而action称作动作或后件或结论。前件部分常

是一些事实Ai的合取，而结论常是某一事实B,如考虑不确定性，需另附可信

度度量值。

2.3.2产生式系统的组成和推理

多数较为简单的专家系统(ExpertSystem)都是以产生式表示知识的，相

应的系统称作产生式系统。

产生式系统，由知识库和推理机两部分组成。其中知识库由规则库和数据库

组成。规则库是产生式规则的集合，数据库是事实的集合。

规则是以产生式表示的。规则集蕴涵着将问题从初始状态转换解状态的那些

变换规则，规则库是专家系统的核心。规则可表成与或树形式，基于数据库中

的事实对这与或树的求值过程就是推理。

数据库中存放着初始事实、外部数据库输入的事实、中间结果事实和最后结

果事实。

推理机是一个程序，控制协调规则库与数据库的运行，包含推理方式和控制

策略。

产生式系统的推理方式有正向推理、反向推理和双向推理

正向推理：从已知事实出发，通过规则库求得结论，或称数据驱动方式。推

理过程是

规则集中的规则前件与数据库中的事实进行匹配，得匹配的规则集合。

从匹配规则集合中选择一条规则作为使用规则。

执行使用规则的后件。将该使用规则的后件送入数据库中

重复这个过程直至达到目标

具体说如数据库中含有事实A,而规则库中有规则A->B,那么这条规则便是

匹配规则，进而将后件B送入数据库中。这样可不断扩大数据库直至包含目标

便成功结束。如有多条匹配规则需从中选一条作为使用规则，不同的选择方法

直接影响着求解效率，选规则的问题称作控制策略。正向推理会得出一些与目

标无直接关系的事实，是有浪费的。

反向推理：从目标（作为假设）出发，反向使用规则，求得已知事实，或称

目标驱动方式，推理过程是：

规则集中的规则后件与目标事实进行匹配，得匹配的规则集合；

从匹配的规则集合中选择一条规则作为使用规则；

将使用规则的前件作为子目标；

重复这个过程直至各子目标均为已知事实成功结束；

如果目标明确，使用反向推理方式效率较高。

双向推理：同时使用正向推理又使用反向推理。

2.3.3产生式表示的特点

产生式表示格式固定，形式单一，规则（知识单位）间相互较为独立，没有

直接关系使知识库的建立较为容易，处理较为简单的问题是可取的。另外推理

方式单纯，也没有复杂计算。特别是知识库与推理机是分离的，这种结构给知

识的修改带来方便，无须修改程序，对系统的推理路径也容易作出解释。所以,

产生式表示知识常作为构造专家系统的第一选择的知识表示方法。

2.4语义网络表示法

逻辑表示法和产生式表示法常用于表示有关论域中各个不同状态间的关系，

然而用于表示一个事物同其各个部分间的分类知识就不方便了。槽（slot）与

填槽表示方法便于表示这种分类知识。语义网络和框架表示方法就属于其中的

两种。

2.4.1语义网络的结构

语义网络是对知识的有向图表示方法。一个语义网络是由一些以有向图表示

的三元组（结点1,弧，结点2）连接而成。

结点表示概念、事物、事件、情况等。

弧是有方向的有标注的。方向体现主次，结点1为主，结点2为辅。弧上的标

注表示结点1的属性或结点1和结点2之间的关系。

如事实“雪是白色的”，可表示成：

颜色

,雪,

A白色的

如规理“如果A那么B"，可表示成:

R

A----------------------->B

这样事实与规则的表示是相同的，区别仅是弧上的标注有别。

从逻辑表示法来看，一个语义网络相当于一组二元谓词。因为三元组（结点1,

弧，结点2）可写成P（个体1,个体2）,其中个体1、个体2对应于结点1、

结点2,而弧及其上标注的结点1与结点2的关系由谓词P来体现。

语义网络视作一种知识的单位，人脑的记忆是由存储了大量的语义网络来体现

的。而产生式表示法是以一条产生式规则作为知识的单位，而各条产生式规则

没有直接的联系。

结点间的关系有isa,a-part-of,is型

⑴ISA链用来表示具体-抽象关系，或说表示一种隶属关系，体现某种层次分类。

特点是具体层结点可继承抽象层结点的属性。

特点是part-of

2.4.2语义网络表示下的推理

语义网络表示下的推理方法不像逻辑表示法和产生式表示法的推理方法那

样明了。语义网络表示法是依匹配和继承来进行推理的。最简单的isa关系下

的推理是直接继承，如：

便有：

--------isa--------

A-------------->C

也可以将语义网络引入逻辑含义，表示出A,V,〜关系，便可以使用归结推

理法。

还有人将语义网络中的结点看成有限自动机（DFA）,为寻求几个概念间的

关系，起动相应的自动机，如有回合点便可求得解答。

2.5框架表示法

2.5.1框架理论

1975年Minsky的论文“Aframeworkforrespresentingknowledge”中提

出了框架理论。其基本观点是人脑已存储有大量典型情景，当人面临新的情景

时，就从记忆中选择一个称为框架的基本知识结构，这个框架是以前记忆的一

个知识空框，而其具体内容依新的情景而改变，对这空框的细节加工修改和补

充，形成对新情景的认识又记忆于人脑中。框架理论将框架视作的知识单位，

将一组有关的框架连接起来便形成框架系统。系统中不同框架可以有共同结点,

系统的行为由系统内框架的变化来表现的。推理过程是由框架间的协调来完成

的。

框架表示法是一种适应性强、概括性高、结构化良好、推理方式灵活又能把

陈述性知识与过程性知识相结合的知识表示方法。

2.5.2框架结构

框架是由若干结点和关系（统称为槽slot）构成的网络。是语义网络一般化

形式化的一种结构，同语义网络没有本质区别。将语义网络中结点间弧上的标

注也放入槽内就成了框架表示法。

框架是表示某一类情景的结构化的一种数据结构。框架由框架名和一些槽

（slot）组成，每个槽有一些值，槽值可以是逻辑的、数字的，可以是程序、

条件、默认值或是一个子框架。槽值含有如何使用框架信息、下一步可能发生

的信息、预计未实现该如何做的信息等。

框架的一般格式：

FRAMEWORK：<frameworkname>

<slot1>

<face11>:value

<faceln>:value

<slot2>

<face21>:value

<face2n>:value

例：

framework:〈大学教师》

类属:〈教师＞

学历:（学士，硕士，博士）

专业:〈学科专业〉

职称：（助教，讲师，副教授，教授）

外语：

范围：（英，法，德，...）

默认：英

水平：（优、良、中、差）

默认：良

2.5.3框架表示下的推理

框架表示法没有固定的推理机理。但框架系统的推理和语义网络一样遵循匹

配和继承的原则，而且框架中如if-needed、if-added等槽的槽值是附加过程,

在推理过程中起重要作用。如确定一个人的年龄，已匹配的知识库中的框架为

槽名

年龄：NIL

if-needed:ASK

if-added:CHECK

在推理的过程中便启动了if-needed和if-added两个槽的附加过程ASK和

CHECKo

4.5.4框架与产生式表示法的比较

productionframework

知识表示

规则框架

单位

推理固定、与知识库独立可变，与知识库成一体

建立知识

容易困难

库

通用性低高

应用简单问题复杂问题

用户初学者专家

2.6面向对象的表示法

2.7脚本表示法

2.8过程表示法

2.9状态空间表示法：用来表示问题及其搜索过程的一种方法。

1.问题状态空间的构成

（1）状态：是描述问题求解过程中不同时刻状况的数据结构。一般用一组变量的有序集合表示：

Q=（q0,ql,q2,…,qn）,其中qi为集合的分量，称为状态变量。当-个分量以确定的值时，就得到一个具体

的状态。

（2）算符：引起状态中某些分量发生变化，从而使问题由个状态转变为另•个状态的操作。

（3）状态空间：由表示一个问题的全部状态及一切可用算符构成的集合。一般由三部分构成：问题的所

有可能的初始状态构成的集合S,算符集合F,目标状态集合G,用一个三元组表示：（S,F,G）

状态空间的图示形式称为状态空间图，其中，节点表示状态，有向边表示算符。

（4）问题的解：从问题的初始状态集S出发，经过,系列的算符运算，到达目标状态，由初始状态到目

标状态所用算符的序列就构成了问题的一个解。

2.用状态空间表示问题的步骤

（1）定义问题状态的描述形式

（2）用所定义的状态描述形式吧问题的所有可能的状态都表示出来，并确定出问题的初始状态集合描述

和目标状态集合描述。

（3）定义一组算符，使得利用这组算符可把问题由•种状态转变到另一种状态。

3.利用状态空间求解问题的过程

例：二阶Hanoi塔问题（见P72）

解：第一步，定义问题状态的描述形式

第二步，用所定义的状态描述形式把问题的所有可能的状态都表示出来，并确定出问题的初始状态集

合描述和目标状态集合描述

第三步，定义一组算符

2.10与/或树表示法

1、与或树的概念

用一个类似图的结构来表示把问题归约为后继问题的替换集合，画出归约问题图。

例如，设想问题A需要由求解问题B、C和D来决定，那么可以用一个与图来表示；同样，一个问题

A或者由求解问题B、或者由求解问题C来决定，则可以用一个或树来表示。

2、与或树的有关术语

父节点是一个初始问题或是可分解为子问题的问题节点；

子节点是一个初始问题或是子问题分解的子问题节点；

或节点只要解决某个问题就可解决其父辈问题的节点集合；

与节点只有解决所有子问题，才能解决其父辈问题的节点集合；

弧线是父辈节点指向子节点的圆弧连线；

终叶节点是对应于原问题的本原节点。

3、与或树的有关定义

可解节点与或树中一个可解节点的一般定义可以归纳如下：

（1）终叶节点是可解节点（因为它们与本原问题相关连）。

（2）如果某个非终叶节点含有或后继节点，那么只有当其后继节点至少有一个是可解的时，此非终叶

节点才是可解的。

（3）如果某个非终叶节点含有与后继节点，那么只要当其后继节点全部为可解时，此非终叶节点才是

可解的。

不可解节点不可解节点的一般定义归纳于下：

（1）没有后裔的非终叶节点为不可解节点。

(2)如果某个非终叶节点含有或后继节点，那么只有当其全部后裔为不可解时，此非终叶节点才是不

可解的。

(3)如果某个非终叶节点含有与后继节点，那么只要当其后裔至少有一个为不可解时，此非终叶节点

才是不可解的。

4、与或树构树规则

(1)与或树中的每个节点代表•个要解决的单一问题或问题集合。树中所含起始节点对应于原始问题。

(2)对应于本原问题的节点，叫做终叶节点，它没有后裔。

(3)对于把算符应用于问题A的每种可能情况，都把问题变换为•个子问题集合；有向弧线自A指向

后继节点，表示所求得的子问题集合。

(4)一般对于代表两个或两个以上子问题集合的每个节点，有向弧线从此节点指向此子问题集合中的

各个节点。

(5)在特殊情况下，当只有一个算符可应用于问题A,而且这个算符产生具有一个以上子问题的某个

集合时，山上述规则3和规则4所产生的图可以得到简化。

第三章推理方法

谓词逻辑是一种表达力很强的形式语言，谓词逻辑及其推理方法是人工智能

中知识表示方法,机器推理,定理证明的基本方法。另外谓词逻辑中的替换合一

技术，也是符号推理中模式匹配的基本技术。本章主要讲解基于谓词逻辑的归

结演绎推理。

3.1归结推理方法（确定性推理方法）

3.1.1谓词、函数、量词

・谓词：表示个体对象之间的关系、属性或状态。其表示形式如下：

P（xl,x2,x3,...xn）

其中：

P是谓词符号，表示xl,x2,x3,...xn个体对象之间的属性、状态或关系。

xl,x2,x3,...xn是谓词的参量（或称项），一般表示个体，它可以是个体常

量、个体变量或是个体函数。个体变元的变化范围称为个体域（或论域）

例：

口（外：表示乂是素数

FRIEND（a,b）：表示a和b是朋友

・个体函数：表示项之间的关系

有了个体函数之后，谓词的表达能力更强。假如个体函数father（b）表示“个

体b的父亲”，则谓词FRIEND（a,father（b））表示“a和b的父亲是朋友”，

显然表达能力更强了。

再例：

E（x,y）:表示x和y相等关系

个体函数square（x）：表示个体x的平方

则谓词E（square（a）,b）表示什么？

约定：（1）谓词符号有大写字母表示，如P,Q,R,S等；（2）用小写字母

x,y,z等作为个体变元符号；（3）用小写字母a,b.c等作为个体常元符号；

（4）用小写字母f,g,h表示个体函数符号。

•量词

全称量词：“所有”，“一切”，“任一”，“全体”，“凡是”等词称为全称

量词，记为“x

存在量词：“存在”、“有些”、“至少有一个”、“有的”等词统称为存

在量词，记为mx

引入量词和连接符（一蕴涵，八合取，▽析取，否定词〜）之后，谓词的表

达能力大大扩充了

例1:

谓词M(x):表示x是人，谓词N(x):表示x有名字，则\*(14a)一爪9)表示

“凡是人都有名字”。

例2：

谓词G(x):表示x是整数,E(x)：表示x是偶数，则mx(G(x)八〜E(x))表示

“存在不是偶数的整数”

例3：知识“不存在最大的整数”的表示

设：谓词G(x):表示x是整数，D(x,y)表示x大于y。则表示如下：

〜三x(G(x)AVy(G(y)-*D(x,丫)))或外&&)A3y(G(y)AD(y,x)))

・谓词公式：用谓词、量词(存在量词，全称量词)、联接词(一蕴涵，A合取,

▽析取)连接而成的复杂的符号表达式称为谓词公式。

3.1.2命题逻辑的归结法

］概念，

不带参数(肯定也不含量词))的谓词称为命题.

谓词的表达能力更强，命题没有概括能力；

命题：

P1:代表“北京是一个城市”

P2：代表“上海是一个城市”

P3：代表“广州是一个城市”

谓词：CITY(x)：代表“x是一个城市”，x的论域为口=｛北京，上海，广州｝

谓词代表变化着的情况，而命题代表固定的情况；

P：北京是一个城市；

Q：煤球是白的；

则P为永真式，Q为永假式；

而对于以上的谓词CITY(x),当x取值为“北京”时为“真”值，当x取值为“煤

球”时为“假”值。

谓词和命题相比的优点是谓词在不同的知识之间建立联系；

例如下面四个知识单元：

HUMAN(X)：代表x是人；

LAWED(x):代表x受法律管制；

COMM^'(x):代表x犯法；

PUNISHED(x):x受法律制裁；

则

HUMAN(x)-LAWED(x)表示一个高级的知识单元“人人都受法律的管制”。

COMMIT(x)-PUNISHED(x)表示只要x犯罪，x就要受法律制裁。

｛(HUMAN(x),LAWED(x))-*(COMMIT(x)-PUNISHED(x))｝表示“如果由于

某个x是人而受到法律管制，则这个人犯了罪就一定要受到惩罚”

由连接词(一蕴涵，八合取，V析取，等价否定词~)将命题连接在一起构

成命题公式。

A->B,A称为前件，B称为后件，其真值表如下所示：

ABA->B

001

011

100

111

A<->B等价于(A->B)A(B->A)

—*叱概念.

4藁：真值为T的命题公式称为永真式或重言式或有效的。

永假式：真值为F的命题公式称为永假式或不可满足的。

非永真式：不是永真式的命题公式；

可满足式：不是永假公式的命题公式；

原子公式:不含任何连接词的命题公式称为原子公式或称原子.例如P,Q

文字:原子公式及其否定形式称为文字.例如P,〜L

子句:文字的析取称为子句.例如:PVRV〜Q

互补文字：设L为一个文字，则称L与〜L为互补文字。

一些有用的等价关系：

~~A<=>A双重否定

AAA<=>A

AVA<=>A

AAB<=>BAA

交换律

AVB<=>BVA

(AAB)AC<=>AA(BAC)

结合律

(AVB)VC<=>AV(BVC)

AA(BVC)<=>(AAB)V(AAC)

分配律

AV(BAC)<=>(AVB)A(AVC)

AA(AVB)<=>A

吸收律

AV(AAB)<=>A

〜(AAB)<=>~AV~B

摩根定律

〜(AVB)<=>~A八~B

A—B<=>-AVB蕴含表达式

A<->B<=>(A-*B)A(B-*A)

AAT<=>A

AAF<=>F等价表达式

AVT<=>T

AVF<=>A

AA~A<=>F矛盾律

AV-A<=>T排中律

A-(B->CX=>AAB-*C输出律

(AtB)A(A—~B)<=>~A归谬律

A->B<=>~B—~A逆反律

2命题逻辑中的归结推理方法

若命题逻辑描述的命题Al,A2,••.An和B,要证明在AlAA2八.•.AAn成立的

条件下有B成立，或说A1AA2八…八AnfB。很显然A1AA2A...AAnfB等价

于证明A1AA2A...AAn八〜B是矛盾(永假)式。归结推理的方法就是从A1AA2

A...AAnA〜B出发使用归结推理规则来寻找矛盾，从而证明A1AA2A...A

An-B的成立。这种方法称为反演推理方法。

3归结式

设有两个子句

ci=pvcr

C2=~PVC2'

从中消去互补对一，所得新子句R(C1,C2)=C1'VC2',称为子句Cl',C2'的归结

式。没有互补对的两子句没有归结式。

归结推理规则就指的是对两子句做归结，也即求归结式。

下面证明归结推理规则是正确的，即C1AC2=>R(C1,C2),也即证明归结式是两

子句的逻辑结论，或者说任一使Cl,C2为真的解释I下必有R(C1,C2)也为真。

证：设I是使Cl,C2为真的任一解释，若在I下P为真，从而〜P为假，则C2'

必为真，那么R(C1,C2)=C1'VC2'为真。若在I下P为假，则C1'必为真，那么

R(C1,C2)=C1'VC2'为真。从而证明了C1AC2=>R(C1,C2),即归结式是子句的逻

辑结论。

特别地,当C1=P,C2=~P时,R(C1,C2)=口，记作为空子句。显然Cl,C2同时

为真是矛盾，或者说空子句口体现了矛盾。

4命题逻辑的归结推理过程

(1)利用逻辑蕴含式和逻辑等价式将命题公式化成合取范式(子句的析取)

(2)子句集：将若干个子句的合取式中的合取词人换成逗号，形成的集合称

为子句集。

(3)从子句集S出发，仅只对S的子句间使用归结推理规则(即求归结式)，

并将所得归结式仍放入S中，进而再对新子句集使用归结推理规则，重复这

些步骤直到得到空子句口(说明有矛盾)。便说明S是不可满足的，从而与

子句集S对应的定理是成立的。

例：证明(PfQ)A〜Q==>〜P

证：

先将已知以及结论的反化成合取范式

(〜PVQ)八〜QA(〜〜P)==>(〜PVQ)A〜QAP,建立子句集S={〜PVQ,〜

Q,P)

对S作归结

⑴〜PVQ

⑵〜Q

⑶P

(4)〜P..........................对(1)(2)求归结式

(5)口..............对(3)(4)求归结式

得证。

例:证明(PfQ)A(R-〜Q)==>(Rf〜P)

证明:将已知以及结论的反化成合取范式

==〉(〜PVQ)A(〜RV〜Q)A(〜(〜RV〜P))

==>(〜PVQ)A(〜RV〜Q)ARAP化成子句集

S={-PVQ,〜RV〜Q,R,P}，对S做归结：

⑴〜PVQ

(2)〜RV〜Q

(3)R

(4)P

(5)〜Q...(2)(3)归结

(6)Q...(1)(4)归结

(7)口...(5)(6)归结

3.L3谓词公式的子句集

1合取范式和析取范式

(1)合取范式:若谓词公式A有如下形式B1AB2A...ABn,其中Bi(i=l,2,...n)

形如L1VL2V...VLn,并且LI,L2,...Ln都是文字。例：

(P(x)V〜Q(y))八(〜P(x)VR(x,y))八(〜Q(y)V〜R(x,y))

应用逻辑等价式可以将任一谓词公式化成合取范式。

(2)析取范式:若谓词公式A有如下形式BlVB2V...VBn,其中析(i=l,2,...n)

形如L1AL2A...ALn,并且LI,L2,...Ln都是文字。例：

(P(x)/-Q(y)^R(x,y))y(-P(x)/\R(x,y))

应用逻辑等价式和逻辑蕴含式可以将任一谓词公式化成析取范式。

(3)前束范式:将所有的量词都放在谓词公式的前面。如

mx〃y(P(x,y)AQ(a)八R(z))就是前束范式。

Vx(N(x)A3yD(y,x))就不是前束范式。前束范式可分成前束合取范式和前束析

取范式。

化成前束合取范式的步骤：

・stepl:去掉多余的量词，即没意义的量词

・step2:将同名的约束变元与自由变元改名，使它们不同名。

・消去A,V,~以外的连接词

A->B........................〜AVB

A<->B......................CAVB)ACBVA)

・step4:将连接词〜内移，移到原子公式之前

〜(〜A)=A

〜(AAB)<=>〜AV〜B

〜(AVB)<=>〜AA〜B

〜*xA(x)<=>^x〜A(x)

xA(x)<=>Vx〜A(x)

・step5:将量词尽可能向左推，推到前缀所在的位置，用下列公式：

3xA(x)VB...........3X(A(x)VB),其中B中不含约束变元

BV3XA(X)...........3x(BVA(x)),其中B中不含约束变元

VxA(x)VB............Vx(A(x)VB),其中B中不含约束变元

BVVxA(x)............Vx(BVA(x)),其中B中不含约束变元

同样对上面式子中的▽改为A可得到另一组关于的A的替换式。

另外还可用下式进行替换：

VxA(x)A^xB(x).................Vx(A(x)AB(x))

^xA(x)V^xB(x).................(A(x)VB(y))，采用更名规则

3

3xA(x)VXB(X).................3X(A(x)VB(x))

3XA(X)A3XB(X).................3x3y(A(x)AB(y))，采用更名规则

・step6:使用A,V的分配律化成合取范式。

例：将下列谓词公式化成前束合取范式：

网((。尸⑸vVzQ(z,))>V亦限诩

=Vx((尸(x)vVzQ(zj))7-VyR(xM)

=>Vx((P(x)vVzQ(zj))

=>Vx((p(x)VVzg(z,7))-»

nVx(〜(尸(x)vVzQ(zj))\/加~R(x,u))

=Vx((~P(x)A3Z-Q(z,y))7m然~R(x,u))

=Vx(3z(~P(x)/\~Q(z,y))vBu~&(尤必))

nVx王力((~产Q(zj))V~氏(x,〃))

=Vx生土((〜产(x)v〜八(〜Q(z,y)v〜&

(4)Skolem(斯克林)标准型：将一个谓词公式中所有存在量词消去之后，便

得到该谓词公式的Skolem标准型。

(5)建立谓词公式的子句集

2将谓词公式化成子句集的步骤：

・按上述步骤化成前束合取范式；

・化成Skolem标准型，消去存在量词

消取存在量词时，还要进行变元替换。变元替换分两种情况：

①若该存在量词在某些全称量词的辖域内，则用这些全称量词指导变元的一

个函数代替该存在量词辖域中的相应约束变元，这样的函数称为Skolem函数;

②若该存在量词不准任何全称量词的辖域内，则用一个常量符号代替该存在

量词辖域中相应约束变元，这样的常量符号称为Skolem常量；

・消去所有全称量词

・消去合取词A,用逗号代替，以子句为元素组成一个集合S,即是谓词公式

的子句集

例1：求谓词公式G=^x3y3z((〜P(x,y)VR(x,y,z))A(Q(x,z)VR(x,y,z)))

的子句集。

解：

已经是前束范式，并且不含连接词。由于存在量词y,z都在全称量词x的辖

域中，所以将y,z分别用Skolem函数f(x)、g(x)代替。

“x((~P(x,f(x))VR(x,f(x),g(x)))A(Q(x,g(x))VR(x,f(x),g(x))))已

经是合取范式了，所以谓词公式G的子句集是

{〜P(x,f(x))VR(x,f(x),g(x)),Q(x,g(x))VR(x,f(x),g(x)))

例2：求谓词公式的子句集:Vx(*yP(x,y)-*~"y(Q(x,y)-*R(x,y)))

解：Vx(VyP(x,y)-*〜%(Q(x,y)-*R(x,y)))

==>Vx(VyP(x,y)fmy〜(~Q(x,y)VR(x,y)))

==>"x(VyP(x,y)fmy(Q(x,y)A~R(x,y)))

==>Vx(%P(x,y)fmz(Q(x,z)八〜R(x,z)))…改名

==>VX3y(p(x,y)Z(Q(x,z)A~R(x,z)))...量词分配率

==>^x3产z(P(x,y)f(Q(x,z)A~R(x,z)))...量词分配率

==>VX3y3z(〜P(x,y)V(Q(x,z)A~R(x,z)))

==>VX3y3z[(〜P(x,y)VQ(x,z))A(〜P(x,y)V〜R(x,z))]...分配律

==>"x[(〜P(x,f(x))VQ(x,g(x)))A(~P(x,f(x))V〜R(x,g(x))]...消

取存在量词

从而谓词公式的子句集是

{~P(x,f(x))V(Q(x,g(x)、〜P(x,f(x))V~R(x,g(x)))

例3：设G=mx4y4z闩w(P(x,y,z)A~Q(u,v,w)),求其子句集

解：三xVyVz3uVv3w(P(x,y,z)八〜Q(u,v,w)

==>VyVz3uVv3w(p(a>y,z)A-Q(u,v,w))..........消去x=a(常数)

==>VyVzVvaw(p(a)y,z)A~Q(f(y,z),v,w))..........消去u=f(y,z)

==>VyVzVv(p(a>y,z)-〜Q(f(y,z),v,g(y,z,v)))..........消去

w=g(y,z,v),得Skolem标准型

从而G的子句集是

{P(a,y,z),〜Q(f(y,z),v,g(y,z,v))}

例4:将机器证明〃梯形的对角线与上下底构成的内错角相等〃给出逻辑描述,建

立子句集合.

解：

设梯形顶点依次为a,b,c,d,定义谓词：

T(x,y,u,v):表示xy为上底,uv为下底的梯形.

P(x,y,u,v):表示xy|uv

E(x,y,z,u,v,w)表示Nxyz=Nuvw,问题的描述和相应的子句集为

VxVyVuVv[T(x,y,u,v)-*P(x,y,u,v)]...梯形上下底平行

子句：〜T(x,y,u,v)\/P(x,y,u,v)

VxVyVuVv[p(x；y,.v)-E(x,y,v,u,v,y)]...平行则内错交相等

子句：

T(a,b,c,d)...已知

子句：T(a,b,c,d)

E(a,b,d,c,d,b)...要证明的结论

子句：〜E(a,b,d,c,d,b)

子句集S为

{〜T(x,y,u,v)VP(x,y,u,v),〜P(x,y,u,v)VE(x,y,v,u,v,y),

T(a,b,c,d),~E(a,b,d,c,d,b)}

利用后面学到的替换和合一知识之后可给出证明过程。

3.1.4Herbrand理论：

证明一个谓词公式的不可满足性是困难的，这是因为谓词中个体变量的论域D

的任意性，以及解释的个数的无限性。例如：

「&):代表*是偶数。

若x的论域为9={2,4,6,8},则P是永真式，是可满足的；

若x的论域为口={1,3,5,7},则P是永假式，是不可满足的；

若x的论域为口={1,2,5,8},则P的真值与取论域D上的解释有关；

所以如果对一个具体的谓词公式能找到一个比较简单的特殊的论域，使得只要

在这个论域上该公式是不可满足的，便能保证该公式在任一论域上也是不可满

足的。所要建立的Herbrand域(简称H域)就具有这样的性质。

1H域

设G是谓词公式，定义在论域D上，令H。是G中所出现的常量的集合。若G中

没有常量出现，就任取常量a£D,而规定H°={a}；

U{所有形如f(\tl….tn)的元素},

其中f(tl,...,tn)是出现于G中的任一函数符号，而tl...tn是Hi-1的元素，

i=l,2,...o

规定上为G的H域。不难看出H域是直接依赖于G的最多只有可数个元素。

例1：S={P(a),~P(x)VP(f(x))},依H域的定义有：

HO={a}

Hl={a}U{f(a)}={a,f(a)}

H2={a,f(a)}U{f(a),f(f(a))}={a,f(a),f(f(a))}

H0°={a,f(a),f(f(a)),…}

例2：S={~P(z),P(x)V~Q(y)}

依定义有

HO={a}a是论域D中的一个常量

H1=HO

H2=H1

H0°={a}

例3：S={P(f(x),a,g(y),b)}

依定义有

HO={a,b}

Hl={a,b)U{f(a),f(b),g(a),g(b)}={a,b,f(a),f(b),g(a),g(b)}

H2={a,b,f(a),f(b),g(a),g(b)}U

{f(a),f(b),f(f(a)),f(f(b)),f(g(a)),f(g(b)),g(a),g(b),g(f(a)),g(f(

b)),g(g(a)),g(g(b)))

={a,b,f(a),f(b),g(a),g(b),f(f(a)),f(f(b)),f(g(a)),f(g(b)),g(f(a))

,g(f(b)),g(g(a)),g(g(b))}

H«==HOUH1UH2U....

注意：如果在谓词或子句集中出现函数形如f(x,a)仍视为f(x,y)的形式，这时

若H0={a,b},则Hl中除有f(a,a),f(b,a)外,还出现f(a,b),f(b,b)o

为了讨论在H域上子句集S中各谓词的真值。令集合

A={所有形如P(tl,t2,...,tn)的元素}

称为子句集S(或公式G)的原子集。其中是出现于S中的任

一谓词符号，而是S的H域的任意元素。

上述例1中的原子集为A={P(a),P(f中))原子集为)))，...}

上述例2中的原子集为A={P(a),Q(a)}

上述例3中的原子集为A={P(a,a,a,a),P(a,a,a,b),...}

例4：S={P(x)VQ(x),R(f(y))}

依定义有上匕,£5),£(£1)),...}

原子集

A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),P(f(f(a))),Q(f(f(a))),R(f(

f(a)}

由于S中谓词个数是有限的，而H是可数集，必然原子集A也是可数集。

2H解释

由子句集S建立H域、原子集A,从而讨论S在一般论域D上为真的解释I,就

可依赖于在H域上的某个解释I*来实现。也就是子句集S在D上的不可满足问

题转化成了在H上的不可满足问题。

下例说明由I寻求I*的过程

例1：S={P(x),Q(y,f(y,a)))

则有H={a,f(a,a),f(a,f(a,a)),f(f(a,a),a),f(f(a,a),f(a,a))...}

A={P(a),Q(a,a),P(f(a,a)),Q(a,f(a,a)),Q(f(a,a),a),Q(f(a,a),f(a,a)),..

.}

设论域D={1,2},解释I作如下设定

a-f(l,1)—f(l,2)—f(2,1)—f(2,2)

2—1--------2--------2---------1——

P(D—P(2)—Q(l,1)—Q(l,2)—Q(2,D—Q(2,2)

T______T_______p_________T________T________F

于是有

---x=l,y=l---x=l,y=2---x=2,y=l---x=2,y=2一

S|I=P(1)AQ(l,f(l,2))AP(1)AQ(2,f(2,1))AP(2)AQ(1,f(1,2))AP(2)A

Q(2,f(2,2))

=T

可按下列方法选取相应的r,

a—2

f(a,a)-*f(2,2)-*l

f(a,f(a,a))ff(2,1)-2

f(f(a,a),a)-f(f(2,2),2)ff(1,2)-2

f(f(a,a),f(a,a))-*f(1,1)-*1

P(a)-P⑵-T

Q(a,a)-Q(2,2)-F

P(f(a,a))-P(l)T

Q(a,f(a,a))-Q(2,1)=T

Q(f(a,a),a)-Q(l,2)=T

Q(f(a,a),f(a,a))-Q(2,2)=F

于是得到相应的H域下的解释I*为

I*={P(a),~Q(a,a),P(f(a,a)),Q(a,f(a,a)),Q(f(a,a),a),~Q(f(a,a),f(a,a))

5•••}

显然

S|I*=T

例2求5=付&)位0))小(£6))}的H域、原子集A,I*解释。

仍然设D={1,2},解释I设定如下：

f(1)—f(2)—P(l)—P(2)—Q(l)—Q(2)—R(l)—R(2)

2______2_____T_____F_____p_____T______F____T

于是由S|I=P⑴VQ(1)AR(f(D)AP(1)VQ(1)AR(f(2))AP(2)VQ(2)A

R(f(l))AP(2)VQ(2)AR(f(2))=T

设a=l,则相应的解释为：

H*={P(a),〜Q(a),〜R(a)/P(f(a)),Q(f(a)),R(f(a)),...}

S|I1=T

定理：设I是S的论域D上的解释，存在对应于I的H解释I*,使得若有S|I=T,

必有S|I*=T

定理：子句集S是不可满足的，当且仅当在所有的S的H解释下为假。

定理：子句集S是不可满足的当且仅当对每个解释I下，至少有S的某个子句

的某个基例为假。

3语义树

讨论S的不可满足性问题，可将S的所有解释展现在一棵二叉树上(这是一个

完全二叉树)，但要依赖于S的H解释以及S的原子集A。

例：对子句集S={P(x)VQ(y)/P(a),~Q(b)}画出相应的语义树

因为H={a,b}

A={P(a),Q(a),P(b),Q(b)}从A出发可画出语义树(部分)

N41N42N43N44

为了方便常以I(N)表示从根结点到结点N分支上所标记的所有文字的集合。

例如I(N32)={P(a),Q(a),~P(b)},I(N42