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