第四章 谓词逻辑及演算

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第四章 谓词逻辑及演算,4.1 谓词与个体,4.2 量词,4.3 函词（函数）,4.4 自由变元与约束变元,习题及参考答案,袍腮赖己索臼抄较扳扮掏奴卫氛拜滑矽晕景睁肇戌僧伞兵锡托唯逞定辩海第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,1,4.1 谓词与个体,我们知道，命题演算的基本研究单位是,原子命题,，在命题演算中，原子命题是不能再分割的了。这对研究命题间的关系是比较合适的。但是，在进一步研究时就会发现，仅仅命题演算对我们是很不够的并且也不充分，比如：三段论在命题演算系统中是无法完成的。,例如,：所有的科学是有用的。,数理逻辑是科学。,所以，数理逻辑是有用的。,又,例如,：凡人必死。,张三是人,故张三必死。,煞谁癸碉惟鞋赎密吮抹蛹抗奉匡醉映介撑滦铣削杠塑谰庇框贡德胰涨两仰第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,2,上述两个例子的主要原因就是在于这种推理中,需要对原子命题作进一步分解,，在上述两个例子中，每个例子三个命题间，具有必然的内在逻辑关系，只有对这种内存逻辑联系深入研究后，才能解决形式逻辑中的一些推理问题。谓词演算正是为了这样的目的，,换言之也就是对原子命题进行进一步的分解。,在谓词演算中，将原子命题分解为谓词与个体两部分，在上例中，“数理逻辑是科学”即,主语“数理逻辑”与谓语“是科学”,，“张三是人”中的,“张三”是主语，“是人”为谓语,。换言之,在数理逻辑中将主语称为个体，将谓语称为谓词。,所谓个体既是可以独立存在的物体。它可以是抽象的，也可以是具体的，如：鲜花代表团，自行车，自然数，唯物主义等等都是个体。谓词是用来刻划个体的性质或关系。如“,3整除6”,这里,3与6是个体，关系“整除”是谓词。,一个谓词可以与某个个体相联，此种谓词称为一元谓词。上例中张三，3，6等也可以是抽象的，比如x，y。由个体组成的集合称为个体域（或论述域），以某个个体域I为变域的变元叫做个体变元。,岗硝拴侗坷畸茬圃括刑垄职社钮颇臀尘括倚声径迈颖华哑琢哪脸售壶片娶第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,3,一个单独的谓词是没有含义的，如：,“,是大学生,“,，这个谓词必须跟随一定数量的个体后才有明确的含义，最重要的是能分别其,真假,。个体谓词中的,次序,有时也是很重要的，如,“,上海位于南京与杭州之间,”,，此命题为真，其中,“,上海,”,、,“,南京,”,、,“,杭州,”,三个个体间次序不能随便颠倒,，如果写成,“,杭州位于南京和上海之间,”,，则此时命为,假,。所以，由谓词以及跟随它的若干个有一定次序的个体便可构成一个完整的命题。,下面我们一般用大写拉丁字母A，B,E表示谓词，用小写拉丁字母a，b，c,z表示个体（或叫个体变元），这样x，y间具有关系B可记作B（x，y），x，y，z具有关系C，记作C（x，y，z），上述是二元谓词和三元谓词，当然也可以表示为n元谓词就是有n个个体变元的谓词，并约定0元谓词是命题。并记为P，Q，R。,n元谓词当然需要赋于n个个体变元才有意义，我们把谓词后填以,个体称为谓词填式,。,有了谓词的概念后我们可以将一些日常用语及命题更深刻地刻划出来，下面我们以几个例子说明：,庆予轿琐埋撤脓凰率钒颗走叶练光扛忍绩谎蚊栓暂淮守巾芦运瘸斜营蔡淑第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,4,例1：王强是大学生李华也是大学生。,解：F表示大学生，F（x）表示x是大学生。,a表示,“,王强,”,，b表示,“,李华,”,，则此式可表示为：,F（a）F（b）,例2：我国领导人访问美国。,解：F（x，y）表示x访问y，a表示我国领导人，b表示美国，则此式可表示为：,F（a，b）,吗权未耳曙陆吕肋起尤购及勋含蛇挤蜡肥侵循恃漏捉臀蔚糯聘牟乃馆栅件第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/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）,亩跃饵楚拌武卸费筷救氮石绳袁汲粉杆歧廊缄涤胳渺炯哄喊术胰歧税产薯第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,6,一般地讲，对日常的语句，我们可给出一个大体的准则，根据这些准则可写出其逻辑表达式来。,名词：专用名词（如王强，美国等）为个体,用名词（如楼房，人等）一般可为谓词,代名词：人称代词（如：你，我，他），指示代词（如这个，那个）为个体。,不定代词（如任何，每个，有些，一些等）为量词。,形容词：一般为谓词,数词：一般为量词,动词：一般为谓词,副词：与所修饰的动词合并为一谓词，不在分解。,前置词：与其它有关字合并为一，本身不独立表示。,连接词：一般为命题联结词。,以上准则只供参考，在具体应用时常常也有许多例外。,骗哪噬贷仑回域曙绍邑眨纸钳愤桶捅移孤箕绅杉台然赔仇徘川以反闲股辜第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,7,4.2量词,在数学上或日常生活中经常碰到,“,对一切,”,、,“,所有的,”,、,“,存在一个,”,、,“,至少有一个,“,等的概念。我们以上学过的方法与技巧是无法表达清楚的，一个谓词演算中的表达不一定是确定的，个体域中不同而个体代入后可得到不同的真假值。如我们考察下面两个式子（它们均以整数作为其个体域）：,（1）（X+1）2=X2+2X+1,（2）X+6=5,对于（1）我们发现任何整数代入后等式总是正确，但是对,（2）分析则不然，它只存在一个整数即（-1）代入后使得等式,成立。,又如：,“,q或者大于0，或者等于0，或者小于0,”,，当然,该句可写成：q0q=0q0a=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),涣巩因乖竞十裙铀咏脂读封人躲确烂穆铰疏硷陨沿沼侣户凉溅苞对牌逃窄第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,27,其意思是,“,对于任何个体，其平方必0，并且对于任何新个体，新个体必与自己相等并且存在一个个体，它大于该新个体,”,，,显然它们的意思不相同,，从约束关系看，结果式的约束关系显然与原来的约束关系不相同，但是：z（z20 y（z=y z（z=y）,意思与原式相同,，从约束关系看，结果式的约束关系与原式一样。,例如,：上面这个例子中，如果将原式的约束变元y改名为其它变元，如改名为t，再将约束变元x改名为y结果式为：,y（y20 t（y=t x（z t）显然与原来,的约束关系完全相同,，所以说这是正确的改名。,是否不改变原约束关系的,改名都是正确的改名呢？,确实如此。,壹晒杂檄赚告呢围阻烙挟八狡番棍的勉洼映凌唤旱鸦磷纤况灯戒翰匝睫缨第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,28,总之改名规则用更加简单的途述为：,（,1,）改名时需要更改的变元符号范围是量词中的变元以及该量词辖域中此变元所有约束出现处，而在公式之其余部分不变。,（,2,）改名时所更改的符号一定不能出现在量词的辖域内。,钻轨椰鹅据剐翼圈舟疥牡供竣俱圾儡来福避踢毁葡俄烟球其将脐钳里翁娜第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,29,接下来我们在讨论代入问题。,第一,.,代入是对自由变元而言,，也就是说对自由变元可施行代入。,第二,.特别注意代入是有条件的，不能盲目代入，不则将发生错误。,岗尺亲翱赞镊淑照饿辞俱冀适留隔皂箔河瘫摇逊羞溶达格署将惭检隘惮储第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,30,例如,：,x（x=y,z）,该公式中的自由变元y可以代以,2,z,y+z,sint,等因为代入后的结果式,x（x=2,z）,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=x,z)，x(x=（x+t）,z)，,x(x=（sinx）,z),均不是原式的特例，也就是说这时的约束关系与原式不同。,歪岩们瑶鲍片榆刷节肆抚蔓崇各躲忆奠征县届斑蟹坯舌逮岩凌相阁伶拂芽第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,31,再例如：如果一定要代以x或代以含x的项，则必须先把原式中的约束变元改名，使得与代入项无关，,比如将上式改为u，而后施行代入，这时结果式为,：,u（u=x,z），u（u=（x+t）,z），,u（u=（sinx）,z）,显然这是原式的特例，,约束关系与原式一致。,第三,.,代入必须,“,处处,”,进行,。所谓,“,处处,”,进行是指当对某由自由变元施行代入时，必须对该公式中该变元的一切自由出现均施行代入，否则将是错误的。,桂专涕规后秸憾蜡丛邪永荒肮条第醛淹般赵掷惟褐蓝俐禄溶脆刘欺彩怖寝第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,32,第四,.为了确保对自由个体变元的正确代入，我们规定，代入前先对原式施行改名，使得原式中所有约束变元名代入式中所有变元名互不相同，然后再施行代入。,第五.,对于命题变元和谓词变元也可施行代入，而且代入也就是有条件的，,其条件仍就是代入前后约束关系必须保持不变,。下面我们举例说明对命题变元和谓词变元的代入。,悍完搞怪仆离层株毅榴坐桩鲍稻靡簧泌疾蜜乡菠草哼旭驶锹渔屎鹤潍器偿第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/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）,这个结果显然是原式的特例，故代入正确。,伏惶黎欢蔗销粤用换沙征盆证睁疫樊眨两韭脉琢来浙决膛谢祸椿劣拿涯竞第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,34,经过分析为了确保对命题变元的代入正确我们规定，代入前先对原式施行改名，然后施行代入，显然，按此规定施行代入，结果一定正确。而且一切正确的关与命题变元的代入均可按此规定得到。,谓词变元的代入比较复杂,，因为在公式中为此变元均是以谓词填式的形式出现，因此在代入前应先将代入的谓词变成相应的填式，然后在把代入好的填式代到原式中去，因此要使个代入正确，必须保证二次代入均正确，即二次代入过程中的约束关系均不应发生变化，我们举例说明这一过程。,霓棒宰傍彦钢美懈剩竿阳窑园翌穴弛庄袒颂艾旷略逃溪坦遂遏邻宵租瘫崇第四章 谓词逻辑及演算第四章 谓词逻辑及演算,10/3/2024,35,例2.试在 x（x（x，y）y（x）yX（t，y）中