2012-2013下11级普本离散数学卷参考答案

1、第二师范学院 2012 2013 学年度第二 学期离散数学课程参考（ B 卷）方式： 闭 卷（开卷、闭卷）命题教师： 计算机科学与技院、系：计算机学院专业班级：11 计科 1-3 班，12 计科 5 班注：参考需写清题号、每小题分值、参考要点、评分标准等一、判断题（每小题 1 分，共 14 分）二、单项选择题（每小题 2 分，共 30 分）三、综合题（每小题 5 分，共 40 分）1. 求下列集合的幂集（1）解：P() = ，（2）A=a, b, c 解：P(A) = ，c，a, b，A2 分3 分2. 设 p：（1）努力学习 q：取得好成绩，试将下列命题符号化。取得好成绩，如果她努力学习。解

2、：pq2 分（2）只有努力学习，她才能取得好成绩。解：q p3 分3. 试将下列命题符号化（1）在卖菜的人不全是东北人。解：设 F(x)：x 在卖菜，G(x)：x 是东北人，则命题可符号化为： x(F(x) G(x)（或 x(F(x) G(x) ）2 分12345678910111213CCCBCACADACBD1234567891011121314（2）有的汽车比有的火车快。解：设 F(x)：x 是汽车，G(x)：x 是火车，H(x, y)：x 比 y 快则命题可符号化为： xy ( F(x) G(y) H(x, y)3 分4. 试给出A = 1, 2, 3 上的所有等价关系。解：R1= ，

3、 IAR2= ， IAR3= ， IAR4=IAR5=EA5 分（酌情给分）5. 设 R 为实数集，f：RR，f (x) = x2 x + 2，g：RR，g (x) = x -4。（1）求复合函数 f g，g f解：f g (x) = g (f(x) = g (x2 x + 2) = x2 x + 2 -4 = x2 x -2g f (x) = f (g(x) = f ( x 4) = (x-4)2 (x-4) +2 = x2 9x +221 分1 分（2）求 g (x) 的反函数。g-1 (x) = yg(y) = x，又 g(y) = y-4解：设则所以由 y-4 = x,y = x+4g

4、-1 (x) = x+43 分（酌情给分）即6.画出以 1, 1, 1, 2, 2, 3 为度数列的 3 个非同构的无向简单图。解：作图如下：5 分（酌情给分）7.说明理由。的两个图 G1，G2 是否同构，若两图同构，写出顶点之间的对应关系，若不同构，则解：（1）不同构2 分（2）图 G2 中有 3 个顶点分别不相邻，如：2，3，4；但图 G1 中没有 3 个不相邻的顶点。即图 G1 与图 G2 结构不一样。3 分（酌情给分）G1G28. 已知一棵无向树T 中有 4 度，3 度，2 度的分支结点各一个，其余的顶点均为树叶，问 T 中有几片树叶？解：设T 中有x 片树叶，m 条边，n 个结点，由

5、树的特性：m = n-1所以 m = 3+x-11 分2 分a1bcd234ef56由握手定理：2m = 2(3+x-1) = 4+3+2+x，解得：x = 5四、证明题（每小题 5 分，共 20 分。）2 分1. 在自然推理系统 P 中，构造下面推理的证明。如果他是计算机本科生或者是计算机，那么他一定学过 C 语言而且学过 C+语言。只要他学过 C 语言或者 C+语言，那么他就会编程序。因此如果他是计算机本科生，那么他就会编程序。（注意：字母按 p, q, r, s, t 的顺序符号化。）p：他是计算机系本科生 q：他是计算机系r：他学过DELPHI 语言 s：他学过 C+语言 t：他会编程

6、序前提：(pq)(rs)，(rs)t结论：pt解：令2 分1 分证：p pq(pq)(rs)rs r rs(rs)ttPP(附加前提)附加(前提引入) 假言推理 化简 附加P (前提引入) 假言推理2 分证明等值式 x ( F(x) G(x) ) x ( F(x) G(x) ) 成立。2.x (F(x) G(x) )x ( F(x) G(x) )x (F(x) G(x) )x ( F(x) G(x) )证明：命题得证。1 分2 分2 分（量词否定等值式）（蕴含等值式）（德律）设 R 是集合 A 上的自反关系，证明 RR-1 是A 上的自反关系。证明： 对 x，若 x A，由条件，则 R R R R-1 x( R R-1 ) RR-1所以，RR-1 是 A 上的自反关系。命题得证。3.2 分3 分（酌情给分）设 f：AB，g：BC 是两个函数，证明：若f g 是单射，则 f 是单射。证明： 由条件 f g：A C 且 f g 是单射，对 a1，a2 A，