离散数学刘任任版答案省公共课一等奖全国赛课获奖课件.pptx

习题二第1页1.(1).R=,(2).R=,第2页2.设R是定义在集合A上二元关系。(1).设A=，则R=既是自反又是反自反.(2).令A=1，2，R=，于是R既不是自反又不是反自反；(3).令A=1，2，R=,于是R既是对称又是反对称；第3页(4).令A=1,2,3,R=,于是R既不是对称又不是反对称。第4页3.设A=X1,X2,Xn，于是定义在A上二元关系R中元素来自于以下矩阵：.第5页(1)共有2n2种定义在A上不一样二元关系；说明:|A|=n|AA|=n2|(AA)|=2n2第6页(2)共有种定义在A上不一样自反关系；说明:A上自反关系必须满足全部形如序偶包含在关系中，而形如序偶有n个。即|AA-|=n2-n在结构A上自反关系时候能够先将全部放到这些关系中再考虑其它序偶组合。即|(AA-)|=2n2-n第7页(3)共有种定义在A上不一样反自反关系；说明:A上反自反关系必须满足全部形如序偶不能包含在关系中，在结构A上反自反关系时候能够先将全部拿出后再考虑其它序偶组合。即(AA-)=2n2-n第8页(4)共有种定义在A上不一样对称关系;说明:A上对称关系必须满足：假如在这个关系中，则也必须在这个关系中。在结构A上对称关系时候能够先将全部和（其中xy）看成是一个整体。要考虑序偶个数有：n+(n2-n)/2=n(n+1)/2(+(AA-)/2)=2(n2+n)/2第9页(5)共有种定义在A上不一样反对称，其中，。第10页4.(1)自反关系矩阵主对角线上元素全为1；而关系图中每个结点上都有圈（即若关系R是自反，当且仅当在关系矩阵中，对角线上全部元素都是1，在关系图上每个结点都有自回路）。(2)反自反关系矩阵主对角线上元素全为0;而关系图中每个结点上均无圈（即若关系R是反自反，当且仅当在关系矩阵中，对角线上全部元素都是0，在关系图上每个结点都没有自回路）。第11页(3)对称关系矩阵为对称矩阵;而关系图中任何两个结点之间有向弧是成对出现,方向相反。（即若关系R是对称，当且仅当关系矩阵是对称，且在关系图上任两个结点若有定向弧线，则定向弧线必定是成对出现）(4)反对称关系矩阵元素满足：当ij时，。而关系图中任何两个结点之间有向弧是单向。（即若关系R是反对称，当且仅当关系矩阵中以对角线对称元素不能同时为1，在关系图上任两个结点定向弧线不可能成对出现）第12页5.RS=,SR=;R2=,;S2=,.第13页6.设R=,T=,S=,P=,第14页第15页7.(1)正确。因为对任意xA，有xRx，xSx,所以x(RS)x。故RS是自反。(2)错误。比如，设x,yA，xy,且xRy，ySx，于是x(RS)x。故RS不是反自反。(3)错误。比如，设对称关系R=,S=,。则RS=故RS不是对称。第16页(4)错误。比如，设反对称关系R=,S=,xy。于是，RS=,。故RS不是反对称。(5)错误。比如，设传递关系R=,S=,wv。于是，RS=,，显然，RS不是一个传递关系。第17页思索：假设R，S是定义在有限集合A上满足下表列标题性质二元关系，试判断下表行标题所列二元关系是否含有对应性质。自反性反自反 对称性 反对称 传递性R-1RSRSR-SR.S第18页思索：假设R，S是定义在有限集合A上满足下表列标题性质二元关系，试判断下表行标题所列二元关系是否含有对应性质。第19页8.第20页第21页(3)由定义，于是存在z1,z2,zn-1,满足：R1 R1R2第22页举例说明“”成立。设第23页9.设R1和R2是集合A上二元关系。注意到第24页第25页第26页第27页(3)由定义，t(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。第28页所以有R1n而且R2n，即R1nR2n所以(R1R2)n(R1nR2n)比如：设A=1，2，3，R1=,R2=则t(R1)=,t(R2)=,t(R1)t(R2)=,R1R2=,t(R1R2)=第29页w10.说法不正确.w这是因为自反性要求对任意x和x都有关系R,x和y有没有关系R,我们不考虑；不过,我们题目中得出结论x和x含有关系R,是以对称性为前提条件,所以我们知道该论述不正确。第30页11.设R是等价关系。若,R，则由R对称性知,R。再由R传递性有R。反之,假设只要,R，就有R。(1)对称性。设R，由自反性有R。于是R。(2)传递性。设,R。由对称性有R,再由假设有R。第31页12.而由A/R1=A/R2,有对任意xA,因为xR1A/R2而且xxR1xR2，所以xR1=xR2。产生矛盾。第32页13.第33页14.第34页故S是X一个划分第35页15.设A=1,2,3,4,则A上等价关系数目即A上划分数目共有15个(1)最大划分1,2,3,4(2)最小划分1,2,3,4(3)将A分成两个集合S=A1，A2，有两种可能：第36页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上全部等价关系数目,则第37页第38页w因为En是将n个元素集合进行划分方法数，对任何一个划分来说，b总是在划分某一个块中，也就是某一个子集中。不妨设这个子集有k个元素(k=1,n),则在此子集中另外k-1个元素将从n-1个元素中选取。然后对剩下n-k个元素进行划分。故有第39页16.A1,1535A2,126231542793A3,第40页17.(1)最(极)大元x1,无最小元;(2)上界下界上确界下确界x2,x3,x4x1x4x1x4x3,x4,x5x1,x3无x3无x1,x2,x3x1x4x1x4第41页18.(2)题16中A1,子集3,5无最大元;(3)题16中A2,子集2,3,6有下确界但无最小元;(4)题16中A2,子集1有上界2,3,6,12,不过无上确界。第42页19.设为全序集,且|A|=n。所以,B中必有最小元a.故为良序集第43页20.设B是A非空有限集。若B中不存在极大(小)元,则对任何xB,则存在yB,使得xy(yx),如此下去,得出B为无限集.矛盾.故结论成立。第44页21.设B是A上一个非空有限集,由上题知,B中最少有一个极大(小)元。又因A,为全序集,故B极大(小)元均唯一,且就是最大(小)元。第45页