命題邏輯習(xí)題

1、數(shù)理邏輯習(xí)題命題邏輯（一）1.指出下列語(yǔ)句中哪些是命題 a) 離散數(shù)學(xué)的研究對(duì)象是自然數(shù)。b) 請(qǐng)勿喧嘩。c) 夸夸其談可以創(chuàng)造財(cái)富。d) “飛碟”來(lái)自于銀河系之外。e) 今天很冷。f) 你明天還來(lái)嗎？解 a) 是命題。因?yàn)樗羌俚年愂鼍?。b) 不是命題。因?yàn)樗瞧硎咕?。c) 是命題。因?yàn)樗羌俚年愂鼍洹) 是命題。因?yàn)樗强纱_定真假的陳述句，雖然其真假性現(xiàn)時(shí)還無(wú)法確定，但隨著人類認(rèn)識(shí)的發(fā)展終將得到證實(shí)。e) 是命題。因?yàn)樗强纱_定真假的陳述句，其真假取決于說(shuō)話人的主觀判斷和外部環(huán)境的客觀溫度。f) 不是命題。因?yàn)樗且蓡?wèn)句。2.用符號(hào)形式寫下面命題，其中P表示命題“明天下雪”；Q表示命題“

2、我們明天上課”；R表示命題“我們明天上公園”。a) 如果明天下雪且我們停課，那么我們?nèi)ス珗@。b) 只有明天不下雪，我們才去公園。c) 除非明天不下雪且我們上公園，否則我們將上課。d)無(wú)論明天下雪與否，我們照常上課。解 a) PÙØQR；b) ØØPØR（或RØP）；c) Ø(ØPÙR)«ØQ （或ØPÙR«ØQ）；d) PÚØPQ（或Q）。3.用上題的命題P，Q，R解釋下面的形式命題。 a) ØPÚQ

3、16;Rb) PÙRc) ØPQÚRd) ØQ«R解 a) 只有明天下雪且不上課，我們才去公園；b) 明天下雪，明天我們?nèi)ス珗@；c) 如果明天不下雪，那么我們上課或去公園；d) 除非明天不停課(上課)，否則我們?nèi)ス珗@。4.將下述命題符號(hào)化 a) 不是小王就是老李來(lái)找過(guò)你。b) 盡管小張與小趙是同學(xué)，但他們很少在一起。c) 如果程序能正常結(jié)束，那么就不會(huì)有語(yǔ)法錯(cuò)誤。d) 既然你今天不去開會(huì)，就該在家好好休息一下。e) 只有博覽群書，知識(shí)才能豐富。f) 只要懂得法律，就能夠成為一名律師。g) 學(xué)好數(shù)、理、化，走扁天下都不怕。h) 并非由于學(xué)校是重點(diǎn)

4、，畢業(yè)生才是一流的，而是由于畢業(yè)生是一流的，學(xué)校才能成為重點(diǎn)。i) 他能考上交大，除了由于他有一個(gè)較好的環(huán)境之外，還在于他平時(shí)的刻苦精神。解 a) 令：P：小王來(lái)找過(guò)你Q：老李來(lái)找過(guò)你形式化公式：PÚQ（實(shí)際上是不可兼或：PQ）；b) 令：P：小張與小趙是同學(xué) Q：小張與趙在一起。形式化公式：PÙØQ；c) 令：P：程序正常結(jié)束 Q：程序有語(yǔ)法錯(cuò)誤形式化公式：PØQ；d) 令：P：你今天去開會(huì) Q：你在家休息一下。形式化公式：ØPÙQ；e) 令：P：(某人)博覽群書 Q：(某人)知識(shí)豐富形式化公式：ØPØQ（或者Q

5、P）；f) 令：P：(某人)懂得法津 Q：(某人)成為一名律師形式化公式：PQ；g) 令：P：(某人)學(xué)好數(shù)學(xué) Q：(某人)學(xué)好物理 R：(某人)學(xué)好化學(xué) S：(某人)走遍天下都不怕形式化公式：P ÙQ ÙRS；h) 令：P：學(xué)校是重點(diǎn) Q：畢業(yè)是一流的形式化公式：Ø(PQ) Ù(QP) ；i) 令：P：他考上了交大 Q：他有一個(gè)較好的環(huán)境 R：他平時(shí)刻苦形式化公式：Q ÙRP。5.試通過(guò)對(duì)命題公式中聯(lián)結(jié)詞的個(gè)數(shù)歸納，證明命題公式在任一指派下的真假值都是唯一的。證 (采用串值數(shù)學(xué)歸納法)為證命題公式在任一賦值下的真值是唯一的，我們對(duì)公式中所含聯(lián)

6、結(jié)詞的個(gè)數(shù)n進(jìn)行串值歸納： 1）若n0，則P是一原子公式，從而() P()顯然是唯一的。2）假設(shè)n0，1，2，k時(shí)，任何含有n個(gè)聯(lián)結(jié)詞的公式在下的真值() 是唯一的。3）于是，當(dāng)nk+1時(shí)，則根據(jù)合式公式的形成規(guī)則，可知 Ø1，或者1*2（這里* Ù或Ú或或«）。我們?cè)O(shè)1和2中的聯(lián)結(jié)詞個(gè)數(shù)分別為k1和k2，那么a) 當(dāng)Ø1時(shí)，則有k1+1k+1，從而k1k0于是由歸納假設(shè)可知，真值是唯一的，所以由Ø的真值表知真值() Ø (1()是唯一的；b) 當(dāng)1*2時(shí)，則有k1+k2+1k+1，從而k1+k2k，即有k1£k，

7、k2£k。于是由歸納假設(shè)知，真值1()，2 ()是唯一的，所以由*的真值表（Ù，Ú，«的真值表）知真值()1()*2()都是唯一的。這就用串值歸納法證明了命題公式在任一賦值下的真值（真假值）都是唯一的。6.令P，Q，R，S分別取值為T，F(xiàn)，T，F(xiàn)。求出下列命題公式在相應(yīng)指派下的真假值。 a) ØPÚ (QPÙR)b) QÚP(QÙS«R)c) (PQ) Ù(RQÙS)d) PÚ(QRÙØS)«QÚØP解 這里賦值（T

8、，F(xiàn)，T，F(xiàn)） a) (Ø P Ú(QPÙR)()Ø P° Ú(Q°P°ÙR°)Ø T Ú(FTÙT)F Ú (FT)F Ú TTb) (QÚP(QÙS«R)() Q°ÚP°(Q°ÙS °«R°) FÚT(FÙF«T) T(F«T) TFFc) (PQ) Ù (RQÙS)() (

9、P°Q°) Ù (R°Q°ÙS°) (TF) Ù (TFÙF) FÙ (TF) FÙF Fd) (PÚ(QRÙØS)«QÚØ P)() (P°Ú(Q°R°ÙØS°)«Q°ÚØP°) TÚ(FTÙØF)«FÚØT TÚ(FTÙT)&

10、#171;FÚF TÚ(FT)«F TÚT«FT«FF7.構(gòu)造下列命題公式的真值表。 a) PÙ(QÚR)b) (PQ) Ù(PÚR)c) (P(QÙØQ)ØPd) (PQ)(PR)(P(QR)解 a)PQRQÚRPÙ(QÚR)TTTTTTTFTTTFTTTTFFFFFTTTFFTFTFFFTTFFFFFFb)PQRPQPÚR(PQ) Ù(PÚR)TTTTTTTTFTTTTFTFTFTFFFTFFTTTTT

11、FTF TFFFFTTTTFFFTFFc) PQØPØQQÙØQP(QÙØQ)(P(QÙØQ)ØPTTFFFFTTFFTFFTFTTFFTTFFTTFTTd) PQRPQPRQR(PQ)(PR)P(QR)(PQ)(PR)(P(QR)TTTTTTTTTTTFTFFFFTTFTFTTTTTTFFFFTTTTFTTTTTTTTFTFTTFTTTFFTTTTTTTFFFTTTTTT8.利用真值表法判斷下列邏輯等價(jià)式是否成立。 a) (PØQ)(QØP)b) (PQ)(QP)c) P(QR)(P

12、Q)(PR)d) Ø(PQ)PÙØQe) Ø(PÙQ)ØPÚØQf) P«Q(PÙQ) Ú(ØPÚØQ)g) P(QP)ØP(QØP)h) (PR)Ù(QR)PÚQRi)(P«Q)«RP«(Q«R)解a) 成立。PQØPØQPØQQØPTTFFFFTFFTTTFTTFTTFFTTTT此真值表最后兩列全完相同。故a) 的邏輯等價(jià)式成立。b)

13、 不成立。PQPQQPTTTTTFFTFTTFFFTF此真值表最后兩列不完全相同。故b) 的邏輯等價(jià)式不成立。c) 成立。PQRPQPRQRP(QR)(PQ)(PR)TTTTTTTTTTFTFFFFTFTFTTTTTFFFFTTTFTTTTTTTFTFTTFTTFFTTTTTTFFFTTTTT此真值表最后兩列完全相同。故c) 的邏輯等價(jià)式成立。d) 成立。PQØQPQØ(PQ)PÙØQTTFTFFTFTFTTFTFTFFFFTTFF此真值表最后兩列完全相同。故d) 的邏輯等價(jià)式成立。e) 成立。PQØPØQPÙQØ

14、 (PÙQ)ØPÚØQTTFFTFFTFFTFTTFTTFFTTFFTTFTT此真值表最后兩列完全相同。故e) 的邏輯等價(jià)式成立。f) 成立。PQØPØQP ÙQØP ÙØQP«Q(PÙQ)Ú(ØPÙØQ)TTFFTFTTTFFTFFFFFTTFFFFFFFTTFTTT此真值表最后兩列完全相同。故f) 的邏輯等價(jià)式成立。g) 成立。PQØ PQPQØ PP(QP)Ø P(QØ P)TTFTFTTT

15、FFTTTTFTTFTTTFFTTTTT此值表最后兩列完工全相同。故f) 邏輯等價(jià)式成立。h) 成立。PQRPRQRPÚQ(PR)Ù(QR)PÚQRTTTTTTTTTTFFFTFFTFTTTTTTTFFFTTFFFTTTTTTTFTFTFTFFFFTTTFTTFFFTTFTT此真值表最后兩列完全相同。故h) 的邏輯等價(jià)式成立。i) 成立。PQRP«QQ«R(P«Q)«RP«(Q«R)TTTTTTTTTFTFFFTFTFFFFTFFFTTTFTTFTFFFTFFFTTFFTTFTTFFFTTFF此真值表最后

