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

1、第一章部分課后習(xí)題參考答案16 設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。 （1）p(qr) 0(01) 0 （2）（pr）(qs) （01）(11) 010. （3）（pqr）(pqr) （111） (000)0(4)（rs）(pq) （01）(10) 00117判斷下面一段論述是否為真：“是無(wú)理數(shù)。并且，如果3是無(wú)理數(shù)，則也是無(wú)理數(shù)。另外6能被2整除，6才能被4整除?！贝穑簆: 是無(wú)理數(shù) 1 q: 3是無(wú)理數(shù) 0 r: 是無(wú)理數(shù) 1 s:6能被2整除 1t: 6能被4整除 0 命題符號(hào)化為： p(qr)(ts)的真值為1，所以這一段的論述為真。19用真值表判斷下列公式的

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

3、pr)(p(pq)(pr)ppqr1 所以公式類(lèi)型為永真式(3) P q r pq pr （pq）(pr)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1 所以公式類(lèi)型為可滿足式4.用等值演算法證明下面等值式：(2)(pq)(pr)(p(qr)(4)(pq)(pq)(pq) (pq)證明（2）(pq)(pr) (pq)(pr)p(qr)p(qr)（4）(pq)(pq)(p(pq) (q(pq)(pp)(pq)(qp) (qq)1(pq)(pq)1(pq)(pq) 5.

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

5、r) (p(qr)(pqr)(p(qr)(pqr)(p(pqr)(qr)(pqr) 11 1 所以該式為永真式. 永真式的主合取范式為 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）：tr 前提引入t 化簡(jiǎn)律qs 前提引入st 前提引入qt 等價(jià)三段論（qt）(tq)  置換（qt） 化簡(jiǎn)q 假言推理qp 前提引入

6、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é)論的否定引入pq 前提引入q 假言推理rq 前提引入r 化簡(jiǎn)律rs 前提引入r 化簡(jiǎn)律rr 合取由于最后一步rr 是矛盾式,所以推理正確.第四章部分課后習(xí)題參考答案3. 在一階邏輯中將下面將下面命題符號(hào)化,并分別討論個(gè)體域限制為(a),(b)條件時(shí)命題的真值:(1) 對(duì)于任

7、意x,均有2=(x+)(x).(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è)體域中都解釋為，在（a）中為假命題，在(b)中為真命題。(2)在兩個(gè)個(gè)體域中都解釋為，在（a）(b)中均為真命題。4. 在一階邏輯中將下列命題符號(hào)化:(1) 沒(méi)有不能表示成分?jǐn)?shù)的有理數(shù).(2) 在北京賣(mài)菜的人不全是外地人.解:(1)F(x): x能表示成分?jǐn)?shù) H(x): x是有理數(shù)命題符號(hào)化為: (2)F(x): x是北京賣(mài)菜的人 H(x): x是外地人命題符號(hào)化為: 5. 在一階邏輯將下列命題符號(hào)化:

8、 (1) 火車(chē)都比輪船快. (3) 不存在比所有火車(chē)都快的汽車(chē). 解:(1)F(x): x是火車(chē); G(x): x是輪船; H(x,y): x比y快命題符號(hào)化為: (2) (1)F(x): x是火車(chē); G(x): x是汽車(chē); H(x,y): x比y快命題符號(hào)化為: 9.給定解釋I如下: (a) 個(gè)體域D為實(shí)數(shù)集合R. (b) D中特定元素=0. (c) 特定函數(shù)(x,y)=xy,x,y. (d) 特定謂詞(x,y):x=y,(x,y):x<y,x,y. 說(shuō)明下列公式在I下的含義,并指出各公式的真值:(1)(2)答:(1) 對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x<y, 那么xy. 真值1.(

9、2) 對(duì)于任意兩個(gè)實(shí)數(shù)x,y,如果x-y=0, 那么x<y. 真值0.10. 給定解釋I如下： （a） 個(gè)體域D=N(N為自然數(shù)集合). （b） D中特定元素=2. （c） D上函數(shù)=x+y,(x,y)=xy. （d） D上謂詞(x,y):x=y.說(shuō)明下列各式在I下的含義，并討論其真值.(1) xF(g(x,a),x)(2) xy(F(f(x,a),y)F(f(y,a),x)答:(1) 對(duì)于任意自然數(shù)x, 都有2x=x, 真值0.(2) 對(duì)于任意兩個(gè)自然數(shù)x,y,使得如果x+2=y, 那么y+2=x. 真值0.11. 判斷下列各式的類(lèi)型:(1) (3) yF(x,y).解:(1)因?yàn)?為

10、永真式； 所以 為永真式；(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對(duì)任意實(shí)數(shù)y都有x+y=5，后件假，此時(shí)為假命題再取解釋I個(gè)體域?yàn)樽匀粩?shù)N，F(xiàn)(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ì)睡覺(jué).成真解釋F(x)：x是泰安人,G(x)：x是濟(jì)南人.（2）成假解釋(2)個(gè)體域:泰山學(xué)院的學(xué)生F(x)：x出生在山東,G(x):x出生在北京,H(x):x出生在江蘇,成假解釋.F(x)：x會(huì)吃飯,G(x)：x會(huì)睡覺(jué),H(x)：x會(huì)呼吸. 成真解釋.第五章部分課后習(xí)題參考答案5.給定解釋如下:(a)個(gè)體域D=3,4;(b)為(c). 試求下列公式在下的真值.(1) (3)解:(1) (2) 12.求下列各式的前束范式。(1) (5) (本題課本上有錯(cuò)誤)解:(1) (5) 15.在自然數(shù)推理系統(tǒng)F中,構(gòu)造下面推理的證明:(1) 前提: ,結(jié)論: xR(x)(2) 前提: x(F(x)(G(a)R(x), xF(x)結(jié)論:x(F(x)R(x)證明