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

1、2021春课件作业第一部分集合论第一章集合的基本概念和运算1-1设集合 a =2，3,4 ，5，1 ，下面命题为真是（挑选题 ） c a1 a；b2 a ；c3 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 = xx r 并 且 x 2 - 7x + 12 = 0，f = 4，.，3

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

3、的 x=3,2,1;(2) ranr=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 = b，f

4、= 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 设 x x+1， x x-1 都是从实数集合到的函数，就； ca x+1；bx-1；c x；dx2；2-5 关系型数据库与关系与函数一章内容有何联系？ （简答题）答：关系数据库，是建立在关系模型基础上的数据库，借助于集合代数和各种函数关系等数学概念和方法来处理数据库中的数据，现实世界中的各种实体以及实体之间的各种联系均用关系模型来

5、表示；第三章结构代数 群论初步 3-1， 3-2 为挑选题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， 2， n ；二元运算；定义如下：对于全部ai ，ajs2，都有 ai；aj = ai；c a 不构成代数系统；b只是代数系统；c半群；d群；（ 3） s3 = 0 ，1 ，二元运算*是一般乘法； ca 不能构成代数系统；b半群；c独异点；d群；3-2 在自然数集合上，以下那种

6、运算是可结合的 aa x*y = maxx,y；bx*y = 2x+y；cx*y = x 2+y2；dx*y = x-y .3-3设 z为整数集合，在z上定义二元运算；，对于全部x ， yz都有x；y=x - y试问？在 z上二元运算；能否构成代数系统，何种代数系统？为什麽？（ 综合题 ）假设代数系统的幺元是集合中的元素e, 就一个方程来自于二元运算定义,即e ；x = e + x - 4，一个方程来自该特别元素的定义的性质,即e ；x = x. 由此而来的两个方程联立结果就有: e+x = x 成立.设y是x的逆，就一个方程为y ；x= y + x - 4, 另一个方程为y ；x= 4,联立

7、结果得到y = 8-x ；结论是：代数系统z，；构成群；其次部分图论方法第四章图以下三题分别为：挑选题是非题填空题4-1 10 个顶点的简洁图g中有 4 个奇度顶点，问g 的补图中有r个偶数度顶点； ca r =10；b r = 6；c r = 4；d r = 9；4-2 是非判定： 无向图 g中有 10 条边 ,4 个 3 度顶点 , 其余顶点度数全是2, 共有 8 个顶点； 是4-3 填空补缺： 1 条边的图g 中，全部顶点的度数之和为2；第五章树5-1 概述无向图与无向树的关系；（简答题）答：连通而不含回路的无向图称谓无向树；（1）生成树的定义 - 生成子图概念；（ 2）生成子图与母图的

8、关系- 定点数相同；（ 3）何种图采纳生成树- 连通图；（ 4）连通图中的那种永久不会进入任何一颗生成树中- 环；（ 5）连通图中的那种边必定会进入其生成树中- 桥；5-2 握手定理的应用（指无向树）（运算题）（ 1）在一棵树中有7片树叶， 3个3 度顶点，其余都是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 =

9、 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显现的频率分别为25%;20%;20%.15%,10%,5%,4%,1%;试完成以下要求；（综合题）1、最优二元树t ；2、二元树的权w（t）=；3、每个字母的码字；10060；30；a；4015；c10 ；20；b；f；ghde编码如下：

10、 g（ 00000），h（ 00001），f（ 0001），d（ 100），e（101）,c001,b11,a01；第六章命题规律第三部分规律推理理论6-1判定以下语句是否命题，简洁命题或复合命题；（ 填空题 ）（1）2月 17号新学期开头；（是简洁）命题（2）离散数学很重要；（是简洁）命题（3）离散数学难学吗？（不是）命题（4）c 语言具有高级语言的简洁性和汇编语言的敏捷性（是复合）命题（5）x + 5 > 2；（不是）命题（6）今日没有下雨，也没有太阳，是阴天；（是复合）命题6-2将以下命题符号化.（填空题 ）（1）2 是偶素数；符号化为：p q ；（2）小李不是不聪慧，而是不好学；

11、符号化为： p q；（3）明天考试英语或考数学；（兼容或）符号化为： p q ； 6-3用等值演算法求以下命题公式的主析取范式，并由此指出该公式的类型（ 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；cp q；dqp6-5 p：天气好； q：我去游玩命题”假如天气好，就我去游玩”符号化为aa p q；b qp；cp q；dqp6-6 将以下推理

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

13、公式分成前提及结论；前提：（ p q）， p； 结论： q；证 明 ： （1）（ p q）前提引入（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 一阶规律与命题规律有何联系？举例说明