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

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

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

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

例2下述都不是命題:;(a)x+y＞4。 (c)真好啊!;(b)x=3。 (d)你去哪里?;(a)和(b)是斷言,但不是命題,因為它的真值取決于x和y的值。(c)和(d)都不是斷言,所以不是命題。

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

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

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

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

P0110例4(a)

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

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

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

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

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

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

(a)P:天不下雨,Q:草木枯黃。P→Q:如果天不下雨,那么草木枯黃。(b)R:G是正方形,S:G的四邊相等。R→S:如果G是正方形,那么G的四邊相等。(c)W:桔子是紫色的,V:大地是不平的。W→V:如果桔子是紫色的,那么大地是不平的。在日常生活中用蘊含式來斷言前提和結論之間的因果或實質(zhì)關系,如上例(a)和(b),這樣的蘊含式叫形式蘊含,然而,在命題演算中,一個蘊含式的前提和結論并不需要有因果和實質(zhì)聯(lián)系,這樣的蘊含式叫實質(zhì)蘊含,如上例(c)中,桔子的顏色和大地的外形之間沒有因果和實質(zhì)關系存在,但蘊含式W→V是真,因為前提是假而結論是真。采用實質(zhì)蘊含作定義,是因為在討論邏輯和數(shù)學問題中,這不僅是正確的,且方便應用。蘊含式P→Q可以用多種方式陳述:;“若P,則Q”“P是Q的充分條件”“Q是P的必要條件”“Q每當P”;“P僅當Q”等。如上例(b)中的R→S可陳述為“G是正方形的必要條件是它的四邊相等”。給定命題P→Q,我們把Q→P,

P→

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

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

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

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

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

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

P∧Q∧R∨P∧Q∧R∨P∧Q∧R∨P∧Q∧R(v)“當且僅當明天不下雪并且不下雨時我才去學?！笨蓪懗?

P∧Q

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

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

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

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

B)是命題公式。

(3)只有有限步應用條款(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)以下不是命題公式,因為它們不能由形成規(guī)則得出?！腝,(P→Q,P→∧Q,((PQ)∧R)

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

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

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

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

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

P是假。因而

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

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

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

1.若AB,BC

則AC;若AB,BC則AC。;

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

證A→B永真;

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

證

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

一重言式中某個命題變元出現(xiàn)的每一處均代入以同一公式后,所得的仍是重言式。這條規(guī)則之所以正確是由于重言式之值不依賴于變元的值的緣故。例如

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)一樣。代入后所得公式稱為原公式的代入實例。對非重言式通常不作代入運算,特別是偶然,因所得代入實例的性質(zhì)不確定,沒有用處。例如:B:P→Q原是偶然,若用R∨R代換B中之Q,得

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

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

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

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

D。

應用這兩條規(guī)則和已有的重言式可以得出新的重言式。例如,對公式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

……

對公式E19:

P∧T

P,我們利用公式P∨PT,對其中的T作替換(注意不是代入,對命題常元不能代入)得公式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)試將語句“情況并非如此:如果他不來,那么我也不去?！被啞?/p>

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

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)是所求表達式。1.2.6對偶原理定義1.2-1設有公式A,其中僅有聯(lián)結詞∧,∨,。在A中將∧,∨,T,F分別換以∨,∧,F,T得公式A*,則A*稱為A的對偶公式。對A*采取同樣手續(xù),又得A,所以A也是A*的對偶。因此,對偶是相互的。例3

(a)

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

(b)P∨F

和P∧T互為對偶。定理1.2-1設A和A*是對偶式。P

1,P2,…,Pn是出現(xiàn)于A和A*中的所有命題變元,于是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為命題變元P1,P2,…..,Pn及聯(lián)結詞∧,∨,構成的公式,則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)永真因為上式是永真式,可以使用代入規(guī)則,以Pi代Pi,1≤i≤n,得A*(P1,P2,…,Pn)B*(

P1,P2,…,

Pn)永真所以,A*

B*。證畢。本定理常稱為對偶原理。

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

定理1.2-3如果AB,且A,B為命題變元P1,P2,…,Pn及聯(lián)結詞∧,∨,構成的公式,則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)永真因為上式是永真式,可以使用代入規(guī)則,以Pi代Pi,1≤i≤n,得

B*

A*。

