第1章-數(shù)理邏輯

第一章數(shù)理邏輯1.1命題1.2重言式1.3范式1.4聯(lián)結(jié)詞的擴(kuò)充與歸約1.5推理規(guī)則和證明方法1.6謂詞和量詞1.7謂詞演算的永真公式1.8謂詞演算的推理規(guī)則1.1命題1.1.1命題

斷言是一陳述語句。一個(gè)命題是一個(gè)或真或假而不

能兩者都是的斷言。如果命題是真,我們說它的真值為真如果命題是假,我們說它的真值是假。例1下述都是命題:;(a)今天下雪;;(b)3+3=6;;(c)2是偶數(shù)而3是奇數(shù);;(d)陳涉起義那天,杭州下雨;;(e)較大的偶數(shù)都可表為兩個(gè)質(zhì)數(shù)之和。;以上命題,(a)的真值取決于今天的天氣,(b)和(c)是真,(d)已無法查明它的真值,但它是或真或假的,將它歸屬于命題。(e)目前尚未確定其真假,但它是有真值的,應(yīng)歸屬于命題。

例2下述都不是命題:;(a)x+y＞4。 (c)真好啊!;(b)x=3。 (d)你去哪里?;(a)和(b)是斷言,但不是命題,因?yàn)樗恼嬷等Q于x和y的值。(c)和(d)都不是斷言,所以不是命題。

例3一個(gè)人說:“我正在說謊”。他是在說謊還是在說真話呢?如果他講真話,那么他所說的是真,也就是他在說謊。我們得出結(jié)論如果他講真話,那么他是在說謊。另一方面,如果他是說謊,那么他說的是假;因?yàn)樗姓J(rèn)他是說謊,所以他實(shí)際上是在說真話,我們得出結(jié)論如果他是說謊,那么他是講真話。從以上分析,我們得出他必須既非說謊也不是講真話。這樣,斷言“我正在說謊”事實(shí)上不能指定它的真假,所以不是命題。這種斷言叫悖論。若一個(gè)命題已不能分解成更簡單的命題,則這個(gè)命題叫原子命題或本原命題。例1中(a),(b),(d),(e)都是本原命題,但(c)不是,因?yàn)樗蓪懗伞?是偶數(shù)”和“3是奇數(shù)”兩個(gè)命題。命題和本原命題常用大寫字母P,Q,R:表示。如用P表示“4是質(zhì)數(shù)”,則記為;

P:4是質(zhì)數(shù)。1.1.2命題聯(lián)結(jié)詞命題和原子命題?？赏ㄟ^一些聯(lián)結(jié)詞構(gòu)成新命題,這種新命題叫復(fù)合命題。例如;

P:明天下雪,Q:明天下雨是兩個(gè)命題,利用聯(lián)結(jié)詞“不”,“并且”,“或”等可分別構(gòu)成新命題:;“明天不下雪”;;“明天下雪并且明天下雨”;;“明天下雪或者明天下雨”等。即;“非P”;;“P并且Q”;“P或Q”等。在代數(shù)式x+3中,x,3叫運(yùn)算對(duì)象,+叫運(yùn)算符,x+3表示運(yùn)算結(jié)果。在命題演算中,也用同樣術(shù)語。聯(lián)結(jié)詞就是命題演算中的運(yùn)算符,叫邏輯運(yùn)算符或叫邏輯聯(lián)結(jié)詞。常用的有以下5個(gè)。1.否定詞設(shè)P表示命題,那么“P不真”是另一命題,表示為P,叫做P的否定,讀做“非P”。從排中律知:如果P是假,則P是真,反之亦然。所以否定詞面具可以如右表所示定義。P

P假真真假這張表叫真值表,定義運(yùn)算符的真值表,指明如何用運(yùn)算對(duì)象的真值,來決定一個(gè)應(yīng)用運(yùn)算符的命題的真值。真值表的左邊列出運(yùn)算對(duì)象的真值的所有可能組合,結(jié)果命題的真值列在最右邊的一列。為了便于閱讀,我們通常用符號(hào)T(true)或1代表真,符號(hào)F(false)或0代表假。一般在公式中采用T和F,在真值表中采用1和0。這樣,以上真值表可寫成P

P0110例4(a)

P:4是質(zhì)數(shù)。

P:4不是質(zhì)數(shù)。或4是質(zhì)數(shù),不是這樣。(b)Q:這些都是男同學(xué)。

Q:這些不都是男同學(xué)。(翻譯成“這些都不是男同學(xué)”是錯(cuò)的。)2.合取詞∧;如果P和Q是命題,那么“P并且Q”也是一命題,記為P∧Q,稱為P和Q的合取,讀做“P與Q”或“P并且Q”。運(yùn)算符∧定義如下表所示:從真值表可知P∧Q是真當(dāng)且僅當(dāng)P和Q俱真。PQP∧Q000110110001例5

P:王華的成績很好,Q:王華的品德很好。P∧Q:王華的成績很好并且品德很好。3.析取詞∨如果P和Q是命題,則“P或Q”也是一命題,記作P∨Q,稱為P和Q的析取,崐讀做“P或Q”。運(yùn)算符∨定義如右表所示。從真值表可知P∨Q為真,當(dāng)且僅當(dāng)P或Q至少有一為真。PQP∨Q000110110111例6;(a)P:今晚我寫字,Q:今晚我看書。

P∨Q:今晚我寫字或看書“或”字常見的含義有兩種:一種是“可兼或”,如上例中的或,它不排除今晚既看書又寫字這種情況。一種是“排斥或”,例如“人固有一死,或重于泰山,或輕于鴻毛”中的“或”,它表示非此即彼,不可兼得。運(yùn)算符∨表示可兼或,排斥或以后用另一符號(hào)表達(dá)。(b)P:今年是閏年;Q:今年她生孩子。

P∨Q:今年是閏年或者今年她生孩子。4.蘊(yùn)涵詞→(涵常簡寫作含)如果P和Q是命題,那么“P蘊(yùn)含Q”也是命題,記為P→Q,稱為蘊(yùn)含式,讀做“P蘊(yùn)含Q”或“如果P,那么Q”。運(yùn)算對(duì)象P叫做前提,假設(shè)或前件,而Q叫做結(jié)論或后件。運(yùn)算符定義如右表所示。命題P→Q是假,當(dāng)且僅當(dāng)P是真而Q是假。PQP→Q000110111101例7

