离散数学考试试题（共8篇）
一、【单项选择题】
(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。
1、在由3个元素组成的集合上，可以有()种不同的关系。
[A] 3 [B] 8 [C]9 [D]272、设A1,2,3,5,8,B1,2,5,7,则AB()。
[A] 3,8 [B]3 [C]8 [D]3,83、若X是Y的子集，则一定有()。
[A]X不属于Y [B]X∈Y
[C]X真包含于 Y [D]X∩Y=X4、下列关系中是等价关系的是()。
[A]不等关系 [B]空关系
[C]全关系 [D]偏序关系
5、对于一个从集合A到集合B的映射，下列表述中错误的是()。
[A]对A的每个元素都要有象 [B] 对A的每个元素都只有一个象
[C]对B的每个元素都有原象 [D] 对B的元素可以有不止一个原象
6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为()。
[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、设A={a,b,c},则A到A的双射共有()。
[A]3个 [B]6个 [C]8个 [D]9个
8、一个连通G具有以下何种条件时，能一笔画出：即从某结点出发，经过中每边仅一次回到该结点()。
[A] G没有奇数度结点 [B] G有1个奇数度结点
[C] G有2个奇数度结点 [D] G没有或有2个奇数度结点
9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是()。
[A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元
10、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为()
[A] p→┐q [B] p∨┐q
[C] p∧q [D] p∧┐q11、设G=的结点集为V={v1,v2,v3},边集为E={,}.则G的割(点)集是()。
[A]{v1} [B]{v2} [C]{v3} [D]{v2,v3}
12、下面4个推理定律中，不正确的为()。
[A]A=>(A∨B)(附加律)[B](A∨B)∧┐A=>B(析取三段论)
[C](A→B)∧A=>B(假言推理)[D](A→B)∧┐B=>A(拒取式)
13、在右边中过v1,v2的初级回路有多少条()
[A] 1 [B] 2 [C] 3 [D]
414、若R，是环，且R中乘法适合消去律，则R是()。
[A]无零因子环
[C]整环 [B]除环 [D]域
15、无向G中有16条边，且每个结点的度数均为2，则结点数是()。
[A]8 [B]16 [C]4 [D]
32二、【判断题】
(本大题共8小题，每小题3分，共24分)正确的填T，错误的填F，填在答题卷相应题号处。
16、是空集。()
17、设S,T为任意集合，如果S—T=，则S=T。()
18、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。()
19、关系的复合运算满足交换律。()
20、集合A上任一运算对A是封闭的。()
21、0,1,2,3,4,max,min是格。()
22、强连通有向一定是单向连通的。()
23、设都是命题公式，则(PQ)QP。()
三、【解答题】
(本大题共3小题，24、25每小题10分，26小题11分，共31分)请将答案填写在答题卷相应题号处。
24、设集合A={a, b, c}，B={b, d, e}，求
(1)BA;(2)AB;(3)A-B;(4)BA.25、设非空集合A，验证(P(A)，,~，A)是布尔代数
26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。
离散数学试题答案
一、【单项选择题】(本大题共15小题，每小题3分，共45分)
BDDCCCBABDADCBB
二、【判断题】(本大题共8小题，每小题3分，共24分)
FFTFTTTF
三、【解答题】(本大题共3小题，24、25每小题10分，26小题11分，共31分)
24、设集合A={a, b, c}，B={b, d, e}，求(1)BA;(2)AB;(3)A-B;(4)BA.标准答案：(1)BA={a, b, c}{b, d, e}={ b }
(2)AB={a, b, c}{b, d, e}={a, b, c, d, e }
(3)A-B={a, b, c}-{b, d, e}={a, c}
(4)BA= AB-BA={a, b, c, d, e }-{ b }={a, c, d, e }
复习范围或考核目标：考察集合的基本运算，包括交集，并集,见课件第一章第二节,集合的运算。
25、设非空集合A，验证(P(A)，,~，A)是布尔代数
标准答案：证明 因为集合A非空，故P(A)至少有两个元素，显然，是P(A)上的二元运算.由定理10，任给B,C,DP(A), H1 BD=DC CD=DC
H2 B(CD)=(BC)(BD)B(CD)=(BC)(BD)
H3 P(A)存在和A，BP(A), 有B=B，BA=B
H4，BP(A), BA，存在A~B，有
BA~B)= A B(A～B)=
所以(P(A)，,~，A)是布尔代数.复习范围或考核目标：考察布尔代数的基本概念，集合的运算，见课件代数系统中布尔代数小节。
26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。
标准答案：令p：他是计算机系本科生
q：他是计算机系研究生 r：他学过DELPHI语言
s:他学过C++语言
t:他会编程序
前提：(p∨q)→(r∧s),(r∨s)→t
结论：p→t
证①p P(附加前提)
②p∨q T①I
③(p∨q)→(r∧s)P(前提引入)
④r∧s T②③I
⑤r T④I
⑥r∨s T⑤I
⑦(r∨s)→t P(前提引入)
关键词：离散数学,兴趣,课堂教学
离散数学课程与传统的大学数学课程 (如高等数学) 有很大的区别, 高等数学研究的一般是自变量在区间上连续变化的函数, 而离散数学是研究离散变量及其相互关系的学科, 如自然数、真假值等等。这门课程是随着计算机的发展而产生的 (机器语言只有0、1两个离散值) , 因此开设这门课程的专业都是与计算机关系密切的专业, 如信息与计算科学、计算机科学与技术、信息管理、电子商务、物联网等。
众所周知, 高等数学有大家公认的经典和传统的教材, 即使版本不同, 内容也大同小异, 而离散数学一般是学校根据自己专业的培养目标和方向自行定制教材, 内容的侧重点也不尽相同, 但无论哪一种教材, 都会包括四部分内容:数理逻辑、集合论、代数系统和图论, 这其实是数学专业需要分开学习的四门课程, 相对比较枯燥, 离散数学教材将这些放在一起, 每一部分都介绍了与计算机技术相关的内容, 不像数学专业学的深入, 但涉及的面很广, 对学生而言非常困难。和高等数学比较, 由于学生从中学开始就接触函数, 因此高等数学课程的入门相对容易, 课程前后的内容联系紧密, 开始学习时学生感觉不会太困难。但离散数学不同, 学生以前基本没有接触过相关的知识, 并且内容前后之间又没有必然的联系 (充分体现了离散性) , 学习后面的经常忘记前面的, 这就给学生的学习制造了很多的麻烦, 他们普遍认为离散数学不好学, 甚至有个别学生最后只能放弃。俗话说, 兴趣是最好的老师, 鉴于以上这些原因, 本文根据这四部分内容, 谈谈如何在课堂教学中提高学生的学习兴趣。
1 数理逻辑之趣
逻辑学简单地讲, 就是研究推理的学科, 数理逻辑也不例外, 它是运用一套符号体系加上一些规则, 研究我们生活中的一切与推理有关的问题, 这不就让课堂生动起来了吗?比如生活中有这样的叙述:“情况并非如此, 如果他不来, 那么我也不去。”这句话如果说给外国人听, 他们一定会觉得云山雾罩的, 即便是中国人自己, 能够理解清楚也不是很容易吧, 到底是他来或不来, 我去还是不去呢?现在我们用数理逻辑的理论去研究, 看看到底说的什么意思?设P表示“他来”, Q表示“我去”, 这句话翻译成逻辑语言是:┐ (┐P→┐Q) , 利用推理规则得到与之等价的命题┐P∧Q, 再将其还原回生活语言就是“他没来, 但我去了”, 如此之简单, 学生恍然大悟, 马上会兴趣倍增的。再有, 课堂上如果让学生分析下面这段程序, 结果会怎样呢?“If A then if B then X else Y else if B then X else Y”, 就是对计算机专业的学生而言, 理解程序的条件和结论也不容易吧, 但程序肯定是正确的, 计算机也是可以执行的, 现在让我们用数理逻辑理论化简一下吧。执行X的条件: (A∧B) ∨ (┐A∧B) , 化简后等价于B;执行Y的条件: (A∧┐B) ∨ (┐A∧┐B) , 化简后等价于┐B, 结果出乎人们的意料, A在程序中根本没起作用, 纯属捣乱而已, 此程序实际可以简化为:“If B then X else Y”。如此好玩的问题, 与日常生活和学生的专业又有密切的联系, 我们可以想象一下, 学生学习起来会多么高兴, 又怎么会在课堂上睡觉呢?
2 集合关系之趣
在生活中, 存在着各式各样的关系, 如父子关系、夫妻关系、朋友关系、上下级关系等等, 这些关系看起来各不相同, 但很多关系却可以用数学思想抽象出它们共同的性质。离散数学集合论部分涉及到的就是研究各种各样的关系, 如等价关系、序关系等等, 研究这些关系, 也是非常有趣的事情。比如利用“同姓”关系, 可以将人群分类:{张}、{王}、{李}、{欧阳}、{诸葛}……等等, 如果要研究同一姓氏的人有什么共同特征时, 可以分别从不同的姓氏集合中, 任取一个人进行研究, 这个人可以作为每一类姓氏人群的代表, 他有的特征和他同类的人都有;再比如平常说的“家族”关系, 可以理解为集合中的复合关系, 如果R是“父子”关系, S是“兄弟”关系, 那么R○R表示“祖孙”关系、S○R表示“伯侄”关系等等, 只要将条件设计好, 红楼梦中的林黛玉和王熙凤之间的关系也可以用数学语言表示出来。事实上, 生活中的所有关系都是可以用数学符号描绘出来的, 这方面可以引导学生自己去探索, 以便提高他们的学习兴趣。
3 代数系统之趣
代数系统是离散数学中最抽象的一部分, 它在数学学科中属于抽象代数的内容, 怎样用生活中有趣的例子解释、描述抽象的概念, 是课堂教学需要认真研究的问题之一。事实上, 在集合中定义运算, 是构成代数系统的关键, 而运算就是函数, 比如一台自动售货机, 它接受人民币, 吐出各种商品, “两个一元对应一瓶橙汁, 一个一元和一个二元对应一瓶可乐, 两个二元对应一个冰淇淋”等等, 这就是运算, 如果再对运算要求具有封闭性, 就构成了代数系统。再如定义代数系统的幺元和零元时, 可以用“洗衣”的例子说明, 用洗衣机洗衣服时, 浅色和浅色混洗后, 衣服还是浅色;浅色和深色混洗后, 衣服变成了深色;深色和深色混洗后, 衣服还是深色, 可以令S={浅色, 深色}, “*”代表“洗衣”这种运算, 那么对于代数系统<S, *>而言, “浅色”是系统的幺元;、“深色”是系统的零元, 让学生想象浅色和深色的特征, 就可以充分理解幺元和零元的概念了。还有, 群的概念在代数系统中非常典型和重要, 不了解群就等于没有学过代数系统, 那么群到底有什么, 换句话说, 我们熟悉的什么样的事物可以是群呢?从群的概念考虑, 群中对所定义的运算要有幺元, 每一个元素还要有逆元, 假设定义的运算是“加法”, 幺元一定是0, 那么每个元素的逆元应该是其相反数, 也就是说, 它的相反数也必须是集合中的元素, 故集合必须是关于0对称的 (对加法运算) , 由此得到, 整数集合上定义加法运算构成群;实数集合上定义加法运算也构成群;但非负有理数上定义加法运算就不会构成群了, 一句话, 构成群的集合一定是对称的 (关于运算) , 这时可以提问:如果换成乘法运算, 什么样的集合对乘法运算构成群呢?这样的分析一环扣一环, 让学生跟着教师的思路去思考, 既有趣又有成就感, 而且又将概念讲解的非常到位, 学生怎么会不喜欢这样的课堂呢?
4 图论之趣
位于波罗的海海岸的美丽小城———格尼斯堡, 在图论的起源和发展中占有绝对重要的地位, 由著名的“格尼斯堡七桥”问题, 数学家欧拉创立了一个重要的数学分支———图论。“格尼斯堡七桥”问题实际是一个“一笔画”问题, 应用欧拉的理论, 对任何一个图形, 都可以很快知道它是否可以一笔画出, 这是一件多么了不起的工作啊!图论帮我们解决了很多现实问题, 如环游世界问题、匹配问题、最优化问题等等, 尤其是“树”的概念的引进, 在日常生活和计算机理论中, 应用相当的广泛。比如百姓的“家谱”就是一棵“根树”, 树根是“祖宗”, 平行边是“兄弟”, 上下相邻的两个顶点分别表示“父亲”和“儿子”, 看到一颗“家谱树”, 马上就清楚了谁是谁的“祖先”, 谁又是谁的“后裔”, 一目了然。再如“购买接线板的问题”, 寝室有28盏电灯, 要共用一个电源插座, 需要购买多少个具有四孔的接线板?这是图论中“完全四叉树求分支点”的问题, 让学生带着问题去思考, 自己解决, 既生动又实用, 何乐而不为呢?
兴趣是最好的老师, 不论一门课程多么抽象、复杂, 首先要求教师深刻地理解课程内容, 要用通俗易懂的语言讲授给学生, 同时要调动学生学习的积极性, 让学生有“我要学”的冲动, 那么这门课就一定可以学好。S
参考文献
[1]左孝凌, 等.离散数学[M].上海:上海科技文献出版社, 1982.
【关键词】离散数学 学生自主性 教学方法
【中图分类号】G642.0【文献标识码】A【文章编号】1673-8209(2010)05-0-01
离散数学课程是计算机科学与技术系各专业的一门重要的基础课程,也是计算机科学基础理论的核心课程。本课程介绍计算机科学与技术系各专业所需要的离散数学基础知识,为进一步学习计算机科学的基本理论和方法、学好专业课奠定基础,内容包括数理逻辑、集合论、代数结构与布尔代数、图论和在计算机中的应用共五部分。该课程是培养学生抽象思维能力、逻辑推理能力、缜密概括能力以及分析和解决实际问题能力的主干课程,对学习其他诸多课程,具有重要的指导作用。离散数学教学内容具有知识点多、散、抽象等特点,加之许多学生不能认识到该课程的重要性,缺乏学习兴趣和学习主动性,不仅忽视该课程的学习,甚至害怕这门课程。因此,创新教学方法,提高学生自主学习的积极性,对提高学生的能力、提升教学质量和水平,具有重要的意义。作者在离散数学教学和实践中,积累了若干经验和做法,仅供大家参考。
1 引导学生提高对离散数学课程应用性的认识,激发学生学习的兴趣和爱好,增强汲取知识的自主性
离散数学课程是一门基础性课程,由于许多学生并不能认识到离散数学课程对后续诸多主干课程的指导性作用,看不到该课程的实际应用价值,加上该课程知识比较难而且抽象,很多学生对该课程缺乏学习兴趣和学习主动性,对该门课程只是应付,甚至根本不愿意去学习。
学习离散数学课程对学生今后的学习和工作,具有重要的作用,例如,对数据结构、操作系统、数据库、编译原理、软件工程等后续课程学习的指导作用;培养学生的抽象思维能力和缜密的逻辑推理能力,并为学生今后处理离散信息,提高专业理论水平,从事计算机的实际工作提供必备的数学工具;通过学习,可以掌握数理逻辑,集合论,代数结构和图论的基本概念和原理,并会运用离散数学的方法,分析和解决计算机理论和应用中的一些问题等。学习主动性是学生的力量之源,因此,引导学生充分认识学习离散数学课程的作用,能够激发学生学习的爱好和热情,提升学生学习的积极性和主动性,从而使学生学有成效。
2 认真备课,合理准备教学内容和安排教学环节,优化教学方式方法
备好课是教学取得预期效果的前提和基础,针对学生学习具体情况,合理准备教学内容和安排教学环节,使用恰当的教学方法,在教学中可以起到事半功倍的效果。
(1)合理地准备教学内容。根据课程教学大纲和离散数学课程定理定义比较多、知识比较抽象的特点以及学生的实际情况,准备深度和广度适合学生特点的教学内容。
(2)合理地讲解课程内容,重难点突出讲解,注意轻重缓急。对于离散数学中比较重要、比较抽象的概念和定理,如逻辑的推理理论、关系的性质、群、图等,认真分析,用多种方式和方法深入讲解,可以使用解析法、图示法、矩阵法举实例等多种方法讲解,例如对关系的对称性质的讲解中,可以使用矩阵法进行讲解,判断一个关系是否对称,只需观察它的关系矩阵是否对称即可,再如对关系的传递性质的讲解中,可以使用关系图进行讲解,判断一个关系是否传递,只需观察在关系图中,当x到y有一条路径时,x与y是否有关系即可。对于比较容易理解和掌握的内容,可以一笔带过。这样,学生对所学内容就会有重点地学习,主次分明,学生不仅可以对所学内容掌握透彻,更能熟练把握离散数学中分析问题和解决问题的思路、方式和方法。
(3)启发式教学和教师讲授相结合。很多人认为,大学教学课时紧,内容多,关键靠学生自主学习,所以,大学教学以教师的讲授为主,不需要通过提问、讨论等方式进行教学互动。笔者认为这是不全面的。如果教师不顾学生的理解情况,只顾在讲台上讲授知识,课堂氛围会很沉闷,很多同学不能专注于该门课程的学习,经常走神,教学很难达到预期的效果。因此,有针对性地提问和展开讨论,不仅能够培养学生的思考能力,更能调动学生学习的兴趣和积极性,从而使教学达到最佳效果。
然而,由于离散数学课程在教学难度、课堂教学时间等方面的原因,很多学校都出现师生、学生之间的交流较少,致使学生对该门课程缺乏兴趣,教学效果不佳。所以,教师有必要针对课程中的主要问题或疑难问题适时地提问或者让学生展开讨论,鼓励他们进行独立思考,各抒己见,引导他们逐步深入地对问题进行实质性地分析,必要时,教师对其进行引导,及时总结,使教学达到预期效果。
3 合理布置作业,认真批改作业,有针对性地安排习题课和课后答疑
为了强化学生能力的训练,培养学生的抽象思维能力、逻辑推理能力、实际问题的解决能力等,在保证作业数量的同时,更要提高布置作业的质量,增加典型简答题、讨论题、推理题、实际应用题等习题在作业中的分量,使学生在掌握各种基本知识和基本技能的同时,提高自身的综合能力。当然,布置作业是一回事,学生能否认真完成作业,是预期目标能否实现的关键所在,认真检查和批改作业,是督促学生学习的主要途径,也是教师了解学生理解和掌握所学课程情况的主渠道。必要时,教师可以批改一部分作业,其他作业让同学们之间互相检查和批改,不仅可以督促学生学习,更能让学生在批改其他同学作业时逐步认识到自身的缺陷和不足,以备今后更有针对性地学习。
教师在作业检查和批改过程中发现的主要问题和疑难以及学生提出的有代表性的问题,有必要安排习题课进行讲解,帮助学生对解决疑难,加深对所知识的理解。对于学生比较争论的问题,可以展开讨论,鼓励学生大胆发言,培养学生探索未知的精神和创造性解决实际问题的能力。
因此,上好离散数学课,关键是根据学生具体实际,有针对性地安排教学内容,合理使用教学方式方法,最大限度地激发学生的学习兴趣,充分发挥教师的主导作用和学生的主体作用,达到教与学和谐。
参考文献
[1] 屈婉玲,耿素云,张立昂.离散数学[M].北京:高等教育出版社.2008.
[2] 黄巍,金国祥.”离散数学”课程教学改革的探讨[J].中国电力教育,2009(8):82-83.
[3] 周小燕,胡丰华.对提高离散数学教学质量的探讨[J].浙江科技学院学报,2007,19(2):156-158.
[4] 龙浩,张佳佳.怎样教好《离散数学》课[J].贵阳学院学报,2007,2(1):53-57.
一、证明题（10分）
1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R 证明: 左端(P∧Q∧R)∨((Q∨P)∧R)((P∧Q)∧R))∨((Q∨P)∧R)((P∨Q)∧R)∨((Q∨P)∧R)((P∨Q)∨(Q∨P))∧R ((P∨Q)∨(P∨Q))∧R T∧R(置换)R 2)x(A(x)B(x)) xA(x)xB(x)证明 ：x(A(x)B(x))x(A(x)∨B(x))xA(x)∨xB(x)xA(x)∨xB(x)xA(x)xB(x)
二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式（10分）。
证明：(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R))（P∧(Q∨R)）∨(P∧Q∧R)(P∧Q)∨(P∧R))∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R)m0∨m1∨m2∨m7 M3∨M4∨M5∨M6
三、推理证明题（10分）
1）C∨D，(C∨D) E，E(A∧B)，(A∧B)(R∨S)R∨S 证明：(1)(C∨D)E(2)E(A∧B)
P P
P(3)(C∨D)(A∧B)T(1)(2)，I(4)(A∧B)(R∨S)(5)(C∨D)(R∨S)(6)C∨D
T(3)(4)，I P(7)R∨S T(5)，I 2)x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))证明(1)xP(x)P
(2)P(a)T(1)，ES(3)x(P(x)Q(y)∧R(x))P(4)P(a)Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)，I(6)Q(y)T(5)，I(7)R(a)T(5)，I(8)P(a)∧R(a)T(2)(7)，I(9)x(P(x)∧R(x))T(8)，EG(10)Q(y)∧x(P(x)∧R(x))T(6)(9)，I
四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数（10分）。
解：A，B，C分别表示会打排球、网球和篮球的学生集合。则|A|=12，|B|=6，|C|=14，|A∩C|=6，|B∩C|=5，|A∩B∩C|=2。
先求|A∩B|。
∵6=|（A∪C）∩B|=|（A∩B）∪（B∩C）|=|（A∩B）|+|（B∩C）|-|A∩B∩C|=|（A∩B）|+5-2，∴|（A∩B）|=3。
于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。
五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C)（10分）。
证明：∵x A-（B∪C） x A∧x（B∪C）
x A∧（xB∧xC）
（x A∧xB）∧（x A∧xC） x（A-B）∧x（A-C） x（A-B）∩（A-C）
∴A-（B∪C）=（A-B）∩（A-C）
六、已知R、S是N上的关系，其定义如下：R={
解：R={
七、设R={，
解：r(R)={，
12-1
2s(R)={，
八、证明整数集I上的模m同余关系R={
证明：1）x∈I，因为（x-x）/m=0，所以xx(mod m)，即xRx。
2）x，y∈I，若xRy，则xy(mod m)，即（x-y）/m=k∈I，所以（y-x）/m=-k∈I，所以yx(mod m)，即yRx。
3）x，y，z∈I，若xRy，yRz，则（x-y）/m=u∈I，（y-z）/m=v∈I，于是（x-z）/m=（x-y+y-z）/m=u+v ∈I，因此xRz。
九、若f:A→B和g:B→C是双射，则（gf）=fg（10分）。
1-1-14325证明：因为f、g是双射，所以gf：A→C是双射，所以gf有逆函数（gf）：C→A。同理可推fg：C→A是双射。
因为
1-1
-1-1-1-1
-1-1-1
-1离散数学试题(B卷答案2）
一、证明题（10分）
1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T 证明: 左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R))(摩根律)((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(分配律)((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(等幂律)T(代入)2)xy(P(x)Q(y)) (xP(x)yQ(y))证明：xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)(xP(x)yQ(y))
二、求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（10分）
解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q)(P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1 m0∨m2∨m3
三、推理证明题（10分）
1)(P(QS))∧(R∨P)∧QRS 证明：(1)R(2)R∨P(3)P(4)P(QS)(5)QS(6)Q(7)S(8)RS 2)x(A(x)yB(y))，x(B(x)yC(y))xA(x)yC(y)。
证明：(1)x(A(x)yB(y))P(2)A(a)yB(y)T(1)，ES(3)x(B(x)yC(y))P(4)x(B(x)C(c))T(3)，ES(5)B(b)C(c)T(4)，US(6)A(a)B(b)T(2)，US(7)A(a)C(c)T(5)(6)，I(8)xA(x)C(c)T(7)，UG(9)xA(x)yC(y)T(8)，EG
四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。
解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生 的集合，则命题可符号化为：PxA(x)，xA(x)QQP。
(1)PxA(x)P(2)PxA(x)T(1)，E(3)xA(x)P T(2)，E(4)xA(x)Q P(5)(xA(x)Q)∧(QxA(x))T(4)，E(6)QxA(x)T(5)，I(7)QP T(6)(3)，I
五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)（10分）
证明：∵x A∩（B∪C） x A∧x（B∪C） x A∧（xB∨xC）（x A∧xB）∨（x A∧xC） x（A∩B）∨x A∩C x（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C）
六、A={ x1,x2,x3 }，B={ y1,y2}，R={
七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。
解：r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>, <3,3>,<4,4>,<5,5>} s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>} R=R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>} R={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>} t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}
八、设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠。关系R满足：<
证明 对任意的
对任意的
5∈R，即
对任意的
综上可得，R是A×B上的等价关系。
九、设f：AB，g：BC，h：CA，证明：如果hgf＝IA，fhg＝IB，gfh＝IC，则f、g、h均为双射，并求出f、g和h（10分）。
解 因IA恒等函数，由hgf＝IA可得f是单射，h是满射；因IB恒等函数，由fhg＝IB可得g是单射，f是满射；因IC恒等函数，由gfh＝IC可得h是单射，g是满射。从而f、g、h均为双射。
由hgf＝IA，得f＝hg；由fhg＝IB，得g＝fh；由gfh＝IC，得h＝gf。－
1－1
－1－1－1
－1离散数学试题(B卷答案3）
一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程)1)P(P∨Q∨R)2)((QP)∨P)∧(P∨R)3)((P∨Q)R)((P∧Q)∨R)解：1)重言式；2)矛盾式；3)可满足式
二、（10分）求命题公式（P∨(Q∧R))(P∨Q∨R)的主析取范式，并求成真赋值。
解：（P∨(Q∧R))(P∨Q∨R)(P∨(Q∧R))∨P∨Q∨R P∧(Q∨R)∨P∨Q∨R (P∧Q)∨(P∧R)∨(P∨Q)∨R ((P∨Q)∨(P∨Q))∨(P∧R)∨R 1∨((P∧R)∨R)1 m0∨m1∨m2∨m3∨m4∨m5∨m6∨m7 该式为重言式，全部赋值都是成真赋值。
三、（10分）证明((P∧Q∧A)C)∧(A(P∨Q∨C))(A∧(PQ))C 证明：((P∧Q∧A)C)∧(A(P∨Q∨C))((P∧Q∧A)∨C)∧(A∨(P∨Q∨C))((P∨Q∨A)∨C)∧((A∨P∨Q)∨C)
((P∨Q∨A)∧(A∨P∨Q))∨C ((P∨Q∨A)∧(A∨P∨Q))C ((P∨Q∨A)∨(A∨P∨Q))C ((P∧Q∧A)∨(A∧P∧Q))C (A∧((P∧Q)∨(P∧Q)))C (A∧((P∨Q)∧(P∨Q)))C (A∧((QP)∧(PQ)))C (A∧(PQ))C
四、（10分）个体域为{1，2}，求xy（x+y=4）的真值。
解：xy（x+y=4）x（（x+1=4）∨（x+2=4））
（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4））（0∨0）∧（0∨1）0∧10
五、（10分）对于任意集合A，B，试证明：P(A)∩P(B)=P(A∩B)解：xP(A)∩P(B)，xP(A)且xP(B)，有xA且xB，从而xA∩B，xP(A∩B)，由于上述过程可逆，故P(A)∩P(B)=P(A∩B)
六、（10分）已知A={1，2，3，4，5}和R={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>}，求r(R)、s(R)和t(R)。
解：r(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<3，2>，<4，3>，<4，5>} t(R)={<1，2>，<2，1>，<2，3>，<3，4>，<5，4>，<1，1>，<1，3>，<2，2>，<2，4>，<1，4>}
七、（10分）设函数f：R×RR×R，R为实数集，f定义为：f(
解：1）
2）
∈R×R，由f( ，通过计算可得x=(p+q)/2；y=(p-q)/2；从而 的原象存在，f是满射。 八、（10分） 证明：1）a，b∈G，ab=a*u*b∈G，运算是封闭的。 2）a，b，c∈G，（ab）c=（a*u*b）*u*c=a*u*（b*u*c）=a（bc），运算是可结合的。 3）a∈G，设E为的单位元，则aE=a*u*E=a，得E=u，存在单位元u。4）a∈G，ax=a*u*x=E，x=u*a*u，则xa=u*a*u*u*a=u=E，每个元素都有逆元。 所以 九、（10分）已知：D= 解：1）D的邻接距阵A和可达距阵P如下： A= 0 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1- 1-1 P= 1 1 1 1 十、（10分）求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 解：最优二叉树为 权＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148 离散数学试题(B卷答案4） 一、证明题（10分） 1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T 证明: 左端((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R))(摩根律)((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(分配律)((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R))(等幂律)T(代入)2)x(P(x)Q(x))∧xP(x)x(P(x)∧Q(x))证明：x(P(x)Q(x))∧xP(x)x((P(x)Q(x)∧P(x))x((P(x)∨Q(x)∧P(x))x(P(x)∧Q(x))xP(x)∧xQ(x)x(P(x)∧Q(x)) 二、求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（10分） 解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q)(P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1m0∨m2∨m3 三、推理证明题（10分） 1)(P(QS))∧(R∨P)∧QRS 证明：（1）R 附加前提(2)R∨P P(3)P T(1)(2),I(4)P(QS)P(5)QS T(3)(4),I(6)Q P(7)S T(5)(6),I(8)RS CP 2)x(P(x)∨Q(x))，xP(x)x Q(x)证明：(1)xP(x)P(2)P(c)T(1),US(3)x(P(x)∨Q(x))P(4)P(c)∨Q(c)T(3),US(5)Q(c)T(2)(4),I(6)x Q(x)T(5),EG 四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（10分）。 证明：把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。 五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)（10分） 证明：∵x A∩（B∪C） x A∧x（B∪C） x A∧（xB∨xC）（x A∧xB）∨（x A∧xC） x（A∩B）∨x A∩C x（A∩B）∪（A∩C）∴A∩（B∪C）=（A∩B）∪（A∩C） 六、={A1，A2，„，An}是集合A的一个划分，定义R={|a、b∈Ai，I=1，2，„，n}，则R是A上的等价关系（15分）。 证明：a∈A必有i使得a∈Ai，由定义知aRa，故R自反。a,b∈A，若aRb，则a,b∈Ai，即b,a∈Ai，所以bRa，故R对称。 a,b,c∈A，若aRb 且bRc，则a,b∈Ai及b,c∈Aj。因为i≠j时Ai∩Aj=，故i=j，即a,b,c∈Ai，所以aRc，故R传递。 总之R是A上的等价关系。 七、若f:A→B是双射，则f:B→A是双射（15分）。 证明:对任意的x∈A，因为f是从A到B的函数，故存在y∈B，使 对任意的x∈A，若存在y1,y2∈B，使得 因此f是双射。 八、设 证明 假设A≠G且B≠G，则存在aA，aB，且存在bB，bA（否则对任意的aA，aB，从而AB，即A∪B＝B，得B＝G，矛盾。） 对于元素a*bG，若a*bA，因A是子群，aA，从而a *(a*b)＝b A，所以矛盾，故a*bA。同理可证a*bB，综合有a*bA∪B＝G。综上所述，假设不成立，得证A＝G或B＝G。 九、若无向图G是不连通的，证明G的补图G是连通的（10分）。 证明 设无向图G是不连通的，其k个连通分支为G1、G2、„、Gk。任取结点u、v∈G，若u和v不在图G的同一个连通分支中，则[u，v]不是图G的边，因而[u，v] 1-1-1 -1-1-1-1是图G的边；若u和v在图G的同一个连通分支中，不妨设其在连通分支Gi（1≤i≤k）中，在不同于Gi的另一连通分支上取一结点w，则[u，w]和[w，v]都不是图G的边，因而[u，w]和[w，v]都是G的边。综上可知，不管那种情况，u和v都是可达的。由u和v的任意性可知，G是连通的。 离散数学试题（B卷答案5） 一、（10分）求命题公式(P∧Q)(PR)的主合取范式。 解：(P∧Q)(PR)（(P∧Q)(PR)）∧（(PR)(P∧Q)）（(P∧Q)∨(P∧R)）∧（(P∨R)∨(P∨Q)）(P∧Q)∨(P∧R)(P∨R)∧（Q∨P）∧（Q∨R） (P∨Q∨R)∧(P∨Q∨R)∧（P∨Q∨R）∧（P∨Q∨R）M1∧M3∧M4∧M5 二、（8分）叙述并证明苏格拉底三段论 解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。命题符号化为x（F（x）G（x）），F（a）G（a）证明： （1）x(F(x)G(x))P（2）F(a)G(a)T(1),US（3）F(a)P（4）G(a)T(2)(3),I 三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)证明：∵x A∩（B∪C） x A∧x（B∪C） x A∧（xB∨xC） （x A∧xB）∨（x A∧xC） x（A∩B）∨x A∩C x（A∩B）∪（A∩C） ∴A∩（B∪C）=（A∩B）∪（A∩C） 四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。 解：x∈A，因为R和S是自反关系，所以 x、y∈A，若 x、y、z∈A，若 总之R∩S是等价关系。 2）因为x∈[a]R∩S 五、(10分)设A＝{a，b，c，d}，R是A上的二元关系，且R＝{， 解 r(R)＝R∪IA＝{， t(R)＝R＝{， 4232-1d>，} 六、(15分)设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×CB×D且∈A×C，h()＝ 证明：1）先证h是满射。 2）再证h是单射。 、∈A×C，若h()＝h()，则 到D的双射，所以a1＝a2，c1＝c2，所以＝，所以h是单射。 综合1）和2），h是双射。 七、(12分)设 证明： a,b∈H有b∈H，所以a*b∈H。a∈H，则e=a*a∈H a=e*a∈H ∵a,b∈H及b∈H，∴a*b=a*（b）∈H ∵HG且H≠,∴*在H上满足结合律 ∴ 八、（10分）设G= 解：设G的每个结点的度数都大于等于6，则2|E|=d(v)≥6|V|，即|E|≥3|V|，与简单无向平面图的|E|≤3|V|-6矛盾，所以G至少有一个结点的度数小于等于5。九.G=,A={a,b,c},*的运算表为：(写过程，7分)- 1-1 -1-1-1-1-1 -1-1（1）G是否为阿贝尔群？ （2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元 解：（1）(a*c)*(a*c)=c*c=b=a*b=(a*a)*(c*c)(a*b)*(a*b)=b*b=c=a*c=(a*a)*(b*b)(b*c)*(b*c)=a*a=a=c*b=(b*b)*(c*c)所以G是阿贝尔群 （2）因为a*a=a a*b=b*a=b a*c=c*a=c 所以G的单位元是a（3）因为a*a=a 所以G的幂等元是a（4）因为b*c=c*b=a，所以b的逆元是c且c的逆元是b 十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 解：最优二叉树为 权＝148 离散数学试题（B卷答案6） 一、（20分）用公式法判断下列公式的类型：(1)(P∨Q)(PQ)(2)(PQ)(P∧(Q∨R))解：（1）因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q)∨(P∧Q)m1∨m2∨m3 M0 所以，公式(P∨Q)(PQ)为可满足式。 （2）因为(PQ)(P∧(Q∨R))((P∨Q))∨(P∧Q∧R)) (P∨Q)∨(P∧Q∧R)) (P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R)(P∨Q)∧(P∨Q∨R) (P∨Q∨(R∧R))∧(P∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M0∧M1 m2∨m3∨m4∨m5∨m6∨m7 所以，公式(PQ)(P∧(Q∨R))为可满足式。 二、（15分）在谓词逻辑中构造下面推理的证明：每个科学家都是勤奋的，每个勤奋 又身体健康的人在事业中都会获得成功。存在着身体健康的科学家。所以，存在着事业获得成功的人或事业半途而废的人。 解：论域：所有人的集合。Q(x)：x是勤奋的；H(x)：x是身体健康的；S(x)：x是科学家；C(x)：x是事业获得成功的人；F(x)：x是事业半途而废的人；则推理化形式为： x(S(x)H(x))Q(x))，x(Q(x)∧H(x)C(x))，x(S(x)∧x(C(x)∨F(x))下面给出证明： (1)x(S(x)∧H(x)) P(2)S(a)∧H(a) T(1)，ES(3)x(S(x)Q(x)) P(4)S(a)Q(a) T(1)，US(5)S(a) T(2)，I(6)Q(a) T(4)(5)，I(7)H(a) T(2)，I(8)Q(a)∧H(a) T(6)(7)，I(9)x(Q(x)∧H(x)C(x)) P(10)Q(a)∧H(a)C(a) T(9)，Us(11)C(a) T(8)(10)，I(12)xC(x) T(11)，EG(13)x(C(x)∨F(x)) T(12)，I 三、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解 P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}} 四、（15分）设R和S是集合A上的任意关系，判断下列命题是否成立？(1)若R和S是自反的，则R*S也是自反的。(2)若R和S是反自反的，则R*S也是反自反的。(3)若R和S是对称的，则R*S也是对称的。 (4)若R和S是传递的，则R*S也是传递的。(5)若R和S是自反的，则R∩S是自反的。(6)若R和S是传递的，则R∪S是传递的。 解 (1)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R*S，故R*S也是自反的。 (2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。 (3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，则R和S是对称的，但R*S＝{<1，3>，<3，2>}不是对称的。 (4)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S＝{<1，3>，<1，1>，<2，1>}不是传递的。 (5)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R∩S，所以R∩S是自反的。 五、（15分）令X＝{x1，x2，„，xm}，Y＝{y1，y2，„，yn}。问(1)有多少个不同的由X到Y的函数？ (2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？(3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？ 解 (1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共nm个。 (2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到 mY的不同的单射，故不同的单射有Cnm!＝n(n－1)(n―m―1)个。 (3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，故不同的双射有m!个。 六、（5分）集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？ 解 X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。 七、（10分）若 b。 证明 设e是群 － － －所以，x＝a1*b是a*x＝b的解。－若x∈G也是a*x＝b的解，则x＝e*x＝(a1*a)*x＝a1*(a*x)＝a1*b＝x。所以，x － － －＝a1*b是a*x＝b的惟一解。－ 八、（10分）给定连通简单平面图G＝ 证明 由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是d(f)＝2|E|＝ fF24。若存在f∈F，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。 离散数学试题（B卷答案7） 一、（15分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。 (1)写出F在全功能联结词组{}中的命题公式。(2)写出F的主析取范式与主合取范式。 解 (1)设A：开关A关闭；B：开关B关闭；C：开关C关闭；F＝(A∧C)∨(B∧C)。在全功能联结词组{}中： A(A∧A)AA A∧C(A∧C)(AC)(AC)(AC) A∨B(A∧B)((AA)∧(BB))(AA)(BB)所以 F((AC)(AC))∨((BC)(BC))(((AC)(AC))((AC)(AC)))(((BC)(BC))((BC)(BC)))(2)F(A∧C)∨(B∧C) (A∧(B∨B)∧C)∨((A∨A)∧B∧C)(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C)m3∨m5∨m7 主析取范式 M0∧M1∧M2∧M4∧M6 主合取范式 二、（10分）判断下列公式是否是永真式？(1)(xA(x)xB(x))x(A(x)B(x))。(2)(xA(x)xB(x))x(A(x)B(x)))。解 (1)(xA(x)xB(x))x(A(x)B(x))(xA(x)∨xB(x))x(A(x)B(x))(xA(x)∨xB(x))∨x(A(x)∨B(x))(xA(x)∧xB(x))∨xA(x)∨xB(x)(xA(x)∨xA(x)∨xB(x))∧(xB(x)∨xA(x)∨xB(x))x(A(x)∨A(x))∨xB(x)T 所以，(xA(x)xB(x))x(A(x)B(x))为永真式。 (2)设论域为{1，2}，令A(1)＝T；A(2)＝F；B(1)＝F；B(2)＝T。 则xA(x)为假，xB(x)也为假，从而xA(x)xB(x)为真；而由于A(1)B(1)为假，所以x(A(x)B(x))也为假，因此公式(xA(x)xB(x))x(A(x)B(x))为假。该公式不是永真式。 三、（15分）设X为集合，A＝P(X)－{}－{X}且A≠，若|X|＝n，问(1)偏序集是否有最大元？(2)偏序集是否有最小元？ (3)偏序集中极大元和极小元的一般形式是什么？并说明理由。解 偏序集不存在最大元和最小元，因为n＞2。 考察P(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|＝n，则第n－1层是X的n－1元子集，第n层是X。偏序集与偏序集 相比，恰好缺少第0层和第n层。因此的极小元就是X的所有单元集，即{x}，x∈X；而极大元恰好是比X少一个元素，即X－{x}，x∈X。 四、（10分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，－ <4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，i11>，<5，4>，<5，5>}。 五、（10分）设函数g：A→B，f：B→C，(1)若fg是满射，则f是满射。(2)若fg是单射，则g是单射。 证明 因为g：A→B，f：B→C，由定理5.5知，fg为A到C的函数。 (1)对任意的z∈C，因fg是满射，则存在x∈A使fg(x)＝z，即f(g(x))＝z。由g：A→B可知g(x)∈B，于是有y＝g(x)∈B，使得f(y)＝z。因此，f是满射。 (2)对任意的x1、x2∈A，若x1≠x2，则由fg是单射得fg(x1)≠fg(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。 六、（10分）有幺元且满足消去律的有限半群一定是群。 证明 设 考虑a，a2，„，ak，„。因为G只有有限个元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是幺元。由消去率得am＝e。 于是，当m＝1时，a＝e，而e是可逆的；当m＞1时，a*am-1＝am-1*a＝e。从而a是可逆的，其逆元是am-1。总之，a是可逆的。 七、（20分）有向图G如图所示，试求：(1)求G的邻接矩阵A。 (2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？ (3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。(4)求出可达矩阵P。(5)求出强分图。 解 (1)求G的邻接矩阵为： 00A00101011 101100(2)由于 002A001110220130A0211102011120322044A 031201012313 2322所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。(3)由于 00ATA000002131212TAA 21011102132110 2121再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。 (4)00B4AA2A3A40000所以求可达矩阵为P0000(5)因为PPT0010100110+10101000111111。 11111111101111∧1111111100001110＝01110111000111，所以{v1}，{v2，v3，v4} 111111因 1110 2010 + 1110 0110 2120312204+ 2120320101231323220 000 为 741 747，747 434构成G的强分图。 离散数学试题（B卷答案8） 一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R 证明 因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。(1)R 附加前提(2)PR P(3)P T(1)(2)，I(4)P∨Q P(5)Q T(3)(4)，I(6)QS P(7)S T(5)(6)，I(8)RS CP(9)S∨R T(8)，E 二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。 设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。 (1)x(P(x)Q(x)) P(2)x(P(x)∨Q(x)) T(1)，E(3)x(P(x)∧Q(x)) T(2)，E(4)P(a)∧Q(a) T(3)，ES(5)P(a) T(4)，I(6)Q(a) T(4)，I(7)x(P(x)(A(x)∨B(x)) P(8)P(a)(A(a)∨B(a)) T(7)，US(9)A(a)∨B(a) T(8)(5)，I(10)x(A(x)Q(x)) P (11)A(a)Q(a) T(10)，US(12)A(a) T(11)(6)，I (13)B(a) T(12)(9)，I(14)P(a)∧B(a) T(5)(13)，I(15)x(P(x)∧B(x)) T(14)，EG 三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。 解 设A、B、C分别表示会打排球、网球和篮球的学生集合。则： |A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。 四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称 i13为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。 证明 小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。 对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，即有a∈si，于是Usi。又显然有siU，所以U＝si。 i1i1i1i1i13rrrr任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。 综上可知，{s1，s2，…，sr}是U的一个划分。 五、（15分）设R是A上的二元关系，则：R是传递的R*RR。 证明 (5)若R是传递的，则 反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则 六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。 证明 对G的边数m作归纳法。 当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。 设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论： 若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。 若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。 由数学归纳法知，结论成立。 七、（10分）设函数g：A→B，f：B→C，则：(1)fg是A到C的函数； (2)对任意的x∈A，有fg(x)＝f(g(x))。 证明 (1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使 对任意的x∈A，若存在y1、y2∈C，使得 综上可知，fg是A到C的函数。 (2)对任意的x∈A，由g：A→B是函数，有 八、（15分）设 证明 对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。 － － 若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以 － － －a>∈R。 若∈R， － － －1*b)*(b1*c)＝a1*c∈H，故∈R。－－综上可得，R是G中的一个等价关系。 对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h，－ －于是b∈aH，[a]RaH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH[a]R。所以，[a]R＝aH。 离散数学试题（B卷答案9） 一、（10分）证明(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C。证明：(P∧Q∧AC)∧(AP∨Q∨C)(P∨Q∨A∨C)∧(A∨P∨Q∨C) (P∨Q∨A∨C)∧(A∨P∨Q∨C)((P∨Q∨A)∧(A∨P∨Q))∨C ((P∧Q∧A)∨(A∧P∧Q))∨C (A∧((P∧Q)∨(P∧Q)))∨C (A∧(PQ))∨C (A∧(PQ))C。 二、（10分）举例说明下面推理不正确：xy(P(x)Q(y))，yz(R(y)Q(z))xz(P(x)R(z))。 解：设论域为{1，2}，令P(1)＝P(2)＝T；Q(1)＝Q(2)＝T；R(1)＝R(2)＝F。则： xy(P(x)Q(y))x((P(x)Q(1))∨(P(x)Q(2))) ((P(1)Q(1))∨(P(1)Q(2)))∧((P(2)Q(1))∨(P(2)Q(2)))((TT)∨(TT))∧((TT)∨(TT))T yz(R(y)Q(z))y((R(y)Q(1))∨(R(y)Q(2))) ((R(1)Q(1))∨(R(1)Q(2)))∧((R(2)Q(1))∨(R(2)Q(2))) ((FT)∨(FT))∧((FT)∨(FT)) T 但 xz(P(x)R(z))x((P(x)R(1))∧(P(x)R(2)))((P(1)R(1))∧(P(1)R(2)))∨((P(2)R(1))∧(P(2)R(2)))((TF)∧(TF))∨((TF)∧(TF))F 所以，xy(P(x)Q(y))，yz(R(y)Q(z))xz(P(x)R(z))不正确。 三、（15分）在谓词逻辑中构造下面推理的证明：所有牛都有角，有些动物是牛，所以，有些动物有角。 解：令P(x)：x是牛；Q(x)：x有角；R(x)：x是动物；则推理化形式为： x(P(x)Q(x))，x(P(x)∧R(x))x(Q(x)∧R(x))下面给出证明： (1)x(P(x)∧R(x)) P(2)P(a)∧R(a) T(1)，ES(3)x(P(x)Q(x)) P(4)P(a)Q(a) T(3)，US(5)P(a) T(2)，I(6)Q(a) T(4)(5)，I(7)R(a) T(2)，I(8)Q(a)∧R(a) T(6)(7)，I(9)x(Q(x)∧R(x)) T(8)，EG 四、（10分）证明(A∩B)×(C∩D)＝(A×C)∩(B×D)。 证明：因为 五、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，－ <4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，i11>，<5，4>，<5，5>}。 六、（10分）若函数f：A→B是双射，则对任意x∈A，有f1(f(x))＝x。 －证明 对任意的x∈A，因为f：A→B是函数，则 －由f－1是B到A的函数，于是可写为f1(f(x))＝x。 － 七、（10分）若G为有限群，则|G|＝|H|·[G:H]。 证明 设[G:H]＝k，a1、a2、…、ak分别为H的k个左陪集的代表元，由定理8.38得 G[ai]RaiH i1i1kk又因为对H中任意不同的元素x、y∈H及a∈G，必有a*x≠a*y，所以|a1H|＝…＝|akH|＝|H|。因此 |G||aiH|i1k|aH|k|H|＝|H|·[G:H]。 ii1k 八、（20分）（1）画出3阶2条边的所有非同构有向简单图。 解：由握手定理可知，所画的有向简单图各结点度数之和为4，且最大出度和最大入度均小于或等于2。度数列与入度列、出度列为： 1、2、1：入度列为0、1、1或0、2、0或1、0、1；出度列为1、1、0或1、0、1或0、2、0 2、2、0：入度列为1、1、0；出度列为1、1、0 四个所求有向简单图如图所示。 （2）设G是n(n≥4)阶极大平面图，则G的最小度≥3。 证明 设v是极大平面图G的任一结点，则v在平面图G－{v}的某个面f内。由于G－{v}是一个平面简单图且其结点数大于等于3，所以d(f)≥3。由G的极大平面性，v与f上的结点之间都有边，因此d(v)≥3。由v的任意性可得，G的最小度≥3。 离散数学试题（B卷答案10） 一、（10分）使用将命题公式化为主范式的方法，证明(PQ)(P∧Q)(QP)∧(P∨Q)。 证明：因为(PQ)(P∧Q)(P∨Q)∨(P∧Q) (P∧Q)∨(P∧Q)(QP)∧(P∨Q)(Q∨P)∧(P∨Q)(P∧Q)∨(Q∧Q)∨(P∧P)∨(P∧Q)(P∧Q)∨P (P∧Q)∨(P∧(Q∨Q))(P∧Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)所以，(PQ)(P∧Q)(QP)∧(P∨Q)。 二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。 解 设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为： AB∨C，BA，DCAD (1)A 附加前提(2)AB∨C P(3)B∨C T(1)(2)，I(4)BA P(5)AB T(4)，E(6)B T(1)(5)，I(7)C T(3)(6)，I (8)DC P(9)D T(7)(8)，I(10)AD CP 三、（10分）证明xy(P(x)Q(y))(xP(x)yQ(y))。xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)(xP(x)yQ(y)) 四、（10分）设A＝{，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)B。解 P(A)＝{，{}，{1}，{{1}}，{，1}，{，{1}}，{1，{1}}，{，1，{1}}} P(B)－{0}＝{，{0}，{{0}}，{0，{0}}－{0}＝{，{0}，{{0}}，{0，{0}} P(B)B＝{，{0}，{{0}}，{0，{0}}{0，{0}}＝{，0，{{0}}，{0，{0}} 五、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)画出R的关系图。(2)写出R的关系矩阵。 (3)说明R是否是自反、反自反、对称、传递的。解(1)R的关系图如图所示：(2)R的关系矩阵为： 10M(R)111011101100 00(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的； 经过计算可得 10M(R2)111011101100M(R)，所以R是传递的。00 六、（15分）设函数f：R×RR×R，f定义为：f( (4)求复合函数ff和ff。 证明(1)对任意的x，y，x1，y1∈R，若f( (2)对任意的 1uwuwuwuw，y＝，则f( －1 ( xyxy，2xy(xy)>＝ 七、（15分）给定群 证明 对G中任意元a和b。 因为a*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同33 333 2255 13 111理，由a*b＝(a*b)可得，a*b＝(b*a)。由a*b＝(a*b)可得，a*b＝(b*a)。 于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。同理可得，(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。 3333334 344433555444 由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。 八、（15分）（1）证明在n个结点的连通图G中，至少有n－1条边。 证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。设G中结点为v1、v2、„、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、„、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、„、vn1中的某个结点相邻，得新边en1，由此可见G中至少有n－1条边。 （2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝ 解 下图满足条件但不连通。 一、判断哪些是命题 *命题的表示（联结词），符号化命题(样题2)*真值表（用来证明） *等价式的证明（用已知的等价式推导）(样题3)蕴涵的证明(样题4)对偶式（化对偶式） *写出主析（合）取范式（真值表，公式推导）(样题5)*命题的推理（真值表，直接，间接）(样体6) 二、*谓词公式的翻译（存在，全称）(p60习题2,批p61例题,批p62习题1)约束变元及其换名(p63例题1)等价式和蕴涵式（转换，扩展和收缩，分配，多量词）(p66-p70)前束范式(p73例题)*推理 p76-p77 三、*集合的表示 *集合的运算（。。幂集）*包含排斥 序偶（同集合） 关系（定义域，值域，特殊的关系，*关系的表示,特别是矩阵）*关系的性质（5大性质，） 复合关系和逆关系 p114例题1,p115例题5,p118例题4 关系的闭包运算（三个）p121例题1,p124例题4 集合的划分和覆盖（能判断哪些是划分和覆盖） *等价关系（判定，要会用等价关系对集合划分即写出等价类）p131,132例题, *序关系（判定，哈斯图，链反链）p140,141例题, *求极大（小），最大（小），上（下）界，上（下）确界 p146习题6 四、*判定是否函数，满，入，双 *逆函数、复合函数（判定原函数是满，入，双复合后是否满，入，双）判定二个集合是否等势（构造双射函数）有限集，无限集（可数，不可数） 自然数 实数集 可列 五、*代数运算的表示（包括运算表）p189例题 *判断代数系统的运算性质：封闭，可交换，可结合，可分配，吸收率，等幂性 *代数系统的幺元和零元（唯一性证明），逆元 p184 半群的判断，独异点的判断 *群与子群的判断，群的性质证明 交换群的性质，循环群的性质 *定理5-7.1,意义，性质 任何一个群不是4阶循环群就是Klein群 *同构同态的判断（满，单一，）p214例题，同余 环，域判断，同态象 六、*格、子格的定义 *并，交运算的定义及其性质 p233例题 p241例题 p242习题 格的同态与同构 *分配格的性质，p244例2,3 ,有补格的性质，补元素 p252习题1 布尔代数，布尔表达式及其范式 七、图简单性质（点边数目关系），图的同构判断，生成子图，补图 路，回路，通路，连通，点割集（割点），边割集（割边）及其性质 有向图的单侧连通（分图），强连通（分图），弱连通（分图）p287习题8 *图的矩阵（邻接，可达性，完全关联）p290例题1, *欧拉图的判定，H图的判定,p306,p310,样体21平面图的判定（K3,3 K5）p317习题5 对偶图和着色 p318,p319 p321习题 *树的等价定义和证明 证明等价关系：即要证明关系有自反、对称、传递的性质。 证明偏序关系：即要证明关系有自反、反对、传递的性质（特殊关系的证明就列出来两种，要证明剩下的几种只需要结合定义来进行）。 证明满射：函数f：X®Y，即要证明对于任意的yÎY，都有xÎX，使得f(x)=y。 证明入射：函数f：X®Y，即要证明对于任意的x1，x2ÎX，且x1≠x2，则f(x1)≠f(x2)；或者对于任意的f(x1)=f(x2)，则有x1=x2。 证证明集合等势：即明两个集合中存在双射。有三种情况：第一，证明两个具体的集合等势，用构造法，或者直接构造一个双射，或者构造两个集合相互间的入射。 第二，已知某个集合的基数，如果为א，就设它和R之间存在双射f，然后通过f的性质推出另外的双射，因此等势；如果为א0，则设和N之间存在双射。第三，已知两个集合等势，然后再证明另外的两个集合等势，这时，先设已知的两个集合存在双射，然后根据剩下题设条件证明要证的两个集合存在双射。 证明群：即要证明代数系统封闭、可结合、有幺元和逆元（同样，这一部分可以作为证明题的概念更多，要结合定义把它们全部理解透彻）。 证明子群：虽然子群的证明定理有两个，但如果考证明子群的话，通常是考第二个定理，即设是群，S是G的非空子集，如果对于S中的任意元素a和b有a*b-1ÎS，则是的子群。对于有限子群的相关证明，则可以考虑第一个定理。 证明正规子群：若是一个子群，H是G的一个子集，即要证明对于任意的aÎG，有aH=Ha，或者对于任意的hÎH，有a-1 *h*aÎH。这是最常见的题目中所使用的方法。 教师要想上好一节课, 必须拿出上课时间三倍的时间来备课。教师首先要吃透教材, 只有熟悉了教材才能顺利完成教学任务, 熟悉教材不仅包括掌握课本上的内容, 而且要深入到更深的层次上。 比如在讲欧拉图和哈密顿图的过程中, 教师可以在上课前通过上网查资料, 弄清楚欧拉图是欧拉通过哥尼斯堡七桥问题抽象出来的。尼斯堡是位于普累格河上的一座城市, 它包含两个岛屿和连接它们的七座桥, 该河流经城区的这两个岛, 岛与河岸之间架有六座桥, 另一座桥则连接着两个岛。星期天散步已成为当地居民的一种习惯, 但试图走过这样的七座桥, 而且每桥只走过一次却从来没有成功过, 但直至引起瑞士数学家欧拉注意之前, 没有人能够解决这个问题。通过这样一个有意思的小故事引出欧拉图, 学生就很容易记住欧拉图讲的是边不能重复的问题。在讲哈密顿图时, 教师可以介绍一下哈密顿周游世界问题, 从正十二面体的一个顶点出发, 沿着正十二面体的棱前进, 要把十二面体顶点无一遗漏地全部通过, 而每个顶点恰好只通过一次, 最后回到出发点。在这个问题刚提出来时, 生产商以为这是一个难题, 专为此设计了一个玩具, 以为可以吸引消费者, 谁知当这玩具推出市场时, 这个问题立刻被人解决了, 令生产商损失了一大笔钱。学生可以在笑声中很容易地记住哈密顿图是点不重复问题, 知道这两个图的区别。这些都要求教师在备课的过程中要充分准备各种资料。 教师在开始离散数学的教学之前应先简单介绍一下这门课程的重要意义及作用, 点明离散数学对其后续课程的基础作用, 让学生意识到这门课程在整个专业课程中的地位。学生只有提高了学习的积极性, 才会主动地去学习, 而不是被动地接受老师填鸭式的教学。教师应先把整个教材的内容分成几个小部分, 把每一部分的结构帮学生梳理清楚, 简单介绍一下每部分的主要内容。以耿素云的《离散数学》为例, 教师可以通过列表的方法把整个教材分成五个部分, 这样子可让学生在学习之前就大体了解离散数学的框架。 在上课的过程中, 教师要采用多种教学方法。离散数学定义特别多, 不太适用传统教学手段像黑板板书之类的, 这就要求教师采用现代化的教学方法多媒体, 而对数学来讲单纯多媒体教学效果不是特别好, 所以应该将这两种教学方法相结合。在课堂上教师应注意学生对这节课教学内容的反馈, 多问几个“听明白了吗”, “有没有问题”, 不能只注重教, 要注重教学效果, 要重视学生的情绪, 及时调整教学进度, 把学生的思路引进到教学活动中来, 使之兴趣盎然。比如在讲数理逻辑这一部分内容时, 教师可以多举几个实际问题的例子, 以便引起学生的兴趣。在讲关键路径时, 在定义描述中最早完成时间是沿最长路径到达目的地所需要的时间, 大部分学生对这个最长路径不理解。我给学生举了个简单的例子:在工程的盖楼过程中, 假设盖好一层楼需要两个必须步骤, 一是买水泥做钢筋混凝土, 二是打木桩, 在盖楼的过程中, 买水泥需要两周的时间, 做混凝土需要三周, 而打木桩需要四周, 那么现在盖起楼的最早完成时间是五周, 取决于时间最长的那个步骤。这样通过一个简单的例子, 学生就记住最早完成时间的概念。教学方法只是一种手段, 而不是教学目的, 甚至可以对某些内容设计几套方案, 以防止种种可能出现的结果, 做到有备无患。 在离散数学的教学过程中要讲求教学的针对性, 离散数学是计算机类专业普遍开设的一门专业基础课, 这就决定了其面向特定的学生, 这要求教师要注重学生的学科特点和内容的针对性。计算机学科的发展速度很快, 课本的内容可能有些已经跟不上时代的发展, 教师需要在教学过程中多去查资料, 运用互联网的资源, 把最先进最前沿的学科知识介绍给学生, 不断更新引例, 使授课内容更具时代特色和生活气息。比如在讲最短路径时, 教师可以找一个运用到最短路径的实际例子, 把这个问题的程序给学生运行一下, 让学生明白所学到的知识点和实际问题有什么联系。另外一个问题是在讲特殊的图时, 可以结合实际, 比如说教务处安排考试的问题, 要求教务处七天安排七门考试, 同一个老师担任的几门课程不能排在相邻的两天, 并且已知一个老师最多担任四门课程, 问题是教务处能否安排出可行的考试方案。我在讲课的过程中提到这个问题时, 本来已经介绍过几种特殊的图, 但学生感觉内容太多接受不了, 可是一听考试并且和自己密切相关, 顿时打起精神, 纷纷讨论怎么安排可行, 这就把课堂气氛搞活跃了。最初学生并不能联想到把这个转化成图的问题, 我就一步一步地引导, 告诉他们先把实际问题转化成图的问题画在纸上, 然后看看题目要求的这个图具有什么特性。最后学生才恍然大悟, 原来是哈密顿通路问题, 这样子这一节课的教学效果就会比较好。 检查学生掌握程度的手段是测试, 但是不能让测试成为学生的压力, 让他们对离散数学的学习产生抵触程序。考试是衡量学生学习水平的重要手段, 应该为教学而考试, 而不是为考试而教学, 学生掌握这门课程才是教师教的目的。 学习知识的目的是为了培养学生动手能力, 同时也加深他们对该课程在专业教学中地位的理解和认识。在离散数学的教学过程中, 教师应尝试在传统教学内容的基础上, 适当增加上机实验操作的教学模式。教师在探索的基础上, 应不断丰富实验内容, 在量的积累的基础上达到质的飞跃, 从而建立一套完备的离散数学的教学方法, 进一步提高离散数学在计算专业中的地位。 参考文献 [1]罗幼芝.提高离散数学实践性教学的探讨.湖北生态工程职业技术学院学报, 2009, Vol7, No.4:25-28. [2]离散数学课程教学改革探索与实践.计算机教育, 2010.3.25, 6:100-103. 关键词：离散数学 启发式教学 多媒体教学 离散数学是计算机专业一门重要基础课,搞好本课程的教学,不但能为学生学好后续课程奠定坚实的数学理论基础,而且有利于培养学生的计算机数学思维,并且在进一步的学习和工作中适应本学科专业的发展。 由于離散数学内容多，抽象难懂，逻辑性较强，学习它需要有一定的抽象思维能力、演绎推理能力和归纳总结能力。但是，高职学生抽象思维水平不高,认知结构具有不稳定性,对离散数学这种内容的抽象性和逻辑推理中的形式化证明缺乏必要的思维和心理准备, 这些问题导致学生学习兴趣不足，不会学,导致学不会,因而也就不愿意学。怎样提高高职计算机专业《离散数学》课程的教学质量已经成为我们迫切需要解决的问题。为协调好教与学的双边关系，使学生对这门课的学习发生兴趣，从而调动学生的学习积极性，使其由被动接受变为主动参与，就要在教学内容、教学方法、教学手段等方面进行相应的改革。 一、精选教学内容，突出其应用性 1．1 精心安排讲授内容，以“够用”为主 离散数学课程不仅内容多，而且繁又难，针对高职学生这一特定的对象和学时的限制，我们必须精选讲授内容，不能面面俱到、不分主次，而要突出重点，以学生“够用”为准，选择内容时应考虑到它是否能覆盖计算机科学所需的理论基础，强化基本概念的描述，注重基本方法的讲解。如对于离散数学中的纵多的定理证明，我们作了有针对性的、精心的处理；对于一些有利于加深对基本概念的理解，或者可以提高解决问题能力的定理的证明，都给予了详细的介绍；而另一些定理则仅给出一些描述性的说明，省略了完整的证明，其目的是突出要点，突出理论在实际中的应用。 1．2以实用性培养学生的学习兴趣和主动性 离散数学知识在计算机专业中的应用或“分散”或“隐含”,无处不在,但作为基础课程的离散数学教学在内容与形式上缺乏对本专业的直接针对性。在教学过程中，应注重让学生了解所学离散数学知识与相关学科之间的联系，要有意识地引导学生运用所学理论去联系实际问题，提高离散数学课对专业课的针对性和适用性，使学生学了以后感到“有用”。比如，在讲授图论中通路与回路概念时，给出它们在研究操作系统是否存在死锁，程序设计语言中一个过程是否递归等方面的应用。在讲授平面图时，给出它们在印刷电路板、集成电路等方面的应用。这样使学生感受《离散数学》的实用价值，提高学生学习的积极性、主动性 二、改革方法，激发学生学习兴趣，提高教学质量 离散数学基本概念、定理、方法特别多，单纯的讲授教学，枯燥乏味，很难激发学生的学习兴趣。我们采用了多种教学方法,以提高学生学习的积极性、主动性，提高教学质量。具体如下: 2.1 注重理论的理解、注重学习的过程 离散数学课程中有很多定义、定理、规则,对学生而言,几乎每一节课堂上均要接受数十个新的术语或定理,这显然是有很大的难度,而且很容易产生枯燥甚至畏难情绪。因此,新课伊始,我们就告诉学生,不用记忆,只需要理解,注重学习过程。我们认为,宁愿少讲授部分内容,也要学生对于讲授的理论知识能够真正理解掌握。在整体上分析之后,对部分知识删节,不用在课堂上讲授,而是作为学生的课外作业去完成。在课堂讲授中,我们注重对于问题的完整理解过程,而不是只告诉学生结论,也正因如此,尽管常常在一个课时中,可能仅仅完成一个问题的讲授而显得课时紧张,但我们认为这是完全值得的,事实上,也取得了好的效果。 2.2 抽象与具体相结合 离散数学中,有许多定义、定理、规则,教科书上对其描述很精练,学生常常感到很抽象, 如果直接给出定义，学生往往感到很难理解，所以在讲解这些概念时，先给出具体例子，再抽象出基本概念，使得学生对这些概念有更深刻的理解，加深学生对概念的印象。例如“代数系统”就是一个抽象的概念，在讲解时，笔者先给出学生比较熟悉的非空集(如整数集I)，并结合其上的运算(如加法运算)，再得出运算在非空集上封闭，逐步引出代数系统的定义，这样学生就不感到抽象、难理解了。 2.3采用启发式教学方法,联系高等数学知识，讲清离散数学中的难点 虽然离散数学的理论较为抽象，方法也较难，但它归根到底总是一门数学学科，它和大学生所学的高等数学中的一些知识总有一定的联系，因此，我们牢牢地抓住这个特点，采用启发式教学方法，促使学生回忆以往学过的知识，再和现在所学的联系起来，从而加深学生对基本概念的理解和掌握。例如在学习命题和谓词的时候，部分学生对命题与谓词的关系，特别是加上量词的谓词的理解不深刻。我们在讲解的时候启发学生回忆以前学习过的常数和函数及定积分的概念，然后指出，谓词就是一个命题函数，命题在这里可借助于常数的概念来理解，而带量词的谓词可借助于函数加上定积分后变成什么来理解，通过这样的启发，学生就很容易知识命题是谓词的特例，谓词是命题的推广的关系。当然，类似的例子在离散数学的教学中还有很多。 2.4上好习题课，调动学生积极性 习题讨论课不仅是帮助学生巩固所学知识的一种重要方式，还是属于提高性的教学环节。每章学完后，安排一次习题讨论课,所选习题要具有典型性、实际应用性等特点，让学生自己动脑、动手、动口，学会独立分析问题和解决问题，检查自己对知识的理解及掌握程度。通过让学生运用所学知识解决一些实际问题，可以训练其思维能力及分析问题、解决问题的能力, 激发学生学习离散数学的积极性。例如,在讲完根树这一章后，可安排这样一次习题讨论课。首先,让学生回忆课堂上讲过的有序二元树的树叶集合可生成前缀码的知识,再让学生分析怎样把一个前缀码用有序二元树表达出来,最后让学生讨论如何利用一棵最优树产生一个最佳前缀码，使得在传送信息时，既准确无误，又能节省二进制位。这样通过课堂讨论，既让学生巩固和完善所学的知识内容，又了解离散数学在计算机中的重要作用，同时也训练学生思维能力及分析问题、解决问题的能力，激发了学生学习离散数学的积极性。 三、改变教学手段，充分利用多媒体教学 离散数学课的一个特点是定义、定理、性质特别多，利用多媒体教学，教师不必再象过去那样一黑板、一黑板地去抄写，这为缩短理论授课时间，增强应用内容提供了保证。利用多媒体教学，有利于新旧知识的联结。在讲授某一新知识点时，常常要涉及到前面的内容，比如，在进行数理逻辑的推理时，就要用到前面的一些推理定律，而通过展示幻灯片，重新唤醒学生对这些定律的认识后，就会较容易使学生从已有的知识顺利过渡到新的知识点上来，轻松自然地获取新知识。 参考文献： [1]贾振华. 《离散数学》[M]．北京.水利水电出版社，2004,2. 【离散数学考试试题】推荐阅读： 离散数学模拟试题06-09 离散数学自学考试10-12 离散数学期末复习07-17 离散数学作业答案一06-15 关于离散数学的问题07-19 离散数学第三章总结10-28 《离散型随机变量及其分布列》数学教学反思07-05 《离散型随机变量的期望》说课稿10-15 数学考试解题策略，高考数学得分策略06-07 金融数学考试题09-20上海海事大学离散数学考试提纲 篇5
离散数学考试题型之定理应用题 篇6
浅谈大学离散数学的教学 篇7
离散数学考试试题 篇8
