离散数学-习题集.pdf

离散数学 习题集 离散数学 习题集 第一部分 判断题 第一部分 判断题 一 第一章 集合 一 第一章 集合 1 已知集合A的元素个数为 10 则集合A的幂集的基 10 2 2 已知两个集合 A B 若 A 中的元素都是 B 中的元素 则记为 A B 2 已知集合A的元素个数为n 则集合A的幂集P A 的元素个数为n 2 3 已知两个集合 A B 则 A B 4 已知两个集合 A B 则 A B 5 已知两个集合 A B 若 A 中的元素都是 B 中的元素 则记为 A B 6 已知集合A的元素个数为n 则集合A的幂集P A 的元素个数为n 2 7 已知集合A的元素个数为n 则A A的幂集的元素个数为n 2 8 已知两个集合 A B 则 A B 是由属于 B 但不属于 A 的元素构成的集合 二 第二章 二元关系 二 第二章 二元关系 1 若R是A上的二元关系 IA是A上的恒等关系 则当且仅当IA R时 R是A上的自反关系 2 若 R 是集合 A 上的二元关系 且当 a b R 且 a c R 时 就有 b c R 则 R 是 A 上的可传递关系 3 设A是集合 A1 A2 An都是A的非空子集 令S A1 A2 An 则如果S是集合A的一个 划分 那么S一定是集合A的一个完全覆盖 反之亦然 5 R 是非空集合 A 上的等价二元关系 则 A 关于 R 的商集 A R 是集合 A 的一个划分 但不是 A 的一 个完全覆盖 6 已知集合A有 4 元素 易知集合A共有 24个互不相同的子集合 所以在集合A上一共可定义 24个互 不相同的二元关系 7 若R1和R2都是集合A上的可传递二元关系 则R1 R2也是A上的传递关系 8 设 R 是有限的非空集合 A 上的偏序关系 则 A 必有极大 小 元和最大 小 元 9 若R1和R2都是集合A上的相容关系 则R1 R2也是A上的相容关系 10 若R1和R2都是集合A的可传递二元关系 则R1 R2也是A上的传递关系 11 R 是集合 A 上的等价关系 商集 A R 是 A 的划分 但不是 A 的完全覆盖 12 设 R 是有限的非空集合 A 上的偏序关系 则 A 至少有一个最大 小 元 13 R 是集合 A 上的自反二元关系 则 R 的传递闭包仍是 A 上的自反关系 三 第三章 函数 三 第三章 函数 1 设集合 A a b c B x y z e R 是 A 到 B 的二元关系 若 R a x b y c z 则 R 的逆关系是 B 到 A 的函数 2 设I是整数集合 N是自然数集合 f是I到N的函数 且对任意的整数x I都有f x x 3 则f是I到N的 双射函数 3 若 f 是集合 A 到 B 的双射函数 则 f 的逆关系称为 f 的逆函数 4 设集合 A a b c B x y z e R 是 A 到 B 的二元关系 若 R a x b y c z 则 R 的逆关系是 B 到 A 的函数 5 设I是整数集合 N是自然数集合 f是I到N的函数 且对任意的整数x I都有f x x 3 则f是 I到N的双射函数 6 若 f 是 A 到 B 的单射函数 则 f 的逆关系即为 B 到 A 的函数 7 若 f 是 A 到 B 的满射函数 则 f 的逆关系必为 B 到 A 的满射函数 四 第四章 代数系统 四 第四章 代数系统 1 设 G 是代数系统的运算 对 G 是封闭的 可结合的 且 G 中存在幺元 称 G 为群 2 对于代数系统 A 如果 A 中存在幺元 则 A 中每个元素都有逆元 3 若 A 是群 则在 A 运算表中 每一列 行 的元素互不相同 4 含有幺元的半群叫独异点 每个元素都有逆元的独异点称为群 5 对于一个代数系统 A 若 A 中每个元素都有右幺元 则也都有左幺元 6 设 G 是 12 阶群 则 G 必存在 2 阶子群 7 设 G 是有限群 则在 G 的运算表中每一行 列 中的元素都是互不相同的 8 可交换群也称为 阿贝尔群 循环群必是 阿贝尔群 反之亦然 9 设 G 是有限群 H 是其子群 若 G m H n 则 n 必整除 m 五 第五章 图论 五 第五章 图论 1 一个无向连通图是半欧拉图的充要条件是图中至少有两个奇度点 2 在有向树 T 中 如果某内点有 n 个儿子 则称 T 为完全 n 元树 3 已知图 G 是一个由 n 个顶点 m 条边构成的无向连通平面图 则 n 和 m 满足下面不等式 3n 6 m 4 一个无向连通图是半欧拉图的充要条件是图中至少有两个奇度点 5 若无向简单图G V1 V2 是完全二部图 则它也是无向简单完全图 6 设 T 是具有 n 片叶子的完全二元树 则 T 共有 2n 1 个顶点 六 第六章 命题逻辑 六 第六章 命题逻辑 1 设S是一命题公式 若S可以逻辑等价地写成A1 A2 An 其中Ai均为由命题公式S的命题变元 或其否定构成的析取式 则称A1 A2 An为S的析取范式 2 设 P Q 是命题 P 和 Q 的排斥析取也是一个命题 当且仅当 P 和 Q 的真值都为 T 时 P 和 Q 的排 斥析取为 T 其它情况 P 和 Q 的排斥析取为 F 3 若 A B 是两个命题公式 A B 是指在命题变元的各种可能指派下 命题公式 A B 取真值 T 和假值 F 的个数都一样多 4 在谓词合式中 一个变量要么是约束元 要么是自由元 5 已知命题公式 A 在其变元的各种可能的指派下共有 5 种情况取 T 值 11 种情况取 F 值 则 A 的 主析取范式中必有 5 个合取项 主合取范式中必有 11 个析取项 七 第七章 谓词逻辑 七 第七章 谓词逻辑 1 设 P X X 是素数 Q X X 是偶数 有些素数是偶数 符号化为 彐 X P X Q X 2 在谓词逻辑中 一般地 全称量词的特性谓词常作蕴含的前件 存在量词的特性谓词常作合取项 第二部分 填空题 第二部分 填空题 一 第一章 集合 一 第一章 集合 1 设 A 为有限集合 则 A 2 3 4 设 A 4 则 A A 5 设 A B 是有限集合 则 A B 6 设 A a 则 A 的幂集 P A 7 已知集合 N 则集合 N 的幂集 P N 8 设 A B 是两个集合 且 A 3 B 5 则 A 到 B 可以定义 种不同的函数 二 第二章 二元关系 二 第二章 二元关系 1 设集合 A 1 2 3 4 那么在集合 A 上一共可定义 种互不相同的对称关系 2 设 A 1 3 5 7 9 R 是 A 上的模 4 同余关系 试写出 A 关于 R 的商集 A R 3 如果 R 是集合 A 2 3 4 5 6 10 12 上的整除关系 则 A 的极大元是 极小元是 最大元是 最小元是 4 设 A 1 2 3 4 R 是 A 上的全域关系 则由 R 确定的集合 A 的划分为 6 设 R 是非空集合 A 上的二元关系 如果 R 是自反的 和可传递的二元关系 则称 R 是 A 上的偏序关系 或叫半序关系 6 若 R 是集合 A 上的自反关系 则 R 的对称闭包 填 是 或 不是 A 上的自反关系 三 第三章 函数 三 第三章 函数 1 若 f 是集合 A 到 B 的单射函数 则 A 和 B 的元素个数之间有关系式 2 某人步行 10 小时 共走 65 公里 已知他第一小时走了 4 公里 最后一小时走了 7 公里 则必有连续 的两小时 在这两小时内至少走了 公里 四 第四章 代数系统 四 第四章 代数系统 1 代数系统 R 中的幺元是 R 0 中的幺元是 2 代数系统 N6 6 中 4 的逆元是 5 的逆元是 3 群 N5 0 为模 5 乘法运算 中元素 2 的阶数是 4 代数系统 N6 中 若 为模 6 加法运算 则元素 5 的逆元是 5 群 N5 0 中 若 为模 5 乘法运算 则元素 2 的阶数是 6 当 A 为 注 可填半群 独异点 群 子群其中之一 时 若 a b A 有 a b a 或 b a a 则 A 的幺元是 a 7 群 N5 0 5 中 元素 2 的阶数是 8 群 N7 0 7 中的生成元是 9 具有 n 个顶点的无向树 各顶点的度数和为 10 群 N12 12 中元素 8 关于子群 0 4 8 12 的陪集是 五 第五章 图论 五 第五章 图论 1 若 G 是无向连通平面图 它具有 n 个顶点 m 条边 r 个区域 则欧拉公式为 2 若平面图 G 有 n 个顶点 m 条边 r 个区域 则有欧拉公式 3 设图 G 是完全二元树 且有 t 片叶子 那么它有 条边 4 设 T 是树叶权为 1 2 3 4 5 的最优树 则树 T 的权为 5 具有 n 个顶点的无向树 各顶点的度数和为 6 当n和m满足什么条件 时 完全二部图Kn m是欧拉图 7 若G V1 V2 是完全二部图 且 V1 n V2 m 则G有 条边 8 设 G 是一棵无向树 它有 n 个顶点 m 条边 则 n 和 m 间有关系式 9 树 T 有 2 个 2 度点 3 个 3 度点 4 个 4 度点 无大于 4 度的点 该树有 个 1 度点 10 一棵具有 n 个顶点的二元树 它的最大高度是 六 第六章 命题逻辑 六 第六章 命题逻辑 1 写出 P Q 的主析取范式为 2 P Q R 的主合取范式为 3 设 P 表示 天下雪 Q 表示 我去看电影 R 表示 我在家复习功课 则 如果天不下雪 那么我 去看电影 否则我在家复习功课 可符号化为 4 写出下面命题的有效结论 如果我努力学习 那么我能通过考试 我没有通过考试 则有效结论为 5 给定命题 今晚 9 00 整 中央电视台五套节目转播 NBA 比赛或足球比赛 若令 P 表示 转播 NBA 节目 Q 表示 转播足球比赛 则该命题可符号化为 七 第七章 谓词逻辑 七 第七章 谓词逻辑 1 用谓词合式表示命题 如果两数的乘积为零 则其中至少有一个数为零 其中 P x y 表示 x 与 y 的乘积为零 A x 表示 x 为零 B y 表示 y 为零 则符号化的谓词合式为 2 在谓词合式 V x P x y Q x 彐y R y S y 中 是约束元 第三部分 单项选择题 第三部分 单项选择题 一 第一章 集合 一 第一章 集合 1 设 A B 是集合 如果 A B a 则 A A B 且 A B B A B 但 A B C A B 但 A B D A B 且 A B 二 第二章 二元关系 二 第二章 二元关系 1 设 A a b c A 上的二元关系 R a a a b a c 则 R 是 A 自反的 B 反自反的 C 对称的 D 反对称的 2 集合 A 3 4 5 6 8 10 12 24 R 是 A 上的整除关系 则子集 3 4 6 的上确界是 A 6 B 8 C 10 D 12 3 设 R 是 A a b c A 上的二元关系 R a a a b a c c a 那么 R 是 A 自反的 B 反自反的 C 对称的 D 反对称的 E 可传递的 4 若 A 2 3 4 5 6 8 10 12 24 R 是 A 上的整除关系 则 R 是集合 A 上的 A 相容关系 B 等价关系 C 偏序关系 D 不确定 三 第三章 函数 三 第三章 函数 1 下列二元关系中 哪个能构成函数 A 集合 A 1 2 3 B 4 5 6 当 a A b B 且 a n 1 n 2 2 证明 G 是连通的 19 证明 小于 30 条边的简单平面图有一个结点度数小于等于 4 P171 2 20 证明 在简单平面图中 必存在一点 其读数小于等于 5 P171 3 21 证明每个区域至少有 4 条边任何连通简单平面图中 m 2n 4 其中 n 为结点数 m 为边数 22 证明 在有 6 个结点 12 条边的连通简单平面图中 每个区域由 3 条边组成 23 设 G 是至少有 11 个顶点的无向简单连通平面图 证明 G 的补图一定是非平面图 例 5 10 24 如果图G是具有n个顶点 m条边的二部图 证明m n2 4 P165 1 25 证明 一棵完全二元树 必有奇数个结点 定理 5 10 1 中的 特别 26 设图 G 是简单连通平面图 如果 G 是自对偶图 试证明 G 中至少存在 4 个 3 度点 P171 10 概念解释 如果图 G 的对偶图与 G 同构 则称 G 为自对偶图 27 若 G 是有 n 个顶点 m 条边的连通平面 且图 G 的每个区域至少有 k k 3 条边围成 则 m k n 2 k 2 P167 补例 六 第六章 命题逻辑 六 第六章 命题逻辑 1 试用 PT 规则证明 P Q P R Q S 永真蕴含 R S P194 例 6 19 2 试证明 P Q Q R 永真蕴含 P R 期中 3 求证 A B C D D H E 永真蕴含 A E 4 证明 A B C C D E F D E A B F 5 证明 P Q P Q 七 第七章 谓词逻辑 七 第七章 谓词逻辑 1 求证 Vx P x Q x Vx Q x R x 彐X R x 彐x P x 2 利用谓词演算的推理理论 试证明苏格拉底的三段论 即要证明 所有的人都是要死的 苏格拉底是人 所以苏格拉底是要死的 第五部分 综合题 第五部分 综合题 一 第一章 集合 一 第一章 集合 1 70 名学生参加体育比赛 短跑得奖者 36 人 跳高得奖者 29 人 投掷得奖者 36 人 三项都得奖者 6 人 仅得 2 项奖者有 24 人 问一项奖都没有得到的人数有几人 期中 3 2 某班有学生 50 人 其中不会骑自行车的有 23 人 不会滑旱冰的有 35 人 两样都会的有 4 人 问两样 都不会的有多少人 3 某班有学生 60 人 其中有 38 人学习 PASCAL 语言 有 16 人学习 C 语言 有 21 人学习 COBOL 语言 有 3 个人这 3 种语言都学习 有 2 个人这 3 种语言都不学习 问仅学习两门语言的学生数是多少 二 第二章 二元关系 二 第二章 二元关系 1 若集合 A 有 5 个元素 问在 A 上一共可定义多少种互不相同的等价关系 期中 2 已知集合 A 有 3 个元素 试问 1 集合 A 的幂集有几个元素 2 在集合 A 上共可定义多少个互不相同的二元关系 3 在集合 A 上共可定义多少个互不相同的自反关系 4 在集合 A 上共可定义多少个互不相同的对称关系 5 在集合 A 上共可定义多少个互不相同的等价关系 3 A 1 2 3 4 5 6 8 10 12 16 24 R 是 A 上的整除关系 画出 R 的哈斯图 并求 A 的极大 极小元和最大 最小元 并求子集 2 4 6 12 的上界 下界和上确界 下确界 期中 4 集合 A 111 122 341 456 666 745 843 当 a b A 且 a b 至少有一个数码相同时 a b R 求 R 的所有最大相容类 5 集合 A 2 4 6 8 10 12 14 16 R 是 A 上的模 3 同余关系 写出 R 的所有不同的等价类 6 A a b c d e f g 将 A 中元素分成 3 个组 a b c 是一组 d e 是一组 f g 是一组 在 A 上定义二元关系 R 当 A 中元素在同一组内时 认为是相关的 试说明 R 是等价关系 并写出它的表格 表示和矩阵表示 7 已知 A a1 a2 a3 a4 a5 R a1 a2 a2 a3 a3 a3 a3 a4 a5 a1 a5 a4 求 R 的传递闭包 三 第三章 函数 三 第三章 函数 1 集合 A 具有 3 个元素 集合 B 具有 4 个元素 问 A 到 B 可以定义多少种不同的 1 二元关系 2 函数 3 单射函数 4 满射函数 2 某班在一次离散数学课上老师出了两道题 规定做对一道题得 1 分 不做得 0 分 做错得 1 分 老师 说 可以肯定全班同学中至少有 5 名同学每题的得分数都相同 那么 这个班至少有多少人 四 第四章 代数系统 四 第四章 代数系统 1 求群 N12 12 的所有非平凡子群 P85 例 4 15 2 写出代数系统 N7 7 中各元素的逆元 如果存在逆元 和各元素的阶 3 试分别求出代数系统 N5 5 和 N5 5 中的幺元 等幂元 零元和各元素的逆元 4 设 A 是半群 A 是有限集合 则 A 中必存在等幂元 5 若 A 是群 a 是 A 的一个元素 如果在 A 中存在另一个元素 b 使得 a b b 则 1 a 必为等幂 元 2 群 A 中的等幂元是唯一的 6 写出代数系统 N7 7 中各元素的逆元 如果存在着逆元 和各元素的阶 五 第五章 图论 五 第五章 图论 1 设 G 为无向连通图 有 n 个结点 那么 G 中至少有几条边 为什么 对有向图如何 2 问有 6 个顶点的不同构的无向树有几种 试画出这些无向树 P172 补例 3 试画出树叶权为 1 2 3 5 6 7 11 12 的最优树 并求出最优树的权 P179 6 4 某次会议有 20 人参加 其中每人都至少有 10 个朋友 这 20 人围一圆桌入席 要想使每人相邻的两位 都是朋友是否可能 试说明理由 5 已知图 G 是一个有 50 条边的简单无向连通图 它没有大于 5 度的点 但有 5 个 5 度点 4 个 4 度点 3 个 3 度点 问图 G 最多有几个顶点 最少有几个顶点 最多 51 最少 37 6 某城市拟在六个区之间架设有线电视网 其网点间距离如下面有权图矩阵给出 如 a32 4 表示 a3 到 a2 有一条长为 4 的电视线 试给出架设线路的最优方案 请画出图 并计算出线路的长度 7 一棵无向树有n2个 2 度点 n3个 3 度点 nk个k度点 问它有几个 1 度点 8 求下图 图一 中 a 到 z 的最短通路及最短通路的权和 9 求下图 图一 中 a 到 z 的最短通路及最短通路的权和 10 一棵无向树有 13 个 1 度点 2 个 2 度点 3 个 3 度点 且没有大于 4 度的点 问这棵树有几个 4 度点 11 求下图 图 1 的最小生成树 12 设 T 是无向树 它有 40 个 1 度点 20 个 2 度点 31 个 3 度点 且没有大于等于 6 度的顶点 问 树 T 有多少个 4 度点和多少个 5 度点 13 设无向树 T 有 7 片叶子 其余顶点的度数均为 3 求 T 中 3 度顶点的个数 14 下面哪一种图不是树 a 无回路的连通图 b 有 n 个结点 n 1 条边的连通图 c 每对