离散数学试题与答案 (23)

二十三试题与 一、单项选择题：（每小题1分，本大题共10分） 1．命题公式是（ ）。 A、 矛盾式； B、可满足式； C、重言式； D、等价式。 2．下列各式中哪个不成立（ ）。 A、； B、； C、； D、。 3．谓词公式中的 x是（ ）。 A、自由变元； B、约束变元； C、既是自由变元又是约束变元； D、既不是自由变元又不是约束变元。 4．在0 之间应填入（ ）符号。 A、= ； B、； C、； D、。 5．设< A ，( > 是偏序集，，下面结论正确的是（ ）。 A、的极大元且唯一； B、的极大元且不唯一； C、的上界且不唯一； D、的上确界且唯一。 6．在自然数集N上，下列（ ）运算是可结合的。 （对任意） A、； B、； C、； D、。 7．Q为有理数集N，Q上定义运算*为a*b = a + b – ab ,则的幺元为（ ）。 A、a； B、b； C、1； D、0。 8．给定下列序列，（ ）可以构成无向简单图的结点次数序列。 A、（1，1，2，2，3）； B、（1，1，2，2，2）； C、（0，1，3，3，3）； D、（1，3，4，4，5）。 9．设G是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。 A、点与边； B、边与点； C、点与点； D、边与边。 10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。 A、5； B、7； C、9； D、8。 二、填空：（每空1分，本大题共15分） 1．在自然数集中，偶数集为、奇数集为，则= ； = 。 2．设，则 r (R) = ；s (R) = ；t (R) = 。 3．设R为集合A上的等价关系，对，集合= ， 称为元素a形成的R等价类，，因为 。 4．任意两个不同小项的合取为 ，全体小项的析取式为 。 5．设，，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1） ； （2） 。 6．设T为根树，若 ，则称T为m元树； 若 则称T为完全m叉树。 7．含5个结点，4条边的无向连通图（不同构）有 个， 它们是 。 三、判断改正题：（每小题2分，本大题共20分） 1．命题公式是一个矛盾式。 （ ） 2．任何循环群必定是阿贝尔群，反之亦真。 （ ） 3．根树中最长路径的端点都是叶子。 （ ） 4．若集合A上的关系R是对称的，则也是对称的。 （ ） 5．数集合上的不等关系（≠）可确定A的一个划分。 （ ） 6．设集合A、B、C为任意集合，若A×B = A×C，则B = C。 （ ） 7．函数的复合运算“。”满足结合律。 （ ） 8．若G是欧拉图，则其边数合结点数的奇偶性不能相反。 （ ） 9．图G为（n , m）图，G的生成树必有n个结点。 （ ） 10．使命题公式的真值为F的真值指派的P、Q、R值分别是T、F、F。 （ ） 四、简答题（每小题5分，本大题共25分） 1．设和都是群的子群，问和是否是的子并说明理由。 2．设，，从A到B的关系 ，试给出R的关系图和关系矩阵，并说明此关系是否为函数？为什么？ 3．设是半群，是左零元，对任是否是左零元？为什么？ 4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由） 5．通过主合取范式，求出使公式的值为F的真值指派。 五、证明题：（共30分） 1．设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。 2．试证明若是群，，且任意的，对每一个，有，则是的子群。 3．设G是每个面至少由（）条边围成的连通平面图，试证明，其中为结点数，为边数。 4．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。 答案 一、单项选择题： 题号 1 2 3 4 5 6 7 8 9 10 答案 C A C D D B D B C C 二、填空题： 1．。 2．， ， ， ，， 所以， 。 3．；。4．永假式（矛盾式），永真式（重言式）。 5．（1）。 （2）。 6．每个结点的出度都小于等于m；除叶子外，每个结点的出度都等于m。 7．3。 三、判断改正题： 1．× 命题公式是一个重言式。 2．× 任何循环群必定是阿贝尔群，但反之不真。 3．× 根树中最长路径的端点不都是叶子。 4．√ 5．× ≠不能确定A的一个划分。 6．√ 7．√ 8．× 欧拉图其边数和结点数的奇偶性可以相反。 9．√ 10．√ 四、简答题 1．解：是 的子群，不一定是的子群。 都是的子群， 的子群。 如：G = {1，5，7，11}，：模12乘，则为群。且H = {1，5}，K = {1，7}， 皆为的子群，但， 不是的子群。因为 ，即运算不封闭。 2．解：则R的关系图为： R的关系矩阵为 关系R不是A到B的函数，因为 元素2，4的象不唯一（或元素9无象）。 3．解：仍是左零元。因为，由于是左零元，所以，，又 为半群，所以*可结合。 所以，，所以，仍是左零元。 4．解：可能。将人用结点

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf

示，当两人是朋友时相应结点间连一条边，则得一个无向图 ，20人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一次得回路。由题已知，，，由判定定理，G中存在一条汉密尔顿回路。即所谈情况可能。 5．解： ∴使公式的值为F的真值指派为： ； ； 。 五、证明题： 1．证明：假设R不是反对称的，则 由R的传递性， ∴ 此与R反自反矛盾，∴R反对称。 2．证明：（1）设群的幺元为，则有 ，∴即H非空。 （2），则 有 ， 从而 故 是的子群。 3．解：设连通平面图G有个面：则有 ， 又有题意， 又 ， ∴， 。从而 ，∴。 4．解：设：喜欢美术，：喜欢体育，：喜欢音乐。论域：人。 命题形式化为：前提：，， 结论：。 证明：（1） P (2) ES(1) (3) P (4) US(4) (5) T(2)(4)I (6) P (7) US(6) (8) T(5)(7)I (9) EG(8) ∴ 结论有效。 A� � 2� � 3� � 4� � 9� � B� � 2� � 4� � 7� � 10� � 12� �