第5章谓词逻辑的等值和推理演算PPT课件

1、第5章 谓词逻辑的等值和推理演算l谓词逻辑研究的对象是重要的逻辑规律，谓词逻辑研究的对象是重要的逻辑规律，普遍有效式是最重要的逻辑规律，普遍有效式是最重要的逻辑规律，而等值而等值式、推理式都是普遍有效的谓词公式，式、推理式都是普遍有效的谓词公式，因因此等值和推理演算就成了谓词逻辑的基本此等值和推理演算就成了谓词逻辑的基本内容内容l这章的讨论，主要是以这章的讨论，主要是以语义的观点语义的观点进行的进行的非形式的描述，而严格的形式化的讨论见非形式的描述，而严格的形式化的讨论见第第6章所建立的公理系统章所建立的公理系统51 否定型等值式l等值：等值：若给定了两个谓词公式A，B，说A和B是等值的，如果

2、在公式A，B的任一解释(注意在谓词逻辑中，解释的范围还包含注意在谓词逻辑中，解释的范围还包含论域以外的其他要素，见论域以外的其他要素，见P65)下，A和B都有相同的真值l其他说法：其他说法：A，B等值当且仅当AB是普遍有效的公式(注意这里不再说重言式了)记作AB或AB。511 由命题公式移植来的等值式l 若将命题公式的等值式，直接以谓词公式代入命题若将命题公式的等值式，直接以谓词公式代入命题变项便可得谓词等值式由变项便可得谓词等值式由pp,pq=pq, (pq)r=(pr)(qr)可得可得(以下每两个为一对：无量词、有量词以下每两个为一对：无量词、有量词)P(x)P(x)(x)P(x)(x)P

