闭包和等价关系

2023学堂在线网课《离散数学》课后作业单元考核答案第一单元答案1.1题目：在集合 {1, 2, 3, 4} 上定义一个二元关系 R，其中 R = {(1,1), (2,2), (3,3), (4,4), (1,4), (4,1)}。

给出 R 的自反、对称、反对称和传递性特点。

•自反特性：对于任意元素x ∈ {1, 2, 3, 4}，都存在 (x, x) ∈ R。

所以，R 是自反的。

•对称特性：对于任意的(x, y) ∈ R，都存在(y, x) ∈ R。

所以，R 是对称的。

•反对称特性：对于任意的(x, y) ∈ R，如果存在 (y, x) ∈ R，那么 x = y。

所以，R 是反对称的。

•传递性特性：对于任意的(x, y) ∈ R 和(y, z) ∈ R，都存在(x, z) ∈ R。

所以，R 是传递的。

1.2题目：在集合 {1, 2, 3, 4} 上定义一个二元关系 R，其中 R = {(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)}。

给出 R 的自反、对称、反对称和传递性特点。

•自反特性：对于任意元素x ∈ {1, 2, 3, 4}，都存在 (x, x) ∈ R。

所以，R 是自反的。

•对称特性：对于任意的(x, y) ∈ R，都存在(y, x) ∈ R。

所以，R 是对称的。

•反对称特性：对于任意的(x, y) ∈ R，如果存在 (y, x) ∈ R，那么 x = y。

所以，R 是反对称的。

•传递性特性：对于任意的(x, y) ∈ R 和(y, z) ∈ R，都存在(x, z) ∈ R。

所以，R 是传递的。

第二单元答案2.1题目：证明或给出一个反例：若 R 是集合 A 上的一个等价关系，且对于任意 a, b ∈ A，有 (a, b) ∈ R 或 (b, a) ∈ R，那么 A 必然可以划分为若干等价类。

假设 R 是集合 A 上的一个等价关系，且对于任意a, b ∈ A，有(a, b) ∈ R 或(b, a) ∈ R。

离散数学集合与关系离散数学是数学中一门独立的分支，它主要研究离散的数学结构和被限制在有限范围的对象。

集合论和关系理论是离散数学的重要组成部分，它们在计算机科学、信息科学等领域具有广泛的应用。

一、集合的概念与基本运算集合是离散数学中最基本的概念之一，它是由确定的元素所组成的整体。

集合的表示通常使用大写字母，元素用小写字母表示，并用花括号{}括起来。

例如，集合A={1,2,3,4}表示由元素1,2,3,4组成的集合A。

在集合论中，集合之间的关系可以通过特定的运算来描述。

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

并集是指所有属于被操作的集合的元素的集合。

交集是指同时属于所有被操作的集合的元素的集合。

差集是指属于一个集合而不属于另一个集合的元素的集合。

补集是指在全集中属于一个集合而不属于另一个集合的元素的集合。

二、关系的定义与性质关系是描述集合之间元素之间的某种联系或者规律的数学概念。

在离散数学中，关系可以用二元组的形式表示。

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

自反性是指元素与自身之间存在关系。

对称性是指如果两个元素之间存在关系，那么它们之间的关系是互逆的。

传递性是指如果两个元素之间存在关系，并且与另一元素之间也存在关系，那么这两个元素之间也存在关系。

三、集合的基数与幂集集合的基数是指集合中的元素个数。

若集合A中的元素个数为n，则记作|A|=n。

基数为有限值的集合称为有限集，基数为无限值的集合称为无限集。

幂集是指一个集合的所有子集所组成的集合。

例如，对于集合A={1,2}，它的幂集为{{},{1},{2},{1,2}}。

幂集的基数等于原集合的基数的2的幂次方。

四、关系的类型与性质在离散数学中，关系可以分为几种不同的类型。

常见的关系类型包括等价关系、序关系和函数关系。

等价关系是指满足自反性、对称性和传递性的关系。

序关系是指满足自反性、反对称性和传递性的关系。

函数关系是指每个定义域中的元素都有唯一对应的值域中的元素的关系。

1.内容及范围主要来自 ppt，标签对应书本2.可能有错，仅供参考离散数学知识点说明：定义：红色表示。

定理性质：橙色表示。

公式：蓝色表示。

算法: 绿色表示页码：灰色表示数理逻辑：1.命题公式：命题，联结词(⌝，∧，∨，→，↔)，合式公式，子公式2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集5.推理理论：重言蕴含式，有效结论，P 规则，T 规则， CP 规则，推理6.谓词与量词:谓词，个体词，论域，全称量词，存在量词7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入8.公式语义:解释，赋值，有效的，可满足的，不可满足的9.前束范式:前束范式10.推理理论:逻辑蕴含式，有效结论，∀-规则（US），∀+规则（UG），∃-规则(ES)，∃+规则(EG), 推理集合论：1.集合: 集合, 外延性原理, ∈, ⊆, ⊂, 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R),对称闭包 s(R), 传递闭包 t(R)4.等价关系: 等价关系, 等价类, 商集, 划分5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数结构：1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零元,逆元2.代数系统：代数系统，子代数，积代数，同态，同构。

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

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

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

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

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

2、掌握求复合关系与逆关系的方法。

3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。

4、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。

5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。

6、理解函数概念：函数、函数相等、复合函数和反函数。

7、理解单射、满射、双射等概念，掌握其判别方法。

第三章命题逻辑[复习知识点]１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题２、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式４、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）５、公式的蕴涵与逻辑结果６、形式演绎本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎[复习要求]１、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。

等价关系和划分1.等价关系定义：如果集合A上的等价关系R是自反的、对称的和传递的，则称R是等价关系。

1）自反性：A上的每一个芫荽都和自己等价；2）对称性：如果a等价于b，则b也等价于a，在有向图中，如果有从a到b的弧，则也有从b到a的弧。

3）传递性：如果a等价于b，b等价于c，则a等价于c.在有向图中，如果a 到c有一条路径，则a到此有一条弧。

4）数中的相等关系、集合中的相等关系、命题演算中的⇔关系都是等价关系。

5）空集合中的二元关系时等价关系。

定理：设k是一个正整数而Iba∈、.如果对某整数kmbam⋅=-,，则a和b是模k等价，写成)mod(kba≡整数k叫做等价的模数。

定理：模k等价是任何集合IA⊆等等价关系。

定义：设R是集合A上的等价关系，对每一个Aa∈，a关于R的等价类是集合}|{xRax，记为[]R a，或者[]a；称a是等价类[]a的表示元素。

如果等价类个数有限，则R的不同等价类的个数叫做R的秩；否则秩是无限的。

定理：设R是非空集合A上的等价关系，aRb当且仅当[][]ba=。

证明：充分性：aRbbabaa∴∈∴=∈],[],[][必要性：][][].[][,][][].[.,,,],[,baabbabx xRbaRbxRaaxbaR=∴⊆⊆∴∈∴∈∀。

同理又传递性可知又以上说明：一个等价类中的任意元素都可以作为此等价类的表示元素。

因为对同一等价类中的任两个元素a和b，都有aRb。

定理：设R是集合A上的等价关系，则对于所有Aba∈,，或者][][ba=，或者φ=][][ba 。

证明：][][][],[][,][][b c a b c a c b a ==∈∈∃≠则和φ 。

又非空][],[b a ，][][][][b a b a =≠和φ 不可兼得。

以上说明，不同的等价类是不相交的。

定义：给定非空集合A 和非空集合族},...,{21m A A A =π，如果 mi i A A 1==，则称集合族π是A 的覆盖。