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

1、習(xí)題一1、利用邏輯聯(lián)結(jié)詞把以下命題譯成符號(hào)邏輯形式(1) 他既是本片的編劇,又是導(dǎo)演-PAQ(2) 銀行利率一降低,股價(jià)隨之上揚(yáng)-P-Q(3) 盡管銀行利率降低,股價(jià)卻沒有上揚(yáng)-PAQ(4) 占據(jù)空間的、有質(zhì)量而且不斷變化的對(duì)象稱為物質(zhì)-M(SAPAT)(5) 他今天不是乘火車去北京,就是隨旅行團(tuán)去了九寨溝-PQ(6) 小張身體薄弱,但是極少生病,并且頭腦好使-PAQAR(7) 不識(shí)廬山真面目,只緣身在此山中-P-Q(解釋：由于身在此山中,所以不識(shí)廬山真面目)(8) 兩個(gè)三角形相似,當(dāng)且僅當(dāng)他們的對(duì)應(yīng)角相等或者對(duì)應(yīng)邊成比例-S(EVT)(9) 如果一個(gè)整數(shù)能被6整除,那么它就能被2和3整除.如

2、果一個(gè)整數(shù)能被3整除,那么它的各位數(shù)字之和也能被3整除解：設(shè)P-一個(gè)整數(shù)能被6整除Q-一個(gè)整數(shù)能被2整除R-一個(gè)整數(shù)能被3整除S-一個(gè)整數(shù)各位數(shù)字之和能被3整除譯為：(P一(QAR)A(RS)2、判別下面各語句是否命題,如果是命題,說出它的真值(1)BASIC語言是最完美的程序設(shè)計(jì)語言-Y,T/F(2)這件事大概是小王干的-N(3)x(4)略4、利用真值表方法驗(yàn)證以下各式為永真式(1)(8)略5、證實(shí)以下各等價(jià)式(1)(PAQ)V(PAQ)V(PAQ)P證實(shí)：左式(PVQ)A(PVQ)V(PAQ)PV(PAQ)V(PAQ)VTV(PAQ)P右式(2)(P一Q)A(R一Q)(PVR)一Q證實(shí)：左

3、式(PVQA(RVQ)=64-N(4)可導(dǎo)的實(shí)函數(shù)都是連續(xù)函數(shù)-Y,T/F(5)我們要發(fā)揚(yáng)連續(xù)作戰(zhàn)的作風(fēng),再接再厲,爭(zhēng)取更大的勝利-N(6)客觀規(guī)律是不以人們意志為轉(zhuǎn)移的-Y,T(7)到2021年,中國的國民生產(chǎn)總值將趕上和超過美國-Y,N/A(8)凡事都有例外-Y,F3、構(gòu)造以下公式的真值表,并由此判別哪些公式是永真式、矛盾式或可滿足式(1)(PV(PAQ)一Q解：PQPAQPV(PAQ)(PV(PAQ)一Q可滿足式00001011111001011011(PAR)VQ(PVR)VQ(PVR)一Q右式(3) P一(QVR)(P一Q)V(PR)證實(shí)：左式PVQVRPVQVPVR(PVQV(PV

4、R)(P一Q)V(P一R)右式(4) (PAQ)V(RAQ)V(RAP)(PVQ)A(RVQ)A(RVP)證實(shí)：左式(PVR)AQ)V(RAP)(PVR)VR)A(PVR)VP)A(QVR)A(QVP)(PVQ)A(RVQ)A(RVP)右式6、如果PVQQVR,能否斷定PR?如果PAQQAR,能否斷定PR?如果PR,能否斷定PR?解：(1)如果PVQQVR,不能判斷PR,由于如果Q=PVR,那么PVQPVPVRQVR,(1P可以不等價(jià)于R.(2)如果PAQQAR,不能判斷PR,由于如果Q=PAR,那么PAQPAPARQAR,(1P可以不等價(jià)于R.(3)如果PR,那么有PR,由于PR,那么P&l

5、t;->R為永真式,及有P<->R為永真式,所以PR.7、檢查T和J是否滿足結(jié)合率解：用真值表方式檢查PQRPTQQTR(PTQ)TRPT(QTR)00011110011101010111101110011001110101110011001101110011由上表可知,T不滿住結(jié)合率PQRPJ1QQJR(PJ1Q)J1RPJ(QJ1R)00011000011001010001101100011000110101000011000101110000由上表可知,J不滿住結(jié)合率8、把以下各式用T等價(jià)表示出來(1) (PAQ)VP解：原式(PTQ)T(PTQ)V(PTP)(PTQ)

6、T(PTQ)T(PTQ)T(PTQ)T(PTP)T(PTP)(2) P一(P一Q)解：原式PVPVQQ(QTQ)T(QTQ)(3) (QVR>)八P解：原式(PVQVR)八PPV(QAP)V(RAP)(PTP)V(QTQ)A(PTP)V(RA(PTP)(PTP)V(QTQ)T(PTP)T(QTQ)T(PTP)V(RT(PTP)T(RT(PTP)設(shè)：(PTP)=N(QTQ)T(PTP)T(QTQ)T(PTP)=L(RT(PTP)T(RT(PTP)=M那么上式(NTN)T(LTL)T(NTN)T(LTL)T(MTM)(4)PAQA(?P)解：原式PAQA(RVP)(PTP)A(QTQ)A(P

7、TP)T(RTR)(PTP)T(QTQ)T(PTP)T(QTQ)A(PTP)T(RTR)設(shè)：(PTP)T(QTQ)T(PTP)T(QTQ)=N(PTP)T(RTR)=M那么上式(NTM)T(NTM)9、證實(shí)：>是最小功能完備集合證實(shí)：由于,V是最小功能完備集合,所以,如果>能表示出V,那么其是功能完備集合.由于PVQ(P)-Q,所以>是功能完備集合.由于一不能相互表示,所以一是最小功能完備集合；同理可證：非,條件非也能將或表示出來：PVQ(P!一Q)10、證實(shí)：,不是功能完備集證實(shí)：PVQ沒有方法通過,的公式表達(dá)出來,由于PQPVQPVP-(PVP)PVQ0000100110

8、11101011111010所以,通過,不能表達(dá)出真值為三個(gè)1或1個(gè)1的情況,因此,不能表達(dá)出PVQ所以不是功能完備集.11、用和A把公式PVQVR和(PVQ一R表示出來解：(PVQ)VR(PAQV(PAQ)VR(PAQ)V(PAQ)八R)V(PAQV(PAQ)AR)(PAQ)八(PAQ)八R)V(PAQ八(PAQ)八R)(PAQ八(PAQ)八R)八(P八Q八(PAQ)八R)(PVQ)一R(PAQ八(PAQ)八R)12、分別利用真值表法和等價(jià)變換法求以下公式的主合取范式及主析取范式P一(RAQ)一S)解：真值表法PQRSRAQ(RAQ)一SP一(RAQ)一S)00000110001011001

9、00110011011010001101010110110101011111110000111001011101001110110111100011110101111101001111111所以：主合取范式為=PVQVRVS=M14主析取范式為=m1Vm2Vm3Vm4Vm5Vm6Vm7Vm8Vm9Vm10Vm11Vm12Vm13Vm14Vm16等價(jià)變換法(略)(2)(PVQ)一(P<->Q解：真值表法PQPVQP<->Q(PVQ一(P<->Q00100011111011111001所以：主合取范式為=PVQ=M0主析取范式為=(PAQ)V(PAQ)V(PAQ

10、)=m1Vm2Vm3等價(jià)變換法(略)P一(RA(Q-P)解：真值表法PQRCHPRA(Q-P)P一(RA(Q-P)000101001111010001011001100100101111110100111111所以：主合取范式為=(PVQVR)A(PVQVR)=M4AM6主析取范式為=(PAQAR)V(PAQAR)V(PAQAR)V(PAQAR)V(P八QAR)V(PAQAR)=m0Vm1Vm2/m3Vm5Vm7等價(jià)變換法(略)(4)(P一(QAR)A(P一(QAR)解：真值表法PQRQARQARP-(QAR)P一(Q八R)(P-(QAR)A(P一(QAR)000011110010010001

11、0001000111010010001010101000101100001011110111所以：主合取范式為=(PVQVR)A(PVQVR)A(PVQVR)A(PVQVR)A(PVQVR)A(PVQVR)=M1AM2AM3AMMM5AM6主析取范式為=(PAQAR)V(PAQAR)=m0Vm7等價(jià)變換法(略)13、 用轉(zhuǎn)化范式的方法判別下面各組公式是否等價(jià)(1) (-Q一(PAQ)和(P一QA(CHP)解：(P-Q一(PAQ(pvQV(PAQ(PAQV(PAQ-合取范式(P一Q)A(QHP)(PVQ)A(QVP)PV(QAQ)P(PAQV(PAQ)-合取范式兩式的合取范式相同,所以等價(jià)(2)

12、 (QA(PR)和P一(QAR)解：(P-QA(PR)(PVQ)A(PVR)-合取范式P(QAR)PV(QAR)(PVQ)A(PVR)-合取范式兩式的合取范式相同,所以等價(jià)14、 從A,B,C,D4個(gè)人中派2人出差,要求滿足以下條件：如果A去,那么必須在C或D中選一人同去；B和C不能同日去；C和D不能同時(shí)去.用構(gòu)造范式的方法決定選派方案.解：由題設(shè)A:A去,B:B去,C:C去,D:D去那么滿足條件的選派應(yīng)滿足如下范式：(A-(C?D)A(BAC)A(CAD)構(gòu)造和以上范式等價(jià)的主析取范式(A-(C?D)A(BAC)A(CAD)?(AABACAD)V(AABACAD)V(AABACAD)V(AA

13、BACAD)V(AABACAD)V(AABACAD)V(AABACAD)V(AABACAD)共有八個(gè)極小項(xiàng),但根據(jù)題意,需派兩人出差,所以,只有其中三項(xiàng)滿足要求：(AABACAD),(AABACAD),(AABACAD)即有三種方案：A和C去或者A和D去或者B和D去.15、 證實(shí)以下蘊(yùn)含試：(1) PfQ=>P>(PAQ)證實(shí)：PQ?PVQ?TA(PVQ)?(PVP)A(PVQ)?PV(PAQ)?Pf(PAQ)所以,這是個(gè)等價(jià)式,因此也是個(gè)蘊(yùn)含式(2) (P-Q)Q=>(PVQ)證實(shí)：(P-Q)-Q?(PVQ)VQ?(PAQ)VQ?(PVQ)A(QVQ)?(PVQ)AT?(P

14、VQ)所以,這是個(gè)等價(jià)式,因此也是個(gè)蘊(yùn)含式(3) PAPAR=>S證實(shí)：PAPAR?F=>S(F可蘊(yùn)含任何命題公式)(4) P=>Q/RVR證實(shí)：P=>T?QVRVR16、 證實(shí)蘊(yùn)含關(guān)系的性質(zhì)1、性質(zhì)2和3證實(shí)：性質(zhì)1A=>A由于在任意的解釋下,公式A的真值顯然和自己相同,當(dāng)然在為真時(shí)也相同,所以蘊(yùn)含成立.性質(zhì)2如果A=>B且B=>A,貝UA?B由于A=>B且B=>A及(A-B)A(B-A)為永真式,那么A<->B為永真式.所以A?B.性質(zhì)3如果A=>B且A永真式,那么B必為永真式由于(A-B)為永真式,且A為永真式,那么

15、只有B為永真式才能滿足(A-B)為永真式成立.所以結(jié)論為真.17、 證實(shí)定理1.12證實(shí)：A=>B,當(dāng)且僅當(dāng)B=>A證實(shí)：A=>B?A-B為永真式？-BfA為永真式？B=>-AA=>B,當(dāng)且僅當(dāng)B=>A18、 一個(gè)有錢人生前留下了一筆珍寶,藏在一個(gè)隱秘處.在他留下的遺囑中指出尋找珍寶的線索如下：(1) 如果藏寶的房子靠近池塘,那么珍寶不會(huì)藏在東廂房.(2) 如果房子的前院栽有大柏樹,那么珍寶就藏在東廂房.(3) 藏寶房子靠近池塘.(4) 要么前院栽有大柏樹,要么珍寶埋在花園正中地下.(5) 如果后院栽有香樟樹,珍寶藏在附近.請(qǐng)利用蘊(yùn)含關(guān)系找出藏寶處.解：根據(jù)

16、給定的條件有下述命題：P:珍寶藏在東廂房Q藏寶的房子靠近池塘R：房子的前院栽有大柏樹S:珍寶藏在花園正中地下T:后院栽有香樟樹M珍寶藏在附近根據(jù)題意,得出：(QHP)A(R-P)AQA(RVS)A(T-M)T?(QHP)A(R-P)AQA(RVS)A(T-M)TPA(FHP)A(RVS)A(TM)TRA(RVS)A(T-M)TSA(TfM)TS即珍寶藏在花園正中地下19、 判斷以下蘊(yùn)含關(guān)系式是否成立：(1) QA(PfQ)TP解：當(dāng)左端公式解釋為1時(shí),Q必須為1;Q為1,P比為1;所以,右端公式也為1;因此,蘊(yùn)含關(guān)系成立(2) (P-(QVR)A(Q-(PAR)TPR解：左端公式？Q<-

17、>(PAR),當(dāng)解釋為1是,分兩種情況,PAR與Q同為1,那么PfR也為1;PAR與Q同為0,如果此時(shí)P=1,R=0,那么P-R為0;因此,此蘊(yùn)含式不成立(3)PA(PfQ)TQ解：左端公式解釋為1時(shí),P必為0;當(dāng)P為0時(shí),那么Q可為0,也可為1;因此,此蘊(yùn)含式不成立(4) (PVQ)A(P-Q)A(P-R)TR解：當(dāng)左端公式按P=0,Q=1,R=0解釋時(shí),為1,但右端不為1;因此,此蘊(yùn)含式不成立(PAQ)-R)A(PVQ)A(Q-P)TR解：當(dāng)左端公式按P=1,Q=1,R=0解釋時(shí),真值為1,但右端為0;因此,此蘊(yùn)含式不成立20、 演繹證實(shí)下面各蘊(yùn)含式：(1)PVQ,RfQTPfR證實(shí)

18、：運(yùn)用cp法,將結(jié)論條件式的前件作為前提,證實(shí)步驟如下1 Pp(附加前提)2 PVQp3 QT1,2I4 RHQp5 RT3,4I6 PRCP1,5(2) (PVQ)(RAS),(SVE)-BTP-B證實(shí)：運(yùn)用cp法,將結(jié)論條件式的前件作為前提,證實(shí)步驟如下1 Pp(附加前提)2 (PVQ)-(RAS)p3 RAST1,2I4 (SVE)fBp5 BT3,4I6 FBCP1,5(3) Pf(Q-R),(RAS)-E,Bf(SAE)TPf(QfB)B,證實(shí)：運(yùn)用cp法,將結(jié)論條件式的前件作為前提,先將結(jié)論進(jìn)行等價(jià)變換為(PAQ因此PAQ可作為附加前提,證實(shí)步驟如下1 PAQp(附加前提)2 P(

19、Q-R)p3 (PAQ-RT2E4 RT1,3I5 (RAS)fEp6 ET4,6I7 B<(SAE)p8 BT6,7I9 (PAQfBcp1,8(4) (R-Q)A(R-S),(Q-E)A(S-B),(EAB),(PfR)TP證實(shí)：運(yùn)用反證方法,將結(jié)論的非納入前提,證實(shí)步驟如下1 Pp(附加前提)2 PRp3 RT1,2I4 (RfQ)A(R-S)p5 QAST3,4I6 (QfE)A(S-B)p7 EABT5,6I8 (EAB)p9 F(矛盾式)T7,8EPf(QfR),Qf(RfS)TPf(QfS)證實(shí)：運(yùn)用cp法,將結(jié)論條件式的前件作為前提,證實(shí)步驟如下1Pp(附加前提)2P(Q

20、fR)p3QRT1,2I4g(RfS)p5R-(QS)T4E6QST3,5I7P-(QS)CP1,621、把以下句子演繹成邏輯形式,并給出證實(shí)(1) 如果資方拒絕增加工資,那么罷工不會(huì)結(jié)束；除非罷工超過一年,并且資方撤換了經(jīng)理；現(xiàn)在資方拒絕了增加工資,罷工剛開始.判斷罷工能否停止.解：根據(jù)題意,有如下命題P:資方拒絕增加工資Q:罷工結(jié)束R:罷工超過一年S:資方撤換了經(jīng)理所以,前提條件符號(hào)化為PQ;gRAS;PAR因此,推理過程如下：1 PARp2 P>Qp3QT1,2I所以,罷工不會(huì)結(jié)束(2)某公司發(fā)生了一起盜竊案,經(jīng)仔細(xì)偵察,掌握了如下一些事實(shí):被盜現(xiàn)場(chǎng)沒有留下任何痕跡失盜時(shí),小花或那

21、么小英正在卡拉ok廳如果失竊時(shí)小胖正在附近,他就會(huì)習(xí)慣性地破門而入偷走東西后揚(yáng)長而去如果失盜時(shí)小花正在卡拉ok廳唱歌,那么金剛是最大的嫌疑者如果失盜時(shí)小胖不在附近,那么他的女友小英會(huì)和他一起外出旅游如果失盜時(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,QVR,SfP,PP SfP S S>R R QVR QT QfT TT即金剛是偷竊者R,RMPTIPTIPIPI22、 設(shè)

22、A1,A2,An是一組命題公式,如果存在一個(gè)解釋使A1AA2AAAn取值真,就稱這組公式是相容的,否那么稱為不相容的.不相容意味著A1AA2AAAn蘊(yùn)含一個(gè)矛盾式,現(xiàn)在判別以下各命題組是否相容(1) Pf(Q-R),S-(QAR),PAS解：根據(jù)題意(P-(QfR)A(S-(QAR)A(PAS)T(Q-R)A(QAR)TRARTF所以,這組命題公式不相容(2) PVQ,RVS,Q,S解：根據(jù)題意(PVQ)A(RVS)AQASTPAR所以,當(dāng)P=1,Q=0R=0,S=0時(shí),合取式解釋為1,因此這組命題公式相容(3) P<->Q,Q-R,RVS,PS,S解：根據(jù)題意(P<->

23、;Q)A(CHRA(RVS)A(PS)AST(P<->Q)A(CHR)ARAPT(P<->Q)AQAPTF所以,這組命題公式不相容(4) P-Q,P-R,QR,P解：根據(jù)題意(PfQ)A(P-R)A(GHR)APTQARA(GHR)TRARTF所以,這組命題公式不相容23、 利用消解法證實(shí)以下各蘊(yùn)含式：(1) R-Q,RVS,SfQ,P-QTP證實(shí)：FHQ?RVQ因此子句集合=RVQSVQ,RVS,PVQ,P消解過程如下：1 RVQp2 SVQp3 RVSp4 PVQp5 Pp6 Q由4,5歸結(jié)7 R由1,6歸結(jié)8 S由2,6歸結(jié)9 S由3,7歸結(jié)10 FLASE口由8

24、,9歸結(jié)導(dǎo)出空子句(2)(P-Q)f(RVS),(QfP)VR,RTP<->Q證實(shí)：(P-Q)-(RVS)?PVQVRVS(QfP)VR?QVPVR(P<->Q)?(AQA(QHP)?(P-QV(QHP)?(PAQ)V(QAP)?(PVQ)A(PVQ)因此子句集合=PVQVRVS,QVPVR,PVQPVQ,R消解過程如下：1PVQVRVSp2QVPVRp3PVQp4PVQp5Rp6QVP由2,5歸結(jié)7P由3,6歸結(jié)8QVRVS由1,7歸結(jié)9PVS由2,8歸結(jié)10PVR由2,3歸結(jié)11Q由4,6歸結(jié)12 RVS由8,11歸結(jié)13 QVPVS由2,12歸結(jié)14 PVRVS(

25、此題可能有問題)(3)Pf(QfR),Qf(RfS)TPf(QfS)證實(shí)：P(QfR)?PVQVRg(RfS)?QVRVS(P-(QfS)?PAQAS因此子句集合=PV-QVRQVRVS,P,Q-S消解過程如下：1PVQVRP2PP3QVR由1,2歸結(jié)4Qp5R由3,4歸結(jié)6QVRVSp7Sp8QVR由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ù)ARa(x)譯如下："(x)(Ra(x)-R(x)A"(x)(R(

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

27、-B(x)?C(x)(6) 但凡存錢的人都想有利息,如果沒有利息,人們就不會(huì)存錢解：A(x)-x是存錢的人F(x,y)-x想有yP-存錢沒有利息Q：-人們不存錢a:-利息譯如下："(x)(A(x)-F(x,a)A(P-Q)2、 設(shè)論域D=0,1,2,把以下公式用不含量詞的公式表示出來(1) "(x)P(x)A$(x)Q(x)解：上式？P(0)AP(1)AP(2)A(Q(0)VQ(1)VQ(2)(2) "(x)P(x)-Q(x)解：上式？(P(0)-Q(0)A(P(1)-Q(1)A(P(2)-Q(2)(3) "(x)P(x)V$(x)Q(x)解：上式？(P

28、(0)AP(1)AP(2)VQ(0)VQ(1)VQ(2)3、指出以下公式中的約束變?cè)妥杂勺冊(cè)?并確定公式的轄域略4、對(duì)以下公式中的變?cè)M(jìn)行代換,以使任何變?cè)荒芗仁羌s束變?cè)质亲杂勺冊(cè)?1) "(x)$(y)P(x,y)-Q(y,z)V"(z)R(x,y,z)解：代換如下"(x)$(y)P(x,y)-Q(y,z)V"(s)R(u,v,s)(2) ("(x)P(x)-R(x)VQ(x)A($(x)R(x)-$(z)S(x,z)解：代換如下("(x)P(x)-R(x)VQ(u)A($(y)R(y)f$(z)S(u,z)5、把以下語句符號(hào)

29、化,并確定相應(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=0Vy=0)A(x-1w0).(x-1)(x+1)豐0)這是一個(gè)可滿足式,但不是永真式,由于存在x=-1時(shí),謂詞公式不成立,但其它情況均成立,如果論域中不包含-1,為真,包含就不成立(2)老實(shí)的人都講實(shí)話.小林不是老實(shí)的,因而小林不講實(shí)話解：H(x)-x老實(shí)T(x)-x講真話a-小林譯如下：("(x)(H(x)-T(x)AH(

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

31、D(x,y)-x創(chuàng)作yh-哈姆雷特s-莎士比亞譯如下：("(x)(A(x).B(x)A(C(x)B(x)A(B(x).D(x,h)A(A(x)C(x)AD(s,h)-B(s)此謂詞公式成立(但沒有區(qū)分詩人和作家,還可有更好的表達(dá)形式)6、對(duì)于題目給定的解釋,求以下各公式相應(yīng)的真值(1) A="(x)P(x)VQ(x)AR(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)VQ(1)A(P(2)VQ(2)A(P(3)VQ(2)AR(1),根據(jù)P(x),Q(x),R(x)的定義,顯然P(1)VQ(1

32、)=1,P(2)VQ(2)=1,P(3)VQ(2)=1,R(1)=1,所以整個(gè)公式解釋為真(2) A=P(a,f(b)AP(b,f(a),B="(x)$(y)P(y,x),C=$(y)"(x)P(y,x),E="(x)"(y)P(x,y)fP(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)镻(3,3)AP(2,2)=1A0=0,真值為B變?yōu)?P(2,2)VP(3,2)A(P(2,3)VP(3,3)=(0V1)A(0V1)=1,真值為真

33、C變?yōu)?P(2,2)AP(2,3)V(P(3,2)AP(3,3)=(0A0)V(1A1)=1,真值為真E變?yōu)?P(2,2)-P(3,3)A(P(2,3)-P(3,2)A(P(3,2)-P(2,3)A(P(3,3)fP(2,2)=(0-1)A(0-1)A(1-0)A(1-0)=0,真值為假7、設(shè)論域?yàn)檎麛?shù)集合Z,試判定下面各公式是否是永真式,矛盾式或可滿足式,、_一2一(1) "(x)x>-10Ax>0答：為假命題(2) $(x)2x>8Ax2-6x+5W0答：為真命題,當(dāng)4,5使?jié)M足謂詞公式(3) "(x)$(y)x+y=1024答：為真命題,對(duì)任意整數(shù)x

34、,y取值為1024-x及可(4) $(y)"(x)xy<10Vx+y>2答：為真命題,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、 證實(shí)以下各式成立:(1) "(x)"(y)P(x)-Q(y)$(x)P(x)證實(shí)：右式"(x)"(y)P(x)VQ(y)"(y)Q(y)(2) $(x)$(y

35、)P(x)-Q(y)"(x)P(x)證實(shí)：右式$(x)$(y)P(x)VQ(y)“"(y)Q(y)"(x)P(x)V"(y)Q(y)$(x)P(x)-f$(y)Q(y)$(x)P(x)V$(y)Q(y)"(x)P(x)f$(y)Q(y)(3) $(y)"(x)P(x,y)"(y)$(x)P(x,y)證實(shí)：右式"(y)"(x)P(x,y)"(y)$(x)P(x,y)10、 判別$(x)P(x)fQ(x)$(x)P(x)f$(x)Q(x)是否成立,如果成立,請(qǐng)給出證明；如果不成立,找一個(gè)解釋予以說明

36、解：$(x)P(x)fQ(x)$(x)P(x)VQ(x)$(x)P(x)V$(x)Q(x)"(x)P(x)f$(x)Q(x)顯然和$(x)P(x)f$(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)解釋為真,而$(x)P(x)-$(x)Q(x)解釋為假,所以不等價(jià)11、 把以下公式化為等價(jià)的前束范式,再求出對(duì)應(yīng)的SKolem范式(1)("(x)P(x)-$(y)P(y)解：原式("(x)P(x)V$(y)P(y)"(x)P(x)A"(y)P(y)&qu

37、ot;(x)(P(x)AP(x)F(2) ("(x)P(x)-$(y)"(z)Q(y,z)"(x)$億)(P(x)AQ(x,z)A$(v)Q(y,v)AQ(x,u)AQ(y,v)解：原式"(x)P(x)A"(y)$(z)Q(y,z)其SKolem范式為："(x)(P(x)AQ(x,f(x)(3) "(x)"(y)$(z)P(x,y,z)A$(u)Q(x,u)解：原式"(x)"(y)$(z)$(u)$(v)P(x,y,z)其SKolem范式為："(x)"(y)P(x,y,f(x

38、,y)AQ(x,g(x,y)AQ(y,l(x,y)(4) "(x)P(x,0)-($(y)P(y,f(x)A"(z)Q(x,z)解：原式"(x)P(x,0)V($(y)P(y,f(x)A"(z)Q(x,z)"(x)$(y)"(z)P(x,0)V(P(y,f(x)AQ(x,z)其SKolem范式為："(x)"(z)P(x,0)V(P(g(x),f(x)AQ(x,z)12、 設(shè)G的前束范式為$(x)"(y)P(x,y),其中P(x,y)不含x,y以外的變?cè)?；設(shè)f是不出現(xiàn)在P(x,y)中的函數(shù)符號(hào).證實(shí)：G是永

39、真式當(dāng)且僅當(dāng)$(x)P(x,f(x)為永真式證實(shí)：1)充分性：當(dāng)G為永真式,及至少存在一個(gè)x=a,使得"(y)P(a,y)為永真,及對(duì)論域中任意的元素b,P(a,b)為真,設(shè)函數(shù)f(a)=b,那么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、 證實(shí)以下各式成立證實(shí)：左式(1) $(x)$(y)P(x)AQ(y)T$(x)P(x)(2) ($(x)P(x)AQ(a)證實(shí)：左式$(x)P(x)(3

40、) "(x)P(x)-Q(x)證實(shí)：左式"(x)(P(x)(4) "(x)P(x)VQ(x)證實(shí)：左式"(x)(P(x)$(x)P(x)A$(y)Q(y)T$(x)P(x)T$(x)P(x)Q(a)VQ(a)$(x)P(x)-Q(a)A"(x)Q(x)TP(x)AQ(x)TP(x)-Q(x)AQ(x)T(P(x)-Q(x)A"(x)P(x)T'(x)Q(x)VQ(x)AP(x)T"(x)Q(x)T"(x)Q(x)A"(x)P(x)T"(x)Q(x)$(x)P(x)fQ(x)A"

41、(x)P(x)證實(shí)：左式("(x)P(x)V"(x)Q(x)14、 判別下面各式是否成立,并說明理由(1) P(x)-"(x)Q(x)T$(x)P(x)AQ(x)答：不成立,由于當(dāng)P(x)恒為假時(shí),左式成立,但右式不成立(2) $(x)P(x)-"(x)Q(x)T'(x)P(x)-Q(x)答：成立,由于左式"(x)P(x)V"(x)Q(x)T"(x)P(x)VQ(x)"(x)P(x)-Q(x)(3) "(x)P(x)-Q(x)T$(x)P(x)-"(x)Q(x)答：不成立,由于在如下解釋

42、情況,左式成立,而右式不成立D=a,b,P(a)=Q(a)=0,P(b)=Q(b)=115、 下面給出了對(duì)"(x)P(x)VQ(x)T'(x)P(x)V"(x)Q(x)的證實(shí)：(證實(shí)過程略)試判斷這個(gè)證實(shí)是否正確.你能給出一個(gè)證實(shí)嗎？答：這個(gè)證實(shí)不正確,由于：如果PTQ那么QTP而PTQ不一定成立,因此在這個(gè)證實(shí)過程中,第二步到第三步的蘊(yùn)含不成立.16、 演繹以下各式(1) $(x)P(x)-Q(x)T"(x)P(x)-$(x)Q(x)證實(shí)：運(yùn)用CP法1$(x)P(x)-Q(x)2P(a)-Q(a)ES23"(x)P(x)p附加前提4P(a)US

43、15Q(a)T2,3I6$(x)Q(x)EG57"(x)P(x)-$(x)Q(x)CP3,6(2)"(x)P(x)-"(x)Q(x)T$(x)P(x)-Q(x)證實(shí)：1 "(x)P(x)f"(x)Q(x)p2 "(x)P(x)V"(x)Q(x)T1E3 $(x)P(x)V"(y)Q(y)T2E4 $(x)"(y)(P(x)VQ(y)T3E5 "(y)(P(a)VQ(y)ES46 (P(a)VQ(a)GS57 P(a)-Q(a)T6E8 $(x)P(x)-Q(x)EG7(2) "(x)P

44、(x)-Q(x)T$(x)P(x)-Q(x)證實(shí)：1 "(x)P(x)-Q(x)p2 "(x)P(x)VQ(x)T1E3 P(a)VQ(a)US24 P(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)證實(shí)：1 "(x)R(x)-Q(x)p2 R(x)Q(x)US13 Q(x)-R(x)T2E4 "(x)P(x)-Q(x)p5 P(x)-Q(x)US46 P(x)R(x)T3,5I7 R(x)-P(x)T6E8 "(x

45、)R(x)-P(x)UG7(4)"(x)P(x)f(Q(y)AR(x),$(x)P(x)TQ(y)A$(x)P(x)AR(x)證實(shí)：1 "(x)P(x)f(Q(y)AR(x)p2 P(a)-(Q(y)AR(a)US13 $(x)P(x)p4 P(a)ES35 Q(y)AR(a)T2,4I6 Q(y)AR(a)AP(a)T4,5I7 Q(y)A$(x)P(x)AR(x)EG617、 判別下面各個(gè)推理是否正確,如果不正確,指出錯(cuò)在什么地方(題目不再重復(fù))(1)答：不正確,全稱指定應(yīng)該變?yōu)槠渌莤的變?cè)?可修改為：P(y)-Q(x)(2)答：正確(3)答：不正確,全稱指定應(yīng)該使用

46、相同的個(gè)體常量,可修改為：P(a)VQ(a)(4)答：題目不正確,存在量詞的指導(dǎo)變?cè)獞?yīng)該是另外的變?cè)?hào)(5)答：不正確,存在量詞的轄域應(yīng)該包含全部的謂詞,可修改為：$(x)P(x)-Q(x)(6)答：不正確,對(duì)不同的個(gè)體常元應(yīng)該用不同的變?cè)M(jìn)行存在指定,可修改為：$(x)P(x)-Q(b)(7)答：不正確,推理過程中,應(yīng)該先使用存在指定,然后使用全稱指定18、 把下面蘊(yùn)含式變成SKolem范式,然后用消解法證實(shí)其正確性(1) "(x)P(x)-Q(x)T"(x)$(y)P(y)AR(x,y)-$(y)Q(y)AR(x,y)證實(shí)：首先,把結(jié)論否認(rèn)后作為附加前提,與原有前提一

47、起轉(zhuǎn)化為skolem范式"(x)P(x)-Q(x)A"(x)P(x)VQ(x)進(jìn)行變量替換："(x)P(x)VQ(x)$(u)$(y)"(x)"(v)P(x)T"(x)"(v)P(x)("(x)$(y)P(y)$(x)$(y)P(y)$(u)$(y)P(y)VQ(x)VQ(x)AP(a)AR(x,y)f$(y)Q(y)AR(x,y)A"(y)Q(y)AR(u,y)A"(v)Q(v)P(y)AR(b,a)AR(x,y)VR(x,y)VR(u,v)八R(u,y)AQ(v)VR(u,v)AQ(v)VR

48、(b,v)由skolem范式得到子句集合為:,Q(v)VR(b,v)P(x)VQ(x),P(a),R(b,a)利用代換進(jìn)行消解的過程如下：1234567(2)Q(v)VR(b,v)R(b,a)Q(a)P(x)VQ(x)P(a)P(a)口$(x)P(x)"(x)(P(x)1和2,代換a/v3和4,代換a/xVQ(x)-R(x),$(x)P(x),$(x)Q(x)T$(x)$(y)R(x)skolem范式($(x)P(x)-"(x)(P(x)$(y)R(x)AR(y)("(x)P(x)V"(x)(P(x)"(y)R(x)vR(y)VQ(x)-R(x

49、)AAQ(x)VR(x)$(x)P(x)A$(x)P(x)$(x)Q(x)AA$(x)Q(x)($(x)A"(x)"(x)"(y)P(x)"(y)R(x)VR(y)"(x)"(y)P(x)A$(u)Q(u)$(z)$(u)"(x)"(y)VR(y)AP(z)AV(P(y)V(P(y)P(x)VQ(u)AQ(y)AQ(y)R(y)T"(x)"(y)P(x)VR(y)VP(y)AP(a)AQ(b)由skolem范式得到子句集合為：P(x)VR(y)VP(y),P(x)V1P(x)VR(y)VQ(y)VR(y)VR(y)A$(z)P(z)A$(u)Q(u)A"(x)AR(x)VR(y)A$(z)P(z)VP(y)AP(x)VR(y)VQ(y)AP(x)VR(y)VQ(y)AR(x)R(y)VQ(y),R(x)VR(y),P(a),Q(b)AR(x)VR(y)AR(y)證實(shí)：首先,把結(jié)論否認(rèn)后作為附加前提,與原有前提一起轉(zhuǎn)化為2P(a)3R(y)V-Q(y)1和2,代換a/x4Q(b)5R(b)3和4,代換b/y6R(x)VR(y)7R(y)5和6,代換b