證畢。1.3范式1.3.1析取范式和合取范式為敘述方便,我們把合取式稱呼為積,析取式稱呼為和。;定義1.3-1命題公式中的一些命題變元和一些命題變元的否定之積,稱為基本積;一些命題變元和一些命題變元的否定之和,稱為基本和。例如,給定命題變元P和Q,則P,P∧Q,P∧Q,P∧P,

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

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

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

證

充分性

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

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

必要性用反證法。設基本積永假但不含P和P形式的兩個因子,則給這個基本積中不帶否定符的命題變元指派真值T,帶有否定符的命題變元指派真值F,得基本積的真值是T,但這與假設矛盾。證畢。定義1.3-2一個由基本積之和組成的公式,如果與給定的命題公式A等價,則稱它是A的析取范式,記為A

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

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

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

P∧P∨P∧Q

P∧(P→Q)不是永假式,因為其析取范式中,后一個基本積非永假。如果需要求出最簡的析取范式,那么(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一個由基本和之積組成的公式,如果與給定的命題公式A等價,則稱它是A的合取范式,記為A

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

如果給定的公式的合取范式中每個基本和都是永真式,則該式也必定是永真式。例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的合取范式中,每一個基本和都是永真式,所以它是永真式。(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個變元的基本積中,若每一個變元與其否定不同時存在,而兩者之一必出現(xiàn)一次且僅出現(xiàn)一次,則這種基本積叫極小項。

n個變元可構成2n個不同的極小項。例如3個變元P,Q,R可構造8個極小項。我們把命題變元看成1,命題變元的否定看成0,那么每一極小項對應一個二進制數(shù),因而也對應一個十進制數(shù)。對應情況如下:

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我們把對應的十進制數(shù)當作足標,用mi表示這一項,即;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個變元的極小項是:m0

P1∧P2∧P3…∧

Pnm1

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

P1∧P2∧P3…∧Pn

定義1.3-5一個由極小項之和組成的公式,如果與給定的命題公式A等價,則稱它是A的主析取范式。任何一個命題公式都可求得它的主析取范式,這是因為任何一個命題公式都可求得它的析取范式,而析取范式可化為主析取范式。例如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)前邊講過每一極小項和它的足標的二進制數(shù)一一對應,因而和一種指派一一對應,例如三個變元時,極小項足標指派

P∧Q∧R——101——1,0,1當且權當將對應的指派代入該極小項,該極小項的值才為1。因此,在命題公式的主析取范式中,諸極小項都與真值表中相應指派處的該公式的真值1相對應,反之亦然。例3證明

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

證

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所以,二式邏輯等價。定義1.3-6

在n個變元的基本和中,若每一個變元與其否定不同時存在,而二者之一必出現(xiàn)一次且僅出現(xiàn)一次,則這種基本和叫極大項。

n個變元可構成2n個不同的極大項。類似于(但不同)極小項的記法,它們是:

M0

P1∨P2∨…∨Pn

M

1

P1∨P2∨…∨

Pn

M

2

P1∨P2∨…∨

Pn-1∨Pn

…

M2n-1

P1∨P2∨…∨Pn這里是將命題變元對應于0,命題變元的否定對應于1,恰與極小項記法相反,例如3個變元的極大項是這樣對應的極大項足標指派

P∨Q∨R——010——0,1,0其目的是當且僅當將極大項的對應指派代入該極大項,才使該極大項的真值為0,使今后許多運算得到方便。

定義1.3-7一個由極大項之積組成的公式,如果與給定的命題公式A等價,則稱它是A的主合取范式。任何一個命題公式都可求得它的主合取范式,這是因為任何一個命題公式都可求得它的合取范式,而合取范式可化為主合取范式。例如

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)一個命題公式的真值表是唯一的,因此一個命題公式的主合取范式也是唯一的。兩個命題公式如果有相同的主合取范式,那么兩個命題公式是邏輯等價的。一個命題公式的主析取范式和主合取范式緊密相關,在它們的簡記式中,代表極小項和極大項的足標是互補的,即兩者一起構成0,1,2,…,2n-1諸數(shù),例如

AP∧Q∨R

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

P∧Q∨R

π(0,2,4)下面列出極小項和極大項性質(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主析取范式的個數(shù)當n=1時,極小項有21=2個,即P,P。主析取范式有:沒有極小項全部極小項當n=2時,極小項有22=4個,即P∧Q,P∧Q,P∧Q,P∧Q。主析取范式有共222=16個。以此類推,n個命題變元,可構造22n個不同的主析取范式(包括F)。這個數(shù)字增長非?？?如n=3時223=256,n=4時224=65536。

主合取范式和主析取范式是一一對應的,因此,n個命題變元,也可構造22n個不同的主合取范式(包括T)。1.4聯(lián)結詞的擴充與歸約1.4.1聯(lián)結詞的擴充1.一元運算Pf1

f2

f3f

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

7,f8,f

13,f

14,f15已定義,f

1,f10,f

11,f

16作為運算意義不大,只需再定義以下4個:

f

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

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

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

Q)P∧Q∨P∧Q

f

3,f

4蘊含否定:P→Q(P→Q)

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

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

證設f(P,Q)表示僅用命題變元P和Q及聯(lián)結詞,構成的任意的命題公式?，F(xiàn)證明對P,Q的4種指派,f(P,Q)的真值只能是下表中的8種結果之一:①在未運算前,P和Q的值是屬于表中結果3和4,即屬于8種之一。②以上8種結果任兩種(包括自己對自己)經(jīng)運算,仍得以上8種結果之一。③以上8種結果,任一種經(jīng)運算,仍得以上8種結果之一。所以,對P,Q的4種指派,經(jīng)反復用和運算,只能得出以上8種結果之一,即f(P,Q)的真值只能是表中8種結果之一。但以上8種結果都是偶數(shù)個1,而P∨Q是3個1,所以不能用f(P,Q)表達P∨Q,故{,}不是全功能集合。一般地說,要證明聯(lián)結詞集合A是不是全功能的,只需選一個全功能聯(lián)結詞集合B,一般選{∨,}或{∧,},若B中每一聯(lián)結詞都能用A中的聯(lián)結詞表達,則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)結詞擴充后,也可由極小項和聯(lián)結詞⊕構成主異或范式,由極大項和聯(lián)結詞構成主等值范式。例如因為對任一指數(shù),任兩個不同的極小項mi和mj不可能同時為真,因此mi∨mj與mi⊕mj是等價的,故由主析取范式可轉寫成主異或范式。類似地,任兩個不同的極大項Mi和Mj不可能同時為假,因此Mi∧Mj和Mi

Mj是等價的,故主合取范式可轉寫成主等值范式。主異或范式和主等值范式也是唯一的。1.5推理規(guī)則和證明方法1.5.1推理規(guī)則像前幾節(jié)那樣確定命題演算,本質(zhì)上和簡單的開關代數(shù)一樣,簡單的開關代數(shù)是命題演算的一種應用?，F(xiàn)在,我們從另一角度研究命題演算,即從邏輯推理角度來理解命題演算。先考察4個推理的例子,在每一例子中,橫線上的是前提,橫線下的是結論。右側是例子的邏輯符表示。設x屬于實數(shù),P:x是偶數(shù),Q:x2是偶數(shù)。例1如果x是偶數(shù),則x2是偶數(shù)。x是偶數(shù)。x2是偶數(shù)。前提結論∴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中,若不管命題的具體涵義,那么它所應用的推理規(guī)則就是Q∴PP∧(P→Q)Q

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

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

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

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

2∧…∧Hn

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

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

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

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

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

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

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

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

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

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

4.間接證明法因P→Q

Q→P,對Q→P進行直接證明,即假設Q假,如果能推得P是假,則

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

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

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

這是間接證明法。

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

P1∧P2∧…∧Pn∧P→Q

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

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

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

P1∧P2∧…∧

Pn∨Q

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

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

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

b)c=a(b

c)。;

證對任意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.反證法(歸謬法)

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

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

證因為H1∧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叫假設前提。

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

證把(P∧Q)作為假設前提?！郟∧Q(P∧Q)反證法有時使證明很方便,但它不是必不可少的證明法,總可以用CP規(guī)則代替它,因為若已證得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)結起來,求出所得式子的主合取范式,隨意地取出若干個極大項并用∧聯(lián)結之,這樣得出的式子,便是推論。因為主合取范式為真,其每一合取項為真,因此,若干個合取項之積也是真,所以它是這些公理的推論。如果有m個合取項,可得2m-1個(0個合取項不包括在內(nèi))不同的推論。例如,以P及P→Q作公理時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)。