離散數(shù)學(xué)-馮欒石陳編-習(xí)題答案

1、For personal use only in study and research; not for commercial use習(xí)題一1、 利用邏輯聯(lián)結(jié)詞把下列命題翻譯成符號(hào)邏輯形式（1） 他既是本片的編劇，又是導(dǎo)演 - P Q（2） 銀行利率一降低，股價(jià)隨之上揚(yáng)- P Q（3） 盡管銀行利率降低，股價(jià)卻沒有上揚(yáng)- P Q（4） 占據(jù)空間的、有質(zhì)量而且不斷變化的對(duì)象稱為物質(zhì) - M ?(SPT)（5） 他今天不是乘火車去北京，就是隨旅行團(tuán)去了九寨溝- P Q（6） 小張身體單薄，但是極少生病，并且頭腦好使- P Q R（7） 不識(shí)廬山真面目，只緣身在此山中- P Q（解釋：因?yàn)樯碓诖松街?/p>

2、，所以不識(shí)廬山真面目）（8） 兩個(gè)三角形相似，當(dāng)且僅當(dāng)他們的對(duì)應(yīng)角相等或者對(duì)應(yīng)邊成比例- S ?(ET)（9） 如果一個(gè)整數(shù)能被6整除，那么它就能被2和3整除。如果一個(gè)整數(shù)能被3整除，那么它的各位數(shù)字之和也能被3整除解：設(shè) P 一個(gè)整數(shù)能被6整除Q 一個(gè)整數(shù)能被2整除R 一個(gè)整數(shù)能被3整除S 一個(gè)整數(shù)各位數(shù)字之和能被3整除翻譯為：（P （Q R） （R S）2、 判別下面各語句是否命題，如果是命題，說出它的真值（1）BASIC語言是最完美的程序設(shè)計(jì)語言- Y，T/F（2）這件事大概是小王干的- N（3）x2 = 64- N（4）可導(dǎo)的實(shí)函數(shù)都是連續(xù)函數(shù)- Y，T/F（5）我們要發(fā)揚(yáng)連續(xù)作戰(zhàn)的作

3、風(fēng)，再接再厲，爭(zhēng)取更大的勝利- N（6）客觀規(guī)律是不以人們意志為轉(zhuǎn)移的- Y，T（7）到2020年，中國(guó)的國(guó)民生產(chǎn)總值將趕上和超過美國(guó)- Y，N/A（8）凡事都有例外- Y，F(xiàn)3、 構(gòu)造下列公式的真值表，并由此判別哪些公式是永真式、矛盾式或可滿足式（1）（P （P Q） Q解：PQP QP （P Q）（P （P Q） Q可滿足式00001011111001011011（2）（4）略4、 利用真值表方法驗(yàn)證下列各式為永真式（1）（8）略5、 證明下列各等價(jià)式（1）（P Q）（P Q）（P Q）? P證明：左式 ? （P Q）（P Q）（P Q）? P （P Q）（P Q） T （P Q）? P

4、? 右式（2）（P Q）（R Q）?（P R）Q證明：左式 ?（PQ）（RQ）ó （P R）Qó （P R）Qó （P R）Q ? 右式（3）P（Q R）? （P Q）（P R）證明：左式?PQ Ró PQP Ró （PQ）（P R）ó （P Q）（P R）? 右式（4）（P Q）（R Q）（R P）? （P Q）（R Q）（R P）證明：左式?(（PR） Q）（R P）ó (（PR）R) ) (（PR）P) ) （QR）（QP）ó （P Q）（R Q）（R P）? 右式6、 如果P Q ? QR,能否斷定 P ?

5、 R ？ 如果P Q ? QR，能否斷定 P ? R？如果P ? R，能否斷定 P ? R？解：（1）如果P Q ? QR，不能判斷P ? R，因?yàn)槿绻?Q = P R, 那么P Q? PP R ? QR，但P可以不等價(jià)于R. （2）如果P Q ? QR，不能判斷P ? R，因?yàn)槿绻?Q = P R, 那么P Q? PP R ? QR，但P可以不等價(jià)于R.（3）如果P ? R，那么有P ? R，因?yàn)镻 ? R，則P <-> R為永真式，及有P <-> R為永真式，所以P ? R.7、 檢查和是否滿足結(jié)合率解： 用真值表方式檢查PQRPQQR(PQ) RP(Q R)000

6、11110011101010111101110011001110101110011001101110011由上表可知，不滿住結(jié)合率PQRPQQR(PQ) RP(Q R)00011000011001010001101100011000110101000011000101110000由上表可知，不滿住結(jié)合率8、 把下列各式用等價(jià)表示出來（1）(PQ) P解：原式 ? (PQ) (PQ) (PP)? (PQ) (PQ) (PQ) (PQ) (PP) (PP)（2）P（P Q）解：原式 ? PPQ? Q? (QQ) (QQ)（3）（P（Q R） P解：原式 ? （ PQ R） P? P（Q P）（R

7、P）? (PP) （(QQ) (PP)）（R(PP)）? (PP) （(QQ) (PP)）（(QQ) (PP)）（R(PP)）（R(PP)）設(shè)：(PP) = N（(QQ) (PP)）（(QQ) (PP)）= L（R(PP)）（R(PP)） = M則上式? (NN) (LL) (NN) (LL) (MM)（4） PQ（R P）解：原式 ? PQ（RP）? (PP) (QQ) （(PP) (RR)）? (（(PP) (QQ)）（(PP) (QQ)）) （(PP) (RR)）設(shè)：(（(PP) (QQ)）（(PP) (QQ)）) = N（(PP) (RR)） = M則上式? (NM) (NM)9、 證

8、明： 是最小功能完備集合證明:因?yàn)? 是最小功能完備集合,所以,如果 能表示出,則其是功能完備集合。由于 P Q ? (P) Q ,所以 是功能完備集合。因?yàn)?不能相互表示，所以 是最小功能完備集合；同理可證：非，條件非也能將或表示出來：P Q ? (P ! Q)10、 證明: ， 不是功能完備集證明： PQ沒有辦法通過，的公式表達(dá)出來，因?yàn)镻QPQPP(PP)PQ000010011011101011111010所以，通過，不能表達(dá)出真值為三個(gè)1或1個(gè)1的情況，因此，不能表達(dá)出PQ，所以不是功能完備集。11、 用和把公式 PQR和（PQ）R表示出來解：（PQ）R ? (（PQ）（PQ）) R?

9、 (（PQ）（PQ）) R) (（PQ）（PQ）) R)? (（PQ）（PQ）R) （PQ）（PQ）R）? （(（PQ）（PQ）R)）（PQ）（PQ）R）（PQ）R?（ (（PQ）（PQ）R)12、 分別利用真值表法和等價(jià)變換法求下列公式的主合取范式及主析取范式:(1) P(RQ) S)解：真值表法PQRSRQ(RQ) SP(RQ) S)0000011000101100100110011011010001101010110110101011111110000111001011101001110110111100011110101111101001111111所以：主合取范式為 = PQRS =