(a)P:天不下雨,Q:草木枯黃。P→Q:如果天不下雨,那么草木枯黃。(b)R:G是正方形,S:G的四邊相等。R→S:如果G是正方形,那么G的四邊相等。(c)W:桔子是紫色的,V:大地是不平的。W→V:如果桔子是紫色的,那么大地是不平的。在日常生活中用蘊(yùn)含式來斷言前提和結(jié)論之間的因果或?qū)嵸|(zhì)關(guān)系,如上例(a)和(b),這樣的蘊(yùn)含式叫形式蘊(yùn)含,然而,在命題演算中,一個(gè)蘊(yùn)含式的前提和結(jié)論并不需要有因果和實(shí)質(zhì)聯(lián)系,這樣的蘊(yùn)含式叫實(shí)質(zhì)蘊(yùn)含,如上例(c)中,桔子的顏色和大地的外形之間沒有因果和實(shí)質(zhì)關(guān)系存在,但蘊(yùn)含式W→V是真,因?yàn)榍疤崾羌俣Y(jié)論是真。采用實(shí)質(zhì)蘊(yùn)含作定義,是因?yàn)樵谟懻撨壿嫼蛿?shù)學(xué)問題中,這不僅是正確的,且方便應(yīng)用。蘊(yùn)含式P→Q可以用多種方式陳述:;“若P,則Q”“P是Q的充分條件”“Q是P的必要條件”“Q每當(dāng)P”;“P僅當(dāng)Q”等。如上例(b)中的R→S可陳述為“G是正方形的必要條件是它的四邊相等”。給定命題P→Q,我們把Q→P,

P→

Q,Q→P分別叫做命題P→Q的逆命題,反命題和逆反命題.

5.等值詞如果P和Q是命題,那么“P等值于Q”也是命題,記為PQ,稱為等值式,讀做“P等值于Q”。運(yùn)算符定義如右表所示。把蘊(yùn)含式和等值式的真值表加以比較,易知如果PQ是真,那么P→Q和Q→P俱真;反之如果P→Q和Q→P俱真,那么PQ是真。由于這些理由,PQ也讀做“P*是Q的充要條件”或“P當(dāng)且僅當(dāng)Q”。PQP

Q000110111001從以上5個(gè)定義可看出,聯(lián)結(jié)詞之意義由其真值表唯一確定,而不由命題的含義確定。使用以上5個(gè)聯(lián)結(jié)詞,可將一些語句翻譯成邏輯式。翻譯時(shí)為了減少圓括號(hào)(一般不用其它括號(hào))的使用,我們作以下約定:;·運(yùn)算符結(jié)合力的強(qiáng)弱順序?yàn)?、∧,∨,→,凡符合此順序的,括號(hào)均可省去?！は嗤倪\(yùn)算符,按從左至右次序計(jì)算時(shí),括號(hào)可省去?！ぷ钔鈱拥膱A括號(hào)可以省去。例如:(((P∧Q)∨R)→((R∨P)∨Q))可寫成;(P∧Q∨R)→R∨P∨Q

但有時(shí)為了看起來清楚醒目,也可以保留某些原可省去的括號(hào)。例8(a)設(shè)P表示“他有理論知識(shí)”,Q表示“他有實(shí)踐經(jīng)驗(yàn)”,則“他既有理論知識(shí)又有實(shí)踐經(jīng)驗(yàn)”可譯為:P∧Q。(b)設(shè)P:明天下雨,Q:明天下雪,R:我去學(xué)校。則(i)“如果明天不是雨夾雪則我去學(xué)?！笨蓪懗?(P∧Q)→R;(ii)“如果明天不下雨并且不下雪則我去學(xué)校”可寫成;

P∧Q→R;(iii)“如果明天下雨或下雪則我不去學(xué)?！笨蓪懗?

P∨Q→R;(iv)“明天,我將雨雪無阻一定去學(xué)?！笨蓪懗?

P∧Q∧R∨P∧Q∧R∨P∧Q∧R∨P∧Q∧R(v)“當(dāng)且僅當(dāng)明天不下雪并且不下雨時(shí)我才去學(xué)校”可寫成;

P∧Q

R;(c)用邏輯符表達(dá)“說小學(xué)生編不了程序,或說小學(xué)生用不了個(gè)人計(jì)算機(jī),那是不對(duì)的”。設(shè)P:小學(xué)生會(huì)編程序,Q:小學(xué)生會(huì)用個(gè)人計(jì)算機(jī)。則上句可譯為(P∨Q)(d)用邏輯符表達(dá)“若不是他生病或出差了,我是不會(huì)同意他不參加學(xué)習(xí)”。設(shè)P:他生病了,Q:他出差了,R:我同意他不參加學(xué)習(xí),則上句可譯為 (P∨Q)R或P∨QR

翻譯時(shí)要按邏輯關(guān)系翻譯,而不能憑字面翻。例如,設(shè)P:林芬做作業(yè),

Q:林芳做作業(yè),則“林芬和林芳同在做作業(yè)”可譯為P∧Q,但“林芬和林芳是姐妹”就不能翻釋成兩個(gè)命題的合取,它是一個(gè)原子命題。1.1.3命題變?cè)兔}公式通常,如果P代表真值未指定的任意命題,我們就稱P為命題變?cè)?如果P代表一個(gè)真值已指定的命題,我們就稱P為命題常元。但由于在命題演算中并不關(guān)心具體命題的涵義,只關(guān)心其真假值。因此,我們可以形式地定義它們。以“真”,“假”為其變域的變?cè)?稱為命題變?cè)?T和F稱為命題常元。單個(gè)命題變?cè)兔}常元叫原子公式。由以下形成規(guī)則生成的公式叫命題公式

(簡稱公式):;(1)單個(gè)原子公式是命題公式。(2)如果A和B是命題公式,則(A),(A∧B),(A∨B),(A→B),(A

B)是命題公式。

(3)只有有限步應(yīng)用條款(1)和(2)生成的公式才是命題公式。這種定義叫歸納定義,也叫遞歸定義。由這種定義產(chǎn)生的公式叫合式公式。例9(a)說明(P→(P∨Q))是命題公式。;解

