离散数学 |
您所在的位置:网站首页 › 蛇喜欢竹林吗 › 离散数学 |
一、 数理逻辑
1. 2. 解析:19.其实也可以找极小项: m5 3. 解析: 4. 5.在推理理论中,推导过程中如果一个或多个公式重言蕴涵某个公式,则这个公式就可以 引入推导过程中,这一推理规则叫做 ( T 规则 ) 。6. 7. 8. 9.
10.
大题: 考查解释: 2.3. 解答: ① s 附加前提引入 ② s->p 前提引入 ③p ①② 假言推理 ④p->(q->r) 前提引人 ⑤ q->r ③④假言推理 ⑥ q 前提引入 ⑦r ⑤⑥ 假言推理 ⑧ s->r ①⑦附加前提 二、 集 合1. 答案:A-∅=A ∵任何集合减去∅均为其本身,两个集合相减=第一个集合去掉两者相同的部分。 幂集个数为2的(元素个数)次方。
2. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是a1= {(a,1), (b,1)}, a2= {(a,2), (b,2)},a3= {(a,1), (b,2)}, a4= {(a,2), (b,1)},其中双射的是_ a3, a4. 4. 6. 集合的基数:集合A={1,2,…,n},含有n个元素,这个集合的基数是n,记为card A = n 表示集合中所含元素多少的量,也可记为|A|=n 7. 大题: 1. 4. A, B为两个任意集合,求证:A-(A∩B) = (A∪B)-B . 解答: 证明:A-(A∩B) = A∩~(A∩B)=A∩(~A∪~B)=(A∩~A)∪(A∩~B) =∅∪(A∩~B) =(A∩~B) =A-B 而 (A∪B)-B = (A∪B)∩~B = (A∩~B)∪(B∩~B) = (A∩~B)∪∅ = A-B 所以:A-(A∩B) = (A∪B)-B. 2.设A,B为任意集合,证明:(A-B)-C = A-(B∪C). 解答: 证明:(A-B)-C = (A∩~B)∩~C = A∩(~B∩~C) = A∩~(B∪C) = A-(B∪C) 三、 二元关系1.设集合A中有3个元素,则A上的二元关系有( 512 )个,其中有( 27 )个是A到A的函数. 解答:二元关系个数等于2^(3*3),A到A的函数要求定义域要满,即固定3位数,其余随意取故有3*3*3.. 具体:设A = {0, 1, 2},则A上不同关系的个数为 512 2. 设D24是24的所有正因数组成的集合,“|”是其上的整除关系,则3的补元( 8 ),4的补元( 不存在 ),6的补元( 不存在 ). 最大元与最小元互为补元。求其余元素的补元时,若A与B互为补元,从这两个点出发的路径,向上只相交于最大元,向下只相交于最小元。 3. 4. 5.设R是集合A上的等价关系,则R所具有的关系的三个特性是__自反性;对称性;传递性 .而偏序关系的三个特性分别为:自反性,反对称性,传递性·。 6. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1·R2 = {(1,3),(2,2),(3,1)} ,R2·R1 = {(2,4),(3,3),(4,2)} , R12 = { (2,2),(3,3)}. 7. 8. 9.设 A 为非空集合,A 的商集就是 A 的一个划分(对) 10.. 设 X={a,b,c,d},Y={1,2,3},f={,,},则 f 是从 X 到 Y 的二元关系,但不是从 X 到 Y 的函数 ( √) 11.关于整数集Z上的“<”关系R,以下描述不正确的是( D ) A.R的自反闭包是“≤”关系 B.R的对称闭包是“≠”关系 C.R的传递闭包是它本身 D.R的反自反闭包是“>” (三)大题 对偏序集({3,5,6,15,24,30},|)上的整除关系,画出哈斯图并回答 下列问题: 求极大、极小元素; 极大元素:24,30 极小元素:3,5 求最大、最小元素; 无最小元素,也无最大元素 找出{3,5}的所有上界,如果存在的话求出最小上界; 上界:15 ,30,最小上界:30找出{15,30}的所有下界,如果存在的话求出最大下界。 3,5 解析:极大元素:即极大元·,没有元素比他大(在它的范围它是大哥);极小元素:即极小元·,没有元素比他小(在它的范围它是小弟);显然,孤立的点既是极大元素也是极小元素。 最大元素:即 在全部范围没有元素比他大,否则无最大元;最小元素:即最小元·,即 在全部范围没有元素比他小; 上界:偏序集中大于或等于它的子集中一切元素的元素。 下界:偏序集中小于或等于它的子集中一切元素的元素。 最小上界(上确界): 上界中最小元。 最大下界(下确界):下界最大元。 2. 3. 4. 四、函数 (二)选择题 (三)大题1.函数复合: 五、 图论 (一)判断题1.无向完全图Kn (n>=3) 都是欧拉图。(×); K5既是欧拉图又是哈密顿图。( 对 );
对于顶点个数大于2的图,如果图中任意两点度的和大于或等于顶点总数,那这个图一定是哈密顿图。(对); 设无向图G具有割点,则G中一定不存在哈密尔顿通路。( × ); 度数为奇数的结点个数为0个或2个的连通的无向图G可一笔画出。(欧拉图定义)(√); 2.若无向连通图G中存在桥,则G的点连通度和边连通度都是1。 ( √ ); 任何平面图G的对偶图G*都是连通平面图。( √ ); 图G中的初级回路(基本回路)都是简单的回路。 ( 对 ); 2. (二)选择题3.设图G的相邻矩阵为,则G的顶点数与边数分别为( D ). (A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8. 4.设G是连通平面图,有5个顶点,6个面,则G的边数( A ).欧拉公式:面数+顶点数=边数+2 (A) 9条 (B) 5条 (C) 6条 (D) 11条. 5.若供选择答案中的数值表示一个简单图中各个顶点的度,能画出图的是(C ). (A)(1,2,2,3,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6). 能判断:首先度之和是偶数(利用奇数度节点的个数是偶数) 每个节点度数最多为(n-1),n为节点个数.
9. 10.
11. (三)大题 1.已知 a,b,c,d,e,f,g 7 人中,会讲语言分别是: a:英语,德语 b:英语,汉语 c :英语,意大利语,俄语 d:汉语,日语 e:意大利语,德语 f:俄语,日语,法语 g:德语,法语 问能否将他们的座位安排在圆桌旁,使得每个人都能与他身边的人交流.2. 答: 树论 (一)判断题·:1.任何无向树都是二部图。(对 ); (二)填空题1.不同构的5阶根树有( 9 )棵. 解析:如图 2.连通无回路的无向图称为_______。(无向树或树) 3. 森林是_____________________。(每个连通分支都是树的无向图) 4. 度数大于等于2的顶点是________________。(分支点) 5.无向图G有生成树当且仅当_______________。( G是连通图)6.设G是5个顶点的完全图,则从G中删去( 6 )条边可以得到树.(A)6 (B)5 (C)10 (D)4. 7.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为_12 _,分枝点数为 _3_ . 8.设G是具有8个顶点的树,则G中增加__21_条边才能把G变成完全图. 解析:完全图边数:n*(n-1)/2 树的边数:n-1 故为增加边数为:(n-2)*(n-1)/2。 9. 解析: (三)大题1.设无向树 T 中,有 2 个 2 度顶点,2 个 3 度顶点,1 个 4 度顶点,其余 的顶点均为树叶,试求 T 的阶数 n,边数 m,树叶数 t。 解答:由常识可知:n=m-1,由握手定理可知,2m=2(n-1)=2*2+2*3+1*4+t*1; t+2+2+1=n; 解得:n=11,m=10,t=6 2. 设 7 个字母在通信中出现的频率如下 : a: 35% b: 20% c: 15% d: 10% e: 10% f: 5% g: 5% 用 Huffman 算法求传输它们的前缀码.要求画出最优树,指出每个字母对应的编 码.并指出传输 10n(n≥2)个按上述频率出现的字母,需要多少个二进制数字. 此最优树并不唯一: 1.a:11 b:00 c:101 d:100 e:011 f:0100 g:0101
|
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |