離散數(shù)學(xué)謂詞邏輯省公開課獲獎?wù)n件市賽課比賽一等獎?wù)n件

謂詞邏輯習(xí)題課第九周2023.11命題符號化討論在給定解釋下謂詞公式旳真值判斷公式是不是永真式，并加以闡明轉(zhuǎn)換前束合取范式推理證明1.將下列命題符號化(1)沒有不犯錯誤旳人(2)發(fā)光旳不都是金子(3)一切人都不同高(4)并不是全部旳汽車都比火車快(5)不論黑貓白貓，抓住老鼠就是好貓(6)有唯一旳偶素數(shù)(7)對平面上任意兩點(diǎn)，有且僅有一條直線經(jīng)過這兩點(diǎn)(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))

(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）不論黑貓白貓，抓住老鼠就是好貓

需要考慮問題： ①只是限制黑貓白貓，還是包括其他顏色旳貓？ ②是指至少抓住一只就能夠，還是抓住全部旳？設(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)有唯一旳偶素數(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)對平面上任意兩點(diǎn)，有且僅有一條直線經(jīng)過這

兩點(diǎn)設(shè)P(x):x是一種點(diǎn),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)))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（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

真值為F3.判斷下列公式是不是永真式，并加以闡明（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；綜上該公式不是永真式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)]第四步，將

進(jìn)一步：

(

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

]5.推理證明：(1)(x)(P(x)∨Q(x)(x)P(x)∨(x)Q(x)因?yàn)?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(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

(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)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(4)全部有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，所以某些實(shí)數(shù)是整數(shù)。

設(shè)Q(x):x是有理數(shù)R(x):x是實(shí)數(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⑻(5)小楊、小劉和小林為高山俱樂部組員，該俱樂部旳每個組員是個滑雪者或登山者。沒有一種登山者喜歡雨。而全部滑雪者都喜歡雪。但凡小楊喜歡旳，小劉就不喜歡。小楊喜歡雨和雪。試證明該俱樂部是否有個是登山者而不是滑雪者旳組員。假如有，他是誰？設(shè)：M(x):x是高山俱樂部組員。H(x):x是滑雪者。

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

a:小楊；b:小劉；c:小林；d:雨；e:雪。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)