16、兩列完全相同。故i) 的邏輯等價(jià)式成立。9.東東的爺爺帶東東乘車去玩，當(dāng)路過(guò)一座高樓時(shí)，爺爺說(shuō)：“你只有現(xiàn)在好好學(xué)習(xí)，將來(lái)才能住上這樣的高樓?！睎|東聽了爺爺?shù)脑捯院螅卮鹫f(shuō)，“爺爺決有住上這樣的高樓，所以爺爺沒(méi)有好好學(xué)習(xí)?！闭?qǐng)問(wèn)：東東是否誤解了爺爺原話的意思，為什么解 東東誤解了爺爺原話的意思。因?yàn)槿袅睿篜：(你)現(xiàn)在好好學(xué)習(xí) Q：(你)將來(lái)住上這樣的高樓則爺爺?shù)脑捫问交癁椋篞P而東東的回答形式化是：ØQØP這兩個(gè)公式不是邏輯等價(jià)的。這可用真值表法證明如下：PQØPØQQPØQØPTTFFTTTFFTTFFTTFFTFFTTTT此真

17、值表最后兩列不完全相同，說(shuō)明QP與ØQØP不是邏輯等價(jià)的（事實(shí)上QPØPØQ），所以，東東的回答與爺爺?shù)脑捠遣坏葍r(jià)的，不是一個(gè)意思。因而，東東誤解了爺爺原話的意思。10.某單位派人外出學(xué)習(xí)。但由于工作關(guān)系，A，B兩個(gè)不能同去。如果B去則C必須留下工作。如果派D去則B和C至少應(yīng)去一人。試問(wèn) a) 四人中最多能派幾人？b) 若己決定派B去，是否還可以增派其它人？請(qǐng)通過(guò)對(duì)成真指派的分析給出上面問(wèn)題的最佳人選。解 令：P：A去 Q：B去 R：C去 S：D去則問(wèn)題形式化為一公式（條件公式）：=Ø(PÙQ) Ù(QØR) &

18、#217;(S(QÚR)a) 因四人全去,得到賦值1(T，T，T，T)，使得真值(1)F，從而四人全去不行, 故至多只能派三人同去。又因A和B不能同時(shí)去，而A去，C去，D去，得到賦值2(T，F(xiàn)，T，T)，使得真值(2)T，故至少可以派三個(gè)人同去。所以，四人中最多能派三人同去。b) 若己決定派B去，則根據(jù)Ø(PÙQ)，可知不能派A去；又根據(jù)(QØR)，可知不能派C去，因而至多只能增派D去。從而得到賦值3(F，T，F(xiàn)，T)，使得真值(3)T。故此，若己決定派B去，則還可以增派D同去。11.利用真值表判斷下列公式的永真性（有效性）。a) ØP(PQ)

19、b) (PQ)(QR)(PR)c) (PÚQ)ÙR)Ú(PÙQØR)d) (P(QR)«(Q(PR)解 a)ØP（PQ）PQØPPQØP(PQ)TTFTTTFFFTFTTTTFFTTT 因?yàn)榇酥当淼淖詈笠涣腥荰, 故公式是有效的。b) (PQ)(QR)(PR)PQRPQQPPR(QR)(PR)(PQ)(QR)(PR)TTTTTTTTTTFTFFTTTFTFTTTTTFFFTFFTFTTTTTTTFTFTFTTTFFTTTTTTFFFTTTTT因?yàn)榇苏嬷当淼淖詈笠涣腥荰, 故公式是有效的。c) (P&#

20、218;Q)ÙR)Ú(PÙQ)ØR)PQRPÚQQÙPØR(PÚQ)ÙRPÙQØR(PÚQ)ÙR)Ú(PÙQØR)TTTTTFTFTTTFTTTFTTTFTTFFTTTTFFTFTFTTFTTTFFTTTFTFTFTFTTFFTFFFFTTFFFFFTFTT因?yàn)榇苏嬷当淼淖詈笠涣腥荰, 故公式是有效的。d) (P(QR)«(Q(PR)PQRQRPRP(QR)Q(PR)TTTTTTTTTFFFFFTFTTTTTTFFTFTTF

21、TTTTTTFTFFTTTFFTTTTTFFFTTTT因?yàn)榇苏嬷当淼淖詈髢闪型耆嗤? 故公式是有效的。12.利用真值表證明下列邏輯蘊(yùn)涵式。 a)Ø(PQ)Pb)ØQÙ(PQ) ØPc) (PÚQ)Ù(PR) Ù(QS) RÚSd)ØP(QÙØQ) P證 a) 邏輯蘊(yùn)涵式Ø(PQ)P成立。PQPQØ (PQ)PTTTFTTFFTTFTTFFFFTFF因?yàn)榇苏嬷当矸彩?#216;(PQ)列為T的行，P列相應(yīng)的行也為T。b) 邏輯蘊(yùn)涵式ØQÙ(PQ)

22、 ØP成立PQØQPQØQÙ(PQ)Ø PTTFTFFTFTFFFFTFTFTFFTTTT因?yàn)榇苏嬷当矸彩?#216; QÙ(PQ)列為T的行，ØP列相應(yīng)的行也為T。c) 邏輯蘊(yùn)涵式(PÚQ)Ù(PR) Ù(QS) RÚS成立。PQRSPÚQPÚRQS(PÚQ)Ù(PR)Ù(QS)RÚSTTTTTTTTTTTTFTTFFTTTFTTFTFTTTFFTFFFFTFTTTTTTTTFTFTTTTTTFFTTFTFTTFFFTFTF

23、FFTTTTTTTTFTTFTTFFTFTFTTTTTTFTFFTTFFFFFTTFTTFTFFTFFTTFTFFFTFTTFTFFFFFTTFF因?yàn)榇苏嬷当矸彩?PÚQ)Ù(PR) Ù(QS)列為T的行，RÚS列相應(yīng)的行也為T。d) 邏輯蘊(yùn)涵式ØP(QÙØQ) P成立。PQØPØQQÙØQØP(QÙQ)PTTFFFTTTFFTFTTFTTFFFFFFTTFFF 因?yàn)檎嬷当矸彩?#216;P(QÙØQ)列為T的行，P列相應(yīng)的行也為T。13.求下列

24、命題公式的代入實(shí)例。 a) P(PQ)Q)其中：P代入為PQ，Q代入為(PQ)Qb) (PQ)(QR)(PR) 其中，P代入為QR，Q代入為PR。解 a) (P(PQ)Q)(PQ)/P,(PQ)Q)/Q=(PQ)(PQ)(PQ)Q)(PQ)Q) ；b) (PQ)(QR)(PR)(QR)/P,(PR)/Q=(QR)(PR)(PR)R)(QR)R) 。14.設(shè)a1，a2，b為命題公式。如果a1a2，證明： a) Øa2Øa1b) a1Ùba2Ùbc) a1Úba2Úbd) a1ba2b 證 a)對(duì)于任一賦值，如果(Øa2)()=

25、T，則a2()=F。根據(jù)a1a2，可知a1()=F，從而(Øa1)()=T。所以Øa2Øa1成立。b) 對(duì)任一賦值，如果(a1Ùb)()=T，那么a1()=T且b()=T。根據(jù)a1a2，可得a2()=T，從而a2()=T且b()=T，也即是(a2Ùb)()=T，所以a1Ùba2Ùb成立。c) 對(duì)任一賦值，如果(a1Úb)()=T，那么a1()=T或者b()=T。于是分情況證明如下：1°若a1()=T，那么根據(jù)a1a2，可知a2()=T，因此(a2Úb)()=T；2°若b()=T，則顯然

26、(a2Úb)()=T；因此，無(wú)論如何，總有(a2Úb)()=T。所以a1Úba2Úb成立。d) 對(duì)任一賦值，如果(a2b)()=T，那么若a2()=T，則b()=T。于是： 1°若a1()=F，那么顯然有(a1b)()=T；2°若a1()=T，那么根據(jù)a1a2，可知a2()=T，從而有b()=T，因此得到(a1b)()=T；于是，無(wú)論如何，總有(a1b)()=T。所以a1ba2b成立。15.利用變換法證明下列邏輯等價(jià)式。 a) P(QP)ØP(PQ) b) (PR)Ù(QR)PÚQR c)Ø(P

27、«Q)(PÚQ)Ù(PÚQ) d)Ø(PQ)PÙØQ證明 a) P(QP)ØPÚ(ØQÚP) （替換定理，聯(lián)結(jié)詞化歸） (PÚØP)ÚØQ （結(jié)合律） PÚØP (PÚØP) ÚQ PÚ(ØPÚQ) （結(jié)合律） ØØPÚ(ØPÚQ) （替換定理，雙重否定律） ØP(PQ) （替換定理，聯(lián)結(jié)詞化歸）b) (PR

28、)Ù(QR) (ØPÚR) Ù(ØQÚR) （替換定理，聯(lián)結(jié)詞化歸） (ØPÙØQ)ÚR （分配律） Ø(PÚQ) ÚR （替換定理，de Morg an律） PÚQR （聯(lián)結(jié)詞化歸） c) Ø(P«Q) Ø(PQ)Ù(QR) （替換定理，聯(lián)結(jié)詞化歸） Ø(ØPÚQ)Ù(ØQÚP) （替換定理，聯(lián)結(jié)詞化歸）Ø(ØPÚQ)

29、8;Ø(ØQÚP) （de Morgan律）(ØØPÙØQ)Ú(ØØQÙØP) （替換定理，de Morgam律）(PÙØQ)Ú(QÙØP) （替換定理，雙重否定律）(PÚØP)Ù(PÚQ)Ù(ØPÚØQ)Ù(QÚØQ)（分配律、替換定理，結(jié)合律，交換律）(PÚQ) Ù (ØPÚ

30、ØQ) （化簡(jiǎn)律）d) Ø(PQ) Ø (ØPÚQ) （替換定理，聯(lián)結(jié)詞化歸） ØØPÙØQ （de Mergan律） PÙØQ （替換定理，雙重否定律）。16.利用變換法證明下列邏輯蘊(yùn)涵式。 a) P(QR) (PQ)(PR)b) (PQ)Q PÚQc) (PQ)(QP)QPd) PQ PÚRQÚR證 a) 實(shí)際上，我們可證邏輯等價(jià)式：P(QR)(PQ) (PR)就是 P(QR)ØP Ú (ØQÚR) （替換定理，

