河北工业大学计算机科学技术与软件学院离散数学
Discrete Mathematics
郭永芳
guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn
3－ 1 集合的概念及其表示法一,集合的概念及表示集合,集合是数学中最基本的概念之一,不能以更简单的概念来定义 (define),只能给出它的描述 (description)。 一些具有共同性质的对象的整体就称为一个集合,这个整体的每个对象称为该集合的一个 元素 (member或
element)。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法
用大写字母 A,B,C等表示集合,用小写字母 a,
b,c等表示集合的元素
·a?A表示,a是集合 A的元素,或说 a属于集合 A
·a?A表示,a不是集合 A的元素，或说 a不属于集合 A
集合的元素还可以是一个集合。
Guoyongfang.2006@yahoo.com.cn
一个集合，若其组成集合的元素的个数是有限的，则称作有限集，否则称为无限集。
集合中的元素是无序的，不重复的 。
集合的概念及其表示法
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法通常使用两种方法来给出一个集合：
·列元素法：列出某集合的所有元素,如：
·A = {0,1,2,3,4,5,6,7,8,9}表示所有小于 10的自然数所构成的集合
·B = {a,b,?,z} 表示所有小写英文字母所构成的集合
·性质概括法：使用某个性质来概括集合中的元素,
如,·A = { n | n 是小于 10的自然数 }
·C = { n | n 是质数 }表示所有质数所构成的集合
·D= { x | p（ x） } 如果 p(x)为真,则 x属于 D,否则 x不属于 D。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法二、集合的相等与子集外延性原理：
集合相等：两个集合 A和 B相等，当且仅当它们具有相同的成员，记为 A = B，即 a
属于集合 A当且仅当 a属于集合 B。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法子集,设 A,B是任意两个集合 B，假如 A的每一个元素是 B的成员，则称 A为 B的子集，或 A
包含在 B内，或 B包含 A。记为 A?B。如果集合
A的每一个元素都属于 B，但集合 B中至少有一个元素不属于 A，则称 A为 B的真子集，即 A?B
且 A不等于 B(A? B)。
一个集合 A的 平凡子集 有,A和?
定理,集合 A和 B相等的充要条件是两个集合相等互为子集。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法空集,不包含 任何元素的集合，称为空集，记为?。
定理,空集是任何集合的子集。
全集,在一定范围内，如果所有集合均为某一集合的子集。则称该集合为全集。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法三、幂集幂集,集合 A的幂集，记为 P(A)，是 A的所有子集所构成的集合，即：
·P(A) = { B | B? A }
·例如,A = {0,1},则 P(A) = {?,{0},{1},{0,
1} }
·显然，对任意集合 A，有 P(A)和 A?P(A)
定理,如果有限集合 A有 n个元素，则其 幂集
P(A)有 2n个元素。
Guoyongfang.2006@yahoo.com.cn
第一节作业
3-1习题
（ 2）（ 4） a,b,c （ 7）
Guoyongfang.2006@yahoo.com.cn
3-2集合的运算一、集合的交集合的 交,设任意集合 A和 B，由集合 A和 B的所有共同元素组成的集合，称为集合 A和 B的交集，记作 A?B。
S=A?B = {x | x?A? x?B}
集合的交也可推广到多个集合，设 A1,A2,…,An都是集合，它们的交定义为：
A1?A2…?An = {x |?i(x?Ai)}
Guoyongfang.2006@yahoo.com.cn
集合的运算二、集合的并集合的 并,设任意集合 A和 B，由所有属于集合 A或属于 B的元素组成的集合 S，称为集合 A和 B的并集，
记作 A?B 。
S=A?B = {x | x?A? x?B}
集合的并可推广到多个集合，设 A1,A2,…,An都是集合，它们的并定义为：
A1?A2…?An = {x |?i(x?Ai)}
Guoyongfang.2006@yahoo.com.cn
集合的运算三、集合的补集合的 补,设任意集合 A和 B，所有属于集合 A而不属于 B的一切元素组成的集合 S，称为集合 B 对于 A的补集或相对补，
记作 A?B 。
A?B = {x | x?A?x?B}。
A?B 也称为集合 A和 B的差。
绝对补,设 E为全集，对任一集合 A关于 E的补 E?A，称为集合
A的绝对补,记作 ~A。
~A= E?A= {x | x?E? x?A}。
Guoyongfang.2006@yahoo.com.cn
集合的运算四、集合的对称差集合的 对称差,设任意集合 A和 B,A和 B的 对称差为集合 S，其 元素属于集合 A，或属于 B，但不能既属于集合 A又属于 B，记作 A?B 。
A?B = (A?B)? (A?B) 。
Guoyongfang.2006@yahoo.com.cn
集合的运算用文氏图表示集合的运算：
Guoyongfang.2006@yahoo.com.cn
（ 1） 等幂律 A∪ A=A
A∩ A=A
（ 2） 结合律 (A∪ B)∪ C=A∪ (B∪ C)
(A∩ B)∩ C=A∩ (B∩ C)
（ 3） 交换律 A∪ B=B∪ A
A∩ B=B∩ A
Guoyongfang.2006@yahoo.com.cn
（ 4） 分配律
A∪ (B∩ C)=(A∪ B)∩ (A∪ C)
A∩ (B∪ C)=(A∩ B)∪ (A∩ C)
（ 5） 幺律
A∪?=A
A∩ U=A
Guoyongfang.2006@yahoo.com.cn
（ 6） 零律 A∪ U=U
A∩?=?
（ 7） 补律 A∪ A’=U
A∩ A’=?
（ 8） 吸收律 A∪ (A∩ B)=A
A∩ (A∪ B)=A
Guoyongfang.2006@yahoo.com.cn
（ 9） 德 ·摩根律
~(A∪ B)＝ ~ A∩ ~ B
~(A∩ B)＝ ~ A∪ ~ B
（ 10） 对合律 ~ (~A)=A
Guoyongfang.2006@yahoo.com.cn
集合的运算五、集合运算的性质：
~ (~ A) = A ~? = E ~ E =? A? ~A=E
A? ~ A =?
A?B = B?A A?(B?C) = (A?B)?C
A= A A?A =?
A?B= (A? ~B)? (~ A? B)
Guoyongfang.2006@yahoo.com.cn
集合的运算续：
(A?B)?A (A?B)?B A?(A?B) B?(A?B) (A?B)?A
A?B? (A?B) = B? (A?B) = A? (A?B) =?
(A?B) = (A? ~B)
A?B = A?C? B = C
A?(B-C) = (A? B)?(A? C)
Guoyongfang.2006@yahoo.com.cn
3－ 4序偶与笛卡尔积一,序偶定义 由两个元素 x,y按照一定的次序组成的二元组称为 有序偶对 (序偶 ),记作
<x,y>,其中 x为第一个元素,y为第二个元素 。 常常表达两个客体之间的关系 。
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积例,平面上点的坐标 <x,y>； 中国地处亚洲 <中国,亚洲 >，
<上,下 >,<左，右 >等都是有 序对。 <操作码,地址码 >则为一条单地址指令 。
定义 两个 序偶相等
<x,y>＝ <u,v>当且仅当 x＝ u,y＝ v。
序偶与集合的区别
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积定义 由 N个元素 a1,a2,a3,…,an按照一定的次序组成的 N元组称为 N重有序组,记作
<a1,a2,a3,…,an>即：
<a1,a2,a3,…,an>＝ <<a1,a2,a3,…,an-1>,an>。
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积例,a年 b月 c日 d时 e分 f秒可用下述六重有序组来描述,<a,b,c,d,e,f>。
性质 <a1,a2,a3,...,an>＝ <b1,b2,b3,…,bn>当且仅当 ai＝ bi。 (i＝ 1,2,3,...n)。
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积二,笛卡尔积定义 设 A,B是两个集合,若序偶的第一个成员是 A
的元素,第二个成员是 B的元素,所有这样序偶的集合,称为 A和 B的 笛卡尔积 或 直积 。 记作
A× B,
A× B＝ {<x,y>|(x∈ A)∧(y ∈ B)}。
Guoyongfang.2006@yahoo.com.cn
A× B＝ {<x,y>|(x∈A)∧(y∈B)};
序偶与笛卡尔积
B
A
例：
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积
× × × ×
× × × ×
× × × ×
× × × ×
1 2 3 4
a
b
c
d
D
C
C× D＝ {<x,y>|(x∈C)∧(y∈D)}
＝ {<1,a>,<1,b>,<1,c>,<1,d>,<2,a>,<2,b>,<2,c>,<2,d>,
<3,a>,<3,b>,<3,c>,<3,d>,<4,a>,<4,b>,<4,c>,<4,d>}。
例：
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {1,2},B＝ {a,b}
则 A× B＝ {<1,a>,<1,b>,<2,a>,<2,b>}；
而 B× A＝ {<a,1>,<a,2>,<b,1>,<b,2>｝。
由于 <1,a>≠<a,1>,<1,b>≠<b,1>,…,知：
A× B≠B × A 但 |A× B|＝ |B× A|＝ |A|× |B|。
因此，一般情况下，对任何两个集合 A,B，
当 A≠B 时，有,A× B≠B × A，
当 A＝ B时，有,A× B＝ B× A＝ A2。
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
笛卡尔积有如下性质：
1,A=?且A =?
2,不适合交换律,即 A?B不一定等于
B?A。
3,不适合结合律,即 A?(B?C)不等于
(A?B)?C。
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
笛卡尔积有如下性质 (续 )：
4,笛卡尔积运算对并和交运算满足分配律,即：
A?(B?C) = (A?B)?(A?C)
(B?C)?A = (B?A)?(C?A)
A?(B?C) = (A?B)?(A?C)
(B?C)?A = (B?A)?(C?A)
5,设 A,B,C,D是非空集合，则有 A?C,B?D?
A?B?C?D。
6,若 C非空，则
A?B? A?C?B?C?C?A?C?B
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
例,设 A,B,C,D为 4个集合,有：
1.A?B =?当且仅当 A =?或 B =?。
2.A,则 A?B?A?C当且仅当 B?C
3,A?C且 B?D,则 A?B?C?D,并且当
A = B =?或 A且 B时,其逆为真 。
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
定义 设 A1,A2,…,An是 N个集合，称下述集合：
A1× A2× … × An
＝ {<a1,a2,…,an>|(ai∈A i)∧i∈ {1,2,…,n}}
为由 A1,A2,A3,...,An构成的 笛卡尔积 。
当 A1＝ A2＝ … ＝ An时,A1× A2× … × An＝ An。
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
一、关系 定义
R,R中任一序偶 <x,y>可 记为 <x,y>∈ R 或 xRy。
不在 R中任一序偶 <x,y>可 记为 <x,y>?R，或 xRy。
3-5、关系及其表示
Guoyongfang.2006@yahoo.com.cn
3-5、关系及其表示定义 设 R为二元关系，由 <x,y>∈ R的所有 x
组成的集合 称为 R的 前域,即
dom R = {x |?y(xRy) }
使 <x,y>∈ R的所有 y组成的集合 称为 R的 值域,即
ran R = {y |?x(xRy) }
R的前域 和 值域 一起 称为 R的 域,记作 FLD R,即
FLD R= dom R ∪ ran R
Guoyongfang.2006@yahoo.com.cn
例,设 R1＝ {<x,y>|(x,y?I)∧(x≤y)} ；
R2＝ {<x,y>|(x,y?I)∧(x 2+y2＝ 1)}；
R3＝ {<x,y>|(x,y?I)∧(|x| ＝ |y|＝ 3)}；
R4＝ {<x,y>|(x,y?I)∧(|x| ＝ y)}。
都是定义在整数集 I上的关系，求它们的定义域和值域。
关系及其表示解,domR1＝ I,ranR1＝ I；
domR2＝ {0,1,-1},ranR2＝ {0,1,-1}；
domR3＝ {3,-3},ranR3＝ {3,-3}；
domR4＝ I,ranR4=0,1,2… 。
Guoyongfang.2006@yahoo.com.cn
定义 X,Y为两个集合,X× Y的任何一个子集 R所定义的二元关系称为 从 X到 Y的二元关系,
简称关系 (Relation)。
把 X× Y的两个平凡子集 X× Y和?,分别称为
X到 Y的 全域关系 和 空关系 。
如 R是从 X到 X的二元关系，则称 R为 X上的二元关系 。
关系及其表示
Guoyongfang.2006@yahoo.com.cn
关系及其表示关系的数目：
由于任何 A× B的子集都是一个二元关系，
按照子集的定义，知 A× B共有 2|A|╳|B| 个不同的子集。因此，从 A到 B不同的关系共有 2|A|╳|B| 个。
恒等关系,设 Ix是 X的二元关系且满足 Ix =
{<x,x>|x?X},则称 Ix 是 X上的恒等关系。
Guoyongfang.2006@yahoo.com.cn
二、关系运算设 R,S都是集合 A到 B的两个关系，则：
R∪S ＝ {<x,y>|(xRy)∨(xSy)}
R∩S ＝ {<x,y>|(xRy)∧(xSy)}
R-S＝ {<x,y>|(xRy)∧(xS y)}
={<x,y>|(x y)}
根据定义，由于 A× B是相对于 R的全集，所以
＝ A× B-R,且 ∪ R＝ A× B,∩R ＝ Φ。
R?
关系及其表示
R R R
R
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {a,b,c},B＝ {1,2}，
R＝ {<a,1>,<b,2>,<c,1>}，
S＝ {<a,1>,<b,1>,<c,1>}，
则,R∪S ＝ {<a,1>,<b,2>,<c,1>,<b,1>}；
R∩S ＝ {<a,1>,<c,1>}；
R-S＝ {<b,2>}；
＝ {<a,2>,<b,1>,<c,2>}＝ A× B-R。R
关系及其表示
Guoyongfang.2006@yahoo.com.cn
关系及其表示三、关系的表示法
1.集合表示法
2.关系矩阵
3.关系图法
Guoyongfang.2006@yahoo.com.cn
关系及其表示
1.集合表示法例 1)、设 A＝ {2},B＝ {3},关系 R＝ {<2,3>}
2)、如定义集合 N上的“小于等于”关系：
R＝ {<x,y>|(x,y?N)∧(x≤y) }。
Guoyongfang.2006@yahoo.com.cn
2.关系矩阵设 A＝ <a1,a2,a3,...,an>,B＝ <b1,b2,b3,...,bm>，
R是从 A到 B的一个二元关系，则对应于关系 R之关系矩阵 MR＝（ rij)n× m。其中,称 MR为 R的 邻接矩阵 。
)m,.,,,3,2,1j,n,.,,,3,2,1i(Rb,a0 Rb,a 1r
ji
ji
ij
关系及其表示
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {2,3,4｝,B＝ {1,2,4｝,
考虑从 A到 B的,大于等于,关系 R和,小于等于,关系 S：
R＝ {<2,1>,<2,2>,<3,1>,<3,2>,<4,1>,<4,2>,<4,4>}，
S＝ {<2,2>,<2,4>,<3,4>,<4,4>｝。
写出 R,S的关系矩阵。
解,
111
011
011
M R
100
100
110
M S
关系及其表示
Guoyongfang.2006@yahoo.com.cn
三,关系图法如 R是定义在 A＝ <a1,a2,a3,...,an>上的关系，则对应于关系 R有如下规定：
①,设 a1,a2,...,an为图中节点，用,。,表 示
②,如 <ai,aj>?R,则从 ai到 aj可用一有向边 ai。 。 aj相连。
<ai,aj>为对应图中的有向边。
③,如 <ai,ai>?R,则从 ai到 ai用一带箭头的小圆环表示。
关系及其表示
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ <P1,P2,P3,…,P6>是六个程序，考虑它之间的一种调用关系 R，如 Pi可调用 Pj,则有 <Pi,Pj>R,现假设
R＝ {<P1,P2>,<P2,P6>,<P5,P2>,
<P4,P4>,<P3,P1><P3,P4><P4,P5>}
则此关系 R的关系图如下：
关系及其表示
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {a1,a2,a3,?,a 6｝是六个人,B＝ {1,2,3｝
是三套房间，考虑 A到 B之间的一种住宿关系 R，如 ai住房间 j,则有 <ai,j>?R,现假设,R＝ {<a1,1>,<a2,3>,<a3,1>,
<a4,2>,<a5,3>,<a6,2>}则此关系 R的关系图如下：
关系及其表示
Guoyongfang.2006@yahoo.com.cn
3－ 6关系性质一、关系的一些重要性质定义 R是集合 X上的二元关系，
对任意的 x∈ X,都满足 <x,x>∈ R,则称 R是 自反 的关系 。
对任意的 x∈ X,都满足 <x,x>?R,则称 R是 反自反 的关系 。
对任意的 x,y∈ X,满足 <x,y>∈ R?<y,x>∈ R,则称 R是 对称 的关系 。
对任意的 x,y∈ X,满足 <x,y>∈ R∧<y,x> ∈ R?x＝ y,则称 R是 反对称 的关系 。
对任意的 x,y,z∈ X,满 <x,y>∈ R∧<y,z> ∈ R?<x,z>∈ R,
则称 R是 传递 的关系 。
Guoyongfang.2006@yahoo.com.cn
例,在整数集 I上定义的,小于等于,关系是自反的、反对称的、传递的关系；,小于,关系是反自反的、反对称的、
传递的关系；,等于,关系是自反的、反对称的、对称的、
传递的关系。
幂集上的,包含,关系关系是自反的、反对称的、传递的关系；
,真包含,关系是反自反的、反对称的、传递的关系；
,相等,关系是自反的、反对称的、对称的、传递的关系。
请注意：
任何不是自反的关系未必一定是反自反的关系，反之亦然。
任何不是对称的关系也未必一定是反对称的关系，反之亦然。
关系性质
Guoyongfang.2006@yahoo.com.cn
例 设 A＝ {1,2,3,4},R＝
{<1,1>,<1,2>,<2,1>,<3,4>}是 A上的关系 。 则 R即不是自反的，又非反自反的；即不是对称的，也非反对称的；而且也不是传递的。即不具备关系的任何性质。
关系性质
Guoyongfang.2006@yahoo.com.cn
关系性质例 设 A是任意的集合,A上的完全关系 A× A是自反的、对称的、传递的关系； A上的空关系 Φ是反自反的、反对称的、对称的、传递的关系； A上的恒等关系 IA是自反的、对称的、反对称的、传递的关系。
例 1)朋友关系是自反的、对称的、而非传递的关系；
2)父子关系是反自反的、反对称的、而非传递的关系,
Guoyongfang.2006@yahoo.com.cn
二、用关系图来描述关系的这几种重要的性质在关系图中,每个节点都有环,则此关系是自反关系,
在关系图中,每个节点都无环,则此关系是反自反关系。
在关系图中,任何一对节点 (可以相同 )之间,要么有方向相反的两条边,要么无任何边,则此关系是对称关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
用关系图来描述关系的这几种重要的性质 (续 )
在关系图中,任何一对节点 (可以相同 )之间,至多有一条边存在,则此关系是反对称关系。
在关系图中,任何三个节点 x,y,z(可以相同 )之间，若从 x到 y有一条边存在,从 y到 z有一条边存在,则从 x
到 z一定有一条边存在,则此关系是传递关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
三、用关系矩阵来描述关系的这几种重要的性质在关系矩阵中,对角线上全为 1,则此关系是自反关系。
在关系矩阵中,对角线上全为 0,则此关系是反自反关系。
若 R之关系矩阵为对称矩阵,则此关系是对称关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
用关系矩阵来描述关系的这几种重要的性质 (续 )
若 R之关系矩阵为反对称矩阵 (关于元素 1的反对称 ),则此关系是反对称关系。
在关系矩阵中,对任意 i,j,k ∈ {1,2,3,…,
n},满足 如 rij＝ 1∧r jk＝ 1则 rik＝ 1,则此关系是传递关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {1,2,3},定义在 A上的关系如下图：
关系性质
Guoyongfang.2006@yahoo.com.cn
解,从关系图易判断上述关系之性质如下：
图 (a)的关系是自反的、对称的、反对称的、传递的关系；
图 (b)的关系是具备反自反的、对称的、反对称的、传递的关系；
图 (c)的关系是具备对称的、反对称的、传递的关系；
图 (d)的关系是不具备任何的性质关系；
关系性质
Guoyongfang.2006@yahoo.com.cn
解 （ 续）,
图 (e)的关系是具备自反的、对称的、传递的关系；
图 (f)的关系是具备反自反的、反对称的、传递的关系；
图 (g)的关系是具备反自反的、反对称的关系；
图 (h)的关系是具备反自反的、斜对称的、反对称的、传递的关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
例,设 R＝ {<a,a>,<b,b>}是定义在 A＝ {a,b}上的二元关系,S＝ {<a,a>,<b,b>}是定义在 B＝ {a,b,c}上的二元关系,试判断 R,S具备何种性质。
解,1.由于 R＝ {<a,a>,<b,b>}是定义在 A＝ {a,b}上的关系，所以，对任意的 x∈A,都满足 <x,x>∈R,则 R是自反的关系；另外,R也是对称的、反对称的和传递的,
2,S＝ {<a,a>,<b,b>}虽然与 R完全相等 (从集合的观点 )，但它却是定义在 B＝ {a,b,c}上的二元关系。由于 c∈B,但 <c,c>?S,所以,S不是 B上的自反关系；另外,S也是对称的、反对称的和传递的。
关系性质
Guoyongfang.2006@yahoo.com.cn
关系性质关系性质的逻辑表示,设 R是集合 A上的二元关系，
1) R是自反的?
))Rx,x()Ax)((x( 是永真的
2) R不 是自反的? ))Rx,x()Ax)((x( 是永真的
3) R是 反 自反的? ))Rx,x()Ax)((x( 是永真的
4) R不 是 反 自反的? ))Rx,x()Ax)((x( 是永真的
5) R是 对称 的? ))Rx,y()Ry,x)((y)(x( 是永真的
6) R不 是 对称 的? ))Rx,y()Ry,x)((y)(x( 是永真的
Guoyongfang.2006@yahoo.com.cn
关系性质
9) R是 传递 的?
))Rz,x())Rz,y()Ry,x)(((z)(y)(x( 是永真的
10)R不 是 传递 的?
))Rz,x()Rz,y()Ry,x)((z)(y)(x(
是永真的
7) R是 反 对称 的?
))Rx,y())Ry,x()yx)(((y)(x(
))yx())Rx,y()Ry,x)(((y)(x(
是永真的
8) R不 是 反 对称 的?
))Rx,y()Ry,x()yx)((y)(x( 是永真的关系性质的逻辑表示 (续 )
Guoyongfang.2006@yahoo.com.cn
2,反自反关系性质
1,自反任取 x?A,中间过程任取 x?A,中间过程
<x,x>?R。
<x,x>?R。
关系性质的证明方法：
Guoyongfang.2006@yahoo.com.cn
关系性质
3,对称任取 x,y?A，
假设 <x,y>?R，
中间过程 <y,x>?R。
4,传递任取 x,y,z?A，假设
<x,y>?R,<y,z>?R,中间过程 <x,z>?R。
关系性质的证明方法 (续 )：
Guoyongfang.2006@yahoo.com.cn
关系性质
5,反对称任取 x,y?A，假设
<x,y>?R,<y,x>?R,中间过程 x＝ y。
或者任取 x,y?A,x≠y，
假设 <x,y>?R,中间过程 <y,x>?R。
关系性质的证明方法 (续 )：
Guoyongfang.2006@yahoo.com.cn
作业
P113 3-6习题
（ 2）（ 4）（ 6）
Guoyongfang.2006@yahoo.com.cn
3－ 7复合 关系和逆关系一,复合 关系定义 设 R是一个从集合 A到集合 B的二元关系,S是从集合 B到集合 C的二元关系 (也可简单的描述为 R,A→B,S：
B→C),则 R与 S的 复合关系 R?S是从 A到 C的关系,并 且：
R?S＝ {<x,z>|(x∈A)∧(z∈C)∧
(?y)((y∈B)∧(xRy)∧(ySz))}
运算,?” 称为 复合运算 。
Guoyongfang.2006@yahoo.com.cn
例：设 R＝ {<1,2>,<3,4>,<2,2>}
S＝ {<4,2>,<2,3>,<3,1>}，
分别是定义为从 A→B 和从 B→C 的关系，其中 A＝ B＝ C＝ {1,2,3,4}。
1).用集合方法求 R?S,S?R,R?R,S?S。 则：
R?S＝ {<1,3>,<3,2>,<2,3>}；
S?R＝ {<4,2>,<2,4>,<3,2>}；
R?R＝ {<1,2>,<2,2>}；
S?S＝ {<4,3>,<2,1>}。
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
复合 关系和逆关系
2).用关系矩阵求 R?S。
0000
0010
0100
0100
0010
0001
0100
0000
0000
1000
0010
0010
MMM SRSR?
其中，
MR?S＝ (r'ij)|A|× |C|，
|C|,.,,2,1j
|A|,.,,,2,1i)rr('r
kjik
|B|
1k
ij?
Guoyongfang.2006@yahoo.com.cn
设 I是整数集合,R,S是 I到 I的两个关系：
R＝ {<x,3x>|x∈ I}； S＝ {<x,5x>|x∈ I}。
则,R?S＝ {<x,15x>|x∈ I}
S?R＝ {<x,15x>|x∈ I}
R?R＝ {<x,9x>|x∈ I}
S?S＝ {<x,25x>|x∈ I}
(R?R)?R＝ {<x,27x>|x∈ I}
(R?S)?R＝ {<x,45x>|x∈ I}
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
定义 设 R是集合 A上的二元关系，则可定义 Rn,
该 Rn也是 A上的二元关系，定义如下：
1.R0＝ IA＝ {<a,a>|a∈ A}；
2.R1＝ Ｒ；
3.Rn+1＝ Rn?R＝ R?Rn。
显然,Rm?Rn＝ Rm+n,(Rm)n＝ Rmn。
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
二、逆关系定义 设 R是一个从集合 A到集合 B的二元关系，则从 B到 A的关系 Rc＝
{<b,a>|<a,b>R}称为 R的 逆关系,运算
,c”称为 逆运算 。
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {a,b,c),B＝ {1,2,3},R是从 A到 B的一个关系,R＝ {<a,1>,<c,2>,<b,3>}，
则,Rc＝ {<1,a>,<2,c>,<3,b>}。
关系图和关系矩阵如下：
010
100
001
M
,
010
100
001
M
1
R
R
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
三、几种运算之间的若干重要性质定理 设 R,S,T分别是从集合 A到集合 B，
集合 B到集合 C，集合 C到集合 D的二元关系，则：
1)(R?S)?T＝ R?(S?T)
2)(R?S)c＝ Sc?Rc
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
复合 关系和逆关系证明,1)设 <a,d>∈ (R?S)?T,则由复合运算知,至少存在
c∈C,使得,<a,c>∈R?S,<c,d>∈ T。
又 对于 <a,c>∈ R?S,则至少 存一个 b∈B,使得：
<a,b>∈ R,<b,c>∈ S。
因此,由 <b,c>∈ S,<c,d>∈ T,有 <b,d>∈ S?T，
又由 <a,b>∈ R和 <b,d>∈ S?T,知,<a,d>∈ R?(S?T),
所以 (R?S)?T?R?(S?T)。
同理可证,R?(S?T)?(R?S)?T。
由集合性质知,(R?S)?T＝ R?(S?T)。
Guoyongfang.2006@yahoo.com.cn
2).任取 <c,a>∈ (R?S)c，则 <a,c>∈ R?S,由,?” 的定义知：则至少存一个 b∈B,使得,<a,b>∈ R，
<b,c>∈ S，
即,<b,a>∈ Rc,<c,b>∈ Sc。由 <c,b>∈ Sc和 <b,a>∈ Rc,
有,<c,a>∈ Sc?Rc，所以,(R?S)c?Sc?Rc。
反之,任取 <c,a>∈ Sc?Rc，由,?” 的定义知：则至少存一个 b∈B,使得,<c,b>∈ Sc和 <b,a>∈ Rc，所以：
<a,b>∈ R,<b,c>∈ S。 由,?” 知,<a,c>∈ R?S。即有,<c,a>∈ (R?S)c。所以,Sc?Rc?(R?S)c。
由集合的定义知,(R?S)c＝ Sc?Rc。■
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
定理 设 R,S是从集合 A到集合 B的二元关系，
则有：
(Rc)c＝ R；
(R∪S) c＝ Rc∪S c；
(R∩S) c＝ Rc∩S c；
(R-S)c＝ Rc-Sc；
(R)c＝ Rc；
(A× B)c＝ (B× A)；
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
定理：设 R为 X上的二元关系，则
R是对称的，当且仅当 R=Rc
R是反对称的，当且仅当 R ∩R c? Ix
Guoyongfang.2006@yahoo.com.cn
定义 设 R是 X上的二元关系,如果另一个关系 R’是满足：
1,R’是自反的 （ 对称的,传递的 ） ；
2,R? R’；
3.对于 A上的任意自反的 （ 对称的,传递的 ） 关系 R”,若
R?R”,则 R’?R”。
则称 R’为 R的 自反 （ 对称,传递 ） 闭包 。
换句话说,R的自反闭包（对称闭包、传递闭包）是包含 R的最小的自反的（对称的、传递的）关系。通常分别用 r(R),s(R)和 t(R)表示 R的自反闭包、对称闭包和传递闭包。
3-8关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
【 定理 】 设 R 是 X 上的二元关系,则：
1,R是自反的当且仅当 r(R) = R；
2,R是对称的当且仅当 s(R) = R；
3,R是传递的当且仅当 t(R) = R；
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
定理 设 R是集合 A上的二元关系，则：
1,r(R)＝ R∪I A。
2,s(R)＝ R∪R -1。
3,t(R)＝ t(R) = R? R2? R3?,..。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
证,1,首先 R? IA是自反的，且 R? R? IA，
若又有自反关系 R’满足 R? R’，则因为 R’
是自反的有 IA? R’，即有 R? R’? IA? R’，
从而有 R? IA? R’，命题得证。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
证,2.首先 R? R-1是对称的，因为 (R? R-1)-1 = R? R-1。
若又有对称关系 R? R’，则对任意的 <x,y>? A? A，
有,<x,y>? R? R-1? (<x,y>? R)? (<x,y>? R-1)?
(<x,y>? R’)? (<y,x>? R)? (<x,y>? R’)? (<y,x>?
R’)? (<x,y>? R’)? (<y,x>? R’-1) // R’ = R’-1
(<x,y>? R’)? (<x,y>? R’)? <x,y>? R’
即 R? R-1? R’，命题得证。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
证,3.记 R+ = R? R2? R3?,..，首先证 t(R)? R+，这只要证 R+是传递的，因为若 R+是传递的，而又有 R? R+，
那么根据传递闭包的定义有 t(R)? R+。为了证 R+是传递的，我们考察对任意的 x,y,z?A，若 <x,y>?R+且 <y,
z>?R+，则必存在自然数 n,m使得 <x,y>?Rn且 <y,
z>?Rm，那么有 <x,z>?Rn? Rm = Rn+m，从而 <x,y>?R+，
因此 R+确实是传递的。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
证,3,再证 R+? t(R)，这只要证对任意的自然数 n?1有 Rn? t(R)，
为此我们使用数学归纳法：
i),归纳基,当 n = 1时,根据传递闭包的定义有 R?t(R)；
ii).归纳步，设当 n = k时，有 Rk? t(R)，考察 n = k+1，因为有 Rk+1 = Rk? R，所以对任意的 x,y?A，若 < x,y>?R k+1，则必存在 z?A使得 <x,z>?Rk且 <z,y>?R，因此有 <x,z>?t(R)且
<z,y>?t(R)，而 t(R)是传递的，因此有 <x,y>?t(R)，即对任意的自然数 n?1有 Rn? t(R)，因此 R+? t(R)，而上面已经证明了 t(R)? R+，所以有 R+ = t(R)，从而命题得证。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
例,设 P＝ {P1,P2,P3,P4}是四个程序,R,S是定义在 P上的调用关系如下：
R＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>}
S＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>}
求 r(R),s(R),t(R),r(S),s(S),t(S)。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
关系的闭包运算解,r(R)＝ R∪I A
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>}∪
{<P1,P1>,<P2,P2>,<P3,P3>,<P4,P4>}
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>,<P1,P1>,
<P2,P2>,<P3,P3>,<P4,P4>}。
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>,<P1,P4>}。
s(R)＝ R∪R -1＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>}∪
{<P2,P1>,<P3,P1>,<P4,P2>,<P4,P3>}
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>,<P2,P1>,
<P3,P1>,<P4,P2>,<P4,P3>}。
Guoyongfang.2006@yahoo.com.cn
关系的闭包运算
t(R)＝ R∪R 2∪R 3∪R 4＝ {<P1,P2>,<P1,P3>,<P2,P4>,
<P3,P4>}∪{<P 1,P4>}∪ Φ∪ Φ
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>,<P1,P4>}。
r(S)＝ S∪I A＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>}∪
{<P1,P1>,<P2,P2>,<P3,P3>,<P4,P4>}
＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>,<P1,P1>,
<P2,P2>,<P3,P3>,<P4,P4>}。
Guoyongfang.2006@yahoo.com.cn
s(S)＝ S∪S -1＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>}
∪{<P 2,P1>,<P1,P2>,<P3,P2>,<P4,P3>}
＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>,<P3,P2>,<P4,P3>}
关系的闭包运算
t(S)＝ S∪S 2∪S 3∪S 4
＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>}
∪{<P 1,P1>,<P2,P2>,<P1,P3>,<P2,P4>}
∪{<P 1,P2>,<P2,P1>,<P1,P4>,<P2,P3>}
∪{<P 1,P1>,<P2,P2>,<P1,P3>,<P2,P4>)
＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>,<P1,P1>,
<P2,P2>,<P1,P3>,<P1,P4>,<P2,P4>}。
Guoyongfang.2006@yahoo.com.cn
证明：
对?（ ｘ,ｙ ） ∈ t(Ｒ ),?ｋ,使 （ ｘ,ｙ ） ∈
Ｒ k,表明在Ａ中存在不同元素ａ 1,ａ 2,…,ａ k-1，
使 （ ｘ,ａ 1）,（ ａ 1,ａ 2）,（ ａ 2,ａ 3）,…，
（ ａ k-1,ｙ ） ∈ Ｒ 。 若ｋ＞ｎ,则ａ 1,ａ 2,…，
ａ k-1,ｙ中至少有两个相同,不妨设ａ i＝ｙ,
（ ｉ ≤ ｋ－１ ） 。
定理,设｜Ａ｜＝ｎ,Ｒ是Ａ上二元关系,则存在正整数ｋ,ｋ ≤ ｎ,使 t(Ｒ )＝Ｒ ∪ Ｒ 2∪ …∪ Ｒ k。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
于是（ｘ，ａ 1）,…（ａ i，ａ i-1 ） ∈ Ｒ,
（ａ i-1,ｙ） ∈ Ｒ，故（ｘ，ｙ） ∈ Ｒ i，
即 若ｋ＞ｎ，必存在比ｋ小的正整数ｉ，
使（ｘ，ｙ） ∈ Ｒ i。
注：定理说明,可用Ｒ ∪ Ｒ 2∪ …∪ Ｒ n来求 t(Ｒ ) 。
例６,设Ａ＝ ｛ １,２,３ ｝,
Ｒ＝ ｛（ １,１ ）,（ １,２ ）,(２,３ ）｝
求 t(Ｒ )。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
解,Ｒ＝
000
100
011
,Ｒ
2
＝
000
000
111
＝Ｒ
3
故
R
＝Ｒ∪Ｒ
2
∪Ｒ
3
＝
000
100
111
R
＝ ｛ （１，１）,（１，２）,（１，３）,（２，３）｝
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
Ｗａｒｓｈａｌｌ算法：（１９６２）
设Ｒ是ｎ个元素集合上的二元关系
(1)
(2)ｉ ← １；
(3)ｆｏｒ ｊ＝１ ｔｏ ｎ
iｆ ａ j,i＝１ ｔｈｅｎ
ｆｏｒ ｋ＝１ ｔｏ ｎ ｄｏ
ａ j,k← ａ j,k∨ ａ i,k
(4)ｉ =ｉ＋１；
(5) iｆ ｉ ≤ｎ,ｔｈｅｎ go (3)
ｅｌｓｅ ｓｔｏｐ
注：当｜Ａ｜＝ｎ较大时,用上述定理计算 t(Ｒ )工作量非常大 。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
注,（ 1） 结果 (aij)nxn是 t(Ｒ )的相关矩阵 。
（ 2） 算法的复杂度为ｎ 3。
例７：Ａ＝ ｛ ａ,ｂ,ｃ,ｄ ｝
Ｒ＝ ｛（ ａ,ｂ ）,（ ｂ,ｃ ）,
（ ｃ,ｄ ） ｝
计算 t(Ｒ ) 。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
0000
1000
0100
0010
R
(1)i=1 由于 aj1=0(j=1,2,3,4) 不改动
(2)i=2 j=1,aji=1? a13=1
(3)i=3
0000
1000
0100
011
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
j=1,a13=1? a14=1
j=2,a23=1? a24=1
即 Ｒ *＝｛（ａ，ｂ），（ａ，ｃ），
（ａ，ｄ），（ｂ，ｃ），
（ｂ，ｄ），（ｃ，ｄ）｝
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
定理 R是集合 A上的关系，则：
1)rs(R)＝ sr(R)
2)rt(R)＝ tr(R)
3)st(R)?ts(R)
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖
定义 若把一个集合 A分成若干个叫做分块的非空子集，
使得 A中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做 A的一个覆盖。如果 A中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做 A的一个划分（或分化）。
Guoyongfang.2006@yahoo.com.cn
定义 A是一个集合,A1,A2,A3...Am是 A的任何 m个子集,如果 A1,A2,A3...Am满足：
1) 则 称集合 П (A)＝ {A1,A2,A3,....,Am｝ 为集合 A的一个 覆盖 。
2)对一切的 i≠j(i,j ＝ 1,2,3,....,m),都有 Ai∩A j＝ Φ。
则称集合 П (A)＝ {A1,A2,A3,....,Am｝ 为集合 A的一个 划分,而 A1,A2,A3,...Am叫做这个划分的 块 。
3－ 9集合的划分与覆盖
AA im
1i
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖
例如,A={a,b,c},考虑下列子集：
S={{a,b},{b,c}},Q={{a},{a,b},{a,c}}
D={{a},{b,c}},G={{a,b,c}}
E={{a},{b},{c}},F={{a},{a,c}}
则 S,Q是 A的覆盖,D,G,E是 A的划分,F既不是划分也不是覆盖。显然，若是划分则必是覆盖，其逆不真。
最大划分最小划分
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖
定义 若 {A1,A2,···,Ar}与 {B1,B2,···,Bs}是同一集合 A的两种划分，则其中所有 Ai∩ Bj≠∮ 组成的集合,称为是原来两种划分的交叉划分。
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖定理 设 {A1,A2,···,Ar}与 {B1,B2,···,Bs}是同一集合 X的两种划分,则其交叉划分亦是原集合的一种划分 。
证明：因为题设的交叉划分是：
{A1∩ B1,A1∩ B2,···,A1∩ Bs，
A2∩ B1,A2∩ B2,···,A2∩ Bs,···,
Ar∩ B1,Ar∩ B2,···Ar∩ Bs},
在交叉划分中,取任两元素,Ai∩ Bh,Aj∩ Bk,考虑 （ Ai∩ Bh） ∩ (Aj∩ Bk)，
Ⅰ,若 i≠j 且 h=k,因为 Ai∩ Aj = Φ故
Ai∩ Bh∩ Aj∩ Bk= Φ ∩ Bh∩ Bk= Φ
Ⅱ,若 i≠j 且 h≠k,因为 Ai∩ Aj = Φ,Bh∩ Bk= Φ故
Ai∩ Bh∩ Aj∩ Bk= Φ ∩ Φ = Φ
Ⅲ,若 I=j且 h≠k,情况与 Ⅰ 相同 。
综上所述,在交叉划分中,任取两元素,其交为
Ai∩ Bh∩ Aj∩ Bk= Φ
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖其次交叉划分中所有元素得并为：
(A1∩ B1)?(A1∩ B2)? ···?(A1∩ Bs)?
(A2∩ B1)?(A2∩ B2 )? ···?(A2∩ Bs)? ···?
(Ar∩ B1)?(Ar∩ B2 )? ···?(Ar∩ Bs)=X ∩ X= Φ
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖
定义 给定 X的任意两个划分 {A1,A2,···,Ar}与 {B1,B2,···,Bs}，若对于每一个 Aj均有 Bk，使 AjBk，则 {A1,A2,···,Ar}称为是
{B1,B2,···,Bs}的加细。
定理 任何两种划分的交叉划分，都是原来个划分的一种加细。
证明：设 {A1,A2,···,Ar}与 {B1,B2,···,Bs}的交叉划分为 T,对 T中任意元素 Ai∩ Bj 必有 Ai∩ Bj ∈ Ai和 Ai∩ Bj ∈ Bj,故 T必是原划分的加细。
Guoyongfang.2006@yahoo.com.cn
3-10等价关系与等价类一、等价关系定义 R是定义在集合 A上的关系，如果 R是 自反的、对称的、传递的,则称此关系 R为 A上的 等价关系 。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类例,1,在全体中国人所组成的集合上定义的,同姓,关系,就是具备自反的,对称的,传递的性质,因此,
就是一个等价关系；
2,对任何集合 A,考虑 R＝ A× A,则 R是 A上的等价关系；
3,三角形的,相似关系,,,全等关系,等是等价关系；
4.,朋友,关系,则不是等价关系,因它是不传递的 。
5,幂集上定义的,?”,整数集上定义的,≤,都不是
,因为它们是不对称的 。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类证明,1、对任意 x∈A,有 (x-x)被 12所整除，所以 <x,x>∈R,
即 R是自反的。
2、对任意 x,y∈A,若 <x,y>∈R,有 (x-y)被 12所整除，所以
(y-x)＝ -(x-y)被 12所整除,所以,<y,x>∈R,即 R是对称的。
3、对任意 x,y,z∈A,若 <x,y>∈R 且 <y,z>∈R,有 (x-y)被 12所整除且 (y-z)被 12所整除,所以 (x-z)＝ (x-y)＋ (y-z)被 12
所整除,所以,<x,z>∈R,即 R是传递的,
由 1,2,3知 R是等价关系。■
例,在时钟集合 A＝ {1,2,3,…,24}上定义关系
R＝ {<x,y>|(x,y?A)∧((x -y)被 12所整除 )｝。
证明 R是一个等价关系。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类此等价关系的关系图：
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类例,考虑整数集合 I上的关系如下：
R＝ {<x,y>|{x,y∈I)∧((x -y)被 m所整除 )∧(m∈N ＋ )}，
此 R称为 I上的 以 m为模的同余关系 。一般记 xRy为：
x?y(mod m) (同余式 )。
可以证明,R也是 I上的 等价关系,此时 R将 I分成了如下的一些子集：
{…,-3m,-2m,-m,0,m,2m,3m,… }；
{…,-3m＋ 1,-2m＋ 1,-m＋ 1,1,m＋ 1,2m＋ 1,3m＋ 1,… }；
{…,-3m＋ 2,-2m＋ 2,-m＋ 2,2,m＋ 2,2m＋ 2,3m＋ 2,… }；
……
{…,-2m-1,-m-1,-1,m-1,2m-1,3m-1,4m-1,… }；
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类二、等价类
R是集合 A上的等价关系,对任意 x∈A,称集合 [x]R：
[x]R＝ {y|(y∈A)∧(<x,y>∈R)}
叫做 x关于 R的 等价类,或叫作由 x生成的一个 R等价类。其中 x称为 [x]R的 生成元 (或叫 代表元,
或 典型元 )。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类例,设 A＝ {0,1,2,3,5,6,8}，考虑 R是 A上的以 3为模的同余关系，
求其等价类。对于前边例子中的时钟集合，求其等价类。
解,1,R是一个等价关系,为此可求 [x]R(x∈A) 。
[0]R＝ {0,3,6}＝ [3]R＝ [6]R；
[1]R＝ {1}；
[2]R＝ {2,5,8}＝ [5]R＝ [8]R。
2,[1]R＝ {1,13}＝ [13]R；
[2]R＝ {2,14}＝ [14]R；
…
[12]R＝ {12,24}＝ [24]R。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类定理 设给定集合 A上的等价关系 R,对于 a,b∈A 有 aRb iff
[a]R=[b]R.
证明：假定 [a]R=[b]R,因为 a∈[a] R,a∈[b] R,即 aRb.
反之,若 aRb,设
c∈[a] R=>aRc=>cRa=>cRb=>c∈[b] R
即 [a]R∈[b] R
同理,若 c∈[b] R=>bRc=>aRc=>c∈[a] R,故 [b]R[a]R,
由此证得若 aRb,则 [a]R∈ [b]R 。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类定义 R是集合 A上的等价关系，由 R确定的一切等价类的集合，称为集合 A上的关于 R的 商集,记为 A/R，
A/R＝ {[x]R|(x∈A)} 。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类三、等价与划分的关系定理 R是集合 A上的等价关系，则此关系 R可唯一的确定 A上的一个划分 П R(A),П R(A)＝ {[x]R|(x∈A)},
此划分正好是集合 A上关于 R的商集 A/R。
证明：Ｒ是等价关系,?ａ ∈ Ａ，由Ｒ的自反性，（ａ，
ａ） ∈ Ｒ，即ａ与ａ属于同一等价类，也即?ｉ，ａ ∈
Ａ i 若ｉ ≠ｊ，Ａ i≠Ａ j，而Ａ i∩Ａ j ≠?，则?ｃ ∈ Ａ i∩Ａ j，
ｃ ∈ Ａ i，且ｃ ∈ Ａ j,
Guoyongfang.2006@yahoo.com.cn
续：
对?ａ ∈ Ａ i,ａ～ｃ
对?ｂ ∈ Ａ j,ｂ～ｃ,即ｃ～ｂ (对称性 )
由Ｒ传递性,ａ～ｂ
由ａ,ｂ的任意性,故Ａ i＝Ａ j 与Ａ i和Ａ j 为不同的等价类矛盾 。
故Ａ i∩Ａ j =? 所以,Ｒ完成了等价类的划分 。
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
定理 集合 A的任何一个划分 П (A)可唯一地确定 A上的一个等价关系 RП,RП ＝ {<x,y>|(x,y∈A)∧(x,y 同属 П (A)的一个划分块 )｝即若设 П (A)＝
{A1,A2,A3,....,Am}，则,RП ＝
A1× A1)∪(A 2× A2)∪(A 3× A3)∪...∪(A m× Am)。
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
证,若Ａ已进行了划分,则构造二元关系Ｒ 。
(1)?ａ ∈ Ａ,使 （ ａ,ａ ） ∈ Ｒ,
(2)分别对每一等价类内所有两个不同元素ａ,ｂ,
（ ａ,ｂ ） ∈ Ｒ,使 （ ｂ,ａ ） ∈ Ｒ,
显然,Ｒ是自反的,对称的,而且也是传递的,
因为若 （ ａ,ｂ ） ∈ Ｒ,（ ｂ,ｃ ） ∈ Ｒ,则ａ,
ｂ,ｃ均在同一等价类内,
故 （ ａ,ｃ ） ∈ Ｒ 。
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类解,R1＝ {1,2,3}× {1,2,3}∪{4,5} × {4,5}∪{6} × {6}
＝ {<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,
<2,3>,<3,2>,<4,4>,<5,5>,<4,5>,<5,4>,<6,6>}；
R2＝ {1,2,3}× {1,2,3}∪{4,5,6} × {4,5,6}
＝ {<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,
<3,1>,<2,3>,<3,2>,<4,4>,<5,5>,<6,6>,
<4,5>,<5,4>,<4,6>,<6,4>,<5,6>,<6,5>}。
例,设集合 A＝ 1,2,3,4,5,6}的两个划分如下：
П 1(A)＝ {{1,2,3},{4,5},{6}}； П 2(A)＝ {{1,2,3},{4,5,6}}.
求其相应的等价关系。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类证明,,?” 若 R是等价关系。
1)、显然 R是自反的。
2)、对任意 a,b,c∈A,若 <a,b>∈R,<a,c>∈R,则由 R是对称的，有 <b,a>∈R 并且 <a,c>∈R,由 R是传递的，所以,<b,c>∈R 。即 R是循环的关系。
1),2)知 R是自反的和循环的。
例,设 R是集合 A上的一个关系，对?a,b,c∈A,若 <a,b>
∈R 并且 <a,c>∈R,则有,<b,c>∈R,则 R称为 A上的循环关系。试证明 R是 A上的一个等价关系的充要条件是 R是循环关系和自反关系。
Guoyongfang.2006@yahoo.com.cn
“?” 若 R是自反的和循环的。
1),显然 R是 自反性 的；
2)、对任意 a,b∈ A,若 <a,b>∈ R,则由 R是自反的,有 <a,a>∈ R，
因 R是循环的，所以,<a,b>∈ R且 <a,a>∈ R? <b,a>∈ R，
即 R是对称的。
3)、对任意 a,b,c∈ A，若 <a,b>∈ R,<b,c>∈ R，则由 R对称的，有 <b,a>∈R 并且 <b,c>∈R ；由 R是循环的，所以
<b,a>∈R 且 <b,c>∈R?<a,c>∈R,即 R是传递的。
由 1),2),3)知 R是 A上的一个等价关系。■
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
定理 设 R1和 R2为非空集合 A上的等价关系，则
R1=R2当且仅当 A/ R1=A/ R2。
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系一、相容关系定义 R是定义在集合 A上的关系，如果 R是 自反的、对称的,则称此关系 R为 A上的 相容关系 。
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系例如,设 A是由下列英文单词组成的集合 。
A={cat,teacher,cold,desk,knife,by}
定义关系：
r={<x,y>|x,y∈ A且 x和 y由相同的字母 }。 显然,r是一个相容关系 。
令 x1=cat,x2=teacher,x3=cold,x4=desk,x5=knife,x6=by.
R的关系图可由图表示 。
R的关系矩阵为由于相容关系是自反和对称的，因此其关系矩阵的对角线元素都是 1，且矩阵是对称的。
100000
011010
011110
001111
011111
000111
Mr
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系定义 设 r是集合 A上的相容关系,如 C∈ A,如果对于 C中任意两个元素 a1和 a2有 a1ra2,称 C是由相容关系 r产生的相容类 。
定义 设 r是集合 A上的相容关系,不能真包含在任何其他相容类中的相容类,称做最大相容类 。 记作 Cr。
在相容关系图中,最大完全多边形的顶点集合,就是最大相容类 。 所谓完全多边形,就是其每个顶点都与其他顶点连接的多边形 。 例如一个三角形是完全多边形,一个四边形加上两条对角线就是完全多边形 。
此外,在相容关系图中,一个孤立结点,以及不是完全多边形的两个结点的连线,也是最大相容类 。
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系例 设给定相容关系图如图 3-11,3,写出最大相容类 。
解：最大相容类为：
{a1,a2,a4,a6},{a3,a4,a6},{a4,a5},{a7}
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系定理 r是有限集 A上的相容关系,C是一个相容类,那么必存在一个最大相容类 Cr,使 CCr。
证明：设 A={a1,a2,···,an},构成相容类序列
,其中 C0=C,且 Ci+1=Ci∪ {aj},其中 j是满足 aj不属于 Ci而 aj与 Ci
中各元素都有相容关系的最小足标 。
由于 A的元素个数 |A|=n,所以至多经过 n-|C|步,就使这个过程终止,而此序列的最后一个相容类,就是所要找到的最大相容类 。
210 CCC
Guoyongfang.2006@yahoo.com.cn
3－ 11相容容关系定义 在集合 A上给定相容关系 r,其中最大相容类的集合称作集合 A的完全覆盖,记作 Cr(A)。
定理 给定集合 A的覆盖 {A1,A2,···,An},由他确定的关系 R= A1
× A1 ∪ A2 × A2 ∪ ···∪ An× An 是相容关系 。
证明,因为 A=,对于任意 x∈ A,必存在某个 j>0使得 x∈ Aj,所以 <x,x>∈ Aj× Aj,即 <x,x>∈ R,因此 R是自反的 。
其次,若有任意 x,y∈ A且 <x,y>∈ R,则必存在某个 h>0使 <x,
y>∈ Ah× Ah,故必有 <y,x>∈ Ah× Ah,即 <y,x>∈ R,所以 R是对称的 。
因此证得 R是 A上的相容关系 。
定理 集合 A上相容关系 r与完全覆盖 Cr(A)存在一一对应 。
ni AiA 1
Guoyongfang.2006@yahoo.com.cn
3-12序关系定义 偏 序关系
Ｒ是Ａ上的二元关系,如果Ｒ满足：
(1) 自反的
(2） 反对称的
(3) 传递的则称Ｒ是Ａ上 偏序关系 /半序关系 /部分序关系
(记为,≤,)
定义 集合 A连同 A上的偏序关系Ｒ一起 称为一个偏序 集,记为 <A,R > 。
Guoyongfang.2006@yahoo.com.cn
例,A={1,2,3,4,5,6,7,8,9}，
A上的二元关系
Ｒ 1＝ ｛ <ａ,ｂ >｜ ａ ≤ ｂ,ａ,ｂ ∈ A｝
Ｒ 2＝ ｛ <ａ,ｂ >｜ ａ |ｂ,ａ,ｂ ∈ A｝
Ｒ 1,Ｒ 2都是 A上的二元关系,
<A,Ｒ 1 >,<A,Ｒ 2>都是偏序集 。
序关系
Guoyongfang.2006@yahoo.com.cn
例,整数集 I上的二元关系
Ｒ 1＝ ｛ <ａ,ｂ > ｜ ａ ≤ ｂ,ａ,ｂ ∈ I｝
Ｒ 2＝ ｛ <ａ,ｂ > ｜ ａ |ｂ,ａ,ｂ ∈ I｝
<I,Ｒ 1 >,<I,Ｒ 2 >也都是偏序集 。
序关系
Guoyongfang.2006@yahoo.com.cn
例,A＝ ｛ ａ,ｂ,ｃ ｝
Ｒ 3＝ ｛ <ｓ 1,ｓ 2>｜ｓ 1?ｓ 2,ｓ 1,ｓ 2∈P （ A）｝
Ｒ 3是 P(A)上的二元关系,<P(A),Ｒ 3 >是偏序集 。
例,B是任意一个集合
Ｒ 3＝ ｛ <ｓ 1,ｓ 2> ｜ｓ 1?ｓ 2,ｓ 1,ｓ 2∈P （ B）｝
Ｒ 4是 B上的二元关系,<P（ B）,Ｒ 4>是偏序集 。
序关系
Guoyongfang.2006@yahoo.com.cn
例,集合 A的幂集 P(A)上定义的,?” 是 偏 序关系,
<P(A),?>是偏序集 。
例,实数集合 R上定义的,≤,是偏序关系,<R,≤> 是偏序集。
序关系例,大于零的 自然数集合 N＋ 上定义的,整除,关系,|”
也是一个偏序关系,<N＋,|>是偏序集。
Guoyongfang.2006@yahoo.com.cn
几点说明：
（ 1） 同一集合上的两个不同的偏序关系,构成两个不同的偏序集 。
如：Ｒ 1和Ｒ 2都定义在Ａ＝ {１,２,３,４,５,６,７,８,９ }上,
但 <Ａ,Ｒ 1>与 <Ａ,Ｒ 2>显然不是一样的偏序集 。
（ 2） 不同集合上分别相同定义的偏序关系,其偏序关系不同,同样构成两个不同的偏序集 。
如,<A,Ｒ 3>与 <B,Ｒ 3>是 两个不同的 偏序 集 。
序关系
Guoyongfang.2006@yahoo.com.cn
哈斯图二,哈斯图定义 设 <A,? >是偏序集,x,y?A,若有 x? y? y? x,则称 x与 y是可比的 。 若 x与 y可比,且 x? y,但不存在 z?A，
使得 x? z? z? y,则称 y盖住 x。
根据上述定义,可以简化偏序关系的关系图得到哈斯图,具体画法如下：
Guoyongfang.2006@yahoo.com.cn
序关系
用小圆圈表示 A中的元素，省掉关系图中所有的环。
(因自反性 )
对任意 x,y∈A(x≠y),若 x≤y,则将 x画在 y的下方，
可省掉关系图中所有边的箭头。 (因反对称性 )
对任意 x,y∈A(x≠y),若 x≤y,且 x与 y之间不存在
z∈A,使得 x≤z,z≤y,则 x与 y之间用一条线相连之，
否则无线相连。 (因传递性 )
Guoyongfang.2006@yahoo.com.cn
序关系例,设 A＝ {2,3,6,12,24,36},“≤,是 A上的整除关系，
画出其一般的关系图和哈斯图。
关系图 哈斯图
Guoyongfang.2006@yahoo.com.cn
序关系例,设集合 A＝ {a},B＝ {a,b},C＝ {a,b,c},D＝ {a,b,c,d}。
分别画出集合 A,B,C,D之幂集 P(A),P(B),P(C),P(D)上定义的,?” 的哈斯图。
Guoyongfang.2006@yahoo.com.cn
三,全序关系定义 设 <Ａ,≤>是偏序集,Ｂ?Ａ,若Ｂ中每两个元素都有关系,则称Ｂ为 链 。 若Ｂ中每两个元素都无关,则称Ｂ为 反链 。
定义 设 <A,? >为偏序集,若 A是一个 链,则称?为 A上的全序关系或线序关系,此时称 <A,? >为全序集 。 也就是集合 A中任意的两个元素都有关系 。
全序关系
Guoyongfang.2006@yahoo.com.cn
序关系例,1) 集合 A＝ {a,b,c}上定义的关系
R＝ {<a,a>,<b,b>,<c,c>,<a,b>,<b,c>,<a,c>}
则是一个全序关系。
2) 实数集合 R上定义的,≤,是全序关系。 <R,≤> 是全序集。
3) 集合 A＝ {a}的幂集 P(A)上定义的,?” 是全序关系。
<P(A),?>是全序集。
4) 任意基数 (元素个数 )大于２的集合 A的幂集 P(A)上定义的
,?” 则不是全序关系，仅是偏序关系。 <P(A),?>不是全序集。
Guoyongfang.2006@yahoo.com.cn
偏序集与特殊元素四、偏序集与特殊元素定义 <A,≤> 是偏序集,B是 A的任何一个子集。
若存在元素 b∈B,使得对任意 x∈B,都有 x≤b,则称 b为 B的最大元素 。
若存在元素 b∈B,使得对任意 x∈B,都有 b≤x,则称 b为 B的最小元素 。
若存在元素 b∈B,使得对任意 x∈B,满足 b≤x?x＝ b,则称 b为 B的极大元素 。
若存在元素 b∈B,使得对任意 x∈B,满足 x≤b?x＝ b,则称 b为 B的极小元素 。
Guoyongfang.2006@yahoo.com.cn
序关系续：
若存在元素 a∈A,使得对任意 x∈B,都有 x≤a,则称 a为 B的上界 。
若存在元素 a∈A,使得对任意 x∈B,都有 a≤x,则称 a为 B的下界 。
若元素 a’∈ A是 B的上界,元素 a∈A 是 B的任何一个上界,若均有 a’
≤ a,则称 a’为 B的上确界 。
若元素 a’∈A 是 B的小界,元素 a∈A 是 B的任何一个小界,若均有 a≤a ’,
则称 a为 B的下确界。
Guoyongfang.2006@yahoo.com.cn
序关系例,设集合 A＝ {1,2,3,4,5,6,7,8},D是 A上的整除关系，则 <A，
D>是偏序集，考虑 A的子集,B1＝ {1,2,3,6},B2＝ {2,3,5,7}，
B3＝ A。求出 B1,B2,B3的最大 (小 )元、极大 (小 )元、上 (下 )界、
上 (下 )确界。
集合 最大元 最小元 极大元 极小元上界 下界上确界 下确界
B1 6 1 6 1 6 1 6 1
B2 无 无 2,3,5,7 2,3,5,7 无 1 无 1
B3 无 1 5,6,7,8 1 无 1 无 1
Guoyongfang.2006@yahoo.com.cn
序关系例,设集合 A＝ {a,b,c}，考虑 P(A)上的关系,?”,则
<P(A),?>是偏序集。求 P(A)的子集,B1＝ {{a,b},{b,c},
{b},{c},Φ},B2＝ {{a},{c},{a,c}},B3＝ (A)的最大 (小 )元、
极大 (小 )元、上 (下 )界、上 (下 )确界。
集合最大元 最小元 极大元极小元上界下界上确界 下确界
B1 无 Φ {a,b},{b,c} Φ {a,b,c} Φ {a,b,c} Φ
B2 {a,c} 无 {a,c} {a},{c} {a,c},
{a,b,c}
Φ {a,c} Φ
B3 {a,b,c} Φ {a,b,c} Φ 无 Φ {a,b,c} Φ
Guoyongfang.2006@yahoo.com.cn
序关系例,设 A＝ {x1,x2,x3,x4,x5},A上定义偏序集 <A,≤> 的哈斯图如下，求 B＝
{x3,x4,x5}的最大 (小 )元、极大 (小 )元、上 (下 )界、上 (下 )确界。
解,最大元：无；
极大元,x3,x4；
x1,x2；
x5；
x5；
x5；
x5。
Guoyongfang.2006@yahoo.com.cn
一些结论,设 <A,≤> 是一偏序集,B是 A的子集。则：
若 b∈B 是 B的最大元?b是 B的极大元、上界、上确界；
若 b∈B 是 B的最小元?b是 B的极小元、下界、下确界；
若 a∈A 是 B的上确界，且 a∈B?a是 B的最大元；
若 a∈A 是 B的下确界，且 a∈B?a是 B的最小元；
若,≤,是一个全序关系，则 b∈B 是 B的最大元?b∈B 是 B的极大元；
若,≤,是一个全序关系，则 b∈B 是 B的最小元?b∈B 是 B的极小元。
若 b∈B 是 B的极大元，且 b是唯一的?b是 B的最大元。
若 b∈B 是 B的极小元，且 b是唯一的?b是 B的最小元。
序关系
Guoyongfang.2006@yahoo.com.cn
五、良序关系定义 设 <A,≤> 是一偏序集，若 A的任何一个非空子集都有最小元素，则,≤,称为良序关系,<A,≤> 是良序集。
良序关系例,设在集合 A＝ {a,b,c}上定义的偏序关系,≤,
的哈斯图如右图所示，可知此,≤,是良序关系。例,<N,≤>,<[0,1],≤> 都是良序集，
<I,≤>,<(0,1),≤> 则不是良序集。
Guoyongfang.2006@yahoo.com.cn
定理 （ 1） 良序集是全序集
（ 2） 全序集未必是良序的,
例：实数全体,任两个实数都是可比较的,但子集 ｛ 1/n｝ 的最小元找不到 。
（ 3） 有限的全序集是良序集 。
序关系
Discrete Mathematics
郭永芳
guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn
3－ 1 集合的概念及其表示法一,集合的概念及表示集合,集合是数学中最基本的概念之一,不能以更简单的概念来定义 (define),只能给出它的描述 (description)。 一些具有共同性质的对象的整体就称为一个集合,这个整体的每个对象称为该集合的一个 元素 (member或
element)。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法
用大写字母 A,B,C等表示集合,用小写字母 a,
b,c等表示集合的元素
·a?A表示,a是集合 A的元素,或说 a属于集合 A
·a?A表示,a不是集合 A的元素，或说 a不属于集合 A
集合的元素还可以是一个集合。
Guoyongfang.2006@yahoo.com.cn
一个集合，若其组成集合的元素的个数是有限的，则称作有限集，否则称为无限集。
集合中的元素是无序的，不重复的 。
集合的概念及其表示法
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法通常使用两种方法来给出一个集合：
·列元素法：列出某集合的所有元素,如：
·A = {0,1,2,3,4,5,6,7,8,9}表示所有小于 10的自然数所构成的集合
·B = {a,b,?,z} 表示所有小写英文字母所构成的集合
·性质概括法：使用某个性质来概括集合中的元素,
如,·A = { n | n 是小于 10的自然数 }
·C = { n | n 是质数 }表示所有质数所构成的集合
·D= { x | p（ x） } 如果 p(x)为真,则 x属于 D,否则 x不属于 D。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法二、集合的相等与子集外延性原理：
集合相等：两个集合 A和 B相等，当且仅当它们具有相同的成员，记为 A = B，即 a
属于集合 A当且仅当 a属于集合 B。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法子集,设 A,B是任意两个集合 B，假如 A的每一个元素是 B的成员，则称 A为 B的子集，或 A
包含在 B内，或 B包含 A。记为 A?B。如果集合
A的每一个元素都属于 B，但集合 B中至少有一个元素不属于 A，则称 A为 B的真子集，即 A?B
且 A不等于 B(A? B)。
一个集合 A的 平凡子集 有,A和?
定理,集合 A和 B相等的充要条件是两个集合相等互为子集。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法空集,不包含 任何元素的集合，称为空集，记为?。
定理,空集是任何集合的子集。
全集,在一定范围内，如果所有集合均为某一集合的子集。则称该集合为全集。
Guoyongfang.2006@yahoo.com.cn
集合的概念及其表示法三、幂集幂集,集合 A的幂集，记为 P(A)，是 A的所有子集所构成的集合，即：
·P(A) = { B | B? A }
·例如,A = {0,1},则 P(A) = {?,{0},{1},{0,
1} }
·显然，对任意集合 A，有 P(A)和 A?P(A)
定理,如果有限集合 A有 n个元素，则其 幂集
P(A)有 2n个元素。
Guoyongfang.2006@yahoo.com.cn
第一节作业
3-1习题
（ 2）（ 4） a,b,c （ 7）
Guoyongfang.2006@yahoo.com.cn
3-2集合的运算一、集合的交集合的 交,设任意集合 A和 B，由集合 A和 B的所有共同元素组成的集合，称为集合 A和 B的交集，记作 A?B。
S=A?B = {x | x?A? x?B}
集合的交也可推广到多个集合，设 A1,A2,…,An都是集合，它们的交定义为：
A1?A2…?An = {x |?i(x?Ai)}
Guoyongfang.2006@yahoo.com.cn
集合的运算二、集合的并集合的 并,设任意集合 A和 B，由所有属于集合 A或属于 B的元素组成的集合 S，称为集合 A和 B的并集，
记作 A?B 。
S=A?B = {x | x?A? x?B}
集合的并可推广到多个集合，设 A1,A2,…,An都是集合，它们的并定义为：
A1?A2…?An = {x |?i(x?Ai)}
Guoyongfang.2006@yahoo.com.cn
集合的运算三、集合的补集合的 补,设任意集合 A和 B，所有属于集合 A而不属于 B的一切元素组成的集合 S，称为集合 B 对于 A的补集或相对补，
记作 A?B 。
A?B = {x | x?A?x?B}。
A?B 也称为集合 A和 B的差。
绝对补,设 E为全集，对任一集合 A关于 E的补 E?A，称为集合
A的绝对补,记作 ~A。
~A= E?A= {x | x?E? x?A}。
Guoyongfang.2006@yahoo.com.cn
集合的运算四、集合的对称差集合的 对称差,设任意集合 A和 B,A和 B的 对称差为集合 S，其 元素属于集合 A，或属于 B，但不能既属于集合 A又属于 B，记作 A?B 。
A?B = (A?B)? (A?B) 。
Guoyongfang.2006@yahoo.com.cn
集合的运算用文氏图表示集合的运算：
Guoyongfang.2006@yahoo.com.cn
（ 1） 等幂律 A∪ A=A
A∩ A=A
（ 2） 结合律 (A∪ B)∪ C=A∪ (B∪ C)
(A∩ B)∩ C=A∩ (B∩ C)
（ 3） 交换律 A∪ B=B∪ A
A∩ B=B∩ A
Guoyongfang.2006@yahoo.com.cn
（ 4） 分配律
A∪ (B∩ C)=(A∪ B)∩ (A∪ C)
A∩ (B∪ C)=(A∩ B)∪ (A∩ C)
（ 5） 幺律
A∪?=A
A∩ U=A
Guoyongfang.2006@yahoo.com.cn
（ 6） 零律 A∪ U=U
A∩?=?
（ 7） 补律 A∪ A’=U
A∩ A’=?
（ 8） 吸收律 A∪ (A∩ B)=A
A∩ (A∪ B)=A
Guoyongfang.2006@yahoo.com.cn
（ 9） 德 ·摩根律
~(A∪ B)＝ ~ A∩ ~ B
~(A∩ B)＝ ~ A∪ ~ B
（ 10） 对合律 ~ (~A)=A
Guoyongfang.2006@yahoo.com.cn
集合的运算五、集合运算的性质：
~ (~ A) = A ~? = E ~ E =? A? ~A=E
A? ~ A =?
A?B = B?A A?(B?C) = (A?B)?C
A= A A?A =?
A?B= (A? ~B)? (~ A? B)
Guoyongfang.2006@yahoo.com.cn
集合的运算续：
(A?B)?A (A?B)?B A?(A?B) B?(A?B) (A?B)?A
A?B? (A?B) = B? (A?B) = A? (A?B) =?
(A?B) = (A? ~B)
A?B = A?C? B = C
A?(B-C) = (A? B)?(A? C)
Guoyongfang.2006@yahoo.com.cn
3－ 4序偶与笛卡尔积一,序偶定义 由两个元素 x,y按照一定的次序组成的二元组称为 有序偶对 (序偶 ),记作
<x,y>,其中 x为第一个元素,y为第二个元素 。 常常表达两个客体之间的关系 。
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积例,平面上点的坐标 <x,y>； 中国地处亚洲 <中国,亚洲 >，
<上,下 >,<左，右 >等都是有 序对。 <操作码,地址码 >则为一条单地址指令 。
定义 两个 序偶相等
<x,y>＝ <u,v>当且仅当 x＝ u,y＝ v。
序偶与集合的区别
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积定义 由 N个元素 a1,a2,a3,…,an按照一定的次序组成的 N元组称为 N重有序组,记作
<a1,a2,a3,…,an>即：
<a1,a2,a3,…,an>＝ <<a1,a2,a3,…,an-1>,an>。
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积例,a年 b月 c日 d时 e分 f秒可用下述六重有序组来描述,<a,b,c,d,e,f>。
性质 <a1,a2,a3,...,an>＝ <b1,b2,b3,…,bn>当且仅当 ai＝ bi。 (i＝ 1,2,3,...n)。
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积二,笛卡尔积定义 设 A,B是两个集合,若序偶的第一个成员是 A
的元素,第二个成员是 B的元素,所有这样序偶的集合,称为 A和 B的 笛卡尔积 或 直积 。 记作
A× B,
A× B＝ {<x,y>|(x∈ A)∧(y ∈ B)}。
Guoyongfang.2006@yahoo.com.cn
A× B＝ {<x,y>|(x∈A)∧(y∈B)};
序偶与笛卡尔积
B
A
例：
Guoyongfang.2006@yahoo.com.cn
序偶与笛卡尔积
× × × ×
× × × ×
× × × ×
× × × ×
1 2 3 4
a
b
c
d
D
C
C× D＝ {<x,y>|(x∈C)∧(y∈D)}
＝ {<1,a>,<1,b>,<1,c>,<1,d>,<2,a>,<2,b>,<2,c>,<2,d>,
<3,a>,<3,b>,<3,c>,<3,d>,<4,a>,<4,b>,<4,c>,<4,d>}。
例：
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {1,2},B＝ {a,b}
则 A× B＝ {<1,a>,<1,b>,<2,a>,<2,b>}；
而 B× A＝ {<a,1>,<a,2>,<b,1>,<b,2>｝。
由于 <1,a>≠<a,1>,<1,b>≠<b,1>,…,知：
A× B≠B × A 但 |A× B|＝ |B× A|＝ |A|× |B|。
因此，一般情况下，对任何两个集合 A,B，
当 A≠B 时，有,A× B≠B × A，
当 A＝ B时，有,A× B＝ B× A＝ A2。
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
笛卡尔积有如下性质：
1,A=?且A =?
2,不适合交换律,即 A?B不一定等于
B?A。
3,不适合结合律,即 A?(B?C)不等于
(A?B)?C。
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
笛卡尔积有如下性质 (续 )：
4,笛卡尔积运算对并和交运算满足分配律,即：
A?(B?C) = (A?B)?(A?C)
(B?C)?A = (B?A)?(C?A)
A?(B?C) = (A?B)?(A?C)
(B?C)?A = (B?A)?(C?A)
5,设 A,B,C,D是非空集合，则有 A?C,B?D?
A?B?C?D。
6,若 C非空，则
A?B? A?C?B?C?C?A?C?B
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
例,设 A,B,C,D为 4个集合,有：
1.A?B =?当且仅当 A =?或 B =?。
2.A,则 A?B?A?C当且仅当 B?C
3,A?C且 B?D,则 A?B?C?D,并且当
A = B =?或 A且 B时,其逆为真 。
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
定义 设 A1,A2,…,An是 N个集合，称下述集合：
A1× A2× … × An
＝ {<a1,a2,…,an>|(ai∈A i)∧i∈ {1,2,…,n}}
为由 A1,A2,A3,...,An构成的 笛卡尔积 。
当 A1＝ A2＝ … ＝ An时,A1× A2× … × An＝ An。
序偶与笛卡尔积
Guoyongfang.2006@yahoo.com.cn
一、关系 定义
R,R中任一序偶 <x,y>可 记为 <x,y>∈ R 或 xRy。
不在 R中任一序偶 <x,y>可 记为 <x,y>?R，或 xRy。
3-5、关系及其表示
Guoyongfang.2006@yahoo.com.cn
3-5、关系及其表示定义 设 R为二元关系，由 <x,y>∈ R的所有 x
组成的集合 称为 R的 前域,即
dom R = {x |?y(xRy) }
使 <x,y>∈ R的所有 y组成的集合 称为 R的 值域,即
ran R = {y |?x(xRy) }
R的前域 和 值域 一起 称为 R的 域,记作 FLD R,即
FLD R= dom R ∪ ran R
Guoyongfang.2006@yahoo.com.cn
例,设 R1＝ {<x,y>|(x,y?I)∧(x≤y)} ；
R2＝ {<x,y>|(x,y?I)∧(x 2+y2＝ 1)}；
R3＝ {<x,y>|(x,y?I)∧(|x| ＝ |y|＝ 3)}；
R4＝ {<x,y>|(x,y?I)∧(|x| ＝ y)}。
都是定义在整数集 I上的关系，求它们的定义域和值域。
关系及其表示解,domR1＝ I,ranR1＝ I；
domR2＝ {0,1,-1},ranR2＝ {0,1,-1}；
domR3＝ {3,-3},ranR3＝ {3,-3}；
domR4＝ I,ranR4=0,1,2… 。
Guoyongfang.2006@yahoo.com.cn
定义 X,Y为两个集合,X× Y的任何一个子集 R所定义的二元关系称为 从 X到 Y的二元关系,
简称关系 (Relation)。
把 X× Y的两个平凡子集 X× Y和?,分别称为
X到 Y的 全域关系 和 空关系 。
如 R是从 X到 X的二元关系，则称 R为 X上的二元关系 。
关系及其表示
Guoyongfang.2006@yahoo.com.cn
关系及其表示关系的数目：
由于任何 A× B的子集都是一个二元关系，
按照子集的定义，知 A× B共有 2|A|╳|B| 个不同的子集。因此，从 A到 B不同的关系共有 2|A|╳|B| 个。
恒等关系,设 Ix是 X的二元关系且满足 Ix =
{<x,x>|x?X},则称 Ix 是 X上的恒等关系。
Guoyongfang.2006@yahoo.com.cn
二、关系运算设 R,S都是集合 A到 B的两个关系，则：
R∪S ＝ {<x,y>|(xRy)∨(xSy)}
R∩S ＝ {<x,y>|(xRy)∧(xSy)}
R-S＝ {<x,y>|(xRy)∧(xS y)}
={<x,y>|(x y)}
根据定义，由于 A× B是相对于 R的全集，所以
＝ A× B-R,且 ∪ R＝ A× B,∩R ＝ Φ。
R?
关系及其表示
R R R
R
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {a,b,c},B＝ {1,2}，
R＝ {<a,1>,<b,2>,<c,1>}，
S＝ {<a,1>,<b,1>,<c,1>}，
则,R∪S ＝ {<a,1>,<b,2>,<c,1>,<b,1>}；
R∩S ＝ {<a,1>,<c,1>}；
R-S＝ {<b,2>}；
＝ {<a,2>,<b,1>,<c,2>}＝ A× B-R。R
关系及其表示
Guoyongfang.2006@yahoo.com.cn
关系及其表示三、关系的表示法
1.集合表示法
2.关系矩阵
3.关系图法
Guoyongfang.2006@yahoo.com.cn
关系及其表示
1.集合表示法例 1)、设 A＝ {2},B＝ {3},关系 R＝ {<2,3>}
2)、如定义集合 N上的“小于等于”关系：
R＝ {<x,y>|(x,y?N)∧(x≤y) }。
Guoyongfang.2006@yahoo.com.cn
2.关系矩阵设 A＝ <a1,a2,a3,...,an>,B＝ <b1,b2,b3,...,bm>，
R是从 A到 B的一个二元关系，则对应于关系 R之关系矩阵 MR＝（ rij)n× m。其中,称 MR为 R的 邻接矩阵 。
)m,.,,,3,2,1j,n,.,,,3,2,1i(Rb,a0 Rb,a 1r
ji
ji
ij
关系及其表示
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {2,3,4｝,B＝ {1,2,4｝,
考虑从 A到 B的,大于等于,关系 R和,小于等于,关系 S：
R＝ {<2,1>,<2,2>,<3,1>,<3,2>,<4,1>,<4,2>,<4,4>}，
S＝ {<2,2>,<2,4>,<3,4>,<4,4>｝。
写出 R,S的关系矩阵。
解,
111
011
011
M R
100
100
110
M S
关系及其表示
Guoyongfang.2006@yahoo.com.cn
三,关系图法如 R是定义在 A＝ <a1,a2,a3,...,an>上的关系，则对应于关系 R有如下规定：
①,设 a1,a2,...,an为图中节点，用,。,表 示
②,如 <ai,aj>?R,则从 ai到 aj可用一有向边 ai。 。 aj相连。
<ai,aj>为对应图中的有向边。
③,如 <ai,ai>?R,则从 ai到 ai用一带箭头的小圆环表示。
关系及其表示
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ <P1,P2,P3,…,P6>是六个程序，考虑它之间的一种调用关系 R，如 Pi可调用 Pj,则有 <Pi,Pj>R,现假设
R＝ {<P1,P2>,<P2,P6>,<P5,P2>,
<P4,P4>,<P3,P1><P3,P4><P4,P5>}
则此关系 R的关系图如下：
关系及其表示
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {a1,a2,a3,?,a 6｝是六个人,B＝ {1,2,3｝
是三套房间，考虑 A到 B之间的一种住宿关系 R，如 ai住房间 j,则有 <ai,j>?R,现假设,R＝ {<a1,1>,<a2,3>,<a3,1>,
<a4,2>,<a5,3>,<a6,2>}则此关系 R的关系图如下：
关系及其表示
Guoyongfang.2006@yahoo.com.cn
3－ 6关系性质一、关系的一些重要性质定义 R是集合 X上的二元关系，
对任意的 x∈ X,都满足 <x,x>∈ R,则称 R是 自反 的关系 。
对任意的 x∈ X,都满足 <x,x>?R,则称 R是 反自反 的关系 。
对任意的 x,y∈ X,满足 <x,y>∈ R?<y,x>∈ R,则称 R是 对称 的关系 。
对任意的 x,y∈ X,满足 <x,y>∈ R∧<y,x> ∈ R?x＝ y,则称 R是 反对称 的关系 。
对任意的 x,y,z∈ X,满 <x,y>∈ R∧<y,z> ∈ R?<x,z>∈ R,
则称 R是 传递 的关系 。
Guoyongfang.2006@yahoo.com.cn
例,在整数集 I上定义的,小于等于,关系是自反的、反对称的、传递的关系；,小于,关系是反自反的、反对称的、
传递的关系；,等于,关系是自反的、反对称的、对称的、
传递的关系。
幂集上的,包含,关系关系是自反的、反对称的、传递的关系；
,真包含,关系是反自反的、反对称的、传递的关系；
,相等,关系是自反的、反对称的、对称的、传递的关系。
请注意：
任何不是自反的关系未必一定是反自反的关系，反之亦然。
任何不是对称的关系也未必一定是反对称的关系，反之亦然。
关系性质
Guoyongfang.2006@yahoo.com.cn
例 设 A＝ {1,2,3,4},R＝
{<1,1>,<1,2>,<2,1>,<3,4>}是 A上的关系 。 则 R即不是自反的，又非反自反的；即不是对称的，也非反对称的；而且也不是传递的。即不具备关系的任何性质。
关系性质
Guoyongfang.2006@yahoo.com.cn
关系性质例 设 A是任意的集合,A上的完全关系 A× A是自反的、对称的、传递的关系； A上的空关系 Φ是反自反的、反对称的、对称的、传递的关系； A上的恒等关系 IA是自反的、对称的、反对称的、传递的关系。
例 1)朋友关系是自反的、对称的、而非传递的关系；
2)父子关系是反自反的、反对称的、而非传递的关系,
Guoyongfang.2006@yahoo.com.cn
二、用关系图来描述关系的这几种重要的性质在关系图中,每个节点都有环,则此关系是自反关系,
在关系图中,每个节点都无环,则此关系是反自反关系。
在关系图中,任何一对节点 (可以相同 )之间,要么有方向相反的两条边,要么无任何边,则此关系是对称关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
用关系图来描述关系的这几种重要的性质 (续 )
在关系图中,任何一对节点 (可以相同 )之间,至多有一条边存在,则此关系是反对称关系。
在关系图中,任何三个节点 x,y,z(可以相同 )之间，若从 x到 y有一条边存在,从 y到 z有一条边存在,则从 x
到 z一定有一条边存在,则此关系是传递关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
三、用关系矩阵来描述关系的这几种重要的性质在关系矩阵中,对角线上全为 1,则此关系是自反关系。
在关系矩阵中,对角线上全为 0,则此关系是反自反关系。
若 R之关系矩阵为对称矩阵,则此关系是对称关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
用关系矩阵来描述关系的这几种重要的性质 (续 )
若 R之关系矩阵为反对称矩阵 (关于元素 1的反对称 ),则此关系是反对称关系。
在关系矩阵中,对任意 i,j,k ∈ {1,2,3,…,
n},满足 如 rij＝ 1∧r jk＝ 1则 rik＝ 1,则此关系是传递关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {1,2,3},定义在 A上的关系如下图：
关系性质
Guoyongfang.2006@yahoo.com.cn
解,从关系图易判断上述关系之性质如下：
图 (a)的关系是自反的、对称的、反对称的、传递的关系；
图 (b)的关系是具备反自反的、对称的、反对称的、传递的关系；
图 (c)的关系是具备对称的、反对称的、传递的关系；
图 (d)的关系是不具备任何的性质关系；
关系性质
Guoyongfang.2006@yahoo.com.cn
解 （ 续）,
图 (e)的关系是具备自反的、对称的、传递的关系；
图 (f)的关系是具备反自反的、反对称的、传递的关系；
图 (g)的关系是具备反自反的、反对称的关系；
图 (h)的关系是具备反自反的、斜对称的、反对称的、传递的关系。
关系性质
Guoyongfang.2006@yahoo.com.cn
例,设 R＝ {<a,a>,<b,b>}是定义在 A＝ {a,b}上的二元关系,S＝ {<a,a>,<b,b>}是定义在 B＝ {a,b,c}上的二元关系,试判断 R,S具备何种性质。
解,1.由于 R＝ {<a,a>,<b,b>}是定义在 A＝ {a,b}上的关系，所以，对任意的 x∈A,都满足 <x,x>∈R,则 R是自反的关系；另外,R也是对称的、反对称的和传递的,
2,S＝ {<a,a>,<b,b>}虽然与 R完全相等 (从集合的观点 )，但它却是定义在 B＝ {a,b,c}上的二元关系。由于 c∈B,但 <c,c>?S,所以,S不是 B上的自反关系；另外,S也是对称的、反对称的和传递的。
关系性质
Guoyongfang.2006@yahoo.com.cn
关系性质关系性质的逻辑表示,设 R是集合 A上的二元关系，
1) R是自反的?
))Rx,x()Ax)((x( 是永真的
2) R不 是自反的? ))Rx,x()Ax)((x( 是永真的
3) R是 反 自反的? ))Rx,x()Ax)((x( 是永真的
4) R不 是 反 自反的? ))Rx,x()Ax)((x( 是永真的
5) R是 对称 的? ))Rx,y()Ry,x)((y)(x( 是永真的
6) R不 是 对称 的? ))Rx,y()Ry,x)((y)(x( 是永真的
Guoyongfang.2006@yahoo.com.cn
关系性质
9) R是 传递 的?
))Rz,x())Rz,y()Ry,x)(((z)(y)(x( 是永真的
10)R不 是 传递 的?
))Rz,x()Rz,y()Ry,x)((z)(y)(x(
是永真的
7) R是 反 对称 的?
))Rx,y())Ry,x()yx)(((y)(x(
))yx())Rx,y()Ry,x)(((y)(x(
是永真的
8) R不 是 反 对称 的?
))Rx,y()Ry,x()yx)((y)(x( 是永真的关系性质的逻辑表示 (续 )
Guoyongfang.2006@yahoo.com.cn
2,反自反关系性质
1,自反任取 x?A,中间过程任取 x?A,中间过程
<x,x>?R。
<x,x>?R。
关系性质的证明方法：
Guoyongfang.2006@yahoo.com.cn
关系性质
3,对称任取 x,y?A，
假设 <x,y>?R，
中间过程 <y,x>?R。
4,传递任取 x,y,z?A，假设
<x,y>?R,<y,z>?R,中间过程 <x,z>?R。
关系性质的证明方法 (续 )：
Guoyongfang.2006@yahoo.com.cn
关系性质
5,反对称任取 x,y?A，假设
<x,y>?R,<y,x>?R,中间过程 x＝ y。
或者任取 x,y?A,x≠y，
假设 <x,y>?R,中间过程 <y,x>?R。
关系性质的证明方法 (续 )：
Guoyongfang.2006@yahoo.com.cn
作业
P113 3-6习题
（ 2）（ 4）（ 6）
Guoyongfang.2006@yahoo.com.cn
3－ 7复合 关系和逆关系一,复合 关系定义 设 R是一个从集合 A到集合 B的二元关系,S是从集合 B到集合 C的二元关系 (也可简单的描述为 R,A→B,S：
B→C),则 R与 S的 复合关系 R?S是从 A到 C的关系,并 且：
R?S＝ {<x,z>|(x∈A)∧(z∈C)∧
(?y)((y∈B)∧(xRy)∧(ySz))}
运算,?” 称为 复合运算 。
Guoyongfang.2006@yahoo.com.cn
例：设 R＝ {<1,2>,<3,4>,<2,2>}
S＝ {<4,2>,<2,3>,<3,1>}，
分别是定义为从 A→B 和从 B→C 的关系，其中 A＝ B＝ C＝ {1,2,3,4}。
1).用集合方法求 R?S,S?R,R?R,S?S。 则：
R?S＝ {<1,3>,<3,2>,<2,3>}；
S?R＝ {<4,2>,<2,4>,<3,2>}；
R?R＝ {<1,2>,<2,2>}；
S?S＝ {<4,3>,<2,1>}。
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
复合 关系和逆关系
2).用关系矩阵求 R?S。
0000
0010
0100
0100
0010
0001
0100
0000
0000
1000
0010
0010
MMM SRSR?
其中，
MR?S＝ (r'ij)|A|× |C|，
|C|,.,,2,1j
|A|,.,,,2,1i)rr('r
kjik
|B|
1k
ij?
Guoyongfang.2006@yahoo.com.cn
设 I是整数集合,R,S是 I到 I的两个关系：
R＝ {<x,3x>|x∈ I}； S＝ {<x,5x>|x∈ I}。
则,R?S＝ {<x,15x>|x∈ I}
S?R＝ {<x,15x>|x∈ I}
R?R＝ {<x,9x>|x∈ I}
S?S＝ {<x,25x>|x∈ I}
(R?R)?R＝ {<x,27x>|x∈ I}
(R?S)?R＝ {<x,45x>|x∈ I}
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
定义 设 R是集合 A上的二元关系，则可定义 Rn,
该 Rn也是 A上的二元关系，定义如下：
1.R0＝ IA＝ {<a,a>|a∈ A}；
2.R1＝ Ｒ；
3.Rn+1＝ Rn?R＝ R?Rn。
显然,Rm?Rn＝ Rm+n,(Rm)n＝ Rmn。
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
二、逆关系定义 设 R是一个从集合 A到集合 B的二元关系，则从 B到 A的关系 Rc＝
{<b,a>|<a,b>R}称为 R的 逆关系,运算
,c”称为 逆运算 。
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
例,设 A＝ {a,b,c),B＝ {1,2,3},R是从 A到 B的一个关系,R＝ {<a,1>,<c,2>,<b,3>}，
则,Rc＝ {<1,a>,<2,c>,<3,b>}。
关系图和关系矩阵如下：
010
100
001
M
,
010
100
001
M
1
R
R
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
三、几种运算之间的若干重要性质定理 设 R,S,T分别是从集合 A到集合 B，
集合 B到集合 C，集合 C到集合 D的二元关系，则：
1)(R?S)?T＝ R?(S?T)
2)(R?S)c＝ Sc?Rc
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
复合 关系和逆关系证明,1)设 <a,d>∈ (R?S)?T,则由复合运算知,至少存在
c∈C,使得,<a,c>∈R?S,<c,d>∈ T。
又 对于 <a,c>∈ R?S,则至少 存一个 b∈B,使得：
<a,b>∈ R,<b,c>∈ S。
因此,由 <b,c>∈ S,<c,d>∈ T,有 <b,d>∈ S?T，
又由 <a,b>∈ R和 <b,d>∈ S?T,知,<a,d>∈ R?(S?T),
所以 (R?S)?T?R?(S?T)。
同理可证,R?(S?T)?(R?S)?T。
由集合性质知,(R?S)?T＝ R?(S?T)。
Guoyongfang.2006@yahoo.com.cn
2).任取 <c,a>∈ (R?S)c，则 <a,c>∈ R?S,由,?” 的定义知：则至少存一个 b∈B,使得,<a,b>∈ R，
<b,c>∈ S，
即,<b,a>∈ Rc,<c,b>∈ Sc。由 <c,b>∈ Sc和 <b,a>∈ Rc,
有,<c,a>∈ Sc?Rc，所以,(R?S)c?Sc?Rc。
反之,任取 <c,a>∈ Sc?Rc，由,?” 的定义知：则至少存一个 b∈B,使得,<c,b>∈ Sc和 <b,a>∈ Rc，所以：
<a,b>∈ R,<b,c>∈ S。 由,?” 知,<a,c>∈ R?S。即有,<c,a>∈ (R?S)c。所以,Sc?Rc?(R?S)c。
由集合的定义知,(R?S)c＝ Sc?Rc。■
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
定理 设 R,S是从集合 A到集合 B的二元关系，
则有：
(Rc)c＝ R；
(R∪S) c＝ Rc∪S c；
(R∩S) c＝ Rc∩S c；
(R-S)c＝ Rc-Sc；
(R)c＝ Rc；
(A× B)c＝ (B× A)；
复合 关系和逆关系
Guoyongfang.2006@yahoo.com.cn
定理：设 R为 X上的二元关系，则
R是对称的，当且仅当 R=Rc
R是反对称的，当且仅当 R ∩R c? Ix
Guoyongfang.2006@yahoo.com.cn
定义 设 R是 X上的二元关系,如果另一个关系 R’是满足：
1,R’是自反的 （ 对称的,传递的 ） ；
2,R? R’；
3.对于 A上的任意自反的 （ 对称的,传递的 ） 关系 R”,若
R?R”,则 R’?R”。
则称 R’为 R的 自反 （ 对称,传递 ） 闭包 。
换句话说,R的自反闭包（对称闭包、传递闭包）是包含 R的最小的自反的（对称的、传递的）关系。通常分别用 r(R),s(R)和 t(R)表示 R的自反闭包、对称闭包和传递闭包。
3-8关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
【 定理 】 设 R 是 X 上的二元关系,则：
1,R是自反的当且仅当 r(R) = R；
2,R是对称的当且仅当 s(R) = R；
3,R是传递的当且仅当 t(R) = R；
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
定理 设 R是集合 A上的二元关系，则：
1,r(R)＝ R∪I A。
2,s(R)＝ R∪R -1。
3,t(R)＝ t(R) = R? R2? R3?,..。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
证,1,首先 R? IA是自反的，且 R? R? IA，
若又有自反关系 R’满足 R? R’，则因为 R’
是自反的有 IA? R’，即有 R? R’? IA? R’，
从而有 R? IA? R’，命题得证。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
证,2.首先 R? R-1是对称的，因为 (R? R-1)-1 = R? R-1。
若又有对称关系 R? R’，则对任意的 <x,y>? A? A，
有,<x,y>? R? R-1? (<x,y>? R)? (<x,y>? R-1)?
(<x,y>? R’)? (<y,x>? R)? (<x,y>? R’)? (<y,x>?
R’)? (<x,y>? R’)? (<y,x>? R’-1) // R’ = R’-1
(<x,y>? R’)? (<x,y>? R’)? <x,y>? R’
即 R? R-1? R’，命题得证。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
证,3.记 R+ = R? R2? R3?,..，首先证 t(R)? R+，这只要证 R+是传递的，因为若 R+是传递的，而又有 R? R+，
那么根据传递闭包的定义有 t(R)? R+。为了证 R+是传递的，我们考察对任意的 x,y,z?A，若 <x,y>?R+且 <y,
z>?R+，则必存在自然数 n,m使得 <x,y>?Rn且 <y,
z>?Rm，那么有 <x,z>?Rn? Rm = Rn+m，从而 <x,y>?R+，
因此 R+确实是传递的。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
证,3,再证 R+? t(R)，这只要证对任意的自然数 n?1有 Rn? t(R)，
为此我们使用数学归纳法：
i),归纳基,当 n = 1时,根据传递闭包的定义有 R?t(R)；
ii).归纳步，设当 n = k时，有 Rk? t(R)，考察 n = k+1，因为有 Rk+1 = Rk? R，所以对任意的 x,y?A，若 < x,y>?R k+1，则必存在 z?A使得 <x,z>?Rk且 <z,y>?R，因此有 <x,z>?t(R)且
<z,y>?t(R)，而 t(R)是传递的，因此有 <x,y>?t(R)，即对任意的自然数 n?1有 Rn? t(R)，因此 R+? t(R)，而上面已经证明了 t(R)? R+，所以有 R+ = t(R)，从而命题得证。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
例,设 P＝ {P1,P2,P3,P4}是四个程序,R,S是定义在 P上的调用关系如下：
R＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>}
S＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>}
求 r(R),s(R),t(R),r(S),s(S),t(S)。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
关系的闭包运算解,r(R)＝ R∪I A
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>}∪
{<P1,P1>,<P2,P2>,<P3,P3>,<P4,P4>}
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>,<P1,P1>,
<P2,P2>,<P3,P3>,<P4,P4>}。
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>,<P1,P4>}。
s(R)＝ R∪R -1＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>}∪
{<P2,P1>,<P3,P1>,<P4,P2>,<P4,P3>}
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>,<P2,P1>,
<P3,P1>,<P4,P2>,<P4,P3>}。
Guoyongfang.2006@yahoo.com.cn
关系的闭包运算
t(R)＝ R∪R 2∪R 3∪R 4＝ {<P1,P2>,<P1,P3>,<P2,P4>,
<P3,P4>}∪{<P 1,P4>}∪ Φ∪ Φ
＝ {<P1,P2>,<P1,P3>,<P2,P4>,<P3,P4>,<P1,P4>}。
r(S)＝ S∪I A＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>}∪
{<P1,P1>,<P2,P2>,<P3,P3>,<P4,P4>}
＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>,<P1,P1>,
<P2,P2>,<P3,P3>,<P4,P4>}。
Guoyongfang.2006@yahoo.com.cn
s(S)＝ S∪S -1＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>}
∪{<P 2,P1>,<P1,P2>,<P3,P2>,<P4,P3>}
＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>,<P3,P2>,<P4,P3>}
关系的闭包运算
t(S)＝ S∪S 2∪S 3∪S 4
＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>}
∪{<P 1,P1>,<P2,P2>,<P1,P3>,<P2,P4>}
∪{<P 1,P2>,<P2,P1>,<P1,P4>,<P2,P3>}
∪{<P 1,P1>,<P2,P2>,<P1,P3>,<P2,P4>)
＝ {<P1,P2>,<P2,P1>,<P2,P3>,<P3,P4>,<P1,P1>,
<P2,P2>,<P1,P3>,<P1,P4>,<P2,P4>}。
Guoyongfang.2006@yahoo.com.cn
证明：
对?（ ｘ,ｙ ） ∈ t(Ｒ ),?ｋ,使 （ ｘ,ｙ ） ∈
Ｒ k,表明在Ａ中存在不同元素ａ 1,ａ 2,…,ａ k-1，
使 （ ｘ,ａ 1）,（ ａ 1,ａ 2）,（ ａ 2,ａ 3）,…，
（ ａ k-1,ｙ ） ∈ Ｒ 。 若ｋ＞ｎ,则ａ 1,ａ 2,…，
ａ k-1,ｙ中至少有两个相同,不妨设ａ i＝ｙ,
（ ｉ ≤ ｋ－１ ） 。
定理,设｜Ａ｜＝ｎ,Ｒ是Ａ上二元关系,则存在正整数ｋ,ｋ ≤ ｎ,使 t(Ｒ )＝Ｒ ∪ Ｒ 2∪ …∪ Ｒ k。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
于是（ｘ，ａ 1）,…（ａ i，ａ i-1 ） ∈ Ｒ,
（ａ i-1,ｙ） ∈ Ｒ，故（ｘ，ｙ） ∈ Ｒ i，
即 若ｋ＞ｎ，必存在比ｋ小的正整数ｉ，
使（ｘ，ｙ） ∈ Ｒ i。
注：定理说明,可用Ｒ ∪ Ｒ 2∪ …∪ Ｒ n来求 t(Ｒ ) 。
例６,设Ａ＝ ｛ １,２,３ ｝,
Ｒ＝ ｛（ １,１ ）,（ １,２ ）,(２,３ ）｝
求 t(Ｒ )。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
解,Ｒ＝
000
100
011
,Ｒ
2
＝
000
000
111
＝Ｒ
3
故
R
＝Ｒ∪Ｒ
2
∪Ｒ
3
＝
000
100
111
R
＝ ｛ （１，１）,（１，２）,（１，３）,（２，３）｝
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
Ｗａｒｓｈａｌｌ算法：（１９６２）
设Ｒ是ｎ个元素集合上的二元关系
(1)
(2)ｉ ← １；
(3)ｆｏｒ ｊ＝１ ｔｏ ｎ
iｆ ａ j,i＝１ ｔｈｅｎ
ｆｏｒ ｋ＝１ ｔｏ ｎ ｄｏ
ａ j,k← ａ j,k∨ ａ i,k
(4)ｉ =ｉ＋１；
(5) iｆ ｉ ≤ｎ,ｔｈｅｎ go (3)
ｅｌｓｅ ｓｔｏｐ
注：当｜Ａ｜＝ｎ较大时,用上述定理计算 t(Ｒ )工作量非常大 。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
注,（ 1） 结果 (aij)nxn是 t(Ｒ )的相关矩阵 。
（ 2） 算法的复杂度为ｎ 3。
例７：Ａ＝ ｛ ａ,ｂ,ｃ,ｄ ｝
Ｒ＝ ｛（ ａ,ｂ ）,（ ｂ,ｃ ）,
（ ｃ,ｄ ） ｝
计算 t(Ｒ ) 。
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
0000
1000
0100
0010
R
(1)i=1 由于 aj1=0(j=1,2,3,4) 不改动
(2)i=2 j=1,aji=1? a13=1
(3)i=3
0000
1000
0100
011
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
j=1,a13=1? a14=1
j=2,a23=1? a24=1
即 Ｒ *＝｛（ａ，ｂ），（ａ，ｃ），
（ａ，ｄ），（ｂ，ｃ），
（ｂ，ｄ），（ｃ，ｄ）｝
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
定理 R是集合 A上的关系，则：
1)rs(R)＝ sr(R)
2)rt(R)＝ tr(R)
3)st(R)?ts(R)
关系的闭包运算
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖
定义 若把一个集合 A分成若干个叫做分块的非空子集，
使得 A中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做 A的一个覆盖。如果 A中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做 A的一个划分（或分化）。
Guoyongfang.2006@yahoo.com.cn
定义 A是一个集合,A1,A2,A3...Am是 A的任何 m个子集,如果 A1,A2,A3...Am满足：
1) 则 称集合 П (A)＝ {A1,A2,A3,....,Am｝ 为集合 A的一个 覆盖 。
2)对一切的 i≠j(i,j ＝ 1,2,3,....,m),都有 Ai∩A j＝ Φ。
则称集合 П (A)＝ {A1,A2,A3,....,Am｝ 为集合 A的一个 划分,而 A1,A2,A3,...Am叫做这个划分的 块 。
3－ 9集合的划分与覆盖
AA im
1i
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖
例如,A={a,b,c},考虑下列子集：
S={{a,b},{b,c}},Q={{a},{a,b},{a,c}}
D={{a},{b,c}},G={{a,b,c}}
E={{a},{b},{c}},F={{a},{a,c}}
则 S,Q是 A的覆盖,D,G,E是 A的划分,F既不是划分也不是覆盖。显然，若是划分则必是覆盖，其逆不真。
最大划分最小划分
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖
定义 若 {A1,A2,···,Ar}与 {B1,B2,···,Bs}是同一集合 A的两种划分，则其中所有 Ai∩ Bj≠∮ 组成的集合,称为是原来两种划分的交叉划分。
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖定理 设 {A1,A2,···,Ar}与 {B1,B2,···,Bs}是同一集合 X的两种划分,则其交叉划分亦是原集合的一种划分 。
证明：因为题设的交叉划分是：
{A1∩ B1,A1∩ B2,···,A1∩ Bs，
A2∩ B1,A2∩ B2,···,A2∩ Bs,···,
Ar∩ B1,Ar∩ B2,···Ar∩ Bs},
在交叉划分中,取任两元素,Ai∩ Bh,Aj∩ Bk,考虑 （ Ai∩ Bh） ∩ (Aj∩ Bk)，
Ⅰ,若 i≠j 且 h=k,因为 Ai∩ Aj = Φ故
Ai∩ Bh∩ Aj∩ Bk= Φ ∩ Bh∩ Bk= Φ
Ⅱ,若 i≠j 且 h≠k,因为 Ai∩ Aj = Φ,Bh∩ Bk= Φ故
Ai∩ Bh∩ Aj∩ Bk= Φ ∩ Φ = Φ
Ⅲ,若 I=j且 h≠k,情况与 Ⅰ 相同 。
综上所述,在交叉划分中,任取两元素,其交为
Ai∩ Bh∩ Aj∩ Bk= Φ
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖其次交叉划分中所有元素得并为：
(A1∩ B1)?(A1∩ B2)? ···?(A1∩ Bs)?
(A2∩ B1)?(A2∩ B2 )? ···?(A2∩ Bs)? ···?
(Ar∩ B1)?(Ar∩ B2 )? ···?(Ar∩ Bs)=X ∩ X= Φ
Guoyongfang.2006@yahoo.com.cn
3－ 9集合的划分与覆盖
定义 给定 X的任意两个划分 {A1,A2,···,Ar}与 {B1,B2,···,Bs}，若对于每一个 Aj均有 Bk，使 AjBk，则 {A1,A2,···,Ar}称为是
{B1,B2,···,Bs}的加细。
定理 任何两种划分的交叉划分，都是原来个划分的一种加细。
证明：设 {A1,A2,···,Ar}与 {B1,B2,···,Bs}的交叉划分为 T,对 T中任意元素 Ai∩ Bj 必有 Ai∩ Bj ∈ Ai和 Ai∩ Bj ∈ Bj,故 T必是原划分的加细。
Guoyongfang.2006@yahoo.com.cn
3-10等价关系与等价类一、等价关系定义 R是定义在集合 A上的关系，如果 R是 自反的、对称的、传递的,则称此关系 R为 A上的 等价关系 。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类例,1,在全体中国人所组成的集合上定义的,同姓,关系,就是具备自反的,对称的,传递的性质,因此,
就是一个等价关系；
2,对任何集合 A,考虑 R＝ A× A,则 R是 A上的等价关系；
3,三角形的,相似关系,,,全等关系,等是等价关系；
4.,朋友,关系,则不是等价关系,因它是不传递的 。
5,幂集上定义的,?”,整数集上定义的,≤,都不是
,因为它们是不对称的 。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类证明,1、对任意 x∈A,有 (x-x)被 12所整除，所以 <x,x>∈R,
即 R是自反的。
2、对任意 x,y∈A,若 <x,y>∈R,有 (x-y)被 12所整除，所以
(y-x)＝ -(x-y)被 12所整除,所以,<y,x>∈R,即 R是对称的。
3、对任意 x,y,z∈A,若 <x,y>∈R 且 <y,z>∈R,有 (x-y)被 12所整除且 (y-z)被 12所整除,所以 (x-z)＝ (x-y)＋ (y-z)被 12
所整除,所以,<x,z>∈R,即 R是传递的,
由 1,2,3知 R是等价关系。■
例,在时钟集合 A＝ {1,2,3,…,24}上定义关系
R＝ {<x,y>|(x,y?A)∧((x -y)被 12所整除 )｝。
证明 R是一个等价关系。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类此等价关系的关系图：
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类例,考虑整数集合 I上的关系如下：
R＝ {<x,y>|{x,y∈I)∧((x -y)被 m所整除 )∧(m∈N ＋ )}，
此 R称为 I上的 以 m为模的同余关系 。一般记 xRy为：
x?y(mod m) (同余式 )。
可以证明,R也是 I上的 等价关系,此时 R将 I分成了如下的一些子集：
{…,-3m,-2m,-m,0,m,2m,3m,… }；
{…,-3m＋ 1,-2m＋ 1,-m＋ 1,1,m＋ 1,2m＋ 1,3m＋ 1,… }；
{…,-3m＋ 2,-2m＋ 2,-m＋ 2,2,m＋ 2,2m＋ 2,3m＋ 2,… }；
……
{…,-2m-1,-m-1,-1,m-1,2m-1,3m-1,4m-1,… }；
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类二、等价类
R是集合 A上的等价关系,对任意 x∈A,称集合 [x]R：
[x]R＝ {y|(y∈A)∧(<x,y>∈R)}
叫做 x关于 R的 等价类,或叫作由 x生成的一个 R等价类。其中 x称为 [x]R的 生成元 (或叫 代表元,
或 典型元 )。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类例,设 A＝ {0,1,2,3,5,6,8}，考虑 R是 A上的以 3为模的同余关系，
求其等价类。对于前边例子中的时钟集合，求其等价类。
解,1,R是一个等价关系,为此可求 [x]R(x∈A) 。
[0]R＝ {0,3,6}＝ [3]R＝ [6]R；
[1]R＝ {1}；
[2]R＝ {2,5,8}＝ [5]R＝ [8]R。
2,[1]R＝ {1,13}＝ [13]R；
[2]R＝ {2,14}＝ [14]R；
…
[12]R＝ {12,24}＝ [24]R。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类定理 设给定集合 A上的等价关系 R,对于 a,b∈A 有 aRb iff
[a]R=[b]R.
证明：假定 [a]R=[b]R,因为 a∈[a] R,a∈[b] R,即 aRb.
反之,若 aRb,设
c∈[a] R=>aRc=>cRa=>cRb=>c∈[b] R
即 [a]R∈[b] R
同理,若 c∈[b] R=>bRc=>aRc=>c∈[a] R,故 [b]R[a]R,
由此证得若 aRb,则 [a]R∈ [b]R 。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类定义 R是集合 A上的等价关系，由 R确定的一切等价类的集合，称为集合 A上的关于 R的 商集,记为 A/R，
A/R＝ {[x]R|(x∈A)} 。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类三、等价与划分的关系定理 R是集合 A上的等价关系，则此关系 R可唯一的确定 A上的一个划分 П R(A),П R(A)＝ {[x]R|(x∈A)},
此划分正好是集合 A上关于 R的商集 A/R。
证明：Ｒ是等价关系,?ａ ∈ Ａ，由Ｒ的自反性，（ａ，
ａ） ∈ Ｒ，即ａ与ａ属于同一等价类，也即?ｉ，ａ ∈
Ａ i 若ｉ ≠ｊ，Ａ i≠Ａ j，而Ａ i∩Ａ j ≠?，则?ｃ ∈ Ａ i∩Ａ j，
ｃ ∈ Ａ i，且ｃ ∈ Ａ j,
Guoyongfang.2006@yahoo.com.cn
续：
对?ａ ∈ Ａ i,ａ～ｃ
对?ｂ ∈ Ａ j,ｂ～ｃ,即ｃ～ｂ (对称性 )
由Ｒ传递性,ａ～ｂ
由ａ,ｂ的任意性,故Ａ i＝Ａ j 与Ａ i和Ａ j 为不同的等价类矛盾 。
故Ａ i∩Ａ j =? 所以,Ｒ完成了等价类的划分 。
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
定理 集合 A的任何一个划分 П (A)可唯一地确定 A上的一个等价关系 RП,RП ＝ {<x,y>|(x,y∈A)∧(x,y 同属 П (A)的一个划分块 )｝即若设 П (A)＝
{A1,A2,A3,....,Am}，则,RП ＝
A1× A1)∪(A 2× A2)∪(A 3× A3)∪...∪(A m× Am)。
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
证,若Ａ已进行了划分,则构造二元关系Ｒ 。
(1)?ａ ∈ Ａ,使 （ ａ,ａ ） ∈ Ｒ,
(2)分别对每一等价类内所有两个不同元素ａ,ｂ,
（ ａ,ｂ ） ∈ Ｒ,使 （ ｂ,ａ ） ∈ Ｒ,
显然,Ｒ是自反的,对称的,而且也是传递的,
因为若 （ ａ,ｂ ） ∈ Ｒ,（ ｂ,ｃ ） ∈ Ｒ,则ａ,
ｂ,ｃ均在同一等价类内,
故 （ ａ,ｃ ） ∈ Ｒ 。
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类解,R1＝ {1,2,3}× {1,2,3}∪{4,5} × {4,5}∪{6} × {6}
＝ {<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,
<2,3>,<3,2>,<4,4>,<5,5>,<4,5>,<5,4>,<6,6>}；
R2＝ {1,2,3}× {1,2,3}∪{4,5,6} × {4,5,6}
＝ {<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,
<3,1>,<2,3>,<3,2>,<4,4>,<5,5>,<6,6>,
<4,5>,<5,4>,<4,6>,<6,4>,<5,6>,<6,5>}。
例,设集合 A＝ 1,2,3,4,5,6}的两个划分如下：
П 1(A)＝ {{1,2,3},{4,5},{6}}； П 2(A)＝ {{1,2,3},{4,5,6}}.
求其相应的等价关系。
Guoyongfang.2006@yahoo.com.cn
等价关系与等价类证明,,?” 若 R是等价关系。
1)、显然 R是自反的。
2)、对任意 a,b,c∈A,若 <a,b>∈R,<a,c>∈R,则由 R是对称的，有 <b,a>∈R 并且 <a,c>∈R,由 R是传递的，所以,<b,c>∈R 。即 R是循环的关系。
1),2)知 R是自反的和循环的。
例,设 R是集合 A上的一个关系，对?a,b,c∈A,若 <a,b>
∈R 并且 <a,c>∈R,则有,<b,c>∈R,则 R称为 A上的循环关系。试证明 R是 A上的一个等价关系的充要条件是 R是循环关系和自反关系。
Guoyongfang.2006@yahoo.com.cn
“?” 若 R是自反的和循环的。
1),显然 R是 自反性 的；
2)、对任意 a,b∈ A,若 <a,b>∈ R,则由 R是自反的,有 <a,a>∈ R，
因 R是循环的，所以,<a,b>∈ R且 <a,a>∈ R? <b,a>∈ R，
即 R是对称的。
3)、对任意 a,b,c∈ A，若 <a,b>∈ R,<b,c>∈ R，则由 R对称的，有 <b,a>∈R 并且 <b,c>∈R ；由 R是循环的，所以
<b,a>∈R 且 <b,c>∈R?<a,c>∈R,即 R是传递的。
由 1),2),3)知 R是 A上的一个等价关系。■
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
定理 设 R1和 R2为非空集合 A上的等价关系，则
R1=R2当且仅当 A/ R1=A/ R2。
等价关系与等价类
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系一、相容关系定义 R是定义在集合 A上的关系，如果 R是 自反的、对称的,则称此关系 R为 A上的 相容关系 。
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系例如,设 A是由下列英文单词组成的集合 。
A={cat,teacher,cold,desk,knife,by}
定义关系：
r={<x,y>|x,y∈ A且 x和 y由相同的字母 }。 显然,r是一个相容关系 。
令 x1=cat,x2=teacher,x3=cold,x4=desk,x5=knife,x6=by.
R的关系图可由图表示 。
R的关系矩阵为由于相容关系是自反和对称的，因此其关系矩阵的对角线元素都是 1，且矩阵是对称的。
100000
011010
011110
001111
011111
000111
Mr
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系定义 设 r是集合 A上的相容关系,如 C∈ A,如果对于 C中任意两个元素 a1和 a2有 a1ra2,称 C是由相容关系 r产生的相容类 。
定义 设 r是集合 A上的相容关系,不能真包含在任何其他相容类中的相容类,称做最大相容类 。 记作 Cr。
在相容关系图中,最大完全多边形的顶点集合,就是最大相容类 。 所谓完全多边形,就是其每个顶点都与其他顶点连接的多边形 。 例如一个三角形是完全多边形,一个四边形加上两条对角线就是完全多边形 。
此外,在相容关系图中,一个孤立结点,以及不是完全多边形的两个结点的连线,也是最大相容类 。
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系例 设给定相容关系图如图 3-11,3,写出最大相容类 。
解：最大相容类为：
{a1,a2,a4,a6},{a3,a4,a6},{a4,a5},{a7}
Guoyongfang.2006@yahoo.com.cn
3－ 11相 T容关系定理 r是有限集 A上的相容关系,C是一个相容类,那么必存在一个最大相容类 Cr,使 CCr。
证明：设 A={a1,a2,···,an},构成相容类序列
,其中 C0=C,且 Ci+1=Ci∪ {aj},其中 j是满足 aj不属于 Ci而 aj与 Ci
中各元素都有相容关系的最小足标 。
由于 A的元素个数 |A|=n,所以至多经过 n-|C|步,就使这个过程终止,而此序列的最后一个相容类,就是所要找到的最大相容类 。
210 CCC
Guoyongfang.2006@yahoo.com.cn
3－ 11相容容关系定义 在集合 A上给定相容关系 r,其中最大相容类的集合称作集合 A的完全覆盖,记作 Cr(A)。
定理 给定集合 A的覆盖 {A1,A2,···,An},由他确定的关系 R= A1
× A1 ∪ A2 × A2 ∪ ···∪ An× An 是相容关系 。
证明,因为 A=,对于任意 x∈ A,必存在某个 j>0使得 x∈ Aj,所以 <x,x>∈ Aj× Aj,即 <x,x>∈ R,因此 R是自反的 。
其次,若有任意 x,y∈ A且 <x,y>∈ R,则必存在某个 h>0使 <x,
y>∈ Ah× Ah,故必有 <y,x>∈ Ah× Ah,即 <y,x>∈ R,所以 R是对称的 。
因此证得 R是 A上的相容关系 。
定理 集合 A上相容关系 r与完全覆盖 Cr(A)存在一一对应 。
ni AiA 1
Guoyongfang.2006@yahoo.com.cn
3-12序关系定义 偏 序关系
Ｒ是Ａ上的二元关系,如果Ｒ满足：
(1) 自反的
(2） 反对称的
(3) 传递的则称Ｒ是Ａ上 偏序关系 /半序关系 /部分序关系
(记为,≤,)
定义 集合 A连同 A上的偏序关系Ｒ一起 称为一个偏序 集,记为 <A,R > 。
Guoyongfang.2006@yahoo.com.cn
例,A={1,2,3,4,5,6,7,8,9}，
A上的二元关系
Ｒ 1＝ ｛ <ａ,ｂ >｜ ａ ≤ ｂ,ａ,ｂ ∈ A｝
Ｒ 2＝ ｛ <ａ,ｂ >｜ ａ |ｂ,ａ,ｂ ∈ A｝
Ｒ 1,Ｒ 2都是 A上的二元关系,
<A,Ｒ 1 >,<A,Ｒ 2>都是偏序集 。
序关系
Guoyongfang.2006@yahoo.com.cn
例,整数集 I上的二元关系
Ｒ 1＝ ｛ <ａ,ｂ > ｜ ａ ≤ ｂ,ａ,ｂ ∈ I｝
Ｒ 2＝ ｛ <ａ,ｂ > ｜ ａ |ｂ,ａ,ｂ ∈ I｝
<I,Ｒ 1 >,<I,Ｒ 2 >也都是偏序集 。
序关系
Guoyongfang.2006@yahoo.com.cn
例,A＝ ｛ ａ,ｂ,ｃ ｝
Ｒ 3＝ ｛ <ｓ 1,ｓ 2>｜ｓ 1?ｓ 2,ｓ 1,ｓ 2∈P （ A）｝
Ｒ 3是 P(A)上的二元关系,<P(A),Ｒ 3 >是偏序集 。
例,B是任意一个集合
Ｒ 3＝ ｛ <ｓ 1,ｓ 2> ｜ｓ 1?ｓ 2,ｓ 1,ｓ 2∈P （ B）｝
Ｒ 4是 B上的二元关系,<P（ B）,Ｒ 4>是偏序集 。
序关系
Guoyongfang.2006@yahoo.com.cn
例,集合 A的幂集 P(A)上定义的,?” 是 偏 序关系,
<P(A),?>是偏序集 。
例,实数集合 R上定义的,≤,是偏序关系,<R,≤> 是偏序集。
序关系例,大于零的 自然数集合 N＋ 上定义的,整除,关系,|”
也是一个偏序关系,<N＋,|>是偏序集。
Guoyongfang.2006@yahoo.com.cn
几点说明：
（ 1） 同一集合上的两个不同的偏序关系,构成两个不同的偏序集 。
如：Ｒ 1和Ｒ 2都定义在Ａ＝ {１,２,３,４,５,６,７,８,９ }上,
但 <Ａ,Ｒ 1>与 <Ａ,Ｒ 2>显然不是一样的偏序集 。
（ 2） 不同集合上分别相同定义的偏序关系,其偏序关系不同,同样构成两个不同的偏序集 。
如,<A,Ｒ 3>与 <B,Ｒ 3>是 两个不同的 偏序 集 。
序关系
Guoyongfang.2006@yahoo.com.cn
哈斯图二,哈斯图定义 设 <A,? >是偏序集,x,y?A,若有 x? y? y? x,则称 x与 y是可比的 。 若 x与 y可比,且 x? y,但不存在 z?A，
使得 x? z? z? y,则称 y盖住 x。
根据上述定义,可以简化偏序关系的关系图得到哈斯图,具体画法如下：
Guoyongfang.2006@yahoo.com.cn
序关系
用小圆圈表示 A中的元素，省掉关系图中所有的环。
(因自反性 )
对任意 x,y∈A(x≠y),若 x≤y,则将 x画在 y的下方，
可省掉关系图中所有边的箭头。 (因反对称性 )
对任意 x,y∈A(x≠y),若 x≤y,且 x与 y之间不存在
z∈A,使得 x≤z,z≤y,则 x与 y之间用一条线相连之，
否则无线相连。 (因传递性 )
Guoyongfang.2006@yahoo.com.cn
序关系例,设 A＝ {2,3,6,12,24,36},“≤,是 A上的整除关系，
画出其一般的关系图和哈斯图。
关系图 哈斯图
Guoyongfang.2006@yahoo.com.cn
序关系例,设集合 A＝ {a},B＝ {a,b},C＝ {a,b,c},D＝ {a,b,c,d}。
分别画出集合 A,B,C,D之幂集 P(A),P(B),P(C),P(D)上定义的,?” 的哈斯图。
Guoyongfang.2006@yahoo.com.cn
三,全序关系定义 设 <Ａ,≤>是偏序集,Ｂ?Ａ,若Ｂ中每两个元素都有关系,则称Ｂ为 链 。 若Ｂ中每两个元素都无关,则称Ｂ为 反链 。
定义 设 <A,? >为偏序集,若 A是一个 链,则称?为 A上的全序关系或线序关系,此时称 <A,? >为全序集 。 也就是集合 A中任意的两个元素都有关系 。
全序关系
Guoyongfang.2006@yahoo.com.cn
序关系例,1) 集合 A＝ {a,b,c}上定义的关系
R＝ {<a,a>,<b,b>,<c,c>,<a,b>,<b,c>,<a,c>}
则是一个全序关系。
2) 实数集合 R上定义的,≤,是全序关系。 <R,≤> 是全序集。
3) 集合 A＝ {a}的幂集 P(A)上定义的,?” 是全序关系。
<P(A),?>是全序集。
4) 任意基数 (元素个数 )大于２的集合 A的幂集 P(A)上定义的
,?” 则不是全序关系，仅是偏序关系。 <P(A),?>不是全序集。
Guoyongfang.2006@yahoo.com.cn
偏序集与特殊元素四、偏序集与特殊元素定义 <A,≤> 是偏序集,B是 A的任何一个子集。
若存在元素 b∈B,使得对任意 x∈B,都有 x≤b,则称 b为 B的最大元素 。
若存在元素 b∈B,使得对任意 x∈B,都有 b≤x,则称 b为 B的最小元素 。
若存在元素 b∈B,使得对任意 x∈B,满足 b≤x?x＝ b,则称 b为 B的极大元素 。
若存在元素 b∈B,使得对任意 x∈B,满足 x≤b?x＝ b,则称 b为 B的极小元素 。
Guoyongfang.2006@yahoo.com.cn
序关系续：
若存在元素 a∈A,使得对任意 x∈B,都有 x≤a,则称 a为 B的上界 。
若存在元素 a∈A,使得对任意 x∈B,都有 a≤x,则称 a为 B的下界 。
若元素 a’∈ A是 B的上界,元素 a∈A 是 B的任何一个上界,若均有 a’
≤ a,则称 a’为 B的上确界 。
若元素 a’∈A 是 B的小界,元素 a∈A 是 B的任何一个小界,若均有 a≤a ’,
则称 a为 B的下确界。
Guoyongfang.2006@yahoo.com.cn
序关系例,设集合 A＝ {1,2,3,4,5,6,7,8},D是 A上的整除关系，则 <A，
D>是偏序集，考虑 A的子集,B1＝ {1,2,3,6},B2＝ {2,3,5,7}，
B3＝ A。求出 B1,B2,B3的最大 (小 )元、极大 (小 )元、上 (下 )界、
上 (下 )确界。
集合 最大元 最小元 极大元 极小元上界 下界上确界 下确界
B1 6 1 6 1 6 1 6 1
B2 无 无 2,3,5,7 2,3,5,7 无 1 无 1
B3 无 1 5,6,7,8 1 无 1 无 1
Guoyongfang.2006@yahoo.com.cn
序关系例,设集合 A＝ {a,b,c}，考虑 P(A)上的关系,?”,则
<P(A),?>是偏序集。求 P(A)的子集,B1＝ {{a,b},{b,c},
{b},{c},Φ},B2＝ {{a},{c},{a,c}},B3＝ (A)的最大 (小 )元、
极大 (小 )元、上 (下 )界、上 (下 )确界。
集合最大元 最小元 极大元极小元上界下界上确界 下确界
B1 无 Φ {a,b},{b,c} Φ {a,b,c} Φ {a,b,c} Φ
B2 {a,c} 无 {a,c} {a},{c} {a,c},
{a,b,c}
Φ {a,c} Φ
B3 {a,b,c} Φ {a,b,c} Φ 无 Φ {a,b,c} Φ
Guoyongfang.2006@yahoo.com.cn
序关系例,设 A＝ {x1,x2,x3,x4,x5},A上定义偏序集 <A,≤> 的哈斯图如下，求 B＝
{x3,x4,x5}的最大 (小 )元、极大 (小 )元、上 (下 )界、上 (下 )确界。
解,最大元：无；
极大元,x3,x4；
x1,x2；
x5；
x5；
x5；
x5。
Guoyongfang.2006@yahoo.com.cn
一些结论,设 <A,≤> 是一偏序集,B是 A的子集。则：
若 b∈B 是 B的最大元?b是 B的极大元、上界、上确界；
若 b∈B 是 B的最小元?b是 B的极小元、下界、下确界；
若 a∈A 是 B的上确界，且 a∈B?a是 B的最大元；
若 a∈A 是 B的下确界，且 a∈B?a是 B的最小元；
若,≤,是一个全序关系，则 b∈B 是 B的最大元?b∈B 是 B的极大元；
若,≤,是一个全序关系，则 b∈B 是 B的最小元?b∈B 是 B的极小元。
若 b∈B 是 B的极大元，且 b是唯一的?b是 B的最大元。
若 b∈B 是 B的极小元，且 b是唯一的?b是 B的最小元。
序关系
Guoyongfang.2006@yahoo.com.cn
五、良序关系定义 设 <A,≤> 是一偏序集，若 A的任何一个非空子集都有最小元素，则,≤,称为良序关系,<A,≤> 是良序集。
良序关系例,设在集合 A＝ {a,b,c}上定义的偏序关系,≤,
的哈斯图如右图所示，可知此,≤,是良序关系。例,<N,≤>,<[0,1],≤> 都是良序集，
<I,≤>,<(0,1),≤> 则不是良序集。
Guoyongfang.2006@yahoo.com.cn
定理 （ 1） 良序集是全序集
（ 2） 全序集未必是良序的,
例：实数全体,任两个实数都是可比较的,但子集 ｛ 1/n｝ 的最小元找不到 。
（ 3） 有限的全序集是良序集 。
序关系
