第二章命題邏輯§2.2主要解題方法證明命題公式恒真或恒假主要有以下方法：方法一.真值表方法。即列出公式的真值表，若表中對(duì)應(yīng)公式所在列的每一取值全為1，這說明該公式在它的全部講解下都是真，所以是恒真的；若表中對(duì)應(yīng)公式所在列的每一取值全為0，這說明該公式在它的全部講解下都為假，所以是恒假的。真值表法比較煩雜，但只要仔細(xì)仔細(xì)，不會(huì)出錯(cuò)。例說明G=(PQR)(PQ)(PR)是恒真、恒假還是可滿足。解：該公式的真值表以下：PQRPQP(PQPRGRQR)(PQ)0001111100111111010111110111111110010011101100111100100111111111表由于表中對(duì)應(yīng)公式G所在列的每一取值全為1，故G恒真。方法二.以基本等價(jià)式為基礎(chǔ)，經(jīng)過屢次對(duì)一個(gè)公式的等價(jià)代換，使之最后轉(zhuǎn)變?yōu)橐粋€(gè)恒真式或恒假式，從而實(shí)現(xiàn)公式恒真或恒假的證明。例說明G=((PR)R)((QP)是恒真、恒假還是可滿足。解：由(PR)R=

P

R

R=1，以及(Q

P)

P=

（QP）

P=Q

PP=0知，((PR)R)((QP)P)=0，故G恒假。方法三.取式包含全部取式包含全部

設(shè)命題公式G含n個(gè)原子，若求得nn2個(gè)極大項(xiàng)，則G是恒假的。

G的主析G的主合方法四.對(duì)任給要判斷的命題公式G，設(shè)其中有原子P1，P2，，Pn，令P1取1值，求G的真值，或?yàn)?，或?yàn)?，或成為新公式G1且其中只有原子P2，，Pn，再令P1取0值，求G真值，這樣連續(xù)，到最后只含0或1為止，若最后結(jié)果全為1，則公式G恒真，若最后結(jié)果全為0，則公式G恒假，若最后結(jié)果有1，有0，則是可滿足的。例子拜會(huì)書中例。方法五.注意到公式G蘊(yùn)涵公式H的充要條件是：公式H是恒真的；公式G，H等價(jià)的充要條件是：公式GH是恒真的，所以，若是待觀察公式是GH型的，可將證明GH是恒真的轉(zhuǎn)變?yōu)樽C明G蘊(yùn)涵H；若是待觀察公式是GH型的，可將證明GH是恒真的轉(zhuǎn)變?yōu)樽C明G和H相互相蘊(yùn)涵。例證明G=(PR)((QR)((PQ)R))恒真。證明：要證明(P恒真，只要證明(P我們使用形式演繹法。

R)((QR)((PQ)R))R)((QR)((PQ)R))。（1）PR規(guī)則1（2）QR附加前提（3）PR規(guī)則2，依照（1）（4）QR規(guī)則2，依照（2）（5）（PR）（QR）規(guī)則2，依照（3）、（4）（6）（PQ）R規(guī)則2，依照（5）（7）（PQ）R規(guī)則2，依照（6）（8）（PQ）R規(guī)則2，依照（7）（9）(QR)((PQ)R)規(guī)則3，依照（2）、8）公式蘊(yùn)涵的證明方法主要有以下方法：給出兩個(gè)公式A，B，證明A蘊(yùn)涵B，我們有以下幾種方法：方法一.真值表法。將公式A和公式B同列在一真值表中，掃描公式A所對(duì)應(yīng)的列，考據(jù)該列真值為行家上相應(yīng)公式B所對(duì)應(yīng)列上的每一項(xiàng)必為A蘊(yùn)涵B。

1

的每一項(xiàng)，它所1（真），則公式例設(shè)A=(PQR)(PQ)，B=(PR)，證明：B。證明：PQRPQPABRQ00011110011111010111101111111001001101100111001001111111表由表能夠看出，使A為真的講解均使B亦為真，所以，AB。方法二.證明AB是恒真公式。由例知，(PQR)(PQ)馬上可獲得例中的結(jié)論：(P(PR)，即AB。

(P

R)恒真，所以，QR)(PQ)例設(shè)A、B和C為命題公式，且AB。請(qǐng)分別闡述（必定或否定）以下關(guān)系式的正確性。（1）(AC)(BC)；（2）(AC)(BC)。解：由AB知，AB是恒真公式，故A=1時(shí)，B不能能為0。真值表以下：ABCAB(AC)(AC)(BC)(BC)000111001111010110011111110111111111表從真值表能夠看出，(AC)(BC)(A不是恒真公式，所以，

(AC)(A

C)(BC)

(BC)是恒真公式，所以，C)正確；(AC)(BC)(BC)不正確。例設(shè)A=(R

P)Q，B=PB

