《离散数学(第1次)解析.docx》由会员分享，可在线阅读，更多相关《离散数学(第1次)解析.docx（16页珍藏版）》请在三一文库上搜索。
1、第1次作业一、单项选择题(本大题共30分，共15小题，每小题2分) 1.图G所示平面图deg(R3)为A.4B.5C.6D.32.在完全m又树中，若树叶数为t,分枝点数为i,则有()o A.B.c.(m-1)i=t-lD.(m-l) i WtT3.命题a)：如果天下雨，我不去。写出命题a)的逆换式。A.如果我不去，天下雨。B.如果我去，天下雨。C.如果天下雨，我去。D.如果天不下雨，我去。4.设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该 图有多少个顶点()A.5B.c.2D.65.假设A=a, b, c, d,考虑子集S=a, b, b, c, d,则下列选项正确的是 (
2、)oA.S是A的覆盖B.S是A的划分C.S既不是划分也不是覆盖D.以上选项都不正确6.没有不犯错误的人。M(x)： x为人。F (x) ： x犯错误。则命题可表示为 ()OA.(Vx) (M(x) f F (x)B.(3x) (M(x)AF (x)C.(Vx) (M(x)AF(x)D.(3x) (M(x) -*F (x)A. 命题逻辑演绎的CP规则为() A.在推演过程中可随便使用前提B.在推演过程中可随便使用前面演绎出的某些公式的逻辑结果C.如果要演绎出的公式为B-C形式，那么将B作为前提，演绎出CD.设。(A)是含公式A的命题公式，BA,则可以用B替换。(A)中的A8.设G是有6个结点的完
3、全图，从G中删去()条边，则得到树。 A.6B.9C.10D.159.设A、B两个集合，当()时A-B二B。A.A=BB.A1BC.B7AD.A=B=(|)10.设 U=1, 2, 3, 4, 5, A=2, 4, B=4, 3, 5, C=2, 5, 3,确定集 合(A-C)-B =()oA.1,4B. 3, 4, 5)C.42011.下图的最小生成树的权为（）-A.40B.44C.48D.5212.对偶式为P t Q表达式是A.PAQB.P I QC.PVQD.P-*Q13.下列语句是命题，并且真值为0的是()A.雪式白的。B.l+24oC.天气真好啊！D.我正在说谎。14.如果有限个数的
4、乘积为零，那么至少有一个因子等于零。N(x)： x是有限 个数的乘积。Z(y)： y为0。P (x) ： x的乘积为0。F (y) ： y为乘积中的一 个因子则命题可表示为()。A.(3x) (N(x) f P(x) A(3y) (F(y)A(Z(y)B.(3x) (N(x) AP(x) - Gy) (F(y)A(Z(y)C.(3 x) (N (x) f P (x) A(3 y) (F (y) (Z (y)D.(Vx) (N (x) -P (x) A(3 y) (F (y) A(Z (y)15.设A、B、C是任意集合，判断下述论断是否正确，并将正确的题号填入括 号内（）。A.若 AUB=AUC
5、,则 B二CB.若 AHB=AGC ,则 B二CC.若 A-B=A-C,则 B=CD.则 A=B二、多项选择题（本大题共20分，共5小题，每小题4分） 1.两个命题变元P和Q生成的4个小项为：oA.PAQB.1 PAQC.PA-i QD.n PAn Q2.下图是O oA.是强连通的B.是弱连通的C.是单侧连通的D.是不连通的3.下列说法正确的是（）A.设Z,+是整数加法群，令f:nn,V nZ,则f是Z的一个自同构映射。B.设G是一个Abel群，令f: a R a2-(T) (V aG),则f是G的一个自同 构映射。C.设I ,是实数乘法群，是实数加法群，令f: x-5x,则f是R的一个 满同
6、态映射D.A、B、C都是正确的。4.函数 f: RXR-*RXR, f ()=是( )函数。A.入射B.满射C.双射D.以上答案都不对5.设4=1,2,3,则集合 A上的关系 R=,是()关系；A.自反B.反自反c.不是自反D.不是反自反三、判断题(本大题共20分，共10小题，每小题2分)1 .判断对错：集合2,3,4, 是无限集()。2 .设G是一个联结词的集合，若任意一个命题公式都可用G中联结词构成的公式来表示，则称G为最小联结词组。3.公式VxP (x)-3yQ (x, y)的前束范式是VxVy (P (x) Q (x, y)。4.判断对错。一个谓词公式wff A,如果在一种赋值下为假，
7、则称该wff A为 不可满足的。5.下图中(c)和(d)是根树6 .设f ： x,yf 1,3,5定义为f(x)=l,f(y)=5,则这个函数是入射函数。7 .设集合 A二216, 243, 357, 648.定义 A 上的关系 R= (x, y) |x,yeA,且 x与y中至少有一个相同数字。则R是A上的一个相容关系，R不是等价关 系。8 .自反(对称、传递)闭包是包含R的最小自反(对称、传递)关系。()9 .设 X=1,2, 3,4, Y=1,2, 3,4,5, Z=1,2, 3, f :X-*Y, f=, g:YZ, g =则 g f=, ,。10 .设R是由A=1,2, 3, 4到B二
8、2, 3, 4的关系，S是由B到C=3, 5, 6的关 系，分别定义为:R= |a+b=6 = , S= | b整除c = ,于是复合关系 R S=,四、计算题(本大题共20分，共4小题，每小题5分)1.设 f, g 均为实函数，f(x)=2x+l ,g(x)=x-2+lo 求fOO r*p O r*Ogg II Ig g O2.设集合A=1, 2, 3,4)，A上的二元关系R= (x, y) |x, yGA,且x2y,求R的关系 图与关系矩阵3.试将公式PA (P-Q)化为析取范式和合取范式：4.设全集合 E二a, b, c, d, e, A=a, d, B=a, b, e, C=b, d,
9、求下列集 合：(l)An-B；(2) (AAB) U C；(3)AU (B-C) ； (4) P (A) A p (B)五、证明题(本大题共10分，共2小题，每小题5分)1.符号化下列命题并推证其结论：科学家都是勤奋的。每个勤奋乂身体健康的人在事业中都会获得成功。存在着 身体健康的科学家。所以存在着事业获得成功的人或事业半途而废的人。2.设整数集Z上的二元关系R定义如下：R=|x,yZ, (x-y)/2是整数，证 明R在Z上是自反的。答案:一、单项选择(30 分,共15每小题2分）1. B 2. C 3. A 4. B 5.A 6. A 7. C 8. C 9. D 10. D 11. C 1
10、2. B 13. B14. B 15. D二、多项选择题(20分,1. ABCD 2. BC 3. AB 4.共5题，每小题4分）ABC 5. CD三、判断题(20分，共10题，每小题2分)1. 7 2. X 3. X 4. X 5. J 6. V 7. J 8. J 9. J 10. V四、计算题（20分,共4题，每小题5分）1.参考答案：f g(x)=2 (x2+l)=2x2+3g f(x)= K(x2+l) 3 2+l=4x 2+4x+2f f(x)=2(2x+l)+l=4x+3g g(x)= K (x2+l)3 2+1=x 4+2x2+2 所以f g= |x&Rg f=|x Rf f
11、= | xGRg g=x, x 4+2x 2+2 | xR解题方案：评分标准：2.参考答案：R=(x, y) |x, yA,且 x2y=(1, 1), (2, 1), (3, 1), (4,1), (2,2), (3,2), (4, 2), (3, 3), (4, 3), (4, 4) R的关系图如图3-1所小。国3-1 R的关系国10 0 0110 011101111解题方案：评分标准：3.参考答案：-I (PVQ) 一 (PAQ)=(-(PVQ) - (PAQ) ) A( (PAQ) -1 (PVQ)(等值律)=(PVQ) V (PAQ) ) A(n (PAQ) Vn (PVQ)(蕴涵律)
12、=(PVQ) A(n PV-i q)(分配律)合取范式= (-1 PVP) V(-)PVQ) V(n QAP) V(n QAQ)(分配律)析取范式方案: 评分标准:4.参考答案：(1) AG B=a, d A c, d = d.(2) (AAB) U-C=a U a, c, e = a, c, e.(3) AU (BC) = b, c, e U a, e = a, b, c, e. P (A) = (|), a, d, a, d.P (B) = (|), a, b e a, b, a, e, b, e, a, b, e 故 P (A) n p (B)=体，a解题方案:评分标准:五、证明题（10
13、分，共2题，每小题5分）参考答案：5(x)： x是科学家。Z)(x)： x是勒奋的。H(x)： x是身体健康的。qx)： x是成功的。论域 是入。bx)(S(x)-。(x), (Vx)(Z)(a-)AZ/(x)-*C(x), (Ex)(5(x) A/7(x)= (Ex)C(x)VCE.vh C (x)证明；(1)(5 八 H(x)p敏a)/H(a)ES(1)演)T(2)I如)T(2)I(Vx)(S(x)-D(x)P(6)演)fa)US(5)驯T(3)(6)I(Vx)(D(x)A/f(x)-Q：x)P2a)八 H(a)rC(a)US(8)(10)0)T(4)(7)(9)I(10(三必)EG(10)(12)(*x)vca)T(H)I解题方案：评分标准：2.参考答案：证明：VxZ, (x-x)/2=0,即R,故 R 是自反的。方案: 评分标准: