集合的概念和性质,以及集合之间的运算 集合{所有课程全体}和集合{所有教室}这两个集合之间就存在着某种联系。 例：A={a,b,c}为学生集合，B={x,y,z,w}为课程集合，则笛卡儿积A×B就是学生与课程所组成的有序对全体。 A×B={(a,x),(a,y),(a,z),(a,w),(b,x),(b,y),(b,z), (b,w),(c,x),(c,y),(c,z),(c,w)} 若(a,x)表示学生a选修课程x，则当a,b,c三个学生选定课程，其情况是： (a,y),(a,w),(b,x),(b,y),(b,w)，而c什么课也没选， R={(a,y),(a,w),(b,x),(b,y),(b,w)} 反映了学生与课程的联系。 RA×B,即R是A×B 的子集。 集合A到集合B的关系。

第二章 关系 2.1 二元关系

定义 2.2:设R是从A到B的二元关系,A的一个子集{a|存在b, 使得(a,b)R}称为R的定义域,记为Dom R。B的一个子集{b|存在a,使得(a,b)R}称为R的值域,记为Ran R。A称为R的前域,B称为R的陪域,并且Dom RA,Ran RB。 例:A={1,3,5,7},B={0,2,4,6},定义关系R:(a,b)R当且仅当a<b 关系还可以用表格表示 R={(1,2),(1,4),(1,6),(3,4), (3,6),(5,6)}

A={1,2,3,4},定义A上二元关系:(a,b)R当且仅当(a-b)/3为整数。称为模3同余关系。 R={(a,b)|(a-b)/3为整数，a,bA}={(1,1), (2,2),(3,3), (4,4),(1,4),(4,1)} Dom R=Ran R=A。 进一步可定义整数集上的模r同余关系： {(a,b)|(a-b)/r为整数,a、bZ,rZ+} 定义 2.3：设A1,A2,…An是n个任意集合,定义A1×A2×…×An的子集R为A1,A2,…An的n元关系,当A1=A2=…=An时,R称为A上的n元关系。

2.2关系的性质 定义2.4：设R是集合A上的二元关系。 (1)自反：如果对任意aA,有aRa,则称R是自反的。 对于自反,必须是对于每个xA,都去检验是否有xRx。

(2)反自反：如果对任意aA,有(a,a)R ,则称R是反自反的。

思考：非空集合A上的空关系是否自反？反自反？ (3)对称：对任意a,bA ,如果aRb必有bRa , 则称R是对称的。 不是自反的，不一定反自反 不是反自反的，也不一定是自反的。 R3={(1,2),(3,2)} 是A上的反自反关系 思考：非空集合A上的空关系是否自反？反自反？ (3)对称：对任意a,bA ,如果aRb必有bRa , 则称R是对称的。 A={1,2,3,4} S1={(1,2),(2,1),(1,3),(3,1)} 对称 S2={(1,2),(2,1),(1,3)} 因为(1,3)S2,而(3,1)S2, 所以S2不是对称的 S3={(1,2),(2,1),(3,3)} 对称

(4)对任意a,bA,如果aRb且bRa,必有a=b,则称R是反对称的。 该定义实际上表明：当ab时，若有(a,b)R,则(b,a)R。 不是对称，不一定是反对称的 不是反对称的，也不一定是对称的。 可以既是对称的，又是反对称的

(5)对任意a,b,cA, 如果aRb且bRc,必有aRc , 则称R是传递的。

例：A上的非空关系R是对称的和反自反的，则R不是传递的。 注意，当导出(a,a)R时，千万不能说R自反。 因为自反的要求是：如果对任意aA,有aRa。

A到B的关系是A×B的子集。 关系的表示，可以用集合的表示方法 对于有限集, 关系还可以用矩阵或图形来表示 定义 2.5：设A和B是两个有限集A={a1,a2,…, am},B={b1,b2,…,bn}，R是从A到B的二元关系,称m×n阶矩阵MR=(mi,j)为R的关系矩阵,其中 当A=B时,A上的二元关系R可以用方阵来表示。

例:A={1,2,3,4}上模3同余关系R={(1,1),(2,2),(3,3), (4,4),(1,4),(4,1)},其关系矩阵为

例：A={2,3,4},B={1,3,5,7},A到B的<关系R={(2,3),(2,5), (2,7),(3,5),(3,7),(4,5),(4,7)},其关系矩阵为 MR怎样表示？ 规定MR上方B，左方为A,此时R与MR唯一对应。

设R是A上的二元关系, 若R是自反的,则MR中的对角线元素均为1 若R是反自反的,则MR中的对角线元素均为 0。 若R是对称的,则MR是对称矩阵。 若R是反对称的,则在MR中对于i<j, 由mij=1可推出mji=0。

集合A到集合B的二元关系个数 集合A到集合B的二元关系是集合A×B的子集，因此应考察A×B有多少个不同的子集，也就是考察A×B的幂集的元素个数。 因为|A×B|=|B||A|,故|P(A×B)|=2|A||B|，因此集合A到集合B的二元关系个数是2|A||B|

A上的二元关系个数有多少个？ 设|A|=n，则A上的二元关系个数有2n2 A上有多少个自反关系？ A={a1,a2,, an} A×A=? 用矩阵形式表示：

