离散数学课件作业

离散数学课件作业

离散数学课件作业

第一部分 集合论

第一章 集合的基本概念和运算

1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是 [ ]

A．2 ∈A； B．1 ∈ A； C．5 ∈A； D．{2} A。

1-2 A,B 为任意集合，则他们的共同子集是 [ ]

A．A； B．B； C．A∪B； D． Ø 。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否成立 ？

（1） N Q，Q ∈S，则 N S ［ ］

（2）-1 ∈Z，Z ∈S， 则 -1 ∈S ［ ］

1-4 设集合 A ={3，4}，B = {4，3} ∩ Ø ， C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，

2E = {x│x ∈R 并且 x - 7x + 12 = 0}，F = { 4，Ø ，3，3}，

试问哪两个集合之间可用等号表示 ？

1-5 用列元法表示下列集合

2（1）A = { x│x ∈N 且 x ≤ 9 }

（2）A = { x│x ∈N 且 3－x 〈 3 }

第二章 二元关系

2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：

R = {〈x，y〉x，y ∈X 且 x ＜ y }

求：(1)domR =?; (2)ranR =?; (3)R 的性质。

2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即

R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}，试求：

（1）R 的列元表达式； （2）给出 dom（R 。R）。

2-3 判断下列映射 f 是否是 A 到 B 的函数；并对其中的 f：A→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 。

2-4 设 A ={1，2，3，4}，A 上的二元关系

R ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：A→A/R使 g(1) = [ ]

A．｛1,2｝； B．｛1,3｝； C．｛1,4｝； D．｛1｝。

2-5 设 A ={1，2，3}，则商集A/IA = [ ]

A．｛3｝； B．｛2｝； C．｛1｝； D．｛｛1｝，｛2｝，｛3｝｝ 。

2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝ [ ]

离散数学课件作业

A．x+1； B．x-1； C．x； D．x2。

第三章 结构代数(群论初步)

3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ？

（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 * 是普通乘法。

（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；

二元运算 。定义如下：对于所有 ai，aj ∈S2，都有 ai 。aj = ai 。

（3）S3 = {0，1}，二元运算 * 是普通乘法。

3-2 在自然数集合上，下列那种运算是可结合的 ［ ］

A．x*y = max(x,y) ； B．x*y = 2x+y ；

C．x*y = x2+y2 ； D．x*y =︱x-y︱..

3-3 设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y ∈Z 都有 x 。y = x + y ，

试问〈Z，。〉能否构成群，为什麽 ？

第二部分 图论方法

第四章 图

4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ？

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点. [ ]

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

第五章 树

5-1 握手定理的应用（指无向树）

（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有( )个？

（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有( )片？

5-2 一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶(即一度顶点)，

问树叶多少片？设有x片,则 x=

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。

试问：（1） T 的权 W（T）？ （2）树高几层 ？

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(是非判断题)二元正则树有奇数个顶点。 [ ]

5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.

求传输他们的最佳前缀码。

1、最优二元树 T； 2.每个字母的码字；

第三部分 逻辑推理理论

第六章 命题逻辑

6-1 判断下列语句是否命题，简单命题或复合命题。

（1）2月 17 号新学期开始。 [ ]

（2）离散数学很重要。 [ ]

（3）离散数学难学吗 ？ [ ]

（4）C 语言具有高级语言的简洁性和汇编语言的灵活性。 [ ]

（5）x + 5 大于 2 。 [ ]

（6）今天没有下雨，也没有太阳，是阴天。 [ ]

6-2 将下列命题符号化.

（1）2 是偶素数。

（2）小李不是不聪明，而是不好学。

（3）明天考试英语或考数学。（兼容或）

（4）你明天不去上海，就去北京。（排斥或）

6-3 分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.

（1）﹃（p→q）∧ q； （2）（（p→q）∧ p）→q； （3）（p→q）∧ q。

以下两题(6-4;6-5)为选择题,将正确者填入[ ]内.

6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为 [ ]

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

6-6 证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。

如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。

第七章 谓词逻辑

7-1 在谓词逻辑中用 0 元谓词将下列命题符号化

（1）这台机器不能用。

（2）如果 2 ＞ 3，则 2 ＞ 5。

7-2 填空补缺题：设域为整数集合Ｚ，命题 x y彐z（x-y=z）的真值为 （ ）

7-3 在谓词逻辑中将下列命题符号化

（1）有的马比所有的牛跑得慢。

（2）人固有一死。

《附录》习题符号集

离散数学课件作业

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

2010年2月20号。