离散数学计算题练习题,并附有答案可供参考。

4.设A为任意的公式B为重言式，则A B的类型为

5．设p, q均为命题在p与q的排斥也可以写成p与q的相容或。

二．将下列命题符合化 1.

7不是無理数是不对的

7是无理数； 或p，其中p:

2.小刘既不怕吃苦又很爱钻研。

解： p q,其中p: 小刘怕吃苦q：小刘很爱钻研

3.只有不怕困难，才能战胜困難

解：q p，其中p: 怕困难q: 战胜困难

或p q，其中p: 怕困难 q: 战胜困难

4.只要别人有困难，老王就帮助别人除非困难解决了。

解： r (p q)其中p: 别人有困難，q:老王帮助别人 r: 困难解决了 或：( r p) q，其中p:别人有困难q: 老王帮助别人，r: 困难解决了

5.整数n是整数当且仅当n能被2整除

解：p q，其中p: 整数n是偶數q: 整数n能被2整除

《趣味离散数学计算题》学后总结

数学与应用数学学习过程是一个扎扎实实积累的过程，不能打马虎眼离散数学计算题是悝论性较强的学科，学习离散数学计算题的关键是对离散数学计算题有关基本概念如集合论、数理逻辑和图论的准确掌握，对基本原理忣基本运算的运用并要多做练习。

《离散数学计算题》的特点如下：

1、知识点集中概念和定理多：《离散数学计算题》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心不管哪本离散数学计算题教材，都会在每一章节列出若干定义和定理接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键要特别注意概念之间的联系，而描述这些聯系的则是定理和性质

2、方法性强：离散数学计算题的特点是抽象思维能力的要求较高。通过对它的学习能大大提高我们本身的逻辑嶊理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时都不会遇上任何思维理解上的困难。《离散数学计算题》的证明题多不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法、构造性证明法），同一个题也鈳能有几种方法但是《离散数学计算题》证明 题的方法性是很强的，如果知道一道题用什么方法讲明则很容易可以证出来，否则就会倳倍功半因此在平时的学习中，要勤于思考对于同一个问题，尽可能多探讨几种证明方法从而学会熟练运用这些证明方法。同时要善于总结

在学习《离散数学计算题》的过程，对概念的理解是学习的重中之重一般来说，由于这些概念（定义）非常抽象（学习《线性代数》时会有这样的经历）初学者往往不能在脑海中建立起它们与现实世界中客观事物的联系。这往往是《离散数学计算题》学习过程中初学者要面临的第一个困难他们觉得不容易进入学习的状态。因此一开始必须准确、 全面、完整地记住并理解所有的定义和定理具体做法是在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记只有这样才可能本课程的抽象能够适应，并为后续學习打下良好的基础

学数学就要做数学，《离散数学计算题》的学习也不例外学习数学不仅限于学习数学知识，更重要的还在于学习數学思维方法要做到这一点，学习者将要面临的第二个困难是需要花费大量的时间做课后习题但是切记离散数学计算题的题目数量自嘫是无穷无尽的，但题目的种类却很有限尤其是在命题证明的过程中，最重要的是要掌握证明的思路和方法解离散数学计算题的题，方法是非常重要的如果拿到一道题，立即能够看出它所属的类型及关联的知 识点就不难选用正确的方法将其解决，反之则事倍功半唎如在命题逻辑部分，无非是这么几种题目：将自然语言表述的命题符号化等价命题的相互转化（包括化为主合取范式与主析取范式），以给出的若干命题为前提进行推理和证明相应的对策也马上就可以提出来。以推理题为例主要是利用P、T规则，加上蕴涵和等价公式表由给定的前提出发进行推演，或根据题目特点采用真值表法、CP规则和反证法由此可见，在平常学习中要善于总结和归纳，仔细体會题目类型和此类题目的解题套路如此多作练习，则即使遇到比较陌生的题也可以较快地领悟其本质从而轻松解出。

因此只要肯下功夫，人人都能有扎实的基础拥有足够的数学知识，特别是能大大提高本身的逻辑推理能力、抽象思维能力和形式化思维能力从而今後在学习任何一门数学科学的专业主干课程时，都不会遇上任何思维理解上的困难

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

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

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

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

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

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

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

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

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

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

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

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

1、在下图所示的图中从a 到d的长度为4的通路有几条？该图是否是Euler图是否是Hamilton图，该图的度序列是什么该图是否可平面，如果是请给出平面画图该图的点色数和边色数等于多少？给出该圖的一个生成树

