离散数学一三四作业答案

1 离散数学形成性考核作业离散数学形成性考核作业参考答案参考答案 作业一作业一 第 1 章 集合及其运算 1 用列举法表示 大于 2 而小于等于 9 的整数 集合 3 4 5 6 7 8 9 2 用描述法表示 小于 5 的非负整数集合 集合 x x Z 0 x 5 3 写出集合 B 1 2 3 的全部子集 1 2 3 1 2 3 4 求集合 A 的幂集 5 设集合 A a a 命题 a P A 是否正确 说明理由 错误 错误 P A P A 中无元素中无元素 a a 6 设求ABC 12 31352 4 6 1 2 AB ABC 3 C A 4 AB 1 3 2 1 2 3 4 5 6 3 4 6 4 2 5 7 化简集合表示式 AB B AB A B B A B B A B B A B B 8 设 A B C 是三个任意集合 试证 A BC A B C A B C B C A A B C B C A A B B C C A B B C C 9 填写集合 4 9 9 10 4 之间的关系 10 设集合 A 2 a 3 4 那么下列命题中错误的是 A A a A B a 4 3 A C a A D A 11 设 B a 3 4 2 那么下列命题中错误的是 B A a B B 2 a 3 4 B C a B D B 第 2 章 关系与函数 1 设集合 A a b B 1 2 3 C 3 4 求 A BC AB AC 并验证 A BC AB AC A B C a b 3 3 A B A C 验证了验证了 A B C A B A C 2 对任意三个集合 A B 和 C 若 ABAC 是否一定有 BC 为什么 当当 A 是空集时 不一定有是空集时 不一定有 BC 当当 A 不是空集时 一定有不是空集时 一定有 BC 2 x A A y B A B A B A C A C y C C 即 即 BC 3 对任意三个集合 A B 和 C 试证 若 AB AC 且 A 则 B C x A A y B A B A B A C A C y C C 即 即 BC 同理 CB B C 4 写出从集合 A a b c 到集合 B 1 的所有二元关系 5 设集合 A 1 2 3 4 5 6 R 是 A 上的二元关系 R a b a bA 且 a b 6 写出 R 的集合表示式 6 设 R 从集合 A a b c d 到 B 1 2 3 的二元关系 写出关系 R a 1 a 3 b 2 c 2 c 3 的关系矩阵 并画出关系图 MR 000 110 010 101 7 设集合 A a b c d A 上的二元关系 R a b b d c c c d S a c b d d b d d 求 RS RS R S RS RS R S R S R S R S RS 8 设集合 A 1 2 B a b c C R 是从 A 到 B 的二元关系 S 是从 B 到 C 的二元关系 且 R S 用关系矩阵求出复合关系 R S M R S MR MS 00 10 00 10 10 100 011 R S 9 设集合 A 1 2 3 4 上的二元关系 R 1 1 1 3 2 2 3 1 3 3 3 4 4 3 4 4 判断 R 具有哪几种性质 自反性 对称性 传递性 自反性 对称性 传递性 10 设集合 A a b c d 上的二元关系 R a a a b b b c d 求 r R s R t R 3 r R a a a b b b c c c d d d s R a a a b b a b b c d d c t R a a a b b b c d 11 设集合 A a b c d R S 是 A 上的二元关系 且 R S 试画出 R 和 S 的关系图 并判断它们是否为等价关系 若是等价关系 则求出 A 中各元素 的等价类及商集 R 是等价关系 是等价关系 A R a c S 不是等价关系 不是等价关系 12 图 1 1 所示两个偏序集A R 的哈斯图 试分别写出集合 A 和偏序关系 R 的集 合表达式 A a b c d e f g R IA S IA 13 画出各偏序集A 1 的哈斯图 并指出集合 A 的最大元 最小元 极大元和 极小元 其中 A a b c d e 1 a b a c a d a e b e c e d e IA 集合集合 A 的最大元的最大元 e 最小元 最小元 a 极大元 极大元 e 和极小元和极小元 a 14 下列函数中 哪些是满射的 那些是单射的 那些是双射的 1 f1 R R f a a3 1 2 f4 N 0 1 f a 为偶数 为奇数 a a 1 0 1 双射 双射 2 满射 满射 15 设集合 A 1 2 B a b c 则 B A 16 设集合 A 1 2 3 4 A 上的二元关系 R 1 2 1 4 2 4 3 3 S 1 4 2 3 2 4 3 2 则关系 B 1 4 2 4 A RS B RS C R S D S R 17 设集合 A 1 2 3 4 上的二元关系 R 1 1 2 3 2 4 3 4 则 R 具有 A 自反性 B 传递性 C 对称性 D 反自反性 18 设集合 A a b c d e 上的偏序关系的哈斯 d b a e c f g 1 b g dc e f a 2 图 1 1 题 12 哈斯图 b c a e d 图 1 2 题 18 哈斯图 4 图如图 1 2 所示 则 A 的极大元为 a 极小元为 c d 19 设 R 为实数集 函数 f RR f a a2 2a 1 则 f 是 D A 单射而非满射 B 满射而非单射 C 双射 D 既不是单射也不是满射 作业 3 一 单项选择题一 单项选择题 1 若集合 A 2 a a 4 则下列表述正确的是 A a a A B a A C 2 A D A 正确答案 B 2 若集合 A a b 1 2 B 1 2 则 A B A 且 B A B B A 但 B A C B A 但 B A D B A 且 B A 正确答案 B 3 设集合 A 1 a 则 P A A 1 a B 1 a C 1 a 1 a D 1 a 1 a 正确答案 C 注意注意 若 A 是 n 元集 则幂集 P A 有 2 n个元素 4 设集合 A 1 2 3 4 5 6 上的二元关系 R a b a bA 且 a b 8 则 R 具有的性质为 A 自反的 B 对称的 C 对称和传递的 D 反自反和传递的 正确答案 B 因为写出二元关系 R 的集合表达式为 R 2 6 6 2 3 5 5 3 4 4 显然 R 是对称的 不是自反的 反自反的 传递的 要求大家能熟练地写出二元关系 R 的集合表达式 5 设集合 A 1 2 3 4 上的二元关系 R 1 1 2 2 2 3 4 4 S 1 1 2 2 2 3 3 2 4 4 则 S 是 R 的 闭包 A 自反 B 传递 C 对称 D 以上都不对 正确答案 C 想一想 R 的自反闭包是什么 如果集合 A 1 2 3 A 上的二元关系 R x A y A x y 8 那么 R 的自反 闭包是什么 请写出 6 设集合 A 1 2 3 4 5 上的偏序关系 2 4 1 3 5 5 的哈斯图如右图所示 若 A 的子集 B 3 4 5 则元素 3 为 B 的 A 下界 B 最大下界 C 最小上界 D 以上答案都不对 正确答案 C 二 填空题二 填空题 1 设集合 A 有 n 个元素 那么 A 的幂集合 P A 的元素个数为 应该填写 2n 如果 n 5 n 8 那么 A 的幂集合 P A 的元素个数分别是多少 2 设集合 A 1 2 3 4 5 B 1 2 3 R 从 A 到 B 的二元关系 R a b aA bB 且 2a b4 则 R 的集合表示式为 应该填写 R 1 1 1 2 1 3 2 1 2 2 3 1 3 设集合 A 0 1 2 B 0 2 4 R 是 A 到 B 的二元关系 BAyxByAxyxR 且且 则 R 的关系矩阵 MR 应该填写 011 000 011 因为 R 由此可以写出 R 的关系矩阵 4 设集合 A a b c A 上的二元关系 R S 则 R S 1 应该填写 因为 R S 所以 R S 1 5 设集合 A a b c d A 上的二元关系 R 则二元关 系 R 具有的性质是 应该填写 反自反的 6 设集合 A 1 2 B a b 那么集合 A 到 B 的双射函数是 应该填写 想一想 集合 A 到 B 的不同函数的个数有几个 三 判断说明题三 判断说明题 判断下列各题 并说明理由 1 设 A B C 为任意的三个集合 如果 A B A C 判断结论 B C 是否成立 并 6 说明理由 解 解 结论不成立 设 A 1 2 B 1 C 2 则 A B A C 但 B C 2 如果 R1和 R2是 A 上的自反关系 判断结论 R 11 R1 R2 R1 R2是自反的 是否成立 并说明理由 解 结论成立 因为 R1和 R2是 A 上的自反关系 即 IA R1 IA R2 由逆关系定义和 IA R1 得 IA R1 1 由 IA R1 IA R2 得 IA R1 R2 IA R1 R2 所以 R1 1 R1 R2 R1 R2是自反的 3 判断 若偏序集 A R 的哈斯图如右图所示 则集合 A 的极大元为 a f 最大元不存在 是否正确 并说明理由 解 正确 按照极大元定义 若对任意 aB 且 ba 都有 a b 则称 b 为 B 的极大元极大元 可知 a f 是 A 的极大元 且最大元不存在 想一想想一想 若偏序集 A R 的哈斯图如右图所示 则集合 A 的最大元为 a 最小元不存在 是否正确 再给出一个判断说明题 大家要重视的 想一想想一想 设 N R 分别为自然数集与实数集 f N R f x x 6 则 f 是单射 是否成 立 并说明理由 四 计算题四 计算题 1 设集合 A a b c B b d e 求 1 B A 2 A B 3 A B 4 B A 解 1 B A a b c b d e b 2 A B a b c b d e a b c d e 3 A B a b c b d e a c 4 B A A B B A a b c d e b a c d e 2 设集合 A 1 2 3 4 5 6 7 8 9 10 11 12 R 是 A 上的整除关系 B 2 4 6 1 写出关系 R 的表示式 2 画出关系 R 的哈斯图 3 求出集合 B 的最大元 最小元 解 1 R IA 2 a c b edf 1 2 3 46 9 5 7 8 10 11 12 关系 R 的哈斯图 7 3 集合 B 没有最大元 最小元是 2 3 设集合 A a b c d 上的二元关系 R 的 关系图如右图所示 1 写出 R 的表达式 2 写出 R 的关系矩阵 3 求出 R2 解 解 1 R 2 1000 0000 0100 0101 R M 3 R2 五 证明题五 证明题 1 试证明集合等式 A B C A B A C 证 若 x A B C 则 x A 或 x B C 即 x A 或 x B 且 x A 或 x C 即 x A B 且 x A C 即 x A B A C 所以 A B C A B A C 反之 若 x A B A C 则 x A B 且 x A C 即 x A 或 x B 且 x A 或 x C 即 x A 或 x B C 即 x A B C 所以 A B A C A B C 因此 A B C A B A C 想一想 等式 A B C A B A C 如何证明 2 设 R 是集合 A 上的对称关系和传递关系 试证明 若对任意 a A 存在 b A 使 得 R 则 R 是等价关系 证明证明 已知 R 是对称关系和传递关系 只需证明 R 是自反关系 任意 a A 存在 b A 使得 R 因为 R 是对称的 故 R a d b c 8 又 R 是传递的 即当 R R 可以得到 R 由元素 a 的任意性 知 R 是自反的 所以 R 是等价关系 3 若非空集合 A 上的二元关系 R 和 S 是偏序关系 试证明 R S 也是 A 上的偏序关 系 证明证明 任意 x A R S R S 所以 R S 有自反性 对任意 x y A 因为 R S 是反对称的 由 R S 且 R S R 且 S 且 R 且 S R 且 R 且 S 且 S x y 且 y x 即 x y 所以 R S 有反对称性 对任意 x y z A 因为 R S 是传递的 由 R S 且 R S R 且 S 且 R 且 S R 且 R 且 S 且 S R 且 S R S 所以 R S 有传递性 总之 R S 是偏序关系 4 5 6 题无答案 作业 4 第 6 章 命题逻辑 1 判断下列语句是否为命题 若是命题请指出是简单命题还是复合命题 1 8 能被 4 整除 2 今天温度高吗 O2 d8 r 6 o4 E2 O 3 今天天气真好呀 4 6 是整数当且仅当四边形有 4 条边 k k4 W E a 5 小王是学生 但小李是工人 6 d U Y J2 u1 O8 6 除非下雨 否则他不会去 解 1 是简单命题 4 5 6 是复合命题 2 翻译成命题公式 1 他不会做此事 5 h0 C e F 2 他去旅游 仅当他有时间 D X s6 o9 R J c P 3 小王或小李都会解这个题 T e b S X 5 设 P 有人去看展览 公式为 P 6 设 P 他去看电影 Q 他去观看了体育比赛 公式为 P Q 1 L f T k k Z H9 p 3 设 P Q 的真值为 1 R S 的真值为 0 求命题公式 P Q R S Q 的真值 T D p n R 解 P Q R S Q 1 1 0 0 1 p 3 V J v Y m z P 1 P Q P2 w9 s 2 z r b E G 解 P Q Q P Q Q P Q Q F l h8 7 3 S8 Q d3 0 1 2 3 4 5 6 7 6 利用求公式的范式的方法 判断下列公式是否永真或永假 7 n L1 H6 8 g3 S 7 u 2 P Q R l8 L F5 M 解 P Q R S1 R X1 S4 B8 r7 I P Q R P Q R6 v u y g1 r8 x P Q R 为析取范式 析取的两个合取式不会永真或永假 所以此公式不是永 真或永假式 对其他一些公式也可以通过求主范式进行类似地判断 9 i Q8 H i o8 b 7 设 P 昨天天晴 Q 前天下雨 则命题 昨天天晴 但前天下雨 可符号化为 A A P Q B P Q C P Q D Q P 8 可以确定下述推理的步骤 D 是正确的 A 1 P Q P 2 P T 1 I B 1 P Q P 2 Q T 1 I C 1 P Q P z y 0 p X o M q a D 1 P Q P 2 P T 1 I S V7 e 5 P v d D v5 T F4 H 6 所有人都需要不断地努力学习 争取进步 v 解 1 设 P x x 是人 Q x x 会来 2 M1 c7 X Y v m b8 y x W V 公式为 x P x Q x 2 设 P x x 是人 Q x x 能做这件事 公式为 x P x Q x t0 Z B5 S5 S m2 p d 3 设 P x x 是人 Q x x 能去 公式为 x P x Q x x P x Q x q R l A b 4 设 P x x 是人 Q x x 这样做 R x x 是事 S x y x 能做 y 事 B A z z x8 g C1 d s7 U 公式为 x P x Q x y x R y P x S x y 4 d9 t m 2 a c n 5 设 P x x 是人 Q x x 愿意做这件事 公式为 x P x Q x 6 设 P x x 是人 Q x x 需要不断地努力学习 争取进步 E2 P 2 u9 公式为 x P x Q x B0 X L4 P i3 S2 2 设谓词 A x x 是偶数 B x x 是奇数 x 的取值为 1 至 10 之间的正整数 试求 出下列谓词公式的值 1 x A x x B x 解 x A x x B x E q Q5 b2 w7 H b7 u6 l A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10 B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 B 9 B 10 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 L3 E0 h5 a z U G 1 2 x A x B x