离散数学课件作业

离散数学课件作业

第一部分集合论

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

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

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

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，?}，
E= {x│x∈R并且x2- 7x + 12 = 0}，F= { 4，?，3，3}，
试问哪两个集合之间可用等号表示？

1-5用列元法表示下列集合
（1）A= { x│x∈N且x2≤9 }
（2）A= { x│x∈N且3－x〈3}
第二章 二元关系

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

指出他的性质，即是否单射、满

射和双射，并说明为什么。

f= {〈1，4〉〈2，4〉〈3，

f= {〈1，1〉〈2，2〉〈3，

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

第三章结构代数(群论初步)
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在自然数集合上，下列那种运算是可结合的 ］［

B．x*y= 2x+y ；
D．x*y=︱x-y︱..

个偶数度顶点？

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-5p：天气好；q：我去游玩．命题”如果天气好，则我去游玩”

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号。