北大2013年春离散数学课件作业.doc

2013年春离散数学课件作业
第一部分 集合论
第一章 集合的基本概念和运算
1-1 设集合 A ={{1，2}，a，4，3}，下面命题为真是 （选择题） [ B ]
A．2 ∈A； B．1 ∈ A； C．3 ∈A； D．{1，2} A。

1-2 A,B,C　为任意集合，则他们的共同子集是 （选择题） [ D ]
A．C； B．A； C．B； D． Ø 。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否正确 （是非题）
（1） N Q，Q ∈S，则 N S，　　　　　　　　　　　　　　　　　 ［ X ］
（2）-1 ∈Z，Z ∈S， 则 -1 ∈S 。　　　　　　　　　　　　　　　　　［ X ］

1-4 设集合 B = {4，3} ∩ Ø ， C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，
E = {x│x ∈R 并且 x2 - 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 }（选择题） [ D ]
A. N; B. Z; C. Q; D. Z+

1-6 为何说集合的确定具有任意性 ? (简答题)
集合：是按照一定的明确的标准，把一定范围内的事物分类归总!
这里的元素的地位都是平等的，没有位置关系区别，这就是集合的无序性。
而集合反映了的一个思路，就是不重不漏，所有的元素都要出现，而且只能出现一次，就是集合的唯一性。

第二章 二元关系
2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：
R = {〈x，y〉x，y ∈X 且 x = y } （综合题）
求：(1)domR =?; (2)ranR =?; (3)R 的性质。
答：R = {<2，3>，<1,2>，<1,3>}；
DomR={R中所有有序对的x}={2,1,1}={2,1};
RanR={R中所有有序对的y}={3,2,3}={3,2}；
R 的性质:反自反,反对称,传递性质.

2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即
R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}，
试给出 dom（R 。R）。 （选择题） [ B ]
A. 3； B. {3}； C. 〈3，3〉； D.{〈3，3〉}。

2-3 判断下列映射 f 是否是 A 到 B 的函数； 以及函数的性质。最后指出 f：A→B
中的双射函数。 （选择题） [ B ]
（1）A = {1，2，3}，B = {4，5}， f = {〈1，4〉〈2，4〉〈3，5〉}。
（2）A = {1，2，3} = B， f = {〈1，1〉〈2，2〉〈3，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 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝ [ C ]　　　　　　
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 ]
A．不构成代数系统； B．只是代数系统。； C． 半群； 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}，二元运算 * 是普通乘法。 [ B ]
A．不能构成代数系统； B．半群； C．独异点； D．群。

3-2 在自然数集合上，下列那种运算是可结合的　　　 　　　　　　　 ［ A ］
A．x*y = max(x,y) ； B．x*y = 2x+y ；
C．x*y = x2+y2 ； D．x*y =︱x-y︱..

3-3 设 N 为自然数集合，在 N 上定义二元运算 。，对于所有 x，y ∈N 都有
x 。y = x - y
试问？在 N 上二元运算 。能否构成代数系统，何种代数系统？为什麽 ？（综合题）

第二部分 图论方法
第四章 图 以下三题分别为： 选择题 是非题 填空题
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 个顶点。[ ∨ ]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为　 2 。

第五章 树
5-1 概述无向图与无向树的关系。 （简答题）

5-2 握手定理的应用（指无向树） （计算题）
（1） 在一棵树中有 7 片树叶，3个3 度顶点，其余都是4 度顶点，共几个顶点
[有1个4度顶点,即：1+7+3 = 11 ]
（2） 一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有几片叶
[9 个 1 度顶点 ]

5-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} [X ]
B4 = {1，11，101，001，0011} [ X ]

5-5 11 阶无向连通图 G 中有 17 条边，其任一棵生成树 T 中必有6条树枝 [ X ]

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）= ； 3、每个字母的码字；

第三部分 逻辑推理理论
第六章 命题逻辑
6-1 判断下列语句是否命题，简单命题或复合命题。 （填空题）
（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 用等值演算法求下列命题公式的主析取范式，并由此指出该公式的类型
（1）﹃（p→q）∧ q <=> 0，永假式； （计算题）

（2）（（p→q）∧ p）→q <=> Σ（0，1，2，3），永真式； （计算题）

（3）（p→q）∧ q <=> Σ（1，3），可满足式。 （计算题）

6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为 　[ B ]
A． p→q； B． q→p； C． p∧q； D． ﹁q→﹁p

6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为 ［ A ］
A． p→q； B． q→p； C． p∧q； D． ﹁q→p

6-6 将下列推理命题符号化，然后用不同方法判断推理结果是否正确。（综合题）
如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。
首先将原子命题符号化，然后，按题意将原子命题组织成公式。再用不同方法，例如用
等值演算法判断推理的正确与否。公式是重言式，所以，推理正确。
方法 1：等值演算法（（p→﹃q）∧p）→﹃q ﹤＝﹥1；
方法 2: 主范式法(略);
方法 3: 真值表法(略);
方法 4：构造证明法,如下:
将公式分成前提及结论。
前提：（p→﹃q），p；
结论：﹃q；
证明： （1）（p→﹃q） 前提引入
（2） p 前提引入
（3）（p→﹃q）∧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彐z（x-y = z）的真值为　 1
题解与分析：本题应特别注意域．因为在整数范围内，ｘ,y可取任何数，都有z存在．

7-3 在谓词逻辑中将下列命题符号化 （填空题）
人固有一死。 x（M（x）→ F（x）） 。

7-4 一阶逻辑与命题逻辑有何联系？ 举例说明。 （简答题）
例如：每个人都会死。命题逻辑中的 P 变成一阶逻辑中的 x（M（x）→ F（x））。
一阶逻辑是区别于高阶逻辑的数理逻辑，它不允许量化性质。性质是一个物体的特性；所以一个红色物体被表述为有红色的特性。命题逻辑以逻辑运算符结合原子命题来构成代表“命题”的公式，以及允许某些公式建构成“定理”的一套形式“证明规则”。

《附录》习题符号集
Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 ,
－ 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，量词 ”所有”，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”。