资源描述
第1章 人工智能综述,第2章 数理逻辑基础,第3章 归结推理方法,第4章 用于人工智能的Prolog语言,第5章 知识表示,第6章 产生式系统的搜索策略,第7章 专家系统,第8章 知识获取与机器学习,THE END,第1章 人工智能综述,本章主要内容：,智能与人工智能,人工智能发展的历史回顾,人工智能的研究目标与研究途径,人工智能的研究领域,,1.1 智能与人工智能,关于智能的几种解释：
智能是人们处理事物、解决问题时表现出来的智慧和能力。
智能是知识和智力的总和。,目前尚不能给智能一个确切的定义。,智能所具有的一些基本特征：,记忆与思维能力,感知能力,自适应能力,表达能力,自学习能力,,有关人工智能的几种说明：,智能机器：能够在各类环境中自主地或交互地执行各种拟人的机器,人工智能（学科）：是计算机科学中涉及研究、设计和应用智能机器的一个分支。,人工智能（能力）：是智能机器所执行的与人类智能有关的功能，如判断、推理、证明、识别、感知、理解、设计、思考、规划、学习和问题求解等思维活动。,简单地讲，人工智能是关于：
机器智能和智能机器的研究,,人工智能是工程技术学科，同时也是理论研究学科。,作为工程技术学科，人工智能的目的是：提出建造人工智能系统的新技术、新方法和新理论，并在此基础上研制出具有只能行为的计算机系统。,作为理论研究学科，人工智能的目的是：提出能够描述和解释智能行为的概念与理论，为建造人工智能系统提供理论依据。,,长期以来，围绕人工智能有很多争议。“机器是否能思考？”这一问题吸引了许多哲学家、科学家和工程师。,计算机科学的创始人之一，艾仑•图灵(Alan Turing)谈到这一问题：,Alan Turing,Alan Turing指出：“机器是否能思考”这一问题的答案取决与人们如何定义“机器”和“思考”。也许还可以指出，这一问题还取决于如何定义“能”。,,先考虑“机器”这一词。,再看看“思考”这个词。,1.2 人工智能发展的历史回顾,20世纪30年代和40年代：,20世纪50年代：,John McCarthy,数学逻辑和关于计算的新思想,第一次人工智能讨论会,20世纪60年代：,第一届国际人工智能联合会议,20世纪70年代：,《人工智能》国际杂志创刊,20世纪80年代：,专家系统和知识工程在全世界迅速发展,国外的发展情况,,国内的发展情况,1978年,国家“智能模拟”研究计划,1984年,召开智能计算机及系统全国学术讨论会,把智能计算机系统、智能机器人和智能信息处理列入国家高技术研究计划。,1986年,1989年,首次召开中国人工智能联合会议,1987年,《模式识别与人工智能》杂志创刊,1993年,智能控制和智能自动化被列入国家科技攀登计划,1997年,由本人编写的《人工智能原理及应用》出版,,,1.3 人工智能的研究目标与研究途径,研究目标分为近期目标和远期目标：,近期目标是，使现有的计算机更聪明、更有用；,远期目标是，构造智能机器。,关于人工智能的研究途径有两种不同观点：,主张用生物学的方法进行研究
------产生出一大学派叫做连接主义(Connectionism),主张用计算机科学的方法进行研究
------产生出一大学派叫做符号主义(Symbolism),,Agent一词的两种解释：
一是，对环境的认识以及对环境产生作用的行为者；
二是，代理人。
倾向于第一种解释的主要是AI领域的研究者M. Minsky指出：“当你试图说明完成一些任务的机器并试图了解它是如何工作时,即将其处理为黑箱时,就称其为Agent"。
软件界的研究人员倾向于第二种解释：代理人。Agent是计算机软件，代表用户，以主动服务方式完成一定操作的计算实体。Agent是具有信息处理能力的主动实体，其结构包含下述模块：感知器、效应器、信息处理器、目标模块、通信机制。,仅代理用户某种任务的软件不能称为智能Agent。智能性，如理解用户用自然语言表达的对信息资源和计算资源的需求，帮助用户在一定程度上克服信息内容的语言障碍，捕捉用户的偏好和兴趣，推测用户的意图并为其代劳等。只有代理性、智能性、自主性均达到相当水准的系统才有条件称为智能Agent。
比尔?盖茨把智能Agent称为“软的软件”，他说：“一旦程序写好了，它就一成不变。软的软件随着你的使用好象会变得越来越聪明”，“你可以把Agent当作直接内置在软件中的合作者，它会记住你擅长什么，你过去做过些什么，并试着预测难题，并提出解决办法”。,,,1.4 人工智能的研究领域,专家系统与知识工程,自动定理证明与自动推理,机器学习,自然语言理解,智能管理系统,自动程序设计,感知系统,智能机器人,专家系统是一个智能计算机程序系统。其内部具有大量专家水平的知识和经验，能够利用人类专家的知识和解决问题的方法来解决该领域的问题。也就是说，专家系统是一个具有大量知识与经验的程序系统。它应用人工智能技术，根据某个领域一个或多个人类专家提供的知识和经验进行推理和判断，模拟人类专家的决策过程，以解决那些需要专家决定的复杂问题。,,自动定理证明是人工智能最早得到应用的领域。对于一个数学定理，给出严格的数学证明，是一项高智能的工作。不仅需要很强的推理能力，而且需要人们有着深刻的洞察力，能预见出在证明主要定理之前，应先证明哪些引理，作好必要的准备，最后证明主要定理。,,机器学习领域的研究工作主要从三个方面进行：一是面向任务的研究，研究和分析改进一组预定任务的执行性能的学习系统；二是认识模拟，研究人类学习过程并进行计算机模拟；三是理论性分析，从理论上探索各种可能的学习方法和独立于应用领域的算法。,,,自然语言理解就是研究如何让机器理解人类的自然语言。机器翻译也属于自然语言理解的范畴，它是研究把一种语言自动的翻译成另一种语言。自然语言理解这一课题虽然困难，但对人工智能的发展却起着重要的作用。,智能管理是人工智能在管理领域中的应用，发展了“智能管理”新技术和新一代的计算机管理系统 “智能管理系统”，如：智能管理信息系统（IMIS Intelligent Management Information System）、智能办公自动化系统（IOAS Intelligent Office Automation System）、智能决策支持系统（IDSS Intelligent Decision Support System）等。
智能管理系统（IMS Intelligent Management System）不仅比常规的计算机管理系统MIS、OAS、DSS等具有更高的智能水平，可以为非结构化半结构化的管理决策提供信息服务和决策支持；而且具有更全面的管理功能，可同时具备信息管理、事务处理、决策支持等多种功能。,,,自动程序设计：包括程序综合与程序验证两方面的内容。前者用以实现自动编程，即用户只需告诉计算机“做什么”，无须告诉“怎样做”；后者是指程序的自动验证，自动完成正确性检查。,人工智能的感知系统的任务，就是为计算机配置各种感觉器官，是其具有感知能力，能够识别各种图形、文字及各种语言信号。,,智能机器人是模拟人类行为的机器。它是人工智能中感知系统、问题求解系统、计划产生系统等领域技术的综合应用。,,,第2章 数理逻辑基础,本章主要内容：,命题逻辑,谓词与量词,谓词公式及其解释,谓词公式的标准形式,谓词公式的等价与蕴涵,2.1 命题逻辑,一个命题是一个或真或假不能两者都是的断言。,断言是指一陈述语句。,简单地说，命题是指一句有真假意义的陈述句。,命题为真，记为 T 命题为假，记为 F,命题变元用 P, Q, R…表示；,一个命题P如果是真值未指定任意命题，称P为命题变元。,如果P是一个真值已经指定的命题，称为命题常元。,命题常元只有 T 和 F。,,2.1.l 命题联结词（逻辑联结词、逻辑运算符）,复合命题：单个命题通过联结词联结构成的新命题。,常用的5种联结词：,复合命题与原命题的真值关系,2.1.2 命题公式及其解释,原子公式：单个命题变元、单个命题常元称为原子公式。,命题公式：由如下规则生成的公式称为命题公式：
1. 单个原子公式是命题公式。
2. 若A ,B是命题公式，则~A , AB , AB , A B , A B是公式。
3. 所有命题公式都是有限次应用1、2得到的符号串。,命题公式的解释：给命题公式中的每一个命题变元指定一个真假值， 这一组真假值，就是命题公式的一个解释。用I表示。,例如：公式G= (AB) C 的一个解释是：,I1(G) = A/T, B/F, C/T,在解释I1(G)下G为真。,永真公式与永假公式：如果公式在它所有的解释I下，其值都为T，则称公式G为恒真的；如果其值都为F，则称公式G为恒假的（不可满足的）。,注意：关于五个联结词的约定：
* 结合力的强弱顺序： ¬， ， ， ，
* 联结词相同时，从左至右运算。
解释的个数：
如果一个公式G中有n个不同的原子公式（或简称原子），则G有2n个不同的解释，于是G在2n个解释下有2n个真值。如果将这些真值和它们的解释列成表，就是G的真值表。,2.1.3 等价命题公式,如果两个命题公式所含原子公式相同，且在任一解释下，两个命题公式的值相同，则称这两个命题公式为等价命题公式或等价公式。,常用的等价公式有：,1. (P Q)= (P Q) (Q P),2.(P Q)=(¬P Q),3. ¬(¬P)= P
4.交换律：P Q=Q P
P Q=Q P,5.结合律：P (Q R)=(P Q) R
P (Q R)=(P Q) R,6.分配律：P (Q R)=(P Q) (P R)
P (Q R)=(P Q) (P R),7.泛界律：P F=P , P T=P
P F=F , P T=T,8.互余律：P ~P=T, P ~P=F,9.德 • 摩根定律：~(P Q)=~P ~Q
~(P Q)=~P ~Q,证明两个公式等价，可用真值表，也可用基本公式。,例如 要证明公式 P Q=~Q ~P,[证] P Q =~ P Q,=~ P ~ (~ Q ),=~(~Q) ~P,=~Q ~P,若要证明公式 P P Q=P,[证] P P Q = P ( P Q),= P (Q ~Q) ( P Q),= (P Q) (P~ Q) ( P Q),=( P Q) ( P ~Q),= P (Q ~ Q),=P,2.1.4 永真蕴涵式,若命题公式G H是恒真的，称其为永真蕴涵式。记为GH，读做“G蕴涵H”，也称“G是H的逻辑结果”。,常用的永真蕴涵式：
1. P P Q,[证] P P Q = ~P (P Q),= ~P P Q,= T Q = T,2. P Q P,[证] P Q P =~(P Q) P,= ~P ~Q P,=T ~Q= T,3. P (P Q) Q,4.( P Q) ~Q ~P,5. ~P (P Q) Q,6.(P Q) (Q R) (P R),7.( P Q) ( (Q R) ( P R)),8.((P Q) ( R S)) (P R Q S),9.(( P Q) ( Q R)) ( P R),公式的标准形式：范式,析取范式 (disjunctive normal form,DNF) ：一个由原子和原子的非组成的析取式，如果与给定的命题公式A等价，则称它是A的析取范式。记作：,A=A1 A2 ... An n1
其中， A1 ,A2, ... An 是原子或是原子非的合取式。,合取范式 (conjunctive normal form,CNF) ：一个由原子和原子的非组成的合取式，如果与给定的命题公式A等价，则称它是A的合取范式。记作：,A=A1 A2 ... An n1
其中， A1 ,A2, ... An 是原子或是原子非的析取式。,注意：1. 任何一个命题公式豆科仪转化成它的析取范式或合取范式;
2. 一个公式的析取范式和合取范式都不是唯一的；
3. 运算符最少的范式称为最简范式。,,2.2 谓词与量词,在命题演算中，基本元素是原子命题，而不考虑命题的内部结构和成分。,在形式逻辑中有一个三段论法：,P:“所有的人都会犯错误”
Q:“张三是人”
R:“张三会犯错误”,R应该是P和Q的逻辑结论。但在命题逻辑中无法准确表达这三个命题的逻辑关系。,因为 ( P Q ) R 不是恒真的。如：取解释:I=P/T,Q/T,R/F 则公式为假值F. 就是说解释I 弄假了此公式。,为准确表达此类公式，必须引进谓词和量词的概念。,2.2.1 谓词,先看几个命题：,1. 3是质数
2. 王二生于武汉市
3. 7=23,x是质数
x生于武汉市
x=y z,F(x)
G(x,y)
H(x,y,z),称“3”、“王二”、“武汉市”、“7”、“2”、“3”为个体;,代表个体的变元称为个体变元；,刻画个体性质或个体之间关系的词叫谓词。,“是质数”、“生于”、“…=... ...”都是谓词。,2.2.2 量词,量词分为全称量词和存在量词。,符号“”表示全称量词。符号“”表示存在量词。,x读作“对一切x”,或“对每一x”，或“对任一x”。x是所作用的个体变元。, x读作“存在一个x”,或“对某些x”，或“至少有一x”。x是所作用的个体变元。,再看前面的三段论法：,P:“所有的人都会犯错误”
Q:“张三是人”
R:“张三会犯错误”,x(M(x) R(x))
M(“张三”)
R(“张三”),在谓词前加上x,叫做变元被全称量化；
在谓词前加上 x,叫做变元被存在量化。
量化的目的是约束变元。,2.2.3 约束变元、自由变元、改名规则,量词的辖域
约束出现
自由出现,改名规则：在同一公式中，一个变元既以约束出现，有以自由出现。就需要对变元改名。改名规则是：,1. 变元若要改名，则该变元在量词及其辖域中的所有出现均须一起更改，其余部分不变；
2. 变元改名时所选用的符号，必须是量词辖域内未出现的符号。一般还应是公式中未出现的符号。,,2.3 谓词公式及其解释,在定义谓词公式前,先介绍“符号”的概念： “项”的定义；原子的定义：,符号： 常元符号,变元符号,函数符号,谓词符号,关于项的定义：
1. 常元符号是项；
2. 变元符号是项；
3. 若f是n元函数符号，t1,…, tn 是项， 则f( t1,…, tn )是项；
4. 所有项都是有限次使用1,2,3生成的符号串。,原子的定义：若P(x1,…, xn)是n元谓词符号， t1,…, tn 是项， 则P(t1,…, tn),谓词公式（公式）的定义：,1. 原子公式是公式；
2. 若H,G是公式，则~H , H G , H G , H G , H G是公式；
3. 若G是公式，x是G中的自由变元，则xG xG是公式；
4. 所有公式都是有限次应用1、2、3得到的符号串。,解释的定义：,公式G的一个解释I，是由非空集D和下列对G中常元符号、函数符号、谓词符号的一组指定组成：,1.对每个常元符号，指定D中一个元素。
2.对每个n元函数符号，指定一个函数，即指定Dn到D的一个映射。
3.对每个n元谓词符号，指定一个谓词，即指定Dn到{T,F}的一个映射。,[例2.1]给以下公式指定一个解释：,1. x P(f(x)) Q(x,f(a))
2. x(P(x) Q(x,a)),可指定如下解释I：
D={1,2}
a/1
f(1)/2 f(2)/1
P(1)/F P(2)/T Q(1,1)/T Q(1,2)/T Q(2,1)/F Q(2,2)/T
在此解释I下，公式 x P(f(x)) Q(x,f(a))为T值。,而公式x(P(x) Q(x,a))在此解释下为F值。,如果存在I使G为T值，则称G可满足，简称I满足G;若I使G为F值，称I不满足G，或称I弄假G。,如果不存在解释I满足公式G，公式G成为不可满足的。如果公式G的所有解释I都满足G,公式G称为恒真的。,,2.4 谓词公式的等价与蕴涵,两个谓词公式等价：
设P与Q是两个谓词公式，D是它们共同的个体域，若D上的任何一个解释，P与Q都有相同的值，则称公式P和公式Q在D上是等价的。
谓词公式的蕴涵：
设P与Q是两个谓词公式，如果PQ是恒真的，则称P蕴涵Q。且称Q为P的逻辑结论，称P为Q的前提，记作 PQ。
显然，若Q是P的逻辑结论，则对P,Q的任意一个解释I,如果P在I下为真，那么Q在I下也为真。反之亦然。,P:“所有的人都会犯错误”
Q:“张三是人”
R:“张三会犯错误”,x(M(x) R(x))
M(“张三”)
R(“张三”),需要证明R是(P Q)的逻辑结论。即证明PQ R 为恒真。
证：设I是P,Q,R的一个解释（I指定“张三”为始量），且I满足（P Q),即I满足x(M(x) R(x)) M(“张三”)，所以I满足R(“张三”）。
否则，R（“张三”）在I下为假，于是（M(“张三”) R(“张三”)）在I下为假，故x(M(x) R(x))在I下为假，矛盾。所以R(“张三”)在I下为真。,三段法的证明：,,2.5 谓词公式的标准形式,2.5.1 前束范式
一个谓词公式，如果量词非否定地放在全式的开头，而量词的辖域都延伸到整个谓词公式，则称这样的公式为前束范式。,一般地，谓词逻辑中的公式G如果有如下形状：
Q1x1,…Qn xn M(x1,…,xn)
则称G为前束范式。
其中Qi是xi或xi, i =1,…,n，M(x1,…,xn)是不含量词的公式。
Q1x1,…Qn xn称为首标，M称为母式。如：,xyz(P(x,y ) Q(x,z))
xyzP(x,y,z)
都是前束范式。,利用改名规则、量词否定公式和量词辖域扩张公式等，可把任一谓词公式化成前束范式。例如：,~x(P(x) xQ(x))
=~x(~P(x) xQ(x))
=x(P(x) ~xQ(x))
= x(P(x) x~Q(x))
= x(P(x) y~Q(y))
xy(P(x) ~Q(y)),[例2.2]将公式xy(z (P(x,z) P(y,z)) uQ(x,y,u))化为前束范式：
解： xy(z (P(x,z) P(y,z)) uQ(x,y,u))
= xy(~z (P(x,z) P(y,z)) uQ(x,y,u))
= xy(z (~P(x,z) ~P(y,z)) uQ(x,y,u))
=xyzu (~P(x,z) ~P(y,z)) Q(x,y,u)),步骤1：使用以下基本等价公式，将G中的和删去：
F H=(F H) (H F)
F H=~F H,步骤2：使用~(~F)=F，摩根定律及以下等价公式，将谓词公式中的所有 否定号~放在原子之前：
~xG(x)=x~G(x)
~xG(x)=x~G(x),步骤3：如果需要，则将约束变量改名。,步骤4：利用等价公式将所有量词提到公式的最前面。,将任意谓词公式化为前束范式的四个步骤：,2.5.2 Skolem范式,Skolem范式是谓词逻辑中公式的又一种标准形式。
设公式G的形式如下：
Q1x1,…Qn xn M(x1,…,xn)
其中Qi是xi或xi, i =1,…,n，M(x1,…,xn)是不含量词的公式。
将上式中的M(x1,…,xn)化为等值的和取范式，然后将所有的存在量词消去，便可得到公式G的Skolem范式。,消去G中的存在量词的方法如下：
设Qrxr (1 r n )是第一个出现在Q1x1,…, Qrxr ,…,Qn xn M(x1,…,xn)中的存在量词，即Q1x1,…, Qr-1xr-1 均为全称量词。,若r=1，即Qrxr 左边没有全称量词，则取异于M(x1,…,xn)中所有常量符号的常量符号C,并用C代表M(x1,…,xn)中的xr，然后在首标中Qrxr。,若1r n，即Qrxr左边有全称量词Qs1 xs1 ,…,Qsm xsm,而m1，1 s1s2...s mr，则取异于出现在M中的所有函数符号的m元函数符号f(xs1,…,xsm)，用f(xs1,…,xsm)代表出现在M中的所有xr,然后在首标中删除存在量词Qrxr。,[例2.3]将公式G=xyz((~P(x,y)Q(x,z)) R(x,y,z))化成Skolem范式。,解：先将M(x,y,z)化成合取范式：
M(x,y,z)= ((~P(x,y) Q(x,z)) R(x,y,z))
= (~P(x,y) R(x,y,z)) (Q(x,z) R(x,y,z)),G= xyz((~P(x,y) R(x,y,z)) (Q(x,z) R(x,y,z)))
消去y得到：xz((~P(x,f(x)) R(x,f(x),z)) (Q(x,z) R(x,f(x),z)))
消去z得到：x ((~P(x,f(x)) R(x,f(x),g(x))) (Q(x,g(x)) R(x,f(x),g(x))))
此式就是公式G的Skolem范式。,[例2.4] 将公式G=xyzuvwP(x,y,z,u,v,w)化成Skolem标准型。,解：消去x,因为其左边没有全称量词，于是引入常量a代替P(x,y,z,u,v,w) 中的所有x,得： yzuvwP(a,y,z,u,v,w),消去u，因为其左边有全称量词yz，于是引入一个二元函数f(y,z)代替P(a,y,z,u,v,w)中的所有u，得： yzvwP(a,y,z,f(y,z),v,w),消去w ，因为其左边有全称量词 yzv，于是引入一个三元函数g(y,z,v)，代替P(a,y,z,f(y,z),v,w)中的所有w。最后得到的Skolem 标准型为：
yzvP(a,y,z,f(y,z),v,g(y,z,v)),注意：1.公式的Skolem 标准型与原公式并不等值；
2.公式的Skolem 标准型与原公式在不可满足的意义上相等。,2.5.3 子句与子句集,若干文字的一个析取式成为子句。如：,P(x,y) ~Q(x,y,z) R(u),没有文字的子句成为空子句。只有一个文字的子句成为单元子句。,将公式G化为Skolem 标准型，其母式M已为合取范式，M中的没一个合取项都是一个子句，M中这些子句的集合用S表示，称为公式G的子句集。,从公式G得到子句集S的方法是：先从公式G得到Skolem 标准型，然后去掉全称量词，最后用符号“，”代替符号“”。外层括号用{}。,如公式：G=xyz((P(x,y) R(x,y,z)) (Q(x,z) R(x,y,z))),G的Skolem标准型为：x ((P(x,f(x)) R(x,f(x),g(x))) (Q(x,g(x)) R(x,f(x),g(x)))),G的子句集S为： {(P(x,f(x)) R(x,f(x),g(x)))，(Q(x,g(x)) R(x,f(x),g(x)))},子句集中S中的每一个子句中的变量都是由全称量词约束着。,对任一公式G都可以建立其对应的S子句集。这样对公式的讨论就可以用对集合的讨论来代替。,引进子句集S的目的就是要简化对A1 A2 A3B的证明，而证明A1 A2 A3B只需证明G= A1 A2 A3 ~B的子句集不可满足即可。,定理 设S是公式G的子句集。于是，G是不可满足的，当且仅当S是不可满足的。,子句集概念的推广：,设G= G1 ... Gn ，Si是Gi化为Skolem范式后其木式给出的子句集，i=1,2,…n。令S=S1... S n。于是G是不可满足的，当且仅当S是不可满足的。也称S是个G的子句集。,,第3章 归结推理方法,子句集的海伯伦域,海伯伦定理,替换与合一算法,归结反演,归结原理,本章主要内容：（讨论：如何证明一个子句集不可满足）,归结控制策略,,课堂练习一,3.1 子句集的海伯伦域,3.1.1 海伯伦域与海伯伦解释,定义：H0是出现于子句集S的常量符号集合。如果S中无常量符号出现，则H0由一个常量符号a组成。对于 i =1,2,…n 令
Hi=Hi-1 {所有型如fn(t1,t2,…tn)的项的集合}
其中fn(t1,t2,…tn)是出现在S中的n元函数符号，tj Hi-1 j=1,2,…,n。于是称Hi为S的i级常量集，H 称为S的海伯伦（Herbrand）域,简称S的H域。,[例3.1]子句集S为： S={P(f(x),a,g(y),b)} 求子句集S的H域。,解：根据定义
H0={a,b}
H1=H0 {f(a), f(b), g(a), g(b)}={a,b, f(a), f(b), g(a),g(b)}
H2=H1 {f(a), f(b), g(a),g(b),f(f(a)), f(f(b)), g(f(a)),g(f(b)), f(g(a)), f(g(b)), g(g(a)),g(g(b))}= {a,b, f(a), f(b), g(a),g(b),f(f(a)), f(f(b)), g(f(a)),g(f(b)), f(g(a)), f(g(b)), g(g(a)),g(g(b))}
…...,[例3.2] 求子句集 S={P(x),Q(y) R(y)}的H域。,解：该子句集中既无个体常量，又无函数，所以可任意指定一个常量a作为个体常量，从而得到：H0=H1=…=H ={a},对于没有变量符号出现的项、项集、原子、原子集合、文字、子句和子句集，分别称之为基项、基项集、基原子、基原子集合、基文字、基子句和基子句集。,关于原子集的定义：
设S是子句集。集合A={所有形如P(t1,…,tn)的元素}称作子句集S的原子集。其中P(t1,…,tn)是出现于S中的任一谓词符号，而t1,…,tn是S的H域的任意元素。,例3.2中 S的原子集为 A={P(a),Q(a),R(a)},[例 3.3] S={P(x) Q(x),R(f(y))}
根据定义有： H={a,f(a),f(f(a)),…}
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中的某子句C中所有变量符号均以S的H域的元素代入时，所得的基子句C'称作C的一个基例。,例：S={P(x),Q(f(y)) R(y)}
有：H={a,f(a),f(f(a),…}
P(a),P(f(a))都称作子句C=P(x)的基例；
Q(f(a)) R(a),Q(f(f(a))) R(f(a))都是Q(f(y)) R(y)的基例。,关于海伯伦解释的定义：,设S是子句集，H是S的海伯伦域，I是S在H上的一个解释。称I为S的一个H解释，如果满足如下条件：,（1）I映射S中的所有常量符号到自身；
（2）若f是S中n元函数符号，h1,…hn是H中元素，则I指定映射：
（ h1,…hn ） f(h1,…hn),设A={A1,A2,…,An}是S的原子集。于是S的一个解释I可以方便地表示为如下一个集合： I={m1,m2,…,m n},,[例3.4] S={P(x)Q(x),R(f(y))},于是： S的H域={a,f(a),f(f(a)),...},S的原子集：A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),P(f(f(a))),...},S的H解释为：
I1={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),P(f(f(a))),...}
I2={~P(a),~Q(a),~R(a),~P(f(a)),~Q(f(a)),~R(f(a)),~P(f(f(a))),...}
I3={P(a),~Q(a),R(a),~P(f(a)),Q(f(a)),~R(f(a)),P(f(f(a))),...}
…...,3.1.2 海伯伦解释与普通解释的关系,子句集S的一个解释，不是必须定义在H域上，即使定义在H域上，也不一定是一个H解释。,D={1,2} a/2 f(1,1)/1 f(1,2)/2 f(2,1)/2 f(2,2)/1
P(1)/T P(2)/F Q(1,1)/F Q(1,2)/T Q(2,1)/F Q(2,2)/T,依照I可以构造S的一个解释I*,使得若S在I下为真则S在I*下也为真。,首先找出S的原子集：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)),...},其次，对A中每一个成员，用解释I进行估值：,P(a)=P(2)=F,Q(a,a)=Q(2,2)=T,P(f(a,a))=P(f(2,2))=P(1)=T,Q(a,f(a,a))=Q(2,f(2,2)=Q(2,1)=F,Q(f(a,a),a)=Q(f(2,2),2)=Q(1,2)=T,Q(f(a,a),f(a,a))=Q(f(2,2),f(2,2))=F,…...,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)),...},于是，可以构造S的H解释,[例3.5] 有子句集 S={P(x),Q(y,f(y,a)}指定S的一个解释I（普通解释）如下：,如果子句集S中没有常量符号，则将S的H域中初始元素a映射到D中任一元素，依照上例的方法，也可以构造S的一个H解释I*，使得若I满足S，则I*也满足S。,[例3.6] S={P(x),Q(y,f(y,z))},令S的一个解释I如下：,D={1,2} f(1,1)/1 f(1,2)/2 f(2,1)/2 f(2,2)/2
P(1)/T P(2)/F Q(1,1)/F Q(1,2)/T Q(2,1)/F Q(2,2)/T,指定a对应1得H解释:
I1* ={P(a),~Q(1,1),P(f(a,a)),~Q(a,f(a,a)),~Q(f(a,a),a),~Q(f(a,a),f(a,a)),...},指定a对应2得H解释:
I2* ={~P(a), Q(1,1),~P(f(a,a)), Q(a,f(a,a)), Q(f(a,a),a), Q(f(a,a),f(a,a)),...},以上根据解释I构造的S的H解释I*，称为对应与I的H解释。,定义：设I是子句集S在区域D上的解释，是如下递归定义的H到D的映射：,1.若S中有常量符号，则H0是出现在S中的所有常量符号的集合。于是对任意a H0, a表示a在I下的映象。
若S中无常量符号，则H0={a}。于是a可以是D中随便哪个元素。,2.对任意(h1,…,hn) Hin，及S中的任意n元函数符号f(x1,…,xn)，令(f (h1,…,hn) ) 是(h1,…,hn)在I下的H解释I *有如下规定。
若(h1,…,hn) =Hn，P (x1,…,xn)是n元函数符号，则规定
T1*(P (h1,…,hn) )=T1(P (h1,…,hn))
其中T1(P (h1,…,hn)) 表示P (h1,…,hn)在I下的真值，T1*(P (h1,…,hn) )表示P (h1,…,hn)在I*下的真值。,引理 如果某区域D上的解释I满足子句集S.则对应于I的任意一个H解释I*也满足S。,定理 子句集S是不可满足的，当且仅当S被所有的H解释弄假。,3.2 海伯伦定理,要证明子句集S是不可满足的，只需要考虑在H域上的所有H解释即可。但是所有的H解释也是无限的。海伯伦定理就是用语义树的方法，把需要考虑无穷个H解释的问题，变成只考虑有限个解释的问题。,3.2.1 语义树（解释树）,设子句集S的原子集A={P,Q,R},,,,,,,,,,,,,,,,,,,,,,,,,,,,,,N38,N37,N36,N34,N35,N33,N32,N31,N24,N23,N22,N21,N12,N11,N0,R,Q,~P,P,~Q,Q,~Q,R,R,R,~R,~R,~R,~R,语义树：,通常以I(N)表示从根结点N0到到叶结点分枝上所标记文字的并集。如：
I(N36)={~P,Q,~R},3.2.2 海伯伦定理,定理（海伯伦定理1）子句集S是不可满足的，当且仅当对应于S的完全语义树是一棵有限的封闭语义树。,定理（海伯伦定理2）子句集S是不可满足的，当且仅当存在S的一个有限不可满足的基例集S'。,对一阶谓词描述下的A1A2A3B的证明问题，对此已经作了足够的准备。首先将这个问题化成G= A1A2A3~B的不可满足问题，进而将G化成Skolem标准型，并建立相应的子句集S，再将一般论域D上的讨论简化成H域上的讨论，最后引入语义树。,3.3 替换与合一算法,3.3.1 替换与最一般合一替换,一个替换是型如 {t1/v1 ,…,t n/vn} 的一个有限集,其中vi是变量，而ti是不同于vi 的项（常量、变量、函数），且vi vj (i j ) ，i,j=1,2,…,n。称为ti替换分子， vi为替换分母。,当t1,…,tn是基项时，称此替换为基替换。,不含任何元素的替换为空替换，以表示。,例如{a/x,b/y,f(x)/z}就是一个替换。,替换可作用与某个谓词公式上，也可作用于某个项上。,令替换= {t1/v1 ,…,t n/vn} ，作用于E，而E是一谓词公式。就是将E中出现的vi均以ti代入(i=1,2,…,n), 作用的结果用E表示，并称E为E的一个例。若t是项， 作用于项t也是将t中出现的vi均以ti代入，作用的结果用t表示。,[例3.7]令 = {a/x,f(b)/y,c/z},E=P(x,y,z),t=g(x,y),于是E的例为 E =P(a,f(b),c),而 t=g(a,f(b)),当E是子句集S的一个子句，用作用于E，当中的v1,…,vn含有E的所有变量， t1,…,tn又是H的元素时， E 便是S的子句E的基例。,[例3.8] 子句集S={P(x,y),Q(x,a) R(y,b)},此子句集的H域： H={a,b},P(x,y)是S的一个子句，以= {a/x,b/y}作用于P(x,y)，得到P(a,b)。,P(a,b)就是S子句P(x,y)的基例。,定义：设= {t1/x1 ,…,t n/xn}， ={u1/y1 ,…,u m/vm}是两个替换。将下面集合,{t1 /x1 ,…,t n /xn，u1/y1 ,…,u m/vm},
展开阅读全文
相关搜索