Q，證明

A蘊(yùn)涵

B。(

((RP

Q)

P)Q)

(

P

Q)=

(

(

RP)

Q)=((

RP)

Q)(

PQ)=(

R

Q)(P

Q)(P

Q)=1方法三.利用一些基本等價(jià)式及蘊(yùn)涵式進(jìn)行推導(dǎo)。關(guān)于例，由基本等價(jià)式可得：A=(R=(

P)

QRP)

Q=(R

P)Q=(R=(R由教材中基本蘊(yùn)涵式2.P(PQ)，即A蘊(yùn)涵B。

Q)(PQ)Q)(PQ)QQ可知，(R

Q)

(P

Q)方法四.任取講解I，若I滿足A，往證I滿足B。例設(shè)A=PQ，B=(RQ)（（PR）Q），證明A蘊(yùn)涵B。證明：任取講解I，若I滿足A，則有以下兩種狀況：1）在講解I下，P為假，這時(shí)，B等價(jià)于(RQ)RQ），所以，I亦滿足B。（2）在講解I下，P為真，Q為真，所以，PRQ為真，故B為真，即，I滿足B。綜上，I滿足B，所以，A蘊(yùn)涵B。方法五.反證法，設(shè)結(jié)論假，往證前提假。關(guān)于例，證明(RP)Q蘊(yùn)涵PQ，若使用方法三，是很煩雜的，而使用方法四，就很簡(jiǎn)單。假設(shè)存在解釋I使PQ為假，則只有一種狀況，P在I下為真，且Q在I下為假，這時(shí)RP在I下為真，故I弄假Q(mào)。所以，(RP)Q蘊(yùn)涵PQ。

(R

P)方法六.分別將公式A和公式B轉(zhuǎn)變?yōu)樗鼈兏髯缘闹魑鋈∈交蛑骱先∈健Ｈ艄紸的主析取式所包含的全部極小項(xiàng)也包含在公式B的主析取式中；也許，公式B的主合取式中所包含的極大項(xiàng)均包含在公式A的主合取式中，則公式A蘊(yùn)涵公式B。使用這種方法需要注意，當(dāng)公式A和公式B中包含的原子不完好同樣時(shí)，在求兩公式的極小項(xiàng)或極大項(xiàng)時(shí)，要考慮該兩公式包含命題原子的并集中的全部原子。在例中，A和B的主析取式分別為：A=(PQR)(PQR)(PQR)(PQR)(PB=(PQR)(PQR)

QR)，(PQ

R)(

PQ

R)

(P

Q

R)

(P

QR)，可見，AB。A和

B的主合取式分別為：A=(P

QR)

(

PQ

R)

(

PQ

R),B=(

PQ

R)

(

PQ

R)可見，

A

B。別的若給出前提會(huì)集S={G1，，Gk}，公式G，證明有以下兩種方法：1.G1GkG

S

G形式演繹法：依照一些基本等價(jià)式和基本蘊(yùn)涵式，從S出發(fā)，演繹出G。教材中已經(jīng)給出了這方面的例子，在此不再贅述。求主合取式和主析取式極小項(xiàng)與極大項(xiàng)的性質(zhì)以3個(gè)原子為例，則對(duì)應(yīng)極小項(xiàng)和極大項(xiàng)的表為：PQR極小項(xiàng)極大項(xiàng)000m0=PM0=PQRQR0011QR1m=PM=PQR010m2=PQRM2=PQR011m=PQRM=PQR33100m4=PQRM4=PQR101m5=PQRM5=PQR110m=PQRM=PQR66111m=PQRM=PQR77表由表可知，對(duì)n個(gè)命題原子P1，，Pn，極小項(xiàng)有以下性質(zhì)：1）n個(gè)命題原子P1，，Pn有2n個(gè)不同樣的講解，每個(gè)講解對(duì)應(yīng)P1，，Pn的一個(gè)極小項(xiàng)。（2）對(duì)P1，，Pn的任意一個(gè)極小項(xiàng)m，有且只有一個(gè)講解使m取1值，若使極小項(xiàng)取1的講解對(duì)應(yīng)的二進(jìn)制數(shù)為i，則m記為mi，于是關(guān)于P1，，Pn的全部極小項(xiàng)為m0，m1，，m2n1。（3）任意兩個(gè)不同樣的極小項(xiàng)的合取式恒假：mimj=0，≠j。2n1（4）全部極小項(xiàng)的析取式恒真：mi=1。i0極大項(xiàng)有以下性質(zhì)：（1）n個(gè)命題原子P1，，Pn有2n個(gè)不同樣的講解，每個(gè)解釋對(duì)應(yīng)P1，，Pn的一個(gè)極大項(xiàng)。（2）對(duì)

P1，，

Pn

