离散数学必备知识点总结

离散数学知识点汇总
1. 集合：集合是由一组具有某种共同特征的元素组成的一个整体，元素可以是任何类型的对象，比如数字、字母、函数等。

2. 关系：关系是一种描述两个或多个对象之间的关联的概念。

它由一组元组组成，每个元组都有两个或多个不同的对象，这些对象之间存在某种关系。

3. 函数：函数是一种把一个或多个输入变量转换为一个输出变量的规则。

它是一种从输入变量到输出变量的映射，可以用来描述复杂的关系。

4. 数学归纳法：数学归纳法是一种推理方法，用于证明一个总体结论是正确的，通过分析一系列具体例子。

5. 逻辑：逻辑是一种用来分析和证明论证的学科，通过推理和证明来解决问题。

6. 排列组合：排列组合是指从一定数量的物品中取出若干不同的物品排列成不同的组合，以达到某种目的的方法。

7. 组合数学：组合数学是一种研究物体的组合及其组合中的性质的数学学科。

离散知识点公式总结1. 集合论集合是离散数学中的基本概念，它是由一些确定的对象所组成的一个整体。

集合之间的运算包括并集、交集、差集、补集等。

其相关公式如下：- 并集：对于集合A和B，它们的并集定义为包含A和B中所有元素的集合，记作A∪B。

公式：A∪B={x|x∈A或x∈B}- 交集：对于集合A和B，它们的交集定义为同时属于A和B的所有元素的集合，记作A∩B。

公式：A∩B={x|x∈A且x∈B}- 差集：对于集合A和B，A与B的差集定义为属于A但不属于B的元素所组成的集合，记作A-B。

公式：A-B={x|x∈A且x∉B}- 补集：对于集合A，相对于全集合U而言，A的补集定义为全集合中不属于A的元素所组成的集合，记作A'。

公式：A'={x|x∈U且x∉A}2. 关系和函数关系是一种描述元素之间的对应关系的数学工具，而函数则是一种特殊的关系。

在离散数学中，关系和函数的定义和性质是非常重要的内容。

其相关公式如下：- 关系R：对于集合A和B，关系R定义为A和B的笛卡尔积中的元素对所组成的集合。

公式：R={(a,b)|a∈A且b∈B}- 函数f：对于集合A和B，如果f是从A到B的一个映射，那么对于任意元素a∈A，都有唯一的元素b∈B与之对应。

公式：f:A→B3. 图论图论是离散数学中的一个重要分支，它研究的是由顶点和边组成的数学结构。

图论的基本概念包括图的类型、路径和回路、连通性、树等。

其相关公式如下：- 有向图：对于图G=(V,E)，如果E中的边是有方向的，则称G为有向图。

公式：G=(V,E)，E={(u,v)|u,v∈V，u→v}- 无向图：对于图G=(V,E)，如果E中的边是无方向的，则称G为无向图。

公式：G=(V,E)，E={{u,v}|u,v∈V，u≠v}- 路径：在图G中，顶点v1,v2,...,vn的一个路径是图G中的一个顶点序列，其中相邻的顶点用一条边连接。

公式：v1,v2, (v)- 回路：在图G中，如果一条路径的起点和终点是同一个顶点，则称其为回路。

离散数学必备知识点总结资料离散数学是指离散的数学概念和结构，独立于连续的数学。

它是在计算机科学、信息科学、数学基础研究、工程技术等领域中的基础课程之一。

以下是离散数学必备的一些知识点总结。

一、逻辑与集合1. 命题与谓词：命题是一个陈述，可以被判断为真或假，而谓词是一种用来描述命题所涉及实体之间关系的语句。

2. 命题逻辑：重点关注命题真假和与或非等运算关系，包括真值表和主范式。

3. 一阶谓词逻辑：注意包含全称量词和存在量词，也包括a|b, a//b等符号的理解。

4. 集合与运算：集合是指不同元素组成的一个整体。

基本的集合运算包括并、交、差等。

5. 关系与函数：关系是一种元素之间的对应关系，而函数是一种具有确定性的关系，即每一个自变量都对应唯一的函数值。

6. 等价关系与划分：等价关系是指满足自反性、对称性和传递性的关系。

划分是指将一个集合分成若干个不相交的子集，每个子集称为一个等价类。

二、图论1. 图的定义和基本概念：图由节点和边构成，节点间的连线称为边。

包括度、路径、连通性等概念。

2. 图的表示方法：邻接矩阵和邻接表。

3. 欧拉图与哈密顿图：欧拉图是指能够一笔画出的图，哈密顿图是指含有一条经过每个节点恰好一次的路径的图。

4. 最短路径与最小生成树：最短路径问题是指在图中找出从一个节点到另一个节点的最短路径。

最小生成树问题是指在图中找出一棵覆盖所有节点的树，使得边权之和最小。

三、代数系统1. 代数结构：包括群、环、域等概念。

2. 群的定义和基本概念：群是在一个集合中定义一种二元运算满足结合律、单位元存在和逆元存在的代数结构。

四、组合数学1. 排列、组合和二项式系数：排列是指从n个元素中任选r个进行排序，组合是指从n个元素中任选r个但不考虑排序，二项式系数是指组合数。

2. 生成函数：将组合数与多项式联系起来的一种工具，用于求出某种算法或结构的某些特定函数。

3. 容斥原理：一个集合的容斥原理指在集合的并、交、补之间的关系。

离散数学知识点整理离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、数理逻辑等领域都有着广泛的应用。

下面为您整理了一些离散数学的关键知识点。

一、集合论集合是离散数学中最基本的概念之一。

集合是由一些确定的、彼此不同的对象组成的整体。

比如，｛1, 2, 3}就是一个集合。

集合的运算包括并集、交集、差集和补集。

并集是将两个集合中的所有元素合并在一起组成的新集合；交集则是两个集合中共同拥有的元素组成的集合；差集是从一个集合中去掉另一个集合中的元素所剩下的元素组成的集合；补集是在给定的全集范围内，某个集合的补集是全集中不属于该集合的元素组成的集合。

