离散数学-集合论_第1页
离散数学-集合论_第2页
离散数学-集合论_第3页
离散数学-集合论_第4页
离散数学-集合论_第5页
已阅读5页,还剩101页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2023/10/111离散数学计算机学院软件与理论教研室(313)DiscreteMathematicsEmail:cslq@

Tel:4994019-8082023/10/112第二部分集合论Set,RelationandMapping2023/10/113第三章集合、关系与映射关系即二元关系,它是集合直乘积的子集映射是特殊的二元关系19世纪末著名德国数学家康托(G.cantor)集合已经发展成为数学及其他各学科不可缺少的描述工具

成为数学中最为基本的概念集合论分为两种体系朴素集合论体系(康托集合论体系).

康托从抽象原则出发

概括出:满足某性质的个体放在一起组成集合

隐含矛盾,即罗素(Russell)悖论.

公理集合论体系(属于数理逻辑范畴)2023/10/1143.1集合及其运算1.集合及其表示法用大写英文字母A,B,C,…表示集合并用x∈A表示x是集合A中的元素,读作“x属于A”用xA表示x不是A中的元素,读作“x不属于A”.一般,集合有两种表示法:列举法和描述元素性质法列举法

A={a,b,c,d,e};B={书,笔记本,铅笔,课桌,黑板};C={0,1,-3,6};D={北京,天坛,故宫,地球,宇宙}.描述元素性质法

Σ={x|x是英文字母};Z={x|x是整数};2023/10/115集合及其表示法需要注意以下几点:集合中的元素各不相同如{1,2,3,4}与{1,1,2,3,4,4}是相同的集合都是含元素1,2,3,4的集合集合中的元素不规定次序如:{1,2,3,4}={4,2,3,1}.有些集合的两种表示法能互相转换,有些则不能如:{x|x是英文字母}={a,b,c,d,e,f,g,…,x,y,z};{x|x是非负偶数}={0,2,4,6,8,10,…,2n,…};{x|x是实数}不能转换为列举法表示.2023/10/116集合及其表示法一些常用集合的表示法:N={x|x是自然数}={0,1,2,…,n,…}

Z={x|x为整数}={…,-3,-2,-1,0,1,2,3,…}Z+={x|x∈Z∧x>0}={1,2,3,…,n,…}Q={x|x是有理数}R={x|x为实数}

还有:P表示素数集合O表示奇数集合E表示偶数集合2023/10/117集合间的包含与相等2.定义3.1.1.设A,B为集合,若B中的元素都是A中的元素,则称B是A的子集,记作B

A,称A包含B,或B包含于A,并以BA表示B不是A的子集.即B

A

∀x(x∈B→x∈A)

B

A

x(x∈B∧x

A).定义3.1.2.设A,B为集合,若集合A

B且A≠B,则称A为B的真子集,记作A

B.即A

B

∀x(x∈A→x∈B)∧

x(x∈B∧x

A).例如:若A={1,2,4},B={1,2,3,4,5},则A

B,而且A

B.对任意集合A有:A

A(自反性)对任意集合A,B,C,若A

B且B

C,则A

C(传递性)

2023/10/118空集与全集定义3.1.3.设A,B为集合,若A

B且B

A,则称A与B相等,记作A=B.定义3.1.4.称不拥有任何元素的集合为空集,记作.空集是任意集合的子集合,是任意非空集合的真子集合

和{}的关系是?空集是任意集合的子集,可以形象地说:

是“最小”的集合.但没有最大的集合.在讨论某些具体问题时,往往使用一个在相对的意义下是“最大”的集合”.

2023/10/119空集与全集定义3.1.5.如果限定所讨论的集合都是某一集合E的子集,则称E为全集全集是一个相对的概念,不同的实际问题可以定义不同的全集.

例如当被讨论的集合仅仅是{0,2,4},{6},{6,8}时,全集可设为{0,2,4,6,8}或{x|x是10以内的自然数}等2023/10/1110集合的幂集3.定义3.1.6.

设A为一个集合,称由A的所有子集组成的集合为A的幂集,记作P(A),即P(A)={X|X

A}.如:设A={1,2,3}则P(A)={,{1},{2},{3},{1,2},1,3},{2,3},A}.若|A|=n,则P(A)的元素个数|P(A)|=2n.元素个数有限的集合称有穷集,对其子集有一种编码方法:设A={a1,a2,a3}则A2=A010={a2},A5=A101={a1,a3}.2023/10/1111集合的运算

4.定义3.1.7.

设A,B为两个集合.

①

称由A与B的公共元素组成的集合为A与B的交集,记作A∩B即A∩B={x|xA∧xB}②

称由A与B的全体元素组成的集合为A与B的并集,记作A∪B即A∪B={x|xA∨xB}③

称属于A,但不属于B的元素组成的集合为A与B的相对补集

记为A-B,即A-B={x|xA∧xB}④

称属于A而不属于B,或属于B而不属于A的元素组成的集合为A与B的对称差集,记为A⊕B

即A⊕B={x|(xA∧xB)∨(xB∧xA)}⑤设E为全集,A

E,称E-A为A的绝对补集,记作~A即~A={x|xA}.2023/10/1112集合的运算例3.1.1

设A={a,b,c,d,e}B={a,c,e,g}E={a,b,c,d,e,f,g,h}

则:A∪B={a,b,c,d,e,g}A∩B={a,c,e}A-B={b,d}B-A={g}A⊕B={b,d,g}=(A-B)∪(B-A)=(A∪B)-(A∩B)~A={f,g,h}~B={b,d,f,h}.2023/10/1113集合的运算集合运算的Venn图表示:2023/10/1114基本恒等式5.集合运算的基本恒等式及其应用定理3.1.1设A,B,C是任意集合,E为全集,则有如下恒等式:①幂等律A∪A=A;A∩A=A.②交换律A∪B=B∪A;A∩B=B∩A.③结合律(A∪B)∪C=A∪(B∪C);(A∩B)∩C=A∩(B∩C).④分配律A∪(B∩C)=(A∪B)∩(A∪C);A∩(B∪C)=(A∩B)∪(A∩C).⑤德摩根律绝对形式~(A∪B)=~A∩~B;~(A∩B)=~A∪~B.

