集合论第二课关系的概念性质与运算

第二课关系的概念、性质与运算2.1二元关系2.2关系的性质2.3关系的运算2.4关系的闭包引言•在现实生活中,集合与集合之间还存在着某种联系。•现实世界中的二元关系1，同一个集合中的二元关系：同学关系、同桌关系……2，两个不同集合之间的二元关系：师生关系、学生和选修课程的关系……•现实世界中的多元关系学生、课程和任课教师的关系形式化和非形式化的描述•形式化描述数学、精确无二义、难理解•非形式化描述自然语言、不精确、易理解2.1二元关系•定义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没有关系RR=：空关系R=AB：全关系注：由于RABR(AB)(AB)，从A到B的关系必然是AB上的关系，本节将主要研究同一集合上的关系，而不同集合间的关系只是它的一种特殊情况。•由定义2.1，得出：•1）二元关系是集合（一种特殊的集合）；•2）二元关系的元素是有序对（或序偶、有序2元组）。2.1二元关系•例：设A={1,2,3,4,5}，A上共有多少个二元关系？•AA的子集都是A上的二元关系，反过来，A上的任意二元关系都是AA的子集，因此A上的二元关系的集合正是AA的幂集，即P(AA)。•西安交通大学1998考研•解：•因为A上的二元关系R是AA的子集，|AA|=25，|P(AA)|=225•所以A上的二元关系R的个数是225。2.1二元关系•定义2.2（定义域，值域）设R是从A到B的二元关系，A的一个子集{a|存在b，使得a,bR}称为R的定义域，记为DomR。B的一个子集{b|存在a，使得a,bR}称为R的值域，记为RanR。A称为R的前域，B称为R的陪域，显然DomRA，RanRB。{|(),}ababR{|(),}baabR•例1整除关系设A={2,3,4},B={3,4,5,6,7},定义从A到B的二元关系R:a,bRa整除b。R={2,4,2,6,3,3,3,6,4,4}DomR={2,3,4},RanR={3,4,6}.•例2A={1,2,3,4}上的小于关系R:a,bRab.•R={1,2,1,3),1,4),2,3),2,4),3,4)}•练习：•A={1,2,3,4}上的小于等于关系：R’={1,1,2,2,3,3,4,4,1,2,1,3,1,4,2,3,2,4,3,4}•A={1,2,3,4}上的不等关系:R”={1,2,1,3,1,4,2,3,2,4,3,4,2,1,3,1,4,1,3,2,4,2,4,3}2.1二元关系•定义2.3（n元关系）设A1,……,An是n个任意集合，定义A1×……×An的子集R为A1,……,An(之间)的n元关系。当A1=……=An时，R称为A上的n元关系。2.2关系的性质•例2.1：整数集上的关系–此关系有一个明显的特点：若a,b之间有关系，当b,c之间也有同样关系时，这一关系就会传递到a,c之间，因此将这种特点称为传递性。•例2.2：浙科院14级学生集合上的“入学分数”关系R–任取浙科院14级学生x，y和z，若x,y∈R（即x入学分数低于y的），y,z∈R，必定可以推出x,z∈R，因此R具有传递性。•定义2.4称二元关系R是传递的，当且仅当对任意a,b,c，若aRb且bRc，则aRc。–定义的核心是一个推论命题：“若aRb且bRc，则aRc”，其中“aRb且bRc”是前提，aRc”是结论。“若…则…”表示从前提到结论的推论关系。这类命题的准确涵义是什么？–请判断以下推论命题是不是真的。•i：若32，则3+12+1•ii：若雪是白的，则太阳从东方升起•iii:若水被加热到100℃，则其会沸腾（标准大气压）–命题iii为真是毫无异议的。下面就从它入手对推论命题进行分析。•若水被加热到100℃，则其会沸腾–因果推论：前提和结论之间有内在的因果关系–在形式上（只考虑前提和结论的真假而非内容）有明显特点：•水被加热到100℃时（前提真），必然会沸腾（结论真），推论为真。•水没被加热到100℃时（前提假），并不妨害“若水被加热到100℃，则其会沸腾”的正确性，因此推论也为真。•概括为性质P：或者前提为假，或者前提为真且结论为真•这是一个可以形式地检验的性质：任给一“若A则B”推论，先检查A的真假，为假时，已经符合P，为真时，再检查B的真假，若也为真，则符合P，否则不符合。–形式推论：符合性质P的推论。非形式推论：前提真，并且结论假因果推论必为形式推论，非形式推论必非因果推论–数学中使用的“推论”，都是形式推论，而未必是因果推论•只要前提为真，从形式推论得出的结果一定为真，如从雪是白的推出太阳东升，结果没有错。至于这样的推论是否有意义，要靠人来把握。•没有人会从假命题出发进行任何严肃的推论，因此“若32，则3+12+1”这样的形式推论是无害的。•设A={1,2,3}，R是A上的二元关系，判断如下R是否具有传递性：–R={1,3,3,2,1,2}–R={1,2,2,3}–R={1,2}–R=•设A是你家的男孩集合，R是A上的兄弟关系，判断如下情形时R是否具有传递性：–你家共有三个男孩：你哥、你、你弟–你家共有两个男孩：你哥、你–你家只有一个男孩：你•以下关系是否传递？父子关系、朋友关系、整数不等关系。•例4：判断A={1,2,3,4}上的以下关系是否传递。R1={1,2,2,3,1,3}是传递的；R2={1,2,1,3}是传递的；R3={1,2}是传递的；R4={1,2,2,3}不是传递的；如果在A上的二元关系R中，存在aRb且bRc，但a,cR，则R不是传递的；否则R是传递的。A上的二元关系R，或者是传递的，或者不是传递的（非传递）。以正难则反思想理解关系传递性•通过命题的双否表述来判断命题是否成立。例如：“你是大学生”，其双否表述为“你并非不是大学生”。•传递性的正面定义是：任取a,b,cA，如果aRb且bRc，必有aRc，则称R是传递的。请以双否方式表述同样含义•首先，该命题的相反表述：存在a,b,cA，aRb且bRc，但并非aRc。对这种取反的方式，举例:任取大学生x，如果x学计算机专业，则x需要学离散反义：存在大学生x，x学计算机专业，但x不必学离散•然后前面加一个并非或不，反义的反义便回到原义。例：不存在大学生x，x学计算机但不学离散传递性双否表述：不存在a,b,cA，aRb且bRc，但并非aRc也就是不存在a,b,cA，aRb，bRc，且并非aRc以此来分析例4：R2={1,2,1,3}传递吗？R3={1,2}呢R4={1,2,2,3}呢•例5.下面的二元关系哪个是传递的？（）•A)父子关系•B)朋友关系•C)集合的包含关系•D)实数的不等关系•/*重庆大学1998年考研试题*/2.2关系的性质•定义2.4(关系的其它性质)设R是集合A上的二元关系。(1)如果任取aA，有aRa，则称R是自反的。(2)如果任取aA，有a,aR，则称R是反自反的。注意反自反不是非自反，请根据(1)给出非自反的定义。存在aA，并非aRa。(3)任取a,bA，如果aRb必有bRa，则称R是对称的。(4)任取a,bA，如果aRb且bRa，必有a=b，则称R是反对称的。注意反对称不是非对称。非对称的涵义是：存在a,bA，aRb，且并非bRa。•例6：自反与反自反•自反：小于等于关系•反自反：小于关系•设A={1,2,3,4}上的关系R={1,1,1,2},则R既不是自反，也不是反自反的；所以，A上的二元关系R可以既不是自反的，也不是反自反的。•例7：对称与反对称•对称：自然数集N上的不等关系•反对称：自然数集N上的小于关系•A={1,2,3,4}上的关系R={2,1,1,2,1,3},则R既不是对称，也不是反对称；所以，A上的二元关系R可以既不是对称，也不是反对称以正难则反思想理解关系反对称•根据命题的逆否表述来判断命题是否成立。例：若你学计算机专业，则你必学离散。逆否表述是：若你不学离散，则你一定不是学计算机专业的。–正面表述：任取a,bA，如果aRb且bRa，必有a=b，则称R是反对称的。–逆否表述：如果ab，则aRb和bRa不同时成立–逆否表述一：如果ab且aRb，必有b,aR。–逆否表述二：如果ab且bRa，必有a,bR。•逆否等价性：若命题A成立，则命题B成立等价于：若命题B不成立，则命题A不成立。用反证法很容易证这种等价性。左推出：假设若命题B不成立，但命题A成立，导出矛盾。右推出：…•应用逆否定义判断关系的反对称性–前述例7：–自然数集N上的关系，是反对称的–用正面定义：是反对称的当且仅当任取a,bN，若ab且ba，必有a=b。由于不可能有ab且ba的情况，似乎难以根据正面定义来判断。怎么办？–正难则反！逆否定义：是反对称的当且仅当任取a,bN，若ab，必有ab或ba。由此就可以很明确地得出结论：是反对称的！•例8集合A的幂集P(A)上的包含关系，具有哪些基本性质？•自反，反对称，传递2.2关系的性质•定义2.5.1（关系矩阵）设A和B是两个有限集A={a1,……,am}，B={b1,……,bn}，R是从A到B的二元关系，称mn阶矩阵MR=(mij)为R的关系矩阵，其中若ai,bjR，mij=1若ai,bjR，mij=0•例9整除关系的关系矩阵•A={2,3,4},B={3,4,5,6,7}010101001001000RM2.2关系的性质•定义2.5.2（关系图）设A={a1,……,an}，R是A上的二元关系。A中每个元素ai用一个点表示，称该点为顶点ai。如果aiRaj，则从顶点ai到顶点aj存在一条有向弧。如果aiRai，则从顶点ai到顶点ai存在一条封闭有向弧（有向环）。以这种方式来表示R关系的图形，称为R的关系图。2.3关系的运算•定义2.6（关系的运算）设R1和R2是从A到B的两个二元关系，则R1R2、R1R2、R1-R2、Ř1也是从A到B的二元关系，其含义是：任取aA，bB，a(R1R2)baR1b或aR2b；a(R1R2)baR1b且aR2b；a(R1-R2)baR1b且(a,b)R2;aŘ1b(a,b)(AB)-R1。2.3关系的运算——逆运算•定义2.7（逆关系）设R是从A到B的二元关系，则从B到A的二元关系R-1定义为R-1={b,a|a,bR}，称R-1为R的逆关系。•练习：•写出R={1,2,3,4,1,3}的逆关系2.3关系的运算•定理2.1（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-1°A-1；（5）-1=；（6）(Ř)-1=;（7）(R1-R2)-1=R1-1-R2-1；（8）若R1R2，则R1-1R2-1。1()R证明方法1.证明两个关系相等，因为关系是集合，可采用证明集合相等的方法（基本法或公式法）证明关系相等。例如用基本法：任取a,bAa,b左式a,b右式;则左式右式；a,b右式a,b左式;则右式左式；则左式=右式。2.证明关系满足某一性质根据该性质的定义进行求证。例如，要证明集合A上的二元关系R是自反的，就是证明对于任意的aA，a,aR。证明两个关系相等•(3)基本法证明：•a,b(R1R2)-1b,a(R1R2)b,aR1且b,aR2