北京大学16秋季《离散数学》课程作业

1、精选优质文档-倾情为你奉上 2016秋课件作业 第一部分 集合论第一章 集合的基本概念和运算 1-1 设集合 A =2，3,4，5，1，下面命题为真是 （选择题） A1 A； B2 A； C3 A； D3，2,1 A。1-2 A,B,C为任意集合，则他们的共同子集是 （选择题） 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，Ø ，E = xx

2、 R 并且 x2 - 7x + 12 = 0，F = 4，Ø ，3，3，试问：集合 B 与那个集合之间可用等号表示 （选择题） A. C; B. D; C. E; D. F.1-5 用列元法表示下列集合：A = xx N 且 3x 3 （选择题） A. N; B. Z; C. Q; D. Z+1-6 为何说集合的确定具有任意性 ? (简答题)第二章 二元关系 2-1 给定 A =（3, 2，1），R 是 A 上的二元关系，其表达式如下： R = x，yx，y A 且 x y （综合题）求：(1)domR =?; (2)ranR =?; (3)R 的性质。 （4）商集 A/R =？ （

3、5）A 的划分=？ （6）合成运算（R 。R）=？ 2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即 R = x，yx，y Z+ 且 x + 3y = 12，试给出 dom（R 。R）。 （选择题） A. 3； B. 3； C. 3，3； D.3，3。2-3 判断下列映射 f 是否是 A 到 B 的函数； 以及函数的性质。最后指出 f：AB 中的双射函数。 （选择题） （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 =

4、 N， f = x2 。（5）A = B = N， f = x + 1 。A.（1）和（2）； B.（2）和（3）； C.（3）和（4）； D.（4）和（5）2-4 设(x)x+1，(x)x-1 都是从实数集合到的函数，则。 Ax+1； Bx-1； Cx； Dx2。 2-5 关系型数据库与关系与函数一章内容有何联系 ？（简答题）第三章 结构代数(群论初步) (3-1)，(3-2)为选择题3-1 给出集合及二元运算，判断是否代数系统，何种代数系统 ？（1）S1 = 1，1/4,1/3,1/2,2，3，4，二元运算 * 是普通乘法。 A不构成代数系统； B只是代数系统。； C 半群； D群。（2）

5、S2 = a1，a2，an，ai R，i = 1，2，n ；二元运算 。定义如下：对于所有 ai，aj S2，都有 ai 。aj = ai 。 A不构成代数系统； B只是代数系统。； C 半群； D群。（3）S3 = 0，1，二元运算 * 是普通乘法。 A不能构成代数系统； B半群； C独异点； D群。3-2 在自然数集合上，下列那种运算是可结合的 Ax*y = max(x,y) ； Bx*y = 2x+y ；Cx*y = x2+y2 ； Dx*y =x-y.3-3 设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y Z 都有 x 。y = x - y 试问？在 Z 上二元运算

6、。能否构成代数系统，何种代数系统？为什麽 ？（综合题） 第二部分 图论方法第四章 图 以下三题分别为： 选择题 是非题 填空题4-1 10 个顶点的简单图G中有4个奇度顶点，问 G 的补图中有 r 个偶数度顶点。 Ar =10 ； Br = 6； Cr = 4； Dr = 9。4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点。 4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为 。第五章 树 5-1 概述无向图与无向树的关系。 （简答题）5-2 握手定理的应用（指无向树） （计算题）（1）在一棵树中有 7 片树叶，3个3 度顶点，其余都是4 度

7、顶点，共几个顶点 （2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有几片叶 5-3 用 Huffman 算法求带权为 1，2，3，5，7，8 的树叶的最优 2 元树 T。（填空题）试问：T 的权 W（T）= ( )；树高 ( ) 层。 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 二元正则树

8、有奇数个顶点。 5-7 通信中 a，b，c，d，e，f,g,h 出现的频率分别为 25%;20%;20%.15%,10%,5%,4%,1%; 试完成下列要求。 （综合题） 1、最优二元树 T； 2、二元树的权 W（T）= ； 3、每个字母的码字； 第三部分 逻辑推理理论第六章 命题逻辑 6-1 判断下列语句是否命题，简单命题或复合命题。 （填空题）（1）2月 17 号新学期开始。 （ ）命题（2）离散数学很重要。 （ ）命题（3）离散数学难学吗 ？ （ ）命题（4）C 语言具有高级语言的简洁性和汇编语言的灵活性（ ）命题（5）x + 5 > 2 。 （ ）命题（6）今天没有下雨，也没有太

9、阳，是阴天。 （ ）命题6-2 将下列命题符号化. （填空题）（1）2 是偶素数。 （2）小李不是不聪明，而是不好学。 （3）明天考试英语或考数学。（兼容或） 6-3 用等值演算法求下列命题公式的主析取范式，并由此指出该公式的类型（1）（pq） q （计算题） （2）（pq） p）q （计算题） （3）（pq） q （计算题）6-4 令 p：经一堑；q：长一智。命题只有经一堑，才能长一智符号化为 A pq； B qp； C pq； D qp6-5 p：天气好；q：我去游玩命题 ”如果天气好，则我去游玩” 符号化为 A pq； B qp； C pq； D qp6-6 将下列推理命题符号化，然后用

10、不同方法判断推理结果是否正确。（综合题）如果今天不下雨，则明天上体育课。今天没有下雨。所以，明天上体育课。题解与分析：首先将原子命题符号化，然后，按题意将原子命题组织成公式。再用不同方法，例如用等值演算法判断推理的正确与否。公式是重言式，所以，推理正确。方法 1：等值演算法(略)方法 2: 主范式法(略);方法 3: 真值表法(略);方法 4：构造证明法,如下: （1）将原子命题符号化： （2）按题意构成前提： （3）按题意构成结论： （4）证明： 第七章 谓词逻辑 7-1 在谓词逻辑中用 0 元谓词将下列命题符号化 （填空题）（1）1 不是素数。 。 （2）如果 2 3，则 2 5。 。 7-2 填空题：设域为整数集合 Z，命题xy彐z（x-y = z）的真值为 7-3 在谓词逻辑中将下列命题符号化 （填空题）人固有一死。 。 7-4 一阶逻辑与命题逻