离散数学第五章集合及其运算习题答案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 x y(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),

2、 (3,12) , (4,9) , (4,12)4.设设A是含是含n个元素的集合，请问在个元素的集合，请问在A上可以定义出多少个二元上可以定义出多少个二元关系？关系？ 解解: 因为因为R是是A上的二元关系上的二元关系, R A A,于是于是R 2A A, 所以共所以共2n2个个二元关系二元关系.习题四 6设在整数集合上定义了如下关系：确定其满足的性质设在整数集合上定义了如下关系：确定其满足的性质自反性自反性反自反反自反性性对称性对称性反对称反对称性性传递性传递性xRy x | y 习题四 6设在整数集合上定义了如下关系：确定其满足的性质设在整数集合上定义了如下关系：确定其满足的性质自反性自反性

3、反自反反自反性性对称性对称性反对称反对称性性传递性传递性xRy x | y xRy xy(mod n) 习题四 6设在整数集合上定义了如下关系：确定其满足的性质设在整数集合上定义了如下关系：确定其满足的性质自反性自反性反自反反自反性性对称性对称性反对称反对称性性传递性传递性xRy x | y xRy xy(mod n) xRy xy0 习题四 6设在整数集合上定义了如下关系：确定其满足的性质设在整数集合上定义了如下关系：确定其满足的性质自反性自反性反自反反自反性性对称性对称性反对称反对称性性传递性传递性xRy x | y xRy xy(mod n) xRy xy0 xRy xy0 习题四 6设

4、在整数集合上定义了如下关系：确定其满足的性质设在整数集合上定义了如下关系：确定其满足的性质自反性自反性反自反反自反性性对称性对称性反对称反对称性性传递性传递性xRy x | y xRy xy(mod n) xRy xy0 xRy xy0 xRy x=y | |x-y|=1 习题四 6设在整数集合上定义了如下关系：确定其满足的性质设在整数集合上定义了如下关系：确定其满足的性质自反性自反性反自反反自反性性对称性对称性反对称反对称性性传递性传递性xRy x | y xRy xy(mod n) xRy xy0 xRy xy0 xRy x=y | |x-y|=1 xRy x2y2 习题四 7设设R是集合

5、上的一个二元关系，是集合上的一个二元关系， xRy yRz xRz ,称称R是是A上的上的一个反传递关系。试举一个实际的反传递关系的例子。一个反传递关系。试举一个实际的反传递关系的例子。解：解：例如：设例如：设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) 不是反传递不是反传递传递和反传递不是绝对互相排斥传递和反传递不是绝对互相排斥实际中，如实际中，如“父

6、子关系父子关系”， “X=Y+1”关系等。关系等。习题四 9判定满足下述每一种条件的关系是否存在，如果存在，举例判定满足下述每一种条件的关系是否存在，如果存在，举例说明。说明。（1）既自反又反自反。）既自反又反自反。答：不存在答：不存在（2）既对称又反对称。）既对称又反对称。答：存在，例如答：存在，例如IA（3）既传递又反传递。）既传递又反传递。答：存在答：存在（4）既自反、反对称、又传递。）既自反、反对称、又传递。答：存在，例如正整数集合上的整除关系。答：存在，例如正整数集合上的整除关系。习题四 8 自反性自反性 反自反性反自反性 对称性对称性 反对称性反对称性 传递性传递性R S 设设R和

7、和S都是集合都是集合A上的二元关系，它们经过关系运算后得到上的二元关系，它们经过关系运算后得到A上的一个上的一个新关系。判别当新关系。判别当R和和S 同时具有表中某种指定性质时，经过指定的运算同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：后所得新关系是否也仍保持这种性质：(a,b) R S(a,b) R (a,b) S (b,a) R (b,a) S(b,a) R S或者由或者由R S= (R S)-1得证得证(a,b) R S(a,b) R (a,b) S (b,a) R (b,a) S(b,a) R S或者由或者由(R S) (R S)-1 IA得证得证 自反

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

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

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

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

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

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

14、系，它们经过关系运算后得到上的二元关系，它们经过关系运算后得到A上的一个上的一个新关系。判别当新关系。判别当R和和S 同时具有表中某种指定性质时，经过指定的运算同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：后所得新关系是否也仍保持这种性质：设设R是集合是集合A上的一个二元关系。证明：上的一个二元关系。证明：（1）R是自反的是自反的 IA R证明：当证明：当R是自反时，任取是自反时，任取(x,x) IA,必有必有(x,x) R IA R当当IA R时，时，R= IA R，故，故R含有所有含有所有(x,x) 序偶，故自反。序偶，故自反。（2） R是反自反的是反自反的

15、R IA= 证明证明: 当当R是反自反的，任何是反自反的，任何(x, y) R, 必有必有xy, 故R IA= ;当当R IA= 时时, R中无中无(x, x)序偶，序偶，故故反自反。反自反。（3）R是对称的是对称的R = R-1证明证明: 当当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上的一个二元关系。证明：上的一个二

16、元关系。证明：（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时，如果时，如果 x y,则则(x, y) R (x, y) R-1 ，即，即(x, y) R (y, x) R R是反对称的。是反对称的。（5） R是传递的是传递的 R2 R证明证明: 当当R是传递的，取是传递的，取(x, z) R2, 即即( y)(x, y) R (y, z) R ，于是，于是(x, z) R R2 R

17、当当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 (m0。证明。证明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

18、(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，它们，它们分别对应于复平面上右半部和左半部。分别对应于复平面上右半部和左半部。习题五 4. 试确定在试确定在4个元素的集合上可以定义出的等价关系数目。个元素的集合上可以定义出的等价关系数目。解：解：A=a,b,c,d可产生

19、的分划如下：可产生的分划如下：含一个等价类含一个等价类 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,c2-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 所以共个所以共个习题五 7. 设设Mn是全体是全体n阶矩阵的集

20、合阶矩阵的集合.如果对矩阵如果对矩阵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的正因子构成的集合的正因子构成的集合,”|”表示整除表示整除.作出偏序集作出偏序集对应的

21、对应的Hasse图图.找出最大元最小元找出最大元最小元,求有多少个包含元素最多的全序子集求有多少个包含元素最多的全序子集A=1，2，3，6，9，18，27，54COVER(|)=(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,1L1=54,18,9,3,1L1=54,18,6,3,1L1=54,18,6,2,118263927541习题五 9.设A=a,b,c ,画出偏序集对应的Hasse图图.a,b,ca,ba,cb,cabc习题五 11.设设R是集合是集合A上的一个等价关系，上的一个等价关系， 现在在等价类之间定义现在在等价类之间定义一个新关系一个新关系S使得对使得对R的任何等价类的任何等价类a和和b满足满足aSb aRb，判别，判别S是一个什么关系？是一个什么关系？解：由已知解：由已知R是等价关系，是等价关系，S是是R等价类集合上的二元关