离散数学知识点总结(通用12篇)

离散数学知识点总结 第1篇

离散数学知识点总结 第2篇

1.二元运算：设S为集合，函数 f：S×S→S 称为S上的二元运算，简称为二元运算。

例：f:N×N→N，f()＝x +y是自然数集合N上的二元运算

       f:N×N→N，f()＝x - y不是自然数集合N上的二元运算

验证一个运算是否为集合S上的二元运算主要考虑两点：

S中任何两个元素都可以进行这种运算，且运算的结果是唯一的。

S中任何两个元素的运算结果都属于S，即S对该运算是封闭的。

自然数集合N上的加法和乘法是N上的二元运算，但减法和除法不是。

整数集合Z上的加法、减法和乘法都是Z上的二元运算，而除法不是。

非零实数集R*上的乘法和除法都是R*上的二元运算，加法、减法不是。

2.一元运算：设S为集合，函数f：S→S称为S上的一元运算，简称为一元运算。

3.设°为S上的二元运算，如果对于任意的x,y∈S都有x°y=y°x，则称运算°在S上满足交换律。

4.设°为S上的二元运算，如果对于任意的x,y,z∈S都有 (x°y)°z=x°(y°z)，则称运算°在S上满足结合律。

5.设°为S上的二元运算，如果对于任意的x∈S有x°x=x，则称运算°在S上满足幂等律。如果S中的某些x满足x°x=x，则称x为运算°的幂等元。

6.普通的加法和乘法不适合幂等律。但0是加法的幂等元，0和1是乘法的幂等元。

7.设°和*为S上两个二元运算，如果对于任意的x,y,z∈S，有

                                              x*(y°z) ＝ (x*y) °(x*z)          （左分配律）                                               (y°z)*x ＝ (y*x) °(z*x)          （右分配律）

 则称运算*对运算°满足分配律。 

8.设°和*为S上两个可交换的二元运算，如果对于任意的x,y∈S，都有

                   x*(x°y)＝x                    x°(x*y)＝x

则称运算°和*满足吸收律。

9.设°为S上的二元运算，如果存在元素el（或er）∈S，使得对任意x∈S都有

                    el°x = x  (或x°er = x)

  则称el (或er)是S中关于°运算的一个左单位元(或右单位元)。

10.若e∈S关于°运算既是左单位元又是右单位元，则称e为S上关于°运算的单位元。单位元也叫做幺元。

设°为S上的二元运算，如果存在元素θl（或θr）∈S，使得对任意x∈S都有 θl°x = θl  (或x°θr = θr)，

 则称θl (或θr)是S上关于°运算的左零元(或右零元)。

11.若θ∈S关于°运算既是左零元又是右零元，则称θ为S上关于运算°的零元。

12.设°为S上的二元运算，eÎS为°运算的单位元，对于x∈S，如果存在yl（或yr）∈S使得yl°x＝e（或x°yr＝e）

则称yl（或yr）是x的左逆元（或右逆元）。

13.若y∈S既是x的左逆元又是x的右逆元，则称y为x的逆元。

14.如果x的逆元存在，则称x是可逆的。

15.设°为S上的二元运算，el、er分别为°运算的左单位元和右单位元，则el = er = e 且e 为S上关于°运算的唯一的单位元。

16.设°为S上的二元运算，θl和θr分别为°运算的左零元和右零元，则有 θl = θr = θ且θ为S上关于°运算的唯一的零元。

17.设°为S上的二元运算，e 和θ分别为°运算的单位元和零元，如果S至少有两个元素，则e!=θ。

18.设°为S上可结合的二元运算，e为该运算的单位元，对于x∈S，如果存在左逆元yl和右逆元yr，则yl = yr= y且y是x的唯一的逆元。

19.设°为S上的二元运算，如果对于任意的x,y,z∈S，满足以下条件：

（1）若x°y ＝x°z且x!=θ，则y ＝z        （左消去律）

（2）若y°x ＝ z°x且x!=θ ，则y＝z        （右消去律）

则称°运算满足消去律。

例如：

      整数集合上的加法和乘法都满足消去律。

      幂集P(S)上的并和交运算一般不满足消去律。

20.设V＝是代数系统，°为二元运算，如果运算是可结合的，则称V为半群（semigroup）。