(i)P是命題公式 根據(jù)條款(1)(ii)Q是命題公式 根據(jù)條款(1)(iii)(P∨Q)是命題公式 根據(jù)(i)(ii)和條款(2)(iv)(P→(P∨Q))是命題公式 根據(jù)(i)(iii)和條款(2)(b)以下不是命題公式,因?yàn)樗鼈儾荒苡尚纬梢?guī)則得出?！腝,(P→Q,P→∧Q,((PQ)∧R)

為了減少圓括號(hào)的使用,以后手寫命題公式時(shí),可按過去的約定省略。例10

(a)((P∨Q)∧P)的真值表如下所示:(b)兩個(gè)命題公式,如果有相同的真值,則稱它們是邏輯等價(jià)命題證明P

Q與P∧Q∨P∧Q是邏輯等價(jià)命題。證用真值表因后兩列的真假值完全一致,所以它們是邏輯等價(jià)命題。1.2重言式1.2.1重言式對(duì)有n個(gè)命題變?cè)拿}公式A(P1,P2,…,Pn),命題變?cè)恼嬷涤?n種不同的組合。每一種組合叫做一種指派,一共有2n種指派,這就是說真值表有2n行。對(duì)應(yīng)于每一指派,命題公式得到一確定的值,即命題公式成為具有真假值的命題,于是可能出現(xiàn)以下情況:(1)對(duì)應(yīng)于所有指派,命題公式均取值真。這種命題公式叫重言式,或叫永真式。例如P∨P。(2)對(duì)應(yīng)于所有指派,命題公式均取值假。這種命題公式叫矛盾式,或叫永假式。假如P∧P。(3)不是永真式,也不是永假式,這種命題公式叫偶然式。一個(gè)公式如果至少存在一個(gè)指派,使其值為真,則稱此公式為可滿足的;一個(gè)公式如果至少存在一個(gè)指派,使其值為假,則稱此公式為非永真。我們著重研究重言式,它最有用,因?yàn)樗幸韵绿攸c(diǎn):(1)重言式的否定是矛盾式,矛盾式的否定是重言式,所以研究其一就可以了。(2)重言式的合取,析取,蘊(yùn)含,等值等都是重言式。這樣,由簡單的重言式可推出復(fù)雜的重言式。(3)重言式中有許多非常有用的恒等式和永真蘊(yùn)含式。1.2.2恒等式設(shè)A:A(P1,P2,…,Pn),B:B(P1,P2,…,Pn)是兩個(gè)命題公式,這里Pi(i=1,2,…,n)不一定在兩公式中同時(shí)出現(xiàn)。如果AB是重言式,則A與B對(duì)任何指派都有相同的真值。記為AB,叫做邏輯恒等式,讀做“A恒等于B”。

容易看出,AB不過是上節(jié)的“A和B邏輯等價(jià)”的另一種描述方式而已。所以,AB也讀做“A等價(jià)于B”。請(qǐng)注意符號(hào)與符號(hào)意義不同。是邏輯聯(lián)結(jié)詞,而是表示A和B有邏輯等價(jià)這個(gè)關(guān)系的符號(hào),它的作用相當(dāng)于代數(shù)中的“=”。表1.2-1邏輯恒等式表1.2-1邏輯恒等式1.2.3永真蘊(yùn)含式如果A→B是一永真式,那么稱為永真蘊(yùn)含式,記為AB,讀做“A永真蘊(yùn)含B”。永真蘊(yùn)含式也可用真值表證明，但也可用以下辦法證明:(1)假定前件是真,若能推出后件是真,則此蘊(yùn)含式是真。(2)假定后件是假,若能推出前件是假,則此蘊(yùn)含式是真。表1.2–2永真蘊(yùn)含式例1證明Q∧(P→Q)P

方法1:設(shè)Q∧(P→Q)是真,則Q,P→Q是真。所以,Q是假,

P是假。因而

P是真。故Q∧(P→Q)P

方法2:設(shè)P是假,則P是真。以下分情況討論。(i)若Q為真,則Q是假,所以Q∧(P→Q)是假。(ii)若Q是假,則P→Q是假,所以Q∧(P→Q)是假。故

Q∧(P→Q)P。1.2.4恒等式和永真蘊(yùn)含式的兩個(gè)性質(zhì)

1.若AB,BC

則AC;若AB,BC則AC。;

這一性質(zhì)也可敘述為:邏輯恒等和永真蘊(yùn)含都是傳遞的。前者留給讀者自證,現(xiàn)證明后者。;

證A→B永真;

B→C永真,所以;(A→B)∧(B→C)永真。由公式I6得A→C永真,既AC。;2.若AB,AC,則AB∧C。;

證

A是真時(shí),B和C都真,所以B∧C也真。因此A→B∧C永真,則AB∧C。1.2.5代入規(guī)則和替換規(guī)則1.代入規(guī)則(RuleofSubstitution)

一重言式中某個(gè)命題變?cè)霈F(xiàn)的每一處均代入以同一公式后,所得的仍是重言式。這條規(guī)則之所以正確是由于重言式之值不依賴于變?cè)闹档木壒省＠?/p>

P∧P

F,今以R∧Q代P得(R∧Q)∧(R∧Q)F,仍正確。它的思想就如同在代數(shù)中,若

x

2-y2=(x+y)(x-y)則(a+b)2-(mn)2=(a+b+mn)(a+b-mn)一樣。代入后所得公式稱為原公式的代入實(shí)例。對(duì)非重言式通常不作代入運(yùn)算,特別是偶然,因所得代入實(shí)例的性質(zhì)不確定,沒有用處。例如:B:P→Q原是偶然,若用R∨R代換B中之Q,得

A:P→(R∨R)卻是重言式。

2.替換規(guī)則(RuleofReplacement)

設(shè)有恒等式AB,若在公式C中出現(xiàn)A的地方,替換以B(不必每一處)而得到公式D,則CD。;

如果A是合式公式C中完整的一部分,且A本身是合式公式,則稱A是C的子公式,規(guī)則中“公式C中出現(xiàn)A”意指“A是C的子公式”。這條規(guī)則的正確性是由于在公式C和D中,除替換部分外均相同,但對(duì)任一指派,A和B的真值相同,所以C和D的真崐值也相同,故C

D。

應(yīng)用這兩條規(guī)則和已有的重言式可以得出新的重言式。例如,對(duì)公式E4:P∨Q

Q∨P,我們以A∧B代P,A∧B代Q,就得出公式A∧B∨A∧B

A∧B∨A∧B

以A代P,A∧B∨C代Q,得就出公式A∨(A∧B∨C)(A∧B∨C)∨A

……

對(duì)公式E19:

P∧T

P,我們利用公式P∨PT,對(duì)其中的T作替換(注意不是代入,對(duì)命題常元不能代入)得公式P∧(P∨P)P

……例2證明P∧Q∨Q

P∨Q

證P∧Q∨Q

Q∨P∧Q E4

(Q∨P)∧(Q∨Q) E9(Q∨P)∧T E20和替換規(guī)則

