[精品]离散数学总结.doc

《[精品]离散数学总结.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、[精品]离散数学总结　　离散数学学习总结　　一、课程内容介绍1．集合论部分集合论是离散数学中第一个抽象难关，在老师的生动讲解下，深入浅出，使得集合论成了相当有趣的知识。　　只是对于以后的应用还不是很了解，感觉学好它很重要。　　直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。　　例如　方程x2－1＝0的实数解集合；　26个英文字母的集合；　坐标平面上所有点的集合；集合通常用大写的英文字母来标记，例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C

2、等。　　表示一个集合的方法有两种列元素法和谓词表示法，如果两个集合的交集为，则称这两个集合是不相交的。　　例如B和C是不相交的。　　两个集合的并和交运算可以推广成n个集合的并和交　　　A1∪A2∪…∪An＝{x

3、x∈A1∨x∈A2∨…∨x∈An}　　　A1∩A2∩…∩An＝{x

4、x∈A1∧x∈A2∧…∧x∈An}2．关系二元关系也可简称为关系。　　对于二元关系R，如果∈R，可记作xRy；如果R，则记作xy。　　例如R1={<1,2>,}，R2={<1,2>,a,b}。　　则R1是二元关系，R2不是二元关系，只是一个集合，除非将a

5、和b定义为有序对。　　根据上面的记法可以写1R12，aR1b，aR1c等。　　给出一个关系的方法有三种:集合表达式，关系矩阵和关系图。　　设R是A上的关系，我们希望R具有某些有用的性质，比如说自反性。　　如果R不具有自反性，我们通过在R中添加一部分有序对来改造R，得到新的关系R'，使得R'具有自反性。　　但又不希望R'与R相差太多，换句话说，添加的有序对要尽可能的少。　　满足这些要求的R'就称为R的自反闭包。　　通过添加有序对来构造的闭包除自反闭保外还有对称闭包和传递闭包。　　3．代数系统代数结构也叫做抽象代数，主要研究抽象的代

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

7、密码学等等都要用到抽象代数的知识。　　代数结构的主要研究对象就是各种典型的抽象代数系统。　　构成一个抽象代数系统有三方面的要素集合、集合上的运算以及说明运算性质或运算之间关系的公理。　　请看下面的例子。　　整数集合Z和普通加法＋构成了代数系统〈Z,＋〉，n阶实矩阵的集合Mn(R)与矩阵加法＋构成代数系统〈Mn(R),＋〉。　　幂集P(B)与集合的对称差运算也构成了代数系统。　　类似这样的代数系统可以列举出许多许多，他们都是具体的代数系统。　　考察他们的共性，不难发现他们都含有一个集合，一个二元运算，并且这些运算都具有交换性和结合

8、性等性质。　　为了概括这类代数系统的共性，我们可以定义一个抽象的代数系统，其中A是一个集合，是A上的可交换、可结合的运算，这类代数系统实际上就是交换半群。　　为了研究抽象的代数系统，我们需要先定义一元和二元代数运算以及二元运算的性质，并通过选择不同的运算性质来规定各种抽象代数系统的定义。　　在此基础上再深入研究这些抽象代数系统的内在特性和应用。　　4．图论部分图论是作为我们计算机专业的一门很有用处的知识，也是新兴的一个数学分支，在计算机迅速发展的同时，图论也迅速发展。　　因此，图论给我们以一种神奇的感觉，在学习图论中，老师总是把

9、图论分析得很透彻，学起来很有趣，同时也很简单。　　图论在数据结构方面的应用极其广泛，对我们学计算机专业的人来说，是一门必须要学好的知识。　　一个图可以用一个图形表示，定义中的结点对可以是有序的，也可以是无序的，若边所对误码的结点对（a,b）是有序的，刚称L是有向边，a称为L的起点，b称为L的终点，若边L所对应的结点对（a,b）是无序的，则称L是无向边。　　5．数理逻辑部分数理逻辑作为离散数学的最后一部分，充满着对逻辑思维的挑战，同时锻炼了我们思考问题的严密性，当然最重要的是学会如何用数学方法去分析逻辑问题。　　数理逻辑又称符号逻

10、辑，它是用数学方法支研究抽象思维的规律的应用学科，1.命题把能判断真假的陈述句称为命题，作为命题的陈述句表达的判断结果称为命题的真值。　　命题公式、对偶与范式、命题演算的推理等等。　　二、学习总结与体会在本学期一开始学习这门课程时，老师就明确的告诉我们这门课程很