离散数学第五章集合及其运算习题答案.ppt

1、习题四,1.设A=1,2,3,4,B=0,1,4,9,12.分别把下面定义的从集合A到集合B的二元关系R用序偶的集合表示出来。 (1) xRy x|y (1,0) ,(1,1),(1,4) ,(1,9) ,(1,12) ,(2,0) ,(2,4) ,(2,12) , (3,0) ,(3,9) ,(3,12) ,(4,0) ,(4,4) ,(4,12) (2) xRy xy(mod 3) (1,1), (1,4) , (3,0) , (3,9) , (3,12) , (4,1) , (4,4) (3) xRy y/x (y-x)/2 (3,9), (3,12) , (4,9) , (4,12)

2、4.设A是含n个元素的集合，请问在A上可以定义出多少个二元关系？ 解: 因为R是A上的二元关系, R AA, 于是R 2AA, 所以共2n2个二元关系.,习题四 6,设在整数集合上定义了如下关系：确定其满足的性质,习题四 6,设在整数集合上定义了如下关系：确定其满足的性质,习题四 6,设在整数集合上定义了如下关系：确定其满足的性质,习题四 6,设在整数集合上定义了如下关系：确定其满足的性质,习题四 6,设在整数集合上定义了如下关系：确定其满足的性质,习题四 6,设在整数集合上定义了如下关系：确定其满足的性质,习题四 7,设R是集合上的一个二元关系， xRy yRz xRz ,称R是A上的一个反

3、传递关系。试举一个实际的反传递关系的例子。 解： 例如：设A=a, b, c, d 则 R1=(a, b), (b, d), (d, c) 反传递 R2=(a, b), (a, c), (d, b) 反传递、传递 R3 =(a, a), (a, b), (b, c) 不是反传递 R4 =(a, a), (b, c) 不是反传递 传递和反传递不是绝对互相排斥 实际中，如“父子关系”， “X=Y+1”关系等。,习题四 9,判定满足下述每一种条件的关系是否存在，如果存在，举例说明。 （1）既自反又反自反。 答：不存在 （2）既对称又反对称。 答：存在，例如IA （3）既传递又反传递。 答：存在 （4

4、）既自反、反对称、又传递。 答：存在，例如正整数集合上的整除关系。,习题四 8,自反性 反自反性 对称性 反对称性 传递性 RS ,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S 同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,(a,b) RS (a,b) R (a,b) S (b,a) R (b,a) S (b,a) RS 或者由RS= (RS)-1得证,(a,b) RS (a,b) R (a,b) S (b,a) R (b,a) S (b,a) RS 或者由(RS) (RS)-1 IA得证,自反性 反自反性 对称性 反对称

5、性 传递性 RS ,(a,b) RS (b,c) RS (a,b) R (a,b) S (b,c) R (b,c) S (a,c) R (a,c) S (a,c) RS,习题四 8,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S 同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性 反自反性 对称性 反对称性 传递性 RS RS ,例如A=0, 1 R=(0,1), S=(1,0) RS =(0,1), (1,0),例如A=0, 1 R=(0,1), S=(1,0) RS =(0,1), (1,0),习题四 8,设R和S都是

6、集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S 同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性 反自反性 对称性 反对称性 传递性 RS RS R-S ,例如A=0, 1 R=(0,1), (1,2), (0,2), S=(0,2) R-S =(0,1), (1,2),习题四 8,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S 同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性 反自反性 对称性 反对称性 传递性 RS RS R-S RS ,例如A=0, 1

7、R=(0,1), S=(1,0) RS =(0,0),例如A=0, 1 R=(0,0), S=(0,1), (1,0) RS =(0,1),习题四 8,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S 同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性 反自反性 对称性 反对称性 传递性 RS RS R-S RS ,例如A=0, 1 R=(0,1), (1,1) S=(1,0), (1,1) RS =(0,0),(0,1), (1,0), (1,1),例如A=0, 1, 2, 3, 4 R=(0,1), (2,3) S=(1

8、,2), (3,4) RS =(0,2),(2,4),习题四 8,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S 同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性 反自反性 对称性 反对称性 传递性 RS RS R-S RS R ,习题四 8,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S 同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,例如A=a, b,c 若R= (a,a),(b,c),自反性 反自反性 对称性 反对称性 传递性 RS RS R-S

9、RS R R-1 ,习题四 8,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S 同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,设R是集合A上的一个二元关系。证明： （1）R是自反的 IAR 证明：当R是自反时，任取(x,x) IA,必有(x,x) R IAR 当IAR时，R= IA R，故R含有所有(x,x) 序偶，故自反。 （2） R是反自反的 R IA= 证明: 当R是反自反的，任何(x, y) R, 必有xy, 故R IA= ; 当R IA= 时, R中无(x, x)序偶，故反自反。 （3）R是对称的R = R-1 证

