第2章 逻辑代数(下)：谓词演算.doc

离散数学教程教案与习题解析 理工学院 段景辉第2章逻辑代数（下）：谓词演算2.1 谓词演算基本概念2.1.1 个体 谓词演算中把一切讨论对象都称为个体(individuals)，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。确定的个体常用a，b，c等小写字母或字母串表示。a，b，c等小写字母或字母串称为个体常元(constants)。不确定的个体常用字母x，y，z，u，v，w等来表示。它们被称为个体变元，或变元(variables)。 谓词演算中把讨论对象个体的全体称为个体域(domain of individuals)，常用字母D表示，并约定个体域都是非空的集合。当讨论对象未作具体指定，而是泛指一切客体时，个体域特称为全总域(universe)，用字母U表示。当给定个体域时，常元表示该域中的一个确定的成员，而变元则可以取该域中的任何一个成员为其值。表示D上运算的运算符与常元、变元可组成所谓个体项(terms)。例如，数学中的代数式a2+b，x2c等。由于在我们讨论的谓词演算中，其变元只能取值个体对象，不能取值函数、命题或谓词，因此，它又常被叫做一阶谓词演算。2.1.2 谓词2.1.3 量词 谓词演算中的量词(quantifiers)指数学中常用的数量词“所有的”（或“每一个”）和“有”（或“存在”），用符号 和 $ 来表示，分别称为全称量词和存在量词。为了用全称量词表示个体域中所有（每一个）个体满足一元谓词P，用存在量词$表示有（存在）个体满足一元谓词P，还需使用变元： xP(x) 读作“所有（任意，每一个）x满足P(x)”，表示个体域中所有的个体满足谓词P(x)。 $x P(x) 读作“有（存在，至少有一个）x满足P(x)”，表示个体域中至少有一个体满足谓词P(x)。 当量词用于一谓词填式或复合的谓词表达式时，该谓词或复合的谓词表达式称为量词的辖域(domains of quantifiers)。因此，量词的辖域或者是紧邻其右侧的那个谓词；或者是其右侧第一对括号内的表达式。 量词的指导变元和量词辖域内的同名变元与通常谓词填式中的个体变元不同，因为它可以改名却不能取值作代入。因此，我们把 xP(x) 和 $xP(x) 中变元x称为约束变元(bound variables)，而那些可以取值作代入的变元则称为自由变元(free variables)。对于一元谓词P(x)，xP(x)，$xP(x)均为命题，它们所断言的“所有个体满足性质P(x)”与“存在个体满足性质P(x)”，其真值已经被给定的个体域所确定。特别是,当个体域中个体有穷时，例如D = a1,an，xP(x) 的意义与命题 P(a1)P(an) 相一致，而 $xP(x) 的意义与命题P(a1)P(an) 相一致。2.1.4 谓词公式及语句形式化 定义2.1 归纳定义谓词公式(predicate formula)集合，谓词公式又称合式公式，简称公式： （1）谓词填式是公式，命题常元是公式（看作零元谓词），常称原子公式。 （2）如果A，B是公式，x为任一个体变元，那么(A)，(AB)，(xA)，($x A)（当使用五个联结词时还有(AB)，(AB)，(AB)）都是公式。 （3）（终极条款，略）。 括号省略原则同命题公式，并约定，(xA)，($x A)中最外层括号也可省略。语句形式化过程的四个关键步骤是：l 准确地从语句中提取谓词。一般说来，表示性质的谓语用一元谓词表示，表示关系的谓语用二元或更多元数的谓词来表示。l 准确使用量词和确定量词的辖域，当辖域中多于一个谓词时必须注意括号的使用。l 准确地使用谓词之间的真值联结词，正确地反映谓词之间的逻辑关系。l 准确地使用多个重叠的量词以及与它们配套的指导变元，量词的排列次序应与原语句的表述相一致。自然语言语句中，常常涉及全总个体域的某个局部的所有个体或某些个体，这时需要使用所谓“限定谓词”把量词限于那个局部。一般地说，当限定谓词用于限定全称量词时，它必须作为蕴涵词的前件加入；当限定谓词用于限定存在量词时，它必须作为合取词的合取项加入，即用 x(限定谓词A(x) 和 $x(限定谓词A(x)表示“所有满足A(x)的东西都 ”和“在满足A(x)的东西中有满足 的个体”。这里A(x)是限定谓词，将个体域暂时限定在满足A(x)的那些个体上。练习2.11. 选择题（1）下面哪个公式不是谓词公式( )AP BP(x)Q(y)R(x)Cx(P(x)R(x,y) Dx(R(x)P(x,y)【答案】：C（2）谓词公式x(P(x)$yR(y)Q(x)中量词x的辖域是( )A x(P(x)$yR(y) B P(x)C P(x)$yR(y) D P(x), Q(x)【答案】：C（3）谓词公式x(P(x)$yR(y)Q(x)中变元x是( )A自由变元 B约束变元C既不是自由变元也不是约束变元 D既是自由变元也是约束变元【答案】：D（4）设C(x):x是国家足球队选手，G(x):x是健壮的。命题“没有一个国家足球队选手不是健壮的”可符号化为( )Ax(C(x)G(x) Bx(C(x)G(x)C$x(C(x)G(x) D$x(C(x)G(x)【答案】：B（5）设L(x) ：x是学员，J(x) ：x是老师，A(x,y)：x钦佩y。命题”所有学员都钦佩某些老师”符号化为( )AxL(x)A(x,y) Bx(L(x)$y(J(y)A(x,y)Cx $y(L(x)J(y)A(x,y) Dx $y(L(x)J(y)A(x,y)【答案】：B（6）命题”没有不犯错误的人”形式化为(设A(x) ：x是人，B(x) ：x犯错误( )Ax(A(x)B(x) B$x(A(x)B(x)C$x(A(x)B(x) D$x(A(x)B(x)【答案】：D（7）设I(x):x是整数，N(x):x是负数，S(x,y):y是x的平方，则“任何整数的平方非负”可表示为下述谓词公式：( )Axy(I(x)S(x,y)N(y) Bx$y(I(x)S(x,y)N(y)Cxy(I(x)S(x,y) N(y) Dx(I(x)S(x,y)N(y)【答案】：A（8）令F(x):x是火车，G(y):y是汽车，H(x):x比y快。则语句“某些汽车比所有的火车慢”可表示为：( )A$y(G(y)x(F(x)H(x,y) B$y(G(y) x(F(x)H(x,y)Cx$y(G(y)(F(x)H(x,y) D$y(G(y)x(F(x)H(x,y)【答案】：B2. 填空题（1）通常一元谓词表示事物的 , 多元谓词表示事物之间的 。【答案】：性质；关系（2）xy(P(x,y)Q(y,z)$x P(x,y)中，x的辖域为 ， y的辖域为 , $x的辖域为 。【答案】：y(P(x,y)Q(y,z)；P(x,y)Q(y,z)；P(x,y)（3）公式x(P(x)Q(x,y)$zR(y,z)S(u)中自由变元为 ，约束变元为 。【答案】： y，u； x ，z（4）设个体域为自然数集,则命题“不存在最大自然数”形式化为 。【答案】：$xy(xy)（5）个体域为自然数集，P(x):x为奇数，Q(x):x为偶数，则命题“不存在既是奇数又是偶数的自然数”形式化为 。【答案】：$x(P(x)Q(x)（6）设个体域为实数集,则命题“任意实数总能比较大小”形式化为 。【答案】：xy(xyx0则x+y0x+y0) （2）x(x=5x=6) （3）x $y(x+y=3) （4）$y x (x+y0)为真（2）对个体域5，6，x(x=5x=6)为真（3）对整数集个体域，x $y(x+y=3)为真（4）对负整数集个体域，$yx (x+y0)为真，但使得$yx (x+y0) 为真的整数集的最大的子集不存在。9. 以实数集为个体域, 用谓词公式将下列语句形式化：（1）如果两实数的平方和为零，那么这两个实数均为零。（2）f(x)为一实函数当且仅当对每一实数x都有且只有一个实数y满足y = f(x)（不得使用量词 $!。“f(x)为实函数”可译为RF(f)）。【答案】解.（1）xy(x2+y2=0x=0y=0) 。（2）RF(f )x$y(y = f(x)$z(zyz= f(x)10. 用谓词公式将下列语句形式化：（1）高斯是数学家，但不是文学家。（2）没有一个奇数是偶数。（3）一个数既是偶数又是质数，当且仅当该数为2。（4）有的猫不捉耗子，会捉耗子的猫便是好猫。（5）党指向哪里，我们就奔向那里。（6）发亮的东西不都是金子。（7）不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。（8）一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任。（9）君子坦荡荡，小人长戚戚。（孔子）（10）谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。（歌德）【答案】解.（1）M(x) 表示“x是数学家”，A(x) 表示“x是天文学家”，g表示“高斯”，原句可表示为 M(g) A(g)（2）O(x) 表示“x是奇数”，E(x) 表示“x是偶数” ，原句可表示为 $x(O(x)E(x)（3）E(x) 表示“x是偶数”，P(x) 表示“x是质数” ，原句可表示为x(E(x)P(x) x=2)（4）C(x) 表示“x是猫”，M(x) 表示“x是老鼠”，G(x) 表示“x是好的”，K(x,y)表示“x会捉y” ，原句可表示为 $x(C (x)y(M (y)K(x,y)x(C (x)y(M (y)K(x,y)G(x)（5）Q(x,y) 表示“x指向y”，J(x,y) 表示“x奔向y”，party表示“党” ，us表示“我们”,原句可表示为x(Q(party，x)J(us, x)（6）G(x) 表示“x是金子”，L(x) 表示“x是发亮的” ,原句可表示为 x(L (x)G(x)（7）M(x) 表示“x是男人”， F(x) 表示“x是女人”，H(x,y) 表示“x比y高”,原句可表示为x(M (x)$y(F(y)H(x,y)$x(M (x)y(F(y)H(x,y)（8）M(x) 表示“x是人”，B(x,y)表示“x相信y”, 原句可表示为 x(M (x)$y(M(y)xyB(x,y)$y(M(y)xyB(y,x)（9）M(x) 表示“x是人”，J(x) 表示“x是君子”， H(x) 表示“x坦荡荡”，原句可表示为x(M(x)J(x)H(x)x(M(x)J(x)H(x)（10）M(x) 表示“x是人”，K(x) 表示“x游戏人生”，L(x) 表示“x一事无成”， H(x,y) 表示“x主宰y”，N(x) 表示“x是奴隶”，原句可表示为x(M(x)K(x)L(x)x(H(x,x)N(x)2.2 谓词演算永真式2.2.1 谓词公式的语义谓词公式的真值不仅依赖于个体域，依赖于公式中各个体变元的取值状况，还依赖于对公式中谓词符号、函数符号、常元符号意义的确认，即人们对它们所作的解释。解释是这些符号与个体域上具体性质、关系、函数、对象间的一个映射，常用I表示这种解释。I恒把命题常元（零元谓词）解释为真值0或1。 定义2.2 给定个体域D及公式A中各谓词符号的解释I，如果A中个体变元x1,xn分别取值u1,un时A真，则称A在u1,un处真；当x1,xn无论取D中怎样的个体u1 ,un，A在u1 ,un处均真，则称A在解释I下真。 定义2.3 给定个体域D，若公式A在每一解释I下均真，那么称A在D上永真。若公式A对任何个体域D均有D上永真，则称A为永真式，或称A永真(valid)。A永真仍记为 A。 定义2.4 公式A称为可满足的，如果有某一个体域、某一解释，使得变元在某一取值状况下，A取值真。否则，称公式A不可满足。公式A不可满足时也称A为永假式。2.2.2 谓词演算永真式 常用的谓词演算逻辑等价式与逻辑蕴涵式分为以下八组，其中A，B，C等表示任意的谓词公式。 第一组：所有命题演算中的重言式。首先，由于谓词演算中允许使用命题常元（如果不限于一阶谓词演算，还可以使用命题变元），因而谓词公式中仍包含命题公式，其中的重言式显然在谓词演算中仍然是永真式。 其次，当我们把命题演算中的重言式中的命题常元、命题变元，改为任意的谓词公式，都不会影响原式的永真性，从而它们也是谓词公式中的永真式。 第二组：当A不含自由变元x时，既A与自由变元x无关，根据我们的约定，以下两式显然成立： x AA , $x AA第三组：对任意含有自由变元x的公式A(x)，有 x A(x) A(x) A(x) $x A(x) x A(x) $x A(x)第四组：对任意含有自由变元x的公式A(x)，有$xA(x)x A(x) xA(x)$x A(x) $x A(x)xA(x) x A(x)$xA(x) 第五组：当公式B中不含自由变元x时，对任意含有自由变元x的公式A(x)，有 x A(x)Bx (A(x)B) x A(x)Bx (A(x)B)$x A(x)B$x (A(x)B)$x A(x)B$x (A(x)B) 第六组：上一组永真式中的公式B若含自由变元x，情况就要复杂一些。对任意含有自由变元x的公式A(x)，B(x)，有 x (A(x)B(x)x A(x)x B(x) x A(x)x B(x) x (A(x)B(x)$x (A(x)B(x) $x A(x)$x B(x)$x (A(x)B(x)$xA(x)$x B(x) 第七组：对任意含有自由变元x,y的公式A(x,y)，有xyA(x,y)yx A(x,y) xyA(x,y) $yx A(x,y) $yxA(x,y) x$ y A(x,y) x$y A(x,y) $y$ x A(x,y) $x $ y A(x,y)$y$x A(x,y) 第八组：当C中无自由变元x时，对任意含有自由变元x的公式A(x)，B(x)，有 x(CA(x)Cx A(x) $x(CA(x)C$x A(x) x (A(x)B(x) x A(x)x B(x)2.2.3 谓词公式等价变换的几个基本原理 定义2.5 设谓词公式A中含自由变元x，设t为一个体项，且t中无自由变元为A中的约束变元，那么称t是在A中对x可代入的，其代入实例记为A(t/x)（代入的意义同前）。 由于约束变元可改名，因此总可对A中约束变元改名，使t成为对x是可代入的。 定理2.1（代入原理）若A是永真式，那么对A中变元可代入的代入实例都是永真式。 定理2.2（替换原理）设A，D为谓词公式，C为A的子公式，且CD。若B为将A中子公式C的某些出现（未必全部）替换为D后所得的公式，那么AB。 定义2.6 设A为仅含联结词 ，的谓词公式，A*为将A中符号，t，f， , $分别换为，f，t, $， 后所得的公式，那么称A*为A的对偶式。 注意，第1章中关于命题演算对偶式的一切讨论，即对偶原理，对于谓词演算都仍然成立。 定理2.3 （改名原理）若公式A(x)中无自由变元y，那么， xA(x)yA(y) , $xA(x)$yA(y)练习2.21. 选择题（1）设论域为整数集,下列公式中哪个值为真( )Ax$y(x+y=0) B$xy(x+y=0)Cxy(x+y=0) D$x $y(x+y=0)【答案】：A（2）谓词公式xP(x)$yP(y)是( )A永真的 B不可满足的 C可满足的 D非永真的【答案】：B（3）设谓词P(x):x是奇数，Q(x):x是偶数，谓词公式$x(P(x)Q(x)在哪个个体域中是可满足的( )A自然数 B整数 C实数 D以上均不成立【答案】：D（4）设个体域A=a,b,公式xP(x)$xS(x)在A上消去量词后应为( )AP(x)S(x) BP(a)P(b)(S(a)S(b)CP(a)S(b) DP(a)P(b)S(a)S(b)【答案】：B（5）在谓词演算中,下列各