离散数学王元元习题解答 (3).doc

《离散数学王元元习题解答 (3).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章谓词演算及其形式系统2.1个体、谓词和量词内容提要谓词演算中把一切讨论对象都称为个体，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。确定的个体常用a，b，c等到小写字母或字母串表示。a，b，c等称为常元（constants）。不确定的个体常用字母x，y，z，u，v，w等来表示。它们被称为变元（variables）。谓词演算中把讨论对象——个体的全体称为个体域（domainofindividuals）），常用字母D表示，并约定任何D都至少含有一个成员。当讨论对象遍及一切客体时，个体域特称为全总域（universe），用字母U表

2、示。例如，当初中学生说“所有数的平方非负”时，实数集是个体域；而达尔文在写《物种起源》时，则以全体生物为个体域；也许哲学家更偏爱全总域。讨论常常会涉及多种类型个体,这时使用全总域也是比较方便的。当给定个体域时，常元表示该域中的一个确定的成员，而变元则可以取该域中的任何一个成员为其值。表示D上个体间运算的运算符与常元、变元组成所谓个体项（terms）。例如，x+y，x2等。我们把语句中表示个体性质和关系的语言成分（通常是谓语）称为谓词（predicate）。谓词携有可以放置个体的空位，当空位上填入个体后便产生一个关于这些个体的语句，它断言个体具有谓词所表示

3、的性质和关系。通常把谓词所携空位的数目称为谓词的元数。谓词演算中的量词（quantifiers）指数量词“所有”和“有”，分别用符号"(All的第一个字母A的倒写)和$(Exist的第一个字母E的反写)来表示。为了用量词"和$分别表示个体域中所有个体和有些个体满足一元谓词P，需引入一个变元，同时用作量词的指导变元（放在量词后）和谓词P的命名式变元："xP(x)读作“所有（任意,每一个）x满足P(x)”。表示个体域中所有的个体满足谓词P(x)。$xP(x)读作“有（存在,至少有一个）x满足P(x)”。表示个体域中至少有一个体满足P(x)。当量词用于一谓词或

4、复合的谓词表达式式，该谓词或复合的谓词表达式称为量词的辖域（domainsofquantifiers）。因此，量词的辖域或者是紧邻其右侧的那个谓词;或者是其右侧第一对括号内的表达式。当然，量词辖域内与该量词指导变元同一的变元都是约束变元。例如"x(A(x)→B(x))∨C(x)中"x的辖域是A(x)→B(x)，其中的x是约束变元；但C(x)不在辖域内，其中的x则是自由变元；$xA(x)∧B(x)中$x的辖域是A(x)，其中x是约束变元，而B(x)中x为自由变元。定义2.1以下条款规定的符号串称为谓词公式（predicateforrmula），简称公式。（

5、1）谓词填式是公式，命题常元是公式（看作零元谓词）。（2）如果A，B是公式，x为任一变元，那么(┐A)，(A→B)，("xA)，($xA)（当使用五个联结词时还有(A∧B)，(A∨B)，(A«B)）都是公式。（3）只有有限步使用（1），（2）条款所形成的符号串是公式。括号省略原则同前，并约定，("xA)，($xA)中最外层括号也可省略。习题解答练习2.11、指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题：（1）"x(P(x)∨Q(x))∧R（R为命题常元）（2）"x(P(x)∧Q(x))∧$xS(x)→T(x)（3）"x

6、(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是命题。（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)

7、，其中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(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)再将它们的量词消去,表示成合取或析取命题公

8、式，鉴别你所确定的真值是否正确。解（1）"x(E(x)→┐x=1)真"x(E(x