数理逻辑练习题及答案-5

一阶逻辑等值式与置换规则

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