《6邏輯代數(shù)(上)：命題演算習(xí)題答案》由會員分享，可在線閱讀，更多相關(guān)《6邏輯代數(shù)(上)：命題演算習(xí)題答案（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、練習(xí)6.1 1. 判斷下列語句哪些是命題，若是命題其真值是什么？ （1）a+b+c。 （2）x>0。 （3）請進(jìn)！ （4）離散數(shù)學(xué)是計算機科學(xué)與技術(shù)專業(yè)的基礎(chǔ)課程。 （5）2009年7月我們?nèi)ヒ獯罄拿滋m旅游。 （6）啊！這里真漂亮。 （7）今天是星期四嗎？ （8）我明天或者后天去天津。 （9）如果買不到飛機票，我就去不了海南。 （10）除非你陪我，否則我不去。 （11）本命題是假的。 （12）如果雪是黑的，太陽從北邊升起。 解： （1）不是命題。 （2）不是命題。 （3）不是命題。 （4）是命題。真值是1。 （5）是命題。真值是0。 （6）不是命題。

2、 （7）不是命題。 （8）是命題。真值是0。 （9）是命題。真值是1。 （10）是命題。真值是lo （11）不是命題，是悖論。 （12）是命題。真值是lo 2. 指出下列語句哪些是原子命題，哪些是復(fù)合命題？并將復(fù)合命題形式化。 （1）他去了教室，也去了機房。 （2）今晚我去書店或者去圖書館。 （3）我昨天沒有去超市。 （4）我們不能既看電視又看電影。 （5）如果買不到飛機票，我就去不了海南。 （6）小王不是坐飛機去上海，就是坐高鐵去上海。 （7）喜羊羊和懶羊羊是好朋友。 （8）除非小李生病，否則他每天都會練習(xí)書法。 （9）侈而惰者貧，而力而儉者富。（韓非：《韓非子

3、?顯學(xué)》）解： （1）P：他去了教室。Q：他去了機房。PAQ （2）P：今晚我去書店。Q：今晚我去圖書館。PVQ （3）P：我昨天去超市。「P (4) P：我們看電視。Q：我們看電影?！?PAQ) (5) P：我買到飛機票。Q：我去海南。 (6) P：小王坐飛機去上海。Q：小王坐高鐵去上海。 (PVQ)Ai(PAQ)或者「(P分Q) (7) 原子命題 (8) P：小李生病。Q：小李每天都會練習(xí)書法?！窹oQ (9) P：侈。Q：惰。R：貧。((P/\Q)TR)A((「P/\「Q)T「R) 3. 判定下列符號串是否為命題公式。 (1) PAV^Q (2) (PVQR)f