31、聯(lián)結(jié)詞化歸）(PÚØPÚR)Ù(ØPÚQÚR) （化簡(jiǎn)律）(PÙØQ)Ú (ØPÚR) （分配律）Ø (ØPÚQ)Ú (ØPÚR) （替換定理、雙重否定律，de Morgan律）Ø (PQ) Ú (PR) （替換定理，聯(lián)結(jié)詞化歸）(PQ)(PR) （聯(lián)結(jié)詞化歸）b) 實(shí)際上我們可證邏輯等價(jià)式：(PQ)QPQ變換證明如下：(PQ)QØ (ØPÚQ)ÚQ （替換

32、定理，聯(lián)結(jié)詞化歸）(ØØPÙØQ)ÚQ （替換定理、de Morgan律）(PÙØQ)ÚQ （替換定理、雙重否定律）( PÚQ) Ù (QÚØQ) （分配律）PÚQ （化簡(jiǎn)律）c) 實(shí)際上，我們可證邏輯等價(jià)式：(PQ)(QP)QP變換證明如下 (PQ) (QP) Ø (ØPÚQ)Ú (ØQÚP) （替換定理、聯(lián)結(jié)詞化歸） (ØØPÚØQ)Ú (ØQ

33、ÚP) （替換定理，de Morgasn律） (PÙØQ) Ú (ØQÚP) （替換定理、雙重否定律） ØQÚP （吸收律） QP （聯(lián)結(jié)詞化歸）d) PQØPÚQ （聯(lián)結(jié)詞化歸）ØPÚQÚR （析取構(gòu)成式） (ØPÚQÚR) Ù (RÚØRÚQ) （化簡(jiǎn)律） (ØPÙØR)Ú (QÚR) （分配律）Ø (PÚR)Ú

34、(QÚR) （替換定律， de Morgan律） PÚRQÚR （聯(lián)結(jié)詞化歸）。17.求下列命題公式的對(duì)偶式。 a) (PQ)ØPÚRb) Ø (P«Q)Ù(PÚQ)c) (PQÚR)Ù(QP)解 a) 由于(PQ)ØPÚRØ(ØPÚQ) ÚØPÚR所以其對(duì)偶式為Ø(ØPÙQ)ÙØPÙR 。b) 由于 Ø (P«Q) Ù

35、; (PÚQ)Ø (PQ) Ù (QP) Ù ( PÚQ) Ø (ØPÚQ) Ù (ØQÚP ) Ú (PÚQ) Ø (PÚØQ) Ù (ØPÚQ) Ù (PÚQ)因此其對(duì)偶式為 Ø (ØPÚQ)Ù(ØPÚQ)Ú(PÙQ) 。c) 因?yàn)?(ØPQÚR) Ù (QP) (Ø

36、;ØPÚQÚR) Ù (ØQÚP) (PÚQÚR) Ù (ØQÚP)從而其對(duì)偶式為 (PÙQÙR) Ú (ØQÙP) 。18.將下列命題公式化成只含有全功能聯(lián)結(jié)詞集合Ø,中聯(lián)結(jié)詞的命題公式。 a) PÚ (QÙØR)b) (PÚQ)ÙRPÚRc) PÚ (ØQÙRP)d) Ø (P« (ØQRÚP)

37、解 a) PÚ (QÙØR) (QÙØR)ÚP (ØØQÙØR)ÚP Ø (ØQÚR)ÚP (QR)Pb) (PÚQ)ÙRPÚR(ØPQ)ÙR)(ØPR)Ø (ØPQ)ØR)(ØPR)c) PÚ (ØQÙRP)ØP(Ø (ØQØR)P) ØP(Ø (RQ)P)

