离散数学
2020-03-03 17:53:40 来源：范文大全收藏下载本文
离散数学课件作业
第一部分 集合论
第一章集合的基本概念和运算
1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是[ B ]
A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{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［不成立］
（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}，
试问哪两个集合之间可用等号表示 ？
答：A = E；B = C；D = F
1-5 用列元法表示下列集合
（1）A = { x│x ∈N 且 x2 ≤ 9 }
（2）A = { x│x ∈N 且 3－x 〈 3 }
答：（1）A = { 0，1，2，3 }；
（2）A = { 1，2，3，4，……} = Z+；
第二章二元关系
2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：
R = {〈x，y〉x，y ∈X 且 x≤ y }
求：(1)domR =?;(2)ranR =?;(3)R 的性质。
答：R = {，，}；
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}，试求：
（1）R 的列元表达式； （2）给出 dom（R 。R）。
答：根据方程式有：y=4-x/3，x 只能取 3，6,9。
（1）R = {〈3，3〉,〈6，2〉,〈9，1〉}；
至于(2),望大家认真完成合成运算 R 。R={}.然后,给出 R 。R 的定义域,即
（2）dom（R 。R）= {3}。
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 。
答：（1）是 A 到 B 的函数，是满射而不是单射；
（2）是双射；
（3）是双射；
（4）是单射，而不是满射；
（5）是单射而不是满射。
2-4 设 A ={1，2，3，4}，A 上的二元关系
R ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：A→A/R使 g(1) =[C]
A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。
2-5 设 A ={1，2，3}，则商集A/IA =[D]
A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝ 。
2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝[C]
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}，二元运算 * 是普通乘法。
答：（1）二元运算*在S1上不封闭．所以，＂S1，*＂不能构成代数系统。
（2）由二元运算的定义不难知道，。在 S2 内是封闭的，所以，〈S2， 。〉构成代数
系统；然后看该代数系统的类型：该代数系统只是半群。
（3）很明显，〈{0，1}，*〉构成代数系统；满足结合律，为半群；1是幺元，为独异
点；而 0 为零元；结论：仅为独异点，而不是群。
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 设 Z 为整数集合，在 Z 上定义二元运算 。，对于所有 x，y ∈Z都有
x 。y=x + y ，
试问〈Z，。〉能否构成群，为什麽 ？
答：由题已知，集合Z满足封闭性；二元运算满足结合律，依此集合Z为半群；有幺元为 －5，为独异点.假设代数系统的幺元是集合中的元素 e,则一个方程来自于二元运算定义, 即e 。x= e + x，一个方程来自该特殊元素的定义的性质,即e 。x = x.由此而来的两个方程联立结果就有: e+x=x 成立.削去 x,e=0 的结果不是就有了吗!；每个元素都有逆.求每个元素的逆元素,也要解联方程,如同求幺元一样的道理；结论是：代数系统〈 Z，。〉构成群。
第二部分图论方法
第四章 图
4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ？ 答：因为10阶完全图的每个顶点的度数都是n-1=9――为奇数。这样一来，一个无向简单图 G 的某顶点的度数是奇数，其补图的相应顶点必偶数，因为一个偶数与一个奇数之和才是奇数．所以，Ｇ的补图中应有 10-4＝6 个奇数度顶点。
4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点.[是]
4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为[2]
第五章树
5-1握手定理的应用（指无向树）
（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有(有1个4度顶点)个？
（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有(9个1度顶点)片？
5-2 一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶(即一度顶点)，问树叶多少片？设有x片,则 x=
答：假设有 x 片树叶，根据握手定理和树的顶点与边数的关系，有关于树叶的方程，解方程得到树叶数 x = Σi（i—2） i + 2，（i = 2，3，……k）。
5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1） T 的权 W（T）？（2）树高几层 ？
答：用 Huffman 算法，以 1，2，3，5，7，8 为权，最优 2 元树 T ；然后，计算并回答所求问题：（1）T 的权 W（T）= 61；（2）树高几层：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(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [非]
5-6(是非判断题)二元正则树有奇数个顶点。[是]
5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.求传输他们的最佳前缀码。
1、最优二元树 T；2.每个字母的码字；
答：每个字母出现频率分别为：G、D、B、E、Y：14%，O：28%；(也可以不归一,某符号
出现次数即为权，如右下图).。100（近似）7.。563..
4。。282..2..2。..1..14141414111
1所以，得到编码如下：G（000），D（001），B（100），E（101），
Y（01），O（11）。
第三部分逻辑推理理论
第六章 命题逻辑
6-1 判断下列语句是否命题，简单命题或复合命题。
（1）2月 17 号新学期开始。[真命题]
（2）离散数学很重要。[真命题]
（3）离散数学难学吗 ？[真命题]
（4）C 语言具有高级语言的简洁性和汇编语言的灵活性。[复合命题]
（5）x + 5 大于 2 。[真命题]
（6）今天没有下雨，也没有太阳，是阴天。[复合命题]
6-2 将下列命题符号化.
（1）2 是偶素数。
（2）小李不是不聪明，而是不好学。
（3）明天考试英语或考数学。（兼容或）
（4）你明天不去上海，就去北京。（排斥或）
答：（1）符号化为： p ∧ q。
（2）符号化为：p ∧ ﹃q。
（3）符号化为：p ∨ q。
（4）符号化为：（﹃p ∧ q）∨（p ∧ ﹃q）。
6-3分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.
（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。 答：（1） 0；
（2）Σ（0，1，2，3）；
（3）Σ（1，3）。
以下两题(6-4;6-5)为选择题,将正确者填入[]内.
6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为[B]
A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p
6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为［B］
A． p→q；B．q→p；C．p∧q；D．﹁q→p
6-6证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。
如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。 答：将公式分成前提及结论。
前提：（p→﹃q），p；
结论：﹃q；
证明：（1）（p→﹃q）前提引入
（2） p前提引入
（3）（p→﹃q）∧p（1）（2）假言推理
（4）﹃q
要证明的结论与证明结果一致，所以推理正确。
第七章谓词逻辑
7-1 在谓词逻辑中用 0 元谓词将下列命题符号化
（1）这台机器不能用。
（2）如果 2 ＞ 3，则 2 ＞ 5。
答：（1）﹃F（a）。
（2）L（a，b）→ H（a，z）。
7-2 填空补缺题：设域为整数集合Ｚ，命题xy彐z（x-y=z）的真值为 （0）
7-3在谓词逻辑中将下列命题符号化
（1）有的马比所有的牛跑得慢。
（2）人固有一死。
答：（1）符号化为：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。
（2）与（1）相仿，要注意量词、联结词间的搭配：
x（F（x）→y（G（y）→ H（x，y）））。
《附录》习题符号集
Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 , － 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，量词 ”所有”，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”。
2010年8月12号。
相关推荐
人人范文网 m.inrrp.com.cn 手机版