专业课考研复习资料（最新版）专业课考研复习资料（最新版）（知识点汇总（知识点汇总-考研重点集合考研重点集合-精准预测再现）精准预测再现）封封面面离散数学离散数学-模拟卷模拟卷 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的极大元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)刻划下列 （）关系。A、点与边；B、边与点；C、点与点；D、边与边。10一颗树有两个 2 度结点，1 个 3 度结点和 3 个 4 度结点，则 1 度结点数为（） 。A、5；B、7；C、9；D、8。二、填空： （每空二、填空： （每空 1 分，本大题共分，本大题共 15 分）分）1在自然数集中，偶数集为1N、奇数集为2N，则21NN =；21NN =。2设3 , 34 , 2,2 , 1,4 , 3 , 2 , 1，RX，则r (R) =；s (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任何循环群必定是阿贝尔群，反之亦真。（）3根树中最长路径的端点都是叶子。（）4若集合 A 上的关系 R 是对称的，则1R也是对称的。（）5数集合上的不等关系（）可确定 A 的一个划分。（）6设集合 A、B、C 为任意集合，若 AB =AC，则 B = C。（）7函数的复合运算“。 ”满足结合律。（）8若 G 是欧拉图，则其边数e合结点数v的奇偶性不能相反。（）9图 G 为（n , m）图，G 的生成树GT必有 n 个结点。（）10使命题公式)(RQP的真值为 F 的真值指派的 P、Q、R 值分别是 T、F、F。（）四、简答题（每小题四、简答题（每小题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通过主合取范式，求出使公式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符号化下列各命题，并说明结论是否有效（用推理规则） 。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。离散数学离散数学-模拟卷模拟卷2一、填空题： （每空一、填空题： （每空1分，本大题共分，本大题共15分）分）1 设4,3,2aA，1,4,3,aB， 请在下列每对集合中填入适当的符号：,。（1）aB,(2)3,4,aA。2设1,0A，N 为自然数集， 是偶数。，是奇数，xxxf10)(若AAf：，则f是射的，若ANf：，则f是射的。3设图 G = 中有 7 个结点，各结点的次数分别为 2，4，4，6，5，5，2，则 G 中有条边，根据。4两个重言式的析取是，一个重言式和一个矛盾式的合取是。5设个体域为自然数集，命题“不存在最大自然数”符号化为。6设 S 为非空有限集，代数系统,2S中幺元为，零元为。7设 P、Q 为两个命题，其 De-Morden 律可表示为。8当8G时，群,G只能有阶非平凡子群，不能有阶子群，平凡子群为。二、单项选择题： （每小题二、单项选择题： （每小题1分，本大题共分，本大题共15分）分）1设162xxxA是整数且，下面哪个命题为假（） 。A、A4,2,1,0；B、A1,2,3；C、A；D、Axxx 4是整数且。2设,BA，则 BA 是（） 。A、；B、；C、,；D、。3下图描述的偏序集中，子集,feb的上界为 （） 。A、cb,；B、ba,；C、b；D、cba,。4设f和g都是 X 上的双射函数，则1)(gf为（） 。A、11gf；B、1)(fg；C、11fg；D、1fg。5下面集合（）关于减法运算是封闭的。A、N ；B、2Ixx；C、12Ixx；D、是质数xx。6具有如下定义的代数系统,G， （）不构成群。A、10,1G，*是模 11 乘 ；B、9,5,4,3,1G，*是模 11 乘 ；C、QG（有理数集） ，*是普通加法 ；D、QG（有理数集） ，*是普通乘法。7设,32InmGnm，*为普通乘法。则代数系统,G的幺元为（） 。A、不存在 ；B、0032 e；C、32e；D、1132e。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设,fedcbaV ，,efeddaaccbbaE，则有向图EVG,是（） 。A、强连通的 ；B、单侧连通的 ；C、弱连通的 ；D、不连通的。10下面那一个图可一笔画出（） 。11在任何图中必定有偶数个（） 。A、度数为偶数的结点 ；B、入度为奇数的结点 ；C、度数为奇数的结点 ；D、出度为奇数的结点 。12含有 3 个命题变元的具有不同真值的命题公式的个数为（） 。A、32；B、23；C、322；D、232。13下列集合中哪个是最小联结词集（） 。A、,；B、,；C、,；D、,。14下面哪个命题公式是重言式（） 。A、)()(RQQP；B、PQP)(；C、)()(QPQP；D、PQP)(。15在谓词演算中，下列各式哪个是正确的（） 。A、),(),(yxxAyyxyAx；B、),(),(yxxAyyxyAx；C、),(),(yxxAyyxyAx；D、)()(xxAaA。三、判断改正题： （每小题三、判断改正题： （每小题2分，本大题共分，本大题共20分）分）1设2,1A，aB，则BABA222。 （其中A2为（A） ）()2设1,0A，2,1B，则2,0,1,1,0,1,2,1,0,1,1,02 BA。（）3集合 A 上的恒等关系是一个双射函数。（）4设 Q 为有理数集，Q 上运算 * 定义为),max(baba，则，Q是半群。 （）5阶数为偶数的有限群中，周期为 2 的元素的个数一定为偶数。（）6在完全二元树中，若有t片叶子，则边的总数12 te。（）7能一笔画出的图不一定是欧拉图。（）8设 P，Q 是两个命题，当且仅当 P，Q 的真值均为 T 时，QP 的值为 T。 （）9命题公式QQPP)(是重言式。（）10设，是研究生：xxP)(，曾读过大学：xxQ)(命题“所有的研究生都读过大学”符号化为：)()(xQxPx。（）四、简答题： （四、简答题： （25分）分）1设,cbaA ，A 上的关系,bccbbaaa，求出)()(,)(tsr和。2 集 合36,24,12,6,3,2A上 的 偏 序 关 系为 整 除 关 系 。 设12,6B，6,3,2C，试画出的哈斯图，并求 A，B，C 的最大元素、极大元素、下界、上确界。3图给出的赋权图表示五个城市54321vvvvv，及对应两城镇间公路的长度。试给出一个最优化的设计方案使得各城市间能够有公路连通。4 已知654321，G，7为模 7 乘法。 试说明7，G是否构成群？是否为循环群？若是，生成元是什么？5给定命题公式)()(WSRQP，试给出相应的二元树。五、证明题： （五、证明题： （25分）分）1 如果集合 A 上的关系 R 和 S 是反自反的、 对称的和传递的， 证明：SR 是 A 上的等价关系。2用推理规则证明)()(aGaP是)()(,)(,)()(,)()()(xGxSxaSaRaQxRxQxPx的有效结论。3若有 n 个人，每个人都恰有三个朋友，则 n 必为偶数。4设 G 是（11，m）图，证明 G 或其补图G是非平面图。