电大离散数学本科期末复习题.docx

电大离散数学本科期末复习题离散数学 一、单项选择题 1设P：a是偶数，Q：b是偶数。R：a + b是偶数，则命题“若a是偶数，b是偶数，则a + b 也是偶数”符号化为。 2表达式"xÚQ）Ù3设S1）中"x的辖域是 Q）。 $y"zQ。 =Æ,S2=Æ,S3=P(Æ),S4=P(Æ)则命题为假的是4设G是有n个结点的无向完全图，则G的边数）。 5设G是连通平面图，有v个结点，e条边，r个面，则r=。 6若集合A=1，2，1，2，则下列表述正确的是( 1ÌA ) 7已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( 5 ) é0ê18设无向图G的邻接矩阵为êê1êê1êë11111ù0011úú则G的边数为( 7 ) 0000úú1001ú1010úû9设集合A=a，则A的幂集为(Æ，a ) 10下列公式中 (ØAÙØB « Ø(AÚB) )为永真式 11若G是一个汉密尔顿图，则G一定是( 连通图 ) 12集合A=1, 2, 3, 4上的关系R=<x，y>|x=y且x, yÎA，则R的性质为 13设集合A=1，2，3，4，5，偏序关系£是A上的整除关系，则偏序集<A，£>上的元素5是集合A的 14图G如图一所示，以下说法正确的是 ( (a, d) ,(b, d)是边割集 ) 16若集合A=1，2，B=1，2，1，2，则下列表述正确的是(AÌB，且AÎB ) 图一 15设A：x是人，B：x是工人，则命题“有人是工人”可符号化为 17设有向图、与如图一所示，则下列结论成立的是 ( 是强连通的 ) é0ê118设图G的邻接矩阵为êê1êê0êë01100ù0011úú则G的边数为( 5 ) 0000úú1001ú1010úû19无向简单图G是棵树，当且仅当(G连通且边数比结点数少1 ) 20下列公式 (P®(ØQ®P)«(ØP®(P®Q) )为重言式 21若集合A a，a，1，2，则下列表述正确的是(aÍA) 22设图G<V, E>，vÎV，则下列结论成立的是 (ådeg(v)=2E ) vÎV23命题公式R的析取范式是 (R ) 24下列等价公式成立的为(P®(ØQ®P) ÛØP®(P®Q) ) 25设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=<a，2>, <b，2>，R2=<a，1>, <a，2>, <b，1>，R3=<a，1>, <b，2>，则不是从A到B的函数 26设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为 (无、2、无、2) 27若集合A的元素个数为10，则其幂集的元素个数为 1 / 10 28如图一所示，以下说法正确的是 (e是割点)图一 29设完全图Kn有n个结点(n2)，m条边，当时，Kn中存在欧拉回路 30已知图G的邻接矩阵为 二、填空题 ，则G有 1设A，B为任意命题公式，C为重言式，若A ÙCÛBÙC，那么A«B是 重言 式。 2命题公式ÚP的主合取范式为 (PÚQ)Ù(ØPÚQ) 。 3设集合A=Æ，a，则P= Æ,Æ,a,Æ,a 。 4设图G =V，E， G =V，E，若 V=V,E E ,则G是G的生成子图。 5在平面G =V，E中，则 ådeg(r)= 2|E| ，其中r是G的面。6命题公式PÙØP的真值是 假 irii=17若无向树T有5个结点，则T的边数为 4 8设正则m叉树的树叶数为t，分支数为i，则(m-1)i= t-1 9设集合A=1，2上的关系R<1, 1>,<1, 2>，则在R中仅需加一个元素 <2, 1> ，就可使新得到的关系为对称的 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=<1,2>,<2,1>,<3,3>,，g=<1,3>,<2,2>,<3,2>,，则复合函数g°f = <1, 2>, <2, 3>, <3, 2>, 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) 的真值为 假 16命题公式P®(QÚP)的真值是 T 17若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 W£|S| 18给定一个序列集合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 )中的y 21设集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元关系，R=<<2, 2>，<2, 3>，<3, 2>，<3, 3> 22设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式 v-e+r=2 23设G<V, E>是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树 24无向图G存在欧拉回路，当且仅当G连通且 所有结点的度数全为偶数 25设个体域D1,2，则谓词公式$xA(x)消去量词后的等值式为 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 条边后使之变成树 29设连通平面图G的结点数为5，边数为6，则面数为 3 2 / 10 x,y>xÎA且yÎB且x,yÎAÇB则R的有序对集合为 30设个体域Da, b，则谓词公式("x)A(x)B消去量词后的等值式为 (A (a)A (b)(BB) 31. 设集合A=0，1 ，2 ，B=l ，2 ，3 ， 剖，R 是A到B 的二元关系，R= <x ,y> |xA且yB且x， yAB 则R的有序对集合为_<1,1>,<1,2>,<2,1>,<2,2>_ 32. 设G是连通平面图，v， e ， r 分别表示G的结点数， 边数和面数， 则 v， e 和r 满足的关系式_v-e+r=2_ 33.G=<V,E>是有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的表达式知，"xÎA,(x,x)ÎR,即R具有自反性； 三、逻辑公式翻译 1将语句“今天上课”翻译成命题公式 设P：今天上课， 则命题公式为：P 2将语句“他去操场锻炼，仅当他有时间”翻译成命题公式 设 P：他去操场锻炼，Q：他有时间， 则命题公式为：P ®Q 3将语句“他是学生”翻译成命题公式 设P：他是学生， 则命题公式为： P 4将语句“如果明天不下雨，我们就去郊游”翻译成命题公式 设P：明天下雨，Q：我们就去郊游， 则命题公式为：Ø P® Q 5将语句“他不去学校”翻译成命题公式 设P：他去学校， Ø P 6将语句“他去旅游，仅当他有时间”翻译成命题公式 设 P：他去旅游，Q：他有时间， P ®Q 7将语句“所有的人都学习努力”翻译成命题公式 设P(x)：x是人，Q(x)：x学习努力， (P(x)®Q(x) 8将语句“如果你去了，那么他就不去”翻译成命题公式 设P：你去，Q：他去， P®ØQ 9将语句“小王去旅游，小李也去旅游”翻译成命题公式 设P：小王去旅游，Q：小李去旅游， PÙQ 10将语句“所有人都去工作”翻译成谓词公式 设P(x)：x是人，Q(x)：x去工作， ("x)(P(x)®Q(x) 11将语句“如果所有人今天都去参加活动，则明天的会议取消”翻译成命题公式 设P：所有人今天都去参加活动，Q：明天的会议取消， P® Q 12将语句“今天没有人来” 翻译成命题公式 设 P：今天有人来， Ø P 13将语句“有人去上课” 翻译成谓词公式 设P(x)：x是人，Q(x)：x去上课， ($x)(P(x) ÙQ(x) 1 1. 将语句"如果小李学习努力，那么他就会取得好成绩. "翻译成命题公式. 设P：小李学习努力，Q:小李会取得好成绩，PQ 12. 将语句"小张学习努力,小王取得好成绩. "翻译成命题公式. 设P：小张学习努力，Q:小王取得好成绩，PQ 四、判断说明题 1设集合A=1，2，B=3，4，从A到B的关系为f=<1, 3>，则f是A到B的函数 错误 因为A中元素2没有B中元素与之对应，故f不是A到B的函数 2设G是一个有4个结点10条边的连通图，则G为平面图 错误 不满足“设G是一个有v个结点e条边的连通简单平面图，若v3，则e3v-6” 3 / 10 3设N、R分别为自然数集与实数集，f：NR，f (x)=x+6，则f是单射 正确 设x1，x2为自然数且x1¹x2，则有f(x1)= x1+6¹ x2+6= f(x2)，故f为单射 4下面的推理是否正确，试予以说明 (1) FG 前提引入 (2) FG US 错误 应为FG，换名时，约束变元与自由变元不能混淆 5如图二所示的图G存在一条欧拉回路 图二 错误 因为图G为中包含度数为奇数的结点 6设G是一个有6个结点14条边的连通图，则G为平面图 错误 不满足“设G是一个有v个结点e条边的连通简单平面图，若v3，则e3v-6” 7如果R1和R2是A上的自反关系，则R1R2是自反的 正确 R1和R2是自反的，"x ÎA，<x, x> Î R1，<x, x> ÎR2，则<x, x> Î R1ÈR2，所以R1R2是自反的 8如图二所示的图G存在一条欧拉回路 v5 d v4 e g v1 f n c a h v2 b v3 图二 正确 因为图G为连通的，且其中每个顶点的度数为偶数 9PP为永真式 正确 PP是由P与P组成的析取式， 如果P的值为真，则PP为真， 如果P的值为假，则P与PQ为真，即P为真， 也即PP为真， 所以PP是永真式 另种说明： PP是由P与P组成的析取式， 只要其中一项为真，则整个公式为真 可以看到，不论P的值为真或为假，P与P总有一个为真， 所以PP是永真式 或用等价演算PPÛT 10若偏序集<A，R>的哈斯图如图一所示，则集合A的最大元为a，最小元不存在 图一 正确 对于集合A的任意元素x，均有<x, a>ÎR，所以a是集合A中的最大元按照最小元的定义，在集合A中不存在最小元 4 / 10 11. 如果R1和R2是A上的自反关系， 则R1R2是自反的。 正确，R1和R2，是自反的，"xA,<x,x>R1,<x,x>R2,则<x,x> R1R2，所以R1R2是自反的. 12. 如图二所示的图中存在一条欧拉回路. 图二 正确，因为图G为连通的，且其中每个顶点的度数为偶数。 五计算题 1试求出的析取范式 Û (PQ) Û (PQ) Û (PQ)RQ 2设A=1, 1, 2，B= 1, 2，试计算 A - =1 =1, 2, 1, 2 A-=1, 1, 2 3图G=<V, E>，其中V= a, b, c, d ，E= (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)，对应边的权值依次为1、2、3、1、4及5，试 画出G的图形； 写出G的邻接矩阵； 求出G权最小的生成树及其权值 a o d G的图形表示如图一所示： o 3 1 2 4 5 b o 1 oc 图一 éê0111ù邻接矩阵：ê1011úêê1101úú ë1110úû a o 3 o d 最小的生成树如图二中的粗线所示： 1 2 4 5 权为：1+1+3=5 b o o 1 c 图二 4画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权 最优二叉树如图三所示 o12 7 o o 5 3 o o oo o 4 2 3 图三 1 o2 权为1´3+2´3+2´2+3´2+4´2=27 5 / 10 5求R的析取范式与合取范式 R Û ØR Û (ØPØQ)R Û (ØPR)(ØQR) 6设A=0，1，2，3，R=<x，y>|xÎA，yÎA且x+y<0，S=<x，y>|xÎA，yÎA且x+y£2，试求R，S，R·S，S -1，r(R) R=Æ, S=<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0> R·S=Æ， S -1= S， r(R)=IA=<0,0>,<1,1>,<2,2>,<3,3> 7试求出R的析取范式，合取范式，主合取范式 RÛ(PQ)RÛ (PQ)R Û (PR) (QR) Û (PR)(QQ) (QR)(PP) Û (PRQ)(PRQ) (QRP) (QRP) Û (PQR)(PQR) (PQR) 8设A=a, b, 1, 2，B= a, b, 1, 1，试计算 - =a, b, 2 =a, b, 1, 2, a, b, 1 -=a, b, 2, a, b, 1 9图G=<V, E>，其中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，试 画出G的图形； 写出G的邻接矩阵； 求出G权最小的生成树及其权值 G的图形表示为： 邻接矩阵： é0ê1êê1êê0êë11101ù0011úú0011ú ú1101ú1110úû粗线表示最小的生成树， 权为7： 6 / 10 10设谓词公式$x(P(x,y)®"zQ(y,x,z)Ù"yR(y,z)«F(y)，试写出量词的辖域； 指出该公式的自由变元和约束变元 $x量词的辖域为(P(x,y)®"zQ(y,x,z)， "z量词的辖域为Q(y,x,z), "y量词的辖域为R(y,z) 自由变元为(P(x,y)®"zQ(y,x,z)与F(y)中的y，以及R(y,z)中的z 约束变元为x与Q(y,x,z)中的z，以及R(y,z)中的y 11设A=1,2,1,2，B=1,2,1,2，试计算 ； ； A×B A-B =1,2 AB =1,2 A×B=<1,1>，<1,2>，<1,1,2>，<2,1>，<2,2>， <2,1,2>，<1,1>，<1,2>，<1, 1,2>，<2,1>，<2,2>, <2, 1,2> 12设G=<V，E>，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) ，试 给出G的图形表示； 写出其邻接矩阵； 求出每个结点的度数； 画出其补图的图形 G的图形表示为： 邻接矩阵： éê00100ùê00110úêê11011úú ê01101úêúë00110úûv1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 补图如下： 7 / 10 13设集合A=1，2，3，4，R=<x, y>|x, yÎA；|x-y|=1或x-y=0，试 写出R的有序对表示； 画出R的关系图； 说明R满足自反性，不满足传递性 R=<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3> 关系图为 1 ° 2 3 ° ° 4 ° 3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的。 14求P®QÚR的析取范式，合取范式、主析取范式，主合取范式 P ÛP(RQ) Û PQR Û(PQR)(PQR) (PQR) (PQR) (PQR) (PQR) (PQR) 15设图G=<V，E>，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) 求出每个结点的度数； (4) 画出图G的补图的图形 v关系图 o1 v2 o o v5 o o v3 v4 éê01100ù邻接矩阵 ê10110úêê11011úú ê01101úêúë00110úûdeg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 补图 v1 o v2 o o v5 vo o 3 v4 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。 六、证明题 8 / 10 1试证明：若R与S是集合A上的自反关系，则RS也是集合A上的自反关系 证明：设"xÎA，因为R自反，所以x R x，即< x, x>ÎR； 又因为S自反，所以x R x，即< x, x >ÎS 即< x, x>ÎRS 故RS自反 2试证明集合等式AÈ (BÇC)=(AÈB) Ç (AÈC) 证明：设S= AÈ (BÇC)，T=(AÈB) Ç (AÈC)，若xS，则xA或xBÇC，即 xA或xB 且 xA或xC 也即xAÈB 且 xAÈC ，即 xT，所以SÍT 反之，若xT，则xAÈB 且 xAÈC， 即xA或xB 且 xA或xC， 也即xA或xBÇC，即xS，所以TÍS 因此T=S 3试证明集合等式AÇ (BÈC)=(AÇB) È (AÇC) 证明：设S=A(BC)，T=(AB)(AC)， 若xS，则xA且xBC，即 xA且xB 或 xA且xC， 也即xAB 或 xAC ，即 xT，所以SÍT 反之，若xT，则xAB 或 xAC， 即xA且xB 或 xA且xC 也即xA且xBC，即xS，所以TÍS 因此T=S 4试证明集合等式AÈ (BÇC)=(AÈB) Ç (AÈC) 证明：设S= AÈ (BÇC)，T=(AÈB) Ç (AÈC)，若xS，则xA或xBÇC，即 xA或xB 且 xA或xC 也即xAÈB 且 xAÈC ，即 xT，所以SÍT 反之，若xT，则xAÈB 且 xAÈC， 即xA或xB 且 xA或xC， 也即xA或xBÇC，即xS，所以TÍS 因此T=S 5试证明R）Þ PR 证明： R） P PR ES(1) P T(2)I P EG(3) R T(2)I R EG(5) PR T(5)(6)I 6设m是一个取定的正整数，证明：在任取m1个整数中，至少有两个整数，它们的差是m的整数倍 证明 设a1，a2，am+1为任取的m1个整数，用m去除它们所得余数只能是0，1，m1，由抽屉原理可知，a1，a2，am+1这m1个整数中至少存在两个数as和at，它们被m除所得余数相同，因此as和at的差是m的整数倍。 7已知A、B、C是三个集合，证明A-(BC)=(A-B)(A-C) 证明 xÎ A-Û xÎ AxÏÛ xÎ AÛ Û xÎxÎÛ xÎA-= 8设<A，*>是半群，对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*(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 / 10 9求命题公式(ØP®Q)®(PØQ) 的主析取范式和主合取范式 解：(ØP®Q)®(PØQ)ÛØ(ØP®Q)(PØQ)ÛØ(PQ)(PØQ)Û(ØPØQ)(PØQ) Û(ØPPØQ)(ØQPØQ)Û(PØQ)ÛM1Ûm0m2m3 10例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形面积不超过1/8。 证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形面积不超过小正方形的一半，即1/8。 11. 试证明集合等式AU( BC)=(AUB) (AUC). 证明：设S=AU(BC),T=(AUB) (AUC),若xS,则xA或xBC， 即xA或xB且xA或xC,也即xAUB且xAUC, 即xT,所以sÍT. 反之，若xT,则xAUB且xAUC, 即xA或xB且xA或xC, 也即xA或xBC，即xS,所以TÍS. 因此T=S. 12. 利用形式演绎法证明：PQ, RS, PR蕴涵QS。 证明：PQ, RS, PR蕴涵QS (1) PR P (2) ØRP Q(1) (3) PQ P (4) ØRQ Q(2)(3) (5) ØQR Q(4) (6) RS P (7) ØQS Q(5)(6) (8) QS Q(7) 14.利用形式演绎法证明：ØAB, ØCØB, CD蕴涵AD。 证明：ØAB, ØCØB, CD蕴涵AD (1) A D(附加) (2) ØAB P (3) B Q(1)(2) (4) ØCØB P (5) BC Q(4) (6) C Q(3)(5) (7) CD P (8) D Q(6)(7) (9) AD D(1)(8) 所以 ØAB, ØCØB, 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) = (AB)B. 10 / 10