集合论II关系的概念、性质与运算

1、第二课 关系的概念、性质与运算2.1 二元关系二元关系2.2 关系的性质关系的性质2.3 关系的运算关系的运算2.4 关系的闭包关系的闭包引言 在现实生活中, 集合与集合之间还存在着某种联系。 现实世界中的二元关系1，同一个集合中的二元关系：同学关系、同桌关系2，两个不同集合之间的二元关系：师生关系、学生和选修课程的关系 现实世界中的多元关系学生、课程和任课教师的关系形式化和非形式化的描述 形式化描述数学、精确无二义、难理解 非形式化描述自然语言、不精确、易理解2.1 二元关系 定义2.1（二元关系） 设A和B是任意两个集合，将AB的子集R称为从A到B的二元关系。A=B时，称R为A上的二元关系

2、。若R，则称a与b有关系R，记为aRb。 术语：R：a与b没有关系RR=：空关系R=AB：全关系注：由于R AB R (A B) (A B) ，从A到B的关系必然是A B上的关系，本节将主要研究同一集合上的关系，而不同集合间的关系只是它的一种特殊情况。 由定义2.1，得出： 1）二元关系是集合（一种特殊的集合）； 2）二元关系的元素是有序对（或序偶、有序2元组）。2.1 二元关系 例：设A=1, 2, 3, 4, 5，A上共有多少个二元关系？ AA的子集都是A上的二元关系，反过来， A上的任意二元关系都是AA的子集，因此A上的二元关系的集合正是AA的幂集，即P(AA)。 西安交通大学1998考

3、研 解： 因为A上的二元关系R是AA的子集，|AA|=25，|P(AA)|=225 所以A上的二元关系R的个数是225。 2.1 二元关系 定义2.2（定义域，值域） 设R是从A到B的二元关系，A的一个子集 a|存在b，使得R称为R的定义域，记为Dom R。B的一个子集 b|存在a，使得 R称为R的值域，记为Ran R。 A称为R的前域，B称为R的陪域，显然Dom RA，Ran RB。 |(),aba bR |(),baa bR 例1 整除关系 设A=2, 3, 4, B=3, 4, 5, 6, 7, 定义从A到B的二元关系R: Ra整除b。 R=, , , , Dom R=2, 3, 4,

4、Ran R=3, 4, 6. 例2 A=1, 2, 3, 4上的小于关系R: R ab. R=, 1, 3), 1, 4), 2, 3), 2, 4), 3, 4) 练习： A=1, 2, 3, 4上的小于等于关系：R=, , , , , , , , , A=1, 2, 3, 4上的不等关系: R”=, , , , , , , , , , , 2.1 二元关系 定义2.3 （n元关系） 设A1,An是n个任意集合，定义A1An的子集R为A1,An(之间)的n元关系。 当A1=An时，R称为A上的n元关系。2.2 关系的性质 例3.1：整数集上的关系 此关系最主要的特点是什么? 任取整数a,b,

5、c，若ab且bc，必定有ac。这种特点可以概括为传递性传递性（原本a,b之间有关系，当b,c之间也有同样关系时，这一关系就会传递到a,c之间）。 “若ab且bc，必定有ac”是因为在”ab且bc”和“ac”之间有因果推论关系，这种关系来源于“小于”的语义。故上述传递性的确切称谓是语义传递性语义传递性。 例3.2：浙科院14级学生集合上的“入学分数”关系R R是否具有语义传递性？ 任取浙科院14级学生x，y和z，若R（即x入学分数低于y的）， R，必定可以推出R。这是一个因果推论，因此R具有语义传递性。 例3.3：A=a,b,c上的关系R=, R是不是语义传递的？ 不是。这就需要给出一个反例。

6、由于A和R是抽象的，需要给出它们的一个具体的解释，使得R不具有语义传递性。 假设a,b,c表示3个学生，而 R表示在某次考试中x的分数高于y（这当然要求两人都未缺考从而都有成绩）。假设共有3次考试。第1次a的分数高于b, 而c缺考；第2次b的分数高于c，而a缺考；第3次a的分数高于c，而b缺考。 由第1次grade(a)grade(b)， R；由第2次grade(b)grade(c) ， R；由第3次grade(a) grade(c) ， R；R中不再有别的有序对。 但是，在“ R且 R”和“ R”之间没有因果关系。以上述解释为例，没有任何一次考试同时出现a分数高于b，且b分数高于c的情况，因

