离散数学总复习资料4

上传人:油条 文档编号:116653294 上传时间:2019-11-16 格式:DOC 页数:11 大小:412.50KB
返回 下载 相关 举报
离散数学总复习资料4_第1页
第1页 / 共11页
离散数学总复习资料4_第2页
第2页 / 共11页
离散数学总复习资料4_第3页
第3页 / 共11页
离散数学总复习资料4_第4页
第4页 / 共11页
离散数学总复习资料4_第5页
第5页 / 共11页
点击查看更多>>
资源描述

《离散数学总复习资料4》由会员分享,可在线阅读,更多相关《离散数学总复习资料4(11页珍藏版)》请在金锄头文库上搜索。

1、离散数学总复习资料一、鸽笼原理与容斥原理1求证边长为1的正方形中放9个点,由这些点构成的三角形中,必有一个三角形面积小于。证:把该正方形均分成四个相同的小正方形,则由鸽笼原理知,必有一个小正方形内存在三个点,且这三个点构成的三角形面积小于。#2对一列个不同整数,任意排列,证明一定存在长为的上升子序列或下降子序列。证:设此序列为:,从开始上升子序列最长的长度为,下降子序列最长的长度为,每一个都对应了。若不存在长为的上升子序列或下降子序列,那么,形如的不同点对至多有个,而有个,则由鸽笼原理知,必有同时对应,由于,若,则至少比大1,若,则至少比大1,这均与矛盾。故原命题成立。#3求中不被3、4、5整

2、除的个数。解: 设表示中被3整除的数的集合,表示中被4整除的数的集合,表示中被5整除的数的集合,则, ,进而有故有即中不被3、4、5整除的个数为40。#4有100个学生,其中60个爱看小说,30个爱下棋,10个既爱看小说,又爱下棋,5个既爱看小说,又爱跳舞,没有既爱下棋,又爱跳舞的,三种活动都不爱的有10个,问有几个学生爱跳舞?解:设全体学生的集合为,爱看小说的学生集合为,爱下棋的学生集合为,爱跳舞的学生集合为,则依题意有, ,从而,。另一方面,根据容斥原理,我们有,即有,故,即有15个学生爱跳舞。#二、数理逻辑5求的主析取、主合取范式。解:取真为:(1,1),(0,0),(0,1);故的主析

3、取范式为;取假为:(1,0);故的主合取范式为:。6求的主析取、主合取范式。解:取真为:(1,1,1),(0,0,1),(0,1,1),(1,0,0),(1,0,1);故的主析取范式为; 取假为:(1,1,0),(0,1,0),(0,0,0);故的主合取范式为:。7(1)将式子“并非跑的最快的马吃的最多”翻译成用谓词和量词表达的逻辑式子。(2)将式子“爱因斯坦于1952年写完狭义与广义相对论浅说”翻译成用谓词和量词表达的逻辑式子。解:(1):马; :跑的最快的马; :吃的最多的马。上式表示为: (2)设:爱因斯坦; :1952; :狭义与广义相对论浅说; :于年写完;则原式子可翻译成逻辑式子。

4、8求下述公式的前束范式和Skolem标准形。解:=故该公式的前束范式为;Skolem标准形为。#9将下列命题符号化,并证明其论证是否正确。(1)不存在白色的乌鸦;北京鸭是白色的。因此,北京鸭不是乌鸦。解:令是白色的;:是乌鸦;:是北京鸭。则上述命题可符号化为:下面,我们证明上述命题是正确的。(1) (P)(2) (US)(3) (CP)(4) (分离规则)(5) (量词转换律)(6) (US)(7) (T,(4)(8) (9) (UG)#(2)符号化下列语句,并用演绎法加以证明。 大熊猫都产在中国,欢欢是大熊猫,所以,欢欢产在中国。解:令是大熊猫;:产在中国;:欢欢。则上述命题可符号化为: 下