的任意一個(gè)極大項(xiàng)

M，有且只有一個(gè)講解使M取0值，若使極大項(xiàng)取0的講解對(duì)應(yīng)的二進(jìn)制數(shù)為i，則M記為Mi，于是關(guān)于P1，，Pn的全部極大項(xiàng)為M0，M1，，M2n1。（3）任意兩個(gè)不同樣的極大項(xiàng)的析取式恒真：MiMj=1，i≠j。2n1（4）全部極大項(xiàng)的合取式恒假：Mi=0。i0主合取式與主析取式之間的關(guān)系由極小項(xiàng)和極大項(xiàng)的定義可知，二者有以下關(guān)系：mi=Mi，Mi=mi由此可知，若PQR為一公式G的主合取式，則G=G=M0=(M1M2M6)=MMM126=m1m2m6為G的主析取式。若（PQ）（PQ）（PQ）為一公式的主析取式，則H=H=(（PQ）（PQ）（PQ）)=

（（m0

m1

m3））(m2)=M2=PQ為H的主合取式。一般地，若公式A中含n個(gè)命題原子，且A的主析取式中含有k個(gè)極小項(xiàng)：mi1,...,mik，則A的主析取式中必含有其余的2n-k個(gè)極小項(xiàng)，不如設(shè)為：mj1,...,mjn，即2kA=mj1...mj2nk。所以，A=A=（mj1...mj2nk）=mj1...mj2nk=Mj1...Mjn。2k由此可知，從一公式A的主析取式求其主合取式的步驟以下：1）求出A的主析取式中沒有包含的全部極小項(xiàng)。2）求出與（1）中極小項(xiàng)下標(biāo)同樣的極大項(xiàng)。（3）將（2）求出的全部極大項(xiàng)合取起來，即得式。

A的主合取近似地，從一公式A的主合取式求其主析取式的步驟為：1）求出A的主合取式中沒有包含的全部極大項(xiàng)。2）求出與（1）中極大項(xiàng)下標(biāo)同樣的極小項(xiàng)。（3）將（2）求出的全部極小項(xiàng)析取起來，即得A的主析取式。求主合取式和主析取式的方法方法一.真值表法。主析取式恰好是使得公式為真的講解所對(duì)應(yīng)的極小項(xiàng)的析取組成，主合取式恰好是使得公式為假的講解所對(duì)應(yīng)的極大項(xiàng)的合取組成。方法二.公式推導(dǎo)法。設(shè)命題公式G中全部不同樣原子為P1，，Pn，則G的主析取式的求法以下：將公式G化為析取式。刪去析取式中全部恒假的短語。用等冪律將短語中重復(fù)出現(xiàn)的同一文字化簡(jiǎn)為一次出現(xiàn)，如，PP=P。關(guān)于全部不是關(guān)于P1，，Pn的極小項(xiàng)的短語使用同一律，補(bǔ)進(jìn)短語中未出現(xiàn)的全部命題原子，并使用分配律張開，即，若是短語Gi’不是關(guān)于P1，，Pn的極小項(xiàng)，則Gi’中必然缺少原子，不如設(shè)為Pj1，，Pjk，于是Gi’=Gi’(Pj1Pj1)(PjkPjk)=mi1...mik2這樣，就將非極小項(xiàng)Gi’化成了一些極小項(xiàng)之析取。將同樣的短語的多次出現(xiàn)化為一次出現(xiàn)，就獲得了給定公式的主析取式。主合取式的求法近似，留給讀者作為練習(xí)。由上面談?wù)摽芍灰蟪鲆环N式，可馬上獲得別的一種式。例求公式G=P→(Q→R)的主析取式與主合取式。解：（1）使用真值表法。見表。PQRP→(Q→R)00010011010101111001101111001111表依照真值表中使得公式為真的講解，所對(duì)應(yīng)的極小項(xiàng)的析取即為其主析取式：G=(

P

QR)PQ

(R)

P

QR)

