离散数学集合论习题

离散数学集合论习题（精选8篇）

篇1：离散数学集合论习题

作业答案：集合论部分

P90:习题六

5、确定下列命题是否为真。（2）（4）{}

（6）{a,b}{a,b,c,{a,b}} 解答：（2）假（4）真（6）真

8、求下列集合的幂集。（5）{{1,2},{2,1,1},{2,1,1,2}}（6）{{,2},{2}} 解答：

（5）集合的元素彼此互不相同，所以{2,1,1,2}{1,2}，所以该题的结论应该为

{,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}

（6）{,{{,2}},{{2}},{{,2},{2}}}

9、设E{1,2,3,4,5,6}，A{1,4}，B{1,2,5},C{2,4},求下列集合。（1）A（2）解答：（1）A（2）

31、设A,B,C为任意集合，证明 B

(AB)

B{1,4}{3,4,6}{4}

(AB){1}{2,3,4,5,6}

(AB)证明：

(BA)(AB)(AB)

(AB)(BA){x|xABxBA}{x|(xAxB)(xBxA)}{x|(xAxB)(xBxB)(xAxA)(xBxA)} {x|(xAxB)(xBxA)}{x|(xA{x|(xAA

B)(xAxB)}{x|(xAB)(xABB)}{x|(xAB)(xAxB)}B)}B)(xABA34、设A,B为集合，证明：如果(AB)证明：（反证法）

设aA(BA)AB，则AB。

B，则aA,aB，所以aAB,aBA； 所以a(AB)但是aA与(AB)

37、设A,B,C为任意集合，证明：CACBC(A证明：

对任意xC，由于CA,CB，所以xA且xB所以xA因此，C(A

(BA)

B矛盾。

B)。

B B。

(BA)AB)。

P121:习题七

5、设A,B为任意集合，证明

若AABB，则AB。

证明：

xAx,xAA

x,xBBxB所以有AB

9、设A{1,2,4,6}，列出下列关系R（2）R{x,y|x,yA|xy|1}（3）R{x,y|x,yAy为素数} 解答：

11、Ri是X上的二元关系，对于xX定义集合（2）R{1,2,2,1}

（3）R{1,2,2,2,4,2,6,2}

Ri(x){y|xRy}

显然Ri(x)X。如果X{4,3,2,1,0,1,2,3,4},且令

R1{x,y|x,yXxy}

R2{x,y|x,yXy1xy2} R3{x,y|x,yXx2y}

求R1(0),R1(1),R2(0),R2(1),R3(3)。解答：

R1(0){1,2,3,4}R1(1){2,3,4}R2(0){1,0}R2(1){2,1}R3(3)，B{1,3,2,4,4,2}。求A13、设A{1,2,2,4,3,3}

B，AB，domA,domB,dom(A解答：

B),ranA,ranB,ran(AB),fld(AB).AAB{1,2,2,4,3,3,1,3,4,2} B{2,4}

domA{1,2,3} domB{1,2,4} dom(AB){1,2,3,4}

ranA{2,3,4} ranB{2,3,4} ran(A B){4}

fld(AB){1,2,3}

16、设A{a,b,c,d}，R1,R2为A上的关系，其中

R1{a,a,a,b,b,d}，R2{a,d,b,c,b,d,c,b}。求R1R2，R2R1，R12，R23。

解答：

R1R2{a,d,a,c,a,d} R2R1{c,d}

R12{a,a,a,b,a,d} R22{b,b,c,c,c,d} R23{b,c,b,d,c,b}

20、给定A{1,2,3,4}，A上的关系R{1,3,1,4,2,3,2,4,3,4}（1）画出R的关系图。（2）说明R的性质。解答：

（1）

（2）R具有反自反性，反对称性，传递性

21、设A{1,2,3}，图7.11给出12种A上的关系，对于每种关系写出相应的关系矩阵，并说明它所具有的性质。

解答：

110（a）111,具有自反性。101110（b）001,具有反对称性和传递性。100111（c）111,具有自反性，对称性和传递性。111

23、设R的关系图如图7.12所示，试给出r(R)，s(R)和t(R)的关系图。

25、设A{1,2,3,4}，R是A上的等价关系，且R是A上所构成的等价类为{1},{2,3,4}。（1）求R。（2）求RR（3）求R传递闭包。解答：

（1）R{1,1,2,2,3,3,4,4,2,3,3,2,2,4,4,2,3,4, 14,3}

（2）由于等价关系满足对称性，所以R所以RR11R

R

（3）由于等价关系满足传递性，所以传递闭包为其自身，即t(R)R

26、对于给定的A和R，判断R是否为A上的等价关系。（1）A为实数集，x,yA,xRyxy2。（2）A{1,2,3}，x,yA,xRyxy3。（3）AZ，x,yA,xRyxy为奇数。

（5）AP(X),CX，x,yA,xRyxyC 解答：

（1）不是，不满足自反性、对称性、传递性。（2）不是，由于A{1,2,3}集合较小，①自反性：xA,xx3x,xR

②对称性，x,yR,xy3yx3y,xR 但是传递性不满足，1,3,3,2R，但是1,2R。（3）不是，满足对称性、传递性，但是不满足自反性 取x2，但是224不为奇数，所以2,2R。

（5）满足

①自反性：xAxXxxCx,xR ②对称性：x,yRyxxyCy,xR ③传递性：x,y,y,zR

xyC,yzC (xy)(yx)C,(yz)(zy)C(xy)C,(yx)C,(yz)C,(zy)C下面证明(xz)C

a(xz)ax,az

若ay，则ayz，所以aC 若ay，则axy，所以aC

所以(xz)C，同理可证，(zx)C 所以xz(xz)(zx)C 所以x,zR。因此满足传递性。

27、设A{a,b,c,d},A上的等价关系

R{a,b,b,a,c,d,d,c}IA

画出R的关系图，并求出A中各元素的等价类。解答：关系图为

等价类[a][b]{a,b}；[c][d]{c,d}

30、设A{1,2,3,4},，在AA上定义二元关系R，u,v,x,yAA,u,vRx,yuyxv。

（1）证明R为AA上的等价关系。（2）确定由R引起的对AA的划分。解答：（1）证明：

①自反性：x,yAA，由于xyxy，所以x,y,x,yR； ②对称性：x,y,u,vR

有xvuy，所以uyxv 因此u,v,x,yR

③传递性：x,y,u,v,u,v,s,tR

有xvuy，utsv，所以xsty 因此x,y,s,tR。

（2）等价类有

[1,1]{1,1,2,2,3,3,4,4} [1,2]{1,2,2,3,3,4} [1,3]{1,3,2,4} [1,4]{1,4} [2,1]{2,1,3,2,4,3} [3,1]{3,1,4,2} [4,1]{4,1}

37、对于下列集合与整除关系画出哈斯图。（1）{1,2,3,4,6,8,12,24}（2）{1,2,3,4,5,6,7,8,9,10,11,12} 解答：（1）

（2）

38、针对图7.14中的每个哈斯图，写出集合以及偏序关系的表达式。

解答：

（a）集合为A{1,2,3,4,5}，偏序关系为{1,3,1,5,2,4,2,5,3,5,4,5}IA（b）集合为B{a,b,c,d,e,f}，偏序关系为{a,b,c,d,e,f}IB（c）集合为C{1,2,3,4,5}，偏序关系{1,2,1,3,1,4,1,5,2,4,2,5,3,4,3,5,4,5}IC

40、分别画出下列偏序集A,R的哈斯图，并找出A的极大元、极小元、最大元和最小元。

（1）A{a,b,c,d,e,f}，R{a,d,a,c,a,b,a,e,b,e,c,e,d,e}IA

R{c,d}IA（2）A{a,b,c,d,e}

解答：

（1）哈斯图为

极小元为a,f,极大元为e,f，无最大元、最小元（2）哈斯图为

极小元为a,b,c,e，极大元为a,b,d,e，无最大元、最小元

41、A{1,2,3....,12}，R为整除关系，B{x|2x4}，在偏序集A,R中求B的上界、下界、最小上界和最大下界。

解：下界即为公约数，2，3，4的公约数只有1，所以下界为1，最大下界也为1；

下界即为公倍数，2，3，4的公倍数只有12，所以上界为1，最大上界也为12；

P141:习题八

4、判断下列函数中哪些是满射？哪些是单射？哪些是双射？（2）f:NN,f(x)x22（4）f:N{0,1},f(x)01xisodd

xiseven（6）f:RR,f(x)x22x15

解答：（2）单射；（3）满射；（4）既不为单射也不为满射。

{1,2,3}

5、设X{a,b,c,d},Y，f{a,1,b,2,c,3}，判断下列命题的真假。

（1）f是从X到Y的二元关系，但不是X到Y的函数。（3）f是从X到Y的满射，但不是单射。解答：（1）真；（3）假

15、设A{a,b,c}，R为A上的等价关系，且R{a,b,b,a}IA，求自然映射g:AA/R。

解答： A/R{{a,b},{c}}

{a,b}g(x)cxa,b xc19、设f,g是从N到N的函数，且

x1f(x)0x（1）求f（2）说明f解答： x0,1,2,3x4x5g

x

g(x)23xiseven

xisoddg是否为单射、满射、双射？

（1）f3x1gg(f(x))20x2x0,2,5,7,9......x1,3x4x6,8,10,12.....（2）为满射，但是不为单射。

20、设f:NNN，f(x)x,x1（1）说明f是否为单射和满射，说明理由。

（2）f的反函数是否存在，如果存在，求出f的反函数；（3）求ranf。解答：

（1）xy时，x,x1y,y1，所以为单射； 而对1,3NN，不存在xN，使得f(x)x,x1，所以不为满射。

（2）不存在反函数，因为不是双射函数；（3）ranf{x,x1|xN}

22、对于以下集合A和B，构造从A到B的双射函数。（1）A{1,2,3},B{a,b,c}（2）A(0,1),B(0,2)

（3）A{x|xZx0},BN（4）AR,BR 解答： a（1）f(x)bc（2）f(x)2xx1x2 x3x(0,1)（3）f(x)x1

（4）f(x)ax(a0,a1)

篇2：离散数学集合论习题

1.设A、B、C为任意三个集合，判断下列命题的真与假。如命题为真，则证明之；否则，举反例说明。

（1）若AC=BC，则A=B

（2）若AC=BC，则A=B

（3）若AC=BC 且AC=BC，则A=B

2.证明ABAB.3.设A={1，2，3，4，5，6},下面各式定义的R都是A上的二元关系。试分别以序偶、关系矩阵、关系图三种形式分别写出R。

(1)R={|x整除y}；

(2)R={|x是y的倍数}；

(3)R={|(x-y)2A}；

(4)R={|x/ y是素数}。

4.设 R是A到B的二元关系，证明：对于A的任意子集A1和A2，R(A1∩A2)= R(A1)∩R(A2)当且仅当

 a∈A，b∈A，有R(a)∩R(b)= Φ.5.分别对下图中所给的两个关系，求Rn，nN。

篇3：《离散数学》课程教学探讨

关键词：离散数学,教学方法

离散数学是现代数学的一个重要分支, 是以研究离散量的结构和相互间关系为主要目标的一门计算机专业核心基础课程.它不仅是计算机科学的理论基础, 也是培养学生缜密思维、提高学生数学素养的主要课程.因此, 研究如何提高离散数学课程的教学水平和教学质量具有非常重要的意义.

一、激发学生学习兴趣

爱因斯坦说过:“兴趣和爱好是最大的动力.”兴趣是最好的老师, 学生只有对离散数学产生了兴趣, 才会主动去学习, 探究.因此在教学过程中, 教师应特别注重学生学习兴趣的培养, 充分调动学生的积极性, 使学生学得轻松愉快, 才能充分发挥学生的主观能动性.

对于任何一门课程来说, 第一次课都是很重要的, 往往决定了学生能否对这门课程产生兴趣.在离散数学的第一次课上, 教师应该介绍离散数学的组成部分和发展过程, 而集合论作为离散数学的基础和重要组成部分, 我们可以首先讲述下面这个小故事.

这是《堂吉诃德》中的一个故事:堂吉诃德的仆人桑乔·潘萨跑到一个小岛上, 成了这个岛的国王.他颁布了一条奇怪的法律:每一个到达这个岛的人都必须回答一个问题:“你到这里来做什么?”如果回答对了, 就允许他在岛上游玩, 而如果答错了, 就要把他绞死.对于每一个到岛上来的人, 或者是尽兴地玩, 或者是被吊上绞架.有多少人敢冒死到这岛上去玩呢?一天, 有一个胆大包天的人来了, 他照例被问了这个问题, 而这个人的回答是:“我到这里来是要被绞死的.”请问桑乔·潘萨是让他在岛上玩, 还是把他绞死呢?如果应该让他在岛上游玩, 那就与他说“要被绞死”的话不相符合, 这就是说, 他说“要被绞死”是错话, 既然他说错了, 就应该被处绞刑.但如果桑乔·潘萨要把他绞死呢?这时他说的“要被绞死”就与事实相符, 从而就是对的, 既然他答对了, 就不该被绞死, 而应该让他在岛上玩.小岛的国王发现, 他的法律无法执行, 因为不管怎么执行, 都使法律受到破坏.他思索再三, 最后让卫兵把他放了, 并且宣布这条法律作废.

通过这个故事不但可以让学生们了解什么是朴素集合论中的悖论, 而且让学生们知道离散数学所讲述的不仅仅是枯燥的定义和定理, 还和我们现实生活中的事物息息相关的, 从而让学生在第一堂课就对离散数学产生浓厚的兴趣.

二、适当选择教学内容

《离散数学》是一门相对于“连续数学”而命名的数学分支, 它包括多个彼此独立的数学分支, 主要有数理逻辑、集合论、代数系统和图论几大部分, 这些知识点具有或多或少的联系, 但是又自成体系, 每一部分都可作为一个相对独立的分支来进行教学.近年来所出版的一些教材又加入了离散概率等内容, 而与之相矛盾的是各学校在不断地缩减离散数学课程的学时数.如何在有限的学时内选择合理的教学内容成为该课程教学中面临的重要问题.

首先在内容的深度和广度上应进行更新, 修正有些教材的知识面过大、难度过深的教学安排, 以便更适合我们的教学对象, 收效较好;其次添加实际应用教学, 在教学中添加若干上机编程题、设计题和学科论文等训练内容, 使学生加深对离散数学的理解和认识;最后在教学内容上要强调基本方法和技能, 要求学生掌握重要定理的证明和一些常用的解题方法, 如数理逻辑中的命题逻辑、谓词逻辑推理方法、关系论中的几种关系、函数映射中的方法, 等等.

三、科学运用教学方法

《离散数学》课程具有抽象性强而且内容多的特点.在传统的教学模式下, 教师向学生传播知识, 一般通过板书向学生传授, 其输出量比较低, 常常会受到板面的限制和时间的限制, 在此过程中花费大量时间, 不利于讲解和提问互动, 学生会难以理解和记忆;多媒体教学传递的信息量大, 速度快, 课前制作的课件可以节省上课板书时间, 把概念之间的联系以结构图的形式给出, 知识点清晰, 框架清楚, 易于学生记忆, 但在解题时不利于展示数学思维的过程.因此, 在实际教学中, 要适当地把板书形式和多媒体形式教学结合起来, 对于概念定理、公式推导等叙述性内容, 采用多媒体演示;对于例题的演算等思维性内容, 采用传统的板书形式, 一步步推导, 展示数学思维的全过程.这种传统教学方式与现代教学手段相结合的教学方法, 保证了上课时间的充分利用, 增加了课堂信息量, 又不至于使学生陷入一种“看电影”的状态, 很受学生的欢迎.

另外, 在做好课堂教学的同时, 还要充分利用网络辅助教学平台.在条件允许的情况下, 建立离散数学教学网站, 网站将包括以下内容:课程介绍、教学大纲、授课计划、教师队伍、电子教案、学生自测系统、习题库、网上答疑、实验指导、参考文献目录、教学录像等.另外本着方便学生的目的, 网站还提供与本课程相关的外文资料和电子图书, 以及方便学生考研的模拟试题和各高校历年考题.

参考文献

[1]刘叙华, 虞恩蔚, 姜云飞.离散数学[M].北京:中国广播电视大学出版社, 1993.

[2]屈婉玲, 耿素云, 张立昂.离散数学:第2版[M].北京:清华大学出版社, 2008.

[3]何中胜.离散数学教学中的问题分析与对策研究[J].高等理科教育, 2007 (5) :107-109.

[4]王伟静, 彭慧伶.离散数学课程教学问题分析与对策研究[J].科技创新导报, 2009 (18) :150.

篇4：浅谈《离散数学》的教学

摘要：为了激发学生的学习热情，培养其思维能力和应用能力，根据离散数学课程教学的特点，笔者结合课程教学经验，对离散数学教学进行了研究.文章提出一些教学方法和手段的改革，在实际教学中起到了一定的作用，提高了教学质量.

关键词： 离散数学，教学方法，教学手段

【中图分类号】O158-4

On the Teaching "Discrete Mathematics" in

Chenxue Gang Zhou Jiquan

（North China Electric Power University Mathematics， Beijing， 102206， China）

Abstract： In order to stimulate students' enthusiasm for learning， develop their thinking skills and ability， according to the characteristics of Discrete Mathematics Instruction， author of Teaching experience， discrete mathematics teaching were studied. This paper presents some of the reform of teaching methods and means， in the actual teaching has played a certain role in enhancing the quality of teaching.

Keywords： discrete mathematics， teaching methods， teaching means

《离散数学》是计算机科学中重要的基础理论课程之一，它不仅是许多计算机专业课的必备基础，而且对培养学生抽象思维能力和逻辑推理能力有着重要的作用.然而采用以往的教学方法，教学效果往往不够理想.一方面，离散数学知识的分散性令许多学生感到无从下手.另一方面，在传统的离散数学教学中，往往采用“纯数学”教学方法，学生不能很好地体会离散数学对计算机科学的重要意义，所以学习积极性不高.因此，通过教学方法和手段的改革来激发和增强学生的学习兴趣，从而培养学生的创新思维和综合能力，是离散数学教学中非常迫切的需求.本文结合作者近年来从事离散数学课程教学的经验，从教学内容、教学方法、教学手段等方面进行了一些初步探讨.

1精选教学内容

《离散数学》教学内容主要包括数理逻辑、集合论、代数结构及图论等几大分支.各分支均有悠久历史.如果这几部分的内容都要详细讲授，时间上来不及，所以在在教学过程中对讲授内容的选择应当有所侧重.比如简单介绍集合论的理论基础，重点是如何利用集台论的方法解决实际应用问题.在二元关系这部分，重点是二元关系的几个与性质相关问题的论证方法的训练.在数理逻辑上通过将一般命题公式和一阶逻辑公式化成范式，达到强化训练学生逻辑演算能力.图论部分重点放在基本概念的理解和实际问题的处理上，通过对相关定理及其证明思路的理解来体会图论的研究方法.代数系统这部分内容重点放在群论上，尤其要在代数系统、群、子群、循环群、变换群、正规子群的概念及相关问题的理解上下功夫.

2 教学方法探讨

2.1 增加讨论课

老师首先选定讨论的课题，学生分组准备查询相关的文献，并形成自己观点.在讨论课上大家共同交流探讨，从而加深对这门课程的认识.最后各小组完成论文的书写.该方法不仅可以提高学生对离散数学重要性的认识，还可以提高学生互相协作的能力以及书写论文的能力.

2.2 增加趣味性，激发学生的学习兴趣.

“兴趣是 最好的老师”，只有激发起学生的学习兴趣，他们才有真正自主学习的欲望.在教学过程中，根据具体的知识点，介绍它的发展史或者引入趣味问题，增加了学生学习离散数学的兴趣，拓宽了学生们的知识面，提高了学生对离散数学课程学习的积极性与主动性.

2.3 注重归纳与小结

离散数学的内容虽然多且散，但通过归纳和小结，可以用一条主线贯穿始终.离散数学讨论的内容主要包含系统中涉及到的静态（基本概念）与动态（运算、操作、推理）.如集合论中是元素（静态）及其上的运算（动态）；代数系统中是集合（静态）及运算（动态）；数理逻辑中是公式（静态）和推理（动态）.通过归纳与小结，学生能够理清头绪，提高学习效率.

3 教学手段改革

3.1 教学网站建设

信息技术对提高教学质量具有重要的影响，必须予以高度重视.为了提高教学质量，我们建设了一个教学支撑网站，一方面大力推进信息技术在教学中的实际运用，促进教学手段和教学方法现代化；另一方面以此提高教与学的效率.

3.2 重视学生作业，定时测验

离散数学的知识不经过学生的独立思考和多做练习是无法牢固掌握的，因此一定要给学生留一定数量的课后习题.但大部分学生不可能把课本上的习题全部做完，教师也不可能完全批阅.这就要求教师布置作业要选其精华，选题必须要有一定的深度和广度，要覆盖所学的内容，尽量选有启发性质的习题.对于学生的作业，要认真仔细批改，将作业中暴露出来的普遍问题，要进行课堂讲评.通过讲评作业，帮助学生澄清模糊和错误的认识.

3.3 新的考核方式

传统的考核方法就是试卷考试，考察学生的基本知识和基本技能，以及解难题的能力.我们尝试做了一些考核方法的改革，把原来的试卷考试和平时的考核两部分，改成了三部分成绩的统一， 即添加了一个新的内容：写离散数学的论文.把它的评定结果作为成绩的一个重要部分.所写论文必须要求观点明确、主题鲜明和论述严谨，并且具有一定的创新.

4 结束语

总之，要把离散数学这一门课教好，教师就要不断研究新的教学方法和手段，认真掌握教学规律，借助于现代化教学手段，提倡“启发”式教学.教师只要具有扎实的理论功底，并具有对学生高度负责的精神，就一定能够达到良好的教学效果.

参考文献：

[1]赵青杉，孟国艳.关于离散数学教学改革的思考[J].忻州師范学院学报，2005，21（5）：6 .

[2]耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2001.

[3]翁梅，刘倩，冯志慧等.“离散数学”课程教学实践与探索[J].计算机教育，2004（12）：62—63.

[4]钟敏，时念云.改革课程实验提高离散数学教学质量 [J].计算机教育，2008，18.

[5] 张艳华，周雪琴，马新娟，王举辉，张立红. 基于卓越工程师的“离散数学”教学改革探索[J]. 当代教育理论与实践. 2013（12）

篇5：离散数学习题集

数理逻辑(离散数学一分册)王捍贫 北京大学出版社 定价：15元

集合论与图论(离散数学二分册)耿素云 北京大学出版社 定价：19元

代数结构与组合数学(离散数学三分册)屈婉玲 北京大学出版社 定价：21元

离散数学习题集——数理逻辑与集合论分册 耿素云 北京大学出版社 定价：11.5元

离散数学习题集——图论分册 耿素云 北京大学出版社 定价：8元

离散数学习题集——抽象代数分册 张立昂 北京大学出版社 定价：8.8元

离散数学 左孝凌 刘永才 上海科学技术文献出版社 定价：16元

篇6：离散数学复习题

• 设命题p，r的真值为1，命题q，s的真值为0，则（p→q）(﹁r→s)的真值

为。

• 只要4不是素数，3就是素数，用谓语表达式符号化为。

• D=｛｝，则幂集ρ(D)=

• A={a,{b}}，B=｛｝，则A×B=

• 若集合A，B的元素个数分别为|A|=m,|B|=n,则A到B有种不同二元关系。• 设A=｛1,2,3,4｝，B=｛4,5，6,7｝，R=｛<1,4>，<1,6><2,4>，<3,5>，<3,6>｝是由A

到B的二元关系，则domR=，ranR=

• I A是集合A上的恒等关系，A上的关系R具有性当且仅当IAR。• 二元关系R是等价关系，当且仅当的R是。

9.设K4是有4个点的无向完全图，则K4有条边。

10.无向图G是欧拉图当且仅当。

11.在任何无向图这，所有顶点的度数之和等于边数的倍。

12.设K5是有5个点的无向完全图，则K5有条边。

13.无向图G是欧拉图当且仅当。

计算题

• 求公式（PQ）→（QR）的主析取范式

• 集合A=｛a,b,c｝,R={,,,}是集合A上的二元关系，求R的自反

闭包r(R),对称闭包s(R)和传递闭包t(R)(用矩阵运算)，并画出各闭包的关系图。• 设图G

• 写出G的邻接矩阵

• 求各结点的初度，入度

• 求V3到V2长度是3的路的数目

• 设集合A=｛1,2，3,4,6,8，12｝，R是A上的整除关系，• 画出偏序图的哈斯图；

证明题

• 在自然推理系统p中构造下面推理的证明

前提：﹁r，﹁pr，（q）→p

结论：q→﹁

• 在自然系统p中构造下面推理的证明

前提：pq,p→r,q→s

篇7：离散数学复习题1

1、给出的真值表

2、证明为永真式 谓词量词和推理

1、使用量词和谓词表达不存在这一事实

2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门考试蕴含结论“通过考试的某个人没有读过书” 集合、函数、数列与求和

1、全集为，求集合A=的位串？它的补集的位串是什么？写出集合A=的所有子集，写出集合

2、从集合到集合能定义多少个函数？下面给出的函数其定义为：该函数是双射吗？是满射吗？该函数是否存在逆函数？如果存在请给出其逆函数。计数

1、计算机系统的美国用户有一个6～8个字符构成的密码，其中每个字符是一个大写字母或数字，且每个密码必须至少包含一个数字，问总共有多少个合适的密码？

2、在30天的一个月里，某棒球队一天至少打一场比赛，但最多打45场。证明一定有连续的若干天内这个球队恰好打了14场比赛

3、证明n个元素的集合中允许重复的r组合数等于

4、按照字典顺序生成整数1，2，3的所有排列（不允许重复），在362541后面按照字典顺序的下一个最大排列是什么？找出在1000100111后面的下一个最大的二进制串。关系

1、求下面给出关系R的自反闭包、对称闭包和传递闭包的0-1关系矩阵，其中

2、S是所有比特串的集合，关系定义为当s=t或者s和t的长度至少是3，且前3个比特相同时具有关系，例如0101，0011100101，但01010，0101101110。证明是S上的等价关系，由产生的S的等价类是那些集合？

3、偏序集（{2,4,5,10,12,20,25},|）的那些元素是极大的，那些元素是极小的？ 图与树

1、在下图所示的图中，从a 到d的长度为4的通路有几条？该图是否是Euler图，是否是Hamilton图，该图的度序列是什么？该图是否可平面，如果是请给出平面画图，该图的点色数和边色数等于多少？给出该图的一个生成树，2、求下面赋权图从a到z的最短距离是多少？最短路径是什么？（画图给出标号过程）

3、用哈夫曼编码方法来编码下列符号，这些符号具有下列频率：A:0.08，B:0.10，C:0.12，D:0.15，E:0.20，F:0.35,该编码方法编码一个字符的平均位数是多少？

篇8：离散数学初识与应用

离散数学作为现代数学的一个十分重要的分支, 同时是计算机科学和相关技术的理论基础, 所以又被人们戏称为计算机的数学[1]。一般的, 广义离散数学的概念包含了图论、数论、集合论、信息论、数理逻辑、关系理论、代数结构、组合数学等等概念, 现代又加上了算法设计、组合分析、计算模型等应用方向, 总的来说, 离散数学是一门综合学科, 而其应用则遍及现代科学与技术的诸多领域。

二、离散数学在高中数学中的体现

离散数学的概念对于我们高中生来说可能相对陌生, 但其实, 我们高中数学中很多知识都常常涉及到离散数学。相较于我们平时接触较多的连续性数学而言, 离散数学侧重于思维方式和逻辑过程的应用于体现, 可以说是数学中一个非常特别的分支, 在应用的过程中主要是构建起一种专属的思维方式。这种方式既有别于传统的对事物的理解与推论, 还与常规的数学解题思维有着很大的不同。而高中阶段像我们学习所涉及的数理逻辑、集合、数列等知识都是离散数学的基础概念。

以一个简单的高中数学命题的问题为例:高中数学的命题关系的讨论, 其中常见的命题形式有:若p则q, 以及与其相关的原命题、逆命题、否命题、逆否命题的形式与真假关系, 和“且、 或、非”三种简单的逻辑连接词。这是我们在高中数学中常常接触的一类问题, 而延伸至离散数学的概念下, 其实只是更深入的讨论和研究了这一问题, 并建立起独特的逻辑概念, 这种数理的逻辑也是计算机编程的基础。

三、离散数学的应用

(一) 数学思维在计算机软件编程中的应用

随着计算机科技的逐步发展, 信息技术在日常生活中的应用目前越来越为广泛。而软件程序作为各种技术问题的关键, 其发展更是日新月异, 而算法被称为软件编程的基础。数学思维的运用贯穿软件与计算机科学的始终。

其实当我们对编程有了一定的了解后可以发现, 需要通过编程实现的很多要求都可转化为数学逻辑的讨论与梳理。当计算机需要解决一个具体的问题时, 必须运用应用数据结构的知识。而对于问题中所需要处理的数据, 就需要从具体的问题中通过一定方式建立起一定的数学模型。然后再针对这一数学模型建立起相应的算法, 最后通过编程实现对算法的应用, 然后经过反复测试、调整直至确定最终的解答。上述过程即一个编程的过程, 从提取模型、建立算法到问题解决的过程都离不开离散数学的知识运用。

(二) 离散数学与人工智能

人工智能是现在非常热门的一个议题, 作为计算机学科发展的一个非常重要的方向, 人工智能中对于离散数学的应用主要是数理逻辑部分充当智能思维的应用, 即形成类似人类的思考方式。数理逻辑包括了命题逻辑与谓词逻辑:所谓命题逻辑就是以命题为单位进行的前提与结论之间推理过程的研究;而谓词逻辑则侧重于研究句子内在的联系。一般的, 人工智能现在大致分为两个流派, 即连接主义流派和符号主义流派。在符号主义流派里, 认为现实世界的各种事物可以用符号的形式表示出来, 而最主要的理论就是人类的自然语言是可以用符号表示出来的。语言的符号化, 是数理逻辑研究的最基本的内容, 所以计算机的智能化是以将人类的语言符号化为机器可以识别的符号为前提的, 通过这样的方式才能使计算机进行推理, 才能具有智能。由此可见数理逻辑中重要的思想、方法及内容贯穿到人工智能的整个学科。

(三) 现实生活中的离散数学

其实离散数学除了在计算机、软件技术等领域中有着重要的应用价值外。其在金融分析、交通规划、企业管理、战争指挥等广泛的领域也有着重要的应用。正是看到了离散数学对于未来科技发展的重要意义, 很多国家都已将离散数学列为新世纪未来应当重点发展的数学领域之一。甚至美国有一家公司直接以离散数学来命名, 他们运用离散数学的方法来分析解决企业管理上的问题, 进而提高企业的效益。此外, 试验设计也是具有很广泛发展潜力和很大应用价值的一门新兴学科, 它的数学原理就是组合设计。通过使用组合设计的方法解决工业行业的试验设计问题, 已有很多专门的公司在进行这方面的研究。最近, 一位德国著名的离散数学家利用了离散数学的方法对药物结构进行深入研究, 极大节约了制药行业的研制成本, 引起了制药业的广泛关注。

(四) 离散数学重要性

离散数学在计算机以及软件领域都发挥着十分重要的作用, 甚至现代计算机科学的理论基础都可以被称之为离散数学的一个分支。在其中大量的采用了离散数学中基本概念、知识以及基础的研究方法。 离散数学的学习不但为未来大学的进阶学习提供极其必要的理论基础, 而且通过对离散数学思想和方法的学习也反过来提高了我们自身的逻辑思维能力和创造性思维能力。

四、总结

随着科技信息时代的到来, 计算机科学发展如火如荼, 人工智能技术方兴未艾, 工业革命时代以来一直以微积分为基础的连续数学的主导地位已经发生了显著的变化, 离散数学正逐步成为科学领域新突破的土壤, 其重要性逐渐被人们认识。也有越来越多的人把更多的经历投入到这一领域的研究中。

离散数学是一个非常注重思维逻辑的数学学科分支, 对于离散数学的学习过程可以看作是一个对数学思维构建的锻炼的过程。通过本文上述的讨论, 同时也可以看到, 所有的理论学习都是一个循序渐进的过程, 我们不应当放过自己学习中每一个细微的知识点, 扎实的基础知识和严谨的逻辑思维能力都对的未来进阶学习有非常有益的帮助。

参考文献

[1]傅彦, 顾小丰, 王庆先等.离散数学及其应用[M].北京:高等教育出版社, 2007.