2013-2014上12级普本《离散数学》A卷参考答案.doc

20132014上计算机学院离散数学试卷A参考答案湖北第二师范学院2013 2014 学年度第 一 学期离散数学课程考试参考答案（ A卷）考试方式： 闭 卷 （开卷、闭卷）命题教师： 刘志明 院、系： 计算机学院 专业班级：计算机科学与技术12计科1, 2, 3,4,6班12信管，12教技班 注：参考答案需写清题号、每小题分值、参考答案要点、评分标准等一、 判断题（每小题1分，共14分）1234567891011121314二、 单项选择题（每小题2分，共30分）12345678910111213DCCBDBDCAAAAC三、 综合题（每小题5分，共40分）1. 求下列集合的幂集（1）解：P() = , 2分（2）A= , 解：P(A) = , , , , 3分2. 设p：明天下雨q：明天开运动会，下列命题符号化。（1） 解：pq 2分（2）解：p q 3分3. 试将下列命题符号化（1）在NBA打球的人不全是美国人。 解：设F(x)：x在NBA打球，G(x)：x是美国人，则命题可符号化为：x(F(x) G(x) 2分（或$x(F(x) G(x) ） （2）火车都比汽车快。 解：设F(x)：x是火车，G(x)：x是汽车，H(x, y)：x比y快则命题可符号化为：xy ( (F(x) G(y) H(x, y) 3分（或x( F(x)y (G(y) H(x, y) )） 4. 解： R= , , , R2= , , , 5分（酌情给分） 5. 设R为实数集，f：RR，f (x) = x2 + x + 1，g：RR，g (x) = x +1。（1）求复合函数f g，g f 解：f g (x) = g (f(x) = g (x2 + x + 1) = x2 + x + 1 + 1 = x2+ x +2 1分g f (x) = f (g(x) = f ( x+1) = (x+1)2+ (x+1) + 1 = x2 +3x +3 1分（2）求g (x) 的反函数。 解：设 g-1 (x) = y 则 g(y) = x，又 g(y) = y+1 所以由y+1 = x, y = x-1 即g-1 (x) = x-13分（酌情给分）6. 画出下图的补图，并判断原图与补图是否同构。解：补图如下：同构，aa,bd,ce,dc,eb5分（酌情给分）7. 求下图的最小生成树。解：作图如下：5分（酌情给分）8. 解答：（1）最优二元树如下图： 3分 最优前缀码为：A:11 B:01 C:100 D:101 E:001 F:0001 G:0000 2分四、证明题（每小题5分，共20分。）1. 在自然推理系统P中，构造下面推理的证明。如果小王是理科生，她一定学过微积分。如果她不是文科生，她一定是理科生。她没学过微积分，所以她是文科生。（注意：要标识每一步的推理定律）解答：（1）：简单命题符号化 P:小王是理科生 Q：小王学过微积分 R：小王是文科生 （2）构造推理系统：前提：PQ,RP,Q.结论：R（3） 证明：Q 前提引入 PQ 前提引入 P 拒取 RP 前提引入 R 拒取 5分（酌情给分）2. 证明等值式 x ( M(x) F(x) ) $ x ( M(x) F(x) ) 成立。证明：左边 x ( M(x) F(x) ) $x ( M(x) F(x) )$x ( M(x) F(x) )$ x ( M(x) F(x) )右边 5分（酌情给分）3. 设R是集合A上的关系，证明:sr(R)=rs(R)。证明：对任意,sr(R)r(R)r(R)-1r(R)r(R)-1(IAR)(IAR)-1IARIA-1R-1IARR-1IAs(R)rs(R) 5分（酌情给分）4. 设 f：AB，g：BC是两个函数，证明：若是f ，g都是单射，则f g是单射。证明：假设存在x1,x2A,使得f g（x1）=f g（x2）由合成定理有g（f （x1）)=g（f (