21.设V＝是半群,若e∈S是关于°运算的单位元,则称V是含幺半群，也叫做独异点（monoid）。有时也将独异点V记作V＝。

    ，，，，都是半群,+是普通加法。这些半群中除外都是独异点。

     设n是大于1的正整数,和都是半群,也都是独异点,其中+和·分别表示矩阵加法和矩阵乘法。

为半群,也是独异点,其中Å为集合的对称差运算。

     为半群,也是独异点,其中Zn＝{0,1,…,n-1},Å为模n加法。

22.设是代数系统，°为二元运算。如果°运算是可结合的，存在单位元e∈G，并且对G中的任何xxx都有x-1∈G,则称G为群（group）。

     注意:群V=<S,∘>的定义实际上包含5个条件

     ⑴ S非空；

     ⑵ ∘运算封闭；

     ⑶ ∘运算满足结合律；

     ⑷ ∘运算在s中有单位元；

     ⑸ S中任意元素对∘运算有逆。

          ,,都是群,而和不是群。

          是群,而不是群。因为并非所有的n阶实矩阵都有逆阵。

是群，因为对任何B的子集A，A的逆元就是A自身。

          是群。0是Zn中的单位元。x∈Zn，若x＝0，x的逆元就是0，若x≠0，则n-x是x的逆元。

离散数学知识点总结 第3篇

1、A

C)= A

2、A

C)= A