相对形式A-(B∪C)=(A-B)∩(A-C);A-(B∩C)=(A-B)∪(A-C).2023/10/1115基本恒等式⑥吸收律A∪(A∩B)=A;A∩(A∪B)=A.

⑦零律A∪E=E;A∩φ=φ.⑧同一律A∪φ=A;A∩E=A.⑨排中律A∪~A=E.⑩矛盾律A∩~A=φ.⑾余补律~φ=E;~E=φ.⑿双重否定律~(~A)=A.⒀补交转换律A-B=A∩~B.2023/10/1116基本恒等式关于对称差运算有以下恒等式:①交换律A⊕B=B⊕A

②结合律A⊕(B⊕C)=(A⊕B)⊕C.③∩对⊕满足分配律A∩(B⊕C)=(A∩B)⊕(A∩C).④A⊕φ=A;A⊕E=~A.⑤A⊕A=φ;A⊕~A=E.证明集合等式或包含式主要有以下两种方法:①

用集合的并、交、补、对称差等定义,通过逻辑等值演算证明新的等式或包含式②

由已知的集合等式或包含式,通过集合演算证明新的集合等式或包含式2023/10/1117集合恒等式的应用例3.1.3证明:对任意集合A,B有A∪(A∩B)=A.证明:①∀x.x∈A∪(A∩B)

x∈A∨(x∈A∧x∈B)

x∈A例3.1.4证明:

对任意集合A,B有A∩(A∪B)=A.证明:②

A∩(A∪B)=(A∪φ)∩(A∪B)=A∪(φ∩B)=A∪φ=A(前式使用了并、交运算定义,后式运用了逻辑演算的吸收律)A=A∪φ=A∪(φ∩B)=(A∪φ)∩(A∪B)=A∩(A∪B).2023/10/1118续例3.1.5

若A⊕B=A⊕C,则B=C.证明:

采用方法②

A⊕B=A⊕C

A⊕(A⊕B)=A⊕(A⊕C)

(A⊕A)⊕B=(A⊕A)⊕C

φ⊕B=φ⊕C

B=C.按定义若A

B且B

A则B=C证明,并不容易2023/10/1119续例3.1.6

证明:A∩(B⊕C)=(A∩B)⊕(A∩C).证明:(A∩B)⊕(A∩C)=((A∩B)∩~(A∩C))∪

((A∩C)∩~(A∩B))

=((A∩B)∩(~A∪~C))∪((A∩C)∩(~A∪~B))=(A∩B∩~C)∪(A∩C∩~B)=A∩((B-C)∪(C-B))=A∩(B⊕C)2023/10/1120续∩对⊕满足分配律,∪对⊕也满足分配律吗?即是否对任意集合A,B,C有A∪(B⊕C)=(A∪B)⊕(A∪C).设E={a,b,c,d,e,f},A={a,b,c}B={b,c,d}C={c,d,e}

A∪(B⊕C)={a,b,c}∪{b,e}={a,b,c,e}(A∪B)⊕(A∪C)={a,b,c,d}⊕{a,b,c,d,e}={e}.

∪对⊕不满足分配律2023/10/1121续(A∪B)⊕(A∪C)=((A∪B)∩~A∩~C)∪((A∪C)∩~A∩~B)=(B∩~A∩~C)∪(C∩~A∩~B)

=~A∩((B-C)∪(C-B))=~A∩(B⊕C).(A∪B)⊕(A∪C)=~A∩(B⊕C)

=(B⊕C)-A2023/10/1122有限集合并集的元素计数定理3.1.2.设A1,A2,…,An是n个有穷集合,则它们并集的元素个数可由包含排斥公式计算:证明:设A,B是两个有限集合,则结论显然成立,即有:设对n=k结论成立,即有:

当n=k+1时,从由前两式代入整理即得要证结果

2023/10/1123续例3.1.7

设A,B,C是三家计算机公司,它们的固定客户分别有12,16和20家。已知A与B,B与C,C与A的公共固定客户分别为6,8和7家,三家的公共固定客户有5家,求三家计算机公司拥有的固定客户家数。解:以A,B,C分别表记A,B,C三家计算机公司的客户集合,知|A|=12,|B|=16,|C|=20,|A∩B|=6,|A∩C|=7,|B∩C|=8,|A∩B∩C|=5.

求三家计算机公司拥有的固定客户家数,即要计算|A∪B∪C|的元素个数.由有限集合并集元素的计数公式包含排斥公式:|A∪B∪C|=(|A|+|B|+|C|)-(|A∩B|+|A∩C|+|B∩C|)+|A∩B∩C|=(12+16+20)-(6+7+8)+5=32.2023/10/1124罗素悖论

在数理逻辑中,讨论过悖论,罗素悖论在集合论中,其表现形式是:

罗素悖论在以所有集合为个体的论域上定义集合S={X|X

X},即一切不是自身元素的集合的集合.问题是S∈S吗?若S∈S,由定义则S

S;若S

S,再由定义则S∈S.矛盾矛盾的本质在于康托的朴素集合论在刻画集合的方法上缺少限制,以为凡是一个性质就能概括一个集合

2023/10/11253.2关系

