《离散数学王元元习题解答 (3).doc》由会员分享，可在线阅读，更多相关《离散数学王元元习题解答 (3).doc（23页珍藏版）》请在金锄头文库上搜索。
1、第二章 谓词演算及其形式系统2.1 个体、谓词和量词 内容提要 谓词演算中把一切讨论对象都称为个体，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。确定的个体常用a，b，c等到小写字母或字母串表示。a，b，c等称为常元（constants）。不确定的个体常用字母x，y，z，u，v，w等来表示。它们被称为变元（variables）。 谓词演算中把讨论对象个体的全体称为个体域（domain of individuals），常用字母D表示，并约定任何D都至少含有一个成员。当讨论对象遍及一切客体时，个体域特称为全总域（universe），用字母U表示。例如，当初中学生说“所有数的
2、平方非负”时，实数集是个体域；而达尔文在写物种起源时，则以全体生物为个体域；也许哲学家更偏爱全总域。讨论常常会涉及多种类型个体,这时使用全总域也是比较方便的。当给定个体域时，常元表示该域中的一个确定的成员，而变元则可以取该域中的任何一个成员为其值。表示D上个体间运算的运算符与常元、变元组成所谓个体项（terms）。例如，x+y，x2等。我们把语句中表示个体性质和关系的语言成分（通常是谓语）称为谓词（predicate）。谓词携有可以放置个体的空位，当空位上填入个体后便产生一个关于这些个体的语句，它断言个体具有谓词所表示的性质和关系。通常把谓词所携空位的数目称为谓词的元数。 谓词演算中的量词（q
3、uantifiers）指数量词“所有”和“有”，分别用符号 (All的第一个字母A的倒写) 和 $(Exist的第一个字母E的反写)来表示。为了用量词 和 $ 分别表示个体域中所有个体和有些个体满足一元谓词P，需引入一个变元，同时用作量词的指导变元（放在量词后）和谓词P的命名式变元： xP(x) 读作“所有（任意,每一个）x满足P(x)”。 表示个体域中所有的个体满足谓词P(x)。 $x P(x) 读作“有（存在,至少有一个）x满足P(x)”。 表示个体域中至少有一个体满足P(x)。当量词用于一谓词或复合的谓词表达式式，该谓词或复合的谓词表达式称为量词的辖域（domains of quanti
4、fiers）。因此，量词的辖域或者是紧邻其右侧的那个谓词;或者是其右侧第一对括号内的表达式。当然，量词辖域内与该量词指导变元同一的变元都是约束变元。例如x(A(x)B(x)C(x)中x的辖域是A(x)B(x)，其中的x是约束变元；但C(x)不在辖域内，其中的x则是自由变元；$x A(x)B(x)中$x的辖域是A(x)，其中x是约束变元，而B(x)中x为自由变元。 定义2.1 以下条款规定的符号串称为谓词公式（ predicate forrmula），简称公式。 （1）谓词填式是公式，命题常元是公式（看作零元谓词）。 （2）如果A，B是公式，x为任一变元，那么(A)，(AB)，(xA)，($x
5、A)（当使用五个联结词时还有(AB)，(AB)，(AB)）都是公式。 （3）只有有限步使用（1），（2）条款所形成的符号串是公式。括号省略原则同前，并约定，(xA)，($x A)中最外层括号也可省略。 习题解答练习2.1 1、指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题：（1）x(P(x)Q(x)R （R为命题常元） （2）x(P(x)Q(x)$xS(x)T(x) （3）x(P(x)$y(B(x,y)Q(y)T(y)（4）P(x)(y$x(P(x)B(x,y)P(x)解（1）全称量词，辖域 P(x)Q(x)，其中x为约束变元，x(P(x)Q(x)R是命题。（
6、2）全称量词，辖域 P(x)Q(x)，其中 x为约束变元。存在量词$，辖域 S(x) ，其中 x为约束变元。T(x)中x为自由变元。x(P(x)Q(x)$xS(x)T(x)不是命题。（3）全称量词，辖域 P(x)$y(B(x,y)Q(y)T(y)，其中 x为约束变元，T(y)中y为自由变元。存在量词$，辖域B(x,y)Q(y)，其中y为约束变元。x(P(x)$y(B(x,y)Q(y)T(y)是命题。（4）全称量词，辖域$x(P(x)B(x,y)，其中 y为约束变元。存在量词$，辖域P(x)B(x,y)，其中 x为约束变元。不在量词辖域中的P(x)中的x为自由变元。P(x)(y$x(P(x)B(
7、x,y)P(x)不是命题。 2、对个体域0，1判定下列公式的真值, E(x)表示“x是偶数”： （1）x(E(x)x=1) （2）x(E(x)x=1) （3）$x(E(x)x=1) （4）$x(E(x)x=1)再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。解（1）x(E(x)x=1) 真x(E(x)x=1) 可表示成命题公式（E(0)0=1）（E(1)1=1）其中E(0)0=1真，E(1)1=1也真，故（E(0)0=1）（E(1)1=1）真。 （2）x(E(x)x=1) 假 x(E(x)x=1) 可表示成命题公式（E(0) 0=1）（E(1) 1=1）其中E(0)
8、0=1真，但E(1) 1=1假，故（E(0) 0=1）（E(1) 1=1）假。（3）$x(E(x)x=1) 假$x(E(x)x=1) 可表示成命题公式 (E(0)0=1) (E(1)1=1)其中E(0)0=1假，E(1)1=1也假，故 (E(0)0=1) (E(1)1=1)假。（4）$x(E(x)x=1) 真$x(E(x)x=1) 可表示成命题公式 (E(0)0=1) (E(1)1=1)其中E(0)0=1假，但E(1)1=1真，故 (E(0)0=1) (E(1)1=1)真。 3、设整数集为个体域，判定下列公式的真值(*表示数乘运算)： （1）x $y(x*y=x) （2）x$y (x*y=1)
9、 （3）x $y(x+y=1) （4）$y x (x*y=x) （5）$y x (x+y=0) （6）x $y(x+y=0) 解（1）x $y(x*y=x) 真 （2）x$y (x*y=1) 假 （3）x $y(x+y=1) 真 （4）$y x (x*y=x) 真 （5）$y x (x+y=0) 假（6）x $y(x+y=0) 真4、量词 $! 表示“有且仅有”，$!xP(x)表示有且仅有一个个体满足谓词P(x)。试用量词，, $,等号“=”及谓词P(x),表示 $! P(x)，即写出一个通常的谓词公式使之与$!xP(x)具有相同的意义。解 $!xP(x)可用以下具有相同的意义的谓词公式表示
10、$x（P(x) y（P(y)y=x） 5、设个体域为整数集，试确定两个谓词P(x,y)，分别使得下列两个蕴涵式假： （1）x $!yP(x,y) $!yx P(x,y)（2）$!yx P(x,y) x $!yP(x,y)解（1）当P(x,y)表示x+y=0时x $!yP(x,y) $!yx P(x,y)为假。（2）当P(x,y)表示x*y=0时$!yx P(x,y)x $!yP(x,y) 为假(*表示数乘运算)。因为只有数0对一切整数x，有x*0=0，从而前件真；但对数0，可有众多y，使0*y=0，从而后件假。 6、指定整数集的一个尽可能大的子集（如果存在）为个体域，使得下列公式为真： （1）
11、x(x0) （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）使得$y x (x+y0) 为真的整数集的尽可能大的子集不存在。 7、以实数集为个体域, 用谓词公式将下列语句形式化： （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
12、)$z(zyz= f(x) 8、用谓词公式将下列语句形式化： （1）高斯是数学家，但不是文学家。 （2）没有一个奇数是偶数。 （3）一个数既是偶数又是质数，当且仅当该数为2。 （4）有的猫不捉耗子，会捉耗子的猫便是好猫。 （5）发亮的东西不都是金子。 （6）不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。 （7）一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任。 （8）如果别的星球上有人，天文学家是不会感到惊讶的。 （9）党指向哪里，我们就奔向那里。（10）谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。（歌德）解（1）M(x) 表示“x是数学家”，
13、A(x) 表示“x是天文学家”，g表示“高斯”,原句可表示为 M(g) A(g)（2）O(x) 表示“x是奇数”，E(x) 表示“x是偶数” ,原句可表示为 $x(O(x)E(x)（3）O(x) 表示“x是奇数”，E(x) 表示“x是偶数” ,原句可表示为x(O(x)E(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）G(x) 表示“x是金子”，L(x) 表示“x是发亮的” ,原句可表示为 x(L (x)G(x)（6）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)（7）M(x) 表示“x是人”，B(x,y)表示“x相信y”, 原句可表示为 x(M (x)$y(M(y)xyB(x,y)$y(M(y)xyB(y,x)（8）C(x) 表示“x是星球”，M(x) 表示“x是人”，A(x) 表示“x是天文学家”，e表示“地球”，H(x,y) 表示“x有y”，S(x) 表示“x惊讶”，原