((

PQ

R)

(P

QR)

(P

QR)=m

(P0

QR)m1m2

m3

m4

m5

m7依照真值表中使得公式為假的講解，所對(duì)應(yīng)的極大項(xiàng)的合取即為其主合取式：G=PQR=M6（2）公式推導(dǎo)法G=P→(Q→R)=

P

QR=（

P（Q

Q）

（R

R））（Q（P

P）

（R

R））（R

（P

P）

（Q

Q））=(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)=m0m1m2m3m4m5m7G=P→(Q→R)=PQRM6主合取式與主析取式的應(yīng)用1）由可知，利用主合取式與主析取式可求解判斷問題。2）證明等價(jià)式成立。由于任意公式的主式是唯一的，所以能夠分別求出兩個(gè)給定的公式的主式，若二者主式相同，則給定的兩公式是等價(jià)的，否則，給定的兩公式不等價(jià)。求（

例判斷P→(Q→R)與（PQ）→R可否等價(jià)。證明：我們利用求主合取式的方法來判斷。由例知，P→(Q→R)的主合取式為：M6。下面PQ）→R的主合取式。（PQ）→R=（PQ）R=

（

P

Q）

R=

（PR）

（QR）=

（P（

Q

Q）

R）（（P

P）

QR）=（PQR）（PQR）（PQR）=M2M4M6二者的主合取式不同樣，所以，這兩個(gè)公式不等價(jià)。聯(lián)系詞的轉(zhuǎn)變和全功能集關(guān)于聯(lián)系詞的轉(zhuǎn)變和全功能集方面一般有以下題型：（1）要求只用幾個(gè)聯(lián)系詞表示某個(gè)命題公式，見例。2）給出一個(gè)新的聯(lián)系詞的定義，要求證明其是全功能集，并用其表示某個(gè)命題公式。這種題目的做法以下：由于不難證明出{，}，{，}，{，→}，{}，{}都是全功能聯(lián)系詞會(huì)集，所以，若要證明新定義的聯(lián)系詞是全功能集，只要證明上面某個(gè)全功能會(huì)集（比方{，}）中的每個(gè)聯(lián)系詞（如，和）都能夠用新聯(lián)系詞表示。若想用其表示某個(gè)命題公式，能夠先將基本聯(lián)系詞（，，）用給定的新聯(lián)系詞表示，爾后按要求把原命題公式轉(zhuǎn)變?yōu)橛眯侣?lián)系詞表示的形式。見例。3）證明一個(gè)聯(lián)系詞會(huì)集不是全功能集。一般用歸納法，證明在有限步，用這個(gè)聯(lián)系詞結(jié)合不能能表示全部的命題。見例。應(yīng)該說明的是，追求最少聯(lián)系詞的全功能聯(lián)系詞會(huì)集，主要不是個(gè)理論問題，而是為了滿足工程實(shí)踐的需要。但是，一般狀況下，為了不至于由于聯(lián)系詞的減少而使得公式的形式變得復(fù)雜，我們?nèi)猿２捎谩?，，，→，”這5個(gè)聯(lián)系詞。例將公式（P→（QR））（PQ）用僅含聯(lián)系詞和的公式等價(jià)表示。解：（P→（QR））（PQ）=（P（QR））（PQ）=（P（PQ））（（QR）（PQ））=（PQ）（Q（PQ））（R（PQ））=（PQ）（PQ）（（PQ）R）=PQ=（PQ）例定義三元聯(lián)系詞如表。e1e2e3f(e1,e2,e3)00010011010001101001101111011110表三元聯(lián)系詞f(e1,e2,e3)的真值表（1）試證明{f}是齊全的，即，聯(lián)系詞會(huì)集{，}或{，}可由該聯(lián)系詞表示。2）用該聯(lián)系詞表示公式：（P→R）Q。1）證明：由于所以聯(lián)系詞會(huì)集{而聯(lián)系詞會(huì)集

{

，}可由該三元聯(lián)系詞，}是齊全的，所以，

Q)f表示。{f}是齊全的。（2）解：由于PQ=f(P,P,Q)，所以P→Q=PQ=f(P,P,Q).又由PQ=

(

P=

Q)=(f(P,P,Q)=

Q

P)f(Q,Q,P).所以（P→R）Q=f(P,P,R)Q=f(Q,Q,f(P,P,R))=f(Q,Q,f(P,P,f(R,R,R)))=f(f(Q,Q,f(P,P,f(R,R,R))),P,f(R,R,R))),f(Q,Q,f(P,P,f(R,R,R))))

f(Q,。

Q,f(P,例2.2.12{，→}是否是聯(lián)系詞的全功能會(huì)集？證明你的結(jié)論。在證明此題從前，我們先直觀解析一下?？紤]和→這兩個(gè)聯(lián)系詞的特點(diǎn)：當(dāng)一個(gè)命題公式中只含有聯(lián)系詞和→時(shí)，則當(dāng)公式中出現(xiàn)的全部命題原子都取真值1時(shí)，公式也必然取真值

1。這就是說，僅含

和→的公式不能夠表示全部的命題公式，比方恒假式：

A

A。所以，聯(lián)系詞會(huì)集

{

，→}不是全功能集。證明：下面證明{，→}不是聯(lián)系詞的全功能集。對(duì)公式中出現(xiàn)的聯(lián)系詞個(gè)數(shù)使用數(shù)學(xué)歸納法來證明下面的結(jié)論：當(dāng)一個(gè)命題公式中只含有聯(lián)系詞和→時(shí)，則當(dāng)公式中出現(xiàn)的全部命題原子都取真值1時(shí)，公式也必然取真值1。n=0時(shí)，即公式中不含任何聯(lián)系詞時(shí)，公式為原子，結(jié)論顯然。假設(shè)n≤k時(shí)，命題成立，即，若是一個(gè)公式中含有n個(gè)聯(lián)系詞，→，則當(dāng)公式的全部原子真值取1時(shí)，公式也取真值1。當(dāng)n=k+1時(shí)，設(shè)任一含k+1個(gè)聯(lián)系詞的公式為A，則存在公式B和C，使得：A=B→C或

A=B

C，且B和

C中的聯(lián)系詞個(gè)數(shù)均≤

k。由歸納假設(shè)知，當(dāng)全部原子取真值1時(shí)，B和C在該講解下的真值均為1，所以，A在該講解下的真值亦為1。歸納完成。由該結(jié)論知，若是一個(gè)命題公式中只含有聯(lián)系詞和→，那么最少存在一個(gè)講解滿足該公式。所以，只含有聯(lián)系詞和→的公式必定不能夠表示恒假公式。所以，{，→}不是聯(lián)結(jié)詞的全功能集。綜合應(yīng)用題綜合題主若是先符號(hào)化，再使用上面的知識(shí)進(jìn)行聯(lián)系詞的轉(zhuǎn)變、或求主合取式、主析取式、利用基本等價(jià)式化簡(jiǎn)、或進(jìn)行邏輯推理來論證或做邏輯判斷等。例一個(gè)排隊(duì)線路，輸入為A，B，C，其輸出分別為FA,FB,FC。在同一時(shí)間只能有一個(gè)信號(hào)經(jīng)過。假好像時(shí)有兩個(gè)或兩個(gè)以上信號(hào)經(jīng)過時(shí)，則按A，B，C的序次輸出。比方，A，B，C同時(shí)輸入時(shí)，只能A有輸出。寫出FA,FB,FC的邏輯表達(dá)式，并化成全功能集{}中的表達(dá)式。解：先將已知事實(shí)中的各簡(jiǎn)單命題符號(hào)化，設(shè)：：A輸入；：B輸入；：C輸入。爾后依照已知條件，寫出FA,FB,FC的真值表如表。PQRFAFBFC000000001001010010011010100100101100110100111100表于是，(P

Q=

FA=(PR)(P（（P

QQR)Q）

（

R)R

(PR））

（（P

QR)Q（

RR））=

（P

Q）

（P

Q）=P

（QQ）=P=

(P

P)===(P

FB=(=(

(PP)((PP)P)PQPQ)

(P

(PP))P).R)(PQ（RR）

R)PQ=(=(P

PQ)Q)=P=PFC=

P

Q(Q

Q)QR==(P=(=(=((P

(PQR)Q)(R)(PQ))(PQ))Q)(P

(

(R)Q))

R)

(R

R)例一一個(gè)公安人員審查一件盜竊案，已知的事實(shí)以下：1）A或B盜竊了x2）若A盜竊了x，則作案時(shí)間不能夠發(fā)生在子夜前3）若B證詞正確，則在子夜時(shí)屋里燈光未滅4）若B證詞不正確，則作案時(shí)間發(fā)生在子夜前5）子夜時(shí)屋里燈光滅了6）A其實(shí)不豐饒?jiān)囉醚堇[法找出盜竊犯。解：先將已知事實(shí)中的各簡(jiǎn)單命題符號(hào)化，設(shè)：P：A盜竊了xQ：B盜竊了xR：作案時(shí)間發(fā)生在子夜前S：B證詞正確T：在子夜時(shí)屋里燈光未滅U：A其實(shí)不豐饒?jiān)賹⒏髑疤釋懗觯篏1：P∨QG2：P→RG3：S→TG4：：S→RG5：TG6：U演繹過程為：（1）S→T（規(guī)則１）（2）T（規(guī)則１）（3）S（規(guī)則2）（4）S→R（規(guī)則１）（5）R（規(guī)則2）（6）P→R（規(guī)則１）（7）P（規(guī)則2）（8）P∨Q（規(guī)則１）（9）Q（規(guī)則2）所以，是B盜竊了x。例一甲、乙、丙、丁四個(gè)人有且僅有兩個(gè)人參加圍棋優(yōu)勝比賽。關(guān)于誰參加比賽，下面四種判斷都是正確的：1）甲和乙只有一人參加；2）丙參加，丁必參加；3）乙或丁至多參加一人；4）丁不參加，甲也不會(huì)參加。請(qǐng)推斷出哪兩個(gè)人參加了圍棋比賽。解：先將已知事實(shí)中的各簡(jiǎn)單命題符號(hào)化，設(shè)：P：甲參加了比賽；Q：乙參加了比賽；R：丙參加了比賽；S：丁參加了比賽.依已知條件（1）--（4）有：（1）(PQ)(PQ)2）R→S3）（QS）4）S→P將（1）-（4）式合取起來有：（(PQ)(PQ)）（R→S）（QS）S→P）=（(Q

(PS)(S

Q)P)

(P

Q)）

（RS）=(P

Q

RS)

(P

QS)

(

PQR

S)依照已知，甲、乙、丙、丁四個(gè)人有且僅有兩個(gè)人參加比賽，知，

PQ

R

S為假，所以只有

(P

QRS)

(P

QS)

為真，即甲和丁參加了比賽?！?.3第二章習(xí)題解答習(xí)題2.1解答設(shè)P是命題“天下雪”；Q是命題“我上街”；R是命題“我有時(shí)間”。（1）用邏輯符號(hào)寫出以下命題：a．如天不下雪并且我有時(shí)間，那么我上街。b．我去上街，僅當(dāng)我有時(shí)間。c．天不下雪。d．天正在下雪，我也沒去上街。解：a可表示為：(PR)Q；b可表示為：QR；c可表示為：P；d可表示為：PQ。2）對(duì)下述命題用中文寫出語句。a．Q（RP）．RQ．（QR）（RQ）．（RQ）解：a為：我上街當(dāng)且僅當(dāng)我有時(shí)間并且天不下雪；為：我有時(shí)間并且上街了；為：我上街了當(dāng)且僅當(dāng)我有時(shí)間；為：我每時(shí)間又沒上街。說出下述每一命題的抗命題和逆否命題：（1）若是天下雨，我將不去。（2）僅當(dāng)你去我將逗留。（3）若是n是大于2的正整數(shù)，則方程xn+yn=zn無正整數(shù)解。（4）若是我不獲得更多幫助，我不能夠完成這個(gè)任務(wù)。解：（1）抗命題為：若是我不去，那么天下雨；逆否命題為：若是我去，那么天不下雨。（2）抗命題為：僅當(dāng)我將逗留你去；逆否命題為：你不去我將不斷留。（3）抗命題為：若是方程xn+yn=zn無正整數(shù)解，則n是大于2的正整數(shù)；逆否命題為：如nnn有正整數(shù)解，則n是不大于2的正整數(shù)。果方程x+y=z抗命題為：我不能夠完成這個(gè)任務(wù)，由于我沒有獲得更多幫助。逆否命題：若是我完成了任務(wù)，則我獲得了更多幫助。給P和Q指派真值1，給R和S指派真值0，求出下面命題的真值：a)(P(QR))((PQ)(RS))b)((PQ)R)(((PQ)R)S)c)((PQ)R)((QP)(RS))d)(P(Q(RP)))(QS)解：a)令G=(P(QR))((PQ)(RS))則：TI(G)=(1(10))((11)(00))=00=1b)令G=((PQ)R)(((PQ)R)S)則：TI(G)=((11)0)(((11)0)0)=10=1c)令G=((PQ)R)((QP)(RS))=((PQ)R)(((QP)(PQ))(RS))=(PQR)((QP)(PQ)(RS))則：TI(G)=(110)((11)(11)(00))=11=1d)令G=(P(Q(RP)))(QS)=(P(Q(RP)))(QS)=(P(Q(RP)))(QS)=((P(Q(RP)))(QS))((QS)(P(Q(RP))))=(P(Q(RP)))(QS))((QS)(P(Q(RP))))TI(G)=(1(1(01)))(10))((10)(1(1(01))))=11=1習(xí)題2.1解答組成以下公式的真值表：Q（PQ）P（PQR）（PQ）（PR）(3)(PQQR）PR(4)（（PPQ）R）QR解：（1）設(shè)G=Q（PQ）P，其真值表以下：PQG001010101111（2）設(shè)G=（PQR）（PQ）（PR），其真值表以下：PQRGPQRG00001001001010100100110101101110（3）設(shè)G=(PQQR)PR，其真值表以下：PQRGPQRG00001001001010110101110101101110（4）設(shè)G=（（PPQ）R）QR，其真值表以下：PQRGPQRG00011001001010100101110101111111指出以下公式哪些是恒真的哪些是恒假的：(1)P（PQ）Q（PQ）（PQ）(3)（PQ）（QR）（PR）(4)（PQ）（PQPQ）解：（1）是恒真的，（2）是恒真的，（3）是恒真的，（4）是可滿足的。3.對(duì)

P和

Q的全部值，證明

P

Q與

PQ有同樣的真值。證明（

P

Q）

（

PQ）是恒真的。解：對(duì)PQ的任意講解I，若I使PQ為真，則I使P為假或I使P為假，則使P，此時(shí)PQ為真，若I使P和Q同時(shí)為真，則為真，也就是說PQ為真時(shí)PQ為真。若I使PQ為假，則I時(shí)PQ為假，也就是說PQ為假時(shí)PQ為假。綜上知PQ與定義知（PQ）（PQ）是恒真的。

P和Q同時(shí)為真，若Q為真，此時(shí)PQ使P為真Q為假，此PQ同真同假，由判斷以下公式是恒真？恒假？可滿足？a)(P(QR))(P(QR))；b)P(P(QP))；c)(QP)(PQ)；d)(PQ)(PQ)。解：（1）設(shè)G=(P(QR))(P(QR))=(P(QR))(P(QR))=(((P(QR))P)((P(QR))QR)=((PP)(PQR))((P(QR))QR)=((PP)(PQR))((PQ)(PR)QR)=((PP)(PQR))(((PQ)Q)((PR)R))=(PQR)(PQR)，其真值表以下：PQRGPQRG00011000001010100100110001101111所以G是可滿足的。（2）設(shè)G=P(P(QP))=P(P(QP))PP=T其真值表以下：PQG001011101111G(3)G=(QP)=(QP)=(PQ)

(

(

PQ)PQ)(PQ)=F其真值表以下：PQG000010100110所以G是恒假的。(4)G=(PQ)(PQ)=(PQ)((PQ)(QP))=(PQ)((PQ)(QP))=(PQ)(PQ)(PQ)其真值表以下：PQG000011101111所以G是可滿足的。習(xí)題2.3解答證明下面的等價(jià)式：(1)(P(QR))(QR)(PR)=R(2)P(QP)=P(PQ)(3)P(QR)=(PQ)(PR)(4)(PQ)(RQ)=(PR)Q(1)證明：(P(QR))(QR)(PR)=(((P(QR))Q)((P(QR))=((((PQ)(RQ))((PR)R))=((PQ)(RQ)R)(PR)=((PQ)R)(PR)=(PR)(QR)(PR)=R(PP)(QR)=R得證。(2)證明：左邊=P(QP)=P(QP)=PQP=PPQ=T右邊=P(PQ)=PPQ=T

R))(P

R)

(P

R)可有：左邊=右邊，得證(3)證明：左邊=PQR右邊=PQPR=PQR可有：左邊=右邊，得證(4)證明：左邊=(PQ)(RQ)=(PR)Q=(PR)Q=(P

R)

Q=右邊得證2設(shè)

S={G1，，

Gn}

是命題公式會(huì)集。試求出在不增加新原子的狀況下從

S出發(fā)演繹出的全部命題公式。提示：考慮G1Gn的主合取式。解：任設(shè)一公式G’為從S出發(fā)演繹出來的公式。則可知G’為G=G1Gn的一個(gè)邏輯結(jié)果。而G有唯一一個(gè)與其等價(jià)的主合取式，設(shè)為G’’?？稍O(shè)G’’共有m個(gè)極大項(xiàng)，則能夠知道令G’’取1的講解使這m個(gè)極大項(xiàng)也取1。則從S出發(fā)的演繹出來的的全部命題公式正是從這m個(gè)極大項(xiàng)中任取n(0≤n≤m)個(gè)合取組m設(shè)H為由若干極大項(xiàng)組成的合取公式。現(xiàn)在證明：1)S=>H，即G=>H。從定義出發(fā)，設(shè)有一講解I使G=G1Gn取1值，必使G的主合取式也取1值。即使每一個(gè)極大項(xiàng)都取1值。從而使由若干極大項(xiàng)合取組成的公式H也取1值，則有S=>H。任意設(shè)公式H是S的一個(gè)邏輯結(jié)果，H是一些極大項(xiàng)的合取。現(xiàn)在要證組成H的極大項(xiàng)都在G的主合取式G”中。反證法：若否則，假設(shè)H中有一個(gè)極大項(xiàng)mk不在G的主合取式中。則取使mk為0的講解I，可有講解I使H取0值。而I使全部不等于mk的極大項(xiàng)都為1，則可有G的主合取式G’’在I下取1值，即G在I下取1值，這與G=>H矛盾。證明：兩個(gè)公式之間的蘊(yùn)涵關(guān)系擁有反身性，反對(duì)稱性和傳達(dá)性。證明：a)任意設(shè)一公式P,由于PP是恒真的，則有P=>P即蘊(yùn)涵關(guān)系有反身性。任取兩個(gè)命題公式P，Q若是P=>Q并且Q=>P，則有PQ恒真，QP恒真，則（PQ）那么有PQ恒真，得出P=Q，所以蘊(yùn)涵關(guān)系有反對(duì)稱性。c)任取命題公式P，Q，R若是P=>Q，Q=>R；關(guān)于P，Q，R的任意一個(gè)講解I。若是I滿足若I滿足Q則I滿足R。則有I滿足P時(shí)，也滿足R，故有P=>R。所以蘊(yùn)涵關(guān)系有傳達(dá)性。

