離散數(shù)學(xué)屈婉玲答案

1、百度文庫-讓每個(gè)人平等地提升自我11第一章部分課后習(xí)題參考答案16設(shè)p、q的真值為0; r、s的真值為1,求下列各命題公式的真值。(1)pV(qAr) 0 V (0A1) / 0(2)(p? r) A (qVs)(0? 1) A(1 V1)0A 10.(3)(p A q A r), ? (p A q Ar)(1 A 1 A 1) ?式0 A0A 0)0(rAs).-(pA q)(0A 1) 一(1 A0)00117.判斷下面一段論述是否為真:是無理數(shù)。并且，如果3是無理數(shù)，則也是無理數(shù)。另外6能被2整除，6才能被4整除?！贝穑簆: 是無理數(shù)q：3是無理數(shù)r:s:6能被2整除1t:6能被4整除

2、0命題符號(hào)化為：p A (q-r) A (t-s)的真值為1,所以這一段的論述為真19.用真值表判斷下列公式的類型:(4)(p-q) 一( q - p)(5)(pAr) ( pA q)(6)(p-q)八(q-r) (pr)(4)p0011q 0101p-q11 011010所以公式類型為永真式p1100q 一p1101(p-q)( q - p)1111等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值.(1) (pAq-q)(2)(p-(pVq)V (pr)(3)(pVq)-(pAr)答：(2) (p一(pVq) V (p-r)( pV(pVq)V( pVr)pV

3、pV qV r 1所以公式類型為永真式PqrpVqp A r(pV q) (pAr)000001001001010100011100100100101111110100111111所以公式類型為可滿足式4 .用等值演算法證明下面等值式：(p 一 q) A (p 一 r) (p 一 (q A r)(p A q) V ( pA q) (p V q) A (p A q)證明(2) (p q) A (pr)(pVq)A( pVr) pV(q A r)p 一 (q 八 r)(4) (pA q) V( pAq) (p V ( pAq) A( qV( pA q) (p V p) A (p Vq) A ( q

4、V p) A ( qVq)1 A (p V q) A (p A q) A 1 (p V q) A (p A q)5 .求下列公式的主析取范式與主合取范式，并求成真賦值(1)(p-q)(qvp)(2) (p q)AqAr(3)(p V(q Ar) 一(p VqVr)解：(1)主析取范式/(p一 q)(q p)/(p q) ( q p)(p q) ( q p) /(p q)(q p) ( q p) (p q) (p q)(p q) (p q) (p q)mo m2 m3三(0,2,3)主合取范式：(p-q)(q p)(p q) ( q p)(p q) ( q p)(p ( q p)( q ( q

5、p)1 (p q)(p q)Min(2) 主合取范式為：(p-q) q r ( p q) q r(p q) q r 0所以該式為矛盾式.主合取范式為n (0,1,2,3,4,5,6,7)矛盾式的主析取范式為0(3)主合取范式為： (p (q r) 一 (p q r)(p (q r) 一 (p q r)(p ( q r) (p q r)(p (p q r)( q r) (p q r)1 11所以該式為永真式.永真式的主合取范式為1主析取范式為三(0,1,2,3,4,5,6,7)第三章部分課后習(xí)題參考答案14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：*(2)前提：p q, (q r),r結(jié)論： ps

6、,s t,t r(4)前提：q p,q 結(jié)論：p q證明：(2)(q r)q rq rrqp q前提引入置換蘊(yùn)含等值式前提引入拒取式前提引入拒取式證明(4):t rtq ss tq t(q t)(q 7)qq pp(ii)p q前提引入化簡律前提引入前提引入等價(jià)三段論(t q) 置換化簡假言推理前提引入假言推理合取15在自然推理系統(tǒng)P中用附加前提法證明下面各推理:p前提：p (q r),s p,q結(jié)論：s r證明附加前提引入前提引入(qr)假言推理前提引入假言推理前提引入假言推理16在自然推理系統(tǒng)P中用歸謬法證明下面各推理:(1)前提：pq, r q,r s結(jié)論:證明:結(jié)論的否定引入前提引入假

7、言推理 前提引入 化簡律 前提引入 化簡律r r合取由于最后一步rr是矛盾式，所以推理正確.第四章部分課后習(xí)題參考答案條件時(shí)命3.在一階邏輯中將下面將下面命題符號(hào)化，并分別討論個(gè)體域限制為(a),(b) 題的真值:(1)對于任意x,均有松,-2=僅+a)僅7?).(2)存在 x,使彳# x+5=9. /其中(a)個(gè)體域?yàn)樽匀粩?shù)集合./(b)個(gè)體域?yàn)閷?shí)數(shù)集合./解：F(x):- -2=(x+品)(x - ” ).G(x): x+5=9.(1)在兩個(gè)個(gè)體域中都解釋為xF(x)，在(a)中為假命題，在(b)中為真命題。(2)在兩個(gè)個(gè)體域中都解釋為xG(x),在(a) (b)中均為真命題。4 .在一階

8、邏輯中將下列命題符號(hào)化：(1)沒有不能表示成分?jǐn)?shù)的有理數(shù).(2)在北京賣菜的人不全是外地人.解：(1)F(x): x能表示成分?jǐn)?shù)H(x): x是有理數(shù)命題符號(hào)化為：x( F(x) H(x)、(2)F(x): x是北京賣菜的人H(x): x是外地人命題符號(hào)化為：x(F(x) H(x)5 .在一階邏輯將下列命題符號(hào)化：(1) 火車都比輪船快.(3)不存在比所有火車都快的汽車.解： (1)F(x): x 是火車；G(x): x 是輪船；H(x,y): x 比 y 快命題符號(hào)化為：x y(F(x) G(y) H(x, y)(2) (1)F(x): x 是火車；G(x): x 是汽車；H(x,y): x

9、 比 y 快命題符號(hào)化為： y(G(y)x(F(x) H(x,y)9.給定解釋I如下：/(a) 個(gè)體域D為實(shí)數(shù)集合R./(b) D中特定元素工=0./(c) 特定函數(shù)：(x,y)=x -y,x,y DwD>(d) 特定謂詞 F(x,y):x=y, 1(x,y):x<y,x,y D.說明下列公式在I下的含義，并指出各公式的真值:(1) x y(G(x,y) F(x, y)(2) x y(F(f(x,y),a)G(x,y)答：(1)對于任意兩個(gè)實(shí)數(shù)x,y,如果x<y,那么x y.真值1.(2)對于任意兩個(gè)實(shí)數(shù)x,y,如果x-y=0,那么x<y.真值0.10.給定解釋I如下：

10、/(a)個(gè)體域D=N(N為自然數(shù)集合).(b) D中特定元素曜=2.(c) D上函數(shù)果工切=x+y,鼠x,y)=xy.(d) D 上謂詞M(x,y):x=y.說明下列各式在I下的含義，并討論其真值.(1) -xF(g(x,a),x)(2) vxvy(F(f(x,a),y)一F(f(y,a),x)答：(1)對于任意自然數(shù)x,都有2x=x,真值0.(2)對于任意兩個(gè)自然數(shù)x,y,使得如果x+2=y,那么y+2=x.真值0.11.判斷下列各式的類型：(1) 7 .-'.-二(3) - 7- - yF(x,y).解：(1)因?yàn)閜 (q p) p ( q p) 1 為永真式；所以F(xp) t伯

11、值巾-F雙力).為永真式；(3)取解釋I個(gè)體域?yàn)槿w實(shí)數(shù)F(x,y) : x+y=5所以，前件為任意實(shí)數(shù)x存在實(shí)數(shù)y使x+y=5,前件真；后件為存在實(shí)數(shù)x對任意實(shí)數(shù)y都有x+y=5,后件假，此時(shí)為假命題再取解釋I個(gè)體域?yàn)樽匀粩?shù)N,/F(x,y) : :x+y=5所以，前件為任意自然數(shù)x存在自然數(shù)y使x+y=5,前件假。此時(shí)為假命題。 此公式為非永真式的可滿足式。13.給定下列各公式一個(gè)成真的解釋，一個(gè)成假的解釋。/(1)-：(F(x)依騰微/(2)三x(F(x) G(x) H(x)解:(1)個(gè)體域：本班同學(xué)F(x) : x會(huì)吃飯,G(x) : x會(huì)睡覺.成真解釋F(x)： x是泰安人,G(x)

12、 : x是濟(jì)南人.(2)成假解釋(2)個(gè)體域：泰山學(xué)院的學(xué)生 /F(x) : x出生在山東,G(x):x出生在北京，H(x):x出生在江蘇，成假解釋.F(x) : x會(huì)吃飯,G(x) : x會(huì)睡覺,H(x) : x會(huì)呼吸.成真解釋./第五章部分課后習(xí)題參考答案5.給定解釋I如下：(a)個(gè)體域 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)

13、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), f (3) (F(x,4)F(f(x), f (4)x(F(x,3)F(f(x),4) (F(x,4)F(f (x),3)(F(3,3)F(f(3),4) (F(3,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)(1F(3,4) (0 F (3,3)(00) (11)(11) (00)112.求下列各式的前束范式

14、。、/(1) xF(x) yG(x, y)(5) XiF(Xi,X2)(H(xi)X2G(Xi,X2)(本題課本上有錯(cuò)誤)解：(1) xF(x) yG(x,y) xF(x) yG(t,y) x y(F(x) G(t,y)(6) x1 F (x1, x2)(H (x1)x2G(x1,x2)XlF(Xi,X2)(H ( X3 )X2 G(X3,X2)xi F (xi, X4)X2(H (X3)G(X3,X2)Xi X2(F(Xi,X4)(H(X3)G(X3,X2)15.在自然數(shù)推理系統(tǒng)F中，構(gòu)造下面推理的證明：(1)前提：xF(x) y(F(y) G(y)R(y), xF(x) 結(jié)論：xR(x)(2)前提： x(F(x) 一(G(a) A R(x),三 xF(x)結(jié)論：三x(F(x) A R(x)證明(1)xF (x