離散數(shù)學-第二章命題邏輯

第二章

命題邏輯

數(shù)理邏輯是用數(shù)學方法研究思維規(guī)律的一門學科。所謂數(shù)學方法是指:用一套數(shù)學的符號系統(tǒng)來描述和處理思維的形式與規(guī)律。因此,數(shù)理邏輯又稱為符號邏輯。本章介紹數(shù)理邏輯中最基本的內(nèi)容命題邏輯。首先引入命題、命題公式等概念。然后,在此基礎(chǔ)上研究命題公式間的等值關(guān)系和蘊含關(guān)系,并給出推理規(guī)則,進行命題演繹。主要內(nèi)容如下：2.1命題的概念和表示2.2邏輯聯(lián)結(jié)詞2.3命題演算的合適公式2.4等價與蘊含2.5對偶與范式2.6命題演算的推理理論2.1命題的概念和表示

一、命題的概念命題：是能分辨真假的陳述句。

例1判斷下列語句是否是命題。（1）空氣是人生存所必需的。（2）請把門關(guān)上。（3）南京是中國的首都。（4）你吃飯了嗎？（5）x=3。（6）啊，真美呀！(7)明年春節(jié)是個大晴天。

解語句（1）,（3）,（5），(7)是陳述句

（1）、（3）、(7)是命題

用真值來描述命題是“真”還是“假”。分別用“1”和“0”表示

命題用大寫的拉丁字母A、B、C、……P、Q、……或者帶下標的大寫的字母來表示。

例2

判斷下列陳述句是否是命題。

P：地球外的星球上也有人；Q：小王是我的好朋友；

解

P、Q是命題

原子命題：由簡單句形成的命題。復(fù)合命題：由一個或幾個原子命題通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題。

例3

A：李明是三好學生。

B：李明既是三好學生又是足球隊員

C:明天天氣晴朗.

D：張平或者正在釣魚或者正在睡覺。

E：如果明天天氣晴朗，那么我們舉行運動會。

二、原子命題和復(fù)合命題。

解

A、C是原子命題

B、D、E是復(fù)合命題2.2邏輯聯(lián)結(jié)詞

1.否定“?”

定義2.2.1設(shè)P是一個命題，則P的否定是一個復(fù)合命題，稱為P的否命題，記作“?P”(讀作“非P”)。

例4設(shè)P：上海是一個城市；Q：每個自然數(shù)都是偶數(shù)。則有?

P：上海不是一個城市;

?Q：并非每個自然數(shù)都是偶數(shù)。

P

?P

10

01

命題P取值為真時，命題?P取值為假；命題P取值為假時，命題?P取值為真。

2．合取“∧”定義2.2.2設(shè)P和Q是兩個命題，則P和Q的合取是一個復(fù)合命題，記作“P∧Q”（讀作“P且Q”）。

例5設(shè)P：我們?nèi)タ措娪啊：房間里有十張桌子。則P∧Q表示“我們?nèi)タ措娪安⑶曳块g里有十張桌子。”PQP∧Q000010100111當且僅當命題P和Q均取值為真時，P∧Q才取值為真。3.析取“∨”定義2.2.3設(shè)P和Q是兩個命題，則P和Q的析取是一個復(fù)合命題，記作“P∨Q”（讀作“P或Q”）。PQP∨Q000011101111

例6設(shè)命題P：他可能是100米賽跑冠軍；

Q：他可能是400米賽跑冠軍。則命題P∨Q表示：他可能是100米或400米賽跑的冠軍。當且僅當P和Q至少有一個取值為真時，P∨Q取值為真。

4.蘊含“→”

定義2.2.4

設(shè)P和Q是兩個命題，則它們的條件命題是一個復(fù)合命題，記作“P→Q”（讀作“如果P，則Q”）。PQP→Q001011100111

例9將命題“如果我得到這本小說，那么我今夜就讀完它?！狈柣?。

解令P：我得到這本小說；Q：我今夜就讀完它。于是上述命題可表示為P→Q。

例8若P：雪是黑色的；Q：太陽從西邊升起；R：太陽從東邊升起。則P→Q和P→R所表示的命題都是真的.

當P為真，Q為假時，P→Q為假，否則P→Q為真。5．等值“

”

定義2.2.5設(shè)P和Q是兩個命題，則它們的等值命題是一個復(fù)合命題，稱為等值式復(fù)合命題，記作“P

Q”（讀作“P當且僅當Q”）。

當P和Q的真值相同時,P

Q取真,否則取假。

PQPQ001010100111

例10非本倉庫工作人員，一律不得入內(nèi)。

解令P：某人是倉庫工作人員；

Q：某人可以進入倉庫。

則上述命題可表示為P

Q。

例11黃山比喜馬拉雅山高，當且僅當3是素數(shù)令P：黃山比喜馬拉雅山高；Q：3是素數(shù)本例可符號化為P

Q

從漢語的語義看，P與Q之間并無聯(lián)系，但就聯(lián)結(jié)詞

的定義來看，因為P的真值為假，Q的真值為真，所以P

Q的真值為假。

