离散数学第二阶段作业（第四第五章）
1.在一阶逻辑中将下列命题符号化:
（1）每个人都有心脏。

令M(x):x是人，H(x):x有心脏。

命题符号化为：∀x(M(x)→H(x)) （2）有的狗会飞。

设D(x)：x是狗，F(x)：x会飞。

命题符号化为：∃x(D(x)∧F(x)) （3）没有不犯错误的人。

设M(x): x是人，F(x):x犯错误，命题符号化为
①┐∃x(M(x)∧┐F(x))
②∀x(M(x)→F(x))
（4）发光的不都是金子。

设L(x)：x是发光的东西，G(x)：x是金子。

命题符号化为
①┐∀x(L(x)→G(x))
②∃x(L(x)∧﹁G(x))
（5）一切人都不一样高。

设F(x):x是人, H(x,y), x与y相同, L(x,y): x与y一样高，
命题符号化为
∀x(F(x)→∀y(F(y)∧⌝H(x,y)→⌝L(x,y)))
或∀x∀y(F(x)∧F(y)∧⌝H(x,y)→⌝L(x,y))
（6）并不是所有的汽车都比火车快。

设F(x):x是汽车, G(y):y是火车, H(x,y):x比y快，
命题符号化为
⌝∀x∀y(F(x)∧G(y)→H(x,y))
或∃x∃y(F(x)∧G(y)∧⌝H(x,y))
7）没有一个自然数大于等于任何自然数。

设 N(x):x 是自然数，G(x,y):x ≥y
命题符号化为：⌝∃x(N(x)∧∀y(N(y)→G(x,y)))
（8）有唯一的偶素数。

设：Q(x):x 是偶数，P(x):x 是素数， E(x,y):x ＝y
命题符号化为： ∃x(Q(x)∧P(x)∧⌝∃y(Q(y)∧P(y)∧⌝E(x,y)))
2.填空：求下列各式的前束范式。

)),()(()),((x xF y t G x F y x y t G y →∀∀⇔∀→∀⇔）（
(2))),()((),(2121211x x G x x H x x F x ⌝∃→→∃
)),()((),(2323211x x G x x H x x F x ⌝∀→→∃⇔
)),()((),(2332411x x G x H x x x F x ⌝→∀→∃⇔
))),()((),((2334121x x G x H x x F x x ⌝→→∀∀⇔
3.在自然数推理系统F 中,构造下面推理的证明:
前提:))())()((()(y R y G y F y x xF →∨∀→∃,)(x xF ∃
结论:∃xR(x)
①)(x xF ∃前提引入
②F(c) ①EI
③))())()((()(y R y G y F y x xF →∨∀→∃前提引入
④))())()(((y R y G y F y →∨∀ ①③假言推理
(1)∀xF (x ) →∀yG (x , y )
⑤(F(c)∨G(c))→R(c)) ④UI
⑥F(c)∨G(c) ②附加
⑦R(c) ⑤⑥假言推理
⑧∃xR(x) ⑦EG
4.在自然推理系统F中，构造下面推理的证明：
实数不是有理数就是无理数，无理数都不是分数，所以，若有分数，则必有有理数（个体域为实数集合）（设F(x):x是有理数，G(x):x是无理数，H(x):x是分数。

）设 F(x):x是有理数，
G(x):x是无理数，
H(x):x是分数。

前提：∀x(F(x)∨G(x))，∀x(G(x)→┐H(x))
结论：∃xH(x)→∃xF(x)
①∃xH(x) 附加前提引入
②∀x(F(x)∨G(x)) 前提引入
③ H(c) ① EI规则
④ F(c)∨ G(c) ② UI规则
⑤∀x(G(x)→┐H(x)) 前提引入
⑥ G(c)→┐H(c) ⑤UI规则
⑦┐G(c) ③⑥拒取式
⑧ F(c) ④⑦析取三段论
⑨∃(x)F(x) ⑧EG规则
3。