离散数学第三章谓词演算基础-自由变元和约束变元

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 谓词演算基础,3.1,谓词与个体,3.2,函数与量词,3.3,自由变元和约束变元,3.3.1,自由出现和约束出现,3.3.2,改名和代入,3.4,永真性和可满足性,3.5,唯一性量词与摹状词,复习,:,项,例 考察谓词,WRITE(x,y),表示,x,写了,y,的谓词填式：,WRITE(Shakespeare,，,Hamlet,),WRITE(Shakespeare,，,y,),WRITE(,son,(Shakespeare,),，,Hamlet),变量符号,函数！,实体,谓词演算公式的原子公式,谓词填式,A,(,x,1,，,x,2,，,，,x,n,),其中,x,1,，,，,x,n,是项,(,实体、变量符号、函数,),。,原子公式是公式的最小单位，是最小的句子单位。,项不是公式。,函数,f(t,1,.,，,t,m,),不是句子，仅是词，因而不是公式仅是项。项的结果仍是个体名称集合中的名词，而公式的结果,(,真值,),是成立或不成立,(,是,1,或,0),。,合式公式的定义,定义,1,：谓词演算的,合式公式,(,简称公式,),是由,原子命题、,谓词填式（原子公式）、,或由它们利用联结词和量词,构成的式子。,合式公式的形式定义,(1),原子命题,P,是合式公式；,(2),谓词填式,A,(,x,1,，,x,2,，,x,3,，,，,xn,),是合式公式；,(3),若,A,是公式，则,A,是合式公式；,(4),若,A,和,B,是合式公式，则,(,A,B,),，,(,A,B,),，,(,A,B,),，,(,A,B,),为公式；,(5),若,A,是合式公式，,x,是,A,中出现的任何个体变元，则,xA,(,x,),，,xA,(,x,),为合式公式。,(6),只有有限次使用,(1),、,(2),、,(3),、,(4),、,(5),所得到的式子才是合式公式。,自由出现和约束出现,定义,2,：设,为任何一个谓词演算公式，并设,xA,(,x,),，,xA,(,x,),为公式,的子公式，,此时紧跟在,、,之后的,x,称为量词的,指导变元,或,作用变元,，,A,(,x,),称为相应量词的,作用域,或,辖域,，,在作用域中,x,的一切出现均称为,约束出现,，,在,中除了约束出现外的一切出现,x,均称为,自由出现,。,例,x,(,A,(,x,，,y,),例,(29),x,(,A,(,x,，,y,),y,(,B,(,x,，,y,),C,(,z,),),指出合式公式的作用域、约束出现和自由出现。,解：,x,的作用域为：,A,(,x,，,y,),y,(,B,(,x,，,y,),C,(,z,),；,y,的作用域为：,B,(,x,，,y,),C,(,z,),；,公式中的,x,为约束出现，,第一个,y,和,z,是自由出现，,B,(,x,，,y,),C,(,z,),中的,y,为约束出现。,自由变元和约束变元,定义,3,：一个变元,x,若在公式中有自由出现，则称此变元为,自由变元,；,若有约束出现，则称为,约束变元,。,例,x,(,A,(,x,，,y,),x,为约束变元，,y,为自由变元，不受全称量词约束，可以看作为公式中的参数。,例,x(p(x),yQ(x,y),指出公式的指导变元，辖域、约束变元和自由变元。,解：由,x,后的,(),，,x,是指导变元，,x,的辖域是后面整个式子,p(x),yQ(x,y),，,y,是指导变元，辖域仅,Q(x,，,y),此部分。,x,两次出现均是约束出现，,y,的一次出现是约束出现，故,x,，,y,是约束变元，而不是自由变元。,例,xF(x),G(x,y),指出公式的指导变元，辖域、约束变元和自由变元。,解：,x,的辖域仅,F(x),x,是指导变元，变元,x,第一次出现是约束出现，第二次出现是自由出现，,y,的出现是自由出现。,所以第一个,x,是约束变元，第二个,x,是自由变元，本质上这两个,x,的含义是不同的；而,y,仅是自由变元。,例,x(x=y,x,2,+x5,xz),x=5,y,2,指出公式的指导变元，辖域、约束变元和自由变元。,解：,x=y,，,x,2,+x5,，,xz,，,x=5y,2,这是四个原子公式,用逻辑词,，,，,来联结起来的。,x,是指导变元、,x,的辖域是,(),内的这部分,x=y,x,2,+x5,xz,。,因此，,x,第一、二、三、四次出现是约束出现，,x,第五次出现是自由出现。,而,y,，,z,的出现均是自由出现。,第三章 谓词演算基础,3.1,谓词与个体,3.2,函数与量词,3.3,自由变元和约束变元,3.3.1,自由出现和约束出现,3.3.2,改名和代入,3.4,永真性和可满足性,3.5,唯一性量词与摹状词,一、改名,x,(,A,(,x,，,y,),y,(,B,(,x,，,y,),C,(,z,),其中,同一个变元,y,既有约束出现又有自由出现。,对约束变元进行改名，使得,同一个变元要么为约束出现，要么为自由出现，,同时使不同的量词所约束的变元不同名,.,改名的规则,(1),改名是对约束变元而言，自由变元不能改名，改名时应对量词的指导变元及其作用域中所出现的约束变元处处进行；,(2),改名前后不能改变变元的约束关系；,(3),改名用的新名应是该作用域中没有使用过的变元名称。,例：,x,(,A,(,x,，,y,),y,(,B,(,x,，,y,),解：可把公式改名为：,x,(,A,(,x,，,y,),z,(,B,(,x,，,z,),例 对下面公式实施改名,(1),x(A(x,，,y),y(B(x,，,y),C(z),(2),xF(x,，,y),xG(x,，,y),解：,(1),可把公式改名为：,x(A(x,，,y),u(B(x,，,u),C(z),(2)x,是约束变元,y,是自由变元。而,x,的两次出现尽管均是约束的,但分别在不同的辖域。含义是互相无关的。可以将一处换名,但不能与,y,同名。可以改名为：,xF(x,，,y),uG(u,，,y),例,x,(,F(x,y),P(x),),y,(,Q(x,y)R(x),),解：,x,前两次出现是约束的,后两次出现是自由的。,y,第一次出现是自由的,第二次是约束的,准备将约束变元,x,改为,u,约束变元,y,改为,v,成为,u,(,F(u,y),P(u),),v,(,Q(x,v),R(x),),二、代入,谓词演算公式中的自由变元可以更改，称为代入。,代入是对自由变元而言，,约束变元不能代入。,代入后的式子是原式的特例,代入规则,(1),代入必须处处进行，即代入时必须对公式中出现的所有同名的自由变元进行。,(2),代入后不能改变原式和代入式的约束关系。,(3),代入也可以对谓词填式而言，但也要遵循上面两条规则；,(4),命题变元也可以实施代入,。,例,x(A(x,，,y),y(B(x,，,y),C(z),试把公式中的自由变元,y,代以式子,x,2,+2,。,解：先对原式改名，,x,改为,u,，,y,改为,v,，,改名后得：,u,(,A,(,u,，,y,),v,(,B,(,u,，,v,),C,(,z,),最后代入得：,u,(,A,(,u,，,x,2,+2),v,(,B,(,u,，,v,),C,(,z,),验证公式可知，没有改变变元的约束关系，所以这种代入符合代入规则。,例,x(A(x,，,y),y(B(x,，,y),C(z),试把公式中的谓词变元,A(e,1,，,e,2,),代以,yD(e,1,，,e,2,，,y,，,x),。,解,:,现在先对原式改名，,x,改为,u,，,y,改为,v,得：,u,(,A,(,u,，,y,),v,(,B,(,u,，,v,),C,(,z,),，,再对代入式改名，,y,改为,t,得：,tD,(,e,1,，,e,2,，,t,，,x,),，,最后代入，得：,u,(,tD,(,u,，,y,，,t,，,x,),v,(,B,(,u,，,v,),C,(,z,),第三章 谓词演算基础,3.1,谓词与个体,3.2,函数与量词,3.3,自由变元和约束变元,3.3.1,自由出现和约束出现,3.3.2,改名和代入,3.4,永真性和可满足性,3.5,唯一性量词与摹状词,