离散数学试卷及答案(24)

离散数学试卷(24)158一、填空题：（每空1分，本大题共15分）1．设}4,}3{,,2{aA，}1,4,3,}{{aB，请在下列每对集合中填入适当的符号：,。（1）}{aB,(2)}}3{,4,{aA。2．设}1,0{A，N为自然数集，是偶数。，是奇数，，xxxf10)(若AAf：，则f是射的，若ANf：，则f是射的。3．设图G=V，E中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，则G中有条边，根据。4．两个重言式的析取是，一个重言式和一个矛盾式的合取是。5．设个体域为自然数集，命题“不存在最大自然数”符号化为。6．设S为非空有限集，代数系统,2S中幺元为，零元为。7．设P、Q为两个命题，其De-Morden律可表示为。8．当8G时，群,G只能有阶非平凡子群，不能有阶子群，平凡子群为。二、单项选择题：（每小题1分，本大题共15分）1．设}16{2xxxA是整数且，下面哪个命题为假（）。A、A}4,2,1,0{；B、A}1,2,3{；C、A；D、Axxx}4{是整数且。2．设}}{,{,BA，则B－A是（）。A、}}{{；B、}{；C、}}{,{；D、。3．下图描述的偏序集中，子集},,{feb的上界为（）。A、cb,；B、ba,；C、b；D、cba,,。离散数学试卷(24)1594．设f和g都是X上的双射函数，则1)(gf为（）。A、11gf；B、1)(fg；C、11fg；D、1fg。5．下面集合（）关于减法运算是封闭的。A、N；B、}2{Ixx；C、}12{Ixx；D、}{是质数xx。6．具有如下定义的代数系统,G，（）不构成群。A、}10,1{G，*是模11乘；B、}9,5,4,3,1{G，*是模11乘；C、QG（有理数集），*是普通加法；D、QG（有理数集），*是普通乘法。7．设},32{InmGnm，*为普通乘法。则代数系统,G的幺元为（）。A、不存在；B、0032e；C、32e；D、1132e。8．下面集合（）关于整除关系构成格。A、{2，3，6，12，24，36}；B、{1，2，3，4，6，8，12}；C、{1，2，3，5，6，15，30}；D、{3，6，9，12}。9．设},,,,,{fedcbaV，},,,,,,,,,,,{efeddaaccbbaE，则有向图EVG,是（）。A、强连通的；B、单侧连通的；C、弱连通的；D、不连通的。10．下面那一个图可一笔画出（）。11．在任何图中必定有偶数个（）。A、度数为偶数的结点；B、入度为奇数的结点；C、度数为奇数的结点；D、出度为奇数的结点。12．含有3个命题变元的具有不同真值的命题公式的个数为（）。离散数学试卷(24)160A、32；B、23；C、322；D、232。13．下列集合中哪个是最小联结词集（）。A、},{；B、},{；C、},{；D、},,{。14．下面哪个命题公式是重言式（）。A、)()(RQQP；B、PQP)(；C、)()(QPQP；D、PQP)(。15．在谓词演算中，下列各式哪个是正确的（）。A、),(),(yxxAyyxyAx；B、),(),(yxxAyyxyAx；C、),(),(yxxAyyxyAx；D、)()(xxAaA。三、判断改正题：（每小题2分，本大题共20分）1．设}2,1{A，}{aB，则BABA222。（其中A2为（A））()2．设}1,0{A，}2,1{B，则}2,0,1,1,0,1,2,1,0,1,1,0{2BA。（）3．集合A上的恒等关系是一个双射函数。（）4．设Q为有理数集，Q上运算*定义为),max(baba，则，Q是半群。（）5．阶数为偶数的有限群中，周期为2的元素的个数一定为偶数。（）6．在完全二元树中，若有t片叶子，则边的总数12te。（）7．能一笔画出的图不一定是欧拉图。（）8．设P，Q是两个命题，当且仅当P，Q的真值均为T时，QP的值为T。（）9．命题公式QQPP))((是重言式。（）10．设，是研究生：xxP)(，曾读过大学：xxQ)(命题“所有的研究生都读过大学”符号化为：))()((xQxPx。（）四、简答题：（25分）1．设},,{cbaA，A上的关系},,,,,,,{bccbbaaa，求出离散数学试卷(24)161)()(,)(tsr和。2．集合}36,24,12,6,3,2{A上的偏序关系为整除关系。设}12,6{B，}6,3,2{C，试画出的哈斯图，并求A，B，C的最大元素、极大元素、下界、上确界。3．图给出的赋权图表示五个城市54321vvvvv，，，，及对应两城镇间公路的长度。试给出一个最优化的设计方案使得各城市间能够有公路连通。4．已知}654321{，，，，，G，7为模7乘法。试说明7，G是否构成群？是否为循环群？若是，生成元是什么？5．给定命题公式)())((WSRQP，试给出相应的二元树。五、证明题：（25分）1．如果集合A上的关系R和S是反自反的、对称的和传递的，证明：SR是A上的等价关系。2．用推理规则证明)()(aGaP是))()((,)(,))()((,)))()(()((xGxSxaSaRaQxRxQxPx的有效结论。3．若有n个人，每个人都恰有三个朋友，则n必为偶数。4．设G是（11，m）图，证明G或其补图G是非平面图。离散数学试卷(24)162一、填空题1．（1），（2）。2．双射，满射。3．14，EvVvii2)deg(。4．重言式，矛盾式。5．)(xyyx，6．，S。7．QPQPQPQP)()(，；PQPPPQPP)(,)(。8．2，4；3，5，6，7；,,},{Ge。二、单项选择题题号123456789101112131415答案ACBCBDBCCACCABA三、判断改正题1．×BABA222。2．×}211201101111210110200100{2，，，，，，，，，，，，，，，，，，，，，，，BA3．√。4．√。5．×阶数为偶数的有限群中周期为2的元素个数一定为奇数。6．×完全二叉树中，边数)1(2te。7．√。8．×当且仅当P，Q的真值相同时，QP的真值为T。9．√。10．×))()((xQxPx。四、简答案题1．解},,,,,,,,,,,{)(ccbbbccbbaaar，},,,,,,,,,{)(abbccbbaaas，},,,,,,,,,{2ccbbcabaaa，},,,,,,,,,,,{23bccbbacabaaa，离散数学试卷(24)163},,,,,,,,,,,,,{)(2bccbccbbcabaaat。2．解：的哈斯图为集合最大元极大元下界上确界A无24，36无无B12126，2，312C66无63．解此问题的最优设计方案即要求该图的最小生成树，由破圈法或避圈法得最小生成树为：其权数为1+1+3+4=9。4．解：7，G既构成群，又构成循环群，其生成元为3，5。因为：7的运算表为：71234561123456224613533625144415263553164266543211）由运算表知，7封闭；2）7可结合（可自证明）3）1为幺元；4）111，421，531，241，351，661，离散数学试卷(24)164综上所述，7，G构成群。由331，232，633，434，535，136。所以，3为其生成元，3的逆元5也为其生成元。故7，G为循环群。5．解：命题公式对应的二元树见右图。五、证明题1．证明：（1）,,,,,,SaaRaaSRAa自反，SRSRaa,,自反。（2）Aba,，若SRba,，则,,,,SbaRba由R，S对称，所以，,,,,SabRabSRab,，所以SR对称。（3）Acba,,，若,,,,SRcbSRba则,,,,SbaRba,,,,ScbRcb由R，S传递性知，,,,,ScaRca从而,,SRca所以，SR传递。综上所述，SR是A上的等价关系。2．证明：（1）))()(()(xPxQxxPP（2）))()(()(aPaQaPUS(1)(3)))()((aRaQP(4))(aPT(2)(3)I(5)))()((xGxSxP(6))()(aGaSUS(5)(7))()(aGaST(6)E,I离散数学试卷(24)165(8))(aSP(9))(aGT(7)(8)I(10))()(aGaPT(4)(9)I所以，结论有效。3．证明：将每个人用结点表示，当两个人是朋友时，则对应两结点连一条边，则得一无向图EVG,。因为每个人恰有三个朋友，所以，)(,3)deg(Vuu，由任意图奇数度结点一定是偶数个，可知，此图结点数一定是偶数。4．证明：因为G为（11，m）图，）图，为（mG11，且55101121mm。设EVG,，任Vv，则v在G中度数与v在G度数之和定为101n，若有某点v在G中4)deg(v，则在G中6)deg(v，由定理，G为非平面图。易证G、G存在汉密尔顿路，所以，连通。若5)deg(v，则由定理，假设G、G都为简单连通平面图，则276113m，276113m，于是54mm与55mm矛盾。所以GG、至少有一个非平面图。