《人工智能chp40》由会员分享，可在线阅读，更多相关《人工智能chp40（18页珍藏版）》请在金锄头文库上搜索。
1、人工智能(AI),第四章(0) 人工智能中的一级谓词逻辑 4(0).1 一级谓词演算的基本体系 4(0).2 归结(消解Resolution) 4(0).3 归结反演系统(Refutation) 4(0).4 基于归结法的问答系统 参考书： 人工智能原理与技术俞瑞钊、史济建 浙江大学出版社 人工智能基础 高 济、朱淼良 高等教育出版社 人工智能导论 林尧瑞、马少平 清华大学出版社,第四章 人工智能中的谓词逻辑 传统的形式逻辑始于古希腊的亚里士多德,已有两千多年的历史,它是人类思维的形式和规律。17世纪70年代数学中的形式化表示方法引入逻辑研究领域，经过几代科学家出色工作已发展成为数理逻辑的重要
2、方向之一。 4.1 命题及逻辑连接词 定义：命题是能够判断真假的陈述句。 例如：1. 雪是白的。 (是) 2. 他是工人。 (不是) 3. 19是3和6的倍数。(是) 4. 请乘坐汽车去。(不是) 一般情况下用P、Q、R等大写符号表示命题。,第四章 人工智能中的谓词逻辑 逻辑连接词定义： 逻辑“非”，命题P的非记成P,P为真当且仅当P假 “合取”，PQ表示不仅P而且Q，PQ真P和Q为真 “析取”，命题PQ为真当且仅当其中有一个为真 “蕴涵”，PQ意思是如果P则Q,结果为假当且仅当P为真且Q为假 “等价”， ，P Q为真当且仅当P,Q同时为真或同时为假,第四章 人工智能中的谓词逻辑 例子1：命题
3、P表示“昨天下雨”，Q表示“昨天开会”，则“昨天下雨且开会”表示成PQ。 例子2:P表示“6大于4”，Q表示“3大于4”，R表示“18大于16”，则“如果6大于4，3不大于4，则18不大于16”写成(PQ)R。 注意：符号表达语句时首先要确切，与原语句涵义一致。其次对于复合命题都要写成原子命题联结。如用P表示“18是6和9的公倍数”是错误的。 例子3：“小张不会德文也不会法文” 用P表示“小张会德文”，Q表示“小张会法文”，则原语句写成 PQ,第四章 人工智能中的谓词逻辑 4.2 命题公式得永真性与等值 定义(公式):(1) 原子命题是命题公式。 (2) 若是命题公式，则也是命题公式。 (3)
4、 如果, 是命题公式，那么, , , 也都是命题公式。 (4) 所有命题公式都是有限次应用上述规则得到的。 判断一个字符串是否公式的方法是将任意由五个联结符连接的原子命题用一个原子命题表示。 例: =(PQ)R) (PQ) 1 =(PR) P) 2=(PR) P) 3 =(P P) 4=P 3 =P 所以是命题公式。,第四章 人工智能中的谓词逻辑 指派：命题公式含有n个不同的原子命题P1Pn, 它的任意一组确定值(P01,P0n),P0it,f称为的一个指派。指派分为成真指派，成假指派。 永真公式:若的任一指派都使为真(假)，则称为永真(假)公式，存在成真指派则也称为可满足公式。下面是三个永真
5、公式：P(PQ), (PQ)P (PQ)(RS)(PR)(QS) 一般情况下可以列出公式的真值表确定其永真性。 等值公式：设两公式, 对于任意指派都同时取相同的真假值，则称, 为等值公式，记成= 。,常用的等值公式表,第四章 人工智能中的谓词逻辑 替换定理：设公式是公式的部分公式，则将中的某些出现替换成与等值的公式得到的新公式=。 代入规则:等值公式中用任一公式代入等值公式中任一原子命题(处处代入)，则仍为等值公式。 例子1：设=P(QR)，由于(QP)=(QP)，所以用右侧的公式代入的部分公式(QP)中得到的新公式与原公式等值，即：P(QR)=P(QP) 利用上述定理还可以证明一些新的复杂等
6、值公式。但是我们时常需要判断一些公式的永真性和可满足性，最简单的方法是使用真值表，但当变元很多时，指派总数很大，非常麻烦。因此常用二杈树方法确定性质。,第四章 人工智能中的谓词逻辑 二杈树方法(例): =(PQ)R)(PQ)(PR) 将P用t代入作为左分支，f代入作为右分支，依次代Q，R得,(PQ)R)(PQ)(PR),(QR)Q)R,RR,t,t,R=t,R=f,Q=t,Q=f,P=t,P=f,t,t,1、置值时可以从公式中选出现次数最多的符号首先指定值； 2、根据二杈树方法还可以确定该公式所有的指派。,第四章 人工智能中的谓词逻辑 4.3 对偶定理 (最小)完全联结词: 任何一个公式都能够
7、用联结词集S表达成一个与等值的公式，则S称为完全联结词集。若S中每个联结词都是独立的则称其为最小联结词集。常见的最小联结词集有, 对偶公式：设是由,表达的命题公式，将其中的换成, 换成得到的新公式*称为的对偶公式。引 理：设*是的对偶公式,且中含有原子命题P1 , , Pn, 则 (P1Pn)= *(P1Pn) 对偶定理：若和满足=，则对偶公式*和*也满足*=*。,第四章 人工智能中的谓词逻辑 4.4 析取范式和合取范式 定 义: 若公式是由一些原子命题或它的非利用合取联结词()组成的，则称为简单合取式(简单析取式)。即由,或,与原子命题组成，如P1P2P3 显然它们都有特殊的性质，如唯一的成
8、真或成假指派。 定理1：设1n为P1Pm的公式，则合取式1n的成真指派等于1n成真指派的交集，而成假指派是1n成假指派的并集。 定理2：任公式都可以表示为简单合取式的析取(析取范式)，也可以表示为简单析取式的合取(合取范式)。,第四章 人工智能中的谓词逻辑 上述定理表明知道一个公式的成真指派可以写出该公式。 例题:设有四个原子命题P1,P2,P3,P4,其成真指派为txft, ftxf,txxf,则对应的简单合取为P1P3P4,P1P2P4, P1P4,则其析取范式为 =(P1P3P4)(P1P2P4)(P1P4) 任何都可以用等值公式将其化为析取(合取)范式： 1.使用公式 P Q=(PQ)
9、(QP) PQ=PQ 消去联结词“ ”及“” 2.使用 P=P,(PQ)=PQ,(PQ)=PQ 3.反复使用 P(QR)=(PQ)(PR) P(QR)=(PQ)(PR) 将公式化为范式,第四章 人工智能中的谓词逻辑 例题1:将(P(QR)S化为合取范式 (P(QR)S = (P(QR)S = (P(QR)S = (P(QR)S = (P(QR)S = (PQ)(PR)S = (PQS)(PRS) 例题2:将P (QR)化为析取范式 P (QR)=(P(QR)(QR)P) = (P(QR)(QR)P) = (P(QR)(QR)(P(QR)P) = (P(QR)(QR)(QR)(QR)P) = (
10、PQ)(PR)(QRQ)(QRR)(QRP) = (PQ)(PR)(PQR),第四章 人工智能中的谓词逻辑 4.5 逻辑推理 例题1: 如果天气干旱则粮食歉收,又设当粮食歉收时大多数人是不幸的，再设天气干旱，那么可以指出大多数人是不幸的。 设相应的陈述表示为：P表天气干旱，S表粮食丰收，U表大多数人是幸运的。题目中相应的四个陈述分别表示为：PS,SU, P,U。我们指出当上述表示均为真时，U为真。将上述式子的合取化为范式： (PS)(SU)P = P(PS)(SU) = = PSU 如果(PS)(SU)P为真，那么PSU为真，进而必须P、S、U均为真，所以得U为假，此时逻辑上称U是(PS)、(
11、SU)和P的逻辑结果。,第四章 人工智能中的谓词逻辑 定义: 设命题公式序列1n及命题公式，如果对任何使1n成真的指派也使成真，则称为1n的逻辑推论(逻辑结果)，记成： 1n|=。 定理1：设1n及均为命题公式，则1n|= 当且仅当 (1n) 是永真的。 定理2：设1n及均为命题公式，则1n|= 当且仅当 1n 是永假的。 证明：由上知是逻辑结果当且仅当(1n)是永真的，因此(1n)是永假的，而 (1n) = (1n) = 1n 因此定理得证。,第四章 人工智能中的谓词逻辑 4.6 一级谓词逻辑的基本概念 4.6.1 谓词: 谓词是指个体所具有的性质或若干个体之间的关系，如“数理逻辑是科学”分
12、为两部分，主语“数理逻辑”与谓表语“是科学”。“3整除6”，表现3和6间的整除关系。其中“数理逻辑”、 “3”、“6”也可以是抽象的x,y等称为个体变元。“是科学”、“整除”是谓词。 一般用A、B、C等表示谓词，如x,y间的关系写成B(x,y),谓词中有n个体变元则称为n元谓词，0元谓词就是命题，记为P、Q、R等。为方便常用一些符号直接表示谓词，如“等于”直接用“=”表示，这样E(x,y)写成“x=y”。 单独的谓词没有意义，必须赋予个体，通常把谓词填以个体后的式子称为谓词填式。如“张山高于李四，则张山高于王五”，用A表示“高于”，a,b,c分别表示“张山”、“李四”、“王五”，则上述谓词填式
13、表示为A(a,b) A(a,c),第四章 人工智能中的谓词逻辑 4.6.2 量词: 量词有全称量词和存在量词，分别记为 “ x”和“x”,意思为“对于所有的x”和“存在一个x”。当写 xP(x)和yQ(x,y)时称其为量词的作用域，x称为约束变元，y称为自由变元。变元的取值范围称为个体域。 例：“任何整数是正的或负的”，用M(x)表x是整数，P(x)表x是正数，N(x)表x是负数，则整个语句表示为 x(M(x)P(x)N(x) 而如果事先约定个体域是全体整数，则可以表示为 x(P(x)N(x) 注意在受量词约束的变元中，变元用什么记号是不重要的，如 x(P(x)N(x) 与 y(P(y)N(y) 是等价的。,第四章 人工智能中的谓词逻辑 4.6.3 函词: 函词是以个体为变元，同时以个体为值的函数，如果变元有n个就称为n元函词。 例如“小华的父亲”，“x的父亲”中的“的父亲”是一元函词，用F表示“的父亲”，I表示小华，则上述语句表示为F(i)和F(x)。 又如“3与4的乘积”，“x与y的乘积”中，“的乘积”是二元函词，用F表示，则上述可以表示为F(3,4)和F(x,y),与谓词一样，函词填以个体或相当于个体的式子后叫做函词填式。其值可以为一个体的函词，约定0元函词记为a,b,c等，通常称它们为常量。,
