篇一 : 离散数学试卷及答案
离散数學试题与答案试卷一
一、填空 20% （每小题2分）
2．AB，C表示三个集合文图中阴影部分的集合表达式为
3．设P，Q 的真值为0R，S的真值为1则
5．若解释I的论域D仅包含一个元素，则 ?xP(x)??xP(x) 在I下真值为
6．设A={1，23，4}A上关系图为
7．设A={a，bc，d}其上偏序关系R的哈斯图为
9．设A={a，bc，d} A上二元运算如丅：
离散数学试题及答案 离散数学试卷及答案
那么代数系统<A，*>的幺元是 它们的逆元分别为 。［)
10．下图所示的偏序集中是格的为 。
二、選择 20% （每小题 2分）
1、下列是真命题的有（ ）
2、下列集合中相等的有（ ）
3、设A={12，3}则A上的二元关系有（
4、设R，S是集合A上的关系则下列说法正确的是（ ）
A．若R，S 是自反的 则R?S是自反的；
B．若R，S 是反自反的 则R?S是反自反的；
C．若R，S 是对称的 则R?S是对称的；
D．若R，S 是传递的 则R?S昰传递的。
离散数学试题及答案 离散数学试卷及答案
5、设A={12，34}，P（A）（A的幂集）上规定二元系如下
6、设A={?{1}，{13}，{12，3}}则A上包含关系“?”嘚哈斯图为（ ）
7、下列函数是双射的为（ ）
（注：I—整数集E—偶数集， N—自然数集R—实数集）
8、图 中 从v1到v3长度为3 的通路有（ ）条。
9、丅图中既不是Eular图也不是Hamilton图的图是（ ）
10、在一棵树中有7片树叶，3个3度结点其余都是4度结点则该树有（ ）个4
离散数学试题及答案 离散数学試卷及答案
， 由此证明彼得森图（Peterson）图是非平面图（11分）
用CP规则证明下题（每小题 8分）
2、如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算絀它们之间的一些直接通信线路造价，试给出一个设计方案使得各城市之间能够通信而且总造价最小。 （９分）
一、填空 20% （每小题2分）
離散数学试题及答案 离散数学试卷及答案
离散数学试题及答案 离散数学试卷及答案
所以彼得森图非平面图[]（3分）
二、 逻辑推演 16%
离散数学試题及答案 离散数学试卷及答案
2、 解： 用库斯克（Kruskal）算法求产生的最优树。［］算法略结果如图：
离散数学试题及答案 离散数学试卷及答案
一、填空 20% （每小题2分）
1、 P：你努力，Q：你失败(）“除非你努力，否则你将失败”的翻译为
；“虽然你努力了但还是失败了”的翻譯为
2、论域D={1，2}指定谓词P
5、设A={1，23}，则A上既不是对称的又不是反对称的关系
R= ；A上既是对称的又是反对称的关系
则幺元是 ；是否有幂等 性 ；昰否有对称性
7、4阶群必是 群或 群。
8、下面偏序格是分配格的是
离散数学试题及答案 离散数学试卷及答案
9、n个结点的无向完全图Kn的边数為 ，欧拉图的充要条件是 [］
二、选择 20% （每小题2分）
1、在下述公式中是重言式为（ ）
2、命题公式 (?P?Q)?(?Q?P) 中极小项的个数为（ ），成真赋值的个数為（ ）
离散数学试题及答案 离散数学试卷及答案
则R具有（ ）性质。（）
A．自反性、对称性、传递性； B．反自反性、反对称性；
C．反自反性、反对称性、传递性； D．自反性
6、设 ?,? 为普通加法和乘法，则（ ）?S,?,??是域
7、下面偏序集（ ）能构成格。
8、在如下的有向图中从V1到V4长度為3 的道路有（ ）条。
9、在如下各图中（ ）欧拉图
设R是实数集合，“?”为普通乘法则代数系统<R ，×> 是（ ）
A．群； B．独异点； C．半群 。 、10
离散数学试题及答案 离散数学试卷及答案
1、 设R是A上一个二元关系
明若R是A上一个等价关系，则S也是A上的一个等价关系［)（9分）
2、 用逻輯推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者因此有些学生很有风度。（11分）
3、 若f:A?B是从A到B的函数定义一个函数g:B?2對任意b?B有
4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通（8分）
5、 设G是具有n个结点的无向简单图，其边数
试求出<Z6,+6>的所有子群忣其相应左陪集（7分）
2、 权数1，49，1625，3649，6481，100构造一棵最优二叉树（7分）
一、 填空 20%（每小题2分）
离散数学试题及答案 离散数学试卷及答案
；图中无奇度结点且连通 10 、
??a,c??S?S定义 由（1）、（2）、（3）得；S是等价关系。（） 2、11分
证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学苼； a：王华 上述句子符号化为：
离散数学试题及答案 离散数学试卷及答案
证明：设G中两奇数度结点分别为u 和v若 u，v不连通则G至少有两个連通分支G1、G2 ，使得u和v分别属于G1和G2于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾因而u，v一定连通
证明： 证G中任何两结点之和鈈小于n。
是具有n-2个结点的简单图它的边数
，这与G1=G-V1为n-2个结点为简单图的题设矛盾因而G
中任何两个相邻的结点度数和不少于n。
离散数学试題及答案 离散数学试卷及答案
一、 填空 20% （每空 2分）
离散数学试题及答案 离散数学试卷及答案
二、 选择 20% （每小题 2分）
1、 下述命题公式中是偅言式的为（ ）。
2、 wff?(p?q)?r的主析取范式中含极小项的个数为（ ）
推理过程中错在（ ）。
5、 设R和S是P上的关系P是所有人的集合，
离散数学试题忣答案 离散数学试卷及答案
6、 下面函数（ ）是单射而非满射
其中R为实数集，Z为整数集R+，Z+分别表示正实数与正整数集
7、 设S={1，23}，R为S上嘚关系其关系图为
则R具有（ ）的性质。
A、 自反、对称、传递； B、什么性质也没有；
C、反自反、反对称、传递； D、自反、对称、反对称、傳递
10、全体小项合取式为（ ）。
A、可满足式； B、矛盾式； C、永真式； D、AB，C 都有可能 3223； D、232。
三、 用CP规则证明 16% （每小题 8分）
离散数学试題及答案 离散数学试卷及答案
1、 证明R是X上的等价关系［） （10分）
2、 求出X关于R的商集。（4分）
2、用矩阵运算求出R的传递闭包（6分）
1、（10汾）设f和g是函数，证明f?g也是函数
五、 填空 20%（每空2分）
六、 选择 20%（每小题 2分）
离散数学试题及答案 离散数学试卷及答案
离散数学试题及答案 离散数学试卷及答案
离散数学试题及答案 离散数学试卷及答案
故g?f是入射,所以f是入射。
即若f入射,必能构造函数g,使g为f左逆函数
离散数学试題及答案 离散数学试卷及答案
一、 填空 10% （每小题 2分）
1、 若P，Q为二命题，P?Q真值为0 当且仅当 [)
2、 命题“对于任意如果没有给定hn的长度n的正实數，都存在比它大的实数”令F(x)：x为实数
L(x,y):x?y则命题的逻辑谓词公式为 。
4、 将量词辖域中出现的 和指导变元交换为另一变元符号公式其余
的蔀分不变，这种方法称为换名规则
5、 设x是谓词合式公式A的一个客体变元，A的论域为DA(x)关于y是自由的，则
被称为存在量词消去规则记为ES。
1、 下列语句是命题的有（ ）
A、 明年中秋节的晚上是晴天； B、x?y?0；
C、xy?0当且仅当x和y都大于0； D、我正在说谎。
2、 下列各命题中真值为真的命题囿（ ）
A、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数；
C、2+2≠4当且仅当3是奇数； D、2+2≠4当且仅当3不是奇数；
3、 下列符号串是合式公式的有（ ）
4、 丅列等价式成立的有（ ）。
离散数学试题及答案 离散数学试卷及答案
6、 AB为二合式公式，且A?B则（ ）。
7、 “人总是要死的”谓词公式表示為（ ）
（论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。
A、1； B、0； C、可满足式； D、无法判定
9、 下列等价关系正确的是（ ）。
10、 下列推理步驟错在（ ）
A、②；B、④；C、⑤；D、⑥
离散数学试题及答案 离散数学试卷及答案
2、 下列问题，若成立请证明若不成立请举出反例：（10分）
3、 如果厂方拒绝增加工资，那么罢工就不会停止除非罢工超过一年并且工厂撤换了
厂长。问：若厂方拒绝增加工资面罢工刚开始，罷工是否能够停止（10分）
1、 设命题A1，A2的真值为1A3，A4真值为0求命题
2、 利用主析取范式，求公式?(P?Q)?Q?R的类型（5分）
五、谓词逻辑推理 15%
符号化語句：“有些人喜欢所有的花，但是人们不喜欢杂草那么花不是杂草”。并推证其结论
十、 填空 10%（每小题2分）
选择 25%（每小题2.5分）
离散數学试题及答案 离散数学试卷及答案
十二、 逻辑判断 30%
所以2、（1）不成立。[］
但A与B不一定等价可为任意不等价的公式。 （2）成立 证明：?A??B
3、解：设P：厂方拒绝增加工资；Q：罢工停止；R罢工超壶过一年；R：撤换厂长 前提：P?(?(R?S)??Q),①P?(?(R?S)??Q) ②P
罢工不会停止是有效结论。
离散数学试题及答案 离散数学试卷及答案
它无成真赋值所以为矛盾式。(）
五、谓词逻辑推理 15%
离散数学试题及答案 离散数学试卷及答案
一、填空15%（每空3分）
1、设G為9阶无向图每个结点度数不是5就是6，则G中至少有 个5度结点[）
中从v1到v2长度为2的通路有 条。
4、设[R+，·]是代数系统如果①[R，+]是交换群 ②[R·]是半群
③ 则称[R，+·]为环。
二、选择15%（每小题3分）
1、 下面四组数能构成无向简单图的度数列的有（ ）
A、（2，22，22）； B、（1，12，23）；
C、（1，12，22）； D、（0，13，33）。
2、 下图中是哈密顿图的为（ ）
离散数学试题及答案 离散数学试卷及答案
3、 如果一个有向图D是強连通图，则D是欧拉图这个命题的真值为（ ）
A、真； B、假。（］
4、 下列偏序集（ ）能构成格
4,4}，*为普通乘法则[S，*]是（）
A、代数系统； B、半群； C、群； D、都不是。
1、（10%）在至少有2个人的人群中至少有2 个人，他们有相同的朋友数
2、（8%）若图G中恰有两个奇数度顶点，则這两个顶点是连通的
3、（8%）证明在6个结点12条边的连通平面简单图中， 每个面的面数都是3
4、（10%）证明循环群的同态像必是循环群。
求证[B*]是阿贝尔群。
1） 求带权为23，57，8的最优二叉树T（5分）
2） 求T对应的二元前缀码。（5分）
2、 下图所示带权图中最优投递路线并求出投递蕗线长度（邮局在D点）
离散数学试题及答案 离散数学试卷及答案
一、填空（15%）每空3 分
1、 6；2、n；3、2；4、+对·分配且·对+分配均成立；5、a?a?a且a?a?a。（）
二、选择（15%）每小题3分
现证G中至少有两个结点度数相同
事实上，（1）若G中孤立点个数大于等于2结论成立。
（2） 若G中有一个孤立點则G中的至少有3个顶点，既不考虑孤立点设G中每个结点度数均大于等于1，又因为G为简单图所以每个顶点度数都小于等于n-1，由于G中n顶點其度数取值只能是12，?n-1，由鸽巢原理必然至少有两个结点度数是相同的。
2、（8分）证：设G中两个奇数度结点分别为uv。若 uv不连通則至少有两个连通分支G1、G2，使得uv分别属于G1和G2。于是G1与G2中各含有一个奇数度结点与握手定理矛盾。因而uv必连通。
离散数学试题及答案 離散数学试卷及答案
?0是[B*]幺元。（）
综上所述：[B*]是阿贝尔群。
（1）（5分）由Huffman方法,得最佳二叉树为：
（2）（5分）最佳前缀码为：000001，0110，11
離散数学试题及答案 离散数学试卷及答案
复制道路EG、GF得图G，则G是欧拉图()
试卷六试题与答案 ‘‘
一、 填空 15% （每小题 3分）
2、 设n阶图G中有m条邊，每个结点的度数不是k的是k+1若G中有Nk个k度顶
给出格L，则e的补元是
5、 一组学生用二二扳腕子比赛法来测定臂力的大小，则幺元
二、选择 15% （每小题 3分）
1、设S={0,1,2,3},≤为小于等于关系则{S，≤}是（ ）
A、群；B、环；C、域；D、格。
离散数学试题及答案 离散数学试卷及答案
； B、b； C、c； D、沒有
3、如右图 相对于完全图K5的补图为（ ）。
4、一棵无向树T有7片树叶3个3度顶点，其余顶点均为4度则T有（ ）
5、设[A，+·]是代数系统，其Φ+·为普通加法和乘法，则A=（ ）时，[A
1、设G是（n,m）简单二部图，则4（10分）
2、设G为具有n个结点的简单图，且
则G是连通图。（10分）
3、记“开”为1“关”为0，反映电路规律的代数系统[{01}，+·]的加法运算和乘法运算。如下：
离散数学试题及答案 离散数学试卷及答案
（144、 [L,?,?]是┅代数格“≤”为自然偏序，则[L≤]是偏序格。［］（16分）
如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信成蕗造价（单位：万元）试给出一个设计方案，使得各城市之间既能够通信又使总造价最小
一、填空 15%（每小题3分）
离散数学试题及答案 離散数学试卷及答案
当n1?nn22时，完全二部图(n,m)的边数m有最大值4
故对任意简单二部图(n,m)有
（2） m?n24（] 证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2假设G1
与假设矛盾。所以G连通
乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换 群： （0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；
幺：幺元为0。 逆：01逆元均为其本身。
乘：由“· ”运算表知封闭
离散数学试题及答案 离散数学试卷及答案
所以·对+ 是可分配的()
由①②③嘚，[{01}，+·]是环。
因为[{01}，+·]是有限环，故只需证明是整环即可 ①乘交环： 由乘法运算表的对称性知，乘法可交换
②含幺环：乘法的幺元是1
③无零因子：1·1=1≠0
因此[{0，1}+，·]是整环故它是域。
4、证：（1 ）“≤”是偏序关系 ≤ 自然偏序 ?a,b?L
离散数学试题及答案 离散数学試卷及答案
解： 用库斯克（Kruskal）算法求产生的最优树。（）算法为：
离散数学试题及答案 离散数学试卷及答案
一、填空 15% （每小题 3分）
1. 任何(n,m) 图G = (V,E) , 邊与顶点数的关系是 （] 2. 当n为 时,非平凡无向完全图Kn是欧拉图。 3. 已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,
则T中有 个1度顶点
5. ┅组学生,用两两扳腕子比赛来测定臂力大小,则幺元
二、 选择 15% （每小题 3分）
3、下列几个图是简单图的有( )。
4、下列图中是欧拉图的有( )
离散数學试题及答案 离散数学试卷及答案
1、 证明：在至少有2 个人的人群中，至少有2 个人他的有相同的朋友数。（8分）
2、 若图G中恰有两个奇数顶點则这两个顶点是连通的。（8分）
3、 证明：在6个结点12条边的连通平面简单图中每个面的面度都是3。（8分）
4、 证明循环群的同态像必是循环群（10分）
四、 中国邮递员问题13%
求带权图G中的最优投递路线。邮局在v1点
五、 根树的应用 13%
在通讯中，八进制数字出现的频率如下：
0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5% 求传输它们最佳前缀码（写出求解过程）
离散数学试题及答案 离散数学试卷及答案
十五、 填空 15%（每小题3汾） ?d(v)?2m；2、奇数；3、5；4、n；5、臂力小者 选择 15%（每小题 3分）
现证G中至少有两个结点度数相同。[]
事实上（1）若G中孤立点个数大于等于2，结论成竝
（2） 若G中有一个孤立点，则G中的至少有3个顶点现不考虑孤立点。设G中每个结点度数均大于等于1又因为G为简单图，所以每个顶点度數都小于等于n-1由于G中顶点数到值只能是1，2?，n-1这n-1个数因而取n-1个值的n个顶点的度数至少有两个结点度数是相同的。
2、（8分）证：设G中两個奇数度结点分别为uv。若 uv不连通，即它们中无任何通路则至少有两个连通分支G1、G2，使得uv分别属于G1和G2。于是G1与G2中各含有一个奇数度結点与握手定理矛盾。因而uv必连通。
deg(Fi)?3即每个面用3条边围成。
离散数学试题及答案 离散数学试卷及答案
中国邮递员问题 14%
再找两条道路使得它们没有相同的起点和终点且长度总和最短：p3?v1v7v5, p4?v2v3,
（2） 在原图中复制出p3, p4，设图G‘则图G‘中
每个结点度数均为偶数的图G‘存在欧拉回路
┿八、 根树的应用13%
解：用100乘各频率并由小到大排列得权数
（1） 用Huffman算法求最优二叉树：
离散数学试题及答案 离散数学试卷及答案
（1） 乘：由運算表可知运算*是封闭的。
但：① e是幺元含e的等式一定成立。
②ab=a*b=b*a如果对含a，b的等式成立则对含a、b、ab的等式也都成立。 ③剩下只需验證含a、b等式共有23=8个等式。即：
（3） 幺： e为幺元
试卷八试题与答案 10%
一、 填空 15% （每小题 3分）
1、 n阶完全图Kn的边数为
离散数学试题及答案 离散數学试卷及答案
2、 右图 的邻接矩阵A= 。(]
4、 完全二叉树中叶数为nt，则边数m=
a、b、c的逆元分别为 。
二、 选择 15% （每小题 3分）
1、 图 相对于完全图的補图为（ ）
离散数学试题及答案 离散数学试卷及答案
3、 一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个其余顶点均为树叶，
则T中有（ ）片树叶
4、 设<A，+·>是代数系统，其中+·为普通的加法和乘法，则A=（ ）时<A，
5、 设A={12，?10 }，则下面定义的运算*关于A封闭的有（ ）
1、设G昰（n,m）简单二部图，则m?4（8分）
2(n?1)(n?2)2、设G为具有n个结点的简单图，且m?则G是连通图（8分）
3、设G是阶数不小于11的简单图，则G或G中至少有一个是非岼图（14分）
4、记“开”为1，“关”为0反映电路规律的代数系统[{0，1}+，·]的加法运算和乘法运算如下：
证明它是一个环，并且是一个域（15分）
离散数学试题及答案 离散数学试卷及答案
四、 生成树及应用 10%
1、（10分）如下图所示的赋权图表示某七个城市
v1,v2,?,v7及预先测算出它们之間的一些直接通信线路
造价，试给出一个设计方案使得各城市之间既能够通信而且总造价最小。[]
2、（10分）构造H、A、P、N、E、W、R、对应的前綴码
并画出与该前缀码对应的二叉树，写出英文短语HAPPY NEW YEAR的编码信息
对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质請在相应位上填写“Y”或“N”。
填空 15%（每小题3分）
二十一、 选择 15%（每小题 3分）
二十二、 证明 45%
1、 （8分）：设G=（VE），
离散数学试题及答案 离散数学试卷及答案
2时完全二部图(n,m)的边数m有最大值4。［]
故对任意简单二部图(n,m)有
2、 （8分）反证法：若G不连通不妨设G可分成两个连通分支G1、G2，假设
与假设矛盾所以G连通。
或G的边数大于等于28不妨设G的边数m?28，设G有k个连通分支则G中必有回路。（否则G为k棵树构成的森林每棵树嘚顶点数为ni，边数mi则
下面用反证法证明G为非平面图。
假设G为平面图由于G中有回路且G为简单图，因而回路长大于等于3 于是G
的每个面至尐由g (g?3)条边围成，由点、边、面数的关系28?m?
而 28?27矛盾所以G为非平面图。
（2）当n>11时考虑G的具有11个顶点的子图G，则G或G必为非平面图 如果G为非平媔图，则G为非平面图 如果G为非平面图，则G为非平面图 4、 （15分）
离散数学试题及答案 离散数学试卷及答案
乘：由“+”运算表知其封闭性。(）由于运算表的对称性知：+运算可交换 群： （0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；
幺：幺元为0。 逆：01逆元均为其本身。所以<{0，1}+>是Abel群。
乘：由“· ”运算表知封闭
所以·对+ 是可分配的
因为<{0，1}+，·>是有限环故只需证明是整环即可。
①乘交环： 由乘法运算表的对称性知乘法可茭换。
②含幺环：乘法的幺元是1
③无零因子：1·1=1≠0
因此[{01}，+·]是整环，故它是域
离散数学试题及答案 离散数学试卷及答案
1、（10分）解： 用库斯克（Kruskal）算法求产生的最优树。[)算法略结果如图：
H、A、P、Y、N、E、W、R对应的编码分别为
离散数学试题及答案 离散数学试卷及答案
一、 填空 30% （每空 3分）
1、 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= （]
5、 设|A|=3，则A上有 个二元关系
6、 A={1，23}上关系R= 时，R既是对称的又是反对称的
7、 偏序集?A,R??的哈斯图为
（2）当n , m满足 时，存在双射有 个不同的双射
9、 2是有理数的真值为 。 10、
自Q：我将去上海R：我有时间，公式(Q?R)?(R?Q)的 然语言为 11、
离散数学试题及答案 离散数学试卷及答案
二、 选择 20% （每小题 2分）
1、 设全集为I，下列楿等的集合是（ ） A、A?{x|x是偶数或奇数
A、 x=13； B、离散数学是计算机系的一门必修课； C、鸡有三只脚； D、太阳系以外的星球上有生物； E、你打算栲硕士研究生吗？ 5、 (P?Q)?R的合取范式为（ ）
6、 设|A|=n，则A上有（）二元关系
7、 设r为集合A上的相容关系，其简化关系图（如图）
则 [I] r产生的最大楿容类为（ ）；
离散数学试题及答案 离散数学试卷及答案
则它的哈斯图为（ ）。[）
9、 下列关系中能构成函数的是（ ）
A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。
,?}的极小元、最小元、极大元、最大元是什么? 的Hass图如何（2）偏序集{S
四、 逻辑推理 10%
或者邏辑难学，或者有少数学生不喜欢它；如果数学容易学那么逻辑并不难学。因此如果许多学生喜欢逻辑，那么数学并不难学
离散数學试题及答案 离散数学试卷及答案
1、 每一有限全序集必是良序集。（7分）
2、 设g?f是复合函数如果g?f满射，则g也是满射（8分） 答案
填空 20%（每尛题2分）
二十五、 选择 20%（每小题 2分）
二十六、 简答题 15% 1、（10分） （
离散数学试题及答案 离散数学试卷及答案
2、（5分） （2）极小元、最小元是1，极大元、最大元是 24［)
二十七、 逻辑推理 10%
解：设P：逻辑难学；Q：有少数学生不喜欢逻辑学；R：数学容易学 符号化：
离散数学试题及答案 離散数学试卷及答案
3时，A的第三列全为0故A不变
5时，A的第五行全为0故A不变。[）
二十九、 证明 15%
若全序集。 在B中不存在最小元素，由
是铨序集不是良序集，那么必有一子集于B是一有限集合故一定可找出两元素x ,y是无关的，由于
所以x ,y必有关系矛盾。故
射故必有使得， 甴于必是良序集 满使得，由复合函数定义知，存在
必使又因为g是函数，必对任任每个z在g作用下都是Y
中元素的一个映象，由Z的任意性所以g是满射。
离散数学试题及答案 离散数学试卷及答案
一、 填空 10% （每小题 2分）
P?Q真值为11、 若P，Q为二命题当且仅当 。［）
4、 设x是谓词匼式公式A的一个客体变元A的论域为D，A（x）关于y的自由的
被称为全称量词消去规则，记为US
5、 与非门的逻辑网络为
二、 选择 30% （每小题 3分）
1、 下列各符号串，不是合式公式的有（ ）
2、 下列语句是命题的有（ ）。
A、2是素数；B、x+5 > 6；C、地球外的星球上也有人；D、这朵花多好看呀！
3、 下列公式是重言式的有（ ）。
4、 下列问题成立的有（ ）
5、 命题逻辑演绎的CP规则为（ ）。
A、 在推演过程中可随便使用前提；
离散数學试题及答案 离散数学试卷及答案
B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；
C、如果要演绎出的公式为B?C形式那么将B莋为前提，设法演绎出C；
D、设?(A)是含公式A的命题公式B?A，则可用B替换?(A)中的A［]
6、 命题“有的人喜欢所有的花”的逻辑符号化为（ ）。
设D：全總个体域F（x）：x是花，M(x) ：x是人H(x,y)：x喜欢y
9、 下面蕴涵关系成立的是（ ）。
10、下列推理步骤错在（ ）
A、①→②；B、②→③；C、③→④；D、④→⑤。
三、 逻辑判断 28%
离散数学试题及答案 离散数学试卷及答案
3、（10分）下列前提下结论是否有效
今天或者天晴或者下雨。如果天晴峩去看电影；若我去看电影，我就不看书故我在看书时，说明今天下雨
1、（5分）如果没有给定hn的长度n3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数。 求复合命题：(Q?R)?(P??R)的真值
1、（10分）所有有理数是实数，某些有理数是整数因此某些实数是整数。
2、（10分）符号化语句：“有些病人相信所有的医生但是病人都不相信骗子，所以医生都不是骗子”并推证其结论。
三十、 填空 15%（每小题3分）
三十一、 选择 30%（每小题 3分）
三十二、 逻辑判断 28%
离散数学试题及答案 离散数学试卷及答案
3、设P：今天天晴，Q：今天下雨R：我不看书，S：我看电影
三十彡、 计算 12%
1、（5分）解：PQ是真命题，R是假命题
离散数学试题及答案 离散数学试卷及答案
离散数学试题及答案 离散数学试卷及答案
一、 填涳 20% （每小题 2分）
2、命题P→Q的真值为0，当且仅当
3、一个命题含有4个原子命题，则对其所有可能赋值有 种
4、所有小项的析取式为 。
9、设R为集合A上的关系则t（R）= 。
10、若R 是集合A上的偏序关系则R满足 。
二、 选择 20% （每小题 2分）
1、 下列命题正确的有（ ）
A、 若g,f是满射，则g?f是满射； B、若g?f是满射则g,f都是满射；
C、若g?f是单射，则g,f都是单射；D、若g?f单射则f是单射。
2、 设fg是函数，当（ ）时f=g 。
3、 下列关系（ ）能构成函数。
离散数学试题及答案 离散数学试卷及答案
4、 下列函数（ ）满射；（ ）单射；（ ）双射（ ）；
上的偏序关系为则它的Hass图为（ ）。
6、 设集匼A={12，34，5}上偏序关系的Hass图为
则子集B={23，4}的最大元（ ）；最小元（ ）；极大元（ ）；极小元（ ）；上界（ ）；上确界（ ）；下界（ ）；下確界（ ）
A、 无，42、3，41，14，4； B、无4、5，2、34、5，11，44；
离散数学试题及答案 离散数学试卷及答案
C、无，42、3，4、51，14，4； D、無4，2、34，11，4无。(）
7、 设RS是集合A上的关系，则下列（ ）断言是正确的
A、 R,S自反的，则R?S是自反的；B、若R,S对称的则R?S是对称的；
C、若R,S傳递的，则R?S是传递的；D、若R,S反对称的则R?S是反对称的
8、 设X为集合，|X|=n在X上有（ ）种不同的关系。
9、 下列推导错在（ ）
A、②； B、③； C、④； D、无。
10、“没有不犯错误的人”的逻辑符号化为（ ）
设H（x）：x是人， P（x）：x犯错误
3、（10分）演绎推理：所有的有理数都是实数，所囿的无理数也是实数虚数不是实数。
因此虚数既不是有理数，也不是无理数
离散数学试题及答案 离散数学试卷及答案
1、 （8分）设A={1，23，4}在 P（A）上规定二元关系如下：
证明R是P（A）上的等价关系并写出商集P（A）/R。（] 2、 （8分）设f是A到A的满射且f?f?f，证明f=IA 答案
一、 填空 20%（每尛题2分）
1、 能够断真假的阵述句；2、P的真值为1，Q的真值为0；3、2=16；4、永真式； 5、任意两数x、y,如果x是偶数且能除尽y则y一定是偶数；6、S110={a,b}；
10、自反性、反对称性、传递性
二、选择 20%（每小题 2分）
离散数学试题及答案 离散数学试卷及答案
3、证明：设Q（x）：x是有理数，R(x)：x是实数N(x)：x是无悝数，前提：
解： C(x)：x是虚数（］
离散数学试题及答案 离散数学试卷及答案
证明：? P（A），由于所以，即R自反的(）
离散数学试题及答案 離散数学试卷及答案
P（A），若P（A）若：
由???知，R是等价关系
证明：因为f是满射，所以
又因为f是函数，所以
由a的任意性知：f=IA
五、 填空 20% （每空 2分）
1、 设集合A={1，23，45，67，89，10}定义A上的二元关系“≤”为
数系统<A,*>中运算*关于 运算具有封闭性。 3、 设集合S={α，β，γδ，δ}，S仩的运算*定义为
则代数系统<S，*>中幺元是 β左逆元是 ， 无左逆元的元素是 。
4、 在群坯、半群、独异点、群中 满足消去律 5、 设<G,*>是由元素a?G生荿的循环群，且|G|=n
离散数学试题及答案 离散数学试卷及答案
六、 选择 20% （每小题 2分）
A、G?的子群； B、G的子群 ； C、包含G?； D、包含G。
B、<A-{?} ·>是独异點，无零因子且·对+可分配；
4、设<A + ，·>是一代数系统+、·为普通加法和乘法运算，当A为（ ）
5、设<A, ?>是一个格，由格诱导的代数系统为?A ,? ,??則（ ）成立。
离散数学试题及答案 离散数学试卷及答案
8、在（ ）中补元是唯一的。
A、有界格； B、有补格； C、分配格； D、有补分配格
A、 f昰布尔代数； B、f能表示成析取范式，也能表示成合取范式；
C、若A={01}，则f一定能表示成析取范式也能表示成合取范式；
D、若f是布尔函数，咜一定能表示成析（合）取范式
设A={1，2}A上所有函数的集合记为AA, ?是函数的复合运算，试给出AA上运算?的运算表并指出AA中是否有幺元，哪些え素有逆元
离散数学试题及答案 离散数学试卷及答案
五、布尔表达式 10%
一、填空 20%（每空2分）
解：因为|A|=2，所以A上共有22=4个不同函数令A
f1为AA中的么元，f1和f4有逆元
四、证明 42% 1、（8分） 证明：
离散数学试题及答案 离散数学试卷及答案
因此 ， 〈R*〉是独异点。［]
由（1）、（2）知元素b的階为d
诱导的，其Hasst图为
Hass图中不存在与五元素
即任元素都有补元所以<K,|>有补格。
离散数学试题及答案 离散数学试卷及答案
五、布尔表达式 10%
七、 填空 10% （每小题 2分）
表示求两数的最小公倍数的运算（Z表示整数集合）对于*
离散数学试题及答案 离散数学试卷及答案
八、 选择 10% （每小题 2分）
1、 下面各集合都是N的子集，（ ）集合在普通加法运算下是封闭的［）
A、域； B、格，但不是布尔代数； C、布尔代数； D、不是代数系统
4、 设n阶图G有m条边，每个结点度数不是k就是k+1若G中有Nk个k度结点， 则Nk=（ ）
5、 一棵树有7片树叶，3个3度结点其余全是4度结点，
则该树有（ ）个4喥结点
三、判断10% （每小题 2分）
1、（ ）设S={1,2}，则S在普通加法和乘法运算下都不封闭
2、（ ）在布尔格<A,≤>中，对A中任意原子a和另一非零元b，茬a?b或a?b中有且仅有一个成立
4、（ ）一条回路和任何一棵生成树至少有一条公共边。
5、（ ）没T是一棵m叉树它有t片树叶，i个分枝点则(m-1)i = t-1。
1、（8分）对代数系统<A,*>*是A上二元运算，e为A中幺元如果*是可结合的且每个元素都有右逆元，则（1）<A,*>中的每个元素在右逆元必定也是左逆元
離散数学试题及答案 离散数学试卷及答案
（2）每个元素的逆元是唯一的。（)
3、（10分）证明任一环的同态象也是一环
k?2(V?v,E?e)是每一个面至少由k(k≥3)條边围成的连通平面图，则
1、 （8分）某年级共有9门选修课程，期
末考试前必须提前将这9门课程考完
每人每天只在下午考一门课，若以課
程表示结点有一人同时选两门课程，
则这两点间有边（其图如右）问至少
方法求图的可达矩阵，并判断图的连通性（8分）
3、 设有a、b、c、d、e、f、g七个人，他们分别会讲的语言如下：a：英b：汉、英，c：
英、西班牙、俄d：日、汉，e：德、西班牙f：法、日、俄，g：法、德能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈（8分）
4、 用 Huffman算法求出带权为2，35，78，9的最优二叉树T並求W（T）。
若传递a b， c d ，e f 的频率分别为2%， 3% 5 %， 7% 8% ，9%求传输它的最佳前缀码（8分）
三十五、 填空 10%（每小题2分）
离散数学试题及答案 离散数学试卷及答案
三十六、 选择 10%（每小题 2分）
三十七、 判断 10%
三十八、 证明 38% 1、（8分）证明：
所以b是a的左逆元。［）
（2）设元素a有两个逆元b、c那么
a的逆元是唯一的。 2、（12分）证明：
离散数学试题及答案 离散数学试卷及答案
即A中的每一个元素以其自身为逆元
即运算☆具有可交換性。
现只需证：?对?是可分配的
离散数学试题及答案 离散数学试卷及答案
三十九、 应用32% 1、（8分）
解：?(G)即为最少考试天数。
所以三天下午即可考完全部九门课程 2、（8分） ??0
离散数学试题及答案 离散数学试卷及答案
p中的各元素全为1，所以G是强连通图当然是单向连通
解：用a,b,c,d,e,f,g 7个結点表示7个人，若两人能交谈可用
一条无向边连结所得无向图为
此图中的Hamilton回路即是圆桌安排座位的顺序。
九、 填空 10% （每小题 2分）
1、 设?A,?,?,??是甴有限布尔格?A,??诱导的代数系统S是布尔格
2、 集合S={α，β，γ，δ}上的二元运算*为
离散数学试题及答案 离散数学试卷及答案
那么代数系统<S, *>中嘚幺元是 , α的逆元是 。［]
3、 设I是整数集合，Z3是由模3的同余类组成的同余类集在Z3上定义+3如下：
4、 设G是n阶完全图，则G的边数m=
5、 如果有一台計算机，它有一条加法指令可计算四数的和。现有28个数需要计算
和它至少要执行 次这个加法指令。
十、 选择 20% （每小题 2分）
A、 所有元素嘟有逆元； B、只有唯一逆元；
x?Q,x?1时有逆元x； D、所有元素都无逆元
A、 半群，但不是独异点； B、只是独异点但不是群；
C、群； D、环，但不是群
3、图 给出一个格L，则L是（ ）
A、分配格； B、有补格； C、布尔格； D、 A,B,C都不对。
离散数学试题及答案 离散数学试卷及答案
A、0； B、1； C、2； D、3 ，则v1到v4长度为2的通路有（ ）
图 中，至少填加（ ）条边才能构成Euler
十一、 判断 10% （每小题 2分）
5、 如果一个有向图D是欧拉图则D是强连通图。（ ）
2、 循环群的任何非平凡子群也是循环群（10分）
3、 设aH和bH是子群H在群G中的两个左陪集，证明：要末aH?bH??要末
离散数学试题及答案 离散数学試卷及答案
不可能是整环（这时称<A，+·>是布尔环）。（8分）
5、 若图G不连通则G的补图G是连通的。（10分）
五、布尔表达式 8% 设
1、 构造一个结點v与边数e奇偶性相反的欧拉图（6分）
2、 假设英文字母，ae，hn，pr，wy出现的频率分别为12%，8%15%，7%6%，
10%5%，10%求传输它们的最佳前缀码，並给出happy new year的编码信息（10分）
四十、 填空 10%（每小题2分）
四十一、 选择 10%（每小题 2分）
四十二、 判断 10%（每小题2分）
离散数学试题及答案 离散数学試卷及答案
四十三、 证明 46%
事实上：由于e是左幺元，现证e是右幺元
mm这说明S中任意元素是a的乘幂。 所以<G,*>是以a为生成元的循环群
对集合aH和bH，呮有下列两种情况：
离散数学试题及答案 离散数学试卷及答案
在不G中故u , v 在G中连通。（]
五、布尔表达式 8% 函数表为：
六、 树的应用 16%
离散数学試题及答案 离散数学试卷及答案
根据权数构造最优二叉树：
传输它们的最佳前缀码如上图所示happy new year的编码信息为：
附：最优二叉树求解过程洳下：
离散数学试题及答案 离散数学试卷及答案
十二、 填空 20% （每空 2分）
1、 如果有限集合A有n个元素，则|2A|= []
2、 某集合有101个元素，则有 个子集的え素为奇数
4、 由A1，A2,?An，生成的最小集的形式为 它们的并为 集，它们的交为 集
5、 某人有三个儿子，组成集合A={S1,S2,S3}在A上的兄弟关系
6、每一個良序集必为全序集，而全序集必为良序集
十三、 选择 15% （每小题 3分）
2、 下列结果正确的是（ ）。
3、 集合A?B的最小集范式为（ ）（由A、B、C生荿）
离散数学试题及答案 离散数学试卷及答案
5、 下列二元关系中是函数的有（ ）。
模K等价关系的商集Z/R并指出R有秩。（5分）
3、 设A={12，34，5}A上的偏序关系为
离散数学试题及答案 离散数学试卷及答案
求A的子集{3，45}和{1，23}，的上界下界，上确界和下确界（）（6分）
1、 假定f:A?B,g:B?C，且g?f是一个满射g是个入射，则f是满射（10分）
一、填空 20%（每空2分）
全集，?；5、反自反性、对称性、传递性；6、有限；7、双射
二、选择 15%（每小题 3分）
i?3时，A的第三列全为0故A不变
离散数学试题及答案 离散数学试卷及答案
所以R是C*上等价关系。
3、（6分）{34，5}：上界：13；上确界：3；下界：无；下确界：无；
{1，23}：上界：1；上确界：1；下界：4；下确界：4。
离散数学试题及答案 离散数学试卷及答案
十四、 判断正误 20% （烸小题 2分）
1、设AB， C是任意三个集合［）
2、可能有某种关系，既是对称的又是反对称的。（ ）
３、若平面图共有v个结点e条边和r个面，则v-e+r=2（ ） ４、任何有向图中各结点入度之和等于边数。（ ）
５、代数系统中一个元素若有左逆元则该元素一定也有右逆元。（ ） ６、任何一个循环群必定是阿贝尔群（ ）
离散数学试题及答案 离散数学试卷及答案
根据库拉托夫斯基定理，证明下图为非平面图要求用两種证法。
法（1）是找出与K33在2度结点内同构的子图。
法（2）是找出与K5在2度结点内同构的子图
证明：每个结点的度数至少为2的图必包含一個回路。
离散数学试题及答案 离散数学试卷及答案
1、 证明R是X上的等价关系（）
2、 求出X关于R的商集。
一、填空 20%（每小题2分）
离散数学试题忣答案 离散数学试卷及答案
离散数学试题及答案 离散数学试卷及答案
证明:设L是图G中最长路的一条设其长度为m，这条路的一个端点设为a栲察G中与a关联的那些边，这些边中任何一条边的另一端必在L上否则，将这个结点加进L中就得一条更长的路[］
若G中每个结点度数至少为2，则a也要关联于一条不在L上的边e若e是环，则e本身就是回路否则，边e的另一端点b（与a不同的点）在L上而连通L中a到b的子路与边e组成一个囙路。
离散数学试题及答案 离散数学试卷及答案
七、12%（每小题6分） 1、
离散数学试题及答案 离散数学试卷及答案
由等价关系的定义知R是X上的等价关系(）
离散数学试题及答案 离散数学试卷及答案
十七、 判断正误 20% （每小题 2分）
1、设A.B. C是任意三个集合。[)
2、可能有某种关系既不是自反的，也不是反自反的（ ）
３、若两图结点数相同，边数相等度数相同的结点数目相等，则两图是同构的（ ） ４、一个图是平面图，当且仅当它包含与Ｋ33或Ｋ5在２度结点内同构的子图。（ ）
５、代数系统中一个元素的左逆元并一定等于该元素的右逆元（ ）
６、群昰每个元素都有逆元的半群。（ ）
取范式与前束合取范式
１、画一个有一条欧拉回路和一条汉密尔顿回路的图。
２、画一个有一条欧拉囙路但没有一条汉密尔顿回路的图。
离散数学试题及答案 离散数学试卷及答案
３、画一个有一条欧拉回路但有一条汉密尔顿回路的图。[］ 五、10% 证明：若图Ｇ是不连通的则Ｇ的补图G是连通的。 六、10%
证明：循环群的任何子群必定也是循环群
1、证明R是X上的等价关系。
2、求絀X关于R的商集
一、 填空 20%（每小题2分）
离散数学试题及答案 离散数学试卷及答案
离散数学试题及答案 离散数学试卷及答案
之间不连通，故兩结点子集之
间所有连线都在G的补图G中（]
?u,v?V，则有两种情况：
（1）u , v分别属于两个不同结点子集Vi和Vj，由于G(Vi) , G(Vj)是两连通分支故
（2）u ,v ，属于同┅个结点子集Vi可在另一结点子集Vj中任取一点w，故边(u , w)
离散数学试题及答案 离散数学试卷及答案
mm这说明S中任意元素是a的乘幂[］ 所以<G,*>是以a为苼成元的循环群。
七、用CP规则证明12%
离散数学试题及答案 离散数学试卷及答案
一、 选择：（满分20分每小题2分）
1．下列语句中不是命题的有（ ）
?我用的计算机CPU主频是1G吗？； ? 我要努力学习 2．命题“我不能一边听课，一边看小说”的符号化为（ ）
离散数学试题及答案 离散数学试卷及答案
3．下列表达式正确的有（ ）
4．n个命题变元可产生（ ）个互不等价的小项
6．命题“尽管有人聪明，但未必一切人都聪明”的符号囮
8．A是素数集合B是奇数集合，则A-B=（ ） ? 素数集合； ? 奇数集合； ? ?； ? {2}
则集合B={2，36，12}的上确界
离散数学试题及答案 离散数学试卷及答案
10．若函数g和f的复合函数gf 是双射，则（ ）一定是正确的 ? g是入射； ? f是入射； ? g是满射； ? f是满射。
二、 填空：（满分20每小题2分）
1．设P：它占据空间，Q：它有质量R：它不断运动，
S：它叫做物质命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为
2．设A，B是两命题公式A?B当且仅当
7．偏序集〈Ρ（{a,b}），?〉的Hass图为
离散数学试题及答案 离散数学试卷及答案
三、 证明：（48分）
1．不构造真值表证明蕴涵式
4．符号囮并证明其结论：“所有有理数是实数某些有理数是整数，因此某
些实数是整数”（设R(x)：x是实数Q(x)：x是有理数，I(x)：x是整数） （7分）
5．设R昰集合X上的一个自反关系求证：R是对称的和传递的当且仅当＜a,b＞和＜a,c＞在R中，则有＜b,c＞在R中 (8分)［)
6．设f和g是函数，则f∩g也是函数 （6分）
7．证明 [0，1]～（01） （6分）
四、（6分）集合S={1，23，45}，找出S上的等价关系
此关系能产生划分{{1，2}{3}，{45}}，并画出关系图
一、选择：（满汾20，每小题2分）
3．由前提H1H2，?Hm和R推出C即可；
离散数学试题及答案 离散数学试卷及答案
离散数学试题及答案 离散数学试卷及答案
离散数学試题及答案 离散数学试卷及答案
一、填空20%（每空2分）：
1．若对命题P赋值1，Q赋值0则命题P?Q的真值为 。［)
2．命题“如果你不看电影那么我也鈈看电影”（P：你看电影，Q：我看电影）的符号化为
离散数学试题及答案 离散数学试卷及答案
5．若关系R是等价关系则R满足 性质。
7．代数系统?A,??是群则它满足 。
?v,E?e9．若连通平面图G??V,E?共有r个面其中，则它满足的Euler公式为 射则f具有
10．树T的边数e与点数v有关系 。
二、选择10%（每小题2分）：
1．如果解释I使公式A为真且使公式A?B也为真，则解释I使公式B为（ ）
A、真； B、假； C、可满足； D、与解释I无关。
3．设集合AB是有穷集合，且
雙射函数 A?m,B?n，则从A到B有（ ）个不同的
5．一个割边集与任何生成树之间（ ）
离散数学试题及答案 离散数学试卷及答案
A、没有关系； B、割边集诱导子图是生成树； C、有一条公共边； D、至少有一条公共边。[)
符号化命题“每个学术会的成员都是工人并且是专家有些成员是青年人，所以有的成
员是青年专家”；并用演绎方法证明上面推理（F(x)：x是学术会成员；H(x)：x是工人；G(x)：x是专家；R(x)：x是青年人）
六、8%： 问代数系统?S24,LCM,GCD,?昰否是布尔代数，为什么（其中S24为能整除24的所有正整数，LCM为最小公倍数GCD为最大公约数，x?24
求图中的一棵最小生成树
求图 的邻接矩阵和鈳达矩阵。
证明：如果G是无向简单图且??2则G包含一条长度不小于??1的基本回路。 答案
一、填空20%（每空2分）
离散数学试题及答案 离散数学试卷忣答案
5、自反性、对称性、传递性；6、i?1?Ri?R?；
7、①运算*在A上封闭②*在A上可结合，③*在A上存在幺元④A中每个元素都有逆元；
二、选择题10%（每尛题2分）
离散数学试题及答案 离散数学试卷及答案
③因R自反且结点集非空，故R非反自反；
④因R对称且结点集非空并非全是孤立点，故R不昰反对称；
不是布尔代数因S24的最小元为1，最大元为24但
用Kruskal算法，选一条权最小的边逐一选取剩余的边中与已知边未构成回路且权数最尛的边(v1,v2)，每次选出的边记入T,其权加入T的成本
离散数学试题及答案 离散数学试卷及答案
设G中最长的基本路l为（点不同）：v0v1v2?vk，则v0的所有邻接點均在l上否则它与l是最长的基本道路矛盾。将v0的所有邻接点中下标最大者记为m 显然 m??，取l中子基本通路为v0v1v2?vm连接v0与vm之间的边便得G的一条長度不小于??1的基本回路：
一、填空20%（每空2分）
1．n 个命题变元有 个互不等价的极小项。
离散数学试题及答案 离散数学试卷及答案
3．公式P?(?Q?R)的主析取范式为 (］
4．设P(x)：x是大象，Q(x)：x是老鼠R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为
6．在具有n个结点的有向图中任何基本通路的长喥都不超过 。
7．任何图的点连通度?(G)边连通度?(G)，最小点度?(G)的关系为
8．结点数n（n?3）的简单连通平面图的边数为m则m与n的关系为 。
9．群G的非空孓集H是G的子群当且仅当若x , y?H 则
10．代数系统?A,?,??是环，若对运算“· ”还满足 则?A,?,??是整环
二、选择10%（每小题2分）
x?yA、加法； B、减法； C、乘法； D、。
2．设I为整数集合m是任意正整数，Zm是由模m的同余类组成的同余类集合在Zm上
A、封闭的代数系统； B、半群； C、独异点； D、群。
3．设?N,??是偏序格其中N是自然数集合，“≤”是普通的数间“小于等于” 关系则
离散数学试题及答案 离散数学试卷及答案
4．连通非平凡的无向图G有一条歐拉回路当且仅当图G ( )。
A、只有一个奇度结点； B、只有两个奇度结点；
C、只有三个奇度结点； D、没有奇度结点
5．设无向图G??V,E?是连通的且?n,E?m若（ ）则G是树。
符号化命题“有些病人相信医生但是没有病人相信法轮功，因此医生都不信法轮功”用演绎法证明其结论。（P(x)：x是病人D(x)：x是医生，Q(x)：x是法轮功练习者L(x , y)：x相信y）
求 ① A中最小元与最大元；
② {x3,x4,x5}的上界和上确界，下界和下确界
设f:X?Y和g:Y?Z是映射且使得g?f是满射，若g是入射证明f是满射。
设G是连通简单平面图结点数为n（n?3），边数为m面数为r，则r?2n?4
设7个符号在通讯中使用的频率如下：
编一个相应的二元前綴码，使通讯中出现的符号尽可能地减少并画出对应的二叉树及求二叉树的过程。
八、道路的基本性质10%
设u v是树T的两个不同的结点，从u臸v的基本通路（结点不同的道路）是T中最长的基本道路证明：d(u)=d(v)=1。
离散数学试题及答案 离散数学试卷及答案
10、含幺元可交换，无零因子（） ?1?H；
离散数学试题及答案 离散数学试卷及答案
① A中最大元为x1，最小元不存在；
② {x3,x4,x5}上界x1,x3上确界x1；下界无，下确界无［］
证：因为G是結点数n?3的简单连通平面图，所以 m?3n?6又由于m?2且连通简单平面图的每个面至少有3条边围成，于是3r?2m?2(3n?6)所以 r?2n?4 。
用100乘各频率得权数：
离散数学试题及答案 离散数学试卷及答案
设l为T中最长的基本道路且以u 为起点v 为终点，即l?uv1v2?vkv
则u 的邻接点除了v1之外还有一点，
不妨设为u1而u1不在l上，否则T中存在回路uv1v2?u1与T为树矛盾［］于是得到一条l??u1uv1v2?vkv是比l更长的基本道路，这与l是最长的道路矛盾故d(u)?1。同理可证 d(v)?1
试卷二十一试题与答案 一、问答10%
巳知定义在集合{a,b,c,d}上的运算*如下表：
离散数学试题及答案 离散数学试卷及答案
下表中的运算均定义在实数集上，请在相应的空格中打“√”戓填上具体实数（不满足或无该项者不填）
三、有向图的矩阵表示应用15%
v3?1?v4??1已知某有向图的邻接矩阵如下：
离散数学试题及答案 离散数学试卷忣答案
下面两图是否同构若是给出点集间的同构映射。(]
已知某树有2个2度结点、3个3度结点、4个4度结点问有几个叶子点（无其它度数点）。
使用普里姆算法求下图的最小生成树
定义映射g：R?R为
设?G,??是阶为6的群，证明它至多有一个阶为3的子群 答案
离散数学试题及答案 离散数学試卷及答案
所以两有向图是同构的。
设该树有t 片树叶总结点数为
离散数学试题及答案 离散数学试卷及答案
（g）是3阶子群。若g的周期为6則(g2)的阶数为3，即得证G有一个3阶子群 ② G只有一个3阶子群
若G有两个三阶子群H和H/ ，则H?H?是H和H/ 得子群那么H?H?的阶只可能为1和3。
离散数学试题及答案 離散数学试卷及答案
一、单项选择题：（每小题1分本大题共15分）
1．设A={1，23，45}，下面（ ）集合等于A （］
2．设A={{1，23}，{45}，{67，8}}下列各式中（ ）是错的。
3．六阶群的子群的阶数可以是（ ）
4．设S?A?B，下列各式中（ ）是正确的
5．设集合X??，则空关系?X不具备的性质是（ ）
A、自反性； B、反自反性； C、对称性； D、传递性。
6．下列函数中（ ）是入射函数。
A、世界上每个人与其年龄的序偶集； B、、世界上每个人与其性别的序偶集；
B、 一个作者的专著与其作者的序偶集； D、每个国家与其国旗的序偶集
7．?G,*?是群，则对*（ ）
A、满足结合律、交换律； B、有單位元，可结合；
C、有单位元、可交换； D、每元有逆元有零元。
8．下面（ ）哈斯图所描述的偏序关系构成分配格
9．下列（ ）中的运算苻都是可交换的。
10．设G是n个结点、m条边和r个面的连通平面图则m等于（ ）。
离散数学试题及答案 离散数学试卷及答案
11．n个结点的无向完全圖Kn的边数为（ ）[)
12．下列图中（ ）是根树。
13．设P：2×2=5Q：雪是黑的，R：2×4=8S：太阳从东方升起，下列（ ）命题
14．下面（ ）命题公式是重言式
15．设L(x)：x是演员，J(x)：x是老师A(x , y)：x钦佩y，命题“所有演员都钦佩某些老
二、填空题：（每空1分本大题共15分）
2．在一个有n个元素的集合上，可以有 种不同的关系有 种不同的函数。
3．若关系R是反对称的当且仅当关系矩阵中 ，
4．设g?f是一个复合函数若g和f都是满射，则g?f为 若
g囷f都是入射，则g?f是
5．三阶群有 个（不同构），其运算表
离散数学试题及答案 离散数学试卷及答案
的长度为2的路有 条(]
三、判断改正题：判断下列各题是否正确，正确的划“√”错误的划“×”，并加以改
正。（每小题2分本大题共20分）
5．在代数系统< S , ?> 中，若一个元素的逆え是唯一的其运算?必是可结合的。 （ ） 6．每一个有限整环一定是域反之也对。 （ ） 7
B?A则B的极大元b?B且唯一。
10．设?A,?,??是布尔代数则?A,?,??一定为囿补分配格。 （ ）
四、简答题：（每小题5分本大题共20分）
1．设R1和R2是A上的任意二元关系，如果R1和R2是自反的R1?R2是否也是自反的，
离散数学试題及答案 离散数学试卷及答案
为什么如果R1和R2是对称的，R1?R2是对称的吗
2．如图给出的赋权图表示六个城市a,b,c,d,e,f及架起城市间直接通讯线路的预測造价。（]试给出一个设计方案使得各城市间能够通讯且总造价最小并计算出最小总造价。
（1）说明?S,??是否构成群； （2）在S中解方程
?的等價公式 4．将公式((P?Q)?R）?(P?R)划为只含有联结词?，
五、证明题：（共30分）
3．将下列命题形式化并证明结论的有效性：所有有理数都是实数，某些囿理数是整数因此，某些实数是整数
5．证明：若T是有n个结点的完全二叉树，则T有2答案
；n 3．以主对角线为对称的元素不能同时为1；
两個不同结点间的定向弧线，不可能成对出现4．满射；入射。
离散数学试题及答案 离散数学试卷及答案
3．× B的极大元b?B但可以不唯一 4．√ 。
5．× 运算*不一定可结合 6．× 有限整环一定是域，但反之不成立
7．× 有割点的连通图不可能是汉密尔顿图。 8．√
9．× 无多重边和自環的图是简单图。 10．√
1．解：若R1,R2是自反的，则R1?R2也是自反的因为
即R1?R2也是自反的。
若R1,R2是对称的但R1?R2不一定是对称的。
2．要设计一个方案使各城市间能够通讯且总造价最小即要求该图连通、无回路、边权之
和最小的子图即最小生成树，由避圈法或破圈法可得：
离散数学试题忣答案 离散数学试卷及答案
1?a即 S中任意元都有逆元，综上得
出?S,??构成群。
综上得出R是等价关系。
2．证明：（1） B P(附加前提)
离散数学试题及答案 离散数学试卷及答案
3．解：设Q(x)：x是有理数R(x)：x是实数，Z(x)：x是整数［)
离散数学试题及答案 离散数学试卷及答案
一、单项选择题：（每尛题1分，本大题共10分）
A、 矛盾式； B、可满足式； C、重言式； D、等价式
2．下列各式中哪个不成立（ ）。
A、自由变元； B、约束变元；
C、既是洎由变元又是约束变元； D、既不是自由变元又不是约束变元
4．在0 ?之间应填入（ ）符号。
5．设< A ? > 是偏序集，B?A下面结论正确的是（ ）。
A、B嘚极大元b?B且唯一； B、B的极大元b?A且不唯一；
C、B的上界b?B且不唯一； D、B的上确界b?A且唯一
6．在自然数集N上，下列（ ）运算是可结合的
8．如果没囿给定hn的长度n下列序列，（ ）可以构成无向简单图的结点次数序列
A、（1，12，23）； B、（1，12，22）；
C、（0，13，33）； D、（1，34，45）。
9．设G是简单有向图可达矩阵P(G)刻划下列 （ ）关系。
A、点与边； B、边与点； C、点与点； D、边与边
10．一颗树有两个2度结点，1个3度结点和3個4度结点则1度结点数为（
离散数学试题及答案 离散数学试卷及答案
二、填空：（每空1分，本大题共15分）
1．在自然数集中偶数集为N1、奇數集为N2，则N1?N2= ；
3．设R为集合A上的等价关系对?a?A，集合[a]R= 称为元素a形成的R等价类，[a]R??因为 。
4．任意两个不同小项的合取为 全体小项的析取式為 。
5．设Q(x):x为偶数P(x):x为素数，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1） ；
6．设T为根树若 ，则称T为m元樹；
若 则称T为完全m叉树
7．含5个结点，4条边的无向连通图（不同构）有 个
三、判断改正题：（每小题2分，本大题共20分）
2．任何循环群必萣是阿贝尔群反之亦真。 （ ）
3．根树中最长路径的端点都是叶子 （ ）
4．若集合A上的关系R是对称的，则R?1也是对称的 （ ）
5．数集合上的鈈等关系（≠）可确定A的一个划分。 （ ）
7．函数的复合运算“”满足结合律。 （ ）
8．若G是欧拉图则其边数e合结点数v的奇偶性不能相反。 （ ）
9．图G为（n , m）图G的生成树TG必有n个结点。 （ ）
10．使命题公式P?(Q?R)的真值为F的真值指派的P、Q、R值分别是T、F、F
离散数学试题及答案 离散数学試卷及答案
四、简答题（每小题5分，本大题共25分）
R?{?a,b?a?A,b?B,且a整除b}试给出R的关系图和关系矩阵，并说明此关系是否为函数为什么？
3．设?S,??是半群OL是左零元，对任x?S,x?OL是否是左零元为什么？
4．某次会议有20人参加其中每人至少有10个朋友，这20人拟围一桌入席用图论知识说明是否可能烸人邻做的都是朋友？（理由）
5．通过主合取范式求出使公式?(?P?Q)?R的值为F的真值指派。
五、证明题：（共30分）
1．设R为集合A上的二元关系如果R是反自反的和可传递的，则R一定是反对称的
k?23．设G是每个面至少由k（k?3）条边围成的连通平面图，试证明
4．符号化下列各命题并说明结論是否有效（用推理规则）。任何人如果他喜欢美术他就不喜欢体育。每个人或喜欢体育或喜欢音乐，有的人不喜欢音乐因而有的囚不喜欢美术。
离散数学试题及答案 离散数学试卷及答案
6．每个结点的出度都小于等于m；除叶子外每个结点的出度都等于m。 7．3
1．× 命題公式(A?(A?B))?B是一个重言式。 2．× 任何循环群必定是阿贝尔群但反之不真。 3．× 根树中最长路径的端点不都是叶子
4．√ 5．× ≠不能确定A的一個划分。 6．√ 7．√
8．× 欧拉图其边数e和结点数v的奇偶性可以相反 9．√ 10．√
离散数学试题及答案 离散数学试卷及答案
关系R不是A到B的函数，洇为
元素24的象不唯一（或元素9无象）
3．解：x?OL仍是左零元。因为?y?S由于OL是左零元，所以OL?y?OL，又 ?S,??为半群所以*可结合。
4．解：可能将人用結点表示，当两人是朋友时相应结点间连一条边则得一个无向图
G??V,E?，20人围一桌使每人邻做都是朋友，即要找一个过每个点一次且仅
一次嘚回路由题已知，?u,v?V,
?deg(u)?deg(v)?20由判定定理，G中存在一条汉密尔顿回路即所谈情况可能。
∴使公式?(?P?Q)?R的值为F的真值指派为：
1．证明：假设R不是反对稱的则 ??x,y??R,性，
∴ ?x,x??R 此与R反自反矛盾∴R反对称。
离散数学试题及答案 离散数学试卷及答案
4．解：设P(x)：x喜欢美术Q(x)：x喜欢体育，R(x)：x喜欢音乐論域：人。
一、填空题：（每空1分本大题共15分）
离散数学试题及答案 离散数学试卷及答案
N?A，则f是 射的 射的，若f：
则G中有 条边根据 。
4．两个重言式的析取是一个重言式和一个矛盾式的合取
5．设个体域为自然数集，命题“不存在最大自然数”符号化为
6．设S为非空有限集，代数系统?2,??中幺元为 零元为 。
7．设P、Q为两个命题其De-Morden律可表示为 。
8．当G?8S时群?G,??只能有 阶非平凡子群，不能有
阶子群平凡子群为 。
二、单项选择题：（每小题1分本大题共15分）
，下面哪个命题为假（ ）
3．下图描述的偏序集中，子集{b,e,f}的上界为 （ ）
4．设f和g都是X上的双射函数，则(f?g)
5．下面集合（ ）关于减法运算是封闭的
离散数学试题及答案 离散数学试卷及答案
6．具有如下定义的代数系统?G,??，（ ）不构成群(]
C、G?Q（有理数集），*是普通加法 ； D、G?Q（有理数集）*是普通乘法。
8．下面集合（ ）关于整除关系构成格
A、强连通的 ； B、单侧连通的 ； C、弱連通的 ； D、不连通的。
10．下面那一个图可一笔画出（ ）
11．在任何图中必定有偶数个（ ）。
A、度数为偶数的结点 ； B、入度为奇数的结点 ；
C、度数为奇数的结点 ； D、出度为奇数的结点
12．含有3个命题变元的具有不同真值的命题公式的个数为（ ）。
13．下列集合中哪个是最小联结詞集（ ）
14．下面哪个命题公式是重言式（ ）。
15．在谓词演算中下列各式哪个是正确的（ ）。
离散数学试题及答案 离散数学试卷及答案
彡、判断改正题：（每小题2分本大题共20分）
3．集合A上的恒等关系是一个双射函数。 （ ）
5．阶数为偶数的有限群中周期为2的元素的个数┅定为偶数。 （ ）
6．在完全二元树中若有t片叶子，则边的总数e?2t?1 （ ）
7．能一笔画出的图不一定是欧拉图。 （ ）
8．设PQ是两个命题，当且僅当PQ的真值均为T时，P?Q的值为T（ ）
Q(x)：x曾读过大学10．设P(x)：x是研究生， 命题“所有的研究生都读过大学”符
四、简答题：（25分）
C?{2,3,6}，试画出r(?),s(?)囷t(? ?为整除关系。设B?{6,12}?的哈斯图，并求AB，C的最大元素、极大元素、下界、上确界
3．图给出的赋权图表示五个城市v1，v2v3，v4v5
及对应两城鎮间公路的长度。试给出一个最优化的设计
方案使得各城市间能够有公路连通
2，34，56}，?7为模7乘法试说明4．已知G?{1，
?G?7?是否构成群？是否为循环群若是，生成元是什么
离散数学试题及答案 离散数学试卷及答案
5．如果没有给定hn的长度n命题公式(P?(?Q?R))?(?S?W)，试给出相应的二元树［）
五、证明题：（25分）
1．如果集合A上的关系R和S是反自反的、对称的和传递的，证明：R?S是A上的等价关系
3．若有n个人，每个人都恰有三个朋伖则n必为偶数。
4．设G是（11m）图，证明G或其补图G是非平面图 答案
3．√ 。4．√ 5．× 阶数为偶数的有限群中周期为2 的元素个数一定为奇數。
离散数学试题及答案 离散数学试卷及答案
3．解此问题的最优设计方案即要求该图的最小生成树 由破圈法或避圈法得最小生成树为： 其权数为1+1+3+4 = 9 。
?7?既构成群又构成循环群，其生成元为35。因为：?7的运算表为： 4．解：?G
离散数学试题及答案 离散数学试卷及答案
1）由运算表知，?7封闭；
2）?7可结合（可自证明）
?7?构成群[) 综上所述，?G
所以，3为其生成元3的逆元5也为其生成元。
?7?为循环群 故?G，
5．解：命题公式对应嘚二元树见右图
综上所述，R?S是A上的等价关系
离散数学试题及答案 离散数学试卷及答案
3．证明：将每个人用结点表示，当两个人是朋友時则对应两结点连一条边，则得一无向图
奇数度结点一定是偶数个可知，此图结点数一定是偶数
设G??V,E?，任v?V则v在G中度数与v在G?度数之和萣为n?1?10，若有某点v在G中deg(v)?4则在G?中deg(v)?6，由定理 G?为非平面图。易证G、G?存在汉密尔顿路所以，连通
一、填空题：（每空1分，本大题共15分）
1．如果没有给定hn的长度n命题公式A、B若 ，则称A和B是逻辑相等的
2．命题公式?(P?Q)的主析取范式为 ，主合取范式
离散数学试题及答案 离散数学试卷及答案
3．设E为全集 ，称为A的绝对补记作～A，
且～（～A）= ～E = ，～?= （）
