离散数学复习资料和试题

离散数学复习资料和试题离散数学复习资料和试题 集合论 1 集合与集合之间的关系 元素与集合之间的关系 1 判别下列各题是否正确 1 1 2 1 2 3 1 2 3 正确 2 p q r p q r p q r 正确 2 设有集合 a b c 为空集 则 a 3 设 S1 S2 S3 S3 则 S2 S4为假命题 2 幂集 A 就是集合 A 中子集所组成的集合 求下列集合的幂集 1 a a a a a a 2 a a a a a a a a a a 3 集合的运算 10 组集合恒等式 1 交换率 A B B A A B B A 2 结合律 A B C A B C A B C A B C 3 分配律 A B C A B A C A B C A B A C 4 同一律 A A A E A 5 零一律 A A E E 6 互补率 A A E A A E E 7 双重否定率 A A 8 幂等率 A A A A A A 9 吸收率 A A B A A A B A 10 德摩根率 A B A B A B A B 交 A B 并 A B 差运算 A B 属于 A 不属于 B 补运算 A 对称差运算 A B 笛卡儿乘积 A B a A b B 设 A a b c B b d e 则 A B a c A B a c d e 4 集合的计数问题 A 2 n n 是集合 A 的元素的个数 A B A B A B A B C A B C A B A C B C A B C 5 关系的性质 由图写出性质 有性质画图 由关系集合写性质 自反性 反自反性 对称性 反对称性 传递性 P34 2 6 用图表示出来的在集合 X 1 2 3 上的关系的 6 个图形 从图中可以清楚的看出 1 R1 是自反的 对称的 又是传递的 它是一个全关系 2 R2是反自反的 反对称的 QQ374289236 3 R3不是反自反的 反对称的 4 R4是自反的 反对称的 5 R5是反自反的 对称的 反对称的 传递的 它是一个空关系 6 映射与关系 6 设集合 A a1 a2 a3 a4 B b1 b2 b3 a1 b2 a2 b2 a3 b1 a4 b3 则 是满射但不是单射 7 关系的闭包 r R R IA s R R R t R R R 1 R 2 R 3 R n 1 设 A a b c R1 R2是 A 上的二元关系 R1 a a b b b c d d R2 a a b b b c c b d d 试证明 R1是 R2的何种闭包 解 R1 R1 a a b b b c d d c b 即有 R1 R1 R2 根据对成闭包的定义及求解方法只 R2是 R1 的对称闭包 2 设集合 A a b c d 定义 R a b b a b c c d 求 r R s R t R 解 r R a a b b c c d d a b b a b c c d s R a b b a b c c b c d d c t R a a b b a b a c a d b a b c b d c d 3 由关系集合写性质 设 A a b c R a a b b 具有反对称性 8 关系的运算 复合运算 R1R2 1 设 X 0 1 2 3 X 上有两个关系 R1 i j j i 1 或 j i 2 R2 i j i j 2 求复合关系 R1R2 R1 0 1 1 2 2 3 0 0 2 1 R2 2 0 3 1 则有 R1R2 1 0 2 1 2 设 R1 R2是集合 A 1 2 3 4 上的二元关系 其中 R1 1 1 1 2 2 4 R2 1 4 2 3 2 4 3 2 试求 R1R2 解 R1R2 1 4 1 3 9 特殊关系 等价关系 1 A 0 1 2 4 5 8 9 R 为 A 上模为 4 的同余关系 求 1 R 的所有等价类 2 画出 R 的关系图 解 R 0 0 1 1 2 2 9 9 0 4 4 0 1 5 5 1 4 8 8 4 5 9 9 5 0 8 8 0 1 9 9 1 1 0 R 0 4 8 4 R 8 R 1 R 1 5 9 5 R 9 R 2 R 2 2 QQ374289236 2 A a b c d A 的等价关系 R a a b b c c d d a b b a 8 4 c d d c 求 1 图 2 A 的等价类 3 A R 商集 解 1 2 a R b R a b c R d R c d 3 A R a b c d 3 A 1 2 4 24 上定义 R x y A 且 x y 能被 12 整除 1 写出 R 2 画图 3 证明 R 是等价关系 解 1 R 2 3 定义法 若证明 R 为等价关系 只需证明 R 具有自反性 对称性 传递性 自反性 x A 则 R 所以 R 具有自反性 对称性 若 R 则 12 x y y x x y 所以 12 y x 故 R 所以 R 具有对称性 传递性 如果 R 且 R 则 12 x y 且 12 y z 则 x z x y y z 能被 12 整除 故 12 x z R 所以 R 具有传递性 综上所述 R 为等价关系 偏序关系 1 集合 X 2 3 6 8 上的整除关系 R 2 2 3 3 6 6 8 8 2 6 2 8 3 6 是偏序的 求其哈斯图 2 集合 A 2 3 6 12 24 36 上的整除关系 R 是偏序的 它可用哈斯图表示 R 2 2 3 3 6 6 12 12 24 24 36 36 2 6 3 6 6 12 12 24 2 12 3 12 6 24 12 36 2 24 3 24 6 36 2 36 3 36 求特殊关系 1 设 A a b c 的幂集 A a b c a b b c a c a b c 上的 是偏序关 系 则 1 B a b b c b c 2 B a c 求 8 种特殊关系 解 1 不 y B y y 故无罪最大元 最小元是 极大元为 a b b c 极小元为 上界和上确界均 a b c 下界下确界均为 2 无最大最小元 极大元和极小元均为 a c 上界为 a c a b c 上确界为 a c 下界和下确界均为 2 集合 A 2 3 6 12 24 36 其中 为 A 上的整除关系 R QQ374289236 1 画出一般的关系图和哈斯图 2 设 B1 6 12 B2 2 3 B3 24 36 B4 2 3 6 12 为 A 的 子集试求出 B1 B2 B3 B4 8 种元素 3 A a b c d e f g h 对应的哈斯图如下 令 B1 a b B2 c d e 求 B1 B2 8 种元素 解 B1B2 最大元无无 最小元无c 极大元a bd e 极小元a bc 上界c d e f g hh 下界无a b c 上确界ch 下确界无c 最大元最小 元 极大 元 极小 元 上界下界上确界下确界 B1 12612612 24 362 3 6126 B2 无无2 32 36 12 24 36无6无 B3 无无24 3624 36无2 3 6 12无12 B412无122 312 24 36无12无 代数系统 1 代数系统 单位元 逆元素 零元素 1 在实数集 R 上定义二元关系 如下 x y x y xy x y 1 2 x y 1 x y 是否满足结合律 交换率 是否有单位元及逆元 2 x y 是否满足结合律 交换率 是否有单位元及逆元 解 因为 1 x y z x y xy z x y xy z xz yz xyz x y z x y z yz x y xy z xz yz xyz 满足结合率 x y x y xy y x y x xy 满足交换率 x 0 x 0 x 0 0 x 0 x x 所以单位元是 0 x x 1 x x 1 x x 1 0 所以 x 1 x 1 x x 1 所以对于 R 1 的所有 x 均有逆元素 x 1 x 2 因为 x y z 1 2 x y z 1 2 1 2 x y z 1 4 x 1 4 y 1 2 z x y z x 1 2 y z 1 4 y 1 4 z 1 2 x 所以不满足结合律 又因为 x y 1 2 x y y x 1 2 x y 所以满足交换率 不存在单位元素和逆元素 2 在代数系统中的单位元是 0 3 设 A 是非空集合 中 A 对运算 的单位元是 A 对运算 的单 位元是 2 找子群 证明交换群 1 试证阶为偶数的循环群中周期为 2 的元素个数一定是奇数 证明 设 G 是阶为 n 的循环群 即 G n n 是偶数 任取 a G an e m 2 a 的阶为 m a 的逆元素 a 1 G 故 a 1 m a m 1 e 1 e 由群的性质 知 a 1 的阶 QQ374289236 也是 m 则必定有 a a 1 反证法 若 a a 1 则 a2 e 所以 a 的阶不大于 2 这与 m 2 矛盾 所以 a a 1 即当 a 的阶数大于 2 时 a 与它的逆元素总是成对出现的 又因为群中唯一的单位元素 e 的阶为 1 此时阶大于 2 的元素个数是偶数 加上单位元 e 个数为奇数了 剩下的那些阶为 2 的元素个数必须是奇数 才能满足所给条件 n 是偶数 得证 2 找出 Z12 12 的所有子群 解 1 1 阶子群 0 12 2 2 阶子群 0 6 12 3 3 阶子群 0 4 8 12 4 4 阶子群 0 3 6 9 12 5 6 阶子群 0 2 4 6 8 10 12 6 12 阶子群 Z1 2 1 2 3 设群中每个元素的逆元素是其自身的 则 G 是一个交换群 证明 对于任意的 a b G 由 a b G 因为一个元素的逆元素就是其自己 于是 a b a b 1 b 1 a 1 b a 所以 G 是交换群 3 计算置换 设 M 1 2 3 与 是 M 的置换 1 2 3 1 2 3 2 3 1 3 2 1 求 1 1 1 1 2 3 1 2 3 1 2 3 1 2 3 3 1 2 2 3 1 3 2 1 2 1 3 1 2 3 1 2 3 1 2 3 3 2 1 2 3 1 1 3 2 1 1 2 3 3 2 1 4 证明两代数系统同构 1 证明和同构 证 设 g R R g x ln x 显然 g x ln x 为一一对应的函数 ln x1 x2 ln x1 ln x2 得 g x1 x2 g x1 g x2 x1 x2 x 所以证明和同构 2 证明两个代数系统之间的同构关系就是等价关系 证 设 和为任意的三个代数系统 首先 所以满足自反性 其次 如果 即存在 g X Y 使得 x1 x2 X 有 g x1 x2 g x1 g x2 由 g 为一一对应的函数 所以存在 g 1 Y X y1 y2 Y1 g 1 y1 x1 g 1 y2 x2 x1 x2 g 1 y1 g 1 y2 x1 x2 g 1 g x1 x2 g 1 g x1 g x2 g 1 y1 y2 所以 g 1 y1 y2 g 1 y1 g 1 y2 最后 如果 只需要证 即存在 g X Y 使得 x1 x2 X 均有 g x1 x2 g x1 g x2 存在 h Y Z 使得 y1 y2 Y 均有 h y1 y2 h y1 h y2 建立一个一一对应的函数 f h g X Z QQ374289236 x1 x2 X f x1 x2 h g x1 x2 h g x1 g x2 h g x1 h g x2 f x1 f x2 综上所述同构关系就是等价关系 3 任何一个群与一个变换群同构 证明 设群为 a G 可定义变换 a x x a 做集合 G 下面证明 即找出 G 使得 a G 有 a b a b a b a b 说明是映射 a G a G 使得 a x x a 说明是漫射 a G 且 a b x a x b x G 一一映射下的函数就是一一对应函数 a b a b x a b x a b b a x a b x a b 所以是同构 这里额外说明一下 设 f A B g B C f g A C f g x g f x 4 设 G 为群 若 x G 又 x2 e 证 G 为交换群 证明 由 x G 有 x2 e 所以 x x 1 存在逆元素 xy y 1x 1 e 得 x x 1 e 满足结合律 x y G xy xy 1 y 1x 1 yx 满足交换律 5 若为可交换半群 则 a b G 必有 a b n an bn 证明 a b 2 a2 b2 a b G a b 2 a b a b a b a b a a b b a a b b a2 b2 根据数学归纳法得出 a b n an bn 6 设 为群 H K 为 G 的子群 证 H K 也为 G 的子群 1 首先证明 G 是非空的 由于 H K 均为 G 的子集 e H K 所以 H K 非空 2 a b H K a H a K b H b K 又因为 H 为 G 的子群 则 a b 1 H 且在 H 中有唯一解 同理得 a b 1 K 根据群的第二定义 综上所述 得出 H K 为 G 的子群 证 H K 也为 G 的子群 图论 1 数量积 基本通路 n m 图 基本通路的长度 n 1 通路 基本回路 n m 图 基本回路的长度 n n m 的完全图 Kn m 和 n 的关系 2 生成子图 则 V V 且 E E 子图 则 V V 且 E E V E 是 V E 真子图 则 V V 且 E E 3 应用 欧拉图 欧拉通路 1 邮递员从邮局 v1出发沿由路投递信件 其邮路图所示 试问是否 存在一条投递路线使邮递员从邮局出发通过所有路线而不重复且最 后回到邮局 解 由于图中每个结点的次数均为偶次数 由定理知这样的路线一定 是存在的 QQ374289236 C v1 v 5 v 11 v 7 v 12 v 8 v 10 v 6 v 9 v 11 v 12 v 10 v 9 v 5 v 2 v 6 v 4 v 8 v 3 v 7 v 1 2 晒水车从 A 点出发执行晒水任务 城市街道图形如图所示 试问 是否存在一条晒水路线 是晒水车从 A 点出发通过所有街道且不 重复最后回到车库 B15 解 问题的变形是问 AB 之间是否存在欧拉通路 由于图中每个结点 除 了 A B 为奇数外其余均为偶次数 由定理可知这样一条晒水路线使存在的 P A C D E F B G C F G A B 命题逻辑 1 判断何为命题 2 判断命题真假 公式 真值表 逻辑演算 3 命题符号化 4 公式的真值指派 1 下列命题公式 P Q P 记做 G 使 G 的真值指派为 F 的 P Q 的真值是 T F 2 设命题公式 G P Q R 则使 G 得真值指派为 T 的是 TTT TFT TTF 3 p q r p q r p p q r p q r 0 0 01011 0 0 11001 0 1 01111 1 0 01100 1 0 10011 1 1 00001 1 1 00011 1 1 10001 4 1 p p q q 均为成真赋值 2 p q q r 均为成假赋值 5 化简公式 化简下列公式 1 P Q P Q 2 Q P P Q 解 1 P Q P Q 2 Q P P Q Q P Q P Q P P Q Q P Q P 1 P P 6 求主范式 1 命题公式 P Q P 记做 G 使 G 的真值指派为 F 的 P Q 的真值是 QQ374289236 T F 2 设命题公式 G P Q R 则使 G 得真值指派为 T 的是 TTT TFT TFF 3 p q r p q r p p q r p q r 0 0 01011 0 0 11001 0 1 01111 1 0 01100 1 0 10011 1 1 00001 1 1 00011 1 1 10001 4 1 p p q q 均为永真式 2 p q q r 均为永假式 21 p q r 法一 p q r p q r r p q p q r r p q p q r r p q p r q r p q r 含有三个简单析取式的合取范式 式子 p q r p q p p q q r r r p r q p q r p r q r 含有三个简单合取式的析取范式 式子 根据式子 先求主析取范式 p q r p r q r p q r p q q r r p p q p q r p q r p q r r p q r p q p q r p q r p q r r p q 1 0 0 m4 0 1 1 m3 0 0 1 m1 1 1 1 m7 根据式子 先求合取取范式 p r q r p q r p q q r q p p r p q r p q r p q r q p r q p r p q r p q r p q r q p r p q r 0 0 0 M0 0 1 0 M2 1 1 0 M6 1 0 1 M5 法二 真值表 p q r p q r 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 主析取范式 m4 m3 m1 m7 主合取范式 M0 M2 M6 M5 7 在自然推理中的证明 QQ374289236 1 在自然推理中构造下列证明 前提 p q r q r s 结论 p s 证明 p q 前提引入 p q 置换 r q 前提引入 q r 置换 r s 前提引入 q s 假言三段论 p s 假言三段论 2 在自然推理系统中构造下面的证明 若 a 为实数 则它不是有理数就是无理数 若 a 不是能表示成分数 则它不是有理数 a 是实数且他不能表示成分数 则他不是无理数 解 设 p a 为实数 q a 为有理数 r a 为无理数 s a 能表示成分数 前提 p q r s q p s 结论 r 证明 p s 前提引入 p 化简 s 化简 p q r 前提引入 q r 假言推理 s q 前提引入 q 假言推理 r 析取三段论 3 如果 小王是理科生 则他的数学成绩一定很好 如果小王不是文科生 他一定是理 科生 小王的数学不好 所以他是文科生 解 p 小王是理科生 q 他的数学成绩很好 r 小王是文科生 前提 p q r p q 结论 r 证明 p q 前提引入 q 前提引入 p 拒取 r p 前提引入 r 拒取式 4 如果今天是星期天 我们就要到颐和园或圆明园去玩 如果颐和园人游人太多 我们 就不去颐和园玩 今天星期天 颐和园有人太多 所以我们去圆明园玩 解 设 p 今天是星期天 q 到颐和园玩 r 到圆明园玩 s 颐和园人太多 前提 p q r s q p s 结论 r 证明 s q 前提引入 s 前提引入 q 假言推理 p q r 前提引入 p 前提引入 q r 假言推理 r 析取三段论 离散数学离散数学 试题及答案试题及答案 一 选择题 本题共一 选择题 本题共 5 5 小题 每小题小题 每小题 3 3 分 共分 共 1515 分 在每小题给出的四个选项中 只有一分 在每小题给出的四个选项中 只有一 项是符合题目要求的 项是符合题目要求的 1 命题公式为 QQP A 矛盾式 B 可满足式 C 重言式 D 合取范式 2 设 P 表示 天下大雨 Q 表示 他在室内运动 则命题 除非天下大雨 否则他不 QQ374289236 在室内运动 符号化为 A B C D PQ PQ PQ PQ 3 设集合 A 1 2 3 4 5 6 7 8 则下式为真的是 A 1 A B 1 2 3 A C 4 5 A D A 4 设 A 1 2 B a b c C c d 则 A B C A B C D 5 设 G 如右图 那么 G 不是 A 哈密顿图 B 完全图 C 欧拉图 D 平面图 二 填空题 本大题共 5 小题 每小题 4 分 共 20 分 把答案填在对应题 号后的横线上 6 设集合 A a 则 A 的幂集 P A 7 设集合 A 1 2 3 4 B 6 8 12 A 到 B 的关系 R 2 ByAxxyyx 那么 R 1 8 在 同学 老乡 亲戚 朋友 四个关系中 是等价关系 9 写出一个不含 的逻辑联结词的完备集 10 设 X a b c R 是 X 上的二元关系 其关系矩阵为 MR 那么 R 的关系图为 001 001 101 三三 证证明明题题 共共3 30 0 分分 11 10 分 已知 A B C 是三个集合 证明 A B C A B A C 12 10 分 构造证明 P Q S R P Q R S 13 10 分 证明与 与等势 0 1 0 1 0 1 0 1 四 解答题四 解答题 共共 35 分分 14 7 分 构造三阶幻方 以 1 为首项的 9 个连续自然数正好布满一个方阵 且方阵3 3 中的每一行 每一列及主 副对角线上的各数之和都相等 15 8 分 求命题公式的真值表 QPQP 16 10 分 设 R1是 A1 1 2 到 A2 a b c 的二元关系 R2是 A2到 A3 的二元关 系 R1 R2 求 R1 R2的集合表达式 17 10 分 某项工作需要派 A B C 和 D 4 个人中的 2 个人去完成 按下面 3 个条件 QQ374289236 有几种派法 如何派 三个条件 1 若 A 去 则 C 和 D 中要去 1 个人 2 B 和 C 不能都去 3 若 C 去 则 D 留下 一 单项选择题一 单项选择题 每小题每小题 3 分 共分 共 15 分分 1 B 2 C 3 C 4 A 5 B 二 填空题二 填空题 每小题每小题 4 分 共分 共 20