命題邏輯習(xí)題

命題邏輯習(xí)題命題邏輯習(xí)題命題邏輯習(xí)題命題邏輯習(xí)題編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:數(shù)理邏輯習(xí)題命題邏輯（一）1.指出下列語句中哪些是命題a)離散數(shù)學(xué)的研究對象是自然數(shù)。b)請勿喧嘩。c)夸夸其談可以創(chuàng)造財富。d)“飛碟”來自于銀河系之外。e)今天很冷。f)你明天還來嗎[解]a)是命題。因為它是假的陳述句。b)不是命題。因為它是祈使句。c)是命題。因為它是假的陳述句。d)是命題。因為它是可確定真假的陳述句，雖然其真假性現(xiàn)時還無法確定，但隨著人類認(rèn)識的發(fā)展終將得到證實。e)是命題。因為它是可確定真假的陳述句，其真假取決于說話人的主觀判斷和外部環(huán)境的客觀溫度。f)不是命題。因為它是疑問句。2.用符號形式寫下面命題，其中P表示命題“明天下雪”；Q表示命題“我們明天上課”；R表示命題“我們明天上公園”。a)如果明天下雪且我們停課，那么我們?nèi)ス珗@。b)只有明天不下雪，我們才去公園。c)除非明天不下雪且我們上公園，否則我們將上課。d)無論明天下雪與否，我們照常上課。[解]a)PQ→R；b)P→R（或R→P）；c)(PR)Q（或PRQ）；d)PP→Q（或Q）。3.用上題的命題P，Q，R解釋下面的形式命題。a)PQ→Rb)PRc)P→QRd)QR[解]a)只有明天下雪且不上課，我們才去公園；b)明天下雪，明天我們?nèi)ス珗@；c)如果明天不下雪，那么我們上課或去公園；d)除非明天不停課(上課)，否則我們?nèi)ス珗@。4.將下述命題符號化a)不是小王就是老李來找過你。b)盡管小張與小趙是同學(xué)，但他們很少在一起。c)如果程序能正常結(jié)束，那么就不會有語法錯誤。d)既然你今天不去開會，就該在家好好休息一下。e)只有博覽群書，知識才能豐富。f)只要懂得法律，就能夠成為一名律師。g)學(xué)好數(shù)、理、化，走扁天下都不怕。h)并非由于學(xué)校是重點(diǎn)，畢業(yè)生才是一流的，而是由于畢業(yè)生是一流的，學(xué)校才能成為重點(diǎn)。i)他能考上交大，除了由于他有一個較好的環(huán)境之外，還在于他平時的刻苦精神。[解]a)令：P：小王來找過你Q：老李來找過你形式化公式：PQ（實際上是不可兼或：PQ）；b)令：P：小張與小趙是同學(xué)Q：小張與趙在一起。形式化公式：PQ；c)令：P：程序正常結(jié)束Q：程序有語法錯誤形式化公式：P→Q；d)令：P：你今天去開會Q：你在家休息一下。形式化公式：PQ；e)令：P：(某人)博覽群書Q：(某人)知識豐富形式化公式：P→Q（或者Q→P）；f)令：P：(某人)懂得法津Q：(某人)成為一名律師形式化公式：P→Q；g)令：P：(某人)學(xué)好數(shù)學(xué)Q：(某人)學(xué)好物理R：(某人)學(xué)好化學(xué)S：(某人)走遍天下都不怕形式化公式：PQR→S；h)令：P：學(xué)校是重點(diǎn)Q：畢業(yè)是一流的形式化公式：(P→Q)(Q→P)；i)令：P：他考上了交大Q：他有一個較好的環(huán)境R：他平時刻苦形式化公式：QR→P。5.試通過對命題公式中聯(lián)結(jié)詞的個數(shù)歸納，證明命題公式在任一指派下的真假值都是唯一的。[證](采用串值數(shù)學(xué)歸納法)為證命題公式在任一賦值υ下的真值是唯一的，我們對公式中所含聯(lián)結(jié)詞的個數(shù)n進(jìn)行串值歸納：1）若n＝0，則α＝P是一原子公式，從而α(υ)＝P(υ)顯然是唯一的。2）假設(shè)n＝0，1，2，…，k時，任何含有n個聯(lián)結(jié)詞的公式α′在υ下的真值α′(υ)是唯一的。3）于是，當(dāng)n＝k+1時，則根據(jù)合式公式的形成規(guī)則，可知＝α1，或者α＝α1*α2（這里*＝或或→或）。我們設(shè)1和2中的聯(lián)結(jié)詞個數(shù)分別為k1和k2，那么a)當(dāng)α＝α1時，則有k1+1＝k+1，從而k1＝k0于是由歸納假設(shè)可知，真值是唯一的，所以由的真值表知真值α(υ)＝(α1(υ))是唯一的；b)當(dāng)α＝α1*α2時，則有k1+k2+1＝k+1，從而k1+k2＝k，即有k1k，k2k。于是由歸納假設(shè)知，真值α1(υ)，α2(υ)是唯一的，所以由*的真值表（，，→，的真值表）知真值α(υ)＝α1(υ)*α2(υ)都是唯一的。這就用串值歸納法證明了命題公式α在任一賦值υ下的真值（真假值）都是唯一的。6.令P，Q，R，S分別取值為T，F(xiàn)，T，F(xiàn)。求出下列命題公式在相應(yīng)指派下的真假值。a)P(Q→PR)b)QP→(QSR)c)(P→Q)(R→QS)d)P(Q→RS)QP[解]這里賦值υ＝（T，F(xiàn)，T，F(xiàn)）a)(P(Q→PR))(υ)＝P(Q→PR)＝T(F→TT)＝F(F→T)＝FT＝Tb)(QP→(QSR))(υ)＝QP→(QSR)＝FT→(FFT)＝T→(FT)＝T→F＝Fc)((P→Q)(R→QS))(υ)＝(P→Q)(R→QS))＝(T→F)(T→FF)＝F(T→F)＝FF＝Fd)(P(Q→RS)QP)(υ)＝(P(Q→RS)QP)＝T(F→TF)FT＝T(F→TT)FF＝T(F→T))F＝TTF＝TF＝F7.構(gòu)造下列命題公式的真值表。a)P(QR)b)(P→Q)(PR)c)(P→(QQ))→Pd)((P→Q)→(P→R))→(P→(Q→R))[解]a)PQRQRP(QR)TTTTTTTFTTTFTTTTFFFFFTTTFFTFTFFFTTFFFFFFb)PQRP→QPR(P→Q)(PR)TTTTTTTTFTTTTFTFTFTFFFTFFTTTTTFTFTFFFFTTTTFFFTFFc)PQPQQQP→(QQ)(P→(QQ))→PTTFFFFTTFFTFFTFTTFFTTFFTTFTTd)PQRP→QP→RQ→R(P→Q)→(P→R)P→(Q→R)((P→Q)→(P→R))→(P→(Q→R))TTTTTTTTTTTFTFFFFTTFTFTTTTTTFFFFTTTTFTTTTTTTTFTFTTFTTTFFTTTTTTTFFFTTTTTT8.利用真值表法判斷下列邏輯等價式是否成立。a)(P→Q)┝┥(Q→P)b)(P→Q)┝┥(Q→P)c)P→(Q→R)┝┥(P→Q)→(P→R)d)(P→Q)┝┥PQe)(PQ)┝┥PQf)PQ┝┥(PQ)(PQ)g)P→(Q→P)┝┥P→(Q→P)h)(P→R)(Q→R)┝┥PQ→Ri)(PQ)R┝┥P(QR)[解a)成立。PQPQP→QQ→PTTFFFFTFFTTTFTTFTTFFTTTT此真值表最后兩列全完相同。故a)的邏輯等價式成立。b)不成立。PQP→QQ→PTTTTTFFTFTTFFFTF此真值表最后兩列不完全相同。故b)的邏輯等價式不成立。c)成立。PQRP→QP→RQ→RP→(Q→R)(P→Q)→(P→R)TTTTTTTTTTFTFFFFTFTFTTTTTFFFFTTTFTTTTTTTFTFTTFTTFFTTTTTTFFFTTTTT此真值表最后兩列完全相同。故c)的邏輯等價式成立。d)成立。PQQP→Q(P→Q)PQTTFTFFTFTFTTFTFTFFFFTTFF此真值表最后兩列完全相同。故d)的邏輯等價式成立。e)成立。PQPQPQ(PQ)PQTTFFTFFTFFTFTTFTTFFTTFFTTFTT此真值表最后兩列完全相同。故e)的邏輯等價式成立。f)成立。PQPQPQPQPQ(PQ)(PQ)TTFFTFTTTFFTFFFFFTTFFFFFFFTTFTTT此真值表最后兩列完全相同。故f)的邏輯等價式成立。g)成立。PQPQ→PQ→PP→(Q→P)P→(Q→P)TTFTFTTTFFTTTTFTTFTTTFFTTTTT此值表最后兩列完工全相同。故f)邏輯等價式成立。h)成立。PQRP→RQ→RPQ(P→R)(Q→R)PQ→RTTTTTTTTTTFFFTFFTFTTTTTTTFFFTTFFFTTTTTTTFTFTFTFFFFTTTFTTFFFTTFTT此真值表最后兩列完全相同。故h)的邏輯等價式成立。i)成立。PQRPQQR(PQ)RP(QR)TTTTTTTTTFTFFFTFTFFFFTFFFTTTFTTFTFFFTFFFTTFFTTFTTFFFTTFF此真值表最后兩列完全相同。故i)的邏輯等價式成立。9.東東的爺爺帶東東乘車去玩，當(dāng)路過一座高樓時，爺爺說：“你只有現(xiàn)在好好學(xué)習(xí)，將來才能住上這樣的高樓?！睎|東聽了爺爺?shù)脑捯院螅卮鹫f，“爺爺決有住上這樣的高樓，所以爺爺沒有好好學(xué)習(xí)。”請問：東東是否誤解了爺爺原話的意思，為什么[解]東東誤解了爺爺原話的意思。因為若令：P：(你)現(xiàn)在好好學(xué)習(xí)Q：(你)將來住上這樣的高樓則爺爺?shù)脑捫问交癁椋篞→P而東東的回答形式化是：Q→P這兩個公式不是邏輯等價的。這可用真值表法證明如下：PQPQQ→PQ→PTTFFTTTFFTTFFTTFFTFFTTTT此真值表最后兩列不完全相同，說明Q→P與Q→P不是邏輯等價的（事實上Q→P┝┥P→Q），所以，東東的回答與爺爺?shù)脑捠遣坏葍r的，不是一個意思。因而，東東誤解了爺爺原話的意思。10.某單位派人外出學(xué)習(xí)。但由于工作關(guān)系，A，B兩個不能同去。如果B去則C必須留下工作。如果派D去則B和C至少應(yīng)去一人。試問a)四人中最多能派幾人b)若己決定派B去，是否還可以增派其它人請通過對成真指派的分析給出上面問題的最佳人選。[解]令：P：A去Q：B去R：C去S：D去則問題形式化為一公式（條件公式）：α=(PQ)(Q→R)(S→(QR))a)因四人全去,得到賦值υ1＝(T，T，T，T)，使得真值α(υ1)＝F，從而四人全去不行,故至多只能派三人同去。又因A和B不能同時去，而A去，C去，D去，得到賦值υ2＝(T，F(xiàn)，T，T)，使得真值α(υ2)＝T，故至少可以派三個人同去。所以，四人中最多能派三人同去。b)若己決定派B去，則根據(jù)(PQ)，可知不能派A去；又根據(jù)(Q→R)，可知不能派C去，因而至多只能增派D去。從而得到賦值υ3＝(F，T，F(xiàn)，T)，使得真值α(υ3)＝T。故此，若己決定派B去，則還可以增派D同去。11.利用真值表判斷下列公式的永真性（有效性）。a)P→(P→Q)b)(P→Q)→((Q→R)→(P→R))c)((PQ)R)(PQ→R)d)(P→(Q→R))(Q→(P→R))[解]a)?P→（P→Q）PQPP→QP→(P→Q)TTFTTTFFFTFTTTTFFTTT因為此值表的最后一列全是T,故公式是有效的。b)?(P→Q)→((Q→R)→(P→R))PQRP→QQ→PP→R(Q→R)→(P→R)(P→Q)→((Q→R)→(P→R))TTTTTTTTTTFTFFTTTFTFTTTTTFFFTFFTFTTTTTTTFTFTFTTTFFTTTTTTFFFTTTTT因為此真值表的最后一列全是T,故公式是有效的。c)?((PQ)R)((PQ)→R)PQRPQQPR(PQ)RPQ→R((PQ)R)(PQ→R)TTTTTFTFTTTFTTTFTTTFTTFFTTTTFFTFTFTTFTTTFFTTTFTFTFTFTTFFTFFFFTTFFFFFTFTT因為此真值表的最后一列全是T,故公式是有效的。d)?(P→(Q→R))(Q→(P→R))PQRQ→RP→RP→(Q→R)Q→(P→R)TTTTTTTTTFFFFFTFTTTTTTFFTFTTFTTTTTTFTFFTTTFFTTTTTFFFTTTT因為此真值表的最后兩列完全相同,故公式是有效的。12.利用真值表證明下列邏輯蘊(yùn)涵式。a)(P→Q)?Pb)Q(P→Q)?Pc)(PQ)(P→R)(Q→S)?RSd)P→(QQ)?P[證]a)邏輯蘊(yùn)涵式(P→Q)?P成立。PQP→Q(P→Q)PTTTFTTFFTTFTTFFFFTFF因為此真值表凡是(P→Q)列為T的行，P列相應(yīng)的行也為T。b)邏輯蘊(yùn)涵式Q(P→Q)?P成立PQQP→QQ(P→Q)PTTFTFFTFTFFFFTFTFTFFTTTT因為此真值表凡是Q(P→Q)列為T的行，P列相應(yīng)的行也為T。c)邏輯蘊(yùn)涵式(PQ)(P→R)(Q→S)?RS成立。PQRSPQPRQ→S(PQ)(P→R)(Q→S)RSTTTTTTTTTTTTFTTFFTTTFTTFTFTTTFFTFFFFTFTTTTTTTTFTFTTTTTTFFTTFTFTTFFFTFTFFFTTTTTTTTFTTFTTFFTFTFTTTTTTFTFFTTFFFFFTTFTTFTFFTFFTTFTFFFTFTTFTFFFFFTTFF因為此真值表凡是(PQ)(P→R)(Q→S)列為T的行，RS列相應(yīng)的行也為T。d)邏輯蘊(yùn)涵式P→(QQ)?P成立。PQPQQQP→(QQ)PTTFFFTTTFFTFTTFTTFFFFFFTTFFF因為真值表凡是P→(QQ)列為T的行，P列相應(yīng)的行也為T。13.求下列命題公式的代入實例。a)P→((P→Q)→Q)其中：P代入為P→Q，Q代入為(P→Q)→Qb)(P→Q)→((Q→R)→(P→R))其中，P代入為Q→R，Q代入為P→R。[解]a)(P→((P→Q)→Q))[(P→Q)/P,((P→Q)→Q)/Q]=(P→Q)→(((P→Q)→((P→Q)→Q))→((P→Q)→Q))；b)((P→Q)→((Q→R)→(P→R)))[(Q→R)/P,(P→R)/Q]=((Q→R)→(P→R))→(((P→R)→R)→((Q→R)→R))。14.設(shè)1，2，為命題公式。如果1?2，證明：a)2?1b)1?2c)1?2d)1→?2→[證]a)對于任一賦值υ，如果(2)(υ)=T，則2(υ)=F。根據(jù)1?2，可知1(υ)=F，從而(1)(υ)=T。所以2?1成立。b)對任一賦值υ，如果(1)(υ)=T，那么1(υ)=T且(υ)=T。根據(jù)1?2，可得2(υ)=T，從而2(υ)=T且(υ)=T，也即是(2)(υ)=T，所以1?2成立。c)對任一賦值υ，如果(1)(υ)=T，那么1(υ)=T或者(υ)=T。于是分情況證明如下：1°若1(υ)=T，那么根據(jù)1?2，可知2(υ)=T，因此(2)(υ)=T；2°若(υ)=T，則顯然(2)(υ)=T；因此，無論如何，總有(2)(υ)=T。所以1?2成立。d)對任一賦值υ，如果(2→)(υ)=T，那么若2(υ)=T，則(υ)=T。于是：1°若1(υ)=F，那么顯然有(1→)(υ)=T；2°若1(υ)=T，那么根據(jù)1?2，可知2(υ)=T，從而有(υ)=T，因此得到(1→)(υ)=T；于是，無論如何，總有(1→)(υ)=T。所以1→?2→成立。15.利用變換法證明下列邏輯等價式。a)P→(Q→P)┝┥P→(P→Q)b)(P→R)(Q→R)┝┥PQ→Rc)(PQ)┝┥(PQ)(PQ)d)(P→Q)┝┥PQ[證明]a)P→(Q→P)┝┥P(QP)（替換定理，聯(lián)結(jié)詞化歸）┝┥(PP)Q（結(jié)合律）┝┥PP┝┥(PP)Q┝┥P(PQ)（結(jié)合律）┝┥P(PQ)（替換定理，雙重否定律）┝┥P→(P→Q)（替換定理，聯(lián)結(jié)詞化歸）(P→R)(Q→R)┝┥(PR)(QR)（替換定理，聯(lián)結(jié)詞化歸）┝┥(PQ)R（分配律）┝┥(PQ)R（替換定理，deMorgan律）┝┥PQ→R（聯(lián)結(jié)詞化歸）c)(PQ)┝┥((P→Q)(Q→R))（替換定理，聯(lián)結(jié)詞化歸）┝┥((PQ)(QP))（替換定理，聯(lián)結(jié)詞化歸）┝┥(PQ)(QP)（deMorgan律）┝┥(PQ)(QP)（替換定理，deMorgam律）┝┥(PQ)(QP)（替換定理，雙重否定律）┝┥(PP)(PQ)(PQ)(QQ)（分配律、替換定理，結(jié)合律，交換律）┝┥(PQ)(PQ)（化簡律）d)(P→Q)┝┥(PQ)（替換定理，聯(lián)結(jié)詞化歸）┝┥PQ（deMergan律）┝┥PQ（替換定理，雙重否定律）。16.利用變換法證明下列邏輯蘊(yùn)涵式。a)P→(Q→R)?(P→Q)→(P→R)b)(P→Q)→Q?PQc)(P→Q)→(Q→P)?Q→Pd)P→Q?PR→QR[證]a)實際上，我們可證邏輯等價式：P→(Q→R)┝┥(P→Q)→(P→R)就是P→(Q→R)┝┥P(QR)（替換定理，聯(lián)結(jié)詞化歸）┝┥(PPR)(P┐QR)（化簡律）┝┥(PQ)(PR)（分配律）┝┥(PQ)(PR)（替換定理、雙重否定律，deMorgan律）┝┥(P→Q)(P→R)（替換定理，聯(lián)結(jié)詞化歸）┝┥(P→Q)→(P→R)（聯(lián)結(jié)詞化歸）b)實際上我們可證邏輯等價式：(P→Q)→Q┝┥P∨Q變換證明如下：(P→Q)→Q┝┥(PQ)Q（替換定理，聯(lián)結(jié)詞化歸）┝┥(PQ)Q（替換定理、deMorgan律）┝┥(PQ)Q（替換定理、雙重否定律）┝┥(PQ)(QQ)（分配律）┝┥PQ（化簡律）c)實際上，我們可證邏輯等價式：(P→Q)→(Q→P)┝┥Q→P變換證明如下(P→Q)→(Q→P)┝┥(PQ)(QP)（替換定理、聯(lián)結(jié)詞化歸）┝┥(PQ)(QP)（替換定理，deMorgasn律）┝┥(PQ)(QP)（替換定理、雙重否定律）┝┥QP（吸收律）┝┥Q→P（聯(lián)結(jié)詞化歸）d)P→Q?PQ（聯(lián)結(jié)詞化歸）?PQR（析取構(gòu)成式）?(PQR)(RRQ)（化簡律）?(PR)(QR)（分配律）?(PR)(QR)（替換定律，deMorgan律）?PR→QR（聯(lián)結(jié)詞化歸）。17.求下列命題公式的對偶式。a)(P→Q)→PRb)(PQ)(PQ)c)(P→QR)(Q→P)[解]a)由于(P→Q)→PR┝┥(PQ)PR所以其對偶式為(PQ)PR。b)由于(PQ)(PQ)┝┥((P→Q)(Q→P))(PQ)┝┥((PQ)(QP))(PQ)┝┥((PQ)(PQ))(PQ)因此其對偶式為((PQ)(PQ))(PQ)。c)因為(P→QR)(Q→P)┝┥(PQR)(QP)┝┥(PQR)(QP)從而其對偶式為(PQR)(QP)。18.將下列命題公式化成只含有全功能聯(lián)結(jié)詞集合{,→}中聯(lián)結(jié)詞的命題公式。a)P(QR)b)(PQ)R→PRc)P(QR→P)d)(P(Q→RP))[解]a)P(QR)┝┥(QR)P┝┥(QR)P┝┥(QR)P┝┥(Q→R)→Pb)(PQ)R→PR┝┥((P→Q)R)→(P→R)┝┥((P→Q)→R)→(P→R)c)P(QR→P)┝┥P→((Q→R)→P)┝┥P→((R→Q)→P)d)(P(Q→RP))┝┥((P→(Q→RP))((Q→RP)→P))┝┥((P→(Q→(P→R)))((Q→(P→R))→P))┝┥(P→(Q→(P→R)))→((Q→(P→R))→P)。19.證明{↓}是極小全功能的。[證]根據(jù)定理2，聯(lián)結(jié)詞集{，}是全功能的，故為證{↓}是全功能的，只需證明{，}中的每個聯(lián)結(jié)詞都可分別由↓來表示即可。由于P┝┥P↓PPQ┝┥(P↓Q)↓(P↓Q)因此{(lán)↓}是全功能的。由于{↓}中只有一個聯(lián)結(jié)詞，故所以{↓}是極小全功能的。20.證明{，}不是全功能的。[證]{，}不是全功能的。否則，聯(lián)結(jié)詞必定可由聯(lián)結(jié)詞集{，}來表示，即，對于任一原子公式P，存在公式，中只含聯(lián)結(jié)詞和，使得P┝┥設(shè)υ是一對中出現(xiàn)的所有命題變項及P都指派真值T的賦值。則我們可用串值歸納法證明(υ)＝T；但是(P)(υ)＝T＝F，從而P不可能與公式邏輯等價，矛盾。事實上，我們施串值歸納于中聯(lián)結(jié)詞和的個數(shù)m，來證(υ)＝T：當(dāng)m＝1時，只能有＝PP或PQ或QQ,或PP或PQ或QQ。由于υ給P和Q都賦值T，故這時顯然有(υ)＝T。當(dāng)m＝1，2，…，k時，歸納假設(shè)總有(υ)＝T。則當(dāng)m＝k+1時，只能有＝12或12，其中1和2中所含聯(lián)結(jié)詞和的個數(shù)分別為和，于是就有即從而有，，因此，根據(jù)歸納假設(shè)有1(υ)=T，2(υ)=T,所以(υ)=1(υ)2(υ)=TT=T或者(υ)=1(υ)2(υ)=TT=T總之(υ)=T。21.將下列命題公式化為析取范式。a)PQ→(PQ)Rb)(P(P→Q))(Q→R)c)(P→QR)(P→QR)d)Q(P→Q(Q→R))[解]a)(PQ)→(PQ)R┝┥(PQ)(((P→Q)(Q→P))R)┝┥(PQ)(((PQ)(QP))R)┝┥(PQ)(PP)(QP)(PQ)(QQ)R┝┥(PQ)(PQ)(PQ)Rb)(P(P→Q))(Q→R)┝┥(P(PQ))(QR)┝┥(PPQ))(QR)┝┥(PQ)(QR)┝┥(PQ)(QQ)(PR)(QR)┝┥(PQ)(PR)(QR)c)(P→(Q∧R))∧(┐P→(┐Q∧┐R))┝┥(P(QR))(P(QR))┝┥(P(QR))(P(QR))┝┥(PP)(QRP)(PQR)(QRQR))┝┥(PQR)(PQR)d)Q(P→(Q(Q→R)))┝┥Q(P(Q(QR)))┝┥Q(QP(QR))┝┥Q22.將上題的各命公式化為主析取范式。[解]a)(PQ)→((PQ)R)┝┥(PQ)(PQ)(PQ)R┝┥((PQ)(RR))((PQ)(RR))((PQ)(RR))((QQ)R))┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(QR)(QR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)((PP))(QR))((PP)(QR))┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥m7m6m5m4m3m2m1b)(P(P→Q))(Q→R)┝┥(PQ)(PR)(QR)┝┥((PQ)(RR))((PR)(OQ))((PP)(QR))┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)┝┥m7m5m4m3c)(P→QR)(P→QR)┝┥(PQR)(PQR)┝┥m7m0d)Q(P→(Q(Q→R)))┝┥Q┝┥(PQ)(PQ)┝┥((PQ)(RR))((PQ)(RR))┝┥(PQR)(PQR)(PQR)(PQR)┝┥m7m6m3m223.通過化主析取范式的方法，判斷下面的邏輯等價式是否成立。a)(PQ)(PQR)┝┥(P(QR))(Q(PR))b)P(PQ)R┝┥(PQ)(QR)[解]a)因為(PQ)(PQR)┝┥((PQ)(RR))(PQR)┝┥(PQR)(PQR)(PQR)┝┥m7m6m3又因為(P(QR))(Q(PR))┝┥(PQ)(QRQ)(PPR)(QRPR)┝┥(PQ)(QR)(PQR)┝┥((PQ)(RR))((PP)(QR))(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)┝┥m7m6m3所以(PQ)(PQR)┝┥(P(QR))(Q(PR))b)因為P(PQ)R┝┥(P(QQ))((PQ)(RR))((QQ)R)┝┥(PQ)(PQ)(PQR)(PQR)(QR)(QR)┝┥(PQR)(PQR)((PQ)(RR))((PQ)(RR))((PP)(QR))((PP)(QR))┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥m7m6m5m3m2m1m0又因為(PQ)(QR)┝┥(PQ)(QR)┝┥(PQ)(QR)┝┥Q(PR)┝┥((PP)Q)(P(QQ)R)┝┥(PQ)(PQ)(PQR)(PQR)┝┥((PQ)(RR))((PQ)(RR))(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)┝┥(PQR)(PQR)(PQR)(PQR)(PQR)┝┥m7m6m3m2m1所以P(PQ)R與(PQ)(QR)不邏輯等價。24.設(shè)計一個控制兩間會議室的照明電路，要求分別裝在這兩間會議室的兩只開關(guān)都能控制整個會議室的照明。[解]會議室兩個門旁開關(guān)表示k1、k2，“0”表示開關(guān)斷開，“1”表示開關(guān)接通。S表示會議室的照明狀態(tài)，“1”表示全室燈亮，“0”表示全室燈暗。假設(shè)開始時，室內(nèi)無人，燈暗。兩只開關(guān)都處于“0”狀態(tài)。有人進(jìn)入室內(nèi)時，隨手改變門旁的開關(guān)狀態(tài)，則會議室燈亮，S為“1”。此時兩只開關(guān)中有一只（奇數(shù)）處于“0”狀態(tài)。當(dāng)有人離開會議室時，隨手改變門旁的開關(guān)狀態(tài)，會議室燈暗，S為“0”。此時兩只開關(guān)（偶數(shù)）都處于“0”狀態(tài)。……。故此,我們有:當(dāng)有偶數(shù)只開關(guān)處于“0”狀態(tài)時，S為“0”；當(dāng)有奇數(shù)只開關(guān)處于“0”狀態(tài)時，S為“1”；所以，我們有:S┝┥(k1k2)(k1k2)┝┥(k1k2)(k1k2)其電路圖如圖所示：┐┐┐∧∧K1K非門非門或門與門S或門第24題圖25.某公安員在追捕一個逃犯的途中面對前面具有兩條路分叉的路口。己知該路口住著兩個居民，其中一個說謊成性，另一個天性誠實。請問：該公安員如何發(fā)問才能確定逃犯的去向。[解]公安人員手指一路問身旁一名居民說：“逃犯是從這條路逃走的，他（指另一居民）將回答‘是’，你說對嗎”當(dāng)被問居民回答：“否”時，公安人員應(yīng)從所指那條路去追逃犯；當(dāng)被問居民回答“對”時，公安人員應(yīng)從另一條路去追逃犯。分析：①如果被問居民誠實，他回答“對”。則另一居民是說謊者，他回答“是”，那么，逃犯沒有從所指路逃走；②如果被問居民誠實，他回答“否”。則另一居民是說謊者，他回答“否”，那么，逃犯是從所指路逃走的；③如被問居民說謊，可以此類推分析。形式化：設(shè)P：被問居民是誠實的Q：被問居民回答“是”R：另一居民回答“是”S：逃犯是從所指路逃走的則S┝┥(PQ)(PQ)┝┥(PP)Q┝┥QR┝┥PQ真值表如下：PQRSQPQTTTFFTTFFTTFFTFFFFFFTTTT即：“逃犯是從所指路逃走的”當(dāng)且僅當(dāng)“被問居民誠實且其回答是‘否’”（即另一人不誠實因而將回答“否”）或者“被問戰(zhàn)士說謊且其回答是‘否’”（即另一人誠實因而將回答是“是”）當(dāng)且僅當(dāng)“被問戰(zhàn)士回答是‘否’”。并且“另一居民回答是‘是’”當(dāng)且僅當(dāng)“被問居民誠實且其回答是‘是’”或者“被問居民說謊且其回答是‘否’”。26.證明析取消去規(guī)則（－）和否定規(guī)則（－）都是可靠的。[證](a)析取消去規(guī)則（－）為：?，,?，,??其可靠性為要性：?，,?，,??證法一：令：為中所有公式之合取式。根據(jù)定理2，則要證：?，?，??根據(jù)定理1，即要證：?→，?→，?→?→即要證：?(→)(→)(→)?→（*）但是我們能夠證明：(→)(→)(→)?→（**）事實上：(→)(→)(→)┝┥()()()┝┥(()(()))┝┥(())┝┥()()??→因此，根據(jù)（**）可知（*）成立。所以析取消去法規(guī)則（－）是可靠的。證法二：令：為中所有公式之合取式。根據(jù)定理2，則要證：?，?，??對于任一賦值υ，若(υ)=T，則由?，可得()(υ)=T，于是有(υ)=T或者(υ)=T。(i)若(υ)=T，則()(υ)=T，從而由?，可得(υ)=T；(ii)若(υ)=T，則()(υ)=T，從而由?，可得(υ)=T；綜合（i）（ii），總有(υ)=T。所以，由賦值υ的任意性，?。（b）否定消去規(guī)則（－）為：,?，,??其可靠性為要性：,?，,??證法一：令：為中所有公式之合取式。根據(jù)定理2，則要證：?，??根據(jù)定理1，即要證：?→，?→?→即要證：?(→)(→)?→（*）但是我們能夠證明：(→)(→)?→（**）事實上：(→)(→)┝┥()()┝┥()())┝┥┝┥→因此，根據(jù)（**）可知（*）成立。所以否定消去規(guī)則（－）是可靠的。證法二：令：為中所有公式之合取式。根據(jù)定理2，則要證：?，??對于任一賦值υ，若(υ)=T，則有(υ)=T。否則(υ)=F，從而()(υ)=F，于是有()(υ)=T。(i)由?，可得(υ)=T；(ii)由?，可得()(υ)=T，從而可得(υ)=F；(i),(ii)矛盾。所以，由賦值υ的任意性，?。27.構(gòu)造形式證明過程。??()?()()?()()?()()()?()()?()()??→P?P→QQ?P→QQ,P→Q?P[證]a)（1） P（2） －(1)（3） －(1)（4） －(2)(3)b)（1） P（2）□ H(－)（3）□ +(2)（4）□ H(－)（5）□ +（4）（6） －(1)(3)(5)|(2)(4)c)（1）() P（2） －(1)（3） －(1)（4） －(2)（5） －(1)（6） +(4)(5)（7）() +(3)(6)d)（1）() P（2）□ H(－)（3）□□ H(－)（4）□□() +(3)（5）□□ H(－)（6）□□ +(5)（7）□□() +(6)（8）□() －(2)(4)(7)|(3)(5)（9）□ H(－)（10）□ +(9)（11）□() +(10)（12）() －(1)(8)(11)|(12)(9)e)（1）() P（2） －(1)（3） －(1)（4）□β H(－)（5）□ +(2)(4)（6）□()() +(5)（7）□ H(－)（8）□ +(2)(7)（9）□()() +(8)（10）()() －(3)(6)(9)|(4)(7)f)（1）() P（2）□ H(－)（3）□ +(2)（4）□ +(2)（5）□()() +(3)(4)（6）□ H(－)（7）□ －(6)（8）□ +(7)（9）□ －(6)（10）□ +(9)（11）□()() +(8)(10)（12）()() －(1)(5)(11)|(2)(6)（1） P（2）□ H(－)（3）□□ H(＋)（4）□□ －(3)（5）□() ＋(4)(2)|(3)（6）□ H(－)（7）□□ H(＋)（8）□□ －(7)（9）□() ＋(8)(6)|(7)（10）() －(1)(5)(9)|(2)(6)h)（1）() P（2）□ H(＋)（3）□ +(2)（4） ＋(3)(1)|(2)（5）□ H(＋)（6）□ +(5)（7） ＋(6)(1)|(5)（8） +(4)(7)i)（1） P（2）□ H(－)（3）□□ H(→+)（4）□□□ H(－)（5）□□ －(3)(2)|(4)（6）□→ →+(5)|(3)（7）□ H(－)（8）□□ H(→+)（9）□→ →+(7)|(8)（10）→ －(1)(6)(9)|(2)(7)j)（1）P P（2）□P H(→+)（3）□□Q H(－)（4）□Q －(2)(1)|(3)（5）P→Q →+(4)|(2)k)（1）Q P（2）□P H(→+)（3）P→Q →+(1)|(2)l)（1）Q P（2）P→Q P（3）□P H(+)（4）□Q →－(3)(2)（5）P +(4)(1)|(3)28.構(gòu)造形式推理過程?！?()?,→,→?→,→?→→(→),?→(→)(),?→→,,→,→?[證]a)（1）→ P（2）() P（3）□ H(＋)（4）□ →－(3)(1)（5）□ +(4)（6） +(5)(2)|(3)b)（1） P（2）→ P（3）→ P（4）□ H(－)（5）□ →+(4)(2)（6）□ +(5)（7）□ H(－)（8）□ →－(7)(3)（9）□ +(8)（10） －(1)(6)(9)|(4)(7)c)（1）→ P（2）→ P（3）□ H(→+)（4）□□ H(+)（5）□□ +(4)（6）□□ →－(5)(1)（7）□□ →－(6)(2)（8）□□□ H(－)（9）□□□□ H(+)（10）□□□□ －(3)（11）□□□() +(8)(10)|(9)（12）□□□ H(－)（13）□□□□ H(+)（14）□□□□ －(3)（15）□□□() +(12