《离散数学》复习资料12月

1、1 / 8离散数学复习资料年月一、单项选择题（每小题分，本题共分）若集合，则下列表述正确的是（）. ，且三，且三 .：_,且匕.二，且设有向图（）、（）、（）与（）如图一所示，则下列结论成立的是（）.设, , ,是到的一兀关系，且, , , , ,则（ ）不是从到的函数.和.和.设, , , , , , , ，是上的整除关系，, , ，则集合的最大元、最小元、上界、下界依次 为（）.、.无、无、.若集合的元素个数为，则其幕集的元素个数为（）.10 C.设完全图n有个结点（），条边，当（）时，n中存在欧拉回路.为奇数.为奇数1.为偶数工.为偶数.已知图的邻接矩阵为.（）是强连通的.（）是强连通的

2、.设图的邻接矩阵为图 一() 是强连通的()是强连通的0110 0_100 11100000100 1L010 11则的边数为（）.C.无向简单图是棵树，当且仅当（.连通且边数比结点数少）.连通且结点数比边数少.中没有回路.F列公式（）为重言式.（）（一(一) -(一( )（一（）2 / 8r0 1 0II1I000I00 011I010I11110,则有().点，边.点，边.点，边.点，边.无向完全图的不同构的生成子图的个数为()() ()() ()阶无向完全图中的边数为()n(n -1)n(n 1)() ()2 2.在图=中，结点总度数与边数的关系是() ()()()()()Z deg(v

3、) = 2 Ev召召送送d egv() = Ev申申、填空题(每小题分，本题共分).命题公式P (Q P)的真值是_若, - , - , ，则的自反闭包为,_.已知一棵无向树中有个结点，度，度，度的分支点各一个，的树叶数为(一)()()V(,)中的自由变元为(,)中的_.设集合=,，那么集合的幕集是 _ ,.如果和是上的自反关系，则u,n，中自反关系有_ 个.设图是有个结点的连通图，结点的总度数为，则可从中删去 _ 条边后使之变成树.无向图存在欧拉回路，当且仅当所有结点的度数全为偶数且连通.设连通平面图的结点数为，边数为，则面数为 _.设个体域=, ，则谓词公式(-)()A()()消去量词后的

4、等值式为 _()人( ()M () V ()三、逻辑公式翻译(每小题分，本题共分).将语句“雪是黑色的.”翻译成命题公式. 设：雪是黑色的，则命题公式为：.将语句“他不去学校.”翻译成命题公式.(分)3 / 84 / 8则命题公式为：将语句“有人去上课.”翻译成谓词公式将语句“所有的人都学习努力.”翻译成命题公式 解：设()：是人，()：学习努力，-)()()四、判断说明题(每小题分，本题共分)判断下列各题正误，并说明理由设集合, , , , , , ,判断下列关系是否构成函数：ATB，并说明理由.(), , , ；(), , ；(), , , ()不构成函数 因为4，A，但f 4没有定义，所

5、以不构成函数()满足。因为任意A，都有f x B且结果唯一。若集合, 上的二元关系,，则()是自反的关系；()是对称的关系.解：设：他去学校，则命题公式为：-将语句 小王是个学生，小李是个职员，而小张是个军人. 设：小王是个学生，：小李是个职员，：小张是个军人. 则命题公式为：将语句“如果所有人今天都去参加活动，则明天的会议取消. 解：设：所有人今天都去参加活动，:明天的会议取消，则命题公式为： 将语句“他去旅游，仅当他有时间.”翻译成命题公式.”翻译成命题公式.(分)”翻译成命题公式.解：设：他去旅游，：他有时间,则命题公式为：将语句“次列车下午五点开或者六点开.”翻译成命题公式.解：设：次

6、列车下午五点开，：次列车下午六点开，（分）命题公式为：(A )V(-人)将语句“小张学习努力，小王取得好成绩.”翻译成命题设：小张学习努力，：小王取得好成绩,（分）解：设()：是人，()()()（）:（分）答：()不构成函数因为3 A，但f 3没有定义，所以不构成函数5 / 8答：()错误因为3,3；R，所以不是自反的()错误因为1,2? R，但是R，所以不是对称的6 / 8答：成立 因为任意aw A，有(a,a产R,(a,a严 &所以a,a)wR二，(a,a)RUR2,a,a)ER,P|&、u、门是自反的若偏序集的哈斯图如图一所示， 则集合的最大元为，最小元不存在.答：错误，

7、集合没有最大元，也没有最小元/其中是极大元/若偏序集的哈斯图如图一所示，则集合的最大元为，最小元不存在.图一解：正确对于集合的任意元素，均有三(或)，所以是集合中的最大元.按照最小元的定义，在集 合中不存在最小元.如果图是无向图，且其结点度数均为偶数，则图存在一条欧拉回路.答：错误 如果图是无向图，且图是连通的，同时结点度数都是偶数.设是一个连通平面图，且有个结点条边，则有个面.答案：正确定理，连通平面图的结点数为，边数是，面数为，则欧拉公式成立所以则存在一条欧拉回路.设是一个有个结点条边的连通图，则为平面图.解：错误，不满足“设是一个有个结点条边的连通简单平面图，若，则W.” .命题公式(

8、(厂厂) )为永真式.解：正确因为，由真值表-1-1T-1可知，该命题公式为永真式.五.计算题(每小题分，本题共分).设集合, , , , ，试计算()(H)；()(-)；()( n) X.解()(n)；()(-);如果和是上的自反关系，判断结论:“、u、门是自反的” 是否成立？并说明理由.e7 / 8()(门), 设,w, 且,w，迂且0,试求，()(). 解：/,)()图,其中, , , , , (, ), (, ), (, ), (, ), (, ), (, ), (, ), (, ) ,对应边的权值依次为.及,试()画出的图形；()写出的邻接矩阵；()求出权最小的生成树及其权值. 解：

9、()的图形表示为：(分)()邻接矩阵：0 110 110 0 1110 0 110 110 11111 0一()粗线表示最小的生成树，权为：设图， (, )，(, )，(, )，(, )，(, )，(, )，(, ) ，试(1)画出的图形表示；(2)求出每个结点的度数；()画出图的补图的图形.解：()关系图(分)L”8 / 8()() () ()() ()()补图设集合,因为,均属于,即的每个元素构成的有序对均在中, 上不是传递的。,试计算()()因有与属于，但不属于,设集合, , ,()解：()()()(), ;,、求出如图一所示赋权图中的最小生成树(要求写出求解步骤)故在上是自反的。(分)

10、(分)W(Vi, V7)=1W(V3, V4)=3w(V2, V7) =4w(V3,V7)=9wM, V5) =18w(w, V6)=22选 二V1V7选e2=V3V4选Q=V2V7选e4-V3V7选eV4V5选e6=V1V6(分)最小生成树如图四所示:(分)()3* , (-z)Q(x, y, z)，试()写出量词的辖域；()指出该公式的自由变元和约束变元.() 量词的辖域为P(x, y),(分)-量词的辖域为Q(x, y,z),(分)()自由变元为公式中的与Q(x, y,z)中的,(分)约束变元为P(x, y)的与Q(x, y,z).() ( ：.)(、.：.：).求命题公式()()一；一；()()的主析取范式、主合取范式. 解：主析取范式(极小项析取)11 / 8.求(V)T(V)的析取范式，合取范式 解：(V)T(V)二(V)V(V)：=(一A)V(V)=(VV)A(VV)二(VV)析取、合取范式六、证明题(本题共分).试证明集合等式 -(_)(-)