离散数学题库与答案

试卷二十二试题与答案一、单项选择题：（每小题1分，本大题共15分）1．设A={1，2，3，4，5}，下面（）集合等于A。A、{1，2，3，4，5，6}；B、}25{2xxx是整数且；C、}5{xxx是正整数且；D、}5{xxx是正有理数且。2．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（）是错的。A、A；B、{6，7，8}A；C、{{4，5}}A；D、{1，2，3}A。3．六阶群的子群的阶数可以是（）。A、1，2，5；B、2，4；C、3，6，7；D、2，3。4．设BAS，下列各式中（）是正确的。A、domSB；B、domSA；C、ranSA；D、domSranS=S。5．设集合X，则空关系X不具备的性质是（）。A、自反性；B、反自反性；C、对称性；D、传递性。6．下列函数中，（）是入射函数。A、世界上每个人与其年龄的序偶集；B、、世界上每个人与其性别的序偶集；B、一个作者的专著与其作者的序偶集；D、每个国家与其国旗的序偶集。7．,*G是群，则对*（）。A、满足结合律、交换律；B、有单位元，可结合；C、有单位元、可交换；D、每元有逆元，有零元。8．下面（）哈斯图所描述的偏序关系构成分配格。9．下列（）中的运算符都是可交换的。A、,,；B、,；C、,,；D、,。10．设G是n个结点、m条边和r个面的连通平面图，则m等于（）。A、n+r-2；B、n-r+2；C、n-r-2；D、n+r+2。11．n个结点的无向完全图nK的边数为（）。A、)1(nn；B、2)1(nn；C、)1(nn；D、2)1(nn。12．下列图中（）是根树。A、},,,,,{},,,,{1dcbaaadcbaG；B、},,,,,{},,,,{2dcdbbadcbaG；C、},,,,,{},,,,{3acdabadcbaG；D、},,,,,{},,,,{4ddcabadcbaG。13．设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列（）命题的真值为真。A、RQP；B、SPR；C、RQS；D、)()(SQRP。14．下面（）命题公式是重言式。A、RQP；B、)()(QPRP；C、)()(RQQP；D、))()(())((RPQPRQP。15．设L(x)：x是演员，J(x)：x是老师，A(x,y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为（）。A、)),()((yxAxLx；B、))),()(()((yxAyJyxLx；C、)),()()((yxAyJxLyx；D、)),()()((yxAyJxLyx。二、填空题：（每空1分，本大题共15分）1．设}2,121{ZxxxxM整除，被，}3,121{ZxxxxN整除，被，则NM，NM。2．在一个有n个元素的集合上，可以有种不同的关系，有种不同的函数。3．若关系R是反对称的，当且仅当关系矩阵中，在关系图上。4．设fg是一个复合函数，若g和f都是满射，则fg为，若g和f都是入射，则fg是。5．三阶群有个（不同构），其运算表为。6．设图G=V，E，},,,{4321vvvvV的邻接矩阵0001001111011010A，则1v的入度)(deg1v=，4v的出度)(deg4v=，从2v到4v的长度为2的路有条。7．命题公式)))(((RQQPPA的主合取范式为，其编码表示为。三、判断改正题：判断下列各题是否正确，正确的划“√”，错误的划“×”，并加以改正。（每小题2分，本大题共20分）1．A，B，C为任意集合，若CABA，则B=C。（）2．设R是实数集，R上的关系},,2,{Ryxyxyxf，R是相容关系。（）3．设A，≤是偏序集，AB，则B的极大元Bb且唯一。（）4．谓词公式)()()(yyRxxQxxP的前束范式是))()()((yRzQxPyzx。（）5．在代数系统S,中，若一个元素的逆元是唯一的，其运算必是可结合的。（）6．每一个有限整环一定是域，反之也对。（）7．有割点的连通图可能是哈密尔顿图。（）8．)()())()((xxBxxAxBxAx。（）9．无多重边的图是简单图。（）10．设,,A是布尔代数，则,,A一定为有补分配格。（）四、简答题：（每小题5分，本大题共20分）1．设1R和2R是A上的任意二元关系，如果1R和2R是自反的，21RR是否也是自反的，为什么？如果1R和2R是对称的，21RR是对称的吗？2．如图给出的赋权图表示六个城市fedcba,,,,,及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。3．设S=R-{-1}（R为实数集），abbaba。（1）说明,S是否构成群；（2）在S中解方程732x。4．将公式)()((RPRQP）划为只含有联结词，的等价公式。五、证明题：（共30分）1．设}9,,3,2,1{A，在AA上定义关系RdcbaR,,,:当且仅当cbda，证明R是AA上的等价关系，并求出?]5,2[R2．用CP规则证明)(CBA，CFE)(，)(SABEB。3．将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。5．证明：若T是有n个结点的完全二叉树，则T有21n片叶子。答案一、单项选择题：题号123456789答案CDDBADBDD题号101112131415答案ADCADB二、填空题：1．{6，12}；{2，4，8，10}。2．22n；nn。3．以主对角线为对称的元素不能同时为1；两个不同结点间的定向弧线，不可能成对出现。4．满射；入射。*eab5．1；6．3；1；1。7．)()(RQPRQP；001000MM。三、判断改正题：1．×若CABA，则不一定CB。2．√。3．×B的极大元Bb但可以不唯一。4．√。5．×运算*不一定可结合。6．×有限整环一定是域，但反之不成立。7．×有割点的连通图不可能是汉密尔顿图。8．√。9．×无多重边和自环的图是简单图。10．√。四、简答题：1．解：若21,RR是自反的，则21RR也是自反的。因为21,,RRAa自反，21,,,RaaRaa，从而21,RRaa，即21RR也是自反的。若21,RR是对称的，但21RR不一定是对称的。如：A={a,b,c}，},,,{1abbaR，},,,{2bccbR，则21,RR是对称的，但},{21caRR不是对称的。2．要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得：其最小生成树为：其树权即最小造价为：1+2+3+5+7=18。3．解：（1）1）SabbabaSba易证,，即运算*是封闭的。2）Scba,,,)()()(abcbcacabcbacabbacabbacabbacba而eeabaabebbea,)()()()(abcacabbccbabccbabccbabccbacba)()(cbacba，即*可结合。3）设S关于*有幺元e，则aeaaeSa,。而0,eaeaeaaeea。4）Sa设有逆元1a。则eaaaa11，即011aaaa，aaa11，即S中任意元都有逆元，综上得出，,S构成群。（2）由7111266323232xxxxxx，31x。4．解：原式)()()())((RPRQPRPRQP))()((RPRQP。五、证明题：1．证明：1）,,,,,,,RbabaabbaAAba即R自反。2）,,,,,,bcadcbdaRdcba则即Rbadcadbc,,,,从而，即R对称。3）cedfedfccbdaRfedcRdcba,,,,,,,,,则从而ebcecbcedafa，,,,,Rfeba即R传递。综上得出，R是等价关系。且}9,6,8,5,7,4,6,3,5,2,4,1{}3,,,{}25,,,{]5,2[baAAbababaAAbabaR2．证明：（1）BP(附加前提)（2）)(SABP(3)SAT(1)(2)I(4)AT(3)I(5)CBAP(6)CBT(4)(5)I(7)CT(6)I(8)CFE)(P(9))(FET(7)(8)I(10)FET(9)E(11)ET(10)I(12)EBCP3．解：设Q(x)：x是有理数，R(x)：x是实数，Z(x)：x是整数。命题形式化：))()(()),()((xZxQxxRxQx├))()((xZxRx。证明：（1）))()((xZxQxP(2))()(aZaQES(1)(3))(aQT(2)I(4)))()((xRxQxP(5))()(aRaQUS(4)(6))(aRT(3)(5)I(7))(aZT(2)I(8))()(aZaRT(6)(7)I(9)))()((xZxRxEG(8)结论有效。4．证明：设完全二叉树T有i个分枝点，t片树叶。则n=i+t，对于完全二叉树有i=t–1,n=t-1+t,21nt。