数理逻辑-谓词逻辑.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,数理逻辑,谓词逻辑,教师：孙继荣,电话：87768609,Email:sunjr0,1,.,数理逻辑,谓词逻辑,学习内容,谓词逻辑基本概念,谓词，个体词，命题函数,量词，自由变元和约束变元,谓词的合式公式，谓词的解释,自然语句的形式化,谓词逻辑的等值和推理演算,谓词逻辑的等值式,范式，基本推理公式,推理演算。,2,.,数理逻辑,谓词逻辑,教学要求,理解谓词、量词、变元、个体域等概念,掌握用谓词、量词、联结词构造谓词逻辑公式的方法,掌握谓词公式在给定解释下求真值的方法,会将谓词逻辑化为前束公式,会将谓词逻辑作为工具，将命题符号化，并能用推理规则进行逻辑证明。,3,.,2.1谓词逻辑基本概念,个体词与谓词,在谓词逻辑中，原子命题分解成个体词和谓词,定义：,个体词,是可以独立存在的客体，它可以是具体事物或抽象的概念,；,个体域,是个体（客体）的取值范围；,谓词,是用来刻划个体词的性质或事物之间的关系的词,大写字母表示谓词，小写字母表示个体（客体）,注意：,单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题.,4,.,2.1谓词逻辑基本概念,个体词与谓词,谓词也称为,命题函数,或简单命题函数,相关概念：,零元谓词，n元谓词，全总个体域，复合命题函数,命题是谓词的特殊情况,5,.,2.1谓词逻辑基本概念,全称量词与存在量词,量词是在命题中表示数量的词,量词有两类：,全称量词,，表示“所有的”，“任何的”，或“每一个”；,存在量词,，表示“存在某个”或“至少有一个”,.,命题符号化必须指明个体域,6,.,2.1谓词逻辑基本概念,全称量词与存在量词,对于一个谓词，如果其中每个变量都有一个量词作用之下，则它就不再是命题函数，而是一个命题了。,在谓词逻辑，使用量词应注意以下几点：,在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变。,在考虑命题符号化时，如果对个体域未作说明，一律使用全个体域。,多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的涵义。,7,.,2.1谓词逻辑基本概念,课堂练习：,将下列命题符号化,(1),每个母亲都爱自己的孩子；,(2),所有的人都呼吸；,(3),有某些实数是有理数,.,8,.,2.2谓词公式,谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题.所谓解释就是使公式中的每一个变项都有个体域中的元素相对应.,学习这一部分内容要侧重于能将谓词逻辑公式表达式中，消除量词写成与之等值的公式，然后将解释中的数值代入，求出真值，并着重理解在谓词和量词的作用下变元的自由性、约束性和更名规则、代入规则等.,9,.,2.2谓词公式,字母表的意义,个体常项：a,b,c,a,0,a,1,a,2,个体变项：x,y,z,x,0,x,1,x,2,函数符号：f,g,h,f,0,f,1,f,2,谓词符号：P,Q,R,S,0,S,1,S,2,量词符号：,，,逻辑符号：,，,括号与逗号：(,),10,.,2.2谓词公式,相关概念：,字母表,项：,递归定义 P43,原子公式,11,.,2.2谓词公式,合式公式,递归定义：P43,命题常数,0,，,1,，一个命题和命题变元以及一个命题函数,P(x,1,x,2,x,n,),，统称原子公式,由原子公式、联结词和量词可构成谓词公式,(,严格定义见教材,).,命题的符号化结果都是谓词公式。,例子：,x(F(x),G(x)，,x(F(x),G(x)，,x,y(F(x),F(y),L(x,y),H(x,y)等都是谓词公式.,12,.,2.2谓词公式,变元与辖域,在谓词公式,xA,和,xA,中，,x,是,指导变元,，,A,是相应量词的,辖域,.,在,x,和,x,的辖域,A,中，,x,的所有出现都是约束出现，即,x,是,约束变元,，不是约束出现的变元，就是,自由变元,.,也就是说，量词后面的式子是,辖域,.,量词只对辖域内的同一变元有效,.,13,.,2.2谓词公式,变元与辖域,自由变元有时会在量词辖域中出现，但是它不受相应量词指导变元的约束。,当谓词公式中没有自由变元时，它就是一个命题。,出现n个自由变元就是n元谓词。,变元可以既是约束出现又是自由出现。,例子：P44,14,.,2.2谓词公式,换名规则：,对,约束变元,进行换名,就是把公式中量词的指导变元及其该量词辖域中的约束变元换成该公式中,没有出现,的个体变元，公式的其余部分不变,.,代入规则：,对,自由变元,进行代入,就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的该符号,.,经过换名或代入后，公式的意义不应该改变,15,.,2.2谓词公式,课堂练习,对P44 例1中公式用换名或代入规则,重要公式,xA(x),A(a1),A(a2),A(a,n,),xA(x),A(a1),A(a2),A(a,n,),16,.,2.3谓词的等值演算,解释,(,赋值,)：,谓词公式的个体域,D,是非空集合,(1),每一个常项指定,D,中一个元素；,(2),每一个,n,元函数指定,D,n,到,D,的一个函数；,(3),每一个,n,元谓词指定,D,n,到,0,1,的一个谓词,.,解释就是对各个变项指定特殊的常项去代替，有四部分组成：,(1),非空个体域,D,；,(2),D,中有一部分特定元素，用来解释个体常项；,(3),D,上一些特定函数，用来解释出现的函数变项；,(4),D,上一些特定谓词，用来解释谓词变项。,17,.,2.3谓词的等值演算,例子：P46,课堂练习：,给定解释,I,：,D,2,3;,D,中特定元素,a,=2；,函数为,谓词,F,(,x,)为,F,(2)=0,F,(3)=1,G,(,x,y,),为,G,(2,2)=,G,(2,3)=,G,(3,2)=0,G,(3,3)=1,L,(,x,y,),为,L,(2,2)=,L,(3,3)=1,L,(2,3)=,L,(3,2)=0,求在解释,I,下各公式的真值,.,(1),x,(,F,(x)G(x,a),(2),x,y L(x,y),18,.,2.3谓词的等值演算,谓词公式分类,在任何解释下，谓词公式,A,取真值,1,，公式,A,为逻辑有效式,(,永真式,),；,在任何解释下谓词公式,A,取真值,0,，公式,A,为永假式；,至少有一个解释是公式,A,取真值,1,，公式,A,称为可满足式。,19,.,2.3谓词的等值演算,谓词演算的等值式和重言蕴含式,(1),命题公式的推广；,(2),量词否定式的等值式；,(3),量词辖域扩张和收缩的等值式；,(4),量词与联结词,，,，,的等值式；,(5),量词与联结词的重言蕴含式；,(6),两个量词公式间的等值式与重言蕴含式。,20,.,2.4,前束范式,前束范式,:,若一个谓词公式,F,等值地转化成,Q,1,x,1,Q,2,x,2,Q,k,x,k,B,那么就是,F,的前束范式，,其中Q,i,只能是量词,或,，,而,x,1,x,2,x,k,是个体变元，,B,是不含量词的谓词公式,.,量词均在全式的开头，其作用域延伸到整个公式的末尾,21,.,2.4,前束范式,前束范式的重要性质,性质1：P49,性质2：P50,证明忽略,22,.,2.4,前束范式,每个谓词公式,F,都可以变换成与它等值的前束范式,.,其步骤如下：,消去联结词,，,，,；,将联结词,移至原子谓词公式之前；,利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；,将,x,x移至整个公式最左边；,将公式化为前束范式。,一般地，前束范式不是唯一地,。,23,.,2.4,前束范式,谓词公式-前束范式,例子：P51,课堂练习：练习2.4（B）3,24,.,2.5谓词逻辑地推理理论,谓词演算的推理是命题演算推理的推广和扩充,命题演算中的一些规则，如基本等值公式，重言蕴含式以及,P,，,T,，,CP,规则在谓词演算中仍然使用,.,25,.,2.5谓词逻辑地推理理论,在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，引入消去和添加量词的规则，以便使谓词演算公式的推理过程可类似于命题演算的推理进行,US,规则,(,全称量词消去规则,),UG,规则,(,全称量词附加规则,),ES,规则,(,存在量词消去规则,),EG,规则,(,存在量词附加规则,),等,26,.,2.5谓词逻辑地推理理论,课堂练习,27,.,本章小结,本章重点,：,谓词与量词，公式与解释，前束范式，谓词逻辑推理证明,主要概念,：,谓词 个体词 量词 变元,前束范式 推理规则,主要方法：,推理规则,（,US,规则,UG,规则,ES,规则,EG,规则）,主要公式：,(1),命题公式的推广；,(2),量词否定式的等值式；,(3),量词辖域扩张和收缩的等值式；,(4),量词与联结词,，,，,的等值式；,(5),量词与联结词的重言蕴含式；,(6),两个量词公式间的等值式与重言蕴含式,28,.,