关系是离散数学中刻画元素之间相互联系的一个重要概念关系数据库模型最基本的关系是二元关系,即发生在两个个体之间的关系.竞赛中的胜负关系,如果每一场比赛都是在两个对手之间进行,不考虑平局,那么比赛x胜y就可以表示成〈x,y〉关系{〈a,b〉,〈c,b〉,〈c,a〉}记录了3场比赛的结果c是第一名,a是第二名,b是最后一名.该例是集合{a,b,c}上的一个二元关系2023/10/11263.2.1关系的定义及其表示有序对与笛卡尔积定义3.2.1.由两个元素,比如x和y,按照一定次序构成的二元组称为一个有序对,记作〈x,y〉.其中x是序对的第一元素,y是序对的第二元素.直角坐标系中点的坐标(1,-2),(0,5)有序对中,如果两个元素不相等,是不能交换次序的.(0,1)与(1,0)代表不同的有序对两个有序对〈x,y〉与〈u,v〉相等x=u且y=v.2023/10/1127续例3.2.1.设有序对〈x+y,3〉=〈3y-2,x+5〉

根据有序对相等的充要条件,解由第一、第二元素对应相等组成的二元一次方程组得:x=-2,y=0.定义3.2.2.

设A,B为集合,以A中元素作为第一元素,B中元素作为第二元素做有序对,所有这样的有序对构成的集合称为A与B的笛卡尔积,记作A×B.符号化表示为A×B={〈x,y〉|x∈A∧y∈B}.2023/10/1128续例3.2.2.设A={0,1},B={a,b}则A×B={〈0,a〉,〈0,b〉,〈1,a〉,<1,b〉}B×A={〈a,0〉,〈a,1〉,〈b,0〉,〈b,1〉}.有穷集A,B的笛卡尔积是有穷集,且|A×B|=|A|·|B|.笛卡尔积不适合交换律,即A×B≠B×A除非A=B,或者A,B中至少有一空集.对任意集合S,S×φ=φ×S=φ.笛卡尔积不适合结合律,即(A×B)×C≠A×(B×C)除非A,B,C中至少有一空集2023/10/1129关系的定义及其表示笛卡尔积运算对并和交运算适合分配律:n阶笛卡尔积:即n个集合依次连乘的笛卡尔积当这n个集合都为同一集合A时,称作A的n次笛卡尔幂.

A1×A2×…×An={〈x1,x2,…,xn〉|xi∈Ai,i=1,2,…,n}An={〈x1,x2,…,xn〉|xi∈A,i=1,2,…,n}.空间直角坐标系中全体点的集合就是3阶笛卡尔积,亦称A的3次笛卡尔幂,即R×R×R=R3.A×(B∪C)=(A×B)∪(A×C)A×(B∩C)=(A×B)∩(A×C)(A∪B)×C=(A×C)∪(B×C)(A∩B)×C=(A×C)∩(B×C)2023/10/1130续二元关系(关系)建立在二阶笛卡尔积的集合之上定义3.2.3.如果一个集合中的元素都是有序对或者这个集合是空集,则称这个集合是一个二元关系,记作R.序对〈x,y〉∈R简记为xRy,否则记作.例如R={〈a,b〉〈b,c〉}就可以记为aRb,bRc.显然aRc.例3.2.3.①R={〈x,y〉|x,y∈N,x+y≤1}={〈0,0〉,〈0,1〉,〈1,0〉}.②R={〈x,y〉|x,y∈R,x2+y2=1}平面单位圆.xRy2023/10/1131续例3.2.4.关系数据库中的一个实体模型.

表中包括了若干职工的记录每个记录是一个5元组,由5个字段构成,称为属性这些元组的集合构成了一个5元关系R={〈x1,x2,x3,x4,x5〉|xi是相应属性}.2023/10/1132续定义3.2.4.设A,B为集合,A×B的任何子集所定义的二元关系称为从A到B的二元关系

当A=B时则称为A上的二元关系.例3.2.5.A={a,b}B={1,2,3}

则R1={〈a,1〉}R2=A×BR3=φR3=φ,R4={〈a,a〉,〈b,b〉}

R5={〈a,a〉,〈a,b〉,〈b,a〉,〈b,b〉}=A2

都是从A到B的二元关系都是A上的二元关系.2023/10/1133续设|A|=m,|B|=n,则|A×B|=mnA×B的不同的子集有2mn个存在2mn个不同的从A到B的二元关系如果有限集A有|A|=3个元素,|A2|=|A×A|=9则A上不同的二元关系有29=512之多,即3元集{a,b,c}上不同的二元关系有512个2023/10/1134续定义3.2.5.设A为任意集合,则①φA=φ;②EA={〈x,y〉|∀x∈A∧∀y∈A}=A×A=A2;③IA={〈x,x〉|∀x∈A}.

分别称为A上的空关系,全域关系与恒等关系.例3.2.6.A={a,b}EA={〈a,a〉,〈a,b〉,〈b,a〉,〈b,b〉};IA={〈a,a〉,〈b,b〉}.设A为给定的集合,则①LA={〈x,y〉|x,y∈A∧x≤y∧AR,R为实数集};②DA={〈x,y〉|x,y∈A∧x整除y∧A

Z*};③R

={〈x,y〉|x,y∈A∧x

y∧A为集合族ρ(S)}.

被分别称为小于等于关系,整除关系和包含关系2023/10/1135二元关系的表示除了使用集合表达式定义二元关系以外,还可以使用关系矩阵和关系图来表示二元关系.关系矩阵通常用于表示从有穷集合A到有穷集合B的关系或者有穷集合A上的关系关系图只能表示有穷集合A上的关系定义3.2.6.设A={x1,x2,…,xn},B={y1,y2,…,ym},R是从A到B的关系,R的关系矩阵是n×m级布尔矩阵:

MR=(rij)n×m,其中rij=1xiRyj(〈xi,yj〉∈R)当R为A上的关系时,R的关系矩阵是n阶方阵

定义3.2.7.设A={x1,x2,…,xn},R的关系图是GR=〈A,R〉其中A为G的结点集,R为边集.∀xi,xj∈A,如果xiRxj,在图中就有一条从xi到xj的有向边2023/10/1136二元关系的表示例3.2.7.设A={a1,a2,a3,a4,a5}R={〈a1,a1〉,〈a2,a3〉,〈a2,a4〉,〈a3,a1〉,〈a3,a3〉,〈a4,a5〉,〈a5,a2〉,〈a5,a4〉}有穷集合定义的关系矩阵和关系图是唯一的MR=a2a5a4a3a1

