北京大学2016秋课件作业离散数学【答案】

C．独异点；
3-2 在自然数集合上，下列那种运算是可结合的 A．x*y = max(x,y) ； B．x*y = 2x+y ； 2 2 C．x*y = x +y ； D．x*y =︱x-y︱..
［ A ］
3-3 设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y ∈Z 都有 x 。y = x - y 试问？在 Z 上二元运算 。能否构成代数系统，何种代数系统？为什麽 ？（综合题） 答 判定和讨论特殊元素及其对代数结构的作用，整数上的减法运算满足封闭性， 才能构成代数系统，当然要满足群的定义条件，整数上的减法运算只构成一般代数系统， 而不构成半群，更不构成群。
2-4 设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝ A．x+1； B．x-1； C．x； D．x2。 2-5 关系型数据库与《关系与函数》一章内容有何联系 ？（简答题） 答 关系与函数一章的内容是关系型数据库的理论基础 第三章 结构代数(群论初步) (3-1)，(3-2)为选择题 3-1 给出集合及二元运算，判断是否代数系统，何种代数系统 ？ （1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 * 是普通乘法。 A．不构成代数系统； B．只是代数系统。； C． 半群；
结论：﹃q； 证明： （1）（p→﹃q） 前提引入 （2） p 前提引入 （3）（p→﹃q）∧p （1）（2）假言推理 （4）﹃q 扣题：要证明的结论与证明结果一致，所以推理正确。
ቤተ መጻሕፍቲ ባይዱ
第七章 谓词逻辑 7-1 在谓词逻辑中用 0 元谓词将下列命题符号化 （1）1 不是素数。 ﹃F（a） L（a，b）→ H（a，c）
]
]
C．B；
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 E = {x│x ∈R 并且 x - 7x + 12 = 0}，F = { 4，Ø ，3，3}， 试问：集合 B 与那个集合之间可用等号表示 （选择题） [ A A. C; B. D; C. E; D. F. 1-5 用列元法表示下列集合：A = { x│x ∈N 且 3－x 〈 3 }（选择题） + A. N; B. Z; C. Q; D. Z [ D
2-3 判断下列映射 f 是否是 A 到 B 的函数； 中的双射函数。 （1）A = {1，2，3}，B = {4，5}， f （2）A = {1，2，3} = B， f （3）A = B = R， f （4）A = B = N， f （5）A = B = N， f A.（1）和（2）； B.（2）和（3）；
]
]
1-6 为何说集合的确定具有任意性 ? (简答题) 答 按研究的问题来确定集合的元素。 我们所要研究的问题当然是随意的呗。 之所以， 集合的定义（就是集合成分的确定）当然带有任意性哪。 第二章 二元关系 2-1 给定 A =（3, 2，1），R 是 A 上的二元关系，其表达式如下： R = {〈x，y〉x，y ∈A 且 x ＝ y } （综合题） 求：(1)domR =?; (2)ranR =?; (3)R 的性质。 （4）商集 A/R =？ （5）A 的划分∏=？ （6）合成运算（R 。R）=？ 求商集的时候，一定明白关系 R 的性质--等价关系。若R不是等价关系，请留心我对本 题的讨论，工作中也许会有用处。至于合成运算，应该掌握。 无论题中是否要求，都要把关系的元素列出： R = {<1,2>,<1,3>,<2,3>，<1，1>，<2，2>，<3，3>}； (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={2,1,3}； (3)R 的性质:自反,反对称,传递性质.这时，R 不是等价关系。 （4）商集A/R = {{1，2，3}，{2，3}，{3}}。由于R 不是等价关系，所以，等价类之间 出现交集。这是不允许的。请看下面的划分问题。 （5）A的划分∏={{1，2，3}，{2，3}，{3}}；也由于R不是等价关系，造成划分的荒谬 结果：出现交集。试问：让“3”即参加第一组，又参加第二组，她该如何分配呢！！！ 所以，关系 R 必须是等价关系。至于作业中，此两题应说：因为R 不是等价关系， 此题无解。 （6）合成运算R。R = {<1,1>,<3,3>,<2,2>，<1，2>，<1，3>，<2，3>}； 2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即 R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}， 试给出 dom（R 。R）。 （选择题） [ B ]
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）= 270 ； 3、每个字母的码 字；
（6）今天没有下雨，也没有太阳，是阴天。 6-2 将下列命题符号化. （1）2 是偶素数。 p ∧ q。
（
是复合
）命题 （填空题）
（2）小李不是不聪明，而是不好学。
p ∧ ﹃q。
（3）明天考试英语或考数学。（兼容或） p ∨ q。 6-3 用等值演算法求下列命题公式的主析取范式，并由此指出该公式的类型 （1）﹃（p→q）∧ q 0，永假式 （计算题） （2）（（p→q）∧ p）→q （3）（p→q）∧ q Σ（0，1，2，3）永真式 Σ（1，3）可满足式 （计算题） （计算题） ]
6-6 将下列推理命题符号化，然后用不同方法判断推理结果是否正确。（综合题） 如果今天不下雨，则明天上体育课。今天没有下雨。所以，明天上体育课。 题解与分析：首先将原子命题符号化，然后，按题意将原子命题组织成公式。再用不 同方法，例如用等值演算法判断推理的正确与否。公式是重言式，所以，推理正确。 方法 1：等值演算法(略) 方法 2: 主范式法(略); 方法 3: 真值表法(略); 方法 4：构造证明法,如下: （1）将原子命题符号化： （2）按题意构成前提： （3）按题意构成结论： （4）证明： 答 如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。 题解与分析：首先将原子命题符号化，然后，按题意将原子命题组织成公式。再用不 同方法，例如用等值演算法判断推理的正确与否。公式是重言式，所以，推理正确。 方法 1：等值演算法（（p→﹃q）∧p）→﹃q ﹤＝﹥1； 方法 2: 主范式法(略); 方法 3: 真值表法(略); 方法 4：构造证明法,如下: 将公式分成前提及结论。 前提：（p→﹃q），p；
第二部分
图论方法
第四章 图 以下三题分别为： 选择题 是非题 填空题 4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有 r 个偶数度顶点。[ C ] A．r =10 ； B．r = 6； C．r = 4； D．r = 9。
4-2 是非判断：无向图 G 中有 10 条边,4 个 3 度顶点,其余顶点度数全是 2,共有 8 个顶点。[ 是 ]
（填空题） 。 。 1
（2）如果 2 ＞ 3，则 2 ＞ 5。
7-2 填空题：设域为整数集合 Z，命题 x y彐z（x-y = z）的真值为 7-3 在谓词逻辑中将下列命题符号化 人固有一死。
x（M（x）→ F（x））
（填空题） 。
7-4 一阶逻辑与命题逻辑有何联系？ 举例说明。 （简答题） 答 把命题逻辑中的符号化的命题，把句子成分展示出来，并按句子成分符号化，就 变成一阶逻辑中的公式了。例如：每个人都会死。命题逻辑中的 P 变成一阶逻辑中的 x（M（x）→ F（x））。 《附录》习题符号集 Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 , － 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非， 量词 ”所有”，”每个”， ∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”，∏划分。 2016年9月1号.
6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为 [B A． p→q； B． q→p； C． p∧q； D． ﹁q→﹁p 6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为 ［ A． p→q； B． q→p； C． p∧q； D． ﹁q→p
A ］
第三部分
逻辑推理理论
（填空题） （ 是简单 ）命题 ）命题 ）命题 ）命题 ）命题
第六章 命题逻辑 6-1 判断下列语句是否命题，简单命题或复合命题。 （1）2月 17 号新学期开始。 （2）离散数学很重要。 （3）离散数学难学吗 ？
（是简单 （ 不是 是复合 不是
（4）C 语言具有高级语言的简洁性和汇编语言的灵活性（ （5）x + 5 > 2 。 （
4-3 填空补缺：1 条边的图 G 中，所有顶点的度数之和为
2
。
第五章 树 5-1 概述无向图与无向树的关系。 （简答题） 答 （1）生成树的定义---生成子图概念；（2）生成子图与母图的关系----顶点数相 同； （3）何种图才有生成树----连通图；（4）连通图中的那种边永远不会进入任何一颗生 成树中---环。（5）连通图中的那种边必然会进入其生成树中---桥。 5-2 握手定理的应用（指无向树） （计算题） （1）在一棵树中有 7 片树叶，3个3 度顶点，其余都是4 度顶点，共几个顶点 [ 11 ] （2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有几片叶 [9 ] 5-3 用 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 （是非题） [是 ] [是 ] [非 ] [非 ] [非 [是 ] ]
2016秋课件作业【答案】
第一部分 集合论 第一章 集合的基本概念和运算 1-1 设集合 A ={{2，3,4}，5，1}，下面命题为真是 A．1 ∈A； B．2 ∈ A； C．3 ∈A； 1-2 A,B,C 为任意集合，则他们的共同子集是 A．C； B．A；
（选择题） [ A D．{3，2,1} A。 （选择题） D． Ø （是非题） [ D 。
[ A ] D．群。
（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ； 二元运算 。定义如下：对于所有 ai，aj ∈S2，都有 ai 。aj = ai 。 [ C ] A．不构成代数系统； B．只是代数系统。； C． 半群； D．群。 （3）S3 = {0，1}，二元运算 * 是普通乘法。 A．不能构成代数系统； B．半群； [ C ] D．群。
A. 3；
B. {3}；
C. 〈3，3〉；
D.{〈3，3〉}。 以及函数的性质。最后指出 f：A→B （选择题） [ B ] = {〈1，4〉〈2，4〉〈3，5〉}。 = {〈1，1〉〈2，2〉〈3，3〉}。 = x 。 2 = x 。 = x + 1 。 C.（3）和（4）； D.（4）和（5） [ C]