Q∨P E19

P∨Q E4

(b)證明(P→Q)→(Q∨R)P∨Q∨R證

(P→Q)→(Q∨R)(P∨Q)→(Q∨R) E14和替換規(guī)則(P∨Q)∨(Q∨R) E14

P∧Q∨(Q∨R) E10、E1和替換規(guī)則(P∧Q∨Q)∨R) E6

P∨Q∨R

例2(a)和替換規(guī)則(P→Q)(P∨Q) E14和替換規(guī)則

P∧Q E10

P∧Q E1

和替換規(guī)則

Q∧P E5化簡后的語句是“我去了,而他不來”。(c)試將語句“情況并非如此:如果他不來,那么我也不去。”化簡。

解設(shè)P:他來,Q:我去,則上述語句可翻譯為(P→Q)。簡化此公式(d)找出P→(PQ)∨R的僅含∧和兩種聯(lián)結(jié)詞的等價(jià)表達(dá)式。解

P→(P

Q)∨R

P→(P→Q)∧(Q→P)∨R E15和替換規(guī)則

P∨(P∨Q)∧(Q∨P)∨R E14和替換規(guī)則(P∨P∨Q)∧(P∨Q∨P)∨RE9和替換規(guī)則(P∨Q)∧(T∨Q)∨R

E2,E20和替換規(guī)則(P∨Q)∧T∨R E16和替換規(guī)則

P∨Q∨R E19和替換規(guī)則(P∧Q∧R)

E1,E11所以,(P∧Q∧R)是所求表達(dá)式。1.2.6對(duì)偶原理定義1.2-1設(shè)有公式A,其中僅有聯(lián)結(jié)詞∧,∨,。在A中將∧,∨,T,F分別換以∨,∧,F,T得公式A*,則A*稱為A的對(duì)偶公式。對(duì)A*采取同樣手續(xù),又得A,所以A也是A*的對(duì)偶。因此,對(duì)偶是相互的。例3

(a)

P∨(Q∧R)和P∧(Q∨R)互為對(duì)偶。

(b)P∨F

和P∧T互為對(duì)偶。定理1.2-1設(shè)A和A*是對(duì)偶式。P

1,P2,…,Pn是出現(xiàn)于A和A*中的所有命題變?cè)?于是A(P1,P2,…,Pn)A*(P1,P2,…,Pn)如在例3(a)中,A(P,Q,R)P∨Q∧R

A(P,Q,R)(P∨Q∧R)(P)∧(Q∧R)(P)∧(Q∨R)A*(P,Q,R)P∧(Q∨R)A*(P,Q,R)(P)∧(Q∨R)所以,A(P,Q,R)A

*(P,Q,R)。定理1.2–2若AB,且A,B為命題變?cè)狿1,P2,…..,Pn及聯(lián)結(jié)詞∧,∨,構(gòu)成的公式,則A*

B*。

證

AB意味著A(P1,P2,…,Pn)B(P1,P2,…,Pn)永真所以A(P1,P2,…,Pn)B(P1,P2,…,Pn)永真由定理1.2-1得A*(P1,P2,…,

Pn)B*(P1,P2,…,

Pn)永真因?yàn)樯鲜绞怯勒媸?可以使用代入規(guī)則,以Pi代Pi,1≤i≤n,得A*(P1,P2,…,Pn)B*(

P1,P2,…,

Pn)永真所以,A*

B*。證畢。本定理常稱為對(duì)偶原理。

例4若(P∧Q)∨(P∨(P∨Q))P∨Q,則由對(duì)偶原理得(P∨Q)∧(P∧(P∧Q))P∧Q

定理1.2-3如果AB,且A,B為命題變?cè)狿1,P2,…,Pn及聯(lián)結(jié)詞∧,∨,構(gòu)成的公式,則B*A*。

證

A

B意味著

A(P1,P2,…,Pn)→B(P1,P2,….,Pn)永真,

B(P1,P2,…,Pn)→A

(P1,P2,…,Pn)永真。由定理1.2-1得

B*(P1,P2,…,Pn)→A*(P1,P2,…,Pn)永真因?yàn)樯鲜绞怯勒媸?可以使用代入規(guī)則,以Pi代Pi,1≤i≤n,得

B*

A*。

證畢。1.3范式1.3.1析取范式和合取范式為敘述方便,我們把合取式稱呼為積,析取式稱呼為和。;定義1.3-1命題公式中的一些命題變?cè)鸵恍┟}變?cè)姆穸ㄖe,稱為基本積;一些命題變?cè)鸵恍┟}變?cè)姆穸ㄖ?稱為基本和。例如,給定命題變?cè)狿和Q,則P,P∧Q,P∧Q,P∧P,

Q∧P∧Q等都是基本積,Q,Q∨P,P∨Q,P∨P,P∨Q∨Q等都是基本和。

基本積(和)中的子公式稱為此基本積(和)的因子。

定理1.3-1一個(gè)基本積是永假式,當(dāng)且僅當(dāng)它含有P,P形式的兩個(gè)因子。

證

充分性

P∧P是永假式,而Q∧F

F,所以含有P和P形式的兩個(gè)因子時(shí),此基本積是永假式。

必要性用反證法。設(shè)基本積永假但不含P和P形式的兩個(gè)因子,則給這個(gè)基本積中不帶否定符的命題變?cè)概烧嬷礣,帶有否定符的命題變?cè)概烧嬷礔,得基本積的真值是T,但這與假設(shè)矛盾。證畢。定義1.3-2一個(gè)由基本積之和組成的公式,如果與給定的命題公式A等價(jià),則稱它是A的析取范式,記為A

A1∨A2∨…∨An,n≥1這里A1,A2,…,An是基本積。任何一個(gè)命題公式都可求得它的析取范式,這是因?yàn)槊}公式中出現(xiàn)的→和可用∧,∨和表達(dá),括號(hào)可通過德·摩根定律和∧在∨上的分配律消去。但一個(gè)命題公式的析取范式不是唯一的,我們把其中運(yùn)算符最少的稱為最簡析取范式。

如果給定的公式的析取范式中每個(gè)基本積都是永假式,則該式也必定是永假式。例1

(a)求P∧(P→Q)的析取范式。解P∧(P→Q)P∧(P∨Q)

P∧P∨P∧Q

P∧(P→Q)不是永假式,因?yàn)槠湮鋈》妒街?后一個(gè)基本積非永假。如果需要求出最簡的析取范式,那么(1)式還可化簡成

P∧(P→Q)F∨P∧Q

