【数学】15春北京大学《离散数学》作业答案

1、精品word可编辑资料- - - - - - - - - - - - -2021春课件作业第一部分 集合论第一章集合的基本概念和运算1-1设集合 a =2，3,4 ，5，1 ，下面命题为真是（挑选题） c a1 a；b2 a； c 3 a； d 3 ，2,1a；1-2 a,b,c为任意集合，就他们的共同子集是（挑选题） d ac；ba；cb；d .；1-3 设 s = n ，z，q，r，判定以下命题是否正确（是非题）（ 1） nq，q s，就 ns，错（ 2） -1 z， z s， 就 -1s ；错1-4设集合 b = 4， 3 .， c = 4 ， 3 . ， d = 3 ， 4， . ，e

2、 = x x r 并且 x 2 - 7x + 12 = 0，f = 4，.，3，3 ，试问：集合 b 与那个集合之间可用等号表示（挑选题） a a. c;b. d;c. e;d. f.1-5 用列元法表示以下集合： a = xx n 且 3 x 3 （挑选题） da. n;b. z;c. q;d. z+1-6 为何说集合的确定具有任意性.简答题其次章二元关系2-1 给定 x = （3, 2 ， 1）， r 是 x 上的二元关系，其表达式如下：r = x，yx， y x 且 x y （综合题） 求： 1domr =.;2ranr =.;3r的性质；r= ， ， ix ；(1) domr=r中全部

3、有序对的 x=3,2,1; 2ranr=r中全部有序对的 y=3,2,1； 33r的性质: 自反, 反对称, 传递性质 .2-2 设 r 是正整数集合上的关系，由方程x + 3y = 12打算，即r = x，y x， yz+ 且 x + 3y = 12，试给出 dom（r ；r）；（挑选题） b a. 3 ；b. 3；c.3，3；d.3， 3 ；2-3 判定以下映射 f是否是 a 到 b 的函数； 以及函数的性质；最终指出 f ：ab 中的双射函数；（ 挑选题） b （ 1） a = 1 ， 2， 3 ， b = 4 ， 5 ，f = 1，42，43， 5 ；（ 2） a = 1 ， 2， 3

4、 = 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）第 1 页，共 5 页- - - - - - - - - -3-1给出集合及二元运算，判定是否代数系统，何种代数系统？（ 1） s1 = 1 ，1/4,1/3,1/2,2，3，4 ，二元运算 *是一般乘法； aa不构成代数系统；b只是代数系统；c 半群；d群；（ 2） s2 = a1 ，a2， an ，air，i = 1，

5、2， n ；二元运算 ；定义如下：对于全部 ai ，ajs2，都有 ai；aj = ai； c a不构成代数系统；b只是代数系统；c 半群；d群；3-2 在自然数集合上，以下那种运算是可结合的 a ax*y = maxx,y；bx*y = 2x+y；3-3 设 z为整数集合，在 z上定义二元运算 ；，对于全部 x ， y z都有x；y = x - y试问？在 z上二元运算；能否构成代数系统，何种代数系统？为什麽？（ 综合题） 假设代数系统的幺元是集合中的元素e, 就一个方程来自于二元运算定义,即e ；x = e + x - 4，一个方程来自该特别元素的定义的性质,即e ；x = x. 由此而来

6、的两个方程联立结果就有 : e+x = x 成立.设y是x的逆，就一个方程为 y ；x = y + x - 4, 另一个方程为 y ；x = 4,联立结果得到 y = 8-x ；结论是：代数系统 z，；构成群；其次部分图论方法第四章 图 以下三题分别为：挑选题是非题填空题4-1 10 个顶点的简洁图 g中有 4 个奇度顶点，问 g 的补图中有 r个偶数度顶点； car =10 ；b r = 6；c r = 4；d r = 9；4-2 是非判定： 无向图 g中有 10 条边 ,4 个 3 度顶点 , 其余顶点度数全是2, 共有 8 个顶点； 是 4-3 填空补缺： 1 条边的图 g 中，全部顶点

7、的度数之和为2；第五章树第 2 页，共 5 页- - - - - - - - - -精品word可编辑资料- - - - - - - - - - - - -2-4 设 x x+1， x x-1 都是从实数集合到的函数，就； c ax+1；bx-1；c x；dx2；2-5 关系型数据库与关系与函数一章内容有何联系 ？（简答题）答：关系数据库，是建立在关系模型基础上的数据库，借助于集合代数和各种函数关系等数学概念和方法来处理数据库中的数据，现实世界中的各种实体以及实体之间的各种联系均用关系模型来表示；第三章 结构代数 群论初步 3-1， 3-2 为挑选题（ 3） s3 = 0 ，1 ，二元运算*是

