资源描述：
《离散数学教案设计-第二部分-关系》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第二章关系§5关系及其表示法一、集合的笛卡尔积首先引入有序对的概念。定义5.1两个元素a,b组成二元组，若它们有次序之别，称为二元有序组，或有序对,记为a,b>,称8为第一分量，b为第一分量.若aHb时，Ho定义5.2给定两个有序对〈x,y>和〈u,v>o当且仅当x二u和y二v时，有序对和相等，亦即=iff(x=u)a(y=v)可将有序对推广到n元有序组，它的第一分量是(旷1)元有序组，并记为«X1,X2,…，Xn1>,Xn>,或记为3,X2,…，Xn-1,X
2、n>□类似地定义两个“元有序组相等:=iff(xl=yl)a(x2=y2)(xnT二ynT)a(xn二yn)下面将使用有序对和无序对分别定义笛卡儿积。定义5.3给定集合A和B,若有序对的第一分量是A的元素，第二分量是B的元素，所有这些有序对的集合，称为A和B的笛卡尔积，记为AxB,AxB={
3、xwA/ywB}定理5.1任给集合A,B和C,则①Ax(BUC)=(AxB)U(AxC)②Ax(BHC)=(AxB)Cl(AxC)③(AUB)
4、xC=(AxC)U(BxC)④(AAB)xC=(AxC)A(BxC)笛卡尔积的概念可以推广到n个集合A1,A2,…,An的笛卡尔积，它可表成：Ai=(AlxA2x***xAn-l)xAn,nM2。用归纳法不难证明，若Ai(lWiWn)是有穷集合，贝iJ
5、AlxA2x-xAn
6、=
7、Al
8、・
9、A2
10、—
11、An
12、o二、关系定义5.4给定任意集合A和B,若RgAxB,则称R为从A到B的二元关系，特别在A二B时，称R为A上的二元关系。可见,R是有序对的集合。若eR,则也表为xRy,即〈x,y>wRoxRy。若R=0,则称
13、R为A到B上空关系；若R二AxB,称R为A到B上全域关系。特别当A二B吋，称0为A上空关系，称R二AxA为A上的全域关系。称R二{〈x,x>
14、xeA}为A上的恒等关系，记为iAonn类似地可定义n元关系。若S匸x人，则称S为xA上的n元关系。特别A1二A2二…二Ani=l/=1时，称S%A_t的n兀关系。例5.1设A={1,2,3,4},B={5,6}关系R定义如下：eR<=>a,<1,6>,<2,5>,<2,6><3,5>,<3,6><1,5>,<1,6><4,5>,<4,6>}例5
15、.2设A={0,1,2,3,4,5,6,7},在A上定义关系RcAxA如下：eR<=>2
16、(x-y)略解关系R也可以用隐式表示：R={2(x-y)JBLx或wRox三y(mod2)例5.3设RxR上的关系R定义如下：7?={
17、x2+y2例5.4P25例5.5P25§6二元关系与映射一、二元关系R的定义域、值域和域定义6.1令RcAxB,且D(R)={x
18、(3y)(xRy)}R(R)={y
19、(3x)(xRy)}F(R)=D(R)+R(R)则称D(R)、R(R)和F(R)分别是二
20、元关系R的定义域、值域和域。显然D(R)cA,R(R)yB。二、逆运算定义6.2设R是从A到B的二元关系，由关系R得到一个新的从B到A的关系,记为旷，称旷为R的逆运算，亦称旷为R的逆关系。形式地表为：Rl=«y,x>
21、wR}或者xRyoyR由定义可知,0=0,(AxB)*=BxA例6.1实数集R上的“<”关系，其逆关系是关系的逆关系是Y”关系。例6.2实数集R上的“工”关系，其逆关系是“工”，而它的补关系是“二”关系。例6.3整数集Z上的“整除”关系，其逆关系是“倍数”关系。例6.4设集合A={1,2,3},
22、B={aM，R^AxB定义如下：/?={,<2,Z?>,<3,c?>}其逆关系Rj={,,vc,3>}例6.5(P28)定理6.1令R,ScAxB,贝I」①(Rj—R②R=R③(RUS)']=R*US④(Rns)_1=rlns⑤@(R-S)'l=R-S1⑦0—0®(AxBYl=BxA⑨RuSnRtS1⑨RqSu>R^S三、复合关系定义6.3设R是从A到B的关系，S是从B到C的关系。经过对R和S实行复合(或合成)运算“o”，得到了一个新的从A到C的关系，记为RoS,也称RoS为关系R和S的
23、复合(或合成)关系；或称RoS为R和S的复合运算。形式地表为：RoS={
24、(3b)(bwB/aRb/bSc)}例6.6设X二Y二Z二N,RgNxN,S匚NxN；/?={<1,2>,<2,3>,<3,4>}5={<4,3>,<2,4>,<1,3>}则RS={vl,4>,<3,3>}S/?={<4,4>,<1,4>}例6
