逻辑学导论第四章课件.ppt

1、逻辑学导论第四章命题逻辑和词项逻辑的局限性命题逻辑和词项逻辑的局限性（1）它们都不能处理关系命题及其推理。（2）它们都不能处理量词内部含联结词结构的命题及其推理。所以，我们还需要另外的逻辑谓词逻辑谓词逻辑，它把一个命题拆分为个体词、谓词、量词，很多时候还要加上联结词；它能够在一个统一的框架内同时处理性质命题和关系命题及其推理。个体词个体词 个体词就是表示对象域中的个体的符号，包括个体变项个体变项和个体常项个体常项。其中，个体变项使用小写字母x，y，z，等等，表示某个特定的范围内的某个不确定的对象。个体常项使用小写字母a，b，c，等等，表示某个特定范围内的某个确定的对象。这里所说的“某个特定的范

2、围”，叫做“论域”，即由一定对象所组成的类或者集合。论域规定了个体变项的取值范围，因此也叫做“个体域”。论域一般是“全域”，即由世界上所有能够被思考、被谈论的事物组成的集合；有时也取特定个体域为论域。3一元谓词和性质一元谓词和性质 谓词符号，用大写字母F，G，R，S等表示，若只把这些谓词符号用于单个的个体词，叫做“一元谓词符号”，经解释后，它们表示论域中个体的某个具体性质。4原子公式原子公式 如果一个谓词符号后面跟着写在一对括号内的一个个体词（个体常项或个体变项），我们就得到“原子公式”，例如F(a)，G(x)，它们分别表示“a是F”，“x是G”。在派生的意义上，原子公式有两个可能的真值：真或

