离散数学二元关系与运算

离散数学二元关系与运算第1页，课件共60页，创作于2023年2月1.二元有序组：由两个元素x和y按一定顺序排成二元组，记作：<x，y>。§4.1二元关系的概念如：平面直角坐标系中点的坐标一、二元关系的概念第2页，课件共60页，创作于2023年2月二元有序组的性质(1)当x

y时，<x，y><y，x>(2)<x，y>=<u，v>，当且仅当x=u，y=v(1)、(2)说明有序组区别于集合n元有序组：由n个元素x1，x2，…，xn，按一定顺序排成的n元组，记作：(x1，x2，…，xn)。第3页，课件共60页，创作于2023年2月2.一种新的集合运算–––积运算：设A、B为两集合，用A中元素为第一元素，B中元素作为第二元素构成的二元有序组的全体叫做A和B的笛卡儿积。记作：A

B符号化：A

B={<x,y>|xA

yB}第4页，课件共60页，创作于2023年2月例4.1

设A={a,b}，B={0,1,2}，求AB，BA解：根据笛卡儿积的定义知A

B={<a,0>,<a,1>,<a,2>,}B

A={<0,a>,<0,b>,}一般地：如果|A|=m，|B|=n，则|AB|=|BA|=m

n<b,0>,<b,1>,<b,2><1,a>,<1,b>,<2,a>,<2,b>第5页，课件共60页，创作于2023年2月积运算的性质(1)若A，B中有一个空集，则笛卡儿积是空集，即：

B=A

=(2)当AB，且A，B都不是空集时，有ABBA

(3)当A，B，C都不是空集时，有(AB)CA(BC)因为(AB)C中的元素<<x,y>,z>，而A(BC)中的元素为<x,<y,z>>。第6页，课件共60页，创作于2023年2月(4)A(B∪C)=(AB)∪(AC)(对∪的分配律)(B∪C)A=(BA)∪(CA)A(B∩C)=(AB)∩(AC)(B∩C)A=(BA)∩(CA)我们证明：A(B∪C)=(AB)∪(AC)(?)(?)(?)第7页，课件共60页，创作于2023年2月证明思想要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。一般说来，最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度。第8页，课件共60页，创作于2023年2月证明：用第一种方法对于任意的<x,y>

A

(B∪C)xAy(B∪C)xA(yByC)(xAyB)(xAyC)<x,y>AB<x,y>AC<x,y>(AB)∪(AC)

A(B∪C)=(AB)∪(AC)第9页，课件共60页，创作于2023年2月例4.2

设A={1,2}，求P(A)A解：

P(A)A={，{1}，{2}，{1,2}}={<,1>，<,2>，n阶笛卡儿积：={(x1,x2,…xn)|x1A1x2A2…xnAn}A1A2…An{1,2}<{1},1>，<{1},2>，<{2},1>，<{2},2>，<{1,2},1>，<{1,2},2>}第10页，课件共60页，创作于2023年2月二元关系：如果一个集合的元素都是二元有序组，则这个集合称为一个二元关系，记作：R

。如果<x,y>R

，记作x

Ry如果<x,y>R

，记作xRy3、二元关系的数学定义第11页，课件共60页，创作于2023年2月从A到B的二元关系：设A，B为集合，A

B的任何子集所定义的二元关系叫做从A到B的二元关系。若A=B，叫做A上的二元关系；若|A|＝n，则|AA|＝n2。就是说，A上有个不同的二元关系，其中包括空关系、全域关系UA和恒等关系IA。AA的所有子集有个。第12页，课件共60页，创作于2023年2月例4.3

设A={a,b}，写出P(A)上的包含关系R

：解：