P∧Q

P∧Q是P∧(P→Q)的最簡析取范式。(b)

求(P∨Q)(P∧Q)的最簡析取范式。解(P∨Q)(P∧Q)((P∨Q)∧(P∧Q))∨((P∨Q)∧(P∧Q))(P∧Q∧P∧Q)∨((P∨Q)∧(P∨Q))

Q∧P∨P∧Q

定義1.3-3一個(gè)由基本和之積組成的公式,如果與給定的命題公式A等價(jià),則稱它是A的合取范式,記為A

A1∧A2∧…∧An,n≥1這里A1,A2,…,An是基本和。任何一個(gè)命題公式都可求得它的合取范式,這是因?yàn)槊}公式中出現(xiàn)的→和可用∧,∨和表達(dá),否定號(hào)可通過德·摩根定律深入到變?cè)?再利用∨在∧上的分配律可化成合取范式。一個(gè)公式的合取范式也不是唯一的,其中運(yùn)算符最少的稱為最簡合取范式,也可利用卡諾圖等方法求得最簡合取范式。

如果給定的公式的合取范式中每個(gè)基本和都是永真式,則該式也必定是永真式。例2(a)證明Q∨P∧Q∨P∧Q是永真式。解Q∨P∧Q∨P∧Q

Q∨(P∨P)∧Q(Q∨P∨P)∧(Q∨Q)

在Q∨P∧Q∨P∧Q的合取范式中,每一個(gè)基本和都是永真式,所以它是永真式。(b)求(P∨Q)(P∧Q)的最簡合取范式。

解記A(P∨Q)(P∧Q),則

A((P∨Q)(P∧Q)

((P∨Q)∧P∧Q∨(P∨Q)∧(P∧Q))((P∨Q)∧(P∧Q))

P∧Q∨P∧Q

所以,A(P∨Q)∧(P∨Q)。1.3.2主析取范式和主合取范式定義1.3-4在n個(gè)變?cè)幕痉e中,若每一個(gè)變?cè)c其否定不同時(shí)存在,而兩者之一必出現(xiàn)一次且僅出現(xiàn)一次,則這種基本積叫極小項(xiàng)。

n個(gè)變?cè)蓸?gòu)成2n個(gè)不同的極小項(xiàng)。例如3個(gè)變?cè)狿,Q,R可構(gòu)造8個(gè)極小項(xiàng)。我們把命題變?cè)闯?,命題變?cè)姆穸闯?,那么每一極小項(xiàng)對(duì)應(yīng)一個(gè)二進(jìn)制數(shù),因而也對(duì)應(yīng)一個(gè)十進(jìn)制數(shù)。對(duì)應(yīng)情況如下:

P∧Q∧R

——000——0P∧Q∧R ——001——1P∧Q∧R ——010——2P∧Q∧R ——011——3P∧Q∧R ——100——4P∧Q∧R ——101——5P∧Q∧R ——110——6P∧Q∧R —111—7我們把對(duì)應(yīng)的十進(jìn)制數(shù)當(dāng)作足標(biāo),用mi表示這一項(xiàng),即;m0

P∧Q∧R

m1

P∧Q∧Rm2

P∧Q∧

R m3

P∧Q∧Rm4

P∧Q∧R m5

P∧Q∧Rm6

P∧Q∧R m7

P∧Q∧R一般地,n個(gè)變?cè)臉O小項(xiàng)是:m0

P1∧P2∧P3…∧

Pnm1

P1∧P2∧P3…∧Pn……m2n-1

P1∧P2∧P3…∧Pn

定義1.3-5一個(gè)由極小項(xiàng)之和組成的公式,如果與給定的命題公式A等價(jià),則稱它是A的主析取范式。任何一個(gè)命題公式都可求得它的主析取范式,這是因?yàn)槿魏我粋€(gè)命題公式都可求得它的析取范式,而析取范式可化為主析取范式。例如A

P∧Q∨R

P∧Q∧(R∨

R)∨(P∨

P)∧(Q∨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∨P∧Q∧

R∨P∧Q∧R

m1∨m3∨m5∨m6∨m7Σ(1,3,5,6,7)前邊講過每一極小項(xiàng)和它的足標(biāo)的二進(jìn)制數(shù)一一對(duì)應(yīng),因而和一種指派一一對(duì)應(yīng),例如三個(gè)變?cè)獣r(shí),極小項(xiàng)足標(biāo)指派

P∧Q∧R——101——1,0,1當(dāng)且權(quán)當(dāng)將對(duì)應(yīng)的指派代入該極小項(xiàng),該極小項(xiàng)的值才為1。因此,在命題公式的主析取范式中,諸極小項(xiàng)都與真值表中相應(yīng)指派處的該公式的真值1相對(duì)應(yīng),反之亦然。例3證明

P∨Q和P→((P→Q)∧(Q∨P))二式邏輯等價(jià)。

證

P∨Q

P∧(Q∨Q)∨Q∧(P∨P)

P∧Q∨P∧Q∨P∧Q

P→((P→Q)∧(Q∨P))

P∨((P∨Q)∧(Q∧P))

P∨(P∧Q∧P)∨(Q∧Q∧P)

P∨P∧Q

P∧(Q∨Q)∨P∧Q

P∧Q∨P∧Q∨P∧Q所以,二式邏輯等價(jià)。定義1.3-6

在n個(gè)變?cè)幕竞椭?若每一個(gè)變?cè)c其否定不同時(shí)存在,而二者之一必出現(xiàn)一次且僅出現(xiàn)一次,則這種基本和叫極大項(xiàng)。

n個(gè)變?cè)蓸?gòu)成2n個(gè)不同的極大項(xiàng)。類似于(但不同)極小項(xiàng)的記法,它們是:

M0

P1∨P2∨…∨Pn

M

1

P1∨P2∨…∨

Pn

M

2

P1∨P2∨…∨

Pn-1∨Pn

…

M2n-1

P1∨P2∨…∨Pn這里是將命題變?cè)獙?duì)應(yīng)于0,命題變?cè)姆穸▽?duì)應(yīng)于1,恰與極小項(xiàng)記法相反,例如3個(gè)變?cè)臉O大項(xiàng)是這樣對(duì)應(yīng)的極大項(xiàng)足標(biāo)指派

P∨Q∨R——010——0,1,0其目的是當(dāng)且僅當(dāng)將極大項(xiàng)的對(duì)應(yīng)指派代入該極大項(xiàng),才使該極大項(xiàng)的真值為0,使今后許多運(yùn)算得到方便。

