2022年2022年离散数学试卷二十三试题与答案 .pdf

《2022年2022年离散数学试卷二十三试题与答案 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学试卷二十三试题与答案 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、试卷二十三试题与答案一、单项选择题：（每小题 1分，本大题共 10分）1命题公式)(PQP是（） 。A、矛盾式；B、可满足式；C、重言式；D、等价式。2下列各式中哪个不成立（） 。A、)()()()(xxQxxPxQxPx；B、)()()()(xxQxxPxQxPx；C、)()()()(xxQxxPxQxPx；D、QxxPQxPx)()(。3谓词公式)()()(xQyyRxPx中的x 是（） 。A、自由变元；B、约束变元；C、既是自由变元又是约束变元；D、既不是自由变元又不是约束变元。4在 0 之间应填入（）符号。A、= ；B、；C、；D、。5设 是偏序集，AB，下面结论正确的是（） 。A、B

2、的极大元Bb且唯一；B、B的极大元Ab且不唯一；C、B的上界Bb且不唯一；D、B的上确界Ab且唯一。6在自然数集N 上，下列（）运算是可结合的。（对任意Nba ,）A、baba；B、),max(baba；C、baba5；D、baba。7Q 为有理数集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)刻划下列（）

3、关系。A、点与边；B、边与点；C、点与点；D、边与边。10 一颗树有两个2 度结点，1 个 3 度结点和 3 个 4 度结点，则 1 度结点数为（） 。A、5；B、7；C、9；D、8。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 二、填空：（每空 1分，本大题共 15分）1 在自然数集中， 偶数集为1N、 奇数集为2N， 则21NN= ；21NN= 。2设3,34,2,2,1,4,3,2,1，RX，则r (R) = ； s (

4、R) = ； t (R) = 。3 设 R 为集合 A上的等价关系， 对Aa， 集合Ra= ，称为元素a形成的R等价类，Ra，因为。4 任 意 两 个 不 同 小 项 的 合 取 为， 全 体 小 项 的 析 取 式为。5设为偶数xxQ:)(，为素数xxP:)(，则下列命题：（1）存在唯一偶素数； （ 2）至多有一个偶素数；分别形式化：（1）；（2）。6设 T 为根树，若，则称 T 为 m 元树；若则称 T 为完全 m 叉树。7含 5 个结点， 4 条边的无向连通图（不同构）有个，它们是。三、判断改正题：（每小题 2分，本大题共 20分）1命题公式BBAA)(是一个矛盾式。（）2任何循环群必定

5、是阿贝尔群，反之亦真。（）3根树中最长路径的端点都是叶子。（）4若集合 A 上的关系 R 是对称的，则1R也是对称的。（）5数集合上的不等关系（）可确定A 的一个划分。（）6设集合 A、 B、 C 为任意集合，若AB = A C，则 B = C。（）7函数的复合运算“。 ”满足结合律。（）8若 G 是欧拉图，则其边数e合结点数v的奇偶性不能相反。（）9图 G 为（ n , m）图， G 的生成树GT必有 n 个结点。（）10使命题公式)(RQP的真值为 F 的真值指派的P、Q、R 值分别是 T、F、F。（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

6、 - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 四、简答题（每小题5分，本大题共 25分）1设,H和,K都是群,G的子群，问,KH和,KH是否是,G的子并说明理由。2设9432，A，12,10742，B，从 A 到 B 的关系,baBbAabaR整除且，试给出R 的关系图和关系矩阵，并说明此关系是否为函数？为什么？3设,S是半群，LO是左零元，对任LOxSx,是否是左零元？为什么？4某次会议有20 人参加， 其中每人至少有10 个朋友， 这 20 人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）5

7、通过主合取范式，求出使公式RQP)(的值为 F 的真值指派。五、证明题：（共 30分）1设 R 为集合 A 上的二元关系，如果R 是反自反的和可传递的，则R 一定是反对称的。2试证明若,G是群，GH， 且任意的Ha，对每一个Gx，有axxa，则,H是,G的子群。3设 G 是每个面至少由k（3k）条边围成的连通平面图，试证明2)2(kvke，其中v为结点数，e 为边数。4符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。 每个人或喜欢体育，或喜欢音乐， 有的人不喜欢音乐，因而有的人不喜欢美术。答案一、单项选择题：题号1 2 3 4 5 6 7 8 9 10

8、 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 答案C A C D D B D B C C 二、填空题：1;2N。 24,4,2,2,1,1,3,3,4,2,2,1)(Rr，2,4,1,2,3,3,4,2,2,1)(Rs，3,3,4,12RRR，3,323RRR，3,334RRR，所以，4,1,3,3,4,2,2,1)(Rt。3,aRxAxxaR；Raa。4永假式（矛盾式） ，永真式（重言式） 。5 （1）)()()()(yx

9、yPyQyxPxQx。（2）)()()()(yxyPyQxPxQyx。6每个结点的出度都小于等于m；除叶子外，每个结点的出度都等于m。73。三、判断改正题：1命题公式BBAA)(是一个重言式。2任何循环群必定是阿贝尔群，但反之不真。3根树中最长路径的端点不都是叶子。45不能确定A 的一个划分。678欧拉图其边数e和结点数v的奇偶性可以相反。910四、简答题1解：,KH是,G的子群，,KH不一定是,G的子群。,KHKbaHbaKHba和由则都 是,G的子群，,1,11GKHKHbaKbaHba是且的子群。如：G = 1 ，5，7，11 ，：模 12 乘，则,G为群。且H = 1 ，5 ，K =

10、1 ，7 ，,KH和皆为,G的子群，但7,5,1KH，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - ,KH不是,G的子群。因为KH1175，即运算不封闭。2解：12,4,4,4,12,3,12,2,10,2,4,2,2,2R则 R 的关系图为：R 的关系矩阵为00000100101000011011RM关系 R 不是 A 到 B 的函数，因为元素 2，4 的象不唯一（或元素9 无象）。3解：LOx仍是左零元。因为Sy，由于LO

11、是左零元，所以，LLOyO，又,S为半群，所以 *可结合。所以，LLLOxyOxyOx)()(，所以，LOx仍是左零元。4解：可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图EVG,，20 人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅一 次得 回 路。 由题 已知 ，10)deg(,10)deg(,vuVvu，20)deg()deg(vu，由判定定理， G 中存在一条汉密尔顿回路。即所谈情况可能。5解：010110100)()()()()()()()(MMMRQPRQPRQPRQPRQRPRQPRQP原式使公式RQP)(的值为 F 的真值指派为：0:0:1:R

12、QP；0:1:1:RQP；0:1:0:RQP。五、证明题：1证明：假设R 不是反对称的，则yxRxyRyx,由 R 的传递性，Rxx,此与 R 反自反矛盾，R 反对称。A 2 3 4 9 B 2 4 7 10 12 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 2证明：（1）设群,G的幺元为 e ，则Gx有xeex，He即 H 非空。（2）Hba ,，则Gx有bxxbaxxa,，从而Hbabaxbxabxbbabbxbaxba

13、11111111,)()()()()()(故,H是,G的子群。3解：设连通平面图G 有t个面：trrr,21则有2rev，又有题意，tiiiktrkr1)deg(,)deg(又ertii2)deg(1，kte2，ekt2。从而22ekev，)2(2vkke。4解：设)(xP：x喜欢美术，)( xQ：x喜欢体育，)( xR：x喜欢音乐。论域：人。命题形式化为：前提：)()(xQxPx，)()(xRxQx，)(xRx结论：)( xPx。证明：（1）)(xRx P (2) )(aR ES(1) (3) )()(xRxQx P (4) )()(aRaQ US(4) (5) )(aQ T(2)(4)I (6) )()(xQxPx P (7) )()(aQaP US(6) (8) )(aP T(5)(7)I (9) )(xPx EG(8) 结论有效。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -