离散数学 课件 第3-5章 集合、二元关系、函数

第3章集合§1集合的概念及其表示§2

集合的运算§3

集合定律§4包含容斥原理§5多重序元和笛卡尔乘积§1集合的概念及其表示1、集合2、集合的元素3、有限集和无限集4、集合的表示方法5、集合相等6、子集和包含7、真子集和真包含8、空集9、全集10、幂集1、集合

具有某种特殊性质的客体的聚合 集合是一种不可精确定义的数学基本概念，只能给予一种描述。

用大写的英文字母表示集合2、集合的元素

属于集合的任何客体集合的元素集合的成员用小写字母表示元素a属于集合Aa∈Aa属于A元素a不属于集合Aa

Aa不属于A3、有限集和无限集一个集合的元素个数是有限的有限集一个集合的元素个数是无限的无限集4、集合的表示方法（1）列举法：（2）描述法：列出集合中的元素元素之间用逗号分开用花括号括起来用集合中元素所满足的性质表示集合谓词法构造法5、集合相等公理：集合A集合B集合A和B相等A和B具有相同的元素A=B例：一个集合可以做为

另一个集合的元素S={a,{1,2},p,{q}}S中共4个元素，分别为：a{1,2}p{q}{1,2}S{q}S1S2SqS集合的特点（1）元素的确定性（2）互异性（3）无序性集合中的元素是确定的a∈A或a

A二者必居其一集合中的每个元素均不相同集合中元素没有先后顺序6、子集和包含集合A集合BA的每一个元素都是B的元素A为B的子集A

BA包含于BB包含AB

AAB(

x)(→)x

Ax

B证明集合相等的充分必要条件定理： 集合A和B相等的充分必要条件是：A和B互为子集即：

A=B

A

B∧B

A7、真子集和真包含

集合A集合BA的每一个元素都是B的元素A为B的真子集A

BA真包含于BB真包含AA

B

A

B∧A≠Bx

Ax

BB中至少有一个元素不属于AA

B

（x)(→)∧(

y)(∧)y

ByA8、空集不包含任何元素的集合是空集φ｛φ｝｛φ｝φ≠

例：φ{}9、全集

在一定范围内,若所有集合均为某一集合的子集,则该集合称为全集E求子集举例A={1，2，3}，求A的所有子集。解：φ{1}{2}{3}{1，2}{1，3}{2，3}{1，2，3}23=8个子集集合的元素个数10、幂集

给定集合A,由集合A的所有子集为元素组成的集合,称为集合A的幂集ρ(A)=ρ(A){x|}x

A幂集举例A={1，2，3}，求A的幂集解：ρ(A)={φ,{1},{2},{3},{1，2},{1，3},{2，3},{1，2，3}}定理

如果有限集合A有n个元素，则它的幂集ρ(A)有2n个元素。§2

集合的运算1、交运算（∩）2、并运算（∪）3、差分运算（－）4、对称差分运算（⊕）1、交运算（∩）集合A集合B所有共同元素组成的集合A和B的交集A∩BA∩B={x|x∈A∧x∈B}A∩B的文氏图表示A∩B交运算的性质(1)等幂律:A∩A=A(2)零律:A∩φ=φ(3)同一律:A∩E=A(4)交换律:A∩B=B∩A(5)结合律:(A∩B)∩C=A∩(B∩C)A∩B

AA∩B

B集合不相交集合A集合B没有共同的元素A和B不相交A∩B＝φ2、并运算（∪）集合A集合B所有元素组成的集合A和B的并集A∪

BA∪B={x|x∈A∨x∈B}并运算的性质(1)等幂律:A∪A=A(2)零律:A∪E=E(3)同一律:A∪φ=A(4)交换律:A∪B=B∪A(5)结合律:(A∪B)∪C=A∪(B∪C)A

A∪BBA∪B定理：分配率集合A集合B集合C∩对∪

、∪对∩满足分配率A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)定理：吸收律设A、B为任意的两个集合，则：A∪(A∩B)=AA∩(A∪B)=A3、差运算（-）集合A集合B属于A而不属于B的一切元素组成的集合A和B的差集A-BA-B={x|x∈A∧x

B}B对A的相对补集绝对补集（补集）全集E集合AA对E的补集E－AA的绝对补集补集~Ａ~A=={x|x∈E∧x

A}E-A={x|x

A}补运算的性质(1)~(~A)=A(2)~E=φ(3)A∪~A=E(4)A∩~A=φ定理：德.摩根定律设任意两个集合A和B,则：(1)~(A∪B)=~A∪~B~A∩~B(2)~(A∩B)=定理设任意两个集合A和B,则：(1)A-B=A∩~B(2)A-B=A-(A∩B)4、对称差运算(⊕)集合A集合B或属于A,或属于B,但不能既属于A又属于B的元素组成A和B的对称差A⊕BA⊕B=={x|x∈Ax∈B}(A－B)∪(B－A)A－BB－A对称差运算的性质(1)交换律B⊕AA⊕B=(2)结合律(A⊕B)⊕C=A⊕(B⊕C) (3)A⊕φ=A(4)A⊕A=φ(5)A⊕B=(A－B)∪(B－A)=(A∩~B)∪(B∩~A)§3

集合定律1、等幂律 2、结合律3、交换律 4、分配率5、同一律 6、零律7、补余律 8、吸收律9、德.摩根定律 10、双重否定定律11、包含关系式 12、蕴涵式将命题公式转换成集合公式的方法∧

变∩

∨变∪

变~

T 变EF变φ同一律A∪φ=AA∩E=A对应的命题公式：P∨F

PP∧T

P德.摩根定律~(A∪B)=~A∩~B ~(A∩B)=~A∪~B ~E=φ~φ=E对应的命题公式：

(P∨Q)

P∧

Q

(P∧Q)

P∨

Q

TFFT11、包含关系式A∩BA A∩BBAA∪B B

A∪BA-B

A§5多重序元和笛卡尔乘积一、多重序元二、笛卡尔乘积一、多重序元1、序偶2、三重序元3、n重序元1、序偶两个具有固定次序的客体组成的序列<x,y>序偶的第一个元素序偶的第二个元素≠<x,y><y,x>两个序偶相等的定义序偶<x,y>序偶<u,v><x,y>＝<u,v>

x=u∧y=v2、三重序元三重序元是一个序偶第一个元素本身也是个序偶<,z><x,y,z><x,y>3、n重序元n重序元是一个序偶第一个元素是(n-1)重序元<,xn><x1,x2,…,xi,…,xn

><x1,x2,…,xn-1>n重序元的第i个坐标两个n重序元相等的定义n重序元<x1,x2,…,xn>n重序元<a1,a2,…,an><x1,x2,…,xn>＝<a1,a2,…,an>

(x1=a1)∧(x2=a2)∧…∧(xn=an)二、笛卡尔乘积1、笛卡尔乘积的定义2、相关定理3、n个集合的笛卡尔乘积1、笛卡尔乘积的定义注意：笛卡尔乘积不满足交换律、结合律A、B为任意集合序偶的第一个元素是A的元素序偶的第二个元素是B的元素A和B的笛卡尔乘积A×BA×B={<x,y>|}x

A∧y

B2、相关定理设A,B,C为任意三个集合，×对∩和∪满足分配律（1）A×(B∪C)=(A×B)∪(A×C)（2）A×(B∩C)=(A×B)∩(A×C)（3）(A∪B)×C=(A×C)∪(B×C)（4）(A∩B)×C=(A×C)∩(B×C)证明：A×(B∩C)=(A×B)∩(A×C)证明：设对任意的<x,y>

A×(B∩C)

x

A∧y

B∩C

x

A∧y

B∧y

C(x

A∧y

B)∧(x

A∧y

C)

<x,y>

A×B∧<x,y>

A×C

<x,y>

