謂詞邏輯習(xí)題課第九周.11第1頁命題符號化討論在給定解釋下謂詞公式真值判斷公式是不是永真式，并加以說明轉(zhuǎn)換前束合取范式推理證實第2頁1.將以下命題符號化(1)沒有不犯錯誤人(2)發(fā)光不都是金子(3)一切人都不一樣高(4)并不是全部汽車都比火車快(5)不論黑貓白貓，抓住老鼠就是好貓(6)有唯一偶素數(shù)(7)對平面上任意兩點，有且僅有一條直線經(jīng)過這兩點第3頁(1)沒有不犯錯誤人①存在不犯錯誤人是不可能。②只要是人，必定犯錯誤。 設(shè)M(x):x是人，F(xiàn)(x):x犯錯誤 命題符號化為①┐(x)(M(x)∧┐F(x))

②(x)(M(x)→F(x))(2)發(fā)光不都是金子

①不是發(fā)光東西都是金子。②存在著發(fā)光東西不是金子。 設(shè)L(x)：x是發(fā)光東西，G(x)：x是金子。 命題符號化為

①┐(x)(L(x)→G(x))

②(x)(L(x)∧﹁G(x))

第4頁(3)一切人都不一樣高設(shè)F(x):x是人,H(x,y),x與y相同,L(x,y):x與y一樣高，

命題符號化為

(x)(F(x)

y(F(y)

H(x,y)

L(x,y)))

或

(x)y(F(x)

F(y)

H(x,y)

L(x,y))(4)并不是全部汽車都比火車快設(shè)F(x):x是汽車,G(y):y是火車,H(x,y):x比y快，命題符號化為

(x)y(F(x)

G(y)

H(x,y))

或(x)y(F(x)

G(y)

H(x,y))第5頁（5）不論黑貓白貓，抓住老鼠就是好貓

需要考慮問題： ①只是限制黑貓白貓，還是包含其它顏色貓？ ②是指最少抓住一只就能夠，還是抓住全部？設(shè)C(x):x是貓,W(x):x是白,B(x):x是黑

G(x):x是好,M(x):x是老鼠,

K(x):x抓住y

命題符號化為

(x)y(C(x)∧M(y)∧(B(x)∨W(x))∧K(x,y))→G(x))

第6頁

(6)有唯一偶素數(shù)設(shè)：Q(x):x是偶數(shù),P(x):x是素數(shù),

E(x,y):x＝y(tǒng)

命題符號化為：

(x)(Q(x)

P(x)y(Q(y)

P(y)

E(x,y)))

(7)對平面上任意兩點，有且僅有一條直線經(jīng)過這

兩點設(shè)P(x):x是一個點,L(x):x是一條直線

R(x,y,z):z經(jīng)過x,y,E(x,y):x等于y

命題符號化為

(x)y(P(x)∧P(y)∧﹁E(x,y))→z(L(z)∧R(x,y,z)∧u((L(u)∧R(x,y,u))→E(u,z)))第7頁2.討論在給定解釋下謂詞公式真值（1）

x(P→Q(x))∨R(a)

D={-2,3,6}

,P:2>1,Q(x):x≤3,R(x):x>5,a:5（2）

x

y(P(x)∧Q(x,y)) D={1,2}，

P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)FTTTFF第8頁（1）

x(P→Q(x))∨R(a)

D={-2,3,6}

,P:2>1,Q(x):x≤3,R(x):x>5,a:5

x(P→Q(x))∨R(a)(P→

xQ(x))∨R(a)(P→(Q(-2)∧Q(3)∧Q(6)))∨R(5)(T→(T∧T∧F))∨F(T→F)∨F

F∨F

F（2）

x

y(P(x)∧Q(x,y)) D={1,2}，

P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)FTTTFF

真值為F第9頁3.判斷以下公式是不是永真式，并加以說明（1）(

xP(x)→

xQ(x))?

x(P(x)→Q(x))解：不是永真式，取解釋以下

D={1,2}

P(1)P(2)Q(1)Q(2)

F

T

F

T

在該解釋下xP(x)為T，xQ(x)為F，所以xP(x)→

xQ(x)為F；而(P(1)→Q(1))為T，(P(2)→Q(2))為T，所以x(P(x)→Q(x))為T；綜上該公式不是永真式第10頁4.轉(zhuǎn)換前束合取范式(1)將謂詞公式(

x)[(

y)P(x)

(

z)Q(z,y)

(

y)R(x,y)]化為與之等價前束合取范式第一步，取消多出量詞：

(

x)[P(x)

(

z)Q(z,y)

(

y)R(x,y)]第二步，約束變量換名：

(

x)[P(x)

(

z)Q(z,y)

(

w)R(x,w)]第三步，消去條件聯(lián)結(jié)詞：

(

x)[

(P(x)

(

z)Q(z,y))

(

w)R(x,w)]第四步，將

