《第四章 谓词逻辑及演算.ppt》由会员分享，可在线阅读，更多相关《第四章 谓词逻辑及演算.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 第四章 谓词逻辑及演算 4.1 谓词与个体 4.2 量词 4.3 函词（函数）4.4 自由变元与约束变元 习题及参考答案12/21/202214.1 谓词与个体 我们知道，命题演算的基本研究单位是原子命题，在命题演算中，原子命题是不能再分割的了。这对研究命题间的关系是比较合适的。但是，在进一步研究时就会发现，仅仅命题演算对我们是很不够的并且也不充分，比如：三段论在命题演算系统中是无法完成的。例如例如：所有的科学是有用的。数理逻辑是科学。所以，数理逻辑是有用的。又例如例如：凡人必死。张三是人 故张三必死。12/21/20222 上述两个例子的主要原因就是在于这种推理中需要对原子命题作进一步分解
2、，在上述两个例子中，每个例子三个命题间，具有必然的内在逻辑关系，只有对这种内存逻辑联系深入研究后，才能解决形式逻辑中的一些推理问题。谓词演算正是为了这样的目的，换言之也就是对原子命题进行进一步的分解。在谓词演算中，将原子命题分解为谓词与个体两部分，在上例中，“数理逻辑是科学”即主语“数理逻辑”与谓语“是科学”，“张三是人”中的“张三”是主语，“是人”为谓语。换言之在数理逻辑中将主语称为个体，将谓语称为谓词。所谓个体既是可以独立存在的物体。它可以是抽象的，也可以是具体的，如：鲜花代表团，自行车，自然数，唯物主义等等都是个体。谓词是用来刻划个体的性质或关系。如“3整除6”这里3与6是个体，关系“整
3、除”是谓词。一个谓词可以与某个个体相联，此种谓词称为一元谓词。上例中张三，3，6等也可以是抽象的，比如x，y。由个体组成的集合称为个体域（或论述域），以某个个体域I为变域的变元叫做个体变元。12/21/20223 一个单独的谓词是没有含义的，如：“是大学生“，这个谓词必须跟随一定数量的个体后才有明确的含义，最重要的是能分别其真假。个体谓词中的次序有时也是很重要的，如“上海位于南京与杭州之间”，此命题为真，其中“上海”、“南京”、“杭州”三个个体间次序不能随便颠倒，如果写成“杭州位于南京和上海之间”，则此时命为假。所以，由谓词以及跟随它的若干个有一定次序的个体便可构成一个完整的命题。下面我们一般
4、用大写拉丁字母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个个体变元才有意义，我们把谓词后填以个体称为谓词填式。有了谓词的概念后我们可以将一些日常用语及命题更深刻地刻划出来，下面我们以几个例子说明：12/21/20224 例1：王强是大学生李华也是大学生。解：F表示大学生，F（x）表示x是大学生。a表示“王强”，b表示“李华”，则此式可表示为：F（
5、a）F（b）例2：我国领导人访问美国。解：F（x，y）表示x访问y，a表示我国领导人，b表示美国，则此式可表示为：F（a，b）12/21/20225 例例3：这座大楼建成了。解解：F（x）表示“x建成了”，G（x）表示“x是大的”，H（x）表示“x是大楼”，则此式可表示为：F F（a a）G G（a a）H H（a a）例例4：这个人正在看那本红皮面的书。解解：F（x，y）表示“x正在看y”，G（x）表 示“x是人”，H（y）表示“y是红皮面的”，U（y）表示“y是书”，a表示“这个”，b表示“那 本”，则此式可表示为：F F（a a，b b）G G（a a）H H（b b）U U（b b）1
6、2/21/20226 一般地讲，对日常的语句，我们可给出一个大体的准则，根据这些准则可写出其逻辑表达式来。名词：专用名词（如王强，美国等）为个体 用名词（如楼房，人等）一般可为谓词 代名词：人称代词（如：你，我，他），指示代词（如这个，那个）为个体。不定代词（如任何，每个，有些，一些等）为量词。形容词：一般为谓词 数词：一般为量词 动词：一般为谓词 副词：与所修饰的动词合并为一谓词，不在分解。前置词：与其它有关字合并为一，本身不独立表示。连接词：一般为命题联结词。以上准则只供参考，在具体应用时常常也有许多例外。12/21/20227 4.2量词 在数学上或日常生活中经常碰到“对一切”、“所有的
7、”、“存在一个”、“至少有一个“等的概念。我们以上学过的方法与技巧是无法表达清楚的，一个谓词演算中的表达不一定是确定的，个体域中不同而个体代入后可得到不同的真假值。如我们考察下面两个式子（它们均以整数作为其个体域）：（1）（X+1）2=X2+2X+1 （2）X+6=5 对于（1）我们发现任何整数代入后等式总是正确，但是对 （2）分析则不然，它只存在一个整数即（-1）代入后使得等式 成立。又如：“q或者大于0，或者等于0，或者小于0”，当然 该句可写成：q0q=0q0a=0a（x x，0 0），），=（x x，0 0），），（x x，0 0）=（x x，0 0）yzy）。该式中的约束变元x不能改
8、名y（y是作用域中的约束变元），但可改名为z（z也是作用域中的约束变元），因为该公式 x x（x20 y x20 y（x=yx=yz z（zyzy）的意思是“对于任何个体，其平方必0，并且对于任何新个体，原个体都于新个体相等，并且存在一个个体，它大于该新个体”。而改名为y后的结果式为：y y（y20 yy20 y（y=yy=y z z（zy)zy)12/21/202227 其意思是“对于任何个体，其平方必0，并且对于任何新个体，新个体必与自己相等并且存在一个个体，它大于该新个体”，显然它们的意思不相同，从约束关系看，结果式的约束关系显然与原来的约束关系不相同，但是：z（z20 y（z=y z（
9、z=y）意思与原式相同，从约束关系看，结果式的约束关系与原式一样。例如例如：上面这个例子中，如果将原式的约束变元y改名为其它变元，如改名为t，再将约束变元x改名为y结果式为：y（y20 t（y=t x（z t）显然与原来的约束关系完全相同，所以说这是正确的改名。是否不改变原约束关系的改名都是正确的改名呢？确实如此。12/21/202228 总之改名规则用更加简单的途述为：（1 1）改名时需要更改的变元符号范围是量词中的变元以及该量词辖域中此变元所有约束出现处，而在公式之其余部分不变。（2 2）改名时所更改的符号一定不能出现在量词的辖域内。12/21/202229 接下来我们在讨论代入问题。第一
10、第一.代入是对自由变元而言，也就是说对自由变元可施行代入。第二第二.特别注意代入是有条件的，不能盲目代入，不则将发生错误。12/21/202230 例如例如：x x（x=x=y y z z）该公式中的自由变元y可以代以2,z,y+z,sint等因为代入后的结果式 x x（x=2x=2 z z）,x x（x=z x=z z z）,x,x（x=(y+z)x=(y+z)z z）,x x（x=(x=(sint)sint)z z）均是原式的特例,也就是说约束变原没有变化,所以是正确的。又例如:x(x=:x(x=y.zy.z)由自由变元y代以x或者代以含x的式子就错了，如，自由变元y决不能代以x，假如x+
11、t，sinx等等，代如后的结果式为：x(x=x(x=x xz z)，x(x=x(x=（x+tx+t）z)z)，x(x=x(x=（sinxsinx）z)z)均不是原式的特例，也就是说这时的约束关系与原式不同。12/21/202231 再例如：如果一定要代以x或代以含x的项，则必须先把原式中的约束变元改名，使得与代入项无关，比如将上式改为u，而后施行代入，这时结果式为：u u（u=u=x xz z），），u u（u=u=（x+tx+t）z z），），u u（u=u=（sinxsinx）z z）显然这是原式的特例，约束关系与原式一致。第三.代入必须“处处”进行。所谓“处处”进行是指当对某由自由变元施
12、行代入时，必须对该公式中该变元的一切自由出现均施行代入，否则将是错误的。12/21/202232 第四.为了确保对自由个体变元的正确代入，我们规定，代入前先对原式施行改名，使得原式中所有约束变元名代入式中所有变元名互不相同，然后再施行代入。第五.对于命题变元和谓词变元也可施行代入，而且代入也就是有条件的，其条件仍就是代入前后约束关系必须保持不变。下面我们举例说明对命题变元和谓词变元的代入。12/21/202233 例例一.试在 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。解解
13、：因为对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）这个结果显然是原式的特例，故代入正确。12/21/202234 经过分析为了确保对命题变元的代入正确我们规定，代入前先对原式施行改名，然后施行代入，显然，按此规定施行代入，结果一定正确。而且一切正确的关与命题变元的代入均可按此规定得到。谓词变元的代入比较复杂
14、，因为在公式中为此变元均是以谓词填式的形式出现，因此在代入前应先将代入的谓词变成相应的填式，然后在把代入好的填式代到原式中去，因此要使个代入正确，必须保证二次代入均正确，即二次代入过程中的约束关系均不应发生变化，我们举例说明这一过程。12/21/202235 例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是约束变元，所以若盲目代入的话，必须发生变元混乱，产生错误。为此必须先对原式及代入式进行改名，使之相互间的变元均不同名，然后施行代
15、入。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)同理,为了确保对谓词变元的代入正确,我们仍然规定同命题变元的代入规定类同.12/21/202236 习题及参考答案 一.将下列句子用谓词填式表示 1.11.1小赵是优秀学生且书是红的。解解：设A表示“是优秀学生”，i表示小赵，则“小赵是优秀学生”表示为A（i
16、），又若以B表示谓词“是红的”，j表示书，则“书是红的”表示为B（j）所以“小赵是优秀学生且书是红的”整个句子表示为A A（i i）B B（j j）1.21.2张三高于李四,则张三高于王五。解解：用A 表示“高于”a表示“张三”，b表示“李四”，c表示“王五”，则语句表示为 A A（a a，b b）A A（a a，c c）12/21/202237 二.将下列句子写成谓词公式 2.12.1小张学习很好工作也很好。解解：用S（x）表示“x学习很好”W（x）表示“工作很好”x表示“小张”则该语句表示为：S S（x x）W W（x x）2.22.2小李学习不很好但工作很好。解解：用S（x）表示“x学习
17、很好”W（x）表示“工作很好”x表示“小李”则该语句表示为：S S（x x）W W（x x）2.32.3小王如果学习很好工作也很好。解解：用S（x）表示“x学习很好”W（x）表示“工作很好”x表示“小张”则该语句表示为：S S（x x）W W（x x）12/21/202238 三.将下列谓词译成句子.3.13.1用H(x,y)表示“x比y长得高”。设L表示李四，c表 示张三。解解：H H（l l，c c）表示“李四不比张三长得高”，H H（l l，c c）H H（c c，l l）表示“李四不比张三长得高”且 “张三与李四同样高”3.23.2（P P（x x，y y）P P（y y，z z）P
18、P（x x，z z）若P（x，y）解释为“若x小于y”，当x，y，z都在实数域中取值，则这个式子表示为“x x小于小于y y且且y y小于小于z z，则，则x x小于小于z”。这是永真公式。如果P（x，y）解释为“x为y的儿子”，当x，y，z都指人，则“若若x x为为y y的儿子且的儿子且y y是是z z的儿子则的儿子则x x是是z z的儿子的儿子”。这个公式表达的是一个永假公式。如果P（x，y）解释为“x距离y10米”，若x，y，z表示地面上的房子，那么“x距离y10米且y距离z10米则x距离z10米”。这个命题真值将由x，y，z的具体位置而定，它可能为T，也可能为F。12/21/20223
19、9 四.1 1.在某一高级语言程序设计中一维数组使用量词表示array A1：50中每一个项均不为零。解解：x x（I(x)(xI(x)(x，1)(x1)(x，50)50)（A(xA(x)，0 0）2 2.使用量词表示：对于所有自然数x，y均有x+yx。解解：可表示为：x yx y（N(xN(x)（N(y)FN(y)F（x x，y y）12/21/202240 3 3.使用量词表示：某些人对某些食物过敏。解解：设F（x，y）为“x对y过敏”M(x)是特性谓词表示“x是人”，G(y)也是特性谓词表示“y是食物”，此语句可译为：x xy y（M(xM(x)（G(y)FG(y)F（x x，y y）4
20、 4.将高等数学中极限的定义limf（x）=k用谓词演算中表达式刻划。解解：我们知道上述极限定义是：任给 0,必存在一个 0,对所有x如果x xcc则必有f(xf(x)k k 我们设R(x)表示x是实数,则此极限定义可译为:(R(R()(0,x)(0,x)(R(R(0,)0,)x(R(x)(xx(R(x)(xc,)(c,)(f(xf(x)k,k,)12/21/202241 五.指出下列公式中的自由变元，约束变元及约束关系 1 1.x x（x=x=y+xy+x）yxyx 解解：x为约束变元，y为自由变元 约束关系为若x=y+x则必推出yx 2 2.（x=xx=x）（xyxy）（x x（x=xx=
21、x）x x（xyxy）解解：这里自由变元x即为自由变元也为约束变元，y为自由变元，约束关系如果对于所有。x=x则必等价于xy（这是在两个前提，x=x及xy的条件下）3 3.x x y(xy(x=y)=y)x(x(y(xy(x=y)(xy)=y)(xy)x(xx(xy)y)解解：与上同理故略12/21/202242 六.指出下列公式中各量词不能改用什么变元作指导变元,并对各是实行改名.1 1.x(X(xx(X(x)Y(x,tY(x,t)Y(X(yY(X(y)Y(x,yY(x,y)解：解：2.x2.xyX(x,y,tyX(x,y,t)y x)y x X(x,y,tX(x,y,t)3.x(3.x(y(t y(t X(x,tX(x,t)X(y,tX(y,t)X(x,yX(x,y)12/21/202243 七.试对下列公式施行代入 1.在x=y2+3y(yx)中,把x代以(a)y,(b)y+x2 2.在 y z(x(X(y,z)(PY(x,y)(pX(y,z)中 (b)P代以 y(X(y,z)X(e1,e2)代以,z(X(e1,z)Y(e1,e2)(c)P代以X(y,z),X(e1,e2)代以Y(e1,z)yX(y,e2)12/21/202244