《电大离散数学本科期末复习题1.docx》由会员分享，可在线阅读，更多相关《电大离散数学本科期末复习题1.docx（35页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学（本）一、单项选择题1设P：a是偶数，Q：b是偶数。R：a + b是偶数，则命题“若a是偶数，b是偶数，则a + b 也是偶数”符号化为（D P QR）。2表达式x（P（x，y）Q（z）y（Q（x，y）zQ（z）中x的辖域是（P（x，y） Q（z）。3设则命题为假的是（）。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已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( 5 )8设无向图G的邻接矩阵为则G的边数
2、为( 7 )9设集合A=a，则A的幂集为(，a )10下列公式中 (AB (AB) )为永真式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)是边割集 ) 图一15设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（(x)(A(x)B(x) ）16若集合A=1，2，B=1，2，1，2，则下列表述正确的是(AB，且AB
3、 )17设有向图（a）、（b）、（c）及（d）如图一所示，则下列结论成立的是 ( （d）是强连通的 )18设图G的邻接矩阵为则G的边数为( 5 )19无向简洁图G是棵树，当且仅当(G连通且边数比结点数少1 )20下列公式 (P(QP)(P(PQ) )为重言式21若集合A a，a，1，2，则下列表述正确的是(aA)22设图G，vV，则下列结论成立的是 ( ) 23命题公式（PQ）R的析取范式是 (（PQ）R )24下列等价公式成立的为(P(QP) P(PQ) )25设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=, ，R2=, , ，R3=, ，则（ R2 ）不是从A到
4、B的函数26设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为 (无、2、无、2)27若集合A的元素个数为10，则其幂集的元素个数为（1024）28如图一所示，以下说法正确的是 (e是割点)图一29设完全图K有n个结点(n2)，m条边，当（ n为奇数）时，K中存在欧拉回路 30已知图G的邻接矩阵为 ，则G有（ 5点，7边 ） 二、填空题（每小题3分，共15分）1设A，B为随意命题公式，C为重言式，若A CBC，那么AB是 重言 式（重言式、冲突式或可满意式）。2命题公式（PQ）P的主合取范式为 。3设集合A=，
5、a，则P（A）= 。4设图G =V，E， G =V，E，若 V=V,E E ,则G是G的生成子图。5在平面G =V，E中，则= 2|E| ，其中（i=1，2，r）是G的面。6命题公式的真值是 假（或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= 空集（或） 12设集合A=1，2，3上的函数分别为：f=,，g=,，则复合
6、函数gf = , , , 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命题公式的真值是 T （或1） 17若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的全部结点得到的连通分支数为W，则S中结点数|S|及W满意的关系式为 W|S| 18给定一个序列集合000，001，01，10，0，若去掉其中的元素 0 ，则该序列集合
7、构成前缀码19已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 20(x)(P(x)Q(x)R(x，y)中的自由变元为 R(x，y )中的y 21设集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元关系，则R的有序对集合为 ，22设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满意的关系式 v-e+r=2 23设G是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树24无向图G存在欧拉回路，当且仅当G连通且 全部结点的度数全为偶数 25设个体域D1,2，则谓词公式消去量词后的等值式为 A(
8、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 条边后使之变成树29设连通平面图G的结点数为5，边数为6，则面数为 3 30设个体域Da, b，则谓词公式(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= |xA且yB且x， yAB 则R的有序对集合为_,_32. 设G是连通
9、平面图，v， e ， r 分别表示G的结点数， 边数和面数， 则 v， e 和r 满意的关系式_v-e+r=2_33.G=是有20个结点，25 条边的连通图,则从G中删去_6_条边，可以确定图G的一棵生成树.34. 无向图G存在欧拉回路， 当且仅当G全部结点的度数全为偶数且_ 连通_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的表达式知，即R具有自反性； 三、逻辑公式翻译1将语句“
10、今日上课”翻译成命题公式设P：今日上课， 则命题公式为：P 2将语句“他去操场熬炼，仅当他有时间”翻译成命题公式设 P：他去操场熬炼，Q：他有时间， 则命题公式为：P Q3将语句“他是学生”翻译成命题公式设P：他是学生， 则命题公式为： P 4将语句“假如明天不下雨，我们就去郊游”翻译成命题公式设P：明天下雨，Q：我们就去郊游， 则命题公式为： P Q 5将语句“他不去学校”翻译成命题公式设P：他去学校， P 6将语句“他去旅游，仅当他有时间”翻译成命题公式设 P：他去旅游，Q：他有时间， P Q 7将语句“全部的人都学习努力”翻译成命题公式设P(x)：x是人，Q(x)：x学习努力， （x）(
11、P(x)Q(x)8将语句“假如你去了，那么他就不去”翻译成命题公式设P：你去，Q：他去， PQ 9将语句“小王去旅游，小李也去旅游”翻译成命题公式设P：小王去旅游，Q：小李去旅游， PQ 10将语句“全部人都去工作”翻译成谓词公式设P(x)：x是人，Q(x)：x去工作， (x)(P(x)Q(x) 11将语句“假如全部人今日都去参与活动，则明天的会议取消”翻译成命题公式 设P：全部人今日都去参与活动，Q：明天的会议取消， P Q 12将语句“今日没有人来” 翻译成命题公式设 P：今日有人来， P13将语句“有人去上课” 翻译成谓词公式设P(x)：x是人，Q(x)：x去上课， ($x)(P(x)
12、Q(x)1 1. 将语句假如小李学习努力，那么他就会获得好成果. 翻译成命题公式. 设P：小李学习努力，Q:小李会获得好成果，PQ12. 将语句小张学习努力,小王获得好成果. 翻译成命题公式.设P：小张学习努力，Q:小王获得好成果，PQ四、推断说明题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条边的连通简洁平面图，若v3，则e3v-6”3设N、R分别为自然数集及实数集，f：NR，f (x)=x+6，则f是单射正确 设x
13、1，x2为自然数且x1x2，则有f(x1)= x1+6 x2+6= 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为平面图错误 不满意“设G是一个有v个结点e条边的连通简洁平面图，若v3，则e3v-6”7假如R1和R2是A上的自反关系，则R1R2是自反的正确 R1和R2是自反的，x A， R1， R2，则 R1R2，所以R
14、1R2是自反的 8如图二所示的图G存在一条欧拉回路v1v2v3v5v4dbacefghn图二 正确 因为图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）PT10若偏序集的哈斯图如图一所示，则集合A的最大
15、元为a，最小元不存在 图一正确 对于集合A的随意元素x，均有R（或xRa），所以a是集合A中的最大元依据最小元的定义，在集合A中不存在最小元 11. 假如R1和R2是A上的自反关系， 则R1R2是自反的。正确，R1和R2，是自反的，xA,R1,R2,则 R1R2，所以R1R2是自反的.12. 如图二所示的图中存在一条欧拉回路.图二正确，因为图G为连通的，且其中每个顶点的度数为偶数。五计算题（每小题12分，本题共36分）1试求出（PQ）（RQ）的析取范式（PQ）（RQ） (PQ)（RQ） (PQ)（RQ） (PQ)RQ（析取范式） 2设A=1, 1, 2，B= 1, 2，试计算（1）（AB） （
16、2）（AB） （3）A -（AB）（1）（AB）=1 （2）（AB）=1, 2, 1, 2 （3） A-（AB）=1, 1, 2 3图G=，其中V= a, b, c, d ，E= (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)，对应边的权值依次为1、2、3、1、4及5，试（1）画出G的图形； （2）写出G的邻接矩阵；图一ooooabcd112453（3）求出G权最小的生成树及其权值（1）G的图形表示如图一所示： 图二ooooabcd112453（2）邻接矩阵： （3）最小的生成树如图二中的粗线所示： 权为：1+1+3=5 4画一棵带权为1, 2,
17、 2, 3, 4的最优二叉树,计算它们的权ooooooooo1223347512最优二叉树如图三所示 图三权为13+23+22+32+42=27 5求（PQ）R的析取范式及合取范式（PQ）R （PQ）R (PQ)R （析取范式） (PR)(QR) （合取范式） 6设A=0，1，2，3，R=|xA，yA且x+y0，S=|xA，yA且x+y2，试求R，S，RS，S -1，r(R)R=, S=, RS=， S -1= S， r(R)=IA=,7试求出（PQ）R的析取范式，合取范式，主合取范式（PQ）R(PQ)R (PQ)R（析取范式） (PR) (QR)（合取范式） (PR)(QQ) (QR)(PP
18、) (PRQ)(PRQ) (QRP)(QRP) (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 （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), (c, d), (d, e) ，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G
19、的图形； （2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值（1）G的图形表示为： （2）邻接矩阵： （3）粗线表示最小的生成树， 权为7： 10设谓词公式，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元（1）$x量词的辖域为， z量词的辖域为, y量词的辖域为 （2）自由变元为及中的y，以及中的z 约束变元为x及中的z，以及中的y 11设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
20、,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，试（1）给出G的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形（1）G的图形表示为： （2）邻接矩阵： （3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 （4）补图如下： 13设集合A=1，2，3，4，R=|x, yA；|x-y|=1或x-y=0，试（1）写出R的有序对表示； （2）画出R的关系图；（3）说明R满意自反性，不满意传递性（1）R=, 1234（2）关系图为 3）因为,均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 因有及属于R，
21、但不属于R，所以R在A上不是传递的。14求PQR的析取范式，合取范式、主析取范式，主合取范式P（RQ）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)，(v3, v5)，(v4, v5) ，试(1) 画出G的图形表示；(2) 写出其邻接矩阵；(3) 求出每个结点的度数；v1v2v3v4v5ooooo(4) 画出图G的补图的图形（1）关系图 （2）邻接矩阵 （
22、3）deg(v1)=2deg(v2)=3deg(v3)=4deg(v4)=3v1v2v3v4v5ooooodeg(v5)=2 （4）补图16设谓词公式$x(A(x,y) zB(x,y, z) yC(y,z) 试 (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及
23、S是集合A上的自反关系，则RS也是集合A上的自反关系证明：设xA，因为R自反，所以x R x，即R；又因为S自反，所以x R x，即S 即RS 故RS自反2试证明集合等式A (BC)=(AB) (AC) 证明：设S= A (BC)，T=(AB) (AC)，若xS，则xA或xBC，即 xA或xB 且 xA或xC也即xAB 且 xAC ，即 xT，所以ST 反之，若xT，则xAB 且 xAC， 即xA或xB 且 xA或xC， 也即xA或xBC，即xS，所以TS因此T=S3试证明集合等式A (BC)=(AB) (AC)证明：设S=A(BC)，T=(AB)(AC)， 若xS，则xA且xBC，即 xA且
24、xB 或 xA且xC，也即xAB 或 xAC ，即 xT，所以ST 反之，若xT，则xAB 或 xAC， 即xA且xB 或 xA且xC 也即xA且xBC，即xS，所以TS 因此T=S4试证明集合等式A (BC)=(AB) (AC) 证明：设S= A (BC)，T=(AB) (AC)，若xS，则xA或xBC，即 xA或xB 且 xA或xC也即xAB 且 xAC ，即 xT，所以ST 反之，若xT，则xAB 且 xAC， 即xA或xB 且 xA或xC， 也即xA或xBC，即xS，所以TS因此T=S5试证明（$x）（P（x）R（x） （$x）P（x）（$x）R（x）证明： （1）（$x）（P（x）R
25、（x） P （2）P（a）R（a） ES(1) （3）P（a） T(2)I （4）（$x）P（x） EG(3) （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的整数倍证明 设，为任取的m1个整数，用m去除它们所得余数只能是0，1，m1，由抽屉原理可知，这m1个整数中至少存在两个数和，它们被m除所得余数一样，因此和的差是m的整数倍。7已知A、B、C是三个集合，证明A-(BC)=(A-B)(A-C) 证明 x A-（BC） x Ax（BC） x
26、 A（xBxC） （x AxB）（x AxC） x（A-B）x（A-C） x（A-B）（A-C）A-（BC）=（A-B）（A-C）8（15分）设是半群，对A中随意元a和b，如ab必有a*bb*a，证明：(1)对A中每个元a，有a*aa。 (2)对A中随意元a和b，有a*b*aa。 (3)对A中随意元a、b和c，有a*b*ca*c。证明 由题意可知，若a*bb*a，则必有ab。(1)由(a*a)*aa*(a*a)，所以a*aa。(2)由a*(a*b*a)(a*a)*(b*a)a*b*(a*a)(a*b*a)*a，所以有a*b*aa。(3)由(a*c)*(a*b*c)(a*c*a)*(b*c)a*
27、(b*c)(a*b)*c(a*b)*(c*a*c)(a*b*c)*(a*c)，所以有a*b*ca*c。13. 设A,B为随意集合，证明：(A-B)-C = A-(BC).证明：(A-B)-C = (AB)C = A(BC)= A(BC)= A-(BC)9求命题公式(PQ)(PQ) 的主析取范式和主合取范式解：(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) (PPQ)(QPQ)(PQ)M1m0m2m310例5在边长为1的正方形内随意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8。证明：把边长为1的正方形分成四个全等的小正方形，则至少有一
28、个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。11. 试证明集合等式AU( BC)=(AUB) (AUC).证明：设S=AU(BC),T=(AUB) (AUC),若xS,则xA或xBC，即xA或xB且xA或xC,也即xAUB且xAUC,即xT,所以sT.反之，若xT,则xAUB且xAUC,即xA或xB且xA或xC,也即xA或xBC，即xS,所以TS.因此T=S.12. 利用形式演绎法证明：PQ, RS, PR蕴涵QS。证明：PQ, RS, PR蕴涵QS(1) PRP(2) RPQ(1)(3) PQP(4) RQQ(2)(3)(5) QRQ(4)(6)
29、 RSP(7) QSQ(5)(6)(8) QSQ(7)14.利用形式演绎法证明：AB, CB, CD蕴涵AD。证明：AB, CB, CD蕴涵AD(1) AD(附加)(2) ABP(3) BQ(1)(2)(4) CBP(5) BCQ(4)(6) CQ(3)(5)(7) CDP(8) DQ(6)(7)(9) ADD(1)(8)所以 AB, CB, CD蕴涵AD.15. A, B为两个随意集合，求证：A(AB) = (AB)B .证明：A(AB) = A(AB)A(AB)(AA)(AB)(AB)(AB)AB而 (AB)B= (AB)B= (AB)(BB)= (AB)= AB所以：A(AB) = (A
30、B)B.一、单项选择题(每小题3分，本题共15分) 1若集合A=a，b，则下列表述正确的是( ) 。AA BaA Ca，bA DaA 2设A=1，2，3，4，5，6，B=“”1，2，3，A到B的关系R=（x，y）x,A , yB,，x=y 则R=( ) 。 A，) B(， C，) D，) 3n阶无向完全图Kn的边数及每个结点的度数分别是( ) 。 An(n一1)2，n一1 Bn一1，n Cn(n一1)，n一1 Dn(n一1)，n 4设无向完全图Kn有n个结点(n2)，m条边，当( )时，Kn中存在欧拉回路。 Am为奇数 Bn为偶数 Cn为奇数 Dm为偶数 5设个体域为整数集，则公式xy(x+y
31、=0)的说明可为( ) 。 A存在一整数x有整数y满意x+y=0 B对任一整数x存在整数y满意x+y=0 C存在一整数x对随意整数y满意x+y=0D任一整数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个面的连通平面图，则n+k-m等于。 10设个体域D=1，2，3，4)，A(x)为“x等于
32、3”，则谓词公式 (x)A(x)的真值为。三、逻辑公式翻译(每小题6分，本题共12分)。11将语句“他们明天去旅游，仅当明每天晴”翻译成命题公式12将语句“小王是个学生，小李是个职员，而小张是个军人”翻译成命题公式四、推断说明题(每小题7分，本题共14分)。推断下列各题正误，并说明理由13设A=1，2，3)，R=，则R是等价关系 14谓词公式(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)(AB)； (2)(BA)； (3)(AB)B) 16设G=，V=v1，v2，v3，v4，v5)，E=(v1，v3