(A×B)∩(A×C)笛卡尔乘积举例A={1,2},B={α,β},C={a},D=φ求：A×B注意：笛卡尔乘积不满足交换律={<1,α>,<1,β>,<2,α>,<2,β>}B×A={<α,1>,<α,2>,<β,1>,<β,2>}A×C={<1,a>,<2,a>}A×D=φA×A={<1,1>,<1,2>,<2,1>,<2,2>}笛卡尔乘积举例A={1,2},B={α,β},C={a}求：A×(B×C)=?(A×B)×C=?注意：笛卡尔乘积不满足结合律A×B={<1,α>,<1,β>,<2,α>,<2,β>}B×C={<α,a>,<β,a>}A×(B×C)={<1,<α,a>>,<2,<α,a>>,<1,<β,a>>,<2,<β,a>>}不是三重序元(A×B)×C={<<1,α>,a>,<<1,β>,a>,<<2,α>,a>,<<2,β>,a>}是三重序元3、n个集合的笛卡尔乘积A1×A2×…×An=((((A1×A2)×A3)×…×An)={<x1,x2,…,xn>|x1

A1∧x2

A2∧…∧xn

An}=A×A=A2

A×A×A×…×A=An|An|=|A|n笛卡尔乘积举例A={a,b},|A|=2A2=A×A={<a,a>,<a,b>,<b,a>,<b,b>}|A2|=|A|2=22=4A3=A×A×A={<<a,a>,a>,<<a,a>,b>,<<a,b>,a>,<<a,b>,b>,<<b,a>,a>,<<b,a>,b>,<<b,b>,a>,<<b,b>,b>}|A3|=|A|3=23=8第四章二元关系§1关系的基本概念§2关系的性质及运算§3特种关系§1关系的基本概念一、关系的定义二、关系的表示方法一、关系的定义1、关系的定义2、关系相等3、关系的定义域和值域1、关系的定义A1、A2、…、An是任意的n个集合,n

I＋(1)RA1A2An×××

…A1、A2、…、An间的n元关系(2)RA1×A2

从A1到A2的二元关系（3）R＝φ空关系（4）R＝A1×A2×…×An全关系A上的n元关系(5)RAAA×××

…对n元关系定义的解释（1）n元关系是一个集合；（2）集合中的元素均为n重序元:n元关系是n个集合的笛卡儿乘积的一个子集；n重序元中的第1个元素属于A1n重序元中的第i个元素属于Ai2元关系是两个集合的笛卡儿乘积的一个子集；关系举例已知：A={1,2,3,4,5,6}R1={<x,y>|x+y=7},R2={<x,y>|x-y=0}R1={<1,6>,<6,1>,<2,5>,<5,2>,<3,4>,<4,3>}R2={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>}R1A×A

R2A×A

R1、R2均为A上的二元关系关系举例已知：A={1,2,3},B={a,b}R1={<1,a>,<1,b>,<2,a>,<3,b>}A×B={<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>}R1A×B

R1是从A到B的二元关系关系举例R2={<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>}已知：A={1,2,3},B={a,b}R2A×B=R2是从A到B的全关系R3={<1,1>,<2,2>,<3,3>}A×A={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}R3A×A

R3是从A上的二元关系关系举例A={f,m,s,d}R1定义为A上长幼关系，则：R1<x,y>

R={<f,s>,<f,d>,<m,s>,<m,d>}<f,m>

R1f和m没有长幼关系<d,s>

R1d和s没有长幼关系x和y有R关系xyR<x,y>

Rx和y没有R关系xy2、关系相等R1A1A2An×××

…R2B1B2Bm×××

…（1）m=n;（2）若1≤i≤n，则Ai=Bi;（3）集合R1=集合R2关系R1和关系R2相等R1=R2对关系相等的解释（1）必须是同元关系; （2）对应的集合相等；（3）集合R1=集合R2m=nAi=Bi关系相等举例R1：A→BR2：C→BA={1,2}B={a,b}C={1,2,3}R1={<1,a>,<1,b>,<2,a>}R2={<1,a>,<1,b>,<2,a>}问：R1和R2是否相等？m=n=2集合R1=集合R2R1：A→BR2：C→BA≠C结论：R1≠R23、关系的定义域和值域R:X→Y关系R的定义域:关系R的序偶中第一元素所组成的集合D(R)D(R)={x|<x,y>R}X

关系R的值域:关系R的序偶中第二元素所组成的集合R(R)R(R)={y|<x,y>R}Y

定义域和值域举例（1）X={x1,x2,x3}Y={y1,y2}R1={<x1,y1>,<x1,y2>,<x2,y2>,<x3,y1>}（2）A={1,2,3,4}B={a,b,c}R2={<1,a>,<1,b>,<3,a>}求：D(R1),R(R1),D(R2),R(R2)D(R1)={x1,x2,x3}X=R(R1)={y1,y2}Y=D(R2)={1,3}A

R(R2)={a,b}B

定义域和值域举例N:非负整数集合R:N→NR={<x,y>|x+2y=10}求:D(R)=?R(R)=?R={<0,5>,<2,4>,<4,3>,<6,2>,<8,1>,<10,0>}D(R)={0,2,4,6,8,10}R(R)={0,1,2,3,4,5}二、关系的表示方法1、关系图法2、关系矩阵法1、关系图法注意：结点的位置及边的曲直是无关紧要的关系图：结点有向弧线X={x1,x2,…,xm}Y={y1,y2,…,yn}R:X→Y(1)在平面上作m个结点x1x2xixm(2)在平面上作n个结点y1y2yjyn(3)如果<xi,yj>

RXYRGR关系图举例(1)X={1,2,3}Y={a,b}R:X→YR={<1,a>,<1,b>,<2,a>,<3,b>}画出关系R的关系图。123abXYRR的关系图关系图举例(2)X={1,2,3,4,5}R:X→XR={<1,5>,<1,4>,<2,3>,<3,1>,<3,4>,<4,4>}画出关系R的关系图。12345R的关系图闭环(自环)关系图举例(3)X={0,1,2,3,4}R:X→XR={<x,y>|x≥0∧y≥3}画出关系R的关系图R={<0,3>,<0,4>,<1,3>,<1,4>,<2,3>,<2,4>,<3,3>,<3,4>,<4,3>,<4,4>}012342、关系矩阵法X={x1,x2,…,xm}Y={y1,y2,…,yn}R:X→Y关系矩阵:rij=0∨rij=1当<xi,yj>R时,当<xi,yj>R时,rij=1rij=0布尔矩阵m×n矩阵MR关系矩阵举例(1)X={1,2,3}Y={a,b}R:X→YR={<1,a>,<1,b>,<2,a>,<3,b>}求关系R的关系矩阵。MR=123ab111100关系矩阵举例(2)X={1,2,3,4,5}R:X→XR={<1,5>,<1,4>,<2,3>,<3,1>,<3,4>,<4,4>}求关系R的关系矩阵。MR=12345111100123451100000000000000000关系矩阵举例(3)X={0,1,2,3,4}R:X→XR={<x,y>|x≥0∧y≥3}画出关系R的关系矩阵。解答R={<0,3>,<0,4>,<1,3>,<1,4>,<2,3>,<2,4>,<3,3>,<3,4><4,3>,<4,4>}MR=01234111100012341100000001000100011§2关系的性质及运算一、关系的性质二、关系的运算一、关系的性质1、自反性2、反自反性3、对称性4、反对称性5、可传递性1、自反性R:X→XR是自反的

对于每一个x

X，都有<x,x>

RR是自反的

(

x)(→)x

X<x,x>

R自反性关系的举例实数集合R:“≤”关系“≥”关系自反的关系(

x)(→)x

Rx≤x(

x)(→)x

Rx≥x自反性关系的举例X={1,2,3}R1={<1,1>,<2,2>,<3,3>,<3,1>}R2={<1,1>,<2,2>,<3,1>,<2,3>}问：R1、R2是否具有自反性？R1具有自反性R2不具有自反性<3,3>R22、反自反性R:X→XR是自反的

R是自反的

(

x)(→)x

X<x,x>

R对于每一个x

X，都有<x,x>

R反自反性关系的举例X={1,2,3}R1={<1,1>,<2,1>,<3,2>}R2={<1,2>,<1,3>,<3,1>}问：R1、R2是否具有反自反性？R1不具有反自反性<1,1>R2<2,2>R2<3,3>R2R2具有反自反性不自反的关系不是自反的不是反自反的不自反的关系X={1,2,3}R={<1,1>,<2,1>,<3,2>}R是不自反的二元关系；<2,2>R<3,3>R3、对称性R:X→XR是对称的

对于每一个x、y

X，如果有<x,y>

R<y,x>

RR是对称的

(

x)(

y)(→)x

X∧y

X∧<x,y>

R<y,x>

R对称性关系举例实数集合R:“＝”关系:对称关系(

x)(

y)(→)x

R∧y

R∧x=yy=x对称性关系举例X={1,2,3}R1={<1,2>,<2,1>,<3,2>,<1,3>}R2={<1,2>,<2,1>,<3,3>,<3,2>,<2,3>}问：R1、R2是否具有对称性？<2,3>R1R1不具有对称性；R2具有对称性；4、反对称性R:X→XR是反对称的

对于任意的不相同的x、y

X，如果有<x,y>

R<y,x>

RR是反对称的

(

x)(

y)(→)x

X∧y

X∧x≠y∧<x,y>

R<y,x>

RR是反对称的

(

x)(

y)(→)x

X∧y

X∧<x,y>

R

∧<x,y>

Rx=y反对称关系举例实数集合R:“≤”关系:反对称的关系(

x)(

y)(→)x

R∧y

R∧x≠y∧x≤yy≰x(

x)(

y)(→)x

R∧y

R∧x≤y∧y≤xx=y反对称关系举例X={1,2,3}R1={<1,1>,<2,2>,<3,3>}R2={<1,3>,<2,1>,<2,3>}R3={<1,3>,<3,1>,<2,1>,<2,3>}问：R1、R2、R3是否具有反对称性？R1具有反对称性R1具有对称性<3,1>R2<1,2>R2<3,2>R2R2具有反对称性R3不具有反对称性<1,2>R3R3不具有对称性注意：一个关系可以即是对称的，也是反对称的。不对称性不是对称的不是反对称的不对称的关系5、可传递性R:X→XR是可传递的

对于任意的x、y、z

X如果有<x,y>

R和<y,z>

R<x,z>

RR是可传递的

(

x)(

y)(

z)(→)x

X∧y

X∧z

X∧<x,y>

R

∧

<y,z>

R<x,z>

Rxyz可传递关系举例实数集合R:“＝”关系“≤”关系“≥”关系“＜”关系“＞”关系可传递关系(

x)(

y)(

z)(→)x

R∧y

R∧z

R∧x＜y

∧y＜zx＜z可传递关系举例X={1,2,3}R1={<1,2>,<2,1>,<3,1>}R2={<1,2>,<2,3>,<1,3>},R3={<1,2>}问：R1、R2、R3是否具有可传递性？<1,1>R1R1不具有可传递性R2具有可传递性；R3具有可传递性；善意的推定可传递关系判断方法<x,y>

R∧<y,z>

R

→<x,z>

R假在关系R中找不到<x,y>和<y,z>真关系为可传递关系关系性质举例自然数集合N:相等关系“=”大于关系“＞”大于等于关系“≥”各具有什么性质?自反的、对称的、反对称的、可传递的反自反的、反对称的可传递的自反的、反对称的可传递的关系性质举例X=φX≠φX上的空关系具有什么性质？自反的、反自反的、对称的、反对称的、可传递的反自反的、对称的、反对称的、可传递的关系性质举例非空集合A,ρ(A)为A的幂集各具有什么性质？ρ(A)上的包含关系“

”ρ(A)上的真包含关系“

”自反的、反对称的可传递的反自反的、反对称的可传递的利用关系图判断关系的性质(1)自反性:(2)反自反性:(3)对称性:(4)反对称性:每一个结点上必有一个闭环(自回路)；每一个结点上都没有闭环(自回路)；两个结点间如果有有向边必成对出现；两个结点间如果有有向边必单根出现；利用关系矩阵判断关系的性质(1)自反性:(2)反自反性:(3)对称性:(4)反对称性:主对角线上的元素均为“1”；主对角线上的元素均为“0”；对称阵rij=rji反对称阵当i≠j时：若rij＝1rji＝011110000二、关系的运算1、关系的合成运算2、关系的逆运算3、关系的闭包运算1、关系的合成运算（1）合成运算的定义（2）关系R的幂（3）合成关系的矩阵表达和图解引例（1）a是b的父亲b是c的父亲a是c的祖父（2）a是b的弟弟b是c的父亲a是c的叔叔父子关系祖孙关系兄弟关系父子关系叔侄关系（1）合成运算的定义R:X→YS:Y→ZR与S的合成关系复合关系R◦SX→ZR◦S={<x,z>|x

X∧z

Z∧(

y)(∧)}<x,y>

R<y,z>

Sy

Y∧合成运算的举例X={1,2,3,4}Y={2,3,4}Z={1,2,3}R:X→

YS:Y→ZR={<x,y>|x+y=6},S={<y,z>|y-z=1}求：R◦SR={<2,4>,<3,3>,<4,2>}S={<2,1>,<3,2>,<4,3>}R◦S={<2,3>,<3,2>,<4,1>}x+z=5关系R、S、R◦S的关系图X4321Y234RZ123SR◦SXZ4321123合成运算的讨论（1）若：R(R)∩D(S)=φR:X→YS:Y→ZR◦S=φ（2）若：R(R)∩D(S)≠φR◦S≠φ（3）D(R◦S)X

R(R◦S)Z

至少有一个序偶<x,y>

R且<y,z>

S定理：◦对∪满足分配律R1:X→Y;R2、R3:Y→Z；R4:Z→W(1)R1◦(R2∪R3)=(R1◦R2)∪(R1◦R3)(2)(R2∪R3)◦R4=(R2◦R4)∪(R3◦R4)(3)R1◦(R2∩R3)(R1◦R2)∩(R1◦R3)

(4)(R2∩R3)◦R4(R2◦R4)∩(R3◦R4)

证明：(R2∪R3)◦R4=(R2◦R4)∪(R3◦R4)证明：∵R2∪R3:Y→Z；R4:Z→W∴(R2∪R3)◦R4

:Y→W对任意的<y,w>

(R2∪R3)◦R4

(z)(<y,z>R2∪R3∧

<z,w>R4)

(z)((<y,z>R2∨<y,z>R3)∧

<z,w>R4)

(z)((<y,z>R2∧<z,w>R4)∨(<y,z>R3∧<z,w>R4))(z)(<y,z>R2∧<z,w>R4)∨(z)(<y,z>R3∧<z,w>R4)<y,w>R2◦R4∨<y,w>R3◦R4<y,w>(R2◦R4)∪(R3◦R4)证明：(R2∩R3)◦R4

(R2◦R4)∩(R3◦R4)证明：∵R2∩

R3:Y→Z；R4:Z→W∴(R2∩

R3)◦R4

:Y→W对任意的<y,w>

(R2∩R3)◦R4(z)(<y,z>R2∩R3∧

<z,w>R4)

(z)((<y,z>R2∧<y,z>R3)∧<z,w>R4)

(z)((<y,z>R2∧<z,w>R4)∧(<y,z>R3∧<z,w>R4))

(z)(<y,z>R2∧<z,w>R4)∧(z)(<y,z>R3∧<z,w>R4)<y,w>R2◦R4∧<y,w>R3◦R4<y,w>(R2◦R4)∩R3◦R4)定理：合成运算可结合R1:X→Y;R2:Y→Z；R3:Z→W，则有：R1◦(R2

◦R3)==R1◦R2◦R3

