第3 章 集合与关系 集合是数学中最基本的概念,又是数学各分支、自然科学及社会科学各 领域最普遍采用的描述工具。自从19世纪末德国数学家康托(G.Cantor)为 集合论做奠基工作以来,集合论已经成为数学中不可缺少的基本描述工具和 数学中最基本的概念之一。集合论有两种体系:一种是朴素集合论;另一种 是公理集合论。本书仅讨论朴素集合论。 3.1 集合的概念和表示法 3.1.1 集合的表示 集合是不能精确定义的基本概念。当我们讨论某一类对象时,就把这一 类对象的全体称为集合。这些对象称为集合中的元素。 例如:地球上的人。 方程x2-1=0的实数解集合。 26个英文字母的集合。 坐标平面上的点。 集合通常用大写的英文字母标记,如自然数集合N、整数集合Z、有理数 集合Q、实数集合R、复数集合C 等。用小写字母表示一个集的元素,如a, b,x,y。 表示一个集合的方法通常有如下三种。 1.枚举法 这种方法是列出集合的所有元素,元素之间用逗号隔开,并把它们用花 括号括起来。例如: A ={a,b,c,…,z} Z ={0,±1,±2,…} 都是合法的表示。 下面给出常用的集合记号: 第3章集合与关系 89 Z+={x| x 是正整数} 即Z+={1,2,3,4,…} N={x| x 是正整数或0}即N={0,1,2,3,4,…} Z={x| x 是整数} 即Z={…,-3,-2,-1,0,1,2,3,…} Q={ab≠0 x| x 是有理数} 即 Q 中的元素可以写成a/ b 的形式,、 b 是整数, R={x| x 是实数} .是空集,即不含任何元素的集合。 2. 描述法 描述法是把属于集合中元素所具有的属性描述出来,写在花括号里。使用时,描述法 也有两种情况:一种是用文字描述;另一种是用表达式描述。 例3.集合A={中国所有的网站}, 表示集合 A 中的元素是中国所有的网站。 1 例3.集合B={x∈R∧x2-0}, 表示方程x2-0的实数解集。 2 x|1=1= 许多集合可以用两种方法表示,如 B 也可以写成{-1,1}, 但是有些集合不可以用枚 举法表示,如实数集合。 3. 图示法 集合与集合之间的关系以及一些运算结果可用文氏图(VennDiagram)给予直观的 表示。其构造如下:用一个大的矩形表示全集的所有元素(有时为了简单起见,可将全集 省略)。在矩形内画一些圆(或任何其他形状的闭曲线), 用圆代表子集,用圆内部的点表 示相应集合的元素。 为了讨论问题的方便,我们引入全集E(有些教材用 U 表示)的概念,它包含我们讨 论的所有有意义的物体的全体,即讨论中提到的任一集合都是 E 的子集。例如,当讨论 实数时提到的集合 A 和 B 必须是实数集,而不是矩阵、电路等。在Venn图中,全集被表 示成矩形,而其子集则被表示成圆形。全集是有相对性的,不同的问题有不同的全集,即 使是同一个问题,也可以取不同的全集。例如,在研究平面上直线的相互关系时,可以把 整个平面(平面上所有点的集合)取作全集,也可以把整个空间(空间上所有点的集合)取 作全集。一般地,全集取得小一些,问题的描述和 处理会简单一些。 不同的圆代表不同的集合,并将运算结果得 到的集合用阴影或斜线的区域表示新组成的集 合。集合的相关运算用文氏图表示如图3.1 所示。 注意,文氏图只能帮助我们理解复杂的集合 关系,只能用于说明,不能用于证明。图3.文氏图表示集合之间的关系 1 3.2 基本概念 1. 1. 集合与元素之间的关系 集合的元素是彼此不同的,如果同一个元素在集合中多次出现,就应该认为是一个元 素,如{1,1,2,2,3}={1,2,3}。 集合的元素是无序的,如{1,2,3}={3,1,2}。 离散数学(第3版) 元素和集合之间的关系是隶属关系,即属于或不属于,属于记作∈,不属于记作.,例 如A={b,d,{{这里,b,d∈A, a,{c},d}}}, a∈A,{c}∈A, {{d}}∈A,但b.A,{d}.A。 b 和{d}是 A 的元素的元素。 可以用一种树形图表示这种隶属关系,该图分层构成,每个层 上的结点都表示一个集合,它的儿子就是它的元素。上述集合 A 的树形图如图3.2所示。图中的a,b, d 也是集合, c,由于讨 图3.元素和集合间隶属论的问题与a,c,所以没有列出它们的元素。 b, d 的元素无关,2 关系的树形表示为了体系上的严谨性,我们规定:对任何集合A,都有 A .A。 2. 集合之间的关系 下面考虑在同一层次上的两个集合之间的关系。 定义3.设A、 B 为集合,如果 B 中的每个元素都是 A 中的元素,则称 B 是 A 的子 集 , 这时也称 1 B 被 A 包含,或 A 包含B,记作B.A。如果 B 不被 A 包含,则记作B.A。 包含的符号化表示为B.A..x(x∈B→x∈A)。 例如,N.Z.Q.R.C,但Z.N。 显然,对任何集合A,都有A.A。 隶属关系和包含关系都是两个集合之间的关系,对于某些集合,这两种关系可以同时 成立。例如,A={a}} a} 既有{又有{ a,{和{这两个集合, a}∈A, a}.A。前者把它们看 成不同层次上的两个集合,后者把它们看成同一层次上的两个集合,都是正确的。 定义3.设A、 B 为集合,如果A. B 且B.A,则称 A 与 B 相等,记作A=B。 如果 A 2 与 B 不相等,则记作A≠B。相等的符号化表示为A=B.A.B∧B.A。 定义3.设A、如果B. A 且B≠A, 3 B 为集合, 则称 B 是 A 的真子集,记作B.A。如果 B 不是 A 的 真子集,则记作B.A。真子集的符号化表示为B. A 3所示。 .B.A∧B4 ≠A,如图3. 图3.子集和非真子集的图形表示 定义3.不含任何元素的集合称为空集,记 3 作.。例 如,{x|x∈R∧x2+1=0}是方程x2+1=0的实数解集,因为该方程无实数解,所 以是空集。 定理3.空集是一切集合的子集。 证明: 1 任何集合A,由子集定义有 ..A..x(x∈.→x∈A) 右边的蕴涵式因前件假而为真命题,所以.. A 也为真 。 推论空集是唯一的 。 证明:假设存在空集.1和.2,由定理3. 1有 根据定义3.有.1=.2。 .1..2,.2..1。 2, 含有 n 个元素的集合简称 n 元集,它的含有m( m ≤n)个元素的子集叫作它的 m 元 子集。任给一个 n 元集,怎样求出它的全部子集呢? 下面举例说明。 第3章集合与关系 91 例3.1,2,3}, 将 A 的子集分类 。 0元子集,也就是空集,只有一个:. ; 1元子集,即单元集:{1},{2},{3} ; 2元子集:{1,2},{1,3},{2,3} ; 3 A={ 3元子集:{1,2,3}。 它的0元子集有C0 个,nm 元子集有 一般地,对于 n 元集A, n 1元子集有C1 个,……, Cm 个,……,个。子集总数为 n 元子集有Cn nn n +C1 n = n 个。 C0 n +…+Cn 2 定义3.5 设 A 为集合,把 A 的全部子集构成的集合叫作 A 的幂集,记作P(A)。 例如,集合A={2,有P(={.,{2},{1,1,2,1,3}}。 1,3}, A)1},{3},{2},{3},{3},{2, 不难看出,若 A 是 n 元集,则P(A)有2n 个元素。 3.集合的运算 2 3.1 集合的基本运算 2. 集合的运算是一些规则,利用这些规则对给定集合的元素进行重新组合,从而构成新 的集合。集合的基本运算有并、交、相对补和对称差等。 定义3.设A、 A 与 B 的并集 A ∪B,交集 A ∩B, B 对 A 的相对补集 6 B 为集合, A-B, A 与 B 的对称差A.. B 分别定义如下: A ∪B={x| x ∈ A ∨ x ∈ B } A ∩B={x| x ∈ A ∧ x ∈ B } A - B ={x| x ∈ A ∧ x . B } A ..B=( A -B)∪(B-A) 对称差运算可等价定义为A..B=(A∪B)-(A∩B) 。 在给定全集 E 以后,A.E, A 的绝对补集~ A 定义如下 。 定义3.~A=A={x|x∈E∧x.A} 。 7 E 例如,E={b,d},a,c}, A=d}。 4就是一些集合的 a,c,A={b,则~E-A= { 以上集合之间的关系和运算可以用文氏图给予形象的描述。图3. 运算的文氏图描述 。 图3.用文氏图表示集合间的关系和运算 4 92 离散数学(第3 版) 3.2.2 有穷计数集 使用文氏图可以很方便地解决有穷集合的计数问题。首先根据已知条件把对应的文 氏图画出来。一般地,每一条性质决定一个集合。有多少条性质,就有多少个集合。如果 没有特殊说明,任何两个集合都画成相交的,然后将已知集合的元素数填入表示该集合的 区域内。通常从n 个集合的交集填起,根据计算的结果将数字逐步填入所有的空白区 域。如果交集的数字是未知的,可以设为x。根据题目中的条件列出一次方程或方程组, 就可以求得所需要的结果。 例3.4 对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下:会 图3.5 例3.4的文氏图 英、日、德和法语的人分别为13、5、10和9人,其中同时会英 语和日语的有2人,会英、德和法语中任两种语言的都是4 人。已知会日语的人既不懂法语,也不懂德语,分别求只会一 种语言(英、德、法、日)的人数和会3种语言的人数。 解:令A 、B、C、D 分别表示会英、法、德、日语的人的集 合。根据题意画出如图3.5所示的文氏图。从图中可知,只会 日语的有3人。设同时会3种语言的有x 人,只会英、法或德 语一种语言的分别为y1、y2 和y3 人。将x 和y1、y2、y3 填入图中相应的区域,然后依次 填入其他区域的人数。 根据已知条件列出方程组如下: y1 +2(4-x)+x +2=13 y2 +2(4-x)+x =9 y3 +2(4-x)+x =10 y1 +y2 +y3 +3(4-x)+x =19 解得x=1,y1=4,y2=2,y3=3。 例3.5 求1~1000(包含1和1000)既不能被5和6整除,也不能被8整除的数有多 少个。解 :设 E ={x|x ∈Z∧1≤x ≤1000} A ={x|x ∈E ∧x 可被5整除} B ={x|x ∈E ∧x 可被6整除} C ={x|x ∈E ∧x 可被8整除} 用|T|表示有穷集T 中的元素数,.x. 表示小于或等于x 的最大整数,lcm(x1,x2,…,xn) 表示x1,x2,…,xn 的最小公倍数,则有 |A |=.1000/5. =200 |B|=.1000/6. =166 |C|=.1000/8. =125 |A ∩B|=.1000/lcm(5,6). =33 |A ∩C|=.1000/lcm(5,8). =25 第3 章 集合与关系 93 图3.6 例3.5的文氏图 |B ∩C|=.1000/lcm(6,8). =41 |A ∩B ∩C|=.1000/lcm(5,6,8). =8 将这些数字依次填入文氏图,得到图3.6。由图可知,不能被 5、6和8整除的数有1000-(200+100+33+67)=600(个)。 3.2.3 包含排斥原理 现实生活中,我们经常会遇到对集合中的元素进行计数的问题,考虑下面的例子。 例3.6 一个班50人中,有16人期中得优,21人期末得优,17人两项均没得优,问有 多少人两项均得优? 下面给出包含排除原理。 定理3.2 对有限集合A 和B,有 |A ∪B|=|A|+|B|-|A ∩B| 证明:(1)当A 与B 不相交,即A ∩B=.,则 |A ∪B|=|A|+|B| (2)若A ∩B≠.,则 |A|=|A ∩~B|+|A ∩B|,|B|=|~A ∩B|+|A ∩B| 所以 |A |+|B|=|A ∩~B|+|A ∩B|+|~A ∩B|+|A ∩B| =|A ∩~B|+|~A ∩B|+2|A ∩B| 但 |A ∩~B|+|~A ∩B|+|A ∩B|=|A ∪B| 因此|A ∪B|=|A|+|B|-|A ∩B|,证毕。 包含排除原理可以推广至有限集合。 借助文氏图法可以很方便地解决有限集合的计数问题。首先根据已知条件画出相应 的文氏图。如果没有特殊说明,两个集合一般都画成相交的,然后将已知的集合的基数填 入文氏图中的相应区域,用x 等字母表示未知区域,根据题目中的条件,列出相应的方程 或方程组,解出未知数即可得所需求的集合的基数。下面通过例子说明这一做法。 例3.7 计算中心需安排Python、VisualBasic、C3门课程的上机。3门课程的学生 分别有110人、98人、75人,同时学Python和VisualBasic的有35人,同时学Python和 C的有50人,同时学VisualBasic和C的有19人,3门课程都学的有6人。求共有多少 学生。解 :设x 是同时选Python和VisualBasic,但没有选C 的学生人数;y 是同时选 Python和C,但没有选VisualBasic的学生人数;z 是同时选C和VisualBasic,但没有选 Python的学生人数,设p 是仅选Python的学生人数,b 是仅选VisualBasic的学生人 数,c 是仅选C的学生人数。 根据题设有 x+6=35 所以x=29 y+6=50 所以y=44 例3.6解答 94 离散数学(第3版) z+6=19 所以z=13 x+y+6=110- p 所以p=31 x+z+6=98- b 所以b=50 y+z+6=75- c 所以c=12 总计=31+29+50+44+6+13+12=185 图3.7 例3.其文氏图解法如图3. 7的文氏图7所示。 2.广义交和广义并 3.4 以上定义的并和交运算称为初级并和初级交。下面考虑推广的并和交运算,即广义 并和广义交。 定义3.设 A 为集合, A 的元素的元素构成的集合称为 A 的广义并,记为∪A。符 8 x|.z∈A∧x∈z号化表示为∪A={z( c},{ )}。 f}},a}},d}}。 例3.设集合A={{d},{B={{a,{ b,c,e,c, 8 a,a,a,C={ 则 a,c,e, ∪B={ ∪A={b,d,f} a} ∪C= a ∪{d} c, 根据广义并定义不难证明,若 ∪ A. = = {A. 1,A2,…,An }, 则∪A=A1∪A2∪…∪An 。 类似地,可以定义集合的广义交。 定义3.设 A 为非空集合, A 的所有元素的公共元素构成的集合称为 A 的广义 9 交,记为∩A。符号化表示为 ∩A={x|.z(z∈A→x∈z)} 考虑例3. ∩ 有 A={a},∩B={a},∩C=c, 7中的集合, a∩{d} 注意到在定义中特别强调了 A 是非空集合。对于空集.,可以进行广义并,即∪.= .。但空集.不可以进行广义交,因为∩. 不是集合,在集合论中是没有意义的。 和广义并类似,若A={A1,A2,…,An }, 则∩A=A1∩A2∩…∩An 。 在后面的叙述中,若只说并或交,指的都是集合的初级并或初级交;如果在并或交前 边冠以“广义”两个字,则指集合的广义并或广义交。 为了使集合表达式更简洁,对集合运算的优先顺序做如下规定:一元运算优先于二 元运算;一元运算之间按由右向左的顺序进行;二元运算之间由括号决定先后顺序。 其中,一元运算指广义并、广义交、幂集、绝对补运算,二元运算指并、交、相对补、对称 差运算。 例如下面的集合公式: ∩A-∪B,∪P(A),~P(A)∪∪B,~(A∪B)都是合理的公式。 例3.设A={{a,计算∪∪A,∩∩ A 和∩∪A∪(∪∪A-∪∩A)。 9 a},{b}} , 解:∪A={b} a, 95 第3章集合与关系 a} ∪∪A=a∪ b ∩∩A= a ∩∪A=a∩ b ∪∩A= a (∪=(a)a∩b)∪(a) ∩A={ a∩b)∪((=( ∩∪A∪∪A-∪∩A)a∪b)-b-= b 所以∪∪A=a∪b,∩∩A=a,∩∪A∪(∪∪A-∪∩A)=b。 命题代数与集合代数都是特殊的布尔代数。这个事实足以说明,此命题代数中的各 种运算与集合论中的各种运算极为相似。在此将列举若干集合恒等式,它们都有与其对 应的命题等价式。下面介绍集合运算的恒等式。 定理3.设A、 C 为任意集合,B、那么下列各式成立。 3 B、 E 为包含A、 C 的全集, (1)等幂律A∪A=AA∩A= A (2)交换律A∪B=B∪ A A∩B=B∩ A (3)结合律(A∪B)∪C=A∪(B∪C) (A∩B)∩C=A∩(B∩C) (4)同一律A∪.=AA∩E= A (5)零律A∩.=. A∪E= E (6)分配律A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C) (7)吸收律A∩(A∪B)= A A∪(A∩B)= A (8)双重否定律~(~A)= A ~E=. ~.= E (9)排中律A∪~A= E (10)矛盾律A∩~A=. (11)德·摩根律~(A∪B)=~A∩~ B ~(A∩B)=~A∪~ B A-(B∪C)=(A-B)∩(A-C) A-(B∩C)=(A-B)∪(A-C) (12)补交转换律A-B=A∩~ B 例3.试证明A-(C)A-A∩C) 。 10 B-=(B)∪ ( 证明 : 方法 1 x∈A-(B-C) .x∈A∧x.(B∩~C) .x∈A∧(x.B∨x∈C) .(x∈A∧x.B)∨(x∈A∧x∈C) .x∈(A-B)∪(A∩C) 方法 2 进行等值推导 A 。 -(B-C)= A ∩ ~ ( B ∩~C) = A ∩(~ B ∪C) 96 离散数学(第3版) =( A ∩~B)∪( A ∩C) =( A -B)∪( A ∩C) 3.有序对与笛卡儿积 3 最直接的表达两个集合之间的关系的方式,就是利用两个元素组成的有序对。 定义3.10 由两个元素 x 和y(允许x=y)按一定顺序排列成的二元组叫作一个有 序对或序偶,记作,其中 x 是它的第一元素 , ( 有序对 。 y>具有以下性质 : 1)当x≠ y 时,=≠的充分必要条件是x=。 这些性质是二元集{x,y}不具备的。例如,当x≠ y 时,(v) 有{x,y}={y,x}。原因是 有序对中的元素是有序的,而集合中的元素是无序的。 a,c, 如有集合A={b,d}, A 中4个元素分别表示4个男人,是我们研究的对象,其 中 a 是 b 和 c 的父亲, 、、d>表示。这些有序对中的元素的前后次序是不能颠倒的。 例3.已知=<5,2x+y> , 解:由有序对相等的充要条件 有 x+2= 5 解得x=3,2。 2x+y=4 y= 为了更深入地研究关系,下面引入一个新的概念———集合的笛卡儿积 。 定义3.设A、 B 为集合,用 A 中元素为第一元素, B 中元素为第二元素构成有序 对。所有这样的有序对组成的集合叫作 A 和 B 的笛卡儿积,记作A×B。 笛卡儿积的符号化表示为 11 A×B={ | a,0,2}, A ×B ={,,,,,} B ×A ={<0, b >,<1, b >,<2, b >} a >,<0, a >,<1, a >,<2, 由排列组合的知识不难证明,如果|A|=m,|B|=n,则|A×B|= m · n。 下面给出笛卡儿积的运算性质。 (1)对任意集合A,根据定义 有 A×.=.,.×A= . (2)笛卡儿积运算不满足交换律, 即 A×B≠B×A (当A≠.∧B≠.∧A≠ B 时 ) (3)笛卡儿积运算不满足结合律, 即 (A×B)×C≠A×(B×C)( 当A≠.∧B≠.∧C≠. 时 ) (4)笛卡儿积运算对并和交运算满足分配律, 即 A× ( B ∪C)=( A ×B)∪( A ×C) 第3章集合与关系 97 ( B ∪C)×A =( B ×A)∪(C×A) A× ( B ∩C)=( A ×B)∩( A ×C) ( B ∩C)×A =( B ×A)∩(C×A) (5)A.C∧B.D.A×B.C×D 下面给出性质(4)第一个式子的证明 。 证明:任取 y >∈A× ( . x ∈ A ∧ y ∈ B ∪ C . x ∈ A ∧( y ∈ B ∨ y ∈C) .( x ∈ A ∧ y ∈B)∨( x ∈ A ∧ y ∈C) .∈ A ×C y >∈ A ×B ∨∈( 所以有A×(B∪C)=(A×B)∪(A×C)。 注意:性质(5)的逆命题不成立,可分以下4种情况讨论。 ①当A=B=. 时,显然有A. C 和B. D 成立。 ②当A≠. 且B≠. 时,也有A. C 和B. D 成立,证明如下: 任取x∈A,由于B≠.,必存在y∈B,因此有 x∈A∧y∈B.∈C×D.x∈C∧y∈D.x∈C y>∈A×B.,2>,1>,2>, 12 <{1},<{<{<{2}, <{1,2},<{2}, 1>,<.,1>,1},2}, 1>,1,2>} 例3.13 设A、B、C、 D 为任意集合,判断以下命题是否为真,并说明理由 。 (1)A×B=A×C.B= C (2)A-(B×C)=(A-B)×(A-C) (3)A=B∧C=D.A×C=B×D (4)存在集合A,使A.A×AB={C={时, 但B≠C。解:(1)不一定为真。当A=.,1},2} 有A×B=.=A×C, (2)不一定为真。当A=B={1},C={2}时, 有 A-( B ×C)={1}-{<1,2>}={1} ( A -B) × ( A -C) = . × {1} = . (3)为真。由等量代入的原理可证。 (4)为真。当A=. 时,A.A×A 成立。 离散数学(第3版) 3.关系及其表示 4 3.1 基本概念 4. 关系是客观世界存在的普遍现象,它描述了事物之间存在的某种联系。例如,人类集 合中的父子、兄弟、同学、同乡,两个实数间的大于、小于、等于关系,集合中两条直线的平 行、垂直关系等,集合间的包含,元素与集合的属于…… 都是关系在各个领域中的具体表 现。《水浒》中108 条梁山好汉,每个人都有一个绰号,人人都不例外。 宋江———及时雨,吴用———智多星,李逵———黑旋风,白胜———白日鼠,…… 这就是说,梁山好汉的姓名与他们的绰号之间有一种“关系”。 表述两个个体之间的关系,称为二元关系;表示3个以上个体之间的关系,称为多元 关系。我们主要讨论二元关系 。 定义3.如果一个集合满足以下条件之一 : 12 (1)集合非空,且它的元素都是有序对。 (2)集合是空集。 则称该集合为一个二元关系,记作R。二元关系也可简称为关系。对于二元关系R,如果 ∈R,则可记作xRy; y>.R, y 如果,b>},R2={<1,2>,b}, 元关系,只是一个集合,除非将 a 和 b 定义为有序对。根据上面的记法可以写 1R12,R1b。 根据(a) 笛卡儿积的定义,二元关系还可以有如下定义。 定义3.设A、 B 为集合, A ×B 的任何子集均称为从 A 到 B 的二元关系,特别 地,当A= B 13 时,称为 A 上的二元关系。 例如A={0,1},B={1,2,3}, 那么R1={<0,2>},R2=A×B,R3=.,R4={<0, 1>}等都是从 A 到 B 的二元关系,而R3 和R4 同时也是 A 上的二元关系。 集合 A 上的二元关系的数目依赖于 A 中的元素数。如果|A|=n,那么| A ×A|= n2,A×A 的子集就有2n2个。每个子集代表一个 A 上的二元关系,所以 A 上有2n2个不 同的二元关系。例如|A|=3,则 A 上有232=512 个不同的二元关系。 下面介绍一些特殊的二元关系。对于任何集合A,空集.是 A ×A 的子集,叫作 A 上的空关系。下面定义 A 上的全域关系EA 和恒等关系IA 。 定义3.对任意集合A,定义全域关系为EA ={|x∈ A ∧y∈A}= A × A,恒等关系为IA ={x>| 14 ,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>, <2,1>,<2,2> }。 IA 是 A 上的恒等关系,|IA|=|A|=3,IA ={<0,0>,<1,1>,<2,2> }。 除了以上3种特殊的关系以外,还有一些常用的关系,分别说明如下: 99 第3章集合与关系 LA ={|y∈A∧x≤y} , DB ={|y∈B∧ x 整除y}, R.={|x,这里 A 是集合族。 LA 叫作 A 上的小于或等于关系, A 是实数集 R 的子集。DB 叫作 B 上的整除关系, 其中 x 是 y 的因子, B 是非零整数集Z*的子集。R.叫作 A 上的包含关系, A 是由一些 集合构成的集合族。例如A={1,3},a,则 2,B={b}, <1,2>,<1,3>} DA ={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>} 而令 RA.= =P(={.,{b},{b}}, a,b}>,<{a}>, LA ={1>,<1,3>,<2,2>,<2,3>,<3, B)a},{a,则 A 上的包含关系 是 {<.,.>,<.,{b}>,<., { a}>,<.,{a},{ <{a,b},{b},{b}>,<{b},{b}>} a},{b}>,<{b}>,<{a,a,a, 类似地,还可以定义大于或等于关系、小于关系、大于关系、真包含关系等。 例3.设A={1,2,3}, 用列举法给出 A 上的恒等关系IA 和全关系EA , A 上的小于关系LA ={| x, y∈A∧ x 整除 和 y 15 y>|y∈A∧x,<2,2>,<3,3> } EA ={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>, <3,3>} LA ={<1,2>,<1,3>,<2,3>} DA ={<1,1>,<1,3>,<2,3>} 2>,<1,2>,<3, 3.2 关系表示法 4. 1. 列举法 列举出关系的所有有序对,前面的例题大多是用列举法表示关系的。 示 R 例 。 3.设A={2,4}, 试用列元素法表 16 1,3,下面各式定义的 R 都是 A 上的关系, | y>|(y) (3)R={y>| y 是素数 } | 解:(1)R={<4,2>,1>,<3,1>,<2,1>,<1, 4>,<4,<4,3>,<3,2>,<2,1>} (2)R={<2,2>,<4,1>,<4,4>,<1,4>, 1>,<3,3>,<3,2>,<2,3>,<3, <2,2>} 3>,<1, (3)R={<2,1>,<3,2> } 1>,<4, (4)R=EA -2>,<1,4>,<2,3>,<2,1>, IA ={<1,3>,<1,1>,<2,4>,<3, <3,2>,<3,4>,<4,2>,<4, 例3.1>,<4,3>} 16 中的4个关系是用描述法给出的。 1 00 离散数学(第3 版) 2.关系矩阵 关系矩阵是表达两个有限集合之间的关系的有力工具,也是方便计算机处理的一种 表示方式,它的构成是这样的: 设A ={x1,x2,…,xn},R 是A 上的关系。令 rij = 1 xiRxj 0 xiRxj { (i,j =1,2,…,n) 则 MR = r11 r12 … r1n r21 r22 … r2n . . . rn1 rn2 … rnn é . êêêêêê ù . úúúúúú 是R 的关系矩阵,记作MR 。 例3.17 设A ={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},试 求R 的关系矩阵。 解:R 的关系矩阵为 MR = 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 é . êêêêê ê ù . úúúúú ú 3.关系图 还可以利用平面上的图形描述从集合A 到集合B 的二元关系R,以便更好地理解二 元关系。 图3.8 例3.17中R 的关系图 设A={x1,x2,…,xn},R 是A 上的关系,令图G=, 其中顶点集合V=A,边集为E。对于.xi,xj ∈V,满足 ∈E.xiRxj,称图G 为R 的关系图,记作GR 。 图3.9 例3.18小于关 系的关系图 在例3.17中,R 的关系图GR 如图3.8所示。 例3.18 求集合A ={1,2,3,4}上的恒等关系、空关系、全关 系和小于关系,并画出小于关系的关系图。 解:恒等关系IA ={<1,1>,<2,2>,<3,3>,<4,4>}; 空关系=.; 全关系EA ={<1,1>,<1,2>,<1,3>,<1,4>,<2,1>, <2,2>,<2,3>,<2,4>,<3,1>,<3,2>, <3,3>,<3,4>,<4,1>,<4,2>,<4,3>, <4,4>}; 小于关系LA ={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>, <3,4>}。 小于关系的关系图如图3.9所示。 第3章集合与关系 101 例3.设集合 A ={b}, R 是P(A)上的包含关系,求R、 R 的关系矩阵与 R 的 关系图。 19 a, y>|y∈P(解:用描述法表示:R={,<.,{b}>,<., A >,<{a},{a}, A >, a}>,<.,{a}>,<{ <{b}>,<{A>,}b},{b}, 10 所示。 R 的关系矩阵与 R 的关系图如图3. 图3. 10 R 的关系矩阵与 R 的关系图 3.关系的运算 5 5.基本概念 3.1 集合可对关系作并、交、差、补运算,但为了运算结果作为关系的意义更明确,也要求 运算对象应有相同的域,从而运算结果是同一域间的关系。 定义3.设 R 是二元关系。 15 (1) R 中所有的有序对的第一元素构成的集合称为 R 的定义域,记作domR。 表示为domR={x|.y(y>∈R)}。 ∈R)}。 ay|.x(,<1,3>,<2,4>,<4,3>}, 则 domR={1,2,4} ranR={2,3,4} fldR={1,2,3,4} 例3.设 A 1,3,若R={|(y)/2是整数, {|(y)/3是正整数,y∈A}, R∩S,R,R, 解:R={<1,1>,<1,2>,<2,1>,<3,3>,<4,2>, 3>,<2,4>,<3, <4, 4>} S={<4,1>} R∪S={<1,1>,<1,3>,<2,2>,<2,4>,<3,1>,<3,3>,<4,2>, 离散数学(第3版) <4,4>,<4,1>} R∩S=. S-R=S={<4,1>} ~R=A×A-R={<1,2>,<1,4>,<2,1>,<2,3>,<3,2>,<3,4>, <4,1>,<4,3>} R.. S =(R∪S)-(R∩S)=R∪ S ={<1,1>,<1,3>,<2,2>,<2,4>,<3,1>,<3,3>,<4,2>, <4,4>,<4,1>} 3.2 复合关系 5. 假设有a、c3人, b 是兄妹关系, c 是母子关系,、设 b、a、b、则ac 是舅甥关系。又如, R 是兄妹关系, S 是母子关系,则 R 与 S 的复合 T 是舅甥关系。再如, R 是父子关系, R 与 R 复合就是祖孙关系了。 定义3.设A、 C 是3个任意集合, R 是集合 A 到 B 的二元关系, S 是集合B 16 B、 到 C 的二元关系,则定义关系 R 和 S 的合成或复合关系 b 。 >∈ R 且|a∈A,c∈C∧.b∈B,使∈S}。 例如,有关系R={<1,6>}, 关系S={<2,5>,2>,<2,4>,<3,4>,<5,3> }。 1>,<2, <6,3>}, 则 R 和 S 的复合关系R..S={<1,1>,<1,5>,<5, 例3.22 设F={<3,3>,<6,2>},G={<2,3>}, 则 F..G={<6,3> } G..F={<2,3> } b,1,3, 例3.某集合A={c},5}, R 是 A 上的关系, S 是 A 到 B 的 关系。 23 a,B={2,4, R={,,,,} S={,,,,} 求R..S。 ,,,,,,}解:R..S={ 定理3.设IAIB B 上的恒等关系,那么 4 、为集合A、R=A×B, (1)IA..R=R..IB =R; (2)...R=R...=. 。 证明:(1)任取 , ∈IA.. R ∈IA ∧(y)∈R) ..t(t∧(y)∈R) x=t, .∈ R 所以有IA..R=R 。 同理可证R..IB =R 。 (2)证明略。 第3 章 集合与关系1 03 从例3.22可看出,一般地,R..S≠S..R,即关系的复合运算不满足交换律,但是满足 结合律。 定理3.5 设R 是A 到B 的关系,S 是B 到C 的关系,T 是C 到D 的关系,则(R.. S)..T =R..(S..T)。 证明:∈((R..S)..T). .z(∈R°S∧∈T) . .z(.y(∈R∧∈S)∧∈T) . .z.y((∈R∧∈S)∧∈T) . .y.z(∈R∧(∈S∧∈T)) . .y(∈R∧.z(∈S∧∈T)) . .y (∈R∧∈S..T) . ∈R..(S..T) 所以(R..S)..T =R..(S..T),即关系的复合运算满足结合律。 例3.24 设集合A ={0,1,2,3,4},R、S 均为A 上的二元关系,且 R ={|x +y =4} ={<0,4>,<4,0>,<1,3>,<3,1>,<2,2>} S ={|y -x =1} ={<0,1>,<1,2>,<2,3>,<3,4>} 求R..S,S..R,R..R,S..S,(R..S)..R,R..(S..R)。 解:R..S={<4,1>,<1,4>,<3,2>,<2,3>}={|x+z=5} S..R={<0,3>,<1,2>,<2,1>,<3,0>}={|x+z=3} R..R={<0,0>,<4,4>,<1,1>,<3,3>,<2,2>}={,<1,3>,<2,4>}={|z-x=2} (R..S)..R={<4,3>,<1,0>,<3,2>,<2,1>} R..(S..R)={<4,3>,<3,2>,<2,1>,<1,0>} 定理3.6 设F、G、H 是任意关系,则 (1)F..(G∪H )=F..G∪F..H (2)(G∪H )..F=G..F∪H..F (3)F..(G∩H ).F..G∩F..H (4)(G∩H )..F.G..F∩H..F 证明略。 可用数学归纳法证明定理3.5的推广形式: R..(R1 ∪R2 ∪ … ∪Rn)=R..R1 ∪R..R2 ∪ … ∪R..Rn (R1 ∪R2 ∪ … ∪Rn)..R =R1..R ∪R2..R ∪ … ∪Rn ..R R..(R1 ∩R2 ∩ … ∩Rn).R..R1 ∩R..R2 ∩ … ∩R..Rn (R1 ∩R2 ∩ … ∩Rn)..R .R1..R ∩R2..R ∩ … ∩Rn ..R 3.5.3 逆关系 定义3.17 设R 是集合A 到B 的二元关系,则定义一个B 到A 的二元关系 104 离散数学(第3版) R-1={|∈R}, 称为 R 的逆关系,记作R-1 。 说明 : (1)R-1就是将所有 R 中的有序对中的两个元素交换次序成为R-1,故|R| = |R-1|。 1 -1 (2)R-的关系矩阵是 R 的关系矩阵的转置,即MR =MR- 1 (3)R-1的关系 T 图是将 R 的关系图中的弧改变方向所得 。 例3.设集合Aa,c, A 的关系为 R 25 ={b,d},={,,, ,c>}, 则R-1={a>,,, a>,c,,,}。,,,,} S={,,,,} 试验证S-1..R-1=(R..S)-1。 解:R..S={,,,,,,} R-1={,c>,a>,c>} a>,,<2,b>,<4,c>,<5, a>,<4,c>} S-1..R-a>,<2,c>,<4,c>,<5,c>} 1={<1,b>,<2,a>,<4,a>,<5, - (a>,<2,c>,<4,c>,<5,c>} R..S)1={<1,b>,<2,a>,<4,a>,<5, 故可验证S-1..R-1=(R..S)-1。 定理3.设 R 是 A 到 B 的关系,则 7 S 是 B 到 C 的关系, 证明:∈(R..S) .∈( ..y∈B(∈S) y>∈R∧∈S-x>∈R .∈S 从而,(R..S)-1=S-1..R-1。 注意:复合关系的逆等于它们逆关系的反复合。而(R..S)-1≠R-1..S-1,因R-1是 B 到 A 的关系, S 是 C 到 B 的关系,所以S-1..R-1是可以复合的,而R-1..S-1是不能复 合的。 定理3.设 R 和 S 均是 A 到 B 的关系,则 8 (1)(R1)1=R; - (2)(R∪S)1=R-1∪S-1; - (3)(R∩S)1=R-1∩S-1; (4)(R-S)-1=R-1-S-1 。 证明:这里只证明(3)和(4),(1)和(2)留作练习 。 -1 (3)∈( .∈R∩ S 105 第3章集合与关系 .∈S a>∈R∧∈R-1∧∈S .∈R 因此,(R∩S)-1=R-1∩S-1。 (4)(R-S)-1=(R∩~S)-1=R-1∩(~S)-1=R-1∩~S-1=R-1-S-1。 例3.27 设集合A={1,2},R、 S 均为 A 上的二元关系,且 R={<1,1>,<1,2>},S={<1,1>,<1,2>,<2,2>}, 则 R-11= ) {<1,1>,<2,1>},S-1={<1,1>,<2,1>,<2,2>}, 可见, - (R-1=R={<1,1>,<1,2>} --1 (R∪S)1={<1,1>,<1,2>,<2,2> } ={<1,1>,<2,1>,<2,2>}=R-1∪S- 1 - (R∩S)1=R-1∩S-1={<1,1>,<2,1>} - (R-S)1=R-1-S-1=. 定理3.设 R 是任意关系,则 9 domR-1=arnR-1=omR rnR,ad 证明:任取x,-1..∈Ry(x>∈R)a 所以有domR-1=ranR。 同理可证,ranR-1=domR。 3.4 关系幂 5. 定义3.设 R 为 A 上的关系,则 R 的 n 次幂定义为 18 n 为自然数, (1)R0={|x∈A}=IA ; (2)Rn+1=Rn..R 。 由以上定义可知,对于 A 上的任何关系R1 和R2,都 有 R10=R20=IA 也就是说, A 上任何关系的0次幂都相等,都等于 A 上的恒等关系IA 。此外,对于 A 上 的任何关系R,都有R1=R,因为R1=R0..R=IA..R=R。 下面考虑n≥2 的情况。如果 R 是用集合表达式给出的,则可以通过n-1次右复合 计算得到Rn 。如果 R 是用关系矩阵 M 给出的,则Rn 的关系矩阵是Mn ,即 n 个矩阵 M 之积。与普通矩阵乘法不同的是,其中的相加是逻辑加,即 1+1=1,1+0=0+1=1,0+0=0 如果 R 是用关系图 G 给出的,则可以直接由图 G 得到Rn 的关系图G'。G'的顶点集 与 G 相同。考察 G 的每个顶点xi,如果在 G 中从xi 出发经过 n 步长的路径到达顶点 xj ,则在G'中加一条从xi 到xj 的边。当找到所有这样的边以后,就得到图G'。 例3.设A={b,d},,a>,c>,d>}, 次幂,分别用矩阵和关系图表示。 解: R 的关系矩阵为 1 06 离散数学(第3 版) M = 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 é . êêêêê ù . úúúúú 则R2、R3、R4 的关系矩阵分别是 M2 = 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 é . êêêêê ù . úúúúú 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 é . êêêêê ù . úúúúú = 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 é . êêêêê ù . úúúúú M3 =M2M = 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 é . êêêêê ù . úúúúú 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 é . êêêêê ù . úúúúú = 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 é . êêêêê ù . úúúúú M4 =M3M = 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 é . êêêêê ù . úúúúú 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 é . êêêêê ù . úúúúú = 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 é . êêêêê ù . úúúúú 因此M4=M2,即R4=R2。可以得到 R2 =R4 =R6 =… R3 =R5 =R7 =… 而R0,即IA 的关系矩阵是 M0 = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 é . êêêêê ù . úúúúú 至此,R 各次幂的关系矩阵都得到了。 使用关系图的方法得到的R0,R1,R2,R3,…的关系图如图3.11所示。 图3.11 例3.28的关系图 3.5.5 幂运算的性质 定理3.10 设A 为n 元集,R 是A 上的关系,则存在自然数s 和t,使Rs=Rt。 107 第3章集合与关系 证明: R 为 A 上的关系,对任何自然数k,Rk 都是 A ×A 的子集。又知| A ×A|= n2,|P(A×A)|=2n2,即A×A 的不同子集仅2n2个。当列出 R 的各次幂R0,R1,R2,…, n R2,…, 必存在自然数 s 和t使Rs=Rt。 定理3.11 设 R 是 A 上的关系,n∈N, (1)Rm..Rn =Rm+ n ; m,则 (2)( n = Rm )Rmn 。 证明:(1)对于任意给定的m∈N,施归纳于n 。 若n=0,则有 Rm =Rm+ 0 假设Rm..Rn =Rm+ n ,则有 Rm..R0=Rm..IA = Rm..Rn+1=Rm..(Rn..R)=(Rm..Rn )..R=Rm+n+1, 所以,对一切m,有Rm..Rn = n∈N, Rm+ n 。 (2)对于任意给定的m∈N,施归纳于n 。 若n=0,则有 0=IA = n = n , 假设(Rm )Rm则有 (Rm )R0=Rm×0 (Rm )Rm )Rm( 所以,对一切m, n+1= 有 ( ( n..nR= m =(Rmn )..Rm =Rmn+ m =n+1) Rm )Rm 定理3.设Rn 是 ∈ A N, 上的关系, n 。 、s,a>,e>,}, 29 a,d,f},,