离散数学作业
作业11——第3章谓词逻辑
1. 符号化下列命题并推证其结论。

每个大学生不是文科学生就是理工科学生，小张不是理工科学生，因此如果小张是大学生，则他就是文科生。

解：a：小张；M(x):x是大学生；F(x): x是文科生；G(x): x是理工科学生，则符号化为
(x)(M(x)F(x)∨G(x))，┐G(a)M(a) F(a)
(1) M(a) P（附加前提）
(2) (x)(M(x)F(x)∨G(x)) P
(3) M(a)F(a)∨G(a) (2),US
(4) ┐M(a)∨F(a)∨G(a) (3),等值演算
(5) F(a)∨G(a) (1),(4),析取三段论
(6) ┐G(a) P
(7) F(a) (5),(6),析取三段论
(8) M(a) F(a) (1),(7),CP规则
注：也可采用直接证法。

2. 符号化下列命题并推证其结论。

所有的主持人都是有风度的，黎明既是学生又是主持人，所以有一些学生是有风度的。

解：S(x): x是学生；Z(x): x是主持人；F（x）：x是有风度的；a：黎明。

(x)(Z(x)F(x))，S(a)Z(a)(x) (S(x)F(x))
(1) (x)(Z(x)F(x)) P
(2) Z(a)F(a) (1),US
(3) S(a)Z(a) P
(4) S(a) (3),化简
(5) Z(a) (3),化简
(6) F(a) (2),(5),假言推理
(7) S(a)F(a) (4),(6),合取引入
(8) (x) (S(x)F(x)) （7），EG
3．在一阶谓词逻辑中构造下面推理的证明。

前提：(x)(F(x)∨G(x))，(x)(F(x)→H(x))，
结论：(x)(H(x)→G(x))。

证明：反证法
(1)(x)(H(x)→G(x)) 附加前提
(2)(x)(H(x)→G(x)) (1),量词否定等值式
(3)(H(c)→G(c)) (2), ES
(4)(H(c) ∨G(c)) (3), 等值演算
(5)H(c)G(c) (4), 等值演算
(6)H(c) （5），化简
(7)G(c) （5），化简
(8)(x)(F(x)∨G(x)) P
(9)F(c)∨G(c) （8），US
(10)F(c) （7），（9），析取三段论
(11)(x)(F(x)→H(x)) P
(12)F(c)→H(c) （11），US
(13)H(c) （10），（12），假言推理
(14)H(c)H(c) （6），（13），合取引入注：也可采取直接证法。