離散數(shù)學(xué)第二章謂詞邏輯習(xí)題課第1頁一.命題符號化60頁(2)(x)(J(x)→L(x))(x)(L(x)∧S(x))(x)(J(x)∧O(x)∧V(x))J(j)∧

O(j)∧

V(j)(x)(L(x)→J(x))或者

(x)(L(x)∧

J(x)(x)(S(x)∧L(x)∧C(x))(x)(C(x)∧

V(x)或者(x)(C(x)→V(x))h)(x)((C(x)∧O(x))→L(x))i)(x)(W(x)∧C(x)∧H(x))j)(x)(W(x)∧J(x)∧C(x))k)(x)(L(x)→

y(J(y)∧A(x,y)))l)(x)(S(x)∧y(L(y)→

A(x,y)))第2頁習(xí)題課62頁(2)(x)y((P(x)∧P(y)∧

E(x,y))→

z(L(z)∧R(x,y,z)∧

t((L(t)∧R(x,y,t))→E(t,z))))(3)b)設(shè)R(x):x是實數(shù)，G(x,y):x＞y(x)(R(x)→

y(R(y)∧G(y,x)))c)設(shè)R(x):x是實數(shù)，G(x,y):x＞yf(x,y)=x+yg(x,y)=xy(x)y

z(R(x)∧R(y)∧R(z)∧G(f(x,y),g(x,z)))

或者

(x)y

z(R(x)∧R(y)∧R(z)∧G(x+y,xz))第3頁習(xí)題課5)b)設(shè)N(x):x是數(shù)，A(x,y):y是x后繼數(shù)

(x)(N(x)∧A(x,1))(6)設(shè)A(x):x是戴眼鏡,B(x):x是用功,C(x):x是大學(xué)生,D(x):x是大,E(x):x是厚，F(xiàn)(x):x是巨著,

A(x,y):x在看y,a:那位，b:這本

A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(b)∧A(a,b)第4頁補充題：1.每個人叔叔都是他父親弟弟。設(shè)：P(x):x是人，U(x,y):y是x叔叔，

B(x,y):x是y弟弟，f(x)=x父親

(x)(P(x)→

y(U(x,y)→B(y,f(x)))2.下面是判定一個年號是否為閏年命題:“年號能被4整除而且不能被100整除為閏年.或者年號能被400整除也是閏年.”

設(shè)Y(x):x是年號;D(x,y):x可整除y;R(x):x是閏年(x)(Y(x)→(((D(4,x)∧

D(100,x))→R(x))∨(D(400,x)→R(x))))第5頁66頁(3)b)P:2>1,Q(x):x≤3,R(x):x>5,a:5,{-2,3,6}(x)(P→Q(x))∨R(a)(P→(x)Q(x))∨R(a)(P→(Q(-2)∧Q(3)∧Q(6)))∨R(5)(T→(T∧T∧F))∨F(T→F)∨F

F∨F

F4)b)對約束變元換名(x)(P(x)→(R(x)∨Q(x)))∧(x)R(x)→

zS(x,z)

y(P(y)→(R(y)∨Q(y)))∧

tR(t)→

uS(x,u)(5)a)對自由變元代入(yA(x,y)→(x)B(x,z))∧(x)zC(x,y,z)(yA(u,y)→(x)B(x,v))∧(x)zC(x,w,z)第6頁習(xí)題課72頁(2)d)論域為{1,2}P(1)P(2)Q(1,1)Q(1,2)Q(2,1)Q(2,2)FTTTFF(x)y(P(x)∧Q(x,y))

y(P(1)∧Q(1,y))∧

y(P(2)∧Q(2,y))((P(1)∧Q(1,1))∨(P(1)∧Q(1,2)))∧((P(2)∧Q(2,1))∨(P(2)∧Q(2,2)))((F∧T)∨(F∧T))∧((T∧F)∨(T∧F))(F∨F)∧(F∨F)

F第7頁6)判斷下面推證是否正確。

