千文网小编为你整理了多篇相关的《趣味离散数学学后总结1(合集)》，但愿对你工作学习有帮助，当然你在千文网还可以找到更多《趣味离散数学学后总结1(合集)》。
第一篇：离散数学总结
一、课程内容介绍：
1．集合论部分： 离散数学学习总结
集合论是离散数学中第一个抽象难关，在老师的生动讲解下，深入浅出，使得集合论成了相当有趣的知识。只是对于以后的应用还不是很了解，感觉学好它很重要。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如： 方程x2－1＝0的实数解集合；
26个英文字母的集合；
坐标平面上所有点的集合；
集合通常用大写的英文字母来标记，例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。
表示一个集合的方法有两种：列元素法和谓词表示法，如果两个集合的交集为，则称这两个集合是不相交的。例如B和C是不相交的。
两个集合的并和交运算可以推广成n个集合的并和交： A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An} A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}
2．关系
二元关系也可简称为关系。对于二元关系R，如果∈R，可记作xRy；如果R，则记作xy。
例如R1={,}，R2={,a,b}。则R1是二元关系，R2不是二元关系，只是一个集合，除非将a和b定义为有序对。根据上面的记法可以写1R12，aR1b，aR1c等。
给出一个关系的方法有三种:集合表达式，关系矩阵和关系图。 设R是A上的关系，我们希望R具有某些有用的性质，比如说自反性。如果R不具有自反性，我们通过在R中添加一部分有序对来改造R，
得到新的关系R'，使得R'具有自反性。但又不希望R'与R相差太多，换句话说，添加的有序对要尽可能的少。满足这些要求的R'就称为R的自反闭包。通过添加有序对来构造的闭包除自反闭保外还有对称闭包和传递闭包。
3．代数系统
代数结构也叫做抽象代数，主要研究抽象的代数系统。抽象的代数系统也是一种数学模型，可以用它表示实际世界中的离散结构。例如在形式语言中常将有穷字符表记为∑，由∑上的有限个字符（包括0个字符）可以构成一个字符串，称为∑上的字。∑上的全体字符串构成集合∑*。设α,β是∑*上的两个字，将β连接在α后面得到∑*上的字αβ。如果将这种连接看作∑*上的一种运算，那么这种运算不可交换，但是可结合。集合∑*关于连接运算就构成了一个代数系统，它恰好是抽象代数系统--半群的一个实例。抽象代数在计算机中有着广泛的应用，例如自动机理论、编码理论、形式语义学、代数规范、密码学等等都要用到抽象代数的知识。代数结构的主要研究对象就是各种典型的抽象代数系统。
构成一个抽象代数系统有三方面的要素：集合、集合上的运算以及说明运算性质或运算之间关系的公理。请看下面的例子。
整数集合Z和普通加法＋构成了代数系统〈Z,＋〉，n阶实矩阵的集合Mn(R)与矩阵加法＋构成代数系统〈Mn(R),＋〉。幂集P(B)与集合的对称差运算也构成了代数系统
。类似这样的代数系统可以列举出许多许多，他们都是具体的代数系统。考察他们的共性，不难发现他们都含有一个集合，一个二元运算，并且这些运算都具有交换性和结合性等性质。为了概括这类代数系统的共性，我们可以定义一个抽象的代数系统，其中 A是一个集合，是A上的可交换、可结合的运算，这类代数系统实际上就是交换半群。
为了研究抽象的代数系统，我们需要先定义一元和二元代数运算以及二元运算的性质，并通过选择不同的运算性质来规定各种抽象代数系统的定义。在此基础上再深入研究这些抽象代数系统的内在特性和应用。
4．图论部分
图论是作为我们计算机专业的一门很有用处的知识，也是新兴的一个数学分支，在计算机迅速发展的同时，图论也迅速发展。因此，图论给我们以一种神奇的感觉，在学习图论中，老师总是把图论分析得很透彻，学起来很有趣，同时也很简单。图论在数据结构方面的应用极其广泛，对我们学计算机专业的人来说，是一门必须要学好的知识。
一个图可以用一个图形表示，定义中的结点对可以是有序的，也可以是无序的，若边所对误码的结点对（a,b）是有序的，刚称L是有向边，a称为L的起点，b称为L的终点，若边L所对应的结点对（a,b）是无序的，则称L是无向边。
5．数理逻辑部分
数理逻辑作为离散数学的最后一部分，充满着对逻辑思维的挑战，同时锻炼了我们思考问题的严密性，当然最重要的是学会如何用数学方法去分析逻辑问题。
数理逻辑又称符号逻辑，它是用数学方法支研究抽象思维的规律的应用学科，1.命题：把能判断真假的陈述句称为命题，作为命题的陈述句表达的判断结果称为命题的真值。命题公式、对偶与范式、命题演算的推理等等。
二、学习总结与体会
在本学期一开始学习这门课程时，老师就明确的告诉我们这门课程很重要，是我们大学中专业课程的核心课程，同时由于难度系数较高，故本门课程较为难学。总的来说，一个学期下来，自认为比较好地掌握了离散数学的基础知识，并在平时的各方面得到了很好的应用。
对于离散数学，在刚开始学习的不知道他的重要性，以为他与高等数学一样，或者学习的时候的时候，一定要有高等数学的知道，其实不然，当我开始学习之后才知道，只有掌握了高等数学以及线性代数等相关知道才能更好的学习离散数学。而且，作为计算机科学专业的学生，离散数学当中所涉及到相关知道，对于我们是至关重要的。比如，关系、群、路径、图的矩阵表示、树等内容，都是在计算机程序设计以及相关
信息当中要用到的内容。
所以学习了离散数学课之后，我的收获是很多的。对于一些数学相关的知识有了不同的理解，学会了用不同的方法去解决程序设计方法以及将计算机和数学有机联系起来，不过在学习的过程中也遇到了一些难题，最为突出的，就是书本上的和老师讲解的都还是比较的简单，自己在课堂上也能听懂，但是到具体的应用就很困难了。
特别是不看书，就很多的东西都还给了老师，所以，我会严格的要求自己，学过的东西，都要下来练习，尽量的多做一些习题，尽量的把学过的数学基础知识练熟悉，这样才能够提高自己专业知识，提高自己解决问题的能力。
有一点让我遗憾的是没有学完这门课程，但在这门课程快要结束的时候，我总结了学习中遇到的一些问题，最为突出的是，书本上的知识与老师讲的都比较容易懂，可是在真正运到实际生活中时，就不能将老师所讲的知识点与书上所罗列的。因此，针对这一情况，在以后的学习中我会严格要求自己，多参加实践，只有这样，，才能够提高运用知识，解决问题的能力。
三、教学建议
1.在课程开设方面，对于离散数学等相关基础、重要的课程，应当在大一或大二开设，不应放在大三下期，这样对于我们学习时也有一定的帮助。我希望这一本书上能多一些练习题，以便我们学过了，下课了也有很多的练习题做，来巩固课堂上的新内容。同时，我也希望在有些程序部分，能给出详细的注释语句。
2.相互学习，教师应当努力使现代教学手段与传统教学手段有机结合，相互取长补短。在教学实施中既能发挥教学手段的优势，又能善于运用传统方式，使教学效果达到最佳。建议能给一些学生练习的时间，这样我们才能对学过的新内容有一个巩固的时间，其实这样更有助于以后的教学，前面的基础知识打牢了，后面的学习更愉快。
3.提升技能：教师应重新认识离散数学与计算机联系。同时，要始终把学生放在讲课对象的中心位置，特别是在课余时间，建议由老师组
织学生进行分组，大家共同学习，由于现今的大学学习较为分散，很多时候同学们都不同在课堂上完成任务，只能下来之后继续完成，所以组建学习小组后，通过完成任务等方式，让学生学习到更多的知识点。学会更多的内容。
4.任务引领：充分调动学习学习积极性让学习在完成任务的过程当中，充分学习到多媒体课件的制作以及多媒体信息的处理等等。
第二篇：趣味离散数学学后总结
《趣味离散数学》学后总结
0921111028王蓉
数学与应用数学学习过程是一个扎扎实实积累的过程，不能打马虎眼。离散数学是理论性较强的学科，学习离散数学的关键是对离散数学有关基本概念，如集合论、数理逻辑和图论的准确掌握，对基本原理及基本运算的运用，并要多做练习。
《离散数学》的特点如下：
1、知识点集中，概念和定理多：《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。
2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。《离散数学》的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法、构造性证明法），同一个题也可能有几种方法。但是《离散数学》证明 题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法。同时要善于总结，
在学习《离散数学》的过程，对概念的理解是学习的重中之重。一般来说，由于这些概念（定义）非常抽象（学习《线性代数》时会有这样的经历），初学者往往不能在脑海中建立起它们与现实世界中客观事物的联系。这往往是《离散数学》学习过程中初学者要面临的第一个困难，他们觉得不容易进入学习的状态。因此一开始必须准确、 全面、完整地记住并理解所有的定义和定理。具体做法是在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能够适应，并为后续学习打下良好的基础。
学数学就要做数学，《离散数学》的学习也不例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学思维方法。要做到这一点，学习者将要面临的第二个困难是需要花费大量的时间做课后习题。但是切记离散数学的题目数量自然是无穷无尽的，但题目的种类却很有限。尤其是在命题证明的过程中，最重要的是要掌握证明的思路和方法。解离散数学的题，方法是非常重要的，如果拿到一道题，立即能够看出它所属的类型及关联的知 识点，就不难选用正确的方法将其解决，反之则事倍功半。例如在命题逻辑部分，无非是这么几种题目：将自然语言表述的命题符号化，等价命题的相互转化（包括化为主合取范式与主析取范式），以给出的若干命题为前提进行推理和证明。相应的对策也马上就可以提出来。以推理题为例，主要是利用P、T规则，加上蕴涵和等价公式表，由给定的前提出发进行推演，或根据题目特点采用真值表法、CP规则和反证法。由此可见，在平常学习中，要善于总结和归纳，仔细体会题目类型和此类题目的解题套路。如此多作练习，则即使遇到比较陌生的题也可以较快地领悟其本质，从而轻松解出。
因此，只要肯下功夫，人人都能有扎实的基础，拥有足够的数学知识，特别是能大大提高本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门数学科学的专业主干课程时，都不会遇上任何思维理解上的困难。
第三篇：离散数学复习题
逻辑
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,该编码方法编码一个字符的平均位数是多少？
4、下面树的高度是多少？那些节点是内部节点，那些节点是叶子节点，该树是否是3元正则树？分别给出该树节点的前序、中序、后序遍历的节点访问次序
第四篇：离散数学练习题
1、下列句子是简单命题的是（ ）
A)3是素数。B) 2x+3
5C)张三跟李四是同学吗？D) 我在说谎。
2、下列公式不是永真式的是（ ） ．．
A)((p∧q))→p)∨rB)p→(p∨q∨r)
C)┓(q→r) ∧rD)(p→q)→(┓q→┓p)
3、设命题公式G┓(p→q)，Hp→(q →┓p)，则G与H的关系是( ) 。
A) GHB) H→GC) H => GD) G => H
4、下列命题不为真的是（ ） ．
A)Φ ΦB)Φ∈Φ
C){a,b}∈{a,b,c,{a,b}}}D){a,b}{a,b,c,{a,b}}
5、1到300之间（包含1 和1000）不能被
3、5和7整除的数有（ ）个。
13、下列运算在指定集合上不符合交换律的是（）。
A)复数C集合上的普通加法B) n阶实矩阵上的乘法 C)集合S的幂集上的∪D) 集合S的幂集上的
14、下列集合对所给的二元运算封闭的是（）
A) 正实数集合R+和。运算，其中。运算定义如下：a,b∈R+，a。b=ab-a-b B) n∈Z+，nZ={nZ|z∈Z}，nZ关于普通的加法运算 C) S={2x-1|x∈Z+}关于普通的加法运算
D) S={x|x=2n, n∈Z+}，S关于普通的加法运算
15、设V=,其中*定义如下：a，b∈Z, a*b=a+b-2 ,则能构成的代数系统是（）。
A)半群、独异点、群B) 半群、独异点C)半群D) 二元运算
16
上有○
A)138B)120C)68D)12
46、设A, C, B, D为任意集合，以下命题一定为真的是（ ）
A)A∪B= A∪C =>B=C B)A×C= A×B =>B= C
C)A∪(B×C) = (A∪B)×(A∪C)D)存在集合A,使得A A ×A
7、设A={1,2,3,4}，R={,,,,} 是A上的关系，则R的性质是（ ）
A)既是对称的也是反对称的 B)既不是对称的也不是反对称的 C)是对称的但不是反对称的D)不是对称的但是反对称的
8、设R是A上的关系，则R在A上是传递的当且仅当（ ）
则这4个运算中满足幂等律的是（ ）
17、在上述四个运算中有单位元的是（ ）
18、在上述四个运算中有零元的是（ ）
19、与命题公式P（QR）等值的公式是()
A) (PQ)RB) (PQ)RC) (PQ)RD) P(QR)
20、下列集合都是N的子集，能够构成代数系统V=的子代数的是（ ）
A)｛x| x∈N∧x与5互为素数｝B) ｛x| x∈N∧x是30的因子｝ C) {x| x∈N∧x是30的倍数}D) {x|x=2k+1, k∈N }
二、填空题(1分/空，共20分。请将正确答案填在相应的横线上。)
1、公式┓(p∨q) →p的成假赋值为00__,公式┓(q→p) ∧p的成真赋值为。
2、设Ａ，Ｂ为任意命题公式，Ｃ为重言式，若Ａ∧ＣＢ∧Ｃ，那么ＡＢ是重言式（重言式、矛盾式或可满足式）。
3、f：N->N×N，f(x)=,A={5},B={,},则f(x)是A)IA RB)R=R-1C)R∩IA ΦD)R。RR
9、设A={1,2,3,4,5,6,7,8},R为A上的等价关系R={|x,y ∈ A ∧ x=y(mod 3)}
其中， x=y(mod 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。则1的等价类，即[1]，为（ ）
A) {1,4,7}B) {2,5,8}C) {3,6}D) {1,2,3,4,5,6,7,8}
10、当集合A=Φ且B≠Φ时，则BA结果为（ ）
A)ΦB){Φ} C){Φ, {Φ}}D)错误运算
11、函数f:R→R,f(x)= x2-2x+1,则f(x)是（）函数。
A)单射B)满射C)双射D)不是单射，也不是满射
12、设X={a,b,c,d},Y={1,2,3}，f={,,}，则以下命题正确的是()
A) f是从X到Y的二元关系，但不是从X到Y的函数 B) f是从X到Y的函数，但不是满射的，也不是单射的 C) f是从X到Y的满射，但不是单射 D) f是从X到Y的双射
双射）函数，A在f下的像f(A)＝_{}_，B在f下的完全原像f-1(B)=____。
4、已知公式A中含有3个命题变项p,q,r，并且它的成真赋值为000，011，110，则A的主合取范式为（用极大项表示）__M∧_M∧_M∧_M∧_M，主析取范式为（用极小项表示）
5、公式x(F(x,y)→yG(x,y,z))的前束范式为_
6、列出从集合A={1,2}到B={1}的所有二元关系。
7、设A为集合且∣A∣=n，则A共有nP(A)有n
8、设 f，g，h ∈RR 且f(x)=x+3, g(x)=2x+1, h(x)=x/2, 则复合函数
⑦ x (F(x)∧G(x)→H(x))前提引入 ⑧ F(a)∧G(a)→H(a)T ⑦UI⑨ F(a)∧G(a)T ③ ⑥合取 (10)H(a)T ⑧ ⑨ 假言推理
f。g。h(x)=__，f。g。h (x)=_____。
9、含有n个命题变项的公式共有_____个不同的赋值，最多可以生成___个不同的真值表；n个命题变项共可产生___n_____个极小项（极大项）；含n个命题变项的所有有穷多个合式公式中，与它们等值的主析取范式（主合取范式）共有___2^2___种不同的情况。
10、已知集合A={,{}}，则A的幂集P(A)＝_____。
n
n
n
五、设A={1,2,3,4}，在A×A上定义二元关系R，，∈A×A，
Ru+y=x+v
(1) 证明R是A×A上的等价关系
(2) 确定由R引起的对A×A的划分。(5分)
三、利用公式的主合取范式判断下列公式是否等值。（5分）
p→(q→r)与 (p∧q) ∨r p→(q→r)
p∨(q∨r) p∨q∨r M6
(p∧q)∨r
(p∨q) ∨r p∨q)∨r M6
(1)证明: ∈ A×A => x+y=y+x=> ∈ R∴R是自反的 ∈ A×A ,
R => x+v=y+u=> R∴R是对称的 ,∈ A×A ,
R ∧ R=> x+v=y+u ∧ u+n=v+m
=> x+v+u+n=y+u+v+m => x+n=y+m => R ∧∴R是传递的
(2)
解:{{,,,},{,,},{,},{,},{,},{,,}}
四、符号化命题，并推理证明(给出每个符号的准确含义，及每一步推理的根据)。（5分）
每个科学工作者都是刻苦钻研的。每个刻苦钻研而又聪明的人在他的事业中都将获得成功。华有为是科学工作者并且是聪明的，所以华有为在他的事业中将获得成功。
六、A= {1,2,3,4,6,8,12}，R是A上的整除关系，请作出偏序集的哈斯图，给出关系矩阵，并
求出A的极大元、极小元、最大元和最小元。若B={2,3,4}，求出B的上界，下界，最小上界，最大下界。（5分）
解:
首先符号化：M(x)：x是科学工作者；F(x)：x是刻苦钻研的；G(x)：x是聪明的；H(x)：x
在事业中获得成功；a：华有为。
前提： x(M(x)→F(x)）， x (F(x)∧G(x)→H(x)),M(a) ∧ G(a)
结论：H(a)
证明：① M(a) ∧ G(a)前提引入 ② M(a)T ①化简规则 ③ G(a)T ①化简规则 ④ x(M(x)→F(x)）前提引入 ⑤ M(a)→F(a)T ④
⑥ F(a)T ② ⑤ 假言推理
解:A的极大元为
8、12,极小元为1， 无最大元，最小元为1。
B的上界为12，下界为1，
最小上界为12，最大下界为1。
七、在自然推理系统P中构造下面推理的证明。（5分） (1) 前提：(p∨q) →(r∧s),(s∨t) →u
结论：p→u (2) 前提：x(F(x) →(G(a) ∧ R(x)))，x F(x).九、证明下列恒等式 A-(B∪C) = (A-B)∩(A-C)。（5分） 证明：A-(B∪C)
结论： x (F(x) ∧ R(x)).(1)证明：① p附加前提引入规则② p ∨ q①附加规则③ (p ∨ q) →( r ∧ s)前提引入
④ r ∧ s②③ 假言推理⑤ s④化简规则⑥ s ∨ t⑤附加规则⑦ (s ∨ t) → u前提引入
⑧ u⑥ ⑦假言推理
(2)证明：① x F(x)前提引入② F(b)① EI③ x(F(x) →(G(a) ∧ R(x)))前提引入④ F(b) →(G(a) ∧ R(b))③ UI
⑤ G(a) ∧ R(b)② ④假言推理⑥ R(b)⑤化简⑦ F(b) ∧ R(b)②⑥合取⑧x (F(x) ∧ R(x))⑦EG
八、设有理数集合Q上的 * 运算定义如下：a，b∈Q, a*b=a+b-ab 。请指出该运算的性质，并求出其单位元、零元及所有可能的逆元。（5分）
解：(1)因为a*b=a+b-ab =b+a-ba=b*a，所以运算满足交换律。
(2)因为(a*b)*c=( a+b-ab)*c= a+b-ab+c-( a+b-ab)c=a+b+c-ab-bc-ac+abca*(b*c)=a*(b+c-bc)=a+b+c-bc- a(b+c-bc)= a+b+c-ab-bc-ac+abc故运算满足结合律。
(3)任意x∈Q，因为x*x=x+x-xx=2x+x2≠x，故不满足幂等律(4)因为对a∈Q，有a*0=a+0-a0=a，所以0是单位元。(5) 因为对a∈Q，有a*1=a+1-a=1，所以1是零元。
(6) 对a∈Q，令a*x=a+x-ax=0，则有x=a/(a-1)。所以当a≠1时，其逆元为a=a/(a-1)，1没有逆元。
-
1＝A∩～(B∪C) ＝A∩～B∩～C = A∩A∩～B∩～C ＝(A∩～B)∩(A∩～C) =(A-B)∩(A-C)
十、设A,B为任意集合，证明：ABP(A) P(B)。（5分） 证明：先证明充分性（=>）
X∈P(A)=> XA=> XB=> X∈P(B) 再证明必要性（
x∈A=> {x}A=> {x}∈P(A)=> {x}∈P(B)=> {x}B=>x∈B 综上所述，ABP(A) P(B)
第五篇：离散数学试卷1范文
离散数学试题（1）
一、单项选择题（本大题共15小题，每小题1分，共15分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列是两个命题变元p，q的小项是（）
A．p∧┐p∧qB．┐p∨q
C．┐p∧qD．┐p∨p∨q
2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）
A．p→┐q
C．p∧q
B．p∨┐q D．p∧┐q B．x+y=10 D．x mod 3=2 3．下列语句中是命题的只有（） A．1+1=10C．sinx+siny
4．下列等值式不正确的是（）
A．┐(x)A(x)┐A
B．(x)(B→A(x))B→(x)A(x)
C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)
D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)
5．谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z)中量词x的辖域是（）
A．(x)Q(x,z)→(x)(y)R(x,y,z))
B．Q(x,z)→(y)R(x,y,z)
C．Q(x,z)→(x)(y)R(x,y,z)
D．Q(x,z)
6．设R为实数集，函数f：R→R，f(x)=2x，则f是（）
A．满射函数
C．双射函数B．入射函数 D．非入射非满射
7．设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划
分是（）
A．{{a},{b,c},{d}}B．{{a,b},{c},{d}}
C．{{a},{b},{c},{d}}D．{{a,b},{c,d}}
8．设A={Ø}，B=P(P(A))，以下正确的式子是（）
A．{Ø,{Ø}}∈B
C．{{Ø},{{Ø}}}∈BB．{{Ø,Ø}}∈B D．{Ø,{{Ø}}}∈B
9．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（）
A．(X-Y)-Z=X-(Y∩Z)
B．(X-Y)-Z=(X-Z)-Y
C．(X-Y)-Z=(X-Z)-(Y-Z)
D．(X-Y)-Z=X-(Y∪Z)
10．设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（）
A．xA,有x*Z=Z*x=Z
B．ZA，且xA有x*Z=Z*x=Z
C．ZA，且xA有x*Z=Z*x=x
D．ZA，且xA有x*Z=Z*x=Z
离散数学试题（1）
11．在自然数集N上，下列定义的运算中不可结合的只有（）
A．a*b=min(a,b)
B．a*b=a+b
C．a*b=GCD(a,b)(a,b的最大公约数)
D．a*b=a(mod b)
12．设R为实数集，R={x|x∈R∧x>0}，*是数的乘法运算，是一个群，则下列集
合关于数的乘法运算构成该群的子群的是（）
A．{R中的有理数}
+C．{R中的自然数}
A．是交换群 +++
B．{R中的无理数} D．{1，2，3} B．是加法群 D．*对是可分配的 +13．设是环，则下列正确的是（） C．对*是可分配的
14．下列各图不是欧拉图的是（）
15．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（）
A．2个面B．3个面
C．4个面D．5个面
第二部分非选择题（共85分）
二、填空题（本大题共10小题，每空1分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．一公式为之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为之充分必要条件是其合取范式之每一合取项中均必同时包含 一命题变元及其否定。
17．前束范式具有形式(Q1V1)(Q2V2)„(QnVn)A，其中Qi(1≤i≤n)为，A为的
谓词公式。
18．设论域是{a,b,c}，则(x)S(x)等价于命题公式；(x)S(x)等价于命题公式。
19．设R为A上的关系，则R的自反闭包。
20．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R，
其关系矩阵是。
21．设是一个偏序集，如果S中的任意两个元素都有和，则称S关于≤
构成一个格。
22．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，
则代数系统的幺元是，零元是。
23．如下平面图有2个面R1和R2，其中deg(R1)=，deg(R2)=。
24．无向图G具有一条欧拉回路，当且仅当G是，。
25．在下图中，结点v2的度数是，结点v5的度数是。
三、计算题（本大题共6小题，第26—27小题每小题4分，第
28、30小题每小题5分，
第
29、31小题每小题6分，共30分）
26．（4分）求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函
数。
27．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：(y)(x)(xy0)。
28．（5分）设A={a,b,c }，P（A）是A的幂集，是集合对称差运算。已知
是群。
在群
中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}x={b}。
29．（6分）用等值演算法求公式┐(p→q)
(p→┐q)的主合取范式
30．（5分）画出5个具有5个结点5条边的非同构的无向连通简单图。
31．（6分）在偏序集中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求集合
D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。
四、证明题（本大题共3小题，第32~33小题每小题6分，第34小题8分，共20分）
32．（6分）用等值演算法证明((q∧s)→r)∧(s→(p∨r))(s∧(p→q))→r
33．（6分）设n阶无向树G=中有m条边，证明m=n-1。
34．（8分）设P={Ø,{1},{1,2},{1,2,3}}，是集合P上的包含关系。
（1）证明：
是偏序集。
（2）在（1）的基础上证明
是全序集
五、应用题(15分）
35．（9分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如
果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）