離散數(shù)學(xué)(屈婉玲)答案1-5章

1、第一章部分課后習(xí)題參考答案16 設(shè) p、 q 的真值為 0；r、s 的真值為 1，求下列各命題公式的真值。（1）p(q r)0 (0 1)0（2）（ p?r ） ( qs)（0?1） (1 1)0 10.（3）（ p qr ）? (p q r)（111） ? (0 00) 0(4) （ r s） (p q)（01） (1 0)00117判斷下面一段論述是否為真： “是無理數(shù)。并且，如果3 是無理數(shù)，則2 也是無理數(shù)。另外6 能被 2 整除， 6 才能被 4 整除。”答： p:是無理數(shù)1q:3 是無理數(shù)0r:2 是無理數(shù)1s:6能被 2整除1t:6能被 4整除0命題符號化為：p(qr) (t s

2、)的真值為 1，所以這一段的論述為真。19用真值表判斷下列公式的類型：（ 4）(pq) ( q p)（ 5）(pr)(pq)（ 6）(pq) (q r) (pr)答：（ 4）pqpqqpq p(pq) ( q p)0011111011011110010011110011所以公式類型為永真式/最后一列全為 1（5）公式類型為可滿足式（方法如上例） /最后一列至少有一個 1 （6）公式類型為永真式（方法如上例） /第二章部分課后習(xí)題參考答案3. 用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值 .(1) (pqq)(2)(p(pq) (pr)(3)(pq)(pr)答

3、： (2)（p(pq)） (pr) (pq)( pp r)p p q r 1所以公式類型為永真式(3) Pqrp qp r（p q） (pr)000001001001010100011100100100101111110100111111所以公式類型為可滿足式4. 用等值演算法證明下面等值式：(2)(p q) (p r)(p (q r)(4)(p q) (p q)(p q) (p q)證明（ 2）(p q) (p r)(p q) (p r)p(q r)p (q r)（ 4） (p q) (pq)(p (pq)(q(p q)(p p) (p q) (qp) (qq)1(p q) (p q) 1(

4、p q) (p q)5. 求下列公式的主析取范式與主合取范式，并求成真賦值(1)(p q) (qp)(2) (p q) qr(3)(p (q r) (p qr)解：（1）主析取范式(p q) (qp)(p q)(qp)(pq)(qp)(pq)(qp)( qp) (p q) (pq)(pq)(pq)(pq)m0m2m3 (0,2,3)主合取范式：(pq) (qp)(pq)(qp)(pq)(qp)(p(qp)(1(pq)q(qp)(pq)M1 (1)(2) 主合取范式為：(p q)qr(pq)qr(pq)qr0所以該式為矛盾式 .主合取范式為 (0,1,2,3,4,5,6,7)矛盾式的主析取范式為

5、0(3) 主合取范式為：(p(q(pppr)(q(p(pr)qqqr) (pqr)(pr)(r)qqr)r)(pqr)1 11所以該式為永真式 .永真式的主合取范式為1主析取范式為 (0,1,2,3,4,5,6,7)第三章部分課后習(xí)題參考答案14. 在自然推理系統(tǒng) P 中構(gòu)造下面推理的證明：(2) 前提： pq,(qr),r結(jié)論：p(4) 前提： qp,qs,st,tr結(jié)論： pq證明：（ 2）(qr)前提引入qr置換 qr蘊(yùn)含等值式 r前提引入q拒取式 pq前提引入 p拒取式證明（ 4）：t r前提引入t化簡律qs前提引入st前提引入qt等價三段論（ qt ）(tq) 置換（ qt ）化簡q

6、 假言推理qp前提引入p假言推理(11)pq合取15 在自然推理系統(tǒng)P 中用附加前提法證明下面各推理：(1) 前提： p(qr),sp,q結(jié)論： sr證明s附加前提引入sp前提引入p假言推理p(qr) 前提引入qr假言推理q前提引入r假言推理16 在自然推理系統(tǒng)P 中用歸謬法證明下面各推理：(1) 前提： pq,rq,rs結(jié)論：p證明：p結(jié)論的否定引入p q前提引入 q假言推理 rq前提引入 r化簡律rs前提引入r化簡律rr 合取由于最后一步 r r 是矛盾式 , 所以推理正確 .第四章部分課后習(xí)題參考答案3. 在一階邏輯中將下面將下面命題符號化 , 并分別討論個體域限制為 (a),(b) 條

7、件時命題的真值 :(1)對于任意 x, 均有2=(x+)(x).(2)存在 x, 使得 x+5=9.其中 (a) 個體域?yàn)樽匀粩?shù)集合 .(b) 個體域?yàn)閷?shí)數(shù)集合 .解：F(x):2=(x+)(x).G(x): x+5=9.(1) 在兩個個體域中都解釋為(2) 在兩個個體域中都解釋為xF ( x)xG ( x)，在（ a）中為假命題，在 (b) 中為真命題。，在（ a） (b) 中均為真命題。4. 在一階邏輯中將下列命題符號化 :(1) 沒有不能表示成分?jǐn)?shù)的有理數(shù) .(2) 在北京賣菜的人不全是外地人 .解 :(1)F(x): xH(x): x能表示成分?jǐn)?shù)是有理數(shù)命題符號化為 :x(F ( x)

8、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 快命題符號化為:xy( F ( x)G ( y)H (x, y)(2) (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í)數(shù)集合 R.(b) D 中

9、特定元素 =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í)數(shù) x,y, 如果 x<y, 那么 x y. 真值 1.(2) 對于任意兩個實(shí)數(shù) x,y, 如果 x-y=0, 那么 x<y. 真值 0.10. 給定解釋 I 如下：（a） 個體域 D=N(N為自然數(shù)集合 ).（b） D 中特定元素=2.（c） D

10、 上函數(shù)=x+y, (x,y)=xy.（d） D 上謂詞(x,y):x=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)(3)yF(x,y).解:(1)因?yàn)?為永真式；所以為永真式；(3) 取解釋 I 個體域?yàn)槿w實(shí)數(shù)F(x,y) ：x+y=5所以 , 前件為任意實(shí)數(shù)x 存在實(shí)數(shù) y 使 x+y=5，前件真；后件為存在