38、d) Ø (P«(ØQRÚP)Ø (P(ØQRÚP) Ú (ØQRÚP)P)Ø (P(ØQ(ØPR)Ù(ØQ(ØPR)P) (P(ØQ(ØPR)Ø (ØQ(ØPR) P) 。19.證明是極小全功能的。證 根據(jù)定理2，聯(lián)結(jié)詞集Ø，Ú是全功能的，故為證是全功能的，只需證明Ø，Ú中的每個(gè)聯(lián)結(jié)詞都可分別由來(lái)表示即可。由于ØPPPPÚQ(

39、PQ)(PQ)因此是全功能的。由于中只有一個(gè)聯(lián)結(jié)詞，故所以是極小全功能的。20.證明Ù，Ú不是全功能的。證 Ù，Ú不是全功能的。否則，聯(lián)結(jié)詞Ø必定可由聯(lián)結(jié)詞集Ù，Ú來(lái)表示，即，對(duì)于任一原子公式P，存在公式a，a中只含聯(lián)結(jié)詞Ù和Ú，使得ØPa設(shè)是一對(duì)a中出現(xiàn)的所有命題變項(xiàng)及P都指派真值T的賦值。則我們可用串值歸納法證明a()T；但是(ØP)()ØTF，從而ØP不可能與公式a邏輯等價(jià)，矛盾。事實(shí)上，我們施串值歸納于a中聯(lián)結(jié)詞Ù和Ú的個(gè)數(shù)m，來(lái)證a (

40、)T：當(dāng)m1時(shí)，只能有aPÙP或PÙQ或QÙQ,或PÚP或PÚQ或QÚQ。由于給P和Q都賦值T，故這時(shí)顯然有a ()T。當(dāng)m1，2，k時(shí)，歸納假設(shè)總有a ()T。則當(dāng)mk+1時(shí)，只能有aa1Ùa2或a1Úa2，其中a1和a2中所含聯(lián)結(jié)詞Ù和Ú的個(gè)數(shù)分別為和，于是就有 即從而有，£，因此，根據(jù)歸納假設(shè)有a1()=T，a2()=T,所以a ()= a1 () Ù a2 ()=TÙT=T或者a ()= a1 () Ú a2 ()=TÚ T=T 總之a(chǎn)

41、()=T。 21.將下列命題公式化為析取范式。 a) ØPÚØQ(P«ØQ) ÚRb) (PÚ (ØPQ) Ù (QR)c) (PQÙR) Ù (ØPØQÙØR)d) Q Ù (ØPQ ÚØ (QR)解 a) (ØPÚØQ)(P«ØQ)ÚR Ø (ØP ÚØQ) Ú (PØQ) Ù

42、; (ØQP) ÚR) (ØØP ÙØØQ) Ú (ØP ÚØQ) Ù (ØØQ ÚP) ÚR) (PÙQ)Ú (ØPÙP)Ú (ØQÙP)Ú (ØPÙQ)Ú (ØQÙQ)ÚR (PÙQ)Ú (PÙØQ)Ú (ØPÙQ)Ú

