步驟：

(3)求每個(gè)成真賦值對(duì)應(yīng)的十進(jìn)制數(shù)，即極小項(xiàng)的角碼，將極小項(xiàng)按序析取即成。

利用真值表求命題公式的主析取范式。(1)列出的真值表，(2)找出的所有成真賦值，解：(1)列真值表

例用真值表求的主析取范式。解：(2)

成真賦值有010，100，101，110，111(3)對(duì)應(yīng)的十進(jìn)制數(shù)為2，4，5，6，7所以的主析取范式為

例用真值表求的主析取范式。大、小項(xiàng)利用真值表求命題公式的主合取范式。

步驟：

(3)求每個(gè)成假賦值對(duì)應(yīng)的十進(jìn)制數(shù)，即極大項(xiàng)的角碼，將極大項(xiàng)按序合取即成。(1)列出的真值表，(2)找出的所有成假賦值，例

用真值表求的主合取范式。解：(1)列真值表

(3)對(duì)應(yīng)的十進(jìn)制數(shù)為0，1，3。

例

用真值表求的主合取范式。解：(2)的成假賦值有000，001，011，所以的主合取范式：大、小項(xiàng)例10.23求P→((P→Q)∧(Q∨P))

的主合取范式和主析取范式。解：設(shè)A=(P→Q)∧(Q∨P)PQP→QQ∨P(Q∨P)A原式FFTTFFTFTTTFFTTFFTFFFTTTFTTT原式(P∧Q)∨(P∧Q)∨(P∧Q)(主析取范式)(0,1,3)(主析取范式)(P∨Q)(主合取范式)

(2)(主合取范式)大、小項(xiàng)例：設(shè)一公式A的真值表為:解：A(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)m0∨m4∨m7(0，4，7)求公式A的主析取范式PQRA00010010010001101001101011001111大、小項(xiàng)步驟：

(3)消去重復(fù)的項(xiàng)及永假項(xiàng)。

利用等值式演算求命題公式的主析取范式。

如

補(bǔ)充變?cè)?4)按角碼順序排序，并用“”表示。(1)化為析取范式。(2)補(bǔ)入沒有出現(xiàn)的變?cè)?，即添加?P∨P)

這樣的式子，然后用分配律展開。第5次課步驟：(3)消去重復(fù)的項(xiàng)及永真項(xiàng)；

利用等值式演算求命題公式的主合取范式。

如

補(bǔ)充變?cè)?4)按角碼順序排序，并用符號(hào)“”表示；如。記為(1)化為合取范式。(2)補(bǔ)入沒有出現(xiàn)的變?cè)?，即添加?P∧P)

這樣的式子，然后用分配律展開。例求(P∧Q)∨(P∧R)∨(Q∧R)

的主析取范式和主合取范式解：原式((P∧Q)∧(R∨R))∨(P∧R∧(Q∨Q))∨(Q∧R∧(P∨P))(P∧Q∧R)∨(P∧Q∧R)∨(P∧R∧Q)∨(P∧R∧Q)∨(Q∧R∧P)∨(Q∧R∧P)

m7∨m6∨m3∨m1

∑(1，3，6，7)

(0，2，4，5)例：求P→((P→Q)∧(Q∨P))的主析取范式解：原式

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

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

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

(P∧Q)∨(P∧Q)∨(Q∧P)m0∨m1∨m3∑(0，1，3)主(析取/合取)范式的性質(zhì):1.如果命題公式是重言式

它的主析取范式包含所有(2n項(xiàng))的極小項(xiàng)

此時(shí)主合取范式為“空”

定義它為1。2.如果命題公式是矛盾式

它的主合取范式包含所有(2n個(gè)項(xiàng))的極大項(xiàng)

此時(shí)主析取范式為“空”

定義它為0。主(析取/合取)范式的性質(zhì):3.兩個(gè)命題公式是相等的

它們的主合取范式和主析取范式相等。若主范式非空且不包含全部2n個(gè)項(xiàng),則是可滿足式。4.含有n個(gè)命題變?cè)墓紾的主析取范式中小項(xiàng)項(xiàng)數(shù)與G的主合取范式中大項(xiàng)項(xiàng)數(shù)之和為2n。5.若G的主析取范式中有小項(xiàng)mi,則G的主合取范式中

一定不含有大項(xiàng)Mi,反之亦然。由mi

Mi,Mi

mi(0≤i≤2n–1)和性質(zhì)4、5,求出主合取范式,也就求出了主析取范式,反之亦然。已知命題公式的主析取范式(主合取范式)，

求主合取范式(主析取范式)。

(2)寫出與(1)中極小項(xiàng)角碼相同的極大項(xiàng)，

由的主合取范式步驟：

的主析取范式求(1)寫出的主析取范式未出現(xiàn)的極小項(xiàng)，(3)由以上極大項(xiàng)合取即成的主合取范式。例

已知命題公式的主合取范式。(主析取范式為：求含3個(gè)命題變項(xiàng))

解：的主合取范式為：

例

已知命題公式主合取范式為：的主析取范式。(求含2個(gè)命題變項(xiàng))解：的主析取范式為：主范式的用途:

(1)判斷兩命題公式是否等值。

(2)判斷命題公式的類型。

重言式主析取范式含全部的極小項(xiàng)主合取范式不含任何極大項(xiàng)(主合取范式記為1)矛盾式主析取范式不含任何極小項(xiàng)(主析取范式記為0)主合取范式含全部的極大項(xiàng)主范式的用途:

(2)判斷命題公式的類型。

