第1页 / 共47页
第2页 / 共47页
第3页 / 共47页
第4页 / 共47页
第5页 / 共47页
第6页 / 共47页
第7页 / 共47页
第8页 / 共47页
离散数学教程(耿素云)-习题参考答案.pdf
《离散数学教程》1
习题解答2
(beta 16 .11 )3
SOLVED AND TEXIFIED
BY
肖新攀4
新版本下载、考研相关问题讨论
请到计算机科学论坛—计算机考研交流版
(http://www.ieee.org.cn/list.asp?boardid=67)
1《离散数学教程》，耿素云、屈婉玲、王捍贫，北京大学出版社，2002年6月第1版，2003年1月第2次印刷
2此“习题解答”系个人作品，仅供学习交流之用，可以自由复制、打印和传播，但不得用作商业用途。如
发现解答有错误，烦请告知作者(E-mail: xiaoxinpan@163.com)。
3版本号的整数部分表示该版本所包含答案的章数。发布日期： 2006 年 11 月 1 日。完成度(已完成题
数/总题数)：60.17%
4由衷感谢 xbz 网友完成并制作本“习题解答”第十章和第十四章的全部内容、仔细检查其它各章节并
提出众多修改意见和新的证明方法。感谢南京大学计算机系胡海星大侠长期以来给予我热情的鼓励和无私
的帮助。感谢南京大学 02 计算机系赖江山同学提出各种建议和证明思路。感谢北京大学计算机系刘田教
授给予我的帮助和鼓励。感谢 chouxiaoya、tedy、akaru、yitianxing、xuening、ourszf、ushing、pizzamx、
datoubaicai、echoqing、soup1122、lycool、hamletyj、leejunner、zliner、sunbird2002、zhaoming169、zqliu、
qiushuitian1111、tcschen、Supremgoooo、Smilingface、yangling 1985、jianzhentianxia、ouyangj0、kylinwang、
赵现刚、熊亮等网友提出大量修改意见和新的证明方法。谢谢你们！
第一章 集合
1.1
(1) f2g；
(2) f1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196g；
(3) f1, 8, 27, 64g；
(4) f0, 1, 2,¢¢¢g；
(5) f2, 3g；
(6) fa, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, A, B, C, D, E, F, G, H, I, J,
K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Zg。
1.2
(1) f(x, y) j x, y 2 R ^ x2 + y2 < 1g；
(2) fθ j 9k(k 2 Z ^ θ = π
4
(3) fx j x 2 N ^ x < 8g；
(4) f(x, y, z) j x, y, z 2 N ^ x2 + y2 = z2g；
(5) fx j x 2 R ^ x2 + 5x + 6 = 0g。
+ kπ)g；
1.3 (1), (4), (5), (6), (8), (9) 正确，其余不正确。
1.4
(1) 成立。
证明:
A 2 B ^ B C
() A 2 B ^ 8x(x 2 B ! x 2 C)
=) A 2 B ^ (A 2 B ! A 2 C)
=) A 2 C
(子集关系定义)
(x/A)
(假言推理)
2
(2) 不成立。举反例如下：令 A = fag, B = ffagg, C = ffag,fbgg，则有 A 2 B ^ B C，但
A * C。
(3) 不成立。举反例如下：令 A = fag, B = fa, bg, C = ffa, bg,fb, cgg，则有 A B ^ B 2 C，但
A /2 C。
(4) 不成立。举反例如下：令 A = fag, B = fa, bg, C = ffa, bg,fb, cgg，则有 A B ^ B 2 C，但
5
A * C。
1.5 令 A = fag, B = ffagg, C = fffaggg，则有 A 2 B ^ B 2 C，但 A /2 C。
1.6
(1) 0 元集：?
1 元集：fag,fbg,fcg
2 元集：fa, bg,fa, cg,fb, cg
3 元集：fa, b, cg
幂集：f?,fag,fbg,fcg,fa, bg,fa, cg,fb, cg,fa, b, cgg
(2) 0 元集：?
1 元集：f1g,ff2, 3gg
2 元集：f1,f2, 3gg
幂集：f?,f1g,ff2, 3gg,f1,f2, 3ggg
(3) 0 元集：?
1 元集：f?g,ff?gg
2 元集：f?,f?gg
幂集：f?,f?g,ff?gg,f?,f?ggg
(4) 0 元集：?
1 元集：ff1, 2gg
幂集：f?,ff1, 2ggg
(5) 0 元集：?
1 元集：ff?, 1gg,f1g
2 元集：ff?, 1g, 1g
幂集：f?,ff?, 1gg,f1g,ff?, 1g, 1gg
1.7
1.8
(1) f4g；
(2) f1, 3, 5g；
6
AB»(A[B)ABCA\(»B[C)ABC»A\(B\C)ABC(A\B\C)[»(A[B[C)
(3) f2, 3, 4, 5g；
(4) f2, 3, 4, 5g；
(5) f?,f4gg；
(6) ff1g,f1, 4gg。
1.9
(1) f¡7,¡6,¡5,¡4,¡3,¡2,¡1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 15, 16, 18, 21, 24, 27, 30, 32, 64g；
(2) ?；
(3) f¡7,¡6,¡5,¡4,¡3,¡2,¡1, 4, 5g；
(4) f¡7,¡6,¡5,¡4,¡3,¡2,¡1, 0, 3, 4, 5, 6, 9, 12, 15, 18, 21, 24, 27, 30g。
1.10 因为 P(A) = f?,fagg，PP(A) = f?,f?g,ffagg,f?,faggg，故 (1), (2), (4), (5) 成立，其
余不成立。
1.11
证明: 必要性：
若 A ¡ B = A，则有：
A \ B = (A ¡ B) \ B
= (A \ »B) \ B
= A \ (»B \ B)
= A \ ?
= ?
充分性：
若 A \ B = ?，则有：
A = A \ E
= A \ (B [ »B)
= (A \ B) [ (A \ »B)
= ? [ (A \ »B)
= A \ »B
= A ¡ B
综合得：A ¡ B = A , A \ B = ?。
1.12 先证一个引理：
引理 1.1 对任意集合 A 和 B，有 A ¡ B = ? , A B。
证明:
A ¡ B = ? () :9x(x 2 (A ¡ B))
() 8x:(x 2 (A ¡ B))
() 8x:(x 2 A ^ x /2 B)
() 8x:(x 2 A ^ :x 2 B)
() 8x(:x 2 A _ x 2 B)
() 8x(x 2 A ! x 2 B)
() A B
7
(A ¡ B = A)
(补交转换律)
(结合律)
(矛盾律)
(零律)
(同一律)
(排中律)
(分配律)
(A \ B = ?)
(同一律)
(补交转换律)
2
(? 定义)
(量词否定等值式)
(相对补定义)
( /2 定义)
(命题逻辑德¢摩根律)
(蕴涵等值式)
(子集关系定义)
(1) 答：(A ¡ B) [ (A ¡ C) = A 当且仅当 A \ B \ C = ? 。
证明:
(A ¡ B) [ (A ¡ C) = A () A ¡ (B \ C) = A
() A \ (B \ C) = ?
() A \ B \ C = ?
(2) 答：(A ¡ B) [ (A ¡ C) = ? 当且仅当 A (B \ C)。
证明:
(A ¡ B) [ (A ¡ C) = ? () A ¡ (B \ C) = ?
() A (B \ C)
(3) 答：(A ¡ B) \ (A ¡ C) = ? 当且仅当 A (B [ C)。
证明:
(A ¡ B) \ (A ¡ C) = ? () A ¡ (B [ C) = ?
() A (B [ C)
(4) 答：(A ¡ B) \ (A ¡ C) = A 当且仅当 A \ (B [ C) = ?。
证明:
(A ¡ B) \ (A ¡ C) = A () A ¡ (B [ C) = A
() A \ (B [ C) = ?
1.13
(1) 先证两个引理：
引理 1.2 对任意集合 A 和 B，有： A \ B A 和 A \ B B。
证明: 8x，
x 2 A \ B () x 2 A ^ x 2 B
=) x 2 A
故有，A \ B A。同理可证：A \ B B。
引理 1.3 对任意集合 A 和 B，有： A A [ B 和 B A [ B
证明: 8x，
x 2 A =) x 2 A _ x 2 B
() x 2 A [ B
故有，A A [ B。同理可证：B A [ B。
再证原题：
证明:
(A ¡ B) ¡ C = (A \ »B) \ »C
A \ »B
8
2
(德¢摩根律)
(习题 1.11 结论)
(结合律)
2
(德¢摩根律)
(引理 1.1)
2
(德¢摩根律)
(引理 1.1)
2
(德¢摩根律)
(习题 1.11 结论)
2
(集合交定义)
(命题逻辑化简律)
2
(命题逻辑附加律)
(集合并定义)
2
(补交转换律)
(引理 1.2)
(A \ »B) [ (A \ C)
= A \ (»B [ C)
= A \ »(B \ »C)
= A ¡ (B ¡ C)
(2) 答：当且仅当 A \ C = ? 时，(1) 中等号成立。
证明: 先证充分性。当 A \ C = ? 时：
(A ¡ B) ¡ C = (A \ »B) \ »C
= (A \ »C) \ »B
= (A ¡ C) \ »B
= A \ »B
= (A \ »B) [ ?
= (A \ »B) [ (A \ C)
= A \ (»B [ C)
= A \ »(B \ »C)
= A ¡ (B ¡ C)
(引理 1.3)
(分配律)
(德¢摩根律)
(补交转换律)
2
(补交转换律)
(结合律、交换律)
(补交转换律)
(习题 1.11 结论)
(同一律)
(A \ C = ?)
(分配律)
(德¢摩根律)
(补交转换律)
2
(同一律)
(排中律)
(分配律)
(前提)
(分配律)
(排中律)
(同一律)
2
再证必要性。若不然，则存在 x，使得 x 2 A ^ x 2 C。此时，无论 x 是否属于 B，均有
x /2 (A ¡ B) ¡ C 和 x 2 A ¡ (B ¡ C)。这与假设：(A ¡ B) ¡ C = A ¡ (B ¡ C) 矛盾。
1.14
证明:
B = E \ B
= (A [ »A) \ B
= (A \ B) [ (»A \ B)
= (A \ C) [ (»A \ C)
= (A [ »A) \ C
= E \ C
= C
1.15 A = B = D = G，C = F = H。
1.16
(1) f3, 4,f3g,f4gg；
(2) ?；
(3) f?,f?gg。
1.17
(1) f?,ff?gg,fff?ggg,ff?g,ff?gggg；
(2) f?,f?g,ff?gg,f?,f?ggg；
9
(3) ff?g,ff?ggg。
1.18
(1) f?, 1, 2, 3g；
(2) ?；
(3) ?；
(4) ?。
1.19
(1) A [ B；
(2) A；
(3) B。
1.20 先证两个引理。
引理 1.4 对任意集合 A, B, C, D，有 A B ^ C D ) A [ C B [ D
证明: 8x，
x 2 A [ C () x 2 A _ x 2 C
() (x 2 A _ x 2 C)^
(x 2 A ! x 2 B ^ x 2 C ! x 2 D)
=) x 2 B _ x 2 D
() x 2 B [ D
引理 1.5 对任意集合 A, B, C, D，有 A B ^ C D ) A \ C B \ D
证明: 8x，
x 2 A \ C () x 2 A ^ x 2 C
=) x 2 B ^ x 2 C
=) x 2 B ^ x 2 D
() x 2 B \ D
再证原题。
证明:
A = A \ E
= A \ (C [ »C)
= (A \ C) [ (A \ »C)
(B \ C) [ (B \ »C)
= B \ (C [ »C)
= B \ E
= B
1.21
(1) 答：A \ B = A 当且仅当 A B。
10
(集合并定义)
(前提、子集关系定义)
(构造性二难)
(集合并定义)
2
(集合交定义)
(前提、子集关系定义)
(前提、子集关系定义)
(集合交定义)
2
(同一律)
(排中律)
(分配律)
(题设、引理 1.4)
(分配律)
(排中律)
(同一律)
2
证明:
A \ B = A
() 8x((x 2 A ^ x 2 B) $ x 2 A)
() 8x(((x 2 A ^ x 2 B) ! x 2 A) ^ (x 2 A ! (x 2 A ^ x 2 B)))
() 8x((:(x 2 A ^ x 2 B) _ x 2 A) ^ (:x 2 A _ (x 2 A ^ x 2 B)))
() 8x((:x 2 A _ :x 2 B _ x 2 A) ^ (:x 2 A _ (x 2 A ^ x 2 B)))
() 8x((:x 2 A _ x 2 A _ :x 2 B) ^ (:x 2 A _ (x 2 A ^ x 2 B)))
() 8x((:x 2 A _ x 2 A _ :x 2 B)^
((:x 2 A _ x 2 A) ^ (:x 2 A _ x 2 B)))
() 8x((1 _ :x 2 B) ^ (1 ^ (:x 2 A _ x 2 B)))
() 8x(1 ^ (1 ^ (:x 2 A _ x 2 B)))
() 8x(:x 2 A _ x 2 B)
() 8x(x 2 A ! x 2 B)
() A B
(2) 答：A [ B = A 当且仅当 B A。
证明:
A [ B = A
() 8x((x 2 A _ x 2 B) $ x 2 A)
() 8x(((x 2 A _ x 2 B) ! x 2 A) ^ (x 2 A ! (x 2 A _ x 2 B)))
() 8x((:(x 2 A _ x 2 B) _ x 2 A) ^ (:x 2 A _ x 2 A _ x 2 B))
() 8x(((:x 2 A ^ :x 2 B) _ x 2 A) ^ (:x 2 A _ x 2 A _ x 2 B))
() 8x(((:x 2 A _ x 2 A) ^ (:x 2 B _ x 2 A))^
(:x 2 A _ x 2 A _ x 2 B))
() 8x((1 ^ (:x 2 B _ x 2 A)) ^ (1 _ x 2 B))
() 8x((1 ^ (:x 2 B _ x 2 A)) ^ 1)
() 8x(:x 2 B _ x 2 A)
() 8x(x 2 B ! x 2 A)
() B A
(3) 答：A ' B = A 当且仅当 B = ?。
证明: 充分性。若 B = ?，则：
A ' B = A ' ?
= A
必要性。若 A ' B = A，则：
B = ? ' B
= (A ' A) ' B
11
(外延原则、集合交定义)
(等价联结词定义)
(蕴涵等值式)
(命题逻辑德¢摩根律)
(命题逻辑交换律)
(命题逻辑分配律)
(命题逻辑排中律)
(命题逻辑零律)
(命题逻辑同一律)
(蕴涵等值式)
(子集关系定义)
2
(外延原则、集合并定义)
(等价联结词定义)
(蕴涵等值式)
(命题逻辑德¢摩根律)
(命题逻辑分配律)
(命题逻辑排中律)
(命题逻辑零律)
(命题逻辑同一律)
(蕴涵等值式)
(子集关系定义)
2
(B = ?)
(教材例 1.7(4))
(教材例 1.7(4))
(教材例 1.7(5))
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