7、此无法仅凭因果推论得出“在某次考试中a分数高于c”。 继续例3.3 但是在形式上，对任意x,y,z A，若 R且 R，则R。这是可以检验的。 对任意x,y,z A， “ R且 R”的情况只有一种，即 R且 R ，此时我们查看一下R，发现也在其中，这就说明：对任意x,y,z A，若 R且 R，则R。 在前提：“ R且 R”和结论：“R”之间，虽然不具有必然的因果推论关系，但是具有可检验的形式推论关系（形式检验的方法是：先看前提是否成立，若其成立，检查结论是否成立，若结论也成立，则形式推论关系成立）。 对任意x,y,z A， 根据“ R且 R” 都可以形式地推论出“R”，这也是一种传递性。对于关系

8、的这种特点，我们将其定义为一个新的概念形式传递性形式传递性。 继续例3.3 由于集合论中的关系是形式定义的（只有形式描述不方便的时候，才给出语义描述，例如整数集上的小于关系），通常无法获得关系的语义信息，因此无法判断其语义传递性，而只能验证其有没有形式传递性。 但是，形式传递性是语义传递的抽象（一个关系是语义传递的，一定是形式传递的，反之未必）或推广，对形式传递性的一切研究，所得结论都完全适用于语义传递性。 综合上述两点，集合论只定义和研究形式传递性。 关于形式传递性的定义，还有一点不清楚的地方：在对任意x,y,z A检验从“,都 R”到“ R”的形式推论关系的时候，若发现根本不存在,都 R的

9、情况，R的形式传递性应如何定义？也就是说，是否应当认为R有形式传递性？ 既然形式传递是语义传递的抽象，我们应该首先对语义传递的同样情形进行考查，再来决定如何完成抽象。 例3.4：2,3上的关系 这个关系是不是语义传递的？ 写出这个关系 此关系中找不到ab且bc，但仍是语义传递的 例3.5：hou，zhu，yang上的“入学分数”关系S，设hou和zhu分数相同，都低于yang 这个关系在语义上是不是传递的？ 写出这个关系 S=, 找不到R且R，但这个关系在语义上仍然是传递的 由于形式传递是语义传递的抽象，若不存在,都 R的情况，也应当认为R具有形式传递性。 定义2.4（关系的传递性） 设R是集

10、合A上的二元关系，任取a, b, cA，若aRb且bRc，必有aRc，则称R是传递的。 这种传递性指的是形式传递性，不要求“aRb且bRc”和“aRc”之间具有因果推论关系，但要求其形式推论关系。特别地，当“aRb且bRc”不成立时，形式推论关系成立。 任何语义上传递的关系都必然具有形式传递性 我们只研究如上定义的这种（形式）传递性，但其结论完全适用于例3.1和3.2那种“真正的、无可置疑的”传递性，即语义上的传递性。 例4：判断A=1, 2, 3, 4上的以下关系是否传递。R1=, , 是传递的；R2=, 是传递的；R3=是传递的；R4=, 不是传递的； 如果在如果在A上的二元关系上的二元关

11、系R中，存在中，存在aRb且且bRc，但，但 R，则，则R不是传递的；否则不是传递的；否则R是传递的。是传递的。 A上的二元关系上的二元关系R，或者是传递的，或者不是，或者是传递的，或者不是传递的（非传递）。传递的（非传递）。以正难则反思想理解关系传递性 通过命题的双否（正难则反的一种体现）表述来判断命题是否成立。所谓双否表述，就是相反再相反，例如：你是大学生,可表述为你并非不是大学生。 传递性的正面定义是：任取a, b, cA，如果aRb且bRc，必有aRc，则称R是传递的。请以双否方式表述同样含义 首先要知道该命题的相反表述：存在a, b, cA， aRb且bRc，但是aRc不成立。对这种

