台湾交大离散数学12

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 ,。

2024年4月高等教育自学考试全国统一命题考试离散数学(课程代码 02324)注意事项:1.本试卷分为两部分，第一部分为选择题，第二部分为非选择题。

2.应考者必须按试题顺序在答题卡(纸)指定位置上作答，答在试卷上无效。

3.涂写部分、画图部分必须使用2B铅笔，书写部分必须使用黑色字迹签字笔。

第一部分选择题一、单项选择题:本大题共15小题，每小题2分，共30分。

在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。

1.含有3个命题变元的任一命题公式的指派个数是A.6个B.8个C.9个D.10个2.下列命题公式为矛盾式的是A.P→(P ⋁Q ⋁R)B.¬(Q→P) APC.(P→¬P)→¬PD.(P ⋀¬P)→Q3.含有2个命题变元的命题A是重言式的条件是A的主析取范式含有A.4个小项B.1个小项C.4个大项D.1个大项4.设论域元素为a、b,与∀xR(x) ∧(∋y)S(x) 等价的是A.(R(a) ⋀R(b)) ⋀(S(a) ⋀S(b))B.(R(a) ⋀R(b)) ⋀(S(a) ⋁S(b))C.(R(a) ⋁R(b)) ⋀(S(a) ⋀S(b))D.(R(a) ⋁R(b)) ⋀(S(a) ⋁S(b))5.谓词公式 ∀xF(x) ⋀G(x,y) 中变元x 为A.自由出现B.约束出现C.既不是自由出现也不是约束出现D.既是自由出现也是约束出现6.设论域是正整数,下列谓词公式中值为真的是A.)10(22=+∃∀y x y xB.)10(22=+∃∀y x x yC.)10(22=+∀∀y x y xD.)10(22=+∃∃y x y x7.设A ={a,∅},P(A)是A 的幂集,下列选项中正确的是A.{a}∈ P(A),{a}⊆P(A)B.{{A}}∈P(A),{{a}}⊆P(A)C.{a}∈P(A),{∅}∈P(A)D.{a}∈P(A),{∅}⊆P(A)8.一个8阶简单图的边数最大为A.20B.25C.28D.309.下面关于n 阶树的描述,错误．．的是 A.连通图 B.连通且有n-1条边C.无回路且有n-1条边D.连通且无回路10.R={<0,1>,<1,2>,<2,3>},S={<2,1>,<1,2>,<3,3>},下列正确的是A.ran(R) ⊂ ran(R ∩S)B.ran(S) = ran(R ∪S)C.dom(R) = dom(S)D.dom(R) ∪ dom(S) = ran(R) ∪ ran(S)11.设A={1,2,3},则下列关系中是反自反关系的为A.R={<1,1>,<1,2>}B.R={<1,2>,<3,3>}C.R={<1,2>,<3,2>}D.R={<3,1>,<1,3>,<2,2>}12.设A={a,b,c} ,下列选项中既不是对称也不是反对称的是A.R={<a,a>,<a,b>,<b,a>,<c,b>,<b,c>}B.R={<a,a>，<b,b>}C.R={<a,c>，<a,b>}D.R={<a,c>，<b,b>}13. 设f: R →R,f(x) =⎩⎨⎧<-≥3232x x x ，，;g:R →R,g(x)=x+2,则g ∘f:R →R 是A.单射不满射B.满射不单射C.不单射不满射D.双射14.一个5阶简单图G,保证G 为连通图的最少边数为A.4B.5C.6D.715.下列各集合对于整除关系构成偏序集,不能．．构成格的集合是 A.L 1={1,2,3,4} B.L 2={1,2,3,6}C. L 3={1,3,5,15}D.L 4={1,3,9,81}第二部分 非选择题二、填空题:本大题共10小题，每小题2分，共20分。

交大_离散_期末考卷lisan200704a一、选择题（每题1分，共5分）A. 整数分解B. 背包问题C. 确定图是否是连通的D. 确定图是否有哈密顿回路2. 在离散数学中，下列哪个关系是自反的？A. 小于关系B. 整除关系C. 约等于关系D. 矩阵乘法关系A. R1={(1,1), (2,2), (3,3), (1,2)}B. R2={(1,1), (2,2), (3,3), (2,1)}C. R3={(1,1), (2,2), (3,3), (3,1)}D. R4={(1,1), (2,2), (3,3), (1,3)}A. 一个有6个顶点的完全图B. 一个有5个顶点的环图C. 一个有4个顶点的完全二部图D. 一个有3个顶点的路径图5. 在图论中，一个有n个顶点的树有多少条边？A. nB. n1C. n+1D. 2n二、判断题（每题1分，共5分）1. 离散数学中的图论部分主要研究网络的性质和结构。

（）2. 所有的图都至少有一个哈密顿回路。

（）3. 在一个有向图中，每个顶点的入度等于出度。

（）4. 离散数学中的逻辑部分不涉及命题逻辑和谓词逻辑。

（）5. 欧拉定理可以用来判断一个图是否存在欧拉回路。

（）三、填空题（每题1分，共5分）1. 一个有n个顶点的连通图至少有______条边。

2. 在一个无向图中，如果任意两个顶点都相邻，则称该图为______。

3. 命题“如果今天下雨，那么我不去公园”的逆否命题是“如果我去公园，那么今天______”。

4. 一个集合的幂集是指该集合所有______的集合。

5. 在图论中，两个顶点之间的路径长度是指连接这两个顶点的路径上边的______。

四、简答题（每题2分，共10分）1. 简述什么是离散数学。

2. 解释什么是哈密顿回路。

3. 简述集合的笛卡尔积。

4. 什么是命题逻辑中的蕴含关系？5. 解释什么是图的同构。

五、应用题（每题2分，共10分）1. 给定集合A={1,2,3,4}，求A的所有子集。

习 题 十 二1．一个简单图G 有多少不同的定向图？分析：由于简单图的每条边有两种不同的方向可供选择，因此具有q 条边的无向简单图G 共有2q 个不同的定向图。

解.设),(q p G 是简单图，则G 共有2q 个不同的定向图。

2．简单有向图的基础图一定是简单图吗？分析：有向图的基础图是将有向边变成无向边所得到的无向图，由于在有向图中（u,v ）和(v,u) 是两条不同的边，能含有重边，从而不是简单图。

解：不一定，如右图。

3．设),(q p D 是简单有向图，证明：（1）若D 是强连通图，则)1(-≤≤p p q p （2）若D 是弱连通图，则)1(1-≤≤-p p q p分析：强连通图D 是指D 中任意两个顶点间存在双向的通路，因此D 的基础图G 必含H 回路，一条H 回路的边数至少有p 条边，因此p q ≤；另一方面，由于完全强连通图的边数等于)1(-p p ，因此简单有向图D 的边数)1(-≤p p q 。

弱连通图D 是指D 的基础图是连通图的有向图，根据习题5第16题（1）有具有q 个顶点的连通图的边至少有p-1条，因此q p ≤-1。

证明（1）因D 是强连通图，故D 中任意两个顶点v u ,之间既存在),(v u 通路，又存在有向),(u v 一通路，于是，D 的基础图G 必含H 回路.故p q ≤，又因D 是简单有向图.故D 中任何两个顶点之间最多有二条弧，从而)1(-≤p p q ，故)1(-≤≤p p q p .（２）因D 是弱连通图，故D 的基础图G 是连通的，若G 无回路，则1-=p q ，因此，)1(1-≤≤-p p q p4．设),(q p D 是有向图，证明：∑∑==-+==pi pi i D i Du d q u d11)()(分析：)(v d D +是指有向图D 中顶点v 的出度，即以顶点v 为尾的弧的条数；由于D 中的任一弧恰有一个头和一个尾，因此，每增加一条弧，对D 的所有顶点来说，肯定会增加一个出度，同时也会增加一个入度。

离散数学辅助教材概念分析结构思想与推理证明第一部分集合论刘国荣交大电信学院计算机系离散数学习题解答习题一（第一章集合）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。