复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）02/30

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

• 集合的概念和性质,以及集合之间的运算 • 集合{所有课程全体}和集合{所有教室}这两个集合 之间就存在着某种联系。 • 例：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的关系

第二章关系 21二元关系

第二章 关系 2.1 二元关系

定义21:设A和B是任意两个集合A ×B的子集R称为从A到B的二元关 系。当A=B时称R为A上的二元关系。 若(a,b)∈R则称a与b有关系R,记为 aRb°若(a,b)R则称a与b没有关系 R记为aBkb°若R=则称R为空关系。 若R=A×B,则称R为全关系 R={(a,y),(a,w),(b,x),(b,y),(b,w)} (a,y)∈R,aRy (a,x)纟R,aRx

定义 2.1: 设 A 和 B 是任意两个集合,A ×B 的子集 R 称为从 A 到 B 的二元关 系。当 A=B 时, 称 R 为 A 上的二元关系。 若(a,b)R,则称 a 与 b 有关系 R ,记为 aRb。若(a,b)R,则称 a 与 b 没有关系 R,记为 aR/b。若 R=, 则称 R 为空关系。 若 R=A×B,则称 R 为全关系。 R={(a,y),(a,w),(b,x),(b,y),(b,w)} (a,y)R,aRy. (a,x)R, aR/x

定义22:设R是从A到B的二元关系,A的 一个子集{a存在b,使得(ab)∈R}称为R的 定义域记为DomR。B的一个子集{b存 在a,使得(ab)∈R}称为R的值域记为Ran R。A称为R的筋域,B称为R的停域,并且 Dom rca, Ran rcb。 例: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)}

• 定义 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,23,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)} DomR=RanR=A。 进一步可定义整数集上的模r同余关系: {(a,b)(a-b)r为整数,a、b∈Z,r∈Z} 定义23:设A,A2,A是n个任意集合,定 义A1×A2×,An的子集R为A14A2yAn 的m元关系,当A=A2=…=A时,R称为A上的 n元关系

• 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元关系

22关系的性质 定义24:设R是集合A上的二元关系。 (1)自反:如果对任意a∈A有aRa,则称R 是自反的。 自反的定义要求是对所有的A中元素,因 此讨论自反关系,应在一给定集合下 A={1,2,3,4} R1={(1,1),(2,2),(3,3)}? R2={(1,1),(1,2,(2,2),3,3),4,4)? 对于自反,必须是对于每个x∈A,都去检验 是否有xRx

2.2关系的性质 • 定义2.4：设R是集合A上的二元关系。 • (1)自反：如果对任意aA,有aRa,则称R 是自反的。 • 自反的定义要求是对所有的A中元素，因 此讨论自反关系，应在一给定集合下 • A={1,2,3,4} • R1={(1,1),(2,2),(3,3)} ? • R2={(1,1),(1,2),(2,2),(3,3),(4,4)} ? • 对于自反,必须是对于每个xA,都去检验 是否有xRx

·(2)反自反:如果对任意a∈A,有(a,a)∈R, 则称R是反自反的。 反自反要求对任意的A中元素a,有 (a, aERo

• (2)反自反：如果对任意aA,有(a,a)R , 则称R是反自反的。 • 反 自 反要 求 对任 意的 A中元素 a， 有 (a,a)R

·不是自反的,不一定反自反 不是反自反的,也不一定是自反的。 R3={(1,2)(3,2是A上的反自反关系 思考:非空集合A上的空关系是否自反? 反自反? (3)对称:对任意a,beA,如果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不是对称的 3={(1,2(2,1)3,3)对称

• 不是自反的，不一定反自反 • 不是反自反的，也不一定是自反的。 • 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)对任意ab∈A,如果aRb且bRa,必有a=b,则称 R是反对称的。 该定义实际上表明:当a≠b时,若有(a,b)∈R, 则(b,a)gR。 不是对称,不一定是反对称的 不是反对称的,也不一定是对称的。 可以既是对称的,又是反对称的

• (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是传递的。 注意:传递要求是:只要有aRb,bRc,则必 须有aRc 但若没有aRb,bRc,当然也就不需要讨论 是否有aRc

• (5)对任意a,b,cA, 如果aRb且bRc,必有aRc , 则称R是传递的。 • 注意：传递要求是：只要有aRb,bRc,则必 须有aRc • 但若没有aRb,bRc ，当然也就不需要讨论 是否有aRc