2017年电大离散数学(本科)考试试题及答案参考资料小抄.doc

中央电大离散数学（本科）考试试题一、单项选择题（每小题3分，本题共15分）1若集合A=1，2，B=1，2，1，2，则下列表述正确的是( a ) AAÌB，且AÎB BBÌA，且AÎBCAÌB，且AÏB DAËB，且AÎB 2设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( d ) 图一 A（a）是强连通的 B（b）是强连通的C（c）是强连通的 D（d）是强连通的3设图G的邻接矩阵为则G的边数为( b )A6 B5 C4 D34无向简单图G是棵树，当且仅当( a )AG连通且边数比结点数少1 BG连通且结点数比边数少1CG的边数比结点数少1 DG中没有回路5下列公式 ( c )为重言式AØPÙØQ«PÚQ B(Q®(PÚQ) «(ØQÙ(PÚQ) C(P®(ØQ®P)«(ØP®(P®Q) D(ØPÚ(PÙQ) «Q1若集合A=a，b，B= a，b， a，b ，则（ a ） AAÌB，且AÎB BAÎB，但AËB CAÌB，但AÏB DAËB，且AÏB2集合A=1, 2, 3, 4, 5, 6, 7, 8上的关系R=<x，y>|x+y=10且x, yA，则R的性质为（ b ） A自反的 B对称的 C传递且对称的 D反自反且传递的3如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有（ b ）个 A0 B2 C1 D34如图一所示，以下说法正确的是 ( d ) A(a, e)是割边 B(a, e)是边割集C(a, e) ,(b, c)是边割集 D(d, e)是边割集 图一5设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（ c ）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=<a，2>, <b，2>，R2=<a，1>, <a，2>, <b，1>，R3=<a，1>, <b，2>，则（ b ）不是从A到B的函数 AR1和R2 BR2 CR3 DR1和R32设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为 ( b ) A8、2、8、2 B无、2、无、2 C6、2、6、2 D8、1、6、13若集合A的元素个数为10，则其幂集的元素个数为（ a ） A1024 B10 C100 D14设完全图K有n个结点(n2)，m条边，当（ c ）时，K中存在欧拉回路Am为奇数 Bn为偶数 Cn为奇数 Dm为偶数5已知图G的邻接矩阵为 ，则G有（ d ） A5点，8边 B6点，7边 C6点，8边 D5点，7边1若集合A a，a，1，2，则下列表述正确的是( c ) Aa，aÎA B2ÍACaÍA DÆÎA 2设图G<V, E>，vÎV，则下列结论成立的是 ( c ) Adeg(v)=2½E½ B deg(v)=½E½ C D3命题公式（PQ）R的析取范式是 ( d ) AØ（PQ）R B（PQ）R C（PQ）R D（ØPØQ）R4如图一所示，以下说法正确的是 ( a )Ae是割点 Ba, e是点割集Cb, e是点割集 Dd是点割集5下列等价公式成立的为( b )AØPÙØQÛPÚQ BP®(ØQ®P) ÛØP®(P®Q) CQ®(PÚQ) ÛØQÙ(PÚQ) DØPÚ(PÙQ) ÛQ1若G是一个汉密尔顿图，则G一定是( d ) A平面图 B对偶图C欧拉图 D连通图2集合A=1, 2, 3, 4上的关系R=<x，y>|x=y且x, yA，则R的性质为（ c ） A不是自反的 B不是对称的 C传递的 D反自反3设集合A=1，2，3，4，5，偏序关系£是A上的整除关系，则偏序集<A，£>上的元素5是集合A的（ b ） A最大元 B极大元 C最小元 D极小元4图G如图一所示，以下说法正确的是 ( c ) A(a, d)是割边 B(a, d)是边割集C(a, d) ,(b, d)是边割集 D(b, d)是边割集 图一5设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（ a ）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，a，则下列表述正确的是( a ) AaÍA BaÍACa，aÎA DÆÎA2命题公式（PQ）的合取范式是 ( c ) A（PQ） B（PQ）（PQ） C（PQ） DØ（ØPØQ）3无向树T有8个结点，则T的边数为( b )A6 B7 C8 D9 4图G如图一所示，以下说法正确的是 ( b )Aa是割点 Bb, c是点割集Cb, d是点割集 Dc是点割集 图一5下列公式成立的为( d )AØPØQ Û PQ BP®ØQ Û ØP®Q CQ®P Þ P DØP(PQ)ÞQ1“小于5的非负整数集合”采用描述法表示为_a_ Ax½xN, x<5 Bx½xR, x<5 Cx½xZ, x<5 Dx½xQ, x<5 2设R1，R2是集合A=a,b,c,d上的两个关系，其中R1=(a,a),(b,b),(b,c), (d,d)，R2=(a,a),(b,b),(b,c),(c,b),(d,d)，则R2是R1的_b_闭包 A自反 B对称 C传递 D以上答案都不对 3设函数f：RR，f(a)=2a+1；g：RR，g(a)=a2，则_c_有反函数 Afg Bgf Cf Dg 4已知图G的邻接矩阵为，则图G有_d_ A5点，8边 B6点，7边 C6点，8边 D5点7边 5无向完全图K4是_a_ A汉密尔顿图 B欧拉图 C非平面图 D树 6在5个结点的完全二叉树中，若有4条边，则有_b_片树叶 A2 B3 C4 D5 7无向树T有7片树叶，3个3度结点，其余的都是4度结点，则T有_c_个4度结点 A3 B2 C1 D0 8与命题公式P®（Q®R）等值的公式是_a_ A(PÙQ)®R B(PÚQ)®R C(P®Q)®R DP®(QÚR) 9谓词公式中量词"x的辖域是_b_ A B CP(x) D 10谓词公式的类型是_c_ A蕴涵式 B永假式 C永真式 D非永真的可满足式1设A=1,2,3,4，B=1,3，C=-1,0,1,2，则_a_ A B C D 2若集合A的元素个数为10，则其幂集的元素个数为_b_ A1000 B1024 C1 D10 3设集合A=1,2，B=a,b，C=，则_c_ A<1,a,>,<1,b,>,<2,a,>,<2,b,> B<1,<a,>>,<1,<b,>>,<2,<a,>>,<2,<b,>> C<<1,a>,>,<<1,b>,>,<<2,a>,>,<<2,b>,> D1,2,a,b, 4设A=1, 2, 3, 4, 5, 6, 7, 8，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为_d_ A8、1、6、1 B 8、2、8、2 C6、2、6、2 D无、2、无、2 5有5个结点的无向完全图K5的边数为_a_ A10 B20 C5 D25 6设完全图K有n个结点(n2)，m条边，当_b_时，K中存在欧拉回路 An为偶数 Bn为奇数 Cm为偶数 Dm为奇数 7一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则T有_c_个顶点 A3 B8 C11 D13 8命题公式（PQ）R的析取范式是_b_ A（ØPØQ）R B Ø（PQ）R C（PQ）R D（PQ）R 9下列等价公式成立的是_b_ AØPÙØQÛPÚQ B P®(ØQ®P) ÛØP®(P®Q) CØPÚ(PÙQ) ÛQ DQ®(PÚQ) ÛØQÙ(PÚQ) 10谓词公式的类型是_c_ A蕴涵式 B永假式 C永真式 D非永真的可满足式二、填空题（每小题3分，本题共15分）6命题公式的真值是 T （或1） 7若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 W£|S| 8给定一个序列集合000，001，01，10，0，若去掉其中的元素 0 ，则该序列集合构成前缀码9已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 10("x)(P(x)Q(x)R(x，y)中的自由变元为R(x，y )中的y6若集合A的元素个数为10，则其幂集的元素个数为 1024 7设A=a，b，c，B=1，2，作f：AB，则不同的函数个数为 8 8若A=1,2，R=<x, y>|xÎA, yÎA, x+y=10，则R的自反闭包为<1,1>,<2,2> 9结点数v与边数e满足 e=v-1 关系的无向连通图就是树6设集合Aa，b，那么集合A的幂集是Æ,a,b,a,b 7如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有 2 个 8设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树9设连通平面图G的结点数为5，边数为6，则面数为 3 10设个体域Da, b，则谓词公式("x)A(x)（$x）B（x）消去量词后的等值式为(A (a)A (b)(B（a）B（b）) 6设集合A=0, 1, 2, 3，B=2, 3, 4, 5，R是A到B的二元关系，则R的有序对集合为<2, 2>，<2, 3>，<3, 2>，<3, 3>7设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2 8设G<V, E>是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树9无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数10设个体域D1,2，则谓词公式消去量词后的等值式为A(1)ÚA(2)6命题公式的真值是 T （或1） 7若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 W£|S| 8给定一个序列集合000，001，01，10，0，若去掉其中的元素 0 ，则该序列集合构成前缀码9已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 10("x)(P(x)Q(x)R(x，y)中的自由变元为R(x，y )中的y6若集合A的元素个数为10，则其幂集的元素个数为 1024 7设A=a，b，c，B=1，2，作f：AB，则不同的函数个数为 8 8若A=1,2，R=<x, y>|xÎA, yÎA, x+y=10，则R的自反闭包为<1,1>,<2,2> 9结点数v与边数e满足 e=v-1 关系的无向连通图就是树10设个体域Da, b, c，则谓词公式("x)A(x)消去量词后的等值式为A (a) A (b)A（c）6若集合A=1，3，5，7，B=2，4，6，8，则AB=空集（或Æ） 7设集合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>,8设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2|E|（或“边数的两倍”） 9无向连通图G的结点数为v，边数为e，则G当v与e满足 e=v-1 关系时是树 10设个体域D1, 2, 3， P(x)为“x小于2”，则谓词公式("x)P(x) 的真值为假（或F，或0） 6设集合A=2, 3, 4，B=1, 2, 3, 4，R是A到B的二元关系， 则R的有序对集合为<2, 2>，<2, 3>，<2, 4>，<3, 3>，<3, 4>，<4, 4>7如果R是非空集合A上的等价关系，a ÎA，bÎA，则可推知R中至少包含<a, a >，< b, b >等元素8设G<V, E>是有4个结点，8条边的无向连通图，则从G中删去 5 条边，可以确定图G的一棵生成树9设G是具有n个结点m条边k个面的连通平面图，则m等于n+k-210设个体域D1, 2，A(x)为“x大于1”，则谓词公式的真值为真（或T，或1）11设集合A=1,2,3，用列举法写出A上的恒等关系IA，全关系EA： IA = _ IA =<1,1>,<2,2>,<3,3>； EA =<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3> 12设集合Aa，b，那么集合A的幂集是Æ,a,b,a,b 13设集合A=1,2,3，B=a,b，从A到B的两个二元关系R=<1,a>,<2,b>,<3,a>，S=<1,a>,<2,a>,<3,a>，则R-S=_ R-S=<2,b> 14设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2 15无向连通图G是欧拉图的充分必要条件是结点度数均为偶数 16设G<V, E>是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树 17设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有_14_条边，G的总度数是_28_，G的分支点数是_7_ 18设P，Q的真值为1，R，S的真值为0，则命题公式的真值为_0_ 19命题公式的合取范式为析取范式为 20设个体域为整数集，公式真值为_1_11设集合A=1,2,3,4，B=3,4,5,6，则： _3,4_，_1,2,3,4,5,6_ 12设集合A有n个元素，那么A的幂集合P(A)的元素个数为 13设集合A=a,b,c,d，B=x,y,z，R=<a,x>,<a,z>,<b,y>,<c,z>,<d,y>则关系矩阵MR 14设集合A=a,b,c,d,e，A上的二元关系R=<a,b>,<c,d>,<b,b>，S=<d,b>,<b,e>,<c,a>，则R·S=<a,e>,<c,b>,<b,e> 15无向图G存在欧拉回路，当且仅当G连通且_所有结点的度数全为偶数 16设连通平面图G的结点数为5，边数为6，则面数为 3 17设正则二叉树有n个分支点，且内部通路长度总和为I，外部通路长度总和为E，则有E=_ I+2n 18设P，Q的真值为0，R，S的真值为1，则命题公式的真值为_1_ 19已知命题公式为G(ØPÚQ)®R，则命题公式G的析取范式是(PÙØQ)ÚR 20谓词命题公式("x)(P(x)Q(x)R(x，y)中的约束变元为_x_三、逻辑公式翻译（每小题4分，本题共12分）11将语句“如果所有人今天都去参加活动，则明天的会议取消”翻译成命题公式设P：所有人今天都去参加活动，Q：明天的会议取消， （1分） P® Q （4分）12将语句“今天没有人来” 翻译成命题公式设 P：今天有人来， （1分）Ø P （4分）13将语句“有人去上课” 翻译成谓词公式设P(x)：x是人，Q(x)：x去上课， （1分）($x)(P(x) ÙQ(x) （4分）11将语句“如果你去了，那么他就不去”翻译成命题公式设P：你去，Q：他去， （1分）P®ØQ （4分）12将语句“小王去旅游，小李也去旅游”翻译成命题公式设P：小王去旅游，Q：小李去旅游， （1分）PÙQ （4分）13将语句“所有人都去工作”翻译成谓词公式设P(x)：x是人，Q(x)：x去工作， （1分）("x)(P(x)®Q(x) （4分）11将语句“他不去学校”翻译成命题公式设P：他去学校， （1分）Ø P （4分）12将语句“他去旅游，仅当他有时间”翻译成命题公式设 P：他去旅游，Q：他有时间， （1分）P ®Q （4分）13将语句“所有的人都学习努力”翻译成命题公式设P(x)：x是人，Q(x)：x学习努力， （1分）（"x）(P(x)®Q(x) （3分）11将语句“尽管他接受了这个任务，但他没有完成好”翻译成命题公式设P：他接受了这个任务，Q：他完成好了这个任务， （2分） PÙØ Q （6分）12将语句“今天没有下雨”翻译成命题公式设P：今天下雨， （2分）Ø P （6分）11将语句“他是学生”翻译成命题公式设P：他是学生， （2分） 则命题公式为： P （6分）12将语句“如果明天不下雨，我们就去郊游”翻译成命题公式设P：明天下雨，Q：我们就去郊游， （2分） 则命题公式为：Ø P® Q （6分）11将语句“今天考试，明天放假”翻译成命题公式设P：今天考试，Q：明天放假 （2分） 则命题公式为：PQ （6分） 12将语句“我去旅游，仅当我有时间”翻译成命题公式 设P：我去旅游，Q：我有时间， （2分）则命题公式为：P®Q （6分） 将语句“如果明天不下雨，我们就去春游”翻译成命题公式 将语句“有人去上课” 翻译成谓词公式设命题P表示“明天下雨”，命题Q表示“我们就去春游”. 则原语句可以表示成命题公式 PQ. （5分） 设P(x)：x是人，Q(x)：x去上课 则原语句可以表示成谓词公式 ($x)(P(x) ÙQ(x) 四、判断说明题（每小题7分，本题共14分）14P（PQ）P为永真式正确 （3分）P（PQ）P是由P（PQ）与P组成的析取式，如果P的值为真，则P（PQ）P为真， （5分）如果P的值为假，则P与PQ为真，即P（PQ）为真，也即P（PQ）P为真，所以P（PQ）P是永真式 （7分）15若偏序集<A，R>的哈斯图如图一所示，则集合A的最大元为a，最小元不存在 正确 （3分）对于集合A的任意元素x，均有<x, a>ÎR（或xRa），所以a是集合A中的最大元（5分）14如果R1和R2是A上的自反关系，则R1R2是自反的正确 （3分）R1和R2是自反的，"x ÎA，<x, x> Î R1，<x, x> ÎR2， 则<x, x> Î R1ÈR2， 所以R1R2是自反的 （7分）v1v2v3v5v4dbacefghn图二15如图二所示的图G存在一条欧拉回路 正确 （3分）因为图G为连通的，且其中每个顶点的度数为偶数 （7分）14设N、R分别为自然数集与实数集，f：NR，f (x)=x+6，则f是单射正确 （3分）设x1，x2为自然数且x1¹x2，则有f(x1)= x1+6¹ x2+6= f(x2)，故f为单射 （7分）15设G是一个有6个结点14条边的连通图，则G为平面图错误 （3分）不满足“设G是一个有v个结点e条边的连通简单平面图，若v3，则e3v-6” 13下面的推理是否正确，试予以说明 (1) （"x）F（x）G（x） 前提引入 (2) F（y）G（y） US（1）错误 （3分）（2）应为F（y）G（x），换名时，约束变元与自由变元不能混淆 （7分）14若偏序集<A，R>的哈斯图如图二所示，则集合A的最大元为a，最小元不存在 错误 （3分）集合A的最大元不存在，a是极大元 （7分）13下面的推理是否正确，试予以说明 (1) （"x）F（x）G（x） 前提引入 (2) F（y）G（y） US（1）错误 （3分）（2）应为F（y）G（x），换名时，约束变元与自由变元不能混淆 （7分）14如图二所示的图G存在一条欧拉回路错误 （3分）因为图G为中包含度数为奇数的结点 （7分）13如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图错误 （3分）当图G不连通时图G不为欧拉图 （7分）14若偏序集<A，R>的哈斯图如图二所示，则集合A的最大元为a，最小元是f 图二错误 （3分）集合A的最大元与最小元不存在，a是极大元，f是极小元， 五计算题（每小题12分，本题共36分）16设集合A=1，2，3，4，R=<x, y>|x, yÎA；|x-y|=1或x-y=0，试（1）写出R的有序对表示； （2）画出R的关系图；（3）说明R满足自反性，不满足传递性（1）R=<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3> （3分）°°°°1234（2）关系图为 （6分）（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在