集合之间的关系有包含、相等、真包含等。

如果集合 A 的所有元素都属于集合 B，那么 A 包含于 B；如果 A 和 B 的元素完全相同，则 A和 B 相等；如果 A 包含于 B 且 A 不等于 B，那么 A 真包含于 B。

二、关系关系是集合中元素之间的某种联系。

比如在集合{1, 2, 3}中，“小于”就是一种关系。

关系可以用矩阵和图来表示。

矩阵表示法通过 0 和 1 来表示元素之间是否存在关系；图表示法则用节点代表元素，用边表示关系。

关系的性质包括自反性、对称性、反对称性和传递性。

自反性是指每个元素都与自身有关系；对称性是指如果 a 与 b 有关系，那么 b 与 a 也有关系；反对称性是指如果 a 与 b 有关系且 b 与 a 有关系，那么 a ＝b；传递性是指如果 a 与 b 有关系，b 与 c 有关系，那么 a 与 c 有关系。

三、函数函数是一种特殊的关系，对于定义域中的每个元素，在值域中都有唯一的元素与之对应。

函数的类型有单射、满射和双射。

单射是指不同的自变量对应不同的函数值；满射是指函数的值域等于其到达的集合；双射则是既单射又满射。

四、数理逻辑数理逻辑包括命题逻辑和谓词逻辑。

命题是可以判断真假的陈述句。

命题逻辑中的基本运算有与（并且）、或、非、蕴含和等价。

离散数学知识点总结 一、各章复习要求与重点第一章 集 合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。

2、掌握集合的表示法和集合的交、并、差、补等基本运算。

3、掌握集合运算基本规律，证明集合等式的方法。

4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。

[本章重点习题]P5~6，4、6； P14~15，3、6、7； P20，5、7。

[疑难解析] 1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。

2、集合恒等式的证明通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。

实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~⋂=-证明中的特殊作用。

[例题分析]例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。