(x)(A(x)→B(x))⑴(x)(

A(x)∨B(x))⑵(x)(A(x)∧

B(x)⑶(x)(A(x)∧

B(x))⑷((x)A(x)∧(x)B(x))⑸(x)A(x)∨(x)B(x)⑹(x)A(x)∨(x)B(x)⑺(x)A(x)→(x)B(x)第⑷步錯，由⑶到⑷用是公式：

(x)(A(x)∧

B(x))((x)A(x)∧(x)B(x))

無此公式，而是(x)(A(x)∧

B(x))(x)A(x)∧(x)B(x)，應(yīng)將⑷中換成即：第8頁(x)(A(x)→B(x))(x)(A(x)→B(x))⑴(x)(

A(x)∨B(x))⑵(x)(A(x)∧

B(x)⑶(x)(A(x)∧

B(x))⑷((x)A(x)∧(x)B(x))⑸(x)A(x)∨(x)B(x)⑹(x)A(x)∨(x)B(x)⑺(x)A(x)→(x)B(x)因為由公式E18P→QQ→P

(x)(A(x)∧B(x))

(x)A(x)∧(x)B(x)

，

PQ得((x)A(x)∧(x)B(x))(x)(A(x)∧B(x))第9頁75頁(1)b)(x)(

yP(x,y)→(

zQ(z)→R(x)))(x)(

yP(x,y)∨(

zQ(z)∨R(x)))(x)(

yP(x,y)∨(

z

Q(z)∨R(x)))(x)(

yP(x,y)∨

z(

Q(z)∨R(x)))(x)y

z(P(x,y)∨(

Q(z)∨R(x)))(2)c)(x)P(x)→(x)(zQ(x,z)∨zR(x,y,z))(x)P(x)∨(x)(zQ(x,z)∨zR(x,y,z))(x)P(x)∨(x)(zQ(x,z)∨zR(x,y,z))

(x)P(x)∨

u(zQ(u,z)∨tR(u,y,t))(x)uzt(

P(x)∨(Q(u,z)∨R(u,y,t)))(x)uzt(

P(x)∨Q(u,z)∨R(u,y,t))此式既是前束析取范式，也是前束合取范式。第10頁79頁(2)a)用CP規(guī)則證實(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第11頁習(xí)題課第12頁3)a)全部有理數(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⑻第13頁習(xí)題課b)任何人假如他喜歡步行，他就不喜歡乘汽車；每個人或者喜歡乘汽車或者喜歡騎自行車。有人不愛騎自行車，所以有人不愛步行。設(shè)A(x):x是人,B(x):x是喜歡步行,C(x):x喜歡乘汽車，D(x):x喜歡騎自行車(x)(A(x)→(B(x)→

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

D(x))

(x)(A(x)∧

B(x))第14頁

⑴(x)(A(x)∧

D(x))P⑵A(a)∧

D(a))

ES⑴⑶A(a)T⑵I⑷

D(a))T⑵I⑸(x)(A(x)→(B(x)→

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

C(a))US⑸⑺B(a)→

C(a))T⑶⑹I⑻(x)(A(x)→(C(x)∨D(x)))P⑼A(a)→(C(a)∨D(a)))US⑻⑽C(a)∨D(a)T⑶⑼I⑾C(a)T⑷⑽I⑿

B(a)T⑺⑾I⒀A(a)∧

B(a)T⑶⑿I⒁(x)(A(x)∧

B(x))EG⒀第15頁習(xí)題課c)每個大學(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)第16頁習(xí)題課(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第17頁習(xí)題課補充題：小楊、小劉和小林為高山俱樂部組員，該俱樂部每個組員是個滑雪者或登山者。沒有一個登山者喜歡雨。而全部滑雪者都喜歡雪。凡是小楊喜歡，小劉就不喜歡。小楊喜歡雨和雪。試證實該俱樂部是否有個是登山者而不是滑雪者組員。假如有，他是誰？設(shè)：M(x):x是高山俱樂部組員。H(x):x是滑雪者。

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

a:小楊；b:小劉；c:小林；d:雨；e:雪。第18頁

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)T⑸⑺I12⑼(x)(M(x)→(H(x)∨D(x)))P⑽M(b)→(H(b)∨D(b))US⑼⑾M(b)P⑿H(b)∨D(b)T⑽⑾I11⒀D(b)T⑻⑿I10⒁D(b)∧