定義1.3-7一個(gè)由極大項(xiàng)之積組成的公式,如果與給定的命題公式A等價(jià),則稱它是A的主合取范式。任何一個(gè)命題公式都可求得它的主合取范式,這是因?yàn)槿魏我粋€(gè)命題公式都可求得它的合取范式,而合取范式可化為主合取范式。例如

A

P∧Q∨R(P∨R)∧(Q∨R)(P∨R∨Q∧Q)∧(Q∨R∨P∧P)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

M0∧M2∧M4

π(0,2,4)一個(gè)命題公式的真值表是唯一的,因此一個(gè)命題公式的主合取范式也是唯一的。兩個(gè)命題公式如果有相同的主合取范式,那么兩個(gè)命題公式是邏輯等價(jià)的。一個(gè)命題公式的主析取范式和主合取范式緊密相關(guān),在它們的簡記式中,代表極小項(xiàng)和極大項(xiàng)的足標(biāo)是互補(bǔ)的,即兩者一起構(gòu)成0,1,2,…,2n-1諸數(shù),例如

AP∧Q∨R

Σ(1,3,5,6,7)=則 A

P∧Q∨R

π(0,2,4)下面列出極小項(xiàng)和極大項(xiàng)性質(zhì)(1)mi∧mj

F,(i≠j)(2)Mi∨M

j

T,(i≠j)(3)(4)(5)mi

Mi;(6)Mi

mi

1.3.3主析取范式的個(gè)數(shù)當(dāng)n=1時(shí),極小項(xiàng)有21=2個(gè),即P,P。主析取范式有:沒有極小項(xiàng)全部極小項(xiàng)當(dāng)n=2時(shí),極小項(xiàng)有22=4個(gè),即P∧Q,P∧Q,P∧Q,P∧Q。主析取范式有共222=16個(gè)。以此類推,n個(gè)命題變?cè)?可構(gòu)造22n個(gè)不同的主析取范式(包括F)。這個(gè)數(shù)字增長非常快,如n=3時(shí)223=256,n=4時(shí)224=65536。

主合取范式和主析取范式是一一對(duì)應(yīng)的,因此,n個(gè)命題變?cè)?也可構(gòu)造22n個(gè)不同的主合取范式(包括T)。1.4聯(lián)結(jié)詞的擴(kuò)充與歸約1.4.1聯(lián)結(jié)詞的擴(kuò)充1.一元運(yùn)算Pf1

f2

f3f

40100110101永假恒等否定期永真2.二元運(yùn)算除f5,f6,f

7,f8,f

13,f

14,f15已定義,f

1,f10,f

11,f

16作為運(yùn)算意義不大,只需再定義以下4個(gè):

f

12與非:P↑Q(P∧Q)

f2或非:P↓Q(P∨Q)

f9排斥或(異或):P⊕Q(P

Q)P∧Q∨P∧Q

f

3,f

4蘊(yùn)含否定:P→Q(P→Q)

1.4.2聯(lián)結(jié)詞的歸約9個(gè)聯(lián)結(jié)詞是否都必要?顯然不是的,只用∧,∨,三個(gè)聯(lián)結(jié)詞構(gòu)造的式子,就足以把一切命題公式等價(jià)地表示出來。根據(jù)德·摩根定律:(P∧Q)P∨Q,(P∨Q)P∧Q,所以,∧和∨中去掉一個(gè)也足以把一切命題公式等價(jià)地表示出來。

定義1.4-1一個(gè)聯(lián)結(jié)詞集合,用其中聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價(jià)地表達(dá)出來,則這個(gè)聯(lián)結(jié)詞集合稱為全功能的。由以上討論,易知包含∧,∨,的任一聯(lián)結(jié)詞集合都是全功能的。{∧,},{∨,}是全功能聯(lián)結(jié)詞集合。值得注意的是,{↑},{↓}也是全功能集合。容易證明{→,},{→,},{→,F},{→,T}也是全功能集合。但{∧,∨,→,}及其子集都不是全功能聯(lián)結(jié)詞集合,{},{,},{⊕,}等也不是全功能聯(lián)結(jié)詞集合。下面扼要說明為什么不是全功能的聯(lián)結(jié)詞集合。;(1){∧,∨},因?yàn)閷?duì)命題P進(jìn)行∧和∨運(yùn)算,不管怎樣組合和反復(fù),總不能得到P。(2){},因?yàn)槭且辉\(yùn)算,表達(dá)不了二元運(yùn)算。(3){,},證明如下:

證設(shè)f(P,Q)表示僅用命題變?cè)狿和Q及聯(lián)結(jié)詞,構(gòu)成的任意的命題公式。現(xiàn)證明對(duì)P,Q的4種指派,f(P,Q)的真值只能是下表中的8種結(jié)果之一:①在未運(yùn)算前,P和Q的值是屬于表中結(jié)果3和4,即屬于8種之一。②以上8種結(jié)果任兩種(包括自己對(duì)自己)經(jīng)運(yùn)算,仍得以上8種結(jié)果之一。③以上8種結(jié)果,任一種經(jīng)運(yùn)算,仍得以上8種結(jié)果之一。所以,對(duì)P,Q的4種指派,經(jīng)反復(fù)用和運(yùn)算,只能得出以上8種結(jié)果之一,即f(P,Q)的真值只能是表中8種結(jié)果之一。但以上8種結(jié)果都是偶數(shù)個(gè)1,而P∨Q是3個(gè)1,所以不能用f(P,Q)表達(dá)P∨Q,故{,}不是全功能集合。一般地說,要證明聯(lián)結(jié)詞集合A是不是全功能的,只需選一個(gè)全功能聯(lián)結(jié)詞集合B,一般選{∨,}或{∧,},若B中每一聯(lián)結(jié)詞都能用A中的聯(lián)結(jié)詞表達(dá),則A是全功能的,否則A不是全功能的。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

P∧Q∧RP∧Q∨R(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)(P∨Q∨R)(P∨Q∨R)(P∨Q∨R)*1.4.3其它主范式前邊介紹了主析取范式和主合取范式,聯(lián)結(jié)詞擴(kuò)充后,也可由極小項(xiàng)和聯(lián)結(jié)詞⊕構(gòu)成主異或范式,由極大項(xiàng)和聯(lián)結(jié)詞構(gòu)成主等值范式。例如因?yàn)閷?duì)任一指數(shù),任兩個(gè)不同的極小項(xiàng)mi和mj不可能同時(shí)為真,因此mi∨mj與mi⊕mj是等價(jià)的,故由主析取范式可轉(zhuǎn)寫成主異或范式。類似地,任兩個(gè)不同的極大項(xiàng)Mi和Mj不可能同時(shí)為假,因此Mi∧Mj和Mi