解}}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A}}2,1{},2{},1{,{)(φρ=B于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ例2 设{}{}Φ=,,,,b a b a A ，试求：(1){}b a A ,-； (2)Φ-A ； (3){}Φ-A ； (4){}{}A b a -,； (5)A -Φ； (6){}A -Φ。

解 (1){}{}{}Φ=-,,,b a b a A (2)A A =Φ- (3){}{}{}b a b a A ,,,=Φ- (4){}{}Φ=-A b a , (5)Φ=-ΦA (6){}Φ=-ΦA 例3 试证明()()()()B A B A B A B A ~~~~⋂⋃⋂=⋃⋂⋃ 证明()()()()()()()()()()()()()()()()()()B A B A B A B A B B B A A B A A B B A A B A B A B A ~~~~~~~~~~~~~⋂⋃⋂=Φ⋃⋂⋃⋂⋃Φ=⋂⋃⋂⋃⋂⋃⋂=⋂⋃⋃⋂⋃=⋃⋂⋃第二章 二元关系[复习知识点]1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 [复习要求]1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。

离散数学知识点总结及应用
知识点1: 集合论
- 集合的定义和表示方法
- 集合的运算：并、交、差、补
- 集合的基本性质和定律
知识点2: 逻辑与命题
- 命题的定义和特性
- 命题的联结词：与、或、非
- 命题的真值表和逻辑运算
- 命题的充分条件和必要条件
知识点3: 关系与函数
- 关系的定义和性质
- 关系的类型：自反、对称、传递、等价
- 函数的定义和基本概念
- 函数的特性和图像
知识点4: 图论
- 图的基本概念和术语
- 图的存储结构：邻接矩阵、邻接表
- 图的遍历算法：深度优先搜索、广度优先搜索
- 最短路径算法：Dijkstra算法、Floyd-Warshall算法
知识点5: 组合数学
- 排列和组合的基本概念
- 排列和组合的计算方法
- 随机变量和概率分布
- 组合数学在密码学等领域的应用
知识点6: 布尔代数
- 布尔代数的基本运算：与、或、非
- 布尔函数的最小化方法
- 布尔代数的应用：逻辑电路设计、编码器等
知识点7: 计算理论
- 自动机的基本概念和分类
- 正则语言和正则表达式
- 文法的定义和性质
- 上下文无关文法和巴科斯范式
知识点8: 数论
- 整数的性质和基本运算
- 质数和分解定理
- 同余关系和同余方程
- 数论在加密算法中的应用
以上是离散数学中的一些主要知识点和应用场景的简要总结，希望对你的研究有所帮助。

离散数学知识点整理离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、物理学等领域都有着广泛的应用。

以下是对离散数学中一些重要知识点的整理。

一、集合论集合是离散数学中最基本的概念之一。

集合是由一些确定的、互不相同的对象组成的整体。

集合的表示方法有列举法、描述法等。

列举法就是将集合中的元素一一列举出来，比如{1, 2, 3}；描述法是通过描述元素所具有的性质来表示集合，例如{x ｜ x 是大于 0 小于 5 的整数}。

集合之间的关系包括子集、真子集、相等。

如果集合 A 的所有元素都属于集合 B，那么 A 是 B 的子集；如果 A 是 B 的子集，且 B 中存在元素不属于 A，那么 A 是 B 的真子集；如果两个集合的元素完全相同，那么它们相等。

集合的运算有并集、交集、差集等。

并集是将两个集合中的所有元素合并在一起组成的新集合；交集是两个集合中共同拥有的元素组成的集合；差集是从一个集合中去掉另一个集合中的元素所得到的集合。

二、关系关系是集合中元素之间的某种联系。

比如在一个班级中，同学之间的“同桌关系”就是一种关系。

关系可以用矩阵和图来表示。

矩阵表示中，若元素之间存在关系则对应的位置为1，否则为0；图表示中，用点表示元素，用线表示关系。

关系的性质包括自反性、对称性、反对称性和传递性。

自反性是指每个元素都与自身有关系；对称性是指如果 a 与 b 有关系，那么 b 与 a 也有关系；反对称性是指如果 a 与 b 有关系且 b 与 a 有关系，那么 a ＝b；传递性是指如果 a 与 b 有关系，b 与 c 有关系，那么 a 与 c 有关系。

关系的运算有复合关系和逆关系。

复合关系是将两个关系组合起来得到新的关系；逆关系是将原关系中的元素顺序颠倒得到的关系。

三、函数函数是一种特殊的关系，对于定义域中的每个元素，在值域中都有唯一的元素与之对应。

函数的类型有单射、满射和双射。

单射是指不同的定义域元素对应不同的值域元素；满射是指值域中的每个元素都有定义域中的元素与之对应；双射是既是单射又是满射。

离散数学笔记第一章命题逻辑合取析取定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句定义 1.2.1合式公式(1)单个命题变元、命题常元为合式公式，称为原子公式。

(2)若某个字符串A 是合式公式，则⌝A、(A)也是合式公式。

(3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A↔B 是合式公式。

(4)有限次使用(2)~(3)形成的字符串均为合式公式。

1.3等值式1.4析取范式与合取范式将一个普通公式转换为范式的基本步骤1.6推理定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。

（用等值演算或真值表）第二章 谓词逻辑2.1、基本概念∀：全称量词 ∃：存在量词一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"∀x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如∃x(H(x)∨WL(x))，即量词的后面为合取式 例题R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ∀x ∀y(R(x)∧T(y)→H(x,y))有的兔子比所有的乌龟跑得快表示为：∃x ∀y(R(x)∧T(y)→H(x,y))2.2、谓词公式及其解释定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22y x 的 f(x,y))、 谓词常元(如表示人类的 H(x))。

定义 2.2.2、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。

离散数学笔记总结一、命题逻辑。

1. 基本概念。

- 命题：能够判断真假的陈述句。

例如“2 + 3 = 5”是真命题，“1 > 2”是假命题。

- 命题变元：用字母表示命题，如p,q,r等。

2. 逻辑联结词。

- 否定¬：¬ p表示对命题p的否定，若p为真，则¬ p为假，反之亦然。

- 合取wedge：pwedge q表示p并且q，只有当p和q都为真时，pwedge q才为真。

- 析取vee：pvee q表示p或者q，当p和q至少有一个为真时，pvee q为真。

- 蕴含to：pto q表示若p则q，只有当p为真且q为假时，pto q为假。

- 等价↔：p↔ q表示p当且仅当q，当p和q同真同假时，p↔ q为真。

3. 命题公式。

- 定义：由命题变元、逻辑联结词和括号按照一定规则组成的符号串。

- 赋值：给命题变元赋予真假值，从而确定命题公式的真值。

- 分类：重言式（永真式）、矛盾式（永假式）、可满足式。

4. 逻辑等价与范式。

- 逻辑等价：若A↔ B是重言式，则称A与B逻辑等价，记作A≡ B。

例如¬(pwedge q)≡¬ pvee¬ q（德摩根律）。

- 范式：- 析取范式：由有限个简单合取式的析取组成的命题公式。

- 合取范式：由有限个简单析取式的合取组成的命题公式。

- 主析取范式：每个简单合取式都是极小项（包含所有命题变元的合取式，每个变元只出现一次）的析取范式。

- 主合取范式：每个简单析取式都是极大项（包含所有命题变元的析取式，每个变元只出现一次）的合取范式。

二、谓词逻辑。

1. 基本概念。

- 个体：可以独立存在的事物，如人、数等。

- 谓词：用来刻画个体性质或个体之间关系的词。

例如P(x)表示x具有性质P，R(x,y)表示x和y具有关系R。

- 量词：- 全称量词∀：∀ xP(x)表示对于所有的x，P(x)成立。

- 存在量词∃：∃ xP(x)表示存在某个x，使得P(x)成立。

离散数学知识点总结离散数学是现代数学的一个重要分支，它在计算机科学、信息科学、物理学等领域都有着广泛的应用。

下面就来对离散数学中的一些重要知识点进行总结。

一、集合论集合是离散数学的基础概念之一。

集合是由一些确定的、互不相同的对象组成的整体。

集合的表示方法有列举法和描述法。

集合之间的关系包括子集、真子集、相等。

集合的运算有并集、交集、补集等。

集合的并集是由属于两个或多个集合中的所有元素组成的集合。

交集则是由同时属于两个或多个集合的元素组成的集合。

补集是在给定的全集 U 中，不属于某个集合 A 的元素组成的集合。

集合的运算遵循一些基本的定律，如交换律、结合律、分配律等。

这些定律在解决集合相关的问题时非常有用。

二、关系关系是集合论中的一个重要概念，它描述了两个集合元素之间的某种联系。

关系可以用集合的形式表示，也可以用关系矩阵和关系图来表示。

关系的性质包括自反性、反自反性、对称性、反对称性和传递性。

不同性质的关系在实际应用中有着不同的意义。

等价关系是一种特殊的关系，它同时具有自反性、对称性和传递性。

等价关系可以将集合中的元素进行分类，形成等价类。

偏序关系也是一种常见的关系，它具有自反性、反对称性和传递性。

偏序关系可以用来描述元素之间的顺序关系，例如在集合的包含关系中。

三、函数函数是一种特殊的关系，它对于定义域中的每个元素，在值域中都有唯一的元素与之对应。

函数的类型包括单射函数、满射函数和双射函数。

函数的复合是将两个函数依次作用，得到一个新的函数。

函数的逆是在函数是双射的情况下存在的，并且逆函数的复合等于原函数。

四、图论图是由顶点和边组成的结构。

图可以分为无向图和有向图。

图的基本概念包括顶点的度、路径、回路、连通性等。

图的存储方式有邻接矩阵和邻接表。

邻接矩阵适合表示稠密图，而邻接表适合表示稀疏图。

图的遍历算法有深度优先搜索和广度优先搜索。

这两种算法在图的处理中经常被用到，例如寻找图中的路径、判断图的连通性等。

离散数学必备知识点总结汇总
1.集合论：集合的概念、元素、子集、交集、并集、差集、补集、空集、集合的运算、集合的等价关系、集合的序关系等。

2.命题逻辑：命题的概念、命题的联接词（与、或、非）、命题的否
定形式、命题的蕴涵、等价命题、命题的充分条件和必要条件、命题的合
取范式和析取范式、蕴涵式、逻辑等价式、命题的否定形式的推理。

3.谓词逻辑：谓词的概念、谓词的量化、全称量化和存在量化、谓词
逻辑的等价式和推理规则、归纳定理和应用。

4.关系：关系的概念、关系的性质、关系的运算、关系的性质和关系
的代数结构。

5.图论：图的概念、图的表示、连通图、树、度数和定理、欧拉图、
哈密顿图、图的平面性质等。

6.混合图：有向图、无向图、有向图和无向图的表示、混合图的回路、可达矩阵、连通度、强连通图等。

7.布尔代数：布尔运算、布尔函数、布尔代数的运算规则、完备性和
最小化。

8.代数结构：半群、群、环、域的定义和性质、同态和同构。

9.组合数学：排列组合、二项式系数、排列、组合、分配原理、鸽巢
原理、生成函数、容斥原理等。

10.图的着色：图的着色问题、邻接矩阵、边界点、图的着色问题的
算法、四色定理等。

11.概率论：基本概念、概率的性质、条件概率、独立事件、贝叶斯定理、随机变量、概率分布函数、期望、方差、协方差、相关系数、大数定理和中心极限定理等。

12.递归：递归关系、递归函数、递归算法、递归树、递归求解等。

离散数学总复习第1章命题逻辑一、命题的判断例：1、仁者无敌！2、x+y<23、如果雪是红的，那么地球是月亮的卫星。

4、我正在说谎。

二、命题符号化例：1、蓝色和黄色可以调成绿色。

2、付明和杨进都是运动员。

3、刘易斯是百米游泳冠军或百米跨栏冠军。

4、李飞现在在宿舍或在图书馆。

5、只要天不下雨，我就步行上学校。

6、只有天不下雨，我才步行上学校。

7、并非只要你努力了，就一定成功。

三、主范式1、会等值演算；2、主合取和主析取范式的相互转换。

例：求命题公式P∨Q的主析取范式和主合取范式。

3、根据主范式进行方案的选择例1：某科研所要从3名科研骨干A,B,C中挑选1-2名出国进修，由于工作需要，选派需同时满足条件：（1）若A去，则C同去；（2）只有C不去，B才去；（3）只要C不去，则A或B就可以去。

问有哪些选派方案？例2：甲、乙、丙、丁四人有且仅有两个人参加比赛，下列四个条件均要满足：（1）甲和乙有且只有一人参加；（2）丙参加，则丁必参加；（3）乙和丁至多有一人参加；（4）丁不参加，甲也不会参加。

问哪两个人参加了比赛？四、简单的推理例1：如果明天天气好我们就去爬长城。

明天天气好。

所以我们去爬长城。

例3：课后习题16第2章谓词逻辑一、谓词逻辑中的命题符号化例：1、所有运动员都是强壮的2、并非每个实数都是有理数3、有些实数是有理数二、量词的辖域，约束变元换名、自由变元代替例：1、∀x(P(x)∨∃yR(x,y))→Q(x)2、∀x(P(x,z)∨∃yR(x,y))→Q(x)中量词的辖域，重名情况，改名等三、命题逻辑永真式的任何代换实例必是谓词逻辑的永真式。

同样，命题逻辑永假式的任何代换实例必是谓词逻辑的永假式。

例：1、(∀xP(x)→∃xQ(x))↔(⌝∀xP(x)∨∃xQ(x))2、(∀xP(x)→∃xQ(x))∧(∃xQ(x))→∀zR(z)))→(∀xP(x) →∀zR(z))1-2是永真式（重言式）3、⌝(∀xF(x) ∃yG(y)) ∧ ∃yG(y) 永假式（矛盾式）四、消量词例：个体域D={1,2}，对∀x∀y(P(x)→Q(y))消量词五、简单的前束范式会判断即可。

离散数学一、逻辑和证明1.1命题逻辑命题：是一个可以判断真假的陈述句。

联接词：∧、∨、→、↔、¬。

记住“p仅当q”意思是“如果p，则q”，即p→。

记住“q除非p”意思是“¬p→q”。

会考察条件语句翻译成汉语。

系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。

1.3命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。

谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如∀x>0P(x)。

当论域中的元素可以一一列举，那么∀xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。

同理，∃xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。

两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如∀x（P(x)∧Q(x))和(∀xP(x))∧(∀xQ(x))。

