屈婉玲版離散數(shù)學課后習題答案【3】

1、第四章局部課后習題參考答案3. 在一階邏輯中將下面將下面命題符號化，并分別討論個體域限制為(a),(b)條件時命 題的真值：(1) 對于任意 x,均有 -2=(x+ J(x - 一).(2) 存在x,使得x+5=9.其中(a)個體域為自然數(shù)集合.(b)個體域為實數(shù)集合.解：F(x):. ： -2=(x+ _)(x_).G(x): x+5=9.(1) 在兩個個體域中都解釋為xF(x)，在a中為假命題，在(b)中為真命題。在兩個個體域中都解釋為xG(x)，在a(b)中均為真命題。4. 在一階邏輯中將以下命題符號化：(1) 沒有不能表示成分數(shù)的有理數(shù)(2) 在北京賣菜的人不全是外地人.解：(1) F

2、(x): x能表示成分數(shù)H(x): x是有理數(shù)命題符號化為：x( F(x) H(x)(2) F(x): x是北京賣菜的人H(x): x是外地人命題符號化為： x(F(x) H(x)5. 在一階邏輯將以下命題符號化：(1)火車都比輪船快(3) 不存在比所有火車都快的汽車解：(1)F(x): x 是火車；G(x): x 是輪船；H(x,y): x 比 y 快命題符號化為：x y(F(x) G(y) H(x, y)(1)F(x): x 是火車;G(x): x 是汽車;H(x,y): x 比y快命題符號化為： y(G(y) x(F(x) H(x,y)9. 給定解釋I如下:(a)個體域D為實數(shù)集合R.(

3、b) D中特定元素- =0.(c)特疋函數(shù)(x,y)=x -y,x,y D .(d)特疋謂詞：(x,y):x=y,(x,y):x<y,x,yD說明以下公式在I下的含義,并指出各公式的真值：(1) x y(G(x,y) F(x, y)(2) x y(F(f(x,y),a)G(x,y)答:(1)對于任意兩個實數(shù)x,y,如果x<y,那么x y.真值1.(2)對于任意兩個實數(shù)x,y,如果x-y=0,那么x<y.真值0.10. 給定解釋I如下：a個體域D=N(N為自然數(shù)集合).bD中特定元素一 =2.cD 上函數(shù)'餘3 =x+y,護(x,y)=xy.dD 上謂詞二(x,y):x

4、=y.說明以下各式在I下的含義，并討論其真值.(1) xF(g(x,a),x)(2) -x-y(F(f(x,a),y) F(f(y,a),x)答:(1)對于任意自然數(shù)x,都有2x=x,真值0.(2) 對于任意兩個自然數(shù)x,y,使得如果x+2=y,那么y+2=x.真值0.11. 判斷以下各式的類型：(1) 7 一 (3) 啖誹滸躋' :師7yF(x,y).解:(1)因為p (q p) p ( q p) 1 為永真式；所以)険釦。軸朋“撐皿為永真式；(3) 取解釋I個體域為全體實數(shù)F(x,y) : x+y=5所以,前件為任意實數(shù)x存在實數(shù)y使x+y=5,前件真；后件為存在實數(shù)x對任意實數(shù)y

5、都有x+y=5,后件假，此時為假命題再取解釋I個體域為自然數(shù)N,F(x,y) : :x+y=5所以,前件為任意自然數(shù)x存在自然數(shù)y使x+y=5,前件假。此時為假命題。 此公式為非永真式的可滿足式。13.給定以下各公式一個成真的解釋，一個成假的解釋。(1) .(F(x)池跆馳(2) -x(F(x) G(x) H(x)解：(1)個體域：本班同學F(x): x是泰安 人,G(x) : x是濟南人.2成假解釋個體域：泰山學院的學生F(x) : x出生在山東,G(x):x出生在北京,H(x):x出生在江蘇，成假解釋.F(x) : x會吃飯,G(x) : x會睡覺,H(x) : x會呼吸.成真解釋.第五章

6、局部課后習題參考答案5.給定解釋I如下：(a) 個體域 D=3,4;(b) f(x)為 f(3)4, f (4)3(c) F(x,y)為F(3,3)F(4,4)0, F(3,4)F(4,3) 1.試求以下公式在I下的真值.(1)x yF(x,y)(3)x y(F(x,y)F(f(x), f(y)解 :(1)x yF (x, y)x(F(x,3)F(x,4)(F(3,3)F(3,4)(F(4,3)F(4,4)(0 1) (1 0) 1(2) x y(F(x,y) F(f(x), f(y)x(F(x,3)F(f(x),4)(F(x,4) F(f (x),3)(F(3,3)F(f(3),4)(F(3

7、,4)F(f(3),3)(F(4,3) F(f (4),4)(F(4,4)F(f(4),3)(0F(4,4)(F(3,4)F(4,3)(iF(3,4)(0F(3,3)(00) (i i) (ii) (00) ii2.求以下各式的前束范式。(1)xF(x) yG(x, y)XiF(xX2)(H(xJX2G(X!,X2)(此題課本上有錯誤)解：(1)xF(x) yG(x, y)xF(x) yG(t,y) x y(F(x) G(t,y)XiF(Xi,X2)(H (Xi)X2G(xi,X2)XiF(Xi,X2)(H(X3)X2 G(X3,X2)XiF(Xi,X4)X2(H (X3)G(X3,X2 )Xi X2(F(Xi,X4)(H (X3)G(X3,X2)i5.在自然數(shù)推理系統(tǒng)F中，構(gòu)造下面推理的證明：(i)前提:xF(x) y(F(y)G(y)R(y), xF(x)結(jié)論:xR(x)前提:x(F(x) -(G(a) A R(x),_ xF(x)結(jié)論：_x(F(x)A R(x)證明(i) xF(x)前提引入 F(c)El xF(x)y(F(y) G(y)R( y)前 y(F(y)G(y)R(y)假言推理(F(c) V G(c) -R(c)UlF(c) V G(c)附加 R(c)假言推理 xR(