1、离散数学习题解 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+36. (2)2+2 4 的充要条件是 3+36. (3)2+24 与 3+3 6 互为充要条件. (4)若 2+24, 则 3+36, 反 之 亦 然 .(1)pq, 其中, p: 2+2 4, q: 3+3 6, 真值为 1. (2)pq, 其中, p: 2+2 4, q: 3+3 6, 真值为 0. (3) pq, 其 中 , p: 2+2 4, q: 3
2、+3 6, 真值为 0. (4) pq, 其 中 , p: 2+2 4, q: 3+3 6, 真 值 为 1.1.13 将下列命题符号化, 并 给 出 各 命 题 的 真 值 : (1)若今天是星期一, 则 明 天 是 星 期 二 . (2)只有今天是星期一, 明 天 才 是 星 期 二 . (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明 天 是 星 期 三 .令 p: 今 天 是 星 期 一 ; q: 明 天 是 星 期 二 ; r: 明 天 是 星 期 三 . (1) pq 1.(2) qp 1.(3) pq 1.(4) pr 当 p 0 时为真; p 1 时为假.
3、1.14 将下列 命题符号化. (1) 刘 晓 月 跑 得 快 , 跳 得 高 . (2)老王是山东人或河北人.(3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组.(5)李辛与李末是兄弟.(6)王强与刘威都学过法语. (7) 他一面吃饭, 一面听音乐. (8)如果天下大雨, 他 就 乘班 车 上 班 . (9)只有天下大雨, 他 才 乘 班 车上 班 . (10)除非天下大雨, 他 才 乘 班 车 上班 . (11)下雪路滑, 他迟到了.(12)2 与 4 都是素数, 这 是 不 对 的 .(13)“2 或 4 是素数, 这 是 不 对 的 ”是 不 对 的 .离散数学习题解
4、 2(1)pq, 其中, p: 刘晓月跑得快, q: 刘 晓 月 跳 得 高 . (2)pq, 其中, p: 老王是山东人, q: 老 王 是 河 北 人 . (3)pq, 其 中 , p: 天气冷, q: 我 穿 了 羽 绒 服 .(4)p, 其 中 , p: 王 欢 与 李 乐 组 成 一 个 小 组 , 是 简 单 命 题 . (5)p, 其 中 , p: 李 辛 与 李 末 是 兄 弟 .(6)pq, 其中 , p: 王强学过法语 , q: 刘 威 学 过 法 语 . (7)pq, 其中, p: 他吃饭, q: 他 听 音 乐 .(8)pq, 其 中 , p: 天下大雨, q: 他乘班
5、车上班.(9)pq, 其 中 , p: 他乘班车上班, q: 天 下 大 雨 . (10)pq, 其 中 , p: 他乘班车上班, q: 天下大雨. (11)pq, 其 中 , p: 下雪路滑, q: 他迟到了.12) (pq)或 pq, 其中 , p: 2 是素数 , q: 4 是素数 . (13) (pq)或 pq, 其 中 , p: 2 是素数 , q: 4 是素数 .1.15 设 p: 2+3=5.q: 大 熊 猫 产 在 中 国 . r: 复 旦 大 学 在 广 州 . 求下列复合命题的真值 :(1)(pq) r (2)(r(pq) p (3) r(pqr)(4)(pqr) ( pq
6、) r)(1)真 值 为 0.(2)真 值 为 0.(3)真 值 为 0.(4)真 值 为 1.注意: p, q 是 真 命 题 , r 是 假 命 题 .1.16 略1.17 略1.18 略1.19 用真值表判断下列公式的类型: (1)p(pqr)(2)(pq) q(3) (qr) r(4)(pq) (qp)(5)(pr) ( pq) (6)(pq) (qr) (pr) (7)(pq) (rs)离散数学习题解 3(1), (4), (6)为 重 言 式 .(3)为矛盾式.(2), (5), (7)为 可 满 足 式 .1.20 略1.21 略1.22 略1.23 略1.24 略1.25 略1
7、.26 略1.27 略1.28 略1.29 略1.30 略1.31 将下列 命题符号化, 并 给 出 各 命 题 的 真值: (1)若 3+4, 则 地 球 是 静 止 不 动 的 .(2)若 3+24, 则地球是运动不止的. (3) 若地球上没有树木, 则 人 类 不 能 生 存 .(4)若地球上没有水, 则 3 是无理数.(1)pq, 其 中 , p: 2+2 4, q: 地 球 静 止 不 动 , 真 值 为 0. (2)pq, 其 中 , p: 2+2 4, q: 地 球 运 动 不 止 , 真 值 为 1.(3) pq, 其中, p: 地 球 上 有 树 木 , q: 人 类 能 生
8、 存 , 真值为 1. (4) pq, 其 中 , p: 地 球 上 有 水 , q: 3 是无理数, 真值为 1.离散数学习题解 4习题二2.1. 设公式 A = pq, B = pq, 用 真 值 表 验 证 公 式 A 和 B 适 合 德 摩 根 律 :(AB) AB.p q A =pq B =pq (AB) AB0 0 1 0 0 00 1 1 0 0 01 0 0 1 0 01 1 1 0 0 0因为 (AB)和 AB 的 真 值 表 相 同 , 所 以 它 们 等 值 .2.2. 略2.3. 用等值演算法判断下列公式的类型 , 对 不 是 重 言 式 的 可 满 足 式 , 再 用
9、 真 值 表 法 求 出 成 真 赋 值 . (1) (pqq)(2)(p(pq) (pr)(3)(pq) (pr)(1) (pqq)(pq) q) (p q q) pqq p0 0 0. 矛 盾 式 . (2)重言式 .(3) (pq) (pr) (pq) (pr) pq pr 易见, 是 可 满 足 式 , 但 不 是 重 言 式 . 成 真 赋 值 为 : 000, 001, 101, 111p q r p q pr0 0 0 1 1 1 1 00 0 1 1 1 1 1 00 1 0 1 0 0 0 00 1 1 1 0 0 0 01 0 0 0 0 1 0 01 0 1 0 0 1
10、1 11 1 0 0 0 0 0 01 1 1 0 0 0 1 12.4. 用等值演算法证明下面等值式: (1) p(pq) (pq)(3) (pq) (pq) (pq)(4) (pq) (pq) (pq) (pq)(1) (pq) (pq) p (qq) p 1 p. (3) (pq)离散数学习题解 5(pq) (qp)(pq) (qp)(pq) (qp)(pq) (pp) (qq) (pq)(pq) (pq)(4) (pq) (pq)(pp) (pq) (qp) (qq)(pq) (pq)2.5. 求下列公式的主析取范式, 并 求 成 真 赋 值 : (1)( pq) (qp)(2) (p
11、q) qr(3)(p(qr) (pqr)(1)(pq) (qp)(pq) (qp)pq q ppq q p(吸 收 律 )(pp)q p(qq)pq pq pq pqm10 m00 m11 m10m0 m2 m3(0, 2, 3).成真赋值为 00, 10, 11.(2)主析取范式为 0, 无 成 真 赋 值 , 为 矛 盾 式 . (3)m0m1m2m3m4m5m6m7, 为重言式 .2.6. 求下列公式的主合取范式 , 并 求 成 假 赋 值 : (1) (qp) p(2)(pq) (pr)(3)(p(pq) r(1) (qp) p(qp) pqp pq00M0M1M2M3这是矛盾式. 成
12、 假 赋 值 为 00, 01, 10, 11.(2)M4, 成 假 赋 值 为 100.(3)主合取范式为 1, 为重言式.离散数学习题解 62.7. 求下列公式的主析取范式, 再 用 主 析 取 范 式 求 合 取 范 式 : (1)(pq) r(2)(pq) (qr)(1)m1m3m5m6m7M0M2M4 (2)m0m1m3m7M2M4M5M62.8. 略2.9. 用真值表求下面公式的主析取范式. (2) (pq) (pq)p q (p q) (p q)0 0 1 0 0 10 1 1 1 1 01 0 0 1 1 11 1 1 0 0 0(2)从真值表可见成真赋值为 01, 10. 于
13、是( p q) (pq) m1 m2.2.10. 略2.11. 略2.12. 略2.13. 略2.14. 略2.15. 用主析取范式判断下列公式是否等值 : (1) (pq) r 与 q(pr)(2)(pq) r(pq) r(pq) rpq rpq(rr) (pp) (qq)rpqr pqr pqr pqr pqr pqr= m101 m100 m111 m101 m011 m001m1 m3 m4 m5 m7= (1, 3, 4, 5, 7).而 q(pr)q (pr)q p r(pp)q(rr) p(qq)(rr)(pp)(qq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr
14、)(pqr)(pqr)离散数学习题解 7(pqr)(pqr)(pqr)(pqr)= m0 m1 m4 m5m0 m1 m2 m3m1 m3 m5 m7m0 m1 m2 m3 m4 m5 m7(0, 1, 2, 3, 4, 5, 7).两个公式的主吸取范式不同, 所以(pq) r q(pr).2.16. 用主析取范式判断下列公式是否等值: (1)(pq) r 与 q(pr)(2) (pq)与 (pq)(1)(pq) r) m1m3m4m5m7q(pr) m0m1m2m3m4m5m7所以(pq) r) q(pr) (2)(pq) m0m1m2(pq) m0所以 (pq) (pq)2.17. 用主合
15、取范式判断下列公式是否等值: (1)p(qr)与 (pq) r(2)p(qr)与 (pq) r(1)p(qr) M6(pq) rM6所以 p(qr) (pq) r(2)p(qr) M6(pq) rM0M1M2M6所以 p(qr) (pq) r2.18. 略2.19. 略2.20.将下列公式化成与之等值且仅含 , 中 联 结 词 的 公 式 . (3) (pq)r.注意到 AB (AB)(BA)和 AB (AB) (AB)以 及 AB AB. (pq)r离散数学习题解 8(pq r) (r pq)(pq) r) (r (pq)(pq) r) (r (pq)注 联 结 词 越 少 , 公 式 越
16、长 .2.21. 证明:(1) (pq) (qp), (pq) (qp).(pq) (pq) (qp) (qp).(pq) (pq) (qp) (qp).2.22. 略2.23. 略2.24. 略2.25. 设 A, B, C 为 任 意 的 命 题 公 式 .(1)若 ACBC, 举例说明 AB 不一定成立. (2)已知 ACBC, 举例说明 AB 不一定成立. (3)已 知AB, 问 : AB 一 定 成 立 吗 ?(1) 取 A = p, B = q, C = 1 (重 言 式 ), 有AC BC, 但 A B.(2) 取 A = p, B = q, C = 0 (矛 盾 式 ), 有A
17、C BC, 但 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)在联结词完备集, 上 构 造
18、 F. (c)在 联 结 词 完 备 集, ,上 构 造 F.(a)由 条 件 (1)-(4)可 知 , F 的 主 析 取 范 式 为F(pqr) (pqr) (pqr) (pqr)m1m4m3m6m1m3m4m6离散数学习题解 9(b)先化简公式F(pqr) (pqr) (pqr) (pqr)q(pr) (pr) q(pr) (pr)(qq) (pr) (pr)(pr) (pr)(pr) (pr) (已 为 , 中 公 式 ) (c)F(pr) (pr)(pr) (pr)(pr) (pr)(pr) (pr)(rp) (pr) (已 为 , ,中 公 式 )2.28.一个排队线路, 输入为
19、A,B,C, 其输出分别为 FA,FB,FC. 本 线 路 中 , 在 同 一 时 间 内 只 能 有 一 个 信 号 通 过 , 若同时有两个和两个以上信号申请输出时, 则按 A,B,C 的 顺 序 输 出 . 写出 FA,FB,FC 在 联 结 词 完 备 集 , 中的表达式.根据题目中的要求, 先写出 FA,FB,FC 的 真 值 表 (自 己 写 ) 由真值表可先求出他们的主析取范式, 然 后 化 成 , 中 的 公 式 FAm4m5m6m7p (已 为 , 中 公 式 )FBm2m3pq (已 为 , 中 公 式 )FCm1pqr (已 为 , 中 公 式 )2.29. 略2.30.
20、 略离散数学习题解 10习题三3.1. 略3.2. 略3.3. 略3.4. 略3.5. 略3.6. 判断下面推理是否正确. 先 将 简 单 命 题 符 号 化 , 再 写 出 前 提 , 结论, 推 理 的 形 式 结 构 (以 蕴 涵 式 的 形 式 给 出)和判断过程(至少给出两种判断方法):(1)若今天是星期一, 则 明 天 是 星 期 三 ； 今 天 是 星 期 一 . 所 以 明 天 是 星 期 三 . (2)若今天是星期一, 则 明 天 是 星 期 二 ； 明 天 是 星 期 二 . 所 以 今 天 是 星 期 一 . (3)若今天是星期一, 则 明 天 是 星 期三 ； 明 天
21、不 是 星 期 三 . 所 以 今 天 不 是 星 期 一 . (4)若今天是星期一, 则 明 天 是 星 期 二 ； 今 天 不是 星 期 一 . 所 以 明 天 不 是 星 期 二 . (5)若今天是星期一, 则 明 天 是 星 期 二 或 星 期 三 . (6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所 以 明 天 不 是 星 期 三 .设 p: 今天是星期一, q: 明 天 是 星 期 二 , r: 明 天 是 星 期 三 . (1)推理的形式结构为(pr) pr此 形 式 结 构 为 重 言 式 , 即(pr) pr 所以推理正确. (2) 推理的形式结构为(pq) qp 此形式结构不是重言式, 故 推 理 不 正 确 . (3)推理形式结构为(pr) rp此形式结构为重言式, 即(pr) rp 故推理正确. (4) 推理形式结构为(pq) pq 此形式结构不是重言式 , 故 推 理 不 正 确 . (5)推理形式结构为p(qr)它不是重言式, 故推理不正确. (6)推理形式结构为(pr) pr