10、 M14主析取范式為 = m1m2m3m4m5m6m7m 8m9m10m11m12m13m14m16等價(jià)變換法（略）(2)（PQ）（P<->Q）解：真值表法PQPQP<->Q（PQ）（P<->Q）00100011111011111001所以：主合取范式為 = PQ = M0主析取范式為 = (PQ)(PQ)(PQ) = m1m2m3等價(jià)變換法（略） (3) P(R(QP)解：真值表法PQRQPR(QP)P(R(QP)000101001111010001011001100100101111110100111111所以：主合取范式為 = (PQR) (PQR)

11、= M4M6主析取范式為 = (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) = m0m1m2m3m5m7等價(jià)變換法（略）(4) (P(QR) (P(QR)解：真值表法PQRQRQRP(QR)P(QR)(P(QR) (P(QR)0000111100100100010001000111010010001010101000101100001011110111所以：主合取范式為 = (PQR) ( PQR) ( PQR) (PQR) ( PQR) ( PQR) = M1M2M3M4M5M6主析取范式為 = (PQR)(PQR) = m0m7等價(jià)變換法（略）13、 用轉(zhuǎn)化范式的方法判別下

12、面各組公式是否等價(jià)（1）（PQ）（PQ） 和（PQ）（QP）解：（PQ）（PQ）? （PQ）（PQ）? （PQ）（PQ）-合取范式（PQ）（QP）? （PQ）（QP）? P(QQ) ? P ? （PQ）（PQ） -合取范式兩式的合取范式相同，所以等價(jià)（2）（PQ）（PR） 和 P（QR）解： （PQ）（PR）? （PQ）（PR） - 合取范式P（QR）? P（QR）? （PQ）（PR）-合取范式兩式的合取范式相同，所以等價(jià)14、 從A,B,C,D 4個(gè)人中派2人出差，要求滿足下列條件：如果A去，則必須在C或D中選一人同去；B和C不能同時(shí)去；C和D不能同時(shí)去。用構(gòu)造范式的方法決定選派方案。解：由

13、題設(shè) A：A去，B：B去，C：C去，D：D去則滿足條件的選派應(yīng)滿足如下范式：（A（C?D）（BC）（CD）構(gòu)造和以上范式等價(jià)的主析取范式（A（C?D）（BC）（CD）?（AB C D ）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）共有八個(gè)極小項(xiàng)，但根據(jù)題意，需派兩人出差，所以，只有其中三項(xiàng)滿足要求： （ABCD），（ABCD），（ABCD）即有三種方案：A和C去或者A和D去或者B和D去。15、 證明下列蘊(yùn)含試：（1）PQ=>P (PQ)證明：PQ ? P Q ? T(P Q) ? (PP) (P Q) ? P (PQ)? P (PQ)所以，這是個(gè)等

14、價(jià)式，因此也是個(gè)蘊(yùn)含式（2）(PQ) Q=> (PQ)證明：(PQ) Q ? (PQ) Q ? (PQ) Q ? (PQ) (QQ) ? (PQ) T ? (PQ)所以，這是個(gè)等價(jià)式，因此也是個(gè)蘊(yùn)含式（3）PPR=>S證明：PPR ? F => S (F可蘊(yùn)含任何命題公式)（4）P=>QRR證明：P=>T ? QRR16、 證明蘊(yùn)含關(guān)系的性質(zhì)1、性質(zhì)2和3證明：性質(zhì)1 A => A因?yàn)樵谌我獾慕忉屜?，公式A的真值顯然和自己相同，當(dāng)然在為真時(shí)也相同，所以蘊(yùn)含成立。性質(zhì)2 如果 A=>B且B=>A, 則 A ? B因?yàn)?A=>B且B=>A

15、 及 (AB) (BA) 為永真式，則 A <-> B為永真式。所以A ? B。性質(zhì)3 如果A=>B且A永真式，則B必為永真式因?yàn)?(AB)為永真式，且A為永真式，那么只有B為永真式才能滿足(AB)為永真式成立。所以結(jié)論為真。17、 證明定理1.12證明：A=>B,當(dāng)且僅當(dāng)B=>A證明： A=>B ? AB為永真式 ? BA 為永真式 ? B=>A A=>B,當(dāng)且僅當(dāng)B=>A18、 一個(gè)有錢人生前留下了一筆珍寶，藏在一個(gè)隱秘處。在他留下的遺囑中指出尋找珍寶的線索如下：（1） 如果藏寶的房子靠近池塘，那么珍寶不會(huì)藏在東廂房。（2） 如果房子的

16、前院栽有大柏樹，那么珍寶就藏在東廂房。（3） 藏寶房子靠近池塘。（4） 要么前院栽有大柏樹，要么珍寶埋在花園正中地下。（5） 如果后院栽有香樟樹，珍寶藏在附近。請(qǐng)利用蘊(yùn)含關(guān)系找出藏寶處。解：根據(jù)給定的條件有下述命題：P：珍寶藏在東廂房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏樹S：珍寶藏在花園正中地下T：后院栽有香樟樹M：珍寶藏在附近根據(jù)題意，得出：（QP）（RP）Q（RS）（TM） T？（QP）（RP）Q（RS）（TM） TP（RP）（RS）（TM） TR（RS）（TM） TS（TM）TS 即珍寶藏在花園正中地下19、 判斷下列蘊(yùn)含關(guān)系式是否成立：（1）Q(PQ) TP解：當(dāng)左端公式解釋為

17、1時(shí)，Q必須為1；Q為1，P比為1；所以，右端公式也為1；因此，蘊(yùn)含關(guān)系成立（2）(P(QR) (Q(PR) TPR解：左端公式 ? Q <-> (PR)，當(dāng)解釋為1是，分兩種情況，PR與Q同為1，那么PR也為1；PR與Q同為0，如果此時(shí) P=1,R = 0, 則PR為0；因此，此蘊(yùn)含式不成立（3）P (PQ) T Q解：左端公式解釋為1時(shí)，P必為0；當(dāng)P為0時(shí)，則Q可為0，也可為1；因此，此蘊(yùn)含式不成立（4）(PQ) (PQ) (PR) TR解：當(dāng)左端公式按P = 0, Q = 1, R = 0 解釋時(shí)，為1，但右端不為1；因此，此蘊(yùn)含式不成立（5）(PQ) R)(PQ)(QP)

18、 TR解：當(dāng)左端公式按 P =1, Q =1, R = 0解釋時(shí)，真值為1，但右端為0；因此，此蘊(yùn)含式不成立20、 演繹證明下面各蘊(yùn)含式：（1）PQ,RQ T PR證明：運(yùn)用cp法，將結(jié)論條件式的前件作為前提，證明步驟如下1Pp(附加前提)2PQp3QT 1,2 I4RQp5RT 3,4 I6PRCP 1,5（2）(PQ) (RS),(SE) B T PB證明：運(yùn)用cp法，將結(jié)論條件式的前件作為前提，證明步驟如下1Pp（附加前提）2(PQ) (RS)p3RST 1,2 I4(SE) Bp5BT 3,4 I6PBCP1,5（3）P(QR),(RS) E, B(SE) T P(QB)證明：運(yùn)用cp

19、法，將結(jié)論條件式的前件作為前提，先將結(jié)論進(jìn)行等價(jià)變換為（PQ）B,因此PQ可作為附加前提，證明步驟如下1PQp(附加前提)2P(QR)p3（PQ）RT 2 E4RT 1,3 I5(RS) Ep6ET 4,6 I7B(SE)p8BT 6,7 I9（PQ）Bcp 1,8（4）(RQ) (RS),(QE) (SB), (EB),(PR) T P證明：運(yùn)用反證方法，將結(jié)論的非納入前提，證明步驟如下1Pp(附加前提)2PRp3RT 1,2 I4(RQ) (RS)p5QST 3,4 I6(QE) (SB)p7EBT 5,6 I8(EB)p9F(矛盾式)T 7,8 E（5）P(QR),Q(RS) T P(Q

20、S)證明：運(yùn)用cp法，將結(jié)論條件式的前件作為前提，證明步驟如下1Pp(附加前提)2P(QR)p3QRT 1,2 I4Q(RS)p5R(QS)T 4 E6QST 3,5 I7P(QS)CP 1,621、 把下列句子演繹成邏輯形式，并給出證明（1） 如果資方拒絕增加工資，那么罷工不會(huì)結(jié)束；除非罷工超過一年，并且資方撤換了經(jīng)理；現(xiàn)在資方拒絕了增加工資，罷工剛開始。判斷罷工能否停止。解：根據(jù)題意，有如下命題P: 資方拒絕增加工資Q: 罷工結(jié)束R: 罷工超過一年S: 資方撤換了經(jīng)理所以，前提條件符號(hào)化為PQ；QRS；PR因此，推理過程如下：1PRp2PQp3QT 1,2 I所以，罷工不會(huì)結(jié)束（2） 某公

21、司發(fā)生了一起盜竊案，經(jīng)仔細(xì)偵察，掌握了如下一些事實(shí)：l 被盜現(xiàn)場(chǎng)沒有留下任何痕跡l 失盜時(shí)，小花或則小英正在卡拉ok廳l 如果失竊時(shí)小胖正在附近，他就會(huì)習(xí)慣性地破門而入偷走東西后揚(yáng)長(zhǎng)而去l 如果失盜時(shí)小花正在卡拉ok廳唱歌，那么金剛是最大的嫌疑者l 如果失盜時(shí)小胖不在附近，那么他的女友小英會(huì)和他一起外出旅游l 如果失盜時(shí)小英正在卡拉ok廳唱歌，那么瘦子是最大的嫌疑者根據(jù)以上事實(shí)，請(qǐng)通過演繹推理找出偷竊者解：根據(jù)給定的條件有下述命題：P：現(xiàn)場(chǎng)無任何痕跡Q：失竊時(shí)，小花在OK廳R：失竊時(shí)，小英在OK廳S：失竊時(shí)，小胖在附近T：金剛是偷竊者M(jìn)：瘦子是偷竊者則根據(jù)案情有如下命題公式：P，QR，S P，

22、Q T， S R，R M P P SP P S TI SR P R TI QR P Q TI QT P T TI即 金剛是偷竊者22、 設(shè)A1,A2,An是一組命題公式，如果存在一個(gè)解釋使A1A2An取值真，就稱這組公式是相容的，否則稱為不相容的。不相容意味著A1A2An蘊(yùn)含一個(gè)矛盾式，現(xiàn)在判別下列各命題組是否相容（1）P(QR),S(QR),PS解：根據(jù)題意（P(QR)）（S(QR)）（PS）T (QR)(QR) T RR T F所以，這組命題公式不相容（2）PQ, RS, Q, S解：根據(jù)題意(PQ) (RS) Q S T PR所以,當(dāng)P=1，Q=0，R=0，S=0時(shí)，合取式解釋為1，因此

23、這組命題公式相容（3）P<->Q,QR, RS, PS, S解：根據(jù)題意（P<->Q）（QR） （RS） （PS） S T （P<->Q）（QR）R PT（P<->Q）QP T F所以，這組命題公式不相容（4）PQ,PR,QR,P解：根據(jù)題意（PQ）（PR）（QR）P T QR（QR）T RR T F所以，這組命題公式不相容23、 利用消解法證明下列各蘊(yùn)含式：（1）RQ,RS,SQ,PQ T P證明：RQ ? RQSQ ? SQPQ ? PQ因此子句集合 = RQ，SQ，RS，PQ，P 消解過程如下：1RQp2SQp3RSp4PQp5Pp6Q由4

24、，5歸結(jié)7R由1，6歸結(jié)8S由2，6歸結(jié)9S由3，7歸結(jié)10FLASE 由8，9歸結(jié)導(dǎo)出空子句（2）(PQ) (RS),(QP) R,R T P<->Q證明：(PQ) (RS) ? PQRS(QP) R ? QPR(P<->Q) ? （PQ）（QP）? （PQ）（QP）? (PQ) (QP) ? (PQ) (PQ)因此子句集合 = PQRS，QPR，PQ，PQ，R 消解過程如下：1PQRSp2QPRp3PQp4PQp5Rp6QP由2，5歸結(jié)7P由3，6歸結(jié)8QRS由1，7歸結(jié)9PS由2，8歸結(jié)10PR由2，3歸結(jié)11Q由4，6歸結(jié)12RS由8，11歸結(jié)13QPS由2，1

25、2歸結(jié)14PRS(此題可能有問題)（3）P(QR),Q(RS) T P(QS)證明：P(QR) ? PQRQ(RS) ? QRS（P(QS)）? PQS因此子句集合 = PQR，QRS，P，Q，S 消解過程如下：1PQRp2Pp3QR由1，2歸結(jié)4Qp5R由3，4歸結(jié)6QRSp7Sp8QR由6，7歸結(jié)9R由4，8歸結(jié)10FLASE 由5，9歸結(jié)導(dǎo)出空子句習(xí)題二1、 把下列謂詞翻譯成謂詞公式（1）每個(gè)有理數(shù)都是實(shí)數(shù)，但是并非每個(gè)實(shí)數(shù)都是有理數(shù)，有些實(shí)數(shù)是有理數(shù)解： R(x)-x是實(shí)數(shù)Ra(x)-x是有利數(shù)翻譯如下："(x)( Ra(x) R(x) "(x)( R(x) Ra(

26、x)$(x)( R(x) Ra(x)）（2）直線a和b平行當(dāng)切僅當(dāng)a和b不相交解：A(x)-x是直線 F(x，y)-x與y平行G（x,y)-與相交 翻譯如下："()"()（A()A() (F(，) ?G（,)）)（3）除非所有的會(huì)員都參加，這個(gè)活動(dòng)才有意義解：A(x)-是會(huì)員B(x)-x有意義-這個(gè)活動(dòng)F(x，y)-參加翻譯如下：B（）"(x)（A(x)F(x，)） 或"(x)（A(x)F(x，)）B（）（4）任何正整數(shù)不是合數(shù)就是質(zhì)數(shù)解：A(x)-是正整數(shù)(x)-是合數(shù)(x)-是質(zhì)數(shù)翻譯如下："(x)（A(x)(x)?(x)）（6） 凡是存錢

27、的人都想有利息，如果沒有利息，人們就不會(huì)存錢解：A(x)-是存錢的人F(x，y)-想有P-存錢沒有利息Q:-人們不存錢a:-利息翻譯如下："(x)（A(x)F(x，a)）（PQ）2、 設(shè)論域D = 0, 1, 2，把下列公式用不含量詞的公式表示出來（1）"(x) P(x) $(x)Q(x)解：上式 ? P(0) P(1) P(2) （Q(0) Q(1) Q(2)）（2）"(x) P(x) Q(x)解：上式 ? （P(0) Q(0)）（P(1) Q(1)）（P(2) Q(2)）（3）"(x) P(x) $(x)Q(x)解：上式 ? （P(0) P(1) P

28、(2)） Q(0) Q(1) Q(2)3、 指出下列公式中的約束變?cè)妥杂勺冊(cè)⒋_定公式的轄域略4、 對(duì)下列公式中的變?cè)M(jìn)行代換，以使任何變?cè)荒芗仁羌s束變?cè)质亲杂勺冊(cè)?）"(x) $(y)P(x,y) Q(y,z) "(z)R(x,y,z)解：代換如下 "(x) $(y)P(x,y) Q(y,z) "(s)R(u,v,s)（2）("(x) P(x) R(x) Q(x) ( $(x) R(x) $(z) S(x,z)解：代換如下 ("(x) P(x) R(x) Q(u) ( $(y) R(y) $(z) S(u,z)5、 把下列

29、語句符號(hào)化，并確定相應(yīng)謂詞公式是永真式、可滿足式、還是矛盾式（1）如果兩個(gè)數(shù)的積等于0，那么至少其中一個(gè)數(shù)為0，數(shù)x-1不等于0，所以數(shù)x-1和x+1的積也不等于0解：設(shè)論域在任意數(shù)域集合，運(yùn)用常規(guī)的數(shù)學(xué)符號(hào)，翻譯如下"(x) "(y)( xy = 0 (x=0 y=0) (x-1 0) (x-1)(x+1) 0)這是一個(gè)可滿足式，但不是永真式，因?yàn)榇嬖趚=-1時(shí)，謂詞公式不成立，但其它情況均成立，如果論域中不包含-1，為真，包含就不成立（2）誠(chéng)實(shí)的人都講實(shí)話。小林不是誠(chéng)實(shí)的，因而小林不講實(shí)話解：H(x)-x誠(chéng)實(shí)T(x)-x講真話a-小林翻譯如下：（"(x)(H(

30、x) T(x) H(a)） T(a)這是一個(gè)可滿足式，因?yàn)榉穸l件命題前件，不一定后件命題一定為假。及小林雖然不誠(chéng)實(shí)，但也可能講實(shí)話（3）好貨不便宜。小王買的衣服很貴，所以小王買的是優(yōu)質(zhì)衣服解：G(x)-x是好貨C(x)-x便宜a-小王買的衣服翻譯如下：("(x)( G(x) C(x) C(a)）G(a)此謂此公式成立，是永真式（4）每個(gè)懂得人性的作家都很高明，不能刻畫人們內(nèi)心世界的詩人都不是真正的詩人。莎士比亞創(chuàng)作了哈姆雷特。沒有一個(gè)不懂得人性本質(zhì)的作家能夠刻畫人們的內(nèi)心世界。只有真正的詩人才能創(chuàng)作哈姆雷特。因此，莎式比亞是個(gè)高明的作家。解：A(x)-x懂人性B(x)-x很高明C(

31、x)-x能刻畫人們內(nèi)心世界D(x,y)-x創(chuàng)作yh-哈姆雷特s- 莎士比亞翻譯如下：（"(x)( A(x) B(x) (C(x) B(x) (B(x) D(x,h) (A(x) C(x) D(s,h)）B(s)此謂詞公式成立（但沒有區(qū)分詩人和作家，還可有更好的表達(dá)形式）6、 對(duì)于題目給定的解釋，求下列各公式相應(yīng)的真值（1） A = "(x) P(x) Q(x) R(a)，解釋 D =1,2,3，P(x): x2+x=2; Q(x): x是素?cái)?shù)；R(x): x<3; a = 1解： 根據(jù)解釋，A變?yōu)?（P(1) Q(1)）（P(2) Q(2)）（P(3) Q(2)）R(

32、1)，根據(jù)P(x), Q(x), R(x)的定義，顯然P(1) Q(1) = 1，P(2) Q(2) = 1，P(3) Q(2) = 1，R(1) =1，所以整個(gè)公式解釋為真（2） A=P(a, f(b) P(b,f(a), B="(x) $(y)P(y,x), C = $(y) "(x)P(y,x), E = "(x) "(y)P(x,y) P(f(x),f(y)，解釋：D=2,3, a = 3, b = 2, f(2)=3, f(3) =2，P(2,2)=0, P(2,3)=0, P(3,2)=P(3,3) = 1解： 根據(jù)解釋，A變?yōu)?P( 3,

33、3 ) P( 2, 2 ) = 1 0 = 0 ，真值為假B變?yōu)?(P(2,2) P(3,2) (P(2,3) P(3,3) = （01）（01）= 1，真值為真C變?yōu)?(P(2,2) P(2,3) (P(3,2) P(3,3) = （00）（11）= 1，真值為真E變?yōu)?(P(2,2) P(3,3) (P(2,3) P(3,2) (P(3,2) P(2,3) (P(3,3) P(2,2) = （01）（01）（10）（10）= 0，真值為假7、 設(shè)論域?yàn)檎麛?shù)集合Z，試判定下面各公式是否是永真式，矛盾式或可滿足式（1）"(x)x>-10x20答：為假命題（2）$(x)2x>

34、;8x2-6x+50答：為真命題，當(dāng)4，5使?jié)M足謂詞公式（3）"(x) $(y)x+y=1024答：為真命題，對(duì)任意整數(shù)x，y取值為1024-x及可（4）$(y) "(x)xy<10x+y2答：為真命題，y=0及成立8、 試對(duì)公式"(x) $(y)P(x,y) Q(x)構(gòu)造一個(gè)解釋，使在該解釋下公式取值真例如：在整域內(nèi)，P(x,y) 為xy >0, Q(x) 為 x為不為0，那么上述公式解釋為，對(duì)任意一個(gè)整數(shù)x，都存在整數(shù)y，如果x乘y大于0，則x不等于0。顯然是個(gè)真命題。9、 證明下列各式成立：（1）"(x) "(y)P(x) Q

35、(y) ?$(x)P(x) "(y)Q(y)證明：右式 ? "(x) "(y) P(x) Q(y) ? "(x) P(x) "(y)Q(y) ?$(x)P(x) "(y)Q(y)（2）$(x) $(y) P(x) Q(y) ?"(x) P(x) $(y) Q(y)證明：右式 ? $(x) $(y) P(x) Q(y) ? $(x) P(x) $(y) Q(y) ?"(x) P(x) $(y) Q(y)（3）$(y) "(x) P(x,y) ?"( y) $( x) P(x,y) 證明：右式 ?

36、"( y) "(x) P(x,y) ?"( y) $( x) P(x,y) 10、 判別$(x)P(x) Q(x)? $(x)P(x) $(x)Q(x)是否成立，如果成立，請(qǐng)給出證明；如果不成立，找一個(gè)解釋予以說明解：$(x)P(x) Q(x) ? $(x) P(x) Q(x) ? $(x) P(x) $(x)Q(x) ? "(x) P(x) $(x)Q(x) 顯然和$(x)P(x) $(x)Q(x)不等價(jià)，現(xiàn)構(gòu)造如下解釋設(shè)論域?yàn)镈=a,b，P(a) = 0, P(b) = 1, Q(a) = 0, Q(b) = 0, 則$(x)P(x) Q(x)解釋為

37、真，而$(x)P(x) $(x)Q(x)解釋為假，所以不等價(jià)11、 把下列公式化為等價(jià)的前束范式，再求出對(duì)應(yīng)的SKolem范式（1）("(x)P(x) $(y)P(y)解：原式 ? （"(x)P(x)$(y)P(y)）? "(x)P(x) "(y) P(y) ? "(x)( P(x) P(x) ? F（2）("(x)P(x) $(y) "(z)Q(y,z)解：原式 ? "(x)P(x) " (y) $ (z) Q(y,z) ? "(x) $ (z)（P(x) Q(x,z)）其SKolem范式為：

38、"(x) （P(x) Q(x,f(x)）（3）"(x) "(y) $(z)P(x,y,z) $(u)Q(x,u) $(v)Q(y,v)解：原式 ?"(x) "(y) $(z) $(u) $(v) P(x,y,z) Q(x,u) Q(y,v)其SKolem范式為："(x) "(y) P(x,y,f(x,y) Q(x,g(x,y) Q(y,l(x,y)（4）"(x) P(x,0) ($(y)P(y,f(x) "(z)Q(x,z)解：原式 ? "(x) P(x,0) ($(y)P(y,f(x) &qu

39、ot;(z)Q(x,z) ? "(x) $(y) "(z) P(x,0) (P(y,f(x) Q(x,z)其SKolem范式為："(x) "(z) P(x,0) (P(g(x),f(x) Q(x,z)12、 設(shè)G的前束范式為$(x) "(y)P(x,y)，其中P(x,y)不含x,y以外的變?cè)辉O(shè)f是不出現(xiàn)在P(x,y)中的函數(shù)符號(hào)。證明：G是永真式當(dāng)且僅當(dāng)$(x) P(x,f(x)為永真式證明：1）充分性：當(dāng)G為永真式，及至少存在一個(gè)x=a，使得"(y)P(a,y)為永真，及對(duì)論域中任意的元素b，P(a,b)為真，設(shè)函數(shù)f（a）= b

40、,那么P(a, f(a)為真，及$(x) P(x,f(x)為真2）必要性：當(dāng)$(x) P(x,f(x)為永真時(shí)，及至少存在一個(gè)x=a, 在任意的f(a)取任意論域中的值時(shí)，都為真，及"(y)P(a,y)為真，所以G為永真綜上所述，命題成立13、 證明下列各式成立（1）$(x) $(y)P(x) Q(y) T$(x)P(x)證明：左式 ? $(x) P(x) $(y)Q(y) T $(x)P(x)（2）($(x)P(x) Q(a) T$(x)P(x) Q(a)證明：左式 ? $(x)P(x) Q(a) ? $(x)P(x) Q(a)（3）"(x)P(x) Q(x) "

41、;(x)Q(x) TP(x)證明：左式 ? "(x)(P(x) Q(x) Q(x) T (P(x) Q(x) Q(x) TP(x)（4）"(x)P(x) Q(x) "(x)P(x) T"(x)Q(x)證明：左式 ? "(x)(P(x) Q(x)P(x) T "(x)Q(x)（5）$(x)P(x) Q(x) "(x)P(x) T"(x)Q(x)證明：左式 ? ("(x)P(x) "(x)Q(x) "(x)P(x) T"(x)Q(x)14、 判別下面各式是否成立，并說明理由（1）

42、P(x) "(x)Q(x) T$(x) P(x) Q(x)答：不成立，因?yàn)楫?dāng)P(x)恒為假時(shí)，左式成立，但右式不成立（2）$(x)P(x) "(x)Q(x) T"(x) P(x) Q(x)答：成立，因?yàn)樽笫?? "(x) P(x) "(x)Q(x) T "(x) P(x) Q(x) ? "(x) P(x) Q(x)（3）"(x) P(x) Q(x) T$(x)P(x) "(x)Q(x)答：不成立，因?yàn)樵谌缦陆忉屒闆r，左式成立，而右式不成立D = a,b , P(a)=Q(a)=0, P(b)=Q(b)=1

43、15、 下面給出了對(duì)"(x) P(x) Q(x) T"(x) P(x) "(x)Q(x)的證明：（證明過程略）試判斷這個(gè)證明是否正確。你能給出一個(gè)證明嗎？答：這個(gè)證明不正確，因?yàn)椋喝绻?P T Q 則QT P 而 P T Q不一定成立，因此在這個(gè)證明過程中，第二步到第三步的蘊(yùn)含不成立。16、 演繹下列各式（1）$(x)P(x) Q(x) T "(x) P(x) $(x)Q(x)證明：運(yùn)用CP法1$(x)P(x) Q(x) p 2P(a) Q(a)ES23"(x) P(x)p(附加前提)4P(a)US15Q(a)T2,3I6$(x)Q(x)EG5

44、7"(x) P(x) $(x)Q(x)CP3,6（2）"(x)P(x) "(x)Q(x) T $(x)P(x) Q(x) 證明：1"(x)P(x) "(x)Q(x)p2"(x) P(x)"(x)Q(x)T1E3$(x) P(x)"(y)Q(y)T2E4$(x) "(y)(P(x)Q(y)T3E5"(y)(P(a)Q(y)ES46(P(a)Q(a)GS57P(a) Q(a)T6E8$(x)P(x) Q(x) EG7（2）"(x) P(x) Q(x) T $(x)P(x) Q(x) 證明：

45、1"(x) P(x) Q(x)p2"(x) P(x) Q(x)T1E3P(a) Q(a)US24P(a) Q(a)T3E5$(x)P(x) Q(x) EG4（3）"(x) P(x) Q(x)，"(x) R(x) Q(x) T"(x) R(x) P(x)證明：1"(x) R(x) Q(x)p2R(x) Q(x)US13Q(x) R(x)T2E4"(x) P(x) Q(x)p5P(x) Q(x)US46P(x) R(x)T3,5I7R(x) P(x)T6E8"(x) R(x) P(x)UG7（4）"(x) P(x) (Q(y) R(x), $(x)P(x) T Q(y) $(x) P(x) R(x)證明：1"(x) P(x) (Q(y) R(x