4、S (3) (PVQ)fP (4) P->(PVQ (5) P/\(P~Q)/\(Pf「Q) (6) 「(PVQ)分(-nQA-nP) (7) (PA-nR)V(P-Q)解： (1) 不是 (2) 不是 (3) 是 (4) 不是 (5) 是 (6) 是 (7) 是 4.請給出下列命題公式的真值表。 (1)^PVQ p Q -p 「PVQ 0 0 1 1 0 1 1 1 1 0 0 0 1 1 0 1 (2)(-nPAQ)V(PA-nQ) p Q 「p -Q ^PA Q p/\ -Q (^PAQ)V(PA

5、^Q) 0 0 1 1 0 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0 0 0 0 0 (3)-i(PVQ)TR p Q R PVQ -.(PVQ) -n(PVQ)TR 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 (4)(PTQ)A(PA-

6、iQ) P Q PTQ P -Q (PTQ)A(PA^Q) 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 (5)(PTQ)VP p Q PTQ (PTQ)VP 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 練習(xí)6.2 1.試判定下列各式是重言式、可滿足式還是矛盾式。 (1)(P-Q)f(QfP) p Q PfQ Q~P (PfQL(QfP) 0 0 1 1 1 0 1 1 0 0 1 0 0 1

7、1 1 1 1 1 1 由表中最后一列可以看出，原式為可滿足式。 (2)-]P~(P~Q) p Q -1p P->Q 1P~(P~Q) 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1 1 由表中最后一列可以看出，原式為重言式。 (3)QA-i(P-Q) p Q P~Q n(P—Q) QAn(P~ Q) 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 由表中最后一列可以看出，原式為矛盾式。

8、 (4)P/\Q~(P0Q) p Q PAQ P<->Q P/\Qf(PoQ) 0 0 0 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 1 由表中最后一列可以看出，原式為重言式。 (5)(PTQ)\/(RTQ)T((P\/R)TQ) p Q R PTQ RTQ (PTQ)V(RTQ) PV R (PV R)今Q (PTQ)\/(RTQ)T((P\/R)TQ) 0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1

9、 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 由表中最后一列可以看出，原式為可滿足式。 2?證明下列邏輯等價式： (1) (AAB)V("iAAiB) 證明： 方法一 (AAB)V(nAA-]B) o(AV-iA)A(AVqB)A(BV-iA)A(BVnB) <^>TA(AV-iB)A(BVnA)AT 0(-1BVA)A(

10、nAVB) O(ETA)/\(ATE) oAaE 方法二: A B A<-> B AA B "1 A "I B -1AA 1B ((AAB)V(-1AA-1B)) B)<->(V(n AA-IB)) 0 0 1 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 由此真值表可見(A<^B)<^((AAB)V(-iAA-1E))是永真式，所以A<^B<^>(AAB)V(-iAAnE)成立。 方法三假設(shè)a為一

