离散数学试卷及答案

一、填空题：）1设，请在下列每对集合中填入适当的符号：。 （1） , (2) 。2设，N为自然数集， 若，则是 射的，若，则是 射的。3设图G = 中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，则G中有 条边，根据 。4两个重言式的析取是 ，一个重言式和一个矛盾式的合取是 。5设个体域为自然数集，命题“不存在最大自然数”符号化为 。6设S为非空有限集，代数系统中幺元为 ，零元为 。7设P、Q为两个命题，其De-Morden律可表示为 。8当时，群只能有 阶非平凡子群，不能有 阶子群，平凡子群为 。二、单项选择题：（每小题1分，本大题共15分）1设，下面哪个命题为假（ ）。 A、 ； B、 ；C、 ； D、。2设，则BA是（ ）。A、 ； B、 ； C、 ； D、。3下图描述的偏序集中，子集的上界为 （ ）。A、 ； B、 ； C、 ； D、。4设和都是X上的双射函数，则为（ ）。A、 ； B、 ； C、 ； D、。5下面集合（ ）关于减法运算是封闭的。A、N ； B、 ； C、 ； D、。6具有如下定义的代数系统，（ ）不构成群。A、，*是模11乘 ； B、，*是模11乘 ；C、（有理数集），*是普通加法 ； D、（有理数集），*是普通乘法。7设，*为普通乘法。则代数系统的幺元为（ ）。A、不存在 ； B、 ； C、 ； D、。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设，则有向图是（ ）。A、强连通的 ； B、单侧连通的 ； C、弱连通的 ； D、不连通的。10下面那一个图可一笔画出（ ）。11在任何图中必定有偶数个（ ）。A、度数为偶数的结点 ； B、入度为奇数的结点 ；C、度数为奇数的结点 ； D、出度为奇数的结点 。12含有3个命题变元的具有不同真值的命题公式的个数为（ ）。A、 ； B、 ； C、 ； D、 。13下列集合中哪个是最小联结词集（ ）。A、 ； B、 ； C、 ； D、 。14下面哪个命题公式是重言式（ ）。A、 ； B、 ；C、 ； D、 。15在谓词演算中，下列各式哪个是正确的（ ）。A、 ； B、 ；C、 ； D、 。三、判断改正题：（每小题2分，本大题共20分）1设，则 。（其中为P（A） ( )2设，则 。 （ ）3集合A上的恒等关系是一个双射函数。 （ ）4设Q为有理数集，Q上运算 * 定义为，则是半群。（ ）5阶数为偶数的有限群中，周期为2的元素的个数一定为偶数。 （ ）6在完全二元树中，若有片叶子，则边的总数 。 （ ）7能一笔画出的图不一定是欧拉图。 （ ）8设P，Q是两个命题，当且仅当P，Q的真值均为T时，的值为T。（ ）9命题公式是重言式。 （ ）10设 命题“所有的研究生都读过大学”符号化为：。 （ ）四、简答题：（25分）1设，A上的关系 ，求出 。2集合上的偏序关系为整除关系。设，试画出的哈斯图，并求A，B，C的最大元素、极大元素、下界、上确界。3图给出的赋权图表示五个城市及对应两城镇间公路的长度。试给出一个最优化的设计方案使得各城市间能够有公路连通。4已知，为模7乘法。试说明是否构成群？是否为循环群？若是，生成元是什么？5给定命题公式，试给出相应的二元树。五、证明题：（25分）1如果集合A上的关系R和S是反自反的、对称的和传递的，证明：是A上的等价关系。2用推理规则证明是 的有效结论。3若有n个人，每个人都恰有三个朋友，则n必为偶数。4设G是（11，m）图，证明G或其补图是非平面图。一、填空题1（1） ， （2）。 2双射 ， 满射。 314 ， 。4重言式 ，矛盾式 。 5 ， 6 ，S 。 7； 。82，4； 3，5，6，7；。二、单项选择题题号123456789101112131415答案ACBCBDBCCACCABA三、判断改正题1 。2 3 。4 。 5 阶数为偶数的有限群中周期为2 的元素个数一定为奇数。6 完全二叉树中，边数。 7 。 8 当且仅当P，Q的真值相同时，的真值为T。 9 。 10 。四、简答案题1解， ， ，。2解：的哈斯图为集合最大元极大元下界上确界A无24，36无无B12126，2，312C66无63解此问题的最优设计方案即要求该图的最小生成树， 由破圈法或避圈法得最小生成树为： 其权数为1+1+3+4 = 9 。4解：既构成群，又构成循环群，其生成元为3，5。因为：的运算表为： 1234561123456224613533625144415263553164266543211）由运算表知，封闭；2）可结合（可自证明）3）1为幺元；4），综上所述，构成群。 由，。所以，3为其生成元，3的逆元5也为其生成元。故为循环群。5解：命题公式对应的二元树见右图。五、证明题1证明：（1） 自反。 （2），若，则由R ，S对称， 所以， ，所以 对称。 （3），若则由R ，S传递性知，从而 所以，传递。综上所述，是A上的等价关系。2证明：（1） P （2） US(1) (3) P (4) T(2)(3)I (5) P (6) US(5) (7) T(6)E,I (8) P (9) T(7)(8)I (10) T(4)(9)I所以，结论有效。3证明：将每个人用结点表示，当两个人是朋友时，则对应两结点连一条边，则得一无向图 。因为每个人恰有三个朋友，所以，由任意图奇数度结点一定是偶数个，可知，此图结点数一定是偶数。4证明：因为G为（11，m）图，且。设，任，则在G中度数与在度数之和定为，若有某点在G中，则在中，由定理， 为非平面图。易证G、存在汉密尔顿路，所以，连通。 若，则由定理，假设G、都为简单连通平面图，则， ，于是与矛盾。所以 至少有一个非平面图。友情提示：部分文档来自网络整理，供您参考！文档可复制、编制，期待您的好评与关注！165 / 8