Mj是等價(jià)的,故主合取范式可轉(zhuǎn)寫成主等值范式。主異或范式和主等值范式也是唯一的。1.5推理規(guī)則和證明方法1.5.1推理規(guī)則像前幾節(jié)那樣確定命題演算,本質(zhì)上和簡單的開關(guān)代數(shù)一樣,簡單的開關(guān)代數(shù)是命題演算的一種應(yīng)用?，F(xiàn)在,我們從另一角度研究命題演算,即從邏輯推理角度來理解命題演算。先考察4個(gè)推理的例子,在每一例子中,橫線上的是前提,橫線下的是結(jié)論。右側(cè)是例子的邏輯符表示。設(shè)x屬于實(shí)數(shù),P:x是偶數(shù),Q:x2是偶數(shù)。例1如果x是偶數(shù),則x2是偶數(shù)。x是偶數(shù)。x2是偶數(shù)。前提結(jié)論∴QP→Q

P例2如果x是偶數(shù),則x2是偶數(shù)。P→Q

x2是偶數(shù)。x是偶數(shù)。Q∴P例3如果x是偶數(shù),則x2是偶數(shù)。P→Q

x不是偶數(shù)。x2不是偶數(shù)。P∴Q例4如果x是偶數(shù),則x2是偶數(shù)。P→Q

x2不是偶數(shù)。x不是偶數(shù)。Q∴P例1中,若不管命題的具體涵義,那么它所應(yīng)用的推理規(guī)則就是Q∴PP∧(P→Q)Q

中間部分是左側(cè)規(guī)則的另一種寫法,右側(cè)是此推理規(guī)則所對(duì)應(yīng)的永真蘊(yùn)含式。從這個(gè)永真蘊(yùn)含式可看出,它正是代表“如果P并且P→Q是真,則Q是真”的意義,這里P和Q表示任意命題。所以,它恰好代表左側(cè)的推理規(guī)則。這條推理規(guī)則叫假言推理,從形式上看結(jié)論Q是從P→Q中分離出來的,所以又叫分離規(guī)則。它是推理規(guī)則中最重要的一條。對(duì)任一永真蘊(yùn)含式A

B來說,如果前提A為真,則可保證B為真,因此不難看出,任一個(gè)永真蘊(yùn)含式都可作為一條推理規(guī)則。例如,P∧(P∨Q)Q代表以下規(guī)則,叫做析取三段論。P∴Q或P，P∨Q推得Q。下邊舉一個(gè)例子,說明這條推理規(guī)則是正確的。設(shè)P:他在釣魚,Q:他在下棋。他在釣魚或下棋

P∨Q他不在釣魚∴他在下棋這樣,就可給出以下定義:P∴Q定義1.4-1若H1∧H2∧…∧Hn

C,則稱C是H1,H2,…,Hn的有效結(jié)論。特別若AB,則稱B是A的有效結(jié)論。定義說明:若H1∧H

2∧…∧Hn

C,則從H1∧H2∧…∧Hn推出C,這樣的推理是正確的。但注意推理正確不等于結(jié)論為真,結(jié)論的真假還取決于前提H1∧H2∧…∧Hn的真假,前提為真時(shí),結(jié)論C為真;前提為假時(shí),

C可能真也可能假,這就是定義中只說C是H1∧H2∧…∧Hn的有效結(jié)論而不說是正確結(jié)論的原因。有效”是指結(jié)論的推出是合乎推理規(guī)則的。

例2所以錯(cuò)誤,是Q∧(P→Q)→P不是永真蘊(yùn)含式,不能用作推理規(guī)則,換言之,P不是Q和(P→Q)的有效結(jié)論。這種錯(cuò)誤叫肯定后件的錯(cuò)誤。

例3所以錯(cuò)誤,其理由類似于例2,這種錯(cuò)誤叫做否定前件的錯(cuò)誤。最常用的推理規(guī)則,見表1.5-1。表1.5-1最常用的推理規(guī)則下面再介紹兩條規(guī)則:;(1)規(guī)則P:在推導(dǎo)的任何步驟上都可以引入前提。;(2)規(guī)則T:在推導(dǎo)中,如果前面有一個(gè)或多個(gè)公式永真蘊(yùn)含S,則可把S引進(jìn)推導(dǎo)過程。這兩條規(guī)則,一般都認(rèn)為是理所當(dāng)然的,而不作為規(guī)則單獨(dú)提出,但為了提高我們思維的精密性,以便劃清允許或不允許的操作,筆得認(rèn)為有必要列出。

例5(a)考慮下述論證:;如果這里有球賽,則通行是困難的。如果他們按時(shí)到達(dá),則通行是不困難的。他們按時(shí)到達(dá)了。所以這里沒有球賽。前3個(gè)斷言是前提,最后一斷言是結(jié)論,要求我們從前提推出結(jié)論。

設(shè)P:這里有球賽,Q:通行是困難的,R:他們按時(shí)到達(dá)。這論證能表達(dá)如下:用蘊(yùn)含式表達(dá),則是(P→Q)∧(R→Q)∧R→P

證列出前提和結(jié)論叫論證(Argument),它未必是有效的。證明(Proof)則是有效論證的展開,從上例可看出,它由一系列公式(叫公式序列)組成,它們或者是前提,或者是公理,或者是居先公式的結(jié)論,這些結(jié)論都必須根據(jù)推理規(guī)則得出。(b)

證明R∨S是前提C∨D,C→R,D→S的有效結(jié)論。證上述證明過程,本質(zhì)上和數(shù)學(xué)中所見過的是一致的,不過這里每一語句是形式化的,并且都是根據(jù)推理規(guī)則得出的。這樣,就不容易產(chǎn)生推理錯(cuò)誤,可確保我們無誤地構(gòu)造出有效論證的證明。若論證是不正確的,則不能構(gòu)造出這樣的證明,反之亦然。掌握這種形式方法,對(duì)提高我們邏輯分析能力極為重要。

1.5.2證明方法定理常見的形式是“P當(dāng)且僅當(dāng)Q”,“如果P,那么Q”。而前者又相當(dāng)于P→Q并且Q→P,所以歸根結(jié)底,定理的主要形式是P→Q,至于其它形式,諸如P形式,只須證明P是假;P∧Q形式,只須證明P,Q俱真,P∨Q形式,可轉(zhuǎn)化為P→Q形式。1.無義證明法證明P是假,那么P→Q是真。2.平凡證明法證明Q是真,那么P→Q是真。無義證明法和平凡證明法應(yīng)用的次數(shù)較少,但對(duì)有限的或特殊的情況,它們常常是重要的。

