離散數(shù)學(xué)（第3版）課件ch1(2) 命題邏輯1.5-1.8 賁

1第1章命題邏輯1.1現(xiàn)代邏輯學(xué)1.2命題及其表示法1.3命題公式與語句形式化1.4重言式1.5對偶與范式1.6其他聯(lián)結(jié)詞1.7命題演算的推理理論1.8命題演算中的歸結(jié)推理1.9應(yīng)用案例21.5對偶與范式定義1.13在僅含有聯(lián)結(jié)詞

，

，

的命題公式A中，將換成

，將

換成

，同時T和F互相替代，所得公式A*稱為A的對偶式。

顯然A是A的對偶式A*的對偶式。一、對偶例試寫出下列命題公式的對偶式。A1：(p

q)rA2:((pq)F)(T(rp))3定理1.2設(shè)A*，B*分別是A和B的對偶式，如果A

B，則A*B*。例證明下列命題等價式,并寫出其對偶式。Q((PQ)P)T(PQ)(PQ)(PQ)(PQ)

定理1.1

A和A*是互為對偶式，p1,p2,…,pn是出現(xiàn)在A和A*的原子變元，則

A（p1，…，pn）

A*（

p1，…，

pn）A（

p1，…，

pn）

A*（p1，…，pn）4二、范式定義1.15(1)由有限個簡單合取式構(gòu)成的析取式稱為析取范式。(2)由有限個簡單析取式構(gòu)成的合取式稱為合取范式。(3)析取范式與合取范式統(tǒng)稱為范式。定義1.14

命題變元及其否定統(tǒng)稱作文字。僅有有限個文字構(gòu)成的析取式稱作簡單析取式。僅有有限個文字構(gòu)成的合取式稱作簡單合取式。

5求范式步驟：①使用命題定律，消去公式中除

、

和

以外公式中出現(xiàn)的所有聯(lián)結(jié)詞；②使用

(

P)

P和德·摩根律，將公式中出現(xiàn)的聯(lián)結(jié)詞

都移到命題變元之前；③利用結(jié)合律、分配律等將公式化成析取范式或合取范式。定理1.5

對于任何命題公式，都存在與其等價的析取范式和合取范式。6由于合取范式與析取范式的不唯一性，對識別命題公式間是否等價帶來一定困難，而命題公式的主范式解決了這個問題。下面將分別討論主析取范式和主合取范式。7定義1.16

對于含有n個命題變元的命題公式，若已表示成析取范式，并且該范式中的每一個合取式都由這n個命題變元(或其否定)組成，則稱該析取范式為主析取范式。其中，簡單的合取式稱為極小項。三、極小項與主析取范式規(guī)定：極小項中，命題變元的原形對應(yīng)T，其否定對應(yīng)F。8由變元p,q形成的極小項由p,q,r形成的極小項9例

用兩種方式求命題公式

P∧(Q→R)的主析取范式。（1）等值演算法（2）真值表法定理

在命題公式的真值表中，由真值為T的指派所對應(yīng)的極小項而形成的析取即為此命題公式的主析取范式。10定義1.16

對于含有n個命題變元的命題公式，若已表示成合取范式，并且該范式中的每一個析取式都由這n個命題變元(或其否定)組成，則稱該合取范式為主合取范式。其中，簡單的析取式稱為極大項。四、極大項與主合取范式規(guī)定：極大項中，命題變元的原形對應(yīng)F，其否定對應(yīng)T。由變元p,q形成的極大項由p,q,r形成的極大項11定理在命題公式的真值表中，由真值為F的指派所對應(yīng)的極大項而形成的合取即為此命題公式的主合取范式。例

求命題公式

P∧(Q→R)的主合取范式。注意：主析取范式與主合取范式的簡記式中的下標(biāo)是互補

的，因此可由其中一個求另一個。12例設(shè)命題公式A=(p

(p∧q))∨r。(1)A的主析取范式中含有幾個極小項？(2)A的主合取范式中含有幾個極大項？解：(p

(p∧q))∨r

(┐p∨(p∧q))∨r