自反关系一定包含{(a1,a1), (a2,a2) ,, (an,an)}, 余下的共有n2-n个元素，可组成2n2 -n个不同的关系。 故不同的自反关系有2n2 -n个。

有限集A上的二元关系除用方阵表示外, 还可用关系图来表示。这种图称为有向图。 设A={ a1,a2,…,an},R是A上的二元关系。A中每个元素ai用一个点表示, 称该点为顶点ai。如果aiRaj,则画一条从顶点ai到顶点aj的带箭头的线, 称该线为弧。如果aiRai,则画一条从顶点ai到顶点ai的带箭头的封闭弧, 称该弧为自环。对于关系R中每个有序对都可对应地画一条带箭头的弧, 从而得到关系R的图形,称为R关系图。

例:设A={1, 2, 3, 4, 5},A上的模3 同余关系R={(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(4,1),(2,5), (5,2)},画出它的关系图

A到B的关系是A×B的子集,即关系也是一个集合,因此有关集合的并、交、差、补运算以及相应的性质同样适用于关系。 其中补运算 逆运算和复合运算

2.3关系的运算 一、逆运算 R={(a,y),(a,w),(b,x),(b,y),(b,w)}反映了学生选课情况 要求了解课程被选修情况。 {(x,b),(y,a),(y,b),(w,a),(w,b)} 定义 2.7：设R是从A到B的二元关系,则从B到A的二元关系记为R-1,定义为：R-1 ={(b,a)|(a,b)R}称为R的逆关系。 例如实数集上“<”关系的逆关系是“>”关系。 R={(1,2),(2,3),(1,3)} 则R-1={(2,1),(3,2),(3,1)}

定理 2.1：设R,R1,R2是从A到B的二元关系, 则 (1)(R-1)-1=R; (2)(R1∪R2)-1=R1-1∪R2-1; (3)(R1∩R2)-1=R1-1∩R2-1; (4)(A×B)-1=B×A; (5)-1=; (7)(R1-R2)-1=R1-1-R2-1; (8)若R1R2则R1-1R2-1。

(8)若R1R2则R1-1R2-1。

定理 2.2：设R是A上的二元关系,则R是对称的当且仅当R=R-1。 对任意(a,b)R,目标是(b,a)R

二、复合运算 定义 2.8：设R1是从A到B的二元关系,R2是从B到C的二元关系, 则从A到C的二元关系记为R1R2,定义为：R1R2={(a,c)|aA, cC, 且存在bB使(a,b)R1, (b,c)R2}，称为R1和R2的复合关系。 注意:(1)R1和R2复合的前提是: R1是从A到B的二元关系,R2是从B到C的二元关系 (2)复合运算不满足交换律

R1={(a1,b1), (a2,b3), (a1,b2)} R2={(b4,a1), (b4,c1), (b2,a2), (b3,c2)} R1R2={(a1,a2), (a2,c2)} R2R1={(b4,b1), (b4,b2), (b2,b3)} R1R2 R2R1 结合律是否成立? 即对于R1A×B, R2B×C, R3C×D 是否有R1(R2R3)=(R1R2)R3 它们都是A×D的子集.

对任意(a,d)R1(R2R3),目标是证明(a,d)(R1R2)R3, R1(R2R3)(R1R2)R3 类似可以证明(R1R2)R3R1(R2R3) 因此有R1(R2R3)=(R1R2)R3 定理 2.3：R1是从A到B的二元关系,R2是从B到C的二元关系,R3是从C到D的二元关系,则有R1(R2R3)=(R1R2)R3(结合律)

三、幂运算 设R是A上的一个二元关系, RR记为R2,RRR记为R3,… 定义 2.9:设R是A上的二元关系,nN,R的n次幂记为Rn,定义如下： (1)R0是A上的恒等关系(即R0={(a,a)|aA}),记为IA,又R1=R; (2)Rn+1=RnR。

定理 2.4:设R是A上的二元关系,设m,nN, 则 (1)RmRn=Rm+n (2)(Rm)n=Rmn 证明留作习题, 用归纳法证明。 由关系的并, 交, 逆和复合运算得到新的关系都可以用关系矩阵来表示。

A={a1,a2,,an},B={b1,b2,,bm} 关系R1和R2都是A到B的二元关系 MR1=(xij), MR2=(yij) MR1∪R2=(xijyij) MR1∩R2=(xijyij)  0 1  0 1 0 0 1 0 0 0 1 1 1 1 0 1

例:A={2,3,4},B={1,3,5,7} R1={(2,3),(2,5),(2,7),(3,5),(3,7),(4,5),(4,7)} R2={(2,5),(3,3),(4,1),(4,7)}

R的逆关系R-1的关系矩阵MR-1=MRT,MRT是MR的转置。

A={a1,a2,,an},B={b1,b2,,bm}, C={c1,c2,,cr}, R1是A到B的二元关系, 其关系矩阵为MR1=(xij)mn,R2是B到C的二元关系, 其关系矩阵为MR2=(yij)nr,则R1和R2的复合关系R1R2的关系矩阵为:

作业:p41-44 2(2),4,5,7,9(2),18(1)