离散数学第二章习题答案
- 格式：doc
- 大小：157.50 KB
- 文档页数：5
设解释I为：个体域D I ={-2,3,6},一元谓词F（X）：X3，G（X）：X>5,R(X):X7。
在I下求下列各式的真值。
（1）x(F(x)G(x))
解：x(F(x)G(x))
(F(-2) G(-2)) (F(3) G(3)) (F(6) G(6))
((-23) (-2>5)) ((33) (3>5)) ((63) (6<5))
((1 0))((1 0)) ((0 0))
000
(2) x(R(x)F(x))G(5)
解：x(R(x)F(x))G(5)
(R(-2)F(-2)) (R(3)F(3)) (R(6)F(6)) G(5)
((-27) (-23)) (( 37) (33)) (( 67) (63)) (5>5)
(1 1) (1 1) (10) 0
1 1 0 0
(3)x(F(x)G(x))
解：x(F(x)G(x))
(F(-2) G(-2)) (F(3) G(3)) (F(6) G(6))
((-23) (-2>5)) ((33) (3>5)) ((63) (6>5))
(1 0) (1 0) (0 1)
1 1 1
1
求下列各式的前束范式，要求使用约束变项换名规则。
（1）⌝∃xF(x)→∀yG(x,y)
(2) ⌝（∀xF(x,y) ∨∃yG(x,y) ）
解：（1）⌝∃xF(x)→∀yG(x,y)
⇔⌝∃xF(x)→∀yG(z,y) 代替规则
⇔∀x⌝F(x)→∀yG(z,y) 定理（2 ）
⇔∃x(⌝F(x) →∀yG(z,y) 定理（2）③
⇔∃x∀y(⌝F(x) →G(z,y)) 定理（1）④
（2）⌝（∀xF(x,y) ∨∃yG(x,y) ）
⇔⌝(∀zF(z,y) ∨∃tG(x,t)) 换名规则
⇔⌝(∀zF(z,y) )∧⌝(∃tG(x,t) )
⇔∃z⌝F(z,y) ∧∀t⌝G(x,z)
⇔∃z (⌝F(z,y) ∧∀t⌝G(x,z))
⇔∃z ∀t(⌝F(z,y) ∧⌝G(x,t))
求下列各式的前束范式，要求使用自由变项换名规则。
（代替规则）（1）xF(x)∨yG(x,y)
xF(x) ∨yG(z,y) 代替规则
x（F(x) ∨yG(z,y)）定理（1）①
x y（F(x) ∨G(z,y)）定理（2）①
（2）x(F(x)∧yG(x,y,z))→zH(x,y,z)
x(F(x)∧yG(x,y,t))→zH(s,r,z) 代替规则
x y (F(x)∧G(x,y,t))→zH(s,r,z) 定理（1）②
x（y (F(x)∧G(x,y,t))→zH(s,r,z)）定理（2）③
x y（(F(x)∧G(x,y,t))→zH(s,r,z)）定理（1）③
x y z（(F(x)∧G(x,y,t))→H(s,r,z)）定理（2）④
构造下面推理的证明。
（1）前提：xF(x)→y((F(y)∨G(y))→R(y))
xF(x)
结论：xR(x)
证明：①xF(x) 前提引入
② F（c） EI
③y((F(y)∨G(y))→R(y))前提引入错了
④F（c）∨G(c) →R(c) UI
⑤F（c）→(F（c）∨G(c) →R(c)) 前提引入错了
⑥F（c）∨G(c) →R(y) 假言推理②⑤
⑦R(c) 假言推理②⑥
xR(x) EG
应改为：①xF(x) 前提引入
②xF(x)→y((F(x)∨G(y))→R(y)) 前提引入
③y((F(x)∨G(y))→R(y)) ①②假言推理
④F（c）①EI
⑤ F（c）∨G(c) →R(c) ③UI
⑥ F（c）∨G(c) ④附加
⑦ R(c) ⑤⑥假言推理
⑧xR(x) ⑦EG
（2）前提：x(F(x)→(G(y) R(x))),xF(x).
结论：x(F(x)R(x)).
证明：
①xF(x) 前提引入
②F(c) ①EI
③x(F(x)→(G(y) R(x))) 前提引入
④F(c)→(G(c) R(c)) ③UI
⑤G(c) R(c) ②④假言推理
⑥R(c) ⑤化简
⑦F(c)R(c) ②⑥合取
⑧x(F(x)R(x)) ⑦EG
在一阶逻辑中构造下面推理的证明。
大熊猫都产在中国，欢欢是大熊猫。
所以，欢欢产在中国。
解：将命题符号化.
F(x):x是大熊猫.
G(x):x产在中国.
a: 欢欢.
前提: ∀x(F(x )→G(x)),F(a),
结论: G(a)
证明:
①∀x(F(x )→G(x)), 前提引入;
②F(a)→G(a) ①uI;
③F(a) 前提引入
④G(a) ②③假言推理
在一阶逻辑中构造下面推理的证明。
有理数都是实数，有的有理数是整数。
因此，有的实数是整数。
设全总个体域为数的集合
F（x）：x是有理数 G（x）：x是实数 H（x）：x是整数
前提：∀x(F(x)→G(x)) ∃x(F(x)∧H(x))
结论：∃x(G(x)∧H(x))
证明：①∃x(F(x)∧H(x)) 前提引入
② F（c）∧H（C）①EI规则
③∀x(F(x)→G(x)) 前提引入
④ F（c）→G（c）③UI规则
⑤ F（c）②化简
⑥ G（c）④⑤假言推理
⑦ H（c）②化简
⑧ G（c）∧H（c）⑥⑦合取
⑨x（G（x）∧H（x））⑧EG规则
一阶逻辑中构造下面推理的证明。
每个喜欢步行的人都不喜欢坐汽车。
每个人或者喜欢坐汽车或者喜欢骑自行车。
有的人不喜欢骑自行车。
因而有的人不喜欢步行（个体域为人类集合）。
命题符号化：F(x): x喜欢步行。
G(x):x喜欢坐汽车。
H(x): x喜欢骑自行车。
前提：x(F(x)→G(x)), x(G(x)∨H(x)),
∃x(H(x)).
结论：∃x(F(x))
证明
a ∃x(H(x)) 前提引入
b H(c)
c x(G(x) ∨H(x)) 前提引入
d G(c) ∨H(c)
e G(c)
f x(F(x)→G(x)) 前提引入
g F(c)→G(c)) f UI
h F(c)
i x(F(x)) h EG
在上述推理中，b后面的推理规则为A,d后面的规则为B,e后用的是由b,d得到的推理规则C，h后用的是由e,g得到的推理规则D.
供选择的答案
A,B,C,D:1 UI 2:EI 3UG 4 EG 5拒取式 6 假言推理 7析取三段论
A为2
B为1
C为7
D为5 ,。
