离散数学课件(第2章).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学,教案,计算机科学与技术学院,课程学时：,64,主 讲：宋 成,河南理工大学,电子教案,第二章：谓词逻辑,2.1,谓词的概念与表示,2.2,命题函数与量词,2.3,谓词公式与翻译,2.4,变元的约束,2.5,谓词演算的等价式和蕴含式,2.6,前束范式,2.7,谓词演算的推理理论,教学目的及要求：,深刻理解和掌握谓词逻辑的基本概念和基本推理方法,教学类容：,谓词的概念与表示、命题函数与量词、谓词公式与翻译、变量的约束、谓词演算的等价式与蕴含式、前束范式、谓词演算的推理理论。,教学重点：,谓词逻辑中基本概念和基本推理方法。,教学难点：,谓词演算的推理理论。,第二章：谓词逻辑,2.1,谓词的概念与表示,在研究命题逻辑中，原子命题是命题演算中的最基小单位，不在对原子命题进行分解，这样会产生两大缺点,不能研究命题的结构、成分和内部的逻辑特征；,也不能表达两个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的过程。,例：苏格拉底论证是正确的，但是不能用命题逻辑的推理规则推导出来。,“所有的人都是要死的”,A,“,苏格拉底是人”,B,“,所以苏格拉底是要死的”,C,第二章：谓词逻辑,1,、客体（个体）,考察下面的三个原子命题：,李玲是优秀共产党员。,张华比李红高。,小高坐在小王和小刘的中间。,上述命题中的李玲、张华、李红、小高、小王、小刘等就是客体。所以可以这样说，客体是指所研究对象中可以独立存在的具体的或抽象的个体。它可以是独立存在的人或物体，也可以是抽象的概念，如“马列主义”，“资本主义”等。客体常用小写英文字母或小写英文字母带下标表示，叫做客体标识符。,第二章：谓词逻辑,表示具体或特定客体的标识符称作客体常元，一般用小写英文字母,a,、,b,、,c,、,或这些英文字母带下标表示。例如：李玲、张华、李红、小高、小王、小刘可如下表示：,a,：李玲,b,：张华,c,：李红,d,：小高,e,：小王,f,：小刘,a,b,c,d,e,f,都是客体常元。,将表示任意客体或泛指某类客体的标识符称为客体变元，常表示为,x,、,y,、,z,、,等或这些英文字母带下标。,客体变元的变化范围称为客体域或论域。客体域可以是有穷集合，也可以是无穷集合，包含任意客体的客体域称为全总客体域，它是由宇宙间一切对象组成的集合。,第二章：谓词逻辑,2,、谓词,在上面的三个原子命题中，可以分解成为客体“李玲”和“,是优秀共产党员”两部分。“,是优秀共产党员”是用来描述个体“李玲”的性质的；可以分解成为客体“张华”、“李红”和“,比,高”两部分。“,比,高”是用来描述客体“张华”和“李红”的身高关系的；可以分解成为客体“小高”、“小王”、“小刘”和“,坐在,和,的中间”两部分。“,坐在,和,的中间”是用来描述客体“小高”、“小王”、“小刘”的位置关系的。,【,定义,】,用以刻划客体性质或关系的即是谓词。谓词常用大写英文字母表示，叫做谓词标识符。,例如可以用,F,，,G,，,H,表示上面三个命题中谓词：,F,：,是优秀共产党员。,G,：,比,高。,H,：,坐在,和,的中间。,第二章：谓词逻辑,把与一个客体相关联的谓词叫做一元谓词。,F,是一元谓词；把与两个客体相关联的谓词叫做二元谓词。,G,是二元谓词；把与三个客体相关联的谓词叫做三元谓词。,H,是三元谓词；,。一般的，把与,n,个客体相关联的谓词叫做,n,元谓词。,设,F,是一元谓词，,a,是客体常元，用,F,(,a,),表示客体常元,a,具有性质,F,；设,G,是二元谓词，,a,b,是客体常元，用,G,(,a,b,),表示客体常元,a,和,b,具有关系,G,；,于是上面三个命题就表示为：,F,(,a,),：李玲是优秀共产党员。,G,(,b,c,),：张华比李红高。,H,(,d,e,f,),：小高坐在小王和小刘的中间。,将谓词字母后面填上相关联的客体常元所得的式子叫做谓词填式。,F,(,a,),，,G,(,b,c,),，,H,(,d,e,f,),都是谓词填式。谓词填式表示的是命题。,第二章：谓词逻辑,2.2,谓词函数与量词,1,、命题函数,客体在谓词表达式中可以是任意名词。,【,例,】C,：总是要死的。,j:,张三；,t,：老虎；,e:,桌子,则,C(j,),，,C(t,),，,C(e,),均表达了命题。,在上面的例子中，,C,：表示总是要死的，,x,：表示变元（客体变元），则,C(x,),：表示,x,总是要死的，则称,C(x,),为命题函数,第二章：谓词逻辑,类似的，用,F,(,x,),表示个体变元,x,具有性质,F,；用,G,(,x,y,),表示个体变元,x,和,y,具有关系,G,；,，用,P,(,x,1,x,2,x,n,)(,n,1),表示个体变元,x,1,x,2,x,n,具有关系,P,。如果谓词后面有,n,个个体变元，则称为,n,元命题函数。例如,F,(,x,),、,G,(,x,，,y,),、,P,(,x,1,x,2,x,n,),分别叫做一元命题函数、二元命题函数、,n,元命题函数,(,n,1),。,因为命题函数中包含个体变元，因此命题函数没有确定的真值，它不是命题。只要用个体常元取代所有的个体变元，就得到了命题。,第二章：谓词逻辑,例如，用,H,(,x,y,),：,x,+,y,0,，显然此命题函数不是命题，因为它无法判断真假。令,a,：,5,b,：,7,用,a,b,分别取代,x,y,，就得到,H,(,a,b,),，它表示,5+(,7)0,，这是个假命题，它的真值为假。,其实，用个体常元取代命题函数的所有个体变元所得到的表达式就是前面所说的谓词填式。因为它由个体常元取代命题函数中所有的个体变元而得到，所以也把谓词填式叫做,0,元命题函数。,F,(,a,),，,G,(,b,c,),，,H,(,d,e,f,),都是,0,元命题函数，它们都是命题。于是命题逻辑中的命题均可以表示为谓词逻辑中的,0,元命题函数,(,谓词填式,),，命题成为命题函数的特例。,第二章：谓词逻辑,【,定义,】,由一个谓词字母和一个非空的客体变元组成的表达式，称为简单命题函数。,定义讨论,当简单命题变元只有一个客体变元时，称为一元简单命题函数,若用任何客体取代客体变元之后，则命题函数就变为命题,命题函数中的客体变元的取值范围称为个体域（论述域）,例如,P(x,),表示,x,是质数。这是一个命题函数，真值取决于个体域。,第二章：谓词逻辑,【,例,】,将下列命题符号化，并讨论它们的真值。,2,与,3,都是偶数。,如果,5,大于,3,，则,2,大于,6,。,解：设,F,(,x,),：,x,是偶数。,a,：,2,，,b,：,3,该命题符号化为：,F,(,a,),F,(,b,),F,(,b,),表示,3,是偶数，它是个假命题。所以,F,(,a,),F,(,b,),为假。,设,G,(,x,y,),：,x,大于,y,a,：,5,，,b,：,3,，,c,：,2,，,d,：,6,该命题符号化为：,G,(,a,b,),G,(,c,d,),G,(,a,b,),表示,5,大于,3,，它是真命题。,G,(,c,d,),表示,2,大于,6,，这是个假命题。所以,G,(,a,b,),G,(,c,d,),为假。,第二章：谓词逻辑,2,、量词,量词分两种。,全称量词,日常生活和数学中常用的“一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都”等词统称为全称量词，将它们符号化为“,”。并用,(,x,),，,(,y,),等表示个体域里的所有个体，而用,(,x,),F,(,x,),和,(,y,),G,(,y,),等分别表示个体域中的所有个体都有性质,F,和都有性质,G,。,存在量词,“存在”，“有一个”，“有些”，“至少有一个”等词统称为存在量词，将它们符号化为“,”。并用,(,x,),，,(,y,),等表示个体域里有些个体，而用,(,x,),F,(,x,),和,(,y,),G,(,y,),等分别表示在个体域中存在个体具有性质,F,和存在个体具有性质,G,。,全称量词与存在量词统称为量词。,第二章：谓词逻辑,【,例,】,（,1,）存在人；（,2,）某些人很聪明；（,3,）有些实数是有理数,将（,1,）（,2,）（,3,）写成命题。,解：令,M(x,),：,x,是人；,C(x,),：,x,很聪明；,R,1,(x),：,x,是实数；,R,2,(x),：,x,是有理数,则：,(1)(,x)M(x,),；,(2)(,x)(,M(x)C(x,),；,(3)(,x)(R,1,(x)R,2,(x),在命题函数前加上量词,(,x,),和,(,x,),分别叫做个体变元,x,被全称量化和存在量化。一般地说，命题函数不是命题，如果对命题函数中所有命题变元进行全称量化或存在量化，该函数就变成了命题。这一结论在上例中得到验证。,虽然对命题函数中所有命题变元进行量化后，该命题函数就变成了命题，但所得命题的真值与个体域的选定有关。请看下列例题：,第二章：谓词逻辑,【,例,】,对下列命题符号化，并在，三个个体域中考察命题的真值。,命题：所有数小于,5,；至少有一个数小于,5,。,个体域：,-1,，,0,，,1,，,2,，,4,3,，,-2,，,7,，,8,15,，,20,，,24,解：设,L,(,x,),：,x,小于,5,。,“所有数小于,5,。”符号化为：,(,x,),L,(,x,),在个体域，中，它们的真值分别为：真，假，假。,“至少有一个数小于,5,。”符号化为：,(,x,),L,(,x,),在个体域，中，它们的真值分别为：真，真，假。,命题函数中的个体变元被量化以后变成命题，其真值又与个体域的选定有关，这对命题函数的研究带来了一定的困难，为了统一，我们今后使用全总个体域。而将其它个体域用一个谓词来,第二章：谓词逻辑,表示，叫做特性谓词。特性谓词加入的方法为：,对全称量词，特性谓词作为条件命题的前件加入。,对存在量词，特性谓词作为合取项加入。,【,例,】,对下列命题在，两个个体域中符号化。,命题：所有老虎是要吃人。,存在一个老虎要吃人。,个体域：,所有老虎组成的集合。,全总个体域。,解：设,A,(,x,),：,x,是要吃人的。个体域为所有老虎的集合。,符号化为,(,x,),A,(,x,),符号化为,(,x,),A,(,x,),个体域为全总个体域。设特性谓词,T,(,x,),：,x,是老虎。,符号化为,(,x,)(,T,(,x,),A,(,x,),符号化为,(,x,)(,T,(,x,),A,(,x,),第二章：谓词逻辑,2.3,谓词公式与翻译,1,、谓词公式,我们把命题、命题变元、谓词填式和命题函数叫做谓词演算的原子谓词公式。,【,定义,】,按下列规则构成的表达式称为谓词演算的合式公式，简称谓词公式。,谓词演算的原子公式是合式公式。,若,A,是合式公式，则,A,是合式公式。,若,A,和,B,是合式公式，则,(,A,B,),，,(,A,B,),，,(,A,B,),和,(,A,B,),是合式公式。,如果,A,是合式公式，,x,是,A,中出现的任意个体变元，则,(,x,),A,，,(,x,),A,是合式公式。,第二章：谓词逻辑,只有有限次地应用、所得的公式是合式公式。,谓词公式也有以下约定：,最外层的括号可以省略。,如果按,、在运算中的优先级别，省略括号后不改变原来的运算次序，可以省略括号，但量词后面括号不能省略。,第二章：谓词逻辑,下面举例说明如何用谓词公式表达自然语言中的命题。,【,例,】,并非每个实数都是有理数。,解：设,R,(,x,),：,x,是实数,Q,(,x,),：,x,是有理数,该命题符号化为：,(,x,)(,R,(,x,),Q,(,x,),【,例,】,没有不犯错误的人。,解：设,M,(,x,),：,x,是人,F,(,x,),：,x,犯错误,此命题可以理解为：存在一些人不犯错误，这句话是不对的。此时，符号化为：,(,x,)(,M,(,x,),F,(,x,),也可以理解为：任何人都是要犯错误的。此时，符号化为：,(,x,)(,M,(,x,),F,(,x,),第二章：谓词逻辑,【,例,】,并不是所有的兔子都比所有的乌龟跑得快。,解：设,F,(,x,),：,x,是兔子。,G,(,x,),：,x,是乌龟。,H,(,x,y,),：,x,比,y,跑得快。,该命题符号化为：,(,x,)(,y,)(,F,(,x,),G,(,y,),H,(,x,y,),【,例,】,将苏格拉底论证符号化“所有的人都是要死的。因为苏格拉底是人，所以苏格拉底是要死的。”,解：设,M,(,x,),：,x,是人,D,(,x,),：,x,是要死的,M,(,s,),：,苏格拉底,是人,D,(,s,),：,苏格拉底是要死的,该命题的符号化为：,(,x)(,M(x,),D(x,),，,M,(,s,),D,(,s,).,2,、由于对个体描述性质的刻画深度不同，可翻译成不 同形式的谓词公式（如,P61,，例,4,）,第二章：谓词逻辑,2.4,变元的约束,1,、自由变元与约束变元,【,定义,】,如果,A,是谓词公式,B,的一部分且是谓词公式，则称,A,是,B,的子公式。,【,定义,】,紧接量词以后的最小子公式叫做该量词的辖域或作用域。,【,定义,】,量词,(,x,),和,(,x,),中的,x,叫做该量词的指导变元或作用变元。,【,定义,】,量词,(,x,),和,(,x,),的辖域内,x,的一切出现叫约束出现，,x,叫做约束变元；约束变元以外的其它变元的出现叫自由出现，自由出现的变元叫自由变元。,第二章：谓词逻辑,【,例,】,说明下列各式量词的辖域，找出约束变元和自由变元。,(,x,),P,(,x,),Q,(,y,),(,x,)(,P,(,x,)(,y,),Q,(,x,y,),(,x,),P,(,x,)(,y,),Q,(,x,y,),(,x,)(,y,)(,P,(,x,y,),Q,(,y,z,)(,x,),R,(,x,y,),(,x,),P,(,x,),R,(,x,y,),解：,(,x,),的辖域为,P,(,x,),，,x,是约束变元，,y,是自由变元。,(,x,),的辖域为,P,(,x,)(,y,),Q,(,x,y,),，,(,y,),的辖域为,Q,(,x,y,),，,x,和,y,都是约束变元，无自由变元。,(,x,),的辖域为,P,(,x,),，,(,y,),的辖域为,Q,(,x,y,),，,P,(,x,),中的,x,和,Q,(,x,y,),中的,y,是约束变元，,Q,(,x,y,),中的,x,是自由变元。,(,x,),的辖域为,(,y,)(,P,(,x,y,),Q,(,y,z,),，,(,y,),的辖域为,P,(,x,y,),Q,(,y,z,),，,(,x,),的辖域为,R,(,x,y,),，,x,是约束变元，,z,是自由变元，,(,P,(,x,y,),Q,(,y,z,),中的,y,是约束变元，,R,(,x,y,),中的,y,是自由变元。,第二章：谓词逻辑,(,x),的辖域为,P(x,),，,y,是自由变元，,P(x,),中,x,是约束变元，,R(x,y,),中,x,是自由变元。,2,、约束变元的改名规则,由上例可以看出，在一个公式中，同一个变元既可以是约束的，又可以是自由的，容易混淆。因为,(,x,),P,(,x,),与,(,y,),P,(,y,),，,(,x,),P,(,x,),与,(,y,),P,(,y,),都具有相同意义，所以约束变元与表示该变元的符号无关。根据这个特点，可以对约束变元换名。为了使换名后的公式中出现的变元要么是约束的，要么是自由的，我们提出如下的换名规则：,对约束变元可以换名，其更改变元名称的范围是量词的指导变元，以及该量词辖域中的所有该变元，公式的其余部分不变。,换名时一定要更改成辖域中没有出现的变元名，最好是公式中没有的变量名。,第二章：谓词逻辑,【,例,】,对,(,x,)(,y,)(,P,(,x,y,),Q,(,y,z,)(,x,),R,(,x,y,),中的约束变元,y,换名。,解：用,u,置换约束变元,y,。换名后为：,(,x,)(,u,)(,P,(,x,u,),Q,(,u,z,)(,x,),R,(,x,y,),不能换成：,(,x,)(,u,)(,P,(,x,u,),Q,(,y,z,)(,x,),R,(,x,y,),也不能换成：,(,x,)(,z,)(,P,(,x,z,),Q,(,z,z,)(,x,),R,(,x,y,),3,、自由变元的代入规则,对公式中的自由变元也可以进行更改，用来解决公式中约束变元与自由变元的同名问题。这种更改叫做代入，代入规则是：,对于谓词公式中的自由变元可以代入，代入时需对公式中该变元自由出现的每处进行。,代入的变元与原公式中其他变元的名称不能相同。,第二章：谓词逻辑,【,例,】,对,(,x,)(,P,(,y,),R,(,x,y,)(,y,),Q,(,y,),中的自由变元,y,进行代入。,解：用,z,代换,y,，代入后为：,(,x,)(,P,(,z,),R,(,x,z,)(,y,),Q,(,y,),不能换成：,(,x,)(,P,(,x,),R,(,x,x,)(,y,),Q,(,y,),或,(,x,)(,P,(,z,),R,(,x,y,)(,y,),Q,(,y,),4,、区别是命题还是命题函数的方法,若在谓词公式中出现自由变元，则该公式为命题函数,若在谓词公式中的变元均为约束出现，在该公式为命题,【,例,】,(,x,),R,(,x,y,z,),是二元谓词函数,(,y,)(,x,),R,(,x,y,z,),是一元谓词函数,而谓词公式中如果没有自由变元出现，则该公式是一个命题,第二章：谓词逻辑,注：,对于同一个体域，用不同的量词时，特性谓词加入的方法不一样。,对于全称量词，特征谓词通常以前件的形式加入,对于存在量词，特征谓词通常以与的形式加入,当论域中的元素为有限时客体变元中的所有可能的取代是可以枚举的,对于全称量词，同常用“与”联接词,对于存在量词，通常用“或”联接词,量词对变元的约束，往往与量词的次序有关,【,例,】,(,y,)(,x,)(,x,y-2,),表示任何,y,均有,x,，使得,x,y-2,第二章：谓词逻辑,2.5,谓词演算的等价式与蕴含式,【,定义,2.5.1】,设,A,是谓词公式，个体域为,E,，,如果对,A,的任何赋值，,A,都为真，则称,A,是有效的或永真的。,【,定义,2.5.2】,设,A,是谓词公式，个体域为,E,，,如果对,A,的任何赋值，,A,都为假，则称,A,是不可满足的或永假的。,【,定义,2.5.3】,设,A,是谓词公式，如果个体域中至少有一组赋值使,A,为真，则称,A,是可满足的。,根据定义,2.5.1,和定义,2.5.3,，如果一个谓词公式是有效的，它一定是可满足的。,【,定义,2.5.4】,设,A,、,B,是任意两个谓词公式，且有共同的个体域,E,，对,A,、,B,的任何赋值，若其真值相同，则称,A,与,B,是在,E,上是等价的，记作,A,B,；若,A,B,是有效的，则称,A,蕴含,B,，记作,A,B,。设,A,、,B,是任意两个谓词公式。当,A,B,时，由定义,2.5.1,和定义,2.5.4,知,A,B,是永真式。反之，当,A,B,是永真式时，,A,B,。所以，也可以用,A,B,是永真式描述,A,B,。,第二章：谓词逻辑,1,、命题逻辑中的等价式的推广,命题演算中的所有等价式都是谓词演算中的等价式。,从谓词公式的定义可以看出，命题演算的合式公式都是谓词演算的合式公式。再根据定义,2.5.4,，命题演算中的所有等价式都是谓词演算中的等价式。,命题逻辑中的等价式的推广,在命题逻辑中，重言式的同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。在谓词逻辑中可以推广为：在永真的谓词公式中，命题变元出现的每一处都用同一谓词公式置换，其结果仍是永真式。例如：,第二章：谓词逻辑,因为,(,p,q,),p,q,，故,(,p,q,)(,p,q,),为永真式，,用,(,x,),P,(,x,),代替,p,，,(,y,),R,(,y,),代替,q,，得到永真式：,(,x,),P,(,x,)(,y,),R,(,y,)(,x,),P,(,x,)(,y,),R,(,y,),所以,(,x,),P,(,x,)(,y,),R,(,y,),(,x,),P,(,x,)(,y,),R,(,y,),2,、消去量词等价式,设个体域为有限集,a,1,，,a,2,，,，,a,n,，,A(x,),是含自由变元,x,的任意谓词公式，有下列等价式成立：,(,x)A(x),A(a,1,)A(a,2,),A(a,n,),(,x)A(x),A(a,1,)A(a,2,),A(a,n,),3,量词否定等价式,设,A(x,),是含自由变元,x,的任意谓词公式。则,(,x)A(x),(,x)A(x,),(,x)A(x),(,x)A(x,),约定，量词之前的否定联结词，不是否定该量词，而是否定该量词及其辖域。,第二章：谓词逻辑,这两个等价式可在有限个体域上证明，设个体域为,a,1,，,a,2,，,，,a,n,(,x,),A,(,x,),(,A,(,a,1,),A,(,a,2,),A,(,a,n,),A,(,a,1,),A,(,a,2,),A,(,a,n,),(,x,),A,(,x,),(,x,),A,(,x,),(,A,(,a,1,),A,(,a,2,),A,(,a,n,),A,(,a,1,),A,(,a,2,),A,(,a,n,),(,x,),A,(,x,),当个体域为无限集时，等价式也是成立的。但因为情况复杂，仅作以下说明：对等价式,(,x,),A,(,x,),(,x,),A,(,x,),，,(,x,),A,(,x,),表示：并不是所有的,x,都有性质,A,。,(,x,),A,(,x,),表示：存在,x,没有性质,A,。显然“并不是所有的,x,都有性质,A,”,和“存在,x,没有性质,A,”,是相同的，所以,(,x,),A,(,x,),(,x,),A,(,x,),。对等价式,(,x,),A,(,x,),(,x,),A,(,x,),来说，“不存在某个,x,有性质,A,”,和“所有的,x,都没有性质,A,”,是相同的。,第二章：谓词逻辑,4,、量词作用域的扩展与收缩等价式,设,A,(,x,),是含自由变元,x,的任意谓词公式。,B,是不含变元,x,的谓词公式，则,(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,利用上述四式可以得到以下四式：,(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,x,)(,B,A,(,x,),B,(,x,),A,(,x,),(,x,)(,B,A,(,x,),B,(,x,),A,(,x,),【,例,】,证明,(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,解：,(,x,)(,A,(,x,),B,),(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,x,),A,(,x,),B,(,x,),A,(,x,),B,第二章：谓词逻辑,5,、量词分配等价式,设,A,(,x,),和,B,(,x,),是含自由变元,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,和性质,B,”,和“所有的,x,有性质,A,且所有的,x,有性质,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,),B,(,x,),(,x,)(,A,(,x,),B,(,x,),(,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,)(,x,),B,(,x,),于是,(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),第二章：谓词逻辑,6,、量词与联结词的蕴含式,设,A,(,x,),和,B,(,x,),是含自由变元,x,的任意谓词公式。,(,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,),对第一式作如下说明：令,A,(,x,),表示,x,有一支钢笔，,B,(,x,),表示,x,有一支铅笔，个体域是,2000,级计算机,1,班全体同学。全班每个同学都有一支钢笔或每个同学都有一支铅笔，当然可以推出全班每个同学有一支钢笔或有一支铅笔。但反过来是不对的。,第二式可用第一式推出。,第二章：谓词逻辑,【,例,】,证明,(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),解：由第一式可得：,(,x,),A,(,x,)(,x,),B,(,x,),(,x,)(,A,(,x,),B,(,x,),而,(,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,),(,x,)(,A,(,x,),B,(,x,),故有,(,x,),A,(,x,)(,x,),B,(,x,),(,x,)(,A,(,x,),B,(,x,),由双条件否定等价式有,(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),第三、四式可以类似推出。,第二章：谓词逻辑,7,、多个量词的使用,约定：,(,x,)(,y,),A,(,x,y,),表示,(,x,)(,y,),A,(,x,y,),一般地说，多个量词相连时，同名量词是无序的，即改变它们的次序，命题真值不变。异名量词是有序的，即改变它们的次序，命题真值发生变化。对后者作如下的说明：,令,A,(,x,y,),表示,x,+,y,=10,，个体域为整数集合,I,。,(,x,)(,y,),A,(,x,y,),表示对任一整数,x,，存在整数,y,，使,x,+,y,=10,。这是一个真命题。,(,y,)(,x,),A,(,x,y,),表示存在整数,y,，对任一整数,x,，有,x,+,y,=10,。这是一个假命题。,第二章：谓词逻辑,因为同名量词是无序的，所以有：,(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),异名量词有下列的蕴含关系：,(,y,)(,x,),A,(,x,y,),(,x,)(,y,),A,(,x,y,),(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),具有两个量词的谓词公式还有下列的蕴含式：,(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(,x,)(,y,),A,(,x,y,),(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(,x,)(,y,),A,(,x,y,),第二章：谓词逻辑,2.6,前束范式,【,定义,】,一个公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则称为前束范式。,根据这个定义前束范式可表示成如下形式：,(,v,1)(,v,2)(,vn,),A,其中：是,或,vi,是个体变元，,i,=1,n,A,是不含量词的谓词公式,【,例,】,(,x,)(,y,)(,F,(,x,),G,(,y,),L,(,x,y,),(,y,)(,x,)(,z,)(,H,(,x,y,),F,(,x,),L,(,x,z,),都是前束范式。而,(,x,),F,(,x,)(,y,)(,G,(,y,),L,(,x,y,),(,y,)(,x,)(,H,(,x,y,),F,(,x,)(,z,),L,(,x,z,),都不是前束范式。,第二章：谓词逻辑,【,定理,】,任何谓词公式,都可以化成与其等价的前束范式。,证明：利用量词转换将,深入到原子谓词公式前,利用约束变元的改名规则,利用量子辖域的扩张收缩律，把量词移到全式的最前面，这样一定可以得到等价的前束范式,【,例,】,求公式,(,x,),F,(,x,)(,x,),G,(,x,),的前束范式。,解：,(,x,),F,(,x,)(,x,),G,(,x,),(,x,),F,(,x,)(,x,),G,(,x,),(,x,),F,(,x,)(,x,),G,(,x,),(,x,)(,F,(,x,),G,(,x,)(,前束范式,),(,x,)(,F,(,x,),G,(,x,)(,前束范式,),从本例可以看出，谓词公式的前束范式并不惟一。,第二章：谓词逻辑,【,例,】,把公式,(,y,),G,(,x,y,)(,x,),F,(,x,y,),化为等价的前束范式。,解：,(,y,),G,(,x,y,)(,x,),F,(,x,y,),(,t,),G,(,x,t,)(,s,),F,(,s,y,),(,t,)(,s,)(,G,(,x,t,),F,(,s,y,),【,定义,】,一个谓词公式,A,，如果具有如下形式称为前束合取范式。,(,v,1,)(,v,2,)(,v,n,)(,A,11,A,12,),(,A,21,A22,),(,A,m1,A,m2,),其中：是,或,v,i,是个体变元，,i,=1,n,A,ij,是原子公式或其否定。,例如,(,x,)(,y,)(,z,)(,F,(,x,),H,(,x,y,),G,(,x,)(,F,(,x,),L,(,x,z,),是前束合取范式。,第二章：谓词逻辑,【,定理,】,每个谓词公式都可化为与其等价的前束合取范式。,证明：在前面定理的基础上，将谓词公式转换为合取范式,【,例,】,将,(,x,),F,(,x,)(,x,),G,(,x,)(,x,)(,F,(,x,),G,(,x,),化为与其等价的前束合取范式。,解：,(,x,),F,(,x,)(,x,),G,(,x,)(,x,)(,F,(,x,),G,(,x,),(,x,)(,F,(,x,),G,(,x,)(,y,)(,F,(,y,),G,(,y,),(,x,)(,y,)(,F,(,x,),G,(,x,)(,F,(,y,),G,(,y,),(,x,)(,y,)(,F,(,x,),G,(,x,)(,F,(,y,),G,(,y,),(,x,)(,y,)(,F,(,x,),G,(,x,)(,F,(,y,),G,(,y,),(,x,)(,y,)(,F,(,x,),F,(,y,),G,(,y,)(,G,(,x,),F,(,y,),G,(,y,),第二章：谓词逻辑,【,定义,】,一个谓词公式,A,，如果具有如下形式称为前束析取范式。,(,v,1,)(,v,2,)(,v,n,)(,A,11,A,12,),(,A,21,A,22,),(,A,m1,A,m2,),其中：是,或,v,i,是个体变元，,i,=1,n,A,ij,是原子公式或其否定。,【,定理,】,中每一个谓词公式,A,都可以化为与它等价的前束析取范式。,证明从略。,第二章：谓词逻辑,2.7,谓词演算的推理理论,在谓词演算中，,C,是一组前提,A,1,，,A,2,，,，,A,n,的有效结论，仍然定义为,A,1,A,2,A,n,C,。命题演算推理中的,P,规则、,T,规则、,CP,规则、所有的等价式和蕴含式在谓词推理中都是对的，都可以使用；另外，,2.5,节中介绍的谓词演算中的等价式与蕴含式也可以在谓词推理中使用。除此之外，还有以下的规则。,全称指定规则,(US,规则,),如果对个体域中所有的,x,，则,A,(,x,),成立，则对个体域中某个任意客体,c,，,A,(,c,),成立。该规则表示成：,(,x,),A,(,x,),A,(,c,),第二章：谓词逻辑,全称推广规则,(UG,规则,),如果能够证明对个体域中每一个客体,c,，,命题,A,(,c,),都成立，则可得到结论,(,x,),A,(,x,),成立。该规则表示成,A,(,x,),(,x,),A,(,x,),存在指定规则,(ES,规则,),如果对个体域中某些客体,A(x,),，则必有某个,特定,的客体,c,，使,A(c,),成立。该规则表示成：,(,x)A(x),A(c,),【,例,】,设个体域为整数集合,I,，,A,(,x,),表示,x,是奇数，,B,(,x,),表示,x,是偶数。,(,x,),A,(,x,),A,(,c,),，它表示：若存在一些整数是奇数，令,c,为,3,，则,c,是奇数。这个推理是对的。,(,x,),B,(,x,),B,(,d,),，它表示：若存在一些整数是偶数，令,d,为,4,，则,d,是偶数。这个推理也是对的。因此有下列推理成立：,(,x,),A,(,x,)(,x,),B,(,x,),A,(,c,),B,(,d,),第二章：谓词逻辑,而下列推理是错误的：,(,x,),A,(,x,)(,x,),B,(,x,),A,(,c,),B,(,c,)(,x,),A,(,x,)(,x,),B,(,x,),A,(,d,),B,(,d,),因为,3,不能既是奇数，又是偶数；同样，,4,也不能既是奇数，又是偶数。,存在推广规则,(EG,规则,),如果对个体域中某个特定客体,c,，命题,A(c,),成立，则在个体域中，必存在,x,，使,A(x,),成立。该规则表示成：,A(c),(,x)A(x,),第二章：谓词逻辑,注：规则的使用说明,在使用,ES,，,US,时，一定要是前束范式,推导过程中连续使用,US,，可以使用相同的客体，如：,(,x,),P,(,x,),P,(,c,),，,(,x,),Q,(,x,),Q,(,c,),推导过程中既用,ES,，又用,US,，则必须先用,ES,，后用,US,方可取相同的客体，反之不行。,(,x,),P,(,x,),P,(,c,),，,(,x,),Q,(,x,),Q,(,c,),推导过程中连续使用,ES,规则时，使用一次更改一个客体,第二章：谓词逻辑,【,例,】,证明苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。,设：,H,(,x,),：,x,是人。,M,(,x,),：,x,是要死的。,s,：苏格拉底。,本题要证明：,(,x,)(,H,(,x,),M,(,x,),H,(,s,),M,(,s,),证明：,(,x,)(,H,(,x,),M,(,x,)P,H,(,s,),M,(,s,)US,H,(,s,)P,M,(,s,)T,第二章：谓词逻辑,【,例,】,证明,(,x,)(,H,(,x,),M,(,x,),，,(,x,),H,(,x,),(,x,),M,(,x,),证明：,(,x