离散数学2017秋综合练习题.doc

离散数学综合练习题 一、判断下列命题是否正确如果正确，在题后括号内填“/”；否则，填“” （1）空集是任何集合的真子集 （ ）（2）是空集 （ ）（3） （ ） （4）如果，则或 （ ） （5）设集合，则 （ ） （6）设集合，则 是到的关系 （ ）（7）关系的复合运算满足交换律 （ ）（8）设为集合 上的等价关系, 则也是集合 上的等价关系 ( ) （9）设是集合上的等价关系, 则当时， ( ) （10）设为集合 上的等价关系, 则 ( )（11）集合A上的任一运算对A是封闭的 （ ） （12）设A是集合，则是可结合的 （ ） （13）设是群如果对于任意，有 则是阿贝尔群 （ ） （14）设a是群的元素，记 则是的子群 （ ） （15）是格 （ ） （16）设a，b是格的任意两个元素，则 （ ） （17）设是布尔代数，则是格 （ ） （18）设集合，则是格 （ ）（19）设是布尔代数，则对任意，有 （ ） （20）设是布尔代数，则对任意，都有，使得 （ ）（21）n阶完全图的任意两个不同结点的距离都为1. （ ）（22）在有向图中，结点到结点的有向短程即为到的有向短程 （ ） （23）强连通有向图一定是单向连通的 （ ） （24）不论无向图或有向图，初级回路一定是简单回路 （ ） （25）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的 （ ） （26）设A是某个无向图的邻接矩阵，则(是的转置矩阵) （ ）（27）设有向图D的可达矩阵为 则是单向连通的 （ ） （28）有生成树的无向图是连通的 （ ） （29）由r棵树组成的森林的结点数n与边数m有下列关系：m=n-r. （ ）（30）如果有向图D仅有一个结点的入度为0，其余结点的入度都为1，则D是有向树 （ ）（31）“如果872，则三角形有四条边”是命题 （ ） （32）设都是命题公式，则也是命题公式 （ ） （33）命题公式的真值分别为0，1，则的真值为0（以上是在对所包含的命题变元的某个赋值下） （ ）（34）逻辑结论是正确结论 （ ）（35）设都是谓词公式，则也是谓词公式 （ ）（36）设都是谓词公式，则是永真式 （ ） （37）设都是命题公式，则 也是命题公式 （ ） （38）命题公式的真值分别为0，1，则的真值为0（以上是在对所包含的命题变元的某个赋值下） （ ） （39）设是个体域中某个元素，则 其中都是谓词 （ ） （40） （ ）二、填空题（1）设有个元素，则集合的幂集中有 个元素。（2）设，则= .（3）设集合中元素的个数分别为，且，则集合中元素的个数 . （4）设集合，则中元素的个数为 .(5)设为集合 上的二元关系, 则 . (6)集合上的二元关系为传递的充分必要条件是 (7)设：称为母亲，：称为父亲，则： , (8)设为自然数的集合，“”为自然数的小于等于关系，的子集，则的下确界为 ，下确界为 , (9)设10人集合赵茵，钱小滨，孙丽春，赵萍，钱浩，李靖华，李秀娟，钱钰，李惠芝，李莉上的同姓关系为，则等价类赵= ，钱= ， (10)设 , 是 上的包含于关系，,则有= . (11)设为非空有限集，代数系统中，对运算的单位元为 ，零元为 . (12)循环群的生成元为 . (13)循环群的所有子群为 . (14)代数系统中（其中为整数集合，+为普通加法），对任意的，其 . (15)在整数集合上定义运算为，则的单位元为 . (16)设,在代数系统中，的单位元为 ，可逆元为 . (17)设是群，则对于任意的，方程 和 有唯一解。 (18)设是群，对任意，如果，则 . (19)设是群，为单位元，若元素满足，则 . (20)在整数集合上定义运算为，则的单位元为 . (21)设为树，中有4度，3度，2度分支点各1个，问中有 片树叶。 (22)为了从（n，m）连通无向图得到一棵生成树，必须删除G的 条边 (23)设树T中有7片树叶，3个3度结点，其余都是4度结点，问T中有 个4度结点。 (24)无环有向图的关联矩阵的所有元素之和为 (25)n阶完全图的任意两个不同结点的距离都为 (26)图为阶无向完全图，则共有 条边。 (27)设为图，则图中结点度数的总和为 。 (28)设图有6结点，若各结点的度数分别为：1，4，4，3，5，5，则共有 条边。 (29)无向图是由棵树组成的森林，至少要添加 条边才能使成为一棵树。 (30)在任何图中，奇数结点必为 个。 (31)设 天气很冷，老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 . (32)设天下雨， 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 . (33)设经一事, 长一智，则命题“不经一事, 不长一智”符号化为 . (34)设的真值为0，的真值为1，则命题公式的真值为 . (35)设的真值为0，的真值为1，则命题公式的真值为 . (36)由个命题变项可以组成 个不等值的命题公式。 (37)设个体域，公式在上消去量词后应为 . (38)设是自然数，是奇数，是偶数，则命题“任何自然数不是奇数就是偶数” 符号化为 . (39)设是素数，是偶数，则命题“2既是偶数又是素数”符号化为 . (40)设是金子，是发光的，则命题“金子是发光的, 但发光的不一定是金子”符号化为 .三、选择题（每题后面有四个选项，四个选项中只有一个是正确的，请将正确的所对应的字母填在括号内）（1）设为实数集合，下列集合中哪一个不是空集 （ ）A. B C. D. （2）设为集合，若，则一定有 （ ）A. B C. D. （3）下列各式中不正确的是 （ ）A. B C. D. （4）设，则下列各式中错误的是 （ ）A. B C. D. （5）设，则为 （ ）A. B C. D. （6）设，则的恒等关系为 （ ）A. B C. D. （7）集合上的二元关系，则的性质为 （ ）A. 自反的； B对称的； C. 反对称的； D. 反自反的.（8）设上的二元关系如下，则具有传递性的为 （ ）A. B C. D. （9）设为集合上的等价关系，对任意，其等价类为 （ ）A. 空集； B非空集； C. 是否为空集不能确定； D. .（10）映射的复合运算满足 （ ）A. 交换律 B结合律 C. 幂等律 D. 分配律（11）在整数集上，下列哪种运算是可结合的 （ ）A. B C. D. （12）设集合，下面定义的哪种运算关于集合不是封闭的 （ ）A. B C. ，即的最大公约数D. ，即的最小公倍数（13）下列哪个集关于减法运算是封闭的 （ ）A. （自然数集）； B；C. ； D. .（14）设是有理数集，在定义运算为，则的单位元为 （ ）A. ； B； C. 1； D. 0（15）下列代数系统中，哪一个不构成群 （ ）A. 是模11乘法；B. 是模3加法；C. 普通加法；D. 普通乘法.（16）循环群 的生成元为1和2，它们的周期为 （ ）A. 5 B6 C. 3 D. 9（17）循环群 的所有子群为 （ ）A. B C. 和 D. （18）循环群的所有生成元为 （ ）A. 1，0 B-1，2 C. 1，2 D. 1，-1（19）有限布尔代数的元素个数必定等于 （ ）A. ； B； C. ； D. .（20）在下面偏序集的哈斯图中，哪一个是格 （ ） A B C D（21）仅由孤立点组成的图称为 （ ）A. 零图； B平凡图； C. 完全图； D. 多重图.（22）仅由一个孤立点组成的图称为 （ ）A. 零图； B平凡图； C.多重图； D. 子图.（23）在任何图中必有偶数个 （ ）A. 度数为偶数的结点； B度数为奇数的结点； C. 入度为奇数的结点； D. 出度为奇数的结点.（24）设为有个结点的无向完全图，则的边数为 （ ）A. B C. D. （25）图和的结点和边分别存在一一对应关系是（同构）的 （ ）A. 充分条件； B必要条件；C. 充分必要条件； D. 既不充分也不必要条件.（26）给定下列序列，哪一个可构成无向简单图的结点度数序列 （ ）A. BC. D. （27）在有个结点的连通图中，其边数 （ ）A. 最多条； B至少条；C. 最多条； D. 至少条.（28）是无向图的关联矩阵，是中的孤立点，则（ ）A. 对应的一行元素全为0； B对应的一行元素全为1；C. 对应的一列元素全为0； D. 对应的一列元素全为1.（29）任何无向图中结点间的连通关系是 （ ）A. 偏序关系； B等价关系；C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系.（30）有向图，其中，则有向图是 （ ）A. 强连通图； B单向连通图；C. 弱连通图； D. 不连通图.（31）下面哪个联结词不可交换 （ ）A. ； B； C.； D. .（32）命题公式是 （ ）A. 矛盾式； B非永真式的可满足式；C. 重言式； D. 等价式.（33）下列哪一组命题公式是等值的 （ ）A. ，； B，；C. ，； D. ，（34）下面哪一个命题是假命题 （ ）A. 如果2是偶数，那么一个公式的析取范式唯一；B如果2是偶数，那么一个公式的析取范式不唯一；C. 如果2是奇数，那么一个公式的析取范式唯一；D. 如果2是奇数，那么一个公式的析取范式不唯一.（35）设论域为整数集，下列公式中哪个值为真 （ ）A. ； B. ；C. ； D. .（36）设谓词是奇数，是偶数，谓词公式在哪个论域中是可满足的 （ ）A. 自然数； B整数； C. 实数； D. 以上均不成立.（37）命题“没有不犯错误的人”符号化为(设是人,犯错误) （ ）A. ； B.；C. ； D.（38）设个体域，公式在上消去量词后应为 （ ）A. ； B. ；C. ； D. .（39）在谓词演算中，下列各式中，哪一个是正确的 （ ）A.； B.；C.； D.（40）“学习有如逆水行舟，不进则退”。设学习如逆水行舟，学习进步，学习退步。则命题符号化为 （ ）A. ； B； C. ； D. .四、解答题1. 设 上的关系试 （1）写出的关系矩阵； （2）验证是上的等价关系； （3）求出的各元素的等价类。2. 设，上的整除关系，画出的哈斯图。3. 设集合 , 是上的整除关系,画出的哈斯图；4. 设集合, 是上的整除关系，试求：（1） 集合的最大元，最小元（2） 子集和的上界、下界、上确界和下确界。5. 在下面的无向图中，回答下列问题 （1）写出之间的所有初级通路； （2）写出之间的所有短程，并求； （3）判断无向图是否为欧拉图并说明理由。6. 下列各图是否为欧拉图，是否为哈密尔顿图？为什么？ (1) (2)7. 下列图形中最少需添加几条边才能成为欧拉图 a a b e b d c d c （1） （2）8. 有向图如下图所示(1) 求的邻接矩阵；(2) 求中长度为4的通路数和回路数，并找出中从到长度为4的所有通路。(3) 是哪类连通图？9. 设有向图，其邻接矩阵为(1) 画出有向图；(2) 中长度为4的通路有多少条？其中有多少条为回路？(3) 是那类连通图？ 10. 设连通图如下图所示，求它的一棵生成树a b c e f答案不唯一。五、构造下列推理的证明 1. 证明 2. 证明 3. 证明 4. 证明 5. 构造下列推理的证明：每个学术委员会的成员都是专家并且是大学生，有些成员是青年人，所以有些成员是青年专家。6.“有些病人相信所有的医生，病人都不相信骗子，所以医生都不是骗子。”在一阶逻辑中证明以上推理是正确的。六、证明题1. 设为集合上的等价关系, 试证也是集合上的等价关系。2. 设为无向连通图中任意两个顶点，证明：若，则存在顶点，使得3. 证明下面四个矩阵关于矩阵乘法运算构成群。， ， ， 4. 设 是一个群，试证 是交换群 当且仅当对任意的 ,有 . 5. 设是群的元素，记，证明是的子群6. 设是一个群，取定，定义 ， 证明是一个群。离散数学综合练习题答案一、 判断下列命题是否正确（1）错误； （2）错误； （3）正确； （4）错误； （5）错误；（6）正确； （7）错误； （8）正确； （9）正确； （10）错误；（11）正确；（12）正确；（13）正确；（14）正确；（15）正确；（16）正确；（17）正确；（18）正确；（19）正确；（20）正确；（21）正确；（22）错误；（23）正确；（24）正确；（25）正确；（26）正确；（27）正确；（28）正确；（29）正确；（30）错误；（31）正确；（32）错误；（33）错误；（34）错误；（35）错误；（36）正确；（37）正确；（38）正确；（39）错误；（40）错误.二、 填空题（1）； （2）； （3）3； （4）40； (5)(6) ； (7)称为外祖父； (8)5，9； (9)赵= 赵茵，赵萍，钱= 钱小滨，钱浩，钱钰，孙= 孙丽春，李= 李靖华，李秀娟，李惠芝，李莉.(10)(11) ； (12) 1和2；(13)，；(14) ； (15) 2； (16) 1，1； (17) ，； (18) ；(19) ； (20) 0； (21) 5； (22) m-n1； (23) 1； (24) 0； (25) 1；(26) ； (27) ； (28) 11； (29) ； (30) 偶数；(31) ； (32) ； (33) ； (34) 0； (35) 0；(36) ； (37)； (38) ；(39) ； (40) .三、 选择题（1） A； （2） C； （3） C； （4） B； （5） B；（6） A； （7） B； （8） D； （9） B； （10）B；（11）B； （12）D； （13）B； （14）D； （15）D；（16）C； （17）C； （18）D； （19）C； （20）A；（21）A； （22）B； （23）B； （24）C； （25）B；（26）B； （27）B； （28）A； （29）B； （30）C；（31）B； （32）C； （33）B； （34）A； （35）A；（36）D； （37）D； （38）B； （39）B； （40）B.四、 解答题1. 解 （1）的关系矩阵为 （2）从的关系矩阵可知：是自反的和对称的。又由于 所以是传递的。 因为是自反的、对称的和传递的，所以是上的等价关系。（3） ，2. 解： 248 12 4 6 2 33. 解： 32 24 16 12 8 6 2 34. 解：由于是上的整除关系，所以是上的偏序关系，的哈斯图为 4 6 2 3 5 1（1）集合的最大元：无，最小元：1（2）子集上界下界上确界下确界无1无161615. 解：（1）之间的所有初级通路共有7条，分别为，（2）之间的长度最短的通路只有1条，即，因而它是之间唯一的短程，（3）由于无向图中有两个奇度顶点，所以无向图没有欧拉图回路，因而不是欧拉图。6. 解：图（1）中各顶点的度数为 ，由于图（1）中各顶点的度数均为偶数，所以图（1）为欧拉图。 回路为经过图（1）中每个结点一次且仅一次的回路，所以回路为哈密尔顿回路，因此图（1）是哈密尔顿图。图（2）中各顶点的度数为 ，由于图（2）中有两个奇度顶点，所以图（2）存在欧拉图通路，但是没有欧拉图回路，因此图（2）不是欧拉图。 回路为经过图（2）中每个结点一次且仅一次的回路，所以回路为哈密尔顿回路，因此图（2）是哈密尔顿图。7. 解 由于(1)只有两个奇度结点，b,e. 因此，要由(1)得到一个欧拉图，必须使它们的度数都为偶数。最少需添加一条边才能使(1)为欧拉图。由于(2)有 4个奇度结点，因此，要由(2)得到一个欧拉图，必须使它们的度数都为偶数。最少需添加两条边才能使(2)为欧拉图。例如，可在(1)中添加边(b,e), 在(2)中添加边(a,b),(c,d) a a b e b d c d c（1） （2）8. 解：(1) 求的邻接矩阵；(2) , , 中长度为4的通路数为，其中对角元素之和为3，中长度为4的回路有3条。由于中，所以中到长度为4的通路有4条。即，其中为简单通路。(3) 由于 由可知道是单向连通图。9. 解：(1) 有向图为 (2) 由于 中长度为4的通路数为32。因对角元素之和为0，故中无长度为4的回路。(4) 从图可得的可达矩阵为 从可知是强连通的。 10. 解： a b c e f五、 构造下列推理的证明1. 证明： 前提引入； 前提引入； 析取三段论； 前提引入； 置换； 析取三段论。2. 证明 前提引入； 前提引入； 拒取式； 前提引入； 假言推理； 前提引入； 拒取式； 前提引入； 析取三段论。3. 证明 前提引入； 前提引入； 析取三段论； 前提引入； 假言推理； 前提引入； 假言推理。4. 证明： 前提引入； EI； 化简； 前提引入； UI； 假言推理； 化简； 化简； 合取引入(10) EG 5. 解：设是学术委员会的成员，是专家，是大学生，是青年人。前提 结论证明： 前提引入； EI； 前提引入； UI； 化简； 假言推理； 化简； 化简； 合取引入(10) EG 6. 解：记是病人，是医生，是骗子， 相信。则上述推理符号化为前提： 结论：证明： 前提引入； 存在量词消去规则； 化简规则； 前提引入； 全称量词消去规则； 假言推理规则； 全称量词消去规则； 置换； 化简规则； （10） 全称量词消去规则； （11） （10）假言三段论规则；（12） （11）全称量词引入规则；六、 证明题1. 证明：由于是自反的，所以对任意, 因而，即是自反的。 若，则,由于是对称的，所以, 从而，即是对称的。 若，则 ,由于是传递的，所以, 从而，即是传递的。 由于是自反的、对称的和传递的，所以是等价关系。2. 证明：由于的连通性，之间必存在短程，则，取为上除外的任意一点，都有之间的短程为，之间的短程为.否则，若之间存在比短的短程，则比短，这与为之间的短程矛盾。同理可证：为之间的短程。因而等于的长度加上的长度，而的长度加上的长度为的长度 ，即为，所以.3. 证明：令为由上述四个矩阵组成的集合，是矩阵乘法运算，容易验证上述四个矩阵关于矩阵乘法运算是封闭的。(1)由矩阵乘法运算知识知，是可结合的；(2)任取矩阵，由于， 所以矩阵是运算的单位元。(3)由于， ， ，所以中每个元素都是可逆的。 由上面的1，2，3知，是群。4. 解：充分性若在群中，对任意的 ,有 .则 从而 是一个交换群。必要性若 是一个交换群，对任意的 ,有，则 即.5. 证明：由于对任意的，有所以 即 ，由子群的判定定理知是的子群。6. 证明 显然，*是上的二元运算。先证结合律成立。，有 即运算是可结合的.由于，有 故是运算*的单位元. 最后证明，是在中的逆元。由于因此是一个群.