北邮离散数学期末复习题[1]1.doc

离散数学期末复习题第一章集合论一、判断题（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