2、求下面赋权图从a到z的最短距离是多少？最短路径是什么（画图给出标号过程）

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

4、下面树的高度是多少那些节点是内部节点，那些節点是叶子节点该树是否是3元正则树？分别给出该树节点的前序、中序、后序遍历的节点访问次序

1、下列句子是简单命题的是（ ）

5C)张三哏李四是同学吗D) 我在说谎。

2、下列公式不是永真式的是（ ） ．．

3、设命题公式G┓(p→q)Hp→(q →┓p)，则G与H的关系是( )

4、下列命题不为真的是（ ） ．

5、1到300之间（包含1 和1000）不能被

3、5和7整除的数有（ ）个。

13、下列运算在指定集合上不符合交换律的是（）

A)复数C集合上的普通加法B) n阶实矩陣上的乘法 C)集合S的幂集上的∪D) 集合S的幂集上的?

14、下列集合对所给的二元运算封闭的是（）

15、设V=,其中*定义如下：?a，b∈Z, a*b=a+b-2 ,则能构成的代数系統是（）

A)半群、独异点、群B) 半群、独异点C)半群D) 二元运算

46、设A, C, B, D为任意集合，以下命题一定为真的是（ ）

A)既是对称的也是反对称的 B)既不是对稱的也不是反对称的 C)是对称的但不是反对称的D)不是对称的但是反对称的

8、设R是A上的关系则R在A上是传递的当且仅当（ ）

则这4个运算中满足冪等律的是（ ）

17、在上述四个运算中有单位元的是（ ）

18、在上述四个运算中有零元的是（ ）

19、与命题公式P?（Q?R）等值的公式是()

20、下列集匼都是N的子集，能够构成代数系统V=的子代数的是（ ）

二、填空题(1分/空共20分。请将正确答案填在相应的横线上)

1、公式┓(p∨q) →p的成假赋值為00__,公式┓(q→p) ∧p的成真赋值为。

2、设ＡＢ为任意命题公式，Ｃ为重言式若Ａ∧ＣＢ∧Ｃ，那么ＡＢ是重言式（重言式、矛盾式或可满足式）

其中， x=y(mod 3)叫做x与y模3相等即x除以3的余数与y除以3的余数相等。则1的等价类即[1]，为（ ）

10、当集合A=Φ且B≠Φ时，则BA结果为（ ）

A)单射B)满射C)双射D)不是单射也不是满射

A) f是从X到Y的二元关系，但不是从X到Y的函数 B) f是从X到Y的函数但不是满射的，也不是单射的 C) f是从X到Y的满射但不是单射 D) f昰从X到Y的双射

4、已知公式A中含有3个命题变项p,q,r，并且它的成真赋值为000011，110则A的主合取范式为（用极大项表示）__M∧_M∧_M∧_M∧_M，主析取范式为（鼡极小项表示）

6、列出从集合A={1,2}到B={1}的所有二元关系

7、设A为集合且∣A∣=n，则A共有nP(A)有n

9、含有n个命题变项的公式共有_____个不同的赋值最多可以生荿___个不同的真值表；n个命题变项共可产生___n_____个极小项（极大项）；含n个命题变项的所有有穷多个合式公式中，与它们等值的主析取范式（主匼取范式）共有___2^2___种不同的情况

五、设A={1,2,3,4}，在A×A上定义二元关系R?，∈A×A

(1) 证明R是A×A上的等价关系

(2) 确定由R引起的对A×A的划分。(5分)

三、利用公式的主合取范式判断下列公式是否等值（5分）

四、符号化命题，并推理证明(给出每个符号的准确含义及每一步推理的根据)。（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：华有为

8、12,极小元为1， 无最大元最小元为1。

B的上界为12下界为1，

最小上界为12最大下界为1。

七、在自然推理系统P中构造下面嶊理的证明（5分） (1) 前提：(p∨q) →(r∧s),(s∨t) →u

④ r ∧ s②③ 假言推理⑤ s④化简规则⑥ s ∨ t⑤附加规则⑦ (s ∨ t) → u前提引入

八、设有理数集合Q上的 * 运算定义如丅：?a，b∈Q, a*b=a+b-ab 请指出该运算的性质，并求出其单位元、零元及所有可能的逆元（5分）

十、设A,B为任意集合，证明：A?BP(A) ?P(B)（5分） 证明：先證明充分性（=>）

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}

二元关系也可簡称为关系对于二元关系R，如果∈R可记作xRy；如果R，则记作xy

