北邮离散数学期末复习资料题.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 ）是正确的. A．A到B的关系都是A到B的映射 B．A到B的映射都是可逆的 C．A到B的双射都是可逆的 D．时必不存在A到B的双射 （11）设A是集合，则（ B ）成立. A． B． C． D． （12）设A是有限集（），则A上既是又是～的关系共有（ B ）. A．0个 B．1个 C．2个 D．个 三、填空题 1. 设，则____________. 填 2.设，则= . 填 3.设集合中元素的个数分别为，，且， 则集合中元素的个数 .3 4.设集合， ，则中元素的个数为 .40 5.设 , 是 上的包含于关系，,则有 = . 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 ） A． B． C． D． 其中，+，，︱ ︱分别为实数的加法、乘法和取绝对值运算. （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 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 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中各边方向后所得到的无向图是连通的 B．D是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图 C．D的任意两个不同的结点都可以相互到达 D．D是完全图 （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阶完全图的任意两个不同结点的距离都为 ．1 4.图为阶无向完全图，则共有 条边。 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）“如果8＋7＞2，则三角形有四条边”是命题． （ 对 ） （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 ）. A． B． C． D． （4）下列命题中假命题是（ B ）. A．如果雪不是白的，则太阳从西边出来 B．如果雪是白的，则太阳从西边出来 C．如果雪不是白的，则太阳从东边出来 D．只要雪不是白的，太阳就从西边出来 （5）设A，B都是命题公式，则A→B为可满足式是的（ B ）. A．充分而非必要条件 B．必要而非充分条件 C．充分必要条件 D．既非充分又非必要条件 三、填空题 1.设 天气很冷，老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 . 2.设天下雨， 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 . 3. 设的真值为0，的真值为1，则命题公式的真值为 .0 4.设的真值为0，的真值为1，则命题公式的真值为 .0