（QP）恒真，P則I也滿足Q，證明：若前提會(huì)集S中的公式都是恒真的，G是從S出發(fā)的一個(gè)演繹的邏輯結(jié)果，則G必是恒真公式。證明：設(shè)S是由

G1，，Gn組成的，則

G1，，Gn是恒真的，那么

G1

Gn是恒真的，而由已知有：G1Gn=>G，所以由蘊(yùn)涵定義有G必為恒真公式。設(shè)G1，，Gn是公式。證明：從{G1，，Gn}出發(fā)可演繹出公式G的充要條件是從{G1，，Gn，G}出發(fā)可演繹出公式(RR)。其中R為任意公式。證明：充分性，即{G1，，G，G}=>(RR)，可有nGGnG=>(RR)，因(RR)恒假，則GGnG恒假。那么有11（GG）G恒真，即（GG）G恒真，則有(G1G)=>G，所以有1n1nn{G1，，Gn}蘊(yùn)涵G。必要性，即已知：{G，，G}=>G，有（GG）G恒真，即（G1n1n1Gn）G恒真，那么對(duì)上式取非有G1GnG恒假，也就是(G1GnG)(RR)恒真，其中R為任意一個(gè)公式，則有(G1GnG)=>(RR)，即從{G1，，Gn，G}出發(fā)可演繹出公式(RR)。命題得證。證明以下蘊(yùn)涵式：(1)(PQ)(PQ)證明：要證上式成馬上證則：(PQ)(PQ)=(PQ)(=(PQ)(=PQQ

(PQ)PQ)PQ)