((┐p∨p)∧((┐p∨q))∨r

┐p∨q∨r

M4

m0∨m1∨m2∨m3∨m5∨m6∨m7。A的主析取范式中含有7個極小項。A的主合取范式中含有1個極大項。13練習(xí)：試求Q∨((P∨Q)∧P)的主析取范式和主合取范式。14五、范式的應(yīng)用舉例1判斷公式的類型設(shè)公式A中含n個命題變項，容易看出：(1)A為重言式當(dāng)且僅當(dāng)A的主析取范式含全部2n個極小項。(2)A為矛盾式當(dāng)且僅當(dāng)A的主析取范式不含任何極小項。此時，記A的主析取范式為F。(3)A為可滿足式當(dāng)且僅當(dāng)A的主析取范式至少含一個極小項。

152判斷兩個命題公式是否等價設(shè)公式A,B共含有ｎ個命題變項，按ｎ個命題變項求出Ａ與Ｂ的主析取范式Ａ'與Ｂ'。若Ａ'＝Ｂ',則Ａ

Ｂ；否則，ＡＢ。16例1某科研所要從3名科研骨干A，B，C中挑選1～2名出國進修。由于工作需要，選派時要滿足以下條件：

（1）若A去，則C同去；

（2）若B去，則C不能去；

（3）若C不去，則A去或B去。

問所里應(yīng)如何選派他們？17例1某科研所要從3名科研骨干A，B，C中挑選1～2名出國進修。由于工作需要，選派時要滿足以下條件：

（1）若A去，則C同去；

（2）若B去，則C不能去；

（3）若C不去，則A去或B去。

問所里應(yīng)如何選派他們？解：設(shè)p：派A去；q：派B去；r：派C去由已知條件可得命題公式(p→r)∧(q→┐r)∧(┐r→(p∨q))經(jīng)過等值演算可得原命題公式m1∨m2∨m5因為m001┐p∧┐q∧r,

m010┐p∧q∧┐r,

m101p∧┐q∧r所以選派方案有三種：

(1)C去,而A,B都不去；(2)B去,而A,C都不去；(3)A,C同去,而B不去。18例2

甲、乙、丙三個人報考了王教授的研究生?？荚嚭笸踅淌谡f錄取情況如下：

(1)三人中只錄取一人；

(2)如果不錄取甲，就錄取乙；

(3)如果不錄取丙，就錄取甲。請問王教授到底錄取了誰為他的研究生？解：設(shè)p：錄取甲；

q：錄取乙；

r：錄取丙。19思考：(1)n個命題變元最多能構(gòu)成多少個不等價的命題公式？(2)命題邏輯中最多可以有多少個聯(lián)結(jié)詞？20第1章命題邏輯1.1現(xiàn)代邏輯學(xué)1.2命題及其表示法1.3命題公式與語句形式化1.4重言式1.5對偶與范式1.6其他聯(lián)結(jié)詞1.7命題演算的推理理論1.8命題演算中的歸結(jié)推理1.9應(yīng)用案例211.6其他聯(lián)結(jié)詞一、n元真值函數(shù)

n元真值函數(shù)：有n個自變量的命題函數(shù)。TTFFFTFTFTF3(1)F2(1)F1(1)F0(1)p１元真值函數(shù)1個命題變元恰有22個不等價的命題公式。n個命題變元最多能構(gòu)成多少個不等價的命題公式？22pqF0(2)F1(2)F2(2)F3(2)F4(2)F5(2)F6(2)F7(2)TTFTFTFTFTTFFFTTFFTTFTFFFFTTTTFFFFFFFFFFpqF8(2)F9(2)F10(2)F11(2)F12(2)F13(2)F14(2)F15(2)TTFTFTFTFTTFFFTTFFTTFTFFFFTTTTFFTTTTTTTT2元真值函數(shù)p∧qp∨q(p

q)p∧p(p→q)p(q→p)q(p

q)(p∨q)(p∧

q)p∨p

q

pp→qq→p思考：命題邏輯中最多可以有多少個聯(lián)結(jié)詞？最少呢？23二、聯(lián)結(jié)詞的完備集定義1.18

設(shè)s是一些聯(lián)結(jié)詞組成的非空集合，如果任何的命題公式都可以用僅包含s中的聯(lián)結(jié)詞的公式表示，則稱s是聯(lián)結(jié)詞完備集。特別的，若s是聯(lián)結(jié)詞完備集且s的任何真子集都不是完備集，則稱s是最小完備集。

(1)s1={┐,∧,∨,→,

}

(2)s2={┐,∧,∨,→}(3)s3={┐,∧}

(4)s4={┐,∨}

(5)s5={┐,→}24三、單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集

定義1.19

設(shè)p、q為兩個命題，復(fù)合命題“p與q的否定式”

(“p或q的否定式”）稱作p,q的與非式（或非式），記作p↑q(p↓q)。符號↑(↓)稱作與非聯(lián)結(jié)詞（或非聯(lián)結(jié)詞）。

p↑q為真當(dāng)且僅當(dāng)p與q不同時為真，

p↓q為真當(dāng)且僅當(dāng)p與q同時為假。25定理：{↑}，{↓}都是聯(lián)結(jié)詞完備集。

證明：已知{┐,∧,∨}為聯(lián)結(jié)詞完備集，因而只需證明其中的每個聯(lián)結(jié)詞都可以由↑定義即可。┐p

┐(p∧p)p↑pp∧q┐┐(p∧q)┐(p↑q)

(p↑q)↑(p↑q)p∨q┐┐(p∨q)┐(┐p∧┐q)┐p↑┐q

(p↑p)↑(q↑q)

與非的性質(zhì)(1)p↑q

q↑p(2)(p↑q)↑(p↑q)(p∧q)(3)(p↑p)↑(q↑q)(p∨q)或非的性質(zhì)(1)p↓qq↓p(2)(p↓q)↓(p↓q)(p∨q)(3)(p↓p)↓(q↓q)(p∧q)26思考（1）{┐,∧,∨，→,

}中有無單元素構(gòu)成聯(lián)結(jié)詞完備集？（2）{┐,∧,∨，→,

}中有多少個子集構(gòu)成聯(lián)結(jié)詞完備集？某軍需倉庫大批戰(zhàn)利品失竊。罪犯（一人或多人）是用汽車運走贓物的。三個出了名的犯罪分子A,B,C被帶到倫敦警察廳刑事部盤問。查明了如下事實：（1）

A,B,C以外沒有人參與作案。（2）不邀A作搭檔（可能還有別人），C從不作案。（3）

B不懂怎么開車。A有罪無罪？2728第1章命題邏輯1.1現(xiàn)代邏輯學(xué)1.2命題及其表示法1.3命題公式與語句形式化1.4重言式1.5對偶與范式1.6其他聯(lián)結(jié)詞1.7命題演算的推理理論1.8命題演算中的歸結(jié)推理1.9應(yīng)用案例29

數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法來研究推理。所謂推理是指從前提出發(fā)推出結(jié)論的思維過程，而前提是已知命題公式集合，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。1.7命題演算的推理理論30(1)昨天晚上彭桂曦或去上自習(xí)或去值班；他沒有去上自習(xí)。所以，他去值班了。(2)若下午氣溫超過30℃，則盧宇峰必去游泳；若他去游泳，他就不去跑步了。盧宇峰沒有去跑步，所以下午氣溫必超過了30℃。思考：下列推理是否正確？31一、有效推理定義1.20

設(shè)α1，α2，…，αn，β都是命題公式，稱推理“α1，α2，…，αn推出β”是有效的（或正確的），如果對α1，α2，…，αn，β中出現(xiàn)的命題變項的任一指派，若α1，α2，…，αn都真，則β亦真，并稱β是有效結(jié)論。記為{α1，α2，…，αn}|=β。否則，稱“由α1，α2，…，αn推出β”是無效的或不合理的。注意：在推理形式中，推理形式的有效與否與前提中命題公式的排列次序無關(guān)。32例判斷下列推理是否正確：

(1){p,p→q}|=q(2){p,q→p}|=qpqp∧(p→q)qp∧(q→p)qTTTTTTTFFFTFFTFTFTFFFFFF33定理1.8

命題公式A1,A2,…,Ak推B的推理正確當(dāng)且僅當(dāng)

(A1∧A2∧…∧Ak)→B為重言式。有效推理的等價定義(1)昨天晚上彭桂曦或去上自習(xí)或去值班；他沒有去上自習(xí)。所以，他去值班了。(2)若下午氣溫超過30℃，則盧宇峰必去游泳；若他去游泳，他就不去跑步了。盧宇峰沒有去跑步，所以下午氣溫必超過了30℃。思考：下列推理是否正確？34(1)昨天晚上彭桂曦或去上自習(xí)或去值班；他沒有去上自習(xí)。所以，他去值班了。

設(shè)p：彭桂曦昨天晚上上自習(xí)；q：彭桂曦昨天晚上值班。

前提：p∨q，┐p結(jié)論：q

推理形式結(jié)構(gòu)：((p∨q)∧┐p)→q((p∨q)∧p)→q

┐((p∨q)∧┐p)∨q

((┐p∧┐q)∨p)∨q

((┐p∨p)∧(┐q∨p))∨q

┐q∨p∨qT

說明為重言式，所以推理正確。35(2)若下午氣溫超過30℃，則盧宇峰必去游泳；若他去游泳，他就不去跑步了。盧宇峰沒有去跑步，所以下午氣溫必超過了30℃。設(shè)p：下午氣溫超過30℃；q：盧宇峰去游泳；r：盧宇峰去跑步。前提：p→q，q→┐r

結(jié)論：┐r→p

推理的形式結(jié)構(gòu)：((p→q)∧(q→┐r))→(┐r→p)用主析取范式法判斷是否為重言式。

36用主析取范式法判斷是否為重言式。

((p→q)∧(q→┐r))→(┐r→p)

┐((┐p∨q)∧(┐q∨┐r))∨(r∨p)

((p∧┐q)∨(q∧r))∨r∨p

r∨p(用兩次吸收律)

(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∨m4∨m5∨m6∨m7

可見不是重言式，所以推理不正確。

37例判斷下面推理是否正確：(1)若a能被4整除，則a能被2整除；a能被4整除。所以a能被2整除。(2)若a能被4整除，則a能被2整除；a能被2整除。所以a能被4整除。(1)設(shè)p：a能被4整除；q：a能被2整除。前提：p→q，p結(jié)論：q

推理的形式結(jié)構(gòu)：((p→q)∧p)→q(2)設(shè)p，q的含義同(1)。前提：p→q，q結(jié)論：p

推理的形式結(jié)構(gòu)：((p→q)∧q)→p解：解上述類型的推理問題，首先應(yīng)該將簡單命題符號化。然后分別寫出前提、結(jié)論、推理的形式結(jié)構(gòu)，接著進行判斷。

38二、形式推理系統(tǒng)定義1.21

一個形式系統(tǒng)I由下面四個部分組成：(1)非空的字符表集，記作A。(2)A中符號構(gòu)造的合式公式集，記作E。(3)E中一些特殊的公式組成的公理集，記作AX。(4)推理規(guī)則集，記作r。可以將形式系統(tǒng)I記為<A,E,AX,r>，其中<A,E>是I的形式語言系統(tǒng)，

<AX,r>為I的形式演算系統(tǒng)。形式系統(tǒng)自然推理系統(tǒng)公理推理系統(tǒng)39公理系統(tǒng)

命題邏輯討論的重點是重言式。而整個重言式的個數(shù)是無限的，一些重要的重言式就是邏輯規(guī)律。為了系統(tǒng)地、嚴(yán)謹(jǐn)?shù)匮芯康戎低评?，需要掌握這類規(guī)律的全體，將它們作為整體來考慮。因此就要求將這類重言式窮盡無遺地包括在一個整體之內(nèi)，公理系統(tǒng)就是這樣一個整體。40命題邏輯公理系統(tǒng)定義如下：1．字母表（1）命題變項符號：p，q，r，…

（2）聯(lián)結(jié)詞符號：┐,→

（3）括號和逗號：(,)，，2．合式公式，但限制聯(lián)結(jié)詞為┐,→。3.命題公理AxIα→(β→α)AxII(α→(β→γ))→((α→β)→(α→γ))AxIII(?α→β)→((?α→?β)→α)4.推理規(guī)則（MP）：由α及α→β推得β41例:├α→α證明：①(α→((α→α)→α)→((α→(α→α))→(α→α))AxII②α→((α→α)→α)AxI③(α→(α→α))→(α→α)MP①②④α→(α→α)AxI⑤α→αMP③④所以├α→α3.命題公理AxIα→(β→α)AxII(α→(β→γ))→((α→β)→(α→γ))AxIII(?α→β)→((?α→?β)→α)4.推理規(guī)則（MP）：由α及α→β推得β42證明：①(α→(β→γ))→((α→β)→(α→γ))AxII②[(α→(β→γ))→((α→β)→(α→γ))]→[((α→(β→γ))→(α→β))→((α→(β→γ))→(α→γ))]AxII③((α→(β→γ))→(α→β))→((α→(β→γ))→(α→γ))MP①②例:├((α→(β→γ))→(α→β))→((α→(β→γ))→(α→γ))3.命題公理AxIα→(β→α)AxII(α→(β→γ))→((α→β)→(α→γ))AxIII(?α→β)→((?α→?β)→α)4.推理規(guī)則（MP）：由α及α→β推得β43

當(dāng)引入一種推理規(guī)則或一個推理體系時，總會提出其推理功能的強弱問題。對所建立的公理系統(tǒng)也可以問是不是所有的重言式，或者說所有成立的定理都可以由該系統(tǒng)推導(dǎo)出來？這是一個重要的問題，常稱作完備性。命題邏輯的公理系統(tǒng)是完備的：只要φ1，φ2，…φn|=ψ成立，都存在φ1，φ2，…φn┣ψ的一個證明。完備性：為真皆可證；可靠性：可證皆為真。44自然推理系統(tǒng)定義如下：1．字母表

（1）命題變項符號：p,q,r,…,pi,qi,ri,…

（2）聯(lián)結(jié)詞符號：┐,∧,∨,→,

（3）括號和逗號：(,)，，2．命題公式3．推理規(guī)則形式系統(tǒng)自然推理系統(tǒng)

公理推理系統(tǒng)

公理推理系統(tǒng):

1.字母表2.合式公式3.命題公理4.推理規(guī)則三、自然推理系統(tǒng)45①前提引入規(guī)則：在證明的任何步驟上都可以引入前提。②結(jié)論引入規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以作為后繼證明的前提。③置換規(guī)則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又一個公式。

46

由重言蘊涵式和結(jié)論引入規(guī)則還可以導(dǎo)出以下各條推理定律。④假言推理規(guī)則(或稱分離規(guī)則)：由A→B和A，可得B。⑤附加規(guī)則：由A，可得A∨B。⑥化簡規(guī)則：由A∧B，可得A。⑦拒取式規(guī)則：由A→B和┐B，可得┐A。47⑧假言三段論規(guī)則：由A→B和B→C，可得A→C。⑨析取三段論規(guī)則：由A∨B和┐B，可得A。⑩構(gòu)造性二難推理：由A→B，C→D和A∨C，可得B∨D。⑾破壞性二難推理規(guī)則：由A→B，C→D和┐B∨┐D，可得┐A∨┐C。⑿合取引入規(guī)則：由A和B，可得A∧B。48四、自然推理系統(tǒng)的應(yīng)用舉例例1在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：

前提：A∨B,B→C,A→D,┐D

結(jié)論：C∧(A∨B)49例2前提:如果馬會飛或羊吃草,則母雞就會是飛鳥；如果母雞是飛鳥,那么烤熟的鴨子還會跑；烤熟的鴨子不會跑。

結(jié)論:羊不吃草。符號化上述語句：p:馬會飛,q:羊吃草,r:母雞是飛鳥,s:烤熟的鴨子會跑。前提:p∨q

r,r

s,

s結(jié)論:q50例3在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：

若數(shù)a是實數(shù)，則它不是有理數(shù)就是無理數(shù)；若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)；

a是實數(shù)且它不能表示成分?jǐn)?shù)。所以a是無理數(shù)。首先符號化上述語句：