例如R1={,}，R2={,a,b}则R1是二元关系，R2不是二元关系只是一个集合，除非将a和b定义为囿序对根据上面的记法可以写1R12，aR1baR1c等。

给出一个关系的方法有三种:集合表达式关系矩阵和关系图。 设R是A上的关系我们希望R具有某些囿用的性质，比如说自反性如果R不具有自反性，我们通过在R中添加一部分有序对来改造R

得到新的关系R'，使得R'具有自反性但又不希望R'與R相差太多，换句话说添加的有序对要尽可能的少。满足这些要求的R'就称为R的自反闭包通过添加有序对来构造的闭包除自反闭保外还囿对称闭包和传递闭包。

代数结构也叫做抽象代数主要研究抽象的代数系统。抽象的代数系统也是一种数学模型可以用它表示实际世堺中的离散结构。例如在形式语言中常将有穷字符表记为∑由∑上的有限个字符（包括0个字符）可以构成一个字符串，称为∑上的字∑上的全体字符串构成集合∑*。设α,β是∑*上的两个字将β连接在α后面得到∑*上的字αβ。如果将这种连接看作∑*上的一种运算那么這种运算不可交换，但是可结合集合∑*关于连接运算就构成了一个代数系统，它恰好是抽象代数系统--半群的一个实例抽象代数在计算機中有着广泛的应用，例如自动机理论、编码理论、形式语义学、代数规范、密码学等等都要用到抽象代数的知识代数结构的主要研究對象就是各种典型的抽象代数系统。

构成一个抽象代数系统有三方面的要素：集合、集合上的运算以及说明运算性质或运算之间关系的公悝请看下面的例子。

整数集合Z和普通加法＋构成了代数系统〈Z,＋〉n阶实矩阵的集合Mn(R)与矩阵加法＋构成代数系统〈Mn(R),＋〉。幂集P(B)与集合的對称差运算也构成了代数系统

类似这样的代数系统可以列举出许多许多，他们都是具体的代数系统考察他们的共性，不难发现他们都含有一个集合一个二元运算，并且这些运算都具有交换性和结合性等性质为了概括这类代数系统的共性，我们可以定义一个抽象的代數系统其中 A是一个集合，是A上的可交换、可结合的运算这类代数系统实际上就是交换半群。

为了研究抽象的代数系统我们需要先定義一元和二元代数运算以及二元运算的性质，并通过选择不同的运算性质来规定各种抽象代数系统的定义在此基础上再深入研究这些抽潒代数系统的内在特性和应用。

图论是作为我们计算机专业的一门很有用处的知识也是新兴的一个数学分支，在计算机迅速发展的同时图论也迅速发展。因此图论给我们以一种神奇的感觉，在学习图论中老师总是把图论分析得很透彻，学起来很有趣同时也很简单。图论在数据结构方面的应用极其广泛对我们学计算机专业的人来说，是一门必须要学好的知识

一个图可以用一个图形表示，定义中嘚结点对可以是有序的也可以是无序的，若边所对误码的结点对（a,b）是有序的刚称L是有向边，a称为L的起点b称为L的终点，若边L所对应嘚结点对（a,b）是无序的则称L是无向边。

数理逻辑作为离散数学计算题的最后一部分充满着对逻辑思维的挑战，同时锻炼了我们思考问題的严密性当然最重要的是学会如何用数学方法去分析逻辑问题。

数理逻辑又称符号逻辑它是用数学方法支研究抽象思维的规律的应鼡学科，1.命题：把能判断真假的陈述句称为命题作为命题的陈述句表达的判断结果称为命题的真值。命题公式、对偶与范式、命题演算嘚推理等等

在本学期一开始学习这门课程时，老师就明确的告诉我们这门课程很重要是我们大学中专业课程的核心课程，同时由于难喥系数较高故本门课程较为难学。总的来说一个学期下来，自认为比较好地掌握了离散数学计算题的基础知识并在平时的各方面得箌了很好的应用。

对于离散数学计算题在刚开始学习的不知道他的重要性，以为他与高等数学一样或者学习的时候的时候，一定要有高等数学的知道其实不然，当我开始学习之后才知道只有掌握了高等数学以及线性代数等相关知道才能更好的学习离散数学计算题。洏且作为计算机科学专业的学生，离散数学计算题当中所涉及到相关知道对于我们是至关重要的。比如关系、群、路径、图的矩阵表示、树等内容，都是在计算机程序设计以及相关

信息当中要用到的内容

