离散数学第五版第九章(耿素云、屈婉玲、张立昂编著)

离散数学习题答案习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）(⌝p→q)∧(q∧r)解：原式⇔(p∨q)∧q∧r⇔q∧r⇔(⌝p∨p)∧q∧r ⇔(⌝p∧q∧r)∨(p∧q∧r)⇔m3∨m7，此即公式的主析取范式，所以成真赋值为011，111。

6、求下列公式的主合取范式，并求成假赋值：（2）(p∧q)∨(⌝p∨r)解：原式⇔(p∨⌝p∨r)∧(⌝p∨q∨r)所以成假赋值为100。

7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）(p∧q)∨r解：原式⇔⇔(⌝p∨q∨r)⇔M4，此即公式的主合取范式，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)⇔m1∨m3∨m5∨m6∨m7，此即主析取范式。

主析取范式中没出现的极小项为m0，m2，m4，所以主合取范式中含有三个极大项M0，M2，M4，故原式的主合取范式⇔M09、用真值表法求下面公式的主析取范式：（1）(p∨q)∨(⌝p∧r)解：公式的真值表如下：∧M2∧M4。

由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式⇔m1∨m2∨m3∨m4∨m5∨m6∨m7习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。

前提：⌝p∨q,⌝q∨r,r结论：s 证明：① p 前提引入②④→s,p⌝p∨q 前提引入⌝q∨r 前提引入③ q ①②析取三段论⑤ r ③④析取三段论⑥15、在自然推理系统P中用附加前提法证明下面推理：（2）前提：(p∨q)→(r∧s),(s∨t)→u 结论：r→s 前提引入⑦ s ⑤⑥假言推理p→u证明：用附加前提证明法。