(R1◦R2)◦R3证明证明：∵

R1:X→Y;R2:Y→Z；R3:Z→W∴R1◦R2:X→Z;(R1◦R2)◦R3

:X→W;对任意的<x,w>

(R1◦R2)◦R3

(z)(<x,z>R1◦R2

∧

<z,w>R3)

(z)((y)(<x,y>R1∧<y,z>R2)∧<z,w>R3))(z)(y)(<x,y>R1∧<y,z>R2∧<z,w>R3)(y)(<x,y>R1∧(z)(<y,z>R2∧<z,w>R3))(y)(<x,y>R1∧<y,w>R2◦

R3)<x,w>R1◦

(R2◦

R3)合成运算举例R={<1,2>,<3,4>,<2,2>}S={<4,2>,<2,5>,<3,1>,<1,3>}求：R◦S，S◦R;

R◦S={<1,5>,<3,2>,<2,5>}S◦R={<4,2>,<3,2>,<1,4>}合成运算不满足交换律合成运算举例R={<1,2>,<3,4>,<2,2>}S={<4,2>,<2,5>,<3,1>,<1,3>}求：R◦(S◦R)，(R◦S)◦R;

R◦(S◦R)={<3,2>}(R◦S)◦R={<3,2>}合成运算满足结合律合成运算举例R={<1,2>,<3,4>,<2,2>}S={<4,2>,<2,5>,<3,1>,<1,3>}求：R◦R,S◦SR◦R={<1,2>,<2,2>}S◦S={<4,5>,<3,3>,<1,1>}R2S2合成运算的推广R1:X1→X2;X1→Xn+1R2:X2→X3；Rn:Xn→Xn+1R1◦R2◦…◦Rn:X1=X2=…=Xn+1=XR1=R2=…=Rn=RR1◦R2◦…◦Rn=RnR的n次幂（2）关系R的幂R:X→X;n

