离散数学刘任任版习题2.ppt

习题二 1. (1). R={1,1,1,3,3,1,3,3} 2. 设R是定义在集合A上的二元关系。 (1). 相等关系. (2). 令A={1，2}，R={1，1}，于是R既不是自反又不是反自反的； (3). 令A={1，2}，R={1,1,2,2},于是R既是对称又是反对称的； 3. 设|A|=n，于是 (1)共有 种定义在A上的不同的二元关系； (2)共有 种定义在A上的不同的自反关系； (3)共有 种定义在A上的不同的反自反关系； (4)共有 种定义在A上的不同的对称关系; (5)共有 种定义在A上的不同的反对称， 其中， 。 4. (1) 自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈。 (2) 反自反关系矩阵的主对角线上元素全为0; 而关系图中每个结点上均无圈。 (3) 对称关系矩阵为对称矩阵; 而关系图中任何两个结点之间的有向弧是成对出现的, 方向相反。 5. R·S={1,4,1,3},S·R={3,4}; R 2={1,1,1,2,1,4}; S 2={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，ySx，于是x(R ·S)x。故R ·S不是反自反的。 (4) 错误。例如，设反对称关系R={x,z,y,w},S={z,y,w,x},x≠y。于是，x,y,y,x∈R·S。故R·S不是反对称的。 (5) 错误。例如，设传递关系R={x,w,y,v},S={w,y,v,z},w≠v。于是，x(R·S)y，y(R·S)z，但因为w ≠v，所以，x,z∈R·S。 8. (3)由定义， 9. 设R1和R2是集合A上的二元关系。注意到 （3）证明：因为 10.说法不正确. 这是因为自反性要求对任意的x和x都有关系R, x和y有没有关系R,我们不考虑；但是,我们题目中得出的结论x和x具有关系R,是以对称性为前提条件的,所以我们知道该论述不正确。 11. 设R是等价关系。若x,y,x,z∈R，则由R的对称性知, y,x ∈R。再由R的传递性有y, z∈R。 反之, 假设只要x, y, x, z ∈R，就有y, z∈R。 (1)对称性。 设 x, y ∈R，由自反性有x, x∈R。于是y, x∈R。 (2)传递性。 设x, y, y, z∈R。 由对称性有y, x∈R, 再由假设有x, z∈R。 12. 13. 14. 15. 设 A={1,2, 3,4} , 则A上的等价关系数目即A上的划分的数目共有15个 (1) 最大划分 { {1},{2},{3},{4} } (2) 最小划分 { {1,2,3,4} } (3) 将A分成两个集合S={A1，A2}，有两种可能： {{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上的全部等价关系数目, 则 另外一种做法: 解:f(n,1)=f(n,n)=1,设n1,且1kn,设b是A的某个元素,若{b}组成一个块,则有 f(n-1,k-1)种方法能将A\{b}分成k-1块,另一方面, A\{b}分成块的每个划分允许b被接纳到一块中,有k种方法,因此我们有 f(n,k)=f(n-1,k-1)+kf(n-1,k). 16. 17. (1) 最(极)大元x1, 无最小元; (2) 上界 下界 上确界 下确界 {x2, x3, x4} x1 x4 x1 x4 {x3, x4, x5} x1,x3 无 x3 无 {x1, x2, x3} x1 x4 x1 x4 18. (2)题16中的A1,=,子集{3 ,5}无最大元; (3)题16中的A2,=,子集{2,3,6}有下确