8、一般乘法； ca不能构成代数系统；b半群；c独异点；d群；cx*y = x 2+y2 ；dx*y = x-y.精品word可编辑资料- - - - - - - - - - - - -5-1概述无向图与无向树的关系；（简答题）答：连通而不含回路的无向图称谓无向树；（1）生成树的定义 - 生成子图概念；（ 2） 生成子图与母图的关系 - 定点数相同；（ 3）何种图采纳生成树 - 连通图；（ 4）连通图中的那种永久不会进入任何一颗生成树中 - 环；（ 5）连通图中的那种边必定会进入其生成树中- 桥；5-2握手定理的应用（指无向树）（运算题）（ 1）在一棵树中有 7 片树叶， 3个3 度顶点，其余都是

9、 4 度顶点，共几个顶点11（ 2）一棵树有两个 4 度顶点， 3 个 3 度顶点，其余都是树叶，问有几片叶95-3求最优 2元树：用 huffman算法求带权为1 ，2，3，5，7，8 的最优 2元树t ；试问： t 的权 w（ t）= 61；树高 4层； （ 填空题）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

10、中必有 6 条树枝 非 5-6 二元正就树有奇数个顶点；是 5-7 通信中 a ，b，c，d，e，f,g,h显现的频率分别为 25%;20%;20%.15%,10%,5%,4%,1%;试完成以下要求；（综合题）；10060；30；a15；c1、最优二元树 t ； 2、二元树的权 w（t）=； 3、每个字母的码字；4010 ；20；b； ； f；ghde编码如下： g（ 00000），h（ 00001），f（ 0001），d（ 100），e（101）,c001,b11,a01；第六章 命题规律第三部分规律推理理论6-1 判定以下语句是否命题，简洁命题或复合命题；（ 填空题）第 3 页，共 5 页

11、- - - - - - - - - -精品word可编辑资料- - - - - - - - - - - - -（1）2月 17号新学期开头；（是简洁）命题（2） 离散数学很重要；（是简洁）命题（3） 离散数学难学吗 ？（不是）命题（4）c 语言具有高级语言的简洁性和汇编语言的敏捷性（是复合）命题（5）x + 5 2；（不是）命题（6）今日没有下雨，也没有太阳，是阴天；（是复合）命题6-2 将以下命题符号化 .（填空题）（1）2 是偶素数；符号化为： p q ；（2） 小李不是不聪慧，而是不好学；符号化为： p q；（3） 明天考试英语或考数学；（兼容或）符号化为： p q ；6-3用等值演算法

12、求以下命题公式的主析取范式，并由此指出该公式的类型（ 1）（ pq） q（运算题）（ 2）（ pq） p ）q（运算题）（ 3）（ p q） q（运算题）（ 1） 0，永假式；（ 2）（ 0， 1， 2， 3），永真式；（ 3）（ 1，3），可满意式；6-4令 p：经一堑； q：长一智；命题 只有经一堑，才能长一智 符号化为ba p q；b qp；c p q；d qp6-5 p：天气好； q：我去游玩命题 ”假如天气好，就我去游玩 ”符号化为 aa p q；b qp；c p q；d qp6-6 将以下推理命题符号化，然后用不同方法判定推理结果是否正确；（综合题） 假如今日不下雨，就明天上体育课

13、；今日没有下雨；所以，明天上体育课；题解与分析：第一将原子命题符号化，然后，按题意将原子命题组织成公式；再用不同方法，例如用等值演算法判定推理的正确与否；公式是重言式，所以，推理正确；方法 1 ：等值演算法 略方法 2:主范式法 略;方法 3:真值表法 略;方法 4 ：构造证明法 , 如下:（1） ）将原子命题符号化：（2） ）按题意构成前提：第 4 页，共 5 页- - - - - - - - - -精品word可编辑资料- - - - - - - - - - - - -（3） ）按题意构成结论：（4） ）证明：方法 1 ：等值演算法（ pq） p） q 1； 方法 2:主范式法 略;方法

14、3:真值表法 略;方法 4 ：构造证明法 , 如下:将公式分成前提及结论；前提：（ p q）， 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）；（1）f（a）；（2）l（a， b） h（ a， z）；7-2 填空题： 设域为整数集合 z ，命题xy彐z（x-y = z ）的真值为17-3 在谓词规律中将以下命题符号化（ 填空题）人固有一死；x（m（x） f（ x）；7-4 一阶规律与命题规律有何联系？举例说明；（简答题）附录习题符号集.空集,