GR:2023/10/11373.2.2关系的运算二元关系作为集合,可以进行并、交、相对补、对称差等运算还可定义其他一些常用的关系运算.定义3.2.8.设R为二元关系R的定义域、值域和域分别记作domR,ranR,fldR

domR={x|

y(〈x,y〉∈R)}ranR={y|

x(〈x,y〉∈R)}fldR=domR∪ranR.例3.2.8.设R={〈a,b〉,〈a,{b}〉,〈{a},b〉,〈c,{c}〉}则:domR

={a,c,{a}}ranR={b,{b},{c}}fldR={a,b,c,{a},{b},{c}}.2023/10/1138

续定义3.2.9.设R为二元关系,R的逆记作R-1,R-1={〈y,x〉|〈x,y〉∈R}.关系R的逆R-1就是R的每个有序对的两个元素交换以后得到的关系如果R是整数集Z上的小于关系,则R-1就是Z上的大于关系定义3.2.10.设R,S为二元关系,R与S的合成记作RS,RS={〈x,z〉|

y(〈x,y〉∈R∧〈y,z〉∈S)}2023/10/1139续例3.2.9.设R={〈a,b〉,〈a,{b}〉,〈{a},b〉,〈c,{c}〉}S={〈{b},a〉,〈b,{b}〉,〈{c},b〉,〈c,{c}〉}RS={〈a,{b}〉,〈a,a〉,〈{a},{b}〉,〈c,b〉}SR={〈{b},b〉,〈{b},{b}〉}

关系合成不适合交换律可以把关系看作是一种作用,如果〈x,y〉∈R,〈y,z〉∈S,那么x通过R的作用变到y,y接着通过S的作用又变到z.在R和S的合成作用下将x变到了z,因此〈x,z〉∈RS.这里的y起到一个中介或桥梁的作用.如果对于给定的关系R和S,不存在满足这种条件的中介y,那么RS=φ.2023/10/1140关系的合成运算第一种方法是关系图示法.关系图示法只适用于含有有限个有序对的关系给定含有n个有序对的关系R,R的图示由n条有向边构成.将domR中的元素画在左边,ranR的元素画在右边如果对于x∈domR,y∈ranR,〈x,y〉∈R,那么从代表x的结点到代表y的结点画一条有向边.所有的n条有向边就构成了R的图示为求R与S的合成,先画出R的图示,在这个图示的后面接上S的图示.如果ranR与domS含有共同的元素,那么这个元素只能是同一个结点,而不能画成两个结点.在这个图中,如果从domR的结点x,经过两步有向边到达ranS的结点z,那么〈x,z〉∈RS.2023/10/1141例3.2.9.设R={〈a,b〉,〈a,{b}〉,〈{a},b〉,〈c,{c}〉}S={〈{b},a〉,〈b,{b}〉,〈{c},b〉,〈c,{c}〉}

a

。

b

。

a

。{a}。

{b}

。b。

c。

{c}

。{b}

。

c

。{c}

。b

。

a

。

b。

{b}

。b。{b}。{c}

。{b}

。{c}。

c

。{c}

。

{a}。

c。2023/10/1142第二种方法:关系矩阵乘法.继续考虑例3.2.9.中的关系R和S,先将R和S表示成从一个集合到另一个集合上的关系.domR={a,{a},c},ranR={b,{b},{c}}domS={b,{b},{c},c},ranS={a,{b},b,{c}}ranR∪domS={b,{b},{c},c}将R看作从domR到ranR∪domS的关系将S看作从ranR∪domS到ranS的关系因此R。S就是从domR到ranS的关系.分别写出R和S的关系矩阵MR和MS,然后计算MR和MS的乘积需要注意的是在计算中元素进行相加时,采用逻辑加(即∨).所得结果即为关系R。S的关系矩阵例3.2.9.设R={〈a,b〉,〈a,{b}〉,〈{a},b〉,〈c,{c}〉}S={〈{b},a〉,〈b,{b}〉,〈{c},b〉,〈c,{c}〉}2023/10/1143

例3.2.9.设R={〈a,b〉,〈a,{b}〉,〈{a},b〉,〈c,{c}〉}S={〈{b},a〉,〈b,{b}〉,〈{c},b〉,〈c,{c}〉}R。S={〈a,{b}〉,〈a,a〉,〈{a},{b}〉,〈c,b〉}关系的合成运算2023/10/1144定理3.2.1.设R是任意的关系,则

①

(R-1)-1=R.

②domR-1=ranR,ranR-1=domR.证明:

①

任取〈x,y〉,由逆的定义有:〈x,y〉∈(R-1)-1

〈y,x〉∈R-1

〈x,y〉∈R,所以有(R-1)-1=R.

关系的合成运算②任取x,x∈domR-1

y(〈x,y〉∈R-1)

y(〈y,x〉∈R)x∈ranR.所以有domR-1=ranR另一式同理可证.关系的逆是相互的;求了逆运算以后,其定义域与值域互换2023/10/1145关系的运算定理3.2.2.设R,S,H是任意的关系,则关于合成运算成立:①(R°S)°H=R°(S°H).

②(R°S)-1=S-1°R-1.证明:①任取〈x,y〉,〈x,y〉∈(R°S)°H

t(〈x,t〉∈R°S∧〈t,y〉∈H)

t(

s(〈x,s〉∈R∧〈s,t〉∈S)∧〈t,y〉∈H)

t

s(〈x,s〉∈R∧〈s,t〉∈S∧〈t,y〉)

s(〈x,s〉∈R∧

t(〈s,t〉∈S∧〈t,y〉))

s(〈x,s〉∈R∧〈s,y〉∈S°H)

〈x,y〉∈R°(S°H)所以(R°S)°H=R°(S°H).

②任取〈x,y〉,〈x,y〉∈(R°S)-1

〈y,x〉∈R°S