量词表达式的否定：¬∀xP(x) ⇔∃x¬P(x)，¬∃xP(x) ⇔∀x¬P(x)。

1.5量词嵌套我们采用循环的思考方法。

量词顺序的不同会影响结果。

语句到嵌套量词语句的翻译，注意论域。

嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。

1.6推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。

但有效论证二、集合、函数、序列、与矩阵2.1集合∈说的是元素与集合的关系，⊆说的是集合与集合的关系。

常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。

A和B相等当仅当∀x(x∈A↔x∈B)；A是B的子集当仅当∀x(x∈A→x∈B)；A是B的真子集当仅当∀x(x∈A→x∈B)∧∃x(x∉A∧x∈B)。

幂集：集合元素的所有可能组合，肯定有∅何它自身。

离散数学知识点全归纳离散数学是数学的一个分支，研究的是离散对象和离散结构。

在计算机科学、信息技术以及其他领域中，离散数学具有重要的应用价值。

以下是离散数学的一些重要知识点的全面总结。

1. 集合论和逻辑- 集合：基本概念、运算、包含关系、并集、交集、差集、幂集等。

- 命题逻辑：命题、命题的连接词、真值表、逻辑等价、析取范式、合取范式等。

- 谓词逻辑：谓词、量词、逻辑推理、存在量词和全称量词等。