P(A)={,{a},{b}{a,b}}R={<,>,<,{a}>,<{,{b}>,<{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}第13页，课件共60页，创作于2023年2月A上关系的表示法1.关系矩阵：设A={x1,x2,…,xn)，R是A上的关系，rij

=1若xi

R

xj0若xi

Rxj(i,j=1,2,…,n)则(rij)nxn=是R的关系矩阵令：二、二元关系的表示方法第14页，课件共60页，创作于2023年2月2.关系图：以E={<xi,xj>|xiAxjAxiRxj}为有向边集组成的有向图G=<V,E>以V=A={x1,x2,…,xn}为顶点集，第15页，课件共60页，创作于2023年2月例4.4

设A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}是A上的关系，试写出R的关系矩阵并画出关系图：解：关系矩阵：0011000001001100关系图：1342第16页，课件共60页，创作于2023年2月§4.2关系的运算关系R的定义域：

domR={x|(y)<x,y>R}(即R中有序组的第一个元素构成的集合)关系R的值域：

ranR={y|(x)<x,y>R}(即R中有序组的第二个元素构成的集合)一、关系的定义域与值域第17页，课件共60页，创作于2023年2月例4.5

下列关系都是整数集Z上的关系，分别求出它们的定义域和值域：(1)R1={<x,y>|x,y

Z

xy}(2)R2={<x,y>|x,y

Z

x2+y2=1}(3)R3={<x,y>|x,y

Z

y=2x}(4)R4={<x,y>|x,y

Z

|x|=|y|=3}第18页，课件共60页，创作于2023年2月解：

domR1=ranR1=Z解：

R2={<0,1>,<0,1>,domR2=(?)ranR2=(?)(1)R1={<x,y>|x,y

Z

xy}(2)R2={<x,y>|x,y

Z

x2+y2=1}<1,0>,<1,0>}第19页，课件共60页，创作于2023年2月解：

domR3=Z，ranR3={偶数}解：

domR4=ranR4=(?)(3)R3={<x,y>|x,y

Z

y=2x}(4)R4={<x,y>|x,y

Z

|x|=|y|=3}第20页，课件共60页，创作于2023年2月二、关系的常用运算F是任意关系，F的逆F1={<x,y>|yFx}

F、G是任意两个关系，F与G的合成记作：FG={<x,y>|(z)(xGzzFy)} 关系F在集A上的限制，记作：F|

A={<x,y>|xFyxA}集A在关系F下的象F[A]=ran(F

|A)(1)逆：(2)合成：(3)限制：(4)象：第21页，课件共60页，创作于2023年2月例4.6

设F，G是N上的关系，其定义为：F={<x,y>|x,yNy=x2}G={<x,y>|x,yNy=x+1}求G1，FG，GF，F

|{1,2}，F[{1,2}]解：由定义知：G1={<y,x>|y,xNy=x+1}列出G1

中的元素就是G1={<1,0>,<2,1>,<3,2>,…,<x+1,x>,…}第22页，课件共60页，创作于2023年2月为了求F

G，可以先直观表示如下：对任何xNx

x+1=G即y=(x+1)2因此FG={<x,y>|x,yNy=(x+1)2}同理可求GF={<x,y>|(?)}(自己做！)发现F

G

G

FF

|{1,2}={<1,1>,<2,4>}F

[{1,2}]=ran(F

|{1,2})={1,4}F

Z

Z2=y第23页，课件共60页，创作于2023年2月关系运算的性质：设F、G、H、为任意关系，则有：(1)(F1)1=F(2)domF1=ranF，ranF1=domF(3)(F

G)

H=F(G

H)(4)(FG)1=G1

F1(5)F

(G∪H)=F

G∪F

H(对∪的分配律)(6)F

(G∩H)

F

G∩F

H(对∩的半分配律)(7)(G∪H)

F=GF∪H

F(8)(G∩H)

F

G

F∩H

F(?)(?)第24页，课件共60页，创作于2023年2月任取<x,y><x,y>(F

G)1<y,x>F

G(z)(<y,z>G<z,x>F)(z)(<z,y>G1<x,z>F1)<x,y>G1

F1(4)(F

G)1=G1

F1的证明：第25页，课件共60页，创作于2023年2月任取<x,y><x,y>F(G∪H)(z)(<x,z>(G∪H)<z,y>F)(z)((<x,z>G∪<x,z>H)<z,y>F)(注意对括号的顺序)(z)(<x,z>G<z,y>F>∪(<x,z>H<z,y>F))<x,y>FG∪<x,y>F

H∴F

(G∪H)=F

G∪F

H(5)F

(G∪H)=F

G∪F

H的证明：第26页，课件共60页，创作于2023年2月§4.3关系的性质R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性：xA

有<x,x>R(R是A上的关系)关系矩阵：主对角线元素全是0关系图：每个顶点都没有环反自反性：xA<x,x>R第27页，课件共60页，创作于2023年2月对称性：若<x,y>R，则<y,x>R

关系矩阵：对称阵关系图：如果两个顶点之间有边，一定是一对方向相反的边。第28页，课件共60页，创作于2023年2月反对称性：若<x,y>R且xy，则<y,x>R

关系矩阵：如果rij

=1，且ij，则rji

=0关系图：如果两个顶点之间有边，一定是只有一条有向边。第29页，课件共60页，创作于2023年2月传递性：若<x,y>R且<y,z>R，则<x,z>R

关系图：如果顶点xi到xj有边，

xj到xk有边，则从xi到xk有边第30页，课件共60页，创作于2023年2月例4.7

设A={1,2,…,10}，对于A上的关系R={<x,y>|(xy)/3I}I为整数集，问R有哪些性质？第31页，课件共60页，创作于2023年2月解：逐条性质加以验证R={<x,y>|(xy)/3I}任取A中元素x，由于(xx)/3=0，所以R是自反的；又设A中任意两个元素x,y，如果xRy，即xy可被3整除，则yx也一定可被3整除，即yRx，从而R是对称的；如果A中三个元素x，y，z满足xRy，yRz，则xy，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，从而xRz即R具有传递性。第32页，课件共60页，创作于2023年2月§4.4关系的闭包运算闭包：设RAA，自反闭包记作r(R)对称闭包记作s(R)传递闭包记作t(R)由A求r(R)，s(R)，t(R)的过程叫闭包运算。那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包；包含R而使之具有对称性质(传递性质)的最小关系，称之为R的对称(传递)闭包。一、定义第33页，课件共60页，创作于2023年2月幂运算：设RAA，kN，约定(1)R0=IA={<x,x>|xA}(2)R1=R(3)Rk+1=Rk

R显然Rm

Rn

=Rm+n

(Rm)n

=Rmn二、计算方法为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。第34页，课件共60页，创作于2023年2月闭包运算的方法：设R是A上的任一关系，则(1)r(R)

=R∪IA(2)s(R)

=R∪R(3)t(R)

=R∪R2∪R3∪…∪Rn∪…第35页，课件共60页，创作于2023年2月矩阵形式：(M为R的关系矩阵)(1)Mr=M+E(2)Ms=M+M'(M'是M的转置)(3)Mt=M+M2+M3……其中“+”均表示“逻辑加”第36页，课件共60页，创作于2023年2月例4.8

