离散数学屈婉玲版课后答案
3
习题一
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)若今天是星期一, 则明天是星期二.
(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) 刘晓月跑得快, 跳得高.
(2)老王是山东人或河北人.
(3)因为天气冷, 所以我穿了羽绒服.
(4)王欢与李乐组成一个小组.
(5)李辛与李末是兄弟.
(6)王强与刘威都学过法语.
(7)他一面吃饭, 一面听音乐.
(8)如果天下大雨, 他就乘班车上班.
(9)只有天下大雨, 他才乘班车上班.
(10)除非天下大雨, 他才乘班车上班.
(11)下雪路滑, 他迟到了.
(12)2与4都是素数, 这是不对的.
(13)“2或4是素数, 这是不对的”是不对的.
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是素数.
设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)为可满足式.
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.
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 习题二
2.1. 设公式A = p q, B = p←?q, 用真值表验证公式A 和B 适合德摩根律:
←(A(B) ? ←A←?B.
A =p q
B =p←?q ←(A(B) ←A←?B
0 0 1 1 0
1
1
1
1
1
1
因为←(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 ( p?r
1 1 1 1 0 0 0 0 1
1
1
1
1
1
1
1
1
1
1
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)
7
?← ((p q) ? (q p))
?← ((←p(q) ? (←q(p))
? (p?←q) ( (q?←p)
? (p(q) ? (p(←p) ? (←q(q) ? (←p(←q)
? (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, 为重言式.
p q ( p q ) ( p ← ? q )
0 0
0 1
1 0 1 1 1 0 0 1
1 1 1 0
0 1 1 1
1 0 0 0
8
2.7. 求下列公式的主析取范式, 再用主析取范式求合取范式:
(1)(p?q) (r
(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)
(2)从真值表可见成真赋值为01, 10. 于是(p q) (p← ? q) ? m1 ( m2 .
2.10. 略
2.11. 略
2.12. 略
2.1
3. 略
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).
q (p r).
两个公式的主吸取范式不同, 所以(p q) r
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)))
注联结词越少, 公式越长.
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.2
3. 略
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) (已为{←, , }中公式)
2.28. 一个排队线路, 输入为A,B,C, 其输出分别为F A,F B,F C. 本线路中, 在同一时间内只能有一个信号通过,
若同时有两个和两个以上信号申请输出时, 则按A,B,C的顺序输出. 写出F A,F B,F C在联结词完备集{←, (}中的表达式.
根据题目中的要求, 先写出F A,F B,F C的真值表(自己写)
由真值表可先求出他们的主析取范式, 然后化成{←, ?}中的公式
F A?m4(m5(m6(m7
?p
F B?m2(m3 ?←p?q
F C?m1
?←p?←q?r
2.29. 略
2.30. 略(已为{←, ?}中公式) (已为{←, ?}中公式) (已为{←, ?}中公式)
习题三
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
故推理正确.
推理是否正确, 可用多种方法证明. 证明的方法有真值表法, 等式演算法. 证明推理正确还可用构造证明法.
下面用构造证明法证明(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.1
4.在自然推理系统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
14
结论: r?s
(6)前提: ←p(r, ←q(s, p?q
结论: t (r(s)
(1)证明:
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 ④化简
③⑤假言推理前提引入
⑦置换
⑧化简
⑥⑥假言推理
q p
○
12 p
p?q ○
13
(5)证明:
p r ①前提引入
q s ②前提引入
p?q ③前提引入
④③化简p
⑤③化简q ⑩○假言推理11
⑩○合取
12
⑥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 附加前提引入前提引入
①②假言推理前提引入
③④假言推理前提引入
⑤⑥假言推理
(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)
⑥为矛盾式, 所以推理正确.
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 q(r
s ←q
p
s
前提引入
q(r ←q ①②假言推理
前提引入
r
前提引入
(1)的证明树④⑤假言推理
③⑥析取三段论
(2) 令p: 小王是理科生, q: 小王是文科生, r: 小王的数学成绩很好. 前提: p r, ←q p, ←r
结论: q
证明:
p r
←q ←r ②前提引入
←p ③①②拒取式
←p ←q p ④前提引入
(2)的证明树
⑤③④拒取式q
(3)令p: 明天是晴天, q: 明天是雨天, r: 我看电影, s: 我看书.
前提: p(q, p r, r ←s
结论: s q
证明:
①附加前提引入s
r ←s ②前提引入
←r ③①②拒取式
p r ④前提引入
←p ⑤③④拒取式
p(q ⑥前提引入
⑦⑤⑥析取三段论q p q
←r p r
习题四
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)有的人天天锻炼身体.
没指定个体域, 因而使用全总个体域.
(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).
量词顺序不可随意调换.
(2) 可选的翻译:
①“每个整数都有一个倒数.”
②“对于每个整数, 都能找到另一个整数, 它们相乘结果是零.”
③“对于任意整数x, 都存在整数y, 使得x⊕y = z.”
选③, 是直接翻译, 无需数理逻辑以外的知识.
4.8. 指出下列公式中的指导变元, 量词的辖域, 各个体变项的自由出现和约束出现:
(3) x y(F(x, y) ? G(y, z)) ( xH(x, y, z)
x y(F(x, y) ? G(y, z) ) ( x H(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)个体域D I为实数集合.
(b)D I中特定元素↓a =0.
(c)特定函数↓f (x,y)=x y, x,y∈D I.
(d)特定谓词↓F(x,y): x=y,↓G(x,y): x 说明下列公式在I下的含义, 并指出各公式的真值: (1) x y(G(x,y) ←F(x,y)) (2) x y(F(f(x,y),a) G(x,y)) (3) x y(G(x,y) ←F(f(x,y),a)) (4) x y(G(f(x,y),a) F(x,y)) (1) x y(x (2) x y((x y=0) x (3) x y((x (4) x y((x y<0) (x=y)), 真值为0. 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)) 22 (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. 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.1 5.(1) 给出一个非闭式的永真式. (2) 给出一个非闭式的永假式. (3) 给出一个非闭式的可满足式, 但不是永真式. (1) F(x) ( ←F(x). (2) F(x) ? ←F(x). (3) x(F(x, y) F(y, x)). 离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论 离散数学习题解答 习题一（第一章集合） 1. 列出下述集合的全部元素： 1）A={x | x ∈N∧x是偶数∧x＜15} 2）B={x|x∈N∧4+x=3} 3）C={x|x是十进制的数字} [解] 1）A={2，4，6，8，10，12，14} 2）B= 3）C={0，1，2，3，4，5，6，7，8，9} 2. 用谓词法表示下列集合： 1）{奇整数集合} 2）{小于7的非负整数集合} 3）{3，5，7，11，13，17，19，23，29} [解] 1）{n n∈I∧(?m∈I)(n=2m+1)}； 2）{n n∈I∧n≥0∧n<7}； 3）{p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性： 1） 2）∈ 3）{} 4）∈{} 5）{a，b}{a，b，c，{a，b，c}} 6）{a,b}∈(a，b，c，{a，b，c}) 7）{a，b}{a，b，{{a，b，}}} 8）{a，b}∈{a，b，{{a，b，}}} [解]1）真。因为空集是任意集合的子集； 2）假。因为空集不含任何元素； 3）真。因为空集是任意集合的子集； 4）真。因为是集合{}的元素； 5）真。因为{a，b}是集合{a，b，c，{a，b，c}}的子集； 6）假。因为{a,b}不是集合{a，b，c，{a，b，c}}的元素； 7）真。因为{a，b}是集合{a，b，{{a，b}}}的子集； 8）假。因为{a,b}不是集合{a，b，{{a，b}}}的元素。 4. 对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B∈C，则A∈C。 2）如果A∈B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A∈C。 [解] 1）假。例如A={a}，B={a，b}，C={{a}，{b}}，从而A∈B∧B∈C但A∈C。 2）假。例如A={a}，B={a，{a}}，C={{a}，{{a}}}，从而A∈B∧B∈C，但、A ∈C。 3）假。例如A={a}，B={a，b}，C={{a}，a，b}，从而ACB∧B∈．C，但A∈C。5．对任意集合A，B，C，确定下列命题的真假性： 1）如果A∈B∧B C，则A∈C。 2）如果A∈B∧B C，则A C。 3）如果A B∧B∈C，则A∈C。 3）如果A B∧B∈C，则A C。 [解] 1）真。因为B C x（x∈B x∈C），因此A∈B A∈C。 2）假。例如A={a}，B={{a}，{b}}，C={{a}，{b}，{c}}从而A∈B∧B C，但A C。 3）假。例如A={a}，B={{a，b}}，C={{a，{a，b}}，从而A B∧B∈C，但A C。 4）假。例如A={a}，B={{a，b}}，C={{a，b}，b}，从而A B∧B∈C，但A C。 6．求下列集合的幂集： 1）{a，b，c} 2）{a，{b，c}} 3）{} 4）{，{}} 5）{{a，b}，{a，a，b}，{a，b，a，b}} [解] 1）{，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}} 2）{，{a}，{{b，c}}，{a，{a，b}}} 3）{，{}} 4）{，{}，{{}}，{，{}}} 习题参考解答 习题 1、（3）P：银行利率降低 Q：股价没有上升 P∧Q （5）P：他今天乘火车去了北京 Q：他随旅行团去了九寨沟 Q P? （7）P：不识庐山真面目 Q：身在此山中 Q→P，或～P→～Q （9）P：一个整数能被6整除 Q：一个整数能被3整除 R：一个整数能被2整除 T：一个整数的各位数字之和能被3整除 P→Q∧R ，Q→T 2、（1）T （2）F （3）F （4）T （5）F （6）T （7）F （8）悖论 习题 1（3） ) ( ) ( ) ( ) ( ) ( ) ( R P Q P R P Q P R Q P R Q P → ∨ → ? ∨ ? ∨ ∨ ? ? ∨ ∨ ? ? ∨ → （4） ()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右 2、不， 不， 能 习题 1(3) (())~((~)) (~)()~(~(~))(~~)(~) P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取范式 ) ()()()()()()()()()()()()()())(())(()()(()) ()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取范式 (2) ()()(~)(~) (~(~))(~(~))(~~)(~)(~~) P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、 ()~() (~)(~) (~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价 3、解：根据给定的条件有下述命题公式： （A →（CD ））∧～（B ∧C ）∧～（C ∧D ） （～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ） （（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨ （～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ） 离散数学习题答案 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 ) 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()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 ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 。 解：公式的真值表如下： 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ [ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 } ⑦ s ⑤⑥假言推理 15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论： p u → 证明：用附加前提证明法。 ① p 附加前提引入 习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为1. （2）5是无理数. 答：此命题是简单命题，其真值为1. （3）3是素数或4是素数. 答：是命题，但不是简单命题，其真值为1. x+< （4）235 答：不是命题. （5）你去图书馆吗？ 答：不是命题. （6）2与3是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！ 答：不是命题. （9）吸烟请到吸烟室去！ 答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为1. （11）只有6是偶数，3才能是2的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8是偶数的充分必要条件是8能被3整除. 答：是命题，但不是简单命题，其真值为0. （13）2008年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p:是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5是有理数. 答：否定式：5是无理数.p：5是有理数.q：5是无理数.其否定式q的真值为1. （2）25不是无理数. 答：否定式：25是有理数. p ：25不是无理数. q ：25是有理数. 其否定式q 的真值为1. （3）2.5是自然数. 答：否定式：2.5不是自然数. p ：2.5是自然数. q ：2.5不是自然数. 其否定式q 的真值为1. （4）ln1是整数. 答：否定式：ln1不是整数. p ：ln1是整数. q ：ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2与5都是素数 答：p ：2是素数，q ：5是素数，符号化为p q ∧，其真值为1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p ：π是无理数，q ：自然对数的底e 是无理数，符号化为p q ∧，其真值为1. （3）虽然2是最小的素数，但2不是最小的自然数. 答：p ：2是最小的素数，q ：2是最小的自然数，符号化为p q ∧?，其真值为1. （4）3是偶素数. 答：p ：3是素数，q ：3是偶数，符号化为p q ∧，其真值为0. （5）4既不是素数，也不是偶数. 答：p ：4是素数，q ：4是偶数，符号化为p q ?∧?，其真值为0. 5.将下列命题符号化，并指出真值. （1）2或3是偶数. （2）2或4是偶数. （3）3或5是偶数. （4）3不是偶数或4不是偶数. （5）3不是素数或4不是偶数. 答: p ：2是偶数，q ：3是偶数，r :3是素数，s :4是偶数, t :5是偶数 (1) 符号化: p q ∨，其真值为1. (2) 符号化：p r ∨，其真值为1. (3) 符号化：r t ∨，其真值为0. (4) 符号化：q s ?∨?，其真值为1. (5) 符号化：r s ?∨?，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p ：小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨，符号化为: p q ∨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：p ：刘晓月选学英语，q ：刘晓月选学日语，符号化为: ()()p q p q ?∧∨∧?. 7.设p ：王冬生于1971年，q ：王冬生于1972年，说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表： 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式//最后一列全为1 （5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （6）公式类型为永真式（方法如上例）// 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解： （1）主析取范式 (?p→q)→(?q∨p) 离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（pr）∧(﹁q∨s) ?（01）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）(p∧q∧﹁r) ?（1∧1∧1） (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 （5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式，并求成真赋值 (1)(?p→q)→(?q∨p) 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 错误！未找到引用源。2=(x+错误！未找到引用源。)(x 错误！未找到引用源。). G(x): x+5=9. (1)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快 命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误！未找到引用源。=0. (c) 特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y D ∈错误！未找到引用源。. (d) 特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 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是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 离散数学第四版课后答案 第1章习题解答 1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9）， （10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。 分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。 本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。 其次，4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与” 联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）p: 2是无理数，p为真命题。 （2）p:5能被2整除，p为假命题。 （6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真 命题，因而p→q为假命题。 （7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命 题，q为真命题，因而p→q为假命题。 （8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不 知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。 1 （10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。 （12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q 为假命题，p∨q为真命题。 （13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q 为假命题。 （14）p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15）p：蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 （1）p→q （2）p→?q （3）?p→q （4）?p→?q 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值： （4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()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 ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： 4.1 （1）设S={1，2}，R 是S 上的二元关系，且xRy 。如果R=Is ，则（A ）；如 果R 是数的小于等于关系，则（B ），如果R=Es ，则（C ）。 （2）设有序对 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+24, 则 3+36, 反之亦然. (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）设Ｓ={１,２｝,R 是S 上的二元关系，且ｘR ｙ。如果Ｒ=Is ，则(A)； 如果R 是数的小于等于关系,则（Ｂ),如果Ｒ=Es ，则（C)。 （2）设有序对<ｘ+2，４>与有序对<５,2x+y>相等，则 ｘ=(D),y=(E). 供选择的答案 Ａ、B 、C ：① x ，y 可任意选择１或2;② ｘ＝1,ｙ=1；③ x=１,y=1 或 ２；x=y=2; ④ ｘ＝2,y=2;⑤ x=y=１或 x ＝y=２;⑥ x=1,ｙ＝2；⑦x=2,y ＝１。 D 、E:⑧ 3；⑨ 2;⑩－2。 答案: Ａ: ⑤ B: ③ Ｃ： ① D: ⑧ Ｅ: ⑩ 4.2设S ＝<1,2，３，４>,R 为S 上的关系，其关系矩阵是 ????? ???????0001100000011001 则（1）R 的关系表达式是（A ）。 (2)dom Ｒ＝(Ｂ),ranR=(C). (3）R ?Ｒ中有(Ｄ)个有序对。 (4）R ˉ1的关系图中有(E)个环。 供选择的答案 A ：①{<1,1>,<1,２>，<1，4>，<4，１>,＜4，3>}; ②{<１,１＞,<1,４＞,<2,1>,<４,1>,＜３,４>}; Ｂ、C ：③{１，2，3,4}；④{１,2，４};⑤{1,４}⑥{1，３,４}。 Ｄ、E ⑦1;⑧３；⑨6；⑩7。 答案： A ：② B:③ Ｃ：⑤ Ｄ:⑩ E:⑦ 4.3设R 是由方程ｘ+３ｙ=１2定义的正整数集Z+上的关系,即 { 离散数学习题详细答案 ————————————————————————————————作者：————————————————————————————————日期： 离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： 证明 设A 上定义的二元关系R 为： ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ① 对任意＜x,y ＞∈A ，因为x y =x y ，所以 ＜＜x,y ＞, ＜x,y ＞＞∈R 即R 是自反的。 ② 设＜x,y ＞∈A ，＜u,v ＞∈A ，若 ＜＜x,y ＞, ＜u,v ＞＞∈R ?x y =u v ?u v =x y ?＜＜u,v ＞,＜x,y ＞＞∈R 即R 是对称的。 ③ 设任意＜x,y ＞∈A ，＜u,v ＞∈A ，＜w,s ＞∈A ，对 ＜＜x,y ＞, ＜u,v ＞＞∈R ∧＜＜u,v ＞, ＜w,s ＞＞∈R ?（x y =u v ）∧（u v =w s ）?x y =w s ?＜＜x,y ＞, ＜w,s ＞＞∈R 故R 是传递的，于是R 是A 上的等价关系。 3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使 ………………………………………………最新资料推 荐……………………………………… 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是素数,这是不对的”是不对的. 习题3.7 1. 列出关系}6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z 中所有有序4元组。 解 }6|{=???∈><+ d c b a d c b a d c b a 且，，，，，，Z ,2,1,3,1,3,1,2,1,2,3,1,1,3,2,1,1,1,1,1,6,1,1,6,1,1,6,1,1,6,1,1,1{><><><><><><><><= ><><><><><><><><2,1,1,3,3,1,1,2,1,2,1,3,1,3,1,2,1,1,2,3,1,1,3,2,1,2,3,1,1,3,2,1 2. 列出二维表 3.18所表示的多元关系中所有5元组。假设不增加新的5元组，找出二维表3.18所有的主键码。 表3.18 航班信息 航空公司 航班 登机口 目的地 起飞时间 Nadir 112 34 底特律 08:10 Acme 221 22 丹佛 08:17 Acme 122 33 安克雷奇 08:22 Acme 323 34 檀香山 08:30 Nadir 199 13 底特律 08:47 Acme 222 22 丹佛 09:10 Nadir 322 34 底特律 09:44 解 略 3. 当施用投影运算5,3,2π到有序5元组>离散数学第三版课后习题答案
离散数学课后习题答案
离散数学习题答案(耿素云屈婉玲)
离散数学习题解答
屈婉玲版离散数学课后习题答案【1】
离散数学答案屈婉玲版第二版 高等教育出版社课后答案
屈婉玲版离散数学课后习题答案【2】
离散数学课后习题答案(左孝凌版)
离散数学课后答案
离散数学第四版课后标准答案
最新离散数学习题答案
离散数学(屈婉玲版)第四章部分答案
离散数学最全课后答案(屈婉玲版)
离散数学(屈婉玲版)第四章部分标准答案
离散数学习题详细答案
离散数学课后习题答案_(左孝
离散数学最全课后答案(屈婉玲版)
离散数学课后习题答案二
- 离散数学第四版课后标准答案
- 离散数学课后习题答案.pdf
- 离散数学(第二版)课后习题答案详解(完整版)
- 最新屈婉玲版离散数学课后习题答案【2】
- 离散数学最全课后答案(屈婉玲版)
- 离散数学课后习题答案
- 离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案
- 离散数学课后习题答案
- 离散数学课后习题答案
- 离散数学课后答案
- 离散数学课后习题答案(左孝凌版)
- 最新 离散数学(第二版)最全课后习题答案详解
- 离散数学课后习题答案_(左孝凌版)
- 离散数学最全课后答案(屈婉玲版)_0
- 离散数学课后习题答案
- 离散数学 第二版 课后习题答案详解
- 离散数学课后习题答案二
- 最新离散数学课后习题答案_(左孝凌版)
- 离散数学第2版课后答案
- 离散数学课后习题答案-(左孝凌版)