离散数学导论(第5版)-第五篇
- 格式:ppt
- 大小:254.50 KB
- 文档页数:45
离散数学第五章习题答案题目1: 定义一个关系R在集合A上,如果对于所有的a, b, c属于A,满足以下条件:- 如果(a, b)属于R,则(b, a)属于R。
- 如果(a, b)属于R且(b, c)属于R,则(a, c)属于R。
证明R是传递的。
答案:根据题目给出的条件,R是对称的和传递的。
首先,对称性意味着如果(a, b)属于R,那么(b, a)也必须属于R。
其次,传递性意味着如果(a, b)和(b, c)都属于R,那么(a, c)也必须属于R。
结合这两个性质,我们可以得出结论:对于任意的a, b, c属于A,如果(a, b)和(b, c)都属于R,那么(a, c)也属于R,从而证明了R的传递性。
题目2: 给定一个函数f: A → B,如果对于A中的每个元素a,都有唯一的b属于B使得f(a) = b,那么称f为单射(或一一映射)。
证明如果函数f是单射,那么它的逆函数f^-1也是单射。
答案:要证明f^-1是单射,我们需要证明对于B中的任意两个元素b1和b2,如果f^-1(b1) = f^-1(b2),则b1 = b2。
假设f^-1(b1) = a且f^-1(b2) = a',其中a, a'属于A。
由于f是单射,我们知道f(a) = b1且f(a') = b2。
根据f^-1的定义,我们有b1 = f(a) = f(a') = b2。
因此,如果f^-1(b1) = f^-1(b2),则b1必须等于b2,这证明了f^-1是单射。
题目3: 证明一个函数f: A → B是满射(或到上映射)当且仅当对于B中的每个元素b,都存在A中的元素a使得f(a) = b。
答案:首先,我们证明如果f是满射,那么对于B中的每个元素b,都存在A 中的元素a使得f(a) = b。
假设f是满射,这意味着B中的每个元素都是A中某个元素的像。
因此,对于B中的任意元素b,我们可以找到一个a属于A,使得f(a) = b。
离散数学第五版习题答案【篇一:自考2324离散数学第五章课后答案】txt>5.1习题参考答案1、设无向图g有16条边,有3个4度结点,4个3度结点,其余结点的度数均小于3,问:g中至少有几个结点。
阮允准同学提供答案:解:设度数小于3的结点有x个,则有解得:x≥4所以度数小于3的结点至少有4个所以g至少有11个结点2、设无向图g有9个结点,每个结点的度数不是5就是6,证明:g中至少有5个6度结点或至少有6个5度结点。
阮允准同学答案:证明:由题意可知:度数为5的结点数只能是0,2,4,6,8。
若度数为5的结点数为0,2,4个,则度数为6的结点数为9,7,5个结论成立。
若度数为5的结点数为6,8个,结论显然成立。
由上可知,g中至少有5个6度点或至少有6个5度点。
3、证明:简单图的最大度小于结点数。
阮同学认为题中应指定是无向简单图.晓津证明如下:设简单图有n个结点,某结点的度为最大度,因为简单图任一结点没有平行边,而任一结点的的边必连有另一结点,则其最多有n-1条边与其他结点相连,因此其度数最多只有n-1条,小于结点数n.4、设图g有n个结点,n+1条边,证明:g中至少有一个结点度数≥3 。
阮同学给出证明如下:证明:设g中所有结点的度数都小于3,即每个结点度数都小于等于2,则所有结点度数之和小于等于2n,所以g的边数必小于等于n,这和已知g有n+1条边相矛盾。
所以结论成立。
5、试证明下图中两个图不同构。
晓津证明:同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。
我们可以看出,(a)图和(b)图中都有一个三度结点,(a)图中三度结点的某条边关联着两个一度结点和一个二度结点,而(b)图中三度结点关联着两个二度结点和一个一度结点,因此可断定二图不是同构的。
6、画出所有5个结点3条边,以及5个结点7条边的简单图。
解:如下图所示: (晓津与阮同学答案一致)7、证明:下图中的图是同构的。
证明如下:在两图中我们可以看到有a→e,b→h,c→f,d→g两图中存在结点与边的一一对应关系,并保持关联关系。
离散数学(第五版)清华大学出版社第5章习题解答5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨分析S 为n 元集,那么S×S有n2个元素.S 上的一个二元运算就是函数n2n2f:S×S→S.这样的函数有n 个.因此{a,b}上的二元运算有n =16个.下面说明通过运算表判别二元运算性质及求特导元素的方法.1 °交换律若运算表中元素关于主对角线成对称分布,则该运算满足交换律.2 °幂等律设运算表表头元素的排列顺序为x1,x2,Lxn,如果主对角线元素的排列也为x1,x2,Lxn,则该运算满足幂等律.其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特征,只能针对所有可能的元素x,y,z等来验证相关的算律是否成立.3 °幺元e设运算表表头元素的排列顺序为x1.,x2,Lxn,如果元素xi所在的行和列的元素排列顺序也是x1,x2,Lxn,则xi为幺元.4 °零元θ.如果元素xi所在的行和列的元素都是xi,则xi是零元.5 °幂等元.设运算表表头元素的排列顺序为x1,x2,Lxn,如果主对角线上第i个元素恰为xii∈{1,2,L,n}那么xi是幂等元.易见幺元和零元都是幂等元.6 °可逆元素及其逆元.设xi为任意元素,如果xi所在的行和列都有幺元,并且这两个幺元关于主对角线成对称分布,比如说第i行第j列和第j行第i列的两个位置,那么xj与xi互为逆元.如果xi所在的行和列具有共同的幺元,则幺元一定在主对角线上,那么xi的逆元就是xi自己.如果xi所在的和地或者所在的列没有幺元,那么x 不是可逆元素.不难看出幺元e一定是可逆元素,且e−1=e;而i零元θ不是可逆元素.以本题为例,f1,f2,f3的运算表是对称分布的,因此,这三个运算是可交换的,62而f4不是可交换的.再看幂等律.四个运算表表头元素排列都是a,b,其中主对角线元素排列为a,b的只有f4,所以, f4遵从幂等律.下面考虑幺元.如果某元素所在的行和列元素的排列都是a,b,该元素就是幺元.不难看出只有f2中的a满足这一要求,因此,a 是f2的幺元,其他三个运算都不存在幺元.最后考虑零元.如果a所在的行和列元素都是a,那么a就是零元;同样的,若b所在的行和列元素都是b,那么b 就是零元.检查这四个运算表,f1中的a满足要求,是零元,其他运算都没有零元.在f4的运算表中,尽管a和b的列都满足要求,但行不满足要求.因而f4中也没有零元.5.2 A:①; B:③; C:⑤; D:⑦; E:⑩分析对于用解析表达式定义的二元运算°和*,差别它们是否满足交换律,结合律,幂等律,分配律和吸收律的方法总结如下:任取x,y,根据°运算的解析表达式验证等式xoy=yox是否成立.如果成立°运算就满足交换律.2 ° °运算的地合律任取x,y,z根据°运算的解析表达式验证等式(xoy)oz=xo(yoz)是否成立. 如果成立, °运算就是可结合的.3 ° °运算的幂等律任取x,根据°运算的解析表达式验证等式xox=x是否成立.如果成立,°运算满足幂等律.4 ° °运算对*运算的分配律任取x,y,z , 根据°和* 运算的解析表达式验证等式xo(y*z)=(xoy)*(xoz)和(y*z)ox=(yox)*(zox)是否成立。
离散数学第五版课后习题答案离散数学是一门重要的数学学科,它研究的是离散对象和离散结构的性质和关系。
离散数学的应用广泛,涉及计算机科学、信息科学、通信工程、运筹学等领域。
而《离散数学》第五版是离散数学领域的经典教材,它详细介绍了离散数学的基本概念、方法和应用。
在学习离散数学的过程中,课后习题是非常重要的一部分。
通过解答习题,可以巩固理论知识,培养分析问题和解决问题的能力。
然而,由于离散数学的习题种类繁多,难度不一,很多学生在自学或课后复习时会遇到一些困难。
因此,提供《离散数学第五版》课后习题的答案可以帮助学生更好地学习和掌握相关知识。
首先,我们来看一下《离散数学第五版》课后习题的类型。
该教材的习题分为多个章节,每个章节都包含了基本概念、定理和算法的习题。
这些习题涵盖了集合论、逻辑、证明方法、图论、代数结构、计数原理等多个方面的内容。
习题的难度也有所不同,有一些是基础题,有一些是拓展题,还有一些是应用题。
通过解答这些习题,学生可以逐步提高自己的能力,掌握离散数学的核心概念和方法。
接下来,我们来讨论一下为什么提供《离散数学第五版》课后习题的答案是有意义的。
首先,课后习题的答案可以帮助学生检查自己的解答是否正确。
在学习过程中,学生可能会遇到一些难以理解或容易出错的问题,通过对比答案,可以及时发现和纠正错误,提高学习效果。
其次,答案还可以作为学生学习的参考,帮助他们理解问题的解题思路和方法。
有时候,学生可能会陷入思维定势,无法找到问题的突破口,而参考答案可以给他们一些启示和思路。
最后,答案还可以作为学生自学的辅助材料,帮助他们进行自主学习和巩固知识。
然而,提供《离散数学第五版》课后习题的答案也存在一些问题和挑战。
首先,习题的答案可能存在多种解法,因此提供一个标准答案并不容易。
不同的学生可能会有不同的思路和方法,他们的解答也可能会有所不同。
其次,习题的答案可能会涉及一些复杂的推理和证明过程,这些过程可能需要较长的篇幅来解释和讨论。
第五章函数Function函数在数学、应用数学等许多领域,尤其计算机科学领域有着极其重要的作用。
函数的思想、概念和应用无处不在,无时不在。
它主要是研究变量之间的关系和规律。
函数的划分有很多种。
有线性与非线性之分、连续与离散之分。
例如,kx x f y ==)( 2211)(x c x c x g y +== bx ce x h y ==)(5.1 函数假定A ,B 是两个非空集合,f : A→B ,称f 为A 到B 上的函数,对每个a ∈A , 有唯一的f (a)∈B, 记做b = f(a)。
函数也叫映射mappings 或变换transformations (错误)a 叫做函数f 的自变量argument ,b 被称为因变量,b=f (a)叫做函数的值value ,也叫a 的像。
例1. A ={1,2,3,4}, B={a,b,c,d},c d a a B A f →→→→→4,3,2,1,:,则 f 是一个函数。
也可以简单记为,f ={(1,a), (2,a), (3,d), (4,c)}另外,ca b a A B g →→→→→4,2,1,1,: g={(1,a), (1,b), (2,a), (4,c)}因为对于1来说,1∈A , 不是唯一的f (1)∈B 与之相对应, f (1)=a, 并且f (1)=b, 因此g 就不是一个函数。
例2.f :Z→Z ,f (a)=⎩⎨⎧是奇数是偶数a if a if 1f 是函数。
例3. 恒等函数1A (a)=a 是函数。
正如,我们在第四章里表述的,函数 f : A→B ,b=f(a), 是一个特殊的二元关系,我们知道,由函数f 可以确定一个关系f R ,简单地,可以表示为(a,b)∈f R ,或 a f R b 。
关系fR 的特征函数为 ⎩⎨⎧==否则0)(1),(a f b b a R f 或者简记为⎩⎨⎧==否则0)(1),(a f b b a f 因此,这样一来,我们以前所讨论的有关集合或关系的运算和性质对于函数来说,就可以完全适用。