2022年2022年离散数学试卷及答案 18.pdf
离散数学试卷（22）142 一、单项选择题：（每小题 1 分，本大题共 15 分）1设 A=1，2，3，4，5，下面（）集合等于A。A、1，2，3，4，5，6；B、252xxx是整数且；C、5xxx是正整数且；D、5xxx是正有理数且。2设 A=1，2，3，4，5，6，7，8，下列各式中（）是错的。A、A；B、6，7，8A；C、4，5A；D、1，2，3A。3六阶群的子群的阶数可以是（）。A、1，2，5；B、2，4；C、3，6，7；D、2，3。4设BAS，下列各式中（）是正确的。A、domSB；B、domSA；C、ranSA；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、,。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8 页 -离散数学试卷（22）143 10设 G 是 n 个结点、m 条边和 r 个面的连通平面图，则m 等于（）。A、n+r-2；B、n-r+2；C、n-r-2；D、n+r+2。11n 个结点的无向完全图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,121ZxxxxM整除，被，3,121ZxxxxN整除，被，则NM，NM。2在一个有n 个元素的集合上，可以有种不同的关系，有种不同的函数。3若关系R 是反对称的，当且仅当关系矩阵中，在名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -离散数学试卷（22）144 关系图上。4设fg是一个复合函数，若g和f都是满射，则fg为，若g和f都是入射，则fg是。5三阶群有个（不同构），其运算表为。6设图 G=，,4321vvvvV的邻接矩阵0001001111011010A，则1v的入度)(deg1v=，4v的出度)(deg4v=，从2v到4v的长度为 2的路有条。7命题公式)(RQQPPA的主合取范式为，其编码表示为。三、判断改正题：判断下列各题是否正确，正确的划“”，错误的划“”，并加以改正。（每小题2 分，本大题共20 分）1A，B，C 为任意集合，若CABA，则 B=C。（）2设 R 是实数集，R 上的关系,2,Ryxyxyxf，R 是相容关系。（）3设是偏序集，AB，则 B 的极大元Bb且唯一。（）4谓词公式)()()(yyRxxQxxP的前束范式是)()()(yRzQxPyzx。（）5在代数系统 中，若一个元素的逆元是唯一的，其运算必是可结合的。（）6每一个有限整环一定是域，反之也对。（）7有割点的连通图可能是哈密尔顿图。（）8)()()()(xxBxxAxBxAx。（）9无多重边的图是简单图。（）10设,A是布尔代数，则,A一定为有补分配格。（）四、简答题：（每小题 5 分，本大题共 20 分）名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -离散数学试卷（22）145 1设1R和2R是 A 上的任意二元关系，如果1R和2R是自反的，21RR是否也是自反的，为什么？如果1R和2R是对称的，21RR是对称的吗？2如图给出的赋权图表示六个城市fedcba,及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。3设 S=R-1（R 为实数集），abbaba。（1）说明,S是否构成群；（2）在S中解方程732x。4将公式)()(RPRQP）划为只含有联结词，的等价公式。五、证明题：（共 30 分）1 设9,3,2,1A，在AA上 定 义 关 系RdcbaR,:当 且 仅 当cbda，证明R是AA上的等价关系，并求出?5,2R2用 CP 规则证明)(CBA，CFE)(，)(SABEB。3将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。5证明：若T 是有 n 个结点的完全二叉树，则T 有21n片叶子。一、单项选择题：题号1 2 3 4 5 6 7 8 9 答案C D D B A D B D D 题号10 11 12 13 14 15 答案A D C A D B 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -离散数学试卷（22）146 二、填空题：16，12；2，4，8，10。222n；nn。3以主对角线为对称的元素不能同时为1；两个不同结点间的定向弧线，不可能成对出现。4满射；入射。51；63；1；1。7)()(RQPRQP；001000MM。三、判断改正题：1若CABA，则不一定CB。2。3B 的极大元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，,1abbaR，,2bccbR，则21,RR是对称的，但,21caRR不是对称的。2要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得：其最小生成树为：其树权即最小造价为：1+2+3+5+7=18。*e a b e e a b a a b e b b e a 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -离散数学试卷（22）147 3解：（1）1）SabbabaSba易证,，即运算*是封闭的。2）Scba,)()()(abcbcacabcbacabbacabbacabbacba而,)()()()(abcacabbccbabccbabccbabccbacba)()(cbacba，即*可结合。3）设 S 关于*有幺元 e，则aeaaeSa,。而0,eaeaeaaeea。4）Sa设有逆元1a。则eaaaa11，即011aaaa，aaa11，即S 中任意元都有逆元，综上得出，,S构成群。（2）由7111266323232xxxxxx，31x。4解：原式)()()()(RPRQPRPRQP)()(RPRQP。五、证明题：1证明：1）,RbabaabbaAAba即 R 自反。2）,bcadcbdaRdcba则即Rbadcadbc,从而，即 R 对称。3）cedfedfccbdaRfedcRdcba,则名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -离散数学试卷（22）148 从而ebcecbcedafa，,Rfeba即 R 传递。综上得出，R 是等价关系。且9,6,8,5,7,4,6,3,5,2,4,13,25,5,2baAAbababaAAbabaR2证明：（1）B P(附加前提)（2）)(SABP(3)SAT(1)(2)I(4)A T(3)I(5)CBAP(6)CBT(4)(5)I(7)C T(6)I(8)CFE)(P(9)(FET(7)(8)I(10)FET(9)E(11)E T(10)I(12)EBCP 3解：设Q(x)：x 是有理数，R(x)：x 是实数，Z(x)：x 是整数。命题形式化：)()(),()(xZxQxxRxQx)()(xZxRx。证明：（1）)()(xZxQxP(2)()(aZaQES(1)(3)(aQT(2)I(4)()(xRxQxP(5)()(aRaQUS(4)(6)(aRT(3)(5)I 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -离散数学试卷（22）149(7)(aZT(2)I(8)()(aZaRT(6)(7)I(9)()(xZxRxEG(8)结论有效。4证明：设完全二叉树T 有 i 个分枝点，t 片树叶。则n=i+t，对于完全二叉树有i=t 1,n=t-1+t,21nt。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -
