离散数学(第1次)解析

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分，共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)e