t(〈y,t〉∈R∧〈t,x〉∈S)

t(〈x,t〉∈S-1∧〈t,y〉∈R-1)

〈x,y〉∈S-1

°R-1.所以(R°S)-1=S-1°R-1.合成运算满足结合律两个关系合成的逆等于它们逆的反次序合成2023/10/1146关系的运算定理3.2.3.设R是A上的二元关系,IA为恒等关系,则:R°IA=IA°R=R.证明:任取〈x,y〉,〈x,y〉∈R°IA

t(〈x,t〉∈R∧〈t,y〉∈IA)

t(〈x,t〉∈R∧〈t,y〉∈IA∧t=y)

〈x,y〉∈R.

从而有RIA=R.同理可证另一式.对于任何A上的关系R,恒等关系对于合成运算是没有贡献的.

恒等关系在关系合成中的作用,有似于实数普通乘法中的1.2023/10/1147关系的运算2.关系的幂运算关系的合成适合结合律可以定义关系的幂运算定义3.2.10.设R为A上的关系,n为自然数,则R的n次幂定义为:

①R0={〈x,x〉|x∈A}=IA.

②Rn+1=Rn°R.求解R的n次幂:与R的表示法有关如果关系用集合表达式给出,可以采用关系的图示的方法.为求R的n次幂,将R的图示复制n次,第i个图示从i层的A中的结点到达第i+1层的A中的结点.如果从第1层A中的结点x,经过n步长的有向路径,可以到达最后一层(第n+1层),那么〈x,y〉∈Rn.2023/10/1148关系的运算求解R的n次幂:与R的表示法有关如果R是用关系矩阵MR表示的,只需计算MR的n次方,就得到了Rn的关系矩阵.利用关系图求关系幂的方法比较方便.设R的关系图是GR,先在Rn的关系图中画出与R相同的n个点然后顺序考察原来关系图GR的每个结点x.如果结点x到y有一条长为n的有向通路,那么就在Rn的关系图中加上一条从x到y的有向边.在x=y时,得到的是由x引向x的有向环边.当所有的结点都检查完毕,就得到Rn的关系图.2023/10/1149解:①矩阵方法:例3.2.10.设A{a,b,c,d}R={〈a,b〉,〈b,a〉,〈b,c〉,〈c,d〉}分别用矩阵方法和关系图方法求R的各次幂.用关系矩阵的方法得到①R2=R4=R6=…;②R3=R5=R7=….②关系图方法:以下给出了R0与R的关系图,以及对R的2次幂,3次幂,…的构造结果.abcdR0abcdR1abcdR2bacdR32023/10/1150关系的运算定理3.2.4.设A为n元集,R是A上的关系,则存在自然数s和t,使得Rs=Rt.证明:R为A上的关系,|A|=n,A上的不同关系只有2n·n个,列出R的各次幂:R1,R2,…,Rn·n,…,这些幂中必有两个相等(鸽巢原理:n只以上鸽子飞回n个巢,必存在至少飞进2只鸽子的巢).即存在自然数s和t,使得Rs=Rt.定理3.2.4.说明有穷集上的关系R只有有限个不同的幂2023/10/1151关系的运算定理3.2.5.设R是A上的关系,m,n∈N,则关系R关于合成运算成立幂律:

①Rm

°Rn=Rm+n.②(Rm)n=Rmn.证明:设定m,对n做归纳.

①

对于任意给定的m∈N,施归纳于n.若n=0,则有Rm°R0=Rm

°IA=Rm=Rm+0.假设Rm°Rn=Rm+n,则有Rm

°Rn+1=Rm

°(Rn

°R)=(Rm

°Rn)°R=Rm+n+1.所以①式成立.

②

对于任意给定的m∈N,施归纳于n.若n=0,则有(Rm)0=IA=R0=Rm·0.假设(Rm)n=Rmn,则有(Rm)n+1=(Rm)n

°Rm=Rmn

°Rm=Rmn+m=Rm(n+1).所以②式成立本题的证明方法,也是数学归纳法。与一般的数学归纳法相比命题中有两个自然数。当命题存在多个自然数时,一般只选择其中一个自然数进行归纳,对其他的自然数只要任意给定即可2023/10/1152定理3.2.6.设R是A上的关系,若存在自然数s,t(s<t)使得Rs=Rt,则:

①

对任何的自然数k,有Rs+k=Rt+k;②对任何自然数k,i,有Rs+kp+i=Rs+i,其中p=t-s;

③令S={R0,R1,…,Rt-1},则对于任意的自然数q有Rq∈S.证明:①Rs+k=Rs°Rk=Rt

°Rk=Rt+k.

②

对k做归纳.

若k=0,则有Rs+0p+i=Rs+i.

假设Rs+kp+i=Rs+i,其中p=t-s,则Rs+(k+1)p+i=Rs+kp+i+P=Rs+kp+i

°RP=Rs+i

°RP=Rs+P+i

=Rs+t-s+i=Rt+i=Rs+i.由归纳法命题得证

③任取q∈N,若q<t,显然有Rq∈S.若q≥t,则存在自然数k和i,使得q=s+kp+i,其中0≤i≤p-1.于是Rq=Rs+kp+i=Rs+i而s+i≤s+p-1=s+(t-s)-1=t-1即Rs+i=Rt-1.

即Rq∈S.2023/10/1153关系的运算定理3.2.6.给出了R的不同幂的一个上界.如果Rs=Rt,那么R的不同的幂至多有t个.如果s和t是使得Rs=Rt成立的最小的自然数,那么R恰好有t个不同的幂.这里的t-s可以看作是幂变化的周期.

利用幂的周期性,在某些情况下可以将R的比较高的幂化简成比较低的幂.如例3.2.10.由于R2=R4,且2和4使之成立的最小的自然数,所以R的不同的幂有4个,即R0,R1,R2,R3.利用这个性质,可得R100=R98=R96=…=R4=R2.

