离散数学习题解 1
习题一
1.1．略 1.2．略 1.3．略 1.4．略 1.5．略 1.6．略 1.7．略 1.8．略 1.9．略
1.10． 略 1.11． 略 1.12． 将下列 命题符号化, 并给出各命题的 真值:
(1)2+2＝4 当且仅当 3+3＝6. (2)2+2＝4 的充要条件是 3+3?6. (3)2+2?4 与 3+3＝6 互为充要条件. (4)若 2+2?4, 则 3+3?6, 反之亦然.
(1)p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 1. (2)p??q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 0. (3) ?p?q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 0. (4) ?p??q, 其中, p: 2+2＝4, q: 3+3＝6, 真值为 1.
1.13． 将下列命题符号化, 并给出各命题的真值: (1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三.
令 p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) p?q ??1. (2) q?p ??1. (3) p?q ??1.
(4) p?r 当 p ??0 时为真; p ??1 时为假.
1.14． 将下列 命题符号化.
(1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人.
(3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组.
(5)李辛与李末是兄弟.
(6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2 与 4 都是素数, 这是不对的. (13)“2 或 4 是素数, 这是不对的”是不对的.
离散数学习题解
(1)p?q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p?q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p?q, 其中, p: 天气冷, q: 我穿了羽绒服.
(4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟.
(6)p?q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p?q, 其中, p: 他吃饭, q: 他听音乐. (8)p?q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p?q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p?q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p?q, 其中, p: 下雪路滑, q: 他迟到了.
12) ??(p?q)或?p??q, 其中, p: 2 是素数, q: 4 是素数. (13) ???(p?q)或 p?q, 其中, p: 2 是素数, q: 4 是素数.
2
1.15．
设 p: 2+3=5. q: 大熊猫产在中国. r: 复旦大学在广州. 求下列复合命题的真值: (1)(p?q) ?r (2)(r??(p?q)) ???p (3) ?r??(?p??q?r)
(4)(p?q??r) ??(( ?p??q) ?r) (1)真值为 0. (2)真值为 0. (3)真值为 0. (4)真值为 1.
注意: p, q 是真命题, r 是假命题.
1.16． 1.17． 1.18． 1.19．
略 略 略
用真值表判断下列公式的类型: (1)p??(p?q?r) (2)(p??q) ??q (3) ??(q?r) ?r (4)(p?q) ??(?q??p) (5)(p?r) ??( ?p??q) (6)((p?q) ??(q?r)) ??(p?r) (7)(p?q) ??(r?s)
离散数学习题解
(1), (4), (6)为重言式. (3)为矛盾式.
(2), (5), (7)为可满足式.
3
1.20． 1.21． 1.22． 1.23． 1.24． 1.25． 1.26． 1.27． 1.28． 1.29． 1.30． 1.31．
略 略 略 略 略 略 略 略 略 略 略
将下列 命题符号化, 并给出各命题的 真值:
(1)若 3+＝4, 则地球是静止不动的.
(2)若 3+2＝4, 则地球是运动不止的. (3)若地球上没有树木, 则人类不能生存. (4)若地球上没有水, 则 3 是无理数.
(1)p?q, 其中, p: 2+2＝4, q: 地球静止不动, 真值为 0. (2)p?q, 其中, p: 2+2＝4, q: 地球运动不止, 真值为 1. (3) ?p??q, 其中, p: 地球上有树木, q: 人类能生存, 真值为 1. (4) ?p?q, 其中, p: 地球上有水, q: 3 是无理数, 真值为 1.
离散数学习题解 4
习题二
2.1. 设公式 A = p?q, B = p??q, 用真值表验证公式 A 和 B 适合德摩根律:
?(A?B) ???A??B.
p 0 0 1 1 q 0 1 0 1 A =p?q B =p??q 1 1 0 1 0 0 1 0 ?(A?B) ?A??B 0 0 0 0 0 0 0 0
因为 ?(A?B)和 ?A??B 的真值表相同, 所以它们等值.
2.2. 略
2.3. 用等值演算法判断下列公式的类型, 对不是重言式的可满足式, 再用真值表法求出成真赋值.
(1) ??(p?q?q) (2)(p??(p?q)) ??(p?r)
(3)(p?q) ??(p?r)
(1) ??(p?q?q)????(?(p?q) ??q) ????(?p ???q ??q) ??p?q??q ??p?0 ??0 ??0. 矛盾式. (2)重言式.
(3) (p?q) ??(p?r) ???(p?q) ??(p?r) ???p??q ??p?r 易见, 是可满足式, 但不是重言式. 成真赋值为: 000, 001, 101, 111
p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 ?p ???q ? p?r 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1
2.4. 用等值演算法证明下面等值式: (1) p??(p?q) ??(p??q) (3) ??(p?q) ??(p?q) ???(p?q)
(4) (p??q) ??(?p?q) ??(p?q) ???(p?q) (1) (p?q) ??(p??q) ??p ??(q??q) ??p ??1 ??p. (3) ??(p?q)
离散数学习题解
???((p?q) ??(q?p)) ???((?p?q) ??(?q?p)) ??(p??q) ??(q??p)
??(p?q) ??(p??p) ??(?q?q) ??(?p??q)
5
??(p?q) ???(p?q) (4) (p??q) ??(?p?q)
??(p??p) ??(p?q) ??(?q??p) ??(?q?q)
??(p?q) ???(p?q)
2.5. 求下列公式的主析取范式, 并求成真赋值: (1)( ?p?q) ??(?q?p) (2) ??(p?q) ?q?r
(3)(p??(q?r)) ??(p?q?r) (1)(?p?q) ??(?q?p) ???(p?q) ??(?q?p)
???p??q ???q ??p???p??q ???q ??p(吸收律)??(p??p)??q ??p?(q??q) ??p??q ??p??q ??p?q ??p??q ??m10 ??m00 ??m11 ??m10 ??m0 ??m2 ??m3 ???(0, 2, 3).
成真赋值为 00, 10, 11.
(2)主析取范式为 0, 无成真赋值, 为矛盾式. (3)m0?m1?m2?m3?m4?m5?m6?m7, 为重言式.
2.6. 求下列公式的主合取范式, 并求成假赋值: (1) ??(q??p) ??p (2)(p?q) ??(?p?r)
(3)(p??(p?q)) ?r (1) ??(q??p) ???p ???(?q??p) ???p ??q?p ???p ??q?0 ??0
??M0?M1?M2?M3
这是矛盾式. 成假赋值为 00, 01, 10, 11. (2)M4, 成假赋值为 100. (3)主合取范式为 1, 为重言式.
离散数学习题解
2.7. 求下列公式的主析取范式, 再用主析取范式求合取范式: (1)(p?q) ?r
6
(2)(p?q) ??(q?r)
(1)m1?m3?m5?m6?m7?M0?M2?M4 (2)m0?m1?m3?m7?M2?M4?M5?M6
2.8. 略
2.9. 用真值表求下面公式的主析取范式.
(2) (p?q) ??(p??q)
p q 0 0 0 1 1 0 1 1 (p ??q) ??(p ????q) 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0
(2)从真值表可见成真赋值为 01, 10. 于是(p ??q) ??(p????q) ??m1 ??m2.
2.10. 略 2.11. 略 2.12. 略 2.13. 略 2.14. 略
2.15. 用主析取范式判断下列公式是否等值: (1)
(p?q) ?r 与 q??(p?r)
(2)(p?q) ?r ???(?p?q) ??r ???(?p?q) ??r ??p??q ??r
??p??q?(r??r) ??(p??p) ??(q??q)?r ??p??q?r ??p??q??r ??
p?q?r ??p??q?r ???p?q?r ???p??q?r = m101 ??m100 ??m111 ??m101 ??m011 ??m001 ??m1 ??m3 ??m4 ??m5 ??m7 = ?(1, 3, 4, 5, 7). 而 q?(p?r) ???q ??(?p?r) ???q ???p ?r
??(?p?p)??q?(?r?r) ???p?(?q?q)?(?r?r) ??(?p?p)?(?q?q)?r
?????(?p??q??r)?(?p??q?r)?(p??q??r)?(p??q?r) ?(?p??q??r)?(?p??q?r)?(?p?q??r)?(?p?q?r)
离散数学习题解
?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) = m0 ??m1 ??m4 ??m5 ??m0 ??m1 ??m2 ??m3 ??m1 ??m3 ??m5 ??m7
???m0 ??m1 ??m2 ??m3 ??m4 ??m5 ??m7 ???(0, 1, 2, 3, 4, 5, 7).
两个公式的主吸取范式不同, 所以(p?q) ?r? q??(p?r).
7
2.16. 用主析取范式判断下列公式是否等值: (1)(p?q) ?r 与 q??(p?r) (2) ??(p?q)与??(p?q)
(1)
(p?q) ?r) ?m1?m3?m4?m5?m7
q??(p?r) ?m0?m1?m2?m3?m4?m5?m7 所以(p?q) ?r) ? q??(p?r) (2)
??(p?q) ?m0?m1?m2 ??(p?q) ?m0
所以??(p?q) ? ??(p?q)
2.17. 用主合取范式判断下列公式是否等值: (1)p??(q?r)与??(p?q) ?r (2)p??(q?r)与(p?q) ?r
(1)
p??(q?r) ?M6 ??(p?q) ?r?M6
所以 p??(q?r) ????(p?q) ?r (2)
p??(q?r) ?M6
(p?q) ?r?M0?M1?M2?M6 所以 p??(q?r) ? (p?q) ?r
2.18. 略 2.19. 略
2.20.将下列公式化成与之等值且仅含 {?, ?} 中联结词的公式.
(3) (p?q)?r.
注意到 A?B ??(A?B)?(B?A)和 A?B ???(?A??B) ???(A??B)以及 A?B ???A?B. (p?q)?r
离散数学习题解
??(p?q ??r) ??(r ??p?q) ??(?(p??q) ??r) ??(r ???(p??q)) ???((?(p??q) ??r) ???(r ???(p??q))) 注?联结词越少, 公式越长.
8
2.21. 证明:
(1) (p?q) ??(q?p), (p?q) ??(q?p). (p?q) ???(p?q) ???(q?p) ??(q?p).
(p?q) ???(p?q) ???(q?p) ??(q?p). 2.22. 略 2.23. 略 2.24. 略
2.25. 设 A, B, C 为任意的命题公式.
(1)若 A?C?B?C, 举例说明 A?B 不一定成立. (2)已知 A?C?B?C, 举例说明 A?B 不一定成立. (3)已知?A??B, 问: A?B 一定成立吗?
(1) 取 A = p, B = q, C = 1 (重言式), 有
A?C ??B?C, 但 A ? B. (2) 取 A = p, B = q, C = 0 (矛盾式), 有
A?C ??B?C, 但 A ? B.
好的例子是简单, 具体, 而又说明问题的. (3)一定.
2.26. 略
2.27.某电路中有一个灯泡和三个开关 A,B,C. 已知在且仅在下述四种情况下灯亮: (1)C 的扳键向上, A,B 的扳键向下. (2)A 的扳键向上, B,C 的扳键向下. (3)B,C 的扳键向上, A 的扳键向下. (4)A,B 的扳键向上, C 的扳键向下.
设 F 为 1 表示灯亮, p,q,r 分别表示 A,B,C 的扳键向上. (a)求 F 的主析取范式.
(b)在联结词完备集{?, ?}上构造 F. (c)在联结词完备集{?, ?,?}上构造 F.
(a)由条件(1)-(4)可知, F 的主析取范式为 F??(?p??q?r) ??(p??q??r) ??(?p?q?r) ??(p?q??r) ?m1?m4?m3?m6 ?m1?m3?m4?m6
离散数学习题解
(b)先化简公式
F??(?p??q?r) ??(p??q??r) ??(?p?q?r) ??(p?q??r) ??q??((?p?r) ??(p??r)) ?q??((?p?r) ??(p??r)) ??(?q?q) ??((?p?r) ??(p??r)) ??(?p?r) ??(p??r)
???(??(?p?r) ???(p??r)) (已为{?, ?}中公式) (c) F??(?p?r) ??(p??r) ????(?p?r) ??(p??r) ???(?p?r) ??(p??r) ??(p??r) ???(?p?r) ??(r?p) ???(p?r) (已为{?, ?,?}中公式)
9
2.28.一个排队线路, 输入为 A,B,C, 其输出分别为 FA,FB,FC. 本线路中, 在同一时间内只能有一个信号通过, 若同
时有两个和两个以上信号申请输出时, 则按 A,B,C 的顺序输出. 写出 FA,FB,FC 在联结词完备集{?, ?} 中的表达式.
根据题目中的要求, 先写出 FA,FB,FC 的真值表(自己写) 由真值表可先求出他们的主析取范式, 然后化成{?, ?}中的公式 FA?m4?m5?m6?m7 ?p FB?m2?m3 ??p?q FC?m1 ??p??q?r
(已为{?, ?}中公式)
(已为{?, ?}中公式)
(已为{?, ?}中公式)
2.29. 略 2.30. 略
离散数学习题解 10
习题三
3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略
3.6. 判断下面推理是否正确. 先将简单命题符号化, 再写出前提, 结论, 推理的形式结构(以蕴涵式的形式给
出)和判断过程(至少给出两种判断方法):
(1)若今天是星期一, 则明天是星期三；今天是星期一. 所以明天是星期三. (2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一. (3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一. (4)若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二. (5)若今天是星期一, 则明天是星期二或星期三. (6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所以明天不是星期三.
设 p: 今天是星期一, q: 明天是星期二, r: 明天是星期三. (1)推理的形式结构为 (p?r) ?p?r
此形式结构为重言式, 即 (p?r) ?p?r 所以推理正确. (2)推理的形式结构为
(p?q) ?q?p 此形式结构不是重言式, 故推理不正确. (3)推理形式结构为 (p?r) ??r??p 此形式结构为重言式, 即 (p?r) ??r??p 故推理正确. (4)推理形式结构为
(p?q) ??p??q 此形式结构不是重言式, 故推理不正确. (5)推理形式结构为 p??(q?r)
它不是重言式, 故推理不正确. (6)推理形式结构为 (p?r) ??p??r
离散数学习题解
此形式结构为重言式, 即 (p?r) ??p??r 故推理正确.
11
推理是否正确, 可用多种方法证明. 证明的方法有真值表法, 等式演算法. 证明推理正确还可用构造证明法.
下面用构造证明法证明(6)推理正确. 前提: p?r, ?p 结论: ?r 证明: ① p?r
② (p?r) ??(r?p) ③ r?p ④?p ⑤?r 所以, 推理正确.
前提引入 ①置换 ②化简律 前提引入 ③④拒取式
3.7. 略 3.8. 略
3.9. 用三种方法(真值表法, 等值演算法, 主析取范式法)证明下面推理是正确的:
若 a 是奇数, 则 a 不能被 2 整除. 若 a 是偶数, 则 a 能被 2 整除. 因此, 如果 a 是偶数, 则 a 不是奇数.
令 p: a 是奇数; q: a 能被 2 整除; r: a 是偶数. 前提: p ???q, r ??q. 结论: r ???p.
形式结构: (p ???q) ??(r ??q) ??(r ???p). ……
3.10.略 3.11.略 3.12.略 3.13.略
3.14.在自然推理系统 P 中构造下面推理的证明: (1)前
提: p??(q?r), p, q 结论: r?s
(2)前提: p?q, ??(q?r), r 结论: ?p (3)前提: p?q 结论: p??(p?q)
(4)前提: q?p, q?s, s?t, t?r 结论: p?q
(5)前提: p?r, q?s, p?q
离散数学习题解
结论: r?s
(6)前提: ?p?r, ?q?s, p?q 结论: t??(r?s) (1)证
明:
12
① ② ③ ④ ⑤ ⑥
p?(q?r) p q?r q r r?s
前提引入 前提引入 ①②假言推理 前提引入 ③④假言推理 ⑤附加律
前提引入 ①置换 前提引入 ②③析取三段论 前提引入 ④⑤拒取式
(2)证明:
① ② ③ ④ ⑤ ⑥
??(q?r) ?q??r r ?q p?q ?p
(3)证明:
① ② ③ ④ ⑤
p?q ?p?q
(?p?q) ??(?p?p) ?p??(p?q) p??(p?q)
前提引入 ①置换 ②置换 ③置换 ④置换
也可以用附加前提证明法, 更简单些. (4)证明:
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩
s?t
(s?t) ??(t?s) t?s t?r t s q?s
(s?q) ??(q?s) s?q q
前提引入 ①置换 ②化简 前提引入 ④化简 ③⑤假言推理 前提引入 ⑦置换 ⑧化简 ⑥⑥假言推理
离散数学习题解
○11 q ?p 前提引入
○12 p ⑩○11 假言推理 ○
13 p?q
⑩○
12 合取
(5)证明:
① p?r 前提引入 前② q?s 提引入 ③ p?q 前提引入 ④ p ③化简 ⑤ q ③化简 ⑥ r ①④假言推理 ⑦ s ②⑤假言推理 ⑧
r?s
⑥⑦合取
(6)证明:
① t 附加前提引入 ② ?p?r 前提引入 ③ p?q 前提引入 ④ p ③化简
⑤ r ②④析取三段论 ⑥
r?s
⑤附加
说明: 证明中, 附加提前 t, 前提?q?s 没用上. 这仍是正确的推理.
3.15.在自然推理系统 P 中用附加前提法证明下面各推理: (1)前提: p??(q?r), s?p, q 结论: s?r
(2)前提: (p?q) ??(r?s), (s?t) ?u 结论: p?u
(1)证明:
① s 附加前提引入 ② s?p 前提引入 ③ p ①②假言推理 ④ p??(q?r) 前提引入 ⑤ q?r ③④假言推理 ⑥ q 前提引入 ⑦
r
⑤⑥假言推理
13
离散数学习题解
(2)证明:
①
P 附加前提引入
②
p?q
①附加 ③
(p?q) ??(r?s)
前提引入 ④
r?s ②③假言推理
⑤
S ④化简 ⑥
s?t
⑤附加
⑦
(s?t) ?u 前提引入 ⑧
u
⑥⑦假言推理
3.16.在自然推理系统 P 中用归谬法证明下面推理:
(1)前提: p??q, ?r?q, r??s 结论: ?p
(2)前提: p?q, p?r, q?s 结论: r?s
(1)证明:
① P 结论否定引入 ② p??q 前提引入 ③ ?q ①②假言推理 ④ ?r?q 前提引入 ⑤ ?r ③④析取三段论 ⑥ r??s 前提引入 ⑦ r ⑥化简 ⑧
?r?r
⑤⑦合取
⑧为矛盾式, 由归谬法可知, 推理正确. (2)证明:
① ??(r?s) 结论否定引入 ② p?q 前提引入 ③ p?r 前提引入 ④ q?s 前提引入 ⑤ r?s
②③④构造性二难 ⑥
??(r?s) ??(r?s)
①⑤合取
14
离散数学习题解
⑥为矛盾式, 所以推理正确.
15
3.17.P53 17. 在自然推理系统 P 中构造下面推理的证明:
只要 A 曾到过受害者房间并且 11 点以前没用离开, A 就犯了谋杀罪. A 曾到过受害者房间. 如果 A 在 11 点以前离开, 看门人会看到他. 看门人没有看到他. 所以 A 犯了谋杀罪.
令 p: A 曾到过受害者房间; q: A 在 11 点以前离开了; r: A 就犯了谋杀罪; s:看门人看到 A.
前提: p??q ??r, p, q ??s, ?s. 结论: r.
前提: p??q ??r, p, q ??s, ?s; 证明: ① ?s ② q ??s ③ ?q ④ p ⑤ p??q ⑥ p??q ??r ⑦ r
结论: r.
前提引入 前提引入
①②拒取 前提引入 ③④合取 前提引入 ⑤⑥假言推理
3.18.在自然推理系统 P 中构造下面推理的证明.
(1)如果今天是星期六, 我们就要到颐和园或圆明园去玩. 如果颐和园游人太多, 我们就不去颐和园玩. 今天是星期六. 颐和园游人太多. 所以我们去圆明园玩.
(2)如果小王是理科学生, 他的数学成绩一定很好. 如果小王不是文科生, 他必是理科生. 小王的数学成 绩不好. 所以小王是文科学生.
(3)明天是晴天, 或是雨天；若明天是晴天, 我就去看电影；若我看电影, 我就不看书. 所以, 如果我看书, 则明天是雨天.
(1)令 p: 今天是星期六; q: 我们要到颐和园玩; r: 我们要到圆明园玩; s:颐和园游人太多.
前提: p??(q?r), s ???q, p, s. 结论: r.
① p ② p?q?r ③ q?r ④ s ⑤ s ???q ⑥ ?q ⑦ r
前提引入
前提引入 ①②假言推理 前提引入 前提引入
p p?q?r
s s ???q ?q
q?r
r
(1)的证明树
④⑤假言推理
③⑥析取三段论
离散数学习题解
(2) 令 p: 小王是理科生, q: 小王是文科生, r: 小王的数学成绩很好. 前提: p?r, ?q?p, ?r 结论: q 证明:
16
① ② ③ p?r ?r ?p 前提引入 前提引入 ①②拒取式 ?q ?p p?q
?r?p
④ ?q?p 前提引入 ⑤
q
③④拒取式
(2)
的证明树
(3)令 p: 明天是晴天, q: 明天是雨天, r: 我看电影, s: 我看书. 前提: p?q, p?r, r??s 结论: s?q 证明:
① s 附加前提引入 ② r??s 前提引入 ③ ?r ①②拒取式 ④ p?r 前提引入 ⑤ ?p ③④拒取式 ⑥ p?q 前提引入 ⑦
q
⑤⑥析取三段论
r
离散数学习题解 17
习题四
4.1. 将下面命题用 0 元谓词符号化: (1)小王学过英
语和法语. (2)除非李建是东北人, 否则他一定怕冷.
(1) 令 F(x): x 学过英语; F(x): x 学过法语; a: 小王. 符号化为
F(a)?F(b).
或进一步细分, 令 L(x, y): x 学过 y; a: 小王; b1: 英语; b2: 法语. 则符号化为
L(a, b1)?L(a, b2).
(2) 令 F(x): x 是东北人; G(x): x 怕冷; a: 李建. 符号化为
?F(a)?G(a) 或 ?G(a)?F(a).
或进一步细分, 令 H(x, y): x 是 y 地方人; G(x): x 怕冷; a: 小王; b: 东北. 则符号化为
?H(a, b)?G(a) 或 ?G(a)??H(a, b).
4.2. 在一阶逻辑中将下面命题符号化, 并分别讨论个体域限制为(a),(b)时命题的真值:
(1)凡有理数都能被 2 整除.
(2)有的有理数能被 2 整除. 其中(a)个体域为有理数集合, (b)个体域为实数集合.
(1)(a)中, ?xF(x), 其中, F(x): x 能被 2 整除, 真值为 0.
(b)中, ?x(G(x) ?F(x)), 其中, G(x): x 为有理数, F(x)同(a)中, 真值为 0. (2)(a)中, ?xF(x), 其中, F(x): x 能被 2 整除, 真值为 1.
(b)中, ?x(G(x) ?F(x)), 其中, F(x)同(a)中, G(x): x 为有理数, 真值为 1.
4.3. 在一阶逻辑中将下面命题符号化, 并分别讨论个体域限制为(a),(b)时命题的真值: (1)对于任意的 x, 均有 x2?2=(x+ 2 )(x????2 ). (2)存在 x, 使得 x+5=9. 其中(a)个体域为自然数集合, (b)个体域为实数集合.
(1)(a)中, ?x(x2?2=(x+ 2 )(x????2 )), 真值为 1.
(b)中, ?x(F(x) ??(x2?2=(x+ 2 )(x????2 )))), 其中, F(x): x 为实数, 真值为 1. (2)(a)中, ?x(x+5=9), 真值为 1.
(b)中, ?x(F(x) ??(x+5=9)), 其中, F(x): x 为实数, 真值为 1.
4.4. 在一阶逻辑中将下列命题符号化: (1)没有不能表示成分数的有理数. (2)在北京卖菜的人不全是外地人.
离散数学习题解
(3)乌鸦都是黑色的. (4)有的人天天锻炼身体.
18
没指定个体域, 因而使用全总个体域.
(1) ??x(F(x) ??G(x))或?x(F(x) ?G(x)), 其中, F(x): x 为有理数, G(x): x 能表示成分数. (2) ??x(F(x) ?G(x))或?x(F(x) ??G(x)), 其中, F(x): x 在北京卖菜, G(x): x 是外地人. (3) ?x(F(x) ?G(x)), 其中, F(x): x 是乌鸦, G(x): x 是黑色的. (4) ?x(F(x) ?G(x)), 其中, F(x): x 是人, G(x): x 天天锻炼身体.
4.5. 在一阶逻辑中将下列命题符号化: (1)火车都比
轮船快. (2)有的火车比有的汽车快. (3)不存在比所有火车都快的汽车. (4)“凡是汽车就比火车慢”是不对的.
因为没指明个体域, 因而使用全总个体域
(1) ?x?y(F(x) ?G(y) ?H(x,y)), 其中, F(x): x 是火车, G(y): y 是轮船, H(x,y):x 比 y 快. (2) ?x?y(F(x) ?G(y) ?H(x,y)), 其中, F(x): x 是火车, G(y): y 是汽车, H(x,y):x 比 y 快. (3) ??x(F(x) ??y(G(y) ?H(x,y)))
或?x(F(x) ??y(G(y) ??H(x,y))), 其中, F(x): x 是汽车, G(y): y 是火车, H(x,y):x 比 y 快. (4) ??x?y(F(x) ?G(y) ?H(x,y))
或?x?y(F(x) ?G(y) ??H(x,y) ), 其中, F(x): x 是汽车, G(y): y 是火车, H(x,y):x 比 y 慢.
4.6. 略
4.7. 将下列各公式翻译成自然语言, 个体域为整数集 ?, 并判断各命题的真假.
(1) ?x?y?z(x ??y = z); (2) ?x?y(x?y = 1).
(1) 可选的翻译:
①“任意两个整数的差是整数.”
② “对于任意两个整数, 都存在第三个整数, 它等于这两个整数相减.” ③ “对于任意整数 x 和 y, 都存在整数 z, 使得 x ??y = z.” 选③, 直接翻译, 无需数理逻辑以外的知识. 以下翻译意思相同, 都是错的:
??“有个整数, 它是任意两个整数的差.”
??“存在一个整数, 对于任意两个整数, 第一个整数都等于这两个整数相减.” ??“存在整数 z, 使得对于任意整数 x 和 y, 都有 x ??y = z.” 这 3 个句子都可以符号化为
?z?x?y(x ??y = z).
0量词顺序不可随意调换. (2) 可选的翻译:
离散数学习题解
①“每个整数都有一个倒数.”
② “对于每个整数, 都能找到另一个整数, 它们相乘结果是零.” ③ “对于任意整数 x, 都存在整数 y, 使得 x?y = z.” 选③, 是直接翻译, 无需数理逻辑以外的知识.
19
4.8. 指出下列公式中的指导变元, 量词的辖域, 各个体变项的自由出现和约束出现: (3)?x?y(F(x, y) ??G(y, z)) ???xH(x, y, z)
?x?y(F(x, y) ??G(y, z)) ???xH(x, y, z)
前件 ?x?y(F(x, y)?G(y, z)) 中, ??的指导变元是 x, ??的辖域是 ?y(F(x, y)?G(y, z)); ??的指导变元是 y, ??的辖域 是 (F(x, y)?G(y, z)).
后件 ?xH(x, y, z) 中, ??的指导变元是 x, ??的辖域是 H(x, y, z).
整个公式中, x 约束出现两次, y 约束出现两次, 自由出现一次; z 自由出现两次.
4.9. 给定解释 I 如下: (a)个体
域 DI 为实数集合\\.
(b)DI 中特定元素?a =0. (c)特定函数?f (x,y)=x?y, x,y∈DI.
(d)特定谓词?F(x,y): x=y,?G(x,y): x (4) ?x?y(G(f(x,y),a) ?F(x,y)) (1) ?x?y(x 4.10.给定解释 I 如下: (a)个体域 D=?(?为自然数). (b)D 中特定元素?a=2. (c)D 上函数?f (x,y)=x+y,?g (x,y)=x·y. (d)D 上谓词?F (x,y): x=y. 说明下列公式在 I 下的含义, 并指出各公式的真值: (1) ?xF(g(x,a),x) (2) ?x?y(F(f(x,a),y) ?F(f(y,a),x)) (3) ?x?y?z(F(f(x,y),z) (4) ?xF(f(x,x),g(x,x)) 离散数学习题解 (1) ?x(x·2=x), 真值为 0. (2) ?x?y((x+2=y) ??(y+2=x)), 真值为 0. (3) ?x?y?z(x+y=z),真值为 1. (4) ?x(x+x=x·x),真值为 1. 20 4.11.判断下列各式的类型: (1) F(x, y) ??(G(x, y) ??F(x, y)). (3) ?x?yF(x, y) ???x?yF(x, y). (5) ?x?y(F(x, y) ??F(y, x)). (1) 是命题重言式 p ??(q ??p) 的代换实例, 所以是永真式. (3) 在某些解释下为假(举例), 在某些解释下为真(举例), 所以是非永真式的可满足式. (5) 同(3). 4.12.P69 12. 设 I 为一个任意的解释, 在解释 I 下, 下面哪些公式一定是命题? (1) ?xF(x, y) ???yG(x, y). (2) ?x(F(x) ??G(x)) ???y(F( y) ??H( y)). (3) ?x(?yF(x, y) ???yG(x, y)). (4) ?x(F(x) ??G(x)) ??H( y). (2), (3) 一定是命题, 因为它们是闭式. 4.13.略 4.14.证明下面公式既不是永真式也不是矛盾式: (1) ?x(F(x) ??y(G(y) ?H(x,y))) (2) ?x?y(F(x) ?G(y) ?H(x,y)) (1) 取个体域为全总个体域. 解释 I1: F(x): x 为有理数, G(y): y 为整数, H(x,y): x 在 I1 下: ?x(F(x) ??y(G(y) ?H(x,y)))为真命题, 所以该公式不是矛盾式. 解释 I2: F(x),G(y)同 I1, H(x,y): y 整除 x. 在 I2 下: ?x(F(x) ??y(G(y) ?H(x,y)))为假命题, 所以该公式不是永真式. (2) 请读者给出不同解释, 使其分别为成真和成假的命题即可. 4.15.(1) 给出一个非闭式的永真式. (2) 给出一个非闭式的永假式. (3) 给出一个非闭式的可满足式, 但不是永真式. (1) F(x) ???F(x). (2) F(x) ???F(x). (3) ?x(F(x, y) ??F(y, x)). 离散数学习题解 21 习题五 5.1. 略 5.2. 设个体域 D={a,b,c}, 消去下列各式的量词: (1) ?x?y(F(x) ?G(y)) (2) ?x?y(F(x) ?G(y)) (3) ?xF(x) ??yG(y) (4) ?x(F(x,y) ??yG(y)) (1) ?x?y(F(x) ?G(y)) ??xF(x) ??yG(y) ??(F(a) ?F(b)) ?F(c)) ??(G(a) ?G(b) ?G(c)) (2) ?x?y(F(x) ?G(y)) ??xF(x) ??yG(y) ??(F(a) ?F(b) ?F(c)) ??(G(a) ?G(b) ?G(c)) (3) ?xF(x) ??yG(y) ??(F(a) ?F(b) ?F(c)) ??(G(a) ?G(b) ?G(c)) (4) ?x(F(x,y) ??yG(y)) ??xF(x,y) ??yG(y) ??(F(a,y) ?F(b,y) ?F(c,y)) ??(G(a) ?G(b) ?G(c)) 5.3. 设个体域 D={1,2}, 请给出两种不同的解释 I1 和 I2, 使得下面公式在 I1 下都是真命题, 而在 I2 下都是假 命题. (1) ?x(F(x) ?G(x)) (2) ?x(F(x) ?G(x)) (1)I1: F(x):x≤2,G(x):x≤3 F(1),F(2),G(1),G(2)均为真, 所以 ?x(F(x) ?G(x)) ??(F(1) ?G(1) ??(F(2) ?G(2))为真. I2: F(x)同 I1,G(x):x≤0 则 F(1),F(2)均为真, 而 G(1),G(2)均为假, ?x(F(x) ?G(x))为假. (2)留给读者自己做. 5.4. 略 5.5. 给定解释 I 如下: (a) 个体域 D={3,4}. (b)?f (x)为?f (3)=4,?f (4)=3. (c)?F(x,y)为?F(3,3)=?F(4,4)=0,?F(3,4)=?F(4,3)=1. 离散数学习题解 试求下列公式在 I 下的真值: (1) ?x?yF(x,y) (2) ?x?yF(x,y) 22 (3) ?x?y(F(x,y) ?F(f(x),f(y))) (1) ?x?yF(x,y) ??(F(3,3) ?F(3,4)) ??(F(4,3) ?F(4,4)) ??(0?1) ??(1?0) ?1 (2) ?x?yF(x,y) ??(F(3,3) ?F(3,4)) ??(F(4,3) ?F(4,4)) ??(0?1) ??(1?0) ?0 (3) ?x?y(F(x,y) ?F(f(x),f(y))) ??(F(3,3) ?F(f(3),f(3))) ??(F(4,3) ?F(f(4),f(3))) ??(F(3,4) ?F(f(3),f(4))) ??(F(4,4) ?F(f(4),f(4))) ??(0?0) ??(1?1) ??(1?1) ??(0?0) ?1 5.6. 略 5.7. 略 5.8. 在一阶逻辑中将下列命题符号化, 要求用两种不同的等值形式. (1) 没有小于负数的正数. (2) 相等的两个角未必都是对顶角. (1) 令 F(x): x 小于负数, G(x): x 是正数. 符合化为: ??x((F(x) ??G(x)) ???x(G(x) ???G(x)). (2) 令 F(x): x 是角, H(x, y): x 和 y 是相等的, L(x, y): x 与 y 是对顶角. 符合化为: ??x?y(F(x) ??F(y) ??H(x, y) ??L(x, y)) ???x?y(F(x) ??F(y) ??H(x, y) ???L(x, y)) ???x(F(x) ??(?y(F(y) ??H(x, y) ???L(x, y))). 5.9. 略 5.10.略 5.11.略 5.12.求下列各式的前束范式. (1) ?xF(x) ???yG(x, y); (3) ?xF(x, y) ???xG(x, y); (5) ?x1F(x1, x2) ??(F(x1) ????x2G(x1, x2)). 前束范式不是唯一的. (1) ?xF(x) ???yG(x, y) ???x(F(x) ???yG(x, y)) 离散数学习题解 ???x?y(F(x) ??G(x, y)). (3) ?xF(x, y) ???xG(x, y) ??(?xF(x, y) ???xG(x, y)) ??(?xG(x, y) ???xF(x, y)) ??(?x1F(x1, y) ???x2G(x2, y)) ??(?x3G(x3, y) ???x4F(x4, y)) ???x1?x2(F(x1, y) ??G(x2, y)) ???x3?x4(G(x3, y) ??F(x4, y)) ???x1?x2?x3?x4((F(x1, y) ??G(x2, y)) ??(G(x3, y) ??F(x4, y))). 23 5.13.将下列命题符号化, 要求符号化的公式全为前束范式: (1) 有的汽车比有的火车跑得快. (2) 有的火车比所有的汽车跑得快. (3) 说所有的火车比所有的汽车跑得快是不对的. (4) 说有的飞机比有的汽车慢是不对的. (1) 令 F(x): x 是汽车, G( y): y 是火车, H(x, y): x 比 y 跑得快. ?x(F(x) ???y(G( y) ??H(x, y)) ???x?y(F(x) ??G( y) ??H(x, y)). (2)令 F(x): x 是火车, G( y): y 是汽车, H(x, y): x 比 y 跑得快. ?x(F(x) ???y(G( y) ??H(x, y))) ???x?y(F(x) ??(G( y) ??H(x, y))). 0错误的答案: ?x?y(F(x) ??G( y) ??H(x, y)). (3)令 F(x): x 是火车, G( y): y 是汽车, H(x, y): x 比 y 跑得快. ??x(F(x) ???y(G( y) ??H(x, y))) ????x?y(F(x) ??(G( y) ??H(x, y))) ????x?y(F(x) ??G( y) ??H(x, y)) ???x?y(F(x) ??G( y) ??H(x, y)). (4)令 F(x): x 是飞机, G( y): y 是汽车, H(x, y): x 比 y 跑得慢. ???x(F(x) ???y(G( y) ??H(x, y))) ?????x?y(F(x) ??G( y) ??H(x, y)) (不是前束范式) ???x?y ??(F(x) ??G( y) ??H(x, y)) (不是前束范式) ???x?y(F(x) ??G( y) ???H(x, y)). 5.14.略 5.15.在自然推理系统 F 中构造下面推理的证明: (1) 前提: ?xF(x) ???y((F(y) ??G(y)) ??R(y)), ?xF(x) 结论: ?xR(x). (2) 前提: ?x(F(x) ??(G(a) ?R(x))), ?xF(x) 结论: ?x(F(x) ?R(x)) (3) 前提: ?x(F(x) ?G(x)), ??xG(x) 结论: ?xF(x) (4) 前提: ?x(F(x) ?G(x)), ?x(?G(x) ??R(x)), ?xR(x) 结论: ?xF(x) 离散数学习题解 (1)证明: 24 ① ?xF(x) ???y((F(y) ??G(y)) ??R(y)) ② ?xF(x) ③ ?y((F(y) ??G(y)) ??R(y)) ④ (F(c) ??G(c)) ??R(c) ⑤ F(c) ⑥ F(c) ??G(c) ⑦ R(c) ⑧ ?xR(x) 前提引入 前提引入 ①②假言推理 ③UI ①EI ⑤附加 ④⑥假言推理 ⑦EG (2) 证明: ① ?xF(x) ② F(c) ③ ?x(F(x) ??(G(a) ??(R(x))) ④ F(c) ??(G(a) ?R(c)) ⑤ G(a) ?R(c) ⑥ R(c) ⑦ F(c) ?R(c) ⑧ ?x(F(x) ?R(x)) 前提引入 ①EI 前提引入 ④UI ②④假言推理 ⑤化简 ②⑥合取 ⑥EG (3) 证明: ① ??xG(x) ② ?x?G(x) ③ ?G(c) ④ ?x(F(x) ?G(x) ⑤ F(c) ?G(c) ⑥ F(c) ⑦ ?xF(x) 前提引入 ①置换 ②UI 前提引入 ④UI ③⑤析取三段论 ⑥EG (4) 证明: ① ?x(F(x) ?G(x)) ② F(y) ?G(y) ③?x(?G(x) ??R(x)) ④ ⑤ ⑥ ⑦ ?G(y) ??R(y) ?xR(x) R(y) ?G(y) 前提引入 ①UI 前提引入 ③UI 前提引入 ⑤UI ④⑥析取三段论 ②⑦析取三段论 UG ⑧ F(y) ⑥ ?xF(x) 5.16.略 离散数学习题解 5.17.略 25 5.18.略 5.19.略 5.20.略 5.21.略 5.22.略 5.23.在自然推理系统 F 中, 证明下面推理: (1) 每个有理数都是实数, 有的有理数是整数, 因此有的实数是整数. (2) 有理数, 无理数都是实数, 虚数不是实数, 因此虚数既不是有理数, 也不是无理数. (3) 不存在能表示成分数的无理数, 有理数都能表示成分数, 因此有理数都不是无理数. (1) 设 F(x):x 为有理数, R(x):x 为实数, G(x):x 是整数. 前提: 结论: 证明: ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑥ ?x(F(x) ?G(x)) F(c) ?G(c) F(c) G(c) ?x(F(x) ?R(x)) F(c) ?R(c) R(c) R(c) ?G(c) ?x(R(x) ?G(x)) 前提引入 ①EI ②化简 ②化简 前提引入 ⑤UI ③⑥假言推理 ④⑦合取 ⑧EG ?x(F(x) ?R(x)), ?x(F(x) ?G(x)) ?x(R(x) ?G(x)) (2) 设: F(x):x 为有理数, G(x):x 为无理数, R(x)为实数, 前提: 结论: 证明: ① ② ③ ④ ⑤ ⑥ ⑦ ?x((F(x) ?G(x) ?R(x)) F(y) ?G(y)) ?R(y) ?x(H(x) ??R(x)) H(y) ??R(y) ?R(y) ???(F(y) ?G(y)) H(y) ???(F(y) ?G(y)) H(y) ??(?F(y) ??G(y)) 前提引入 ①UI 前提引入 ③UI ②置换 ④⑤假言三段论 ⑥置换 ?x((F(x) ?G(x)) ?R(x)), ?x(H(x) ??R(x)) ?x(H(x) ??(?F(x) ??G(x))) H(x)为虚数 离散数学习题解 ⑧ ?x(H(x) ??(?F(x) ??G(x))) ⑦UG 26 (3) 设: F(x):x 能表示成分数, G(x):x 为无理数, 前提: 结论: 证明: ① ② ③ ④ ⑤ ⑥ ⑦ ?x(H(x) ?F(x)) H(y) ?F(y) ?x(G(x) ??F(x)) G(y) ??F(y) F(y) ??G(y) H(y) ??G(y) ?x(H(x) ??G(x)) 前提引入 ①UI 前提引入 ③UI ④置换 ②⑤假言三段论 ⑥UG ?x(G(x) ??F(x)), ?x(H(x) ?F(x)) ?x(H(x) ??G(x)) H(x)为有理数 5.24.在自然推理系统 F 中, 构造下面推理的证明: 每个喜欢步行的人都不喜欢骑自行车. 每个人或者喜欢骑自行车或者喜欢乘汽车. 有的人不喜欢乘汽车, 所以有的人不喜欢步行. (个体域为人类集合) 令 F(x): x 喜欢步行, G( x): x 喜欢骑自行车, H(x): x 喜欢乘汽车. 前提: ?x(F(x) ???G(x)), ?x(G(x) ??H(y)), ?x?H(x). 结论: ?x?F(x). ① ?x(G(x) ??H(y)) ② G(c) ??H(c) ③ ?x?H(x) ④ ?H(c) ⑤ G(c) ⑥ ?x(F(x) ???G(x)) ⑦ F(c) ???G(c) ⑧ ?F(c) ⑨ ?x?F(x) 前提引入 ①UI 前提引入 ③UI ②④析取三段 前提引入 ⑥UI ⑤⑦拒取 ⑧EG 5.25.略 离散数学习题解 27 习题六 6.1. 选择适当的谓词表示下列集合: (1)小于 5 的非负整数 (2)奇整数集合 (3)10 的整倍数的集合 (1){x|x∈??0≤x<5} (2){x|x=2k+1?k∈?} (3){x|x=10k?k∈? } 6.2. 用列元素法表示下列集合: (1)S1＝ {x|x 是十进制的数字} (2)S2＝{x|x＝2?x＝5} (3)S3＝{x|x＝x∈??3 (4)S4＝{x|x∈\\?x2－1＝0?x>3} (5)S5＝{?x, y>|x, y∈??0≤x≤2??1≤y≤0} (1) S1={0,1,2,3,4,5,6,7,8,9} (2) S2={2,5} (3) S3={4,5,6,7,8,9,10,11} (4) S4=?? (5) S5={?0, ?1?,?1, ?1?,?2, ?1?,?0,0?,?1,0?,?2,0?} 6.3. 略 6.4. 设 F 表示一年级大学生的集合, S 表示二年级大学生的集合, M 表示数学专业学生的集合, R 表示计算机 专业学生的集合, T 表示听离散数学课学生的集合, G 表示星期一晚上参加音乐会的学生的集合, H 表示 星期一晚上很迟才睡觉的学生的集合. 问下列各句子所对应的集合表达式分别是什么? 请从备选的答 案中挑出来. (1)所有计算机专业二年级的学生在学离散数学课. (2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉. (3)听离散数学课的学生都没参加星期一晚上的音乐会. (4)这个音乐会只有大学一, 二年级的学生参加. (5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会. 备选答案: ①T?G∪H ②G∪H?T ③S∩R?T ④H＝G∪T ⑤T∩G＝??⑥F∪S?G ⑦G?F∪S ⑧S??(R∪M) ?G ⑥G?S??(R∩M) 答案: (1) ③S∩R?T (2) ④H=G∪T (3) ⑤T∩G=??(4) ⑦G?F∪S (5) ⑧S??(R∪M) ?G 6.5. 确定下列命题是否为真: (1) ????(2) ?∈??(3) ??{?} (4) ?∈{?} (5){a, b}?{a, b, c, {a, b, c}} 离散数学习题解 (6){a, b}∈{a, b, c, {a, b }} (7){a, b}?{a, b, {{a, b}}} (8){a, b}∈{a, b, {{a, b}}} 28 (1) 真(2)假(3) 真(4) 真(5) 真(6) 真(7) 真(8) 假 6.6. 略 6.7. 略 6.8. 略 6.9. 略 6.10.略 6.11.略 6.12.略 6.13.略 6.14.略 6.15.略 6.16.略 6.17.略 6.18.略 6.19.略 6.20.略 6.21.略 6.22.略 6.23.略 6.24.略 6.25.略 6.26.略 6.27.略 6.28.略 6.29.略 6.30.略 6.31.略 6.32.略 6.33.略 6.34.略 6.35.略 6.36.略 6.37.略 6.38.略 6.39.略 6.40.略 6.41.略 6.42.略 6.43.略 6.44.略 6.45.略 离散数学习题解 29 习题七 7.1. 已知 A={?,{?}},求 A×P(A). A×P(A)={ ???,??,??,{?}?,??,{{?}}?,??,{?,{?}}?,?{?},??,?{?},{?}?,?{?},{{?}}?, ?{?},{?,{?}}?} 7.2. 对于任意集合 A,B,C, 若 A×B?A×C,是否一定有 B?C 成立? 为什么? 不一 定, 因为有反例: A=?,B={1},C={2},B?C,A×B=?=A×C. 7.3. 设 A, B, C, D 是任意集合, (1) 求证(A∩B)×(C∩D)=(A×C)∩(B×D). (2) 下列等式中哪个成立? 那些不成立?对于成立的给出证明, 对于不成立的举一反例. (A∪B)×(C∪D)=(A×C)∪(B×D) (A?B)×(C?D)=(A×C) ??(B×D) (1) ??x,y?? ?x,y?∈(A∩B)×(C∩D) ?x∈A∩B?y∈C∩D??(x∈A?x∈B) ??(y∈C?y∈D) ??(x∈A?y∈C) ?? (x∈B?y∈D) ??x,y?∈(A×B) ??x,y?∈(C×D) ??x,y?∈A×B∩C×D (A∩B)×(C∩D)=(A×C)∩(B×D) (2)都不成立, 反例: A={1,2},B={2,3},C={1,2},D={2,3} (A∪B)×(C∪D)={1,2,3}×{1,2,3}?(A×C)∪(B×D) (A?B)×(C?D)={1}×{1}?(A×C) ??(B×D) 7.4. 略 7.5. 设 A, B 为任意集合, 证明 若 A×A=B×B, 则 A=B. ?x, x∈A??x,x?∈A×A??x,x?∈B×B?x∈B A=B 7.6. 列出从集合 A={1, 2}到 B={1}的所有的二元关系. R1=??,R2={?1,1?},R2={?2,1?},R3={?1,1?,?2,1?}. 7.7. 列出集合 A={2, 3, 4}上的恒等关系 IA, 全域关系 EA, 小于或等于关系 LA, 整除关系 DA. IA={?2,2?,?3,3?,?4,4?} EA=A×A={?2,2?,?2,3?,?2,4?,?3,2?,?3,3?,?3,4?,?4,2?,?4,3?,?4,4?} LA={?2,2?,?2,3?,?2,4?,?3,3?,?3,4?,?4,4?} DA={?2,2?,?2,4?,?3,3?,?4,4?} 7.8. 列出集合 A={?, {?}, {?, {?}}, {?, {?}, {?, {?}}}}上的包含关系. R?={??,??,??,{?}?,??,{?,{?}}?,??,{?,{?},{?,{?}}}?,?{?},{?}?,?{?},{?,{?}}?,?{?},{?,{?},??,{ ?}?}?,?{?,{?}}, {?,{?}}?,?{?,{?}},{?,{?},{?,{?}}}?, ?{?,{?},{?,{?}}},{?,{?},{?,{?}}}?} 7.9. 设 A={1, 2, 4, 6}, 列出下列关系 R: (1) R={?x, y?|x, y∈A?x+y?2} (2) R={?x, y?|x, y∈A?|x?y|=1} 离散数学习题解 (3) R={?x, y?|x, y∈A?x/y∈A} (4) R={?x, y?|x, y∈A?y 为素数} (1)R={?1,2?,?1,4?,?1,6?,?2,1?,?2,2?,?2,4?,?2,6?,?4,1?,?4,2?,?4,4?,?4,6?,?6,1?,?6,2?,?6,4?,?6,6?}=EA?{?1,1?} (2)R={?1,2?,?2,1?} (3)R={?1,1?,?2,2?,?4,4?,?6,6?,?2,1?,?4,2?,?4,1?} (4)R={?1,2?,?2,2?,?4,2?,?6,2?} 30 7.10.略 7.11.Ri 是 X 上的二元关系, 对于 x∈X 定义集合 Ri(x)={y|xRiy}. 显然 Ri(x) ?X. 如果 X={?4, ?3, ?2, ?1, 0, 1, 2, 3, 4}, 且令 R1={?x, y?|x, y∈X?x 求 R1(0), R1(1), R2(0), R2(?1), R3(3). R1(0)={1,2,3,4} R1(1)={2,3,4} R2(0)={ ?1,0} R2(?1)={ ?2, ?1} R3(3)= ?? 7.12.设 A={0, 1, 2, 3}, R 是 A 上的关系, 且 R={?0, 0?, ?0, 3?, ?2, 0?, ?2, 1?, ?2, 3?, ?3, 2?} 给出 R 的关系矩阵和关系图. 7.13.设 A = {?1, 2?, ?2, 4?, ?3, 3?} B = {?1, 3?, ?2, 4?, ?4, 2?} 求 A∪B, A∩B, domA, dom(A∪B), ranA, ranB, ran(A∩B), fld(A?B). A∪B={?1,2?, ?1,3?, ?2,4?, ?3,3?, ?4,2?} A∩B={?2,4?} domA={1,2,3} dom(A∪B)={1,2,3,4} ranA={2,3,4} ranB={3,4,2} ran(A∩B)={4} fld(A?B)={1,2,3} 7.14.设 ?1 R={?0,1?,?0,2?,?0,3?,?1,2?,?1,3?,?2,3?} 求 R○R,R,R?{0,1},R[{1,2}]. R○R={?0,2?, ?0,3?, ?1,3?} R?1={?1,0?,?2,0?,?3,0?,?2,1?,?3,1?,?3,2?} R?{0,1}={?0,1?, ?0,2?, ?0,3?, ?1,2?, ?1,3?} R[{1,2}]={2,3} 7.15.设 ?1 2A={??,{?,{?}}?,?{?},??} 求 A,A,A3,A?{?},A[?],A??,A?{{?}},A[{{?}}]. A?1={?{?,{?}},??,??,{?}?}, A2={?{?},{?,{?}}?}, A3=?, A?{?}={??,{?,{?}}?}, A[?]={?,{?}}, 离散数学习题解 A??=?, A?{{?}}={?{?},??}, A[{{?}}]=?? 31 7.16.设 A={a,b,c,d}, R1,R2 为 A 上的关系, 其中 R1={?a,a?,?a,b?,?b,d?} R2={?a,d?2 ,?b,c?,?b,d?,?c,b?} 3 求 R1○R2, R2○R1,R1 ,R2 . R1○R2={?a,a?,?a,c?,?a,d?}, R2○R1={?c,d?}, 2R 1 ={?a,a?,?a,b?,?a,d?}, 3R 2 ={?b,c?,?b,d?,?c,b?} 7.17.设 A={a,b,c}, 试给出 A 上两个不同的关系 R1 和 R2,使得 R1 =R1, R2 =R2. R1={?a,a?,?b,b?}, R2={?b,c?,?c,b?} 7.18.证明定理 7.4 的(1), (2), (4). 2 3 (1) F○ (G∪H)=F○G∪F○H 任取?x,y?, ?x,y?∈F○ (G∪H) ??t(?x,t?∈F??t,y?∈G∪H) ??t(?x,t?∈F??(?t,y?∈G??t,y?∈H)) ??t((?x,t?∈F??t,y?∈G) ??(?x,t?∈F??t,y?∈H)) ??t(?x,t?∈F??t,y?∈G) ??t(?x,t?∈F??t,y?∈H)) ??x,y?∈F○G??x,y?∈F○H ??x,y?∈F○G∩F○H 所以有 F○ (G∩H)??F○G∩F○H. (2) (G∪H) ○F=G○F∪H○F 任取?x,y?, ?x,y?∈(G∪H) ○F ??t(?x,t?∈(G∪H) ??t,y?∈F) ??t((?x,t?∈G??t,y?∈H) ??t,y?∈F)) ??t((?x,t?∈G??t,y?∈F) ??(?x,t?∈H??t,y?∈F)) ??t(?x,t?∈G??t,y?∈F) ??t(?x,t?∈H??t,y?∈F)) ??x,y?∈G○F??x,y?∈H○F ??x,y?∈G○F∪H○F (4) (G∩H) ○F?G○F∩H○F 任取?x,y?, ?x,y?∈(G∩H) ○F ??t(?x,t?∈(G∩H) ??t,y?∈F) ??t((?x,t?∈G??t,y?∈H) ??t,y?∈F)) ??t((?x,t?∈G??t,y?∈F) ??(?x,t?∈H??t,y?∈F)) ??t(?x,t?∈G??t,y?∈F) ??t(?x,t?∈H??t,y?∈F)) ??x,y?∈G○F??x,y?∈H○F ??x,y?∈G○F∪H○F 7.19.证明定理 7.5 的(2), (3). (2) F[A∪B]=F[A]∪F[B] 任取 y, 离散数学习题解 y∈F[A∪B] ??x(?x,y?∈F?x∈A∪B) ??x(?x,y?∈F??(x∈A?x∈B)) ??x((?x,y?∈F?x∈A) ??(?x,y?∈F?x∈B)) ??x(?x,y?∈F?x∈A) ??x(?x,y?∈F?x∈B) ?y∈F[A] ?y∈F[B] ?y∈F[A]∪F[B] 所以有 F[A∩B]=F[A]∪F[B]. (3) F? (A∩B) ?F?A∩F?B 任取?x,y?? ?x,y?∈F? (A∩B) ??x,y?∈F?x∈(A∩B) ??x,y?∈F??(x∈A?x∈B) ??(?x,y?∈F?x∈A) ??(?x,y?∈F?x∈B) ??x,y?∈F?A??x,y?∈F?B ??x,y?∈F?A∩F?B 所以有 F? (A∪B) ?F?A∩F?B. 32 7.20.设 R1 和 R2 为 A 上的关系, 证明: (1)(R1∪R2) ?1=R1 ∪R2 (2)(R1∩R2) ?1=R1 ∩R2 ?1 ?1 ?1 ?1 ?1 (1)(R1∪R2) ?1=R1 ∪R2 任取?x,y?? ?x,y?∈(R1∪R2) ?1 ??y,x?∈(R1∪R2) ??y,x?∈R1??(y,x)∈R2) ?1 ?1 ??x,y?∈R1 ?1 ??x,?y1 ?∈R2 ??x,y?∈R1 ??R1 2 ?1 ?1 所以(R1∪R2) =R1 ∪R2 (2)(R1∩R2) ?1=R1 ∩R2 ?1 ?1 ?1 任取?x,y?? ?x,y?∈(R1∩R2) ?1 ??y,x?∈(R1∩R2) ??y,x?∈R1??(y,x)∈R2) ?1 ?1 ??x,y?∈R1 ?1 ??x,?y1 ?∈R2 ??x,y?∈R1 ?R2 所以(R1∪R2) ?1=R1 ∩R2 7.21.略 7.22.略 7.23.略 7.24.略 7.25.略 7.26.略 7.27.略 7.28.略 7.29.略 7.30.略 7.31.略 7.32.略 7.33.略 7.34.略 7.35.略 7.36.略 7.37.略 7.38.略 7.39.略 7.40.略 ?1 ?1 离散数学习题解 7.41.略 7.42.略 7.43.略 7.44.略 7.45.略 7.46.略 7.47.略 7.48.略 7.49.略 7.50.略 33 离散数学习题解 34 习题八 8.1. 1 设 f: ???, 且 ?1 ?f (x) ???? ??x 2 ??若x为奇数 若x为偶数 求 f(0), f({0}), f(1), f({1}), f({0, 2, 4, 6, …}), f({4, 6, 8}), f({1, 3, 5, 7}) f(0) = 0, f({0}) = {f(0)} = {0}, f(1) = 1, f({1}) = {f(1)} = {1}, f({0, 2, 4, 6, …}) = {f(0), f(2), f(4), f(6), …} = {0, 1, 2, 3, …} = ?, f({4, 6, 8}) = {f(4), f(6), f(8)} = {2, 3, 4}, f({1, 3, 5, 7}) = {1, 1, 1, 1} = {1}. 8.2. 2.设 A={1, 2}, B={a, b, c}, 求 BA. BA={f1, f2, f3, f4, f5, f6, f7, f8, f9} f1 = {?1, a?, ?2, a?}, f2 = {?1, a?, ?2, b?}, f3 = {?1, a?, ?2, c?}, f4 = {?1, b?, ?2, a?}, f5 = {?1, b?, ?2, b?}, f6 = {?1, b?, ?2, c?}, f7 = {?1, c?, ?2, a?}, f8 = {?1, c?, ?2, b?}, f9 = {?1, c?, ?2, c?}. 8.3. 3.给定函数 f 和集合 A, B 如下: (1) f: R?R, f(x)=x, A={8}, B={4} (2) f: R?R+, f(x)=2x, A={1}, B={1, 2} (3) f: N?N?N, f(x)= ?x, x+1}, A={5}, B={?2, 3?} (4) f: N?N, f(x)=2x+1, A={2, 3}, B={1, 3} (5) f: Z?N, f(x)=|x|, A={?1, 2}, B={1} (6) f: S?S, S=[0, 1], f(x)=x/2+1/4, A=(0, 1), B=[1/4, 1/2] (7) f: S?R, S=[0, +∞), f(x)=1/(x+1), A={0, 1/2}, B={1/2} (8) f: S?R+, S=(0, 1), f(x)=1/x, A=S, B={2, 3}. 对以上每一组 f 和 A, B, 分别回答以下问题: (a) f 是不是满射, 单射和双射的?如果 f 是双射的, 求 f 的反函数. (b) -1 求 A 在 f 下的像 f(A)和 B 在 f 下的完全原像 f(B). 8.4. 4.判断下列函数中那些是满射的? 哪些是单射的? 哪些是双射的? (1) f: ???, f(x) = x2 + 2 (2) f: ???, f(x) = (x)mod 3, x 除以 3 的余数. ?1 (3) f: ???, f (x) ???? ?0 ?0 ?1 若x为奇数 若x为偶数 若x为奇数 若x为偶数 (4) f: ??{0, 1}, f (x) ???? (5) f: ??{0}?R, f(x)=log10x (6) f: R?R, f(x)=x2?2x?15 离散数学习题解 (1)单射, ∵ f(x) = x2 + 2 在?上是单调的. 不是满射, ∵ ?x??, f(x) = x2 + 2 ??0. 35 (3)不是单射的, ∵ f(0) = f(2) = 0. 不是满射的, ∵ ?x??, ?0 f (x) ? ???1 若x为奇 ??2. 数 若x为偶数 (5)是单射的, ∵ f(x)=log10x 在?上是单调的. 不是满射的, ∵ ?x??, f(x)=log10x ??2. 8.5. 设 X = {a, b, c, d}, Y = {1, 2, 3}, f = {?a, 1?, ?b, 2?, ?c, 3?}, 判断以下命题的真假 (1)f 是从 X 到 Y 的二元关系, 但不是从 X 到 Y 的函数; (2) f 是从 X 到 Y 的函数, 但不是从满射, 也不是单射 (3) f 是从 X 到 Y 的满射, 但不是从单射; (4) f 是从 X 到 Y 的双射. 8.6. 对于给定的 A, B 和 f, 判断 f 是否为从 A 到 B 的函数 f : A ??B. 如果是, 说明 f 是否为单射, 满射, 双射的. 2 (1)A = ?, B = ?, f (x) = x+ 1. (2)A = ?, B = _, f (x) = 1 ??x. (3) A = ???, B = _, f (?x, y?) = x ??(y+1).. (4)A = {1, 2, 3}, B = {p, q, r}, f = {?1, q?, ?2, q?, ?3, q?}. (5)A = B = ?, f (x) = 2x. (6) A = B = \\?\\, f (?x, y?) = ?y + 1, x + 1?. (7) A = ???, B = ?, f (?x, y?) = x2 + 2y2. (8) A = B = \\, f (x) = 1 x ??1 . (9) A = ???, B = ?, f (?x, y, z?) = x + y ??z. 8.7. 7.设 A = {a, b, c, d}, B = {0, 1, 2} (1)给出一个函数 f : A ??B, 使得 f 不是单射的也不是满射的; (2)给出一个函数 f : A ??B, 使得 f 不是单射的但是满射的; (3)能够给出一个函数 f : A ??B, 使得 f 是单射但不是满射的吗? (4)设|A| = m, |B| = n, 分别说明存在单射, 满射, 双射函数 f : A ??B 的条件. (1)答案不唯一. f = {?a, 0?, ?b, 0?, ?c, 0?, ?d, 0?}. (2)答案不唯一. f = {?a, 0?, ?b, 1?, ?c, 2?, ?d, 2?}. (3)不能. 事实上 A 到 B 不存在单射, ∵|A| = 4 > |B| = 3. (4)存在单射的条件是 m ??n, 存在满射的条件是 m ??n, 存在双射的条件是 m = n. 8.8. 给出自然数集?上的函数 f, 使 得 (1)f 是单射的, 但不是满射的; (2)f 是满射的, 但不是单射的. 8.9. 9.设 A 是 n 元集(n ??1), 则从 A 到 A 的函数中有多少个双射函数? 有多少个单射函数. 从 A 到 A 的函数中双射函数和单射函数都有 n!个. 注: 事实上, 从 A 到 A 的函数中满射函数也有 n!个. 8.10.10. 设 f : ??? ???, f (?x, y?) = x + y + 1 (1)说明 f 是否为单射, 满射, 双射的; (2)令 A = {?x, y?|x, y??且 f (?x, y?) = 3}, 求 A; (3)令 B = { f (?x, y?)|x, y?{1, 2, 3}且 x = y}, 求 B. (1)f 不是单射的, ∵ f (?0, 1?) = f (?0, 1?) = 2. f 不是满射的, ∵ ??x??, f (?x, y?) > 0. 从而 f 不是双射的. (2)要使 f (?x, y?) = x + y + 1 = 3, 可取?x, y??= ?1, 1?, ?0, 2?, ?2, 0?. 故 A = {?1, 1?, ?0, 2?, ?2, 0?}. (3) B = { f (?1, 1?), f (?2, 2?), f (?3, 3?)} = {3, 5, 7}. 8.11.确定 f 是否为从 X 到 Y 的函数, 并对 f : X ??Y 指出哪些是单射, 哪些是满射, 那些是双射的. 2 (1)X = Y = \\, \\为实数集, f (x) = x– x; (2) X = Y = \\, f (x) =??x; 离散数学习题解 36 (3) X = Y = \\, f (x) = + 1 x ; x ??1 x ??1 (4)X = Y = ?={x| x ???, x > 0}, f (x) = x + 1; 8.12.设 f: S?T, 证明 (1)f (A∩B) ??f (A) ∩ f (B), 其中 A, B ??S. (2)举出反例说明等式 f (A∩B) = f (A) ∩ f (B)不是永远为真的. (3)说明对于什么函数, 上述等式为真. 8.13.设 A 为非空集合, R 为 A 上的等价关系, g: A ??A / R 为自然映射. (1)设 R 为整数集合上的模 n 相等关系, 求 g(2). (2)说明 g 的性质(单射, 满射, 双射). (3)说明在什么条件下, g 为双射函数. 8.14.设 S 为集合, A, B 是 S 的子集, ?T 表示 T 的特征函数, 且?A = {?a, 1?, ?b, 1?, ?c, 0?, ?d, 0?}, ?B = {?a, 0?, ?b, 1?, ?c, 0?, ?d, 1?}, 求?A B. 8.15.15.设 A={1, 2, 3, 4}, A1={1, 2}, A2={1}, A3=?, 求 A1, A2, A3 和 A 的特征函数?A1, ?A2, ?A3 和?A. ∩?x (5)X = Y = ?, f (x) = ???x ?1 . 8.16.16.设 A={a, b, c}. R 为 A 上的等价关系, 且 R={?a, b?, ?b, a?}∪IA 求自然映射 g: A?A/R. 8.17.17．设 f, g, h∈RR, 且 f(x)=x+3, g(x)=2x+1, h(x)= 1 2 求 f○g, g○f, f○f, g○g, h○f, g○h, f○h, g○h○f. 8.18.18．设 f, g, h∈?, 且有 ? ?0 f(n)=n+1, g(n)=2n, h(x) ???? ?1 求 f○f, g○f, f○g, h○g, g○h, h○g○f 若x为偶数 若x为奇数 8.19.设 f : \\ ??\\, f (x) = x2 ??2, g : \\ ??\\, g(x) = x + 4, h : \\ ??\\, h(x) = x ??1. (1)求 g○f, f○g; (2)问 g○f 和 f○g 是否为单射, 满射, 双射的? (3)f, g, h 中哪些函数有反函数? 如果有, 求出这些反函数. 8.20.20.设 f, g 是从?到?的函数, 且 ?x ?1 ?f (x) ????0 ?x, ??(1)求 f○g x ??0,1, 2, 3 x ??4 x ??5 ? x g(x) ? ??2 ????3 ?? x为偶数 x为奇数 (2)说明 f○g 是否为单射, 满射, 双射的. 离散数学习题解 37 (1)这里的复合运算是右复合: f○g(x) = g(f (x)). 当 x = 1, 3, 4 以及大于 5 的偶数时, f (x)是偶数; 当 x = 0, 2 以及 大于 5 的奇数时, f (x)是奇数, 所以 ??x ?1 ???2 ,???0, g(x) ???? ?3, ??x ??2, ? 并且 f○g: ? ???. x ??1, 3 ?1, ?2, ???0, x ??4 ???? x ??0, 2或 ??5的奇 ?3, 数 ? x x为大于 的偶数 5 ? , ??2 x ??1 x ??3 x ??4 x ??0, 2或 ??5的奇数 x为大于5的偶数 (2)f 不是单射的, ∵ f(0) = f(2) = 3. f 是满射的, ∵ ran f ={0, 1, 2, 3}∪{x/2|x 为大于 5 的偶数} = {0, 1, 2, 3}∪{3, 4, 5, …, n, …} = ?. 8.21.21.设 f : ? ?????, f (x) = ?x, x + 1?. (1)说 明 f 是否为单射和满射, 为什么 (2)f 的反函数是否存在, 如果存在, 求出 f 的反函数; (3)求 ran f. (1)f 是单射的, ∵?x1, x2??, 若 x1 ??x2, 则 f(x1) = ?x1, x1 + 1????f(x2) = ?x2, x2 + 1?. F 不是满射的, 因为若?0, 0????ran f, 则?x??, 使得 f (x) = ?x, x + 1??= ?0, 0?, 而这是不可能的. (2)因为 f = {?x, ?x, x + 1??| x??}是单射, 它的逆关系 f ?1= {??x, x + 1?, x?| x??}是函数, 是从 ran f 到 dom f = ? 的双射函数. 但 f ?1 不是??? ???的函数, 因为 dom f ?1 = ran f ? ???. (3) ran f={?n, n + 1??n??}. 8.22.设 f: ? ???, f (x) = (x)mod n. 在?上定义等价关系 R, ?x, y??, ?x, y??R ??f(x) = f (y). (1)计算 f (?). (2)确定商集? / R. 8.23.设 f1, f2, f3, f4 为实数集\\到\\的函数, 且 f1(x) = ?? f2(x) = x, f3(x) = ?? ???1, x ??0 , ??1, x ??0 ??1, x为整数 ???1, 否则 , f4(x) = 1. 在\\上定义二元关系 Ei, ?x, y?\\, ?x, y??Ei ?f (x) = f (y), 则 Ei 是\\上的等价关系, 称 为 fi 导出的等价关系, 求商集\\/Ei, i = 1, 2, 3, 4. 8.24.24.对于以下集合 A 和 B, 构造从 A 到 B 的双射函数 f: A?B. (1)A={1, 2, 3}, B={a, b, c} (2)A=(0, 1), B=(0, 2) (3) A={x|x???x<0}, B=? (4) A=R, B=R+ 8.25.25.设 f: \\?\\?\\?\\, f(?x, y?)=??(x+y)/2, (x-y)/2?, 证明 f 是双射的. 8.26.设 f: A ??B, g: B ??C, 且 f○g: A ??C 是双射. 证明: (1)f : A ??B 是单射的. (2)g: B ??C 是满射的. 8.27.按照阶从低到高的次序排列下列函数, 如果 f (n)与 g(n)的阶相等, 则表示为 f (n) = ?(g(n)). 33 3 x, ??n, log n, n, nlog n, 2n+ n, 2n, (log n)2, lg n, n+ log n. 8.28.证明 (log n)log n = nloglog n . 4log n = n2; 2log n = n; 2 = n1 / log n; 离散数学习题解 38 2 2log n ??n 2 log n 离散数学习题解 39 习题九 9.1. 1.设 A={a,b,c}, B=2A, 由定义证明 P(A)≈2A. 9.2. 2.设[1, 2]和[0, 1]是实数区间, 由定义证明[1, 2]≈[0, 1]. 9.3. 3.设 A={2x|x∈?}, 证明 A≈?. 9.4. 4.证明定理 9.1. 9.5. 5.证明定理 9.3 的(1), (3). 9.6. 设 A, B, C, D 是集合, 且 A≈C, B≈D, 证明 A×B≈C×D. 9.7. 找出三个不同的?的真子集, 使得他们都与?等势. 9.8. 找出三个不同的?的真子集 A, B, C, 使得 A?·?, B?·?, C?·?. 9.9. 根据自然数的集合定义计算: (1)3∪6, 2∩5 (2)4?3, 3?1 (3)∪4, ∩1 (4)1×4, 22. 9.10.略 9.11.设 A, B 为可数集, 证明 (1)A∪B 是可数集. (2)A×B 是可数集. 离散数学习题解 40 习题十 10.1.列出以下运算的运算表: 1 x 的倒数, 即○x= 1 . (1) A={1,2, }, ?x∈A, ○x 是 2 x ?x,y∈A 有 (2) A={1,2,3,4},x○y=max(x,y),max(x,y)是 x 和 y 之中较大的数. x ○x 1 1 1 (1) 2 2 1 2 2 10.2.略 10.3.略 10.4.判断下列集合对所给的二元运算是否封闭: (1) 整数集合?和普通的减法运算 (2) 非零整数集合?*和普通的除法运算 1 1 2 3 4 (2) 2 2 2 3 4 3 3 3 3 4 4 4 4 4 4 (3) 全体 n×n 实矩阵集合 Mn(\\)和矩阵加法及乘法运算, 其中 n≥2 (4) 全体 n×n 实可逆矩阵集合关于矩阵加法和乘法运算, 其中 n≥2 (5) 正实数集合\\+和○运算, 其中○运算定义为: ?a,b∈\\+,a○b=ab?a?b (6) n∈?+,n?={nz|z∈?}.n?关于普通的加法和乘法运算. (7) A={a1,a2,...,an},n≥2. ○运算定义如下: ?ai,aj∈A,ai○aj=ai. (8) S={2x?1|x∈?+}关于普通的加法和乘法运算. (9) S={0,1},S 关于普通的加法和乘法运算. (10)S={x|x=2n,n∈?+}, S 关于普通的加法和乘法运算. (1)封闭 (2)不封闭 (3)加法与乘法都封闭 (4)乘法封闭,加法不封闭 (5)不封闭 (6)加法与乘法都封闭 (7)封闭 离散数学习题解 (8)加法不封闭,乘法封闭 (9)加法不封闭,乘法封闭 (10)加法不封闭,乘法封闭 41 10.5.对于上题中封闭的二元运算判断是否适合交换律, 结合律和分配律. (1)没有交换律, 没有结合律 (3)加法适合交换与结合律；乘法只适合结合律；乘法对于加法有分配律. (4)乘法适合结合律 (6)加法有交换, 结合律；乘法有交换, 结合律；乘法对于加法有分配律. (7)结合律 (8)乘法有交换, 结合律 (9)乘法有交换, 结合律 (10)乘法有交换, 结合律 10.6.对习题 4 中封闭的二元运算找出它的单位元, 零元和所有可逆元素的逆元. (1)没有单位元, 零元和可逆元素. (3)加法单位元为 n 阶全 0 矩阵,没有零元,任意 n 阶矩阵 M 有加法逆元?M；乘法单位元为 n 阶单位矩阵,零 元为 n 阶全 0 矩阵,可逆矩阵 M(行列式不为 0)有乘法逆元 M?1. (4)乘法单位元为 n 阶单位矩阵,没有零元,任何 M 有乘法逆元 M?1. (6)加法单位元为 0, 没有零元, x 的加法逆元是?x；乘法零元为 0, 当 n=1 时单位元为 1, 1 和?1 有乘法逆元, 就是自身. (7)没有单位元, 零元与可逆元素 (8)单位元为 1,没有零元,1 的乘法逆元是 1 (9)单位元为 1,零元是 0,1 的乘法逆元是 1 (10)没有单位元, 零元与可逆元素. 10.7.略 10.8.S=_×_, _为有理数集, ?为 S 上的二元运算, ??a,b?,?x,y?∈S 有 ?a,b???x,y?=?ax,ay+b?? (1) ?运算在 S 上是否可交换, 可结合? 是否为幂等的? (2) ?运算是否有单位元, 零元? 如果有, 请指出, 并求 S 中所有可逆元素的逆元. (1)不可交换, 可结合, 不满足幂等律. (2)单位元为?1,0?, 没有零元,当 a?0, ?a,b?的逆元为?? 1 a , ? ?? b f1(?x,y?)=x+y, f2(?x,y?)=x?y, f3(?x,y?)=x·y, f4(?x,y?)=max(x,y), f5(?x,y?)=min(x,y), f6(?x,y?)=|x?y| (1) 指出哪些函数是\\上的二元运算. a 10.9.\\为实数集, 定义以下六个函数 f1, … ,f6. ?x,y∈\\有 (2) 对所有\\上的二元运算说明是否为可交换, 可结合, 幂等的. (3) 求所有\\上二元运算的单位元, 零元以及每一个可逆元素的逆元. 离散数学习题解 (1)都是\\上的二元运算 (2)f1, f3, f4, f5, f6 可交换, f1, f3, f4, f5 可结合, f4,f5 幂等； (3)f1 的单位元为 0,没有零元,x 的逆元为?x；f2 没有单位元, 零元与可逆元素；f3 的单位元为 1, 零元为 0, x (x?0)的逆元为 ；f4, f5, f6 没有单位元, 零元与可逆元素. 42 1 x 10.10. 令 S = {a, b}, S 上有 4 个二元运算: ?, ○, i 和 □, 分别由表 10.8 确定. 表 10.8 ? a b a a a b a a ○ a b a a b b b a i a b a b a b a a □ a b a a b b a b (1) 这 4 个运算中哪些运算满足交换律, 结合律, 幂等律 (2) 求每个运算的单位元, 零元及所有可逆元素的逆元. (1) ?, ○,·可交换；?,○,□可结合；□幂等. (2) ?没有单位元和可逆元素,零元为 a；○的单位元为 a,没有零元,每个元素都是自己的逆元；·和□没有单位 元, 零元和可逆元素. 10.11. 设 S = {1, 2, … , 10}, 问下面定义的运算能否与 S 构成代数系统?S, ????如果能构成代数系统则说 明?运算是否满足交换律, 结合律, 并求?运算的单位元和零元. (1) x?y=gcd(x,y),gcd(x,y)是 x 与 y 的最大公约数. (2) x?y=lcm(x,y),lcm(x,y)是 x 与 y 的最小公倍数. (3) x?y=大于等于 x 和 y 的最小整数. (4) x?y=质数 p 的个数, 其中 x≤p≤y. (1)构成；满足交换律, 结合律,没有单位元,零元为 1. (2)不构成. (3)构成；单位元为 1,零元为 10,只有 1 有逆元,就是 1. (4)不构成. 10.12. 10.13. 10.14. 10.15. 略 略 略 下面各集合都是?的子集, 它们能否构成代数系统V=??,+ ?的子代数: (1) {x|x∈??x可以被 16 整除} (2) {x|x∈??x与 8 互质} (3) {x|x∈??x是 40 的因子} (4) {x|x∈??x是 30 的倍数}. (1)构成. (2)不构成. (3)不构成. (4)构成. 10.16. 设 V=??,+,·?, 其中+和·分别代表普通加法和乘法, 对下面给定的每个集合确定它是否构成 V 的子 代数, 为什么? (1) S1={2n|n∈?} (2) S2={2n+1|n∈?} (3) S3={－1, 0, 1} (1)是,因为 S1 对于加法和乘法封闭. (2)不是,因为 S2 对于加法不封闭. (3)不是,因为 S3 对于加法不封闭. 离散数学习题解 43 10.17. 设 V1=?{1,2,3},○,1?,其中 x○y 表示取 x 和 y 之中较大的数. V2=?{5,6},?,6?,其中 x?y 表示取 x 和 y 之 中较小的数. 求出 V1 和 V2 的所有子代数. 指出哪些是平凡子代数, 哪些是真子代数. V1 的子代数为 {1},{1,2},{1,3},{1,2,3},平凡子代数是{1}和{1,2,3}；V2 的子代数为{6}和{5,6},都是平凡子代 数. 离散数学习题解 44 习题十一 11.1.设 A={0,1},试给出半群?AA, ○?的运算表,其中○为函数的复合运算. AA={ f1,f2,f3,f4}, 其中 f1={?0,0?,?1,0?},f2={?0,0?,?1,1?}, f3={?0,1?,?1,0?},f4={?0,1?,?1,1?} 运算表为 ○ f1 f2 f3 f4 f1 f1 f1 f1 f1 f2 f1 f2 f3 f4 f3 f4 f3 f2 f1 f4 f4 f4 f4 f4 11.2.略 11.3.略 11.4.略 11.5.略 11.6.略 11.7.设 G={a+bi|a,b∈?},i 为虚数单位,即 i2= ?1.验证 G 关于复数加法构成群. 复数加法在 G 上封闭,有结合律,单位元为 0=0+0i,a+bi 的逆元为?a?bi. 11.8.略 11.9.设?为整数集合,在?上定义二元运算○如下: ?x,y∈?,x○y=x+y?2 问?关于○运算能否构成群? 为什么? 易见该运算封闭,任取整数 x,y,z, (x○y) ○z=(x+y?2) ○z = x+y?2+z?2 = x+y+z?4 x○ (y○z)=x+(y+z?2) ?2 = x+y+z?4 = x+y+z?4 结合律成立. 单位元为 2. X 的逆元为 4?x. 11.10. 设 A={x|x∈\\?x?0,1}.在 A 上定义六个函数如下: f1(x)=x, f2(x)=x?1, f3(x)=1?x, ?1?1 f4(x)=(1?x) , f5(x)=(x?1)x, f6(x)=x(x?1) ?1 令 F 为这 6 个函数构成的集合, ○运算为函数的复合运算. (1) 给出○运算的运算表. (2) 验证?F, ○?是一个群. 离散数学习题解 45 ○ f1 f2 (1) f3 f1 f1 f2 f3 f4 f5 f6 f2 f2 f1 f5 f6 f3 f4 f3 f3 f4 f1 f2 f6 f5 f4 f4 f3 f6 f5 f1 f2 f5 f5 f6 f2 f1 f4 f3 f6 f6 f5 f4 f3 f2 f1 f4 f5 f6 (2)易见封闭性满足, 函数合成满足结合律,单位元是 f1, ?1 ?1 ?1 ?1 ?1 ?1 f1 =f1,f2 =f2,f3 = f3,f4 =f5,f5 =f4,f6 =f6. 11.11. 11.12. 11.13. 11.14. 略 略 略 设 G 为群,且存在 a∈G,使得 G={ak|k∈?}, 证明 G 是交换群. 任取 ai,aj, aiaj = ai+j = aj+i = ajai 11.15. 11.16. 略 设 G 为群,若?x∈G 有 x2=e,证明 G 为交换群. 任取 G 中元素 a,b, 由于 a,b 为二阶元, a=a?1, b=b?1, 从而 ab=a?1b?1=(ba) ?1=ba 11.17. 设 G 为群,证明 e 为 G 中唯一的幂等元. 设 a 为幂等元,那么 aa=a,由消去律得 a=e. 11.18. 11.19. 略 *证明 4 阶群必含 2 阶元. 设 G 为 4 阶群, 若 G 中含有 4 阶元 a,那么 a2 是 2 阶元；若 G 中不含 4 阶元, 根据拉格朗日定理, G 中元素的 阶只能是 2 或 1, 而 G 不是平凡群, 必有非单位元存在, 这些非单位元就是 2 阶元. 11.20. *设 G 是非阿贝尔群,证明 G 中存在元素 a 和 b,a?b,且 ab=ba. 先证 G 中必含 3 阶或 3 阶以上的元素. 假设 G 中只有 1 阶或 2 阶元,那么 G 中任意元素 a 都有 a2=e. 根据第 7 题的结果,G 为 Abel 群,与已知矛盾. 设 a 为 G 中元素,且|a|>2,那么 a?a?1,令 b=a?1,则有 ab=ba. 11.21. 11.22. 11.23. 略 略 11.设 H 是群 G 的子群,x∈G,令 ?1 xHx={xhx?1|h∈H}, 证明 xHx?1 是 G 的子群,称为 H 的共轭子群. e 是 xHx?1 中的元素,因此 xHx?1 非空. 任取 xhx?1,xkx?1∈xHx?1,h,k∈H,则有 (xhx?1)(xkx?1) ?1=(xhx?1)(xk?1x?1)=x(hk?1)x?1 因为 H 为子群,hk?1 属于 H,从而 x(hk?1)x?1 属于 xHx?1. 由判定定理,命题得证. 11.24. 11.25. 11.26. 略 证明定理 11.11. *设 ????1 0 ????1 ????G ? ?? ??, ? , ? , ? 0 1 ??1????0 1 ? ???????0 ??0 0 ?????1 0 ?????1 0 ???? ????1???? 离散数学习题解 (1) G 上的二元运算为矩阵乘法,给出 G 的运算表 (2) 试找出 G 的所有子群 (3) 证明 G 的所有子群都是正规子群. 46 将 G 中矩阵依次记为 A,B, ?B, ?A. ? A (1)运算表为 B A A B B ?B ??A B ?B ??A A ??A ?B A B B A ?B ?B ??A ??A ??A ?B (2)子群: {A}, {A, ?A}, {A, ?B}, {A,B}, G (3)G 是 Abel 群, 所有的子群都是正规的. 11.27. 11.28. 11.29. 略 略 令 G={?,+}是整数加群. 求商群?/4?,?/12?和 4?/12?. ?/4?={4?,4?+1,4?+2,4?+3} (4?+a)+(4?+b)=4?+(a+b)mod 4 ?/12?={12?,12?+1,12?+2,12?+3,…,12?+11} (12?+a)+(12?+b)=12?+(a+b)mod 12 4?/12?={12?,12?+4,12?+8} (12?+a)+(12?+b)=12?+(a+b)mod 12 11.30. 对以下各小题给定的群 G1 和 G2 以及 f:G1?G2,说明 f 是否为群 G1 到 G2 的同态. 如果是,说明 G 是否为单同态,满同态和同构,并求同态像 f(G1)和同态核 kerf. (1) G1=??,+ ?,G2=?\\*,·?,其中\\*为非零实数的集合,+和·分别表示数的加法和乘法. f: ??\\*, f(x)= ?? ??1 x是偶 数 x是??1 奇数 (2) G1=??,+ ?,G2=?A,·?,其中+和·分别表示数的加法和乘法 A={x|x∈??|x|=1},其中?为复数集合. f: ??A,f(x)=cosx+i sinx (3) G1=?\\,+ ?,G2=?A,·?,+和·以及 A 的定义同(2). f: \\?A,f(x)=cosx+i sinx (1)同态,不是单同态,也不是满同 态. 同态像为{?1,1},同态核为 2?. (2)同态,单同态,不是满同态,同态像为{cosx+i sin x|x∈?},同态核为{0}. (3)同态,满同态,不是单同态,同态像为 A,同态核为{2kπ|k∈?}. 11.31. 11.32. 略 设?是群 G1 到 G2 的同构,证明??1 是 G2 到 G1 的同构. 易见???1 为 G2 到 G1 的双射函数. 任取 G2 中的元素 x,y,存在 G1 中元素 a,b 使得??(a)=x, ??(b)=y.因此, ?1?1?1 ??(xy)= ??(??(a)??(b)) = ??(??(ab))=ab=???1(x)???1(y) 从而证明了???1 为同构. 11.33. 略 离散数学习题解 11.34. 设 G1 为循环群,??是群 G1 到 G2 的同态,证明??(G1)也是循环群. 47 设 G1=?a?, 任取??(G1)的元素 x, 存在 ai∈G1,使得??(ai)=x. x = ??(ai) = (??(a))i 这证明了??(a)为??(G1)的生成元. 11.35. 设 G=?a?是 15 阶循环群. (1) 求出 G 的所有的生成元. (2) 求出 G 的所有子群. (1)生成元: a,a2,a4,a7,a8,a11,a13,a14 (2)子群: ?a?, ?a3?={e,a3,a6,a9,a12}, ?a5?={e,a5,a10}, G 11.36. ??1 2 3 4 5? ?1 2 3 4 5 ??????? ??, ????? ?? ??2 1 4 5 3? ??3 4 5 1 2 ?? ?1?1?1 (1) 计算??,??,?, ?, ???? (2) 将??,??1, ??1??表成不交的轮换之积. (3) 将(2)中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换. 设?,?是 5 元置换,且 ??1 2 3 4 5???????? ? 2 5, 4 3 1 ?? ?? ? 1 2 3 4 5??????????? ? 4 5 3 2 1?? ?1 ? 2 3 4 5 ?? ??(1) ??1??? 1 5 3 4 ?? ? 1 2 3 4 5 ?????1 ??? 5 1 2 ?? ? 43?? ??1 2 3 4 5 ?????1???????5 4 1 3 2 ? ? ??????1423?? ?? (2) ???1 ???14253?????1??????15243????????14??12??13?? (3) ???1 ???14??12??15??13?????1??????15??12??14??13?? ??为奇置换, ??1, ??1??为偶置换. 11.37. *证明群中运算满足消去律 任取 G 中元素 a,b,c,若 ab=ac,则有 ?1 a(ab)=a?1(ac) 即 (a?1a)b=(a?1a)c,从而有 b=c. 同理可证右消去律的成立. 11.38. *设 G 是有限群, K 是 G 的子群, H 是 K 的子群,证明[G:H]=[G:K][K:H]. 由拉格朗日定理有 |G|=[G:K]|K|, |K|=[K:H]|H|, 代入得 |G|=[G:K][K:H]|H| 再根据拉格朗日定理有 |G|=[G:H]|H|, 比较两个等式, 命题得证. 离散数学习题解 48 习题十二 12.1.设 A={a+bi|a,b∈?,i2 = ?1}, 证明 A 关于复数的加法和乘法构成环,称为高斯整数环. 12.2.略 12.3.(1) 设 R1,R2 是环,证明 R1 与 R2 的直积 R1×R2 也是环. (2) 若 R1 和 R2 为交换环和含幺环,证明 R1×R2 也是交换环和含幺环. 12.4.判断下列集合和给定运算是否构成环, 整环和域,如果不能构成,说明理由. (1) A={a+bi|a,b∈?},其中 i2= ?1,运算为复数的加法和乘法. (2) A={?1,0,1},运算为普通加法和乘法. (3) A=M2(?),2 阶整数矩阵的集合, 运算为矩阵加法和乘法. (4) A 是非零有理数集合 Q*,运算为普通加法和乘法. 12.5.略 12.6.略 12.7.略 12.8.证明定理 12.1(3) 离散数学习题解 49 习题十三 13.1. 1.图 13.9 中给出 6 个偏序集的哈斯图.判断其中哪些是格. 如果不是格, 说明理由. d f d c b a (b) (c) e d f e c b a (a) g f d e b a c f d d c e b b f e c a (f) b a c a (d) (e) 13.9 图 (a), (c), (f)是格. (b)中的{e, d}没有最大下界. (d)中的{d, e}没有最大下界. (e)中的{a, b}没有最大下界. 13.2.2.下列各集合对于整除关系都构成偏序集, 判断哪些偏序集是格. (1) L = {1, 2, 3, 4, 5} (2) L = {1, 2, 3, 6, 12} (3) L = {1, 2, 3, 4, 6, 9, 12, 18, 36} (4) L = {1, 2, 22, ..., 2n}, n??+ (1)不是格, 其他都是. 13.3.3. (1)群??12, ??的子群格. (2)画出 3 元对称群 S3 的子群格. 见答图. 离散数学习题解 50 ?12 S3 ?2?? ?3?? ?(12)?? ?4?? ?(123)???(23)???(13)?? ?6?? ?0??(1) ?(1)?? (2) 第 3 题答图 13.4.4.设 L 是格, 求以下公式的对偶式: (1) a??(a?b)? a (2) a??(b?c) ? (a?b) ??(a?c) (3) b??(c?a) ? (b?c) ?a. (1) a?(a?b) “a (2) a??(b?c) “ (a?b) ??(a?c) (3) b??(c?a) “ (b?c) ?a 13.5.5.设?为集合 S 上可交换, 可结合的二元运算, 若 a, b 是 S 上关于?运算的幂等元, 证明 a?b 也是关于?运 算的幂等元. 证 a ??b = b ??c (a ??b) ??(a ??b) = ((a ??b) ??a) ??b = (a ??(a ??b)) ??b = ((a ??a) ??b) ??b = (a ??a) ??(b ??b) = a ??b. 13.6.6.设 L 是格, a, b, c?L, 且 a ? b ? c, 证明 a ??b = b ??c a ??b = b; b ??c = b. 13.7.7.针对图 13.4 中的格 L1, L2 和 L3, 求出他们的所有子格. d b a c a1 L2 L3 d1 d1 c2 b2 a2 L1 图 13.10 L1 的子格: {a}, {b}, {c}, {d}, {a, b}, {a,c}, {a, d}, {b, d}, {c, d},{a, b, d},{a, c, d}, L1. L2 的子格: {a1}, {d1}, L2 L3 的子格: {a2}, {b2}, {c2}, {d2}, {a2, b2}, {a2, c2}, {a2, d2}, {b2, c2}, {b2, d2}, {c2, d2}, {a2, b2, c2}, {a2, b2, d2}, {a2, c2, d2}, {b2, c2, d2}, L3