谓词逻辑及演算

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第四章 谓词逻辑及演算,4.1 谓词与个体,4.2 量词,4.3 函词（函数）,4.4 自由变元与约束变元,习题及参考答案,11/27/2024,1,4.1,谓词与个体,我们知道，命题演算的基本研究单位是,原子命题,，在命题演算中，原子命题是不能再分割的了。这对研究命题间的关系是比较合适的。但是，在进一步研究时就会发现，仅仅命题演算对我们是很不够的并且也不充分，比如：三段论在命题演算系统中是无法完成的。,例如,：所有的科学是有用的。,数理逻辑是科学。,所以，数理逻辑是有用的。,又,例如,：凡人必死。,张三是人,故张三必死。,11/27/2024,2,上述两个例子的主要原因就是在于这种推理中,需要对原子命题作进一步分解,，在上述两个例子中，每个例子三个命题间，具有必然的内在逻辑关系，只有对这种内存逻辑联系深入研究后，才能解决形式逻辑中的一些推理问题。谓词演算正是为了这样的目的，,换言之也就是对原子命题进行进一步的分解。,在谓词演算中，将原子命题分解为谓词与个体两部分，在上例中，“数理逻辑是科学”即,主语“数理逻辑”与谓语“是科学”,，“张三是人”中的,“张三”是主语，“是人”为谓语,。换言之,在数理逻辑中将主语称为个体，将谓语称为谓词。,所谓个体既是可以独立存在的物体。它可以是抽象的，也可以是具体的，如：鲜花代表团，自行车，自然数，唯物主义等等都是个体。谓词是用来刻划个体的性质或关系。如“,3整除6”,这里,3与6是个体，关系“整除”是谓词。,一个谓词可以与某个个体相联，此种谓词称为一元谓词。上例中张三，3，6等也可以是抽象的，比如x，y。由个体组成的集合称为个体域（或论述域），以某个个体域I为变域的变元叫做个体变元。,11/27/2024,3,一个单独的谓词是没有含义的，如：“是大学生“,，这个谓词必须跟随一定数量的个体后才有明确的含义，最重要的是能分别其,真假,。个体谓词中的,次序,有时也是很重要的，如“上海位于南京与杭州之间”，此命题为真，其中“上海”、“南京”、“杭州”,三个个体间次序不能随便颠倒,，如果写成“杭州位于南京和上海之间”，则此时命为,假,。所以，由谓词以及跟随它的若干个有一定次序的个体便可构成一个完整的命题。,下面我们一般用大写拉丁字母A，BE表示谓词，用小写拉丁字母a，b，cz表示个体（或叫个体变元），这样x，y间具有关系B可记作B（x，y），x，y，z具有关系C，记作C（x，y，z），上述是二元谓词和三元谓词，当然也可以表示为n元谓词就是有n个个体变元的谓词，并约定0元谓词是命题。并记为P，Q，R。,n元谓词当然需要赋于n个个体变元才有意义，我们把谓词后填以,个体称为谓词填式,。,有了谓词的概念后我们可以将一些日常用语及命题更深刻地刻划出来，下面我们以几个例子说明：,11/27/2024,4,例1：王强是大学生李华也是大学生。,解：F表示大学生，F（x）表示x是大学生。,a表示“王强”，b表示“李华”，则此式可表示为：,F（a）F（b）,例2：我国领导人访问美国。,解：F（x，y）表示x访问y，a表示我国领导人，b表示美国，则此式可表示为：,F（a，b）,11/27/2024,5,例,3：这座大楼建成了。,解,：F（x）表示“x建成了”，G（x）表示“x是大的”，H（x）表示“x是大楼”，则此式可表示为：,F（a）G（a）H（a）,例,4：这个人正在看那本红皮面的书。,解,：F（x，y）表示“x正在看y”，G（x）表 示“x是人”，H（y）表示“y是红皮面的”，U（y）表示“y是书”，a表示“这个”，b表示“那 本”，则此式可表示为：,F（a，b）G（a）H（b）U（b）,11/27/2024,6,一般地讲，对日常的语句，我们可给出一个大体的准则，根据这些准则可写出其逻辑表达式来。,名词：专用名词（如王强，美国等）为个体,用名词（如楼房，人等）一般可为谓词,代名词：人称代词（如：你，我，他），指示代词（如这个，那个）为个体。,不定代词（如任何，每个，有些，一些等）为量词。,形容词：一般为谓词,数词：一般为量词,动词：一般为谓词,副词：与所修饰的动词合并为一谓词，不在分解。,前置词：与其它有关字合并为一，本身不独立表示。,连接词：一般为命题联结词。,以上准则只供参考，在具体应用时常常也有许多例外。,11/27/2024,7,4.2,量词,在数学上或日常生活中经常碰到“,对一切,”、“,所有的,”、“存在一个”、“至少有一个“等的概念。我们以上学过的方法与技巧是无法表达清楚的，一个谓词演算中的表达不一定是确定的，个体域中不同而个体代入后可得到不同的真假值。如我们考察下面两个式子（它们均以整数作为其个体域）：,（,1,）（,X+1,）,2=X2+2X+1,（,2,）,X+6=5,对于（,1,）我们发现任何整数代入后等式总是正确，但是对,（,2,）分析则不然，它只存在一个整数即（,-1,）代入后使得等式,成立。,又如：“,q,或者大于,0,，或者等于,0,，或者小于,0”,，当然,该句可写成：,q,0q=,0q,0a=,0a,（x，0），=（x，0），（x，0）=（x，0）y）,。,该式中的约束变元,x,不能改名,y,（y是作用域中的约束变元），但可改名为z（z也是作用域中的约束变元），因为该公式,x（x20 y（x=yz（zy）,的意思是“,对于任何个体，其平方必0，并且对于任何新个体，原个体都于新个体相等，并且存在一个个体，它大于该新个体,”。而改名为y后的结果式为：,y（y20 y（y=y z（zy),11/27/2024,27,其意思是“对于任何个体，其平方必0，并且对于任何新个体，新个体必与自己相等并且存在一个个体，它大于该新个体”，,显然它们的意思不相同,，从约束关系看，结果式的约束关系显然与原来的约束关系不相同，但是：z（z20 y（z=y z（z=y）,意思与原式相同,，从约束关系看，结果式的约束关系与原式一样。,例如,：上面这个例子中，如果将原式的约束变元y改名为其它变元，如改名为t，再将约束变元x改名为y结果式为：,y（y20 t（y=t x（z t）显然与原来,的约束关系完全相同,，所以说这是正确的改名。,是否不改变原约束关系的,改名都是正确的改名呢？,确实如此。,11/27/2024,28,总之改名规则用更加简单的途述为：,（,1,）改名时需要更改的变元符号范围是量词中的变元以及该量词辖域中此变元所有约束出现处，而在公式之其余部分不变。,（,2,）改名时所更改的符号一定不能出现在量词的辖域内。,11/27/2024,29,接下来我们在讨论代入问题。,第一,.,代入是对自由变元而言,，也就是说对自由变元可施行代入。,第二,.特别注意代入是有条件的，不能盲目代入，不则将发生错误。,11/27/2024,30,例如,：,x（x=yz）,该公式中的自由变元y可以代以,2,z,y+z,sint,等因为代入后的结果式,x（x=2z）,x（x=z z）,x（x=(y+z)z）,x（x=(sint)z）,均是原式的特例,也就是说约束变原没有变化,所以是正确的。,又例如,:x(x=y.z),由自由变元y代以x或者代以含x的式子就错了，如，自由变元y决不能代以x，假如x+t，sinx等等，代如后的结果式为：,x(x=xz)，x(x=（x+t）z)，,x(x=（sinx）z),均不是原式的特例，也就是说这时的约束关系与原式不同。,11/27/2024,31,再例如：如果一定要代以x或代以含x的项，则必须先把原式中的约束变元改名，使得与代入项无关，,比如将上式改为u，而后施行代入，这时结果式为,：,u（u=xz），u（u=（x+t）z），,u（u=（sinx）z）,显然这是原式的特例，,约束关系与原式一致。,第三,.,代入必须“处处”进行,。所谓“处处”进行是指当对某由自由变元施行代入时，必须对该公式中该变元的一切自由出现均施行代入，否则将是错误的。,11/27/2024,32,第四,.为了确保对自由个体变元的正确代入，我们规定，代入前先对原式施行改名，使得原式中所有约束变元名代入式中所有变元名互不相同，然后再施行代入。,第五.,对于命题变元和谓词变元也可施行代入，而且代入也就是有条件的，,其条件仍就是代入前后约束关系必须保持不变,。下面我们举例说明对命题变元和谓词变元的代入。,11/27/2024,33,例,一.试在 y（pA（y）（p xA（x）中把p代入以y B（x，y），和把p代以x B（x，y）,注意,：y B（x，y），x B（x，y）也可以写为,y B xy，x Bxy。,解,：因为对p用y B（x，y）代以后约束关系不发生变化，所以可立即施行代入得,y（y B（x，y）A（y）（y B（x，y）,x A（x）反之对于 y B（x，y）代p的情形，如盲目代入的话，约束关系就将发生变化，从而出现错误，所以必须先将原式中的约束变元y改名，使之与代入式中的变元无关，,如将y改为t得,t（x B（x，y）A（t）x A（x）,这个结果显然是原式的特例，故代入正确。,11/27/2024,34,经过分析为了确保对命题变元的代入正确我们规定，代入前先对原式施行改名，然后施行代入，显然，按此规定施行代入，结果一定正确。而且一切正确的关与命题变元的代入均可按此规定得到。,谓词变元的代入比较复杂,，因为在公式中为此变元均是以谓词填式的形式出现，因此在代入前应先将代入的谓词变成相应的填式，然后在把代入好的填式代到原式中去，因此要使个代入正确，必须保证二次代入均正确，即二次代入过程中的约束关系均不应发生变化，我们举例说明这一过程。,11/27/2024,35,例2.试在 x（x（x，y）y（x）yX（t，y）中，把x（e1，e2）代以 tA（e1，e2）x，t)。,解：因为代入式 tA（e1，e2）x，t）中x是自由变元，t是约束变元，而原式中谓词填式X（x，y）中x是约束变元，所以若盲目代入的话，必须发生变元混乱，产生错误。为此必须先对原式及代入式进行改名，使之相互间的变元均不同名，然后施行代入。,1)先把代入式改名为,uA（e1，e2，x，u）,2)再把原式改名为,z(X(z,y)Y(z)yX（t，y）,3)再作关于X(z,y)的代入式的填式,uA(z,y,x,u),4)再作关于X(t,y)的代入式的填式,uA(t,y,x,y),5)最后将这两个填式3),4)代入到原式即可,z(u A(z,y,x,y)Y(z)yu A(t,y,x,y)同理,为了确保对谓词变元的代入正确,我们仍然规定同命题变元的代入规定类同.,11/27/2024,36,习题及参考答案,一,.,将下列句子用谓词填式表示,1.1,小赵是优秀学生且书是红的。,解,：设,A,表示“是优秀学生”，,i,表示小赵，则“小赵是优秀学生”表示为,A,（,i,），又若以,B,表示谓词“是红的”，,j,表示书，则“书是红的”表示为,B,（,j,）所以“小赵是优秀学生且书是红的”整个句子表示为,A,（,i,）,B,（,j,）,1.2,张三高于李四,则张三高于王五。,解,：用,A,表示“高于”,a,表示“张三”，,b,表示“李四”，,c,表示“王五”，则语句表示为,A,（,a,，,b,）,A,（,a,，,c,）,11/27/2024,37,二,.,将下列句子写成谓词公式,2.1,小张学习很好工作也很好。,解,：用,S,（,x,）表示“,x,学习很好”,W,（,x,）表示“工,作很好”,x,表示“小张”则该语句表示为：,S,（,x,）,W,（,x,）,2.2,小李学习不很好但工作很好。,解,：用,S,（,x,）表示“,x,学习很好”,W,（,x,）表示“工,作很好”,x,表示“小李”则该语句表示为：,S,（,x,）,W,（,x,）,2.3,小王如果学习很好工作也很好。,解,：用,S,（,x,）表示“,x,学习很好”,W,（,x,）表示,“工作很好”,x,表示“小