2010秋季学期-离散数学-集合论-关系的闭包运算

离散数学（集合论）

集合的基本概念

集合的元素

属于∈

空集∅ 全集

有限集 、⽆限集

集合的元素数（基数）：特别的：| ∅ |=0，|{∅}|=1

集合的特征：确定性、互异性、⽆序性、多样性

集合相等：两个集合A和B的元素完全⼀样

⼦集(subset) ：设A，B是两个集合，若A的元素都是B的元素，则称A是B的⼦集，也称B包含A，或A包含于B记以A ⊆B

若A⊆B，且A≠B，则称A是B的真⼦集(proper subset)，也称B真包含A，或A真包含于B，记以A⊂B

集合的运算及性质：

并集(Union)：

交集(Intersection)：

差集(Difference)：

余集(Complement)：

环和（对称差）：

环积：

集合的算律：

集合的证明题：

集合的幂与笛卡尔积：

幂集的性质：1.

2.

3. 有序n元组(ordered n-tuple)：(a1,a2 ,… ,an)

有序对(ordered pairs)：当n=2 时，将其称作有序对，也称作序偶，或有序⼆元组

有序对特点：1. 若a≠b,则（a，b）≠（b，a）2. 两个有序对(a,b)和(c,d)相等当且仅当a=c，b=d

笛卡⼉积(Cartesian product)：

笛卡⼉积的性质：1. |A×B|=|A| ×|B|；

2. 对任意集合A，有A×∅=∅，∅×A=∅；

3. 笛卡⼉积运算不满⾜交换律，即A×B≠B×A；

4. 笛卡⼉积运算不满⾜结合律，即(A×B)×C≠A×(B×C)

5. 笛卡⼉积运算对并和交运算满⾜分配律

6. 设A，B，C，D是集合，若A⊆C且B⊆D，则A×B ⊆ C×D。

证明集合的包含关系的常⽤⽅法：1. 利⽤定义：⾸先任取x∈A，再演绎地证出x∈B成⽴2. 设法找到⼀个集合T,满⾜A⊆T且T⊆B,由包含关系的传递性有A⊆B.3. 利⽤A⊆B的等价定义,即A∪B=B,A∩B=A或A-B=∅来证.4. 利⽤已知包含式的并、交等运算得到新的包含式5. 反证法

离散数学-⼆元关系、闭包的概念

⼆元关系

设S是⼀个⾮空集合,R是关于S的元素的⼀个条件.假设对S中随意⼀个有序元素对（a,b）,我们总能确定a与b是否满⾜条件R,就称R是S的⼀个关系（relation）.假设a与b满⾜条件R,则称a与b满⾜条件R,则称a与b有关系R,记做aRb;否则称a与b⽆关系R.关系R也成为⼆元关系.定义： 集合 X 与集合 Y 上的⼆元关系是 R=(X, Y, G(R)) 其中 G(R),称为R 的图,是笛卡⼉积 X × Y的⼦集.若 (x,y) ∈ G(R) 则称 x 是 R-关系於 y 并记作 xRy 或 R(x,y).

但常常地我们把关系与其图等价起来,即若 R ⊆ X × Y 则 R 是⼀个关系.

闭包

关系的运算时关系上的⼀元运算。它把给出的关系R扩充成⼀新关系R’，使R’具有⼀定的性质。且所进⾏的扩充⼜是最“节约”的。⽐⽅⾃反。相当于把关系R对⾓线上的元素全改成1。其它元素不变，这样得到的R’是⾃反的。且是修改次数最少的。即是最“节约”的。

⼀个关系R的闭包，是指加上最⼩数⽬的有序偶⽽形成的具有⾃反性，对称性或传递性的新的有序偶集，此集就是关系R的闭包。

设R是集合A上的⼆元关系，R的⾃反（对称、传递）闭包是满⾜下⾯条件的关系R'：

（i）R'是⾃反的（对称的、传递的）；

（ii）R'⊇R。

（iii）对于A上的不论什么⾃反（对称、传递）关系R"，若R"⊇R，则有R"⊇R'。R的⾃反、对称、传递闭包分别记为r(R）、s(R) 和t(R）。

性质1

集合A上的⼆元关系R的闭包运算能够复合。⽐如：ts(R)=t(s(R))

表⽰R的对称闭包的传递闭包，通常简称为R的对称传递闭包。⽽tsr(R)则表⽰R的⾃反对称传递闭包。