3、(B

A = B

4、(B

A = B

5、A

BóA

C ó C

6、A

B,C

DóA

定义 令

是 n 个集合，称n元组的集合{<

>|

}，为

的直积或笛卡尔积，记为

离散数学知识点总结 第4篇

离散数学的特点是知识点集中，对抽象思维能力的要求较高。由于这些定义的抽象性，使初学者往往不能在脑海中直接建立起它们与现实世界中客观事物的联系。不管是哪本离散数学教材，都会在每一章中首先列出若干个定义和定理，接着就是这些定义和定理的直接应用，如果没有较好的抽象思维能力，学习离散数学确实具有一定的困难。因此，在离散数学的学习中，要注重抽象思维能力、逻辑推理能力的培养和训练，这种能力的培养对今后从事各种工作都是极其重要的。

在学习离散数学中所遇到的这些困难，可以通过多学、多看、认真分析讲课中所给出的典型例题的解题过程，再加上多练，从而逐步得到解决。在此特别强调一点：深入地理解和掌握离散数学的基本概念、基本定理和结论，是学好离散数学的重要前提之一。所以，同学们要准确、全面、完整地记忆和理解所有这些基本定义和定理。

离散数学知识点总结 第5篇

1.若集合A有m个元素，集合B有n个元素，则A,B的笛卡尔基的基数为m*n，A到B上可以定义种关系。

2.五种性质的解释：    1）自反性：R为AxA的非空子集，若任意的，有（x，x）都属于R，则称由R规定的关系是自反的。    2）反自反性：R为AxA的非空子集，若任意的，有（x，x）都不属于R，则称由R规定的关系是反自反的。    3）对称性：R为AxA的非空子集，若任意的，有（x，y）属于R，且（y，x）也一定属于R，则称R规定的关系是对称的。    4）反对称性：R为AxA的非空子集，若任意的，当且仅当x=y时，有（x，y）属于R，（y，x）也属于R，则称R规定的关系是对称的。    5）传递性：R为AxA的非空子集，若任意的，若（x，y）属于R，（y，z）属于R，则（x，z）属于R，则称R所规定的关系是传递的。

3.全关系的性质：1）自反性；2）对称性；3）传递性    空关系的性质：1）反自反性；2）反对称性；3）传递性    全封闭环的性质：1）自反性；2）对称性；3）反对称性；4）传递性

4.前域：所有xxx组成的集合    后域：所有xxx组成的集合；

5.等价关系：集合A上满足1）自反，2）对称，3）传递三种性质的二元xxx称为等价关系

6.偏序关系：集合A上满足1）自反，2）反对称，3）传递三种性质的二元xxx称为偏序关系

7.自反闭包：添加最少的序偶后产生的满足自反性的关系称为原关系的自反闭包    对称闭包：添加最少的序偶后产生的满足对称性的关系称为原关系的对称闭包    传递闭包：添加最少的序偶后产生的满足传递性的关系称为原关系的传递闭包

8.极xxx、极大元、最xxx、最大元的概念。这个概念是建立在偏序关系上的。    极xxx：假设a为极xxx，则任取与a具有xxx的xxx，都有aRx，则a为极xxx    极大元：假设a为极大元，则任取与a具有xxx的xxx，都有xRa，则a为极大元    最xxx：假设a为最xxx，集合A中任意xxx，都有aRx，则a为最xxx    最大元：假设a为最大元，集合A中任意xxx，都有xRa，则a为最大元    下面我们以集合A = {1,2,3,4,5}，定义关系为整除关系，则xxx为{(1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,4),(3,3),(4,4),(5,5)}     为方便我们计算若干元，我们利用上述偏序关系画出哈斯图，具体步骤就是，删除自反和传递结果，即{(1,2),(1,3),(1,5),(2,4)},作图如下： 那么对于集合A = {1,2,3,4,5}来说，极大元：4,3,5；极xxx：1；最大元：无；最xxx1。    大家还可以那下面这个相对复杂的集合和偏序关系来练手：集合A = {1,2,3,4,5,6,7,8}，定义关系为整除关系，则哈斯图如下：    那么对于子集B = {2,3,6}来说，分别判断其各个元的值：    答案： 

9.上界、上确界、下界，下确界，同样是建立在偏序关系上的：这里我们引用书上的定义    几点性质：1.上界、上确界、下界，下确界不一定存在；                      2.上界、下界如果存在也不一定唯一；                      3.上确界、下确界若存在则一定唯一；                      4.集合的最xxx就是其下确界，最大元就是其上确界；单反之不一定成立。第六章 函数

1.函数的三要素：定义域，值域，对应法则。

2.从集合的角度看函数的定义：设A和B是两个非空集合，如果按照某种对应关系 ，对于集合A中的任何一个元素a，在集合B中都存在唯一的一个元素b与之对应，那么，这样的对应（包括集合A，B，以及集合A到集合B的对应xxx）叫做集合A到集合B的映射（Mapping），记作,定义在非空集合上的这种映射称为函数。其中，b称为a在映射f下的象，记作：; xxxb关于映射f的原象。集合A中所有元素的象的集合记作f（A）。

3.集合X的基|X| = m，集合Y的基|Y| = n，则从X到Y有种关系，有种函数。

4.单射：,对任意的，则，则称f为单射。    满射：,Y中任意元素在X中都有一个或多个元素对应，则称f为满射。    双射：既是单射又是满射，则称为双射，这里|X| = |Y|。

5.有关单射/双射：若集合X的基|X| = m，集合Y的基|Y| = n，m <= n, X到Y有 个单射.                              若集合X的基|X| = m，集合Y的基|Y| = n，m = n, X到Y有 个单射

离散数学知识点总结 第6篇

定义 设 A、B 是两个合法的谓词公式，如果在任何解释下，这两个公式的真值都相等，则称 A 与 B 等值，记为 A ó B。

当 AóB 时，根据定义可知，在任何解释下，公式 A 与公式 B 的真值都相同，故 A↔B 为永真式，故得到如下的定义。

定义 设 A、B 是两个合法谓词公式，如果在任何解释下， A↔ B 为永真式， 则 A与 B 等值，记为 A ó B。

一、利用代换实例可证明的等值式(p↔﹁﹁p 永真，代换实例∀ xF(x) ↔﹁﹁∀ xF(x)永真)

二、个体域有限时，带全称量词、存在量词公式的等值式

离散数学知识点总结 第7篇

离散数学的三大体系虽然来自于不同的学科，但是这三大体系前后贯通，形成一个有机的整体。通过认真的分析可寻找出三大部分之间知识的内在联系性和规律性。如：集合论、函数、关系和图论，其解题思路和证明方法均有相同或相似之处。

如何应对考试:一般来说，离散数学的考试要求分为了解、理解和掌握。了解是能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。为了考核学生对这三部分的理解和掌握的程度，试题类型一般可分为：判断题、填空题、选择题、计算题和证明题。判断题、填空题、选择题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算；计算题主要考核学生的基本运用技能和速度，要求写出完整的计算过程和步骤；证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出严格的推理和论证过程。

学习离散数学的最大困难是它的抽象性和逻辑推理的严密性。在离散数学中，假设让你解一道题或证明一个命题，你应首先读懂题意，然后寻找解题或证明的思路和方法，当你相信已找到了解题或证明的思路和方法，你必须把它严格地写出来。一个写得很好的解题过程或证明是一系列的陈述，其中每一条陈述都是前面的陈述经过简单的推理而得到的。仔细地写解题过程或证明是很重要的，既能让读者理解它，又能保证解题过程或证明准确无误。一个好的解题过程或证明应该是条理清楚、论据充分、表述简洁的。针对这一要求，在讲课中老师会提供大量的典型例题供同学们参考和学习。

通过离散数学的学习和训练，能使同学们学会在离散数学中处理问题的一般性的规律和方法，一旦掌握了离散数学中这种处理问题的思想方法，学习和掌握离散数学的知识就不再是一件难事了。

首先要明确的是，由于《离散数学》是一门数学课，且是由几个数学分支综合在一起的，内容繁多，非常抽象，因此即使是数学系的学生学起来都会倍感困难，对计算 科学专业的学生来说就更是如此。大家普遍反映这是大学四年最难学的一门课之一。但鉴于《离散数学》在计算科学中的重要性，这是一门必须牢牢掌握的课程。既 然如此，在学习《离散数学》时，大家最应该牢记的是唐诗“熟读唐诗三百首，不会做诗也会吟。”学习过程是一个扎扎实实积累的过程，不能打马虎眼。离散数学是理论性较强的学科，学习离散数学的关键是对离散数学(集合论、数理逻辑和图论)有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。

《离散数学》的特点是：

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

2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。《离 散数学》的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法、构造性证明法），同一个题也可能有几种方法。但是《离散数学》证明 题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多 探讨几种证明方法，从而学会熟练运用这些证明方法。一般来说，由于这些概念（定义）非常抽象（学习《线性代数》时会有这样的经历），初学者往往不能在脑海中 建立起它们与现实世界中客观事物的联系。这往往是《离散数学》学习过程中初学者要面临的第一个困难，他们觉得不容易进入学习的状态。因此一开始必须准确、 全面、完整地记住并理解所有的定义和定理。具体做法是在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能 够适应，并为后续学习打下良好的基础。

离散数学知识点总结 第8篇

图论基本概念

1.图：无向图和有向图统称为图

2.图的阶：顶点数称为图的阶，n个顶点的图称作n阶图

3.一条边也没有的图称作零图，一阶图称作平凡图

4.在图的定义中规定顶点集V为非空集，但在的运算中可能产生顶点集为空集的运算结果，为此规定顶点集为空集的图为空图

5.标定图：给每个顶点和每一条边指定一个符号，否则称为非标定图

6.将有向图的各条有向边改成无向边后所得到的无向图称作这个有向图的基图

7.多重图：含平行边的图

8.简单图：不含平行边也不含环的图

9.悬挂顶点：顶点度数为1，与它关联的边称作悬挂边

10.握手定理：在任何图中（有向图&无向图），所有顶点的度数之和等于边数的2倍

11.推论：任何图中，奇度顶点的个数是偶数

12.可图化：当且仅当所有顶点度数和为偶数

13.图的同构必要条件：顶点数、边数、度数列相同

图的连通性和图的运算

1.在n阶图G中，若从顶点u到v（u!=v）存在通路，则u到v一定存在长度小于等于n-1的初级通路

2.在n阶图G中，若存在V到自身的的回路，则一定存在V到自身长度小于等于n的初级回路

3.设无向图G，若u，v之间存在通路，则称u，v是连通的

4.连通图：无向图G是平凡图或G中任何两个顶点都是连通的

欧拉图与xxx图

1.欧拉通路：通过图中所有的边一次且仅一次行遍所有的顶点的通路称作欧拉通路

2.欧拉回路：通过图中所有的边一次且仅一次行遍所有的顶点的回路称作欧拉回路

3.欧拉图：具有欧拉回路的图

4.半欧拉图：具有欧拉通路而没有欧拉回路的图

5.定理1：无向图G是欧拉图当且仅当G是连通图且没有奇度顶点

6.定理2：无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点

7.定理3：有向图G是欧拉图当且仅当G是强连通的且每个顶点的入度等于出度

8.定理4：有向图G是半欧拉图当且仅当G是单向连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大一，另一个顶点的出度比入度大一，其余顶点入度等于出度

9.xxx通路：经过图中所有顶点一次且仅一次的通路称作xxx通路

10.xxx回路：经过图中所有顶点一次且仅一次的回路称作xxx回路

11.xxx图：具有xxx回路的图

12.半xxx图：具有xxx通路但不具有xxx回路的图

离散数学知识点总结 第9篇

定义 设°是集合 S 上的二元运算，若

都有 x°y=y°x，则称°在 S 上是可交换的，或者说运算°在 S 上满足交换律。

定义 设°是集合 S 上的二元运算，若

都有(x°y)°z=x°(y°z)，则称°在 S上是可结合的,或者说运算°在 S 上满足结合律。

定义 设°是集合 S 上的二元运算，若

都有 x°x=x， 则称°在 S 上是幂等的,或说运算°在 S 上满足幂等律。

定义 设°与*是集合 S 上的二种运算，若

都有 x*(y°z)=(x*y)°(x*z)与(y°z)*x=(y*x)°(z*x)，则称*对°是可分配的。

定义 设°与*是集合 S 上的二种可交换的二元运算，若

都有 x*(x°y)=x 与x°(x*y)=x 则称*与°是满足吸收律，内外二种运算不一样，运算符内外各出现一次，以多吃少。

广群：

半群：

群：

子群：

离散数学知识点总结 第10篇

定义 给定集合A上的关系ρ，若ρ是自反的、对称的，则称ρ是A上的相容关系。

定义 给定非空集合A，设有集合S={

}，其中

，i=1,2,…,m,且

，则称集合S称作A的覆盖。

定理 给定集合A的覆盖，

，由它确定的关系：

是相容关系。

定义 设R为定义在集合A上的一个关系，若R是自反的，对称的，传递的，则R称为等价关系。(显然等价关系一定是相容关系)。

定义 设给定非空集合A，若有集合S={

}，其中

(i=1,2,…,m)，且有

，同时有

，则称S为A的一个划分。(所有子集的并为A，且子集的交为空，则这些子集组成的集合为A的一个划分，覆盖中，子集的交集可不为空)

等价类

偏序关系(自反性，反对称性，传递性)

，哈斯图，可比的，xxx盖住xxx，全序关系，极大元，极xxx，最大元，最xxx

拟序关系(反自反的，传递的)

离散数学知识点总结 第11篇

定义 若

R，则R是自反关系。(自己到自己的关系全属于R)

定义 若

R,则 R 是反自反的。(自己到自己的关系全不属于R)

定义 如果所有形如的序偶都在关系 R 中， R 也只有这种形式的序偶， 则称 R为恒等关系，记为

对于恒等关系而言，其关系矩阵是单位矩阵，即其主对角线全是 1，其他位置全是 0，对关系图是每个点都有自旋，仅只有自旋，没有其他边。

定义 令xxx

A，如果当

R 时

R，则称 R 为对称关系。

定义 令xxx

A，如果当

R 且x

R， 则称 R 为反对称关系。

定义 令xxx

A，若当

R时有

R，则称R为可传递关系。

R 的关系矩阵可知，其非0元素在R的关系矩阵都出现，即

，凡满足这个不等式的关系，肯定为可传递关系。

所以不可传递。

R的关系矩阵可知，其非0元素出现在(1,1)，(1,3)，(2,2)，(2,4)，在 R 的关系矩

阵都没出现，不满足

，不可传递关系。

离散数学知识点总结 第12篇

：自然数集，N*：正整数集，R：实数集，Q：有理数集，Z：整数集，C：复数集。

2.基：集合A中不同元素的个数，|A|。

3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，记做P(A)。

4.若集合A中有n个元素，则A有个子集（含空集），则其幂集P(A)中含个元素。

5.集合的分划    ①.由集合A的若干非空子集构成；    ②.这几个子集相交为空，相并为A。 6.集合的覆盖    ①.由集合A的若干非空子集构成；    ②.这些非空子集的相交未必为空，但相并一定为A