3、(x)P(x)Q(x)P(x)Q(x)(x)P(x)(x)Q(x) (x)P(x)(x)Q(x)(P(x)Q(x)R(x)=(P(x)R(x)(Q(x)R(x)(x)P(x)Q(y)(z)R(z)=(x)P(x)(z)R(z)(Q(y)(z)R(z)512 否定型等值式（摩根律的推广） (x)P(x)=(x)P(x)(x)P(x)=(x)P(x)l 形式上看这对公式，是说否定词”可越过量词深入到量词的辖域内，但要把所越过的量词转换为，转换为. (1)(1)从语义上说明从语义上说明(2)(2)例：在例：在ll，22域上分析域上分析(x)P(x)=(P(1)P(2)=P(1)vP(2) =(x)

4、P(x)(x)P(x)=(P(1)vP(2)=P(1) P(2) =(x)P(x)(3)(3)语义上的证明语义上的证明l 证明方法：依等值式定义，A=B如果在任一解释I下A真B就真，而且B真A就真若证明(x)P(x)=(x)P(x)1. 设某一解释I下若(x)P(x)=T从而(x)P(x)=F，即有一个xoD,使P(Xo)=F于是P(xo)=T 故在I下(x)P(x)=T2. 反过来，设某一解释I下若 (x) P(x)=T即有一个xoD,使P(Xo)=T 从而P(Xo)=F 于是(x) P(x)=F即 (x)P(x)=T(4)(4)举例举例例1 “并非所有的动物都是猫”的表示设 A(x)：x是

5、动物B(x)：x是描原语句可表示成(x)(A(x)B(x)依否定型公式得例2 “天下乌鸦般黑”的表示设 F(x)：x是乌鸦G(x，y)：x与y是一般黑原语句可表示成(x)(y)(F(x)F(y) G(x,y)不难知道与之等值的公式是(x)(y)(F(x)F(y)G(x,y)即不存在x,y是乌鸦但不一般黑这两句话含义是相同的经计算有 5 52 2 量词分配等值式量词分配等值式一、含单独的命题变项，与x无关521 量词对、的分配律l 这是一组量词对这是一组量词对 、 的分配律，其中的分配律，其中q q是命题变项，是命题变项，与个体变元与个体变元x x无关，这是很重要的条件无关，这是很重要的条件l

6、我们仅对第一个等式给出证明，其余三个同样可我们仅对第一个等式给出证明，其余三个同样可证证l设在一解释I下，(x)(P(x)q)=T，从而对任一x D ，有P(x)q=T 若qT，则(x)P(x)q=T若qF，从而对任一x D ，有P(x) =T ，即有(x)P(x)=T，故仍有，(x)P(x)q=Tl反过来，设在一解释I下，(x)P(x)q=T，若q=T，则(x)(P(x)q)=T若q=F，必有(x)P(x)=T，从而对任一xD有P(x)=T，于是对任一x D有P(x)q=T故(x)(P(x)q)=T5 52 22 2 量词对量词对的分配律的分配律l 这是一组量词对的分配律，其中p，q是命题变

7、项，与个体变元x无关，这是很重要的条件l 5.2节介绍的等值公式中仅有这里的第一、二个公节介绍的等值公式中仅有这里的第一、二个公式有量词的改变！式有量词的改变！l 先证明其中的第一个等式先证明其中的第一个等式 依依5 52 21 1的等值式的等值式 依依5 5l l2 2的等值式的等值式l 再证明其中的第三个等式再证明其中的第三个等式 依依5 52 2l l的等值式的等值式l 其余两个等值式同样可证其余两个等值式同样可证二、辖域中无单独的命题变项二、辖域中无单独的命题变项5 52 23 3 量词量词 对对 、量词、量词 对对V V的分配律的分配律l 这是当这是当P(x)P(x)，Q(x)Q(x

8、)都含有个体变元都含有个体变元x x时，量词时，量词 对对 ，量词，量词 对对V V所遵从的分配律然而所遵从的分配律然而 对对V V， 对对 的分配律一般并不成立证明中使用了的分配律一般并不成立证明中使用了5.2.15.2.1中的解释方法。中的解释方法。(x)P(x)v(x)Q(x)=(x)(P(x)vQ(x)(x)(P(x)Q(x)=(x)P(x)(x)Q(x)一些例子一些例子5 52 24 4 变元易名后的分配律变元易名后的分配律( (在求前束范式时有很大作用在求前束范式时有很大作用) )l 这两个等值式，说明了通过变元的易名，仍可实现这两个等值式，说明了通过变元的易名，仍可实现 对对V

9、V， 对对 的分配律的分配律l 证明是容易的首先有变元易名等值式证明是容易的首先有变元易名等值式( ( x)P(x)= (x)P(x)= ( y y)P(y)P(y)( ( x)P(x)= (x)P(x)= ( y y)P(y)P(y)于是于是( ( x)P(x)v(x)P(x)v( x)Q(x)=x)Q(x)=( ( x)P(x)v(x)P(x)v( y)Q(y)y)Q(y)对对x x而言而言( ( y)Q(y)y)Q(y)相当于命题变项，与相当于命题变项，与x x无关，可推得无关，可推得(x)P(x)v(y)Q(y)=(x)(P(x)v(y)Q(y)对对y y而言，而言，P(x)P(x)相

10、当于命题变项与相当于命题变项与y y无关，又可推得无关，又可推得(x)(P(x)v(y)Q(y)=(x)(y)(P(x)vQ(y)同理(x)(y)(P(x)Q(y)=(x)P(x)(x)Q(x)然而(x)(y)(P(x)vQ(y)与(x)(P(x)vQ(x)是不等值的(x)(y)(P(x)Q(y)与(x)(P(x)Q(x)也是不等值的5 53 3 范范 式式l在命题逻辑里每一公式都有与之等值的范在命题逻辑里每一公式都有与之等值的范式，范式是一种统一的表达形式式，范式是一种统一的表达形式 对谓词逻辑的公式来说也有范式，其中对谓词逻辑的公式来说也有范式，其中前束前束范式与原公式是等值的范式与原公式

11、是等值的，而其他范式与原公，而其他范式与原公式只有较弱的关系。式只有较弱的关系。5 53 31 1 前束范式前束范式l 定义定义5 53 31 1 说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边(不含否定词)且这些量词的辖域都延伸到公式的末端，前束范式A的一般形式为 (Q1x1)(Qnxn)M(xl，xn)其中其中Q Qi i为量词为量词 或或 (il，n)，M称作公式A的母式母式( (基基式式) )，M中不再有量词不再有量词定理定理5 53 31 1 谓词逻辑的任一公式都可化为与之谓词逻辑的任一公式都可化为与之等值的等值的前束范式但其前束范式前束范式但其前束范式并不唯一并不唯

12、一l 经过这几步，便可求得任一公式的前束范式由于每一步变换都保持着等值性，所以，所得到的前束形与原公式是等值的l 这里的S(a，b，x，y，z)便是原公式的母式其中a,b为自由个体变项。l 由于前束中量词的次序排列，以及对母式都没有明确的限制，自然前束范式不是唯一的，如例1的前束范式也可以是 (x)(z)(y)(S(a,b,x,y,z)P)其中P可以是任一不含量词的普遍有效的公式。532 Skolem标准形l前束范式对前束量词没有次序要求，也没有其他要求如果对前束范式进而要求所有存在量词都在全称量词之左得到存在前束范式(略)，或是只保留全称量词而消去存在量词得到Skolem标准形。不难想像，仍

13、保持与原公式的等值性就不可能了，只能保持在某种意义下的等值关系(1) (1) 前束范式前束范式( (略略) )l 一个公式的前束范式为 (x1)(xi)(xi+1)(xn )M(x1，xn)即存在量词都在全称量词的左边，且可保持至少至少有一个存在量词(i1)，其中M(x1，xn)中不再含有量词也无自由个体变项 定理定理5.3.25.3.2 谓词逻辑的任一公式A，都可化成相应的前束范式，并且A是普遍有效的当且仅当其前束范式是普遍有效的。 这定理是说对普遍有效的公式，它与其前束范式是等值的，而一般的公式与其前束范式并不是等值的自然仅当自然仅当A A是普遍有效的，方使用是普遍有效的，方使用 前束范式

14、前束范式例2 求( x)( y)( u)P(x，y，u)的前束范式(P中无量词)l将一公式化成前束形，首先要求出前束形，再做前束，这个例子已是前束形了，便可直接求前束形l 首先将全称量词( y)改写成存在量词( y)，其次是引入谓词S和一个变元z，得S(x，z)，建立公式( x)(y)(u)(P(x，y，u)S(x，y)V(z)S(x，z)其中S(x，y)的变元，是(y)的变元y和(y)左边存在量词( x)的变元x, 附加的(z)S(x，z)中的变元z是新引入的未在原公式中出现过的个体，S也是不曾在M中出现过的谓词l 进而将(z)左移(等值演算)，便得前束范式( x)(y)(u)(z)(P(x

15、，y，u)S(x，y)VS(x，z)当原公式中，有多个全称量词在存在量词的左边，可按这办法将全称量词逐一地右移l 前束范式仅在普遍有效的意义下与原公式等值 前束形对谓词逻辑完备性的证明是重要的改写前=改写后：简单改写后=改写前：反证若A=( x)( y)( u)P(x，y，u)不是普遍有效，则存在解释I使A为F,于是( x)( y)( u)P(x，y，u)为F. 因此在解释I下，改写后B= ( x)(z)S(x，z)可为F,因为S是谓词变元。(2) (2) SkolemSkolem标准形标准形 另一种Skolem标准形是仅保留全称量词的前束形 定理定理5.35.3. .3 3 谓词逻辑的任一公

16、式A，都可化成相应的Skolem标准形(只保留全称量词的前束形)，并且A是不可满足的当且仅当其Skolem标准形是不可满足的l 这定理是说对不可满足的公式，它与其Skolem标准形是等值的，而一般的公式与其Skolem标准形并不是等值的自然仅当A是不可满足的方使用Skolem标准形.例3 求公式(x)(y)(z)(u)(v)(w)P(x,y,z,u,v,w)的Skolem标准形将一公式化成Skolem标准形，首先也要求出前束形这个例子已是前束形了，便可直接求Skolem标准形了首先将最左边的(x)消去，而将谓词P中出现的所有变元x均以论域中的某个常项a(a未在P中出现过,且不知道a具体是哪个常

17、量）代入。进而消去从左边数第二个存在量词(u)，因(u)的左边有全称量词(y)(z)，需将谓词P中出现的所有变元u均以y，z的某个二元函数f(y，z) (f未在P中出现过，且不知道f具体是哪个函数)代入最后按同样的方法消去存在量词(w)，因(w)的左边有全称量词(y)(z)和(v)，需将谓词P中出现的所有变元w均以y，z，v的某个三元函数g(y，z，v)(g未在P中出现过也不同于f)代入这样便得消去全部存在量词的Skolem标准形 (y)(z)(v)P(a,y,z,f(y,z),v,g(y,z,v)54 基本的推理公式l命题逻辑中有关推理形式、重言蕴涵以及基本的推理公式的讨论和所用的术语，都可

18、引入到谓词逻辑中并可把命题逻辑的推理作为谓词逻辑推理的一个部分来看待l这里所介绍的是谓词逻辑所特有的，在命题逻辑里不能讨论的推理形式和基本的推理公式。 54 .1 推理形式举例l例例1 所有的整数都是有理数，所有的有理所有的整数都是有理数，所有的有理数都是实数，所以所有的整数都是实数数都是实数，所以所有的整数都是实数引入谓词将这三句话形式化，可得如下推引入谓词将这三句话形式化，可得如下推理形式理形式: (x)(P(x)Q(x)(x)(Q(x)R(x)(x)(P(x)R(x)l例2 所有的人都是要死的，孔子是人，所以孔子是要死的，引入谓词将这三句话形式化，可得如下推理形式：(x)(A(x)B(x

19、)A(孔子)B(孔子)l例3 有一个又高又胖的人，必有一个高个子而且有个胖子。引入谓词将这两句话形式化，可得如下推理形式：(x)(C(x)D(x)(x)C(x)(x)D(x)l例4 若某一个体a具有性质E，那么所有的个体x都具有性质E这两句话形式化，可得如下推理形式：E(a)(x)E(x)l不难看出，由例1，2，3所建立的推理形式是正确的，而例4的推理形式是不正确的5.4.2 5.4.2 基本的量词推理公式基本的量词推理公式(1)(1) ( ( x)P(x)V(x)P(x)V( x)Q(x)=(x)Q(x)=( x)(P(x)VQ(x)x)(P(x)VQ(x)量词分配律量词分配律p73p73(

20、2) (x)(P(x)Q(x)=(x)P(x) (x)Q(x) 注意(1)(1)的逆否的逆否,例3(3) (x)(P(x)Q(x)=(x)P(x)(x)Q(x) 5.2.25.2.2的推广的推广(4) (x)(P(x)Q(x)=(x)P(x)(x)Q(x) 5.2.25.2.2的推广的推广(5) (x)(P(x)Q(x) )=(x)P(x) (x)Q(x) (3)(3)的推广的推广(6) (x)(P(x) Q(x)=(x)P(x) (x)Q(x) (4)(4)的推广的推广(7) (x)(P(x)Q(x) (x)(Q(x)R(x)=(x)(P(x)R(x) 例例1 1(8) (x)(P(x)Q(

21、x) P(a)=Q(a) 例例2 2(9)(x)(y)P(x,y)=(x)(y)P(x,y)易理解易理解(10)(x)(y)P(x,y)=(y)(x)P(x,y)易理解，注意右边易理解，注意右边x x是是y y的函数的函数这些推理公式或称推理定理的逆一般是不成立的，这些推理公式或称推理定理的逆一般是不成立的，所以正确地理解这些定理的前提与结论的不同是重所以正确地理解这些定理的前提与结论的不同是重要的。要的。5.5 5.5 推理演算推理演算l命题逻辑中引入推理规则的推理演算，可命题逻辑中引入推理规则的推理演算，可推广到谓词逻辑，有关的推理规则都可推广到谓词逻辑，有关的推理规则都可直直接移入接移入

22、到谓词逻辑，除此之外还需介绍到谓词逻辑，除此之外还需介绍4 4条条有关量词的消去和引入规则有关量词的消去和引入规则l( (代入规则需补充说明：保持合式公式和普代入规则需补充说明：保持合式公式和普遍有效性不被破坏，见遍有效性不被破坏，见p58)p58)5 55 51 1 推理规则推理规则(1)(1)全称量词消去规则全称量词消去规则(x)P(x)=P(y)注：1其中y是论域中任意一个体2需限制y不在P(x)中约束出现(右侧量不在左侧约束出现) 如(x)P(x)(x)(y)(xP(y)因P(y)会有问题(2)全称量词引入规则P(y) =(P(y) =( x)P(x)x)P(x)注：注：1 1任一个体

23、任一个体y(y(自由变项自由变项) )都具有性质都具有性质P P2 2仍需限制仍需限制x x不在不在P(y)P(y)中约束出现中约束出现(右侧量不在左侧约束出现) 如如P(y)P(y)( ( x)(xy)x)(xy)时，时，P(x)P(x)会会有问题有问题(3)(3)存在量词消去规则存在量词消去规则(x)P(x)=P(c)注1. c是论域中使P为真的某个个体常项2. 需限制(x)P(x)中没有自由个体出现3. 还需限制P(x)中不含有c (右侧量不在左侧出现) 如在实数域上(x)P(x)=(x)(cP(c)的正确性(4)存在量词引入规则P(c)=(x)P(x)注：1. c是论域中使P为真的一个

24、特定个体常项2. 需限制x不出现在P(c)中(右侧量不在左侧出现) 如实数域上，P(c)( x)(xc)时，P(x)会出问题l这4条推理规则是基本的，对多个量词下的量词消去与引入规则的使用也已谈到再明确说明一下(x)(y)P(x，y)=(y)P(x，y)的右端，不允许写成(y)P(y，y)，(x)P(x，c)=(y)(x)P(x，y)的右端不允许写成(x)(x)P(x，x)。(x)(y)P(x，y)=(y)P(x，y)=P(x，a)但不允许再推演出(x)P(x，a)和(y)(x)P(x，y)原因是(x)(y)P(x，y)成立时，所找到的y是依赖于x的，从而P(x，y)的成立是有条件的，不是对所

25、有的x对同一个a都有P(x，a)成立，于是不能再推演出(y)(x)P(x,y)552 使用推理规则的推理演算举例l 和命题逻辑相比，在谓词逻辑里使用推理规则进行推理演算同样是方便的，然而在谓词逻辑里，真值表法不能使用真值表法不能使用，又不存在判明不存在判明AB是普遍有是普遍有效的一般方法效的一般方法，从而使用推理规则的推理方法已使用推理规则的推理方法已是谓词逻辑的基本推理演算方法是谓词逻辑的基本推理演算方法l 推理演算过程首先首先是将以自然语句表示的推理问题引入谓词形式化，若若不能直接使用基本的推理公式便消去量词，在无量词下使用规则和公式推理，最后再引入量词以求得结论例1 前提 (x)(P(x

26、)Q(x)，(x)(Q(x)R(x) 结论 (x)(P(x)R(x)证明 (1)(x)(P(x)Q(x) 前提 (2)P(x)Q(x) 全称量词消去全称量词消去 (3)(x)(Q(x)R(x) 前提 (4)Q(x)R(x) 全称量词消去 (5)P(x)R(x) (2)，(4)三段论 (6)(x)(P(x)R(x) 全称量词引入全称量词引入例2 所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的首先引入谓词形式化，令P(x)表x是人，Q(x)表x是要死的，于是问题可描述为 (x)(P(x)Q(x)P(苏格拉底)Q(苏格拉底)证明 (1)(x)(P(x)Q(x) 前提 (2)P(苏格拉底)Q(

27、苏格拉底) 全称量词消去 (3)P(苏格拉底) 前提 (4)Q(苏格拉底) (2)(3)分离规则分离规则例3 前提(x)P(x)(x)(P(x)VQ(x)R(x)，(x)P(x) 结论(x)(y)(R(x)R(y)证明 (1)(x)P(x)(x)(P(x)VQ(x)R(x) 前提 (2)(x)P(x) 前提 (3)(x)(P(x)VQ(x)R(x) (1)，(2)分离 (4)P(c) (2)存在量词消去存在量词消去 (5)P(c)VQ(c)R(c) (3)全称量词消去 (6)P(c)VQ(c) (4) (7)R(c) (5)，(6)分离 (8)(x)R(x) (7)存在量词引入存在量词引入 (

28、9)(y)R(y) (7)存在量词引入 (10)(x)R(x)(y)R(y) (8)，(9) (11)(x)(y)(R(x)R(y) (10)置换例4(不正确) 分析下述推理的正确性 (1)(x)(y)(xy) 前提 (2)(y)(zy) 全称量词消去,y y与与z z有关有关 (3)zb 存在量词消去,b b依赖依赖z z (4)(z)(zb) 全称量词引入,b b不依赖不依赖z z (5)bb 全称量词消去 (6)(x)(xx) 全称量词引入 推理(1)到(2)，应明确指出y是依赖于x的，即(2)中y和z有关(2)到(3)，其中的b是依赖于z的从而(3)到(4)是不成立的又由于b是常项，(5)到(6)也是不允许的，因个体常项不能用全称量词量化56 谓词逻辑的归结推理法l归结方法可推广到谓词逻辑，困难在于出现了量词，变元证明过程同命题逻辑，只不过每一步骤都要考虑到有变元，从而带来复杂性l使用推理规则的推理演算过于灵活，技巧性强，而归结法较为机械，容易使用计算机来实现。5.6.1 谓词逻辑归结证明过程四步骤(从例子来理解步骤)(1)为证明AB是定理(A，B为谓词公式)，即AB, 等价的是证明G=AB是矛盾式，这是归结法的出发点(反证法)(2)通过G的合取形式建立子句集S，在建立子句集S的时利用前束范式及Skolem标准形(不严格)，消去存在量