离散数学刘任任答案PPT课件

1、2.设R是定义在集合A上的二元关系。 (1). 设A= ，则R= 既是自反的又是反自反的. (2). 令A=1，2，R=，于是R既不是自反又不是反自反的； (3). 令A=1，2，R=,于是R既是对称又是反对称的；第1页/共44页 (4). 令A=1,2,3,R=, 于是R既不是对称又不是反对称的。第2页/共44页3. 设A=X1,X2 ,Xn，于是定义在A上的二元关系R中的元素来自于下列矩阵： . 第3页/共44页 (1)共有2n2 种定义在A上的不同的二元关系； 说明: |A|=n |AA|=n2 |(AA)|=2n2 第4页/共44页 (2)共有 种定义在A上的不同的自反关系；说明: A

2、上的自反关系必须满足所有形如的序偶包含在关系中，而形如的序偶有n个。即|AA-|=n2-n 在构造A上的自反关系的时候可以先将所有的放到这些关系中再考虑其他序偶的组合。即|(AA-)|=2n2-n nn 22第5页/共44页 (3)共有 种定义在A上的不同的反自反关系；说明: A上的反自反关系必须满足所有形如的序偶不能包含在关系中， 在构造A上的反自反关系的时候可以先将所有的拿出后再考虑其他序偶的组合。即(AA-)=2n2-n nn 22第6页/共44页 (4)共有 种定义在A上的不同的对称关系;说明: A上的对称关系必须满足：如果在这个关系中，则也必须在这个关系中。 在构造A上的对称关系的时

3、候可以先将所有的和（其中xy）看成是一个整体。 要考虑的序偶的个数有： n+(n2-n)/2=n(n+1)/2 (+(AA-)/2)=2(n2+n)/2 2/ )1(2/ )1(222nnnnn第7页/共44页 (5)共有 种定义在A上的不同的反对称， 其中， 。 kmmkkmnC2202) 1( nnm第8页/共44页4. (1) 自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈（即若关系R是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1，在关系图上每个结点都有自回路）。 (2) 反自反关系矩阵的主对角线上元素全为0; 而关系图中每个结点上均无圈（即若关系R是反自反的，

4、当且仅当在关系矩阵中，对角线上的所有元素都是0，在关系图上每个结点都没有自回路） 。第9页/共44页 (3) 对称关系矩阵为对称矩阵; 而关系图中任何两个结点之间的有向弧是成对出现的, 方向相反。 （即若关系R是对称的，当且仅当关系矩阵是对称的，且在关系图上任两个结点若有定向弧线，则定向弧线必定是成对出现的）(4)反对称关系矩阵 的元素满足： 当ij 时 ， 。 而关系图中任何两个结点之间的有向弧是单向的。（即若关系R是反对称的，当且仅当关系矩阵中以对角线对称的元素不能同时为1，在关系图上任两个结点的定向弧线不可能成对出现）nnijRrM)(0jiijrr第10页/共44页5.RS=,SR=;

5、R 2=,;S 2=,.第11页/共44页6.设R=,T=,S=,P=,)(,TSRTS于是有3 , 3,3 , 3,2 , 3TRSR3 , 3)()(TRSR因此)()()(TRSRTSR从而第12页/共44页,1 , 1,)(PSPTS又1 , 1,1 , 3PT1 , 1)()(PTPS因此)()()(PTPSPTS从而第13页/共44页7. (1) 正确。因为对任意xA，有xRx，xSx,所以x(RS)x。故RS是自反的。 (2) 错误。例如，设x,yA，xy,且xRy，ySx，于是x(R S)x。故R S不是反自反的。(3)错误。例如，设对称关系R=,S=,。则RS=故RS不是对称

6、的。第14页/共44页(4) 错误。例如，设反对称关系R=,S=,xy。于是，RS=,。故RS不是反对称的。 (5) 错误。例如，设传递关系R=,S=,wv。于是，RS=,，显然， RS不是一个传递关系。第15页/共44页思考：假设R，S是定义在有限集合A上的满足下表列标题性质的二元关系，试判断下表行标题所列二元关系是否具有相应性质。自反性反自反 对称性 反对称 传递性R-1RSRSR-SR.S第16页/共44页思考：假设R，S是定义在有限集合A上的满足下表列标题性质的二元关系，试判断下表行标题所列二元关系是否具有相应性质。第17页/共44页8.0212121)()()() 1 (RRRRRR

7、r)()(020121RRRR)()(022011RRRR)()(21RrRr第18页/共44页1212121)()()()2(RRRRRRs)()(121121RRRR)()(122111RRRR)()(21RsRs第19页/共44页(3)由定义，,)(,)(22222111RRRtRRRt,)()()(2212121RRRRRRt22221121)()(RRRRRtRt于是)()(222121RRRRnnnRRRRn)(12121 有下证对任意nnRRyx21,任取nRyx1, 不妨设,211212111RRRzzRRRzx于是存在z1,z2,zn-1,满足：R1 R1R2第20页/共44

8、页nRRyx)(,21从而举例说明“ ”成立。设于是3 , 2,2 , 1,3 , 2 , 121RRA3 , 2,3 , 1,2 , 1)(21RRt3 , 1,2 , 1)()(21RtRt第21页/共44页9.设R1和R2是集合A上的二元关系。注意到 ，于是0210201)(RRRR0212121)()()() 1 (RRRRRRr0121)(RRR)()(012011RRRR)()(022011RRRR)()(21RrRr第22页/共44页1212121)()()()2(RRRRRRs12221111)(,)(RRRsRRRs任取)()()()(12211121RRRRRsRs1212

9、121)()()(,RRRRRRsyx),(,)(21RRyxi若从而,1222RRRyx)()(,122111RRRRyx且则,1111RRRyx)()(21RsRs第23页/共44页,)(,)(121RRyxii 若即则),(,21RRxy,21从而且RxyRxy,11111且RRRyx,12212于是RRRyx)()(,122111RRRRyx).()()(2121RsRsRRs故)()(21RsRs:成立举例说明 第24页/共44页,1 , 2,2 , 1,2 , 121于是设RRA1212121)()()(RRRRRRs而,1,1 , 2,2 , 1)(1111RRRs1 , 2,2

10、 , 1)(1222RRRs,1 , 2,2 , 1)()(,21RsRs因此)()()(2121RsRsRRs故第25页/共44页(3)由定义，,)(,)(22222111RRRtRRRtt(R1R2)=(R1R2)(R1R2)2于是 t(R1)t(R2)=(R1R2)(R1R22) (R12R22)(R12R2) ) 下证对任意的n1,有(R1R2)n (R1nR2n)证明:任取(R1R2)n, 则存在n-1个元素z1,z2zn-1满足R1R2, R1R2,R1R2。从而有R1 , R1, R1并且R2 , R2, R2。第26页/共44页所以有R1n 并且R2n，即 R1n R2n所以(

11、R1R2)n (R1nR2n)例如：设A=1，2，3，R1=, R2=则t(R1)=, t(R2)=, t(R1)t(R2)=, R1R2= , t(R1R2)= 第27页/共44页 10.说法不正确. 这是因为自反性要求对任意的x和x都有关系R, x和y有没有关系R,我们不考虑；但是,我们题目中得出的结论x和x具有关系R,是以对称性为前提条件的,所以我们知道该论述不正确。第28页/共44页11.设R是等价关系。若,R，则由R的对称性知, R。再由R的传递性有R。反之, 假设只要, R，就有R。 (1)对称性。 设R，由自反性有R。于是R。 (2)传递性。 设, R。由对称性有R, 再由假设有

