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

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

1．设个体域D={a,b,c}，消去下列各式的量词：

2.

3．(1)xy(F(x)∧G(y))

4．(2)xy(F(x)∨G(y))

5.

6．(3)xF(x)→yG(y)

7.

8．(4)x(F(x,y)→yG(y))

9．设个体域D={1,2}，请给出两种不同的解释I和I，使得下面公式在I下都是真命

121

题，而在I下都是假命题。

2

10.

11．(1)x(F(x)→G(x))

12．(2)x(F(x)∧G(x))

13．给定解释I如下：

14.

15．(a)个体域D={3,4}。

16．(b)(x)为(3)=4，(4)=3。

17．(c)(x,y)为(3,3)=(4,4)=0，(3,4)=(4,3)=1。

试求下列公式在I下的真值：

(1)xyF(x,y)

(2)xyF(x,y)

(3)xy(F(x,y)→F(f(x),f(y)))

18．构造下面推理的证明：

19.

20．(1)前提：x(F(x)→(G(a)∧R(x)))，xF(x)

21．结论：x(F(x)∧R(x))

22.

23．(2)前提：x(F(x)∨G(x))，┐xG(x)

24．结论：xF(x)

25.

26．(3)前提：x(F(x)∨G(x))，x(┐G(x)∨┐R(x))，xR(x)

27．结论：xF(x)

28．证明下面推理：

29.

30．(1)每个有理数都是实数，有的有理数是整数，因此有的实数是整数。

31.

32．(2)有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、

也不是无理数。

33.

34．(3)不存在能表示成分数的无理数，有理数都能表示成分数，因此有理数

都不是无理数。

答案

1.

(1)xy(F(x)∧G(y))

xF(x)∧yG(y)

(F(a)∧F(b))∧F(c))∧(G(a)∨G(b)∨G(c))

(2)xy(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)

I:F(x):x≤2,G(x):x≤3

1

F(1),F(2),G(1),G(2)均为真，所以

x(F(x)→G(x))

(F(1)→G(1)∧(F(2)→G(2))为真。

I:F(x)同I,G(x):x≤0

21

则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

(2)

(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)

①ES

③

x(F(x)→(G(a)∧(R(x)))

前提引入

④

F(c)→(G(a)∧R(c))

④US

⑤

G(a)∧R(c)

②④假言推理

⑥

R(c)

⑤化简

⑦

F(c)∧R(c)

②⑥合取

⑧

x(F(x)∧R(x))

⑥EG

5.(1)

证明：①

┐xG(x)

前提引入

②

x┐G(x)

①置换

③

┐G(c)

②US

④

x(F(x)∨G(x))

前提引入

⑤

F(c)∨G(c)

④US

⑥

F(c)

③⑤析取三段论

⑦

xF(x)

⑥EG

(3)

证明：①

x(F(x)∨G(x))

前提引入

②

F(y)∨G(y)

①US

③

x(┐G(x)∨┐R(x))

前提引入

④

┐G(y)∨┐R(y)

③US

⑤

xR(x)

前提引入

⑥

R(y)

⑤US

⑦

┐G(y)

④⑥析取三段论

⑧

F(y)

②⑦析取三段论

⑨

xF(x)

UG

设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)①ES

③F(c)②化简

④G(c)②化简

⑤x(F(x)→R(x))前提引入

⑥F(c)→R(c)⑤US

⑦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)①US

③x(H(x)→┐R(x))前提引入

④H(y)→┐R(y)③US

⑤┐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)))

②置换

④⑤假言三段论

⑥置换

⑦UG

(3)

设：F(x):x能表示成分数，G(x):x为无理数，H(x)为有理数

前提：x(G(x)→┐F(x)),x(H(x)→F(x))

结论：x(H(x)→┐G(x))

证明：①x(H(x)→F(x))前提引入

②H(y)→F(y)