2023/10/11543.2.3关系性质1.关系性质的定义和判别定义3.2.11.设R是集合A上的关系.

①如果∀x(x∈A→〈x,x〉∈R),则称R在A上自反.

②如果∀x(x∈A→〈x,x〉R),则称R在A上反自反.

恒等关系IA,全域关系EA以及小于等于关系LA都是给定集合A上的自反关系空关系φ,小于关系是A上的反自反关系.非空集合A上的关系R由是否具有自反性和反自反性划为3类:①R自反;②R反自反;③R既不自反也不反自反.2023/10/1155关系的性质例3.2.11.设A={a,b,c}R1={〈a,a〉,〈b,b〉,〈b,c〉,〈c,c〉}R2={〈a,b〉}R3={〈a,a〉,〈b,c〉}.对于任意集合A,最大的自反关系是EA,最小的自反关系是IA

最大的反自反关系是EA-IA,最小的反自反关系是空关系φ.

R是A上自反关系IARR是A上反自反关系R∩IA=φ.从关系矩阵看自反关系的主对角元素都是1反自反关系的主对角元素都是0

既不自反也不反自反的关系主对角元素有1也有0自反关系反自反关系既不自反也不反自反对应于关系图自反关系是每个结点都有环反自反关系是每个结点都无环既不自反也不反自反是有的结点有环,有的结点却无环bca(3)bca(2)bca(1)2023/10/1156续定义3.2.12.设R是集合A上的关系.①如果∀x∀y(x,y∈A∧〈x,y〉∈R→〈y,x〉∈R),则称R在A上对称.②如果∀x∀y(x,y∈A∧〈x,y〉∈R∧〈y,x〉∈R→x=y),则称R在A上反对称.空关系φ和恒等关系IA,全域关系EA都是A上对称关系空关系φ和恒等关系IA也是A上反对称关系.小于关系,整除关系,包含关系是相应集合上的反对称关系反对称性质的理解:任意x,y∈A,仅当x=y时,才有〈x,y〉∈R并且〈y,x〉∈R.等价定义:

若∀x∀y(x,y∈A∧〈x,y〉∈R∧x≠y→〈y,x〉R),则称R在A上反对称.2023/10/1157续非空集合A上的关系R根据是否具有对称性和反对称性可以划分为4类:

①R对称但不是反对称的

②R反对称但不是对称的

③R既是对称的也是反对称的④R既不是对称的也不是反对称的.例3.2.12.设A={a,b,c}R1={〈a,a〉,〈b,b〉,〈b,c〉,〈c,b〉}R2={〈a,b〉,〈c,a〉}R3={〈a,a〉,〈b,b〉}

R4={〈a,b〉,〈b,a〉,〈a,c〉}R1对称但不是反对称R2反对称但不对称R3既对称也反对称R4既不是对称的也不是反对称的对于任意集合A,最大的对称关系是EA最小的对称关系是空关系φ最小的反对称关系也是空关系φ.R是A上对称关系R=R-1R是A上反对称关系R∩R-1IA.bca(2)bca(1)2023/10/1158续从关系矩阵看对称关系R的关系矩阵MR是对称的,即MR与它的转置矩阵相等反对称关系R的关系矩阵MR中处于对称位置的所有元素((i,j)与(j,i))不能同为1既对称也反对称关系R的关系矩阵,只在主对角元素有1.从关系图看每两个不同的结点之间如有有向边,有向边则是成对反向的每两个不同的结点之间如有有向边,有向边则是单向的既不对称也不反对称关系的关系图中,两个不同的结点之间既有单向边,也有成对反向的边如果关系图中所有不同的结点对之间都无有向边,则这个对应的二元关系就既是对称的,也是反对称的2023/10/1159续定义3.2.13.设R是集合A上的关系若∀x∀y∀z(x,y,z∈A∧〈x,y〉∈R∧〈y,z〉∈R→〈x,z〉∈R)则称R是A上的传递关系.空关系φ、恒等关系IA、全域关系EA、小于等于关系、整除关系

包含关系R

等都是相应集合A上的传递关系例3.2.12.设A={a,b,c}

R1={〈a,b〉,〈b,c〉,〈a,c〉}R2={〈a,b〉,〈b,a〉}R3={〈a,a〉,〈b,b〉}

R4={〈a,b〉}R是A上的传递关系R°RR.传递不具备传递性传递传递2023/10/1160有穷集合A上关系R传递性的关系矩阵MR判别法:①给出MR

②计算M=MR·MR

③针对M中元素为1的每个位置,检查MR中相应位置是否也为1.如果在MR中相应的位置都是1,那么R是传递的有穷集合A上关系R传递性的关系图GR判别法:

①给出集合A={x1,x2,…,xn}上的关系图GR②依次考察GR的每一个结点xi,i=1,2,…,n.若xi经过两步长的有向路径到达xj,则在GR中应该有一条从xi到xj的有向边(若xi=xj则为环边)③如果找到某个结点不满足要求,那么R不是传递的,如果不存在这样的结点则R是传递的.2023/10/1161bca(1)bca(2)bca(3)bca(4)例3.2.13.设A={a,b,c}上的关系的关系图如下所示:(1)反对称,传递但不是对称关系而且也是既不自反也不反自反的关系(2)反自反但不是对称,不是反对称不是自反也不是传递的关系(3)自反,传递,反对称但不是对称也不是反自反的关系(4)不自反,不反自反但是传递而且既是对称也是反对称的关系bca(5)(5)自反,反对称但不是传递,不是对称也不是反自反的关系2023/10/1162关系的性质设R1和R2都是集合A上的关系,则具有下述联系:①若R1和R2都自反,则,R1∩R2,R1∪R2,R1°R2也自反.②若R1,R2都反自反,则,R1∩R2,R1∪R2,R1-R2也反自反.③若R1,R2都对称,则,R1∩R2,R1∪R2,R1-R2也对称.④若R1,R2都反对称,则,R1∩R2,R1-R2也反对称.⑤若R1,R2都是传递的,则,R1∩R2也是传递的.2023/10/1163关系的性质2.关系的闭包运算求满足指定性质的以给定关系为子集的最小关系的运算称关系的闭包运算闭包运算从已知关系出发,通过增加最少的有序对来生成满足某种指定的关系性质的运算定义3.2.14.设R是集合A上的关系,R的自反(对称;传递)闭包是A上的关系R',使得R'满足以下条件:

