ch7(代数结构基本知识)(2)

离散数学课件。主要讲述了离散数学课程的部分基础知识。

第七章代数结构基本知识计算机系网络所：张小平 zhxp@http://doc.guandang.net

离散数学课件。主要讲述了离散数学课程的部分基础知识。

主要内容 7.1集合与映射 7.2等价关系 7.3代数系统的概念 7.4同构与同态

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 定义7.2.0设A,B是集合，称集合

{ a, b

| a∈ A, b∈ B}

是A和B的笛卡儿积，记为A×B

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 对于集合 A到集合 B的任何一个映射 f,都b可以写出很多二元组 (a, b ),其中 a∈ A,∈ B。

显然，这是A×B的子集。 我们将映射的概念加以推广，即定义域不一定是A本身，就引出二元关系。

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 定义7.2.1集合 A和 B的笛卡儿积 A×B的任一子集 R称为A与 B之间的一个二元关系，它的元素是有序对 (a, b ),记为 a R b,其中a∈ A, b∈ B。当 (a, b ) R

时，说 a与 b没有 R

关系，记作 a R b。 当A=B时，称 R为集合 A上的二元关系

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 定义7.2.2设R是集合A上的二元关系，如果1.对所有的a∈ A,都有a R a,即R具有自反性 2.对所有的a, b∈ A,若a R b,则b R a,即R具有对称性 3.对所有的a, b, c∈ A,若a R b,b R c,则a R c,即R具有传递性

则称 R是 A上的等价关系。用符号~表示。

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 设R是集合 A上的一个等价关系，对任一元素 a∈ A,可以把所有与 a有 R关系的元素构成一个集合，称之为A的一个等价类，记做 a,即 a={x∈ A| x~ a}其中，a为该等价类的代表元

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 等价类 a的性质：1. a∈ a 2.若 b, c∈ a,则 b~ c等价类中任两个元素都有等价关系！

3.若 b∈ a且 b~ x,则 x∈ a任两个有等价关系的元素都在同一等价类中！

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 定理7.2.1设~是 A上的一个等价关系，对任意元素 a, b∈ A若非则有b=a bIa=φ

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 定理7.2.2设 a1, a2,L, an是 A上由等价关系~确定的全部等价类，那么

U a1= Ai=1

n

ai I a j=φi≠ j

集合 A上的等价关系~可确定它的一个划分！

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 把由等价关系~确定的等价类的集合称为等价类族，用 A表示：A=

{ a| a∈ A}

为表示等价类族是由等价关系~确定的，常使用记号A/~表示 A,并称之为集合 A关于~的商集商集就是由A上等价关系~确定的等价类的集合

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 商集A/~确定后，对每一个 a∈ A,它必定属于唯一的等价类，即对应商集中某个确定元a。 令映射γ: a→ a为集合 A到 A/~的一个映射，称之为 A到 A/~的自然映射 显然，自然映射为满射

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 思考–集合A上的等价关系~可以确定A的一个划分–那么，如果给定集合A的一个划分，能否确定一个集合A上的等价关系呢？

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系 定理7.2.3集合A的一个划分可以确定A的一个等价关系！

证明：–假定 A= U Ai, (i= 1,2,L, n)–构造关系R:R={( x, y )| Ai, x∈ Ai且y∈ Ai}

–如果能够证明A上的关系R满足自反性、对称性、传递性，即可说明该关系为等价。

离散数学课件。主要讲述了离散数学课程的部分基础知识。

等价关系-小结 基本概念：–二元关系、等价关系–等价类、代表元

等价类的性质–等价类的基本性质–商集的概念–等价类与集合划分的关系

离散数学课件。主要讲述了离散数学课程的部分基础知识。

主要内容 7.1集合与映射 7.2等价关系 7.3代数系统的概念 7.4同构与同态