第2章谓词逻辑.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,离散数学-谓词逻辑,第二章 谓词逻辑,在Ls中，把命题分解到原子命题为止，认为原子命题是不能再分解的，仅仅研究以,原子命题为基本单位,的复合命题之间的逻辑关系和推理。这样，有些推理用命题逻辑就难以确切地表示出来。例如，著名的,亚里士多德三段论,苏格拉底推理：,退出,所有的人都是要死的，,苏格拉底是人，,所以苏格拉底是要死的。,根据常识，认为这个推理是正确的。但是，若用Ls来表示，设,P,、,Q,和,R,分别表示这三个原子命题，则有,P,，,Q,R,然而，(,P,Q,),R,并不是永真式，故上述推理形式又是错误的。一个推理，得出矛盾的结论，问题在哪里呢?问题就在于这类推理中，,各命题之间的逻辑关系不是体现在原子命题之间，而是体现在构成原子命题的内部成分之间,，即体现在命题结构的,更深层次,上。对此，Ls是无能为力的。所以，在研究某些推理时，,有必要对,原子命题,作进一步分析，分析出其中的,个体词,，,谓词,和,量词,，研究它们的形式结构的逻辑关系、正确的推理形式和规则，这些正是谓词逻辑（简称为Lp）的基本内容。,2.1 个体、谓词和量词,2.2 谓词公式与翻译,2.3 约束变元与自由变元,2.4 公式解释与类型,2.5 等价式与蕴涵式,2.6 谓词公式范式,2.7 谓词逻辑的推理理论,2.1 个体、谓词和量词,在Lp中，命题是具有真假意义的陈述句。从语法上分析，一个陈述句由,主语,和,谓语,两部分组成。在Lp中，为揭示,命题内部结构及其不同命题的内部结构关系,，就按照这两部分对命题进行分析，并且把,主语,称为,个体,或,客体,，把,谓语,称为,谓词,。,对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定把小写字母写在大写字母右侧的圆括号()内。,例如,，在命题“张三是位大学生”中，“张三”是个体，“是位大学生”是谓词，它刻划了“张三”的性质。设,S,：是位大学生，,c,：张三，则“张三是位大学生”可表示为,S,(,c,)，或者写成,S,(,c,)：张三是位大学生。,又如,，在命题“武汉位于北京和广州之间”中，武汉、北京和广州是三个个体，而“位于和之间”是谓词，它刻划了武汉、北京和广州之间的关系。设,P,：位于和之间，,a,：武汉，,b,：北京，,c,：广州，则,P,(,a,，,b,，,c,)：武汉位于北京和广州之间。,定义2.1.2,一个原子命题用一个谓词(如,P,)和,n,个有次序的,个体常元,(如,a,1,，,a,2,，,a,n,)表示成,P,(,a,1,，,a,2,，,a,n,)，称它为该原子命题的谓词形式或,命题的谓词形式,。,应注意的是，命题的谓词形式中的,个体出现的次序影响命题的真值,，不是随意变动，否则真值会有变化。如上述例子中，,P,(,b,a,c,)是假。通常个体出现的次序事先要约定好。,.原子谓词公式,原子命题的谓词形式还可以进一步加以抽象，比如在谓词右侧的圆括号内的,n,个,个体常元,被替换成,个体变元,，如,x,1,x,2,x,n,，这样便得了一种关于命题结构的新表达形式，称之为,n,元原子谓词。,定义2.1.3,由一个谓词(如,P,)和,n,个体变元(如,x,1,，,x,2,，,x,n,)组成的,P,(,x,1,，,x,2,，,x,n,)，称它为,n,元原子谓词,或,n,元命题函数,，简称,n,元谓词。而个体变元的论述范围，称为,个体域,或,论域,。,当,n,=1时，称一元谓词；当,n,=2时，称为二元谓词，。特别地，当,n,=0，称为零元谓词。,零元谓词,就是通常的命题，这样命题与谓词就得到了统一。,通常一元谓词表达了个体的“性质”，而多元谓词表达了个体之间的关系。,n,元谓词不是命题,，,只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。,但个体变元在哪些论域取特定的值，对命题的真值极有影响。,例如,，令,S,(,x,)：,x,是大学生。若,x,的论域为某大学的计算机系中的全体同学，则,S,(,x,)是真的；若,x,的论域是某中学的全体学生，则,S,(,x,)是假的；若,x,的论域是某剧场中的观众，且观众中有大学生也有非大学生的其它观众，则,S,(,x,)是真值是不确定的。,通常，把一个,n,元谓词中的每个个体的论域综合在一起作为它的论域，称为,n,元谓词的全总论域。定义了,全总论域,或全总个体域，为深入研究命题提供了方便。当一个命题没有指明论域时，一般都从全总论域作为其论域。而这时又常常要采用一个谓词如,P,(,x,)来限制个体变元,x,的取值范围，并把,P,(,x,)称为,特性谓词,。,.量词,利用,n,元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题。,例如,S,(,x,)表示,x,是大学生，而,x,的个体域为某单位的职工，那么,S,(,x,)可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧义，在Lp中，需要引入用以刻划“所有的”、“存在一些”等表示不同数量的词，即量词，其定义如下：,定义2.1.4,符号,称为全称量词符，用来表达“对所有的”、“每一个”、“对任何一个”、“一切”等词语；,x,称为,全称量词,，称,x,为指导变元。,符号,称为存在量词符，用来表达“存在一些”、“至少有一个”、“对于一些”、“某个”等词语；,x,称为,存在量词,，,x,称为指导变元。,符号,!称为存在唯一量词符，用来表达“恰有一个”、“存在唯一”等词语；,!,x,称为存在唯一量词，称,x,为指导变元。,全称量词、存在量词、存在唯一量词统称量词。量词记号是由逻辑学家F,ray,引入的，有了量词之后，用逻辑符号表示命题的能力大大加强了。,例2.1.1,试用量词、谓词表示下列命题：,所有大学生都热爱祖国；,每个自然数都是实数；,一些大学生有远大理想；,有的自然数是素数。,解,令,S,(,x,)：,x,是大学生，,L,(,x,)：,x,热爱祖国，,N,(,x,)：,x,是自然数，,R,(,x,)：,x,是实数，,I,(,x,)：,x,有远大理想，,P,(,x,)：,x,是素数。,则例中各命题分别表示为：,(,x,)(,S,(,x,),L,(,x,)(,x,)(,N,(,x,),R,(,x,),(,x,)(,S,(,x,),I,(,x,)(,x,)(,N,(,x,),P,(,x,),在该例的解答中，由于命题中没有指明个体域，这便意味着各命题是在全总论域中讨论，因而都使用了特性谓词，如,S,(,x,)、,N,(,x,)。而且还可以看出，量词与特性谓词的搭配还有一定规律，即,全称量词后跟一个条件式,，而特性谓词作为其前件出现；,存在量词后跟一个合取式,，特性谓词作为一个合取项出现。,如果在解答时，指明了个体域，便不用特性谓词，例如在、中令个体域为全体大学生，和中的个体域为全部自然数，则可符号化为：,(,x,),L,(,x,)(,x,),R,(,x,),(,x,),I,(,x,)(,x,),P,(,x,),谓词前加上了量词，称为谓词的量化。,若一个谓词中所有个体变元都量化了，则该谓词就变成了命题,。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数,f,(,x,)，的值是不确定的，但 可确定其值。,2.2 谓词公式与翻译,.谓词公式,为了方便处理数学和计算机科学的逻辑问题及谓词表示的直觉清晰性，将引进,项,的概念。,定义2.2.1,项由下列规则形成：,个体常元和个体变元是项；,若,f,是,n,元函数，且,t,1,，,t,2,，,t,n,是项，则,f,(,t,1,，,t,2,，,t,n,)是项；,所有项都由和生成。,有了项的定义，函数的概念就可用来表示个体常元和个体变元。例如，令,f,(,x,y,)表示,x,+,y,，谓词,N,(,x,)表示,x,是自然数，那么,f,(2,3)表示个体自然数5，而,N,(,f,(2,3)表示5是自然数。这里函数是就广义而言的，例如,P,(,x,):,x,是教授，,f,(,x,):,x,的父亲，,c,:张强，那么,P,(,f,(,c,)便是表示“张强的父亲是教授”这一命题。,函数的使用给谓词表示带来很大方便。例如，用谓词表示命题：对任意整数,x,，,x,2,-1=(,x,+1)(,x,-1)是恒等式。令,I,(,x,):,x,是整数，,f,(,x,)=,x,2,-1，,g,(,x,)=(,x,+1)(,x,-1)，,E,(,x,y,):,x,=,y,，则该命题可表示成：(,x,)(,I,(,x,),E,(,f,(,x,),g,(,x,)。,定义2.2.2,若,P,(,x,1,，,x,2,，,x,n,)是,n,元谓词，,t,1,，,t,2,，,t,n,是项，则称,P,(,t,1,，,t,2,，,t,n,)为,Ls,中原子谓词公式，简称,原子公式,。,下面，由原子公式出发，给出Lp中的,合式谓词公式,的归纳定义。,定义2.2.3,合式谓词公式当且仅当由下列规则形成的符号串,原子公式是合式谓词公式；,若,A,是合式谓词公式，则(,A,)是合式谓词公式；,若,A,，,B,是合式谓词公式，则(,A,B,)，(,A,B,)，(,A,B,)和(,A,B,)都是合式谓词公式；,若,A,是合式谓词公式，,x,是个体变元，则(,x,),A,、(,x,),A,都是合式谓词公式；,仅有有限项次使用、和形成的才是合式谓词公式。,.谓词逻辑的翻译,把一个文字叙述的命题，用谓词公式表示出来，称为谓词逻辑的翻译或符号化；反之亦然。一般说来，符号化的步骤如下：,正确理解给定命题。必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来。,把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。,找出恰当量词。应注意全称量词(,x,)后跟条件式，存在量词(,x,)后跟合取式。,用恰当的联结词把给定命题表示出来。,例2.2.1,将命题“没有不犯错误的人”符号化。,解,令,M,(,x,):,x,是人;,F,(,x,):,x,犯错误，,则原命题表示为：,(,x,(,M,(,x,),F,(,x,),),也可以表示为：,(,x,)(,M,(,x,),F,(,x,)。,例2.2.2,将命题“没有最大的自然数”符号化。,解,命题中“没有最大的”显然是对所有的自然数而言，所以可理解为“对所有的,x,，如果,x,是自然数，则一定还有比,x,大的自然数”，再具体点，即“对所有的,x,如果,x,是自然数，则一定存在,y,，,y,也是自然数，并且,y,比,x,大”。令,N,(,x,):,x,是自然数，,G,(,x,y,):,x,大于,y,，,则原命题表示为：,(,x,)(,N,(,x,),(,y,)(,N,(,y,),G,(,y,x,)。,例2.2.3,将语句“今天有雨雪，有些人会跌跤”符号化。,解,本语句可理解为“若今天下雨又下雪，则存在,x,，,x,是人且,x,会跌跤”。,令,R,:今天下雨，,S,:今天下雪，,M,(,x,):,x,是人，,F,(,x,):,x,会跌跤，则本语句可表示为：,R,S,(,x,)(,M,(,x,),F,(,x,)。,由于人们对命题的文字叙述含意理解的不同，强调的重点不同，对个体性质的刻画深度不同，会影响到命题符号化的形式不同。,例,2.2.4,“这只大红书柜摆满了那些古书”。,解法1,设,F,(,x,y,):,x,摆满了,y,;,R,(,x,):,x,是大红书柜；,Q,(,y,):,y,是古书;a:这只;b:那些.,R,(,a,),Q,(,b,),F,(,a,b,).,解法2,设,A,(,x,):,x,是书柜;,B,(,x,):,x,是大的;,C,(,x,):,x,是红的;,D,(,y,):,y,是古老的;,E,(,y,):,y,是书;,F,(,x,y,):,x,摆满了,y,;a:这只;b:那些.,A(a),B(a),C(a),D(b),E(b),F(a,b).,2.3 约束变元与自由变元,定义2.3.1,给定一个谓词公式,A,，其中有一部分公式形如(,x,),B,(,x,)或(,x,),B,(,x,)，则称它为,A,的,x,约束部分，称,B,(,x,)为相应量词的,作用域,或,辖域,。在辖域中，,x,的所有出现称为,约束出现,，,x,称为,约束变元,；,A,中不是约束出现的其它个体变元的出现称为,自由出现,，这些个体变元称,自由变元,。自由变元可以看作是公式中的参数。,对于给定的谓词公式，能够,准确地判定它的,辖域,、,约束变元,和,自由变元,是很重要的,。,通常，一个量词的辖域是某公式,A,的一部分，称为,A,的子公式。因此，确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体地讲：,若量词后有括号，则括号内的子公式就是该量词的辖域；,若量词后无括号，则与量词邻接的子公式为该量词的辖域。,判定给定公式,A,中个体变元是约束变元还是自由变元，关键是要看它在,A,中是约束出现，还是自由出现。,今后常用元语言符号,A,(,x,)表示,x,是其中的一个个体变元自由出现的任意公式，如,A,(,x,)可为,P,(,x,),Q,(,x,)，,P,(,x,),(,y,),Q,(,x,y,)等。一旦在,A,(,x,)前加上量词(,x,)或(,x,)，即得公式(,x,),A,(,x,),或(,x,),A,(,x,)。这时，,x,即是约束出现了。类似地，用,A,(,x,y,)表示,x,和,y,是自由出现的公式。,定义2.3.2,设,A,为任意一个公式，若,A,中无自由出现的个体变元，则称,A,为封闭的合式公式，简称,闭式,。,由闭式定义可知，闭式中所有个体变元均为约束出现。,例,说明以下各式的辖域与变元约束的情况。,a)(,x,),(,P,(,x,),Q,(,x,),;(闭式),b)(,x,)(,y,),(,P,(,x,),Q,(,x,y,),;(闭式),c)(,x,)(,P,(,x,),Q,(,x,y,);,d)(,y,)(,z,),L,(,x,y,z,);,e)(,x,)(,y,),(,P,(,x,y,),Q,(,y,z,),(,x,),P,(,x,y,),;,f)(,x,)(,P,(,x,)(,x,),Q,(,x,z,),(,y,),R,(,x,y,),Q,(,x,y,);,在e)f)中,个体变元,y,既约束出现又自由出现。,从下面讨论可以看出，,在一公式中，有的个体变元既可以是约束出现，又可以是自由出现,，这就容易产生混淆。为了避免混淆，采用下面两个规则：,约束变元,改名规则,，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。,自由变元,代入规则,，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且,处处代入,。,例,对约束变元进行换名或对自由变元进行代入：,1.(,x,)(,P,(,x,),Q,(,x,y,),Q,(,x,y,);,可改名为：(,z,)(,P,(,z,),Q,(,z,y,),Q,(,x,y,);,代入：(,x,)(,P,(,x,),Q,(,x,u,),Q,(,v,u,);2.(,x,)(,P,(,y,),Q,(,x,y,)；,可改名为：(,u,)(,P,(,y,),Q,(,u,y,),可代入为：(,x,)(,P,(,z,),Q,(,x,z,).,改名规则与代入规则的共同点都是不能改变约束关系，而不同点是：,施行的对象不同。改名是对约束变元施行，代入是对自由变元施行。,施行的范围不同。改名可以只对公式中一个量词及其辖域内施行，即只对公式的一个子公式施行；而代入必须对整个公式同一个自由变元的所有自由出现同时施行，即必须对整个公式施行。,施行后的结果不同。改名后，公式含义不变，,因为约束变元只改名为另一个个体变元，约束关系不改变,。约束变元不能改名为个体常元；代入，不仅可用另一个个体变元进行代入，并且也可用个体常元去代入，从而使公式由具有普遍意义变为仅对该个体常元有意义，即公式的含义改变了。,需要指出的是：量词作用域中的约束变元，当论域的元素有限时，个体变元的所有可能的取代时可枚举的。,设论域元素为：,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,).,此外，量词对变元的约束，通常与量词的顺序有关，不能随意颠倒，约定按从左到右的顺序读出。,上面讲了约束变元改名规则和自由变元代入规则。有时在一公式,A,(,x,)中，也会用,项,t,替代个体变元,x,，那么如何做才能不引起量词和辖域间关系发生变化？或者说，替代后结果与替代前在直觉解释上没有区别这就需要引入项,t,对,A,(,x,)中的,x,是自由的概念。,定义2.3.3,令,A,是任意合式公式，,x,为自由出现。如果,x,不出现,A,中项,t,所含的任意个体变元,y,的量词(,y,)或(,y,)的辖域内，称项,t,对,A,中的,x,是自由的。,例如,，取,A,为(,x,),B,(,x,y,),(,z,),C,(,x,z,)，则项,f,(,x,w,)对,y,不是自由的，项,g,(,y,z,)对,y,是自由的，项,h,(,x,z,)不是自由的，项,y,对,x,是自由的。,由定义可知，对任何公式,A,和任意个体变元,x,，不管,x,在,A,中是否自由出现，,x,对,A,中的,x,是自由的。,2.4 公式解释与类型,1公式解释,一般情况下，Lp中的公式含有：个体常元、个体变元（约束变元或自由变元）、函数变元、谓词变元等，,对各种变元用指定的特殊常元去代替，就构成了一个公式的解释或赋值,。也就是当个体变元由具体的个体所代替，而命题变元由具体的命题所代替，这样就确定了一个具有真值：真与假的命题。当然在给定的解释下，可以对多个公式进行解释。下面给出解释的一般定义。,定义2.4.1,一个解释,I,由下面4部分组成：,非空个体域,D,I,。,D,I,中部分特定元素,a,，,b,，。,D,I,上的特定一些函数,f,，,g,，。,D,I,上特定谓词：,P,，,Q,，。,在一个具体解释中，个体常元、函数符号、谓词符号的数量一般是有限的，并且其解释一旦确定下来就不再改变，只是个体变元的值在个体域,D,I,内变化，量词符,或,仅作用于,D,I,中的元素。,2公式类型,定义2.4.2,若一公式在任何解释下都是真的，称该公式为,逻辑有效的,，或,永真的,。,若一公式在任何解释下都是假的，称该公式为矛盾式，或,永假式,或不可满足的。,若一公式至少存在一个解释使其为真，称该公式为,可满足式,。,从定义可知，逻辑有效式为可满足式，反之未必成立。,与命题公式中分类一样，谓词公式也分为三种类型，即逻辑有效式（或重言式）、矛盾式（或永假式）和可满足式。,由于谓词公式的复杂性和解释的多样性，至今还没有一个可行的算法判定任何公式的类型。早在1936年，Churen和Turing各自独立地证明了：,对于Lp，其判定问题是不可解的。但是，Lp是个半个可判定的，即若Lp中公式是重言式，则存在算法在有限步骤内能验证它。,当然，对于一些较为简单的公式，或某些特殊公式，还是可以判定其类型的。,下面讨论代入规则的扩展，因为它对判定重言式这种公式类型是很有用的。,在2.3节中，介绍了自由变元的代入规则，实际上代入规则并非只局限于自由变元，对公式中命题变元、谓词变元均可实施代入，,其关键是不能因为代入而改变原有公式的约束关系,。今将谓词变元（包括命题变元）代入规则叙述如下：,在一公式中，一个,n,元(,n,0)谓词变元,P,(,x,1,x,2,x,n,)可以代入至少有,n,个自由变元的公式,B,(,y,1,y,2,y,n,y,n,+1,y,n,+2,y,n,+,r,)，其中,r,0，,y,1,y,2,y,n,是分别对应于,x,1,x,2,x,n,的任意选定的,n,个自由变元，且对,P,出现进行处处代入，,B,中的,r,个自由变元不允许在原公式中以约束出现，,P,中的个体变元也不允许在,B,中以约束出现。,为保证代入规则顺利而正确地实行，常常对约束变元改名而适应之。,2.5 等价式与蕴涵式,1等价式,定义2.5.1,设,A,、,B,为任意两个公式，若,A,B,为逻辑有效的，也即对变元的任一赋值其真值一样，则称,A,与,B,是等价的，记为,A,B,，称,A,B,为等价式。,由于重言式(永真式)都是逻辑有效的，可见1.3节中的命题定律（基本等价式）都是Lp 等价式。,此外，还有一置换规则：,设,(,A,)是含有,A,出现的公式，,(,B,)是用公式,B,替换若干个公式,A,的结果。,若,A,B,，则,(,A,),(,B,)。,显然，,若,(,A,)为重言式，则,(,B,)也是重言式,。,下面给出涉及量词的基本等价式。,(1)量词否定等价式：,(,a,),(,x,),A,(,x,),(,x,),A,(,x,),(,b,),(,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,),),(,x,),A,(,x,).,这两个等价式，可用量词的定义给予说明。由于“并非对一切,x,，,A,为真”等价于“存在一些,x,，,A,为真”，故(,a,)成立。由于“不存在一些,x,，,A,为真”等价于“对一切,x,，,A,为真”，所以(,b,)成立。这两个等价式的意义是：否定联结词可通过量词深入到辖域中。对比这两个式子，容易看出，将(,x,)与(,x,)两者互换，可从一个式子得到另一个式子，这表明(,x,)与(,x,)具有对偶性。另外，由于这两个公式成立也表明了，两个量词是不独立的，可以互相表示，所以只有一个量词就够了。,对于多重量词前置“,”，可反复应用上面结果，逐次右移,。例如，,(,x,)(,y,)(,z,),P,(,x,y,z,),(,x,)(,y,)(,z,),P,(,x,y,z,),当量词前面的,移到量词的后面去时，存在量词改为全称量词，而全称量词改为存在量词，反之，如将量词后面的移到量词之前时，也要做相应的改变。,（2）量词辖域缩小或扩大等价式,设,B,是不含,x,自由出现，,A,(,x,)为有,x,约束出现的任意公式，则有：,(,a,)(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,b,)(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,c,),(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,d,)(,x,)(,B,A,(,x,),B,(,x,),A,(,x,),(,e,)(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,f,)(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,g,),(,x,)(,A,(,x,),B,),(,x,),A,(,x,),B,(,h,)(,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.,例,证明(,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,(,y,),(,x,),A,(,x,),B,(,y,).,(,x,)(,y,)(,P,(,x,y,),Q,(,z,),(,x,)(,y,),P,(,x,y,),Q,(,z,).,(3)量词分配律等价式：,(见书P70),例,：联欢会上所有的人既唱歌又跳舞；,与,联欢会上，所有人唱歌且所有人跳舞。,(,a,)(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),(,b,)(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,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,)(,x,),B,(,x,)。,(4)多重量词等价式,(,a,)(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(,b,)(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),其中,A,(,x,y,)为含有,x,自由出现的任意公式。,例,A,(,x,y,)表示,x,和,y,同姓；论域：,x,是甲村的人，,y,是乙村的人。,(,x,)(,y,),A,(,x,y,):甲村与乙村的所有人同姓。(,y,)(,x,),A,(,x,y,)：乙村与甲村的所有人同姓。(,x,)(,y,),A,(,x,y,)：甲村与乙村有人同姓。,2.蕴涵式,由于,Ls,中蕴涵式（或永真条件式）在Lp中都是逻辑有效的，而且使用代入规则得到蕴涵式也都是Lp中逻辑有效的。,例如,，(,x,),P,(,x,),(,x,),P,(,x,)(,y,),Q,(,y,)附加,(,x,),P,(,x,),Q,(,x,y,)(,x,),P,(,x,),Q,(,x,y,)假言推理,下面将给出Lp中的一些,蕴涵式,，其证明省略了。,(见书P70),设,A,(,x,),和,B,(,x,),为含有,x,自由出现的任意公式。,(,a,)(,x,),A,(,x,)(,x,),B,(,x,),(,x,)(,A,(,x,),B,(,x,),(,b,)(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),(,c,)(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,)(,x,),B,(,x,),(,d,)(,x,)(,A,(,x,),B,(,x,),(,x,),A,(,x,),(,x,),B,(,x,),例如,：这些学生都聪明或这些学生都努力；可以推出这些学生都聪明或努力。,(a),由,(a),推导,(b),见书,P69,证,：由（a)可得：,(,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,),(,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,)。,证毕,(2)(,a,)(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(,b,)(,y,)(,x,),A,(,x,y,),(,x,)(,y,),A,(,x,y,),(,c,)(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(,d,)(,y,)(,x,),A,(,x,y,),(,x,)(,y,),A,(,x,y,),(,e,)(,x,)(,y,),A,(,x,y,),(,y,)(,x,),A,(,x,y,),(f)(,y,)(,x,),A,(,x,y,),(,x,)(,y,),A,(,x,y,),其中，,A,(,x,y,)为含有,x,、,y,的自由出现的任意公式。,例,A,(,x,y,)表示,x,和,y,同姓；论域：,x,是甲村的人，,y,是乙村的人。,(,y,)(,x,),A,(,x,y,):表示存在一个乙村的人，甲村的人和他同姓。,(,x,)(,y,),A,(,x,y,):表示对甲村的所有人，乙村都有人与他同姓。,从上述例子发现：全称量词与存在量词在公式中出现的次序，不能随意更换。,2.6 谓词公式范式,.前束范式,定义2.6.1,一个合式公式称为,前束范式,，如果它有如下形式：,(,x,1,)(,x,2,)(,x,k,),A,其中,为量词,或,，,A,为不含有量词的公式。也就是,量词均在全式的开头部分,，它们的辖域延伸至整个公式的末尾。称,x,1,x,2,x,k,为公式的首标。,特别地，若公式,中无量词，则,也看作是前束范式。,可见，前束范式的特点是，所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式之末。,例如，(,x,)(,y,)(,z,)(,P,(,x,y,),Q,(,y,z,),R,(,x,y,)等都是前束范式，而(,x,),P,(,x,),(,y,),Q,(,y,)，(,x,)(,P,(,x,),(,y,),Q,(,x,y,)不是前束范式。,定理2.6.1,(前束范式存在定理),Lp中任意公式,A,都有与之等价的前束范式。,证明,利用量词转化公式，将否定深入到个体变元和谓词填式之前，其次利用：,(,x,)(,A,B,(,x,),A,(,x,),B,(,x,),(,x,)(,A,B,(,x,),A,(,x,),B,(,x,),把量词移到全式的前面，这样便得前束范式。,例,把公式(,x,),P,(,x,),(,x,),Q,(,x,)化为前束范式。,解,原式,(,x,),P,(,x,),(,x,),Q,(,x,),(,x,),(,P,(,x,),Q,(,x,).,例,把公式,(,x,),(,y,),A,(,x,y,),(,x,),(,y,),B,(,x,y,),(,y,)(,A,(,y,x,),B,(,x,y,)化为前束范式。,解,原式,(,x,),(,y,),A,(,x,y,),(,x,),(,y,),B,(,x,y,),(,y,)(,A,(,y,x,),B,(,x,y,),(,x,),(,y,),A,(,x,y,),(,x,),(,y,),B,(,x,y,),(,y,),(,A,(,y,x,),B,(,x,y,)(,否定深入,),(,x,),(,y,),A,(,x,y,),(,u,),(,w,),B,(,u,w,),(,z,),(,A,(,z,u,),B,(,u,z,),(,x,),(,y,),(,u,),(,w,),(,z,),A,(,x,y,),B,(,u,w,),(,A,(,z,u,),B,(,u,z,).,定义2.6.2,一个 谓词公式,A,若具有如下形式称为,前束合取范式。,(,x,1,)(,x,2,)(,x,k,)(,A,11,A,12,A,1k1,),(,A,21,A,22,A,1k2,),(,A,m1,A,m2,A,1km,),其中,为量词,或,x,i,是个体变元，,A,ij,是,原子公式或其否定。,定义2.6.2,一个 谓词公式,A,若具有如下形式称为,前束析取范式。,(,x,1,)(,x,2,)(,x,k,)(,A,11,A,12,A,1k1,),(,A,21,A,22,A,1k2,),(,A,m1,A,m2,A,1km,)。,定理2.6.1,Lp中任意公式,A,都可以转化为与之等价的前束合取(析取)范式。,例,求(,x,),(,y,),P,(,x,),(,z,),Q,(,z,y,),(,y,),R,(,x,y,)的,前束合取范式。,解,(i)消除多余的量词,原式,(,x,),P,(,x,),(,z,),Q,(,z,y,),(,y,),R,(,x,y,),(ii)换名,原式,(,x,),P,(,x,),(,z,),Q,(,z,y,),(,w,),R,(,x,w,),(iii)消去条件联结词,原式,(,x,),(,P,(,x,),(,z,),Q,(,z,y,),(,w,),R,(,x,w,),(iv)否定深入,原式,(,x,),(,P,(,x,),(,z,),Q,(,z,y,),(,w,),R,(,x,w,),(v)量词提前,原式,(,x,)(,z,)(,w,)(,P,(,x,),Q,(,z,y,),R,(,x,w,),(,x,)(,z,)(,w,)(,P,(,x,),R,(,x,w,),(,Q,(,z,y,),R,(,x,w,).,.斯柯林范式,前束范式的的优点是全部量词集中在公式前面，其缺点是各量词的排列无一定规则，这样当把一个公式化归为前束范式时，其表达形式会显现多种情形，不便应用。1920年斯柯林(,Skolem,)提出对前束范式首标中量词出现的次序给出规定：每个存在量词均在全称量词之前。按此规定得到的范式形式，称为斯柯林范式。显然，任一公式均可化为斯柯林范式。它的优点是：全公式按顺序可分为三部分，公式的所有存在量词、所有全称量词和辖域。这给Lp的研究提供了一定的方便。,2.7 谓词逻辑的推理理论,Lp是Ls的进一步深化和发展，因此Ls的推理理论在Lp中几乎可以完全照搬，只不过这时涉及的公式是Lp的公式罢了。在Lp中，某些前提和结论可能受到量词的约束，为确立前提和结论之间的内部联系，有必要消去量词和添加量词，因此,正确理解和运用有关量词规则,是Lp推理理论中十分重要的关键所在。,下面在介绍有关量词规则之前做些必要准备。作为定义2.3.3的一种特例，将给出,A,(,x,)对,y,是自由的这个概念。其目的是，允许用,y,代入,x,后得到,A,(,y,)，它不改变原来公式,A,(,x,)的约束关系。,定义2.7.1,在谓词公式,A,(,x,)中，若,x,不自由出现在量词(,y,)或(,y,)的辖域，则称,A,(,x,)对于,y,是自由的。,由定义可知，若,y,在,A,(,x,)中不是约束出现，则,A,(,x,)对于,y,一定是自由的。,.有关量词消去和产生规则,(1)全称量词消去规则(简称,UI,或,US,规则,),(i)(,x,),P,(,x,),P,(,c,),其中,c,为任意个体常元.,(ii)(,x,),P,(,x,),P,(,y,),P,(,x,)对,y,是自由的.,例,：,P,(,x,):,x,总是要死的；,(,x,),P,(,x,)：所有人总是要死的；,有结论：,P,(,c,):苏格拉底总会死的。,(2)全称量词产生规则(简称,UG,规则,),P,(,x,),(,x,),P,(,x,),这个规则是要把命题量化。如能证明对论域中的每个个体c断言,P,(,c,),都成,立,则可得到结论(,x,),P,(,x,)成立。,在应用本规则时，必须证明,P,(,x,)对论域中的所有可能的,x,均为真。,(3)存在量词消去规则(简称,EI,或,ES,规则,),(,x,),P,(,x,),P,(,c,),其中,c,为特定个体常元,这里,c,是论域中的某些个体，但须注意这里的个体,c,不是任意指定的。,例如：,(,x,),P,(,x,)和(,x,),Q,(,x,)都为真，则对论域中的某些,c,和,d,可以断定,P,(,c,),Q,(,d,),为真，但不能断定,P,(,c,),Q,(,c,),为真。,(4)存在量词产生规则(简称,EG,规则,),P,(,c,),(,x,),P,(,x,),其中,c,为特定个体常元.,Lp中推理实例,