离散数学第二章.ppt

1、第四篇图论,1.命题逻辑,2.谓词逻辑,3.集合与关系,4.函数,6.布尔代数,5.代数结构,目录,.图论,第一篇数理逻辑,第二篇集合论,第三篇代数结构,绪论,用命题逻辑处理苏格拉底三段论：,谓词逻辑,又例:张华是大学生,李明也是大学生。,所有的自然数都等于1.(F);存在着自然数等于1.(T),P,Q,R,人总是要死的,苏格拉底是人,苏格拉底是要死的。,若论证有效则有:PQR,即PQR永真.,谓词逻辑,对简单命题作进一步分析,分离出个体和谓词,并考虑到泛指和特指(全称和存在),在此基础上,研究命题的逻辑结构及命题间的推理关系。,PredicateLogic,第二章,-1谓词的概念与表示,-2

2、量词,-3谓词公式,-5等价式与重言式,-7谓词演算的推理理论,26前束范式,谓词逻辑,-4谓词公式的解释,谓词逻辑谓词公式,本节课主要讨论以下问题：1.命题如何分解？2.命题如何表示？3.命题如何符号化？,命题是具有确定真值的陈述句。,2-1谓词的概念和表示,如“电子计算机是科学技术的工具。”,个体:思维的对象,可以是具体的事物或抽象的概念,谓词:刻画个体性质或个体之间关系的词。,1.个体和谓词,陈述句由主语和谓语两部分构成，,主语,谓语,个体,谓词,一元谓词:与一个个体相关联的谓词.(描述个体性质),N元谓词:与N个个体相关联的谓词.(描述个体间的关系),谓词逻辑谓词的概念和表示,(a).

3、他是三好学生。,(b).7是质数。,(c).每天作广播操是好习惯。,(d).5大于3.,(e).地球绕着太阳转。,一元谓词。谓词刻画个体性质,(f).张明和张亮是兄弟。,(e).上海位于南京和杭州之间。,谓词刻画个体间关系。,在谓词逻辑中,命题是由一个谓词和若干有序个体组成的。,谓词逻辑谓词的概念和表示,二元谓词,二元谓词,二元谓词,三元谓词,2.个体和谓词的表示,命题由一个谓词和若干个体组成,谓词逻辑谓词的概念和表示,用大写字母A,B,C,D,.代表谓词。用小写字母代表个体：用小写字母a,b,c.表示特定个体:个体常元用小写字母x,y,z.表示任意个体：个体变元.,一个n元谓词记作:A(x1

4、,x2,xn)其中x1,x2,xn为个体变元.当A(x1,xn)中个体变元用个体常元:a1,an代入后,A(a1an)就成为一个命题。,则A(a)表示命题:张华是大学生,A(b)表示命题:李明是大学生。,例:令A(x):x是大学生;a:张华,b:李明,并非任意个体都和任意谓词都能构成命题。,如:2是偶数,(T),个体域:个体的取值范围,用D表示,如谓词“.是偶数”的个体域D:全体整数。“.是要死的”D:全体生物或D:人类,全总个体域:所有个体的集合称之。,谓词逻辑谓词的概念和表示,3是偶数,(F),x是偶数(不是命题),当谓词确定后,其允许的个体取值范围称为个体域。,则A(a)表示命题:张华是

5、大学生,A(b)表示命题:李明是大学生。,例:令A(x):x是大学生;D:人类a:张华,b:李明,又例:上海位于南京和杭州之间。,令L(x,y,z):x位于y和z之间,D:城市,则命题符号化为:L(a,b,c),谓词逻辑谓词的概念和表示,则L(2,3)表示命题:2量词,4.个体函数,例如:张华的母亲爱张华.,-1谓词的概念与表示,-2量词,-3谓词公式,-5等价式与蕴含式,-7谓词演算的推理理论,26前束范式,谓词逻辑,-4谓词公式的解释,例如:任何人都是要死的.(T),有些人是聪明的.(T),所有的自然数都等于1.(F),存在着自然数等于1.(T),对个体域中的所有个体成立,对个体域中的某些

6、个体成立,当命题的主语是泛指时,命题的真值还取决于谓词与个体域中个体的数量关系.,谓词逻辑量词,2-2量词,1.全称量词与存在量词,两种,量词:命题中表示个体数量的词。,全称量词(UniversalQuantifier):表示个体域中全体个体的词，记作相当于“任意”,“凡是”,“所有”.,若个体域中所有个体x,均使A(x)为真,记作(x)A(x),存在量词(ExistentialQuantifier):表示个体域中部分个体的词，记作相当于“存在”,“至少有一个”,“有些”.,若个体域中存在某些个体x,使A(x)为真,记作(x)A(x),谓词逻辑量词,设H(x):x是要死的,任何人都是要死的。,