可滿足式主析取范式至少含一個(gè)極小項(xiàng)主合取范式至少缺一個(gè)極大項(xiàng)(3)求成真(假)賦值。

(4)求真值表。

例

已知含3個(gè)命題變項(xiàng)的公式：

和(1)判斷的類型。解：為矛盾式。為可滿足式，(2)判斷是否等值。解：不等值。例

已知含3個(gè)命題變項(xiàng)的公式：

和(3)求的成真賦值和成假賦值。(4)求的真值表。解：真值表

的成假賦值有010，011，100，101。

的成真賦值有000，001，110，111。

解：為減少括號(hào)的使用量，規(guī)定聯(lián)結(jié)詞的優(yōu)先級(jí)由高到低的次序?yàn)椋?、∧、∨、→、遇有括?hào)時(shí)，先進(jìn)行括號(hào)內(nèi)的運(yùn)算。同級(jí)聯(lián)結(jié)詞,按從左往右的次序運(yùn)算。為確保命題的清晰性,提高可讀性,適當(dāng)添加括號(hào)還是必要的。§4命題演算的推理理論推理是由已知的命題得到新命題的思維過程。任何一個(gè)推理都由前提和結(jié)論組成。前提就是推理所根據(jù)的已知的命題,結(jié)論則是從前提通過推理而得到的新命題。推理一般分為演繹推理和歸納推理兩類,凡前提和結(jié)論之間的聯(lián)系時(shí)必然的,此類推理稱為演繹推理,否則稱為歸納推理。數(shù)理邏輯研究的主要是演繹推理。推理理論對(duì)于計(jì)算機(jī)科學(xué)中的程序驗(yàn)證、定理的機(jī)械證明和人工智能等都是十分重要的。從語言角度,推理分為語義和語法兩種。語義推理注重內(nèi)涵的正確性,也就是從真的前提出發(fā)要推出真的結(jié)論來,推理過程考慮得少,關(guān)心的是結(jié)論的正確性。語法推理則注重形式上的有效,注重推理過程是否符合某些事先規(guī)定的邏輯規(guī)則,若結(jié)論是嚴(yán)格遵循規(guī)則得到的,那便是有效的。數(shù)理邏輯主要采用語法推理,它關(guān)心的是結(jié)論的有效性，而不關(guān)心前提的實(shí)際真值,當(dāng)然語法推理作為一種推理方法,它必須能反映客觀事物中真實(shí)存在的邏輯關(guān)系,換句話說,語法推理必須保證語義上的正確性。給定命題公式A，B，若A→B為永真式，即AB，則稱B為A的有效結(jié)論，或稱B可由A推導(dǎo)出來。定義10.23設(shè)H1，H2，…，Hm，C是命題公式，若H1∧H2∧…∧HmC，則稱C是一組前提H1，H2，…，Hm的有效結(jié)論。定義10.24判別有效結(jié)論的基本方法有：(1)真值表法(2)直接證法(3)間接證法判斷推理是否正確的方法:

等值演算法，真值表法，主析取范式法。

例判斷下面的推理是否正確。

如果天氣涼快，小王就不去游泳，天氣涼快，所以小王沒去游泳。

結(jié)論：

推理形式結(jié)構(gòu)為：

判斷它是否為重言式。

前提：，解：設(shè)小王去游泳。：：天氣涼快，[方法一]用等值演算法。

所以推理正確。

[方法二]用真值表法。

其真值表中最后一列全為1，

所以推理正確。

[方法三]用主析取范式法。

主析取范式含全部小項(xiàng)，所以推理正確。

例判斷下列推理是否正確。

如果今天是星期二，則明天是星期四。

今天是星期二，所以明天是星期四。

以上推理即假言推理，所以推理是正確的。

解：：明天是星期四，：今天是星期二，前提：結(jié)論：

，例10.27在下列三種情況下，試確定結(jié)論C在前提H1，H2下的有效性：解：實(shí)際上就是判斷：

(1)(P∧(P∨Q)→Q是否為永真式。

(2)(P→Q)→(P→(P∧Q))

是否為永真式。

(3)(

P∧(P∨Q))→(P∧Q)是否為永真式。為此，構(gòu)造真值表如下：

H1H2C(1)PP∨QQ(2)P→QP→(P∧Q)(3)

PP∨QP∧Q

PQPP→QP∨QP∧QP∧(P∨Q)P→(P∧Q)(1)(2)(3)FFFTTFTT所以，(1)、(2)為有效結(jié)論，而(3)不是。TTFFTTFTFTTTFFFTFTFFTTFT(1)(P∧(P∨Q)→Q(2)(P→Q)→(P→(P∧Q))

(3)(

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

當(dāng)前提和結(jié)論都是比較復(fù)雜的命題公式或者所包含的命題變?cè)芏鄷r(shí),用真值表的辦法顯得很繁瑣,需要尋求更有效的推理方法。

一個(gè)描述推理過程的命題序列,其中每個(gè)命題或者是已知的命題,或者是由某些前提所推得的結(jié)論,序列中最后一個(gè)命題就是所要求的結(jié)論,這樣的命題序列稱為形式證明。命題定律E1～E26（P32）基本蘊(yùn)涵式I1～I(xiàn)17（P33）規(guī)則P：在推導(dǎo)的任何步驟上可以引入前提；規(guī)則T：在推導(dǎo)過程中，如果前面有一個(gè)或多個(gè)公式永真蘊(yùn)涵公式S，則可以把S引入推導(dǎo)過程中；規(guī)則CP：如果能從前提集合及R中推導(dǎo)出S來，那么就能從前提集合直接導(dǎo)出R→S。置換規(guī)則