《离散数学试卷与答案22_中学教育-中考.pdf》由会员分享，可在线阅读，更多相关《离散数学试卷与答案22_中学教育-中考.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学试卷（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不具备的性质是（）
2、。A、自反性；B、反自反性；C、对称性；D、传递性。6下列函数中，（）是入射函数。A、世界上每个人与其年龄的序偶集；B、世界上每个人与其性别的序偶集；B、一个作者的专著与其作者的序偶集；D、每个国家与其国旗的序偶集。7,*G是群，则对*（）。A、满足结合律、交换律；B、有单位元，可结合；C、有单位元、可交换；D、每元有逆元，有零元。8下面（）哈斯图所描述的偏序关系构成分配格。9下列（）中的运算符都是可交换的。A、,；B、,；C、,；D、,。离散数学试卷（22）143 10设 G 是 n 个结点、m 条边和 r 个面的连通平面图，则 m 等于（）。A、n+r-2；B、n-r+2；C、n-r-2；
3、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 是
4、老师，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 是反对称的，当且仅当关系矩阵中 ，在是错的六阶群的子群的阶数可以是设下列各式中是正确的设集合则空关系不具备的性质是自反性反自反性对称性传递性下列函数中是入射函
5、数世界上每个人与其年龄的序偶集世界上每个人与其性别的序偶集一个作者的专著与其作者元下面哈斯图所描述的偏序关系构成分配格下列中的运算符都是可交换的离散数学试卷设是个结点条边和个面的连通平面图则等于个结点的无向完全图的边数为下列图中是根树设雪是黑的太阳从东方升起下列命题的真值为真下面命被整除则在一个有个元素的集合上可以有种不同的关系有种不同的函数若关系是反对称的当且仅当关系矩阵中在离散数学试卷关系图上设是一个复合函数若和都是满射则为若和都是入射则是三阶群有个不同构其运算表为设图的邻接离散数学试卷（22）144 关系图上 。4 设fg 是一个复合函数，若g和f都是满射，则fg 为 ，若g和f都是入射
6、，则fg 是 。5三阶群有 个（不同构），其运算表为 。6设图 G=，,4321vvvvV 的邻接矩阵0001001111011010A，则1v的入度 )(de g1v=，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
7、谓词公式)()()(yyRxxQxxP的前束范式是)()()(yRzQxPyzx。（）5在代数系统 中，若一个元素的逆元是唯一的，其运算 必是可结合的。（）6每一个有限整环一定是域，反之也对。（）7 有割点的连通图可能是哈密尔顿图。（）8)()()()(xxBxxAxBxAx。（）9无多重边的图是简单图。（）10设,A是布尔代数，则,A一定为有补分配格。（）四、简答题：（每小题 5 分，本大题共 20 分）是错的六阶群的子群的阶数可以是设下列各式中是正确的设集合则空关系不具备的性质是自反性反自反性对称性传递性下列函数中是入射函数世界上每个人与其年龄的序偶集世界上每个人与其性别的序偶集一个作者的
8、专著与其作者元下面哈斯图所描述的偏序关系构成分配格下列中的运算符都是可交换的离散数学试卷设是个结点条边和个面的连通平面图则等于个结点的无向完全图的边数为下列图中是根树设雪是黑的太阳从东方升起下列命题的真值为真下面命被整除则在一个有个元素的集合上可以有种不同的关系有种不同的函数若关系是反对称的当且仅当关系矩阵中在离散数学试卷关系图上设是一个复合函数若和都是满射则为若和都是入射则是三阶群有个不同构其运算表为设图的邻接离散数学试卷（22）145 1设1R和2R是 A 上的任意二元关系，如果1R和2R是自反的，21RR 是否也是自反的，为什么？如果1R和2R是对称的，21RR 是对称的吗？2如图给出的
9、赋权图表示六个城市fedcba,及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。3设 S=R-1（R 为实数集），abbaba。（1）说明,S是否构成群；（2）在S中解方程732 x。4将公式)()(RPRQP）划为只含有联结词，的等价公式。五、证明题：（共 30 分）1设 9,3,2,1A，在AA上定义关系RdcbaR ,:当且仅 当cbda，证明R是AA上的等价关系，并求出?5,2R 2用 CP 规则证明)(CBA，CFE)(，)(SABEB。3将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。因此，某些
10、实数是整数。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 是错的六阶群的子群的阶数可以是设下列各式中是正确的设集合则空关系不具备的性质是自反性反自反性对称性传递性下列函数中是入射函数世界上每个人与其年龄的序偶集世界上每个人与其性别的序偶集一个作者的专著与其作者元下面哈斯图所描述的偏序关系构成分配格下列中的运算符都是可交换的离散数学试卷设是个结点条边和个面的连通平面图则等于个结点的无向完全图的边数为下列
11、图中是根树设雪是黑的太阳从东方升起下列命题的真值为真下面命被整除则在一个有个元素的集合上可以有种不同的关系有种不同的函数若关系是反对称的当且仅当关系矩阵中在离散数学试卷关系图上设是一个复合函数若和都是满射则为若和都是入射则是三阶群有个不同构其运算表为设图的邻接离散数学试卷（22）146 二、填空题：16，12；2，4，8，10。222n；nn。3以主对角线为对称的元素不能同时为 1；两个不同结点间的定向弧线，不可能成对出现。4满射；入射。51；63；1；1。7)()(RQPRQP；001000MM。三、判断改正题：1 若CABA，则不一定CB。2。3 B 的极大元Bb但可以不唯一。4 。5 运
12、算*不一定可结合。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要设计一个方案使各城市间能够通讯且总造价最小，即要求该图连通、无回路、边权之和最小的子图即最小生成树，由避圈法或破圈法可得：其最小生成树为：其树权即最小造
13、价为：1+2+3+5+7=18。*e a b e e a b a a b e b b e a 是错的六阶群的子群的阶数可以是设下列各式中是正确的设集合则空关系不具备的性质是自反性反自反性对称性传递性下列函数中是入射函数世界上每个人与其年龄的序偶集世界上每个人与其性别的序偶集一个作者的专著与其作者元下面哈斯图所描述的偏序关系构成分配格下列中的运算符都是可交换的离散数学试卷设是个结点条边和个面的连通平面图则等于个结点的无向完全图的边数为下列图中是根树设雪是黑的太阳从东方升起下列命题的真值为真下面命被整除则在一个有个元素的集合上可以有种不同的关系有种不同的函数若关系是反对称的当且仅当关系矩阵中在离散
14、数学试卷关系图上设是一个复合函数若和都是满射则为若和都是入射则是三阶群有个不同构其运算表为设图的邻接离散数学试卷（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）
15、由7111266323232xxxxxx，31x。4解：原式)()()()(RPRQPRPRQP )()(RPRQP。五、证明题：1证明：1）,RbabaabbaAAba即 R 自反。2）,bcadcbdaRdcba则 即Rbadcadbc,从而，即 R 对称。3）cedfedfccbdaRfedcRdcba,则 是错的六阶群的子群的阶数可以是设下列各式中是正确的设集合则空关系不具备的性质是自反性反自反性对称性传递性下列函数中是入射函数世界上每个人与其年龄的序偶集世界上每个人与其性别的序偶集一个作者的专著与其作者元下面哈斯图所描述的偏序关系构成分配格下列中的运算符都是可交换的离散数学试卷设是个
16、结点条边和个面的连通平面图则等于个结点的无向完全图的边数为下列图中是根树设雪是黑的太阳从东方升起下列命题的真值为真下面命被整除则在一个有个元素的集合上可以有种不同的关系有种不同的函数若关系是反对称的当且仅当关系矩阵中在离散数学试卷关系图上设是一个复合函数若和都是满射则为若和都是入射则是三阶群有个不同构其运算表为设图的邻接离散数学试卷（22）148 从而 ebcecbcedafa，,Rfeba即 R 传递。综上得出，R 是等价关系。且9,6,8,5,7,4,6,3,5,2,4,1 3,25,5,2baAAbababaAAbabaR 2证明：（1）B P(附加前提)（2）)(SAB P (3)SA
17、 T(1)(2)I (4)A T(3)I (5)CBA P (6)CB T(4)(5)I (7)C T(6)I (8)CFE)(P (9)(FE T(7)(8)I (10)FE T(9)E (11)E T(10)I (12)EB CP 3解：设 Q(x)：x 是有理数，R(x)：x 是实数，Z(x)：x 是整数。命题形式化：)()(),()(xZxQxxRxQx)()(xZxRx。证明：（1）)()(xZxQx P (2)()(aZaQ ES(1)(3)(aQ T(2)I (4)()(xRxQx P (5)()(aRaQ US(4)(6)(aR T(3)(5)I 是错的六阶群的子群的阶数可以是
18、设下列各式中是正确的设集合则空关系不具备的性质是自反性反自反性对称性传递性下列函数中是入射函数世界上每个人与其年龄的序偶集世界上每个人与其性别的序偶集一个作者的专著与其作者元下面哈斯图所描述的偏序关系构成分配格下列中的运算符都是可交换的离散数学试卷设是个结点条边和个面的连通平面图则等于个结点的无向完全图的边数为下列图中是根树设雪是黑的太阳从东方升起下列命题的真值为真下面命被整除则在一个有个元素的集合上可以有种不同的关系有种不同的函数若关系是反对称的当且仅当关系矩阵中在离散数学试卷关系图上设是一个复合函数若和都是满射则为若和都是入射则是三阶群有个不同构其运算表为设图的邻接离散数学试卷（22）14
19、9 (7)(aZ T(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 ,21nt。是错的六阶群的子群的阶数可以是设下列各式中是正确的设集合则空关系不具备的性质是自反性反自反性对称性传递性下列函数中是入射函数世界上每个人与其年龄的序偶集世界上每个人与其性别的序偶集一个作者的专著与其作者元下面哈斯图所描述的偏序关系构成分配格下列中的运算符都是可交换的离散数学试卷设是个结点条边和个面的连通平面图则等于个结点的无向完全图的边数为下列图中是根树设雪是黑的太阳从东方升起下列命题的真值为真下面命被整除则在一个有个元素的集合上可以有种不同的关系有种不同的函数若关系是反对称的当且仅当关系矩阵中在离散数学试卷关系图上设是一个复合函数若和都是满射则为若和都是入射则是三阶群有个不同构其运算表为设图的邻接