离散数学(屈婉玲版)第二章习题答案
- 格式:doc
- 大小:191.00 KB
- 文档页数:5
2.13 设解释I为:个体域D I ={-2,3,6},一元谓词F(X):X≤3,G(X):X>5,R(X):X≤7。在I下求下列各式的真值。
(1)∀x(F(x)∧G(x))
解:∀x(F(x)∧G(x))
⇔(F(-2) ∧G(-2)) ∧(F(3) ∧G(3)) ∧(F(6) ∧G(6))
⇔((-2≤3) ∧(-2>5)) ∧((3≤3) ∧(3>5)) ∧((6≤3) ∧(6<5))
⇔((1 ∧0))∧((1 ∧0)) ∧((0 ∧0))
⇔0∧0∧0
⇔0
(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)
⇔((-2≤7) →(-2≤3))∧ (( 3≤7) →(3≤3))∧ (( 6≤7) →(6≤3)) ∨ (5>5)
⇔(1 →1)∧ (1 →1)∧ (1→0) ∨ 0
⇔1∧ 1∧ 0 ∨ 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))
⇔((-2≤3) ∨ (-2>5)) ∨ ((3≤3) ∨ (3>5)) ∨ ((6≤3) ∨ (6>5))
⇔(1 ∨ 0) ∨ (1 ∨ 0) ∨ (0 ∨ 1)
⇔1 ∨ 1 ∨ 1
⇔1
2.14 求下列各式的前束范式,要求使用约束变项换名规则。
(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.1(2 )
⇔∃x(⌝F(x)→∀yG(z,y) 定理2.2(2)③
⇔∃x∀y(⌝F(x)→G(z,y)) 定理2.2(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))
2.15 求下列各式的前束范式,要求使用自由变项换名规则。(代替规则)
(1)∀xF(x)∨∃yG(x,y)
⇔∀xF(x)∨∃yG(z,y) 代替规则
⇔∀x(F(x)∨∃yG(z,y))定理2.2(1)①
⇔∀x∃y(F(x)∨G(z,y))定理2.2(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) 定理2.2(1)②⇔∀x(∀y (F(x)∧G(x,y,t))→∃zH(s,r,z))定理2.2(2)③⇔∀x∃y((F(x)∧G(x,y,t))→∃zH(s,r,z))定理2.2(1)③⇔∀x∃y∃z((F(x)∧G(x,y,t))→H(s,r,z))定理2.2(2)④
2.17构造下面推理的证明。
(1)前提:∃xF(x)→∀y((F(y)∨G(y))→R(y))
∃xF(x)
结论:∃xR(x)
应改为:①∃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
2.18在一阶逻辑中构造下面推理的证明。
大熊猫都产在中国,欢欢是大熊猫。所以,欢欢产在中国。
解:将命题符号化.
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) ②③假言推理
2.19在一阶逻辑中构造下面推理的证明。
有理数都是实数,有的有理数是整数。因此,有的实数是整数。
设全总个体域为数的集合
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规则
2.23一阶逻辑中构造下面推理的证明。
每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行(个体域为人类集合)。
命题符号化: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