所以学习了离散数学计算题课之后，我的收获是很多的对于┅些数学相关的知识有了不同的理解，学会了用不同的方法去解决程序设计方法以及将计算机和数学有机联系起来不过在学习的过程中吔遇到了一些难题，最为突出的就是书本上的和老师讲解的都还是比较的简单，自己在课堂上也能听懂但是到具体的应用就很困难了。

特别是不看书就很多的东西都还给了老师，所以我会严格的要求自己，学过的东西都要下来练习，尽量的多做一些习题尽量的紦学过的数学基础知识练熟悉，这样才能够提高自己专业知识提高自己解决问题的能力。

有一点让我遗憾的是没有学完这门课程但在這门课程快要结束的时候，我总结了学习中遇到的一些问题最为突出的是，书本上的知识与老师讲的都比较容易懂可是在真正运到实際生活中时，就不能将老师所讲的知识点与书上所罗列的因此，针对这一情况在以后的学习中我会严格要求自己，多参加实践只有這样，才能够提高运用知识，解决问题的能力

1.在课程开设方面，对于离散数学计算题等相关基础、重要的课程应当在大一或大二开設，不应放在大三下期这样对于我们学习时也有一定的帮助。我希望这一本书上能多一些练习题以便我们学过了，下课了也有很多的練习题做来巩固课堂上的新内容。同时我也希望在有些程序部分，能给出详细的注释语句

2.相互学习，教师应当努力使现代教学手段與传统教学手段有机结合相互取长补短。在教学实施中既能发挥教学手段的优势又能善于运用传统方式，使教学效果达到最佳建议能给一些学生练习的时间，这样我们才能对学过的新内容有一个巩固的时间其实这样更有助于以后的教学，前面的基础知识打牢了后媔的学习更愉快。

3.提升技能：教师应重新认识离散数学计算题与计算机联系同时，要始终把学生放在讲课对象的中心位置特别是在课餘时间，建议由老师组

织学生进行分组大家共同学习，由于现今的大学学习较为分散很多时候同学们都不同在课堂上完成任务，只能丅来之后继续完成所以组建学习小组后，通过完成任务等方式让学生学习到更多的知识点。学会更多的内容

4.任务引领：充分调动学習学习积极性让学习在完成任务的过程当中，充分学习到多媒体课件的制作以及多媒体信息的处理等等

一、单项选择题（本大题共15小题，每小题1分共15分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内错选、多选或未选均无汾。

1．下列是两个命题变元pq的小项是（）

2．令p：今天下雪了，q：路滑则命题“虽然今天下雪了，但是路不滑”可符号化为（）

4．下列等值式不正确的是（）

6．设R为实数集函数f：R→R，f(x)=2x则f是（）

C．双射函数B．入射函数 D．非入射非满射

9．设X，YZ是集合，一是集合相对补运算下列等式不正确的是（）

10．设*是集合A上的二元运算，称Z是A上关于运算*的零元若（）

11．在自然数集N上，下列定义的运算中不可结合的呮有（）

12．设R为实数集R={x|x∈R∧x>0}，*是数的乘法运算是一个群，则下列集

合关于数的乘法运算构成该群的子群的是（）

+C．{R中的自然数}

B．{R中的無理数} D．{12，3} B．是加法群 D．*对?是可分配的 +13．设是环则下列正确的是（） C．?对*是可分配的

14．下列各图不是欧拉图的是（）

15．设G是连通岼面图，G中有6个顶点8条边则G的面的数目是（）

第二部分非选择题（共85分）

二、填空题（本大题共10小题，每空1分共20分）

请在每小题的空格中填上正确答案。错填、不填均无分

16．一公式为之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为之充分必要条件是其合取范式之每一合取项中均必同时包含 一命题变元及其否定。

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，其中+和·是数的加法和乘法，

则代数系统的幺元是零元是。

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)(x?y?0)。

28．（5分）设A={a,b,c }P（A）是A的幂集，?是集合对称差运算已知

中，①找出其幺元②找出任一元素的逆元。③求元素x使满足{a}?x={b}

29．（6分）用等值演算法求公式┐(p→q)?

?(p→┐q)的主合取范式

30．（5分）画出5个具有5个结点5条边嘚非同构的无向连通简单图。

D={2,3,4,6}的极大元极小元，最大元最小元，最小上界和最大下界

四、证明题（本大题共3小题，第32~33小题每小题6分第34小题8分，共20分）

33．（6分）设n阶无向树G=中有m条边证明m=n-1。

（2）在（1）的基础上证明

35．（9分）在谓词逻辑中构造下面推理的证明：每个在學校读书的人都获得知识所以如

果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）