离散数学期末考试复习题.doc

、判断题（共5道小题，共50.0分） 1. 如果，则或A. 正确 B. 错误 知识点:集合学生答案:B;得分:10试题分值:10.0提示:2. 设为集合 上的等价关系, 则A. 正确 B. 错误 知识点:关系学生答案:B;得分:10试题分值:10.0提示:3. 设为集合上的等价关系, 则也是集合上的等价关系A. 正确 B. 错误 知识点:关系学生答案:A;得分:10试题分值:10.0提示:4. 设A. 正确 B. 错误 知识点:关系学生答案:A;得分:10试题分值:10.0提示:5. (错误) 设集合，则A. 正确 B. 错误 知识点:关系学生答案:A;得分:0试题分值:10.0提示:二、单项选择题（共5道小题，共50.0分） 1. 设A，B，C是集合，则（ ）成立.A. 如果 B. 如果 C. 如果 D. 如果 知识点:集合学生答案:B;得分:10试题分值:10.0提示:2. 设，则下列各式中错误的是A.B.C.D.知识点:集合学生答案:B;得分:10试题分值:10.0提示:3. (错误) 下列各式中不正确的是A.B.C.D.知识点:集合学生答案:B;得分:0试题分值:10.0提示:4. 设为实数集合，下列集合中哪一个不是空集A.B.C.D.知识点:集合学生答案:A;得分:10试题分值:10.0提示:5. 设，则的恒等关系为A.B.C.D.知识点:关系学生答案:A;得分:10试题分值:10.0提示:一、判断题（共5道小题，共50.0分） 1. 设是代数系统的元素，如果是该代数系统的单位元），则A. 正确 B. 错误 知识点:代数系统的基本概念学生答案:A;得分:10试题分值:10.0提示:2. 集合A上的任一运算对A是封闭的A. 正确 B. 错误 知识点:代数系统的基本概念学生答案:A;得分:10试题分值:10.0提示:3. 设是群如果对于任意，有 ，则是阿贝尔群A. 正确 B. 错误 知识点:群、环和域学生答案:A;得分:10试题分值:10.0提示:4. 设是布尔代数，则对任意，有A. 正确 B. 错误 知识点:格和布尔代数学生答案:A;得分:10试题分值:10.0提示:5. 设集合，则是格A. 正确 B. 错误 知识点:格和布尔代数学生答案:A;得分:10试题分值:10.0提示:二、单项选择题（共5道小题，共50.0分） 1. 下列哪个集关于减法运算是封闭的A. （自然数集） B.C.D.知识点:代数系统的基本概念学生答案:B;得分:10试题分值:10.0提示:2.下列定义的实数集R上的运算 * 中可结合的是A.B.C.D.知识点:代数系统的基本概念学生答案:c得分:0试题分值:10.0提示:3. 在整数集上，下列哪种运算是可结合的A.B.C.D.知识点:代数系统的基本概念学生答案:B;得分:10试题分值:10.0提示:4.循环群的所有生成元为A. 1，0 B. -1，2 C. 1，2 D. 1，-1 知识点:群、环和域学生答案:D得分:0试题分值:10.0提示:5.设代数系统A，则下面结论成立的是.A. 如果A，是群，则A，是阿贝尔群 B. 如果A，是阿贝尔群，则A，是循环群 C. 如果A，是循环群，则A，是阿贝尔群 D. 如果A，是阿贝尔群，则A，必不是循环群 知识点:群、环和域学生答案:C得分:0试题分值:10.0提示:一、判断题（共5道小题，共50.0分） 1. 强连通有向图一定是单向连通的A. 正确 B. 错误 知识点:无向图和有向图学生答案:A;得分:10试题分值:10.0提示:2. 有生成树的无向图是连通的A. 正确 B. 错误 知识点:树学生答案:A;得分:10试题分值:10.0提示:3. 设P，Q都是命题公式，则A. 正确 B. 错误 知识点:命题逻辑学生答案:A;得分:10试题分值:10.0提示:4. 设都是命题公式，则也是命题公式A. 正确 B. 错误 知识点:命题逻辑学生答案:B;得分:10试题分值:10.0提示:5. “如果872，则三角形有四条边”是命题A. 正确 B. 错误 知识点:命题逻辑学生答案:A;得分:10试题分值:10.0提示:6.二、单项选择题（共5道小题，共50.0分） 1.设G1=V1,E1,G2=V2,E2都是无向图，则#V1=#V2且#E1=#E2是G1与G2同构的A. 充分必要条件 B. 充分而非必要条件 C. 必要而非充分条件 D. 既非充分又非必要条件 知识点:无向图和有向图学生答案:C得分:0试题分值:10.0提示:2.有向图，其中，则有向图是A. 强连通图 B. 单向连通图 C. 弱连通图 D. 不连通图 知识点:无向图和有向图学生答案:C得分:0试题分值:10.0提示:3. 是无向图的关联矩阵，是中的孤立点，则A. 对应的一行元素全为0 B. 对应的一行元素全为1 C. 对应的一列元素全为0 D. 对应的一列元素全为1 知识点:图的矩阵表示学生答案:A;得分:10试题分值:10.0提示:4.由前提得到的有效结论为A. S B. Q C. P D.知识点:命题逻辑学生答案:C得分:0试题分值:10.0提示:5. 设个体域，公式在上消去量词后应为A.B.C.D.知识点:一阶逻辑学生答案:B;得分:10试题分值:10.0提示:离散数学期末复习题第一章集合论一、判断题（1）空集是任何集合的真子集 （ 错 ）（2）是空集 （ 错 ）（3） （ 对 ）（4）设集合. ( 对 ）（5）如果，则或 （ 错 ）解 则，即且，所以且（6）如果A （ 对 ）（7）设集合，则 （ 错 ）（8）设集合，则是到的关系 （ 对 ）解 ，（9）关系的复合运算满足交换律 （ 错 ）（10） （ 错 ）（11）设 ( 对 )（12）集合A上的对称关系必不是反对称的. （ 错 ）（13）设为集合上的等价关系, 则也是集合上的等价关系( 对 )（14）设是集合上的等价关系, 则当时， ( 对 )（15）设为集合 上的等价关系, 则 ( 错 )二、单项选择题（1）设为实数集合，下列集合中哪一个不是空集 （ A ）A. B C. D. （2）设为集合，若，则一定有 （ C ）A. B C. D. （3）下列各式中不正确的是 （ C ）A. B C. D. （4）设，则下列各式中错误的是 （ B ）A. B C. D. （5）设，则为 （ B ）A. B C. D. （6）设，则的恒等关系为 （ A ）A. B C. D. （7）设上的二元关系如下，则具有传递性的为 （ D ）A. B C. D. （8）设为集合上的等价关系，对任意，其等价类为 （ B ）A. 空集； B非空集； C. 是否为空集不能确定； D. .（9）映射的复合运算满足 （ B ）A. 交换律 B结合律 C. 幂等律 D. 分配律（10）设A，B是集合，则下列说法中（ C ）是正确的.AA到B的关系都是A到B的映射BA到B的映射都是可逆的CA到B的双射都是可逆的D时必不存在A到B的双射（11）设A是集合，则（ B ）成立.A BCD（12）设A是有限集（），则A上既是又是的关系共有（ B ）.A0个B1个C2个D个三、填空题1. 设，则_.填2.设，则= . 填3.设集合中元素的个数分别为，且，则集合中元素的个数 .34.设集合，则中元素的个数为 .405.设 , 是 上的包含于关系，,则有= .6.设为集合 上的二元关系, 则 . 7.集合上的二元关系为传递的充分必要条件是 8. 设集合及集合A到集合的关系|_.填 四、解答题1. 设 上的关系 （1）写出的关系矩阵； （2）验证是上的等价关系； （3）求出的各元素的等价类。解 （1）的关系矩阵为 （2）从的关系矩阵可知：是自反的和对称的。又由于 或满足所以是传递的。 因为是自反的、对称的和传递的，所以是上的等价关系。（3） ，2. 设集合，是上的整除关系，（1） 写出的关系矩阵；（2） 画出偏序集的哈斯图；（3） 求出的子集的最小上界和最大下界。解：（1） （2） （3）lubB=6, glbB=1 五、证明题1. 设为集合上的等价关系, 试证也是集合上的等价关系。证明：由于是自反的，所以对任意, 因而，即是自反的。 若，则,由于是对称的，所以, 从而，即是对称的。 若，则 ,由于是传递的，所以, 从而，即是传递的。 由于是自反的、对称的和传递的，所以是等价关系。第二章 代数系统一、判断题（1）集合A上的任一运算对A是封闭的 （ 对 ）（2）代数系统的零元是可逆元. （ 错 ）（3）设A是集合，则是可结合的 （ 对 ）（4）设是代数系统的元素，如果是该代数系统的单位元），则 ( 对 ) （5）设 （ 错 ）（6）设是群如果对于任意，有 ，则是阿贝尔群 （ 对 ）（7）设 （ 对 ）（8）设集合，则是格 （ 对 ）（9）设是布尔代数，则是格 （ 对 ）二、单项选择题（1）在整数集上，下列哪种运算是可结合的 （ B ）A. B C. D. （2）下列定义的实数集R上的运算 * 中可结合的是. （ C ）ABCD其中，+， 分别为实数的加法、乘法和取绝对值运算.（3）设集合，下面定义的哪种运算关于集合不是封闭的 （ D ）A. B C. ，即的最大公约数D. ，即的最小公倍数（4）下列哪个集关于减法运算是封闭的 （ B ）A. （自然数集）； B；C. ； D. .（5）设是有理数集，在定义运算为，则的单位元为 （ D ）A. ； B； C. 1； D. 0（6）设代数系统A，则下面结论成立的是. （ C ）A如果A，是群，则A，是阿贝尔群B如果A，是阿贝尔群，则A，是循环群C如果A，是循环群，则A，是阿贝尔群D如果A，是阿贝尔群，则A，必不是循环群（7）循环群的所有生成元为 （ D ）A. 1，0 B-1，2 C. 1，2 D. 1，-1三、填空题1. 设为非空有限集，代数系统中，对运算的单位元为 ，零元为 .填2.代数系统中（其中为整数集合，+为普通加法），对任意的，其 .填3.在整数集合上定义运算为，则的单位元为 .解 设单位元为，所以，又，所以单位元为4.在整数集合上定义运算为，则的单位元为 .解设单位元为，所以5.设是群，对任意，如果，则 .填6.设是群，为单位元，若元素满足，则 .填四、解答题1.设为实数集上的二元运算，其定义为，对于任意求运算的单位元和零元。解：设单位元为，则对任意，有，即 ，由的任意性知 ，又对任意，；所以单位元为0 设零元为，则对任意，有，即 ，由的任意性知 又对任意，所以零元为 2. 设为集合上的二元运算，其定义为，对于任意（1） 写出运算的运算表；（2） 说明运算是否满足交换律、结合律，是否有单位元和零元、如果有请指出；（3） 写出所有可逆元的逆元解：（1）运算表为 0 1 2 3 40 0 0 0 0 01 0 1 2 3 42 0 2 4 1 33 0 3 1 4 24 0 4 3 2 1（2）运算满足交换律、结合律，有单位元，单位元为1，有零元，零元为0；（3）1的逆元为1，2的逆元为3，3的逆元为2，4的逆元4，0没有逆元五、证明题1. 设 是一个群，试证 是交换群 当且仅当对任意的 ,有 .证明：充分性若在群中，对任意的 ,有 .则 从而 是一个交换群。必要性若 是一个交换群，对任意的 ,有，则 即.2. 证明代数系统是群，其中二元运算定义如下： ：，（这里，+，分别是整数的加法与减法运算.）证明 （1）运算满足交换律 对任意Z，由 满足结合律；（2）有单位元 3是单位元；（3）任意元素有逆元对任意Z，Z，是群.第三章 图论一、判断题（1）n阶完全图的任意两个不同结点的距离都为1. （ 对 ）（2）图G的两个不同结点连接时一定邻接. （ 错 ）（3）图G中连接结点 （ 错 ）（4）在有向图中，结点到结点的有向短程即为到的有向短程 （ 错 ）（5）强连通有向图一定是单向连通的 （ 对 ）（6）不论无向图或有向图，初级回路一定是简单回路 （ 对 ）（7）设图G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的 （ 对 ）（8）有生成树的无向图是连通的 （对）（9）下图所示的图是欧拉图. （ 错 ）（10）下图所示的图有哈密尔顿回路. （ 对 ）二、单项选择题（1）仅由孤立点组成的图称为 （ A ）A. 零图； B平凡图； C. 完全图； D. 多重图.（2）仅由一个孤立点组成的图称为 （ B ）A. 零图； B平凡图； C.多重图； D. 子图.（3）在任何图中必有偶数个 （ B ）A. 度数为偶数的结点； B度数为奇数的结点； C. 入度为奇数的结点； D. 出度为奇数的结点.（4）设为有个结点的无向完全图，则的边数为 （ C ）A. B C. D. （5）在有个结点的连通图中，其边数 （ B ）A. 最多条； B至少条；C. 最多条； D. 至少条.（6）任何无向图中结点间的连通关系是 （ B ）A. 偏序关系； B等价关系；C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系.（7）对于无向图，下列说法中正确的是. （ B ）A不含平行边及环的图称为完全图B任何两个不同结点都有边相连且无平行边及环的图称为完全图C具有经过每条边一次且仅一次回路的图称为哈密尔顿图D具有经过每个结点一次且仅一次回路的图称为欧拉图（8）设D是有向图，则D强连通的充分必要条件为. ( C )A略去D中各边方向后所得到的无向图是连通的BD是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图CD的任意两个不同的结点都可以相互到达DD是完全图（9）对于无向图G，以下结论中不正确的是. （ A ）A如果G的两个不同结点是连接的，则这两个结点之间有初级回路B如果G的两个不同结点是连接的，则这两个结点之间至少有一条短程C如果G是树，则任何两个不同结点之间有且仅有一条初级通路 D如果G是欧拉图，则G有欧拉回路三、填空题1. 设树T中有7片树叶，3个3度结点，其余都是4度结点，则T中有 个4度结点.解 用握手定理和树的性质列出方程求解，设有个4度结点，2.设为树，中有4度，3度，2度分支点各1个，问中有 片树叶。解 与上题解法相同，设有片树叶，3.n阶完全图的任意两个不同结点的距离都为 14.图为阶无向完全图，则共有 条边。5.设为图，则图中结点度数的总和为 。6. 图G为欧拉图的充分必要条件是_. G为无奇度结点的连通图四、解答题1. 对下图所示的图G，求（1）G的邻接矩阵；（2）G的结点之间长度为3的通路；（3）G的连接矩阵；（4）G的关联矩阵。 解 （1） A=（2） 因为 A2= A3=所以，结点之间长度为3的通路共有7条，它们是 （3）由于图G是连通的，所以 C=（4） M=2. 在下面的有向图中，回答下列问题（1）写出图的邻接矩阵； （2）写出结点到结点的长度为3的所有有向通路； （3）写出结点到自身的长度为3的所有有向回路；解：（1）（2） 所以结点到结点的长度为3的所有有向通路只有一条: （3）结点到自身的长度为3的所有有向回路只有一条：3.在下面的无向图中，回答下列问题 （1）写出之间的所有初级通路； （2）写出之间的所有短程，并求； （3）判断无向图是否为欧拉图并说明理由。解（1）之间的所有初级通路共有7条，分别为， （2）之间的长度最短的通路只有1条，即，因而它是之间唯一的短程， （3）由于无向图中有两个奇度顶点，所以无向图没有欧拉回路，因而不是欧拉图。第四章 数理逻辑一、判断题（1）“如果872，则三角形有四条边”是命题 （ 对 ）（2）设都是命题公式，则也是命题公式 （ 错 ）（3）命题公式的真值分别为0，1，则的真值为0（以上是在对所包含的命题变元的某个赋值下） （ 错 ）（4）设他生于1964年，则命题“他生于1963年或1964年”可以符号化为 （ 对 ）（5）设P，Q都是命题公式，则（ 对 ）（6）逻辑结论是正确结论 （ 错 ）（9）设都是命题公式，则 也是命题公式 （ 对 ）（10）命题公式的真值分别为0，1，则的真值为0（以上是在对所包含的命题变元的某个赋值下） （ 对 ）二、单项选择题（1）下面哪个联结词不可交换 （ B ）A. ； B； C.； D. .（2）命题公式是 （ C ）A. 永假式； B非永真式的可满足式；C. 永真式； D. 等价式.（3）记他懂法律，他犯法，则命题“他只有懂法律，才不会犯法”可符号化为（ B ）.ABCD（4）下列命题中假命题是（ B ）.A如果雪不是白的，则太阳从西边出来B如果雪是白的，则太阳从西边出来C如果雪不是白的，则太阳从东边出来D只要雪不是白的，太阳就从西边出来（5）设A，B都是命题公式，则AB为可满足式是的（ B ）.A充分而非必要条件B必要而非充分条件C充分必要条件D既非充分又非必要条件三、填空题1.设 天气很冷，老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 .2.设天下雨， 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 .3. 设的真值为0，的真值为1，则命题公式的真值为 .04.设的真值为0，的真值为1，则命题公式的真值为 .0离散数学综合练习题 一、判断下列命题是否正确如果正确，在题后括号内填“/”；否则，填“” （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）错误；（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）设集合中元素的个数分别为，且，则集合中元素的个数 . （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）； （2）； （3）3； （4）40； (5)(6) ； (7)称为外祖父； (8)5，9； (9)赵= 赵茵，赵萍，钱= 钱小滨，钱浩，钱钰，孙= 孙丽春，李= 李靖华