离散数学PPT课件21谓词逻辑.ppt

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 谓词逻辑,问题的提出,：,(,即命题逻辑的局限性,),在第一章,一个原子命题只用一个字母表示，,而不再对命题中的句子成分细分。这样有一些逻,辑问题无法解决。请看下面的例子。,例,1,.,令：小张是大学生。,：小李是大学生。,从符号、中,不能归纳出他们都是大学生的共,性,。我们希望从所使用的符号那里带给我们更多,的信息，比如可以看出他们的共性。这种想法在,第一章是无法实现的。,例,2,.,令,：所有自然数都是整数。,：是自然数。,：是整数。,这是著名的三段论推理，,A,是大前提，,B,是小前提,C,是结论。显然，由和可以推出结论。这,个推理是有效的，但是,这个推理在第一章也是无,法实现的,。,分析：,命题与中的谓语是相同的,(,是大学生,),只是主语不同。命题、之间在主语谓语,方面也是有联系的，靠这种联系才能由、推,出。而从这三个符号上看不出此种联系。,所以就要,另外考虑表示命题的方法,。,解决这个问题的方法,：,在表示命题时，既表示出主语，也表示出谓语，,就可以解决上述问题。这就提出了,谓词,的概念。,令,S(x),表示,x,是大学生，,a:,小张，,b:,小李,命题,P,表示成,S(a):,小张是大学生。,命题,Q,表示成,S(b):,小李是大学生。,从符号,S(a),、,S(b),可看出小张和小李都是大学生的共性,.,令,N(x):x,是自然数。,I(x):x,是整数。,表示所有的。,A:,x,(N(x)I(x),B,:N(8),C,:I(8),N(8)I(8),N(8),I(8),符号,S(x),、,N(x),、,I(x),就是所谓的谓词,。,推理如此实现：,2-1,基本概念,2-1.1,客体与客体变元,定义,：能够独立存在的事物，称之为,客体,，也,称之为,个体,。它可以是具体的，也可以是抽象的,事物。通常用小写英文字母,a,、,b,、,c,、,.,表示。,例如，小张、小李、,8,、,a,、,沈阳、社会主义等等,都是客体。,定义,：用小写英文字母,x,、,y,、,z.,表示任何客,体，则称这些字母为,客体变元,。,注意：客体变元本身不是客体,。,2-1.2,谓词,定义,：一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为,谓词,。如果括号内有,n,个客体变元，称该谓词为,n,元谓词,。,例如,S(x):,表示,x,是大学生。,一元谓词,G(x,y),：,表示,xy,。,二元谓词,B(x,y,z),：,表示,x,在,y,与,z,之间。三元谓词,一般地,P(x,1,x,2,x,n,),是,n,元谓词。,2-1.3,命题函数,谓词本身并不是命题，只有谓词的括号内填入足够的客体，才变成命题,。,例如，,a,表示小张，,b,表示小李，则,S(a):,小张是大学生。,S(b):,小李是大学生。,(7,3),表示,:,。,如果,c,表示锦州，,d,表示沈阳，,e,表示山海关，则,B(c,d,e),表示：锦州在沈阳与山海关之间。,这时,S(a),、,S(b),、,G(7,3),、,B(c,d,e),才是命题。,令谓词,S(x):x,是大学生，括号内填入不同的人名，,就得到不同的,命题,，故谓词,S(x),相当于一个函数，,称之为,命题函数,。,定义,：,n,元谓词,P(x,1,x,2,x,n,),称之为,简单命题函数,。,规定：,当命题函数,P(x,1,x,2,x,n,),中,n=0,时，即,0,元谓词，表示不含有客体变元的谓词，它本身就是,一个,命题变元,。,定义,：将若干个简单命题函数用逻辑联结词联结起,来，构成的表达式，称之为,复合命题函数,。简单命,题函数与复合命题函数统称为,命题函数,。,例如,给定简单命题函数：,A(x),：,x,身体好，,B(x),：,x,学习好，,C(x),：,x,工作好，,复合命题函数,A(x)(,B(x),C(x),表示如果,x,身体不好，则,x,的学习与工作都不会好。,2-1.4,论域,(,个体域,),定义,：在,命题函数,中命题变元的取值范围，称之为,论域,，也称之为,个体域,。,例如,S(x):x,是大学生，论域是,:,人类。,G(x,y),：,xy,，,论域是,:,实数。,论域是一个集合。,定义,：由所有客体构成的论域，称之为,全总个体域,。它是个“最大”的论域。,约定,:,对于一个命题函数，如果没有给定论域，则,假定该论域是全总个体域,。,2-1.5,量词,例如：有些人是大学生。,所有事物都是发展变化的。,“有些”,“,所有的”,就是对客体量化的词。,定义,：在命题中表示对客体数量化的词，称之为,量词,。,定义了两种量词：,(1).,存在量词,：记作,，表示“有些”、“一些”、,“某些”、“至少一个”等。,(2).,全称量词,：记作,，表示“每个”、“任何,一个”、“一切”、“所有的”、,“,凡是,”,、,“,任意,的,”,等。,定义,：量词后边要有一个客体变元，指明对哪个客体变元量化，称此客体变元是,量词后的指导变元,。,例如,x(,读作“任意,x”),，,x,(,读作“存在,x”),，,其中的,x,就是量词后的指导变元。,例题,.,所有的自然数都是整数。,设,N(x),：,x,是自然数。,I(x),：,x,是整数。此命,题可以写成,x(N(x)I(x),例题,.,有些自然数是偶数。,设,E(x),：,x,是偶数。,此命题可以写成,x(N(x)E(x),例题,3.,每个人都有一个生母。,设,P(x):x,是个人。,M(x,y):y,是,x,的生母。此命题可以写成,x,(P(x),y,(P(y)M(x,y),2-2,谓词公式及命题符号化,命题逻辑中有命题公式，类似地，在谓词逻辑,中，要研究谓词公式。,2-2.1,客体函数,有些命题中，可能有若干个客体，其中有些客体,之间有函数关系，例如,例题,1,.,如果,x,是奇数，则,2x,是偶数。,其中客体,x,与客体,2x,之间就有函数关系，可以设,客体函数,g(x)=2x,，,谓词,O(x),：,x,是奇数，,E(x),：,x,是偶数，,则此命题可以表示为：,x(O(x)E(g(x),例题,2,小黄的父亲是个医生。,设函数,f(x)=x,的父亲，谓词,D(x):x,是个医生，,a:,小黄，此命题可以表示为,D(f(a).,例题,3,如果,x,和,y,都是奇数，则,x+y,是偶数,.,设,h(x,y)=x+y,，,此命题可以表示为,:,x,y(O(x)O(y)E(h(x,y),像上述的,g(x),、,f(x),、,h(x,y),就是客体函数，一般地用小写的英文字母,f,g,h.,表示客体函数。,注意,:,客体函数与谓词是不同的，不可混淆,.,要注意区分客体函数与谓词间的区别：,设例题,1,的论域是自然数集合,N,。,客体函数中的客体变元用客体带入后的结果依然,是个客体,(3N,g(3)=6,，,所以,g(3)N),。,谓词中的客体变元用确定的客体带入后就,变成了命题,，其真值为或者为,(3N,O(,),是个命题,真值为,T),。,把它们都看成“映射”的话，则,客体函数是论域到论域的映射,，,g:NN,，,如果,指定的客体,aN,，则,g(a)N,。,而谓词是从论域到,T,F,的映射,，即谓词,E(x),可,以看成映射,E:NT,F,，,如果指定客体,aN,，,则,E(a),的真值,T,F,。,2-2.2,原子谓词公式,定义,：称,n,元谓词,P(x,1,x,2,.,x,n,),为原子谓词公式。,例如,P,、,Q(x),、,A(x,f(x),、,B(x,y,a),都是原子谓词公式。,2-2.3,谓词合式公式,(WFF),(Well Formed formulas),定义,：谓词合式公式递归定义如下：,1.,原子谓词公式是合式公式。,2.,如果,A,是合式公式，则,A,也是合式公式。,3.,如果,A,、,B,是合式公式，则,(AB),、,(AB),、,(AB),、,(A,B),都是合式公式。,4.,如果,A,是合式公式，,x,是中的任何客体变元，则,x,和,x,也是合式公式。,5.,只有有限次地按规则,(1),至,(4),求得的公式才是合式公式。,谓词合式公式,也叫,谓词公式,，简称,公式,。,下面都是合式公式：,P,、,(PQ),、,(Q(x)P),、,x(A(x)B(x),、,xC(x,),而下面都不是合式公式：,x,y,P(x),、,P(,x)Q(x),x,为了方便，最外层括号可以省略，但是若量词后边有括号，则此括号不能省。,注意：,公式,x,(,A(x)B(x),),中,x,后边的括号不是最外层括号，所以不可以省略。,2-2.4,量词的作用域,(,辖域,),定义,：在谓词公式中，量词的作用范围称之为量词的,作用域,，也叫量词的,辖域,。,例如,xA(x),中,x,的辖域为,A(x).,x(P(x)Q(x),yR(x,y,),中,x,的辖域是,(,P(x)Q(x),yR(x,y,),y,的辖域为,R(x,y),。,x,y,z(A(x,y)B(x,y,z)C(t),x,的辖域,z,的辖域,y,的辖域,一般地，,如果量词后边只是一个原子谓词公式时，该量词的辖域就是此原子谓词公式。,如果量词后边是括号，则此括号所表示的区域就是该量词的辖域。,如果多个量词紧挨着出现，则后边的量词及其辖域就是前边量词的辖域。,2-2.5,自由变元与约束变元,在谓词公式中的客体变元可以分成两种，,一种是受到量词约束的，一种是不受量词,约束的。请看下面公式：,x(F(x,y),yP(y)Q(z,),(x,y),中的,x,在,x,的辖域内，受到,x,的,约束，而其中的,y,不受,x,的约束。,P(y),中的,y,在,y,的辖域内，受,y,的约束。,Q(z),中的,z,不受量词约束。,定义,：如果客体变元,x,在,x,或者,x,的辖域内，则称,x,在此辖域内约束出现，并称,x,在此辖域内是,约束变元,。否则,x,是自由出现，并称,x,是,自由变元,。,上例中,x(F(x,y),yP(y)Q(z,),F(x,y),中的,x,和,P(y),中的,y,是约束变元。,而,F(x,y),中的,y,和,Q(z),中的,z,是自由变元。,对约束变元和自由变元有如下几点,说明,;,(1).,对约束变元用什么符号表示无关紧要。,就是说,xA(x),与,yA(y,),是一样的。这类似于计算积分与积分变元无关，即积分,f(x)dx,与,f(y)dy,相同。,(2).,一个谓词公式如果无自由变元，它就表示一个命题,。,例如,A(x),表示,x,是个大学生。,xA(x),或者,xA(x),就是个命题了，因为它们分别表示命题“有些人是大学生”和“所有人都是大学生”。,(3).,一个,n,元谓词,P(x,1,x,2,x,n,),，,若在前边添加,k,个量词，使其中的,k,个客体变元变成约束变元，则此,n,元谓词就变成了,n-k,元谓词。,例如,P(x,y,z),表示,x+y=z,，,假设论域是整数集。,x,yP(x,y,z,),表示“任意给定的整数,x,，,都可以找到整数,y,，,使得,x+y=z”,。,如果令,z=1,，则,x,yP(x,y,1),就变成了命题“任意给定的整数,x,，,都可以找到整数,y,，,使得,x+y=1”,。,可见每当给,z,指定个整数,a,后，,x,yP(x,y,a,),就变成了一个命题。所以谓词公式,x,yP(x,y,z,),就相当于只含有客体变元,z,的一元谓词了。,在一个谓词公式中，如果某个客体变元既以约束变元形式出现，又以自由变元形式出现，就容易产生混淆。为了避免此现象发生，可以对客体变元更改名称,.,如,x(F(x,y,),yP(,y,)Q(z,),约束变元的改名规则,：,(1).,对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量词的辖域内此客体变元出现的各处同时换名,.,(2).,改名后用的客体变元名称，不能与该量词的辖域内的其它变元名称相同。,例如,x(P(x)Q(x,y)(R(x)A(x),此式中的,x,就是以两种形式出现。可以对,x,改名,成,z(P(z)Q(z,y)(R(x)A(x),对自由变元也可以换名字，此换名叫代入。,对,自由变元的代入规则,：,(1).,对谓词公式中的自由变元可以作代入。代入时需要对公式中出现该变元的每一处，同时作代入。,(2).,代入后的变元名称要与公式中的其它变元名称不同,上例也可以对自由变元,x,作代入，改成,x(P(x)Q(x,y)(R(z)A(z),2-2.6,命题的符号化,在谓词演算中，命题的符号化比较复杂，,命题的符号表达式与论域有关系,。例如,1.,每个自然数都是整数。,(1).,如果论域是自然数集合,N,，,令,I(x),：,x,是整数，则命题的表达式为,xI(x,),(2).,如果论域扩大为,全总个体域,时，上述表达式,xI(x,),表示“所有客体都是整数”，显然这是假的命题，此表达式已经不能表达原命题了。因此需要添加谓词,N(x),：,x,是自然数，,用于表明,x,的特性,，于是命题的符号表达式为,x(N(x)I(x),2.,有些大学生吸烟。,(1).,如果论域是大学生集合,S,，令,A(x),：,x,吸烟，则命题的表达式为,xA(x),(2).,如果论域扩大为,全总个体域,时，上述表达式,xA(x),表示“有些客体吸烟”，就不是表示此命题了，故需要添加谓词,S(x),：,x,是大学生，,用于表明,x,的特性,，于是命题的表达式为,x(S(x)A(x),从上述两个例子可以看出，命题的符号表达式与论域有关。,当论域扩大时，需要添加用来表示客体特性的谓词，称此谓词为,特性谓词,。,特性谓词,往往就是给定命题中量词后边的那个名词,。如上面两个例子中的“所有,自然数,”、“有些,大学生,”。,如何添加特性谓词，这是个十分重要的问题,，,这与前边的量词有关,。,特性谓词的添加方法如下：,如果,前边是全称量词,，,特性谓词后边是蕴含联结词“”；,如果,前边是存在量词,，,特性谓词后边是合取联结词“”。,为什么必须这样添加特性谓词？,分析一下特性谓词和原谓词所表示的概念之间的关系，得出下面的图，从此图可以得出如此添加特性谓词的正确性。,令,N:,自然数集合，,I:,整数集合，,S:,大学生集合，,A:,烟民的集合。,I,N,S,A,吸烟大学生,I,包含,N,x(N(x)I(x),吸烟大学生是,S,与,A,的交集,x(S(x)A(x),3.,所有大学生都喜欢一些歌星。,令,S(x),：,x,是大学生，,X(x),：,x,是歌星，,L(x,y),：,x,喜欢,y,。,则命题的表达式为,x(S(x),y(X(y)L(x,y),4.,没有不犯错误的人。,此话就是“没有人不犯错误”，“没有”就是“不存在”之意。令,P(x),：,x,是人，,F(x),：,x,犯错误，,此命题的表达式为,x(P(x),F(x),或者,x(P(x)F(x),5.,不是所有的自然数都是偶数。,令,N(x),：,x,是自然数，,E(x),：,x,是偶数，,命题的表达式为,:,x(N(x)E(x),或者,x(N(x),E(x),6.,如果一个人只是说谎话，那么他所说的每句话没有一句是可以相信的。,令,A(x),：,x,是人，,B(x,y),：,y,是,x,说的话，,C(x):x,是谎话，,D(x),：,x,是可以相信的,命题的表达式为,:,x(A(x)(,y(B(x,y)C(y),z(B(x,z)D(z),或者 ,x(A(x),y(B(x,y)C(y),D(y),7.,每个自然数都有唯一的后继数。,令,N(x),：,x,是自然数，,A(x,y),：,y,是,x,的后继数，,E(x,y),：,x=y,则命题的表达式为,x(N(x),y(N(y)A(x,y),z(N(z)A(x,z)E(y,z),有一个后继数,后继数的唯一性,下面请同学们自己做练习第,60,页,(2),小结,1.,命题的符号表达式形式与论域有关系。,论域扩大需要用特性谓词对客体进行说明,.,注意如何添加特性谓词,(,即要注意特性谓词后边是什么联结词,),。,2.,如果量词前有否定符号，如,“,没有,.,”,“,不是所有的,.”,等，可以按照字面直译。如“,x”,“,x.,”,3.,命题的符号表达式中所有客体变元必须都是约束变元，才表示命题。有时给定命题中有些量词没有明确给出，要仔细分析并写出这隐含的量词。例如,a),金子闪光，但闪光的不一定都是金子。,G(x),F(x),x(,G(x),F(x),x(,F(x),G(x),b),没有大学生不懂外语。,S(x),K(x,y),F(x),x(,S(x),y(,F(y),K(x,y),2-3,谓词演算的等价式与蕴涵式,在命题逻辑中，我们是通过对公式的命题变元赋值来讨论永真式、永真蕴含式及等价公式的。,在谓词演算中，也要讨论一些重要的谓词公式。但是由于谓词公式中可能有命题变元、客体变元。对命题变元赋值比较容易，因为只有两个值可赋。而对客体变元作指派却不那么简单，因为论域中的客体可能有无限个。另外谓词公式的真值还与论域有关。,2-3.1,对谓词公式赋值,定义,：若将给定的谓词公式中的命题变元，用确定的命题代替，对公式中的客体变元用论域中的客体代替，这个过程就称之为,对谓词公式作指派,，或者称之 为,对谓词公式赋值,。,例如公式,PN(x),，,N(x),：,x,是自然数，论域为实数集合,R,，,令,P,：,21,，,x=4,时，此公式变成,PN(4),，,它的真值就是“真”。,2-3.2,谓词公式的永真式,定义,定义,：给定谓词公式,A,，,E,是其论域，如果不论对公式,A,作任何赋值，都使得,A,的真值为真，则称公式,A,在论域,E,上是永真式,。如果不论对什么论域,E,，,都使得公式,A,为永真式，则称,A,为永真式,。,例如，,I(x),：,x,是整数，论域,E,为自然数集合，公式,I(x),在,E,上就是永真式。,而公式,I(x),I(x),就是与论域无关的永真式。,2-3.3,谓词公式的等价公式,定义,定义,：给定谓词公式,A,、,B,，,E,是它们的论域，如果不论对公式,A,、,B,作任何赋值，都使得,A,与,B,的真值相同,(,或者说,A,B,是永真式,),，则称公式,A,与,B,在论域,E,上是等价的。如果不论对什么论域,E,，,都使得公式,A,与,B,等价，则称,A,与,B,等价，记作,A,B,。,例如，,I(x),：,表示,x,是整数，,N(x),：,表示,x,是自然数，假设论域,E,是自然数集合，公式,I(x),与,N(x),在,E,上是等价的。,而公式,N(x)I(x),与,N(x)I(x),就是与论域无关的等价的公式，即,N(x)I(x),N(x)I(x),。,2-3.4,谓词公式的永真蕴含式,定义,定义,：给定谓词公式,A,、,B,，,E,是它们的论域，如果不论对公式,A,、,B,作任何赋值，都使得,AB,为永真式，则称在论域,E,上公式,A,永真蕴含,B,。,如果不论对什么论域,E,，,都使得公式,AB,为永真式，则称,A,永真蕴含,B,，,记作,A,B,。,例如，,G(x),：,表示,x,大于,5,，,N(x),：,表示,x,是自然数，论域,E=-1,-2,6,7,8,9,.,，,在,E,上公式,G(x)N(x),是永真式。,而公式,(G(x)N(x)N(x),就是与论域无关的永真式，所以,(G(x)N(x),N(x),。,2-3.5.,重要公式,下面讨论重要的谓词等价公式和永真蕴含式。,一,.,由命题公式推广出的公式,因一个不含自由变元的谓词公式本身如,xA(x),、,xB(x,),就是命题,。一个含有,n,个自由变元的谓词公式，赋予论域,中的,n,个指定客体后就变成命题,(,例如,S(a),、,G(3,1),等,),。,因此可以把此公式,看成一个命题变元,。所以在命题演算,的永真式中，将其中的同一个命题变元，用同一个谓词,公式代替，所得到的公式也是永真式。这样就可以将命,题演算中的等价公式和永真蕴含式推广到谓词演算中使,用。例如,A(x),A(x)B(x),P,PQ,x(A(x)B(x),x(,A(x)B(x),PQ,P,Q,(,xA(x),xB(x),xA(x),xB(x,),摩根定律,二,.,带量词的公式在论域内的展开式,先看一个例子，令,A(x),：,表示,x,是整数，,B(x),：,表示,x,是奇数，设论域是,1,2,3,4,5,，谓词公式,xA(x),表示论域内所有的客体都是整数，显然公式,xA(x),的真值为真，因为,A(1),、,A(2),、,A(3),、,A(4),、,A(5),都为真，于是有,xA(x),A(1)A(2)A(3)A(4)A(5),类似地，谓词公式,xB(x,),表示论域内有些客体是奇数，显然公式,xB(x,),的真值也为真，因为,B(1),、,B(3),、,B(5),的真值为真，于是有,xB(x),B(1)B(2)B(3)B(4)B(5),一般地，设论域为,a,1,a,2,.,a,n,，,则,1.,xA(x),A(a,1,)A(a,2,).A(a,n,),2.,xB(x),B(a,1,)B(a,2,).B(a,n,),三,.,量词否定公式,我们还是先用一个例子说明这个问题。令,(x),表示,x,是优等生，论域是某班级的学生集合,.,xA(x),表示：不是所有人都是优等生。,x,A(x),表示：有些人不是优等生。,xA(x),表示：没有人是优等生。,x,A(x),表示：所有人都不是优等生。,从这个例子可以看出,“不是所有人都是优等生。”与“有些人不是优等生。”是等价的。,“没有人是优等生。”与“所有人都不是优等生。”是等价的。于是有：,1.,xA(x),x,A(x),2.,xA(x),x,A(x),对这两个公式可以证明如下：,证明：,设论域为,a,1,a,2,.,a,n,，,则,xA(x),(A(a,1,)A(a,2,).A(a,n,),A(a,1,),A(a,2,).,A(a,n,),x,A(x),类似可以证明另一个公式。,从这两个公式，可以总结出如下,规律,：将量词前的“,”移到量词的后边，或者将量词后的“,”移到量词的前边时，量词也随着改变，如果原来是全称量词改成存在量词，如果原来是存在量词改成全称量词。所以我们也把这两个公式称为量词转换公式。,四,.,量词辖域的扩充公式,如果,是个不含客体变元,x,的谓词公式,，且不在,x,和,x,的辖域内，可以将放入,x,和,x,的辖域内。即得如下公式：,1.,xA(x)B,x(A(x)B),2.,xA(x)B,x(A(x)B),3.,xA(x)B,x(A(x)B),4.,xA(x)B,x(,(x)B),5.B,xA(x),x(BA(x),6.B,xA(x),x(BA(x),7,.,xA(x)B,x(A(x)B),8,.,xA(x)B,x(A(x)B),上述公式我们只证明三个。,证明：,设论域为,a,1,a,2,.,a,n,，,xA(x)B,(A(a,1,)A(a,2,).A(a,n,)B,(A(a,1,)B)(A(a,2,)B).(A(a,n,)B),x(,(x),),B,xA(x),B,xA(x),x(,BA(x),x(BA(x),xA(x)B,xA(x)B,x,A(x)B,x(,A(x)B),x(A(x)B),在使用公式,7.,、,8.,时，要特别注意，量词的辖域扩充后，量词发生了变化,。,五,.,量词分配公式,1.,x(A(x)B(x),xA(x),xB(x,),2.,x(A(x)B(x),xA(x),xB(x,),3.,x(A(x)B(x),xA(x),xB(x,),4.,xA(x),xB(x),x(A(x)B(x,),证明,：设论域为,a,1,a,2,.,a,n,，,x(A(x)B(x),(A(a,1,)B(a,1,)(A(a,2,)B(a,2,),(A(a,n,)B(a,n,),(A(a,1,)A(a,2,).A(a,n,),(B(a,1,)B(a,2,).B(a,n,),xA(x),xB(x,),注意,公式,3.,和,4.,不是等价公式，而是永,真蕴含式。,例如公式,3.,由,xA(x),xB(x,),不能推出,x(A(x)B(x),，,我们可以举一个反例，设,A(x),和,B(x),分别表示“,x,是奇数”和“,x,是偶数”，显然命题,xA(x),xB(x,),为真。而,x(A(x)B(x),是表示命题“存在一些数既是奇数，也是偶数”，显然不为真。,所以说由,xA(x),xB(x,),不能推出,x(A(x)B(x).,证明公式,3.,x(A(x)B(x),xA(x),xB(x,),证明,：假设前件,x(A(x)B(x),为真，,则论域中至少有一个客体,a,，,使得,A(a)B(a),为真，于是,A(a),和,B(a),都为,真，所以有,xA(x),以及,xB(x,),为真，进而得,xA(x),xB(x,),为真。于是有,x(A(x)B(x),xA(x),xB(x,),下面利用公式,3.,证明公式,4.,。,证明,：因为公式,3.,中的,A(x),和,B(x),是任意的谓词公式，不妨用,A(x),和,B(x),分别代替公式,3.,中的,A(x),和,B(x),得,x(,A(x),B(x),x,A(x),x,B(x),x,(A(x)B(x),xA(x),xB(x,),x(A(x)B(x),(,xA(x),xB(x,),应用公式,P,Q,Q,P,得,xA(x),xB(x),x(A(x)B(x,),公式,4.,得证。,在使用公式,4.,的时候，,特别要注意蕴含式的方向，不要搞错。,六其它公式,1,.,x(A(x)B(x),x,A(x),x,B(x,),2.,xA(x),x,B(x),x(,A(x),B(x,),证明1.,x,A(x),x,B(x,),x,A(x),x,B(x,),x,A(x),x,B(x,),x(,A(x),B(x),x(A(x),B(x),证明2.,xA(x),x,B(x,),xA(x),x,B(x,),x,A(x),x,B(x,),x(,A(x),B(x),x(,A(x),B(x),七两个量词的公式,在,A(x,y),前有两个量词，如果两个量词是相同的，它们的次序是无关紧要，但是如果是不同的，它们的次序就不可以随便交换。例如设,A(x,y),表示“,x+y=0”,论域为：实数集合,x,yA(x,y,),表示“对于任意给定的一个实数,x,可以找到一个,y,使得,x+y=0”,这是一个为“真”的命题。而交换量词后,y,xA(x,y),表示“存在一个实数,y,与任意给定的一个实数,x,之和都等于,0”,这是一个为“假”的命题。,有如下一些公式：,1.,x,yA(x,y),y,xA(x,y,),2.,x,yA(x,y),y,xA(x,y,),3.,y,xA(x,y),x,yA(x,y,),4.,x,yA(x,y),x,yA(x,y,),5.,y,xA(x,y),x,yA(x,y,),6.,x,yA(x,y),y,xA(x,y,),7.,y,xA(x,y),x,yA(x,y,),8.,x,yA(x,y),y,xA(x,y,),注意：下面式子不成立,x,yA(x,y),y,xA(x,y,),为了便于记忆，用下面图形表示上面八个公式。,x,yA(x,y,),y,xA(x,y),x,yA(x,y,),y,xA(x,y),x,yA(x,y,),y,xA(x,y),y,xA(x,y),x,yA(x,y,),实际上，根据,具有传递性，还可以派生出一些公式。下面我们只证明一个等价公式。用谓词逻辑推理方法很容易证明上面那些永真蕴涵式，在此就不证明了。下面证明公式,1.,。,证明：,设论域为,a,1,a,2,.,a,n,，,则,x,yA(x,y),yA(a,1,y),yA(a,2,y),yA(a,n,y,),(A(a,1,a,1,)A(a,1,a,2,)A(a,1,a,n,),(A(a,2,a,1,)A(a,2,a,2,)A(a,2,a,n,),(A(a,n,a,1,)A(a,n,a,2,)A(a,n,a,n,),(A(a,1,a,1,)A(a,2,a,1,)A(a,n,a,1,),(A(a,1,a,2,)A(a,2,a,2,)A(a,n,a,2,),(A(a,1,a,n,)(A(a,2,a,n,)A(a,n,a,n,),xA(x,a,1,),xA(x,a,2,),xA(x,a,n,),y,xA(x,y),本节小结：,熟练掌握谓词等价公式和永真蕴涵式的证明方法及应用。,作业题：,P,66,(3)b),P,71,(2)d),(6),面作做个,练习,P71(1)c),练习,P71(1)c),.,论域,D=1,2 a=1 b=2 f(1)=2 f(2)=1,P(1,1)=T P(1,2)=T P(2,1)=F P(2,2)=F,求,xy(P(x,y)P(f(x),f(y),y(P(1,y)P(f(1),f(y)y(P(2,y)P(f(2),f(y),(,(P(,1,1)P(f(,1,),f(1)(P(,1,2)P(f(,1,),f(2),),(,(P(,2,1)P(f(,2,),f(1)(P(,2,2)P(f(,2,),f(2),),(,(P(,1,1)P(2,2)(P(,1,2)P(2,1),),(,(P(,2,1)P(1,2)(P(,2,2)P(1,1),),(,(T F)(T F),),(,(F T)(F T),),(,F F,),(,T T,),FT,F,2-4,前束范式,与命题公式的范式类似，谓词公式也有规范形式。这,里主要介绍前束范式,-,所有量词都在公式前边约束变元,.,1.,前束范式定义：,如果一个谓词公式符合下面条件，它就是,前束范式,：,所有量词前面都没有联接词；,所有量词都在公式的左面；,所有量词的辖域都延伸到公式的末尾。,例如,y,x,z,(,A(x)(B(x,y)C(x,y,z),),x,(,(x)B(x),),就是前束范式，而,xA(x),y,B(y,),x,y(A(x)(B(x,y),zC(z,),xA(x)B(x),这三个就不是前束范式。,2.,前束范式的写,法,给定一个带有量词的谓词公式，,1),消去公式中的联接词和,(,为了便于量词辖域的扩充,),；,2),如果量词前有“,”，则用量词否定公式将“,”后移。再用摩根定律或求公式的否定公式，将,“,”,后移到原子谓词公式之前,.,3),用约束变元的改名规则或自由变元的代入规则对变元换名,(,为量词辖域扩充作准备,),4),用量词辖域扩充公式提取量词，使之成为前束范式形式。,例,1.,xA(x),xB(x,),xA(x),x,B(x,),x,A(x),x,B(x,),x,A(x),y,B(y,)(,换元,),x(,A(x),y,B(y,)(,量词辖域扩充,),x,y,(,A(x)B(y),另一个方法：,xA(x),xB(x,),xA(x),x,B(x,),x,A(x),x,B(x,),x(,A(x)B(x)(,量词分配公式,),例,2.,x,(,P(x)R(x)(,xP(x)Q(x),x,(,P(x)R(x)(,xP(x)Q(x),(,去,),x,(,P(x)R(x)(,x,P(x)Q(x,)(,量词转换,),x,(,P(x),R(x)(,x,P(x)Q(x,)(,后移,),x,(,P(x),R(x)(,y,P(y)Q(z,)(,换变元,),x,(,P(x),R(x),y(,P(y)Q(z,)(,扩量词辖域,),x,y(,(,P(x),R(x)(,P(y)Q(z,)(,扩量词辖域,),3.,前束析取范式与前束合取范式：,前束析取范式,:,前束范式中量词后的括号内是析取范式形式。,前束合取范式,:,前束范式中量词后的括号内是合取范式形式。,上例的前束析取范式为,:,x,y(,P(x),R(x)(,P(y)Q(z,),上例的前束合取范式为,:,x,y(,P(x),R(x),P(y)(,P(x),R(x)Q(z,),本节掌握,前束范式的写法。,作业,P,75,(1)b),(2)c),2-5,谓词演算的推理理论,推理方法：,直接推理、条件论证、反证法,所用公式：,43,页和,70,页的,I,1,I,19,，,E,1,E,33,推理规则：,P,、,T,、,CP,、,US,、,ES,、,EG,、,UG,后四个规则，是处理量词的，因为推理时要使用不含量词的命题公式，所以要去掉量词，如果结论有量词，还要添加量词。,下面介绍四个新规则：,一,.,全称特指规则,US,(Universal Specialization),形式：,xA(x),A(c),(,其中,c,是论域内,指定客体,),含义：如果,xA(x),为真，则在论域内,任,何指定,客体,c,，,都使得,A(c),为真。,作用：去掉全称量词。,要求：,c,不是,A(x),中的符号。,二,.,存在特指规则,ES,(Existential Specialization),形式：,xA(x),A(c),(,其中,c,是论域内,指定客体,),含义：如果,xA(x),为真，则在论域内,指定,客体,c,，,都使得,A(c),为真。,作用：去掉存在量词。,要求：,c,不是,A(x),中的符号。,用,ES,指定的客体,c,不应该是,在此之前,用,US,规则或者用,ES,规则所指定的客体,c(,即本次用,ES,特指客体,c,，,不应该是以前特指的客体,),。,请看下面两个例子：,例,1.,令,A(x),表示,x,是自然数，,B(x),表示,x,是整数。,x(A(x)B(x)P,A(c)B(c)US,如,c=0.1,xA(x)P,A(c),ES,A(0.1),为,F,xB(x,)P,B(c)ES,如,c=-1,xA(x)P,A(c),ES,A(-1),为,F,三,.,存在推广规则,EG,(Existential Generalization),形式：,A(c),xA(x),(,其中,c,是论域内,指定客体,),含义：如果,在论域内,指定,客体,c,使得,A(c),为真，则,xA(x),为真。,作用：添加存在量词。,要求：,x,不是,A(c),中的符号,。,四,.,全称推广规则,UG,(Universal Generalization),形式：,A(c),xA(x),(,其中,c,是论域内,任何,指定客体,),含义：如果,在论域内,任何指定,客体,c,都,使,得,A(c),为真，则,xA(x),为真。,作用：添加,全称,量词。,要求：,x,不是,A(c),中的符号。,c,一定是任意,的客体，否则不可,全,称推广,。,例,1,所有金属都导电。铜是金属。,故铜导电。,令,M(x):x,是金属。,C(x):x,导电。,a:,铜。,符号化为：,x(M(x)C(x),M(a),C(a),x(M(x)C(x),P,M(a)C(a)US,M(a)P,C(a)T I,11,例,2.,所有自然数都是整数。有些数是自然数。因此有些数是整数。,令,A(x),表示,x,是自然数，,B(x),表示,x,是整数。,x(A(x)B(x),，,xA(x),xB(x,),xA(x)P,A(c)ES,x(A(x)B(x)P,A(c)B(c)US,B(C)T I,11,xB(x,)EG,例,2,中，如果按下面方法推理，是否正确？,x(A(x)B(x),，,xA(x),xB(x,),x(A(x)B(x)P,A(c)B(c)US,xA(x)P,A(c)ES,B(C)T I,11,xB(x,)EG,问题在哪里？,例,3,不认识错误的人，也不能改正错误。有些诚实的人改正了错误。所以有些诚实的人是认识了错误的人。,设,A(x):x,是,认识错误的人。,B(x):x,改正了错误。,C(x):x,是诚实的人。,符号化为：,x(,A(x),B(x),，,x(C(x)B(x),x(C(x)A(x),x(,A(x),B(x)，,x(C(x)B(x),x(C(x)