12、取反的方式，举例: 任取大学生x，如果x学计算机专业，则x需要学离散反义：存在大学生x，x学计算机专业，但x不必学离散 然后前面加一个并非或不，反义的反义便回到原义。例：不存在大学生x，x学计算机但不学离散传递性双否表述：不存在a, b, cA， aRb且bRc，但aRc不成立也就是不存在a, b, cA， aRb，bRc，且 并非 aRc以此来分析例4： R2=, 传递吗？ R3= 呢 R4=, 呢 例5. 下面的二元关系哪个是传递的？（ ） A) 父子关系 B) 朋友关系 C) 集合的包含关系 D) 实数的不等关系 /*重庆大学1998年考研试题*/2.2 关系的性质 定义2.4(关系的其

13、它性质) 设R是集合A上的二元关系。(1)如果任取aA，有aRa，则称R是自反的。(2)如果任取aA，有R，则称R是反自反的。注意反自反不是非自反，请根据(1)给出非自反的定义。 存在a A，并非aRa。(3)任取a, bA，如果aRb必有bRa，则称R是对称的。(4)任取a, bA，如果aRb且bRa，必有a=b，则称R是反对称的。 注意反对称不是非对称。非对称的涵义是： 存在a, b A， aRb，且并非bRa。 例6：自反与反自反自反与反自反 自反：小于等于关系 反自反：小于关系设A=1, 2, 3, 4上的关系R=, , 则R既不是自反，也不是反自反的；所以，A上的二元关系R可以既不是

14、自反的，也不是反自反的。 例7：对称与反对称 对称：自然数集N上的不等关系 反对称：自然数集N上的小于关系 A=1, 2, 3, 4上的关系R=, , , 则R既不是对称，也不是反对称；所以，A上的二元关系R可以既不是对称，也不是反对称以正难则反思想理解关系反对称 根据命题的逆否（另一种正难则反）表述来判断命题是否成立。例：若你学计算机专业，则你必学离散。逆否表述是：若你不学离散，则你一定不是学计算机专业的。 正面表述：任取a, bA，如果aRb且bRa，必有a=b，则称R是反对称的。 逆否表述一：如果aRb且ab，必有R 。 逆否表述二：如果bRa且ab，必有R 。 逆否表述：如果ab，则a

15、Rb和bRa不同时成立 逆否等价性的证明：若命题A成立，则命题B成立等价于：若命题B不成立，则命题A不成立。用反证法很容易证。假设若命题B不成立，但命题A成立，导出矛盾。 应用逆否定义判断关系的反对称性 前述例7： 自然数集N上的关系，是反对称的 用正面定义： 是反对称的 当且仅当 任取a,b N，若ab且ba，必有a=b。由于不可能有ab且ba的情况，似乎难以根据正面定义来判断。怎么办？ 正难则反！ 逆否定义：b或ba。由此就可以很明确地得出结论： 是反对称的！ 例8 集合A的幂集P(A)上的包含关系，具有哪些基本性质？自反，反对称，传递2.2 关系的性质 定义2.5.1（关系矩阵） 设A和

16、B是两个有限集A=a1, , am，B=b1, , bn，R是从A到B的二元关系，称m n阶矩阵MR=(mij)为R的关系矩阵，其中若R， mij =1若R，mij =0 例9 整除关系的关系矩阵 A=2, 3, 4, B=3, 4, 5, 6, 70 1 0 1 01 0 0 1 00 1 0 0 0RM2.2 关系的性质 定义2.5.2 （关系图） 设A=a1, , an，R是A上的二元关系。A中每个元素ai用一个点表示，称该点为顶点ai 。 如果aiRaj，则从顶点ai到顶点aj存在一条有向弧。 如果aiRai，则从顶点ai到顶点ai存在一条封闭有向弧（有向环）。以这种方式来表示R关系的

17、图形，称为R的关系图。2 .3 关系的运算 定义2.6 （关系的运算） 设R1和R2是从A到B的两个二元关系，则R1R2、 R1R2 、 R1-R2、 1也是从A到B的二元关系，其含义是：任取aA，bB， a(R1R2)b aR1b或aR2b； a(R1R2)b aR1b且aR2b； a(R1-R2)b aR1b且(a, b)R2; a 1b(a,b)(AB)-R1。2 .3 关系的运算逆运算 定义2.7（逆关系） 设R是从A到B的二元关系，则从B到A的二元关系R-1定义为R-1 =|R，称R-1为R的逆关系。 练习： 写出R=,的逆关系2 .3 关系的运算 定理2.1（1）(R-1)-1=R