43、;Rb) (PÚ (ØPQ) Ù (QR)(PÚ (ØØPÚQ) Ù (ØQÚR)(PÚPÚQ) Ù (ØQÚR)(PÚQ)Ù (ØQÚR)(PÙØQ)Ú (QÙØQ)Ú (PÙR)Ú (QÙR)(PÙØQ)Ú (PÙR) Ú (QÙR)c) (P(QR)(P

44、(QR)(ØPÚ (QÙR) Ù (ØØPÚ (ØQÙØR)(ØPÚ (QÙR) Ù (PÚ (ØQÙØR)(ØPÙP) Ú (QÙRÙP) Ú (ØPÙØQÙØR) Ú (QÙRÙØQÙØR)(PÙQÙR) Ú (&#

45、216;PÙØQÙØR)d) QÙ (ØP(QÚØ (QR)QÙ (ØØPÚ (QÚØ (ØQÚR)QÙ (QÚPÚØ (ØQÚR)Q22.將上題的各命公式化為主析取范式。解 a) (ØPÚØQ)(P«ØQ)ÚR) (PÙQ)Ú (PÙØQ)Ú (ØP

46、7;Q)ÚR(PÙQ) Ù (RÚØR)Ú (PÙØQ) Ù (RÙØR) Ú (ØPÙQ) Ù (RÚØR) Ú (QÚØQ) ÙR) (PÙQÙR) Ú (PÙQÙØR) Ú (PÙØQÙR) Ú (PÙØQÙØR) Ú (&

47、#216;PÙQÙR) Ú (ØPÙQÙØR) Ú (QÙR) Ú (ØQÙR)(PÙQÙR)Ú (PÙQÙØR)Ú (PÙØQÙR)Ú (PÙØQÙØR)Ú (ØPÙQÙR) Ú (ØPÙQÙØR) Ú (PÚ

48、6;P)Ù(QÙR) Ú (PÚØP) Ù (ØQÙR)(PÙQÙR)Ú (PÙQÙØR)Ú (PÙØQÙR)Ú (PÙØQÙØR)Ú (ØPÙQÙR) Ú (ØPÙQÙØR) Ú (PÙQÙR)Ú (ØPÙQÙ

49、;R) Ú(PÙØQÙR)Ú (ØPÙØQÙR) (PÙQÙR)Ú(PÙQÙØR)Ú(PÙØQÙR)Ú(PÙØQÙØR)Ú(ØPÙQÙR)Ú(ØPÙQÙØR)Ú (ØPÙØQÙR)m7Úm6Úm5&#

50、218;m4Úm3Úm2Úm1 b) (PÚ (ØPQ) Ù (QR) (PÙØQ)Ú (PÙR) Ú (QÙR) (PÙØQ)Ú (RÙØR) Ú (PÙR)Ú(OÙØQ) Ù (PÙØP)Ú (QÙR) (PÙØQÙR) Ú (PÙØQÙØR)&

51、#218; (PÙQÙR)Ú(PÙØQÙR)Ú (PÙQÙR)Ú (ØPÙQÙR) (PÙQÙR)Ú (PÙØQÙR) Ú (PÙØQÙØR) Ú (ØPÙQÙR) m7Úm5Úm4Úm3 c) (PQÙR) Ù (ØPØQÙØR

52、) (PÙQÙR)Ú (ØPÙØQÙØR) m7Úm0 d) QÙ(ØP(QÚØ(QR) Q (PÙQ)Ú (ØPÙQ) (PÙQ) Ù (RÙØR) Ú (ØPÙQ) Ù (RÙØR) (PÙQÙR) Ú (PÙQÙØR)Ú (ØPÙQ&

53、#217;R)Ú (ØPÙQÙØR) m7Úm6Úm3Úm223.通過(guò)化主析取范式的方法，判斷下面的邏輯等價(jià)式是否成立。 a) (PÙQ) Ú (ØPÙQÙR)(PÚ (QÙR) Ù (QÚ (ØPÙR) b) ØPÚ (PÙQ) ÚRØ (PÙØQ) Ù (QÚR)解 a) 因?yàn)?(PÙQ) Ú

54、(ØPÙQÙR) (PÙQ) Ù (RÚØR) Ú (ØPÙQÙR) (PÙQÙR) Ú (PÙQÙØR) Ú (ØPÙQÙR) m7Úm6Úm3又因?yàn)?PÚ (QÙR) Ù (QÚ (ØPÙR) (PÙQ)Ú (QÙRÙQ)Ú (PÙØP

55、ÙR) Ú (QÙRÙØPÙR) (PÙQ) Ú (QÙR) Ú (ØPÙQÙR) (PÙQ) Ù (RÚØR)Ú (PÚØP) Ù (QÙR) Ú (ØPÙQÙR) (PÙQÙR) Ú (PÙQÙØR) Ú (PÙQÙR) Ú (

56、6;PÙQÙR) Ú (ØPÙQÙR) (PÙQÙR)Ú (PÙQÙØR)Ú (ØPÙQÙR) m7Úm6Úm3 所以 (PÙQ)Ú (ØPÙQÙR)(PÚ (QÙR) Ù (QÚ (ØPÙR) b) 因?yàn)?ØPÚ (PÙQ)ÚR (ØPÙ (Q&#

57、218;ØQ) Ú (PÙQ) Ù (RÚØR) Ú (QÚØQ) ÙR) (ØPÙQ) Ú (ØPÙØQ) Ú (PÙQÙR) Ú (PÙQÙØR) Ú (QÙR) Ú (ØQÙR) (PÙQÙR)Ú(PÙQÙØR) Ú (ØPÙ

58、;Q) Ù (RÚØR) Ú (ØPÙØQ) Ù (RÚØR)Ú (PÚØP) Ù (QÙR) Ú (PÚØP) Ù (ØQÙR) (PÙQÙR)Ú(PÙQÙØR)Ú(ØPÙQÙR)Ú (ØPÙQÙØR) Ú (ØP&#

59、217;ØQÙR) Ú (ØPÙØQÙØR)Ú (PÙQÙR) Ú (ØPÙQÙR) Ú (PÙØQÙR) Ú (ØPÙØQÙR) (PÙQÙR) Ú (PÙQÙØR) Ú (PÙØQÙR) Ú (ØPÙQÙR) 

60、18; (ØPÙQÙØR) Ú (ØPÙØQÙR) Ú (ØPÙØQÙØR) m7Úm6Úm5Úm3Úm2Úm1Úm0又因?yàn)?Ø (PÙØQ) Ù (QÚR) (ØPÚØØQ) Ù (QÚR) (ØPÚQ) Ù (QÚR) QÚ

61、(ØPÙR) (PÚØP) ÙQ) Ú (ØPÙ (QÚØQ)ÙR) (PÙQ) Ú (ØPÙQ) Ú (ØPÙQÙR) Ú (ØPÙØQÙR) (PÙQ) Ù (RÚØR) Ú (ØPÙQ) Ù (RÚØR) Ú (ØPÙQ&#

62、217;R) Ú (ØPÙØQÙR) (PÙQÙR)Ú(PÙQÙØR)Ú(ØPÙQÙR)Ú(ØPÙQÙØR)Ú(ØPÙQÙR)Ú (ØPÙØQÙR) (PÙQÙR) Ú (PÙQÙØR) Ú (ØPÙQÙR)

63、Ú (ØPÙQÙØR) Ú (ØPÙØQÙR) m7Úm6Úm3Úm2Úm1 所以ØPÚ (PÙQ) ÚR與Ø (PÙØQ) Ù (QÚR)不邏輯等價(jià)。24.設(shè)計(jì)一個(gè)控制兩間會(huì)議室的照明電路，要求分別裝在這兩間會(huì)議室的兩只開關(guān)都能控制整個(gè)會(huì)議室的照明。解 會(huì)議室兩個(gè)門旁開關(guān)表示k1、k2，“0”表示開關(guān)斷開，“1”表示開關(guān)接通。S表示會(huì)議室的照明狀態(tài)，“1”表示全室燈

64、亮，“0”表示全室燈暗。假設(shè)開始時(shí)，室內(nèi)無(wú)人，燈暗。兩只開關(guān)都處于“0”狀態(tài)。有人進(jìn)入室內(nèi)時(shí)，隨手改變門旁的開關(guān)狀態(tài)，則會(huì)議室燈亮，S為“1”。此時(shí)兩只開關(guān)中有一只（奇數(shù)）處于“0”狀態(tài)。當(dāng)有人離開會(huì)議室時(shí)，隨手改變門旁的開關(guān)狀態(tài)，會(huì)議室燈暗，S為“0”。此時(shí)兩只開關(guān)（偶數(shù)）都處于“0”狀態(tài)。故此,我們有: 當(dāng)有偶數(shù)只開關(guān)處于“0”狀態(tài)時(shí)，S為“0”； 當(dāng)有奇數(shù)只開關(guān)處于“0”狀態(tài)時(shí)，S為“1”；所以，我們有:S(Øk1Ùk2)Ú (k1ÙØk2)(k1Úk2) Ù (Øk1ÚØk2)其電路圖如

65、圖所示：K1K2非門非門或門與門S或門第24題圖25.某公安員在追捕一個(gè)逃犯的途中面對(duì)前面具有兩條路分叉的路口。己知該路口住著兩個(gè)居民，其中一個(gè)說(shuō)謊成性，另一個(gè)天性誠(chéng)實(shí)。請(qǐng)問(wèn)：該公安員如何發(fā)問(wèn)才能確定逃犯的去向。解 公安人員手指一路問(wèn)身旁一名居民說(shuō)：“逃犯是從這條路逃走的，他（指另一居民）將回答是，你說(shuō)對(duì)嗎？”當(dāng)被問(wèn)居民回答：“否”時(shí)，公安人員應(yīng)從所指那條路去追逃犯；當(dāng)被問(wèn)居民回答“對(duì)”時(shí)，公安人員應(yīng)從另一條路去追逃犯。分析：如果被問(wèn)居民誠(chéng)實(shí)，他回答“對(duì)”。則另一居民是說(shuō)謊者，他回答“是”，那么，逃犯沒(méi)有從所指路逃走；如果被問(wèn)居民誠(chéng)實(shí)，他回答“否”。則另一居民是說(shuō)謊者，他回答“否”，那么，逃犯

66、是從所指路逃走的；如被問(wèn)居民說(shuō)謊，可以此類推分析。形式化：設(shè)P：被問(wèn)居民是誠(chéng)實(shí)的Q：被問(wèn)居民回答“是”R：另一居民回答“是”S：逃犯是從所指路逃走的則 S(PÙØQ) Ú (ØPÙØQ) (PÚØP)ÙØQ ØQRP«Q真值表如下：PQRSØQP«QTTTFFTTFFTTFFTFFFFFFTTTT即：“逃犯是從所指路逃走的”當(dāng)且僅當(dāng)“被問(wèn)居民誠(chéng)實(shí)且其回答是否”（即另一人不誠(chéng)實(shí)因而將回答“否”）或者“被問(wèn)戰(zhàn)士說(shuō)謊且其回答是否”（即另一人誠(chéng)實(shí)因而將回答是“是”

67、）當(dāng)且僅當(dāng)“被問(wèn)戰(zhàn)士回答是否”。并且“另一居民回答是是”當(dāng)且僅當(dāng)“被問(wèn)居民誠(chéng)實(shí)且其回答是是”或者“被問(wèn)居民說(shuō)謊且其回答是否”。26.證明析取消去規(guī)則（Ú）和否定規(guī)則（Ø）都是可靠的。證(a)析取消去規(guī)則（Ú）為：GaÚb，G,ag，G,bg Þ Gg 其可靠性為要性：GaÚb，G,ag，G,bg Þ Gg 證法一：令：d為G中所有公式之合取式。根據(jù)定理2，則要證：daÚb，dÙag，dÙbg Þ dg 根據(jù)定理1，即要證：daÚb，dÙag，dÙbg &#

68、222; dg 即要證：(daÚb)Ù(dÙag)Ù(dÙbg) Þ dg （*）但是我們能夠證明：(daÚb)Ù(dÙag)Ù(dÙbg)dg （* *）事實(shí)上：(daÚb)Ù(dÙag)Ù(dÙbg)(ØdÚaÚb)Ù(ØdÚØaÚg)Ù(ØdÚØbÚg)ØdÚ (aÚb)&

69、#217;(Ø(aÙb)Úg)ØdÚ (aÚb)Ùg)(ØdÚ aÚb)Ù(ØdÚg)ØdÚgdg因此，根據(jù)（* *）可知（*）成立。所以析取消去法規(guī)則（Ú）是可靠的。證法二：令：d為G中所有公式之合取式。根據(jù)定理2，則要證：daÚb，dÙag，dÙbg Þ dg對(duì)于任一賦值，若d ()=T，則由daÚb，可得(aÚb)()=T，于是有a ()=T或者b ()=T。(i) 若a ()=T，則(dÙa)()=T，從而由dÙag，可得g ()=T；(ii) 若b ()=T，則(dÙb)()=T，從而由dÙbg，可得g ()=T；綜合（i）（ii），總有g(shù) ()=T。所以，由賦值的任意性，dg。（b）否定消去規(guī)則（Ø）為：G,Øag，G,ØaØg Þ Ga 其