N，R的n次幂Rn定义为：（1）R0是X中的恒等关系IX

:R0=IX={<x,x>|xX}（2）Rn+1=Rn◦R定理设：R:X→YIX：X中的恒等关系；IY：Y中的恒等关系；则：IX◦R=R◦IY=

R定理（1）Rm◦Rn=R:X→X;m,nN（2）(Rm)nRm+n=Rmn关系R的幂举例设：A={a,b,c,d}R是集合A中的二元关系,且：R={<a,b>,<b,a>,<b,c>,<c,d>}求：R的幂。注意：有限集合上不同关系的数目是有限的R0=IA={<a,a>,<b,b>,<c,c>,<d,d>}R1=R={<a,b>,<b,a>,<b,c>,<c,d>}R2=R◦R={<a,a>,<a,c>,<b,b>,<b,d>}R3=R2◦R={<a,b>,<a,d>,<b,a>,<b,c>}R4=R3◦R={<a,a>,<a,c>,<b,b>,<b,d>}=R2R5=R4◦R=R2◦R=R3R6=R5◦R=R3◦R=R2R2n+1=R3R2n=R2n>=1R0RR2R3定理|X|=nR:X→X;存在s和t，使得:

Rs=Rt

(0≤s≤t≤)证明关系是笛卡尔乘积的子集|X

X|=n2|ρ(X

X)|=即：X上最多有个不同的关系；R0R1R2…

所以：至少有两项是相同的（3）合成关系的矩阵表达和图解X={x1,x2,…,xm}Y={y1,y2,…,yn}Z={z1,z2,…,zp}R:X→YMR=(aij)m

nS:Y→ZMs=(bij)n

pR◦S:X→ZMR◦S=(cij)m

pMR◦S=MRMs◦cij=(aik∧bkj)i=1,2…,mj=1,2,…,pMR中第i行第k列元素MS中第k行第j列元素MR=ai1ai2…ainMs=b1j…bnjb2jMR◦S=cijai1b1jai1b1j∧()ai2b2j∧()ai2b2jainbnjainbnj∧()∨∨∨…利用关系矩阵求合成关系矩阵举例A={1,2,3}B={1,2,3,4}C={1,2,3,4,5}R:A→BS:B→C并具体给定为：R={<1,2>,<2,1>,<2,3>,<3,3>}S={<1,2>,<1,5>,<2,3>,<3,1>,<3,2>,<4,3>,<4,5>}求MR◦SMR◦S=12312345001001100111000合成关系R∘S的关系矩阵MR◦S合成关系R∘SR◦SMR1∘(

MR1

∘

MR1)=(MR1∘

MR1)∘

MR1R={<1,2>,<2,1>,<2,3>,<3,3>}S={<1,2>,<1,5>,<2,3>,<3,1>,<3,2>,<4,3>,<4,5>}={<1,3>,<2,2>,<2,1>,<2,5>,<3,1>,<3,2>}定理R:X→X，则：R是可传递的

R2R证明：(必要性)∴R2

R已知:R是可传递的

R2R对任意的<x,z>

