离散数学(刘任任版)第2章答案

《离散数学(刘任任版)第2章答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题二1.(1).R={<1,1>,<1,3>,<3,1>,<3,3>}(2).R={<1,0>,<2,1>,<4,2>,<8,3>}2.设R是定义在集合A上的二元关系。(1).设A=，则R=既是自反的又是反自反的.(2).令A={1，2}，R={<1，1>}，于是R既不是自反又不是反自反的；(3).令A={1，2}，R={<1,1>,<2,2>},于是R既是对称又是反对称的；(4).令A={1,2,3},R={<1,2>,<2,1>,<1,3>},于是R既不是对称又不是反对称的。3.设A={X1,X2,…,Xn}，于是定义在A上的二元关系R中的元素来自于下列矩阵：<

2、x1,x2>……….…(1)共有2n2种定义在A上的不同的二元关系；说明:∵

3、A

4、=n∴

5、A×A

6、=n2∴

7、β(A×A)

8、=2n2(2)共有种定义在A上的不同的自反关系；说明:∵A上的自反关系必须满足所有形如的序偶包含在关系中，而形如的序偶有n个。即

9、A×A-{}

10、=n2-n∴在构造A上的自反关系的时候可以先将所有的放到这些关系中再考虑其他序偶的组合。即

11、β(A×A-{})

12、=2n2-n(3)共有种定义在A上的不同的反自反关系；说明:∵A上

13、的反自反关系必须满足所有形如的序偶不能包含在关系中，∴在构造A上的反自反关系的时候可以先将所有的拿出后再考虑其他序偶的组合。即β(A×A-{})=2n2-n(4)共有种定义在A上的不同的对称关系;说明:∵A上的对称关系必须满足：如果在这个关系中，则也必须在这个关系中。∴在构造A上的对称关系的时候可以先将所有的和（其中x≠y）看成是一个整体。∴要考虑的序偶的个数有：n+(n2-n)/2=n(n+1)/2∴β({}+(A×A-{})/2)=2(n2+n)/2(5)共有种定义在A上的不同的反对称，其中，

14、。4.(1)自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈（即若关系R是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1，在关系图上每个结点都有自回路）。(2)反自反关系矩阵的主对角线上元素全为0;而关系图中每个结点上均无圈（即若关系R是反自反的，当且仅当在关系矩阵中，对角线上的所有元素都是0，在关系图上每个结点都没有自回路）。(3)对称关系矩阵为对称矩阵;而关系图中任何两个结点之间的有向弧是成对出现的,方向相反。（即若关系R是对称的，当且仅当关系矩阵是对称的，且在关系图上任两个结点若有定向弧线，则定向弧线必定是成对出现的）反对称关系矩阵的元素满足：当i≠j时，。

15、而关系图中任何两个结点之间的有向弧是单向的。（即若关系R是反对称的，当且仅当关系矩阵中以对角线对称的元素不能同时为1，在关系图上任两个结点的定向弧线不可能成对出现）5.R·S={<1,4>,<1,3>},S·R={<3,4>};R2={<1,1>,<1,2>,<1,4>};S2={<2,2>,<3,4>,<3,3>}.6.设R={<3,1>,<3,2>},T={<1,3>,<3,2>},S={<1,2>,<2,3>},P={<2,1>,<3,1>},7.(1)正确。因为对任意x∈A，有xRx，xSx,所以x(R·S)x。故R·S是自反的。(2)错误。例如，设x,y∈A，x≠y,且xRy

16、，ySx，于是x(R·S)x。故R·S不是反自反的。(3)错误。例如，设对称关系R={,},S={,}。则R·S={}故R·S不是对称的。(4)错误。例如，设反对称关系R={,},S={,},x≠y。于是，R·S={,}。故R·S不是反对称的。(5)错误。例如，设传递关系R={,},S={,},w≠v。于是，R·S={,}，显然，R·S不是一个传递关系。思考：假设R，S是定义在有限集合A上的满足下表列标题性质的二元关系

17、，试判断下表行标题所列二元关系是否具有相应性质。自反性反自反对称性反对称传递性R-1√√√√√R∩S√√√√√R∪S√√√××R-S×√√√×R.S√××××思考：假设R，S是定义在有限集合A上的满足下表列标题性质的二元关系，试判断下表行标题所列二元关系是否具有相应性质。8.(3)由定义，于是存在z1,z2,zn-1,满足：∈R1R1∪R2举例说明“”成立。设9.设R1和R2是集合A上的二元关系。注意到(3)由定义，t(R1∩