數(shù)理邏輯練習題及答案-5

一階邏輯等值式與置換規(guī)則

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．構(gòu)造下面推理的證明：

19.

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

21．結(jié)論：x(F(x)∧R(x))

22.

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

24．結(jié)論：xF(x)

25.

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

27．結(jié)論：xF(x)

28．證明下面推理：

29.

30．(1)每個有理數(shù)都是實數(shù)，有的有理數(shù)是整數(shù)，因此有的實數(shù)是整數(shù)。

31.

32．(2)有理數(shù)、無理數(shù)都是實數(shù)，虛數(shù)不是實數(shù)，因此虛數(shù)既不是有理數(shù)、

也不是無理數(shù)。

33.

34．(3)不存在能表示成分數(shù)的無理數(shù)，有理數(shù)都能表示成分數(shù)，因此有理數(shù)

都不是無理數(shù)。

答案

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為有理數(shù)，R(x):x為實數(shù)，G(x):x是整數(shù)。

前提：x(F(x)→R(x))，x(F(x)∧G(x))

結(jié)論：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為有理數(shù)，G(x):x為無理數(shù)，R(x)為實數(shù)，H(x)為虛數(shù)

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

結(jié)論：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能表示成分數(shù)，G(x):x為無理數(shù)，H(x)為有理數(shù)

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

結(jié)論：x(H(x)→┐G(x))

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

②H(y)→F(y)