英语会话公式离散数学第一章答案

2020年10月4日发(作者：臧廷鉴)
离散数学第一章答案


【篇一：离散数学课后习题答案_屈婉玲(高等教育出版
社)】

txt>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 01 111 1 0 11 011
1 1 00 100 1 1 11 001 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 qr p∨q p∧r （p∨q）→(p∧r)

0 0000 1

0 0100 1

0 1010 0

0 1110 0

10 010 0

10 111 1

11 010 0

11 111 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)

??(p?q)?(?q?p)

?(?p??q)?(?q?p)

? (?p??q)?(?q?p)?(?q??p)?(p?q)?(p??q)

? (?p??q)?(p??q)?(p?q)

?m0?m2?m3

?∑(0,2,3)

主合取范式：

(?p→q)→(?q?p)

??(p?q)?(?q?p)

?(?p??q)?(?q?p)

?(?p?(?q?p))?(?q?(?q?p))

?1?(p??q)

?(p??q) ? m1

?∏(1)

(2) 主合取范式为：

?(p→q)?q?r??(?p?q)?q?r

?(p??q)?q?r?0

所以该式为矛盾式.

主合取范式为∏(0,1,2,3,4,5,6,7)

矛盾式的主析取范式为 0

(3)主合取范式为：

(p?(q?r))→(p?q?r)

??(p?(q?r))→(p?q?r)

?(?p?(?q??r))?(p?q?r)

?(?p?(p?q?r))?((?q??r))?(p?q?r))

?1?1

?1

所以该式为永真式.

永真式的主合取范式为 1

主析取范式为∑(0,1,2,3,4,5,6,7)

第三章部分课后习题参考答案

14. 在自然推理系统p中构造下面推理的证明：

(2)前提：p?q,?(q?r),r

结论：?p

(4)前提：q?p,q?s,s?t,t?r

结论：p?q

证明：（2）

①?(q?r) 前提引入

②?q??r ①置换

③q??r②蕴含等值式

④r前提引入

⑤?q ③④拒取式

⑥p?q前提引入

⑦￢p（3） ⑤⑥拒取式

证明（4）：

①t?r 前提引入

②t①化简律

③q?s 前提引入

④s?t 前提引入

⑤q?t ③④等价三段论

⑥（q?t）?(t?q) ⑤ 置换

⑦（q?t） ⑥化简

⑧q ②⑥ 假言推理

⑨q?p前提引入

⑩p⑧⑨假言推理

(11)p?q ⑧⑩合取

15在自然推理系统p中用附加前提法证明下面各推理：

(1)前提：p?(q?r),s?p,q

结论：s?r

证明

①s附加前提引入

②s?p前提引入

③p ①②假言推理

④p?(q?r) 前提引入

⑤q?r③④假言推理

⑥q 前提引入

⑦r⑤⑥假言推理

16在自然推理系统p中用归谬法证明下面各推理：

(1)前提：p??q,?r?q,r??s

结论：?p

证明：

①p结论的否定引入

②p?﹁q 前提引入

③﹁q ①②假言推理

④￢r?q 前提引入

⑤￢r ④化简律

⑥r?￢s 前提引入

⑦r⑥化简律

⑧r?﹁r ⑤⑦ 合取

由于最后一步r?﹁r 是矛盾式,所以推理正确.

第四章部分课后习题参考答案

3. 在一阶逻辑中将下面将下面命题符号化,并 分别讨论个体域限制为
(a),(b)条件时命题的真值:

(1) 对于任意x,均有2=(x+)(x).

(2) 存在x,使得x+5=9.

【篇二：离散数学最全课后答案(屈婉玲版)】


略

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 是素数.

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)为可满足式.

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.

2.1. 设公式 a = p?q, b = p??q, 用真值表验证公式 a 和 b 适合德摩
根律:

?(a?b) ???a??b.

因为 ?(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

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)

??(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, 为重言式.

【篇三：离散数学课后答案】


题一

6.将下列命题符号化。

（1）小丽只能从框里那一个苹果或一个梨.

（2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：

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

(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)为可满足式

习题二

9.用真值表求下面公式的主析取范式.

(2) (p→q) → (?p?q)

答：

(1)

(2)p q (p → q) → (?p ? q)

0 01 001

0 11 110

1 00 111

111 000

从真值表可见成真赋值为01, 10. 于是(p → q) →(?p ? q) ? m1 ∨
m2

11.用真值表求下面公式的主析取范式和主合取范式；

15. 用主析取范式判断下列公式是否等值:

(1) (p→q) →r与q→ (p→r)

答：

(1)(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) →rk q→ (p→r).

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) k q→ (p→r)

(2) ? (p∧q) ?m0∨m1∨m2

? (p∨q) ?m0

所以? (p∧q) k ? (p∨q)

习题三

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∨t⑤附加

⑦ (s∨t) →u 前提引入

⑧ u ⑥⑦假言推理

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) ①⑤合取

⑥为矛盾式, 所以推理正确.

18.在自然推理系统p中构造下面推理的证明.

(1)如果今天是星期六, 我们就要到颐和园或圆明园去玩. 如果颐和园
游人太多, 我们就不去颐和园玩. 今天是星期六. 颐和园游人太多. 所
以我们去圆明园玩.

(2)如果小王是理科学生, 他的数学成绩一定很好. 如果小王不是文科
生, 他必是理科生. 小王的数学成绩不好. 所以小王是文科学生.

(1)令 p: 今天是星期六;

q: 我们要到颐和园玩;

r: 我们要到圆明园玩;

s:颐和园游人太多.

前提: p→ (q∨r), s → ?q, p, s. 结论: r.

证明① p 前提引入

② p→q∨r前提引入

③q∨r①②假言推理

④s前提引入

⑤ s →?q前提引入

⑥ ?q ④⑤假言推理

⑦??r ③⑥析取三段论 r ?q s → ?q sq∨r p→q∨r p

(2)令p: 小王是理科生,

q: 小王是文科生,

r: 小王的数学成绩很好.

前提: p→r, ?q→p, ?r 结论: q

证明：① p→r 前提引入

② ?r 前提引入

③ ?p ①②拒取式

④ ?q→p 前提引入

⑤ q ③④拒取式

习题四

在一阶逻辑中将下列命题符号化:

(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天天锻炼身体.

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慢. 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): xy, x,y∈di.

说明下列公式在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(xy→x≠y), 真值为1.