12、R。第29页/共44页12.2121/,RARARR则显然设21/,RARA设反之121,RyxRR则不妨设若2,Ryx但2211 ,RRRRyxyx于是21RR 故而由A/R1=A/R2 ,有对任意xA,因为xR1 A/R2并且x xR1 xR2，所以xR1=xR2。产生矛盾。第30页/共44页13.于是设),5(mod|,yxxyR4 ,3 ,2 ,1 ,0/.19,14,9 ,4, 1,6,11.4.18,13, 8 , 3 ,2,7,12.3.17,12,7 ,2, 3, 8,13.2.16,11,6 , 1 ,4,9,14.1 .15,10, 5 ,0 , 5,10,15.0RRRR

13、RRRRRRBA第31页/共44页14.|jijiBABAS证明jiBAS,) 1 (定义知由)()()()(,1 ,1,)2(mjmimljimliiBBAABABAsmjrjiSBASBA和任取第32页/共44页SBABABBAAjiBAsjrijisjrjijimjr111,11)()().().()3(故S是X的一个划分第33页/共44页15.设 A=1,2, 3,4 , 则A上的等价关系数目即A上的划分的数目共有15个 (1) 最大划分 1,2,3,4 (2) 最小划分 1,2,3,4 (3) 将A分成两个集合S=A1，A2，有两种可能： 2,31,4, , 2,41,3, , 3,

14、41,2, ,31/2|,A|A| (i) 2421即种共有C第34页/共44页1,2,34,1,2,4,3, , 1,3,42, 2,3,41, ,4 . 3|A|1,|A| (ii)3421即种共C即种分法故共有元素个则恰有一个集合为个集合分成将,6C,2,3A(4)24 1,2,3,4, 1,3,2,4, 1,4,2,3, 2,3,1,4, 2,4,1,3, 3,4,1,2 .设Ek表示k元集合A上的全部等价关系数目, 则第35页/共44页101101nkknnnCkEEE第36页/共44页 因为En是将n个元素的集合进行划分的方法数，对任何一个划分来说，b总是在划分的某一个块中，也就是

15、某一个子集中。不妨设这个子集有k个元素(k=1,n),则在此子集中的另外k-1个元素将从n-1个元素中选取。然后对剩下的n-k个元素进行划分。故有1011011211101nkkknnnnnnnnnECECECECE第37页/共44页16.A1,1535A2,12623154 2793A3,第38页/共44页17.(1) 最(极)大元x1, 无最小元;(2) 上界 下界 上确界 下确界x2, x3, x4 x1 x4 x1 x4x3, x4, x5 x1,x3 无 x3 无x1, x2, x3 x1 x4 x1 x4第39页/共44页18.(2)题16中的A1,子集3 ,5无最大元;(3)题16中的A2,子集2,3,6有下确界但无最小元;(4)题16中的A2,子集1 有上界2,3,6,12,但是无上确界。0|,) 1 (mZmZZZZ其中无最小元但为整数集为全序集第40页/共44页19. 设为全序集