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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2.1谓词的概念与表示,命题逻辑的局限性：,下列推理：,凡是人都是要死的。,苏格拉底是人。,苏格拉底是要死的。,众所周知，这是真命题。但在命题逻辑中,(,P,Q),R,，,难证其为重言式。,原因：命题逻辑不考虑命题之间的内在联系和数量关系。,办法：将命题再次细分。,2.1谓词的概念与表示,谓词,在反映判断的句子中，用以刻划客体的性质或关系的即是谓词。,例：,(1)3是有理数。(2),x,是无理数。,(3)阿杜与阿寺同岁。,(4),x,与,y,有关系,L。,其中，“是有理数”、“是无理数”、“与同岁”、“与有关系,L”,均为谓词。前两个是指明客体性质的谓词，后两个是指明两个客体之间关系的谓词。,2.1谓词的概念与表示,将上述谓词分别记作大写字母,F、G、H、L，,用小写字母表示客体名称，则上述可表示为：,(1),F(3)(2)G(x),(3)H(a,b)a:,阿杜,b:,阿寺,(4),L(x,y),谓词填式,单独一个谓词不是完整的命题，把谓词字母后填以客体所得的式子称为谓词填式。,2.1谓词的概念与表示,n,元谓词,由,n,个客体插入到固定位置上的谓词填式。,例如：,A(b),称作一元谓词，,B(a,b),称作二元谓词，,L(a,b,c),称作三元谓词，,P(x,1,x,2,x,n,),称作,n,元谓词。,注意：代表客体名称的字母，它在多元谓词中出现的次序是固定的，与事先约定的次序有关，如,L(a,b,c),和,L(b,c,a),代表两个不同的命题。,2.2命题函数与量词,例：,H,是谓词“能够到达山顶”，,t,表示老虎，,c,表示汽车，,z,表示张三，那么,H(t),H(c),H(z),表示三个不同的命题，但它们有一个共同的形式,H(x)，,当,x,分别取,t,c,z,时。,L(x,y),表示“,x,小于,y”，,那么,L(2,3),表示了一个真命题“2小于3”，而,L(5,1),表示假命题“5小于1”。可以看出，,L(x,y),本身不是一个命题，只有当变元,x,y,取特定的客体时，才是一个命题。,2.2命题函数与量词,简单命题函数,由一个谓词，一些客体变元组成的表达式称为简单命题函数。,n,元谓词就是有,n,个客体变元的命题函数。,不带任何客体变元的谓词称为0元谓词。,复合命题函数,由一个或,n,个简单命题函数以及逻辑联结词组合而成的表达式称复合命题函数。,2.2命题函数与量词,命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。,但客体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。,例：,R(x),表示“,x,是大学生”，如果,x,的讨论范围是某大学里班级中的学生，则,R(x),是永真式。如果,x,的讨论范围是某中学里班级中的学生，则,R(x),是永假式。如果,x,的讨论范围为一剧场中的观众，那么对某些观众，,R(x),为真，对另一些观众，,R(x),为假。,2.2命题函数与量词,个体,可以独立存在的具体的或抽象的客体。,个体常量：具体的或特定的，一般用,a,b,c,表示。,个体变元,：,抽象的或泛指的，一般用,x,y,z,表示。,个体域,个体变元的论述范围。,全总个体域,把各种个体域综合在一起作为论述范围的域。,2.2命题函数与量词,量词,用来表示个体常量或变元之间数量关系的词。量词分为两种：,全称量词表示“一切”,“所有”,“凡”,“每一个”,“任意”等意的词称为全称量词，记作。,如：,x,表示个体域内所有的,x。,存在量词表示“某个”,“对于一些”,“存在一些”,“至少有一个”等意的词称为存在量词，记作。,如：,y,表示个体域内存在一些,y。,2.2命题函数与量词,例：用谓词表达式写出下列命题。,(1)凡是人都呼吸。,(2)有的人是左撇子。,解：令,F(x)：x,呼吸。,G(x)：x,是左撇子。,当个体域为,人类集合,时：,(1),xF(x)(2)xG(x),当个体域为,全总个体域,时：,令,M(x)：x,是人。,(1),x(M(x),F(x)(2)x(M(x)G(x),2.2命题函数与量词,约定：以后如不指定个体域，默认为全总个体域。,特性谓词在讨论带有量词的命题函数时，必须确定其个体域。当使用全总个体域时，对客体变元的变化范围限制的词，称作特性谓词。,如上例中，,M(x),为,F(x),和,G(x),的特性谓词，它限定了变元,x,的范围。,一般，对全称量词，特性谓词常作条件的前件；对存在量词，特性谓词常作合取项。,2.2命题函数与量词,例：将下列命题符号化，并讨论其真值。,(1)所有的人都长头发。,解:令,M(x):x,是人。,F(x):x,长头发。则,x(M(x),F(x),真值为,0,(2)有的人吸烟。,解:令,M(x):x,是人。,S(x):x,吸烟。则,x(M(x)S(x),真值为,1,2.2命题函数与量词,(3)没有人登上过木星。,解:令,M(x):x,是人。,D(x):x,登上过木星。则,x(M(x)D(x),真值为,1,(4)清华大学的学生未必都是高素质的。,解:令,Q(x):x,是清华大学的学生。,H(x):x,是高素质的。则,x(Q(x),H(x),真值为,1,或,x(Q(x),H(x),可见，有些命题的符号化形式不止一种。,2.2命题函数与量词,至此，,下列推理即可解决：,凡是人都是要死的。,苏格拉底是人。,苏格拉底是要死的。,令,M(x):x,是人。,D(x):x,是要死的。,s:,苏格拉底。则谓词表达式为：,(,x)(M(x)D(x),M(s),D(s),2.3 谓词公式与翻译,一阶语言,一阶语言,F,的字母表定义如下:,(1)个体常项：,a,b,c,a,i,b,i,c,i,i,1.,(2),个体变项：,x,y,z,x,i,y,i,z,i,i,1.,(3),函数符号：,f,g,h,f,i,g,i,h,i,i,1.,(4),谓词符号：,F,G,H,F,i,G,i,H,i,i,1.,(5),量词符号：,，,.,(6),联结词符号：,，,，,，,.,(7),括号与逗号：,(,),.,2.3 谓词公式与翻译,F,的项：,(1),个体常项和个体变项都是项,。,(2),若,f(x,1,x,2,x,n,),是任意的,n,元函数，,t,1,t,2,t,n,是任意的,n,个项，则,f(t,1,t,2,t,n,),是项。,(3)所有的项都是有限次使用(1),(2)得到的。,原子公式,若,A(x,1,x,2,x,n,),是,F,的任意,n,元谓词，,t,1,t,2,t,n,是,F,的任意,n,个项，则称,A(t,1,t,2,t,n,),为谓词演算的原子公式。,2.3 谓词公式与翻译,谓词演算的合式公式/谓词公式,(1),原子公式是合式公式。,(2),若,A,是合式公式，则(,A),也是合式公式。,(3),若,A,和,B,是合式公式，则(,A,B)，(A,B)，(A,B)，(A,B),也是合式公式。,(4),若,A,是合式公式，,x,是,A,中出现的任何变元，则,x,A,和,x,A,，也是合式公式。,(5),只有有限次应用规则,(1),(4),构成的符号串才是合式公式。,2.3 谓词公式与翻译,约定：最外层的圆括号可以省略。但量词后面若有括号则不能省略。,例：将下列命题符号化。,(1)没有不能表示为分数的有理数。,解:令,Q(x):x,是有理数。,W(x):x,能表示成分数。,则,x(Q(x)W(x),或,x(Q(x)W(x),2.3 谓词公式与翻译,(2)在北京买菜的人不全是外地人。,解:令,B(x):x,在北京买菜的人。,F(x):x,是外地人。则,x(B(x)F(x),或,x(B(x)F(x),例：将下列命题符号化。,(1)火车都比轮船快。,解:令,T(x):x,是火车。,S(x):x,是轮船。,F(x,y):x,比,y,跑得快。则,xy(T(x)S(y),F(x,y),2.3 谓词公式与翻译,(2)有的火车比有的汽车快。,解:令,T(x):x,是火车。,C(x):x,是汽车。,F(x,y):x,比,y,跑得快。则,xy(T(x)C(y)F(x,y),(3)不存在比所有火车都快的汽车。,解:令,T(x):x,是火车。,C(x):x,是汽车。,F(x,y):x,比,y,跑得快。则,x(C(x)y(T(y)F(x,y),或,x(C(x)y(T(y)F(y,x),2.4 变元的约束,给定,A,为一谓词公式，其中有一部分公式形为,x,P(x),或,xP(x)。,和,后面所跟的,x，,称为相应量词的,指导变元,。,P(x),称为相应量词的,作用域,/,辖域,。,在,x,和,x,的辖域中，,x,的所有出现都称为,x,在公式,A,中的,约束出现,，所有约束出现的变元，叫做,约束变元,。,A,中不是约束出现的变元均称作,自由变元,。,2.4 变元的约束,(1),x(F(x)G(x,y),x,是指导变元，量词的辖域为,(F(x)G(x,y)，,其中，,x,是约束出现两次，,y,是自由出现一次。,(2),x F(x,y)y G(x,y),x,是指导变元，量词的辖域是,F(x,y)，,其中，,x,是约束出现一次，,y,是自由出现一次；同时，,y,也是指导变元，量词 的辖域是,G(x,y)，,其中，,y,是约束出现一次，,x,是自由出现一次。,2.4 变元的约束,(3),x y(F(x,y)G(y,z)x H(x,y,z),x、y,是指导变元，对应量词、的辖域为,y,(,F(x,y)G(y,z),和(,F(x,y)G(y,z),，其中,x,是约束出现一次，,y,是约束出现两次，,z,是自由出现一次；后一个,x,也是指导变元，量词的辖域为,H(x,y,z)，,其中,x,是约束出现一次，,y、z,是自由出现一次。,2.4 变元的约束,例:(1),x,(,H(x,y)y,(,W(y)L(x,y,z),),),(2),x,(,H(x)W(y),),y,(,F(x)L(x,y,z),),为了避免由于变元的约束与自由同时出现，引起概念上的混乱，故可对约束变元进行,换名,。使得一个变元在一个公式中只呈一种形式出现，即呈,自由出现,或呈,约束出现,。,一个公式的约束变元所使用的名称符号是无关紧要的，即,x,P(x),与,y,P(y),具有相同的意义，,xP(x),与,yP(y),意义也相同。,2.4 变元的约束,约束变元的换名,规则：,对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，公式的其余部分不变。,换名时一定要更改为作用域中没有出现的变元名称。,例:对,x,(,H(x,y)y,(,W(y)L(x,y,z),),),换名。,解:可换名为,x,(,H(x,y)u,(,W(u)L(x,u,z),),),2.4 变元的约束,对于公式中的自由变元，也允许更改，这种更改叫做,代入,/,代替,。,自由变元的代入,规则：,对于谓词公式中的自由变元，可以作代入，代入时需对公式中出现该自由变元的每一处进行。,用以代入的变元与原公式中所有变元的名称不能相同。,2.4 变元的约束,例:对,x,(,H(x)W(y),),y,(,F(x)L(x,y,z),),代入。,解:经代入后公式为,x,(,H(x)W(v),),y,(,F(u)L(u,y,z),),2.4 变元的约束,A(x,1,x,2,x,n,),是,n,元谓词，它有,n,个相互独立的自由变元。若对其中,k,个变元进行约束则成,n-k,元谓词。若谓词公式中没有自由变元出现，则该式就成为一个命题。,当论域的元素有限时，可以消去公式中的量词。设论域元素为,a,1,a,2,a,n,。,则,(,x,)A,(,x),A(a,1,),A(a,2,),A(a,n,),(,x)A(x)A(a,1,),A(a,2,),A(a,n,),2.4 变元的约束,量词对变元的约束，往往与量词的次序有关。命题中的多个量词，我们约定从左到右的次序读出。注意:量词的次序不能颠倒，否则将与原命题不符。,2.5 谓词演算的等价式与蕴含式,赋值,/,解释,在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题所取代时，就称作对谓词公式,赋值,。一个谓词公式经过赋值以后，就成为命题。,等价,给定任何两个谓词公式,wff A,和,wff B，,设它们有共同的个体域,E，,若对,A,和,B,的变元的任一组真值指派，所得真值均相同，则称谓词公式,A,和,B,在,E,上是,等价,的，并记作,A,B。,永真式,/,逻辑有效式,给定任意谓词公式,wff A，,其个体域为,E，,对于,A,的任一组真值指派，,wff A,皆为,1，,则称公式,A,在,E,上是,有效的,/,永真的,。,不可满足式,/,永假式,一个谓词公式,wff A，,如果在所有赋值下都为,0，,则称该,wff A,是,不可满足的,/,永假的,。,可满足式,一个谓词公式,wff A，,如果至少在一种赋值下为,T，,则称该,wff A,是,可满足的,。,2.5 谓词演算的等价式与蕴含式,谓词演算中的等价式和蕴涵式,命题演算中的等价公式表和蕴含公式表都可,推广,到谓词演算中使用。,消去量词的等价式,量词否定的等价式,（,量词的转化律）,(,x)P(x)(,x),P(x),，,(,x)P(x),(,x),P(x),证明：(可在有限个体域上证明),2.5 谓词演算的等价式与蕴含式,设个体域中的客体变元为,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),2.5 谓词演算的等价式与蕴含式,量词作用域的扩张与收缩的等价式,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(BA(x),Bx 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(BA(x),Bx A(x),2.5 谓词演算的等价式与蕴含式,以上各等价式中的,B,不含客体变元,x;,或含有与量词指导变元,x,不同的变元,如,y,z,等。,试证明,x(A(x)B),x A(x)B,证：左,x(A(x)B),x A(x)B,x A(x)B,x A(x)B（,右）,2.5 谓词演算的等价式与蕴含式,量词分配的等价式,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)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),x A(x),x B(x)x(A(x)B(x),2.5 谓词演算的等价式与蕴含式,具有两个量词的二元谓词公式（共八种）,x y A(x,y)y x 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),x y A(x,y)y x A(x,y),后四种均不等价，故全称量词和存在量词在公式中出现的次序，不能随意更换。,2.5 谓词演算的等价式与蕴含式,2.6 前束范式,前束范式,一个公式如果量词均包含在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式叫做,前束范式,。其形式为(,v,1,),(,v,2,),(,v,n,)A，,其中,是量词,或，,v,i,(i=1,2,n),是客体变元，,A,是没有量词的谓词公式。,如：,x y,(,(F(x)G(y)H(x,y),),x y,(,F(x,y)G(y,z),),x H(x,y,z),2.6 前束范式,Th1(,前束范式存在定理),任意一个谓词公式，均和一个前束范式等价。,本定理说明任何公式的前束范式都是存在的，但一般不是唯一的。,求法：,利用对合律、德,摩根律、量词转化律把否定深入到命题变元和谓词填式的前面；,利用换名和代入规则，量词作用域的扩张和收缩等价式，把量词提到前面。,2.6 前束范式,例:求下列公式的前束范式。,(1),x F(x)x G(x),解：,xF(x),xG(x),xF(x)xG(x)(,量词否定等价式),x(F(x)G(x)(,量词分配等价式),或,xF(x)yG(y)(,换名规则),xF(x)yG(y)(,量词否定等价式),x(F(x)yG(y)(,量词辖域扩张等价式),xy(F(x)G(y)(,量词辖域扩张等价式),2.6 前束范式,(2),x F(x)x G(x),解：原式,xF(x)yG(y)(,换名规则),xF(x)yG(y)(,量词否定等价式),x(F(x)yG(y)(,量词辖域扩张等价式),xy(F(x)G(y)(,量词辖域扩张等价式),(3),x F(x)x G(x),解：原式,xF(x)yG(y)(,换名规则),xy(F(x)G(y)(,量词辖域扩张等价式),2.6 前束范式,(4),x F(x,y)y G(x,y),解：,xF(x,y)yG(x,y),t F(t,y)w G(x,w),(,换名规则),tw(F(t,y)G(x,w),(,量词辖域扩张等价式),或,x F(x,t)y G(w,y),(,代入规则),xy(F(x,t)G(w,y),(,量词辖域扩张等价式),(5),x F(x)x G(x),解：原式,xF(x),yG(y),(,换名规则),x y(F(x),G,(y),(,量词辖域扩张等价式),2.6 前束范式,(6)(,x F(x,y)y G(y)x H(x,y,z),解：原式,(,x F(x,y)b G(b),),c H(c,y,z),x b,(,F(x,y)G(b),),c H(c,y,z),x b c,(,(,F(x,y)G(b),),H(c,y,z),),2.6 前束范式,前束合取范式,一个,wff A,如果具有如下形式，则称为,前束合取范式,。(,v,1,),(,v,2,),(,v,n,)(A,11,A,12,A,1k,1,),(A,21,A,22,A,2k,2,),(A,m1,A,m2,A,mk,m,)，,其中,是量词,或，,v,i,(i=1,2,n),是客体变元，,A,i j,是原子公式或其否定。,Th2(,前束合取范式存在定理),每一个,wff A,都可转化为与其等价的前束合取范式。,2.6 前束范式,前束析取范式,一个,wff A,如果具有如下形式，则称为,前束析取范式,。(,v,1,),(,v,2,),(,v,n,)(A,11,A,12,A,1k,1,),(A,21,A,22,A,2k,2,),(A,m1,A,m2,A,mk,m,)，,其中,是量词,或，,v,i,(i=1,2,n),是客体变元，,A,i j,是原子公式或其否定。,Th3(,前束析取范式存在定理),每一个,wff A,都可转化为与其等价的前束析取范式。,2.6 前束范式,任一个,wff A,转换为等价的前束合(析)取范式的步骤：,消去公式中出现的多余量词；,利用换名、代入规则使所有约束变元均不相同，并且使约束变元和自由变元不同；,将谓词公式中出现的联结词均转化成,；,2.6 前束范式,利用对合律，德,摩根律及量词转化律，将谓词公式中的,深入到命题变元和谓词填式的前面；,利用量词作用域的扩张和收缩等价式，将量词推到左边，扩大量词作用域至整个公式。,2.7 谓词演算的推理理论,命题演算中的推理规则，如,P、T,和,CP,规则等也可在谓词演算的推理理论中应用。,但在谓词推理中，某些前提与结论可能受量词限制，为了能使用命题演算中的等价式和蕴含式，必须在推理过程中有消去和添加量词的规则。,2.7 谓词演算的推理理论,(1)全称指定规则（简记为,US）,(,x)P(x),P(c),如果对论域中所有客体,x，P(x),成立，则对论域中某个任意客体,c，P(c),成立。,2.7 谓词演算的推理理论,(2)全称推广规则（简记为,UG,）,P(x),(,x)P(x),如果能够证明对论域中每一个客体,c,断言,P(c),都成立，则可得到结论,(,x)P(x),成立。,2.7 谓词演算的推理理论,(3)存在指定规则（简记为,ES）,(,x)P(x),P(c),如果对于论域中某些客体,P(x),成立，则必有某个特定客体,c，,使,P(c),成立。应注意，指定的客体,c,不是任意的。,2.7 谓词演算的推理理论,(4)存在推广规则（简记为,EG）,P(c),x P(x),如果对论域中某个特定客体,c，,有,P(c),成立，则在论域中，必存在,x,使得,P(x),成立。,2.7 谓词演算的推理理论,例：构造下列推理的证明。,前提：,x(A(x)B(x)，x A(x),结论：,x B(x),证明：(1),x A(x)P,(2),A(c)(1)ES,(3),x(A(x)B(x)P,(4),A(c)B(c)(3)US,(5),B(c),(2)(4),假言推理,(6),x B(x)(5)EG,注意：(1)(3)引入的顺序不可更改!,2.7 谓词演算的推理理论,例：证明,凡是人都是要死的。,苏格拉底是人。,苏格拉底是要死的。,解:令,M(x):x,是人。,D(x):x,是要死的。,a:,苏格拉底。即要证,x(M(x)D(x),M(a),D(a),证明(1),x(M(x)D(x)P,(2),M(a)D(a)(1)US,(3),M(a),P,(4),D(a),(2)(3)I,2.7 谓词演算的推理理论,例：学术委员会的每个成员都是博士并且是教授。有些成员是青年人。因而有的成员是青年博士。,解：先将命题符号化.,A(x):x,是学术委员会成员。,B(x):x,是博士。,J(x):x,是教授。,H(x):x,是青年人。,前提:,x(A(x)B(x)J(x),x(A(x)H(x),结论:,x(A(x)H(x)B,(,x),2.7 谓词演算的推理理论,证明 (1),x(A(x)H(x)P,(2),A(c)H(c)(1)ES,(3),x(A(x)B(x)J(x),P,(4),A(c)B(c)J(c)(3)US,(5),A(c)(2),化简,(6),H(c)(2),化简,(7),B(c)J(c)(4)(5),假言推理,(8),B(c)(7),化简,(9),A(c)H(c)B(c)(5)(6)(8),合取,(10),x(A(x)H(x)B(x)(9)EG,2.7 谓词演算的推理理论,例：有些病人相信所有的医生。但是病人都不相信骗子。所以，医生都不是骗子。,解：先将简单命题符号化,A(x):x,是病人。,B(x):x,是医生。,J(x):x,是骗子。,H(x,y):x,相信,y。,前提:,x(A(x)y(B(y)H(x,y),x(A(x)y(J(y)H(x,y),结论:,x(B(x)J(x),证明 (1),x(A(x)y(B(y)H(x,y)P,(2),A(c)y(B(y)H(c,y)(1)ES,2.7 谓词演算的推理理论,(3),A(c)(2),化简,(4),y(B(y)H(c,y)(2),化简,(5),x(A(x)y(J(y)H(x,y),P,(6),A(c)y(J(y)H(c,y)(5)US,(7),y(J(y)H(c,y)(3)(6),假言推理,(8),y(H(c,y)J(y)(7),置换,(9),B(z)H(c,z)(4)US,(10),H(c,z)J(z)(8)US,(11),B(z)J(z)(9)(10),假言三段论,(12),x(B(x)J(x)(11)UG,