11、實(shí)數(shù)x 對任意實(shí)數(shù) y 都有 x+y=5，后件假， 此時為假命題再取解釋 I 個體域?yàn)樽匀粩?shù)N，F(xiàn)(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) 個體域 : 本班同學(xué)F(x) ：x 會吃飯 , G(x)：x 會睡覺 . 成真解釋F(x) ：x 是泰安人 ,G(x) ：x 是濟(jì)南人 . （2）成假解釋(2) 個體域 : 泰山學(xué)院的學(xué)生F(x) ：x 出生在山東 ,G(x):x出生在北京

12、 ,H(x):x出生在江蘇 , 成假解釋 .F(x) ：x 會吃飯 ,G(x) ： x 會睡覺 ,H(x) ：x 會呼吸 .成真解釋 .第五章部分課后習(xí)題參考答案5. 給定解釋如下 :(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.試求下列公式在下的真值.(1) x yF ( x, y)(3)x y( F( x, y)F ( f ( x), f ( y)解 :(1)xyF (x, y)x( F (x,3)F ( x,4)(F (3,3)F (3,4)(F (4,3)F

13、 ( 4,4)(01)(10)1(2)xy(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)x1F ( x1 , x2 )(H (x1 )x2G( x1 , x2 ) ( 本題課本上有錯誤 )解:(1)xF ( x)yG( x, y)xF (x)yG (t , y)x y( F ( x) G (t, y)(5)x1 F (x1 , x2 )( H (x1 )x2 G( x1 , x2 )x1 F (x1, x2 )( H ( x3 )x2 G(x3 , x2 )x1 F (x1 , x4 )x2 ( H ( x3 )G( x3 , x2 )x1 x2 (F ( x1 , 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) R(x),xF(x)結(jié)論 :x(F(x) R(