① p 附加前提引入②③④⑥⑦p∨q ①附加(p∨q)→(r∧s) 前提引入r∧s ②③假言推理⑤ s ④化简s∨t ⑤附加(s∨t)→u 前提引入⑧ u ⑥⑦假言推理故推理正确。

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 是素数.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.p q A =p→q B =p⌝∧q⌝(A∨B)⌝A⌝∧B0 0 1 0 0 00 1 1 0 0 01 0 0 1 0 01 1 1 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, 111p q r←p ∍ ←q (p∍r0 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 1 11 1 0 0 0 0 0 01 1 1 0 0 0 1 12.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, 为重言式.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∧M62.8. 略2.9. 用真值表求下面公式的主析取范式.(2) (p→q) → (p⌝↔q)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. 于是(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).2.16. 用主析取范式判断下列公式是否等值:(1)(p→q) →r 与q→ (p→r)(2) ⌝ (p∧q)与⌝ (p∨q)(1)(p→q) →r) ⇔m1∨m3∨m4∨m5∨m7q→ (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) →r2.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.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) (已为{⌝, →,↔}中公式)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.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)证明:①②p→(q→r)p前提引入前提引入③④q→rq①②假言推理前提引入⑤r③④假言推理⑥r∨s⑤附加律(2)证明:①②③⌝ (q∧r)⌝q∨⌝rr前提引入①置换前提引入④⑤⑥⌝qp→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→st∧rt前提引入①置换②化简前提引入④化简⑥s③⑤假言推理⑦⑧⑨⑩q⇒s(s→q) ∧ (q→s)s→qq前提引入⑦置换⑧化简⑥⑥假言推理○11 q →p前提引入○12 ○13 pp∧q⑩○11 假言推理⑩○12 合取(5)证明:①②p→rq→s前提引入前提引入③④p∧qp前提引入③化简⑤q③化简⑥r①④假言推理⑦s②⑤假言推理⑧r∧s⑥⑦合取(6)证明:①②t⌝p∨r附加前提引入前提引入③④p∧qp前提引入③化简⑤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)证明:①②ss→p附加前提引入前提引入③p①②假言推理④⑤⑥p→ (q→r)q→rq前提引入③④假言推理前提引入⑦r⑤⑥假言推理(2)证明:①②Pp∨q附加前提引入①附加③(p∨q) → (r∧s) 前提引入④⑤r∧sS②③假言推理④化简⑥⑦⑧s∨t(s∨t) →uu⑤附加前提引入⑥⑦假言推理3.16.在自然推理系统P 中用归谬法证明下面推理:(1)前提: p→⌝q, ⌝r∨q, r∧⌝s结论: ⌝p(2)前提: p∨q, p→r, q→s结论: r∨s(1)证明:①②Pp→⌝q结论否定引入前提引入③④⑤⑥⑦⌝q⌝r∨q⌝rr∧⌝sr①②假言推理前提引入③④析取三段论前提引入⑥化简⑧⌝r∧r⑤⑦合取⑧为矛盾式, 由归谬法可知, 推理正确.(2)证明:①⌝ (r∨s)结论否定引入②p∨q前提引入③p→r前提引入④q→s前提引入⑤r∨s②③④构造性二难⑥⌝ (r∨s) ∧ (r∨s)①⑤合取①②③④⑤⑥⑦pp q(rq(rss ←q←qr①②假言推理前提引入前提引入⑥为矛盾式, 所以推理正确.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; 结论: r.证明:①⌝s 前提引入②q → s 前提引入③⌝q ①②拒取④p 前提引入⑤p⌝∧q ③④合取⑥p⌝∧q → r 前提引入⑦r ⑤⑥假言推理3.18.在自然推理系统P 中构造下面推理的证明.(1)如果今天是星期六, 我们就要到颐和园或圆明园去玩. 如果颐和园游人太多, 我们就不去颐和园玩.今天是星期六. 颐和园游人太多. 所以我们去圆明园玩.(2)如果小王是理科学生, 他的数学成绩一定很好. 如果小王不是文科生, 他必是理科生. 小王的数学成绩不好. 所以小王是文科学生.(3)明天是晴天, 或是雨天；若明天是晴天, 我就去看电影；若我看电影, 我就不看书. 所以, 如果我看书,则明天是雨天.(1)令p: 今天是星期六; q: 我们要到颐和园玩; r: 我们要到圆明园玩; s:颐和园游人太多.前提: p→ (q∨r), s → ⌝q, p, s.结论: r.前提引入前提引入p p→q∨rq∨rs s → ⌝q⌝qr④⑤假言推理(1)的证明树③⑥析取三段论① p →r 前提引入 ② ⌝r 前提引入 ③ ⌝p ①②拒取式 ④ ⌝q →p 前提引入 ⑤q③④拒取式(2) 令 p : 小王是理科生, q : 小王是文科生, r : 小王的数学成绩很好. 前提: p →r , ⌝q →p , ⌝r 结论: q 证明:⌝qp →q⌝p⌝r →p(2)的证明树 r(3)令 p : 明天是晴天, q : 明天是雨天, r : 我看电影, s : 我看书. 前提: p ∨q , p →r , r →⌝s结论: s →q 证明:① ② s r →⌝s 附加前提引入 前提引入 ③ ⌝r ①②拒取式 ④ p →r 前提引入 ⑤ ⌝p ③④拒取式 ⑥ p ∨q 前提引入 ⑦q⑤⑥析取三段论习题四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).0量词顺序不可随意调换.(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<y, x,y∈D I. 说明下列公式在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<y→x≠y), 真值为1.(2) ∀x∀y((x-y=0) →x<y), 真值为0.(3) ∀x∀y((x<y) → (x-y≠0)), 真值为1.(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))(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<y在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)).习题五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≤3F(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)(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) ⇔15.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))).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)①∃xF(x) → ∀y((F(y) ∨ G(y)) → R(y)) 前提引入②∃xF(x) 前提引入③∀y((F(y) ∨ G(y)) → R(y)) ①②假言推理④(F(c) ∨ G(c)) → R(c) ③UI⑤F(c) ①EI⑥F(c) ∨ G(c) ⑤附加⑦⑧R(c)∃xR(x)④⑥假言推理⑦EG(2) 证明:①∃xF(x) 前提引入②F(c) ①EI③∀x(F(x) → (G(a) ∧ (R(x))) 前提引入④F(c) → (G(a) ∧R(c)) ④UI⑤G(a) ∧R(c) ②④假言推理⑥R(c) ⑤化简⑦F(c) ∧R(c) ②⑥合取⑧∃x(F(x) ∧R(x)) ⑥E G(3) 证明:①⌝∃xG(x) 前提引入②∀x⌝G(x) ①置换③⌝G(c)②UI④∀x(F(x) ∨G(x) 前提引入⑤F(c) ∨G(c) ④UI⑥F(c) ③⑤析取三段论⑦∃xF(x) ⑥E G(4) 证明:①∀x(F(x) ∨G(x)) 前提引入②F(y) ∨G(y) ①UI③∀x(⌝G(x) ∨⌝R(x)) 前提引入④⌝G(y) ∨⌝R(y)③UI⑤∀xR(x) 前提引入⑥R(y) ⑤UI⑦⌝G(y) ④⑥析取三段论⑧F(y) ②⑦析取三段论⑥∀xF(x) U G5.16.略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) →R(x)), ∃x(F(x) ∧G(x))结论: ∃x(R(x) ∧G(x))证明:①∃x(F(x) ∧G(x)) 前提引入②F(c) ∧G(c) ①EI③F(c) ②化简④G(c) ②化简⑤∀x(F(x) →R(x)) 前提引入⑥F(c) →R(c) ⑤UI⑦R(c) ③⑥假言推理⑧R(c) ∧G(c) ④⑦合取⑥∃x(R(x) ∧G(x)) ⑧EG(2)设: F(x):x 为有理数, G(x):x 为无理数, R(x)为实数, H(x)为虚数前提: ∀x((F(x) ∨G(x)) →R(x)), ∀x(H(x) →⌝R(x))结论: ∀x(H(x) → (⌝F(x) ∧⌝G(x)))证明:①∀x((F(x) ∨G(x) →R(x)) 前提引入②F(y) ∨G(y)) →R(y) ①UI③∀x(H(x) →⌝R(x)) 前提引入④H(y) →⌝R(y)③UI⑤⌝R(y) →⌝ (F(y) ∨G(y)) ②置换⑥H(y) →⌝ (F(y) ∨G(y)) ④⑤假言三段论⑦H(y) → (⌝F(y) ∧⌝G(y)) ⑥置换⑧∀x(H(x) → (⌝F(x) ∧⌝G(x)))⑦UG(3)设: F(x):x 能表示成分数, G(x):x 为无理数, H(x)为有理数前提: ∀x(G(x) →⌝F(x)), ∀x(H(x) →F(x))结论: ∀x(H(x) →⌝G(x))证明:①∀x(H(x) →F(x)) 前提引入②H(y) →F(y) ①UI③∀x(G(x) →⌝F(x)) 前提引入④G(y) →⌝F(y)③UI⑤F(y) →⌝G(y) ④置换⑥H(y) →⌝G(y) ②⑤假言三段论⑦∀x(H(x) →⌝G(x))⑥UG5.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) ①UI③∃x⌝H(x) 前提引入④⌝H(c) ③UI⑤G(c) ②④析取三段⑥∀x(F(x) → ⌝G(x)) 前提引入⑦F(c) → ⌝G(c) ⑥UI⑧⌝F(c) ⑤⑦拒取⑨∃x⌝F(x) ⑧EG5.25.略习题六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<x<12}(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) ⊆G6.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}}}(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.略习题七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∈BA=B7.6. 列出从集合A={1, 2}到B={1}的所有的二元关系.R1=∅ ,R2={〈1,1〉},R2={〈2,1〉},R3={〈1,1〉,〈2,1〉}.7.7. 列出集合A={2, 3, 4}上的恒等关系I A, 全域关系E A, 小于或等于关系L A, 整除关系D A.I A={〈2,2〉,〈3,3〉,〈4,4〉}E A=A×A={〈2,2〉,〈2,3〉,〈2,4〉,〈3,2〉,〈3,3〉,〈3,4〉,〈4,2〉,〈4,3〉,〈4,4〉}L A={〈2,2〉,〈2,3〉,〈2,4〉,〈3,3〉,〈3,4〉,〈4,4〉}D A={〈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〉}=E A-{〈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〉}7.10.略7.11.R i 是X 上的二元关系, 对于x∈X 定义集合R i(x)={y|xR i y}.显然Ri(x) ⊆X. 如果X={-4, -3, -2, -1, 0, 1, 2, 3, 4}, 且令R1={〈x, y〉|x, y∈X∧x<y}R2={〈x,y〉|x, y∈X∧y-1<x<y+2}R3={〈x,y〉|x, y∈X∧x2≤y}求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, dom A, dom(A∪B), ran A, ran B, ran(A∩B), fld(A-B).A∪B={〈1,2〉, 〈1,3〉, 〈2,4〉, 〈3,3〉, 〈4,2〉}A∩B={〈2,4〉}dom A={1,2,3}dom(A∪B)={1,2,3,4}r an A={2,3,4}r an B={3,4,2}r an(A∩B)={4}fld(A-B)={1,2,3}7.14.设R={〈0,1〉,〈0,2〉,〈0,3〉,〈1,2〉,〈1,3〉,〈2,3〉}求R○R,R-1 ,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.设A={〈∅,{∅,{∅}}〉,〈{∅},∅〉}求A-1,A2,A3,A†{∅},A[∅],A†∅,A†{{∅}},A[{{∅}}].A-1={〈{∅,{∅}},∅〉,〈∅,{∅}〉},A2={〈{∅},{∅,{∅}}〉},A3=∅,A†{∅}={〈∅,{∅,{∅}}〉},A[∅]={∅,{∅}},1 2A †∅=∅,A †{{∅}}={〈{∅},∅〉}, A [{{∅}}]=∅7.16.设 A ={a ,b ,c ,d }, R 1,R 2 为 A 上的关系, 其中R 1={〈a ,a 〉,〈a ,b 〉,〈b ,d 〉} R 2={〈a ,d 〉,〈b ,c 〉,〈b ,d 〉,〈c ,b 〉} 2 3求 R 1○R 2, R 2○R 1,R 1 ,R 2 .R 1○R 2={〈a ,a 〉,〈a ,c 〉,〈a ,d 〉}, R 2○R 1={〈c ,d 〉}, R 2={〈a ,a 〉,〈a ,b 〉,〈a ,d 〉}, R 3={〈b ,c 〉,〈b ,d 〉,〈c ,b 〉}237.17.设 A ={a ,b ,c }, 试给出 A 上两个不同的关系 R 1 和 R 2,使得 R 1 =R 1, R 2 =R 2.R 1={〈a ,a 〉,〈b ,b 〉}, R 2={〈b ,c 〉,〈c ,b 〉}7.18.证明定理 7.4 的(1), (2), (4).(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 ○F7.19.证明定理 7.5 的(2), (3).(2) F [A ∪B ]=F [A ]∪F [B ]任取 y ,。

《离散数学》教学大纲（Discrete Mathematics）适用专业：电子信息类课程类别：学科基础课课程学时：48课程学分：3.0先修课程：高等数学、线性代数等一、课程简介离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支，是计算机科学中基础理论的核心课程，是计算机科学与技术的支撑学科。

它在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能与机器人、数据库、网络、计算机图形学、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握离散结构的描述工具和处理方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

二、教学目的与任务离散数学是一门培养学生缜密思维、严格推理，具有综合归纳分析能力的课程。

通过本课程的学习，使学生有一定的严格逻辑推理与抽象思维能力，掌握离散量的处理及运算技能，能够将离散数学应用到解决计算机技术中的实际问题中。

不仅能为学生奠定计算机科学的专业基础，并且能为将后续课程的学习及将来开发软、硬件技术及研究、应用提供有力的工具。

三、课程内容第1章命题逻辑的基本概念1.1命题与联结词1.2命题公式及其赋值第2章命题逻辑等值演算2.1等值式2.2析取范式与合取范式* 2.3联结词的完备集* 2.4可满足性问题与消解法第3章命题逻辑的推理理论3.1推理的形式结构3.2自然推理系统P3.3消解证明法第4章一阶逻辑基本概念4.1一阶逻辑命题符号化4.2一阶逻辑公式及其解释第5章一阶逻辑等值演算与推理5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式* 5.3一阶逻辑的推理理论第6章集合代数6.1集合的基本概念6.2集合的运算6.3有穷集的计数6.4集合恒等式第7章二元关系7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质7.5关系的闭包7.6等价关系与划分7.7偏序关系第8章函数8.1函数的定义与性质8.2函数的复合与反函数* 8.3双射函数与集合的基数* 8.4一个电话系统的描述实例第14章图的基本概念14.1图14.2通路与回路14.3图的连通性14.4图的矩阵表示* 14.5图的运算第15章欧拉图与哈密顿图15.1欧拉图15.2哈密顿图15.3最短路问题、中国邮递员问题与货郎担问题第16章树16.1无向树及其性质16.2生成树16.3根树及其应用三、课程学时分配、教学内容与教学基本要求四、教学方法与教学手段说明该课程教学方式主要有：课堂教学、交互学习、课后作业。

第一章命题逻辑基本概念课后练习题答案1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.4.因为p与q不能同时为真.5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.返回第二章命题逻辑等值演算本章自测答案5.(1)：∨∨,成真赋值为00、10、11；(2)：0，矛盾式，无成真赋值；(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；(2)：∨⇔∨∨∨∨∨∨；(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；(2)：∨∨∨∨∨∨∨⇔1；(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ⇒ q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*2)可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(p→q)∧q→p⇔(┐p∨q) ∧q →p⇔q →p⇔┐p∨┐q⇔⇔∨∨从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为(p→q┐)∧(r→q)→(r→┐p) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(p→┐q)∧(r→q)→(r→┐p)⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)⇔(p∨q)∨(┐p∧r)∨┐q∨┐r⇔(┐p∨q)∨(┐q∧┐r)⇔┐p∨(q∨┐q)∧┐r⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(p→q)∧┐p→(┐q∧┐r)⇔(┐p∨q) ∧┐p→(┐q∧┐r)⇔┐p→(┐q∧┐r) (使用了吸收律)⇔p∨(┐q∧┐r)⇔∨∨∨由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明① p→(q→r)前提引入② P前提引入③ q→r①②假言推理④ q前提引入⑤ r③④假言推理⑥ r∨s前提引入（2）证明：① ┐(p∧r)前提引入② ┐q∨┐r①置换③ r前提引入④ ┐q ②③析取三段论⑤ p→q前提引入⑥ ┐p④⑤拒取式（3）证明：① p→q前提引入② ┐q∨q①置换③ (┐p∨q)∧(┐p∨p) ②置换④ ┐p∨(q∧p③置换⑤ p→(p∨q) ④置换15.(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⑥⑦拒取式16.(1)证明：① p结论否定引入② p→ ┐q前提引入③ ┐q ①②假言推理④ ┐r∨q前提引入⑤ ┐r③④析取三段论⑥ r∧┐s前提引入⑦ r⑥化简⑧ ┐r∧r⑤⑦合取（2）证明：① ┐(r∨s)结论否定引入② ┐r∨┐s①置换③ ┐r②化简④ ┐s②化简⑤ p→r前提引入⑥ ┐p③⑤拒取式⑦ q→s前提引入⑧ ┐q④⑦拒取式⑨ ┐p∧┐q⑥⑧合取⑩ ┐(p∨q)⑨置换口p∨q前提引入⑾①口┐(p∨q) ∧(p∨q) ⑩口合取17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。

第一章部分课后习题参考答案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⇔117．判断下面一段论述是否为真：“π是无理数。

并且，如果3是无理数，则2也是无理数。

另外6能被2整除，6才能被4整除。

”答：p: π是无理数 1q: 3是无理数0r: 2是无理数 1s:6能被2整除 1t: 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 10 1 1 0 1 1 11 0 0 1 0 0 11 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 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 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)⇔⌝(p ∨q)∨(⌝q ∨p)⇔(⌝p ∧⌝q)∨(⌝q ∨p)⇔ (⌝p ∧⌝q)∨(⌝q ∧p)∨(⌝q ∧⌝p)∨(p ∧q)∨(p ∧⌝q)⇔ (⌝p ∧⌝q)∨(p ∧⌝q)∨(p ∧q)⇔320m m m ∨∨⇔∑(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) ⇔ M 1⇔∏(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.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x): 2=(x+)(x).G(x): x+5=9.(1)在两个个体域中都解释为)∀，在（a）中为假命题，在(b)中为真命题。

离散数学与其他学科之间的联系摘要：离散数学，又称为组合数学。

离散数学是计算机出现以后迅速发展起来的一门数学分支。

计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。

离散数学的发展改变了传统数学中分析和代数占统治地位的局面。

它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

关键词：离散数学电路设计软件技术人工智能应用等1、离散数学的相关介绍1.1离散数学的简介离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。

它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此离散数学可以充分描述计算机学科离散性的特点。

由于离散数学在计算机科学中的重要作用，国内外几乎所有大学的计算机类专业的教学计划中都将其列为核心课程进行重点建设，它是其他骨干课程，如数据结构、操作系统、人工智能、计算机网络、软件工程、编译原理等的先修课程，国内许多大学将其作为计算机专业类研究生入学考试的内容。

1.2离散数学的发展20世纪的计算机出现，带动了世界性的信息革命的伟大进程。

计算机科学在信息革命中的学科地位有如牛顿力学在工业革命中的学科地位一样，由计算机出现带动的信息革命当然计算机科学将起着主导的作用。

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

第一章命题逻辑基本概念课后练习题答案1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.4.因为p与q不能同时为真.5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.返回第二章命题逻辑等值演算本章自测答案5.(1)：∨∨,成真赋值为00、10、11；(2)：0，矛盾式，无成真赋值；(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；(2)：∨⇔∨∨∨∨∨∨；(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；(2)：∨∨∨∨∨∨∨⇔1；(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ⇒ q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*2)可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(p→q)∧q→p⇔(┐p∨q) ∧q →p⇔q →p⇔┐p∨┐q⇔⇔∨∨从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为(p→q┐)∧(r→q)→(r→┐p) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(p→┐q)∧(r→q)→(r→┐p)⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)⇔(p∨q)∨(┐p∧r)∨┐q∨┐r⇔(┐p∨q)∨(┐q∧┐r)⇔┐p∨(q∨┐q)∧┐r⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(p→q)∧┐p→(┐q∧┐r)⇔(┐p∨q) ∧┐p→(┐q∧┐r)⇔┐p→(┐q∧┐r) (使用了吸收律)⇔p∨(┐q∧┐r)⇔∨∨∨由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明① p→(q→r)前提引入② P前提引入③ q→r①②假言推理④ q前提引入⑤ r③④假言推理⑥ r∨s前提引入（2）证明：① ┐(p∧r)前提引入② ┐q∨┐r①置换③ r前提引入④ ┐q ②③析取三段论⑤ p→q前提引入⑥ ┐p④⑤拒取式（3）证明：① p→q前提引入② ┐q∨q①置换③ (┐p∨q)∧(┐p∨p) ②置换④ ┐p∨(q∧p③置换⑤ p→(p∨q) ④置换15.(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⑥⑦拒取式16.(1)证明：① p结论否定引入② p→ ┐q前提引入③ ┐q ①②假言推理④ ┐r∨q前提引入⑤ ┐r③④析取三段论⑥ r∧┐s前提引入⑦ r⑥化简⑧ ┐r∧r⑤⑦合取（2）证明：① ┐(r∨s)结论否定引入② ┐r∨┐s①置换③ ┐r②化简④ ┐s②化简⑤ p→r前提引入⑥ ┐p③⑤拒取式⑦ q→s前提引入⑧ ┐q④⑦拒取式⑨ ┐p∧┐q⑥⑧合取⑩ ┐(p∨q)⑨置换口p∨q前提引入⑾①口┐(p∨q) ∧(p∨q) ⑩口合取17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。

二元关系传递性的等价定义及其判别法孙凤芝【摘要】通过对二元关系传递性定义的深入分析，突破其原始定义的局限性，给出其等价的定义形式，又由二元关系与矩阵的联系，给出矩形判别法，从而可以方便、快捷地实现二元关系传递性的判定。

%Direct according to definition of transitive binary relation objection within literature [ 1 ] [ 2 ] . Sometimes bad judgment. Based on the binary relation of the definition of transitivity in-depth analysis, breakthrough the limitations of its original definition, this paper presents the definition of its equivalence form. And because binary relationship is linked with Matrix. Diagnostic method of the rectangle is given. Thus we can quickly and easily implement transitive binary relation of determination.【期刊名称】《大庆师范学院学报》【年(卷),期】2014(000)006【总页数】4页(P45-48)【关键词】二元关系;传递性;矩形判别法【作者】孙凤芝【作者单位】大庆师范学院教师教育学院，黑龙江大庆163712【正文语种】中文【中图分类】O158二元关系是离散数学中重要的基本概念,实际判定某个二元关系性质时,自反性、反自反性、对称性的判定比较容易,而传递性的判定有时则较困难,是学习的重点,也是难点。