离散数学习题集十五套含答案

1离散数学试题与答案试卷一一、填空20（每小题2分）1设7|,5|XEXBXNXA且且（N自然数集，E正偶数）则B0，1，2，3，4，6。2A，B，C表示三个集合，文图中阴影部分的集合表达式为。3设P，Q的真值为0，R，S的真值为1，则SP的真值1。4公式的主合取范式为RSPR。5若解释I的论域D仅包含一个元素，则XX在I下真值为1。6设A1，2，3，4，A上关系图为则R2,。7设AA，B，C，D，其上偏序关系R的哈斯图为则R,IA。8图的补图为9设AA，B，C，D，A上二元运算如下ABCDABCDABCDBCDACDABDABC那么代数系统的幺元是A，有逆元的元素为A,B,C,D，它们的逆元分别为A,D,C,D。10下图所示的偏序集中，是格的为C。二、选择20（每小题2分）1、下列是真命题的有（CD）AA；B,；C,；D。2、下列集合中相等的有（BC）A4，3；B，3，4；C4，3，3；D3，4。3、设A1，2，3，则A上的二元关系有（C）个。A23；B32；C；D2。4、设R，S是集合A上的关系，则下列说法正确的是（A）A若R，S是自反的，则SR是自反的；B若R，S是反自反的，则是反自反的；ABC2C若R，S是对称的，则SR是对称的；D若R，S是传递的，则是传递的。5、设A1，2，3，4，P（A）（A的幂集）上规定二元系如下|,|TSPTS则P（A）/R（D）AA；BPA；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A6、设A，1，1，3，1，2，3则A上包含关系“”的哈斯图为（C）7、下列函数是双射的为（A）AFIE,FX2X；BFNNN,FN；CFRI,FXX；DFIN,FX|X|。（注I整数集，E偶数集，N自然数集，R实数集）8、图中从V1到V3长度为3的通路有（D）条。A0；B1；C2；D3。9、下图中既不是EULAR图，也不是HAMILTON图的图是（B）10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（A）个4度结点。A1；B2；C3；D4。三、证明261、R是集合X上的一个自反关系，求证R是对称和传递的，当且仅当和在R中有在R中。（8分）1、证“”XCBA,若RC,A,B，由R传递性得R,C,A到的同态映射，证明是的一个子群。其中C3|1XGFGX且8分证CBA,，有,BGFAF，又,1BBF111BGFFAGFAC1是的子群。3、G|V|V，|E|E是每一个面至少由K（K3）条边围成的连通平面图，则2KVE，由此证明彼得森图（PETERSON）图是非平面图。（11分）证设G有R个面，则RFDERII12，即KER2。而RV故KVE2即得2KV。（8分）彼得森图为10,5,E，这样E不成立，所以彼得森图非平面图。（3分）四、逻辑推演16用CP规则证明下题（每小题8分）1、FAEDCBA,证明P（附加前提）BTIPDCTITIETIFEPFTIACP2、XQXQXPP（附加前提）CPUSPQUSCTIXUGXXCP五、计算181、设集合AA，B，C，D上的关系R,用矩阵运算求出R的传递闭包TR。（9分）解01RM，012RRM40123RRM，0134RRM01432RRRTTR,2、如下图所示的赋权图表示某七个城市721,V及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（分）解用库斯克（KRUSKAL）算法求产生的最优树。算法略。结果如图树权CT2314931757即为总造价。试卷二试题与答案一、填空20（每小题2分）1、P你努力，Q你失败。“除非你努力，否则你将失败”的翻译为QP；“虽然你努力了，但还是失败了”的翻译为P。2、论域D1，2，指定谓词P则公式,XY真值为T。P1,1P1,2P2,1P2,2TTFF3、设SA1，A2，A8，BI是S的子集，则由B31所表达的子集是,876540B。4、设A2，3，4，5，6上的二元关系|,是质数XYXR，则RR,（列举法）。R的关系矩阵MR50011。5、设A1，2，3，则A上既不是对称的又不是反对称的关系RR,；A上既是对称的又是反对称的关系RR,。6、设代数系统，其中AA，B，C,则幺元是A；是否有幂等性否；是否有对称性有。7、4阶群必是KLEIN四元群群或循环群群。8、下面偏序格是分配格的是B。9、N个结点的无向完全图KN的边数为12N，欧拉图的充要条件是图中无奇度结点且连通。10、公式RQPP的根树表示为二、选择20（每小题2分）1、在下述公式中是重言式为（BD）AQP；BPQP；C；D。2、命题公式中极小项的个数为（D），成真赋值的个数为（D）。A0；B1；C2；D3。3、设,S，则S有（D）个元素。A3；B6；C7；D8。4、设3,，定义上的等价关系,|,CBDASDCBADCBAR则由R产生的S上一个划分共有（B）个分块。A4；B5；C6；D9。5、设3,21，S上关系R的关系图为则R具有（D）性质。ABCABCABCBBCCCB6A自反性、对称性、传递性；B反自反性、反对称性；C反自反性、反对称性、传递性；D自反性。6、设,为普通加法和乘法，则（A）,S是域。A,3|QBAXSB,2|ZBANXC,12ZND0N。7、下面偏序集（B）能构成格。8、在如下的有向图中，从V1到V4长度为3的道路有（B）条。A1；B2；C3；D4。9、在如下各图中（B）欧拉图。10、设10、R是实数集合，“”为普通乘法，则代数系统是（C）。A群；B独异点；C半群。三、证明461、设R是A上一个二元关系，,|,RBCCAACBAS且有对于某一个试证明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）1、（9分）（1）S自反的，由R自反，,R，SA,（2）S对称的传递对称定义RSABBCCA,（3）S传递的7定义传递SSCARCBRRCEEBDDBACA,由（1）、（2）、（3）得；S是等价关系。2、用逻辑推理证明所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。证明设PXX是个舞蹈者；QXX很有风度；SXX是个学生；A王华上述句子符号化为前提QP、AP结论Q3分ASPXPPUSTITIASTITIXEG3、若BAF是从A到B的函数，定义一个函数ABG2对任意BB有|BXFXBG，证明若F是A到B的满射，则G是从B到A2的单射。（10分）证明,2121A21,满射211,AFAFAFF是函数由于且使,|1221BGBGBGXFX但又为单射任意性知由B,21。4、若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）证明设G中两奇数度结点分别为U和V，若U，V不连通，则G至少有两个连通分支G1、G2，使得U和V分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而U，V一定连通。5、设G是具有N个结点的无向简单图，其边数2NM，则G是HAMILTON图（8分）证明证G中任何两结点之和不小于N。反证法若存在两结点U，V不相邻且1VDU,令,VUV，则GV1是具有N2个结点的简单图，它的边数21,可得32NM，这与G1GV1为N2个结点为简单图的题设矛盾，因而G中任何两个相邻的结点度数和不少于N。所以G为HAMILTON图四、计算1、设是一个群，这里6是模6加法，Z60，1，2，3，4，5，试求出的所有子群及其相应左陪集。解子群有；0的左陪集0，1；2，3；4，50，3的左陪集0，3；1，4；2，50，2，4的左陪集0，2，4；1，3，52、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）试卷三试题与答案8一、填空20（每空2分）1、设F，G是自然数集N上的函数XGXFX2,1,，则X2X1。2、设AA，B，C，A上二元关系R,则S（R）A,C,A,。3、A1，2，3，4，5，6，A上二元关系|,是素数YXT，则用列举法T362,4,1,1；T的关系图为；T具有反对称性、反自反性性质。4、集合,的幂集A2,。5、P，Q真值为0；R，S真值为1。则SRQPSRPWF真值为1。6、WF的主合。7、设P（X）X是素数，EXX是偶数，OXX是奇数NX,YX可以整数Y。则谓词,YNOYF的自然语言是任意X，如果X是素数则存在一个Y，Y是奇数且Y整除X。8、谓词,UYZPZF的前束范式为,UXQUZ。二、选择20（每小题2分）1、下述命题公式中，是重言式的为（C）。A、QP；B、PQPQ；C、；D、P。2、RWF的主析取范式中含极小项的个数为（C）。A、2；B、3；C、5；D、0；E、8。3、给定推理XGFXPYGFUSPESYTIXUG推理过程中错在（C）。A、B、C、D、E、4、设S11，2，8，9，S22，4，6，8，S31，3，5，7，9，S43，4，5，S53，5，在条件31X且下X与（C）集合相等。A、XS2或S5；B、XS4或S5；C、XS1，S2或S4；D、X与S1，S5中任何集合都不等。5、设R和S是P上的关系，P是所有人的集合，,|的父亲是YXPYXR，,|的母亲是YXYX则表示关系（A）。A、的丈夫是；B、,|的孙子或孙女是；C、；D、,|的祖父或祖母是YXP。6、下面函数（B）是单射而非满射。A、12,XXFRF；B、ZLN；C、的最大整数表示不大于FF,；D、。其中R为实数集，Z为整数集，R，Z分别表示正实数与正整数集。7、设S1，2，3，R为S上的关系，其关系图为则R具有（D）的性质。9A、自反、对称、传递；B什么性质也没有；C、反自反、反对称、传递；D、自反、对称、反对称、传递。8、设2,1,S，则有（A）S。A、1,2；B、1,2；C、1；D、2。9、设A1,2,3，则A上有（D）个二元关系。A、23；B、32；C、32；D、23。10、全体小项合取式为（C）。A、可满足式；B、矛盾式；C、永真式；D、A，B，C都有可能。三、用CP规则证明16（每小题8分）1、FE,P（附加前提）TIBAPTIDTIETIFPTICP2、XQXQXPXP本题可证P（附加前提）TEAESQPPUSATIXQEGXXCP四、（14）集合X,，R,|X1Y2X2Y1。1、证明R是X上的等价关系。（10分）2、求出X关于R的商集。（4分）1证明（1）自反性YXYX由于,自反RYX,（2）对称性XX21,时当21,21211YX也即即有对称性故YX2,（3）传递性XYXYX321,时且当RXRYX31,23212即23123YYX即11有传递性故RYX3,由（1）（2）（3）知R是X上的先等价关系。2、X/R10五、（10）设集合AA,B,C,D上关系R,要求1、写出R的关系矩阵和关系图。（4分）2、用矩阵运算求出R的传递闭包。（6分）01RM；012RRM关系图2、0123RR23401RRRM,4635RM01432RRRTTR,。六、（20）1、（10分）设F和G是函数，证明GF也是函数。2、（10分）设函数STS，证明STF有一左逆函数当且仅当F是入射函数。1、（1）|,XGFYDOMGFXYYXF,|FFDOMHGFH令（2）|,XHFX使得若有对21,Y1GFXFY,GF有是函数或由于XHYDOM使得有唯一即也是函数。2、证明TFTTGF,“则对有一左逆若是入射所以是入射故F,。的左逆元是故则且若或只有一个值则对令若此时令使入射由定义如下是入射FGTSTFGSTFCTSSTSTFTTFTFTFS,|,“左逆函数为使必能构造函数入射即若,。试卷四试题与答案11一、填空10（每小题2分）1、若P，Q，为二命题，Q真值为0当且仅当P真值为1，Q的真值为0。2、命题“对于任意给定的正实数，都存在比它大的实数”令FXX为实数，YXL,则命题的逻辑谓词公式为,YLFYXLFX。3、谓词合式公式的前束范式为。4、将量词辖域中出现的约束变元和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。5、设X是谓词合式公式A的一个客体变元，A的论域为D，AX关于Y是自由的，则Y，Y为D的某些元素被称为存在量词消去规则，记为ES。二、选择25（每小题25分）1、下列语句是命题的有（AC）。A、明年中秋节的晚上是晴天；B、0YX；C、0XY当且仅当X和Y都大于0；D、我正在说谎。2、下列各命题中真值为真的命题有（AD）。A、224当且仅当3是奇数；B、224当且仅当3不是奇数；C、224当且仅当3是奇数；D、224当且仅当3不是奇数；3、下列符号串是合式公式的有（CD）A、QP；B、P；C、QP；D、P。4、下列等价式成立的有（AD）。A、；B、R；C、；D、。5、若N21,和B为WFF，且BAN21则（BC）。A、称A为B的前件；B、称B为N21,的有效结论C、当且仅当FN21；D、当且仅当N21。6、A，B为二合式公式，且，则（ABCDE）。A、为重言式；B、；C、；D、A；E、BA为重言式。7、“人总是要死的”谓词公式表示为（C）。（论域为全总个体域）MXX是人；MORTALXX是要死的。A、XMORTAL；B、XMORTALC、；D、8、公式QP的解释I为个体域D2，PXX3,QXX4则A的真值为（A）。A、1；B、0；C、可满足式；D、无法判定。9、下列等价关系正确的是（B）。A、XXXB、X；C、；D、QXPP。10、下列推理步骤错在（C）。XGFPYGFUSFPYESTIGEGA、；B、；C、；D、三、逻辑判断301、用等值演算法和真值表法判断公式QPA的类型。（1）等值演算法TPQP（2）真值表法所以A为重言式。12PQPPQA11111111001001011000100111112、下列问题，若成立请证明，若不成立请举出反例（10分）（1）已知CBA，问A成立吗（2）已知，问成立吗（1）不成立。若取TCBTTC有则但A与B不一定等价，可为任意不等价的公式。（2）成立。证明充要条件即ABABT所以故。3、如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长。问若厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。（10分）解设P厂方拒绝增加工资；Q罢工停止；R罢工超壶过一年；R撤换厂长前提PS,结论QPPPRTIRPTISTEQTI罢工不会停止是有效结论。四、计算101、设命题A1，A2的真值为1，A3，A4真值为0，求命题23的真值。（5分）解1012、利用主析取范式，求公式RQP的类型。（5分）（1）FRQP它无成真赋值，所以为矛盾式。五、谓词逻辑推理15符号化语句“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。解YXHXGXFXM喜欢是杂草是花是人,YHY,YM证明,PAFAESATI,TI,YXYXP,YYGUS,AYGTI,HYTEZHZFUSZAUSTIXFXUG六、证明（10）设论域DA,B,C，求证BAXBXA。13XBAXCBABACCBACBCBAXBXA试卷五试题与答案一、填空15（每空3分）1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有6个5度结点。2、N阶完全图，KN的点数XKNN。3、有向图中从V1到V2长度为2的通路有2条。4、设R，是代数系统，如果R，是交换群R，是半群对分配且对分配均成立则称R，为环。5、设,L是代数系统，则,L满足幂等律，即对LA有AA且。二、选择15（每小题3分）1、下面四组数能构成无向简单图的度数列的有（AB）。A、（2，2，2，2，2）；B、（1，1，2，2，3）；C、（1，1，2，2，2）；D、（0，1，3，3，3）。2、下图中是哈密顿图的为（BD）。3、如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（B）A、真；B、假。4、下列偏序集（C）能构成格。5、设4,13,21S，为普通乘法，则S，是（D）。A、代数系统；B、半群；C、群；D、都不是。三、证明481、（10）在至少有2个人的人群中，至少有2个人，他们有相同的朋友数。证明用N个顶点V1，VN表示N个人，构成顶点集VV1，VN，设,|VUVUE是朋友且，无向图G（V，E）现证G中至少有两个结点度数相同。事实上，（1）若G中孤立点个数大于等于2，结论成立。14（2）若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于N1，由于G中N顶点其度数取值只能是1，2，N1，由鸽巢原理，必然至少有两个结点度数是相同的。2、（8）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。证设G中两个奇数度结点分别为U，V。若U，V不连通则至少有两个连通分支G1、G2，使得U，V分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而U，V必连通。3、（8）证明在6个结点12条边的连通平面简单图中，每个面的面数都是3。证N6,M12欧拉公式NMF2知F2NM26128由图论基本定理知24DEGMF，而DEGIF，所以必有3DEGIF，即每个面用3条边围成。4、（10）证明循环群的同态像必是循环群。证设循环群A，的生成元为A，同态映射为F，同态像为F（A），于是AAMN,都有MNMNFFAF对N1有N2,有22AFF若NK1时有11KKAFF对NK时，KKAFFFFA1这表明，FA中每一个元素均可表示为NF，所以FA,为FA生成的循环群。5、（12）设1,0,B是布尔代数，定义运算为BAB，求证B，是阿贝尔群。（1）交换律BA,有AA（2）结合律C有CBACBACCCBABBA而CBACBACBAC（3）幺B有AA0000幺元是（4）逆AA的逆元是综上所述B，是阿贝尔群。四、计算221、在二叉树中1）求带权为2，3，5，7，8的最优二叉树T。（5分）2）求T对应的二元前缀码。（5分）2、下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。15（1）（5分）由HUFFMAN方法,得最佳二叉树为（2）（5分）最佳前缀码为000，001，01，10，112、（12分）图中奇数点为E、F，DE3,DF3,DE,F28PEGF复制道路EG、GF，得图G，则G是欧拉图。由D开始找一条欧拉回路DEGFGEBACBDCFD。道路长度为358202084030501961210232试卷六试题与答案一、填空15（每小题3分）1、N阶完全图结点V的度数DVN1。2、设N阶图G中有M条边，每个结点的度数不是K的是K1，若G中有NK个K度顶点，NK1个K1度顶点，则NKNK12M。3、算式FEDCBA的二叉树表示为。4、如图给出格L，则E的补元是0。5一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是臂力小者。二、选择15（每小题3分）1、设S0,1,2,3,为小于等于关系，则S，是（D）。A、群；B、环；C、域；D、格。2、设A,B,C，为代数系统，运算如下ABCAABCBBACCCCC则零元为（C）。A、A；B、B；C、C；D、没有。3、如右图相对于完全图K5的补图为（A）。164、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（A）4度结点。A、1；B、2；C、3；D、4。5、设A，是代数系统，其中，为普通加法和乘法，则A（D）时，A，是整环。A、,|ZNX；B、,12|ZNX；C、0且；D、54RBA。三、证明501、设G是（N,M）简单二部图，则2NM。（10分）证设G（V，E）NYXY2121,对完全二部图有42121NNN当21N时，完全二部图,M的边数M有最大值42故对任意简单二部图,N有42。2、设G为具有N个结点的简单图，且21N，则G是连通图。（10分）证反证法若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为N1和N2，显然21122212NNM与假设矛盾。所以G连通。3、记“开”为1，“关”为0，反映电路规律的代数系统0，1，的加法运算和乘法运算。如下0101001000110101证明它是一个环，并且是一个域。（14分）（1）0，1，是环0，1，是交换群乘由“”运算表知其封闭性。由于运算表的对称性知运算可交换。群（00）00（00）0；（00）10（01）1；（01）00（10）1；（01）10（11）0；（11）11（11）0结合律成立。幺幺元为0。逆0，1逆元均为其本身。0，1，是半群乘由“”运算表知封闭群（00）00（00）0；（00）10（01）0；（01）00（10）0；（01）10（11）0；（11）11（11）0。对的分配律,YX0（XY）0000X0Y；1（XY）当XYXY0则10101YXX；当Y（）则1711011YXYX所以,0,Z均有YZXYXZ同理可证所以对是可分配的。由得，0，1，是环。（2）0，1，是域因为0，1，是有限环，故只需证明是整环即可。乘交环由乘法运算表的对称性知，乘法可交换。含幺环乘法的幺元是1无零因子1110因此0，1，是整环，故它是域。4、,L是一代数格，“”为自然偏序，则L，是偏序格。（16分）证（1）“”是偏序关系，自然偏序ABLA,反自反性由代数格幂等关系。反对称性LBA,若B,即B,，则传递性C,则ABAACBC即即结合律即C（2）LYX,在L中存在X,Y的下（上）确界设则,INFYX事实上同理可证若X,Y有另一下界C，则CYXCXCY是X,Y最大下界，即,INFX同理可证上确界情况。四、101设,32321321XXE是布尔代数,1,0上的一个布尔表达式，试写出,32X的析取范式和合取范式（10分）解函数表为1X23,321XE0000001101000111100010111101111118析取范式,321321321321XXXXE合取范式,321321X五、10如下图所示的赋权图表示某七个城市721,V及预先算出它们之间的一些直接通信成路造价（单位万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。解用库斯克（KRUSKAL）算法求产生的最优树。算法为6161545433772271712,9,VEVWVEVW选选选选选选结果如图树权CT2314931757（万元）即为总造价试卷七试题与答案一、填空15（每小题3分）1任何N,M图GV,E,边与顶点数的关系是VVMD2。2当N为奇数时,非平凡无向完全图KN是欧拉图。3已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有5个1度顶点。4N阶完全图KN的点色数XKNN。5一组学生,用两两扳腕子比赛来测定臂力大小,则幺元是臂力小者。二、选择15（每小题3分）1、下面四组数能构成无向图的度数列的有B。A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。2、图的邻接矩阵为C。A、01；B、1；C、01；D、01。3、下列几个图是简单图的有B。A、G1V1,E1,其中V1A,B,C,D,E,E1AB,BE,EB,AE,DE；B、G2V2,E2其中V2V1,E2,；C、GV3,E3,其中V3V1,E3AB,BE,ED,CC；D、GV4,E4,其中V4V1,E4（A,A）,（A,B）,（B,C）,（E,C）,（E,D）。4、下列图中是欧拉图的有B。195、,2SG，其中3,21，为集合对称差运算，则方程3,12,X的解为（A）。A、；B、；C、3,1；D、。三、证明341、证明在至少有2个人的人群中，至少有2个人，他的有相同的朋友数。（8分）证明用N个顶点V1，VN表示N个人，构成顶点集VV1，VN，设,|VUVUE是朋友且，无向图G（V，E）现证G中至少有两个结点度数相同。事实上，（1）若G中孤立点个数大于等于2，结论成立。（2）若G中有一个孤立点，则G中的至少有3个顶点，现不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于N1，由于G中顶点数到值只能是1，2，N1这N1个数，因而取N1个值的N个顶点的度数至少有两个结点度数是相同的。2、若图G中恰有两个奇数顶点，则这两个顶点是连通的。（8分）证设G中两个奇数度结点分别为U，V。若U，V不连通，即它们中无任何通路，则至少有两个连通分支G1、G2，使得U，V分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而U，V必连通。3、证明在6个结点12条边的连通平面简单图中，每个面的面度都是3。（8分）证N6,M12欧拉公式NMF2知F2NM26128由图论基本定理知4DEGMF，而DEGIF，所以必有3DEGIF，即每个面用3条边围成。4、证明循环群的同态像必是循环群。（10分）证设循环群A，的生成元为A，同态映射为F，同态像为，于是AAMN,都有MNMNFAFF对N1有N2,有22AFF若NK1时有11KKAFF对NK时，KKAFFFFA1这表明，FA中每一个元素均可表示为NF，所以是以FA生成元的循环群。四、中国邮递员问题13求带权图G中的最优投递路线。邮局在V1点。解图中有4个奇数结点，5,3,5,321DVDV（2）求31任两结点的最短路573652532457132121,4VPVPVPVPPPDD再找两条道路使得它们没有相同的起点和终点，且长度总和最短,3245713（3）在原图中复制出4,P，设图G，则图G中每个结点度数均为偶数的图G存在欧拉回路157235726542371VVVC，欧拉回路C权长为43。五、根树的应用13在通讯中，八进制数字出现的频率如下030、120、215、310、410、55、65、75求传输它们最佳前缀码（写出求解过程）。解用100乘各频率并由小到大排列得权数2030,2,15,0,1,5,587654321WWW（4）用HUFFMAN算法求最优二叉树（5）前缀码用00000传送5；00001传送6；0001传送7；100传送3；101传送4；001传送2；11传送1；01传送0（频率越高传送的前缀码越短）。六、10设B4E,A,B,AB，运算如下表，则是一个群（称作KLEIN四元群证明（1）乘由运算表可知运算是封闭的。（2）群即要证明ZYXZY，这里有4364个等式需要验证但E是幺元，含E的等式一定成立。ABABBA，如果对含A，B的等式成立，则对含A、B、AB的等式也都成立。剩下只需验证含A、B等式，共有238个等式。即ABAABABABAAABB；ABBABBAABBAEA；AAAEAAAAAAEA；AABEBBAABAABB；BBAEAABBABABA；BBBEBBBBBBEB；BAAABABBAABEB；BABABBABABBABA。（3）幺E为幺元（4）逆E1E；A1A；B1B；AB1AB。所以为群。试卷八试题与答案一、填空15（每小题3分）1、N阶完全图KN的边数为12N。2、右图的邻接矩阵A。3、图的对偶图为。014、完全二叉树中，叶数为NT，则边数M12TN。5、设为代数系统，运算如下则它的幺元为A；零元为C；A、B、C的逆元分别为A、B、没有。二、选择15（每小题3分）EAABBEABCAABCBBACCCCC216、图相对于完全图的补图为（A）。7、对图G则,GK分别为（A）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。8、一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（C）片树叶。A、3；B、4；C、5；D、69、设是代数系统，其中，为普通的加法和乘法，则A（D）时是整环。A、,2|ZNX；B、,|ZNX；C、0X且；D、,54RBA。10、设A1，2，10，则下面定义的运算关于A封闭的有（AC）。A、XYMAXX,Y；B、XY质数P的个数使得YP；C、XYGCDX,Y；GCDX,Y表示X和Y的最大公约数；D、XYLCMX,Y（LCMX,Y表示X和Y的最小公倍数）。二、证明451、设G是（N,M）简单二部图，则42NM。（8分）设G（V，E），NYX2121,则对完全二部图有4221NNN当21N时，完全二部图,M的边数M有最大值42。故对任意简单二部图,MN有42。2、设G为具有N个结点的简单图，且1N则G是连通图。（8分）反证法若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为N1和N2，显然21。12N2NM与假设矛盾。所以G连通。3、设G是阶数不小于11的简单图，则G或中至少有一个是非平图。（14分）（1）当N11时，1K边数5210M条，因而必有G或的边数大于等于28，不妨设G的边数28，设G有K个连通分支，则G中必有回路。（否则G为K棵树构成的森林，每棵树的顶点数为NI，边数MI，则1,KINII,MNIII11,KIIKI1128矛盾）下面用反证法证明G为非平面图。假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3。于是G的每个面至少由G223G条边围成，由点、边、面数的关系12KNGM，得27313131228KM而7矛盾，所以G为非平面图。（2）当N11时，考虑G的具有11个顶点的子图，则G或必为非平面图。如果为非平面图，则为非平面图。如果为非平面图，则为非平面图。4、记“开”为1，“关”为0，反映电路规律的代数系统0，1，的加法运算和乘法运算。如下0101001000110101证明它是一个环，并且是一个域。（15分）1）0，1，是环0，1，是交换群乘由“”运算表知其封闭性。由于运算表的对称性知运算可交换。群（00）00（00）0；（00）10（01）1；（01）00（10）1；（01）10（11）0；（11）11（11）0结合律成立。幺幺元为0。逆0，1逆元均为其本身。所以，是ABEL群。是半群乘由“”运算表知封闭群0000（00）0；（00）10（01）1；（01）00（10）1；（01）10（11）0；（11）11（11）0；对的分配律对,YX0（XY）0000X0Y1（XY）当XYXY0则11010YXYX当（）则011所以,0,ZYX均有YZXYXZ同理可证所以对是可分配的。由得，是环。（2）是域因为是有限环，故只需证明是整环即可。乘交环由乘法运算表的对称性知，乘法可交换。含幺环乘法的幺元是1无零因子1110因此0，1，是整环，故它是域。三、生成树及应用101、（10分）如下图所示的赋权图表示某七个城市23721,V及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。解用库斯克（KRUSKAL）算法求产生的最优树。算法略。结果如图树权CT2314931757即为总造价2、（10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPYNEWYEAR的编码信息。由二叉树知H、A、P、Y、N、E、W、R对应的编码分别为000、001、010、011、100、101、110、111。显然000，001，010，011，100，101，110，111为前缀码。英文短语HAPPYNEWYEAR的编码信息为000001010010011100101001001101001111四、5对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。MAXMIN可结合性可交换性存在幺元存在零元试卷九试题与答案一、填空30（每空3分）1、选择合适的论域和谓词表达集合A“直角坐标系中，单位元（不包括单位圆周）的点集”则A。2、集合A,的幂集PA。3、设A1，2，3，4，A上二元关系R，画出R的关系图。4、设A,B,则BA,，,、。B,；。5、设|A|3，则A上有29个二元关系。6、A1，2，3上关系R,时，R既是对称的又是反对称的。MAXMIN可结合性YYY可交换性YYY存在幺元NNY存在零元NNN247、偏序集RA,的哈斯图，则R,8、设|X|N，|Y|M则（1）从X到Y有MN个不同的函数。（2）当N,M满足NM时，存在双射有N个不同的双射。9、是有理数的真值为假。10、Q我将去上海，R我有时间，公式Q的自然语言为我将去上海当且仅当我有空。11、公式QP的主合取范式是。12、若,21MSS是集合A的一个分划，则它应满足。二、选择20（每小题2分）1、设全集为I，下列相等的集合是（AD）。A、|是偶数或奇数X；B、2|YXIYX；C、1YIY；D、,43,10。2、设SN，Q，R，下列命题正确的是（C）。A、SN2,则；B、SNQ则,；C、R则；D、则。3、设CA,B,A,B，则CS与分别为（B）。A、C和A,B；B、A,B与；C、A,B与A,B；D、C与C4、下列语句不是命题的有（AE）。A、X13；B、离散数学是计算机系的一门必修课；C、鸡有三只脚；D、太阳系以外的星球上有生物；E、你打算考硕士研究生吗5、RQP的合取范式为（BD）。A、；B、RQP；CRQPRD、QP。6、设|A|N，则A上有（C）二元关系。A、2N；B、N2；C、2N；D、NN；E、N2。7、7、设R为集合A上的相容关系，其简化关系图（如图），则IR产生的最大相容类为（BD）；A、,21X；B、,321X；C、,54X；D、,542XIIA的完全覆盖为（C）。A、,54321；B、,5432121XX；C、2；D、,54321XX。8集合A1，2，3，4上的偏序关系图为则它的哈斯图为（A）。9下列关系中能构成函数的是（B）。A、10,|,YXNYX；B、,|,2XYRXY；C、2R；D、3MODI。2510、N是自然数集，定义3MOD,XFNF（即X除以3的余数），则F是（D）。A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。三、简答题151、10分设S1,2,3,4,6,8,12,24，“”为S上整除关系，问（1）偏序集,S的HASS1,，,COVS,HASS图为（2）极小元、最小元是1，极大元、最大元是24。2、（5分）设解释R如下DR是实数集，DR中特定元素A0，DR中特定函数YXF,，特定谓词YXF,，问公式,ZYXFFYXZA的涵义如何真值如何解公式A涵义为对任意的实数X,Y,Z，如果X,，用WARSHALL方法，求R的传递闭包TR。六、证明151、每一有限全序集必是良序集。（7分）2、设FG是复合函数，如果FG满射，则G也是满射。（8分）26试卷十试题与答案一、填空10（每小题2分）1、若P，Q为二命题，真值为1，当且仅当P，Q的真值相同。2、对公式,YXRZXYX中自由变元进行代入的公式为VU。3、GF的前束范式为XGF。4、设X是谓词合式公式A的一个客体变元，A的论域为D，A（X）关于Y的自由的，则YA被称为全称量词消去规则，记为US。5、与非门的逻辑网络为。二、选择30（每小题3分）1、下列各符号串，不是合式公式的有（BC）。A、RQP；B、SRQP；C、；D、。2、下列语句是命题的有（AC）。A、2是素数；B、X56；C、地球外的星球上也有人；D、这朵花多好看呀。3、下列公式是重言式的有（B）。A、；B、；C、P；D、PQ4、下列问题成立的有（CD）。A、若，则A；B、若，则BA；C、若，则；D、若，则。5、命题逻辑演绎的CP规则为（C）。A、在推演过程中可随便使用前提；B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C、如果要演绎出的公式为形式，那么将B作为前提，设法演绎出C；D、设是含公式A的命题公式，A，则可用B替换A中的A。6、命题“有的人喜欢所有的花”的逻辑符号化为（D）。设D全总个体域，F（X）X是花，MXX是人，HX,YX喜欢YA、,YHFYM；B、,YXHFM；C、；D、。7、公式,PZQXP换名（A）。A、XUU；B、,UPZUQXPY；C、,UYY；D、YY。8、给定公式XX，当DA,B时，解释（BC）使该公式真值为0。A、PA0、PB0；B、PA0、PB1；C、PA1、PB0；D、PA1、PB19、下面蕴涵关系成立的是（BD）。A、XQPQP；B、XX；C、；D、,YAY。10、下列推理步骤错在（C）。,XYFPZFUSCZES,CXUG,EGA、；B、；C、；D、。27三、逻辑判断281、（8分）下列命题相容吗ACBA,BAPAPBTICPTETIFTI所以,不相容。2、（10分）用范式方法判断公式RQQ是否等价。10011001MRQPPRQPPRPRQ所以两式等价。3、（10分）下列前提下结论是否有效今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书时，说明今天下雨。设P今天天晴，Q今天下雨，R我不看书，S我看电影符号化为QR,SPPTITIPPTETI结论有效。四、计算121、（5分）给定3个命题P北京比天津人口多；Q2大于1；R15是素数。求复合命题R的真值。解P，Q是真命题，R是假命题。0102、（7分）给定解释ID2，3，L（X,Y）为L2,2L3,31,L2,3L3,20,求谓词合式公式,YX的真值。五、逻辑推理201、（10分）所有有理数是实数，某些有理数是整数，因此某些实数是整数。解设RXX是实数，QXX是有理数，IXX是整数符号化前提RQ，XIQ结论XIRIPCESPUSCTITIITITIXIREG2、（10分）符号化语句“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。28并推证其结论。解FXX是病人，GXX是医生，HXX是骗子，LX,YX相信Y符号化前提,YLGYF,YXLHF结论H,P,AGAESATI,YLTI,YXYXP,US,ALYTI,TEZZGUSZHZAUSHTIXXUG卷十一试题与答案一、填空20（每小题2分）1、能够断真假的阵述句称为命题。2、命题PQ的真值为0，当且仅当P的真值为1，Q的真值为0。3、一个命题含有4个原子命题，则对其所有可能赋值有2416种。4、所有小项的析取式为永真式。5、令P（X）X是质数，E（X）X是偶数，Q（X）X是奇数，D（X，Y）X除尽Y则,YDY的汉语翻译为任意两数X、Y,如果X是偶数且能除尽Y，则Y一定是偶数6、设SA，B,C则S6的集合表示为S110A,B。7、P（P）。8、BA。9、设R为集合A上的关系，则T（R）。10、若R是集合A上的偏序关系，则R满足自反性、反对称性、传递性。二、选择20（每小题2分）1、下列命题正确的有（AD）。A、若FG,是满射，则FG是满射；B、若