(1)R'是自反的(对称的;传递的)

(2)R

R'

(3)

对A上任何包含R的自反(对称;传递)关系R''有R'

R''.关系R的自反闭包,对称闭包和传递闭包分别记作r(R),s(R)和t(R)如果关系R是自反(对称;传递)的,那么R的自反(对称;传递)闭包r(R)(s(R);t(R))=R.2023/10/1164构造一个关系的闭包有三种方法:

(1)集合表达式法定理3.2.7.设R是A上的关系,则有①r(R)=R∪R0;

②s(R)=R∪R-1;

③t(R)=R∪R2∪R3∪….证明:①要证R∪R0满足自反闭包定义:R0=IA

R∪R0,即R∪R0在A上是自反的;R

R∪R0;再证R∪R0是包含R的最小的自反关系.若R''是包含R的自反关系,那么IA

R'',RR''

因此R∪R0=IA∪RR''.

②证R∪R-1满足对称闭包定义:由(R∪R-1)-1=R-1∪R=R∪R-1知R∪R-1是对称的RR∪R-1

再证R∪R-1是包含R的最小的对称关系.若R''是包含R的对称关系,那么(R'')-1=R'',但RR''所以R-1

R'',因此R∪R-1

R''2023/10/1165③首先证明R∪R2∪R3∪…具有传递性.任取〈x,y〉和〈y,z〉.〈x,y〉∈R∪R2∪R3∪…

∧〈y,z〉∈R∪R2∪R3∪…

t(〈x,y〉∈Rt)∧

s(〈y,z〉∈Rs)

〈x,z〉∈Rt

°Rs

〈x,z〉∈Rt+s

〈x,z〉∈R∪R2∪R3∪….t(R)是具有传递性的包含R的最小关系,R∪R2∪R3∪…是具有传递性的包含R的关系

t(R)

R∪R2∪R3∪…;再证明R∪R2∪R3∪…

t(R)

只需证明对任意正整数n,都有Rn

t(R).对n做归纳:n=1时显然.假设对n=k时Rk

t(R),再证n=k+1时有Rk+1

t(R).令〈x,y〉任意.则〈x,y〉∈Rk+1

〈x,y〉∈Rk

°

R

t(〈x,t〉∈RK)∧〈t,y〉∈R)

t(〈x,t〉∈t(R)∧〈t,y〉∈t(R))

〈x,y〉∈t(R)(t(R)具有传递性).③t(R)=R∪R2∪R3∪….2023/10/1166关系的性质对于有穷集合A上的关系R有t(R)=R∪R2∪R3∪…∪Rs.式中s≤|A|.例3.2.14.设A={a,b,c},R={〈a,a〉,〈a,c〉,〈b,c〉}r(R)=R∪R0=IA∪R={〈a,a〉,〈a,c〉,〈b,c〉}∪IA

={〈a,a〉,〈a,c〉,〈b,c〉,〈b,b〉,〈c,c〉}

s(R)=R∪R-1=R∪{〈a,a〉,〈c,a〉,〈c,b〉}={〈a,a〉,〈a,c〉,〈b,c〉,〈c,a〉,〈c,b〉}t(R)=R∪R2∪R3=R∪{〈a,a〉,〈a,c〉}(R2=R3,s≤3)

={〈a,a〉,〈a,c〉,〈b,c〉}(R2R).2023/10/1167

(2)关系矩阵法(记对应的矩阵为M,Mr,Ms和Mt):

①Mr=M+E;②Ms=M+M’;③Mt=M+M2+M3+…(+为逻辑加)如例3.2.14.

例3.2.14.设A={a,b,c},R={〈a,a〉,〈a,c〉,〈b,c〉}2023/10/1168关系的性质(3)关系图法(设关系R及r(R),s(R),t(R)的关系图分别为G,Gr,Gs,Gt)构造Gr,只需在G中缺少环的每个结点加一个环构造Gs,只需在G中所有存在单向边的不同结点对之间再加一条反向边构造Gt,只需在G中检查每个结点的可达性:结点x若经过至多n(G中结点数|A|)步长的有向路径到达结点y,且G中缺少有向边〈x,y〉,那么就给Gt加上一条x到y的有向边.当所有的结点都检查完以后,就得到图Gt.在t(R)的关系图Gt中,x到y有一条边G中x到y存在长至少为1的路径.2023/10/1169(3)关系图法2023/10/1170关系的性质3.沃舍尔(Warshall)算法关系R的传递闭包,实际上是图的连通关系R*={〈x,y〉|

在G中存在一条从x到y的有向路径}.图的连通性问题通信网络运输路线规划等方面因此传递闭包的计算需要一个高效率的算法.2023/10/1171沃舍尔算法Warshall在1962年提出了一个有效的算法来求解有限集合上二元关系R的传递闭包设集合A含有n个元素,R是A上的一个二元关系,MR是其关系矩阵,则Warshall算法简述为:“置行查列遍寻真(1),见真行上析当今(i),行推列移下右再,行穷列尽闭包成(Mt)”。

2023/10/1172沃舍尔算法输入:集合A(|A|=n)上关系R的关系矩阵MR=(mij)n·n.输出:R的传递闭包t(R)的关系矩阵Mt.

1.置M←MR;

2.取i←1;

3.对j=1,2,…,n,如有mji=1,则新取mjk=mjk∨mik,k=1,2,…,n;

4.i←i+1;

