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

《离散数学王元元习题解答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。谓词携有可以放置个体的空位，当空位上填入个体后便产生一个关于这些个体的语句，它断言个体具有谓词所表示的性质和关系。通常把谓词所携空位的数目称为谓词的元数。 谓词演算中的量词quantifiers指数量词“

3、所有和“有，分别用符号(All的第一个字母A的倒写)和$(Exist的第一个字母E的反写)来表示。为了用量词和$分别表示个体域中所有个体和有些个体满足一元谓词P，需引入一个变元，同时用作量词的指导变元放在量词后和谓词P的命名式变元：xP(x) 读作“所有任意,每一个x满足P(x)。 表示个体域中所有的个体满足谓词P(x)。$x P(x) 读作“有存在,至少有一个x满足P(x)。 表示个体域中至少有一个体满足P(x)。当量词用于一谓词或复合的谓词表达式式，该谓词或复合的谓词表达式称为量词的辖域domainsof quantifiers。因此，量词的辖域或者是紧邻其右侧的那个谓词;或者是其右侧第一

4、对括号的表达式。当然，量词辖域与该量词指导变元同一的变元都是约束变元。例如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 A)当使用五个联结词时还有(AB)，(AB)，(AB)都是公式。 3只有有限步使用1，2条款所形

5、成的符号串是公式。括号省略原如此同前，并约定，(xA)，($x A)中最外层括号也可省略。习题解答练习 1、指出如下谓词公式中的量词与其辖域，指出各自由变元和约束变元，并回答它们是否是命题：1x(P(x)Q(x)RR为命题常元 2x(P(x)Q(x)$xS(x)T(x) 3x(P(x)$y(B(x,y)Q(y)T(y)4P(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(

6、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(x,y)P(x)不是命题。 2、对个体域0，1判定如下公式的真值, E(x)表示“x是偶数： 1x(E(x)x=1) 2x(E(x)x=1) 3$x(E(x

7、)x=1) 4$x(E(x)x=1)再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。解1x(E(x)x=1) 真x(E(x)x=1) 可表示成命题公式E(0)0=1E(1)1=1其中E(0)0=1真，E(1)1=1也真，故E(0)0=1E(1)1=1真。 2x(E(x)x=1) 假x(E(x)x=1) 可表示成命题公式E(0)0=1E(1)1=1其中E(0)0=1真，但E(1)1=1假，故E(0)0=1E(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也假，

8、故 (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、设整数集为个体域，判定如下公式的真值(*表示数乘运算)： 1x$y(x*y=x) 2x$y(x*y=1) 3x$y(x+y=1) 4$yx (x*y=x)5$yx (x+y=0)6x$y(x+y=0) 解1x$y(x*y=x) 真 2x$y(x*y=1) 假 3x$y(x+y=1) 真 4$yx (x*y=x) 真 5$yx (x+y=0) 假6x$

9、y(x+y=0) 真4、量词$!表示“有且仅有，$!xP(x)表示有且仅有一个个体满足谓词P(x)。试用量词，, $,等号“=与谓词P(x),表示$! P(x)，即写出一个通常的谓词公式使之与$!xP(x)具有一样的意义。解 $!xP(x)可用以下具有一样的意义的谓词公式表示$xP(x)yP(y)y=x 5、设个体域为整数集，试确定两个谓词P(x,y)，分别使得如下两个蕴涵式假： 1x$!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(

10、x,y)x$!yP(x,y) 为假(*表示数乘运算)。因为只有数0对一切整数x，有x*0=0，从而前件真；但对数0，可有众多y，使0*y=0，从而后件假。 6、指定整数集的一个尽可能大的子集如果存在为个体域，使得如下公式为真： 1x(x0) 2x(x=5x=6) 3x$y(x+y=3)4$yx (x+y0)为真 2对5，6 ，x(x=5x=6) 为真 3对整数集，x$y(x+y=3) 为真4使得$yx (x+y0$0x| x c |f(x) k |0$0x| x c |f(x) k |00$x| x c |f(x) k |e可用自然语言表述为：存在正数e，对无论怎样的正数，均有x使得| x c

11、 |但|f(x) k |e。 7、判别如下公式是否是可满足的，并说明理由： 1xP(x)$yP(y) 2xP(x)$yP(y) 3(P(a)$xP(x)4(P(a)$xP(x)（5） P(a)$xP(x) 6xP(x)P(a)解 1xP(x)$yP(y) 是可满足的，因为可使xP(x)和$yP(y)之一为真。2xP(x)$yP(y) 是不可满足的，因为不可能使xP(x)和$yP(y)同时为真。3(P(a)$xP(x) 是可满足的，因为只要使$xP(x)真，P(a)假，P(a)$xP(x)便为假，从而(P(a)$xP(x)真。4(P(a)$xP(x) 是可满足的，因为只要使$xP(x)假，或P(

12、a)假，P(a)$xP(x)便为假，从而(P(a)$xP(x)真。5P(a)$xP(x) 是可满足的，因为只要使P(a)假，P(a)$xP(x)便为真。6xP(x)P(a) 是可满足的，因为只要使xP(x)假，xP(x)P(a)便为真。 谓词公式的前束式 容提要定义 公式A称为公式A的前束式prenex normal forms，如果AA，且A形如 Q1x1QnxnB其中Q1，Qn为量词或$，B称为母式，B中无量词。当B为合取析取式时，A称为A的前束合取析取式。定理 前束式定理 对任意谓词公式均可作出其前束式，进而作出其前束合取式或前束析取式。 对任何谓词公式均可作出其前束式，因为我们总可以利

13、用各组逻辑等价式将量词逐个移至公式的前部，其步骤是: 首先将公式中联结词,消除。 其次将否认词深入到各原子公式之前。最后，利用节的第5组和第6组永真式将量词逐个移至公式前部。习题解答练习 1、设个体域D=d1, d2,d3，试用消去量词的方式证明：当A(x)中无自由变元y, B(y) 中无自由变元x时，x$y (A(x)B(y)$yx(A(x)B(y)解 x$y (A(x)B(y)xA(x)B(d1)A(x)B(d2)A(x)B(d3)A(d1)B(d1)A(d1)B(d2)A(d1)B(d3)A(d2)B(d1)A(d2)B(d2)A(d2)B(d3)A(d3)B(d1)A(d3)B(d2)

14、A(d3)B(d3)A(d1)B(d1)B(d2)B(d3)A(d2)B(d1)B(d2)B(d3)A(d3)B(d1)B(d2)B(d3)A(d1)A(d2)A(d3)B(d1)B(d2)B(d3)$yx(A(x)B(y)$y(A(d1)B(y)(A(d2)B(y)(A(d3)B(y)(A(d1)B(d1)(A(d2)B(d1)(A(d3)B(d1)(A(d1)B(d2)(A(d2)B(d2)(A(d3)B(d2)(A(d1)B(d3)(A(d2)B(d3)(A(d3)B(d3)A(d1)A(d2)A(d3)B(d1)A(d1)A(d2)A(d3)B(d2)A(d1)A(d2)A(d3)B(

15、d3)A(d1)A(d2)A(d3)B(d1)B(d2)B(d3)故x$y (A(x)B(y)$yx(A(x)B(y) 2、求如下各式的前束合取式： 1x(A(x)$y B(y) 2x(A(x)$y B(x,y) 3xy ($zA(x,y,z)$z B(x,y,z) 4$x($y A(x,y)($z B(z)C(x)5x($yA(x,y)$xy( B(x,y)y(A(y,x)B(x,y)解 1x(A(x)$y B(y)$xA(x)yB(y)$xyA(x)B(y)2x(A(x)$y B(x,y)x(A(x)$y B(x,y)x$y (A(x)B(x,y)3xy ($zA(x,y,z)$z B(x

16、,y,z)xy($zA(x,y,z)$z B(x,y,z)($z B (x,y,z)$z A(x,y,z)xy($zA(x,y,z)$zB(x,y,z)($z B (x,y,z)$z A(x,y,z)xy(zA(x,y,z)$zB(x,y,z)(zB (x,y,z)$z A(x,y,z)xy(zA(x,y,z)$uB(x,y,u)(vB (x,y,v)$w A(x,y,w)xyz$uv$w(A(x,y,z)B(x,y,u)(B (x,y,v)A(x,y,w)4$x($y A(x,y)($z B(z)C(x)$x($y A(x,y)($z B(z)C(x)$x($y A(x,y)(zB(z)C(

17、x)$x($y A(x,y)z (B(z)C(x)$x$y z (A(x,y)B(z)C(x)5x($yA(x,y)$xy( B(x,y)y(A(y,x)B(x,y)$ x($yA(x,y)$xy( B(x,y)u (A(u,x)B(x, u)$ x($yA(x,y)$xyu( B(x,y)(A(u,x)B(x, u)$ x($yA(x,y)$vwu( B(v, w)(A(u, v)B(v, u)$ x$y$vwu (A(x,y)B(v, w)(A(u, v)B(v, u) 一阶谓词演算形式系统 容提要 一阶谓词演算形式系统FPC的语言成分要复杂得多，它包括： 个体变元 x ,y ,z ,u

18、,v ,w , 个体常元 a ,b ,c ,d ,e, 个体间运算符号函数符 f (n) , g (n) , h (n) ,其中n为任一正整数，表示函数的元数。 谓词符号P(n)，Q(n)，R(n)，S(n)，其中n为非负整数，表示谓词的元数。当 n =0时谓词符退化为一个命题常元。 真值联结词 , 量词 , $ 括号，注意，FPC不使用联结词 , ，和量词$，但把它们看作可定义的记号，或缩写记号。例如，$xA(x)可看作是x A(x)的缩写。当需要引入量词$时，只要在系统中添加定义$的公理：$xA(x)x A(x) , x A(x)$xA(x) FPC的更高一级的语言成分有“个体项和“公式。 FPC的个体项(terms)下简称项由以下条款规定： 1个体变元和个体常元是项。 2对任意正整数n，如果f (n)为一n元函数符，t1, ,tn为项，那么f (n)(t1,tn)也是项。 3除有限次使用1，2条款所确定的符号串外，没有别的东西是个体项。 FPC的公式(formula)由以下条款规定： 1对任意非负整数n，如果P(n)为一n元谓词符，t1, ,tn为项，那么P(0)命题常元和P(n