设A={a,b,c,d}，A上的关系求r(R)，s(R)和t(R)解：

r(R)=R∪IA={<a,b>,<b,c>,<c,d>,<d,c,>,<a,a>,<b,b>,<c,c>,<d,d>}R={<a,b>,<b,c>,<c,d>,<d,c>,<a,a>}=R∪{<a,a>,<b,b,><c,c>,<d,d>}三、实例第37页，课件共60页，创作于2023年2月s(R)=R∪R={<a,b>,<b,c>,<c,d>,<d,c>,<b,a>,<c,b>,<a,a>}t(R)=R∪R2∪R3∪……=R∪{<b,a>,<c,b>,<d,c>,<c,d>,<a,a>}第38页，课件共60页，创作于2023年2月而R2=R

RR3=R2

RR4=R3

R={<a,c>,<b,d><c,c>,<d,d>,<a,b>,<a,d>,<a,a>}={<a,d>,<b,c>,<c,d>,<d,c>,<a,b>,<a,c>,<a,a>}={<a,c>,<b,d>,<c,c>,<d,d>,<a,b>,<a,a>}实际上，看到当k

4时，已有R4

R∪R2∪R3故t(R)=

R∪R2∪R3={<a,b>,<b,c><c,d>,<d,c>,<a,d>,<a,c>,

<b,d>,<c,c>,<d,d>,<a,a>}第39页，课件共60页，创作于2023年2月四、闭包运算的性质设A是有限集且|A|=n，RAA，则：第40页，课件共60页，创作于2023年2月§4.6等价关系和偏序关系等价关系：集A上的关系R是自反的,对称的和传递的。等价类：

R是集A上的等价关系，对于任一aA，[a]R={x|aRx,xA}被称为a的等价类。即A中所有和a有R关系的元素的集合。一、等价关系及用途第41页，课件共60页，创作于2023年2月等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：(1)[x]且[x]A(等价类为A的子集)(2)若xRy，则[x]=[y](3)若x\Ry，则[x]∩[y]=

