20春东师《离散数学》离线考核
离线考核离散数学满分100分一、计算题(共25分)1. 设集合,是上的二元关系,试求:(1) ; (8分) 解:(1) (2) 的关系图与关系矩阵; (8分) 解: 工aaaaaaaaaaa关系图为:(3) 、。(9分)解 二、证明题(每小题15分,共75分。)1.证明等价式:。证明:2. 证明:树是一个偶图。证明:设是一棵树,对任意的,令(1) 因为是连通的,所以对任意的,必有或,因此,(2) 因为是树,与之间的基本通路有且只有一条,所以,(3) 因为是树,中无回路,所以或中的任意的两个顶点不可能是相邻的。综上,是一个偶图。3. 设是群,对任意的,令,证明:是的子群。证明:对任意的,有所以经整理,得所以因此,由子群判定定理,是的子群。4. 设为实数集,对任意的,定义:证明:是双射。证明:(1) 对任意的,存在,使得所以是满射。(2) 对任意的,若,即所以,有解得:即因此是单射。综上,是双射。5. 设是含幺环,且*满足等幂律,在上定义运算+,如下:, , 。证明:是一个布尔代数,其中0和1分别是关于运算和*的幺元。证明:(1) 由题设条件可知,运算+和在上是封闭的。(2) 对任意的,由书上习题结论,有从而有即,运算+和在上是可交换的。(3) 对任意的,有即所以运算对+是可分配的。另外即所以运算+对是可分配的。(4) 对任意的,有(5) 对任意的,有综上,由亨廷顿公理,是布尔代数。