北京大学2012秋离散数学课件作业

1、精选优质文档-倾情为你奉上 2012秋离散数学课件作业 第一部分 集合论第一章 集合的基本概念和运算 1-1 设集合 A =1，2，a，4，3，下面命题为真是 （选择题） C A2 A； B1 A； C3 A； D1，2 A。1-2 A,B,C为任意集合，则他们的共同子集是 （选择题） D AC； BA； CB； D Ø 。1-3 设 S = N，Z，Q，R，判断下列命题是否正确 （是非题）（1） N Q，Q S，则 N S， 错 （2）-1 Z，Z S， 则 -1 S 。 错 1-4 设集合 B = 4，3 Ø ， C = 4，3 Ø ，D = 3，4，

2、6; ，E = xx R 并且 x2 - 7x + 12 = 0，F = 4，Ø ，3，3，试问：集合 B 与那个集合之间可用等号表示 （选择题） A A. C; B. D; C. E; D. F.1-5 用列元法表示下列集合A = xx N 且 3x 3 （选择题）题解与分析：本题以谓词给出集合的表达式。要求把解析表达式所含的元素列出；有的集合的元素需要通过计算才能得到，如下：A = 1，2，3，4， 所以选 D A. N; B. Z; C. Q; D. Z+第二章 二元关系 2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下： R = x，yx，y X

3、且 x y （综合题）求：(1)domR =?; (2)ranR =?; (3)R 的性质。答：由题可得R=<2,3>,<1,2>,<1,3>Ix;（1） DomR = R中所有有序对的x =3,2,1;（2） ranR = R中所有有序对的y =3,2,1;（3） R的性质：自反，反对称，传递性质。2-2 设 R 是正整数集合上的关系，即 R = x，yx，y Z+ 且 x + 3y = 12， （选择题）试给出 dom（R 。R）。 B A. 3； B. 3； C. 3，3； D.3，3。2-3 判断下列映射 f：AB 中的双射函数。 （选择题） B （

4、1）A = 1，2，3，B = 4，5， f = 1，42，43，5。（2）A = 1，2，3 = B， f = 1，12，23，3。（3）A = B = R， f = x 。（4）A = B = N， f = x2 。（5）A = B = N， f = x + 1 。A.（1）和（2）； B.（2）和（3）； C.（3）和（4）； D.（4）和（5）2-4 设 A =1，2，3，4，A 上的二元关系 R =x，y（x-y）能被3整除，则自然映射 g：AA/R使 g(1) = C A1,2； B1,3； C1,4； D1。2-5 设 A =1，2，3，则商集A/IA = D A3； B2； C

5、1； D1，2，3。2-6设(x)x+1，(x)x-1 都是从实数集合到的函数，则。 C Ax+1； Bx-1； Cx； Dx2。 第三章 结构代数(群论初步) (3-1)，(3-2)为选择题3-1 给出集合及二元运算，判断是否代数系统，何种代数系统 ？（1）S1 = 1，1/4,1/3,1/2,2，3，4，二元运算 * 是普通乘法。（2）S2 = a1，a2，an，ai R，i = 1，2，n ；二元运算 。定义如下：对于所有 ai，aj S2，都有 ai 。aj = ai 。（3）S3 = 0，1，二元运算 * 是普通乘法。（1）二元运算*在S1上不封闭所以，S1，*不能构成代数系统。 所

6、以选 A A不构成代数系统； B只是代数系统。； C 半群； D群。（2）由二元运算的定义不难知道，。在 S2 内是封闭的，所以，S2， 。构成代数系统；然后看该代数系统的类型：该代数系统只是半群。 所以选 C A不能构成代数系统； B只是代数系统； C半群； D群。（3）很明显，0，1，*构成代数系统；满足结合律，为半群；1是幺元，为独异点；而 0 为零元；结论：仅为独异点，而不是群。 所以选 C A不能构成代数系统； B半群； C独异点； D群。3-2 在自然数集合上，下列那种运算是可结合的 A Ax*y = max(x,y) ； Bx*y = 2x+y ；Cx*y = x2+y2 ； D

7、x*y =x-y.3-3 设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y Z 都有 x 。y = x - y 试问Z，。能否构成群，为什麽 ？ （综合题）答：第一步由题已知，此二元运算中,只有加法,在集合 Z 中必然满足封闭性；第二步，二元运算满足结合律，以决定半群；第三步，有幺元为 4，为独异点.假设代数系统的幺元是集合中的元素 e,则一个方程来自于二元运算定义, 即e 。x = e + x - 4，一个方程来自该特殊元素的定义的性质,即e 。x = x.由此而来的两个方程联立结果就有: e+x = x 成立.削去 x,e = 4 的结果不是就有了吗!；第四步，每个元素都有