深入：

(

x)[(

P(x)

(

z)Q(z,y))

(

w)

R(x,w)]

(

x)[(

P(x)

(

z)

Q(z,y))

(

w)

R(x,w)]第五步，將量詞提前：

(

x)(

z)(

w)[(

P(x)

Q(z,y))

R(x,w)]

(

x)(

z)(

w)[(

P(x)

R(x,w))

(

Q(z,y)

R(x,w))

]第11頁5.推理證實：(1)(x)(P(x)∨Q(x)(x)P(x)∨(x)Q(x)因為(x)P(x)∨(x)Q(x)(x)P(x)→(x)Q(x)⑴(x)P(x)P(附加前提)⑵(x)

P(x)T⑴E⑶P(a)ES⑵⑷(x)(P(x)∨Q(x)P⑸P(a)∨Q(a)US⑷⑹Q(a)T⑶⑸I⑺(x)Q(x)EG⑹⑻(x)P(x)→(x)Q(x)CP第12頁(2)

xP(x)∨

xQ(x)

x(P(x)∨Q(x))(1)

x(P(x)∨Q(x)) P(假設(shè))(2)

x

(P(x)∨Q(x)) T(1)E(3)

(P(c)∨Q(c)) ES(2)(4)

P(c)∧

Q(c) T(3)E(5)

P(c) T(4)I(6)

x

P(x) EG(5)(7)

xP(x) T(6)E(8)

xP(x)∨

xQ(x) P (9)

xQ(x) T(7)(8)I(10)Q(c) US(9)(11)

Q(c) T(4)I(12)Q(c)∧

Q(c) T(10)(11)I第13頁

(3)每個大學(xué)生不是文科生就是理工科生，有大學(xué)生是優(yōu)等生，小張不是理工科生，但他是優(yōu)等生，所以假如小張是大學(xué)生，他就是文科生。

設(shè)A(x):x是大學(xué)生,B(x):x是文科生,C(x):x是理工科生，D(x):x是優(yōu)等生,

a:小張

x(A(x)→(

B(x)→C(x))),

x(A(x)∧D(x))

C(a)∧D(a)

A(a)→B(a)第14頁x(A(x)→(

B(x)→C(x))),x(A(x)∧D(x))

C(a)∧D(a)

A(a)→B(a)⑴A(a)P(附加前提)⑵x(A(x)→(

B(x)→C(x)))P⑶A(a)→(

B(a)→C(a))US⑵⑷B(a)→C(a))T⑴⑶I⑸C(a)∧D(a)P⑹C(a)T⑸I⑺B(a)T⑷⑹I⑻B(a)T⑺E⑼A(a)→B(a)CP第15頁(4)全部有理數(shù)是實數(shù)，一些有理數(shù)是整數(shù)，所以一些實數(shù)是整數(shù)。

設(shè)Q(x):x是有理數(shù)R(x):x是實數(shù)I(x):x是整數(shù)

(x)(Q(x)→R(x)),(x)(Q(x)∧I(x))

(x)(R(x)∧I(x))⑴(x)(Q(x)∧I(x))P⑵Q(a)∧I(a)ES⑴⑶Q(a)T⑵I⑷I(a)T⑵I⑸(x)(Q(x)→R(x))P⑹Q(a)→R(a)US⑸

⑺R(a)T⑶⑹I⑻R(a)∧I(a)T⑷⑺I⑼(x)(R(x)∧I(x))EG⑻第16頁(5)小楊、小劉和小林為高山俱樂部組員，該俱樂部每個組員是個滑雪者或登山者。沒有一個登山者喜歡雨。而全部滑雪者都喜歡雪。凡是小楊喜歡，小劉就不喜歡。小楊喜歡雨和雪。試證實該俱樂部是否有個是登山者而不是滑雪者組員。假如有，他是誰？設(shè)：M(x):x是高山俱樂部組員。H(x):x是滑雪者。

D(x):x是登山者。L(x,y):x喜歡y。

a:小楊；b:小劉；c:小林；d:雨；e:雪。第17頁M(x):x是高山俱樂部組員。H(x):x是滑雪者。

D(x):x是登山者。L(x,y):x喜歡y。a:小楊；b:小劉；c:小林；d:雨；e:雪。命題符號化為：M(a),M(b),M(c),(x)(M(x)→(H(x)∨D(x))),(x)(D(x)∧L(x,d)),(x)(H(x)→L(x,e))(x)(L(a,x)→

L(b,x)),L(a,d)∧L(a,e)⑴L(a,d)∧L(a,e)P⑵L(a,e)T⑴⑶(x)(L(a,x)→

L(b,x))P⑷L(a,e)→

L(b,e))US⑶⑸

L(b,e))T⑵⑷I11⑹(x)(H(x)→L(x,e))P⑺H(b)→L(b,e))US⑹⑻

H(b)