第42页，课件共60页，创作于2023年2月集A在等价关系R下的商集：设R为非空集A上的等价关系，以R的不交的等价类为元素的集合叫做A在R下的商集，记作A/R.即：A/R={[x]R|xA}第43页，课件共60页，创作于2023年2月集A的划分：设A是非空集合，(1)(2)中任意两个元素不交

(3)中所有元素的并集为A则为A的划分。如果存在一个A的子集族，P(A)满足以下条件：第44页，课件共60页，创作于2023年2月由等价类的性质和商集的定义可知，商集A/R是A的划分，称之为由R诱导的划分。反过来，给定A的任一划分，则A被分割成若干个划分块。若定义A上的二元关系R：x，yA且x,y属的同一块，则xRy，那么R是A上的等价关系，称之为由诱导的等价关系。集A上的等价关系与划分是一一对应的。第45页，课件共60页，创作于2023年2月例4.9

设A={1,2,3}，求出A上所有的等价关系：解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2，3，和4，具有3个划分块5。1={A}2={{1},{2,3}}，4={{3},{1,2}}，3={{2},{1,3}}，5={{1},{2},{3}}第46页，课件共60页，创作于2023年2月设对应于划分i的等价关系Ri，i=1,2,…5，则有R5={<1,1>，<2,2>，<3,3>}R1={<1,1>，<1,2>，<1,3>，R2={<1,1>，R3={<2,2>，R4={<3,3>，<2,2>，<2,1>，<2,3>，<3,3>，<3,1>，<3,2>}<2,2>，<2,3>，<3,3>，<3,2>}<1,1>，<1,3>，<3,3>，<3,1>}<2,2>，<2,1>}<1,1>，<1,2>，第47页，课件共60页，创作于2023年2月偏序关系：集A上的关系R是自反的，反对称的和传递的，记作“”，且称<A,)为偏序集。二、偏序关系及用途第48页，课件共60页，创作于2023年2月例4.10

设A={2,4,6,8}，A上关系R是通常意义下的小于或等于关系，试写出R并验证它是偏序关系。解：R={<2,2>,<2,4>,<2,6>,<2,8>,(1)自反性：(2)反对称性：(3)传递性：<8,8>}<6,6>,<6,8>,<4,4>,<4,6>,<4,8>,<2,2>,<4,4><6,6>,<8,8>均属于R对任意的<x,y>R，必有xy，当xy时，

y>x，从而<y,x>R对任意的<x,y>R，<y,z>R,由于xyyz

，所以xz，从而<x,z>R。第49页，课件共60页，创作于2023年2月例4.11

设C={{a,b},{a},{b},}，C上关系T是集合的“包含于”，试写出T，并验证它是偏序关系。解：

同例4.10类似，自己做！第50页，课件共60页，创作于2023年2月偏序集的哈斯图(1)用小圆圈表示偏序集的元素(称为结点)；(2)按每个元素在偏序中的次序从底向上列结点位置；(3)对于偏序集中任意两个元素x和y，如果xy且不存在另一个元素a，使xaay，则在x与y两结点之间划上一杠，即“|”(x在下，y在上)第51页，课件共60页，创作于2023年2月全序关系：设<A,>是偏序集，(x)(y)(xAyA(xyyx))成立，则称<A,)为全序集，这时的偏序关系叫全序关系。全序集<A,)中全部元素可以排序，它的哈斯图为一条直线。如果第52页，课件共60页，创作于2023年2月偏序集中的一些特殊元素设<A,>是偏序集，BA(1)

如果yB，使得(x)(xByx)为真，则y是B的最小元(“小于”

B中所有元)(2)

如果yB，使得(x)(xBxy)为真，则y是B的最大元(“大于”B中所有元)第53页，课件共60页，创作于2023年2月(4)

若yB，使得(x)(xBxy)，则称y是B的极大元(B中没有比y大的其他元)(5)

若yA，使得(x)(xB

xy)为真，则称y是B的上界(3)

若yB，使得(x)(xBxy)，则称y是B的极小元(B中找不到x小于y)第54页，课件共60页，创作于2023年2月(6)