5、面,我们证明上述命题是正确的。(1) (P) (2) (US) (3) (P) (4) (分离规则) 三、二元关系10(1)举出正整数集上一种关系,它是等价关系但不是偏序关系;(2) 举出正整数集上一种关系,它是偏序关系但不是等价关系。(3)画出集合上整除关系的Hasse图。(4)等价关系与划分关系解:(1)正整数集上模3的同余关系。(2)正整数集上的整除关系。(3) 24 12 8 6 4 3 2 111(1)举出正整数集上一种二元关系,它是等价关系又是偏序关系;(2) 画出的Hasse图 ,其中。解:(1)正整数集上的恒等关系。(2) 6 4 3 2 112设,定义上的一个二元关系如下:(

6、1)画出的关系图,并写出的关系矩阵;(2)求,;(3)求,。解:(略)13(1)设A=1,2,3,R=<1,2>,<2,3>,求R的闭包关系r(R),s(R),t(R),并画出R,r(R),s(R),t(R)的关系图。(2)设是正整数集关于整除关系作成的偏序集,的子集,求的极小元、极大元、上界、下界、最小上界、最大下界。解:(略)(3)设A=1, 2, 3, 4, 5,找出A上的等价关系R,此关系R能够产生划分:1, 2, 3, 4, 5,并画出R的关系图解:R=<1, 1>, <1, 2>, <2, 1>, <2, 2>

7、, <4, 4>, <4, 5>, <5, 4>, <5, 5>, <3, 3> 42153v3四图论14(1)画一个图,使它既有欧拉回路,又有哈密顿回路;(2)画一个回路图,使它既无欧拉回路,又无哈密顿回路。解:(1) (2) 或 15(1)画一个图,使它有欧拉回路,无哈密顿回路;(2)画一个回路图,使它无欧拉回路,有哈密顿回路。解:(1) (2) 16证明小于30条边的简单平面图至少有一个顶点的度数小于5。证:(反证法)假设小于30条边的简单平面图中每一个顶点的度数大于等于5,从而此时顶点数与边数满足;另一方面,由于此时图的每一个

8、区域至少由3条边围成,从而由Euler公式推论知,此时顶点数与边数满足;故有,进而有,这与已知条件产生矛盾。故小于30条边的简单平面图至少有一个顶点的度数小于5。#17证明具有6个顶点和12条边的连通简单平面图,它的每个区域都是由三条边围成。证: 由题意及欧拉公式知,其区域数为。若有一个区域不是由三条边围成,则至少由4条边围成,从而8个区域至少需要25条边才能围成,即图中的边数不少于25/2=12.5, 这与已知条件12条边产生矛盾,故它的每个区域都是由三条边围成。#18设, 任意顶点的次(度)不少于2,且任意两个相邻区域只有一条公共边的简单平面图,证明其着色数不少于3。解:(略)19用算法寻

9、找下图中顶点到的最短路径。 g 2 h 2 i 2 j 2 1 1 2 2 1 d 2 e 2 f 2 1 1 2 b 1 c 2 1 a解:从出发第一短的点为,距离为1,路径为;从出发第二短的点为或,距离为2,路径为或;从出发第四短的点为或,距离为3,路径为或;从出发第五短的点为或或,距离为4,路径为或(或)或。故顶点到的最短路径为。#20求分别用前序、中序、后序遍历(周游)下图。 6 2 10 1 4 7 11 3 5 9 8 解:前序6-2-1-4-3-5-10-7-9-8-11 中序1-2-3-4-5-6-7-8-9-10-11 后序1-3-5-4-2-8-9-7-11-10-6 21求出下图的最小生成树。 21 1 2 1 22 1 3 3 2解: 1 1 1 1 1 1 2 1 或 1 2 2 2 22设7个字母在通讯中出现的频率如下, ,编一个相应的二元前缀码,使通讯中出现的符号尽可能少,并画出对应的二元树。解:该二元前缀码对应的Huffman树为: 100 40 60 20 20 25 35 10 10 10 15 5 5 从而对应的二元前缀码为:。#23给定树叶的权分别为1,4,9,16,25,36,49

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 中学教育 > 其它中学文档

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号