离散数学习题解 21
习题五
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≤3
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):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)
22
(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) ?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 是对顶角. 符合化为:
??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))).
23
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)
离散数学习题解
(1)证明:
24
① ?xF(x) ???y((F(y) ??G(y)) ??R(y)) ② ?xF(x)
③ ?y((F(y) ??G(y)) ??R(y)) ④ (F(c) ??G(c)) ??R(c) ⑤ F(c) ⑥ F(c) ??G(c) ⑦ R(c) ⑧ ?xR(x)
前提引入 前提引入 ①②假言推理 ③UI ①EI ⑤附加 ④⑥假言推理 ⑦EG
(2) 证明:
① ?xF(x) ② F(c)
③ ?x(F(x) ??(G(a) ??(R(x))) ④ F(c) ??(G(a) ?R(c)) ⑤ G(a) ?R(c) ⑥ R(c)
⑦ F(c) ?R(c) ⑧ ?x(F(x) ?R(x))
前提引入 ①EI 前提引入 ④UI
②④假言推理 ⑤化简 ②⑥合取 ⑥EG
(3) 证明:
① ??xG(x) ② ?x?G(x) ③ ?G(c)
④ ?x(F(x) ?G(x) ⑤ F(c) ?G(c) ⑥ F(c) ⑦ ?xF(x)
前提引入 ①置换 ②UI 前提引入 ④UI
③⑤析取三段论 ⑥EG
(4) 证明:
① ?x(F(x) ?G(x)) ② F(y) ?G(y)
③?x(?G(x) ??R(x)) ④ ⑤ ⑥ ⑦
?G(y) ??R(y) ?xR(x) R(y) ?G(y)
前提引入 ①UI 前提引入 ③UI 前提引入 ⑤UI
④⑥析取三段论 ②⑦析取三段论 UG
⑧ F(y) ⑥ ?xF(x)
5.16.略