第3 章 集合与关系 3.1 内容提要 集合与元素 讨论某一类对象时,就把这一类对象的全体称为集合。这些对象称为集 合中的元素。 集合的表示 枚举法、描述法和图示法(文氏图)。 集合与元素的关系 元素和集合之间的关系是隶属关系,即属于或不属于,属于记作 ∈,不属于记作.。 集合与集合的关系 设A 、B 为集合,如果B 中的每个元素都是A 中的元素,则称B 是A 的子集。这时也称B 被A 包含,或A 包含B,记作B.A 。如果B 不被A 包含,则记 作B.A 。设A 、B 为集合,如果A .B 且B.A ,则称A 与B 相等,记作A =B。如果A 与 B 不相等,则记作A ≠B。相等的符号化表示为A =B.A .B∧B.A 。 空集 不含任何元素的集合称为空集,记作.。空集是一切集合的子集。空集是唯 一的。定 理3.1 空集是一切集合的子集。 幂集 设A 为集合,把A 的全部子集构成的集合称为A 的幂集,记作P(A)。若A 是 n 元集,则P(A)有2n 个元素。 集合的广义并 设A 为集合,A 的元素的元素构成的集合称为A 的广义并,记作∪A 。 符号化表示为∪A ={x|.z(z∈A ∧x∈z)}。 集合的广义交 设A 为非空集合,A 的所有元素的公共元素构成的集合称为A 的广 义交,记作∩A 。符号化表示为∩A ={x|.z(z∈A →x∈z)}。 定理3.2 设A 、B、C 为任意集合,E 为包含A 、B、C 的全集,那么下列各式成立。 等幂律 A ∪A =A A ∩A =A 交换律A ∪B=B∪A A ∩B=B∩A 结合律(A ∪B)∪C=A ∪(B∪C) (A ∩B)∩C=A ∩(B∩C) 同一律A ∪.=A A ∩E=A 零律A ∩.=. A ∪E=E 分配律A ∪(B∩C)=(A ∪B)∩(A ∪C) A ∩(B∪C)=(A ∩B)∪(A ∩C) 吸收律A ∩(A ∪B)=A A ∪(A ∩B)=A 双重否定律 ~(~A)=A ~E=. ~.=E 排中律A ∪~A =E 集合与关系 第3章 6 5 矛盾律A ∩~A =. 德·摩根律~(A ∪B)=~A ∩~B ~(A ∩B)=~A ∪~B A -(B∪C)=(A -B)∩(A -C) A -(B∩C)=(A -B)∪(A -C) 补交转换律 A -B=A ∩~B 有序对 由两个元素x 和y(允许x=y)按一定顺序排列成的二元组称为一个有序对 或序偶,记作,其中x 是它的第一元素,y 是它的第二元素。 笛卡儿积 设A 、B 为集合,用A 中元素为第一元素,B 中元素为第二元素构成有序 对。所有这样的有序对组成的集合称为A 和B 的笛卡儿积,记作A ×B。笛卡儿积的符号 化表示为A ×B={|x∈A ∧y∈B}。如果|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), (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 。 二元关系 如果一个集合满足以下条件之一: (1)集合非空,且它的元素都是有序对。 (2)集合是空集。 则称该集合为一个二元关系,记作R。二元关系也简称为关系。对于二元关系R,若∈R,则记作xRy;若.R,则记作x/Ry。设A 、B 为集合,A ×B 的任何子集称 为从A 到B 的二元关系。特别是当A =B 时,称为A 上的二元关系。 关系的表示方法 (1)列举法:列举出关系的所有有序对。 (2)关系矩阵:设A ={x1,x2,…,xn},R 是A 上的关系,令 rij = 1 若xiRxj 0 若x/Rxj (i,j=1,2,…,n) 则MR = r11 r12 … r1n r21 r22 … r2n . . . . rn1 rn2 … rnn é . êêêêê ù . úúúúú 是R 的关系矩阵,记作MR 。 (3)关系图:设A ={x1,x2,…,xn },R 是A 上的关系,令图G =,其中顶点 集合V=A ,边集为E。对于.xi,xj∈V,满足∈E.xiRxj,称图G 为R 的关系 图,记作GR 。 定义域、值域和域 设R 是二元关系, (1)R 中所有的有序对的第一元素构成的集合称为R 的定义域,记作domR。表示为 domR={x|.y(∈R)}。 66 离散数学解题指导(第3版) (2) R 中所有有序对的第二元素构成的集合称为 R 的值域,记作ranR。表示为ranR= {y>∈R)}。 y|.x(∈S}。 c>|a∈A, b>∈ R 且∈R}, 记作R-1。 5 a>||x∈A}=IA 。 n 为自然数, (2)Rn+1=Rn..R。 定理3.设 A 为 n 元集, m,则 则存在自然数 s 和t,使得Rs=Rt。 9 R 是 A 上的关系 , 定理3.10 设 R 是 A 上的关系,n∈N, (1)Rm..Rn =Rm+ n 。 Rm )Rmn 。 (2)( 11 n = 若存在自然数 s 和t( 定理3.设 R 是 A 上的关系, s∈R), x∈A→.R), 则称 R 在 A 上是反自反的。 x∈A→∈R→∈R), (4)若.x.y(y∈A∧∈R→x=y), 则称 R 为 A 上的反 对称关系。 x,y>∈R∧∈R), 则称R z∈A∧∈R→∈R∧∈R, 记作x~ 等价类设 R 为非空集合 A 上的等价关系,令.x∈A,[x] R ={y|y∈ A ∧xRy}, 称 [为 x 关于 R 的等价类,简称为 x 的等价类,简记作[]。x] R 定理3.18 y∈ 设 AR , 是非空集合 则 A [ 上的等价关系,则 x (1).x∈A,[x]是 A 的非空子集。 (2).x,如果xRy, x]=[y] 。 (y∈A,如果x/则[x]与[不相交 。 3).x,Ry, y] (4)∪{[x]|x∈A}=A。 商集设 R 为非空集合 A 上的等价关系,以 R 的所有等价类作为元素的集合称为 A 关于 R 的商集,记作A/R,即A/R={[x]R|x∈A}。 相容关系设 R 为非空集合 A 上的关系。如果 R 是自反的、对称的,则称 R 为 A 上 的相容关系。 相容类设 R 为集合 A 上的相容关系,如果C.A,如果对于 C 中任意两个元素x1 和 x2 有x1Rx2,则称 C 是由相容关系 R 产生的相容类。 最大相容类设 R 为集合 A 上的相容关系,不能真包含在任何其他相容类中的相容类 称为最大相容类。 定理3.设 R 为有限集合 A 上的相容关系,那么必存在一个最大 19 C 是一个相容类, 相容类Cr ,使得C.Cr 。 偏序关系设 R 为非空集合 A 上的关系,如果 R 是自反的、反对称的和传递的,则称 R 为 A 上的偏序关系。集合 A 和 A 上的偏序关系.一起称为偏序集,记作 。 可比与不可比设 R 为非空集合 A 上的偏序关系,如果a. b 或b.a,则称 a 和 b 是 可比的。如果既没有a. b 也没有b.a,则称 a 和 b 是不可比的。 哈斯图作图法 (1)以圆圈表示元素; (2)若x.y,则 y 画在 x 的上层; (3)若 y 覆盖x,则连线; (4)不可比的元素可画在同一层 。 偏序中特殊元素设(A,.)是偏序集,集合B.A,特殊元 有 (1)如存在元素b∈B,使得.a∈B,均有a.b,则称 b 为 B 的最大元。 (2)如存在元素b∈B,使得.a∈B,均有b.a,则称 b 为 B 的最小元。 (3)若存在元素b∈B,.a∈B,如b.a,则a=b,称 b 为 B 的极大元。 (4)若存在元素b∈B,.a∈B,如a.b,则a=b,称 b 为 B 的极小元。 (5) a 为 B 的上界.a∈A∧.x(x∈B→x.a)。 (6) a 为 B 的下界.a∈A∧.x(x∈B→a.x)。 (7)如果 C 是 B 的所有上界的集合,即C={y| y 是 B 的上界}, 则 C 的最小元 a 称为 B 的最小上界或上确界。 (8)如果 C 是 B 的所有下界的集合,即C={y| y 是 B 的上界}, 则 C 的最大元 a 称为 集合与关系 第 B 的最大下界或下确界。 3 定理3.包含排斥原理) 有|A∪B||A|+|B||A∩B|。 20( 对有限集合 A 和B,= 章 3.例题精选 2 69 例3.判断下列属于和包含关系是否正确。 1 (1)... 。 (2).∈. 。 (3)..{.}。 (4).∈{.} 。 (5){b}.{b,a, c a,a,c,{b,}} 。 (6){b}∈{b,a, a,a,c,{b}} 。 (7){b,{{b}}} 。 a,a, b}.{a, (8){b}∈{b,{{b}}} 。 a,a,a, (9)若a.A,A.P(B), 则a.P(B)。 (10)若a∈A,A∈P(B), 则a∈P(B)。 解:(1)、(3)、(4)、(5)、(6)、(7)、(9)为真,其余为假。由空集是任何集合的子集,所以 (1)、(3)为真。判断元素是否属于集合,是要检查元素作为一个整体是否在集合中出现,不 难判断(4)、(6)为真。判断集合A.B,需要依次检查 A 的每个元素是否在 B 中出现,不难 判断(5)、(7)为真。根据包含具有传递性,属于是不能传递的,因此判断(9)为真,(10)为假。 另外,也可以用文氏图或包含的谓词定义来判断。 例3.证明:(B)C=(C)B-=B∪C。 2 A--A--(C)A 证明:证明两个集合相等有三种方法,利用集合恒等式、利用集合相等的定义以及利用 文氏图。本题仅用前两种方法解题。 方法一:利用集合恒等式。 (A-B)- C =(A∩~B)∩~ C (补交转换) =A∩(~B∩~C)(结合律) =A∩~(B∪C)(德·摩根律) =A-B∪ C (补交转换) (A-C)-(B-C)=(A∩~C)∩~(B∩~C)(补交转换 ) =(A∩~C)∩(~B∪C)(德·摩根律 ) =(A∩~C∩~B)∪(A∩~C∩C)( 分配律 ) =(A∩~C∩~B)∪. (矛盾律、零律 ) =A∩~(B∪C)(同一律 ) =A-B∪ C (补交转换 ) 方法二:利用集合相等的定义,互为子集则相等。即要证A=B,任取x,然后完成推理 过程:x∈A.….x∈B。 x∈(A-B)- C .x∈A∧x.B∧x. C .x∈A-C∧x. B 离散数学解题指导(第3 版) 7 0 .x∈(A -C)-B .x∈A ∧x.B∧x.C .x∈A ∧.(x∈B∨x∈C) .x∈A -B∪C x∈(A -B)-C .x∈A ∧x.B∧x.C .(x∈A ∧x.B∧x.C)∨(x∈A ∧x.C∧x∈C) .(x∈A ∧x.C)∧(x.B∨x∈C) .x∈(A -C)∧.(x∈B∧x.C) .x∈A -C∧x.(B-C) .x∈(A -C)-(B-C) 例3.3 列出集合A ={2,3,4}上的恒等关系IA ,全域关系EA ,小于或等于关系LA ,整 除关系DA 。若|A|=n,则A 上有多少个不同的二元关系?IA 中有多少个有序对? EA 中 有多少个有序对? 解:IA ={<2,2>,<3,3>,<4,4>}。 EA ={<2,2>,<2,3>,<2,4>,<3,2>,<3,3>,<3,4>,<4,2>,<4,3>, <4,4>}。 LA ={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}。 DA ={<2,2>,<3,3>,<4,4>,<2,4>}。 根据关系的定义及关系有序对个数知,A 上有2n2 个不同的二元关系,IA 中有n 个有序 对,EA 中有n2 个有序对。 例3.4 设A ={<1,2>,<2,4>,<3,3>},B ={<1,3>,<2,4>,<4,2>},求: A ∪B,A ∩B,domA ,domB,dom(A ∪B ),ranA ,ranB,ran(A ∩B ),fld(A -B ),A -1, A..B,B3。 解:此题涉及的知识点是关系的基本运算。 A ∪B={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>}。 A ∩B={<2,4>}。 domA ={1,2,3}。 domB={1,2,4}。 dom(A ∪B)={1,2,3,4}。 ranA ={2,3,4}。 ranB={2,3,4}。 ran(A ∩B)={4}。 A -B={<1,2>,<3,3>}。 fld(A -B)={1,2,3},A -1={<2,1>,<4,2>,<3,3>}。 A..B={<1,4>,<2,2>}。 B3={<2,2>,<4,4>}..B={<2,4>,<4,2>}。 例3.5 证明关系的包含和相等。 (1)(A -B)× (C-D ).(A ×C)-(B×D )。 (2)设R 是A 到B 的关系,S 是B 到C 的关系,T 是C 到D 的关系,则(R..S)..T = 集合与关系 第 R..(S..T)。 3 (3)设R1 和R2 是 A 上的关系,证明r(R1∪R2)=r(R1)∪r(R2)。 章 证明:关系的包含和相等的方法与证明集合的包含和相等类似。 x,B)×(.x∈(D)( (1)任取(y)∈(A-C-D)A-B)∧y∈(C-根据笛卡儿积定义) 71 .(x∈A∧x.B)∧(y∈C∧y.D) .(x,A×C)∧(y).(B×D) y)∈(x, y)∈(- ( 所以,(A-B)×(C-D).(A×C)- . (B(x×, D)。 A×C)B×D) (2)任取∈ ( R.... T ..z(z>∈R..w>∈T)( ..z(.y(∈S)∧∈R∧∈T) ..z.y( ∈S)∧∈R∧∈T) ..y.z(∈T) y>∈R∧(z>∈S∧∈T) y>∈R∧.z(z>∈S∧∈S..T) y>∈R∧∈R..( S..T) 所以,(R..S)..T=R..(S..T),即关系的复合运算满足结合律 。 (3)因为R1.R1∪R2,R2.R1∪R2, 16可知r(R1).r(r(R2). 由定理3.R1∪R2), r(R1∪R2),从而有r(R1)∪r(R2).r(R1∪R2)。反之,由R1.r(R1),R2.r(R2),得 R1∪R2.r(R1)∪r(R2),又知道r(R1)∪r(R2)是自反的,即r(R1)∪r(R2)是包含R1∪ R2 的自反关系,根据闭包的最小性,从而得到r(R1∪R2).r(R1)∪r(R2)。根据集合相等 的定义,得到r(R1∪R2)=r(R1)∪r(R2)。 例3.分析定义在集合A={2,上的下列关系具有哪些性质。 6 1,3} (1)R1={<1,1>,<1,2>,<1,3>,<3,3> }。 (2)R2={<1,1>,<1,2>,<2,2>,<2,3> }。 (3)R3=. 。 (4)R4=A×A。 解:(1)R1 具有反对称性、传递性。因为<2,2>.R1,所以R1 不具有自反性。因为 <1,3>∈R1, 2>∈R1,<2,1>.R1,所以 1>,<3,所以R1 不具有反自反性。因为<1, R1 不具有对称性。 (2)R2 具有反对称性。因为<1,2>,<2,3>∈R2,而<1,3>.R2,所以R2 不具有 传递性。 (3)R3 具有反自反性、对称性、反对称性和传递性。注意,空关系是一个特殊的关系 , 关于空关系有以下性质:空集上的空关系具有自反性、对称性、反对称性和传递性。非空 集 合上的空关系具有反自反性、对称性、反对称性和传递性 。 (4)R4 全关系具有自反性、对称性、传递性 。 例3.(1)设A={1,2,…,8},如下定义 A 上的关系R:R≡{|y∈ A ∧ x≡y(mod3)},其中x≡y(mod3)表示 x 与 y 模3相等,验证 R 为 A 上的等价关系。 令S={|.c∈A, Rc 离散数学解题指导(第3版) 解:(1)因为.x∈A,有x≡x(mod3), 所以关系 R 具有自反性。 .x,y∈A,若x≡y(mod3), 则有y≡x(mod3), 所以关系 R 具有对称性。 .x,z∈A, y≡z(momo 传递性。 y,若x≡y(mod3),d3), 则有x≡z(d3), 所以关系 R 具有 由等价关系的定义可知 R 为 A 上的等价关系。 关系 R 的关系图如图3-1所示。 72 图3-例3. 17关系 R 的关系图 不难看出,图3-1关系图被分为三个互不相连通的部分。每部分中的数两两都有关系, 不同部分中的数则没有关系。每一部分中的所有的顶点构成一个等价类,[1]=[4]=[7]= {1,4,7},[2]=[5]=[8]={2,5,8},[3]=[6]={3,6}。 (2)证明:因为 R 是 A 上的等价关系,所以 R 是自反的、对称的和传递的。 .a∈A,因为 R 自反, a>∈A。取c=∈S, 存在c∈A,使得∈R。因为 R 对称,所以∈S, c>∈R,∈ R,∈R,a>∈S, .,∈R,∈S, d∈A, c>∈R,∈R, ∈R。因为 R 传递, b>∈R,e>∈R,e>∈S, 由等价关系的定义S,也是 A 上的等价关系 。 例3.分别画出下列各偏序集 的哈斯图,并找出 A 的极大元、极小元、最大 元和最小元 ,,,,,,(e>}∪IA (2)A={a,b,d,}∪IA 。 8 c,e},.={ 解:利用偏序集哈斯图作图法:①以圆圈表示元素;②若x.y,则 y 画在 x 的上层;③ 若 y 覆盖x,则连线;④不可比的元素可画在同一层。由此可得到哈斯图,如图3-2所示。 图3- 2 例3. 8哈斯图 集合与关系 图3-2(a)对应(1),其极大元是e,极小元是a,最大元是e,最小元是a。图3-2(b)对应 (2),其极大元是a、b、d、e,极小元是a、b、c、e,没有最大元和最小元。 例3.在Sh506S计算器上,30的值为1073741820 。如果这个值是正确的, 9 arpEL-2 那么228=230/4的最后一位一定是5。显然,2的幂不可能是奇数,所以230的最后一位是错 误的。那么,230的最后一位数字是什么? 解:两个正整数有相同的个位数当且仅当它们模10同余,但在Z10中,[230]=[26= [6=[6=[=[4], 30的最后一位为4。实际上,30= 5] 32]2]26]64]=[因此,221073741824 。 3.应用案例 3 3.1 同余关系在出版业中的应用 3. 同余经常应用于检错码。本例将描述这种编码在出版业中的应用。从1972年开始,世 界上任何地方出版的图书都带有一个10位的数字编码,这个编码称为国际标准书号 (nentoatnadBoeISBN )。例如,ecnene有 ItrainlSadrokNumbr,Spne和VadnEydn撰写的《 限数学》的ISBN是0-673-38582-5。这种编号给图书提供了一个标准的标识,相对于用作 者、标题和版本来标识每本书的方法,这种方法使出版商和书店可以更容易地将库存和记账 过程计算机化。 一个ISBN由4部分组成:组号、出版商号、出版商指定的标识号、校验位。在ISBN 0-673-38582-5中,组号0表示这本书是在英语国家(澳大利亚、加拿大、新西兰、南非、英国 或美国)出版的,673标识出版商,第三组数字38582在该出版商所出版的所有书中标识出 这本书,最后一位数字5是校验位,用于检测复制和传送ISBN过程中产生的错误。利用校 验位,出版商常可以检测出错误的ISBN,从而避免由错误的订单所导致的昂贵的运输费。 校验位有11种可能的值:0、1、2、3、4、5、6、7、8、9或X(X代表10 )。校验位是按下列 方法计算出来的:分别用10 、9、8、7、6、5、4、3和2乘以ISBN的前9位,并将这9个乘积相 加得到y,校验位 d 是满足y+ d ≡0(mod11)的数字。例如,《有限数学》的校验位为5, 因为 10×0+9×6+8×7+7×3+6×3+5×8+4×5+3×8+2×2 =0+54+56+21+18+40+20+24+4=237 而237+5=242≡0(mod11 )。 类似地,RobCalan所著图书ArtificialInteligence 的ISBN是0-333-80136-9。这 里,校验位是9,因为 10×0+9×3+8×3+7×3+6×8+5×0+4×1+3×3+2×6 =0+27+24+21+48+0+4+9+12=145 而145+9=154≡0(mod11 )。 通过同余关系产生的校验位可以发现ISBN码的单位错误。 证明:假设x1,x2,…,x10变成y1,y2,…,只改变其中的第 i 位,即yi ≠xi,而 k≠i)。 y10, yk =xk ( 假设xi>yi,则存在整数使得xi=yi+a,其中1≤a≤10 。 第 章 73 74 离散数学解题指导(第3版) 因此 1y1+2y2+3y3+4y4+5y5+6y6+7y7+8y8+9y9+10y10 =1i1)xi-yi+(xi+1+…+10x10 x1+…+(-1+ii+1) =1i1)-xi+i(a)i+1)x10 x1+…+(-xi1+i-+(xi+1+…+10 =Σixi+i(-a) 注意到Σixi≡0mod(11), 这是因 为 1x1+2x2+3x3+4x4+5x5+6x6+7x7+8x8+9x9 ≡x10 mod(11) 则必有 1x1+2x2+3x3+4x4+5x5+6x6+7x7+8x8+9x9+10x10 ≡0mod(11) 如果y1,y2,…,y10 是正确的ISBN 号,则Σiyi≡0mod(11 )。 故y1,由此i(-a)≡0mod(11), 则11|ia,但是1≤i≤10,1≤a≤10,不可能, y2,…, y10 不是正确的ISBN 号。 3.2 拓扑排序在建筑工序中的应用 3. 问题描述:建造一所房屋所需要的各项任务所需的天数及其直接的前继任务如表3-1 所示。如果所有的任务由一组每次只能进行一项任务的人来完成,那么这些任务应该以怎 样的顺序来完成? 通过同时进行某些任务,多少天内可以完成所有的任务? 表3- 1 一组建筑任务所需的天数及其直接的前继任务 任务天数前继任务任务天数前继任务 A场地准备4 没有H电气设施3 E B地基6 A I绝缘2 G,H C排水设施3 A J幕墙6 F D骨架10 B K墙纸5 I,J E屋顶5 D L清洁和油漆3 K F窗2 E M地板和装修4 L G管道4 C,E N检验10 I 解答:在这个建筑项目中,某些任务只有等到别的任务完成后才能开始。例如,任务G 即铺设管道只有等到任务C和E完成后才可以开始。另外还有一些条件在表3-1中没有明 确地表示出来,如任务G只有等任务A、B、C、D和E都完成后才能开始,这是因为任务E 必须等任务D完成后才能开始,而任务D必须在任务B完成后才能开始,任务B又必须等 待任务A结束。在图3-3中考察任务之间的所有依赖关系更容易,其中任务 X 到任务 Y 的 箭头表示任务 Y 必须在任务 X 及其之前的所有任务都完成后才可以开始。 通过约定所有的箭头由左指向右,从而省略图3-3中的所有箭头,则所得到的图如图3-4 集合与关系 所示。 第3章 75 图3- 3 建筑工序图(1) 图3- 4 建筑工序图(2) 由于任务必须依次地完成,所以要在任务集合上寻找一个包含原偏序R(图3-5所示的 哈斯图描述了R,等同于图3-4)的全序T。即希望得到一个全序T,满足R.T。 为了说明拓扑排序算法的使用,需要为建筑的例子中的任务集合 S 构造一个全序,这 个例子包含给定的偏序。从图3-5所示的哈斯图可以看出,A是 S 的唯一的极小元。因 此,取s1=A,并从 S 中删除A。与这个新的集合对应的哈斯图如图3-6所示。这里,B和 C都是极小元,可以任意地选择其中的一个,假设取s2=C 。对应于新集合的哈斯图如图3-7 所示。因为B是这个新集合中唯一的极小元,所以取s3=B 。 图3- 5 建筑工序哈斯图(1) 图3- 6 建筑工序哈斯图(2) 图3- 7 建筑工序哈斯图(3) 按照这种方式继续,选取s4=D,s6=G,s8=I,s10=J, s5=E,s7=H,s9=F,s11=N, s12=K,s14=M 。于是,A、C、B、D、E、G、H、I、F、J、N、K、L、M就是一个这样的序列: s13=L, 它包含了任务的给定的偏序,且任务可按照它来进行。 当然,可能还会有其他同类序列,因为在算法的各个阶段,步骤2中可能存在多个可供 选择的极小元。另一个可能的序列是A、B、D、E、F、J、C、H、G、I、K、L、M、N。每一个这样 的序列都对应于一个 S 中的任务的全序,它包含了给定的偏序,并且是这样形成的一个序 关系:定义 X 与 Y 是相关联的当且仅当 X = Y 或 X 在序列中出现在 Y 之前。 通过同时进行某些任务,在45 天内就可以完成所有的任务(从而完全造好房屋)。计算 过程略。 76 离散数学解题指导(第3版) 3.等价关系在软件测试等价类划分中的应用 3.3 问题描述:给定一程序,从对话框中读取三个整数值,其数据范围是1~200 。这三个整 数值代表了三角形三条边的长度。程序输出信息,指出该三角形究竟是不规则三角形、等腰 三角形还是等边三角形,或者不构成三角形。运用等价类概念,设计测试用例。 解答: b,赋值分类如下。 算法分析:给集合{a,c} 1 存在输入值不在有效范围的情况或者输入的边长个数不对的情况 5) ) 1.1 有一个输入值无效(某边的长度为负数,或者为0,或者为非整数(如2. (又可以细分为 ) 1.1a无效 1. 1.2b 无效 1. 1.3c无效 1. 2 有两个输入值无 效 (又可以细分为 ) 1. 2.a、 1.1 b无效 2.a、 1.2 c无效 1.3b 、c无效 2. 3 三个输入值均无效 1. 4 输入的边长个数不对(如仅输入了两个数 ) 2 不存在输入值不在有效范围的情况(即输入值均在有效范围 ) 1. 2.两边之和大于第三边) 1 构成三角形的情况( 2.1 三个元素均不相等( 1.不规则三角形) 2.2 两个元素相等( 三种情况:①3,4;②3,3;③4,3) 1.等腰三角形, 3,4,3, 2.3 三个元素均相等( 1.等边三角形) 2 不构成三角形的情况 2. 2.1 三个元素值均不相等 2. 2.2.2 两边之和等于第三边(如①1,2,3;②1,3,2;③3,1,2) 2.2.4;②1,2;③4, 3 两边之和小于第三边(如①1,2,4,1,2) 按上述安排设计测试用例输入,此外除了定义输入值,是否定义了程序针对该输入值的 预期输出值? 用例设计如下。 (1)一般等价类测试用例,如表3-2所示。 表3- 2 一般等价类测试用例 测试用例 a b c 预期输出 WN1 5 5 5 等边三角形 WN2 2 2 3 等腰三角形 WN3 3 4 5 不等边三角形 WN4 4 1 2 非三角形 (2)a、b、 c 中有一个无效值的等价类测试用例,如表3-3所示。 集合与关系 表3- 3 a、b、 c 中有一个无效值的等价类测试用例 测试用例 WR1 WR2 WR3 WR4 WR5 WR6 a -1 5 5 201 5 5 b 5 -1 5 5 201 5 c 5 5 -1 5 5 201 预期输出 a 取值不在所允许的取值值域内 b 取值不在所允许的取值值域内 c 取值不在所允许的取值值域内 a 取值不在所允许的取值值域内 b 取值不在所允许的取值值域内 c 取值不在所允许的取值值域内 第 章 77 (3)a、b、 c 中有二个及三个无效值的等价类测试用例,如表3-4所示。 表3- 4 a、b、 c 中有二个及三个无效值的等价类测试用例 测试用例 a b c 预期输出 WS1 -1 -1 5 a、 b 取值不在所允许的取值值域内 WS2 5 -1 -1 b、 c 取值不在所允许的取值值域内 WS3 -1 5 -1 a、 c 取值不在所允许的取值值域内 WS4 -1 -1 -1 a、b、 c 取值不在所允许的取值值域内 说明:等价划分是一种黑盒测试方法,它将程序的输入划分为若干数据类,从中生成测 试用例。等价划分试图定义一个测试用例以期发现一类错误,由此减少所需设计测试用例 的总数。 等价划分的测试用例设计是基于对输入条件的等价类的评估。等价类表示输入条件的 一组有效的或无效的状态。通常情况下,输入条件要么是一个特定值、一个数据域、一组相 关的值,要么是一个布尔值。可以根据下述指导原则定义等价类。 ①若输入条件指定一个范围,则可以定义一个有效和两个无效的等价类。 ②若输入条件需要特定的值,则可以定义一个有效和两个无效的等价类。 ③若输入条件指定集合的某个元素,则可以定义一个有效和一个无效的等价类。 ④若输入条件为布尔值,则可以定义一个有效和一个无效的等价类。 通过运用设计等价类的指导原则,可以为每个输入域数据对象设计测试用例并执行它。 选择测试用例以便可以一次测试一个等价类的尽可能多的属性。 3.习题解答 4 3.判定下列断言的对错。 1 a∈{{}} 。 (2){ aa, , cc} 。 (1) a a}.{b, (3).∈{b,}。 (4)..{b,} 。 a, a, ac ,c,{b,}} 。 (5){b}.{b,a, c 78 离散数学解题指导(第3版) (6){{4}.{{1}。 a},1,3,a},3,4, (7){b}.{b,{b}} 。 a,a,a, (8)如果A∩B=B,则A=E。 解:(1)×。(2)√。(3)×。(4)√。(5)√。(6)×。 (7)√。(8)×。 3.2 (1)将“大于3而小于或等于7的整数集合”用集合表示出来。 (2)将“小于10 的素数”集合表示出来。 解:(1){x|x>3∧x≤7∧x∈Z}或{4,5,6,7} 。 x|2,3,5, (2){x<10∧ x 是素数}或{7}。 3.3 若A、 B 都是集合,那么 A 能同时既是 B 的元素又是 B 的子集吗? 举例说明。 解:可以。例如,A={B={{a,c a},a},b,}。 3.化简下列集合表达式。 4 (1)((A∪B)∩B)-(A∪B) 。 (2)((A∪B∪C)-(B∪C))∪A 。 (3)(B-(A∩C))∪(A∩B∩C) 。 (4)(A∩B)-(C-(A∪B)) 。 B=. 解 。 :(1)((A∪B)∩B)-( A ∪B)= B -( A ∪B)= B ∩~( A ∪B)= B ∩~ A ∩~ (2)((A∪B∪C)-(B∪C))∪A=((A∪B∪C)∩~(B∪C))∪A=A。 (3)(B-(A∩C))∪(A∩B∩C)=(B∩~(A∩C))∪(B∩(A∩C))=B∩E=B。 (4)(A∩B)∩~(C∩~(A∪B))=( A ∩B)∩(~C∪ A ∪B)=(( A ∩B)∩~C)∪ ((A∩B)∩(A∪B))=((A∩B)∩~C)∪(A∩B)=A∩B。 3.写出下列集合的子集。 5 (1)A={b}, a,{c} 。 (2)B={.} 。 (3)C=. 。 解:(1).,{b}},{a,{a,b},a,{ c (2).,{.}。a},{{c},{b}},{c},{{c},{b},}。 (3).。 3.6 设集合A={1,2,3,4},B={2,3,5}, 求:A∪B,A∩B,A-B,B-A,A..B。 解:A∪B={1,3,5}。 A∩B={2,3}。 2,4, A-B={1,4}。 B-A={5}。 A7 ..B=(A-B)∪(B-A)={1,4,5}。 n2<50, 设全集E=N,有下列子集:A={1,2,8,10},B={n∈N},C={ n 可 3. n∈N},i<6 且i, n|n| 以被3整除,且n<20,i,n∈N}。求下列集合 。 (1)A∪(C∩D)。 D={n|n= 2 (2)A∩(B∪(C∩D)) 。 集合与关系 (3)B-(A∩C) 。 (4)(~A∩B)∪D 。 解:(1)A∪(C∩D)=A∪.=A={1,2,8,10 } 。 (2)A∩(B∪(C∩D))=A∩(B∪.)=A∩B={1,2} 。 (3)B-(A∩C)=n|n∈N}0,2,4,6, B-.={n2<50,={1,3,5,7}。 (4)(~A∩B)∪D={0,3,4,5,6,7}∪{1,2,4,8,16,32}={0,1,2,3,4,5,6,7,8,16, 32 }。 31.8 )A 设 - A{x= , {x,x, (}。 y,{y},.}。求下列各式的结果。 x, y -A。 (2){{y}} (3).-A 。 (4)A-{.} 。 (5)P(A) 。 解:(1){{y},.} 。 (2).。 x, (3). x 。 ,x, (4){y,{y}} 。 (5){.,{y},{.},{{y}},{y},{y,.},{x,x,y} , x},{x,x,x,.},{x,{y}},{{y}, {{x,x,x,x,.},{{y},x,x,x,x, y},.},{y,.},{{y},x,y,.},{{y},y},{{y},y, .}}。 a,{}}。求:P(P(A))。 3.9 已知A={aA),P( 解:P(A)a},{{a,{}}} 。 ={.,{a}},{ a P(P(A))={.,{.},{{a}}},{{a}}},{.,{a}},{.,{{a}}},{.,{a, a}},{{{a,{ {a},{{a},{a}}},{{{a,{a},{{a},{a, a}}},{{a}}},{{a,{a}},{a}}}},{.,{a}}},{.,{ {a}}},{.,{{a}},{a}}},{{a}},{a}}},{.,{a}},{a}}}}, 个元素。 a,{a},{{a,{a},{{a,{共16 3.10 设 A 和 B 分别表示整数1985 和1986 的正因子集,而P(A)和P(B)分别表示 A 和 B 的幂集。求: (1)P(A)∩P(B)。 (2)P(A)-P(B)的基数。 (3)P(B)-P(A)的基数。 解:首先用枚举法表示集合A={1,5,397,1985}和集合B={1,2,3,6,331,1986 }。 (1)P(A)∩P(B)={.,{1}}。 (2)24-2=14 。 (3)26-2=62 。 3.令x={{5},4}}, 4)。 11 2,4,{求:∩(∪x 解:∪x={2,5,0,1,3,4},∪x-4=∪x-{0,1,2,3}={4,5},∩(∪x-4)=4。 3.12 证明:(1)P(A)∪P(B).P(A∪B) 。 (2)P(A)∩P(B)=P(A∩B) 。 第 章 79 离散数学解题指导(第3 版) 8 0 证明:(1)若任意取x∈P(A)∪P(B),则x∈P(A )或x∈P (B),于是x.A 或x. B,所以x.A ∪B,即x∈P(A ∪B),于是有P(A)∪P(B).P(A ∪B)。 (2)若任意取x∈P(A)∩P(B),则x∈P (A )且x∈P (B),于是x.A 且x.B,所 以x.A ∩B,即x∈P(A ∩B),于是有P(A)∩P(B).P(A ∩B)。反过来,若任意取x∈ P(A∩B),则x.A∩B,所以x.A 且x.B,即x∈P(A)且x∈P(B),于是有x∈P(A)∩ P(B),即P(A ∩B).P(A)∩P(B),所以P(A)∩P(B)=P(A ∩B)。 3.13 令x={{{1,2},{1}},{{1,0}}}。求:∪x,∩x,∪∩x,∩∩x,∪∪x,∩∪x。 解:∪x={{1,2},{1},{1,0}}。 ∩x=.。 ∪∩x=.。 ∩∩x 无定义。 ∪∪x={1,2,0}。 ∩∪x={1}。 3.14 证明:A ..B=(A ∪B)-(A ∩B)。 证明:A ..B=(A -B)∪(B-A)=(A ∩~B)∪(B∩~A)=(A ∪B)∩(~B∪B)∩ (A ∩~A)∩(~A ∪~B)=(A ∪B)∩(~A ∪~B)=(A ∪B)∩~(A ∩B)=(A ∪B)- (A ∩B)。 3.15 试证明对任意集合A 、B、C,等式(A -B )∪(A -C)=A 成立的充分必要条件 是A ∩B∩C=.。 证明:若(A-B)∪(A-C)=A,则(A-B)∪(A-C)=A-(B∩C),即A-(B∩C)=A, 任取x∈A 则x .(B ∩C),综上A ∩B ∩C =.。若A ∩B ∩C =.,则任取x ∈A 有 x.(B∩C),因此,x∈A -(B∩C)。所以A .A -(B∩C),另一方面A -(B ∩C).A 显 然成立,所以A -(B∩C)=A ,即(A -B)∪(A -C)=A 成立。 3.16 (1)若A -B=B,问A 、B 分别是什么集合? 请说明理由。 (2)证明:(A -B)-C=A -(B∪C)=(A -C)-B=(A -C)-(B-C)。 解:(1)B=.,A =.时,A -B=B。 如果x∈A -B,则x∈A ∧x.B,而A -B=B,得到x∈B,矛盾。 因此,B=A -B=.,A -B=A -.,从而,A =.。 (2)x∈(A -B)-C .x∈A ∧x.B∧x.C .x∈A -C∧x.B .x∈(A -C)-B .x∈A ∧x.B∧x.C .x∈A ∧.(x∈B∨x∈C) .x∈A -(B∪C) x∈(A -B)-C .x∈A ∧x.B∧x.C .(x∈A ∧x.B∧x.C)∨(x∈A ∧x.C∧x∈C) .(x∈A ∧x.C)∧(x.B∨x∈C) .x∈(A -C)∧.(x∈B∧x.C) .x∈A -C∧x.(B-C) .x∈(A -C)-(B-C)。 集合与关系 第 3.用谓词公式对集合 A 和 B 证明:A-(A∩B)=A-B。 17 3 证明:任取x∈ A -( A ∩B), 即x∈ A ∧x. A ∩B,即x∈ A ∧(x. A ∨x.B), 即 章 (x∈A∧x.B)∨F,即x∈A-B。所以A-(A∩B).A-B。另一方面A∩B.B,所以 A-B.A-(A∩B), 原命题得证。 81 3.(1)证明:“ A 为有限集”等价于“ A 的任何子集为有限集”。 18 (2)说明在下列各条件下集合 A 与 B 有什么关系,或者 A 与 B 是什么集合。 ①A∩B=A。 ②A-B=B-A。 =A。③(A-B)∪(B-A) 证明:(1)充分性显然。必要性:设|A|=n, B .A,则|B|≤|A|=n,所以 B 为有 限集。 (2)①A.B。②A=B。③B=., A 任意。 3.计算或简单回答以下各题,其中A、 B 为任意集合。 19 (1)∪{A} 。 (2)P({.,1}) 。 (3){1,2}×{b,} 。 a, c (4)A..B=. 的充要条件是什么 ? (5) A 与P(A)等势吗 ? 解:(1)A 。 (2){.,{1},{.},{.,1}} 。 (3){<1,b>,<1,a>,<2,c>} 。 a>,<1,c>,<2,b>,<2, (4)充要条件是A=B。 (5)不等势。 3.假设A、B、证明:(B)C-D).(-(B×D)。 20 C 为集合, A-×(A×C) 证明:任取∈(A-×(则x∈(B),C-D) ( B)C-D), A-y∈(根据笛卡儿积 的定义), 即x∈ A 且x.B,.(所以 y∈ C 且y.D,y>∈(B×D), ∈(A×C)-(B×D), 即(A-B)×(C-D).(A×C)-(B×D)。 3.设集合A={b},1,3},d}。求:A×B×C 和B×A。 21 a,B={2,C={ 解:A×B={,,,,, }。 A×B×C={<,d>,<,d>,<,d>,<,d>, <,<}。 d>,3> , B×A={<1,b>,<2,b>,<3,b>} 。 a>,<1,a>,<2,a>,<3, 证明:如果X={0},0},1}, 则(Y×Z)。 证明:因为( X ×Y)×Z ={<<0,0>,1>}, X ×( Y ×Z)={<0,<0,1>>}, 而 <0,0>≠0,所以(×Z≠ X ×( 3.22 Y={Z={X×Y)×Z≠ X ×( X×Y)Y×Z)。 3.设集合A={1,2,3}, 用列举法给出 A 上的恒等关系IA ,全关系EA , A 上的小于 23 关系LA ={|y∈A∧x,<2,2>,<3,3> }。 全关系EA ={<1,2>,<1,1>,<2,3>,<3,2>, 1>,<1,3>,<2,2>,<2,1>,<3, 离散数学解题指导(第3 版) 8 2 <3,3>}。 小于关系LA ={<1,2>,<1,3>,<2,3>}。 IA 的关系矩阵为 1 0 0 0 1 0 0 0 1 é . êêêê ù . úúúú 。 EA 的关系矩阵为 1 1 1 1 1 1 1 1 1 é . êêêê ù . úúúú 。 LA 的关系矩阵为 0 1 1 0 0 1 0 0 0 é . êêêê ù . úúúú 。 3.24 设集合A ={1,2,3},R1与R2是A 上的二元关系分别为 R1={<1,1>,<1,2>,<2,2>,<3,2>,<3,3>}。 R2={<1,1>,<2,1>,<2,2>,<2,3>,<1,3>,<3,3>}。 (1)试分别写出R1、R2的关系矩阵。 (2)分别画出R1、R2的关系图。 (3)判定R1、R2个具有关系的哪几种性质。 解:(1)R1 的关系矩阵为 1 1 0 0 1 0 0 1 1 é . êêêê ù . úúúú ;R2 的关系矩阵为 1 0 1 1 1 1 0 0 1 é . êêêê ù . úúúú。 (2)R1 和R2 的关系图如图3-8所示。 图3-8 题3.24R1 和R2 的关系图 (3)R1 具有自反性、反对称性、传递性;R2 具有自反性、反对称性、传递性。 3.25 设集合A ={1,2,3,4,5},试求A 上的模2同余关系R 的关系矩阵和关系图。 解:R={<1,1>,<1,3>,<1,5>,<2,2>,<2,4>,<3,1>,<3,3>,<3,5>, <4,2>,<4,4>,<5,1>,<5,3>,<5,5>}。 关系矩阵为 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 é . êêêêêêê ù . úúúúúúú 。 关系图如图3-9所示。 集合与关系 第3章 8 3 图3-9 题3.25的关系图 3.26 设集合A ={1,2,3,4},A 上的二元关系为 R1={<1,1>,<1,3>,<1,4>,<2,4>,<3,3>,<4,4>}。 R2={<1,2>,<1,3>,<2,3>,<4,4>}。 R3={<1,1>,<2,2>,<3,3>,<4,4>}。 求:R1∩R2,R2∪R3,~R1,R1-R3,R1..R2。 解:R1∩R2={<1,3>,<4,4>}。 R2∪R3={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>,<4,4>}。 ~R1={<1,2>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,4>,<4,1>, <4,2>,<4,3>}。 R1-R3={<1,3>,<1,4>,<2,4>}。 R1..R2={<1,2>,<1,3>,<1,4>,<2,4>,<4,4>}。 3.27 设集合Z={a,b,c,d}上有如下关系。 R1={,,}。 R2={,,,}。 试给出关系((R1..R2)-1)2 的关系矩阵和关系图,并说明它具有什么性质以及理由。 解:R1..R2={,},(R1..R2)-1={,},((R1..R2)-1)2=.。 它具有反自反、对称、反对称和可传递性。关系矩阵为元素全为0的4×4矩阵,关系图为只 有4个顶点、没有边的平凡图。 3.28 给定集合A ={0,1,2,3},且A 中有关系为 R1={|(i,j∈A)∧((j=i+1)∨(j=i/2))}。 R2={|(i,j∈A)∧(i=j+2)}。 试写出合成关系R2..R1 的如R1 或R2 的形式的集合表示式。 解:R1={<0,1>,<1,2>,<2,3>,<2,1>},R2={<2,0>,<3,1>},R2..R1= {<1,0>,<2,1>}。 3.29 设集合A ={2,3,4},B={4,6,7},C={8,9,12,14},R1 是A 到B 的二元关系, R2 是由B 到C 的二元关系。定义:R1={|a 是素数且a 整除b},R2={| b 整除c}。求复合关系R1..R2,并用关系矩阵表示。 解:R1..R2={<2,8>,<2,12>,<3,12>}。 R1..R2 关系矩阵为 1 0 1 0 0 0 1 0 0 0 0 0 é . êêêê ù . úúúú 。 3.30 设R1、R2 和R3 分别是从A 到B、从B 到C 和从C 到D 的关系。证明:(R1..R2)..R3=