11、指派。 若a(A<^B)=b則a(A)=a(B)o (i) 若a(A)=a(B)=0o則a(nA)=a(-]B)=l,從而a(nAAnB)=l,進(jìn)而a(AAB)V(nAAnB)=l. (H)若□(A)=a(E尸1。則a(AAB)=b進(jìn)而a((AAB)V(nAAqB))=lo 若a(AOB)=0,則a(A)和a(E)不相等。從而a(nA)和a(nE)也不相等。則a(AAB)=O且a(-1AA-iB)=0,從而a((AAB)V(nAAqB))=0。 所以(AaE)O(AAE)V(nAA-iB) (2) A-(E~C)OE~(A~C) 證明： 方法一 A—(E~C) o-lAV(

12、B->C) o-lAV(nBVC) o-iBV(nAVC) o-lBV(A^C) oE~(A~C) 方法二： A B c C A-(E—C) A~C E-(A-C) A—(E—C)QB—(A—C) 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 I I 1 1

13、 1 由此真值表可見A~(E~C)(A-C)是永真式，所以A-(E-C)OE~(A-C)成立。 方法三： 假設(shè)a為一指派。 若a(A~(E-C))=l,分以下二種情況： (i) a(A)=l,則a(B-C>1.若a(E)=O,則a(B—(A-C))=l.若a(E尸1,則□(C)=l,從而a(E—(A—C))=l? (11)Q(A)=O,則a(A->C)=lo從而Q(E~(A-C))=l° 若a(A~(E-C))=0,則a(A)=l,a(B)=l,a(C)=0,從而a(E-(A-C))=0° 所以：A-(E~C)OE~(A~C) (3) A-(E~C)O(A~E)f(A-

14、C) 證明： (A~E)-(A-C) 0(-!AVB)->(nAVC) o-l(-1AVB)V(nAVC) o(A/\-]B)V(nAVC) o(AV-]AVC))A(nBVnAVC) BVnAVC o-iBV(A->C) oE~(A~C) (4) ~i(nAVqB)Vn(nAVE)oA 證明： n(1AV-|B)V~i(iAVB) <=>(AAB)V(AAnB) <^>AA(BA-|b) OA/\T oA 3. 證明下列邏輯蘊涵式： (1) AAB=>AkE 證明： (方法一)假設(shè)任一指派a,使得a(AAB)=l,要證a(ATB尸1。由于a(AAB)=

15、L于是a(A)=a(B尸1從而得到a(AoE)=1°故AAB=>AoE得證。 (方法二) AAB =>(AAB)V(-IAAnb) =>A^B (方法三)由于 A B AAB A^->B AAB—(A<^B) 0 0 0 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 1 所以AAB->(A<^B)是永真式，所以AAB=>A<^Bo (2) (A-E)fA=>A 證明： 假設(shè)任一指派a,使得a(A)=O,要證a((A-*B)—A)=Oo由于a(A)=O,于是無論B為真還是為假，都有a(A->B尸1。從而a((A

16、-*B)-*A)=Oo 故(A-B)-A=>A得證。 (3) (AVB)A(A->C)A(B->C)=>C 證明： (方法一)假設(shè)任一指派ot,使得a(C)=O要證a((AVB)A(A->C)A(B-C)尸0 (1) 若cc(A)=a(E尸0 于是a(AVB)=0,此時a((AVB)A(A->C)A(B->C))=0 (2) 若a(A)=l且a(E)=0 于是a(A-C)=0,此時a((AVB)A(A->C)A(B->C))=0 (3) 若a(A)=0且a(B)=l 于是a(B-C)=0,此時a((AVB)A(A->C)A(BC))=0 (4) 若a(A)=l且a(E)=

17、l 于是a(E~C)=a(A—C)=0,此時a((AVB)A(A->C)A(B-C)尸0 故(AVB)A(A-*C)A(B-*C)=>c得證。 (方法二)假設(shè)任一指派a,使得a((AVB)A(A-*C)A(B-*C))=1要證a(C)=l。由于a((AVB)A(A-*C)A(B-C))=1,所以a(AVB)=l,且a(A-C)=l且a(B-*C)=1。由a(AVE尸1,得到a(A)=l或者a(E尸1。 (1) 若a(A)=l,則Fha(A->C)=l得到a(C)=l。 (2) 若a(B)=l,則由a(B-C)=l得到cc(C尸1. 故(AVB)A(A-*C)A(B-*C)=>C得證

18、。 (方法三) (AVB)A(A-C)A(B-C) <^>(AVB)A(-1AVC)A(-1BVC) O(AVE)A((-1AVC)A(-iBVC))o(AVE)A((-iAA-1B)VC)<^>(AVB)A(n(AVB)VC)O((AVE)/\-](AVB))V((AVB)AC)<^>FV((AVB)AC) <^>((AVB)AC) =>c 4. 化簡下列各式： (1) (AVnB)A(AVB)A(nAV-iB) 解： (AVnB)A(AVB)A(nAVnB) o(AV(-|BAB))A(nAVnB) <=>(AVF)A(nAVnB) oA/\(-]AVnB)o(A

19、"A)V(AAnB)<^>FV(AAnB)oA/\iB (2) (-1Q-P)->(P-Q) 解： (-1QfPL(P~Q) 0(QVPL(iPVQ) o-i(QVP)V(nPVQ) 0(1QAnP)V(nPVQ) 0(-1QV-iPVQ)A(nPV-iPVQ) oTA(nPVQ)0(1PVQ)o(P~Q) (3) (P-Q)o(iQ—iP)解： (P-Q)o(lQ-*-|P)0(1PVQ)分(QViP)0(1PVQ)e(iPVQ)oT (4) BV-i((-]AVB)AA)解： BV-i((nAVB)AA)oEV(-i(nAVB)VnA)oEV((AA-]B)VnA)

20、oEV((AV-iA)A(nAV-iB))oEV(T/\(-iAV-iB))oBV(nAVqB)oT (5) (Q/\(P—iQLP)/Vi(Q-P)解： (QA(P-*nQ)-*P)A-i(Q-*P)0(QA(iPVnQ)-*P)AnhQVP)0(QA(iPVnQ)-*P)A(QAnP)0((QA-|P)V(QA-iQ)-*P)A(QAnP)0((QAiP)VF->P)A(QAnP)0((QA-ip)-*p)A(QA-iP)0(1(QAnP)VP)A(QA-iP)0(-1QVPVP)A(QA-1P)0(1QVP)A(QAnP)0(-1QAQA-iP)V(P)AQA-iP)oF\/F O

21、F 練習(xí)6.3 1. 把下列各式化為析取范式: (1) (P->Q)tR解： (P->Q)tR 0-1(-1PVQ)VR o(P/\-iQ)VR (2) (nP/\Q)fR 解： hPAQ)-*R0-1(-1PAQ)VRo(PV-iQ)VROP"QVR (3) n(PAQ)A(PVQ)解： 1(PAQ)A(PVQ)0-1(PAQ)A(PVQ)0(-1PV-IQ)A(PVQ)0(-]PAP)V(nPAQ)V(-]QAP)V(nQAQ)oFV(-iPAQ)V(nQAP)VF0(-1PAQ)V(PA-1Q) (4) (-1Q-P)-Q)解： hQfP)f(Pf1Q)0(QV

22、PL(iPVnQ)o-i(QVP)V(-iPV-iQ)o(-|QA-iP)V-iPV-iQ 2. 把下列各式化為合取范式： (1) (PtQ)tR解： (P->Q)tR o-i(-1PVQ)VRo(P/\-iQ)VRo(PVR)A(-|QVR) (2) nBV-i((-]AVB)AA)解： nBV-i((-iAVB)AA)onBV(n(nAVB)VqA)o-iBV((AAnB)V-iA)o(-lBV-1A)V(AAnB)o(~lBVqAVA)A(nBV-]AV-]B)0(-1BVT)A(nBVnAVqB)oT/\(-iAV-iB)0(-,AVqB) (3) PT(P/\(P?Q)

23、) 解： PT(PA(POQ)) oiPV(PA(P^Q)A(Q^P)) oiPV(PA(qPVQ)A(QVP)) o(1PVP)A(qPV-)PVQ)A(-jPVQVP) (4) (PV(Q<^R))AS 解： (PV(gR))/\S o(PV(QAR)V(nQA-|R))AS o(PVQVqQ)A(PVQV-|R)A(PVRV-|Q)A(PVRVnR)AS 3. 求卞列公式的主析取范式、主合取范式，并據(jù)主析取范式直接確定使該公式為真指派，據(jù)主合取范式直接確定使該公式為假指派。 (1) (PAQ)V(nPAQAR) 解： 求主析取范式 (PAQ)V(-]PAQA

24、R)

25、nQVR)A(qPVQVR)A(-]PVQVqR)A(PVQVR)A(-jPVQVR)A(PVQV-|R))A(iPVQVqR)A(PVQVR)A(qPVQVR)PVQo(PA(Q5Q))V((PV-]P)AQ) o(PAQ)V(PAiQ)V(P

26、AQ)V(qPAQ) <^>(PAQ)V(PA-]Q)V(nPAQ) 使公式為真的指派有： (1,1) 、(1,0)、(0,1) 求主合取范式 1(PVQ)^(PAQ)o(PVQ)V(PAQ) PVQ 使公式為假的指派有： (0,0) (3) P“Pt(QV(iQtR))) 解： 求主析取范式 PV(-]Pt(QV(1QtR))) <^>PV(PV(QV(QVR))) <^>PV(PV((QVR)) <^>PV(PVQVR) <^>PVQVR <^>(PA(QV-]Q)A(RV-|R))V((PVqP)AQA(RV-

27、)R))V((PVnP)A(QV-|Q)AR)

