《2015年电大本科离散数学期末复习考试》由会员分享，可在线阅读，更多相关《2015年电大本科离散数学期末复习考试（9页珍藏版）》请在金锄头文库上搜索。
1、电大离散数学复习资料考试小抄一、单项选择古每小题 3 分，本题共1S 分)1 震集合 4=fl，23，B=fL，2，人4L，23，则下列表述正确的是( A )A，4cB，且4eB B. Bec4，且4eB C. 4cB，且.42B D- 4zB，且4eB2.设有向图(a)、(妨、(e) 与4) 如图一所示，则下列结论成立的是( D ).上四 四国一A.(a) 是强连通的 B- (2) 是强连通的C。(c) 是强连通的 D。(d) 是强和连通的3.设图 G 的邻接答阵为rollo mo和oooolIone则 G的边数为( B 和“开 上A6 Bcl 1 人4 无简单国 6是标档，当且仅当( A
2、OU.C(A，G和连通且边数比结点数少1 B。G连通且结点数比边数少1C，G 的边数比结点数少1 D。G中没有回路。5， 下列公式 (肖C 7 为重言趟。A. -PhnOePvg B. LO-PvODeCONPvO)CPPCO3PJeCP APO) “DECPPAOJTeO6. 设 生僻局，B-iD 23，局，Ra， 及是二到及的二元关系, 是Ri=,，Rrf, ，Rarf, 则(5 B ) 不是从4到妃的函数A. Ri和及 B. PR3 D. R和A7.，设4=fh 2 3,4,5,6,7,8， 及是二上的整除关系，B=t2, 4 6，则集合互的最大元、最小元、上界、下界依次为 (B )A.
3、 8、2、8、2 B- 无、2、无、2C. 6.2.6.2 D. 8、1 6.18 若集合 4 的元素个数为 10，则其宕集的元素个数为( A。 )A. 1024 B. 10 C.10 D.19，设完全图下 有严个结点(三2，严条边，当 C ) 时，五, 中存在欧拉回路人A. 普为奇数 。 B. 7为偶数C. 于为奇数 D. 站为个数10， 已知图 G 的邻接矩阵为则G有(D ),A. 5点，8边 B. 6点，7边C. 6点，8边 D. 5点， 7边了,无向完全图 js 的不同构的生成子图的个数为( C )(A)6 B)5(4 (D)312m阶无向完全图 , 中的边数为( AA )(人 远芭
4、2 【 yorD13.在图 G一中，结点总度数与边数的关系是 C )Adegtw)-2|瑟| (B) deg(o=|E|CzaeneaEl DZasw=e二、填空题每小题3分，本题共15 分)1，谷题公式PE=* (2 wz的真值是 1 ,2. 若 4由.2， 人 和 则尺的自反闭包为。芭22,.; L-已知一可无向村 证有吕丰结点 4放， 和 疯 3关的人二 了的同nk数为(VPCO-OGjVRGe，芒中的自由变元为“Re ?中的?设集合 4= ta，有号，那么集合4的宕集是CUaialtp 二如果 Ri和|肪是 省上的自反关系，则RiURusrRin RsRITR:中自反关系有-2.2个:
5、 设图 G 是有 6 个结点的连通图，结点的总度数为18，则可从 G 中删去“4 “条边后使之变成树.。 无向图 6 存在欧拉回路，当且仅当G 所有结让的度疾全为偶数且、连通一，设连通平面图 G 的结点数为 5，边数为 6，则而数为、_3 .10，设个体域忆= fa, 丰，则谓词公式(Yx)4CD)A (3rz) B (xz) 消去量词后的等值式为“COA4IDO)A(LaivB)三、逻辑公式翻译每小题 6 分，本题共12 分)工 将语句“雪是黑色的. ”翻译成命题公式.设 P: 雪是黑色的， 2分)则命题公式为: 己2将语句“他不去学校. ”翻译成命题公式.解: 设 P; 他去学校，则命题公
6、式为 一己.3. 将语句“小王是个学生，小李是个职员，而小张是个军人”翻译成命题公式,设 P: 小王是个学生，: 小李是个职员，R: 小张是个军人. 人2分)则命题公式为， PAOAR.4将语句“如果所有人今天都去参加活动，则明天的会议取消. ”翻译成命题公式。2oo 解: 设 P， 所有人今天都去参加活动，: 明天的会议取消,则命题公式为: 已C.5将语句“他去旅游，仅当他有时间. ”翻译成命题公式解: 设 P: 他去旅游，Q: 他有时间，则命题公式为 P-O.6将语句“41 次列车下午五点开或者六点开. ”翻译成命题公式、解: 设 P; 41 次列车下午五点开，: 41 次列车下午六点开，
7、 人分)命题公式为: (PA-) V (-PAO)7. 将语句“小张学习努力，小王取得好成绩. ”翻译成命题设 Pi 小张学习努力，2C: 小王取得好成绩， 2分)则命题公式为 PAO.8将语句“有人去上课. ” 翻译成谓词公式.解: 设 Pb: x是人，GD: x去上课， (1分)GePO AQG9将语句“所有的人都学习努力. ”翻译成命厦公式.解: 设 Po): x是人，CGCD: OCD).四、判断说明题“每小题 7分，本题共 14 分) 判断下列各题正误，并说明理由工 议和人4人jslgy 未/是青构) 和2 ，并说明理由，伸产Kb 和 22 6 0O广EU ss全户， ， ， 4,
8、2答:1) 不构成函数 。 因为3s 4，但7 (3) 没有定义，所以不构成函数 2六不构成函数“因为4s 4 ，但 / (4) 没有定义，所以不构成函数(3) 满足。 因为任意xs 4 ，都有7 (x) es 3 且结果唯一。2.若集合4 = fl，2，3上的二元关系 R，则(D丸是自反的关系; (及是对称的关系.答: (1 错误 因为(3.3)e R ，所以及不是自反的2) 错误 因为人,2)s R ，但是(2,1) e R ，所以R 不是对称的3. 如果届和民是二上的自反关系，判断结论:“素i、RIUR2、RinR:是自反的” 是否成立? 并说明理由.答; 成立。 因为任意se 4 ，有
9、(oa)e Riv(aia)e Ra有(os人os，人na)ena Ri 疝Us Rnm是自反的4.。若偏序集4，权的哈斯图如图一所示， /人N则集合的最大元为 mw，最小元不存在， 4 83 | |2 大co答: 错误，集合A 没有最大元，也没有最小元其中a是极大元5.若偏序集的哈斯图如图一所示，则集合二的最大元为 wm，最小元不存在. 解: 正确对于集合4 的任意元素x%，均有eR (或xRa)，所以a 是集合4中的最大元,按照最小元的定义，在集合4中不存在最小元.6 如果图 G是无向图，且其结点度数均为偶数，则图 G 存在一条欧拉回路.答: 错误 如果图 G 是无向图，且图 G 是连通的
10、，同时结点度数都是偶数7.，设 G是一个连通平面图，且有6个结点 联条边，则 G有7个面.答案,正确定理，连通平面图 G 的结点数为 v，边数是e，面数为 p，则欧拉公式 vetr-2 成立所殿亚2-vie=2-6+11=7则 G 存在一条菊拉回路 |8. 设 6是一个有6在缚局 和wa 面图. 人 二解: 错误，不满足“设 6是一个有 个结忘记条边的过 曾图,着 ,世3，则e3vw6. ” 9，合题公趟 一PNCP-一O)vP 为永真式.解: 正确 因为，由真值表PT了2 Pi本22ACOVP0 0下El 1 1站 1 1 人0 于 工工 0 0 工 工 11 1 0 0 0 1 可知，该命
11、题公式为永真式-五. 计算题每小题 12 分，森题共36 分)工 设集合 4=人o, 所)，叶，B=ttaj, cy，试计算CD Cd4nB) 2) (至-4 3 3) (Cd4nB) x忆.解 (1D) Cd4nB) =fcj(CG) (B-4) =1a5 G3) C4nB) xB=f,c， cz2.设 4四，1，2，3，4，5，日，R=e4d ye4d 且xHyHj，S=ed，ye4且xH3，试求有RR，S，ReS，R SrR)-解，R-SI,4ReS-,RE-8 )TCR)=13图 G=也配，其中 玫甩用时，本人(及 oh 人 人力e (cote mh人可，对应边的权值依次为2、1、2、
12、3、6、1、4及5,，试CD 画出G的图形;2) 写出 G 的邻接邱阵;3) 求出 权最小的生成树及其权值.解: 1) G 的图形表示为; (3分)2) 邻接矩阵: 权为7:和 设图 G=了本卫生 二 和 间， ET后癌， 的癌， 0， oa 00辣oo问)试D 画出 G 的图形表示;2) 求出每个结点的度数;(9) 画出图 G 的补图的图形.解: (1) 关系图2) deg(w)2 deg0p)-3 degtes)4dca0=3 。 degts)=263) 补图 加 人 5 设集合 拓人L，2，3，必，R-eye4; pe-1或xy=0，试1) 写出灵的有序对表示;2) 画出灵的关系图3)
13、说明灵满足自反性，不满足传递性.解: (1) R-,i,i (3分)2) 关系图为 (C3) “3 丽，即4 的每个元素构成的有序对均在丸中，故灵在对上是自反的。因有与属王， 人 属于R，所以R 在4 上不是传递的。6 设集个全岂2 91 有 ie 8 ETY 生风|俐1) ReS; 25 RH (Jr CR) 。解: 1D Reg一, 4分)5) REL，P, 8分) (3) Ri=El， 了,24 23 y) ， 3分)呈 量词的辖域为Cs,7,z)， 6分)2) 自由变元为公式中的? 与2(x,y,z) 中的z 9分)约束变元为PCx,y) 的与Gxe az-了1，求命古公式(PvO)-
14、(RvO) 的主析取范式、主合取范式- 7 入-renrre二UPVOPURVO 般小项 柜大项一PA-QA-R一PA-QAR-PAQA-R一PAQAR -PPvQvRPA-QARPAQA-RPAQAR二2关上站1 11主析到范式极小项析取)(-PA-QAR) v (PA-QAR) v (-PAQA-R) v (PAQAR)V (Ph-QAR) v (PAQA-R ) v CPAQAR)主合取范式极大项全取): -PvQvR12. 求 (PVO) 一 (CRVOC) 的析取范式，合取范式.解: (PVO) CRVO) CPVO) V CRVO) (4分)CCPA-OV CRVO)CCPVRVO
15、ACOVRVO) (PVRVGO) 析取、合取范式六、证明题本题共8分)1，试证明集合等式 4人BuO=GdmnB dmnO;证明, 设s4n(BUG，T=UnBiUUdnO，着xsS, 则xc4且xEBUC, 即xE4竹XEB 或xE4且7也mxe405起起 本部 局 态sf) 人4 CLK PP反之,着xE7T 则ke4nB 或xc4nC， |即xe4且xEB 或xc4且xEC也即xe4且xEBUC，即xES，所以7ES.此 738.EC， 2. 试证明 (ax) (PKx) 办R (x) 一(3) P GD)人5H) 玉 ().证明:(CD (xz) (PCz) AR CD) 己(2) P Co) AR (a) ESCD3) PC) TOJ4) (3r) 已(xz) EGG)(C5) R (CO) TO6) (az) R CD) EGG)(7) (ep) P CD 入 Car) R CD) TGS)6IT WwWwWw. docin。 com