10、明: 当R是对称的，任(x, y) R, 必有(y, x) R，即(y, x) R-1 ，必有(x, y) R-1, 故R = R-1 当R = R-1的， R=R R-1 ，则对任何(x, y) R, 必有(y, x) R-1 R ，故R对称,习题四 10,设R是集合A上的一个二元关系。证明： （4） R是反对称的R R-1 IA 证明：当R是反对称时，任取(x, y) R R-1 ，则(x, y) R (x, y) R-1 (x, y) R (y, x) R x=y，所以R R-1 IA 当R R-1 IA时，如果 xy,则(x, y) R (x, y) R-1 ，即(x, y) R (y

11、, x) R R是反对称的。 （5） R是传递的 R2 R 证明: 当R是传递的，取(x, z) R2, 即( y)(x, y) R (y, z) R ，于是(x, z) R R2 R 当R2 R时, 任取(x, y), (y, z) R, 则(x, z) R2 R，故R传递。,习题四 10,设 A=a,b,c,d,e,f,g,h, A上的二元关系R对应的关系图如图，求使Rm= Rn的最小正整数m和n (mn),习题四 13,a,b,c,d,e,f,h,g,R1=R14=R17= =R13k+1 (周期为3的循环) R2=R26=R211= =R25k+1 (周期为5的循环) 所以R= R15

12、k+1 (R1和R2共同周期为15) 取m=1, n=16,有R=R16,R1,R2,习题四 15.,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵,

13、并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对

14、应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 15,a,b,c,d,e,f,h,g,求关系图对应的关系矩阵, 并求其传递闭包,习题四 16,(2)s(R1 R2)= s(R1) s(R2), 证明: s(R1 R2)= (R1 R2) (R1 R2)-1 = (R1 R2) (R1-1 R2-1)= (R1 R1-1) (R2 R2-1) = s(R1) s(R2) s(R1 R2) s(R1) s(R2) 证明: R1 R2

15、 R1 s(R1 R2) s(R1) s(R1 R2) s(R2) s(R1 R2) s(R1) s(R2),设R1和R2是集合A上的二元关系,证明:,(3)t(R1 R2) t(R1) t(R2) 证明: t(R1) t(R2) = (R1 R12 ) (R2 R22 ) =(R1 R2 ) (R12 R22) (R13 R23) (R1 R2 ) (R1 R2)2 (R1 R2)3 = t(R1 R2) 或者 R1 R2 R1 t(R1 R2) t(R1) t(R1 R2) t(R2) t(R1 R2) t(R1) t(R2),习题四 16.,设R1和R2是集合A上的二元关系,证明:,习题

16、五 1.,设A=(a,b)|a,b N a0 b0 ，定义A上的二元关系R=(a,b), (c,d)|ad=bc，证明：R是A上的等价关系。 证明: 因为(a,b)R(c,d) ad=bc 自反性: (a,b), ab=ba (a,b)R(a,b) 对称性: (a,b)R(c,d) ad=bc cb=da (c,d)R(a,b) 传递性: (a,b)R(c,d) (c,d)R(e,f) ad=bc cf=de af=be (a,b)R(e,f) 所以R是A上的等价关系。,习题五 2.,定义复数集合上的子集合C1=a+bi | i2=-1, a,b R, a 0，在C1 上定义关系S为：(a+b

17、i)S(c+di) ac0。证明S是C1上的一个等价关系，并给出S的等价类的几何说明。 证明: 因为(a+bi)S(c+di) ac0 (a,b R,a 0, c 0) r: a 0, a20 (a+bi)S (a+bi) s: (a+bi)S(c+di) ac0 ca0 (c+di)S (a+bi) t: (a+bi)S(c+di) (c+di)S(u+vi) ac0 cu0 au0 (a+bi)S(u+vi) 综上，S是C1上的一个等价关系。 由于ac0，必须a 0, c0且a和c同号，故S只有2个等价类，其一是1=a+bi | a0，另一个是-1=a+bi | a0，它们分别对应于复平面

18、上右半部和左半部。,习题五 4.,试确定在4个元素的集合上可以定义出的等价关系数目。 解：A=a,b,c,d可产生的分划如下： 含一个等价类 S1=a,b,c,d 含二个等价类 1-3型: S2=a,b,c,d, S3=b,a,c,d , S4=c,a,b,d S5=d,a,b,c 2-2型: S6=a,b,c,d, S7=a,c,b,d, S8=a,d,b,c 含三个等价类, 1-1-2型: S9=a,b,c,d, S10=a,c,b,d, S11=a,d,b,c, S12=b,c,a,d, S13=b,d,a,c, S14=c,d,a,b, 含四个等价类: S15=a,b,c,d 所以共个

19、,习题五 7.,设Mn是全体n阶矩阵的集合.如果对矩阵A,B M,存在可逆矩阵P M使得A=PBP-1,则记为AB. 证明: 是Mn上的等价关系. 证明: r: 设E是单位矩阵, 则A, A=EAE-1 AA s: AB A=PBP-1 P-1AP=B B=P-1A(P-1)-1 BA t: AB BC A=PBP-1 B=QCQ-1 A=P(QCQ-1)P-1 A=(PQ)C(PQ)-1 AC 所以是Mn上的等价关系.,习题五 8.,设A是由54的正因子构成的集合,”|”表示整除.作出偏序集对应的Hasse图.找出最大元最小元,求有多少个包含元素最多的全序子集 A=1，2，3，6，9，18，27，54 COVER(|)=(1,2), (1,3), (2,6), (3,6), (3,9), (6,18), (9,18), (9,27), (18,54), (27,54) 最大元：54 最小元：1 有4个包含元素最多的全序子集: L1=54,27,9,3,1 L1=54,18,9,3,1 L1=54,18,6,3,1 L1=54,18,6,2,1,18,2,6,3,9,27,54,1,习