對于上述五種聯(lián)結(jié)詞，應(yīng)注意到：復(fù)合命題的真值只取決于構(gòu)成它的各原子命題的真值，而與這些原子命題的內(nèi)容含義無關(guān)。命題符號化利用聯(lián)結(jié)詞可以把許多日常語句符號化?；静襟E如下：

（1）從語句中分析出各原子命題，將它們符號化

（2）使用合適的命題聯(lián)結(jié)詞，把原子命題逐個聯(lián)結(jié)起來，組成復(fù)合命題的符號化表示。

例12用符號形式表示下列命題。（1）如果明天早上下雨或下雪，那么我不去學校（2）如果明天早上不下雨且不下雪，那么我去學校。（3）如果明天早上不是雨夾雪，那么我去學校。（4）只有當明天早上不下雨且不下雪時，我才去學校。

解令P：明天早上下雨；

Q：明天早上下雪；

R：我去學校。

（1）（P∨Q）→

?R；（2）（?P

∧?Q）→R；（3）?(P∧Q）→R

（4）R→（?P

∧?Q）

例13．將下列命題符號化（1）派小王或小李出差；（2）我們不能既劃船又跑步；（3）如果你來了，那么他唱不唱歌將看你是否伴奏而定；（4）如果李明是體育愛好者，但不是文藝愛好者，那么李明不是文體愛好者；（5）假如上午不下雨，我去看電影，否則就在家里看書。解（1）令P：派小王出差；Q：派小李出差。命題符號化為P∨Q。

（2）令P：我們劃船；Q：我們跑步。則命題可表示為?(P∧Q）。

（3）

令P：你來了；Q：他唱歌；R：你伴奏。則命題可表示為P→（Q

R）

（4）

令P：李明是體育愛好者；Q：李明是文藝愛好者。則命題可表示為（P∧?Q）→?（P∧Q）

（5）

令P：上午下雨；Q：我去看電影；R：我在家讀書。則命題可表示為（?P→Q）∧（P→R）。

練習2-21.

判斷下列語句哪些是命題，若是命題，則指出其真值。（1）只有小孩才愛哭。（2）X+6=Y（3）銀是白的。（4）起來吧，我的朋友。(是假)

(不是)(是真)

(不是)

2．將下列命題符號化（1）我看見的既不是小張也不是老李。

解

令P：我看見的是小張；Q：我看見的是老李。

則該命題可表示為?P∧?Q

（2）如果晚上做完了作業(yè)并且沒有其它的事，他就會看電視或聽音樂。

解令P：他晚上做完了作業(yè)；Q：他晚上有其它的事；

R：他看電視；S：他聽音樂。則該命題可表示為（P∧?Q）→（R∨S）2.3命題演算的合適公式

一、命題公式的概念

1.命題常元

一個表示確定命題的大寫字母。

2．命題變元一個沒有指定具體內(nèi)容的命題符號。

一個命題變元當沒有對其賦予內(nèi)容時，它的真值不能確定，一旦用一個具體的命題代入，它的真值就確定了。3.命題公式

命題公式（或簡稱公式）是由0、1和命題變元以及命題聯(lián)結(jié)詞按一定的規(guī)則產(chǎn)生的符號串。

定義2.3.1

（命題公式的遞歸定義。）（1）0，1是命題公式；（2）命題變元是命題公式；（3）如果A是命題公式，則?A是命題公式；（4）如果A和B是命題公式，則（A∨B），（A∧B）,(A→B）,(A

B）也是命題公式；有限次地利用上述（1）—（4）而產(chǎn)生的符號串是命題公式。例1

判斷下列符號串是否為命題公式。（1）P→(Q∧PR）；（2）（P∨Q）→（?（Q∧R））

解（1）不是命題公式。（2）是命題公式。

4.代入實例定義2.3.2設(shè)A和B是兩個命題公式，如果將A中的某些命題變元用命題公式進行代換便可得到B，并且此種代換滿足：（1）被代換的是命題變元；（2）如果要代換某個命題變元，則要將該命題變元在A中的一切出現(xiàn)進行代換

（3）代換必須同時獨立地進行則稱B是A的一個代入實例例2

設(shè)A=P→(Q∧P）,判斷下列命題公式是否是A的代入實例：

B=S∧R→(Q∧(S∧R)）C=S∧R→(Q∧P）

解

B是；C不是二、真值指派

命題公式代表一個命題，但只有當公式中的每一個命題變元都用一個確定的命題代入時，命題公式才有確定的真值，成為命題。

定義2.3.3設(shè)A(P1，P2，…,Pn

)是一個命題公式，P1，P2，…,Pn是出現(xiàn)于其中的全部命題變元，對P1，P2，…,Pn分別指定一個真值,稱為對P1，P2，…,Pn公式A的一組真值指派。

列出命題公式A在P1，P2，…,Pn的所有2n種真值指派下對應(yīng)的真值，這樣的表稱為A的真值表。

例3給出公式F=(（P∨Q）

（Q∧R）)

(P∧?R）的真值表。解公式F的真值表如下：PQR?RP∨QQ∧R(P∨Q)→(Q∧R)P∧?RF000001010011100101110111101010100011111100010001110100010000101000101110

三、公式類型

定義2.3.5如果對于命題公式F所包含的命題變元的任何一組真值指派，F(xiàn)的真值恒為真，則稱公式F為重言式（或永真公式），常用“1”表示。相反地，若對于F所包含的命題變元的任何一組真值指派，F(xiàn)的真值恒為假，則稱公式F為矛盾式（或永假公式），常用“0”表示。如果至少有一組真值指派使公式F的真值為真，則稱F為可滿足公式。

例4構(gòu)造下列命題公式的真值表，并判斷它們是何種類型的公式（1）（?P

Q）

?（P

Q）；（2）（Q→P）∧（?P∧Q）；（3）（（P∨Q）→（Q∧R））→（P∧?R）。

解令F1=（?P

Q）

?（P

Q）F2=（Q→P）∧（?P∧Q）

F1和F2的真值表如下：PQ?P?P

QP

Q?(P→Q)F1Q→P?P∧QF20010101100011101101010010111001100101100由上可知：F1是重言式,F2是矛盾式。

2.4等價與蘊含一、命題公式的等價關(guān)系

定義2.4.1

設(shè)A和B是兩個命題公式,P1,P2,…,Pn

是所有出現(xiàn)于A和B中的命題變元，如果對于P1,P2,…,Pn

的任一組真值指派，A和B的真值都相同,則稱公式A和B等價，記為A

B,稱A

B為等價式。注意：（1）符號“

”與“

”的區(qū)別與聯(lián)系。

（2）

可以驗證等價關(guān)系滿足：自反性：對任意公式A，有A

A。

對稱性：對任意公式A，B，若A

B，則B

A。

可傳遞性：對任意公式A、B、C，若A

B，B

C，則A

C。

（3）當A是重言式時，A

1；當A是矛盾式時，則A

0。定理2.4.1

A

B當且僅當A

B是永真公式。二、基本的等價式設(shè)P、Q、R是命題變元，下表中列出了24個最基本的等價式:編號

公式E1E1ノE2E2ノE3E3ノE4E4ノE5E5ノE6E6ノE7E7ノ

P∨Q

Q∨P交換律

P∧QQ∧P

交換律

(P∨Q)∨RP∨(Q∨R)結(jié)合律(P∧Q)∧RP∧(Q∧R)

結(jié)合律

P∧(Q∨R)(P∧Q)∨(P∧R)分配律

P∨(Q∧R)(P∨Q)∧(P∨R)分配律

P∨0P

同一律

P∧1P

同一律

P∨P

1

互否律

P∧P

0

互否律

（

P）

P

雙重否定律

P∨PP

等冪律

P∧PP

等冪律

編號

公式E8E8ノE9E9ノE10E10ノE11E12E13E14E15P∨11

零一律

P∧00

零一律P∨（P∧Q）P

吸收律P∧（P∨Q）P

吸收律

（P∨Q）P∧

Q

德.摩根定律

（P∧Q）P∨Q

德.摩根定律PQ

P∨QP

Q(P∧Q)∨(P∧

Q)P(Q

R)

(P∧Q)

RP

Q(P

Q)∧(Q

P)

PQ

Q

P三、等價式的判別有兩種方法：真值表方法，命題演算方法1、真值表方法例1用真值表方法證明E10：

(P

Q)

P

Q

解令：A=

(P

Q)，B=

P

Q，構(gòu)造A，B

以及A

B的真值表如下：

PQP

Q

(P

Q)

P

Q

P

QA

B000111110110100111100101由于公式A

B所標記的列全為1，因此A

B。

10100001例2用真值表方法證明E11：P

Q

P

Q解令A(yù)=P

Q，B=

P

Q

構(gòu)造A，B以及A

B的真值表如下：PQ

P

P

QP

QA

B001111011111100001由于公式A

B所標記的列全為1，因此A

B.110111

例3用真值表方法判斷P

Q

P

Q是否成立.

解令A(yù)=P

Q，B=

P

Q

構(gòu)造A，B以及A

B的真值表PQ

P

Q

P

QP

QA

B0011111011001001100

由于公式A

B所標記的列不全為1，A

B不是永真公式，因此A

B不成立。101100111

(1)代入規(guī)則

重言式的代入實例仍是重言式。2．命題演算方法例如F=（P

Q）

（

Q

P）是重言式，若用公式A∧B代換命題變元P得公式

F1=（（A∧B）

Q）

（

Q

（A∧B）），F(xiàn)1仍是重言式。注意：因為A

B當且僅當A

B是重言式。所以，若對于等價式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等價式。

(2)置換規(guī)則設(shè)C是命題公式A的一部分（即C是公式A中連續(xù)的幾個符號），且C本身也是一個命題公式，則稱C為公式A的子公式。

例如設(shè)公式A=（

P∨Q）

（（P

Q）∨（R∧

S））。

則

P∨Q，P

Q，（P

Q）∨（R∧

S）等均是A的子公式，

但

P∨，P

和

Q等均不是A的子公式，

置換規(guī)則

設(shè)C是公式A的子公式，C

D。如果將公式A中的子公式C置換成公式D之后，得到的公式是B，則A

B。

(3)

等價演算等價演算是指利用已知的一些等價式，根據(jù)置換規(guī)則、代入規(guī)則以及等價關(guān)系的可傳遞性推導(dǎo)出另外一些等價式的過程。

由代入規(guī)則知前述的基本等價式，不僅對任意的命題變元P，Q，R是成立的，而且當P，Q，R分別為命題公式時，這些等價式也成立例2證明命題公式的等價關(guān)系：（P

Q）∧（R

Q）

（P∨R）

Q；證明（P

Q）∧（R

Q）

（

P∨Q）∧(

R∨Q)E11

（

P∧

R）∨QE3ˊ(分配律)

(P∨R)∨QE10(德.摩根定律)

(P∨R)

QE11

所以（P

Q）∧（R

Q）

（P∨R）

Q例3證明下列命題公式的等價關(guān)系(P

Q)

(

P

(

P

Q))

P

Q證明(P

Q)

(

P

(

P

Q))

(P

Q)

((

P

P)

Q) E2(結(jié)合律)

(P

Q)

(

P

Q)E7(等冪律)

(

P

Q)

(P

Q)

E1(交換律)

P

(Q

(P

Q))E2(結(jié)合律)

P

QE

1，E9(交換律，吸收律)例4判別下列公式的類型。（1）Q∧

(

P

（

P∧Q）)（2）（P

Q）∧

P解（1）Q∧

（

P

（

P∧Q））

Q∧

（P∨（

P∧Q））E11,E6

Q∧

（（P∨

P）∧（P∨Q））E3ノ

Q∧

（1∧（P∨Q））

E5

Q∧

（P∨Q）E4ノ

Q∧

P∧

Q

E10

（Q∧

Q）∧

PE1ノ,E2

0E5ノ,E8ノ所以Q∧

(

P

(

P∧Q))是矛盾式。（2）（P

Q）∧

P

（

P∨Q）∧

P

E11

P

E9ノ于是該公式是可滿足式。

三、命題公式的蘊含關(guān)系

定義2.4.2設(shè)A，B是兩個公式，若公式A

B是重言式，即A

B

1，則稱公式A蘊含公式B，記作A

B。稱“A

B”為蘊含式。

注意：

（1）

符號“

”和“

”的區(qū)別和聯(lián)系（2）A

B是偏序關(guān)系即自反性：A

A

反對稱：若A

B，B

A，則A

B

傳遞性：若A

B，B

C，則A

C

（3）若A、B和C是三個命題公式，且A

B，A

C，則A

B∧C

（4）若A、B和C是三個命題公式，且A

C，B

C，則A∧B

C定理2.4.2

A

B當且僅當A

B是永真公式。四、基本的蘊含式編號蘊含式I1P

Q

PI2P

Q

QI3P

P

QI4Q

P

QI5

P

P

QI6Q

P

QI7

(P

Q)

PI8

(P

Q)

Q設(shè)P、Q、R是命題變元，下表中列出了16個最基本的蘊含式。編號蘊含式I9P

Q

P

Q

或表示為：P、QP

QI10

P

(P

Q)

Q

P、(PQ)

QI11P

(P

Q)

QP、PQ

QI12

Q

(P

Q)

P

Q、PQ

PI13(P

Q)

(Q

R)

P

R

PQ、QR

P

RI14(P

Q)

(P

R)

(Q

R)

RPQ、PR、QR

RI15P

Q

(P

R)

(Q

R)I16P

Q

(P

R)

(Q

R)五、蘊含式的判別判定“A

B”是否成立的問題可轉(zhuǎn)化為判定A

B是否為重言式，有下述判定方法：

（1）真值表；（2）等價演算；（3）假定前件A為真；（4）假定后件B為假。

1.真值表方法例4證明I14：(（P∨Q）∧（P

R）∧（Q

R）)

R

證明令公式

F=（（P∨Q）∧（P

R）∧（Q

R））

R，

其真值表如下：

公式F對任意的一組真值指派取值均為1，故F是重言式。PQRP∨QP→RQ→R(P∨Q)∧(P→R）∧（Q→R）F0000010100111001011101110011111111110101110111010001010111111111

2.

等價演算方法

例5

證明I11：P∧（P

Q）

Q證明

（P∧（P

Q））

Q

（P∧（

P∨Q））∨Q

E11

（

P∨

（

P∨Q））∨E10ノ

（

P∨Q）∨

（

P∨Q）

E2

1代入規(guī)則,E5

因此P∧（P

Q）

Q

3.

假定前件A真假定前件A為真，檢查在此情況下，其后件B是否也為真。

ABA

B001011100111

例6證明

I12:

Q∧（P

Q）

P證明令前件

Q∧（P

Q）為真，則

Q為真,且P

Q為真。于是Q為假，因而P也為假。由此

P為真。故蘊含式I12

成立。

4、

假定后件B假假定后件B為假，檢查在此情況下，其前件A是否也為假.

例7證明蘊含式(P

Q)

(R

S)

(P

R)

(Q

S)

證明令后件(P

R)

(Q

S)為假，則P

R為真，Q

S為假,于是P、R均為真，而Q和S至少一個為假。由此可知P

Q與R

S中至少一個為假,因此(P

Q)

(R

S)為假.故上述蘊含式成立。練習2-41．判斷下列等值式是否成立

（1）（P

Q）∧（R

Q）

（P∨R）

Q

（2）

（P

Q）

（P∧

Q）∨（

P∧Q）解

（1）（P

Q）∧（R

Q）

（

P∨Q）∧（

R∨Q）E11

（

P∧

R）∨Q

E3ノ

（P∨R）∨Q

E10（2）（P∧

Q）∨（

P∧Q）

(（

P∨Q）∧（

Q∨P）)E6，E10ノ

(（P

Q）∧（Q

P）)

E11

（P

Q）E14

（P∨R）

QE112．判定蘊含式P

（Q

R）

（P

Q）

（P

R）是否成立

解假定后件（P

Q）

（P

R）為假，則P

Q為真，P

R為假。由P

R為假,得P為真，R為假。

又P

Q為真，故得Q為真。于是P為真，Q

R為假。從而P

（Q

R）為假。因此蘊含式成立。2.5

功能完備集、其他聯(lián)結(jié)詞問題：為了能構(gòu)造任何意義的命題公式，究竟需要定義多少邏輯聯(lián)結(jié)詞？A0=FA1=P∧QA2=P∨

QA3=PA4=

P∧QA5=QA6=（P∧

Q）∨（

P∧Q）A7=P∨Q定義2.5.1設(shè)S是一個由一些邏輯聯(lián)結(jié)詞組成的集合，若對于任意給定的命題公式，總可以找到一個僅含有S中的邏輯聯(lián)結(jié)詞的命題公式與之等價，則稱S是一個聯(lián)結(jié)詞功能完備集。定義2.5.2設(shè)S是一個聯(lián)結(jié)詞功能完備集，若S中的任一聯(lián)結(jié)詞都不能用S中的其他聯(lián)結(jié)詞等價表達，則稱S是一個極小的聯(lián)結(jié)詞功能完備集。

例{∧，},{∨，}是極小的聯(lián)結(jié)詞功能完備集2.6

對偶與范式一、對偶定義2.6.1設(shè)A是一個僅含有聯(lián)結(jié)詞

、∧、和∨的命題公式，在A中用∨代替∧，用∧代替∨，用T代替F,用F代替T，所得的命題公式稱為A的對偶式，記為A*。

例如：P∧Q∨

R和（P

∨

Q）∧R互為對偶式

P∧Q∨R的對偶式是(

P∨Q)∧R定理2.6.1設(shè)A是一個僅含有聯(lián)結(jié)詞

、∧、和∨的命題公式，P1，P2.....Pn是出現(xiàn)于其中的全部命題變元，則

A(P1，P2.....Pn)

A*(P1，

P2.....

Pn)A(P1，

P2.....

Pn)A*(P1，P2.....Pn)定理2.6.2設(shè)A和B是兩個僅含有聯(lián)結(jié)詞

、∧、和∨的命題公式，如果A

B，則A*

B*。二、范式1、析取范式和合取范式

定義2.6.2

一個命題公式若具有P1*∧P2*∧…∧Pn*的形式（n≥1），其中Pi*是命題變元Pi或其否定?Pi，則稱其為質(zhì)合取式。

例如,?P∧Q∧R∧S是由命題變元P、Q、R、S組成的一質(zhì)合取式。

定義2.6.3一個命題公式若具有P1*∨P2*∨…∨Pn*（n≥1）的形式，其中P*i是命題變元Pi或是其否定?Pi，則稱其為質(zhì)析取式。

例如,?Q∨P∨?R是由命題變元P、Q、R組成的一質(zhì)析取式。定理2.6.3（1）一質(zhì)合取式為永假式的充分必要條件是，它同時包含某個命題變元P及其否定?P。

（2）一質(zhì)析取式為永真式的充分必要條件是，它同時包含某個命題變元P及其否定?P。

證明（2）

必要性：假設(shè)A=P1*∨P2*∨…∨Pn*為一質(zhì)析取式，且A為一永真式。

(反證法)假設(shè)A式中不同時包含任一命題變元及其否定，則在A中，當Pi*為Pi時指派Pi取0，當Pi*為?Pi時，指派Pi取1。(i=1,2,…n).這樣的一組真值指派使A的真值取0，這與A為永真式矛盾。

充分性：設(shè)A含命題變元Pi和?Pi，而Pi∨?Pi是永真式，由結(jié)合律和零一律，A的真值必為1，故A也是永真式。

定義2.6.4質(zhì)合取式的析取稱為析取范式。即具有A1∨A2∨…∨An(n≥1)的形式的公式，其中Ai是質(zhì)合取式。

例如，F(xiàn)1=P∨(P∧Q)∨R∨(

P∧

Q∧R)是一析取范式。

定義2.6.5

質(zhì)析取式的合取稱為合取范式。即具有A1∧A2∧…∧An(n≥1)的形式的公式，其中Ai是質(zhì)析取式。

例如，F(xiàn)2=

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

Q∨R)是一合取范式。

F3=(

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

R)也是一合取范式。二、求公式的析取范式和合取范式

任何一個命題公式都可以變換為與它等值的析取范式或合取范式。按下列步驟進行：（1）利用E11，E12和E14消去公式中的運算符“

”和“

”；(2)利用德?摩根定律將否定符號“

”向內(nèi)深入，使之只作用于命題變元；（3）利用雙重否定律E6將

(

P)置換成P；（4）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。例1求F1=(P∧(Q

R))

S的合取范式和析取范式

解

F1

(P∧(

Q∨R))∨S

E11

P∨

(

Q∨R)∨S

E10ノ

P∨(Q∧

R)∨S(析取范式)E10,E6又F1

P∨(Q∧

R)∨S

(

P∨S)∨(Q∧

R)

E1,E2

(

P∨S∨Q)∧(

P∨S∨

R)（合取范式）E3ノ

另外由F1

(

P∨S∨Q)∧(

P∨S∨

R)

(

P∧(

P∨S∨

R))∨(S∧(

P∨S∨

R))∨

(Q∧(

P∨S∨

R))

E3

P∨S∨(Q∧

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

R)（析取范式）E9,E13

例2

求F2=

(P∨Q)

(P∧Q)的析取范式、合取范式。

解

F2

(

(P∨Q)

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

(P∨Q))

E14

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

(P∧Q)∨

(P∨Q))E11,E6

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

P∨

Q∨(

P∧

Q))E2,E10,E10

(P∨Q)∧(

P∨

Q)（合取范式）E2,E9(P∧(

P∨

Q))∨(Q∧(

P∨

Q))

E3

(P∧

P)∨(P∧

Q)∨(

P∧Q)∨(Q∧

Q)（析取范式）E3

定理2.6.4（1）公式A為永真式的充分必要條件是，A的合取范式中每一質(zhì)析取式至少包含一對互為否定的析取項。

三、利用范式判定公式類型

證明（2）必要性（用反證法）：假設(shè)A＝A1∨A2∨…∨An中某個Ai不包含一對互為否定的合取項，（2）公式A為永假式的充分必要條件是，A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項。則由定理知，Ai不是矛盾式。于是存在一組真值指派使Ai取值為真。對同一組真值指派，A的取值也必為真，這與A是矛盾式不符，假設(shè)不成立。

充分性：假設(shè)任一Ai(1≤i≤n)中含有形如P∧P合取式，其中P為命題變元。于是由定理知，每一Ai(1≤i≤n)都為矛盾式，因此A1∨A2∨…∨An必為矛盾式，即A為矛盾式。因此A的析取范式中每一質(zhì)合取式至少包含一對互為否定的合取項。

例3

判別公式A=P

(P∧(Q

P))是否為重言式或矛盾式。

解

A

P∨(P∧(

Q∨P))E11

P∨(P∧

Q)∨(P∧P)(析取范式)E3根據(jù)定理2.6.4，A不是矛盾式。又A

P∨(P∧(

Q∨P))

（

P∨P）∧（

P∨

Q∨P)（合取范式）E3ノ由定理2.6.4知，A是重言式。

例4利用范式判斷公式P

(P

Q)的類型。

解

P

(P

Q)

(P

(P

Q))

(

P

(P

Q)) E12

(P

Q)

(

P

(

P

Q)) E

10

(P

Q)

P(析取范式)E

9由定理，該公式不是永假公式。

(P

P)

(

P

Q)（合取范式） E1，E

3

由定理，該公式也不是永真公式。由上可知，該公式是一可滿足公式。又P

(P

Q)

(P

Q)

P

四、主析取范式和主合取范式

（一）極小項、極大項

定義2.6.6

設(shè)有命題變元P1，P2，…,Pn，形如的命題公式稱為是由命題變元P1，P2，…，Pn所產(chǎn)生的極小項。而形如的命題公式稱為是由命題變元P1，P2，…，Pn所產(chǎn)生的極大項。其中Pi*為Pi或為

Pi(i=1,2,…n).例如,P1∧P2∧P3，

P1∧P2∧

P3均是由P1，P2，P3所產(chǎn)生的極小項。

P1∨

P2∨P3是由P1，P2，P3產(chǎn)生的一個極大項

常用mk(0≤k≤2n-1)表示極小項，其中k為二進制t1t2...tn對應(yīng)的十進制。且若Pi*為

Pi,

ti=0.否則Pi*為1。

例如，三個命題變元P,Q,R共形成八個極小項

m0=

P∧

Q∧

R，m1=

P∧

Q∧R，m2=

P∧Q∧

Rm3=

P∧Q∧R，m4=P∧

Q∧

R，m5=P∧

Q∧Rm6=P∧Q∧

R，m7=P∧Q∧R

常用Mk(0≤k≤2n-1)表示極大項，其中k為二進制t1t2...tn對應(yīng)的十進制。且若Pi*為

Pi,

ti=1.否則Pi*為0。

M0=P

Q

R，M1=P

Q

R，M2=P

Q

RM3=P

Q

R，M4=

P

Q

R，M5=

P

Q

RM6=

P

Q

R，M7=

P

Q

R極小項、極小項的簡記：極小項的性質(zhì)：1）每一個極小項mk在與其下標相對應(yīng)的真值指派下真值為真，而在其余2n-1種真值指派下真值為假。2）任意兩個不同的極小項的合取式是一個永假式。3）全部2n個極小項的析取式是一個重言式極大項的性質(zhì)：1）每一個極大項Mk在與其下標相對應(yīng)的真值指派下真值為假，而在其余2n-1種真值指派下真值為真。2）任意兩個不同的極大項的析取式是一個永真式3）全部2n個極大項的合取式是一個矛盾式

定義2.6.7由不同極小項所組成的析取式，稱為主析取范式。

定義7-18由不同極大項所組成的合取式，稱為主合取范式。

例如(

P1

P2

P3)

(

P1

P2

P3)

(P1

P2

P3)是一個主析取范式。(P1

P2

P3)

(P1

P2

P3)

(

P1

P2

P3)

(

P1

P2

P3)是一個主合取范式。五、求公式的主析取范式和主合取范式(一）真值表法

例：(

PQ)(PR)

(

PQR)(

PQR)(PQR)(PQR)

m2m3m5m7

(PQR)(PQR)(

PQR)(

PQR)

M0M1M4M6

定理2.6.5

每一個不為永假的命題公式F（P1,P2,…,Pn）必與一個由P1，P2，…，Pn所產(chǎn)生的主析取范式等價。

永真公式的主析取范式包含所有2n個最小項。

永假公式的主析取范式是一個空公式。用0表示。

定理2.6.6

每一個不為永真的公式F(P1,P2,…,Pn）

必與一個由P1,P2,…,Pn所產(chǎn)生的主合取范式等價。永假公式的主合取范式包含所有2n個最大項。永真公式的主合取范式是一空公式，用1表示。

例4求公式F1=P

(P

(Q

P))和公式

F2=(P

Q)

(P

Q)的主析取范式.解

F1

P∨(P∧(

Q∨P))E11

P∨(P∧

Q)∨(P∧P)E3

(

P∧(Q∨

Q))∨(P∧

Q)∨(P∧(Q∨

Q))

E7ノ,E4ノ,E5

(

P∧Q)∨(

P∧

Q)∨(P∧

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

Q)

E3

(

P∧Q)∨(

P∧

Q)∨(P∧

Q)∨(P∧Q)

E1,E7

(二）公式演算法對任一給定的公式除了用求范式時的四個步驟外，還要利用同一律、等冪律、互否律、分配律等進一步將質(zhì)合取式（質(zhì)析取式）變換為最小項（最大項）的形式。F2

(P

Q)

(P

Q)

(

P

Q)

(P

Q)

E11

(

P

P

Q)

(Q

P

Q) E3

0

0E

1,E

5

0例5

求公式F1=(P

Q)

(P

Q)和

公式F2=P

(P

(Q

P))的主合取范式F1

(

P

Q)

(P

Q) E11

(

P

Q)

(P

(Q

Q))

(

Q

(P

P)) E

5,E4

(

P

Q)

(P

Q)

(P

Q)

(P

Q)

(

P

Q)E

3

(P

Q)

(P

Q)

(

P

Q)

(

P

Q)

E

7

解

F2

P∨(P∧(

Q∨P))

E11

(

P∨P)∧(

P∨

Q∨P)

E3ノ

1∧1E5,E1

1

六、利用主范式判定公式類型

1.利用主析取范式判定(1)若公式F(P1,P2，…，Pn)的主析取范式包含所有2n個最小項，則F是永真公式。(2)若F的主析取范式是一空公式且為0，則F是永假公式。(3)否則，F(xiàn)為可滿足的公式。

2

利用主合取范式判定

(1)若公式F（P1,P2,…,Pn）的主合取范式包含所有2n個最大項，則F是永假公式。

(2)若F的主合取范式是一空公式且為1，則F是永真公式。

(3)否則，F(xiàn)為可滿足公式例6

求公式F=(Q

(P

Q))

P的主范式并判定公式的類型.

解

(1)求F的主析取范式F

(Q

(

P

Q))

P

Q

(P

Q)

P

(

Q

(P

P))

(P

Q)

(P

(Q

Q))

（P

Q)

(

P

Q)

(P

Q)

(P

Q)

(P

Q)

(P

Q)

(P

Q)

(

P

Q)由此可知F是可滿足公式。(2)求F的主合取范式F

（

Q

(P

Q))P

P

Q由前分析和舉例可知：僅需求出公式F的任一種主范式即可判定F的類型。練習2-6

1．判斷公式F=(

P∨

Q)→(P?

Q)是否為重言式或矛盾式？解F

(

P∨

Q)∨((P→

Q)∧(

Q→P))E11

(P∧Q)∨((

P∨

Q)∧(Q∨P))

E10,E6,E11

(P∧Q)∨((

P∧(Q∨P))∨(

Q∧(Q∨P)))

E3

(P∧Q)∨(

P∧Q)∨(

P∧P)∨(

Q∧Q)∨(

Q∧P)E3

(P∧Q)∨(

P∧Q)∨(

Q∧P)

E5ノ,E8

F的主析取范式既非空公式，又未包含22=4個項，故F不是重言式和矛盾式，只是可滿足式。

2.7命題演算的推理理論

3、如果甲是冠軍，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實是甲已得冠軍，可知_______不能得亞軍。

例1、如果天不下雨，我就去看電影；我沒有去看電影，說明_________2、如果李敏出差到學校，若王軍不生病，則王軍一定去看望李敏。如果李敏出差到長沙，那么李敏一定來學校。王軍沒有生病。所以，___________

一、推理

推理是由已知的命題得到新命題的思維過程。

定義2.7.1

設(shè)A和B是兩個命題公式，如果A

B，即如果命題公式A

B為重言式，則稱B是前提A的結(jié)論或從A推出結(jié)論B。一般地設(shè)H1，H2，…,Hn和C是一些命題公式,若蘊含式H1∧H2∧…∧Hn

C

(*)成立，則稱C是前提集合{H1，H2，…,Hn}的結(jié)論，或稱從前提H1，H2，…,Hn能推出結(jié)論C。有時也記作H1，H2，…,Hn

C

1、真值表法

對于命題公式中所有命題變元的每一組真值指派作出該公式的真值表，看是否為永真。PQ00011011解

構(gòu)造其真值表如下：?P?QP→Q（P→Q）∧P(（P→Q）∧P)→Q11101101010100100111例1

考察結(jié)論C是否是下列前提H1，H2的結(jié)論。（1）H1：P→Q，H2：P，C：Q二、如何判斷由一個前提集合能否推出某個結(jié)論?

（2）H1：P→Q，H2：?P，C：?Q解

構(gòu)造其真值表如下：?P?QP→Q（P→Q）∧?P1111101101000010(（P→Q）∧?P)→?Q1011PQ00011011

2、真值演算方法

例證明

分析根據(jù)題意，需證明證明

3、“形式證明”方法

（1）基本述語

形式證明：一個描述推理過程的命題序列，其中每個命題或者是已知的命題，或者是由某些前提所推得的結(jié)論，序列中最后一個命題就是所要求的結(jié)論，這樣的命題序列稱為形式證明。有效的證明：如果證明過程中的每一步所得到的結(jié)論都是根據(jù)推理規(guī)則得到的，則這樣的證明稱作是有效的。有效的結(jié)論：通過有效的證明而得到結(jié)論，稱作是有效的結(jié)論。

合理的證明：一個證明是否有效與前提的真假沒有關(guān)系。如果所有的前提都是真的，那么通過有效的證明所得到的結(jié)論也是真的。這樣的證明稱作是合理的。合理的結(jié)論：一個結(jié)論是否有效與它自身的真假沒有關(guān)系。通過合理證明而得到的結(jié)論稱作合理的結(jié)論。

(2)推理規(guī)則前提引用規(guī)則(P規(guī)則）：在證明的任何步驟上都可以引用前提。結(jié)論引用規(guī)則（T規(guī)則）：在證明的任何步驟上所得到的結(jié)論都可以在其后的證明中引用。置換規(guī)則：在證明的任何步驟上，命題公式的子公式都可以用與它等價的其它命題公式置換。代入規(guī)則：在證明的任何步驟上，重言式中的任一命題變元都可以用一命題公式代入，得到的仍是重言式。例2證明R∧（P∨Q）是前提P∨Q，Q→R，P→S，?S的結(jié)論。

所以P∨Q，Q→R，P→S，?S

R∧（P∨Q)編號

公式依據(jù)（1）（2）（3）（4）（5）（6）（7）（8）P→S?S?PP∨QQQ→RRR∧（P∨Q）

PPT（1），（2）,IPT（3），（4）,IPT（5），（6）,IT（4），（7）,I例3證明R→S是前提P→（Q→S），?R∨P和Q的有效結(jié)論。

證明

編號公式依據(jù)

(1)(2)(3)(4)(5)(6)(7)(8)(9)

?R∨PR→PP→（Q→S）R→（Q→S）

?R∨（?Q∨S）

?Q∨（?R∨S）Q

?R∨SR→S

PT（1）,EPT（2），（3）,IT（4）,ET（5）,EPT（6），（7）,IT（8）,E

練習用形式證明方法證明：（1）?P∨?Q是前提（P∧Q）→R，?R∨S，?S的結(jié)論。編號公式依據(jù)（1）（2）（3）（4）（5）（6）（7）?R∨S?S?R(P∧Q）→R?（P∧Q）∨R?（P∧Q）?P∨?QPPT（1），（2）,IPT（4）,ET（4），（5）,IT（6）,E

因此，（P∧Q）→R，?R∨S，?S

?P∨?Q

CP規(guī)則：利用永真蘊含式：要證明PQ→

R，則等價于證明