性质2

设R是集合A上的⼆元关系，则有

（a）假设R是⾃反的。那么s(R）和t(R）也是⾃反的。

（b）假设R是对称的。那么r(R）和t(R）也是对称的；

（c）假设R是传递的，那么r(R）也是传递的。

离散数学知识点

摘要：

离散数学是计算机科学和数学的一个分支，它专注于非连续结构的研究。本文旨在概述离散数学的核心知识点，包括集合论、逻辑、关系、函数、图论、组合数学和递归等。

1. 集合论

- 集合的基本概念：集合是离散数学的基础，它是一组明确的、无重复的对象的集合。

- 集合运算：包括并集、交集、差集、补集等。

- 幂集：一个集合所有子集的集合。

- 笛卡尔积：两个集合所有可能的有序对的集合。

2. 逻辑

- 命题逻辑：研究命题（声明的真值）和它们之间的关系，如合取、析取、否定等。

- 谓词逻辑：使用量词（如全称量词和存在量词）来表达更复杂的逻辑关系。

- 逻辑推理：包括直接证明、间接证明和归谬法等。

3. 关系

- 关系的定义：一个集合到另一个集合的有序对的集合。

- 关系的类型：自反性、对称性和传递性等。

- 关系的闭包：在给定关系下，集合的最小闭包。

4. 函数

- 函数的定义：一个集合到另一个集合的映射，每个元素有唯一的像。

- 函数的类型：单射、满射和双射。 - 复合函数：两个函数可以组合成一个新的函数。

5. 图论

- 图的基本概念：由顶点（节点）和边组成的结构。

- 图的类型：无向图、有向图、连通图、树等。

- 图的算法：如最短路径、最小生成树、图的着色等。

6. 组合数学

- 排列和组合：从n个不同元素中取出r个元素的不同排列和组合的数量。

- 二项式定理：描述了二项式的幂展开的系数。

- 生成函数：一种编码序列的方法，用于解决复杂的计数问题。

7. 递归

- 递归定义：一个对象通过引用比自己更小的版本来定义。

- 递归函数：在计算机程序中，一个函数调用自身来解决问题。

结论：

离散数学为理解和设计计算机系统提供了基础工具和理论。它的知识点广泛应用于算法设计、数据结构、编程语言理论和数据库等领域。掌握离散数学对于任何希望在计算机科学领域取得进展的人来说都是至关重要的。

本文提供了一个简洁的离散数学知识点概述，每个部分都直接针对一个主题，避免了不必要的背景信息和解释。文章的结构逻辑清晰，语言准确，适合作为教育资源或参考资料。如果需要进一步的详细信息或特定主题的深入探讨，请提供更具体的指导。

注意/技巧：

析取符号为V，大写字母V

x + y = 3不是命题

前件为假时，命题恒为真

运用吸收律

命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。也就是说，在不改变原意的基础上，按照最简单的方式翻译

通用的方法：真值表法

VxP（x）蕴含存在xP（x）

利用维恩图解题

证明两个集合相等：证明这两个集合互为子集

常用的证明方法：任取待证集合中的元素<,>

构造相应的图论模型

第一章 命题逻辑

命题和联结词

命题的条件：表达判断的陈述句、具有确定的真假值。选择题中的送分题

原子命题也叫简单命题，与复合命题相对

简单联结词的真值表要记住

非（简单）

合取（当且仅当P，Q都为真时，命题为真）

析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或 条件（→）（当且仅当P为真，Q为假时，命题为假）

P是前件，Q是后件

只要P，就Q等价于P→Q

只有P，才Q等价于非P→非Q，也就是Q→P

P→Q特殊的表达形式：P仅当Q、Q每当P

双条件（↔）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）

命题公式

优先级由高到低：非、合取和析取、条件和双条件

括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去

重言式（永真式）、矛盾式（永假式）、偶然式

可满足式：包括重言式和偶然式

逻辑等价和蕴含

（逻辑）等价:这是两个命题公式之间的关系，写作“⇔”，要与作为联结词的↔区分开来。

如果命题公式A为重言式，那么A⇔T

常见的命题等价公式：需要背过被标出的，尽量去理解。关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！

验证两个命题公式是否等价：当命题变元较少时，用真值表法。当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则

定理：设A、B是命题公式，当且仅当A↔B是一个重言式时，有A和B逻辑等价。