2. 证明方法- 直接证明：利用已知事实和逻辑推理，直接得出结论。

- 对证法：从假设的反面出发，利用矛盾推理得出结论。

- 数学归纳法：证明基础情况成立，再证明递推步骤成立。

3. 图论- 图的基本概念：顶点、边、路径、回路、度、连通性等。

- 图的表示：邻接矩阵、邻接表等。

- 最短路径：Dijkstra算法、Floyd-Warshall算法等。

- 最小生成树：Prim算法、Kruskal算法等。

4. 关系与函数- 关系及其性质：自反性、对称性、传递性、等价关系等。

- 函数及其性质：定义域、值域、单射、满射、双射等。

- 逆函数和复合函数：求逆函数、复合函数的定义和性质。

5. 组合数学- 排列和组合：排列、组合的计算公式和性质。

- 递归关系：递推公式、递归算法等。

- 图的着色：色数、四色定理等。

6. 代数系统- 半群、幺半群、群、环、整环和域的定义和性质。

- 同态：同态映射、同构等。

- 应用：编码理论、密码学等。

以上是离散数学的一些重要知识点的概括。

深入理解和掌握这些知识，对于解决实际问题和在相关领域中取得成功非常重要。

在学习过程中，建议结合实际例子和习题进行练习，加深对知识的理解和应用能力。

离散数学知识点总结1. 集合论- 集合的基本概念：集合、元素、子集、幂集、并集、交集、差集、补集。

- 集合的运算：德摩根定律、分配律、结合律、交换律。

- 有限集合和无限集合：可数与不可数集合、阿列夫零、阿列夫一。

2. 数理逻辑- 命题逻辑：命题、联结词、真值表、逻辑等价、逻辑蕴含、逻辑独立。

- 一阶谓词逻辑：量词、谓词、解释、满足、逻辑公式、全称量词、存在量词。

- 证明方法：直接证明、间接证明、反证法、数学归纳法。

3. 递归关系和函数- 递归定义：递归方程、初始条件、递归函数。

- 递归函数的例子：阶乘、斐波那契数列。

- 函数的性质：单射、满射、双射、复合函数。

4. 图论- 图的基本概念：顶点、边、路径、回路、图的同构。

- 图的类型：无向图、有向图、简单图、多重图、连通图、强连通图。

- 图的算法：欧拉路径、哈密顿回路、最短路径（Dijkstra算法）、最小生成树（Prim算法、Kruskal算法）。

5. 组合数学- 排列与组合：排列数、组合数、二项式定理。

- 组合恒等式：Pascal三角形、组合恒等式。

- 组合问题：计数原理、Inclusion-Exclusion原理。

6. 布尔代数- 布尔运算：AND、OR、NOT、XOR、NAND、NOR、XNOR。

- 布尔表达式的简化：卡诺图、奎因-麦克拉斯基方法。

- 布尔函数的表示：真值表、卡诺图、逻辑表达式。

7. 关系论- 关系的基本概念：笛卡尔积、自反性、对称性、传递性。

- 关系的类型：等价关系、偏序关系、全序关系。

- 关系的闭包：自反闭包、对称闭包、传递闭包。

8. 树和森林- 树的基本概念：节点、边、根、叶、子树、兄弟、祖先、子孙。

- 特殊类型的树：二叉树、平衡树、B树、B+树。

- 树的遍历：前序遍历、中序遍历、后序遍历、层次遍历。

9. 算法复杂度- 时间复杂度：最好情况、最坏情况、平均情况、大O表示法。

- 空间复杂度：算法空间需求的分析。

- 渐进分析：渐进紧确界、大Θ表示法、小o和大O的非正式描述。

离散数学一、逻辑与证明1、1命题逻辑命题:就是一个可以判断真假的陈述句。

联接词:∧、∨、→、↔、¬。

记住“p仅当q”意思就是“如果p,则q”,即p→。

记住“q除非p”意思就是“¬p→q”。

会考察条件语句翻译成汉语。

系统规范说明的一致性就是指系统没有可能会导致矛盾的需求,即若pq无论取何值都无法让复合语句为真,则该系统规范说明就是不一致的。

1、3命题等价式逻辑等价:在所有可能情况下都有相同的真值的两个复合命题,可以用真值表或者构造新的逻辑等价式。

谓词+量词变成一个更详细的命题,量词要说明论域,否则没有意义,如果有约束条件就直接放在量词后面,如∀x>0P(x)。

当论域中的元素可以一一列举,那么∀xP(x)就等价于P(x1)∧P(x2)、、、∧P(xn)。

同理,∃xP(x)就等价于P(x1)∨P(x2)、、、∨P(xn)。

两个语句就是逻辑等价的,如果不论她们谓词就是什么,也不论她们的论域就是什么,她们总有相同的真值,如∀x(P(x)∧Q(x))与(∀xP(x))∧(∀xQ(x))。

量词表达式的否定:¬∀xP(x) ⇔∃x¬P(x),¬∃xP(x) ⇔∀x¬P(x)。

1、5量词嵌套我们采用循环的思考方法。

量词顺序的不同会影响结果。

语句到嵌套量词语句的翻译,注意论域。

嵌套量词的否定就就是连续使用德摩根定律,将否定词移入所有量词里。

1、6推理规则一个论证就是有效的,如果它的所有前提为真且蕴含着结论为真。

但有效论二、集合、函数、序列、与矩阵2、1集合∈说的就是元素与集合的关系,⊆说的就是集合与集合的关系。

常见数集有N={0,1,2,3、、、},Z整数集,Z+正整数集,Q有理数集,R实数集,R+正实数集,C 复数集。

A与B相等当仅当∀x(x∈A↔x∈B);A就是B的子集当仅当∀x(x∈A→x∈B); A就是B的真子集当仅当∀x(x∈A→x∈B)∧∃x(x∉A∧x∈B)。

