《离散数学 ( 第3次 ).doc》由会员分享，可在线阅读，更多相关《离散数学 ( 第3次 ).doc（11页珍藏版）》请在金锄头文库上搜索。
1、第3次作业一、填空题（本大题共20分，共 10 小题，每小题 2 分）1. 是否可以画出一个简单的无向图，使得各点度数与一下序列一致。（T or F）（1）2，2，2，2，2，2 ； （）（2）2，2，3，4，5，6 ； （）( 3) 1，2，3，4，4，5； （）2. 在根树中，若从Vi到Vj可达，则称Vi是Vj的_，Vj是Vi的_3. 设A=a,b,B=1,2,3，判断下列集合是否是A到B的函数。F_1=a,1,b,2,F_2=a,1,b,1， F_3=a,1,a,2, F_4=a,34. 用列元法表示下列集合A=x|xN且x29，则可表示为（ ）。5. 设X=a,b,c,d,Y=1,2,
2、3,4,5，且有f=,，则 dom f为（ ）、R_f为 和f(x)为（ ）。6. 判断下列命题正确与否：(1)正整数集N上的小于等于关系“”是良序关系。（ ）（2）In =1,2,n上的小于等于关系“”是良序关系。（ ）(3)整数集Z和实数集R上的小于等于关系“”是良序关系。（ ）7. 在由n个元素组成的集合上，可以有（ ）种不同的二元关系？若集合A,B的元数分别为|A|=m,|B|=n,试问从A到B有( )种不同的二元关系？8. 设R_1 和R_2 是集合A上的二元关系，试判断下列命题是否正确？ ( ) ( ) ( )9. 设R_1和R_2是非空集合A上的等价关系，下列各式哪些是A上的等价
3、关系？哪些不是A上的等价关系 ？举例说明：AA-R_1； ( ) R_1-R_2； ( )R_12； ( ) r(R_1-R_2)； ( )R_1R_2 ( )10. 对下述论断判断正确与否，在相应括号中键入“Y”或“N”。设A=2,3,6,12,24,36，A上的整除关系是一偏序关系，用“”表示。(a）该偏序关系的哈斯图是（ ）（b)“”=2,2,2,6,3,3,3,6,6,6,6,12,12,12,12,24,24,24,36,36 （ ）二、计算题（本大题共40分，共 4 小题，每小题 10 分）1. 试将公式化成等价的前束范式：xF(x)xQ(x)；2. z)R(x，y，z)z)Q(x
4、，z)(x)($x)P(x)(求等价于下面wff的前束合取范式与前束析取范式：(3. 试将公式P（PQ）化为析取范式和合取范式：4. 设f：RR，f（x）=x2-2；g：RR， g（x）=x+4。 (1)求gf，fg (2)问gf和fg是否为单射、满射、双射？ （3）求出f、g、gf和fg中的可逆函数的逆函数。三、简答题（本大题共20分，共 4 小题，每小题 5 分）1. 设G是有两个奇度点的连通图,设计一个构造G的欧拉道路的算法。2. 设X=2,3,4,5，求集合 上的关系“”、dom及ran。3. 设A=1,2,3,4,5,R=,，画出R的关系图。4. 给定集合A=1,2,3,4,5，在集
5、合A上定义两种关系：R=,，S=,，求RS和SR的矩阵。四、证明题（本大题共20分，共 2 小题，每小题 10 分）1. 证明:xy(P(x)Q(y) )=xP(x)yQ(y)2. 设是一个代数系统，*是R上的一个二元运算，使得对于R中的任意元素a,b都有a*b=a+b+ab,试证明：0是幺元且是独异点。答案：一、填空题（20分，共 10 题，每小题 2 分）1. 参考答案：（1）T （2）F （3） F解题方案：评分标准：2. 参考答案：祖先；后代解题方案：评分标准：3. 参考答案：F_1,F_2是函数，F_3,F_4不是函数。解题方案：若不强调是A到B的函数，则F_4是函数，其定义域为a。
6、评分标准：4. 参考答案：1,2,3解题方案：评分标准：5. 参考答案：a,b,c,d 1,3,4 f(a)=1,f(b)=3,f(c)=4,f(d)=4解题方案：评分标准：6. 参考答案：正确 正确 错误解题方案：整数集Z和实数集R上的小于等于关系“”不是良序关系 (因为Z或R本身无最小元) 。评分标准：7. 参考答案：2(n2 ) 2(mn) 解题方案：评分标准：8. 参考答案：（1）命题正确（2）命题正确（3）命题不正确解题方案：评分标准：9. 参考答案：（1）不是 （2）不是 （3） 是 （4） 不是 （5） 是解题方案：评分标准：10. 参考答案：Y N解题方案：评分标准：二、计算题
7、（40分，共 4 题，每小题 10 分）1. 参考答案：xF(x)xQ(x)=xF(x)xQ(x)=xF(x)xQ(x)=x(F(x)Q(x)解题方案：评分标准：2. 参考答案：z)R(x，y，z)z)Q(x，z)(x)($x)P(x)( z)R(x，y，z)z)Q(x，z)(x)($x)P(x)(u)R(x，y，u)z)Q(x，z)(x)($x)P(x)($(u)R(x，y，u)z)Q(x，z)(x)( P(x)($(u)( P(x)Q(x，z)R(x，y，u)z)(x)($(前束合取范式u)(P(x) Q(x，z) R(x，y，u)(P(x) Q(x，z) R(x，y，u)(P(x) Q(
8、x，z) R(x，y，u)(P(x) Q(x，z) R(x，y，u)(P(x) Q(x，z)R(x，y，u)(P(x) Q(x，z) R(x，y，u)(P(x) Q(x，z) R(x，y，u)z)(x)($(前束析取范式解题方案：评分标准：3. 参考答案：（PQ）（PQ）=(（PQ）（PQ）)(（PQ）（PQ）)(等值律)=(（PQ）（PQ）) (（PQ）（PQ）) (蕴涵律)=（PQ）(PQ) (分配律) 合取范式=(PP) (PQ)(QP)(QQ) (分配律)析取范式解题方案：评分标准：4. 参考答案：（1）fg =x,x2+8x+14|x R gf =x,x2 +2|xR （2）gf 和
9、 fg均是非单非满函数。 （3）因为g是双射，所以可逆，其逆函数为：g(-1) ( x)=x-4。解题方案：评分标准：三、简答题（20分，共 4 题，每小题 5 分）1. 参考答案：step1: 添加连接两个奇度点的边Step2: 调用一般的欧拉回路的算法Step3: 在回路中删除添加的边解题方案：评分标准：2. 参考答案：=,dom2,3,4ran3,4,5解题方案：评分标准：3. 参考答案：解题方案：评分标准：4. 参考答案：图 3.6.1-2 RS的矩阵图 3.6.1-3 SR的矩阵解题方案：因为关系可用图形表示，所以复合关系也可用图形表示。评分标准：四、证明题（20分，共 2 题，每小
10、题 10 分）1. 参考答案：xy(P(x)Q(y) )=xy(P(x)Q(y) )=xP(x)yQ(y)=xP(x)yQ(y)=xP(x)yQ(y)解题方案：评分标准：2. 参考答案：对任意 aR，有0*a=0+a+0a=aa*0=a+0+a0=a故0是幺元。对任意 a,bR，有a*b=a+b+abR所以*是封闭的。对任意 a,b,cR，有(a*b)*c=(a+b+ab)+c+(a+b+ab)c=a+b+c+ab+ ac+bc+ abca*(b*c)=a+(b+c+bc)+a(b+c+bc)=a+b+c+ab+ ac+bc+ abc所以(a*b)*c=a*(b*c)故*是可结合的。综上所述，是独异点。解题方案：评分标准：