R2=R◦R(由合成关系的定义）(y)(∧)<x,y>R<y,z>R(

R可传递)

<x,z>

R

R是可传递的证明：(充分性)已知:

R2RR是可传递的对任意的<x,y>

R∧<y,z>R(合成关系定义）

<x,z>

R2(R2

R)

<x,z>

R可传递关系举例X={1,2,3}R={<1,2>,<2,3>,<1,3>}应用定理证明R具有可传递性？证明：R2∴R具有可传递性={<1,3>}R由R的关系图求R2关系图R:X→X

<xi，xk>

R∘R<xi，xj>

R∧

<xj

，xk>

R

=R2R的关系图GRR2的关系图GR2xjxixkxixjxk在R的关系图中，如果从结点xi出发经过两条有向边能够到达结点xk，在R2的关系图中必有一条从xi到xk的有向边由R的关系图求Rn关系图R:X→X，则：Rn的关系图的作图原则： 在R的关系图中，如果从结点xi出发经过n条有向边能够到达结点xk， 在Rn的关系图中必有一条从xi到xk的有向边。由R的关系图求Rn关系图举例X={a,b,c,d}R:X→XR={<a,b>,<b,a>,<b,c>,<c,d>} 试利用R的关系图，求出R2、R3、R4的关系图。关系R、R2、

R3、R4的关系图R2的关系图GR2abcdabcdR3的关系图GR3R4的关系图GR4abcdR2=R42、关系的求逆运算R：X→Y将R中每一序偶的前后元素互换R的逆关系R-1:Y→XR-1={<y,x>|<x,y>∈R}求逆关系的运算逆运算逆运算举例R：X→YX={1,2,3,4}Y={a,b,c}

R={<1,a>,<2,b>,<3,c>}求：R-1R-1={<a,1>,<b,2>,<c,3>}由R的关系图和关系矩阵求R-1的关系图和关系矩阵R关系图上所有的边改变方向第i行第i列R-1的关系图R关系矩阵的转置矩阵R-1的关系矩阵定理R:X→YS：Y→Z：(R∘S)-1=S-1∘R-1证明：任意的<z,x>

(R∘S)-1逆关系的定义

<x,z>

R∘S合成关系的定义(y)(<x,y>R∧<y,z>S)交换率(y)(<y,z>S∧<x,y>R)逆关系的定义(y)(<z,y>S-1∧<y,x>R-1)合成关系的定义

<z,x>

S-1∘R-1定理设R,S:X→Y，则:(1)(R-1)-1=R(2)(R∪S)-1=R-1∪S-1(3)(R∩S)-1=R-1∩S-1(4)(X

Y)-1=Y

X(5)(~R)-1=~(R)-1~R=X

Y-R(6)(R-S)-1=R-1-S-1(7)R=S

R-1=S-1(8)R

S

R-1

S-1(9)φ-1=φ证明：(3)(R∩S)-1=R-1∩S-1证明：任意的<y,x>

(R∩S)-1

<x,y>

R∩S

<x,y>

R∧<x,y>

S

<y,x>

R-1∧<y,x>

S-1

<y,x>

R-1∩S-1定理设R:X→X,则(1)R是对称的

R=R-1(2)R是反对称的

R∩R-1

Ix证明：(1)必要性已知：R是对称的R=R-1(R

R-1且R-1

R)对任意的<x,y>

R(1)

R

R-1R是对称的

<y,x>

R逆关系定义

<x,y>

R-1

R

R-1(2)

R-1

R对任意的<y,x>

R-1

逆关系定义

<x,y>

RR是对称的

<y,x>

R

R-1

R证明：(1)充分性已知：R=R-1R是对称的对任意的<x,y>

R逆关系定义

<y,x>

R-1R=R-1

<y,x>

RR是对称的3、关系的闭包运算R:X→X关系R′满足(1)R′是自反的(2)R

R′(3)对任何自反的关系R"

R

R"R′

R"R的自反闭包对称的对称的对称可传递的可传递可传递r(R)s(R)t(R)对闭包运算的解释关系R的闭包包含关系R具有某种性质最小的关系关系R本身已经具有某种性质关系R的闭包R本身闭包运算的举例X={a,b,c,d}R={<a,a>,<b,b>,<a,d>,<c,d>}求：r(R)、s(R)、t(R)r(R)={<a,a>,<b,b>,<a,d>,<c,d>,<c,c>,<d,d>}R={<a,a>,<b,b>,<a,d>,<c,d>}闭包运算的举例s(R)={<a,a>,<b,b>,<a,d>,<c,d>,<d,a>,<d,c>}t(R)={<a,a>,<b,b>,<a,d>,<c,d>}可传递定理设R:X→Xr(R)=Ix是X上的恒等关系∪RIx定理设R:X→Xs(R)=∪RR-1定理设R:X→Xt(R)=∪RR2R3R4…∪∪闭包运算的举例X={a,b,c}R:X→XR={<a,a>,<a,b>,<b,c>}求：r(R)、s(R)、t(R)r(R)=R∪Ix={<a,a>,<a,b>,<b,c>}∪{<a,a>,<b,b>,<c,c>}s(R)=R∪R-1

{<a,a>,<a,b>,<b,c>}∪{<a,a>,<b,a>,<c,b>}={<a,a>,<a,b>,<b,c>,<b,b>,<c,c>}={<a,a>,<a,b>,<b,c>,<b,a>,<c,b>}闭包运算的举例（续）t(R)=R∪R2∪R3∪R4…R={<a,a>,<a,b>,<b,c>}R2=R∘R={<a,a>,<a,b>,<b,c>}∘{<a,a>,<a,b>,<b,c>}={<a,a>,<a,b>,<a,c>}R3=R2∘R={<a,a>,<a,b>,<a,c>}∘{<a,a>,<a,b>,<b,c>}=R2R4=R3∘R=R2∘R=R3=R2t(R)=R∪R2∪R3∪R4…=R∪R2={<a,a>,<a,b>,<a,c>,<b,c>}

定理设R:X→X

(1)R是自反的

r(R)=R.(2)R是对称的s(R)=R.(3)R是传递的t(R)=R.定理设R:X→X|X|=nt(R)=∪RR2R3Rn…∪∪∪可传递闭包举例A={a,b,c,d}

R={<a,b>,<b,a>,<b,c>,<c,d>}R:A→A求t(R).R2=R∘R={<a,b>,<b,a>,<b,c>,<c,d>}∘{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R3=R2∘R={<a,a>,<a,c>,<b,b>,<b,d>}∘{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<a,d>,<b,a>,<b,c>}R4=R2t(R)=∪RR2R3∪={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}可传递闭包举例X={1,2,3,4,5,6,7}R:X→XR={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}求t(R).R2={<1,1>,<1,2>,<1,4>,<2,2>,<4,4>}R3={<1,1>,<1,2>,<1,4>,<2,4>,<4,2>}R4={<1,1>,<1,2>,<1,4>,<2,2>,<4,4>}=R2R5=R3t(R)=R∪R2∪R3={<1,1>,<1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>}定理设R:X→X，则：（1）如果R是自反的s(R)、t(R)也是自反的；（2）如果R是对称的r(R)、t(R)也是对称的；（3）如果R是可传递的r(R)是可传递的；证明（1）∵

R是自反的

IX

R

IX

R∪R-1=s(R)

∵IXs(R)s(R)是自反的∵

R是自反的

IX

R

IX

R∪R2∪…∪Rn

IXt(R)t(R)是自反的第三节特种关系一、覆盖和划分二、等价关系和等价类三、相容关系和相容类四、次序关系一、覆盖和划分1、覆盖定义2、划分定义3、最大划分4、最小划分5、加细1、覆盖定义A:非空集合S={S1,S2,…,Sm}(1)

Si

A(2)Si≠φi=1,2,…,m(3)S1∪S2∪…∪Sm=AA的覆盖2、划分定义注意：是划分一定是覆盖，反之不然A:非空集合S={S1,S2,…,Sm}是A的覆盖Si∩Sj=φi≠jA的划分m为划分的秩Si为划分的类划分和覆盖的图形表示覆盖和划分的举例S={1,2,3,4,5,6}判断下列集合是覆盖还是划分？(1)A1={{1,2,3},{4,5,6}}(2)A2={{1},{2,3,6},{4,5}}(3)A3={{1},{2},{3},{4},{5},{6}}(4)A4={{1,2,3},{3,4},{3,5,6}}(5)A5={{1,2,3},{4,5}}(6)A6={{1,2,3,4,5,6}}覆盖划分覆盖划分覆盖划分覆盖不是覆盖覆盖划分3、最大划分由单个元素构成的子集为元素的集合秩最大的划分最大划分举例A={a,b,c,d}S1={a},S2={b},S3={c},S4={d}S={S1,S2,S3,S4}最大划分={{a},{b},{c},{d}}4、最小划分秩为1的划分集合的全部元素组成的一个子集为元素的集合最小划分举例A={a,b,c,d}S1={a,b,c,d}最小划分S={S1}={{a,b,c,d}}5、加细A:非空集合{A1,A2,…,Ar}{B1,B2,…,Bs}A的划分若对于每个Ai

均有Bj使得Ai

Bj{A1,A2,…,Ar}是{B1,B2,…,Bs}的加细{A1,A2,…,Ar}{B1,B2,…,Bs}≠真加细加细举例X={a,b,c}

给出X集合的5个不同的划分A、B、C、D、E；问哪些划分是哪些划分的加细？解答A={{a,b,c}}={A1}B={{a,b},{c}}={B1,B2}C={{a},{b,c}}={C1,C2}D={{a,c},{b}}={D1,D2}E={{a},{b},{c}}={E1,E2,E3}B1

A1B2

A1B是A的加细C1

A1C2

A1C是A的加细D1

A1D2

A1D是A的加细E是A、B、C、D的加细证明划分举例 设{A1,A2,…,An}是集合A的划分，若Ai∩B≠φ(1≤i≤n) 试证明{A1∩B,A2∩B,…,An∩B}是A∩B的划分。证明：(1)(A1∩B)∪(A1∩B)∪…∪(An∪B)=A∩B=A∩B∵{A1,A2,…,An}是集合A的划分∴A1∪A2∪…∪An=

A(A1∩B)∪(A2∩B)∪…∪(An∩B)=(A1∪A2∪…∪An)∪B证明：(续)(2)Ai∩B

A∩B(1≤i≤n)∵{A1,A2,…,An}是集合A的划分∴Ai

A(1≤i≤n)∴Ai∩B

A∩B证明：(续)(3)(Ai∩B)∩(Aj∩B)=φ(i≠j)∵{A1,A2,…,An}是集合A的划分∴Ai∩Aj=φ(i≠j)∴(Ai∩B)∩(Aj∩B)=Ai∩Aj∩B=φ∩B=φ 综上：{A1∩B,A2∩B,…,An∩B}是A∩B的划分二、等价关系和等价类1、等价关系2、模m同余关系3、等价类4、商集1、等价关系等价关系R:X→X自反的对称的可传递的等价关系举例X={1,2,3,4}R={<1,1>,<1,4>,<2,2>,<2,3>,<3,2>,<3,3>,<4,1>,<4,4>}验证:R是X上的等价关系.自反的对称的可传递的等价关系2、模m同余关系模m同余关系是一个典型的等价关系。m

I+x,y,tI,若x-y=tmx模m等价于yx≡y(modm)x除m与y除m所得余数相同举例：模4同余关系∵0、4、8、…、4k＋4除4所得余数均为0，∴0≡4(mod4)≡8(mod4)≡…≡4k(mod4)∵1、5、9、…、4k＋1除4所得余数均为1，∴1≡5(mod4)≡9(mod4)≡…≡(4k＋1)(mod4)∵2、6、10、…、4k＋2除4所得余数均为2，∴2≡6(mod4)≡10(mod4)≡…≡(4k＋2)(mod4)∵3、7、11、…、4k＋3除4所得余数均为3，∴3≡7(mod4)≡11(mod4)≡…≡(4k＋3)(mod4)举例：模4同余关系(续)整数集合I{…-4,0,4,8,…,4k,…}{…-3,1,5,9,…,4k+1,…}{…-2,2,6,10,…,4k+2,…}{…-1,3,7,11,…,4k+3,…}I1I2I3I4子集内的任何两个元素均有模4同余关系S={I1,I2,I3,I4}整数集合I的一个划分证明：模m同余关系是等价关系（1）自反性：(a≡a(modm))对任意的元素a

I，均有：a-a=0

m0

I∴a≡a(modm)（2）对称性：a≡b(modm)

b≡a(modm)a、b

Ia≡b(modm)

a-b=tm

b-a=(-t)mt

I-t

I

b≡a(modm)证明：(续)(3)可传递性：a≡b(modm)∧b≡c(modm)

a≡c(modm)a、b、c

Ia≡b(modm)∧b≡c(modm)

(a-b=tm)t

I∧(b-c=sm)s

I

a-c=(s+t)ms+t

I

a≡c(modm)证明题举例R:A→A对称的可传递的 如果对于A中的每一个元素a，在A中也同时存在一个b，使得<a,b>

R证明：R是一个等价关系只需证明R是自反的证明对于任意的元素aA<a,a>

R对于任意的元素aA（已知）

<a,b>

R(R是对称的)

<a,b>

R∧<b,a>

R(R是可传递的)

<a,a>

R∴R是自反的3、等价类R:X→X的等价关系对于任何x∈X[x]R

X定义为:[x]R＝{y|y∈X,xRy}由x生成的R等价类由集合X中与x有等价关系R的那些元素组成的等价类举例X={1,2,3,4}R:X→XR={<1,1>,<1,4>,<4,1>,<4,4>,<2,2>,<2,3>,<3,2>,<3,3>}求：X中各元素的R等价类。[1]R＝{1,4}[2]R＝{2,3}[3]R＝{2,3}=[4]R＝{1,4}=等价类的性质(1)对任意元素x

Xx

[x]R(2)xRy[x]R[y]R＝(3)xyR[x]R[y]R∩＝φ证明：性质1∵R是等价关系∴R是自反的，即：(

x)(x

X→<x,x>

R)

由等价类的定义可知：x

[x]R证明：性质2xRy[x]R[y]R＝([x]R

[y]R,[y]R

[x]R)①对任意的z

[x]RxRz等价类定义对称性zRx已知xRyzRx∧xRy可传递性zRy对称性yRz

z

[y]R等价类定义[x]R

[y]R同理:[y]R

[x]R证明：性质3反证法：假设：xyR但[x]R∩[y]R

≠φ则至少有一个元素z

[x]R∩[y]R

z

[x]R∧z

[y]R等价类定义xRz∧yRz对称性xRz∧zRy可传递性

xRy与假设矛盾∴结论成立由等价类的性质(2)(3)可知对任意的x,y

X给定集合X上的等价关系R或者[x]R＝[y]R或者[x]R∩[y]R

＝φ由R可以确定集合X上的一个划分定理则R的等价类集合是X的一个划分R:X→X的等价关系非空集合{[x]R|x

X}定理证明 要证明{[x]R|x

X}是X的一个划分，就要证明其满足划分的三个条件：（1）[x]R

X且[x]R≠φ

（2）[x1]R∪[x2]R∪…∪[xn]R=X（3）[x]R∩

[y]R＝φ（x≠y）证明（1）对任意的x

X等价类定义

[x]R

X对任意的x

X自反性

x

[x]R

[x]R≠φ证明（2）证明[x1]R∪[x2]R∪…∪[xn]R=X[x1]R∪[x2]R∪…∪[xn]R

XX

[x1]R∪[x2]R∪…∪[xn]R[x1]R∪[x2]R∪…∪[xn]R

X对任意的xi

[x1]R∪[x2]R∪…∪[xn]Rxi

[xi]R[xi]R

XxiX[x1]R∪[x2]R∪…∪[xn]R

XX

[x1]R∪[x2]R∪…∪[xn]R对任意的xiX自反性xi

[xi]Rxi

[x1]R∪[x2]R∪…∪[xn]R[xi]R

[x1]R∪[x2]R∪…∪[xn]RX

[x1]R∪[x2]R∪…∪[xn]R证明（3）由等价类的性质(2)和(3)可知:对任意的x,y

X或者[x]R＝[y]R或者[x]R∩[y]R

＝φ{[x]R|x

X}是X的一个划分由等价关系R确定的划分举例X={1,2,3,4}R:X→XR={<1,1>,<1,4>,<4,1>,<4,4>,<2,2>,<2,3>,<3,2>,<3,3>}求：由等价关系R所确定的集合X的一个划分。[1]R=[4]R={1,4}[2]R=[3]R={2,3}S={[1]R，[2]R}={{1,4},{2,3}}划分4、商集等价关系可以构成集合的一个划分，即商集。R:A→A的等价关系非空集合R的等价类集合{[a]R|a∈A}按R去划分A的商集A/R={[a]R|a∈A}全关系所确定的划分R=X

X全关系（1）R是等价关系（2）X中的每一个元素和X上的所有元素都有R关系按R去划分X的商集X/R={X}最小划分恒等关系所确定的划分最大划分和最小划分均称为平凡划分。IX={<x,x>|x

X}（1）IX是等价关系（2）X中的每一个元素仅与自身有IX关系按IX去划分X的商集X/IX是集合X的最大划分举例设：X={1,2,3}求：按集合X上的全关系R和恒等关系IX去划分X的商集X/R和X/IX

解答R=X

X={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}

X/R={{1,2,3}}[1]R={1,2,3}=[2]R=[3]R解答IX={<1,1>,<2,2>,<3,3>}X/IX={{1},{2},{3}}[1]R={1}[2]R={2}[3]R={3}商集举例R:整数集合I上的模3同余关系R={<x,y>|x∈I∧y∈I∧x≡y(mod3)}求：按R去划分I的商集I/R。解答[0]R={…,-3,0,3,6,9,…}[1]R={…,-2,1,4,7,10,…}[2]R={…,-1,2,5,8,11,…}…=[-3]R=[0]R=[3