p：a是實數(shù)。

q：a是有理數(shù)。

r：a是無理數(shù)。

s：a能表示成分?jǐn)?shù)。前提:?結(jié)論:?51證明：

①p∧┐s

前提引入

②p

①化簡

③┐s

①化簡

④p→(q∨r)前提引入

⑤q∨r

②④假言推理

⑥┐s→┐q

前提引入

⑦┐q

③⑥假言推理

⑧r

⑤⑦析取三段論前提：p→(q∨r),┐s→┐q,p∧┐s

結(jié)論：r

52自然推理系統(tǒng)的證明的兩個常用技巧：1）附加前提證明法；2）歸謬法。

附加前提法

有時推理的形式結(jié)構(gòu)具有如下形式:

（A1∧A2∧…∧Ak)

→(A→B)

上式中結(jié)論也為蘊涵式。此時可將結(jié)論中的前件也作為推理的前提，使結(jié)論只為B。即將上式化為下述形式:

(A1∧A2∧…∧Ak∧A)→B

53例4試用附加前提證明法證明(p→(q→s))∧(

r∨p)∧q

r→s

前提：p→(q→s),r∨p,q

結(jié)論：r→s

證明：(1)

r∨pp(2)rp

(附加前提)(3)pT(1)(2)(析取三段論)(4)p→(q→s)p(5)q→sT(3)(4)(假言推理)(6)qp(7)sT(5)(6)(假言推理)(8)r→sT(2)(7)