28、QV(1QtR))) <^>PV(PV(QV(QVR))) <^>PV(PV((QVR)) <^>PV(PVQVR) <^>PVQVR 使公式為假的指派有： (0,0,0) (4) (PV(Q<^R))AS 解： 求主合取范式 (PV(Q<^R))AS o(PV(QAR)V(-|QA-)R))AS o(PVQV-|Q)A(PVQV-|R)A(PVRV-jQ)A(PVRV-|R)AS <^>(PVQV-|R)A(PVRV-|Q)AS <^>(PVQV-|RV(SA-|S))A(PV-|QVRV(SA-|S))A((PA-|P)V(QA-|Q)V(RA-)R)VS)<^

29、>(PVQV-|RVS)A(PVQV-|RV-|S)A(PV-)QVRVS)A(PV-|QVRVqS)A(PVQVRVS)A(PVQV-|RVS)A(PV-|QVRVS)A(PV-|QVnRVS)A(qPVnQV-jRVS)A(-|PVnQVRVS)A(-!PVQV-|RVS)A(-|PVQVRVS) <^>(PVQV-|RVS)A(PVQV-|RV-|S)A(PV-)QVRVS)A(PV-|QVRVqS)A(PVQVRVS)A(PV-jQV-jRVS)A(-|PV-|QV-|RVS)A(-|PVqQVRVS)A(nPVQV-jRVS)A(-|PVQVRVS) 使公式為假的指派有： (O

30、gO)、(0,0,1,0)、(0,0,1,1)、(0丄0,0)、(0丄0,1)、(0丄1,0)、(l,0Q0)、(1,0,1,0)、(1丄0,0)、(1,1,1,0) 使公式為真的指派有： (0,0,0,1).(0丄1,1)、(1,0.0,1)、(1,0,1,1)、(1,1,0,1)^(14,1,1) 主析取范式為 (-|PA-|QA-|RAS)V(-|PAQARAS)V(PA-|QA-|RAS)V(PA-|QARAS)V(PAQA-|rAS)V(PAqARAS)V 4. A、E、C、D四個人中要派兩個人出差，按下述三個條件有幾種派法？如何派？ (1) 若去則C和D中要去一個人；

