《2022年电大离散数学本科期末复习题 .pdf》由会员分享，可在线阅读，更多相关《2022年电大离散数学本科期末复习题 .pdf（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 / 35 离散数学（本）一、单项选择题1设P：a 是偶数， Q：b 是偶数。 R：a + b 是偶数，则命题“若a 是偶数， b 是偶数，则a + b 也是偶数”符号化为（D P Q R）。2表达式x（P（x，y）Q（z）y（Q（x， y）zQ（z）中x 的辖域是（ P（x， y） Q（ z）。3设)(),(,4321PSPSSS则命题为假的是（42SS）。4设 G 是有 n 个结点的无向完全图，则G 的边数（ 1/2 n （ n-1）。5设 G 是连通平面图，有v 个结点， e 条边， r 个面，则r=（ e-v+2 ）。6若集合A=1，2，1，2，则下列表述正确的是( 1A )7已知一
2、棵无向树T中有 8 个顶点， 4 度、 3 度、 2 度的分支点各一个，T的树叶数为 ( 5 )8设无向图G的邻接矩阵为0101110011000011100111110则G的边数为 ( 7 ) 9设集合A=a，则A的幂集为 (，a )10下列公式中 (AB (A B) )为永真式11若G是一个汉密尔顿图，则G一定是 ( 连通图 )12集合A=1, 2, 3, 4 上的关系R=|x=y且x, yA，则R的性质为（传递的）13设集合A=1，2，3，4，5，偏序关系是A上的整除关系，则偏序集上的元素 5 是集合A的（极大元）14图G如图一所示，以下说法正确的是 ( (a, d) ,(b, d)是边
3、割集 ) 图一15设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（(x)(A(x)B(x) ）16若集合A=1，2，B=1， 2，1，2 ，则下列表述正确的是(A B，且A B )17设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( （d）是强连通的 )精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 35 页2 / 35 18设图G的邻接矩阵为0101010010000011100100110则G的边数为 ( 5 ) 19无向简单图G是棵树，当且仅当(G连通且边数比结点数少1 )20下列公
4、式 (P(QP)(P(PQ) )为重言式21若集合A a， a，1，2 ，则下列表述正确的是(aA)22设图G，v V，则下列结论成立的是 (EvVv2)deg( ) 23命题公式（P Q）R 的析取范式是 (（P Q） R ) 24下列等价公式成立的为(P(QP) P(PQ) )25设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=, ，R2=, , ，R3=, ，则（R2）不是从A到B的函数26设A=1, 2, 3, 4, 5, 6, 7, 8 ，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为(无、 2、无、 2)27若集合A的元
5、素个数为10 ，则其幂集的元素个数为（1024 ）28如图一所示，以下说法正确的是 (e 是割点 )图一29设完全图Kn有n个结点 (n 2) ，m条边，当（n为奇数）时，Kn中存在欧拉回路30已知图G的邻接矩阵为，则G有（ 5 点， 7 边 ）二、填空题（每小题3 分，共 15 分）1设 A，B 为任意命题公式，C 为重言式，若A CBC，那么 AB 是重言式（重言式、矛盾式或可满足式）。2命题公式（ P Q）P 的主合取范式为)()(QPQP。3设集合A=，a ，则 P（A）= , ,aa。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页
6、，共 35 页3 / 35 4设图 G = V，E， G =V， E，若 V =V,E E , 则 G是 G 的生成子图。5在平面G =V，E中，则riir1)deg(=2|E| ，其中ir（i=1，2， r）是 G 的面。 6命题公式PP的真值是假（或 F，或 0）7若无向树T有 5 个结点，则T的边数为 4 8设正则m叉树的树叶数为t，分支数为i，则 (m-1)i= t-1 9设集合A=1，2上的关系R,，则在R中仅需加一个元素 ，就可使新得到的关系为对称的10(x)(A(x)B(x，z)C(y)中的自由变元有 z， y 11若集合A=1，3，5，7，B=2，4，6，8，则AB=空集（或）
7、12设集合A=1，2，3上的函数分别为：f=,，g=,，则复合函数g f =, , , 13设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2|E|（或“边数的两倍”）14无向连通图G的结点数为v，边数为e，则G当v与e满足e=v-1 关系时是树15设个体域D1, 2, 3 ， P(x)为“x小于 2”，则谓词公式 (x)P(x) 的真值为假（或F，或 0） 16命题公式)(PQP的真值是T （或 1）17若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数 |S|与W满足的关系式为W |S|18给定一个序列集合
8、000 ，001 ，01， 10，0，若去掉其中的元素 0 ，则该序列集合构成前缀码19已知一棵无向树T中有 8 个结点， 4 度， 3 度， 2 度的分支点各一个，T的树叶数为 5 20(x)(P(x)Q(x)R(x，y)中的自由变元为R(x，y )中的y21设集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元关系，,BAyxByAxyxR且且则R的有序对集合为 ， ， ， 22设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=223设G是有 6 个结点， 8 条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成
9、树24无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数25设个体域D1,2 ，则谓词公式)(xxA消去量词后的等值式为A(1)A(2)26设集合Aa，b，那么集合A的幂集是 ,a,b,a,b 27如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有 2 个28设图G是有 6 个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 35 页4 / 35 29设连通平面图G的结点数为5，边数为6，则面数为 3 30设个体域Da, b，则谓词公
10、式(x)A(x)（x）B（x）消去量词后的等值式为(A (a)A (b) (B（a）B（b）) 31. 设集合 A=0 ，1 ，2 ，B=l ，2 ， 3 ， 剖， R 是 A 到 B 的二元关系， R= |x A 且 y B 且 x， y A B 则 R 的有序对集合为 _,_ 32. 设 G 是连通平面图，v， e ， r 分别表示G 的结点数，边数和面数，则 v， e 和 r 满足的关系式_v-e+r=2_ 33.G= 是有 20 个结点， 25 条边的连通图 ,则从 G 中删去 _6_条边，可以确定图G 的一棵生成树. 34. 无向图 G 存在欧拉回路，当且仅当G 所有结点的度数全为偶
11、数且_ 连通 _ 35. 设个体域D= 1, 2 ， 则谓词公式 xA(x) 消去量词后的等值式为_A(1) A(2)_ 三、化简解答题11设集合A=1 ，2，3，4， A 上的二元关系R，R= 1， 1， 1，4， 2， 2， 2，3， 3，2， 3，3， 4，1， 4，4，说明 R 是 A 上的等价关系。解从 R 的表达式知，,),( ,RxxAx即 R 具有自反性；三、逻辑公式翻译1将语句“今天上课”翻译成命题公式设P：今天上课，则命题公式为：P2将语句“他去操场锻炼，仅当他有时间”翻译成命题公式设P：他去操场锻炼，Q：他有时间，则命题公式为：P Q3将语句“他是学生”翻译成命题公式设P
12、：他是学生，则命题公式为：P4将语句“如果明天不下雨，我们就去郊游”翻译成命题公式设P：明天下雨，Q：我们就去郊游，则命题公式为：PQ5将语句“他不去学校”翻译成命题公式设P：他去学校，P6将语句“他去旅游，仅当他有时间”翻译成命题公式设P：他去旅游，Q：他有时间，PQ7将语句“所有的人都学习努力”翻译成命题公式设P(x)：x是人，Q(x)：x学习努力，（x） (P(x)Q(x)8将语句“如果你去了，那么他就不去”翻译成命题公式设P：你去，Q：他去，PQ9将语句“小王去旅游，小李也去旅游”翻译成命题公式设P：小王去旅游，Q：小李去旅游，P Q10将语句“所有人都去工作”翻译成谓词公式设P(x)
13、：x是人，Q(x)：x去工作， (x)(P(x)Q(x)11将语句“如果所有人今天都去参加活动，则明天的会议取消”翻译成命题公式设P：所有人今天都去参加活动，Q：明天的会议取消，PQ精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 35 页5 / 35 12将语句“今天没有人来” 翻译成命题公式设P：今天有人来，P13将语句“有人去上课” 翻译成谓词公式设P(x)：x是人，Q(x)：x去上课， (x)(P(x) Q(x)1 1. 将语句 如果小李学习努力，那么他就会取得好成绩. 翻译成命题公式. 设 P：小李学习努力，Q:小李会取得好成绩
14、，P Q 12. 将语句 小张学习努力,小王取得好成绩. 翻译成命题公式.设 P：小张学习努力，Q:小王取得好成绩，P Q 四、判断说明题1设集合A=1，2，B=3 ，4，从A到B的关系为f= ，则f是A到B的函数错误因为 A 中元素 2 没有 B 中元素与之对应，故f 不是 A 到 B 的函数2设G是一个有4 个结点 10 条边的连通图，则G为平面图错误不满足“设G 是一个有v 个结点 e 条边的连通简单平面图，若v 3，则 e 3v-6 ”3设 N、R 分别为自然数集与实数集，f： N R，f (x)=x+6，则f是单射正确设x1，x2为自然数且x1x2，则有f(x1)= x1+6x2+6
15、= f(x2)，故f为单射4下面的推理是否正确，试予以说明 (1) （x）F（x）G（x）前提引入 (2) F（y） G（y） US （1）错误（2）应为F（y）G（x），换名时，约束变元与自由变元不能混淆5如图二所示的图G存在一条欧拉回路图二错误 因为图G为中包含度数为奇数的结点6设G是一个有6 个结点 14 条边的连通图，则G为平面图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 35 页6 / 35 错误不满足“设G是一个有v个结点e条边的连通简单平面图，若v 3，则e 3v-6”7如果R1和R2是 A 上的自反关系，则R1R2是
16、自反的正确R1和R2是自反的，xA， R1， R2，则 R1R2，所以R1R2是自反的8如图二所示的图G存在一条欧拉回路正确因为图G为连通的，且其中每个顶点的度数为偶数9P（PQ）P为永真式正确P（PQ）P是由P（PQ）与 P 组成的析取式，如果P的值为真，则P（PQ）P为真，如果P的值为假，则P与PQ为真，即P（PQ）为真，也即P（PQ）P为真，所以P（PQ） P 是永真式另种说明：P（PQ）P是由P（PQ）与P组成的析取式，只要其中一项为真，则整个公式为真可以看到，不论P的值为真或为假，P（PQ）与P总有一个为真，所以P（PQ）P是永真式或用等价演算P（PQ）PT 10若偏序集 的哈斯图如
17、图一所示，则集合A的最大元为a，最小元不存在v1v2v3v5v4dbacefghn图二精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 35 页7 / 35 图一正确对于集合A的任意元素x，均有 R（或xRa），所以a是集合A中的最大元按照最小元的定义，在集合A中不存在最小元11. 如果 R1和 R2是 A 上的自反关系，则 R1 R2是自反的。正确， R1和 R2，是自反的，x A, R1, R2,则 R1 R2，所以 R1 R2是自反的 . 12. 如图二所示的图中存在一条欧拉回路. 图二正确，因为图G 为连通的，且其中每个顶点的度数
18、为偶数。五计算题（每小题12 分，本题共36 分）1试求出（PQ）（RQ）的析取范式（PQ）（RQ） (PQ)（RQ） (PQ)（RQ） (PQ)RQ（析取范式）2设A=1, 1, 2 ，B=1, 2 ，试计算（ 1）（AB）（2）（AB）（3）A （AB）（1）（AB）=1 （2）（AB）=1, 2, 1, 2 （3）A（AB）=1, 1, 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 35 页8 / 35 3图G=，其中V= a, b, c, d ，E= (a, b), (a, c) , (a, d), (b, c), (b,
19、 d), (c, d)，对应边的权值依次为1、2、3、 1、4及 5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值（1）G的图形表示如图一所示：（2）邻接矩阵：0111101111011110（3）最小的生成树如图二中的粗线所示：权为： 1+1+3=5 4画一棵带权为1, 2, 2, 3, 4的最优二叉树 ,计算它们的权最优二叉树如图三所示图二a b c d 1 1 2 4 5 3 图一a b c d 1 1 2 4 5 3 1 2 2 3 3 4 7 5 12 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8
20、 页，共 35 页9 / 35 图三权为 1 3+23+22+32+42=27 5求（PQ）R的析取范式与合取范式（PQ）R（PQ）R (PQ)R （析取范式） (PR) (Q R) （合取范式）6设A=0，1，2， 3，R=|x A，y A且x+y0 ，S=|x A，y A且x+y2，试求R，S，R S，S -1，r(R)R=, S=, R S=，S -1= S，r(R)=IA=,7试求出（PQ）R的析取范式，合取范式，主合取范式（PQ）R (PQ)R (PQ)R（析取范式） (PR) (QR)（合取范式） (PR) (QQ) (QR) (PP) (PRQ) (PRQ) (QRP) (QRP
21、) (PQR) (PQR) (PQR) 8设A=a, b, 1, 2 ，B= a, b, 1, 1 ，试计算（ 1）（A B）（2）（AB）（3）（AB）（AB）（ 1）（A B）=a, b, 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 35 页10 / 35 （ 2）（AB）=a, b, 1, 2, a, b, 1 （ 3）（AB） （AB）=a, b, 2, a, b, 1 9图G=，其中V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (
22、c, d), (d, e) ，对应边的权值依次为2、1、 2、3、6、1、4 及 5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值（1）G的图形表示为：（2）邻接矩阵：0111110110110011100110110（3）粗线表示最小的生成树，权为 7：10设谓词公式)(),(),(),(yFzyyRzxyzQyxPx，试（ 1）写出量词的辖域；（2）指出该公式的自由变元和约束变元（1）x量词的辖域为),(),(zxyzQyxP，z量词的辖域为),(zxyQ, 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1
23、0 页，共 35 页11 / 35 y量词的辖域为),(zyR（2）自由变元为),(),(zxyzQyxP与)( yF中的y，以及),(zyR中的z约束变元为x与),(zxyQ中的z，以及),(zyR中的y11设A=1,2,1,2 ，B=1,2,1,2 ，试计算（ 1）（A B）；（2）（AB）；（3）AB（ 1）A B =1,2 （2）AB =1,2 （3）AB= ， ， ， ， ， ， ， ， ， ，, 12设G=，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，试（1）给出G的图形表示；（2）写出
24、其邻接矩阵；（3）求出每个结点的度数；（4）画出其补图的图形（1）G的图形表示为：（2）邻接矩阵：0110010110110110110000100（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3， 2 （4）补图如下：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 35 页12 / 35 13设集合A=1，2，3，4，R=|x, y A；|x y|=1 或x y=0，试（1）写出R的有序对表示；（2）画出R的关系图；（3）说明R满足自反性，不满足传递性（1）R=, （2）关系图为3）因为 ,均属于R，即A的每个元素构
25、成的有序对均在R中，故R在A上是自反的。因有 与 属于R，但 不属于R，所以R在A上不是传递的。14求PQ R的析取范式，合取范式、主析取范式，主合取范式P（RQ）12 3 4 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 35 页13 / 35 P (RQ) PQR（析取、合取、主合取范式）(PQR) (PQR) (PQR) (PQR) (PQR) (PQR) (PQR) （主析取范式）15设图G=，V= v1，v2，v3，v4，v5，E= (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，
26、(v3, v5)，(v4, v5) ，试(1) 画出G的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出图G的补图的图形（1）关系图（2）邻接矩阵0110010110110110110100110（3）deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 （4）补图v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 35 页14 / 35 16设谓词公式x(A(x,y) zB(x,y, z) yC(y,z)
27、试 (1)写出量词的辖域。x 量词的辖域为(A(x,y) zB(x,y, z), z 量词的辖域为B(x,y,z), y 量词的辖域为C(y,z) (2)指出该公式的自由变元和约束变元. 自由变元为 (A(x,y) zB(x,y, z) 中的 y,以及 C(y,z) 中的 z. 约束变元为 (A(x,y) zB(x,y, z) 中的 x 与 B(x,y,z) 中的 z,以及 C(y,z) 中的 y。六、证明题1试证明：若R与S是集合A上的自反关系，则RS也是集合A上的自反关系证明：设x A，因为R自反，所以x R x，即 R；又因为S自反，所以x R x，即 S即RS 故RS自反2试证明集合等
28、式A (BC)=(AB) (AC) 证明：设S= A (BC)，T=(AB) (AC)，若xS，则xA或xBC，即xA或xB且xA或x C也即xAB且xA C，即xT，所以S T反之，若xT，则xAB且xAC， 即xA或xB且xA或xC，也即xA或xBC，即xS，所以T S因此T=S3试证明集合等式A (BC)=(AB) (AC)精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 35 页15 / 35 证明：设S=A (BC)，T=(AB) (AC)， 若xS，则xA且xBC，即xA且xB或 xA且xC，也即xAB或xAC，即xT，所以
29、S T反之，若xT，则xAB或xAC，即xA且xB 或xA且xC也即xA且xB C，即xS，所以TS因此T=S4试证明集合等式A (BC)=(AB) (AC) 证明：设S= A (BC)，T=(AB) (AC)，若xS，则xA或xBC，即xA或xB且xA或x C也即xAB且xA C，即xT，所以S T反之，若xT，则xAB且xAC，即xA或xB且xA或xC，也即xA或xBC，即xS，所以T S因此T=S5试证明（x）（P（x）R（x）（x）P（x）（x）R（x）证明：（1）（x）（P（x）R（x）P（2）P（a）R（a） ES(1) （3）P（a） T(2)I （4）（x）P（x） EG(3)
30、 （5）R（a） T(2)I （6）（x）R（x） EG(5) （7）（x）P（x）（x）R（x） T(5)(6)I 6设 m 是一个取定的正整数，证明：在任取m1 个整数中，至少有两个整数，它们的差是m 的整数倍证明设1a，2a，1ma为任取的m1 个整数，用m 去除它们所得余数只能是0，1， m1，由抽屉原理可知，1a，2a，1ma这 m1 个整数中至少存在两个数sa和ta，它们被m 除所得余数相同，因此sa和ta的差是m 的整数倍。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 35 页16 / 35 7已知 A、B、C 是三个
31、集合，证明A-(B C)=(A-B) (A-C) 证明 xA-（B C）xA x（B C）xA（ xB xC）（ xA xB）（xA xC）x（A-B ） x（A-C ） x（A-B）（A-C ） A-（B C）=（A-B ）（A-C ）8（ 15 分）设 是半群，对A 中任意元a 和 b，如 a b 必有 a*b b*a ，证明：(1) 对 A 中每个元a，有 a*a a。(2)对 A 中任意元a 和 b，有 a*b*a a。(3)对 A 中任意元a、 b 和 c，有 a*b*c a*c 。证明由题意可知，若a*b b*a，则必有a b。(1)由 (a*a)*a a*(a*a) ，所以 a*
32、aa。(2)由 a*(a*b*a) (a*a)*(b*a) a*b*(a*a) (a*b*a)*a ，所以有a*b*a a。(3)由 (a*c)*(a*b*c) (a*c*a)*(b*c) a*(b*c) (a*b)*c (a*b)*(c*a*c) (a*b*c)*(a*c) ，所以有a*b*c a*c。13. 设 A,B 为任意集合，证明：(A-B)-C = A-(B C). 证明： (A-B)-C = (A B) C = A (B C) = A (B C) = A-(B C) 9求命题公式 (PQ)(P Q) 的主析取范式和主合取范式解： (PQ)(P Q)(PQ) (P Q)(P Q)
33、(P Q)(P Q) (P Q) (P P Q) (Q P Q)(P Q)M1m0 m2 m3 10例5 在边长为1 的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8 。证明：把边长为1 的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。11. 试证明集合等式AU( B C)=(AUB) (AUC). 证明：设S=AU(B C),T=(AUB) (AUC), 若 x S,则 x A 或 x B C，即 x A 或 x B 且 x A 或 x C,也即 x AU
34、B 且 x AUC, 即 x T,所以 sT. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 35 页17 / 35 反之，若x T,则 x AUB 且 x AUC, 即 x A 或 x B 且 x A 或 x C, 也即 x A 或 x B C，即 x S,所以 TS. 因此 T=S. 12. 利用形式演绎法证明：PQ, RS, PR蕴涵QS。证明： PQ, RS, PR蕴涵QS(1) P R P (2) R P Q(1) (3) P Q P (4) R Q Q(2)(3) (5) Q R Q(4) (6) R S P (7) Q
35、 S Q(5)(6) (8) Q S Q(7) 14. 利用形式演绎法证明：A B, C B, C D蕴涵 A D。证明： A B, C B, C D 蕴涵 A D (1) A D(附加 ) (2) A B P (3) B Q(1)(2) (4) C B P (5) B C Q(4) (6) C Q(3)(5) (7) C D P (8) D Q(6)(7) (9) A D D(1)(8) 所以 A B, C B, C D蕴涵 A D. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 35 页18 / 35 15. A, B 为两个任
36、意集合，求证：A(A B) = (A B)B . 证明： A(A B) = A (A B) A (A B) (A A) (A B) (A B) (A B) AB 而 (A B) B = (A B) B = (A B) (B B) = (A B) = A B 所以： A(A B) = (A B) B. 一、单项选择题(每小题 3 分，本题共15 分) 1若集合A=a ，b，则下列表述正确的是( ) 。A A B a A C a，b A D a? A 2设 A=1 ，2，3，4，5，6，B= “ ” 1，2，3，A 到 B 的关系 R= （x，y） x, A , y B,，x=y 2 则 R=(
37、) 。 A ，) B (， C ， ) D ，) 3n 阶无向完全图Kn 的边数及每个结点的度数分别是( ) 。 A n(n 一 1)2， n 一 1 B n 一 1，n C n(n 一 1)，n 一 1 D n(n 一 1)， n 4设无向完全图Kn 有 n 个结点 (n 2)， m 条边，当 ( ) 时， Kn 中存在欧拉回路。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 35 页19 / 35 A m 为奇数 B n 为偶数 C n 为奇数 D m 为偶数 5设个体域为整数集，则公式? x?y(x+y=0) 的解释可为 ( )
38、 。 A 存在一整数x 有整数 y 满足 x+y=0 B 对任一整数x 存在整数y 满足 x+y=0 C 存在一整数x 对任意整数y 满足 x+y=0 D任一整数x 对任意整数y 满足 z+y=O 二、填空题 (每小题 3 分。本题共15 分 ) 6设集合A=1 ，2，3，4)，B=3 ，4，5，6)，C=5 ，6，7，8)，则 A B U C 等于。7设 A=(a，6)，B=1 ，2)，C=4 ，5)，从 A 到 B 的函数f=，从 B 到 C 的函数 g=， ，则等于。8设 G 是一个图，结点集合为V，边集合为E，则 G 的结点度数之和为。 9设 G 是具有 n 个结点 m 条边 k 个面
39、的连通平面图，则n+k-m 等于。 10 设个体域D=1 ，2，3，4)，A(x) 为“ x 等于 3”，则谓词公式 (?x)A(x) 的真值为。三、逻辑公式翻译(每小题 6 分，本题共12 分)。11将语句“他们明天去旅游，仅当明天天晴”翻译成命题公式12将语句“小王是个学生，小李是个职员，而小张是个军人”翻译成命题公式四、判断说明题(每小题 7 分，本题共14 分)。判断下列各题正误，并说明理由13 设 A=1 ，2，3)，R=， ，则 R 是等价关系精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 35 页20 / 35 14 谓
40、词公式 (?x )P(x ，y)(?z)Q(z ，y，z)中?x 量词的辖域为P(z ，y) (?z)Q(x ，y，z)五、计算题 (每小题 12 分，本题共36 分)。 15 设集合 A=a ，b， c)，B=a ，C，试计算：(1)(A B)； (2)(B A)； (3)(A B) B) 16 设 G= ，V=v1 ，v2，v3 ，v4，v5) ，E=(v1 ，v3) ，(v1 ，v5) ，(v2，v3) ，(v2，v5)， (v3，v4) ，试： (1) 给出 G 的图形表示； (2) 写出其邻接矩阵；(3) 求出每个结点的度数； (4) 画出其补图的图形 17 试求出如图一所示赋权图中
41、的最小生成树(要求写出求解步骤)，并求此最小生成树的权六、证明题 (本题共 8 分) 18试证明：一、单项选择题(每小题 3 分，本题共15 分)。1D 2 B 3 A， 4C 5 B 二、填空题 (每小题 3 分，本题共15 分 )。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 35 页21 / 35 63，4，5，6， 7，8 7，) 8 2El(或“边数的两倍” ) 9 2 10 真 (或 T，或 1) 三、逻辑公式翻译(每小题 6 分，本题共12 分)。 11 设 P：他们明天去旅游，Q：明天天晴则命题公式为：P Q 12
42、设 P：小王是个学生，Q：小李是个职员，R：小张是个军人则命题公式为：P Q R 四、判断说明题(每小题 7 分，本题共14 分)。 13 错误。 R 不是等价关系，因R 中不包含 ，故不满足自反性 14 错误 因为紧接于量词之后最小的子公式称为量词的辖域，所以?x 量词的辖域为P(z，y)五、计算题 (每小题 12 分，本题共36 分) 。 15 (1)(A B)=c 。 (2)(B A)=a) ；(3)(A B) B= ， 16(1)G 的图形表示如图二所示：(2)邻接矩阵： (3)v1 ，v2，v3 ，v4，v5 结点的度数依次为2，2，3，1，2 或 deg(v1)=2 ，deg(v2
43、)=2 ，deg(v3)=3 ，deg(v4)=1 ，deg(v5)=2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 35 页22 / 35 (4)补图如图三所示：17用 Kruskal 算法求产生的最小生成树步骤为：vl，v7)=1 选 el=vlv7 v3，v4)=3 ：选 e2=v3v4 v2，v7)=4 选 e3=-v2v7 (v3 ，v7)=9 选 e4=v3v7 (v4 ，v5)=8 选 e5=v4v5 (v 1 ，v 6)=22 选 e6= v l v 6 最小生成树如图四所示：最小生成树的权为：(T)=22+1+4
44、+9+3+18=57六、证明题 (本题共 8 分) 18 证明： (1) 1(A B) P (2) 1A B T(1)E (3)( B C) P (4) C P (5) 1B T(3)(4)I 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 35 页23 / 35 (6) A T(2)(5)I 说明： 1因证明过程中，公式引用的次序可以不同，一般引用前提正确得1 分，利用两个公式得出有效结论得l 或 2 分，最后得出结论得2 或 1 分 2可以用真值表验证一、单项选择题（每小题3 分，本题共15 分）1若集合A=1 ， 2，B=1，2
45、，1，2 ，则下列表述正确的是( a ) A AB，且 AB BBA，且 AB CAB，且 AB DAB，且 AB 2设有向图（a）、（ b）、（ c）与（ d）如图一所示，则下列结论成立的是 ( d ) 图一 A（ a）是强连通的 B （ b）是强连通的C（ c）是强连通的 D （ d）是强连通的3设图G的邻接矩阵为0101010010000011100100110则 G 的边数为 ( b )A6 B 5 C 4 D 3 4无向简单图G 是棵树，当且仅当( a ) AG 连通且边数比结点数少1 B G 连通且结点数比边数少1 CG 的边数比结点数少1 D G 中没有回路5下列公式 ( c )
46、 为重言式APQPQ B(Q(PQ) (Q(PQ) C (P(QP)(P(PQ) D (P (PQ) Q 1若集合A=a，b，B= a，b， a，b ，则（ a ） A AB，且AB B A B，但A B C AB，但 AB D AB，且A B2集合A=1, 2, 3, 4, 5, 6, 7, 8上的关系R=|x+y=10 且x, yA，则R的性质为（ b ） A 自反的 B对称的 C 传递且对称的 D 反自反且传递的3如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有（ b ）个 A 0 B 2 C 1 D 3 4如图一所示，以下说法正确的是 ( d ) A(a,
47、e)是割边 B (a, e)是边割集C(a, e) ,(b, c)是边割集 D (d, e)是边割集图一5设 A（x）： x 是人， B（x）： x 是学生，则命题“不是所有人都是学生”可符号化为（ c ）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 35 页24 / 35 A(x)(A(x) B(x) B(x)(A(x) B(x) C (x)(A(x) B(x) D(x)(A(x) B(x) 1设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=, ，R2=, , ，R3=, ，则（ b ）不是从A到B的函数
48、 A R1和R2 B R2 C R3 D R1和R32设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6 ，则集合B的最大元、最小元、上界、下界依次为( b ) A 8、2、8、 2 B无、 2、无、 2 C 6、2、6、 2 D8、1、6、 1 3若集合A的元素个数为10，则其幂集的元素个数为（ a ） A 1024 B 10 C 100 D 1 4设完全图Kn有n个结点 (n 2)，m条边，当（ c ）时，Kn中存在欧拉回路Am为奇数 B n为偶数 C n为奇数 D m为偶数5已知图G的邻接矩阵为，则G有（ d ）A5 点， 8 边 B6 点， 7
49、边 C 6 点， 8 边 D 5 点， 7 边1若集合A a，a，1， 2，则下列表述正确的是( c ) A a，aA B2A CaA DA 2设图 G ，vV，则下列结论成立的是 ( c ) A deg(v)=2E B deg(v)=ECEvVv2)deg( D EvVv)deg(3命题公式（ P Q）R 的析取范式是 ( d ) A （P Q） R B （ P Q） R C（ P Q） R D（P Q） R 4如图一所示，以下说法正确的是 ( a ) Ae 是割点 Ba, e 是点割集Cb, e 是点割集 D d是点割集5下列等价公式成立的为( b ) APQPQ B P(QP) P(PQ
50、) C Q(PQ) Q (PQ) D P (PQ) Q 1若 G 是一个汉密尔顿图，则G 一定是 ( d ) A 平面图 B对偶图C欧拉图 D连通图2集合 A=1, 2, 3, 4 上的关系R=|x=y 且 x, yA，则 R 的性质为（ c ） A 不是自反的 B 不是对称的 C 传递的 D反自反3设集合 A=1 ，2，3， 4，5，偏序关系是 A 上的整除关系，则偏序集上的元素5 是集合 A 的（ b ） A 最大元 B 极大元 C 最小元 D 极小元4图 G 如图一所示，以下说法正确的是 ( c ) A(a, d) 是割边 B (a, d) 是边割集C(a, d) ,(b, d) 是边割