资源描述
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+24当且仅当3+36. (2)2+24的充要条件是3+36. (3)2+24与3+36互为充要条件. (4)若2+24, 则3+36, 反之亦然. (1)pq, 其中, p: 2+24, q: 3+36, 真值为1. (2)pq, 其中, p: 2+24, q: 3+36, 真值为0. (3) pq, 其中, p: 2+24, q: 3+36, 真值为0. (4) pq, 其中, p: 2+24, q: 3+36, 真值为1. 将下列命题符号化, 并给出各命题的真值: (1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令 p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) pq 1. (2) qp 1. (3) pq 1. (4) pr当p 0时为真; p 1 时为假. 将下列 命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 4 (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: 他乘班车上班. (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是素数. 设p: 2+3=5. q: 大熊猫产在中国. r: 复旦大学在广州. 求下列复合命题的真值: (1)(pq) r (2)(r (pq) p (3) r (pqr) (4)(pqr) ( pq) 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) 5 (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+24, 则地球是运动不止的. (3)若地球上没有树木, 则人类不能生存. (4)若地球上没有水, 则3是无理数. (1)pq, 其中, p: 2+24, q: 地球静止不动, 真值为0. (2)pq, 其中, p: 2+24, q: 地球运动不止, 真值为1. (3) pq, 其中, p: 地球上有树木, q: 人类能生存, 真值为1. (4) pq, 其中, p: 地球上有水, q: 3是无理数, 真值为1. 6 习题二 2.1. 设公式 A = pq, B = pq, 用真值表验证公式 A 和 B 适合德摩根律: (AB) AB. A =pq B =pq (AB) AB0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 因为(AB)和AB的真值表相同, 所以它们等值. 2.2. 略 2.3. 用等值演算法判断下列公式的类型, 对不是重言式的可满足式, 再用真值表法求出成真赋值. (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, 111 p q pr1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 2.4. 用等值演算法证明下面等值式: (1) p (pq) (pq) (3) (pq) (pq) (pq) (4) (pq) (pq) (pq) (pq) (1) (pq) (pq) p (qq) p 1 p. (3) (pq) 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 7 (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) (pq) qr (3)(p (qr) (pqr) (1)(pq) (qp) (pq) (qp) pq q p pq q p(吸收律) (pp)q p(qq) pq pq pq pq m10 m00 m11 m10 m0 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) p qp p q0 0 M0M1M2M3 这是矛盾式. 成假赋值为 00, 01, 10, 11. (2)M4 , 成假赋值为100. (3)主合取范式为1, 为重言式. 82.7. 求下列公式的主析取范式, 再用主析取范式求合取范式: (1)(pq) r (2)(pq) (qr) (1)m1m3m5m6m7M0M2M4 (2)m0m1m3m7M2M4M5M6 2.8. 略 2.9. 用真值表求下面公式的主析取范式. (2) (pq) (pq) (2)从真值表可见成真赋值为01, 10. 于是(p q) (p q) 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) r pq r pq(rr) (pp) (qq)r pqr pqr pqr pqr pqr pqr = m101 m100 m111 m101 m011 m001 m1 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)(pqr)(pqr) 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 9(pqr)(pqr)(pqr)(pqr) = 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). 两个公式的主吸取范式不同, 所以(pq) r2.16. 用主析取范式判断下列公式是否等值: (1)(pq) r与q (pr) (2) (pq)与 (pq) (1) (pq) r) m1m3m4m5m7 q (pr) m0m1m2m3m4m5m7 所以(pq) r) q (pr) (2) (pq) m0m1m2 (pq) m0 所以 (pq) (pq) 2.17. 用主合取范式判断下列公式是否等值: (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) r 2.18. 略 2.19. 略 q (pr). 2.20. 将下列公式化成与之等值且仅含 , 中联结词的公式. (3) (pq)r. 注意到AB (AB)(BA)和 AB (AB) (AB)以及 AB AB. (pq)r 10 (pq r) (r pq) (pq) r) (r (pq) (pq) r) (r (pq) 注联结词越少, 公式越长. 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 (矛盾式), 有 AC 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)在联结词完备集, 上构造F. (c)在联结词完备集, ,上构造F. (a)由条件(1)-(4)可知, F的主析取范式为 F (pqr) (pqr) (pqr) (pqr) m1m4m3m6 m1m3m4m6 11 (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. 一个排队线路, 输入为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 Am4m5m6m7 p F Bm2m3 pq F Cm1 pqr 2.29. 略 2.30. 略 (已为, 中公式) (已为, 中公式) (已为, 中公式) 12 习题三 3.1. 略 3.2. 略 3.3. 略 3.4. 略 3.5. 略 3.6. 判断下面推理是否正确. 先将简单命题符号化, 再写出前提, 结论, 推理的形式结构(以蕴涵式的形式给 出)和判断过程(至少给出两种判断方法): (1)若今天是星期一, 则明天是星期三；今天是星期一. 所以明天是星期三. (2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一. (3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一. (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 13此形式结构为重言式, 即 (pr) pr 故推理正确. 推理是否正确, 可用多种方法证明. 证明的方法有真值表法, 等式演算法. 证明推理正确还可用构造证明法. 下面用构造证明法证明(6)推理正确. 前提: pr, p 结论: r 证明: pr (pr) (rp) rp 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 (qr), p, q 结论: rs (2)前提: pq, (qr), r 结论: p (3)前提: pq 结论: p (pq) (4)前提: qp, qs, st, tr 结论: pq (5)前提: pr, qs, pq 14 结论: rs (6)前提: pr, qs, pq 结论: t (rs) (1)证明: p(qr) p qr q r rs (2)证明: (qr) qr r q pq p (3)证明: pq pq 前提引入 假言推理 前提引入 假言推理 附加律 前提引入 置换 前提引入 析取三段论 前提引入 拒取式 前提引入 置换 (pq) (pp) p (pq) p (pq) 也可以用附加前提证明法, 更简单些. (4)证明: st (st) (ts) ts tr t s qs (sq) (qs) sq q 化简 假言推理 前提引入 置换 化简 假言推理 15q p 12 p pq 13 (5)证明: pr 前提引入 qs 前提引入 pq 前提引入 化简 p 化简 q 假言推理 11合取 12 r s rs (6)证明: t pr pq p r rs 假言推理 假言推理 合取 附加前提引入 前提引入 前提引入 化简 析取三段论 附加 说明: 证明中, 附加提前t, 前提qs没用上. 这仍是正确的推理. 3.15.在自然推理系统P中用附加前提法证明下面各推理: (1)前提: p (qr), sp, q 结论: sr (2)前提: (pq) (rs), (st) u 结论: pu (1)证明: s sp p p (qr) qr q r 附加前提引入 前提引入 假言推理 前提引入 假言推理 前提引入 假言推理 16 (2)证明: P pq (pq) (rs) rs S st (st) u u 附加前提引入 附加 前提引入 假言推理 化简 附加 前提引入 假言推理 3.16.在自然推理系统P中用归谬法证明下面推理: (1)前提: pq, rq, rs 结论: p (2)前提: pq, pr, qs 结论: rs (1)证明: P pq q rq r rs r rr 结论否定引入 前提引入 假言推理 前提引入 析取三段论 前提引入 化简 合取 为矛盾式, 由归谬法可知, 推理正确. (2)证明: (rs) pq pr qs rs (rs) (rs) 17 为矛盾式, 所以推理正确. 3.17.P53 17. 在自然推理系统 P 中构造下面推理的证明: 只要 A 曾到过受害者房间并且11点以前没用离开, A 就犯了谋杀罪. A 曾到过受害者房间. 如果 A 在11点以前离开, 看门人会看到他. 看门人没有看到他. 所以 A 犯了谋杀罪. 令 p: A 曾到过受害者房间; q: A 在11点以前离开了; r: A 就犯了谋杀罪; s:看门人看到 A. 前提: pq r, p, q s, s. 结论: r. 前提: pq r, p, q s, s; 证明: s 前提引入 q s 前提引入 q 拒取 前提引入 p pq 合取 pq r 前提引入 r 假言推理 结论: r. 3.18.在自然推理系统P中构造下面推理的证明. (1)如果今天是星期六, 我们就要到颐和园或圆明园去玩. 如果颐和园游人太多, 我们就不去颐和园玩. 今天是星期六. 颐和园游人太多. 所以我们去圆明园玩. (2)如果小王是理科学生, 他的数学成绩一定很好. 如果小王不是文科生, 他必是理科生. 小王的数学成 绩不好. 所以小王是文科学生. (3)明天是晴天, 或是雨天；若明天是晴天, 我就去看电影；若我看电影, 我就不看书. 所以, 如果我看书, 则明天是雨天. (1)令 p: 今天是星期六; q: 我们要到颐和园玩; r: 我们要到圆明园玩; s:颐和园游人太多. 前提: p (qr), s q, p, s. 结论: r. p pqr qr s s q q r 前提引入 pqr s q ps 前提引入 qr q 假言推理 前提引入 r前提引入 (1)的证明树 假言推理 析取三段论 18 (2) 令p: 小王是理科生, q: 小王是文科生, r: 小王的数学成绩很好. 前提: pr, qp, r 结论: q 证明: pr qr 前提引入 p 拒取式 p qp 前提引入 (2)的证明树 拒取式 q (3)令p: 明天是晴天, q: 明天是雨天, r: 我看电影, s: 我看书. 前提: pq, pr, rs 结论: sq 证明: 附加前提引入 s rs 前提引入 r 拒取式 pr 前提引入 p 拒取式 pq 前提引入 析取三段论 q pq rpr19 习题四 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, 均有x22=(x+ 2 )(x2 ). (2)存在x, 使得x+5=9. 其中(a)个体域为自然数集合, (b)个体域为实数集合. (1)(a)中, x(x22=(x+ 2 )(x2 ), 真值为1. (b)中, x(F(x) (x22=(x+ 2 )(x2 ), 其中, 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)在北京卖菜的人不全是外地人. 20 (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) xy(F(x) G(y) H(x,y), 其中, F(x): x是火车, G(y): y是轮船, H(x,y):x比y快. (2) xy(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) xy(F(x) G(y) H(x,y) 或xy(F(x) G(y) H(x,y) ), 其中, F(x): x是汽车, G(y): y是火车, H(x,y):x比y慢. 4.6. 略 4.7. 将下列各公式翻译成自然语言, 个体域为整数集 , 并判断各命题的真假. (1) xyz(x y = z); (2) xy(xy = 1). (1) 可选的翻译: “任意两个整数的差是整数.” “对于任意两个整数, 都存在第三个整数, 它等于这两个整数相减.” “对于任意整数 x 和 y, 都存在整数 z, 使得 x y = z.” 选, 直接翻译, 无需数理逻辑以外的知识. 以下翻译意思相同, 都是错的: “有个整数, 它是任意两个整数的差.” “存在一个整数, 对于任意两个整数, 第一个整数都等于这两个整数相减.” “存在整数 z, 使得对于任意整数 x 和 y, 都有 x y = z.” 这3个句子都可以符号化为 zxy(x y = z). 量词顺序不可随意调换. (2) 可选的翻译: 21 “每个整数都有一个倒数.” “对于每个整数, 都能找到另一个整数, 它们相乘结果是零.” “对于任意整数 x, 都存在整数 y, 使得 xy = z.” 选, 是直接翻译, 无需数理逻辑以外的知识. 4.8. 指出下列公式中的指导变元, 量词的辖域, 各个体变项的自由出现和约束出现: (3)xy(F(x, y) G(y, z) xH(x, y, z) xy(F(x, y) G(y, z) ) x H(x, y, z) 前件 xy(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)=xy, x,yD I. (d)特定谓词F(x,y): x=y,G(x,y): xy, x,yD I. 说明下列公式在I下的含义, 并指出各公式的真值: (1) xy(G(x,y) F(x,y) (2) xy(F(f(x,y),a) G(x,y) (3) xy(G(x,y) F(f(x,y),a) (4) xy(G(f(x,y),a) F(x,y) (1) xy(xyxy), 真值为1. (2) xy(xy=0) xy), 真值为0. (3) xy(xy) (xy0), 真值为1. (4) xy(xy0) (x=y), 真值为0. 4.10.给定解释I如下: (a)个体域D=(为自然数). (b)D中特定元素a=2. (c)D上函数f (x,y)=x+y,g (x,y)=xy. (d)D上谓词F (x,y): x=y. 说明下列公式在I下的含义, 并指出各公式的真值: (1) xF(g(x,a),x) (2) xy(F(f(x,a),y) F(f(y,a),x) (3) xyz(F(f(x,y),z) (4) xF(f(x,x),g(x,x) 22 (1) x(x2=x), 真值为0. (2) xy(x+2=y) (y+2=x), 真值为0. (3) xyz(x+y=z),真值为1. (4) x(x+x=xx),真值为1. 4.11.判断下列各式的类型: (1) F(x, y) (G(x, y) F(x, y). (3) xyF(x, y) xyF(x, y). (5) xy(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) xy(F(x) G(y) H(x,y) (1) 取个体域为全总个体域. 解释I1 : F(x): x为有理数, G(y): y为整数, H(x,y): xy 在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). 23习题五 5.1. 略 5.2. 设个体域D=a,b,c, 消去下列各式的量词: (1) xy(F(x) G(y) (2) xy(F(x) G(y) (3) xF(x) yG(y) (4) x(F(x,y) yG(y) (1) xy(F(x) G(y) xF(x) yG(y) (F(a) F(b) F(c) (G(a) G(b) G(c) (2) xy(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):x2,G(x):x3 F(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):x0 则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. 24试求下列公式在I下的真值: (1) xyF(x,y) (2) xyF(x,y) (3) xy(F(x,y) F(f(x),f(y) (1) xyF(x,y) (F(3,3) F(3,4) (F(4,3) F(4,4) (01) (10) 1 (2) xyF(x,y) (F(3,3) F(3,4) (F(4,3) F(4,4) (01) (10) 0 (3) xy(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) (00) (11) (11) (00) 1 5.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 是对顶角. 符合化为: xy(F(x) F(y) H(x, y) L(x, y) xy(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) 25 xy(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)
展开阅读全文