7、例如:,则命题表示为:(x)H(x),个体域D:人类,又例如:有些人是聪明的.,设A(x):x是聪明的,个体域D:人类,则命题表示为:(x)A(x),谓词逻辑量词,当在全总个体域中讨论命题时,需在命题表示中增加一个特性谓词,以给出个体变元的个体域。,2.特性谓词,(1)带全称量词的命题,特性谓词作为加入.,任何人都是要死的,例如:,M(x):x是人,则命题表示为：(x)(M(x)H(x),改为:,谓词逻辑量词,设H(x):x是要死的个体域D:全人类则命题表示为：(x)H(x)。,H(x):x是要死的,条件式的前件,例如:有些人是聪明的.,个体域D：人,设A(x)：x是聪明的,则命题表示为:(x

8、)A(x),改为:,A(x)：x是聪明的,则命题表示为:(x)(M(x)A(x),(2)带存在量词的命题,特性谓词作为合取项加入。,为何特性谓词以前件加在全称量词后,而以合取项加在存在量词后?能否改为:,(x)(H(x)M(x)和(x)(M(x)A(x)?,谓词逻辑量词,M(x):x是人,3.命题符号化,谓词逻辑量词,日常用语翻译,用谓词逻辑处理苏格拉底三段论：,人总是要死的,苏格拉底是人,所以,苏格拉底是要死的。,a:苏格拉底,M(x):x是人,(x)(M(x)P(x),M(a),P(a).,令,谓词逻辑量词,例题,P(x):x是要死的,推理形式为:(x)(M(x)P(x),M(a)P(a)

9、.,1.判断是否复合命题(看有几个主谓结构或连接词).2.对复合命题找出每个原子命题.3.对每个原子命题分出主语和谓语,主语若是泛指需加量词和特性谓词.并用符号表示.4.分析各原子命题的关系,确定连接词.,存在着最小的自然数.,谓词逻辑量词,P61例题,补例兔子比乌龟跑的快,例题3尽管有人聪明,但未必一切人都聪明.,例题1并非每个实数都是有理数.,每个人都有自己喜欢的职业.,R(x):x是实数,设Q(x):x是有理数,故符号化为:(x)(R(x)Q(x),M(x):x是人,设P(x):x是聪明的,(x)(P(x)M(x)(x)(M(x)P(x),谓词逻辑谓词公式,1.命题被分解为哪几个部分？2

10、.谓词如何表示？3.什么是个体域？4.何时使用量词？量词有哪几种？5.如何使用特性谓词？6.谓词逻辑中命题如何符号化？,谓词逻辑谓词公式,1.什么是个体和谓词？2.谓词如何表示？每个命题有一个谓词和若干个体组成.当谓词确定后,命题的真值依赖个体,因此采用函数的记法表示谓词：P(x1,x2,.xn)，3.什么是个体域？x1,x2,.xn的取值范围称为个体域D4.什么是量词？当句子的主语是泛指的时候,用量词符号,表示个体数量5.如何使用特性谓词？通过在命题表达中加入特性谓词,以说明命题中个体的范围.6.命题符号化“每个计算机系的学生都学离散数学“存在着最小的自然数.”,命题逻辑逻辑连接词,作业,2

11、-1，2-2（1）（e）,（f）,（g）,（h）2-3（3）,本节重点掌握的概念:个体，谓词,量词,个体域。本节重点掌握的方法:命题符号化。特别注意特性谓词的两种使用方法。,-1谓词的概念与表示,-2量词,-3谓词公式,-5等价式与蕴含式,-7谓词演算的推理理论,26前束范式,谓词逻辑,-4谓词公式的解释,2-3谓词公式,如P,P(x),P(x,y),P(f(x),y),P(a,y)均原子公式。,1.谓词公式,补充定义(项)1).个体常元和个体变元是项.2).若f是n元个体函数,t1,.,tn是项,则f(t1,.tn)是项.3).只有有限次运用1),2)规则得到的符号串是项.,如x,a,f(x

12、),g(x,y),g(f(x),a).,谓词逻辑谓词公式,项代表公式中以各种形式出现的个体.,原子公式:把A(t1,t2,tn)称为谓词演算的原子公式，其中,t1,t2,tn是项.,不含个体变元的原子公式是原子命题.,定义2-3.1谓词演算的合式公式wff,由下述各条组成：(1)原子谓词公式是合式公式。(2)若A是合式公式,则A是合式公式。(3)若A和B都是合式公式,则(AB),(AB),(AB)和(AB)是合式公式。(4)如果A是合式公式,x是A中出现的任何变元,则(x)A和(x)A都是合式公式。(5)只有经过有限次的应用规则(1),(2),(3),(4)所得到的公式是合式公式。,简称谓词公

13、式,如,xyP(x,y),xP(f(x),y),谓词逻辑谓词公式,P(a,y)Q,2.变元的约束,若给定为一谓词公式,它可带有如下子公式:,(x)A(x)或(x)A(x),指导变元,辖域,约束变元,其中,、后的x称为该量词的指导变元;A(x)称为量词的作用域或辖域(scope);在辖域中x的一切出现称为x在中的约束出现,x称为约束变元;在中除约束变元以外所出现的变元称为自由变元。,P63例题1,如,x(M(x)R(x),yP(x,y)R(y),谓词逻辑谓词公式,闭式:不含自由变元的公式.开式:含有自由变元的公式.其中,含有k个自由变元x1,x2,.xk的公式称为k元谓词,记作A(x1,x2,.

14、xk),0元谓词为闭式.,例如(x)P(x,y,z),x是小于100的质数:L(x,100),又如任意的实数x,都存在着实数y,使得x谓词公式的解释,令P(x,y):xy,D:自然数,xyP(x,y)(闭命题),(F),例,(T);,令P(x,y):x+y=0,D:自然数,Q(x,y)P(x,y)(开命题),例,令D:自然数;P(x,y):x谓词公式的解释,给定解释I和I中的赋值如下:DI:自然数集,L(x,y):x谓词公式的解释,谓词逻辑谓词公式的解释,求下列闭式在解释I下的真值,给定解释I如下:D=2,3,f(2)=3,f(3)=2,P(2)=TP(3)=F,Q(2,2)=T,Q(3,3)

15、=T,Q(2,3)=F,Q(3,2)=F.,解,1)x(Q(f(x),x)P(x)2)x(y)Q(x,y),1).原式=(Q(f(2),2)P(2)(Q(f(3),3)P(3)=(Q(3,2)P(2)(Q(2,3)P(3)=(FT)(FF)=T,2).原式=x(Q(x,2)Q(x,3)=(Q(2,2)Q(2,3)(Q(3,2)Q(3,3)=(TF)(FT)=T,yxQ(x,y)的真值?,补例,谓词逻辑谓词公式的解释,求(x)(y)(P(x)Q(x,y)在解释I的真值,DI=1,2,P(1)=F,P(2)=T,Q(1,1)=T,Q(2,2)=T;Q(1,2)=F,Q(2,1)=F.,原式=(x)

16、(P(x)Q(x,1)(P(x)Q(x,2),=(P(1)Q(1,1)(P(1)Q(1,2)(P(2)Q(2,1)(P(2)Q(2,2),=(FT)(FT)(FF)(TT),=F,补例,谓词逻辑谓词公式的解释,课堂练习1.“并非一切推理都能用计算机完成”符号化为()2.设R(x):x是实数,P(x,y):x=y,则命题“对任意的实数x,y,有x+y=y+x”符号化为()3.不含有自由变元的谓词公式是命题.()4.yE(x,y)L(x,y,z)是二元谓词()5.使一阶逻辑公式yxF(y,x)为真的解释是()A.个体域为自然数集合，F(x,y)为xyB.个体域为自然数集合，F(x,y)为y谓词公式

17、的解释,本节重点掌握的概念:谓词公式,自由变元,约束变元,开式,闭式。本节重点掌握的方法:求谓词公式的真值,要点回顾,谓词逻辑等价与蕴含式,1.个体和谓词2.谓词的表示:P(x1,x2,.xn)3.量词4.特性谓词5.谓词公式6.谓词公式的赋值:对谓词公式一个赋值称为一个解释。闭式在一组解释下会求得一个真值；开式还需在此基础上对自由变元赋值，才能求出一个真值。例:对任意的自然数x存在着自然数y,使得p(x,y)成立.解释1：p(x,y):x等价与蕴含式,命题逻辑永真式（永假式）的代换实例是谓词逻辑的永真式（永假式）。,设A是包含命题变元P1,P2,.Pn的命题公式,B1,B2,.Bn是谓词公式

18、,用B1,B2,.Bn分别代替P1,P2,.Pn在A中的所有出现,得到的谓词公式B称A的代换实例,命题逻辑永真式的代换实例称为重言式.,谓词逻辑等价与蕴含式,命题逻辑的代入定理:一个重言式,对同一分量都用任何合式公式置换,结果仍重言.,谓词逻辑等价与蕴含式,上式可看作命题公式PP的代入实例,1)(x)P(x)(x)P(x),2)(xP(x)(xQ(x)xP(x),上式可看作命题公式(P(QP)的代入实例,而(P(QP)(P(QP)F,所以,(xP(x)(xQ(x)xP(x)为永假式,而PPT,所以,(x)P(x)(x)P(x)为重言式,判定公式的类型,重言式是永真式,但永真未必重言.,例如xP

19、(x)xP(x)是永真式，但不是重言式.,补例,2.等价与蕴含,定义2-5.1设A,B是公式,若AB是永真式,则称A,B等价.记作AB.,等价式的判定,等价演算:利用基本公式、等价的性质和置换定理，推演出其他等价式.,定义2-5.2设A,B是公式,若AB是永真式,则称A蕴含B.记作AB.,谓词逻辑等价与蕴含式,AB当且仅当AB且BA,(1)命题公式的推广,例如PQPQ,用xP(x)代替P;,(x)P(x)(x)Q(x)(x)P(x)(x)Q(x),xQ(x)代替Q得到:,(x)(P(x)Q(x)(x)R(x)(x(P(x)Q(x)(x)R(x),同理P(x)Q(x)P(x)Q(x),利用代入定

20、理,将命题逻辑的所有等价式推广到谓词逻辑.,谓词逻辑等价与蕴含式,(2)量词与联结词的关系,例设P(x):x今天来校上课,D:学生则P(x)表示:x今天没来校上课,“并非所有人今天来校上课”(x)P(x)“有人今天没来校上课”(x)P(x),(x)P(x)(x)P(x),“没有人今天来校上课”(x)P(x)“所有人今天都没来校上课”(x)P(x),(x)P(x)(x)P(x),谓词逻辑等价与蕴含式,(3)量词作用域的扩张与收缩,(x)(A(x)B)(x)A(x)BB(x)A(x),(x)(A(x)B)(x)A(x)BB(x)A(x),(x)A(x)B(x)(A(x)B),(x)A(x)B(x)

21、A(x)B),B(x)A(x)(B(x)A(x),B(x)A(x)(B(x)A(x),由上式可推出,谓词逻辑等价与蕴含式,(4)量词与联结词之间的一些等价式,例,第一式中用A代A,用B代B：,(x)(A(x)B(x)(x)A(x)(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x),与“联欢会上所有人唱歌且所有人跳舞”意义相同,(x)(A(x)B(x)(x)A(x)(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x),对满足分配律,对满足分配律,“联欢会上所有人即唱歌又跳舞.”,谓词逻辑等价与蕴含式,(x)(

22、A(x)B(x)(x)A(x)(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x)?,(x)(A(x)B(x)(x)A(x)(x)B(x)?,(x)(A(x)B(x):对所有的x,有A(x)或B(x)成立.,(x)(A(x)B(x):存在着x,使A(x)和B(x)同时成立.,例D:整数集合,A(x):x是偶数,B(x):x是奇数,(x)A(x)(x)B(x)(T)(x)(A(x)B(x)(F),谓词逻辑等价与蕴含式,(x)A(x)(x)B(x):对所有的x,A(x)成立;或对所有的x,B(x)成立.,(x)A(x)(x)B(x):存在着x,使A(x)成立,且存在x,使B(x)成

23、立.,(5)量词与联结词之间的一些蕴含式,(x)A(x)(x)B(x)(x)(A(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x),(x)(A(x)B(x)(x)A(x)(x)B(x),常见的等价式与蕴含式见表2-5.1,同理可得,谓词逻辑等价与蕴含式,(6)多个量词的使用,公式中多个量词的出现次序关系到命题的含义,不能随意交换.,例如,xyA(x,y):对任意x,都存在y,使得A成立.,例(x)(y)(x+y=0)为真命题,y=-x,yxA(x,y):存在着y,对所有的x都有A成立.,(y)(x)(x+y=0)为假命题,

24、谓词逻辑等价与蕴含式,y的值独立于x.,y的值依赖于x.,特殊情况:,全称量词之间可交换,存在量词之间可交换.,全称与存在之间存在如下关系:,I18(x)(y)A(x,y)(y)(x)A(x,y),I19(x)(y)A(x,y)(x)(y)A(x,y),I20(y)(x)A(x,y)(x)(y)A(x,y),I21(x)(y)A(x,y)(y)(x)A(x,y),I22(x)(y)A(x,y)(y)(x)A(x,y),I23(y)(x)A(x,y)(x)(y)A(x,y),谓词逻辑等价与蕴含式,例题,谓词逻辑等价与蕴含式,右式,验证(x)(A(x)B(x)(x)A(x)(x)B(x),(x)A

25、(x)(x)B(x),(x)A(x)(x)B(x),(x)(A(x)B(x),(x)(A(x)B(x),证明(x)P(x)(x)P(x)为永真式。,证明(P(x)(Q(x)P(x)为永假式。,例题,谓词逻辑等价与蕴含式,(x)P(x)(x)P(x),分析真值法:左右且右左.,给定公式(x)P(x)(x)P(x)一组解释I,若(x)P(x)在I下为真,则(x)P(x)为假,即存在aD,使P(a)为假,即P(a)为真,即(x)P(x)为真.,给定(x)P(x)(x)P(x)一组解释I,若(x)P(x)在I下为真,则存在aD,使P(a)为真,即P(a)为假,即(x)P(x)为真.,则(x)P(x)为

26、假,-1谓词的概念与表示,-2量词,-3谓词公式,-5等价式与蕴含式,-7谓词演算的推理理论,26前束范式,谓词逻辑,-4谓词公式的解释,谓词逻辑前束范式,2-6前束范式,定义2-6.1一个公式,如果量词均在全式的开头,它们的作用域,延伸到整个公式的末尾,则该公式叫做前束范式。,前束范式简记为:,(v1)(v2).(vn)A,或,指导变元,母式(不含量词),例如(x)(y)(z)(Q(x,y)R(z),(x)P(x)(x)Q(x)?,Q(x,y)R(z),定理2-6.1任一谓词公式,均和一个前束范式等价.,化前束范式的方法,(1).将公式中的连接词化为,.(非必须)(2).利用否定律,德.摩根

27、律,及量词转化律,将否定深入到谓词字母前.(3).利用换名规则或代入规则使所有约束变元均不相同且使所有的自由变元与约束变元不同.(4).利用量词的的扩张与收缩,扩大量词的辖域至整个公式.,谓词逻辑前束范式,例如(x)P(x,y)Q(x),(x)P(x)(x)Q(x),因为(x)P(x)(y)P(y),(x)P(x)(y)P(y),所以,若谓词公式中有变元既约束出现,又自由出现,为避免混淆,可对约束变元换名或对自由变元代入,使得一个变元在公式中只呈一种出现.,(1)对约束变元换名,其更改的变元名称范围是:量词中的指导变元及该量词辖域中出现的该变元,而公式中其余变元不变.,(2)对约束变元换名时一

28、定要更改为辖域中未出现的变元名.,换名规则,例如(x)P(x)(x)Q(x),(x)P(x)(y)Q(y),谓词逻辑前束范式,(x)(y)(P(x)Q(y),(x)(P(x)R(x,y)Q(x,y)=?,代入规则,(1).代入须对公式中该自由变元的所有出现同时进行.(2).代入的变元不能与公式中其它变元同名.,例如(x)P(x)Q(x,y),(x)P(x)Q(r,y),(x)(y)P(x,y)R(x,y,z),(x)(y)P(x,y)R(u,v,z),(x)(y)(P(x,y)R(u,v,z),谓词逻辑前束范式,(v1)(v2)(vn)(,其中可能是量词或,vi(i=1,2,n)是指导变元,A

29、ij是原子公式或其否定。,定义2-6.2一个wffA如果具有如下形式称为前束合取范式,例如(x)(z)(y)(P(x,y)(z=b)(Q(y)(a=b),定理2-6.2每一个wffA都可以转换为与它等价的前束合取范式。,谓词逻辑前束范式,其中可能是量词或,vi(i=1,2,n)是客体变元,Aij是原子公式或其否定。,定义2-6.3一个wffA如果具有如下形式称为前束析取范式,例如(x)(z)(y)(P(x,y)(z=b)(Q(y)(a=b),定理2-6.3每一个wffA都可以转换为与它等价的前束析取范式。,(v1)(v2)(vn)(,谓词逻辑前束范式,谓词逻辑前束范式,化前束范式的方法,(1)

30、.将公式中的连接词化为,.(非必须)(2).利用否定律,德.摩根律,及量词转化律,将否定深入到谓词字母前.(3).利用换名规则或代入规则使所有约束变元均不相同且使所有的自由变元与约束变元不同.(4).利用量词的的扩张与收缩,扩大量词的辖域至整个公式.,前束范式：(v1)(v2).(vn)A,谓词逻辑前束范式,例题xyz(P(x,z)P(y,z)uQ(x,y,u)化为前束析取范式.,谓词逻辑前束范式,例题xyP(x)zQ(z,y)yR(x,y)的前束合取范式,原式,消去多余,xP(x)zQ(z,y)yR(x,y),换名,xP(x)zQ(z,y)wR(x,w),自由,w,消去其它,x(P(x)zQ

31、(z,y)wR(x,w),否定深入,x(P(x)zQ(z,y)wR(x,w),量词提出,xzw(P(x)Q(z,y)R(x,w),分配律,xzw(P(x)R(x,w)(Q(z,y)R(x,w),量词,w,联结词,前束析取范式,作业,2-5（4）,（6）2-6(1)(a)(2)(a),(b),谓词逻辑前束范式,本节重点掌握的概念:谓词演算的永真式，重言式，等价式,蕴含式;前束范式.本节重点掌握的方法:证明永真式，等价式,求前束合取范式,析取范式.,-1谓词的概念与表示,-2量词,-3谓词公式,-5等价式与蕴含式,26前束范式,谓词逻辑,-4谓词公式的解释,-7谓词演算的推理理论,2-7谓词演算的

32、推理理论,设H1,H2Hn和C是谓词公式,当且仅当H1H2,HnC称C是一组前提H1,H2Hn的有效结论.,等价演算、分析真值、证明法。,判定谓词公式永真的各种方法都可用于判断推理正确性,谓词逻辑谓词演算的推理.,等价演算：AB即ABT,例：xP(x)xQ(x)x（P(x)Q(x)）,分析真值：设前件在一组解释下为真,推出后件也真；或证明后件在一组解释下为假时，前件也为假。,要证C是一组前提H1,H2Hn的有效结论,需证:H1H2,HnC是重言式即证:H1,H2Hn均为真时,C必为真.为描述这样一个推理过程,可构造一个命题公式序列:其中每个公式或是前提,或是由某些前提利用推理规则推出的.序列的

33、最后一个命题公式就是所要结论.这样一个描述推理过程的命题公式序列称为形式论证(证明或演绎法).,证明法,谓词逻辑谓词演算的推理.,P规则(前提引入规则):前提在推理过程中的任何时候均可引用.T规则(结论引入规则):在推理过程中,如有一个或多个公式蕴含公式S,则S可引入推导过程.,推理规则,命题逻辑推理理论,由于谓词公式中包含量词,还需增加一组处理量词的推理规则.,首先命题逻辑中的推理规则都可应用于谓词逻辑的推理中:,谓词逻辑谓词演算的推理.,(1)全称指定规则US,含义:若D中所有个体使A真,则D中任一个体t也使A真.,例(x)(y)(xy)P(不存在最大实数),例(x)P(x):所有的人都是

34、要死的P,P(a):苏格拉底是要死的.US,(y)(ay)US或(y)(x谓词演算的推理.,使用限制:x不能与A(t)中的自由变元或指导变元同名,例,(2)(y)(xy)US,(3)xaES,(1)(x)(y)(xy)P,取D:有理数,(4)(x)(x谓词演算的推理.,不是新常元,例,(2)(x)F(x)P,(3)F(a)G(a),US,(1)(x)(F(x)G(x)P,前提:(x)(F(x)G(x),(x)F(x)结论:(x)G(x),(4)F(a)ES,(5)G(a)EG,不是新常元,(6)(x)G(x)EG,(2)(x)F(x)P,(4)F(a)G(a)ES,(1)(x)(F(x)G(x

35、)P,(3)F(a)UG,(5)G(a)EG,(6)(x)G(x)EG,谓词逻辑谓词演算的推理.,谓词逻辑谓词演算的推理.,例题1证明(x)(H(x)M(x)H(s)M(s),证明,(1).(x)(H(x)M(x)P,(2).H(s)M(s)US,T1,(3).H(s)P,(4).M(s)T2,3,I13,(苏格拉底三段论),P76例题1,命题逻辑逻辑连接词,例题2证明(x)(C(x)W(x)R(x)(x)(C(x)Q(x)(x)(Q(x)R(x),证明,(1).(x)(C(x)Q(x)P,(2).C(a)Q(a)T2,ES,(3).C(a)T3,I1,(5).(x)(C(x)W(x)R(x)

36、P(6).C(a)W(a)R(a)T1,3,US,(4).Q(a)T3,(7).W(a)R(a)T4,5,I,(8).R(a)T6,I,(9).Q(a)R(a)T7,8,I1,P77例题2,(10).(x)(Q(x)R(x)T9,EG,命题逻辑逻辑连接词,例题3(x)(P(x)Q(x)(x)P(x)(x)Q(x),(CP规则),x(P(x)Q(x)xP(x)xQ(x),(1).xP(x)附加P,(2).xP(x)T1,E,(3).P(c)T2,ES,(6).Q(c)T3,5,I,(4).x(P(x)Q(x)P,(7).xQ(x)T6,ES,(5).P(c)Q(c)T4,US,(8).xP(x)

37、xQ(x)CP规则,P77例题3,例题3(x)(P(x)Q(x)(x)P(x)(x)Q(x),(归谬法),(1).(x)P(x)(x)Q(x)附加P,(2).(x)P(x)(x)Q(x)T1,E,(3).(x)P(x)T2,E,(4).(x)P(x)T3,E,(5).(x)Q(x)T2,I1,(6).(x)Q(x)T5,E,(7).P(c)T4,ES,(8).Q(c)T6,US,(9).P(c)Q(c)T7,8,I,(10).(P(c)Q(c)T9,E,(11).(x)(P(x)Q(x)P,(13).(P(c)Q(c)(P(c)Q(c)T10,12,(12).P(c)Q(c)T11,US,P7

38、7例题3,命题逻辑逻辑连接词,补例所有的有理数是实数.某些有理数是整数.因此,某些实数是整数.,设:R(x):x是实数Q(x):x是有理数,P(x):x是整数,x(Q(x)R(x),(x)(Q(x)P(x)(x)(R(x)P(x),x（Q(x)R(x)）,(x)(Q(x)P(x),(x)(R(x)P(x),命题逻辑逻辑连接词,补例每个用功的学生考试不会不及格。小张是用功的学生。所以，小张考试及格。,设:P(x):x考试及格Q(x):x是学生,R(x):x是用功的。a:小张,x（Q(x)R(x)P(x)）,R(a)Q(a),P(a)Q(a),命题逻辑逻辑连接词,补例所有的有理数是实数.所有的无理

39、数是实数.虚数不是实数，所以虚数不是有理数也不是无理数.,设:R(x):x是实数Q(x):x是有理数,P(x):x是无理数。S(x):x是虚数,x（Q(x)R(x)）,x（P(x)R(x)）,x（S(x)R(x)）,x（S(x)Q(x)P(x)）,命题逻辑逻辑连接词,4.设R(x):x是实数,P(x):x是有理数,“并非每个实数都是有理数”符号化为()A.x(R(x)P(x)B.x(R(x)P(x)5.谓词公式xP(x)xQ(x)xP(x)的类型是_.6.在解释I:DI=1,2,P(1,1)=P(1,2)=0,P(2,2)=P(2,1)=1下,谓词公式xyP(x,y)的真值为_.7.公式xP(

40、x)xQ(x,y)前束合取范式为_.,课堂练习1.在谓词逻辑中,永真式都是重言式。()2.任意谓词公式都有唯一的前束范式与之等价。()3.(x)(A(x)B(x)(x)A(x)(x)B(x)(),命题逻辑逻辑连接词,作业,2-7（1）（a）,（b）（2）,本节重点掌握的概念:4个推理规则本节重点掌握的方法:推理的形式证明方法,谓词逻辑,PredicateLogic,第二章,本章小结,谓词逻辑小结,谓词逻辑小结,一.谓词的概念和表示,量词和特性谓词,谓词,重点掌握的基本概念和方法(一),个体和个体域,谓词公式的翻译(命题符号化),一元谓词:A(x)n元谓词:A(x1,.xn),个体常元:a,b,

41、c.个体变元:x,y,z.D:个体域,全称量词:(x)A(x)存在量词:(x)A(x)(x)(P(x)A(x)(x)(P(x)A(x),特性谓词P(x),谓词逻辑小结,重点掌握的基本概念和方法(二),二.谓词公式及其解释,谓词公式的递归定义,谓词公式的解释与赋值,变元的约束,求谓词公式在一组解释下的真值,有限域,无限域,指导变元与辖域自由变元与约束变元开式与闭式,1).指定个体域DI.2).指定个体常元3).指定个体函数.4).指定谓词5).指定自由变元,开式,闭式,谓词逻辑小结,三.公式类型及相互关系,重点掌握的基本概念和方法(三),判别公式的类型和等价,公式的类型,等价公式AB:即AB永真

42、,蕴含公式AB:即AB永真,代入定理,等价演算,分析真值,构造证明,永真式与重言式永假式可满足式,ABIffAB且BA,谓词逻辑小结,四.前束范式,重点掌握的基本概念和内容(四),前束范式(v1)(v2).(vn)A,前束析取范式前束合取范式,换名规则,求前束范式的方法步骤,对约束变元换名对自由变元代入,谓词逻辑小结,构造推理证明,归谬法,CP规则,直接证法,五.推理理论,有效推理:H1H2,HnC,推理规则:,重点掌握的基本概念和方法(五),前提引入规则P结论引入规则T全称推广规则UG存在推广规则EG全称指定规则US存在指定规则ES,一.在谓词逻辑中将命题符号化,1.判断是否复合命题(看有几

43、个主谓结构或连接词).2.对复合命题找出每个原子命题.3.对每个原子命题分出主语和谓语,主语若是泛指需加量词和特性谓词.并用符号表示.4.分析各原子命题的关系,确定连接词.,1.直线A平行于直线B，当且仅当直线A不相交于直线B.2.如果有限个数的乘积为0,则至少有一个因子等于03.对每一个实数x存在着一个更大的实数y.4.存在着实数x,y,z,使得x与y之和大于x与y之积.5.若xy*z,谓词逻辑小结,谓词逻辑小结,二.求公式在给定解释下的真值,P663)a)x(P(x)Q(x)(T)其中,P(x):x=1,Q(x):x=2,D:1,2,P663)b)x(PQ(x)R(a)(F)其中,P:21

44、,Q(x):x5,a=5,D:-2,3,6,P722)d)xy(P(x)Q(x,y)(F)其中,D:1,2,a=1;P(1)=F,P(2)=T,Q(1,1)=T,Q(1,2)=T,Q(2,1)=F,Q(2,2)=F,xA(x)A(a1)A(a1).A(an)xA(x)A(a1)A(a1).A(an),DI为有限域,三.判定公式类型和等价,1.证明谓词公式A是命题永真式的代入实例(重言式)2.利用等价演算证明公式AT3.证明蕴含AB,只需证AB永真.,P727)xy(p(x)Q(y)xp(x)yQ(y),P724)x(A(x)B(x)xA(x)xB(x),谓词逻辑小结,四.求前束范式,P752)

45、a)(xP(x)xQ(x)x(P(x)Q(x)T,P752)b)x(p(x)y(zQ(x,y)zR(y,x),*(1).将公式中的连接词化为,.(2).利用否定律,德.摩根律,及量词转化律,将否定深入到谓词字母前.(3).利用换名规则或代入规则使所有约束变元均不相同且使所有的自由变元与约束变元不同.(4).利用量词的的扩张与收缩,扩大量词辖域至整个公式.,求合取和析取范式,xy(p(x)Q(x,y)R(y,x),谓词逻辑小结,例题1xp(x)xQ(x),P791)b)xA(x)xB(x)x(A(x)B(x),P791)a)x(A(x)B(x),xB(x)xA(x),五.构造推理证明,P792)

46、a)x(P(x)Q(x)xP(x)xQ(x),谓词逻辑小结,直接证法,H1H2,HnC,要证:H1H2,HnC只需证:H1H2,HnCRR(矛盾),要证:H1H2,HnRC只需证:H1H2,HnRC,C-P规则,间接证法,课堂练习,4.在解释I:DI=1,2,P(1,1)=P(1,2)=0,P(2,2)=P(2,1)=1下谓词公式xyP(x,y)的真值为_.5.公式xP(x)xQ(x,y)前束合取范式为_.,课堂练习1.2.公式xyP(x,y)yxP(x,y)的类型是_.3.(x)(A(x)B(x)(x)A(x)(x)B(x)(),公式P(x,y)Q(x,y)P(x,y)的类型是_.,6.证明

47、等价式xy(A(x)B(y)yx(A(x)B(y),7.构造证明x(P(x)Q(x),xP(x)xQ(x),课堂练习,8.检验推理的有效性:1)每个自然数不是奇数就是偶数;当且仅当一个自然数被2整除才是偶数;8是自然数且能被2整除.因此8不是奇数,2).有些学生相信所有的教师；任何学生都不相信骗子；所以老师都不是骗子。,3).伟大的物理学家都有渊博的知识；历史学家有渊博的知识；所以历史学家是伟大的物理学家；,课堂练习,例题1并非每个实数都是有理数.,2-3谓词公式与翻译,否定,谓,主,全称量词,解,因为在全总论域上讨论,故需加特性谓词.,R(x):x是实数,设Q(x):x是有理数,故符号化为:

48、(x)(R(x)Q(x),P61例题3,例题3尽管有人聪明,但未必一切人都聪明.,2-3谓词公式与翻译,谓,主,合取,解,M(x):x是人,设P(x):x是聪明的,(x)(P(x)M(x)(x)(M(x)P(x),存在量词,否定,全称量词,例题4这只大红书柜摆满了那些古书,2-3谓词公式与翻译,谓词,个体,解1,a:这只大红书柜,设F(x,y):x摆满了y,个体,b:那些古书,符号化为:F(a,b),解2,R(x):x是大红书柜,设F(x,y):x摆满了y,Q(y):y是古书,R(a)Q(b)F(a,b),a:这只,b:那些,解3,A(x):x是红的,设F(x,y):x摆满了y,D(y):y是