第二章谓词逻辑

第二章谓词逻辑在命题逻辑中，主要研究命题和命题演算，其基本组成单位是原子命题，并把它看作不可再分解的。但是原子命题，实际上还是可以作进一步分析的，特别是两个原子命题间，常常有一些共同特征，为了刻划命题内部的逻辑结构，就需要研究谓词逻辑。此外，命题逻辑的推证中有着很大的局限性，有些简单的论断也不能用命题逻辑进行推证。例如，简单而有名的苏格拉底三段论：所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。这个显然成立的推理在第一章中是不能进行推证的，比如令P表示：所有的人都是要死的，Q表示：苏格拉底是人，R表示：苏格拉底是要死的。于是该推理可以表示为：P∧QR但是，用第一章命题逻辑的方法并不能证明该推理成立，因为P∧Q→R不是重言式。比如当P、Q为T，R为F时，P∧Q→R的真值为F。苏格拉底三段论在命题逻辑中不能推证的原因是命题公式描述能力的局限性。比如：“所有的人都是要死的”和“苏格拉底是要死的”这两个命题所表述的性质都为：“是要死的”，但在命题逻辑中需用两个不同的命题符号P和R来表示，两个不同的符号显然掩盖了两个命题描述性质的共同性。这样必须要对命题的内部关系进行深入地研究。第1节谓词的概念与表示1客体命题中涉及的对象称为客体。比如命题：计算机是科学技术的工具，其中“计算机”就是客体。又如命题：张三是李四的领导，其中“张三”和“李四”都是客体。2谓词描述命题中客体性质或客体之间关系的部分称为谓词。比如上述两例中，“是科学技术的工具”和“…是…的领导”都是谓词。又例如：(a)他是三好学生。(b)7是质数。(c)每天早晨做广播操是好习惯。(d)5大于3。(e)哥白尼指出地球绕着太阳转。在上述语句中“是三好学生”、“是质数”、“是好习惯”、“大于”、“指出”都是谓词。前三个是指明客体性质的谓词，后两个是指明两个客体之间关系的谓词。3客体与谓词的表示我们将用大写字母表示谓词，用小写字母表示客体名称，例如A表示“是个大学生”，c表示张三，e表示李四，则A(c)，A(e)分别表示“张三是个大学生”，“李四是个大学生”。用谓词表达命题，必须包括客体和谓词字母两个部份，一般地说，“b是A”类型的命题可用A(b)表达。对于“a小于b”这种两个客体之间关系的命题，可表达为B(a,b)，这里B表示“…小于…”。又如命题“点a在b与c之中”可以表示为L：…在…和…之中，故可记为L(a，b，c)。4谓词的分类我们把A(b)称作一元谓词，B(a,b)称作二元谓词，L(a,b,c)称作三元谓词，依次类推。注意，代表客体名称的字母，它在多元谓词表示式中出现的次序与事先约定有关，因此未经约定前，上例记作L(a，b，c)或L(bc,a)等都可以，但一经约定，L(a,b,c)与L(b,c,a)就代表两个不同的命题。单独一个谓词不是完整的命题，我们把谓词字母后填以客体所得的式子称为谓词填式，这样谓词和谓词填式应该是两个不同的概念。一般地说，n元谓词需要n个客体名称插入到固定的位置上，如果A为n元谓词，a1，a2，…，an是客体的名称，则A(a1，a2，…，an)就可成为一个命题。通常。一元谓词表达了客体的“性质”，而多元谓词表达了客体之间的“关系”。*重点：谓词是描述命题中客体性质或客体之间关系的部分，用大写字母表示。第2节命题函数与量词1命题函数首先应注意，客体有客体常元和客体变元之分，当一个客体表示确定的客体时，称为客体常元；当一个客体表示不确定的客体时，称为客体变元。为了说明命题函数的概念，下面先举例解释命题与谓词的关系。设H是谓词“能够到达山顶”，L表示客体名称李四，t表示老虎，c表示汽车，那么H(L)，H(t)，H(c)等分别表示各个不同的命题，但它们有一个共同的形式，即H(x)。当x分别取L、t、c时就表示“李四能够到达山顶”，“老虎能够到达山顶”，“汽车能够到达山顶”。同理，若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等都是客体变元，很象一些函数，于是便有如下定义。定义2-2.1由一个谓词，一些客体变元组成的表达式称为简单命题函数。由一个或n个简单命题函数以及逻辑联结词组合而成的表达式称复合命题函数。根据这个定义可以看到，n元谓词就是有n个客体变元的命题函数，当n=0时，称为0元谓词，它本身就是一个命题，故命题是n元谓词的一个特殊情况。逻辑联结词，∧，∨、→、的意义与命题演算中的解释完全相同。例1设S(x)表示“x学习很好”，用W(x)表示“x工作很好”。则S(x)表示“x学习不是很好”。S(x)∧W(x)表示“x的工作，学习都很好”。S(x)→W(x)表示“若x的学习很好，则x的工作得很好。”例2用H(x,y)表示“x比y长得高”。设L表示李四，c表示张三。则H(L,c)表示“李四不比张三长得高”。H(L,c)∧H(L,c)表示“李四不比张三长得高”且“张三不比李四长得高”即“张三与李四同样高”。2个体域（或论域）例3设Q(x,y)表示“x比y重”，当x,y指人或物时，它是一个命题，但若x,y指实数时，Q(x,y)就不是一个命题。命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。但是客体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。例4R(x)表示“x是大学生”，如果x的讨论范围为某大学里班级中的学生，则R(x)是永真式。如果x的讨论范围为某中学里班级中的学生，则R(x)是永假式。如果x的讨论范围为一个剧场中的观众，观众中有大学生也有非大学生，那么，对某些观众，R(x)为真，对另一些观众，R(x)为假。例5(P(x,y)∧P(y,z))→P(x,y)若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的具体位置而定,它可能为T，也可能为F。从上述两例可以看到，命题函数确定为命题，与客体变元的论述范围有关。在命题函数中，客体变元的论述范围称作个体域。个体域可以是有限的，也可以是无限的，把各种个体域综合在一起作为论述范围的域称全总个体域。3量词使用上面所讲的一些概念，还不能用符号很好地表达日常生活中的各种命题。例如：S(x)表示x是大学生，而x的个体域为某单位的职工。那么S(x)可以表示某单位职工都是大学生，也可以表示某单位存在一些职工是大学生。为了避免这种理解上的混乱，因此需要引入量词，以刻划“所有的”和“存在一些’的不同概念。例如(a)所有的人都是要呼吸的。(b)每个学生都要参加考试。(c)任何整数或是正的或是负的。这三个例子都需要表示“对所有的x”这样的概念，为此，引入符号：V-x，表示“对所有的x”。符号“”称为全称量词。用来表达“对所有的”“每一个”“对任一个”等。符号“彐”称为存在量词，可用来表达“存在一些”“至少有一个”“对于一些”等。*重点：1）命题函数都有个体域，个体域一般由讨论者确定。2）在使用量词时，根据命题的实际意义，一般情况下全称量词“”后要用联结词“→”，而存在量词“彐”后要用联结词“∧”。第3节谓词公式与翻译1谓词公式我们知道，简单命题函数与逻辑联结词可以组合成一些谓词表达式。有了谓词与量词的概念，谓词表达式所能刻划的日常命题就能广泛而深入得多了。但是，怎样的谓词表达式才能成为谓词公式并能进行谓词演算呢?下面先介绍谓词公式。我们把A(x1，x2，…，xn)称作谓词演算的原子公式，其中x1，x2，…，xn是客体变元，因此原子谓词公式包括下述形式的各种特例。如：Q,A(x)，A(x,y)，A(f(x)，y)，A(x,y,z)，A(a,y)等。定义2-3.1谓词演算的合式公式，即谓词公式，可由下述各条组成：(1)原子谓词公式是谓词公式。(2)若A是谓词公式，则A是一个合式公式。(3)若A和B都是合式公式，则(A∧B)，(A∨B)，(A→B)和(AB)是谓词公式。(4)如果A是合式公式，x是A中出现的任何变元，则xA和彐xA都是谓词公式。(5)只有经过有限次地应用规则(1)、(2)、(3)、(4)所得到的公式是谓词公式。在讨论命题公式时，曾用了关于圆括号的某些约定，即最外层的括号可以省略，在谓词合式公式中亦将遵守同样的约定，但需注意，量词后面若有括号则不能省略。2翻译此处所说的翻译是将自然语言叙述的命题翻译成谓词公式的形式。下面举例说明如何用谓词公式表达自然语言中一些有关命题。由本例可知，对于命题翻译成谓词公式时，机动性很大，由于对个体描述性质的刻划深度不同，就可翻译成不同形式的谓词公式。本例中R(x)表示x是大红书柜，而A(x)∧B(x)∧C(x)也可表示大红书柜，但后一种将更方便于对书柜的大小颜色进行讨论，这样对个体刻划深度的不同就可翻译成不同的谓词公式。例题5在数学分析中极限定义为：任给小正数ε，则存在一个正数δ，使得当0＜│x-a│＜δ时有│f(x)-b│＜ε。此时即称解F(x，y)表示“x大于y”Q(x,y)表示“x小于y”，故可表示为：ε(P(ε,0)→彐δ(P(δ,0)∧x(Q(│x-a│,δ)∧P(│x-a│,0)→Q(│f(x)-b│,ε))))*重点：掌握将自然语言表示的命题翻译成谓词公式的方法。第4节变元的约束1作用域或辖域设α为一个谓词公式，其中有一部份公式形式为xP(x)或彐xP(x)。这里、彐后面所跟的x叫做量词的指导变元或作用变元，P(x)叫做相应量词的作用域或辖域。2约束变元和自由变元在谓词公式α中，x或彐x作用域中出现的x称为α中的约束变元，x亦称为被相应量词中的指导变元所约束。在α中除去约束变元以外所出现的变元称作自由变元。自由变元是不受约束的变元，虽然它有时也在量词的作用域中出现，但它不受相应量词中指导变元的约束，故我们可把自由变元看作是公式中的参数。例题1说明以下各式的作用域与变元约束的情况。a)x(P(x)→Q(x))b)x(P(x)→彐yR(x,y))c)xy(P(x,y)∧Q(y,z))∧彐xP(x,y)d)x(P(x)∧彐xQ(x,z)→彐yR(x,y))∨Q(x,y)解a)x的作用域是P(x)→Q(x)，x为约束变元。b)x的作用域是(P(x)→彐yR(x,y)),彐y的作用域是R(x,y)，x,y都是约束变元.c)x和y的作用域是(P(x,y)∧Q(y,z))，其中x,y是约束变元，z是自由变元。彐x的作用域是P(x,y)，其中x是约束变元，y是自由变元。在整个公式中,x是约束出现，y既是约束出现又是自由出现，z是自由出现。d)x的作用域是(P(x)∧彐xQ(x,z)→(彐y)R(x,y))，x和y都是约束变元，但Q(x,z)中的x是受彐x的约束，而不是受x的约束。Q(x,y)中的x,y是自由变元。从约束变元的概念可以看出，P(x1,x2,…xn)是n元谓词，它有n个相互独立的自由变元，若对其中k个变元进行约束则成为n-k元谓词，因此，谓词公式中如果没有自由变元出现，则该式就成为一个命题。例如，xP(x,y,z)是二元谓词。彐xxP(x,y,z)是一元谓词。3约束变元的换名为了避免由于变元的约束与自由同时出现，引起概念上的混乱，故可对约束变元进行换名。使得一个变元在一个公式中只呈一种形式出现，即呈自由出现或呈约束出现。我们知道，一个公式的约束变元所使用的名称符号是无关紧要的。故：xP(x)与yP(y)具有相同的意义。设A(x)表示x不小于0，那么xA(x)表示一切x