5.如果i≤n,则转3.,否则输出.例3.2.15.设A={a,b,c},R={〈a,a〉,〈a,c〉,〈b,c〉,〈c,b〉}则依据沃舍尔算法:2023/10/1173课堂讲习题由R的关系矩阵判断关系R是否具有传递性.方法:设R是有穷集合A上的关系,则有:

①给出MR

②计算M=MR·MR

③M中元素为1的每个位置,检查MR中相应位置是否也为1.如果在MR中相应的位置都是1,则R是传递的

示例:设A={a,b,c},R={〈a,b〉,〈a,c〉,〈b,c〉}则①

③针对M中元素1的每个位置,经检查MR中相应位置

(〈3,1〉=1)也是1,所以R是A上的传递关系.②2023/10/1174课堂讲习题证明:①R,S都是反对称的R∩S也是反对称的.

②R,S都是传递的,但推不出RoS是传递的.

①任取〈x,y〉,〈y,x〉.〈x,y〉,〈y,x〉∈R∩S

〈x,y〉,〈y,x〉∈Rx=y.即R∩S也是反对称的.

②反例:A={1,2,3}R={〈1,1〉,〈2,3〉}S={〈1,2〉,〈3,3〉}RoS={〈1,2〉,〈2,3〉}不具有传递性质.证明:2023/10/1175课堂讲习题计算具有多种性质闭包的运算次序问题:A上关系R,计算自反闭包是r(R),接着算对称闭包记作sr(R),再算传递闭包为tsr(R).

若,且i≠j,则自反性反自反性对称性反对称性传递性集合表达式关系矩阵主对角线元素都是1主对角线元素都是0关系矩阵是对称矩阵M2中1所在位置,M中相应位置都是1关系图每个结点都有环每个结点都没有环若两个结点之间有边,必为一对反向边(无单边)若两个结点之间有边,必定是一条有向边(无双向边)若结点xi到xj有边,xj到xk有边,则从xi到xk也有边2023/10/1176课堂讲习题计算具有多种性质闭包运算的例与一些重要的事实.

设A={a,b,c},R={〈a,b〉,〈a,c〉}r(R)={〈a,b〉,〈a,c〉,〈a,a〉,〈b,b〉,〈c,c〉}sr(R)={〈a,b〉,〈a,c〉,〈a,a〉,〈b,b〉,〈c,c〉,〈b,a〉,〈c,a〉}(一般:sr(R)=rs(R);tr(R)=rt(R))tr(R)={〈a,b〉,〈a,c〉,〈a,a〉,〈b,b〉,〈c,c〉}tsr(R)={〈a,b〉,〈a,c〉,〈a,a〉,〈b,b〉,〈c,c〉,〈b,a〉,〈c,a〉,〈b,c〉,〈c,b〉}str(R)={〈a,b〉,〈a,c〉,〈a,a〉,〈b,b〉,〈c,c〉,〈b,a〉,〈c,a〉}(一般:st(R)≠ts(R),只有st(R)

ts(R))

注意:对称闭包与传递闭包的次序不可颠倒.因为先计算传递闭包,再计算对称闭包在计算对称闭包时可能将传递性丢失.2023/10/1177关系性质与运算的联系表(拥有某性质的二元关系在指定进行集合的一种运算后是否还具有该性质?):自反性反自反性对称性反对称性传递性√√√√√√√√√√√√√×××√√√×√××××2023/10/11783.2.4等价关系与划分等价关系是一类重要的二元关系划分是一种对对象集合的分类两者能相互惟一确定.

考虑:①班上同学的同性别关系.这是一种满足自反,对称和传递性的等价关系

②把班上同学按男,女分为两个组.这是对班上全体同学的一种划分③在同性别关系下形成两个性别类与按男,女分组的划分方法相互惟一确定2023/10/1179等价关系与划分1.等价关系定义3.2.15.设R是集合A上的关系,如果R是自反、对称和传递的,则称R为A上的等价关系.对于任何元素x,y∈A,如果xRy,则称x与y等价,记作x~y.集合A上的恒等关系IA全域关系EA整数集合Z上的小于等于关系在整数集合Z或者Z的子集上有一种重要的等价关系,即整数模m同余关系:≡.对于任意整数x和y,x≡y(modm)的含义是

x与y除以m的余数相等(即x与y的差可被m整除)2023/10/1180等价关系与划分例3.2.16.设A={1,2,3,4,5,6,7}试构造A上的模3等价关系?R={〈1,1〉,〈1,4〉,〈4,1〉,〈1,7〉,〈7,1〉,〈2,2〉,〈2,5〉,〈5,2〉,〈3,3〉,〈3,6〉,〈6,3〉,〈4,4〉,〈4,7〉,〈7,4〉,〈5,5〉,〈6,6〉,〈7,7〉}.2023/10/1181等价关系与划分等价类和商集等价关系将集合A的元素划分成若干个子集,彼此等价的元素被分在同一个子集里.上例中的1,4,7除以3的余数都是1,它们在同一个子集里.2和5除以3的余数都是2,它们也在同一个子集里.另外一个子集就是由3与6构成的子集,它们除以3的余数为0.这些子集称作这个等价关系产生的等价类.定义3.2.16.设R是集合A上等价关系,x是A的元素,A中与x等价的全体元素构成的子集称为x的等价类,记作[x]R.x的等价类[x]R,简记为[x],即[x]={y|y∈A,xRy}例3.2.16.中的等价类是:[1]=[4]=[7]={1,4,7};[2]=[5]={2,5};[3]=[6]={3,6}.2023/10/1182定理3.2.7.设R是A上的等价关系,则

①∀x∈A,[x]是A的非空子集.

②∀x,y∈A,如果xRy,则[x]=[y].

③∀x,y∈A,如果xRy,则[x]∩[y]=φ.

④A中元素构成的所有等价类的并集证明:①由等价类定义可知,∀x∈A,有[x]A;由自反性有xRx,因而x∈[x],即[x]非空.

②任取z,则有:z∈[x]xRzzRx,又知xRyzRyyRz.从而得z∈[y],即证明了

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论