浙江理工大學本科生課程離散數學-一階邏輯

一階邏輯浙江理工大學本科生課程計算機科學與技術系離散數學答案3.10

在一階邏輯中將下列命題符號化:(1)沒有不吃飯的人。(2)在北京賣菜的人不全是東北人。解：使用全總個體域(1)F(x):x是人，G(x):x吃飯

x(F(x)G(x))

或x(F(x)→G(x))(2)F(x):x在北京賣菜，G(x):x是東北人

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

或x(F(x)G(x))

3.103.11

在一階邏輯中將下列命題符號化:(3)不存在比所有火車都快的汽車。(4)說凡是汽車都比火車慢是不對的。解：使用全總個體域，設F(x):x是火車，G(y):y是汽車

L(x,y):x比y快,H(x,y):x比y慢(3)y(G(y)x(F(x)→L(y,x))

y

(G(y)x(F(x)→L(y,x)))

y(G(y)∨x(F(x)→L(y,x)))

y(G(y)∨x(F(x)∧

L(y,x)))

y(G(y)→x(F(x)∧

L(y,x)))3.11(4)y(G(y)→x(F(x)→H(y,x)))

y(G(y)→x(F(x)→H(y,x)))

y(G(y)∨x(F(x)→H(y,x)))

y(G(y)∧x(F(x)∧

H(y,x)))3.113.143.14指出下列公式中的指導變元，量詞的轄域，各個體變項的自由出現和約束出現

(1)x(F(x)→G(x,y))

(2)xF(x,y)→yG(x,y)解：(1)x(F(x)→G(x,y))

指導變元約束變元自由變元

(2)xF(x,y)→yG(x,y)

指導變元約束變元自由變元

3.173.17判斷下列各式的類型

(1)F(x,y)→(G(x,y)→

F(x,y))

(2)x(F(x)→F(x))→y(G(y)∧

G(y))解：(1)方法一：等值演算法

A=F(x,y)→(G(x,y)→

F(x,y))

F(x,y)∨(

G(x,y)∨F(x,y))

F(x,y)∨

G(x,y)∨F(x,y)

1

方法二：重言式的代換實例

A為重言式p→(q→p)的代換實例，A為永真(2)B=x(F(x)→F(x))→y(G(y)∧

G(y))

x(F(x)∨F(x))→y(G(y)∧

G(y))

1→0

0

矛盾式3.293.29求下列各式的前束范式（只用換名規(guī)則）3.30求下列各式的前束范式（只用代替規(guī)則）（1）xF(x)→yG(x,y)解:xF(x)→yG(x,y)

uF(u)→

yG(x,y)(換名規(guī)則)

u(F(u)→

yG(x,y)(量詞轄域收縮與擴展等值式)

uy(F(u)→G(x,y))(量詞轄域收縮與擴展等值式)

xF(x)→yG(x,y)

xF(x)→

yG(u,y)(代替規(guī)則)

x(F(x)→

yG(u,y)(量詞轄域收縮與擴展等值式)

xy(F(x)→G(u,y))(量詞轄域收縮與擴展等值式)

2.392.39在自然推理系統(tǒng)F中構造下面推理的證明(個體域為中國人組成的集合):東北人都不怕冷，王國瑞怕冷，所以王國瑞不是東北人。解：設F(x)：x是東北人G(x)：x怕冷a：王國瑞前提:x(F(x)→G(x)),G(a)

結論：F(a)

1.G(a)前提引入

2.x(F(x)→G(x))前提引入

3.F(a)→G(a)2UI規(guī)則

4.F(a)1,3拒取式3.403.40每個喜歡步行的人都不喜歡自行車。每個人或者喜歡騎自行車或者喜歡乘汽車。有的人不喜歡乘汽車。所以有些人不喜歡步行（個體域為人類集合)。解：(1).設F(x)：x喜歡步行

G(x)：x喜歡騎自行車

H(x):x喜歡乘汽車

(2).前提:x(F(x)→G(x))

x(G(x)∨H(x))

xH(x)

結論：xF(x)

3.40(3).證明

1.xH(x)前提引入

2.H(c)1EI規(guī)則

3.x(G(x)∨H(x))前提引入

4.G(c)∨H(c)3UI規(guī)則

5.G(c)2,4析取三段論

6.x(F(x)→G(x))前提引入

7.F(c)→G(c)6UI規(guī)則

8.F(c)5,7據取式

9.xF(x)8EG規(guī)則若為全總個體域前提:x(M(x)∧F(x)→G(x))

x(M(x)→(G(x)∨H(x)))

x(M(x)∧H(x))結論：x(M(x)∧F(x))證明

1.x(M(x)∧H(x))前提引入

2.M(c)∧H(c)1EI規(guī)則

3.M(c)2化簡

4.

H(c)2化簡證明（續(xù)）

5.x(M(x)→(G(x)∨H(x)))前提引入

6.M(c)→(G(c)∨H(c))5UI規(guī)則

7.G(c)∨H(c)3,6假言推理

8.G(c)4,7析取三段論

9.x(M(x)∧F(x)→G(x))前提引入

10.M(c)∧F(c)→G(c)9UI規(guī)則

11.（M(c)∧F(c)）8,10據取式

12.