H(b)T⑻⒀第19頁謂詞邏輯處理這個問題方法：在表示命題時，既表示出主語，也表示出謂語，就能夠處理上述問題。這就提出了謂詞概念。令S(x)表示x是大學(xué)生，a:小張，b:小李命題P表示成S(a):小張是大學(xué)生。命題Q表示成S(b):小李是大學(xué)生。從符號S(a)、S(b)可看出小張和小李都是大學(xué)生共性。第20頁謂詞邏輯令N(x):x是自然數(shù)。I(x):x是整數(shù)。

表示全部。

A:(x)(N(x)→I(x))B:N(8)C:I(8)N(8)

I(8)推理如此實現(xiàn)：N(8)→I(8)符號S(x)、N(x)、I(x)就是所謂謂詞。第21頁習(xí)題選講—命題符號化1.在一階邏輯中將以下命題符號化。

（1）每個人都有心臟。

（2）有狗會飛。

（3）沒有不犯錯誤人。

（4）發(fā)光不都是金子。

（5）一切人都不一樣高。

（6）并不是全部汽車都比火車快。

（7）沒有一個自然數(shù)大于等于任何自然數(shù)。

（8）有唯一偶素數(shù)。

（9）不論黑貓白貓，抓住老鼠就是好貓。

（10）對平面上任意兩點，有且僅有一條直線經(jīng)過這兩點。第22頁習(xí)題選講—命題符號化解：因為沒指出個體域，故用全總個體域（1）每個人都有心臟。 本命題含義：對于每一個x，假如x是人，則x有心臟。 因而應(yīng)首先從宇宙間一切事物中，將人分離出來，這就必須引入特征謂詞。 令M(x):x是人，H(x):x有心臟。 命題符號化為：(x)(M(x)→H(x))

假如將其中→改為∧，即(x)(P(x)∧H(x))，它表示意思是：“對于每個x，x是人且x有心臟”。這是一個假命題，而“每個人都有心臟”是真命題。 這說明將命題“每個人都有心臟”符號化為(x)(P(x)∧H(x))是錯誤。第23頁習(xí)題選講—命題符號化（2）有狗會飛。 命題意思是：存在一個x，使得x是狗，而且x會飛。 設(shè)D(x)：x是狗，F(xiàn)(x)：x會飛。

命題符號化為：(x)(D(x)∧F(x))

假如將其中∧改為→，即(x)(D(x)→F(x))， 假如用a表示某只貓，則D(a)為假，因而，D(a)→F(a)為真，所以(x)(D(x)→F(x))為真，而“有狗會飛”為假， 這說明將“有狗會飛”符號化為(

x)(D(x)→F(x))是錯誤。第24頁（3）沒有不犯錯誤人。 命題意思是： ①存在不犯錯誤人是不可能。②只要是人，必定犯錯誤。 設(shè)M(x):x是人，F(xiàn)(x):x犯錯誤 命題符號化為①┐(x)(M(x)∧┐F(x))

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

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

②(x)(L(x)∧﹁G(x))第25頁（5）一切人都不一樣高。設(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))（6）并不是全部汽車都比火車快。設(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))習(xí)題選講—命題符號化第26頁習(xí)題選講—命題符號化（7）沒有一個自然數(shù)大于等于任何自然數(shù)。 設(shè) N(x):x是自然數(shù)，G(x,y):x

y

命題符號化為：

(x)(N(x)y(N(y)

G(x,y)))（8）有唯一偶素數(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)))第27頁習(xí)題選講—命題符號化（9）不論黑貓白貓，抓住老鼠就是好貓。 需要考慮問題： ①只是限制黑貓白貓，還是包含其它顏色貓？ ②是指最少抓住一只就能夠，還是抓住全部？所以在描述命題時，總是將這些含糊概念做某種確切了解。 設(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))

第28頁習(xí)題選講—命題符號化（10）對平面上任意兩點，有且僅有一條直線經(jīng)過這兩點。 設(shè)P(x)：x是一個點，L(x)：x是一條直線

R(x,y,z)：z經(jīng)過x,y，E(x,y)：