18、;（2）(R1R2)-1= R1-1 R2-1; （3）(R1R2)-1= R1-1 R2-1;（4） (AB)-1= B-1A-1；（5） -1=；（6）()-1= ;（7） (R1-R2)-1= R1-1-R2-1；（8）若R1R2，则R1-1 R2-1 。1()R证明方法（1）证明两个关系相等，因为关系是集合，可采用证明集合相等的方法（基本法或公式法）证明关系相等。例如用基本法：任取a,b A左式右式; 则左式右式；右式左式; 则右式左式；则左式=右式。（2）证明关系满足某一性质 根据该性质的定义进行求证。 例如，要证明集合A上的二元关系R是自反的，就是证明对于任意的aA，R。证明两个关

19、系相等 (3) 基本法证明： (R1R2)-1 (R1R2) R1且 R2 R1-1且R2-1 R1-1 R2-1 所以，(R1R2)-1= R1-1 R2-1。 (1), (2)类似, 证明见教材或参考书。 (4)类似。 (5)反证法。 设-1，则存在-1, 那么. 导致矛盾。 (6), (7), (8)基本法或公式法证明。 2 .3 关系的运算 定理2.2 R是A上的二元关系，则R是对称的R=R-1。证明：R是对称的 R=R-1：（证明两个关系相等证明两个关系相等） R, 因为R是对称的，所以R, 则R-1; 所以RR-1。同理，R-1R。则R=R-1。R=R-1 R是对称的：（证明关系满

20、足某一性质）证明关系满足某一性质）如果R, 因为R=R-1，所以R-1，则R。所以R是对称的。（根据对称的定义）（根据对称的定义）2 .3 关系的运算复合运算 定义2.8（复合关系） 设R1是从A到B的二元关系， R2是从B到C的二元关系，则从A到C的二元关系R1R2定义为 R1R2 = | aA, cC, 且 存在bB使 R1, R2称R1R2为R1和R2的复合关系。2 .3 关系的运算 定理2.3（结合律） (R1R2)R3 = R1(R2R3) 证明方法：采用基本法，证明两个关系相等。即： (R1R2)R3R1(R2R3)，则(R1R2)R3 R1(R2R3) ； R1(R2R3) (R

21、1R2)R3 ，则R1(R2R3) (R1R2)R3 。具体证明步骤见教材或参考书。 注意：关系的复合运算不满足交换律，即R1R2 R2R12 .3 关系的运算幂运算 定义2.9（幂关系） 设R是A上的二元关系，nN，R的n次幂记为Rn，定义如下： (1) R0是A上的恒等关系（即R0 = | aA），记为IA，又R1=R； (2)Rn+1= RnR。 定理2.4 (1) Rm Rn=Rm+n (2) (Rm)n= Rmn证明方法：采用归纳法进行证明 设性质为P。 归纳基础：证明P(1)为真； 归纳步骤：对每一个i1，假设P(i)为真，并且利用这一假设证明P(i+1)为真。 证明：(1) 归纳

22、基础：设n=1, 则根据幂运算的定义，RmR1= Rm+1； 归纳步骤：设n=k, Rm Rk=Rm+k成立；n=k+1时, Rm Rk+1= Rm RkR1=Rm+kR1 =Rm+k+1。 所以Rm Rn=Rm+n。 (2)归纳基础：设n=1, 则根据幂运算的定义， (Rm)1= Rm。 归纳步骤：设n=k, (Rm)k= Rmk成立；设n=k+1, (Rm)k+1= (Rm)k (Rm)=Rmk Rm= Rmk+m=Rm(k+1). 归纳证明的思想 / 思维过程 归纳基础证明P(1)为真； 根据归纳步骤，因为P(1)为真，所以P(2)为真；因为P(2)为真，所以P(3)为真；这个过程对所有

