一階邏輯浙江理工大學(xué)本科生課程計算機(jī)科學(xué)與技術(shù)系離散數(shù)學(xué)答案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)說凡是汽車都比火車慢是不對的。解：使用全總個體域，設(shè)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指出下列公式中的指導(dǎo)變元，量詞的轄域，各個體變項的自由出現(xiàn)和約束出現(xiàn)

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

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

指導(dǎo)變元約束變元自由變元

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

指導(dǎo)變元約束變元自由變元

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)(量詞轄域收縮與擴(kuò)展等值式)

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

xF(x)→yG(x,y)

xF(x)→

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

x(F(x)→

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

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

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

結(jié)論：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).設(shè)F(x)：x喜歡步行

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

H(x):x喜歡乘汽車

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

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

xH(x)

結(jié)論：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據(jù)取式

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

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

x(M(x)∧H(x))結(jié)論：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據(jù)取式

12.