54例5在P中構(gòu)造下面推理的證明。

如果小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王去看電影。所以，當(dāng)小趙去看電影時，小李也去看電影。符號化上述語句：設(shè)p:小張去看電影；q:小王去看電影；

r:小李去看電影；s:小趙去看電影。前提：結(jié)論：證明：要求用附加前提證明法。(p∧q)→r,┐s∨p,qs→r55前提：(p∧q)→r,┐s∨p,q

結(jié)論：s→r

證明：用附加前提證明法。①s

附加前提

②┐s∨p

前提引入

③p

①②析取三段論

④(p∧q)→r前提引入

⑤q

前提引入

⑥p∧q

③⑤合取

⑦r

④⑥假言推理56歸謬法

在構(gòu)造形式結(jié)構(gòu)為(A1∧A2∧…∧Ak)→B的推理證明中，如果將┐B作為前提能推出矛盾來，比如說得出(A∧┐A)，則說明推理正確。其原因如下：

(A1∧A2∧…∧Ak)→B

┐(A1∧A2∧…∧Ak)∨B

┐(A1∧A2∧…∧Ak∧┐B)

若(A1∧A2∧…∧Ak∧┐B)為矛盾式，說明(A1∧A2∧…∧Ak)→B為重言式，即(A1∧A2∧…∧Ak)B,故推理正確。

