一阶逻辑等值式与置换规则
1． 设个体域D={a,b,c}，消去下列各式的量词：
(1) (2) (3) (4)
xF(x)→x(F(x,y)→
yG(y) yG(y))
xx
y(F(x)∧G(y)) y(F(x)∨G(y))
2． 设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命
题，而在I2下都是假命题。
(1) (2)
x(F(x)→G(x)) x(F(x)∧G(x))
3． 给定解释I如下：
(a) 个体域D={3,4}。
(b) (c)
(x)为(3)=4，(4)=3。 (x,y)为
(3,3)=
(4,4)=0，
(3,4)=
(4,3)=1。
试求下列公式在I下的真值： (1) (2) (3)
xxx
yF(x,y) yF(x,y)
y(F(x,y)→F(f(x),f(y)))
4． 构造下面推理的证明：
(1) 前提： 结论：
(2) 前提： 结论：
x(F(x)→(G(a)∧R(x)))，x(F(x)∧R(x))
xF(x)
x(F(x)∨G(x))，┐xF(x)
xG(x)
(3) 前提： 结论：
x(F(x)∨G(x))，xF(x)
x(┐G(x)∨┐R(x))，
xR(x)
5． 证明下面推理：
(1) 每个有理数都是实数，有的有理数是整数，因此有的实数是整数。
(2) 有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不是无理数。
(3) 不存在能表示成分数的无理数，有理数都能表示成分数，因此有理数都不是无理数。
答案 1. (1) (2)
x
y(F(x)∧G(y))
yG(y)
xF(x)∧
(F(a)∧F(b))∧F(c))∧(G(a)∨G(b)∨G(c))
xy(F(x)∨G(y))
yG(y)
xF(x)∨
(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))
2.(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)留给读者自己做。 3.
(1) xyF(x,y) (F(3,3)∨F(3,4))∧(F(4,3)∨F(4,4)) (0∨1)∧(1∨0)1
(2) xyF(x,y) (F(3,3)∧F(3,4))∨(F(4,3)∧F(4,4)) (0∧1)∨(1∧0)0
(3) xy(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
4.(1)
证明: ① 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))
(2)
证明： ① ┐xG(x) ②
x┐G(x)
③ ┐G(c) ④
x(F(x)∨G(x))
⑤ F(c)∨G(c) ⑥ F(c)
⑦
xF(x)
前提引入 ①ES 前提引入 ④US
②④假言推理⑤化简 ②⑥合取 ⑥EG
前提引入 ①置换 ②US 前提引入 ④US
③⑤析取三段论 ⑥EG
(3)
证明：
5.(1)
① x(F(x)∨G(x)) 前提引入 ①US 前提引入 ③US 前提引入 ⑤US
④⑥析取三段论 ②⑦析取三段论 UG
② F(y)∨G(y) ③
x(┐G(x)∨┐R(x))
④ ┐G(y)∨┐R(y) ⑤
xR(x)
⑥ R(y) ⑦ ┐G(y) ⑧ F(y) ⑨
xF(x)
设F(x):x为有理数，R(x):x为实数，G(x):x是整数。 前提： 结论：
x(F(x)→R(x))，x(R(x)∧G(x))
x(F(x)∧G(x))
前提引入 ①ES ②化简 ②化简 前提引入 ⑤US
③⑥假言推理 ④⑦合取 ⑧EG
x(F(x)∧G(x))
证明： ①
(2)
② F(c)∧G(c) ③ F(c) ④ G(c) ⑤
x(F(x)→R(x))
⑥ F(c)→R(c) ⑦ R(c) ⑧ R(c)∧G(c) ⑨
x(R(x)∧G(x))
设：F(x):x为有理数，G(x):x为无理数，R(x)为实数， H(x)为虚数 前提： 结论：
x((F(x)∨G(x))→R(x)),
x(H(x)→┐R(x))
x(H(x)→(┐F(x)∧┐G(x)))
x((F(x)∨G(x)→R(x))
前提引入 ①US 前提引入 ③US ②置换 ④⑤假言三段论 ⑥置换 ⑦UG
证明： ①
(3)
② F(y)∨G(y))→R(y) ③
x(H(x)→┐R(x))
④ H(y)→┐R(y)
⑤ ┐R(y)→┐(F(y)∨G(y)) ⑥ H(y)→┐(F(y)∨G(y)) ⑦ H(y)→(┐F(y)∧┐G(y)) ⑧
x(H(x)→(┐F(x)∧┐G(x)))
设：F(x):x能表示成分数， G(x):x为无理数， H(x)为有理数 前提： 结论：
x(G(x)→┐F(x)),x(H(x)→┐G(x))
x(H(x)→F(x))
前提引入 ①US 前提引入 ③US ④置换
②⑤假言三段论 ⑥UG
x(H(x)→F(x))
证明： ①
② H(y)→F(y) ③
x(G(x)→┐F(x))
④ G(y)→┐F(y) ⑤ F(y)→┐G(y) ⑥ H(y)→┐G(y) ⑦
x(H(x)→┐G(x))