31、 (2) E和C不能都去； (3) C去則D要留下。 解： 設(shè)A:A去出差。E:E去出差。C:C去出差。D:D去出差。 將題目中的三個條件進(jìn)行形式化： A"(CoD)-1(BAC)CT-iD 于是將下面的命題公式轉(zhuǎn)化為析取范式： (AT-1(COD))An(BAC)A(C^nD) 0(-1AV(-1CAD)V(CA-ID))A(-1BV-10A(nCVnD) 0(-1AV(-|CAD)V(CA-|D))A((nBAnC)V(-|BAnD)V(nCAnC)V(nCA-|D))O(~]A/\~|B/\~]C)V(~iAA~|B/\~iD)V(~iAA~|C)\Z(~iA/\~iC

32、/\~iD)\/(-)CADAnBAnC)\Z(-1BA-1D)V(-1CADA-IC)\Z0CADAiCAiD)V(CA-iDA -IB/\-iC)V(CA-1DA-IBAnD)V(CA-1DAnC)V(C/\「DAiC/\-|D) 在析取范式中，有些項不符合題意，已用下劃線標(biāo)出，將這些項從始終刪除，得到下式：(-|AA-|C)V(-|CADA-|BA-|C)V(-]CADA-|C)V(-|CADA-|BA-|C)V(-|CADA-|C)V(CA-|DA-|BA-|D) O(1AA-|C)V(-|CADA-]B)V(-|CAD)V(-|CADA-]B)V(CA-|DA-|B) 根據(jù)此

33、式可以得到以下結(jié)論： 可以派E和D,或者A和D,或者A和C。 練習(xí)6.4 i.運用直接證法證明下列各式： (1)-,(PA-|Q),-)QVR,-|R^-|P 證明： 6QVR 引入前提 ?nR 引入前提 ?nQ 由①②析取三段論 ?h(PA-|Q) 引入前提 @-|PVQ 由④置換(據(jù)~1(AAE)o-|AV~iB) ⑥］P 由③⑤析取三段論 (2)J->(MVN).(HVG)->LHVG=>MVN 證明： ?J->(MVN) 引入前提 ②(HVG)->J 引入前提 ③(HVG)->(MVN) 由①②假言三段論 ?HVG 引入前提