57例6試證明(r

q)

(r

s)

(s

q)

(p

q)

p

(1)p

q前提引入

(2)p歸謬法(3)qT(1)(2)(假言推理)(4)rq前提引入

(5)rT(3)(4)(拒取式)(6)sq前提引入

(7)sT由(3)(6)(拒取式)(8)r

sT由(4)(7)(合取引入)(9)r

s

T由(8)(德.摩根律)(10)rs前提引入

(11)r

s

r

sT(9)(10)推出矛盾58第1章命題邏輯1.1現(xiàn)代邏輯學(xué)1.2命題及其表示法1.3命題公式與語句形式化1.4重言式1.5對偶與范式1.6其他聯(lián)結(jié)詞1.7命題演算的推理理論1.8命題演算中的歸結(jié)推理1.9應(yīng)用案例591.8命題演算中的歸結(jié)推理1930年Herbrand為定理證明建立了一種重要方法，奠定了機械定理證明的基礎(chǔ)。1965年J.Robinson建立了歸結(jié)原理，使機械證明定理達到了應(yīng)用階段。下面，引入歸結(jié)推理規(guī)則，討論歸結(jié)反演求解過程。60一、子句與子句集文字：一個文字或是一個原子(正文字)，或者是一個原子的否定(負文字)子句：一個子句是一組文字的析取。