3、者假。5量词和量化公式量词和量化公式 量词包括全称量词和存在量词：xF(x)，读做“对于所有x而言，x是F”。xF(x)，读做“存在x使得x是F”。6原子公式和量化公式还可以用命题联结词连接起来，形成更复杂的公式：x(F(x)G(x)xF(x)yH(y)7量词有其管辖的范围，简称“辖域辖域”。如果一个量词后面有括号，则处于括号内的公式构成该量词的辖域；如果量词后面无括号，则量词后面最短的公式，构成该量词的辖域。一个变项的某一次出现，如果处于量词x或x的辖域之内的，或作为与该量词一起出现的变项（指导变项），则称该变项的这一次出现是“约束出现约束出现”，否则叫做“自由出现自由出现”。8一个变项，如

4、果在一个公式中有约束出现，则称它是“约束约束变项变项”；如果在一个公式中有自由出现，则称它是“自由变项自由变项”。因此，一个体变项在一个公式中可以既是约束变项又是自由变项。一个含有至少一个自由变项的公式，叫做“开公式开公式”。开公式的意义不确定，没有确定的真假。一个不含任何自由变项的公式，叫做“闭公式闭公式”。在给定论域及其解释后，闭公式有确定的意义，也有确定的真假。9自然语言中性质命题的符号化自然语言中性质命题的符号化在论域为全域时，六种直言命题可以如下方式符号化：（1）全称的直言命题应符号化为一个全称蕴涵式。SAP：x(S(x)P(x)SEP：x(S(x)P(x)（2）特称的直言命题应符号

5、化为存在合取式。SIP：x(S(x)P(x)SOP：x(S(x)P(x)（3）单称的直言命题应符号化为原子公式。“春江花月夜是一支中国古代名曲”可以符号化为：F(a)“周作人不是一位具有民族气节的人”可以符号化为：F(b)10关系命题关系命题 包括三个要素：个体词个体词、关系谓词关系谓词和量词量词。从形式上看，关系谓词与性质谓词没有实质性区别，只不过后者涉及一个个体，而前者涉及两个以上的个体。发生在两个对象之间的关系叫做“二元关系”，发生在三个对象之间的关系叫做“三元关系”，依此类推，发生在n个对象之间的关系叫做“n元关系”。11一阶语言一阶语言（）初始符号（i）个体变项：x，y，z，（ii）

6、个体常项：a，b，c，（iii）谓词符号：F，G，R，S，（iv）量词：全称量词，存在量词（v）联结词：，（vi）辅足性符号：逗号，左括号（，右括号）。12（）形成规则（i）一个谓词符号F，后面跟有写在一对括号内、并用逗点适当分开的n个个体词（n1），是原子公式。（ii）如果A是公式，则A是公式。（iii）如果A和B都是公式，则AB，AB，AB，AB是公式。（iv）如果A是公式，则xA，xA是公式。（v）只有按以上方式形成的符号串是公式。13重叠的量词和重叠的量化式重叠的量词和重叠的量化式“重叠量词”指在一个量词的辖域内还有另外的量词。包含重叠量词的公式就叫做“重叠量化式”。一阶语言中允许重复

7、约束和空约束。14自然语言中关系命题的符号化自然语言中关系命题的符号化 例如，下面的关系命题：（1）牛郎不爱有些爱织女的男人。（2）织女爱每一个爱牛郎的人。（3）有的投票人赞成所有的候选人。分别可以符号化为：（1）x(M(x)L(x,a)L(b,x)（2）x(P(x)L(x,b)L(a,x)（3）x(T(x)y(H(y)Z(x,y)15一阶语言的一个模型模型U（亦称“解释”）包括下列因素：（）一个个体域D，即由具有一定性质的个体所构成的集合。当给定个体域之后，全称量词x表示个体域中的所有个体，存在量词x表示个体域中的某些个体。全称量词、存在量词和约束个体变项的意义都确定了。（）个体常项在个体域

8、D中的值，即个体常项表示该个体域中的某个特定个体。（）谓词符号在个体域D上的解释，即表示该个体域中个体的性质和个体间的关系。16当给定模型U后，谓词逻辑的闭公式的意义就确定了，其真假也确定了。但谓词逻辑的开公式的意义尚不确定，为了确定该公式的真值，需要对其中的自由变项的值做指派指派（记为）。在模型U和指派之下，谓词逻辑的所有公式都有了确定的意义，也有了确定的真假。谓词逻辑的语言因此得到了确定的解释。一个模型U和模型U上的一个指派合称为一个赋值，记为U，。17如果一个谓词逻辑的公式对于任一赋值都为真，则称该公式为普遍有效式，亦称常真式。普遍有效式是谓词逻辑的规律。如果一个谓词逻辑的公式对于任一赋

9、值都为假，则称该公式是一个不可满足式，亦称常假式。不可满足式是谓词逻辑中的逻辑矛盾。如果一个谓词逻辑的公式，对于有些赋值为真，对于有些赋值为假，则称该公式是偶真式，但非普遍有效式。所有的偶真式都是可满足式。18普遍有效式举例普遍有效式举例（1）xF(x)F(y)（2）F(y)xF(x)（3）x(F(x)F(x)（4）x(F(x)F(x)19（5）xF(x)xF(x)（6）xF(x)xF(x)（7）x(F(x)G(x)(xF(x)xG(x)（8）x(F(x)G(x)(xF(x)xG(x)（9）x(F(x)G(x)(xF(x)xG(x)（10）xyR(x,y)yxR(x,y)20谓词逻辑的树形图是

10、命题逻辑树形图的扩充，命题逻辑原有的关于联结词的九个画图规则仍然有效；但需要增加关于全称量词x和存在量词x的四个画图规则：21222324谓词逻辑是不可判定的谓词逻辑是不可判定的 即是说，不存在一种机械的、能行的办法，它适合于任一的谓词逻辑公式，将在有穷步内结束，并且就该公式是不是普遍有效式给出唯一确定的结果。不过，某些特殊类型的谓词逻辑公式，例如一元谓词逻辑公式，其普遍有效性是可判定的。在这个意义上，谓词逻辑是半可判定的。25证明非普遍有效性或可满足性的方法证明非普遍有效性或可满足性的方法 要证明这样的一个公式不普遍有效，或者是可满足的，前者是要为该公式找一反模型，使得该公式在其中为假；后者

11、是要为该公式找一模型，使得该公式在其中为真。这种方法叫做“解释方法解释方法”或“模型方法模型方法”。26（一）（一）QN推理规则推理规则 谓词逻辑自然推理QN是命题逻辑自然推理PN的扩充，所有PN的规则都是QN的规则；所有已经证明的PN定理和导出规则，都是QN的定理和导出规则，故在证明或推演中可以直接使用它们，无需另外证明。在PN的基础上，QN增加了四条与量词有关的规则：27 1全称量词消去规则，记为规则：从xA(x)推出A(x/t)，其中代换x的t不会被A中原有的量词所约束。282全称量词引入规则，记为规则：从A(x)推出xA(x)，只要能够确保前提中的自由变项x是任意的。29 若不能确保前

12、提中的自由变项x是任意的，就要给该x加标记，其具体做法是：在一个证明或推演的某一步上，出现了含自由变项x的公式A，且不能保证其中的x是任意的，则在该公式的右边注明该公式来历的位置，写上x，表示该x可能不是任意的，不能对它使用规则。以下三种情形需要给相应的自由变项加标记：（i）给定前提中的自由变项；（ii）根据假设引入规则所引入的假设中的自由变项；（iii）一个在前提或假设中是自由的变项，在从该前提或假设出发，根据QN的推演规则所得到的任意一行中也出现，那么，它在后面这些行的出现也应加标记。303存在量词消去规则，记为规则：从xA(x)可以推出A()，这里要求（i）是先前没有出现过的特指常项；（

13、ii）如果公式A含有x之外的自由变项y，应该用该y给特指常项做下标，写成y。314存在量词引入规则，记为规则：从A(x/t)可以推出xA(x)，只要代换x的t不会被A原有的量词所约束，或者新引入的存在量词不会将A(x)中除x之外的其他自由变项一并加以约束。32量词规则总结量词规则总结 全称量词消去规则全称量词消去规则：从xA(x)推出A(x/t)，其中代换x的t不会被A中原有的量词所约束，这包括以下情形：（1）t是一个个体常项；（2）A是一个原子公式，x是其中的自由变项，t是任一个体词；（3）A含有量词，但自由变项x不在这些量词的辖域之内，t是任一个体词；（4）A含有量词，且自由变项x在这些量

14、词的辖域之内，则t必须是与已量化变项不同的变项。否则，称为t对于公式A中的自由变项x代入不自由。33 全称量词引入规则全称量词引入规则：从A(x)推出xA(x)，只要能够确保前提中的自由变项x是任意的。以下情况下的自由变项不能确保是任意的，被称为“加标记变项”：（i）给定前提中的自由变项；（ii）根据假设引入规则所引入的假设中的自由变项；（iii）从该前提或假设出发，根据QN的推演规则所得到的的那些行中、与前提或假设中的自由变项相同的自由变项；（iv）给特指常项做下标的自由变项。对加标记变项，规则不适用。34 存在量词消去规则存在量词消去规则：从xA(x)可以推出A()，这里要求（i）是先前没

15、有出现过的特指常项；（ii）如果公式A含有x之外的自由变项y，应该用该y给特指常项做下标，写成y。存在量词引入规则存在量词引入规则：从A(x/t)可以推出xA(x)，其中代换x的t不会被A中原有的量词所约束，或者新引入的存在量词不会将A中除x之外的其他自由变项一并加以约束。35（二）（二）QN有前提推演有前提推演3637（三）（三）QN定理及其证明定理及其证明 1xA(x)xA(x)2xA(x)xA(x)3xA(x)xA(x)4xA(x)xA(x)5AxA，若x不在A中自由出现 6AxA，若x不在A中自由出现 7A(x/t)xA(x)，若t对于x代入自由 8xA(x)xA(x)3839第二组

16、9x(A(x)B(x)xA(x)xB(x)10 x(A(x)B(x)xA(x)xB(x)11x(AB(x)AxB(x)，若x不在A中自由出现 12x(AB(x)AxB(x)，若x不在A中自由出现 13x(AB(x)AxB(x)，若x不在A中自由出现 14x(AB(x)AxB(x)，若x不在A中自由出现4041第三组 15x(A(x)B(x)(xA(x)xB(x)16x(A(x)B(x)(xA(x)xB(x)17x(A(x)B(x)(xA(x)xB(x)18x(A(x)B(x)(xA(x)xB(x)19x(AB(x)(AxB(x)，若x不在A中自由出现 20 x(AB(x)(AxB(x)，若x不在A中自由出现 21x(A(x)B)(xA(x)B)，若x不在B中自由出现 22x(A(x)B)(xA(x)B)，若x不在B中自由出现42