(P

Q)恒真，=T即：(P

Q)(P

Q)恒真命題得證。

(或從PQ

Q，Q(P

Q))(2)P

(Q

P)證明：同

a)，P(Q

P)=P

(

QP)=P

P

Q=T命題得證。(或從P(3)(P(QR))(PQ)證明：(P(QR))=(PQR)

(

(P(P

QP)出發(fā))R)Q)(P(PQ

R)R)=T得證。(4)P

QP

(P

Q)證明:若P(PQ)為假，則PQ為假，

P為真。所以有

Q為假，則PQ為假，

(后件假推出前件假等價(jià)于前件真推出后件真

)得證。(5)(P

Q)QPQ證明：(PQ)Q=(PQ)Q=(PQ)Q=(PQ)(QQ)=>(PQ)(基本蘊(yùn)涵式)(6)((PP)Q)((PP)R)(QR)證明：若(QR)為假，則R為假，Q為真，則(PP)R為假，而(PP)Q為真，則有((PP)Q)((PP)R)為假，得證。（用PQ證明也可）(7)(Q(PP))(R(PP))(RQ)證明：若(RQ)為假，則Q為假，R為真，則R(PP)為假，而Q(PP)為真。有(Q(PP))(R(PP))為假，得證。7.證明{CD，(CD)H，H(AB)，(AB)(RS)}共同蘊(yùn)涵RS。證明：1)CD規(guī)則12)(CD)H規(guī)則13)H規(guī)則2，依照1),2)4)H(AB)規(guī)則15)(AB)規(guī)則2，依照3),4)6)(AB)(RS)規(guī)則17)RS規(guī)則2，依照5),6)8.證明{PQ，QR，PM，M}共同蘊(yùn)涵R(PQ)。證明：1)PM規(guī)則12)MP規(guī)則2，依照1)3)M規(guī)則14)P規(guī)則2，依照2),3)5)PQ規(guī)則16)PQ規(guī)則2，依照5)7)Q規(guī)則2，依照4),6)8)QR規(guī)則19)R規(guī)則2，依照7),8)10)R(PQ)規(guī)則2，依照5),9)9.證明{PQ，QR，RS}共同蘊(yùn)涵PS。證明：1)PQ規(guī)則12)P規(guī)則3（附加前提）3)Q規(guī)則2，依照1),2)4)QR規(guī)則15)R規(guī)則2，依照3),4)6)RS規(guī)則17)S規(guī)則2，依照5),6)8)PS規(guī)則3，依照2),7)習(xí)題2.4解答試證明公式：((PQ)(P(QR)))(PQ)(PR)是恒真公式。證明：原式=((PQ)(P(QR)))(PQ)(PR)=((PQ)(P(QR)))(PQ)(PR)=((PQ)(PQ)(PR))(PQ)(PR)=(P(QR))(P(QR))=T模擬主析取式的看法，引進(jìn)主合取式的看法。并證明：對(duì)任意命題公式，存在唯一一個(gè)與其等價(jià)的主合取式。第一引進(jìn)極大項(xiàng)看法：定義6：設(shè)P，，P是n個(gè)不同樣原子，一個(gè)子句若是恰好包含全部這n個(gè)原子或其否1n定，且其排列序次與P1，，Pn的序次