第三章 集合与关系.ppt

§3.7关系的闭包运算[定理]设X是一集合，R是X中的二元关系，则有：（1）r(S(R))=S(r(R));（2）r(t(R))=t(r(R));（3）t(S(R))S(t(R))。第61页，共117页，星期日，2025年，2月5日§3.7关系的闭包运算证明：（1）r(S(R))常用下列符号表示一些闭包：“R加”：，传递闭包，“R星”：，自反可传递闭包，第62页，共117页，星期日，2025年，2月5日§3.7关系的闭包运算例：设X={a,b,c},R={a,bc,c}（1）rS(R)=r{a,bb,ac,c}={a,bb,ac,ca,ab,b}Sr(R)=s{a,bc,ca,ab,b}={a,bb,ac,ca,ab,b}（2）rt(R)=r{a,bc,c}={a,bc,ca,ab,b}tr(R)=t{a,bc,ca,ab,b}={a,bc,ca,ab,b}（3）tS(R)=t{a,bc,cb,a}={a,bc,cb,aa,ab,b}St(R)=S{a,bc,c}={a,bc,cb,a}∴t(S(R))St(R)第63页，共117页，星期日，2025年，2月5日§3.8集合的划分和覆盖[定义1]给定一非空集合A，又设若（1）（2）则称S为A的覆盖。例1：S={a,b,c}，A={{a,b},{b,c}}，B={{a},{a,b},{c}}，C={{a},{b},{c}}，D={{a},{b},{a,c}}均为S的覆盖。第64页，共117页，星期日，2025年，2月5日§3.8集合的划分和覆盖[定义1]给定一非空集合A，又设若（1）（2）则称S为A的覆盖。例2：四个半圆覆盖一正方形。第65页，共117页，星期日，2025年，2月5日§3.8集合的划分和覆盖[定义2]给定一非空集合S，设非空集合如果有：或（i,j=1,2…,m）则称集合A是集合S的一个划分。第66页，共117页，星期日，2025年，2月5日§3.8集合的划分和覆盖讨论定义：（1）划分和覆盖主要差别在第（2）条；（2）划分A中的元素，称为划分的类，在定义中均是A中的一个类，类的个数称为划分的秩；（3）若A为有限集合，则A的秩是有限的，为|A|，若A为无限集合，则划分的秩是无限的；（4）集合的划分必定是一个覆盖，而覆盖不一定是划分；（5）集合S上的秩最大的划分称最大划分，最小的称最小划分。第67页，共117页，星期日，2025年，2月5日§3.8集合的划分和覆盖例3：设S={a,b,c}，下列均为S的一个划分：=2（秩）；最大划分，秩为3；最小划分，秩为1。=2（秩）；=2（秩）；第68页，共117页，星期日，2025年，2月5日§3.8集合的划分和覆盖例4：四个直角三角形组成了正方形的一个划分秩=4第69页，共117页，星期日，2025年，2月5日§3.8集合的划分和覆盖[定义]设A和A’是非空集合S的二种划分，并可表示成：若A’的每一个类都是A的某一个类的子集，则称划分A’是划分A的加细，或讲A’加细了A，若A’加细了A且则称A’是A的真加细。讨论定义：A’加细了A，一定有|A’|≥|A|（秩），若|A’||A|，则一定为真加细。第70页，共117页，星期日，2025年，2月5日§3.8集合的划分和覆盖例：S={a,b,c,d}，S的划分：A={{a,b},{c,d}},A’={{a}{b}{c,d}}，则A’是A的真加细A’’={{a}{b}{c}{d}},则A’’是A的真加细第71页，共117页，星期日，2025年，2月5日§3.9等价关系与等价类[定义3-10.1]设R为定义在集合A上的一个关系，若R是自反的、对称的和传递的，则R称为等价关系。如果R是一个等价关系，a，b∈R称a等价于b，记作a~b。（1）在一群人的集合上年龄相等的关系是等价关系，而朋友关系不一定是等价关系，因为它可能不是传递的。（2）命题公式间的逻辑等值关系是等价关系。（3）集合上的恒等关系和全域关系都是等价关系。（4）在同一平面上直线之间的平行关系，三角形之间