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

习题四,1.设A=1,2,3,4,B=0,1,4,9,12.分别把下面定义的从集合A到集合B的二元关系R用序偶的集合表示出来。(1)xRyx|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)xRyxy(mod3)(1,1),(1,4),(3,0),(3,9),(3,12),(4,1),(4,4)(3)xRyy/x(y-x)/2(3,9),(3,12),(4,9),(4,12)4.设A是含n个元素的集合，请问在A上可以定义出多少个二元关系？解:因为R是A上的二元关系,RAA,于是R2AA,所以共2n2个二元关系.,习题四6,设在整数集合上定义了如下关系：确定其满足的性质,习题四6,设在整数集合上定义了如下关系：确定其满足的性质,习题四6,设在整数集合上定义了如下关系：确定其满足的性质,习题四6,设在整数集合上定义了如下关系：确定其满足的性质,习题四6,设在整数集合上定义了如下关系：确定其满足的性质,习题四6,设在整数集合上定义了如下关系：确定其满足的性质,习题四7,设R是集合上的一个二元关系，xRyyRzxRz,称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)不是反传递传递和反传递不是绝对互相排斥实际中，如“父子关系”，“X=Y+1”关系等。,习题四9,判定满足下述每一种条件的关系是否存在，如果存在，举例说明。（1）既自反又反自反。答：不存在（2）既对称又反对称。答：存在，例如IA（3）既传递又反传递。答：存在（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)-1IA得证,自反性反自反性对称性反对称性传递性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同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性反自反性对称性反对称性传递性RSRS,例如A=0,1R=(0,1),S=(1,0)RS=(0,1),(1,0),例如A=0,1R=(0,1),S=(1,0)RS=(0,1),(1,0),习题四8,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性反自反性对称性反对称性传递性RSRSR-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同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性反自反性对称性反对称性传递性RSRSR-SRS,例如A=0,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同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性反自反性对称性反对称性传递性RSRSR-SRS,例如A=0,1R=(0,1),(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同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,自反性反自反性对称性反对称性传递性RSRSR-SRSR,习题四8,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,例如A=a,b,c若R=(a,a),(b,c),自反性反自反性对称性反对称性传递性RSRSR-SRSRR-1,习题四8,设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。判别当R和S同时具有表中某种指定性质时，经过指定的运算后所得新关系是否也仍保持这种性质：,设R是集合A上的一个二元关系。证明：（1）R是自反的IAR证明：当R是自反时，任取(x,x)IA,必有(x,x)RIAR当IAR时，R=IAR，故R含有所有(x,x)序偶，故自反。（2）R是反自反的RIA=证明:当R是反自反的，任何(x,y)R,必有xy,故RIA=;当RIA=时,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=RR-1，则对任何(x,y)R,必有(y,x)R-1R，故R对称,习题四10,设R是集合A上的一个二元关系。证明：（4）R是反对称的RR-1IA证明：当R是反对称时，任取(x,y)RR-1，则(x,y)R(x,y)R-1(x,y)R(y,x)Rx=y，所以RR-1IA当RR-1IA时，如果xy,则(x,y)R(x,y)R-1，即(x,y)R(y,x)RR是反对称的。（5）R是传递的R2R证明:当R是传递的，取(x,z)R2,即(y)(x,y)R(y,z)R，于是(x,z)RR2R当R2R时,任取(x,y),(y,z)R,则(x,z)R2R，故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,bR,a0,c0)r:a0,a20(a+bi)S(a+bi)s:(a+bi)S(c+di)ac0ca0(c+di)S(a+bi)t:(a+bi)S(c+di)(c+di)S(u+vi)ac0cu0au0(a+bi)S(u+vi)综上，S是C1上的一个等价关系。由于ac0，必须a0,c0且a和c同号，故S只有2个等价类，其一是1=a+bi|a0，另一个是-1=a+bi|a0，它们分别对应于复平面上右半部和左半部。,习题五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,dS5=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阶矩阵的集合.如果对矩阵A,BM,存在可逆矩阵PM使得A=PBP-1,则记为AB.证明:是Mn上的等价关系.证明:r:设E是单位矩阵,则A,A=EAE-1AAs:ABA=PBP-1P-1AP=BB=P-1A(P-1)-1BAt:ABBCA=PBP-1B=QCQ-1A=P(QCQ-1)P-1A=(PQ)C(PQ)-1AC所以是Mn上的等价关系.,习题五8.,设A是由54的正因子构成的集合,”|”表示整除.作出偏序集对应的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,1,18,2,6,3,9,27,54,1,习题五9.,设A=a,b,c,画出偏序集对应的Hasse图.,a,b,c,a,b,a,c,b,c,a,b,c,习题五11.,设R是集合A上的一个等价关系，现在在等价类之间定义一个新关系S使得对R的任何等价类a和b满足aSbaRb，判别S是一个什么关系？解：由已知R是等价关系，S是R等价类集合上的二元关系，且aSbaRb。因为对R的任2个等价类a和b，要么a=b，要么ab=，又aRb说明a和b在同一等价类中，因此，S=(a,a)|aA（等价类集合上的恒等关系），所以S满足自反性、对称性、反对称性、传递性，所以S既是等价关系，又是偏序关系。,判断下列关系的性质:,自反对称传递,a,b,c,判断下列关系的性质:,自反对称传递,自反反对称传递,a,b,c,a,b,c,判断下列关系的性质:,自反对称传递,自反反对称传递,自反对称传递,a,b,c,a,b,c,a,b,