34、 (§)MVN 由③④假言推理 (3)BAC.(HVG)=>HVG 證明： ?BAC 引入前提 ②B 由①化簡 ③c 由①化簡 ?BV-|C 由②附加 ?CV-)B 由③附加 ⑥CTB 由④置換 ⑦BTC 由⑤置換 ⑧(CTB)A(BTC) 由⑥⑦合取引入 ⑨EoC 由⑧置換 ⑩(BoC)^(HVG) 引入前提 (11)(HVG 由⑨⑩假言推理 (4)PTQ,行QVR)AqRq行PAS)=>-|S 證明： ?(-|QVR)A-|R 引入前提 ?qQVR 由①化簡 ③QTR 由②置換 ④PTQ 引入前提 ⑤PTR

35、 由③④假言三段論 ?1R 由①化簡 由⑤＜⑥拒取 @1(1PAS) ⑨PV-|S?qS 引入前提由⑧置換由⑦⑨析取三段論 2.運用歸謬法證明下列各式： (1)-](PAqQX-|QVRn 證明： ?p 引入結(jié)論的否定 ?n(PA-|Q) 引入前提 @-|PVQ 由②置換(據(jù)1(AAB)<=>nAVnB) ?Q 由①③析取三段論 @-)QVR 引入前提 ?1R 引入前提 由⑤⑥析取三段論 ?1QAQ(矛盾) 由⑦④合取引入 (2)PTQ,行QVR)AqRq行PAS)=>qS證明： ?s 引入結(jié)論的否定 ②1(1PAS) 引入

36、前提 @PV-|S 由②置換 ?p 由①③析取三段論 @(-|QVR)A-|R 引入前提 @-|QVR 由⑤化簡 ?qR 由⑤化簡 ⑧1Q 由⑥⑦析取三段論 ⑨PTQ 引入前提 ?qP 由⑧⑨拒取 (1D-|PAP(矛盾) 由④?合取引入 3.運用附加前提的方法證明下列各式: (1)AT(ETC)QTAgDTC 證明： ① D 附加前提引入 ② DTA 引入前提 ③ A 由①②假言推理 ④ AT(ETC) 引入前提 ⑤ ETC 由③④假言推理 ⑥ B 引入前提 ⑦ C 由⑤⑥假言推理 (2)A->

37、(B->C)XCAD)-^E,qF->(DAqE)=>At(BtF)證明： ① A附加前提引入 ② At(BtC) ③ BtC ④ (CAD)tE ⑤ Ct(DtE) ⑥ Et(DtE) ⑦ -)F^(DA-|E) ⑧ -|(DA-|E)->F ⑨ (-|DVE)->F ⑩ (DTE)tF (11)ETF 引入前提 由①②假言推理 引入前提 由④置換 由③⑤假言三段論引入前提 由⑦置換 由⑦置換 由⑦置換 由⑥⑩假言三段論 ① PA-|Q^R ② PT(iQTR) ③ P ④ iQTRQTS 1STjQ-jSTR 1s R ⑤⑥⑦⑧⑨ 4. 構(gòu)造下面推理的證明：只要A曾到過受害者房間并且11點以前沒離開,A就是謀殺嫌犯;A曾到過受害者房間；如果A在11點以前離開房間，看門人會看見他；看門人沒有看見他。所以，A是謀殺嫌犯。 證明：首先進(jìn)行形式化： P：A曾到過受害者房間 Q：A在11點以前離開 R：A是謀殺嫌犯 S：看門人會看見A PA-|Q^R,P,Q^S,-|S=>R 采用推理理論進(jìn)行證明 引入前提 由①置換 引入前提 由②③假言推理 引入前提 由⑤置換 由④⑥假言三段論 引入前提 由⑦⑧假言推理