川大离散数学习题5

1、习 题 5设 A=(a,b)|a,bN. 定 义 A 上 的 一 个 二 元 关 系R=（ a,b）,(c,d)）|ad=bc,证:R是A上的等价关. 证：A a,b|a,bN，R=（a,）,(c,d）|ad=bc自反性：由Aab baa,b NR对称性 设 a,b, c, d R ，则ad bc即 cb dad R1传递性 设 1b c d,11,R，则a db c111c , 1111,c d2 R ，则c d12 d c1 2 a d b c d b d a d bc1 11 11 1 121 2,b11,c , d2 R定义复数集合的子集合C1=a+bi|i2=-1,abR,a 0，在

2、C1上定S(a+bi)S(c+di) ac0C1系，并给出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)ac0cu0 au0(a+bi)S(u+vi) 综上，SC1上的一个等价关系。a0,c0acS2其一是1=a+bi|a0，另一个是-1=a+bi|a0，它们分别对应于复平面上右半部和左半部。3.A=1,2,3,4S=1,2,4,3S00的AR.0解：A,2,34,S ,3 0设 A 1A 2R 242

3、424试确定在4个元素的集合上可以定义出的等价关系数解：每个集合的划分就可以确定一个等价关系集合有多少个划分就可以确定多少个等价关系C 4 C 3 C 2 C 1 15 种。4444R1和 R 是非空集合 A 上的两个等价关系.试确定下列各个关系2是否是A 上的等价关系:如果是,加以证明;如果不是,举例说明：(1)R R；(2)R R3r(R-R)（R R12121212解：R R12R R1不是A是A1R 是A2R oR1不是A设RA如果对每一个xA，存在yA 使xRy，那么，R 是A 上的等价关系。证明：由题可知，对于每一个x，都存在y 使xRy，则非空集合A的元素都存在关系x,，又因为R

4、 具有对称性，则对于所有的x，R 中也必然存在（y,x） 又因为R 具有传递性，则对于所有的x,R 中也必然存在（x,x）,即R综上，据等价关系定义，R 是A 上的等价关系MnAB Mnnp MAB(读为AB).证明：是Mnn等价关系. 证明:r:设E 是单位矩阵,则A,A=EAE-1AA s:ABA=PBP-1P-1AP=BB=P-1A(P-1)-1BA t:ABBCA=PBP-1B=QCQ-1A=P(QCQ-1)P-1A=(PQ)C(PQ)-1AC所以是Mn设A54,|A,|)对应的Hasse 图.解：A=1，2，3，6，9，18，27，54COVER(|)=(1,2), (1,3), (

5、2,6), (3,6), (3,9),(6,18),(9,18), (9,27), (18,54), (27,54)最大元：54 最小元：14L1=54,27,9,3,1L1=54,18,9,3,1L1=54,18,6,3,1L1=54,18,6,2,1设A=a,b,c2A, )对应的Hasse上题Hasse解： A a,b,c2A a,b,a,b,ca,b a,cb,cabc是否存在集合A 上的一个关系R,.解：集合A 、恒等关系IA都是等价关系和偏序关系。设R A 上的一个等价关系。现在在等价类之间定义一个新关系S，使得对Ra和b满足aSb aRb,判别?RS是RaSb aRb。因为对R

6、的任 2 个等价类a和b，要么a=b，要么ab=aRb说明a和b a) | aA（等价类集合上的恒等关系，所以S所以S设RAR称R 是A举一个逆序关系的例子；包是A解：（1）例如：A=A,B,CR=(A,B),(B,C),(A,C)x,y(x,y(y,xx,，与逆序关系的反自反性相矛盾；即若对于两个不同的x,y 不可能存在两个关系(x,y)和(y,x)，所以逆序关系是反对称的。x,y(x,y(y,x同样具有传递性。综上，逆序关系的自反闭包符合偏序关系的定义，故其是A 上的偏序关系。设R是集合A是A的非空子集。证明：RBB是B上的偏序关系。证：i）自反性，对b B A ,b,bR（R的自反性）显然bBBbRBB反对称性，对a,bB,RBB,RBB即RR ，由R a b传递性，对a,b,cB，设bRBB,cRBB则a,bR，R。由RR ，显然B BcRBB5.21A（略）设A=a,b,c,d22,使得是的拓