8、逆.求每个元素的逆元素,也要解联方程,如同求幺元理：设y是x的逆，则一个方程为 y 。x = y + x - 4,另一个方程为y 。x = 4,联立结果得到 y = 8-x；第五步，结论是：代数系统 Z，。构成群。 第二部分 图论方法第四章 图 （选择题，是非题，填空题）4-1 10个顶点的简单图G中有4个奇度顶点，G的补图中有r个偶数度顶点。 C Ar =10 ； Br = 6； Cr = 4； Dr = 9。4-2 无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有几个顶点. 8个顶点4-3 1条边的图 G 中，所有顶点的度数之和为 2 。第五章 树 （5-1），（5-2）为 计

9、算题5-1 握手定理的应用（指无向树）（1）在一棵树中有7片树叶，3个3 度顶点，其余都是4度顶点，全树几个顶点 11 （2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有几片叶 9 5-2 一棵树中有 i 个顶点的度数为 i（=2，k），其余顶点都是树叶，问树叶多少片？答：假设有 x 片树叶，根据握手定理和树的顶点与边数的关系，有关于树叶的方程，解方程得到树叶数 x = i（i2） i + 2，（i = 2，3，k）。5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。问：权 W（T）= 61 ；树高 4 层。（填空题）

10、5-4 以下给出的符号串集合中，那些是前缀码 （以下是非题） B1 = 0，10，110，1111； 是 B2 = 1，01，001，000； 是 B3 = a，b，c，aa，ac，aba，abb，abc 非 B4 = 1，11，101，001，0011 非 5-5 11 阶无向连通图 G 中有 17 条边，其任一棵生成树 T 中必有6条树枝 非 5-6 二元正则树有奇数个顶点。 是 5-7 通信中 a，b，c，d，e，f,g,h 出现的频率分别为 35%;20%;15%.10%,10%,5%,3%,2%; 求传输他们的最佳前缀码。 （综合题） 1、最优二元树 T； 2、二元树的权 W（T）；

11、 3、 每个字母的码字；答： 。a 。100 。40 60。 。b 15。 30。 。20 10。 。f 。 。 。 。 g h d e 7. 3. .4 2. . 2. .2 . . 1 . . 1 1 1 1编码如下：g（00000），h（00001），f（0001），d（100），e（101）,c(001),b(11),a(01)。 第三部分 逻辑推理理论第六章 命题逻辑 6-1 判断下列语句是否命题，简单命题或复合命题。 （填空题）（1）2月 17 号新学期开始。 （ 是简单 ）命题（2）离散数学很重要。 （ 是简单 ）命题（3）离散数学难学吗 ？ （ 不是 ）命题（4）C 语言具有高

12、级语言的简洁性和汇编语言的灵活性。（ 是复合 ）命题（5）x + 5 > 2 。 （ 不是 ）命题（6）今天没有下雨，也没有太阳，是阴天。 （ 是复合 ）命题6-2 将下列命题符号化. （填空题）（1）2 是偶素数。 p q （2）小李不是不聪明，而是不好学。 p q （3）明天考试英语或考数学。（兼容或） p q 6-3 求下列命题公式的主析取范式，并由此指出该公式的类型（等值演算）（1）（pq） q <=> 0，永假式。（2）（pq） p）q <=> （0，1，2，3），永真式。 （3）（pq） q <=> （1，3），可满足式。6-4 令 p：经

13、一堑；q：长一智。命题只有经一堑，才能长一智符号化为 B A pq； B qp； C pq； D qp6-5 p：天气好；q：我去游玩命题 ”如果天气好，则我去游玩” 符号化为 A A pq； B qp； C pq； D qp6-6 将下列推理命题符号化，然后用不同方法判断推理结果是否正确。（综合题）如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。答：方法 1：等值演算法（pq）p）q 1；方法 2: 主范式法(略);方法 3: 真值表法(略);方法 4：构造证明法,如下: 将公式分成前提及结论。 前提：（pq），p； 结论：q； 证明： （1）（pq） 前提引入 （2） p 前提引入（3）（pq）p （1）（2）假言推理 （4）q 扣题：要证明的结论与证明结果一致，所以推理正确。 第七章 谓词逻辑 7-1 在谓词逻辑中用 0 元谓词将下列命题符号化 （填空题）（1）这台机器不能用。 F（a） 。 （2）如果 2 3，则 2 5。 L（a，b） H（a，z） 。 7-2 设域为整数集合，命题xy彐