《谓词逻辑及演算.ppt》由会员分享，可在线阅读，更多相关《谓词逻辑及演算.ppt（44页珍藏版）》请在三一办公上搜索。
1、2023/10/27,1,第四章 谓词逻辑及演算,4.1 谓词与个体 4.2 量词 4.3 函词（函数）4.4 自由变元与约束变元 习题及参考答案,2023/10/27,2,4.1 谓词与个体 我们知道，命题演算的基本研究单位是原子命题，在命题演算中，原子命题是不能再分割的了。这对研究命题间的关系是比较合适的。但是，在进一步研究时就会发现，仅仅命题演算对我们是很不够的并且也不充分，比如：三段论在命题演算系统中是无法完成的。例如：所有的科学是有用的。数理逻辑是科学。所以，数理逻辑是有用的。又例如：凡人必死。张三是人 故张三必死。,2023/10/27,3,上述两个例子的主要原因就是在于这种推理中
2、需要对原子命题作进一步分解，在上述两个例子中，每个例子三个命题间，具有必然的内在逻辑关系，只有对这种内存逻辑联系深入研究后，才能解决形式逻辑中的一些推理问题。谓词演算正是为了这样的目的，换言之也就是对原子命题进行进一步的分解。在谓词演算中，将原子命题分解为谓词与个体两部分，在上例中，“数理逻辑是科学”即主语“数理逻辑”与谓语“是科学”，“张三是人”中的“张三”是主语，“是人”为谓语。换言之在数理逻辑中将主语称为个体，将谓语称为谓词。所谓个体既是可以独立存在的物体。它可以是抽象的，也可以是具体的，如：鲜花代表团，自行车，自然数，唯物主义等等都是个体。谓词是用来刻划个体的性质或关系。如“3整除6”
3、这里3与6是个体，关系“整除”是谓词。一个谓词可以与某个个体相联，此种谓词称为一元谓词。上例中张三，3，6等也可以是抽象的，比如x，y。由个体组成的集合称为个体域（或论述域），以某个个体域I为变域的变元叫做个体变元。,2023/10/27,4,一个单独的谓词是没有含义的，如：“是大学生“，这个谓词必须跟随一定数量的个体后才有明确的含义，最重要的是能分别其真假。个体谓词中的次序有时也是很重要的，如“上海位于南京与杭州之间”，此命题为真，其中“上海”、“南京”、“杭州”三个个体间次序不能随便颠倒，如果写成“杭州位于南京和上海之间”，则此时命为假。所以，由谓词以及跟随它的若干个有一定次序的个体便可构
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个个体变元才有意义，我们把谓词后填以个体称为谓词填式。有了谓词的概念后我们可以将一些日常用语及命题更深刻地刻划出来，下面我们以几个例子说明：,2023/10/27,5,例1：王强是大学生李华也是大学生。解：F表示大学生，F（x）表示x是大学生。a表示“王强”，b
5、表示“李华”，则此式可表示为：F（a）F（b）,例2：我国领导人访问美国。解：F（x，y）表示x访问y，a表示我国领导人，b表示美国，则此式可表示为：F（a，b）,2023/10/27,6,例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）,2023/10/27,7,
6、一般地讲，对日常的语句，我们可给出一个大体的准则，根据这些准则可写出其逻辑表达式来。名词：专用名词（如王强，美国等）为个体 用名词（如楼房，人等）一般可为谓词 代名词：人称代词（如：你，我，他），指示代词（如这个，那个）为个体。不定代词（如任何，每个，有些，一些等）为量词。形容词：一般为谓词 数词：一般为量词 动词：一般为谓词 副词：与所修饰的动词合并为一谓词，不在分解。前置词：与其它有关字合并为一，本身不独立表示。连接词：一般为命题联结词。以上准则只供参考，在具体应用时常常也有许多例外。,2023/10/27,8,4.2量词 在数学上或日常生活中经常碰到“对一切”、“所有的”、“存在一个”、
7、“至少有一个“等的概念。我们以上学过的方法与技巧是无法表达清楚的，一个谓词演算中的表达不一定是确定的，个体域中不同而个体代入后可得到不同的真假值。如我们考察下面两个式子（它们均以整数作为其个体域）：（1）（X+1）2=X2+2X+1（2）X+6=5 对于（1）我们发现任何整数代入后等式总是正确，但是对（2）分析则不然，它只存在一个整数即（-1）代入后使得等式 成立。又如：“q或者大于0，或者等于0，或者小于0”，当然 该句可写成：q0q=0q0a=0a0(a表示”每一数”)这样的结果为,”每一数大于0或每一数等于0或每一数小于0,”显然这与原意不同。,2023/10/27,9,通过上述例子说明
8、：任一谓词演算与其个体间存在着一些关系。例如：1.对个体域中（所有个体）式子均为真 2.对个体域中（一些个体）式子均为真 那么如何在谓词演算中刻划谓词与个体间的关系呢？只有一个办法来引进一些新的符号，它们叫做量词。量词有两种，一种叫做全称量词，一种叫做存在量词。它的定义如下:,2023/10/27,10,定义1：凡表示“任意一个”，“一切”，“每个”，“任何”等词时，均为全称量词（全称变元）记作 x。,定义2：“某个”，“一个”，“一些”等词时均可用存在性变元翻译，记为x。凡表示确定的但目前尚未知道的或不必明白指出的个体变元称之为存在量词。,2023/10/27,11,对于个体域中所有个体x其
9、谓词F（x）均为真时，可用符号“x”表示“对所有x”此时它可以表示成如上例中，当个体域为实数时下面的表示为真，即：x（x+1）2=x2+2 x+1）符号“x”称为全称量词，它后面紧跟着括号内的式子称作全程量词的辖域。对于个体域中个体x，存在某些个体谓词（x）为真时用符号“x”表示“存在某些x”，此时表示为：x（F（x）如：x+6=5当个体域为实数时此时表示式为真：x（x+6=5）符号“x”存在变量，同理，它后面紧跟着括号内的式子称作存在量词的辖域。,2023/10/27,12,一个不确定的公式的公式只要对其所有变元均施加量词后则均为确定的了。如：x+6=5因为当x=-1时它为真（T），当x=3
10、时它为假（F）。但是当使用量词后x（x+3=5）则是确定的，因为它总是为真（T）。这个论点一般而言是正确的，但是它是有前提的，也就是所在确定的个体域条件下，一公式所有个体变元均施加量词后，它就是确定的了。,2023/10/27,13,通过例子我们发现：1.量词所确定的公式与个体域有关。2.对不同的个体域表达式可有不同的值。也就是说，各变元的变域（个体域）须做临时约定。各变元的性质（全称或存在性）须做临时约定。因此在谓词演算中，每个个体变元的个体域必需是确定的。因此可见，量词所确定的公式与个体域有关，对不同的个体域表达式的值不同。例如：x（x+6=5）中，当个体域为实数时它为T，但当个体域为自然
11、数时它为F。,2023/10/27,14,因此，在谓词演算中，每个个体变元的个体域必需是确定的。但有时为了讨论方便起见，我们干脆将谓词演算中所有个体域统一，一律用全总个体域。用了全总个体域后，对每个个体变元的变化范围用一定特性谓词去刻划。对全称量词，此特性谓词可作为蕴含前件而加入。对存在量词，此特性谓词可作为合取式的合取项加入。例如：上二式中设R（x）表示x为实数，它刻划了式中个体变元的特性故是特性谓词，此时（x+1）2=x2+2 x+1可写为：x（R（x）（x+1）2=x2+2 x+1），而x+6=5可写为：x（R（x）（x+6=5）有了量词的概念后，谓词演算表达能力就广泛的多了，它所能刻划
12、的语句也普遍，深入。,2023/10/27,15,下面我们举例说明：,例1：没有不犯错误的人 解：设F（x）为“x犯错误”其特性谓词为M（x），“表示x为人”此句可译为：（x（M（x）F（x）,例2：凡是实数不是大于零就是等于零或者小于零。解：我们将x大于零，x等于零，x小于零分别用（x，0），=（x，0），（x，0）=（x，0）（x，0）,2023/10/27,16,4.3 函词（函数）为了说明命题函词（函数）的概念，下面先举例解释命题与谓词的关系。例：H为谓词“能够到达山顶”。L表示个体名称李四。T表示个体名称老虎。C表示个体名称汽车。那么H（L），H（T），H（C）等分别表示各种不同的命
13、题，但它们都有一个共同的形式，即H（X）。当X取L，T，C时就表示了，“李四能够到达山顶”，“老虎能够到达到山顶”，“汽车能够到达山顶”。,2023/10/27,17,同理，若L（x，y）表示“x小于y”，那么L（2，3）表示了一个真命题：“2小于3”。而L（5，1）表示一个假命题：“5小于1”。又如A（x，y，z）表示一个关系“x+y=z”。则A（3，2，5）表示了真命题“3+2=5”。而A（1，2，4）表示了一个假命题“1+2=4”。总之从上述三个例子可以看到H（x），L（x，y），A（x，y，z）本身不是一个命题，只有当x，y，z等取特定的个体时，才确定了一个命题。即给出如下定义：,20
14、23/10/27,18,定义：由一个谓词及一些个体变元组成的表达式称为命题函词（函数）。根据这个定义可以看到，n元谓词是有n个个体变元函词（函数），当n=0时称为0元函词，它本身就是一个命题，记为a，b，c。通常称它为常量。故命题是n元谓词的一个特殊情况。由一个或n个简单函词（函数）以及逻辑联结词组合而成的表达式称为复合命题函词（函数）。逻辑联结词，。例如：R（x）表示“x是大学生”，如果x的讨论范围为某大学班级里的学生，则R（x）是永真式。如果x的讨论范围为某中学班级里的学生，则R（x）是永假式。,2023/10/27,19,4.4 自由变元与约束变元 在阐述自由变元与约束变元之前首先要给出
15、谓词演算公式的概念。定义：由命题变元和谓词填式利用真值联结词和量词如下作成的式子称为谓词演算公式（简称式）。（1）命题变元是公式；（2）填以个体变元的谓词变元填式是公式；（3）如果A是公式，则A也是公式；（4）如果A和B是公式，则（AB），（AB），（AB），（A B）也是公式；（5）如果A是公式，x是个体变元则 x(A),x(A）也都是公式；（6）公式仅限于此。,2023/10/27,20,定义：那么一个公式中如果其中有一部分公式形式如:x(A)或x(A)，则凡在这部分中的变元x的一切出现都叫做在此公式中的约束出现，而变元x叫做此公式中的约束变元。,例如：x（P（x）F（x）中的变元x的二次
16、出现均是约束出现。,2023/10/27,21,定义：一公式中如果其中有一部分公式内变元X 不呈约束出现，则称X在此公式中自由出现，而此变元X称此公式的自由变元。,例如：x（P（x，y）F（x）中的变元y是自由出现，所以y是自由变元。每个量词都有个辖域，除原子公式外，量词的辖域既是出现在它后面的括号内的公式。,2023/10/27,22,关于约束变元与自由变元我们在举一些例子：例1：x（P（x）yR（x，y）此公式变元x，y均为约束出现，无自由出现。例2：uP（x，z）此公式中变元x,z为自由出现。例3：x P（x）Q（x）此公式中变元x即约束出现，又自由出现。例子中，我们要作一些说明，我们认
17、为在一个公式中允许一个变元即使自由出现又为约束出现。但为了避免概念上的混肴起见，我们有时住住通过改名规则，使得一个变元在一个公式中只有一中形式出现，（即或者自由出现或者约束出现）。这样就避免了二义性。,2023/10/27,23,一个公式的约束变元的符号是无关紧要的，如公式 x P（x）中如将约束变元x改为y，则公式 yP（y）与公式 x P（x）具有相同的意义。所以一公式中约束变元是可以更改的，但是在更改时必须要遵守一定的规则，即约束变元的改名规则。第一.改名是对约束变元而言，不是对自由变元而言，也就是说可以对约束变施行改名，不能对自由变元施行改名。,为什么呢？,2023/10/27,24,
18、我们举例说明：例如：x（x=yxy）该式中的约束变元X可以改名为u，v，w等结果为：u（u=yuy），v（v=yvy），w（w=ywy）等。显然经过改名后的这些式子与原式意义相同，都表示“任何个体都或者等于y或者不等于y”。若将原式的自由变元改名为z这时所得到的式子就与原式的意义不同了。,2023/10/27,25,第二改名必须“处处”进行。“处处”进行的含义是当对公式中受某个量词约束出现均改名时，必须对原式中该变元的一切受该量词约束来出现均改名，否则改名后将改变原式的约束关系，即：改变了原式的意义。例如：将 x（x=yxy）中x的第一第二出现改为u第三出现不改则有：u（u=yxy）。其意思是
19、“任何个体u都或者等于y或者x不等于y”结果与原意不同，其错误的根源在于改名后结果式的约束关系不同了。,2023/10/27,26,第三对受某个量词约束的变元改名时新名决不能与该量词的作用域中的其它自由变元同名。否则改名后将改变元式的约束关系，改变了原式的意义。例如：将 x（x=yxy）中X改名为y则有：y（y=yyy）。其意思是“任何个体都或者与自己相等或者与自己不等”，这与原意不同。,2023/10/27,27,第四对受某个量词约束的变元改名时新名能否与该量词的作用域中的约束变元同名呢？回答是有时行有时不行。这是为什么呢？我们举例说明：例如：将 x（x20 y（x=yz（zy）。该式中的约
20、束变元x不能改名y（y是作用域中的约束变元），但可改名为z（z也是作用域中的约束变元），因为该公式 x（x20 y（x=yz（zy）的意思是“对于任何个体，其平方必0，并且对于任何新个体，原个体都于新个体相等，并且存在一个个体，它大于该新个体”。而改名为y后的结果式为：y（y20 y（y=y z（zy),2023/10/27,28,其意思是“对于任何个体，其平方必0，并且对于任何新个体，新个体必与自己相等并且存在一个个体，它大于该新个体”，显然它们的意思不相同，从约束关系看，结果式的约束关系显然与原来的约束关系不相同，但是：z（z20 y（z=y z（z=y）意思与原式相同，从约束关系看，结果
21、式的约束关系与原式一样。例如：上面这个例子中，如果将原式的约束变元y改名为其它变元，如改名为t，再将约束变元x改名为y结果式为：y（y20 t（y=t x（z t）显然与原来的约束关系完全相同，所以说这是正确的改名。,是否不改变原约束关系的改名都是正确的改名呢？,确实如此。,2023/10/27,29,总之改名规则用更加简单的途述为：（1）改名时需要更改的变元符号范围是量词中的变元以及该量词辖域中此变元所有约束出现处，而在公式之其余部分不变。（2）改名时所更改的符号一定不能出现在量词的辖域内。,2023/10/27,30,接下来我们在讨论代入问题。第一.代入是对自由变元而言，也就是说对自由变元
22、可施行代入。第二.特别注意代入是有条件的，不能盲目代入，不则将发生错误。,2023/10/27,31,例如：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)均不是原式的特例，也就是说这时的约束关系与原式不同。,2023
23、/10/27,32,再例如：如果一定要代以x或代以含x的项，则必须先把原式中的约束变元改名，使得与代入项无关，比如将上式改为u，而后施行代入，这时结果式为：u（u=xz），u（u=（x+t）z），u（u=（sinx）z）显然这是原式的特例，约束关系与原式一致。第三.代入必须“处处”进行。所谓“处处”进行是指当对某由自由变元施行代入时，必须对该公式中该变元的一切自由出现均施行代入，否则将是错误的。,2023/10/27,33,第四.为了确保对自由个体变元的正确代入，我们规定，代入前先对原式施行改名，使得原式中所有约束变元名代入式中所有变元名互不相同，然后再施行代入。第五.对于命题变元和谓词变元也
24、可施行代入，而且代入也就是有条件的，其条件仍就是代入前后约束关系必须保持不变。下面我们举例说明对命题变元和谓词变元的代入。,2023/10/27,34,例一.试在 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改名，使之与代入
25、式中的变元无关，如将y改为t得 t（x B（x，y）A（t）x A（x）这个结果显然是原式的特例，故代入正确。,2023/10/27,35,经过分析为了确保对命题变元的代入正确我们规定，代入前先对原式施行改名，然后施行代入，显然，按此规定施行代入，结果一定正确。而且一切正确的关与命题变元的代入均可按此规定得到。谓词变元的代入比较复杂，因为在公式中为此变元均是以谓词填式的形式出现，因此在代入前应先将代入的谓词变成相应的填式，然后在把代入好的填式代到原式中去，因此要使个代入正确，必须保证二次代入均正确，即二次代入过程中的约束关系均不应发生变化，我们举例说明这一过程。,2023/10/27,36,例
26、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
27、)代入到原式即可 z(u A(z,y,x,y)Y(z)yu A(t,y,x,y)同理,为了确保对谓词变元的代入正确,我们仍然规定同命题变元的代入规定类同.,2023/10/27,37,习题及参考答案,一.将下列句子用谓词填式表示 1.1小赵是优秀学生且书是红的。解：设A表示“是优秀学生”，i表示小赵，则“小赵是优秀学生”表示为A（i），又若以B表示谓词“是红的”，j表示书，则“书是红的”表示为B（j）所以“小赵是优秀学生且书是红的”整个句子表示为A（i）B（j）1.2张三高于李四,则张三高于王五。解：用A 表示“高于”a表示“张三”，b表示“李四”，c表示“王五”，则语句表示为 A（a，b）A
28、（a，c）,2023/10/27,38,二.将下列句子写成谓词公式 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表示“小张”则该语句表示为：S（x）W（x）,2023/10/27,39,三.将下列谓词译成句子.3.1用H(x,y)表示“x比y长得高”。设L表示李四，c表 示张三。解：H
29、（l，c）表示“李四不比张三长得高”，H（l，c）H（c，l）表示“李四不比张三长得高”且“张三与李四同样高”3.2（P（x，y）P（y，z）P（x，z）若P（x，y）解释为“若x小于y”，当x，y，z都在实数域中取值，则这个式子表示为“x小于y且y小于z，则x小于z”。这是永真公式。如果P（x，y）解释为“x为y的儿子”，当x，y，z都指人，则“若x为y的儿子且y是z的儿子则x是z的儿子”。这个公式表达的是一个永假公式。如果P（x，y）解释为“x距离y10米”，若x，y，z表示地面上的房子，那么“x距离y10米且y距离z10米则x距离z10米”。这个命题真值将由x，y，z的具体位置而定，它可
30、能为T，也可能为F。,2023/10/27,40,四.1.在某一高级语言程序设计中一维数组使用量词表示array A1：50中每一个项均不为零。解：x（I(x)(x，1)(x，50)（A(x)，0）2.使用量词表示：对于所有自然数x，y均有x+yx。解：可表示为：x y（N(x)（N(y)F（x，y）,2023/10/27,41,3.使用量词表示：某些人对某些食物过敏。解：设F（x，y）为“x对y过敏”M(x)是特性谓词表示“x是人”，G(y)也是特性谓词表示“y是食物”，此语句可译为：xy（M(x)（G(y)F（x，y）4.将高等数学中极限的定义limf（x）=k用谓词演算中表达式刻划。解：
31、我们知道上述极限定义是：任给 0,必存在一个 0,对所有x如果xc则必有f(x)k 我们设R(x)表示x是实数,则此极限定义可译为:(R()(0,x)(R(0,)x(R(x)(xc,)(f(x)k,),2023/10/27,42,五.指出下列公式中的自由变元，约束变元及约束关系 1.x（x=y+x）yx 解：x为约束变元，y为自由变元 约束关系为若x=y+x则必推出yx 2.（x=x）（xy）（x（x=x）x（xy）解：这里自由变元x即为自由变元也为约束变元，y为自由变元，约束关系如果对于所有。x=x则必等价于xy（这是在两个前提，x=x及xy的条件下）3.x y(x=y)x(y(x=y)(x
32、y)x(xy)解：与上同理故略,2023/10/27,43,六.指出下列公式中各量词不能改用什么变元作指导变元,并对各是实行改名.1.x(X(x)Y(x,t)Y(X(y)Y(x,y)解：2.xyX(x,y,t)y x X(x,y,t)3.x(y(t X(x,t)X(y,t)X(x,y),2023/10/27,44,七.试对下列公式施行代入 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),