23、的自然数继续下去，于是对于任意的自然数k，P(k)为真。2 .4 关系的闭包 定义2.11（自反，对称，传递闭包） 设R是A上的二元关系，R的自反（对称，传递）闭包，记为 R，满足下列三个条件：（1）R是自反的（对称的，传递的）；（2）RR；（3）对任一自反（对称，传递关系）R”，RR”，均有RR”。现在，将R的自反、对称，传递闭包分别记为r(R)，s(R)，t(R)。2 .5 关系的闭包基本性质定理2.5 设R是A上的二元关系，则R是自反的 r(R)=R；R是对称的 s(R)=R；(1) R是传递的 t(R)=R； 证明思想1：采用基本法进行证明，以R是自反的 r(R)=R为例： R是自反的

24、 r(R)=R：因为根据r(R)的定义，r(R)是自反的，所以R是自反的； R是自反的 r(R)=R：根据r(R)的定义，Rr(R) ，需证明r(R)R; 由于RR，且R （左侧的R ）是自反的，由自反闭包的定义可知r(R)R （右侧的R ） 。 证明思想2: （证明满足某一性质）证明满足某一性质） 根据自反，对称和传递闭包定义进行证明，以R是自反的 r( R )=R: R是自反的 r( R )=R , 就是证明R符合R的自反闭包定义的3个条件: (1)R（哪个R？）是自反的；(2) RR （分别是哪个R？） ；(3)对任一自反关系R”，若R （哪个R？） R”，则R （哪个R？） R”。 r

25、( R )=R R是自反的. 定理2.6 设R1和R2是A上的二元关系，若R1R2则 r(R1) r(R2)； s(R1) s(R2)；(1)t(R1) t(R2)。证明思想：反证法：（1）假设r(R1), 但r(R2)，则xy，从而r(R1) (x, y)也是自反的；如果R1，则R2，那么r(R2)，导致矛盾，所以 R1。则r(R1) (x, y) R1，则r(R1)不是R1的自反闭包。矛盾。 r(R2)。r(R1) r(R2)。（2）,（3）证明类似。2 .5 关系的闭包 三 计算 定理2.7 r(R)=R IA证明思想：根据自反闭包定义要满足的性质进行证明。 证明：设R=RIA，所以R

26、R，而且R是自反的；假设R”是A上的自反关系并且RR”，对于R，因为R=RIA，所以R或者IA；如果R，则R”；如果IA，因为R”是自反的，所以R”，即RR”。 所以R=r(R)=RIA。 定理2.8 s(R)=RR-1证明思想：根据对称闭包定义要满足的性质进行证明。 证明：令R=RR-1。由于(RR-1)-1=RR-1 ，根据定理2.2，可知R=RR-1是对称的，且RR。假设R”是A上的对称关系，并且RR”。对于R有R或者R-1。如果R，由于RR”，那么R”；如果R-1，则R，所以R”。因为R”是对称的，所以R”。因此RR”。所以R=s(R)= RR-1。 例9 设A=a, b, c，R是A

27、上的二元关系，且R=, , ，则s(R)= 。 /*重庆大学1999考研*/ 定理2.9 t(R)=RR2R3 /*证明思想：根据传递闭包定义要满足的性质进行证明：令R=RR2R3，证明R满足传递闭包定义的3个条件。*/ 证明： /*R是传递的，即如果R, R, 则R*/ 因为R，必存在整数n，使Rn；同理，因为R，必存在整数k，使Rk；因为Rn Rk=Rn+k，所以Rn+k，所以R。 证明：（续） /* RR */ 因为R=RR2R3，所以RR。 证明：（续） /*对于传递关系R”，如果R”R, 则R”R. */ 如果a,bA, R, 则存在正整数j，使Rj, 即存在j-1个元素c1, c2,cj-1使得R, R, R. 由于R”R, 所以R”, R”, R”. 又因为R”是传递的，因此R”。由此证得R”R。由传递闭包的定义可知：R=t(R)，即t(R) =RR2R3 。 定理2.10 R是A上的二元关系，且|A|=n，则t(R)=RR2R3Rn /* 证明思想：基本法：由定理2.9可知，RR2R3Rnt(R)；只要证明对任意的k0，RkRR2R3Rn。*/ 证明：/*分而治之*/ 对于kn，必有RkRR2R3Rn 。 对于kn，若Rk，则存在元素个数为k+1的元素序列c0, c1, , ck, c0=a, ck=b,