离散数学的基础知识点总结第一章命题逻辑1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假；2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积；3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反；4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写；6.真值表中值为1的项为极小项，值为0的项为极大项；7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取；8.永真式没有主合取范式，永假式没有主析取范式；9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假)10.命题逻辑的推理演算方法：P规则，T规则①真值表法；②直接证法；③归谬法；④附加前提法；第二章谓词逻辑1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质；多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；2.全称量词用蕴含→，存在量词用合取^;3.既有存在又有全称量词时，先消存在量词，再消全称量词；第四章集合1.N，表示自然数集，1,2,3……，不包括0；2.基：集合A中不同元素的个数，|A|；3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)；4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2；5.集合的分划：(等价关系)①每一个分划都是由集合A的几个子集构成的集合；②这几个子集相交为空，相并为全(A)；6.集合的分划与覆盖的比较：分划：每个元素均应出现且仅出现一次在子集中；覆盖：只要求每个元素都出现，没有要求只出现一次；第五章关系1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基数2种不同的关系；为mn，A到B上可以定义mn2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系；3.全关系的性质：自反性，对称性，传递性；空关系的性质：反自反性，反对称性，传递性；全封闭环的性质：自反性，对称性，反对称性，传递性；4.前域(domR)：所有元素x组成的集合；后域(ranR)：所有元素y组成的集合；5.自反闭包：r(R)=RUI;x对称闭包：s(R)=RU1-R;传递闭包：t(R)=RU2R U3R U……6.等价关系：集合A上的二元关系R满足自反性，对称性和传递性，则R称为等价关系；7.偏序关系：集合A上的关系R满足自反性，反对称性和传递性，则称R是A上的一个偏序关系；8.covA={<x,y>|x,y属于A，y盖住x}；9.极小元：集合A中没有比它更小的元素(若存在可能不唯一)；极大元：集合A中没有比它更大的元素(若存在可能不唯一)；最小元：比集合A中任何其他元素都小(若存在就一定唯一)；最大元：比集合A中任何其他元素都大(若存在就一定唯一)；10.前提：B是A的子集上界：A中的某个元素比B中任意元素都大，称这个元素是B的上界(若存在，可能不唯一)；下界：A中的某个元素比B中任意元素都小，称这个元素是B的下界(若存在，可能不唯一)；上确界：最小的上界(若存在就一定唯一)；下确界：最大的下界(若存在就一定唯一)；第六章函数2种不同的关系，有m n种不同的函数；1.若|X|=m,|Y|=n,则从X到Y有mn2.在一个有n个元素的集合上，可以有22n种不同的关系，有n n种不同的函数，有n!种不同的双射；3.若|X|=m,|Y|=n，且m<=n，则从X到Y有A m n种不同的单射；4.单射：f:X-Y，对任意x,2x属于X,且1x≠2x，若f(1x)≠f(2x)；1满射：f:X-Y，对值域中任意一个元素y在前域中都有一个或多个元素对应；双射：f:X-Y，若f既是单射又是满射，则f是双射；5.复合函数：fºg=g(f(x));6.设函数f:A-B，g:B-C，那么①如果f,g都是单射，则fºg也是单射；②如果f,g都是满射，则fºg也是满射；③如果f,g都是双射，则fºg也是双射；④如果fºg是双射，则f是单射，g是满射；第七章代数系统1.二元运算：集合A上的二元运算就是2A到A的映射；2. 集合A上可定义的二元运算个数就是从A×A到A上的映射的个数，即从从A×A到A上函数的个数，若|A|=2,则集合A上的二元运算的个数为2*22=42=16种；3. 判断二元运算的性质方法：①封闭性：运算表内只有所给元素；②交换律：主对角线两边元素对称相等；③幂等律：主对角线上每个元素与所在行列表头元素相同；④有幺元：元素所对应的行和列的元素依次与运算表的行和列相同；⑤有零元：元素所对应的行和列的元素都与该元素相同；4.同态映射：<A,*>,<B,^>,满足f(a*b)=f(a)^f(b),则f为由<A,*>到<B,^>的同态映射；若f是双射，则称为同构；第八章群1.广群的性质：封闭性；半群的性质：封闭性，结合律；含幺半群(独异点)：封闭性，结合律，有幺元；群的性质：封闭性，结合律，有幺元，有逆元；2.群没有零元；3.阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律；4.循环群中幺元不能是生成元；5.任何一个循环群必定是阿贝尔群；第十章格与布尔代数1.格：偏序集合A中任意两个元素都有上、下确界；2.格的基本性质：1) 自反性a≤a 对偶: a≥a2) 反对称性a≤b ^ b≥a => a=b对偶:a≥b ^ b≤a => a=b3) 传递性a≤b ^ b≤c => a≤c对偶:a≥b ^ b≥c => a≥c4) 最大下界描述之一a^b≤a 对偶avb≥aA^b≤b 对偶avb≥b5）最大下界描述之二c≤a,c≤b => c≤a^b对偶c≥a,c≥b =>c≥avb6) 结合律a^(b^c)=(a^b)^c对偶av(bvc)=(avb)vc7) 等幂律a^a=a 对偶ava=a8) 吸收律a^(avb)=a 对偶av(a^b)=a9) a≤b <=> a^b=a avb=b10) a≤c,b≤d => a^b≤c^d avb≤cvd11) 保序性b≤c => a^b≤a^c avb≤avc12）分配不等式av(b^c)≤(avb)^(avc)对偶a^(bvc)≥(a^b)v(a^c)13）模不等式a≤c <=>av(b^c)≤(avb)^c3.分配格：满足a^(bvc)=(a^b)v(a^c)和av(b^c)=(avb)^(avc)；4.分配格的充要条件：该格没有任何子格与钻石格或五环格同构；5.链格一定是分配格，分配格必定是模格；6.全上界：集合A中的某个元素a大于等于该集合中的任何元素，则称a为格<A,<=>的全上界，记为1；(若存在则唯一)全下界：集合A中的某个元素b小于等于该集合中的任何元素，则称b为格<A,<=>的全下界，记为0；(若存在则唯一)7.有界格：有全上界和全下界的格称为有界格，即有0和1的格；8.补元：在有界格内，如果a^b=0,avb=1，则a和b互为补元；9.有补格：在有界格内，每个元素都至少有一个补元；10.有补分配格(布尔格)：既是有补格，又是分配格；11.布尔代数：一个有补分配格称为布尔代数；第十一章图论1.邻接：两点之间有边连接，则点与点邻接；2.关联：两点之间有边连接，则这两点与边关联；3.平凡图：只有一个孤立点构成的图；4.简单图：不含平行边和环的图；5.无向完全图：n个节点任意两个节点之间都有边相连的简单无向图；有向完全图:n个节点任意两个节点之间都有边相连的简单有向图；6.无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边；7.r-正则图：每个节点度数均为r的图；8.握手定理：节点度数的总和等于边的两倍；9.任何图中，度数为奇数的节点个数必定是偶数个；10.任何有向图中，所有节点入度之和等于所有节点的出度之和；11.每个节点的度数至少为2的图必定包含一条回路；12.可达：对于图中的两个节点v,j v，若存在连接i v到j v的路，则称i vi与v相互可达，也称i v与j v是连通的；在有向图中，若存在i v到j v的j路，则称v到j v可达；i13.强连通：有向图章任意两节点相互可达；单向连通：图中两节点至少有一个方向可达；弱连通：无向图的连通；(弱连通必定是单向连通)14.点割集：删去图中的某些点后所得的子图不连通了，如果删去其他几个点后子图之间仍是连通的，则这些点组成的集合称为点割集；割点：如果一个点构成点割集，即删去图中的一个点后所得子图是不连通的，则该点称为割点；15.关联矩阵：M(G)，m是i v与j e关联的次数，节点为行，边为列；ij无向图：点与边无关系关联数为0，有关系为1，有环为2；有向图：点与边无关系关联数为0，有关系起点为1终点为-1，关联矩阵的特点：无向图：①行：每个节点关联的边，即节点的度；②列：每条边关联的节点；有向图：③所有的入度(1)=所有的出度(0);16.邻接矩阵：A(G)，a是i v邻接到j v的边的数目，点为行，点为列；ij17.可达矩阵：P(G)，至少存在一条回路的矩阵，点为行，点为列；P(G)=A(G)+2A(G)+3A(G)+4A(G)可达矩阵的特点：表明图中任意两节点之间是否至少存在一条路，以及在任何节点上是否存在回路；A(G)中所有数的和：表示图中路径长度为1的通路条数；2A(G)中所有数的和：表示图中路径长度为2的通路条数；3A(G)中所有数的和：表示图中路径长度为3的通路条数；4A(G)中所有数的和：表示图中路径长度为4的通路条数；P(G)中主对角线所有数的和：表示图中的回路条数；18.布尔矩阵：B(G)，v到j v有路为1，无路则为0，点为行，点为列；i19.代价矩阵：邻接矩阵元素为1的用权值表示，为0的用无穷大表示，节点自身到自身的权值为0；20.生成树：只访问每个节点一次，经过的节点和边构成的子图；21.构造生成树的两种方法：深度优先；广度优先；深度优先：①选定起始点v；②选择一个与v邻接且未被访问过的节点1v；③从v出发按邻接方向继续访问，当遇到一个节点所1有邻接点均已被访问时，回到该节点的前一个点，再寻求未被访问过的邻接点，直到所有节点都被访问过一次；广度优先：①选定起始点v；②访问与v邻接的所有节点1v,2v,……,k v,这些作为第一层节点；③在第一层节点中选定一个节点v为起点；1④重复②③，直到所有节点都被访问过一次；22.最小生成树：具有最小权值(T)的生成树；23.构造最小生成树的三种方法：克鲁斯卡尔方法；管梅谷算法；普利姆算法；（1）克鲁斯卡尔方法①将所有权值按从小到大排列；②先画权值最小的边，然后去掉其边值；重新按小到大排序；③再画权值最小的边，若最小的边有几条相同的，选择时要满足不能出现回路，然后去掉其边值；重新按小到大排序；④重复③，直到所有节点都被访问过一次；（2）管梅谷算法(破圈法)①在图中取一回路，去掉回路中最大权值的边得一子图；②在子图中再取一回路，去掉回路中最大权值的边再得一子图；③重复②，直到所有节点都被访问过一次；（3）普利姆算法①在图中任取一点为起点v，连接边值最小的邻接点2v；1②以邻接点v为起点，找到2v邻接的最小边值，如果最小边值2比v邻接的所有边值都小(除已连接的边值)，直接连接，否则退回1v，1连接v现在的最小边值(除已连接的边值)；1③重复操作，直到所有节点都被访问过一次；24.关键路径例2 求PERT图中各顶点的最早完成时间, 最晚完成时间, 缓冲时间及关键路径.解：最早完成时间TE(v1)=0TE(v2)=max{0+1}=1TE(v3)=max{0+2,1+0}=2TE(v4)=max{0+3,2+2}=4TE(v5)=max{1+3,4+4}=8TE(v6)=max{2+4,8+1}=9TE(v7)=max{1+4,2+4}=6TE(v8)=max{9+1,6+6}=12 最晚完成时间TL(v8)=12TL(v7)=min{12-6}=6TL(v6)=min{12-1}=11TL(v5)=min{11-1}=10TL(v4)=min{10-4}=6TL(v3)=min{6-2,11-4,6-4}=2TL(v2)=min{2-0,10-3,6-4}=2TL(v1)=min{2-1,2-2,6-3}=0 缓冲时间TS(v1)=0-0=0TS(v2)=2-1=1TS(v3)=2-2=0TS(v4)=6-4=2TS(v5=10-8=2TS(v6)=11-9=2TS(v7)=6-6=0TS(v8)=12-12=0关键路径: v1-v3-v7-v825.欧拉路：经过图中每条边一次且仅一次的通路；欧拉回路：经过图中每条边一次且仅一次的回路；欧拉图：具有欧拉回路的图；单向欧拉路：经过有向图中每条边一次且仅一次的单向路；欧拉单向回路：经过有向图中每条边一次且仅一次的单向回路；26.（1）无向图中存在欧拉路的充要条件：①连通图；②有0个或2个奇数度节点；（2）无向图中存在欧拉回路的充要条件：①连通图；②所有节点度数均为偶数；（3）连通有向图含有单向欧拉路的充要条件：①除两个节点外，每个节点入度=出度；②这两个节点中，一个节点的入度比出度多1，另一个节点的入；度比出度少1；（4）连通有向图含有单向欧拉回路的充要条件：图中每个节点的出度=入度；27.哈密顿路：经过图中每个节点一次且仅一次的通路；哈密顿回路：经过图中每个节点一次且仅一次的回路；哈密顿图：具有哈密顿回路的图；28.判定哈密顿图（没有充要条件）必要条件：任意去掉图中n个节点及关联的边后，得到的分图数目小于等于n；充分条件：图中每一对节点的度数之和都大于等于图中的总节点数；29.哈密顿图的应用：安排圆桌会议；方法：将每一个人看做一个节点，将每个人与和他能交流的人连接，找到一条经过每个节点一次且仅一次的回路(哈密顿图)，即可；30.平面图：将图形的交叉边进行改造后，不会出现边的交叉，则是平面图；31.面次：面的边界回路长度称为该面的次；32.一个有限平面图，面的次数之和等于其边数的两倍；33.欧拉定理：假设一个连通平面图有v个节点，e条边，r个面，则v-e+r=2；34.判断是平面图的必要条件：(若不满足，就一定不是平面图)设图G是v个节点，e条边的简单连通平面图，若v>=3，则e<=3v-6；35.同胚：对于两个图G1,G2，如果它们是同构的，或者通过反复插入和除去2度节点可以变成同构的图，则称G1，G2是同胚的；36.判断G是平面图的充要条件：图G不含同胚于K3.3或K5的子图；37.二部图：①无向图的节点集合可以划分为两个子集V1，V2；②图中每条边的一个端点在V1，另一个则在V2中；完全二部图：二部图中V1的每个节点都与V2的每个节点邻接；判定无向图G为二部图的充要条件：图中每条回路经过边的条数均为偶数；38.树：具有n个顶点n-1条边的无回路连通无向图；39.节点的层数：从树根到该节点经过的边的条数；40.树高：层数最大的顶点的层数；41.二叉树：①二叉树额基本结构状态有5种；②二叉树内节点的度数只考虑出度，不考虑入度；③二叉树内树叶的节点度数为0，而树内树叶节点度数为1；④二叉树内节点的度数=边的总数(只算出度)；握手定理“节点数=边的两倍”是在同时计算入度和出度的时成立；⑤二叉树内节点的总数=边的总数+1；⑥位于二叉树第k层上的节点，最多有12 k个(k>=1)；⑦深度为k的二叉树的节点总数最多为k2-1个，最少k个(k>=1)；⑧如果有n个叶子，2n个2度节点，则0n=2n+1；42.二叉树的节点遍历方法：先根顺序（DLR）；中根顺序（LDR）；后根顺序（LRD）；43.哈夫曼树：用哈夫曼算法构造的最优二叉树；44.最优二叉树的构造方法：①将给定的权值按从小到大排序；②取两个最小值分支点的左右子树(左小右大)，去掉已选的这两个权值，并将这两个最小值加起来作为下一轮排序的权值；③重复②，直达所有权值构造完毕；45.哈夫曼编码：在最优二叉树上，按照左0右1的规则，用0和1代替所有边的权值；每个节点的编码：从根到该节点经过的0和1组成的一排编码；。

离散数学知识点归纳一、集合论。

1. 集合的基本概念。

- 集合是由一些确定的、彼此不同的对象组成的整体。

这些对象称为集合的元素。

例如，A = {1,2,3}，其中1、2、3是集合A的元素。

- 集合的表示方法有列举法（如上述A的表示）和描述法（如B={xx是偶数且x < 10}）。

2. 集合间的关系。

- 子集：如果集合A的所有元素都是集合B的元素，则称A是B的子集，记作A⊆ B。

例如，{1,2}⊆{1,2,3}。

- 相等：如果A⊆ B且B⊆ A，则A = B。

- 真子集：如果A⊆ B且A≠ B，则A是B的真子集，记作A⊂ B。

3. 集合的运算。

- 并集：A∪ B={xx∈ A或x∈ B}。

例如，A = {1,2}，B={2,3}，则A∪B={1,2,3}。

- 交集：A∩ B = {xx∈ A且x∈ B}。

对于上述A和B，A∩ B={2}。

- 补集：设全集为U，集合A相对于U的补集¯A=U - A={xx∈ U且x∉ A}。

二、关系。

1. 关系的定义。

- 设A、B是两个集合，A× B的子集R称为从A到B的关系。

当A = B时，R称为A上的关系。

例如，A={1,2}，B = {3,4}，R={(1,3),(2,4)}是从A到B的关系。

2. 关系的表示。

- 关系矩阵：设A={a_1,a_2,·s,a_m}，B={b_1,b_2,·s,b_n}，R是从A到B的关系，则R的关系矩阵M_R=(r_ij)，其中r_ij=<=ft{begin{matrix}1,(a_i,b_j)∈ R0,(a_i,b_j)∉ Rend{matrix}right.。

- 关系图：对于集合A上的关系R，用节点表示A中的元素，若(a,b)∈ R，则用有向边从a指向b。

3. 关系的性质。

- 自反性：对于集合A上的关系R，如果对任意a∈ A，都有(a,a)∈ R，则R 是自反的。

例如，A={1,2,3}，R = {(1,1),(2,2),(3,3)}是自反关系。