子句集：一個子句的合取范式常常表示為一個子句的集合。

61例將公式?（P→Q）∨（R→P）化為子句集。解：(1)用等價的形式來消除蘊含符號，得?（?P∨Q）∨（?R∨P）(2)縮小?符號的轄域：（P∧?Q）∨（?R∨P）(3)轉(zhuǎn)換為合取范式：（P∨?R∨P）∧（?Q∨?R∨P）(4)消去重復(fù)的P：（P∨?R）∧（?Q∨?R∨P）(5)化為子句的集合{（P∨?R）,（?Q∨?R∨P）}62二、歸結(jié)設(shè)有兩個子句:（其中是子句，P是文字)從中消去互補對(即P和┐P)所得的新子句:R()=便稱作子句的歸結(jié)式。沒有互補對的兩子句沒有歸結(jié)式。63例計算下述子句的歸結(jié)式。(1)(2)(3)：Q，：(4)64例計算下述子句的歸結(jié)式。(1)65例計算下述子句的歸結(jié)式。(2)66例計算下述子句的歸結(jié)式。(3)67例計算下述子句的歸結(jié)式。：Q，：(4)68考慮子句集合S:S若子句集S是不可滿足的，則可以使用歸結(jié)規(guī)則由S產(chǎn)生空子句□。69

為了從一個合式公式