离散数学例题分析精选文档.ppt

离散数学例题分析本讲稿第一页，共三十七页例题分析例题分析 一、选择（102）1下述式子错误的是（）下述式子错误的是（）ABCD答案答案 C 本讲稿第二页，共三十七页例题分析例题分析 答案答案 C 2若若 是是A上的等价关系，则上的等价关系，则 不是（）不是（）A自反的自反的B对称的对称的C反自反的反自反的D传递的传递的本讲稿第三页，共三十七页例题分析例题分析 答案答案 D 3已知已知 ,试问试问 为为:（）（）A内射内射B满射满射C双射双射D非内射、非满射非内射、非满射本讲稿第四页，共三十七页例题分析例题分析 4 为一个代数系统，下列说法不正确的是（）。为一个代数系统，下列说法不正确的是（）。A若若*有左单位元有左单位元 且有右单元且有右单元 ，那么，那么*有单位元，有单位元，B若若*有左零元有左零元 和右零元和右零元 ，那么，那么*有零元有零元 。C若若*有元数有元数a对对*有左逆元，有左逆元，和右逆元和右逆元 ，则，则a有逆元有逆元 。D 若为群，则若为群，则*只有单位元而没有零元。只有单位元而没有零元。答案答案 C本讲稿第五页，共三十七页例题分析例题分析 答案答案 C 5下列能构成独异点的是（）下列能构成独异点的是（）A（N；+）B（N；-）C（N；）D（N；|）本讲稿第六页，共三十七页例题分析例题分析 答案答案 6如果（如果（）为一个格，那么二元运算）为一个格，那么二元运算 不一定满不一定满 足（）足（）A交换律交换律B结合律结合律C吸收律吸收律D分配律分配律本讲稿第七页，共三十七页例题分析例题分析 答案答案 C 7 是是3个结点的完全图，则（）个结点的完全图，则（）A 有有6个边个边B 有有5个边个边C 是欧拉图是欧拉图D 不是哈蜜顿图不是哈蜜顿图本讲稿第八页，共三十七页例题分析例题分析 答案答案 D8下述语句是命题的是（）下述语句是命题的是（）AB你喜欢春天吗？你喜欢春天吗？C天气好暖和呀！天气好暖和呀！D我不喜欢春天。我不喜欢春天。本讲稿第九页，共三十七页例题分析例题分析 答案答案 A9下述公式正确的是（）下述公式正确的是（）ABCD本讲稿第十页，共三十七页例题分析例题分析 答案答案 A10若若T是一个（是一个（n,m）树，则（）树，则（）Am=n-1Bn=m-1Cn-m+k=2Dm=2n-1本讲稿第十一页，共三十七页例题分析例题分析 二、填空（102）1、已知、已知 ，那么，那么 =_答案答案 本讲稿第十二页，共三十七页例题分析例题分析 2、设、设 （0，0）、（）、（0，2），（），（2，0），（），（3，2）则则 的定义域为的定义域为_，值域为，值域为 _。答案答案 本讲稿第十三页，共三十七页例题分析例题分析 3、已知、已知 （nm）问存在）问存在_个不同个不同 的到上的内射。的到上的内射。答案答案本讲稿第十四页，共三十七页例题分析例题分析 答案减法和除法答案减法和除法 4、整数集上的四则运算中不能保证封闭性的是、整数集上的四则运算中不能保证封闭性的是 _ 本讲稿第十五页，共三十七页例题分析例题分析 5、写出群中生成元的定义、写出群中生成元的定义_ 答案答案 g为生成元为生成元,则任给群中的一元素则任给群中的一元素 ,那么存在整数那么存在整数r,使得使得本讲稿第十六页，共三十七页例题分析例题分析 答案答案 互补律、分配律和同一律互补律、分配律和同一律 或或 是有补格且是分配格是有补格且是分配格 6、如果一个格要求成为布尔代数，那么还需要满足的条件、如果一个格要求成为布尔代数，那么还需要满足的条件 _ 本讲稿第十七页，共三十七页例题分析例题分析 答案偶数答案偶数 7、若、若G是欧拉图那么是欧拉图那么G中每个结点的度均为中每个结点的度均为 _ 本讲稿第十八页，共三十七页例题分析例题分析 8、将、将“每个人都会死亡的每个人都会死亡的”符号化：符号化：_ 答案答案本讲稿第十九页，共三十七页例题分析例题分析 答案所有的回路均为偶数长答案所有的回路均为偶数长 9、二部图的充要条件是：、二部图的充要条件是：_ 本讲稿第二十页，共三十七页例题分析例题分析 答案答案10、设代数系统、设代数系统 ，其中定义，其中定义 ，则有则有_个子代数。个子代数。本讲稿第二十一页，共三十七页例题分析例题分析 三、简答题（310）1、说明：、说明：答案答案本讲稿第二十二页，共三十七页例题分析例题分析 2、,试问有多少个由试问有多少个由A1到到A2的不同关系？的不同关系？为什么？为什么？答案答案 共有共有 个个 到到 上的二元关系上的二元关系,因为因为:依据二依据二元元 关系的定义关系的定义,到到 上的二元关系是上的二元关系是 与与 的笛的笛卡卡 尔积的任意一个子集尔积的任意一个子集,而而 与与 的笛卡尔积共有的笛卡尔积共有 个元素个元素,再依据幂集的定义再依据幂集的定义,知共知共有有 个关系。个关系。本讲稿第二十三页，共三十七页例题分析例题分析 3、F=是什么类型的公式？说明理由。是什么类型的公式？说明理由。答案答案 所以所以F为重言式为重言式。本讲稿第二十四页，共三十七页例题分析例题分析 四、证明题（310）1、证明设、证明设 是是 到到 的满同态，则如果的满同态，则如果 *是可交换的，则是可交换的，则 也是可交换的。也是可交换的。证明证明 由于由于h为为A到到B上的满射上的满射,故故 ,使得使得 ,则则 故故 满足交换律。满足交换律。本讲稿第二十五页，共三十七页例题分析例题分析 2、试证明链、试证明链 也是一个分配格。也是一个分配格。证明证明 (1)设设 是一个链是一个链,则则 是一个偏序集是一个偏序集,且且对对 有有 或或 ,于是若于是若 ,则则 ,若若 ,则则 ,所以所以 是格。是格。(2)设任取设任取 ,由于由于L为一个链为一个链,故有故有 或或 或或 或或 或或 ,不妨取不妨取 ,本讲稿第二十六页，共三十七页例题分析例题分析 那么那么 ,由定理由定理7-3得得 而 所以所以 满足分配律满足分配律,所以链所以链 是一个分配格。是一个分配格。本讲稿第二十七页，共三十七页例题分析例题分析 证明证明 证法一由于证法一由于G中所有结点的度均为中所有结点的度均为2,那么对那么对G 中任中任 一连通分图来讲一连通分图来讲,它必然是一个欧拉图它必然是一个欧拉图,并并 且每个结点在欧拉回路中只出现一次且每个结点在欧拉回路中只出现一次,换句话换句话 说说G的每个分图均是环的每个分图均是环,所以所以G是由环构成的。是由环构成的。3、若图、若图G的所有结点的度为的所有结点的度为2，则，则G的每个分图含环。的每个分图含环。本讲稿第二十八页，共三十七页例题分析例题分析 证法二设证法二设G有有r个分图个分图 ,不妨设不妨设 为为 图图,假设假设 不含环不含环,则则 是树是树,于是于是 ,又又 每个结点度数为每个结点度数为2,所以由握手定理所以由握手定理 ,矛盾矛盾,因此必是因此必是 含环。含环。本讲稿第二十九页，共三十七页例题分析例题分析 五、简答题（310）1、一棵树有、一棵树有1个结点度数为个结点度数为5，2个结点度数为个结点度数为4，5个结点个结点 度数为度数为2，14个结点度数为个结点度数为1，问度数为，问度数为3的结点有几个？的结点有几个？答案设答案设T是是(n,m)图图,度为度为3的结点数为，的结点数为，则则 ,由握手定理由握手定理 2m=所以所以,有有5个度数为个度数为3的点。的点。本讲稿第三十页，共三十七页例题分析例题分析 2、判断下面两个图是否为平面图，若认为是平面图，请画、判断下面两个图是否为平面图，若认为是平面图，请画 出其相应的平面图解，否则说明它为什么不是平面图。出其相应的平面图解，否则说明它为什么不是平面图。本讲稿第三十一页，共三十七页例题分析例题分析 答案在图答案在图 中选子图中选子图 在度为在度为2的结点内的结点内 与与 同构同构,所以所以 是非平面图。是非平面图。可以画在平面上无交叉可以画在平面上无交叉,故故 是平面图。是平面图。本讲稿第三十二页，共三十七页例题分析例题分析 3、,且且 和和 都是可逆的，证明都是可逆的，证明 函数复合函数复合 运算满足：运算满足：答案由于，答案由于，均为可逆函数均为可逆函数,也是双射函数也是双射函数,所以所以 ,使得使得 ,同理同理 ,使得使得 ,因此因此 ,由函数复合的定义知由函数复合的定义知 也为可逆函数也为可逆函数,即即 ,而而 所以所以 本讲稿第三十三页，共三十七页例题分析例题分析 六、证明题（310）1、试证明群、试证明群的两个子群的交集也构成的两个子群的交集也构成的子群。的子群。证明设为证明设为 的任意两个子群的任意两个子群,那么那么 ,且且G的单位元的单位元 ,因此因此 ,那么那么 ,且且 ,而而 为群为群,故故 ,因此有因此有 ,同理 ,因此因此 ,故故 也是也是G的子群。的子群。本讲稿第三十四页，共三十七页例题分析例题分析 2、若、若G是连通平面图，则是连通平面图，则G中必有一个结点中必有一个结点V，使得，使得 deg(V)5证明设证明设G(m,n)中中 ,那么那么 而由握手定理而由握手定理 ,故故 ,即即 ,与平面图与平面图 矛盾矛盾,所以假设不成立所以假设不成立,使得使得 ,本讲稿第三十五页，共三十七页例题分析例题分析 3、形式证明：如果他努力学习，则他不会不及格；如果他、形式证明：如果他努力学习，则他不会不及格；如果他 不爱打麻将，则他会努力学习；结果是他考试不及格，不爱打麻将，则他会努力学习；结果是他考试不及格，那么他肯定爱打麻将。那么他肯定爱打麻将。证明证明 P:他努力学习他努力学习,Q:他及格他及格,R:他爱打麻将他爱打麻将 则语句符号化为则语句符号化为:证明证明:(1)前提前提 (2)前提前提 (3)(1),(2);本讲稿第三十六页，共三十七页例题分析例题分析 (4)前提前提 (5)(3),(4),证毕。证毕。本讲稿第三十七页，共三十七页