3.直接證明法假設(shè)P是真,如果能推得Q是真,則P→Q是真。

4.間接證明法因P→Q

Q→P,對(duì)Q→P進(jìn)行直接證明,即假設(shè)Q假,如果能推得P是假,則

Q→P是真,也就是P→Q是真。這個(gè)證明法也叫逆反證明法。例6(a)定理:如果4x+6y=97,那么x或y不是整數(shù)。

證4x+6y=97,可改寫為2x+3y=。2x+3y不是整數(shù),所以x或y不是整數(shù)。這是直接證明法。(b)一個(gè)完全數(shù)是一個(gè)整數(shù),它等于它的所有因子(除本身外)的和。如6是一個(gè)完全數(shù),因?yàn)?=1+2+3,同樣28也是。

定理:一個(gè)完全數(shù)不是一個(gè)質(zhì)數(shù)。;證其逆反如下:一個(gè)質(zhì)數(shù)不是一個(gè)完全數(shù)。假設(shè)P是一質(zhì)數(shù),那么P≥2并且P恰有兩個(gè)因子1和P,所以小于P的所有因子的總和是1。這得出P不是一個(gè)完全數(shù)。

這是間接證明法。

5.(P1∧P2∧…∧Pn)→Q形式命題的證明;可用直接證明法或間接證明法。因(P1∧P2∧…∧Pn)→Q的逆反是Q→P1∨P2∨……∨Pn,用間接證明法時(shí),只須證明至少有一個(gè)i值,使Q蘊(yùn)含Pi是真即可。這也可以說是間接證明法的推廣。6.P1∧P2∧…∧Pn→(P→Q)形式命題的證明根據(jù)公式E22,P1∧P2∧…∧Pn→(P→Q)等價(jià)于P1∧P2∧…∧Pn∧P→Q,所以,只須證明

P1∧P2∧…∧Pn∧P→Q

這個(gè)方法叫CP規(guī)則,也叫演譯定理,因P移作前提,常使證明簡化,所以經(jīng)常應(yīng)用。

例7如果A參加球賽,則B或C也將參加球賽。如果B參加球賽,則A不參加球賽。如果D參加球賽,則C不參加球賽。所以,A若參加球賽,則D不參加球賽。

解設(shè)A:A參加球賽,B:B參加球賽,C:C參加球賽,D:D參加球賽。要證明的是A→D可從A→B∨C,B→A,D→C推出。7.(P1∨P2∨…∨Pn)→Q形式命題的證明;因?yàn)镻1∨P2∨…∨Pn→Q

P1∧P2∧…∧

Pn∨Q

(P1∨Q)∧(P2∨Q)∧…∧(

Pn∨Q) (P1→Q)∧(P2→Q)∧…∧(Pn→Q)所以,欲證P1∨P2∨…∨Pn→Q永真,只須證明對(duì)每一i,Pi→Q成立。這種證明方法叫分情況證明例8

試證記作“”的二元運(yùn)算“max”是可結(jié)合的,即對(duì)任何整數(shù)a,b和c,(a

b)c=a(b

c)。;

證對(duì)任意3整數(shù)a,b,c,下列6種情況之一必須成立:;

a≥b≥c,a≥c≥b,b≥a≥c,b≥c≥a,c≥a≥b或c≥b≥a。

情況1:a≥b≥c,那么;(ab)c=ac=aa(bc)=ab=a

∴(ab)c=a(bc)

其它情況類似可證。]]]]]]]]]]]]]]]

8.反證法(歸謬法)

設(shè)公式H1,H2,…,Hm中的原子命題變?cè)荘1,P2,…,Pn,如果給P1,P2,…,Pn以某一指派,能使H1∧H2…∧Hm具有真值T,則稱命題公式集合{H1,H2,…,Hm}是一致的,否則稱為非一致的。這個(gè)定義也可這樣敘述:若H1∧H2∧…∧Hm

R∧R,則{H1,H2,…,Hm}是非一致的,否則是一致的。定理1.5-1設(shè){H1,H2,…,Hn}是一致的,C是一命題公式,如果{H1,H2,…,Hn,C}非一致,則能從H1,H2,…,Hn推出C。

證因?yàn)镠1∧H2∧…∧Hn∧C

R∧R,所以,H1∧H2∧…∧Hn∧C永假,但{H1,H2,…,Hm}是一致的,所以使H1∧H2∧…∧Hn為真的指派使C為假,因此C為真。故

H1∧H2∧….∧Hn

C

這一定理說明,欲證H1∧H2∧…∧Hn

C,只須證明H1∧H2∧…∧Hn∧C

R∧R。這種證明法叫反證法,又叫歸謬法。其中C叫假設(shè)前提。

例9證明(P∧Q)是P∧Q的有效結(jié)論。

證把(P∧Q)作為假設(shè)前提?！郟∧Q(P∧Q)反證法有時(shí)使證明很方便,但它不是必不可少的證明法,總可以用CP規(guī)則代替它,因?yàn)槿粢炎C得H1∧H2∧…∧Hn∧C

R∧R

則由CP規(guī)則得H1∧H2∧…∧Hn

C→R∧RC→R∧R

C

由前提三段論得H1∧H2∧…∧Hn

C

*1.5.3推理的其它問題把公理用∧聯(lián)結(jié)起來,求出所得式子的主合取范式,隨意地取出若干個(gè)極大項(xiàng)并用∧聯(lián)結(jié)之,這樣得出的式子,便是推論。因?yàn)橹骱先》妒綖檎?其每一合取項(xiàng)為真,因此,若干個(gè)合取項(xiàng)之積也是真,所以它是這些公理的推論。如果有m個(gè)合取項(xiàng),可得2m-1個(gè)(0個(gè)合取項(xiàng)不包括在內(nèi))不同的推論。例如,以P及P→Q作公理時(shí)P∧(P→Q)P∧((P∨Q) (P∨Q∧Q)∧(P∨Q)(P∨Q)∧(P∨Q)∧(P∨Q)于是可作出以下推論;

P∨Q,P∨Q,P∨Q,(P∨Q)∧(P∨Q),(P∨Q)∧(P∨Q),(P∨Q)∧(P∨Q),(P∨Q)∧(P∨Q)∧(P∨Q)。