离散数学第3章答案

习题习题 3 1 1 1 0 1 2 3 4 5 6 7 8 9 2 aa ab ba bb 3 1 1 4 11 13 17 19 23 29 5 1 2 3 79 6 2 2 用描述法表示下列集合 1 不超过 200 的自然数的集合 N200 x xx 2 被 5 除余 1 的正整数的集合 I N51 x xy yxy 3 函数 y sinx 的值域 R11 y yy 4 72 的质因子的集合 N 72 N2 x xxy yyxyx 5 不等式0 3 1 x 的解集 R3 x xx 6 函数 23 1 2 xx y的定义域集 R12 x xxx 3 用归纳定义法描述下列集合 1 允许有前 0 的十进制无符号整数的集合 0 1 2 3 4 5 6 7 8 9 A 如果xA 则 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 x xxxxxxxxx xx xxxxxxxxA 2 不允许有前 0 的十进制无符号整数的集合 1 2 3 4 5 6 7 8 9 A 如果xA 则 0 1 2 3 4 5 6 7 8 9 xx xxxxxxxxA 3 不允许有前 0 的二进制无符号偶数的集合 1A 如果xA 则 0 1 xxA 4 5 的正整数倍的集合 5A 如果xA 则5xA 4 判断下列命题中 哪些是真的 哪些是假的 A 是任意集合 1 2 3 A A AA 4 5 6 AA AA AA 7 答 2 3 4 为真 1 5 6 7 为假 5 判断下列命题中哪些为真 1 2 3 4 5 6 7 8 9 10 a ba b ab a ba b ab 11 12 13 14 答 1 2 4 6 10 11 12 14 为真 3 5 7 8 9 13 为假 6 设 A 和 B 是集合 AB 和AB 能同时成立吗 为什么 答 能 当时 BAA AB 和AB 同时成立 7 设 A 和 B 是集合 AB 和BA 能同时成立吗 为什么 答 不能 若AB 和BA 同时成立 则我们能得到BB 而这是不可能的 8 设 A B 和 C 是集合 若AB 且BC 则AC 可能成立吗 AC 是否总能成 立 为什么 答 AC 可能成立 比如当 BA CA B 时 AB BC 和AC 同时成立 但结论不是总成立 比如 BA CB 时 AB 且BC 但AC 不成立 9 设 A B 和 C 是任意集合 证明或否定下列断言 1 若AB 且BC 则AC 结论成立 因为xAxBxC 所以AC 2 若AB 且BC 则AC 结论不成立 例如当时 有 AaBa b Ca b c AB 且BC 但AC 3 若BA 且CB 则s CA 命题为假 设 易知 BA CB BA 且CB 但CA 4 若BA 且BC 则 CA 结论成立 题目有误 应改为 若BA 且BC 则CA BA BC BA x x A x x x A 0 x x A A 10 设 A B 和 C 是任意集合 证明或否定下列断言 1 若AB 且BC 则AC 答 此断言不正确 例如当 A a B a b C a c 时 有AB 和BC 但AC 2 若AB 且BC 则AC 答 此断言不正确 例如当 A a B a b C a c 时 有AB 和BC 但AC 3 若AB 且BC 则AC 答 此断言不正确 例如当 A a B a b C a c 时 有AB 和BC 但AC 4 若AB 且BC 则AC 答 此断言不正确 例如当 A a B a b C a c 时 有AB 和BC 但AC 11 证明 当且仅当 A A 证 必要性 因为和同时成立A A 所以A 充分性 因为空集是任何集合的子集 而A 所以 A 12 确定下列哪些集合是相等的 A1 a b A2 b a A3 a a b A4 a b c A5 x x a x b x c 0 A6 a b d A7 x x2 a b x ab 0 答 A1 A2 A3 A7相等 A4与 A5相等 13 设 n 个集合 A1 A2 An满足关系 12 n1 AAA A 证明 A1 A2 An 证 对任意的从条件我们得到2in 1i AA 和 1i AA 所以我们有 1i AA 因此 A1 A2 An 习题习题 3 2 1 设全集 U a b c d e A a d B a b c C b d 求下列各集合 1 ABC 2 ABC 3 ABC 4 AB 5 6 ABBC ABC 7 ABC 解 1 ABCa 2 ABCU 3 ABCb d 4 ABda d 5 ABBCa c d 6 ABCb d 7 ABCa d e 2 设 A B 和 C 是集合 试把ABC 表示成各不相交的集合之并 解 ABCABACAB 3 设 A B 和 C 是集合 1 若ABAC 则一定有 吗 答 不一定 例如当 时 和 可以是任意集合 2 若ABAC 则一定有 吗 答 不一定 例如当时 和 可以是任意集合 A 3 若ABAC 则一定有 吗 答 一定 证明如下 若 则A AB 和 从而 AC 若和A B 则ABAC 等 价 于AACAC 若xA 则 xAC 因为xA 所以xC 说明AC 并且AAC 从而 C 若并且A B 条件ABAC 等价于ABABACAC 则 xBxBxAxBxA xAxABABxA xABAB xAxACACxAxACAC xACxACxAxAC xC 从而BC 同理可证CB 因此 BC 4 设 试计算 a bb ca c 1 2 3 4 解 1 a b c 2 3 a b ca b c 4 5 求下列集合的幂集 1 解 2 a b c 解 a b cabca ba cb ca b c 3 cba 解 cbacbacba 4 解 5 a b b 解 a b baba b 6 判断下列哪些运算结果是对的 那些是错的 1 2 3 4 5 6 答 1 3 和 6 是对的 2 4 和 5 是错的 习题习题 3 3 1 证明下列各式 1 ABA 证 ABAABAAAB 2 ABAAB 证 ABAABAABAAABUA B 3 ABCABAC 证 ABCABCABCABACABAC 4 ABCABAC 证 ABCABCABCABACABAC 5 ABCABC 证 ABCABCABCABC 2 证明下列条件是相互等价的 1 AB 2 ABU 3 AB 证 若 1 成立 即AB 则有AB ABBBU 则ABU 得 2 若 2 成立 即ABU 则AB 即AB 得 3 若 3 成立 即AB 则 从而AB AB 得 1 因此 1 2 和 3 是相互等价的 3 证明 当且仅当 ABBABB B 证 必要性 若 ABBABB 由于 ABBABBABBBAB ABBABBABAB 则有ABAB 假设 则至少有 一个 显然 B aB aAB 和 这与aAB ABAB BA 矛盾 因此 B 充 分 性 当时 有B AB 和 ABBA 所 以 AB AB ABB CAB B 证毕 4 化简下列各式 1 B CA CABC 解 ABCABCAC BCAB 原式 ABAB A 2 ABCABABC A 解 A BAABAAA 原式ABAB 3 ABCABCABC 解 A CABCAABCAAC 原式 AB ABC 5 给出下列公式成立的充分必要条件 并加以证明 1 ABA CA 证 由于 ABACABACABC 因此 的充分必要条件是 ABA CA ABC 2 ABAC 证 由于 ABACABACABC 所以 等 价 于 ABAC ABC 等 价 于 ABC U 等 价 于 ABC AB 即 A C 的充分必要条件是ABC 3 ABA CA 证 等价于 ABA CA ABACA 等价于ABCA 所以 的充分必要条件是 ABA CA ABC 4 ABAC 证 等 价 于 ABA C ABC 等 价 于ABCU 所 以 的充分必要条件是 ABAC ABC 5 ACABA 证 由于 CBACABACABA 所以使上式成立的充分必要条件是CBA 充分性 若CBA 则ACBA 即ACABA 必要性 若ACABA 即ACBA 则 CBxCBAxAx 从而CBA 6 ABAC 证 由于 CBACABACABA 所以使 的充分必要条件是 ABA C ABC 7 ABAB 证 使ABAB 的充分必要条件是AB 必要性 假设AB 不妨设有一个元素 aAaB 但 则 aABaAB 但与 ABA B 矛盾 充分性 当AB 时 显然有ABAB 8 ABB 证 ABB 的充分必要条件是 A 和 B 均为空集 充分性显然成立 必要性 反证 若 A 不是空集 则有一个元素aA 若aB 则 这与aAB ABB 矛盾 若 则 也与aB aAB ABB 矛盾 故 A 必须是空集 若B不是空集 则有一个元素b 由B ABB 知bA 则bAB 这与ABB 矛盾 故 B 必须是空集 9 ABBA 证 ABBA 的充分必要条件是 A B 充分性显然 必要性 反证 假设AB 不妨设有 aAaB 但 则 aABaBA 但 这与 ABBA 矛盾 10 ABA 证 ABA 的充分必要条件是B 充分性显然 必要性 反证 假设 B 不是空集 则有bB 若bA 则bAB 与ABA 矛盾 若b 则 与A bAB AB A矛盾 所以 B 必须是空集 6 证明下列各式 1 AABAB 证 AABAAABUABAB 2 AABAB 证 AABAAABABAB 10 习题习题 3 4 1 对 100 名学生阅读 3 种杂志的情况进行调查 结果发现 60 人阅读甲类杂志 50 人阅读乙 类杂志 50人阅读丙类杂志 阅读其中两种杂志的人数均为30 三种杂志都阅读的人数为10 试求 1 阅读并且只阅读两种杂志的人数 2 不阅读任何杂志的人数 解 设 A 表示阅读甲类杂志的学生集合 B 表示阅读乙类杂志的学生集合 C 表示阅读丙类杂 志的学生集合 则 A 60 B 50 C 50 30 ABACBCABC 1 ABACBCABACBC ABACABBCAC BCABACBC 30 30 30 30 10 70 阅读并且只阅读两种杂志的人数是 70 10 60 2 ABCABCABACBCABC 60 50 50 30 30 30 10 80 所以不阅读任何杂志的人数是 100 80 20 2 某班学生 80 人 有 30 人参加日语考试 42 人参加法语考试 25 人两门考试均没参加 问 有多少学生参加了两门考试 解 设 A x x 参加日语考试 B x x 参加法语考试 A 30 B 42 25 BA 17 2580 4230 BABABA 有 17 人参加了两门考试 3 试求 1 到 200 之间能被 2 3 5 或 7 整除的整数个数 解 设 1200 Sx xIx 12 2 3 Ax xS xAx xS x 是 的倍数是 的倍数 34 5 7 Ax xS xAx xS x 是 的倍数是 的倍数 则我们要求 4321 AAAA 根据容斥原理我们知道 12341234 121314232434 1231241342341234 AAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAAAAAA 容易得到 A1 99 A2 66 A3 39 A4 28 A1 A2 33 A1 A3 19 A1 A4 14 A2 A3 13 A2 A4 9 A3 A4 5 A1 A2 A3 6 A1 A2 A4 4 A1 A3 A4 2 A2 A3 A4 1 A1 A2 A3 A4 0 则 A1 A2 A3 A4 99 66 39 28 33 19 14 13 9 5 6 4 2 1 153 所以 1 到 200 之间能被 2 3 5 或 7 整除的整数有 153 个 4 设 A 学日语的学生 B 学法语的学生 C 学英语的学生 则 A 32 B 20 C 45 A B 7 A C 15 B C 10 A B C 30 U 100 1 所求学生人数 A B C A B C A B C A B A C B C 51015745203230100 CBCABACBACBAU 2 只学日语的学生人数 15515732 CBACABAA CABAACBAACBA 类似可得只学法语的学生人数 CBA 8 只学英语的学生人数 CBA 25 3 所求学生人数 CBACBACBACBA 70 15 8 25 22 或者 CBACBACBACBA 7 5 15 5 10 5 5 22 习题习题 3 5 1 1 2 a b 3 4 2 该命题不一定成立 如 A a b B C a A A B C A B A C 4 B x a A A B A Cx C B C 同理 C B 故 B C 5 不一定有 BC 若 A 则 A B A C 但不一定有 B C 若 A 则 BC 证明同习题 4 6 A A A A A B B B B B 故 A B A A A A B B x x BAB 同理 BA 故 A B 7 若 A 则显然成立 若 A 当 B 时 显然成立 当 B 时 BA x A y B C x y A C A B AC 8 1 原式不成立 如A a B b C c D d A B C