7.6、7.7教案

发布时间：2020-03-01 19:46:45 来源：范文大全收藏本文下载本文手机版

7.6 等价关系与划分

主要内容

 等价关系的定义与实例  等价类及其性质  商集与集合的划分

 等价关系与划分的一一对应

一、等价关系的定义与实例

定义7.15 设R为非空集合上的关系.如果R是自反的、对称的和传递的, 则称R为A上的等价关系. 设 R 是一个等价关系, 若∈R, 称 x等价于y, 记做x～y.

实例

设 A={1,2,…,8}, 如下定义A上的关系R：

R={| x,y∈A∧x ≡ y(mod 3)} 其中x ≡ y(mod 3)叫做 x与 y 模3相等, 即x除以3的余数与y除以3的余数相等.不难验证 R 为A上的等价关系, 因为

(1) x∈A, 有 x ≡ x (mod 3) (2) x,y∈A, 若x ≡ y(mod 3), 则有y ≡ x(mod 3)

(3) x,y,z∈A, 若x ≡ y(mod 3), y ≡ z(mod 3), 则有x ≡ z(mod 3)

模 3 等价关系的关系图

二、等价类定义

定义7.16 设R为非空集合A上的等价关系, x∈A，令

[x]R = {y | y∈A∧xRy} 称[x]R 为x关于R的等价类, 简称为x的等价类, 简记为[x]或

实例

A={1, 2, … , 8}上模3等价关系的等价类：

[1] = [4] = [7] = {1, 4, 7}

[2] = [5] = [8] = {2, 5, 8}

[3] = [6] = {3, 6}

三、等价类的性质

定理7.14 设R是非空集合A上的等价关系, 则

(1) xA, [x]是A的非空子集

(2) x,yA, 如果 xRy, 则 [x] = [y] (3) x,yA, 如果 x

y, 则 [x]与[y]不交 (4) ∪{[x] | xA}=A

四、商集与划分

定义7.17 设 R 为非空集合A上的等价关系, 以 R 的所有等价类作为元素的集合称为A关于R的商集, 记做A/R,

A/R = {[x]R | x∈A} 实例设 A={1,2,…,8}，A关于模3等价关系R的商集为 A/R = {{1,4,7}, {2,5,8}, {3,6}} A关于恒等关系和全域关系的商集为：

A/IA = {{1}, {2}, …, {8}}， A/EA = {{1,2,…,8}}

定义7.18 设A为非空集合, 若A的子集族π(π  P(A))满足: (1)  π

(2) xy(x,yπ∧x≠y→x∩y=) (3) ∪π = A

则称π是A的一个划分, 称π中的元素为A的划分块.例10 设 A＝{ a, b, c, d }, 给定 1, 2, 3, 4, 5, 6如下：

1={{ a, b, c },{ d }}

2={{ a, b}, { c }, { d }}

3={{ a }, { a, b, c, d }}

4={{ a, b}, { c }}

5={,{ a, b }, { c, d }}

6={{ a, { a }}, { b, c, d }} 则 1和 2是A的划分, 其他都不是A的划分.

例11

给出 A＝{1,2,3}上所有的等价关系 7.7 偏序关系

主要内容

 偏序关系

偏序关系的定义

偏序关系的实例

 偏序集与哈斯图

 偏序集中的特殊元素及其性质

极大元、极小元、最大元、最小元

上界、下界、最小上界、最大下界

一、定义与实例

定义7.19 偏序关系：非空集合A上的自反、反对称和传递的关系，记作≼.设≼为偏序关系, 如果 ∈≼, 则记作 x ≼ y, 读作x“小于或等于”y.

实例

集合A上的恒等关系 IA是 A上的偏序关系.

小于或等于关系, 整除关系和包含关系也是相应集合上的偏序关系. 定义7.20 设 R 为非空集合A上的偏序关系,

(1) x, y∈A, x与y可比 

x ≼ y∨y ≼ x

(2) 任取元素 x 和 y, 可能有下述几种情况发生：

x ≺ y (或 y ≺ x),

x＝y,

x与y不是可比的

定义7.21 R 为非空集合A上的偏序关系,

(1) x,y∈A, x与y都是可比的，则称R为全序（或线序）

实例：数集上的小于或等于关系是全序关系,整除关系不是正整数集合上的全序关系定义7.22 x,y∈A, 如果 x≺y 且不存在 z∈A 使得 x≺z≺y, 则称 y覆盖x.例如{1,2,4,6}集合上整除关系, 2覆盖1, 4和6覆盖2, 4不覆盖1. 定义7.23 集合A和A上的偏序关系≼一起叫做偏序集, 记作.

实例:

二、哈斯图: 利用偏序关系的自反、反对称、传递性进行简化的关系图

特点：

(1) 每个结点没有环

(2) 两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前 (3) 具有覆盖关系的两个结点之间连边

例12 偏序集和的哈斯图.

例13 已知偏序集的哈斯图如下图所示, 试求出集合A和关系R的表达式.

三、偏序集中的特殊元素

定义7.24 设为偏序集, BA, y∈B (1) 若x(x∈B→y≼x)成立, 则称 y 为B的最小元 (2) 若x(x∈B→x≼y)成立, 则称 y 为B的最大元

(3) 若x(x∈B∧x≼y→x=y)成立, 则称 y 为B的极小元 (4) 若x(x∈B∧y≼x→x=y)成立, 则称 y 为B的极大元性质：

(1) 对于有穷集，极小元和极大元一定存在，可能存在多个. (2) 最小元和最大元不一定存在，如果存在一定惟一.(3) 最小元一定是极小元；最大元一定是极大元. (4) 孤立结点既是极小元，也是极大元.定义7.25 设为偏序集, BA, y∈A

(1) 若x(x∈B→x≼y)成立, 则称y为B的上界