离散数学第三章 集合与关系(8~12) |
您所在的位置:网站首页 › 数学中dom什么意思 › 离散数学第三章 集合与关系(8~12) |
第三章(8~12)
3-8关系的闭包运算
定义:设R是X上的二元关系,如果有另一个关系R’满足: 1.R‘是自反的(对称的,可传递的) 2.R’⊇R 3.对于任何自反的(对称的,可传递的)关系R‘’,如果有R‘’⊇R,就有R‘’⊇R‘。 则称关系R’为R的自反(对称,传递)闭包。记作r(R ),(s(R ),t(R )) tips:自反(对称,传递)闭包应是包含R的最小自反(对称,传递)关系 定理1:设R是X上的二元关系,那么 a) R是自反的,当且仅当r(R )=R b) R是对称的,当且仅当s(R )=R c) R是传递的,当且仅当t(R )=R 定理2:设R是集合X上的二元关系,则 eg1. 定理3:设X是含有n个元素的集合,R是X上的二元关系,则存在一个正整数k≤n,使得 定理4:rs(R )=sr(R ) rt(R )=tr(R ) ts(R )⊇st(R ) 3-9 集合的划分和覆盖定义:若把一个集合A分成若干个叫做分块的非空子集,使得A中每个元素至少属于一个分块,那么这些分块的全体构成的集合叫做A的一个覆盖。 如果A中每个元素属于且仅属于一个分块,那么这些分块的全体构成的集合叫做A的一个划分(或分划)。 符号定义: eg.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}} (既不是划分也不是覆盖) 最小划分:由这个集合的全部元素组成的一个分块的集合 (eg中的G) 最大划分:由每个元素构成一个单元素分块的集合(eg中的E) 交叉划分:若{A₁,A₂,…,A(r )}与{B₁,B₂,…,B(s)}是同一集合A的两种划分,则其中所有A(i)∩B(j)≠∅组成的集合,称为是原来两种划分的交叉划分 X:所有生物 P:所有植物,A:所有动物 则X可构成{P,A} E:史前生物,F:史后生物 则X也可构成{E,F} 其交叉划分为:Q={P∩E,P∩F,A∩E,A∩F} P∩E:史前植物,P∩F:史后植物,A∩E:史前动物,A∩F:史后动物 定理:设{A₁,A₂,…,A(r )}与{B₁,B₂,…,B(s)}是同一集合X的两种划分,则其交叉划分亦是原集合的一种划分 加细定义:给定X的任意两个划分{A₁,A₂,…,A(r )}与{B₁,B₂,…,B(s)},若对于每一个A(j)均有B(k)使A(j)⊆B(k),则{A₁,A₂,…,A(r )}称为是{B₁,B₂,…,B(s)}的加细 定理:任何两种划分的交叉划分,都是原来各划分的一种加细 3-10等价关系与等价类 等价关系定义:设R为定义在集合A上的一个关系,若R是自反的,对称的和传递的,则R称为等价关系。 **eg1.**集合T={1,2,3,4},R={,,,,,,< 3,2>,< 3,3>} 则R是T上的等价关系 同余模k关系:x≡y(modk),x、y被k除有相同的余数 eg2.设***I*为整数集,R={|x≡y(modk)},证明R是等价关系 证明:自反性:∵a-a=k·0, ∴ ∈R 对称性:∵a≡b(modk),a-b=kt,b-a=-kt,∴b≡a(modk) 传递性:若a≡b(modk),b≡c(modk), 则a-b=kt,b-c=ks,a-c=a-b+b-c=k(t+s),∴a≡c(modk) 因此R是等价关系 等价类定义:设R为集合A上的等价关系,对任何a∈A,集合 如在eg1中,T的各个元素等价类为: 定理1:设给定集合A上的等价关系R,对于a,b∈A有 定理2:集合A上的等价关系R,其等价类集合 定理3:集合A上的等价关系R,决定了A的一个划分,该划分就是商集A/R 定理4:集合A的一个划分确定A的元素间的一个等价关系 定理5:设R₁和R₂为非空集合A上的等价关系,则R₁=R₂当且仅当A/R₁=A/R₂ 3-12序关系 偏序关系定义:设A是一个集合,如果A上的一个关系R,满足自反性,反对称性和传递性,则称R是A上的一个偏序关系,并把它记为**“≼”。序偶称作偏序集** 盖住定义:在偏序集合中,如果x,y∈A,x≼y,x≠y且没有其他元素z满足x≼z,z≼y,则称元素y盖住元素x,并且记**COV A={|x,y∈A;y盖住x} eg.设A是正整数m=12的因子的集合,并设≼为整除关系,求COV A 解:m=12其因子集合为A={1,2,3,4,6,12} “≼”={,,,,,,,,< 3,6>,< 3,12>,,,,,< 3,3>,,,} COV A={,,,< 3,6>,,} 偏序集合图(哈斯图)定义:对于给定偏序集,它的盖住关系是唯一的,所以可用盖住的性质画出偏序集合图,或称哈斯图,其作图规则为: A中的元素用小圆圈表示如果x≼y且x≠y,则将代表y的小圆圈画在代表x的小圆圈之上如果∈COV A,则在x与y之间用直线连接上例中的哈斯图为: 定义:设是一个偏序集合,在A的一个子集中,如果每两个元素都是有关系的,则称这个子集为链。 在A的一个子集中,如果每两个元素都是无关的,则称这个子集为反链。 tips:若A的子集只有单个元素,则这个子集既是链又是反链 定义:在偏序集中,如果A是一个链,则称为全序集合或称线序集合,在这种情况下,二元关系≼称为全序关系或称线序关系 全序集就是对任意x,y∈A,或者有x≼y或者有y≼x成立。 例如“≤”关系,对任意i,j∈N,必有:(i≤j)或(j≤i)成立,则"≤"是全序关系 极大/小元定义:设是一个偏序集合,且B是A的子集,对于B中的一个元素b,如果B中没有任何元素x,满足b≠x且b≼x,则称b为B的极大元。同理,对于b∈B,如果B中没有任何元素x,满足b≠x且x≼b,则称b为B的极小元。 tips: 极大元和极小元不是唯一的 当B=A时,偏序集的极大元即是哈斯图中最顶层的元素,其极小元是哈斯图中最底层的元素,不同的极小元素或不同的极大元素之间是无关的 最大/小元定义:令是一个偏序集,且B是A的子集,若有某个元素b∈B,对于B中每一个元素x有x≼b,则称b为的最大元。同理,若有某个元素b∈B,对每一个x∈B有b≼x,则称b为的最小元。 性质: 令为偏序集且B⊆A,若B有最大(最小)元,则必是唯一的 在最大(最小)元的定义中,当子集B与A相等时,B的最大(最小)元就是偏序集的最大(最小)元 上/下界定义:设为一偏序集,对于B⊆A,如有a∈A,且对B的任意元素x,都满足x≼a,则称a为子集B的上界。 同样地,对于B的任意元素x,都满足a≼x,则称a为B的下界。 tips:上界和下界不是唯一的
定义:设为偏序集且B⊆A为一子集,a为B的任一上界,若对B的所有上界y均有a≼y,则称a为B的最小上界(上确界),记作LUB B。 同样,若b为B的任一下界,若对B的所有下界z,均有z≼b。则称b为B的最大下界(下确界),记作GLB B。 定义:任一偏序集合,假如它的每一个非空子集存在最小元素,这种偏序集合称为良序的。 eg. I={1,2,…,n}及N={1,2,3,…},对于小于等于关系来说是良序集合,即,是良序集合 性质: 每一个良序集合,一定是全序集合每一个有限的全序集合,一定是良序集合(对无限的全序集合不一定成立) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |