離散數學及其應用-第2版 課件匯 第1-6章 命題邏輯 -計數

第1章

命題邏輯1第一部分數理邏輯數理邏輯是研究推理邏輯規(guī)則的一個數學分支，它采用數學符號化的方法，給出推理規(guī)則來建立推理體系，進而討論推理體系的一致性、可靠性和完備（全）性等。2第1章命題邏輯1.1命題與聯(lián)結詞

1.2命題公式及其分類1.3命題演算的關系式1.4范式1.5命題演算的推理31.1命題與聯(lián)接詞1.1.1命題的概念定義命題的真值聯(lián)結詞4命題及其真值命題:是用陳述句表示的一個或者為真或者為假，但不能同時既為真又為假的判斷語句。命題的真值:判斷的結果,真（T或1）或假（F或0)真命題:真值為真的命題假命題:真值為假的命題5例題判斷下列句子中那些是命題？若是命題的，判斷其真值。

北京是中國的首都。2+3=6。3-x=5。請關上門。幾點了？除地球外的星球有生物。多漂亮的花?。∥抑唤o所有不給自己理發(fā)的人理發(fā)。6Y真Y假N真值不確定N疑問句N感嘆句N祈使句N悖論Y真值確定,但未知命題的表示引入英文字母表示任意的命題表示命題的符號稱為命題變量，通常用p、q、r...、P、Q、R...表示命題變量。命題變量沒有真值，只有表示一個確定的命題后，才有真值。如用p表示命題：“2+3=6”，這時p的真值為假（F），也可以用p表示命題：“2+3=5”,這時p的真值為真（T）。7簡單命題與復合命題簡單命題(原子命題):不能分解為更簡單的陳述語句的命題

簡單命題：“北京是中國的首都”。復合命題:由兩個或幾個簡單句和連詞組合而成的命題復合命題：“如果明天天氣好,我們就去爬山?！泵}的符號化：用英文字母或英文字母和聯(lián)結詞的組合表示命題，稱為命題的符號化。

聯(lián)結詞

-----連詞8聯(lián)結詞（一）否定

定義1.1.4

設p是一個命題，

p表示一個新命題“非p”。命題

p稱為p的否定。當且僅當p的真值為假時，

p的真值為真。

p的真值表：例如：p：今天是晴天。則

p：今天不是晴天?！胺恰?，“不”，“沒有”，“無”，“并非”等都可用

來表示。9p

pTFFT聯(lián)結詞（二）合取

定義1.1.5設p、q表示任意兩個命題,p

q可表示復合命題“p并且q”。當且僅當p和q的真值同時為真時，p

q的真值為真。p

q的真值表：例如：p:今天是晴天；q:今天去公園。p

q:今天是晴天并且今天去公園。

“和”，“與”，“也”，“并且”，“既...又...”，“不僅...而且...”，“雖然...但是...”等都可用

來表示。10p

qp

qT

TT

FF

TF

FTFFF聯(lián)結詞（三）析取

定義1.1.6設p、q表示任意兩個命題,p

q可表示復合命題“p或q”。當且僅當p和q的真值同時為假時，p

q的真值為假。p

q的真值表：例如：p:今天去看電影；q:今天去公園。p

q:今天去看電影或今天去公園。

“或”，“可能...可能...”，“或者...或者...”等可用

表示。11p

qp

qT

TT

FF

TF

FTTTF聯(lián)結詞自然語言中的“或”具有二義性：兼容性或和不兼容性或。兼容性或

電燈不亮是燈泡或線路有問題所致.不兼容性或（排斥或）

派小王或小李中的一人去開會

表示兼容性或例如：p:電燈不亮是燈泡有問題所致；q:電燈不亮是線路有問題所致。p

q:電燈不亮是燈泡或線路有問題所致。p：派小王去開會，q：派小李去開會，(p

q)

(

p

q):派小王或小李中的一人去開會12聯(lián)結詞（四）蘊涵

定義1.1.7設p、q表示任意兩個命題,p

q可表示復合命題“如果p，則q”。當且僅當p的真值為真，q的真值為假時，p

q的真值為假。p

q的真值表：例如：p:今天天氣晴朗；q:我們去海灘。p

q:如果今天天氣晴朗，我們就去海灘。13p

qp

qT

TT

FF

TF

FTFTT聯(lián)結詞蘊涵式：p

qp為蘊涵前件，q為蘊涵后件p是q的充分條件，q是p的必要條件表示：“如果p，則q”，“如果p，那么q”，“當p則q”，“p僅當q”等。假設：p：天氣晴朗；q：我們去海灘。如果天氣晴朗，我們去海灘。p

q僅當天氣晴朗，我們去海灘。q

p14聯(lián)結詞（五）等價

定義1.1.8設p、q表示任意兩個命題,p

q可表示復合命題“p當且僅當q”。當且僅當p和q的真值同時為真或同時為假時，p

q的真值為真。p

q的真值表：例如：p:兩個三角形是全等的。q：兩個三角形的三條對應邊相等。

p

q表示“兩個三角形是全等的當且僅當它們的三條對應邊相等”。15p

qp

qT

TT

FF

TF

FTFFT聯(lián)結詞等值式p

q表示p與q互為充分必要條件的邏輯關系表示形如“p當且僅當q”，“如果p，那么q，反之亦然”等的命題。16例題將下列命題符號化：雖然天氣很冷，老王還是來了。小王和小李是好朋友。小王和小李是好學生。小王或小李中的一人是游泳冠軍。只有你學過微積分或是數學系的學生，才可以選修這門課。如果明天早晨6點不下雨，我就去跑步。今天下雨與3+3=6。登陸服務器必須輸入一個有效的口令。2+3=5的充要條件是加拿大位于亞洲。17

解：雖然天氣很冷，老王還是來了。

設p：天氣很冷。q：老王來了。

則符號化為：p

q。小王和小李是好朋友。

這句雖然有連詞“和”，但是個簡單句，

可用p表示：小王和小李是好朋友。小王和小李是好學生。

設p：“小王是好學生”

q：“小李是好學生”，

則符號化為：p

q。18

解：小王或小李中的一人是游泳冠軍。設p：“小王是游泳冠軍”，q：“小李是游泳冠軍”

(p

q)

(

p

q)只有你學過微積分或是數學系的學生，才可以選修這門課。

設

p：你學過微積分；q：你是數學系的學生；r：你可以選修這門課。

r

(p

q)如果明天早晨6點不下雨，我就去跑步。設p：明天早晨6點下雨。q：我去跑步

符號化為：

p

q,或者：

q

p。19

解：今天下雨與3+3=6。設p：今天下雨。q：3+3=6。符號化為：p

q。登陸服務器必須輸入一個有效的口令。設p：登陸服務器,q:輸入一個有效的口令,符號化為：p

q。2+3=5的充要條件是加拿大位于亞洲。設p：2+3=5,q:加拿大位于亞洲,符號化為p

q。20聯(lián)結詞

（），

，

，

，

，

優(yōu)先級高

21括號有時被省略，如pq是p和q的合取，這里是省略了p的括號，即(p)q

pq

pp∧qp∨qp

qp

q0010011011011010001001101111聯(lián)結詞的真值表低例題將下列命題符號化，并指出它們的真值：1+1=2和2+3=61+1=2或猴子是飛禽若2+3=6，則猴子是飛禽。若猴子不是飛禽，則1+1=2和2+3=6。若2+3=6或猴子是飛禽，則1+1=2。2+3=6當且僅當猴子不是飛禽。22解

設p：1+1=2，q：2+3=6，r:猴子是飛禽

1+1=2和2+3=6,p

q，真值為0，

1+1=2或猴子是飛禽,

p

q，真值為1，

若2+3=6，則猴子是飛禽,

q

r，真值為1若猴子不是飛禽，則1+1=2和2+3=6。

r

p

q，真值為0，

23例題(續(xù)）例題（續(xù)）若2+3=6或猴子是飛禽，則1+1=2q

r

p，真值為1，

2+3=6當且僅當猴子不是飛禽。q

r，真值為024其它聯(lián)結詞定義1.1.9

設p和q是任意兩個命題,p

q可表示復合命題“p和q的與非”,

稱為與非聯(lián)結詞。命題p

q稱為p和q的與非式。當且僅當p和q的真值同時為真時，p

q的真值為假.p

q的真值表25p

qp

qT

TT

FF

TF

FFTTT其它聯(lián)結詞定義1.1.10設p、q是任意兩個命題,p

q可表示復合命題“p和q的或非”,

稱為或非聯(lián)結詞。命題p

q稱為p和q的或非式。當且僅當p和q的真值同時為假時，p

q的真值為真.p

q的真值表26p

qp

qT

TT

FF

TF

FFFFT其它聯(lián)結詞定義1.1.11設p和q是任意兩個命題,p

q可表示復合命題“p、q之中恰有一個成立”,

稱為異或（不兼容性或）聯(lián)結詞。命題p

q稱為p和q的異或式。當且僅當p和q的真值恰有一個為真時，p

q的真值為真。p

q的真值表27p

qp

qT

TT

FF

TF

FFTTF聯(lián)結詞的真值

28

pq

p∧qp

qp∨qp

q

p

q

p

q000

1

0

1

10010

1100110011001111

010

10聯(lián)結詞的真值p

q1101邏輯關系的數字門電路實現

用數字電路中的“非門”實現，

聯(lián)結詞用“與門”實現，

聯(lián)結詞用“或門”實現29非門與門或門

邏輯門電路符號命題公式的門電路實現命題公式G

(p

q)

p30邏輯電路聯(lián)結詞的應用布爾檢索中，聯(lián)結詞AND用于匹配同時包含兩個檢索項的記錄，聯(lián)結詞OR用于匹配至少包含一個檢索項的記錄，而聯(lián)結詞NOT用于排除某個特定的檢索項。如：把自然語言表示的命題翻譯成由命題變量和邏輯聯(lián)結詞組成的表達式，進行判斷和推理31例題

三個客人坐在餐館，服務生問：“每個人都要咖啡嗎？”，第一位客人回答：“我不知道?！苯又诙豢腿艘不卮穑骸拔也恢??！弊詈?，第三位客人回答：“不是每個人都要咖啡?！币粫?，服務生回來，將咖啡遞給需要的客人。請問服務生是如何判斷哪位客人需要咖啡的？解：根據三位客人的回答，服務生給第一位客人和第二為客人送來咖啡。32例題解：設p、q、r分別表示第一、二、三位客人要咖啡如果每個人都要咖啡，則p

q

r為真。根據第一個客人的回答“我不知道?！保丈梢耘袛鄍為真；根據第二個人的回答“我不知道?！笨梢耘袛鄎為真

；第三位客人的回答：“不是每個人都要咖啡。”說明r為假

因此，服務員可以斷定第一位和第二位客人要咖啡，第三位客人不要咖啡。331.2命題公式及其分類命題常元:代表特定簡單命題。命題變元:代表任意命題，取值為1(真)或0(假)的變量。定義1.2.1

命題公式（公式）的定義如下：每一個命題常元或命題變元都是命題公式。如果A是命題公式，則(

A)是命題公式。如果A和B都是命題公式，則(A

B)，(A

B)，(A

B)，(A

B)都是命題公式。一個由命題常元或命題變元、聯(lián)結詞和括號所組成的符號串是命題公式，當且僅當這個符號串是有限次應用上面的步驟得到的。34命題公式一個含有命題變元的命題公式的真值是不確定的.只有當公式中的所有命題變元被指定代表特定的命題時，命題公式才成為命題，其真值才唯一確定。

例如，命題公式p

q若指定p為“2是素數”，q為“3是奇數”

則p

q為真命題

若指定p為“2是素數”，q為“3是偶數”

則p

q為假命題

35公式的賦值定義1.2.2

若命題公式A含有的全部命題變元為p1,p2,…,pn，給p1,p2,…,pn指定一組真值，稱為對A的一個解釋或賦值。使A的真值為真的賦值稱為成真賦值，使A的真值為假的賦值稱為成假賦值。說明通常賦值與命題變元之間按下標或字母順序對應,即當A的全部命題變元為p1,p2,…,pn時,給A賦值

1

2…

n，是指p1=

1,p2=

2,…,pn=

n;當A的全部命題變元為p,q,r,…時,給A賦值

1

2

3…是指p=

1,q=

2,r=

3,…。36命題公式的真值表例給出公式的真值表

p

(q

r)(p

q)

(

p

q)

(

p

q)

q37真值表:命題公式在所有可能的賦值下的取值的列表含n個變項的公式有2n個賦值例題(續(xù))(1)p

(q

r)38

pqr

r

q

r

p

(q

r)000001010011100101110111101010100010001

0

11110010例題(續(xù))（2）(p

q)

(

p

q)39

pqp

q

p

q

(p

q)

(

p

q)00011011110101111111例題(續(xù))(3)

(

p

q)

q40

pq

p

p

q

(

p

q)

(

p

q)

q000110111100011110000000n個命題變元的不同的真值表有命題公式的分類定義1.2.3設A為一個命題公式(1)若A在它的各種賦值下取值均為真，則稱A為重言式或永真式。(2)若A在它的各種賦值下取值均為假，則稱A為矛盾式或永假式。(3)若至少存在一種賦值使A的真值為真，則稱A為可滿足式。例如(1)p

(q

r)為非重言式的可滿足式

（2）(p

q)

(

p

q)為重言式(3)

(

p

q)

q為矛盾式41命題公式的分類這三類公式之間有下面的關系：公式A永真，則

A永假，反之亦然。公式A是可滿足的，當且僅當

A不是永真式。公式A不是可滿足的，則一定是永假式。公式A不是永假式，則一定是可滿足的。判斷命題公式類型的方法：構造真值表421.3命題演算的關系式等價關系式定義1.3.1

設A和B是兩個命題(或命題公式)，若A

B是永真式，命題A和B稱為邏輯等價的，可記為A

B。說明：A

B是永真式，表示命題公式A和B在所有的賦值下都有相同的真值，也就是說命題公式A和B有相同的真值表?？梢杂谜嬷当砼卸▋蓚€命題是否等價。

43例題證明：p

q和

p

q等價。證列出真值表44所以有:p

q

p

qp

qp

q

p

p

q00111011111000011101例題證明p

(q

r)和(p

q)

(p

r)邏輯等價證列出真值表45所以有：p

(q

r)和(p

q)

(p

r)等價p

q

rp

(q

r)(p

q)

(p

r)0000000100010000110010000101111101111111等價關系式雙重否定律

p

p同一律p

0

p,p

1

p零元律p

1

1,p

0

0等冪律p

p

p,p

p

p交換律p

q

q

p,p

q

q

p結合律(p

q)

r

p

(q

r)(p

q)

r

p

(q

r)德摩根律

(p

q)

p

q

(p

q)

p

q吸收律p

(p

q)

p,p

(p

q)

p46基本等值式(續(xù))分配律p

(q

r)

(p

q)

(p

r)p

(q

r)

(p

q)

(p

r)排中律p

p

1矛盾律p

p

0蘊涵等值式p

q

p

q等價等值式p

q

(p

q)

(q

p)假言易位p

q

q

p等價否定等值式p

q

p

q歸謬論(p

q)

(p

q)

p47等價運算置換規(guī)則

若公式G中的一部分A(包含G中幾個連續(xù)的符號)是公式，稱A為G的子公式；用與A邏輯等價的公式B置換A不改變公式G的真值。

利用已知的等價關系式，將其中的子公式用和它等價的公式置換可以推出其它一些等價關系式，這一過程稱為命題的等價運算。利用命題的等價運算，可以判斷兩個命題是否等價判斷命題公式的類型命題公式的化簡等。48例題例1.3.3證明p

q

q

p解

p

q

p

q

蘊涵等價式

(

q)

p

交換律和雙重否定式

q

p

蘊涵等價式

條件命題：

p

q否命題：

p

q

逆命題：

q

p逆否命題：

q

p

條件命題和它的逆否命題等價49例題例1.3.4

利用命題的等價運算判斷下列公式的類型。（1）

p

(p

q)解

p

(p

q)

p

(

p

q)蘊涵等價式

p

(p

q)摩根律

(

p

p)

q

結合律

F

q

矛盾式

F

零元律

該式是永假式50例題（2）p

(p

q)解p

(p

q)

p

(

p

q)蘊涵等價式

(p

p)

(p

q)分配律

F

(p

q)零元律

p

q同一律該式是可滿足式51例題(3)(p

q)

(

q

p)解(p

q)

(

q

p)

(p

q)

(q

p)摩根律

(p

q)

(p

q)交換律

T排中律該式是永真式52例題化簡公式(p

q)

(p

q)解(p

q)

(p

q)

p

(q

q)分配律

p

T

排中律

p

同一律53例題對于圖1.3.1所示的邏輯電路，可否用更簡單的電路實現該邏輯關系？54解：F

(p

q)

(

p

q)

(p

q)

(p

q)

q

p

q全功能聯(lián)結詞集定義1.3.2設G是一個聯(lián)結詞的集合，若任意一個命題公式都可用G中的聯(lián)結詞構成的公式來表示，則稱G為全功能聯(lián)結詞集。如在G中去掉任何一個聯(lián)結詞，就不再具有這種特性，就稱其為最小全功能聯(lián)結詞集。{

、

、

}，{

、

}，{

、

}，{

、

}，{

}和{

}都是全功能聯(lián)結詞集，而{

、

}，{

、

}，{

、

}，{

}和{

}都是最小全功能聯(lián)結詞集。55A

B(A

B)(B

A)A

B

A

BA

B

(A

B)

(A

B)A

B

(A

B)A

B

(A)B

A

B例題證明：{

},{

}是最小全功能聯(lián)結詞集證：

p(p

p)

p

pp

q(p

q)(p

q)(p

q)(p

q)得證{

}是聯(lián)結詞完備集.對于{

}可類似證明.

只用一個

或

就可以實現聯(lián)結詞

，

，

、

、

表示的邏輯關系。在數字電子技術中，只用與非門或者或非門組成的電路就可以實現任何邏輯運算。56

與非門或非門例題用只有一種與非門的邏輯電路實現F

(p

q)

(

p

q)

(p

q)。解：F

(p

q)

(

p

q)

(p

q)

p

q

(

p

q)

(p

p)

q57對偶式定義1.3.3在僅含有聯(lián)結詞

，

，

的公式A中，將其中的

換成

，

換成

，T(或1)換成F(或0)，F(或0)換成T(或1)，其它符號不變得到的公式稱為A的對偶式，記為A*。p

q

和p

q

，p

q和p

q，

p

(q

r)和

p

(q

r)，p

q和p

q都互為對偶式58對偶式設A(p1，p2，…pn)和A*(p1，p2，…pn)互為對偶式，其中p1，p2，…pn是出現在A和A*中的全部的命題變元，則

A(p1，p2，…pn)

A*(

p1，

p2，…

pn)

A(

p1，

p2，…

pn)

A*(p1，p2，…pn)定理1.3.1設A和B為兩個命題公式，A和A*，B和B*互為對偶式，若A

B，則A*

B*。證明

因為A(p1，p2，…pn)

A*(

p1，

p2，…

pn)，B(p1，p2，…pn)

B*(

p1，

p2，…

pn)，若A(p1，p2，…pn)

B(p1，p2，…pn)，則

A*(

p1，

p2，…

pn)

B*(

p1，

p2，…

pn)，即A*(

p1，

p2，…

pn)

B*(

p1，

p2，…

pn)，則A*(p1，p2，…pn)

B*(p1，p2，…pn)。59例題求公式A

p

(

p

(q

q))的對偶式。解

公式A的對偶式A*為：A*

p

(

p

(q

q))重言式A的對偶式A*是矛盾式601.4范式1.4.1析取范式與合取范式1.4.2主析取范式與主合取范式極小項與極大項主析取范式與主合取范式主范式的用途61析取范式與合取范式定義1.4.1一個命題公式具有形式A1

A2

….

.An(n

1)，其中A1，A2，

….，An

都是由命題變元或其否定所組成的合取式，則稱該命題公式為析取范式。

如：

p

(p

q

r)

(

p

q)

q是析取范式。定義1.4.2一個命題公式具有B1

B2

….

.Bn(n

1)，其中B1，B2，

….，Bn都是由命題變元或其否定所組成的析取式，則稱該命題公式為合取范式。

如：(p

q

r)

(

p

q)

q是合取范式。62范式存在定理定理1.4.1

任何一個命題公式都存在著與之等值的析取范式與合取范式.證

設G為任意一個公式，將公式化成只含

、

、

3個聯(lián)結詞的形式。將否定聯(lián)結詞內移或消去。利用分配律、交換律和結合律等將公式歸納為析取范式和合取范式。通過上面3個步驟可以求出與G等價的析取范式和合取范式，任意一個命題公式都存在著與之等價的析取范式和合取范式。

以上亦是求析取范式和合取范式的步驟。63例題求命題公式(p

(p

q))

q

的析取范式和合取范式。解

(p

(p

q))

q

(p

(

p

q))

q

(p

p)

(p

q)

q

析取范式

(p

q)

q

析取范式

q

析取范式

(p

q)

q

合取范式

(p

q)

(

p

q)合取范式

q

合取范式注意:公式的析取范式與合取范式不惟一.64主析取范式與主合取范式定義1.4.3

含有n個命題變元的合取式中，若每個命題變元與其否定不同時出現，而二者之一必出現且僅出現一次，這樣的合取式稱為極小項。定義1.4.4含有n個命題變元的析取式中，若每個命題變元與其否定不同時出現，而二者之一必出現且僅出現一次，這樣的析取式稱為極大項。說明:(1)由n個命題變元產生的不同的極大項和極小項的個數均為2n個。(2)每個極小項在它的2n個賦值中只有一個成真賦值(3)每個極大項在它的2n個賦值中只有一個成假賦值

65主析取范式與主合取范式(續(xù))66

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

rm000

或

m0

m001

或

m1m010

或

m2m011

或

m3m100

或

m4m101

或

m5m110

或

m6m111

或

m73個命題變元的極小項

一般地，n個命題變元形成的極小項可表示為：主析取范式與主合取范式(續(xù))3個命題變元的極大項67p

q

rp

q

rp

q

rp

q

r

p

q

r

p

q

r

p

q

r

p

q

rM000

或

M0M001

或

M1M010

或

M2M011

或

M3M100

或

M4M101

或

M5M110

或

M6M111

或

M7

一般地，n個命題變元形成的極小項可表示為：主析取范式與主合取范式定義1.4.5如果含n個命題變元的命題公式的析取范式的每個合取式全是極小項，則稱該析取范式為主析取范式。定理1.4.2任何命題公式的主析取范式都是存在的，并且是唯一的。證明

給定命題公式A，1.求A的析取范式A′，A′的形式為A1

A2

….

.An(n

1)；；

2.若A′中的某個簡單合取式Ai不是極小項，則補入在Ai中沒有出現的變元。例如，若pi和

pi都不在Ai中，則將Ai展成如下形式：Ai

Ai

(pi

pi)

(Ai

pi)

(Ai

pi);3.重復步驟2)，直到所有的簡單合取式都含有所有的命題變元或它的否定式；4.消去重復出現的命題變項、矛盾式及重復出現的極小項。

按上述步驟求得的就是A的主析取范式。

唯一性證明（略）

68例題求命題公式(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)

(

p

r)

(p

q

r)析取范式

((

p

q)

(r

r))

((

p

r)

(q

q))

(p

q

r)

(

p

q

r)

(

p

q

r)

(

p

r

q)

(

p

r

q)

(p

q

r)

(

p

q

r)

(

p

q

r)

(

p

q

r)

(p

q

r)

m0

m1

m2

m7

(0，1，2，7)69主析取范式例題試由p

q

r的真值表求它的主析取范式。

p

q

r的真值表

解：p

q

r的成真賦值為001，011，101，110，111p

q

r

(1，3，5，6，7)(

p

q

r)

(

p

q

r)

(p

r

q)

(p

r

q)

(p

q

r)一個命題公式的主析取范式中的每一個極小項的成真賦值就是該公式的一個成真賦值70p

q

rp

q

r00000101001110010111011101010111主析取范式與主合取范式定義1.4.6如果含n個命題變元的命題公式的析取范式的每個合取式全是極小項，則稱該析取范式為

主合取范式。定理1.4.3任何命題公式的主合取范式都是存在的，并且是唯一的。證明

給定命題公式A，1.求A的合取范式B′，B′的形式為B1

B2

….

.Bn(n

1)；2.若B′中的某個析取式Bi不是極大項，則補入在Bi中沒有出現的變元。例如，若pi和

pi都不在Bi中，則將Bi展成如下形式：

Bi

Bi

(pi

pi)

(B

pi)

(B

pi);3.重復步驟2)，直到所有的簡單析取式都含有所有的命題變元或它的否定式；4.消去重復出現的命題變項、重言式及重復出現的極大項。

按上述步驟求得的就是A的主合取范式。

唯一性證明（略）

71例題求命題公式(p

(q

r))

(p

q

r)的主合取范式。

解

(p

(q

r))

(p

q

r)

(

p

(

q

r))

(p

q

r)

(

p

q)

(

p

r)

(

q

r

p)合取范式

((

p

q)

(r

r))

((

p

r)

(q

q))

(p

q

r)

(

p

q

r)

(

p

q

r)

(

p

q

r)

(p

q

r)

主合取范式

M3

M4

M5

M6

(3，4，5，6)

m0

m1

m2

m7

(0，1，2，7)72主析(合）取范式的用途（1）判斷命題公式是否等價例1.4.5判斷(

p

q)

(

q

r)

(

r

p)和(p

q)

(q

r)

(r

p)是否等價。解

(

p

q)

(

q

r)

(

r

p)

(M100

M101)

(M010

M110)

(M001

M011)

M4

M5

M2

M6

M1

M3

(1,2,3,4,5,6)(p

q)

(q

r)

(r

p)

(M010

M011)

(M001

M101)

(M100

M110)

M2

M3

M1

M5

M4

M6

(1,2,3,4,5,6)所以,(

p

q)

(

q

r)

(

r

p)和(p

q)

(q

r)

(r

p)等價。73主析(合）取范式的用途(2)求公式的成真賦值和成假賦值設公式A含n個命題變項,A的主析取范式有s個極小項,則A有s個成真賦值,它們是極小項下標的二進制表示,其余2n-s個賦值都是成假賦值例如

(p

q)

r

m0

m2

m4

m5

m6

成真賦值:000,010,100,101,110;成假賦值:001,011,11174主析（合）取范式的用途(續(xù))(3)判斷公式的類型設A含n個命題變項，則A為重言式當且僅當A的主析取范式含2n個極小項A為矛盾式當且僅當A的主析取范式不含任何極小項,記作0A為可滿足式當且僅當A的主析取范式中至少含一個極小項A為矛盾式當且僅當A的主合取范式含2n個極大項A為重言式當且僅當A的主合取范式不含任何極大項,記作1

A為可滿足式當且僅當A的主合取范式不是包含全部2n個極大項75例題判斷公式G

(p

q)

(

q

p)是否重言式？解G

(p

q)

(

q

p)

(

p

q)

(q

p)

(p

q)

q

p

m10

(m01

m11)

(m00

m01)

m2

m1

m3

m0

m1

(0，1，2，3)公式G

(p

q)

(

q

p)是重言式76例題例1.4.7

設計一個集成學習系統(tǒng)，該系統(tǒng)綜合三個基學習器的分類預測（正類或負類），以投票的方式決定輸入樣本的預測類別，即在超過半數基學習器給出正類的情況下判定該樣本為正類，否則為負類。設計滿足上述條件的集成學習分類器，并嘗試以邏輯電路圖的方式畫出該分類器。77例題（續(xù)）

7800000010010001111000101111011111

例題

一種簡單的三人表決器，表決者每人座位旁有一個按鈕，表決時，若表示同意則按按鈕，若不同意不按按鈕；表決結果超過半數時，喇叭發(fā)出聲音。設計滿足上述條件的表決器。解

三個表決者的按鈕分別為p，q，r，按按鈕為1，不按按鈕為0，喇叭為A，喇叭發(fā)聲為1，不發(fā)聲為0。A

(

p

q

r)

(p

q

r)

(p

q

r)

(p

q

r)

(p

q)

(p

r)

(q

r)

(p

(q

r))

(q

r)79p

q

rA00000101001110010111011100010111例題

某單位選派A、B、C三位業(yè)務骨干去進修，由于工作需要，選派要滿足如下條件：若A去，則C同去。若B去，則C不能去。若C不去，則A或B可以去。問可以有哪些選派方案？80例題（續(xù)）解

設p:派A去，q:派B去，r:派C去。81有3個成真賦值，所以有3種選派方案：A和B不去，C去；A和C不去，B去；A和C去，B不去。該公式的成真賦值就是可行的選派方案。寫出該公式的主析取范式：由已知條件可得：

1.5命題演算的推理1.5.1推理理論1.5.2推理證明方法82推理理論定義1.5.1設A和B是兩個命題公式，當且僅當命題A

B是重言式時(即A

B

T時)，稱從A可推出B，或A蘊涵B，或B是前提A的結論，可以表示成A

B。一般地，推理的前提可以有多個，若(A1

A2

An)

B是重言式，則稱由前提A1，A2，

，An可推出結論B，可表示為(A1

A2

An)

B。83例題判斷下列推理是否正確：p

(p

q)

q(p

q)

q

p解

寫出p

(p

q)

q和(p

q)

q

p的真值表。

p

(p

q)

q

正確(p

q)

q

p不正確

84p

qp

(p

q)

q(p

q)

q

p0011011010111111例題證明“如果牛吃草，則馬會飛；馬不會飛，所以牛不吃草?！笔钦_的推理。證明

設：p：牛吃草；q：馬會飛。前提符號化為：p

q，

q，結論符號化為：

p。

而(p

q)

q

p

((p

q)

q)

p

(p

q)

q

p

(p

q)

(p

q)T所以，

p是p

q和

q的有效結論，這個推理是正確的。注意：推理時，只要推理過程的每一步驟都遵循正確的推理規(guī)則，推出的結論都稱為有效結論，推理都是有效的。85推理定律

86定理（CP規(guī)則）若H1，H2，...，Hm和P推出Q，則H1，H2，...，Hm推出P

Q。證明

從定理的假設有：H1

H2

...

Hm

P

Q

根據定義1.5.1，即有：H1

H2

...

Hm

P

Q

T令H1

H2

...

Hm

H，則

H

P

Q

(H

P)

Q

H

P

Q

H

(P

Q)

T所以H

P

Q，即：H1

H2

...

Hm

P

Q87推理證明方法真值表法等價演算法演繹法附加前提證明法間接推演法(歸謬法)歸結證明法881、真值表法通過寫出真值表判斷A

B的類型，若A

B是重言式，則由前提A可以退出結論B。例證明前提p

q和

p

r，可以推出結論q

r。證明

根據定義1.5.1，只需證明(p

q)

(

p

r)

q

r是重言式。列出真值表：

89

p

qrp

q

p

rq

r(p

q)

(

p

r)

q

r0000101001011101011110111111100100110111111101011111111190由真值表可知，(p

q)

(

p

r)

q

r是重言式，所以前提p

q和

p

r，可以推出結論q

r。2、等價演算法利用命題的等值演算判斷A

B的類型，若A

B是重言式，則由前提A可以退出結論B。證明q是

p和

p

q的結論。證明

p

(p

q)

q

(

p

(p

q))

q

p

(

p

q)

q

p

q

q

T913、演繹法演繹法是從前提（假設）出發(fā)，依據公認的推理規(guī)則和推理定律，推導出一個結論來。命題演算推理系統(tǒng)：推理規(guī)則

推理定律基本等價公式92推理規(guī)則

1）前提引入規(guī)則

在推導的過程中，可隨時引入前提集合中的任意一個前提。2）結論引入規(guī)則

在推導的過程中所得到的結論都可做為后續(xù)推導的前提。3）置換規(guī)則

在推導的過程中，命題公式的子公式都可以用等值的公式置換。4）CP規(guī)則(附加前提規(guī)則)如果推出的結論形為P

Q，則可以把P放到前提中去，設法推出Q即可。93例題證明：前提“今天下午有課且今天比昨天冷；只有今天下午沒有課，我們才去游泳；如果我們不去游泳，則我們打藍球；如果我們打籃球，我們就會感到精力充沛?！蓖瞥鼋Y論“我們感到精力充沛”是正確的。證明：設：p：今天下午有課，q：今天比昨天冷，r：我們去游泳，s：我們打籃球，h：我們感到精力充沛。則前提為：p

q，r

p，

r

s，s

h，結論是：h

94例題

證明：

步驟

公式

理由p

q

前提引入p(1)化簡r

p

前提引入

r(2)，(3)拒取式

r

s

前提引入s(4)，(5)假言推理s

h

前提引入

h(6)，(7)假言推理

95例題證明

r

s是p

(q

r)，p?q的結論。證明：

步驟

公式

理由p

q

前提引入p(1)化簡q(1)化簡p

(q

r)前提引入

q

r(2)，(4)假言推理

r(3)，(5)假言推理r?s(6)附加

r

s(7)置換規(guī)則964、附加前提證明法證明r

s是p

(q

s)，

r

p，q的結論。證明

步驟

公式

理由r

附加前提引入

r

p

前提引入p(1)(2)析取三段論p

(q

s)前提引入q

s(3)(4)假言推理q

前提引入s(6)(5)假言推理975、間接推演法(歸謬法)間接推演法就是把要推出的結論否定后與原來的前提一起使用推出矛盾結論的證明方法。

定義1.5.2設H1，H2，.....Hr是r個命題公式。若H1

H2

.....

Hr是矛盾式，則稱H1，H2，.....Hr是不相容的，否則稱H1，H2，.....Hr是相容的。98例題用間接法證明：

p是p

q，q

r，r

s的結論證明：

步驟

公式

理由

p

否定結論p(1)雙重否定p

q

前提引入

q(2)，(3)假言推理q

r

前提引入

r(4)，(5)析取三段論r

s

前提引入r(7)化簡F(8)，(6)合取996、歸結證明法歸結規(guī)則:(p

q)?(

p

r)

q

r歸結證明法：前提和結論必須被表示為子句，對于非子句的語句，可以用一個或多個等價的是子句的語句替換它子句是變元或其否定的析取，如p

q、

p

r等是子句100歸結證明法證明：如果小張守門或小李上場，則A隊獲勝；或者A隊未獲勝，或者A隊成為聯(lián)賽第一名；A隊沒有成為聯(lián)賽第一名。因此小張沒有守門并且小李沒有上場。證明

設p:小張守門;q:小李上場；r:A隊獲勝；s:A隊成為聯(lián)賽第一名.前提：(p?q)

r，

r?s，

s結論：

p?

q前提中的(p?q)

r

(p

q)

r

(

p

r)?(

q

r)，所以用兩個子句

p

r和

q

r代替(p?q)

r。結論為兩個子句：

p和

q101例題用歸結規(guī)則證明如下：步驟

公式

理由

p

r

前提引入

r

s

前提引入

p

s(1)，(2)歸結規(guī)則

q

r

前提引入

q

s(2)，(4)歸結規(guī)則

s

前提引入

p(3)，(6)歸結規(guī)則

q(5)，(6)歸結規(guī)則

p?

q(7)，(8)合取102離散數學及其應用103第2章謂詞邏輯2.1謂詞邏輯的基本概念2.2謂詞合式公式2.3謂詞公式的解釋和分類2.4謂詞演算的關系式2.5前束范式2.6謂詞演算的推理1042.1謂詞邏輯的基本概念2.1.1個體詞和謂詞定義2.1.1個體詞是指可以獨立存在的客體，可以是一個具體的事物或抽象的概念，是原子命題所描述的對象。

謂詞是用來說明個體的性質或個體間的關系。例如，小王是個大學生

3大于2105謂詞個體詞個體詞個體詞謂詞謂詞

形如“b是A”類型的命題可表達為A(b)；表示多個個體間關系的命題，可表達為B(a，b)，或P(a，b，c)定義2.1.2

和一個個體相聯(lián)系的謂詞稱為一元謂詞，和二個個體相聯(lián)系的謂詞稱為二元謂詞，和n個個體相聯(lián)系的謂詞稱為n元謂詞。

個體常元

表示具體的或特定的個體，如a，b，c，

等；個體變元

表示抽象的或泛指的個體，如x，y，z，

等。

謂詞常項

表示具體性質或關系的謂詞，R(a)表示a是人；

謂詞變項

表示抽象或泛指的謂詞

，如：P(a)表示a具有P性質。106謂詞表達式和命題函數定義2.1.3

一個原子命題可以用一個謂詞常項P和幾個個體常元，如a，b，c，

，表示成P(a，b，c，

)的形式。稱P(a，b，c，

)為原子命題或命題的謂詞表達式。

一個謂詞常項P和幾個個體變元如x，y，z，

表示成P(x，y，z，

)的形式，稱為命題函數，其中的個體變元可以代表任意一個個體。注意：命題的謂詞表達式是有真值的，命題函數的真值是不確定的。107例題寫出下列命題的謂詞表達式。

1.小王和小李是大學生。解：設A(x)：x是大學生。a：小王，b：小李。

A(a)

A(b)2.

北京是中國的首都。解：設F(x，y)：x是y的首都。a：北京，b：中國。F(a，b)3.如果你來，他就走。解：設P(x)：x來。Q(x)：x走。a：你，b：他。

P(a)

Q(b)108例題（續(xù)）4.如果3

2，2

1，則3

1。解：設B(x，y)：x

y。a：3，b：2，c：1。則

：

B(a，b)

B(b，c)

B(a，c)武漢位于北京和廣州之間。解：設Q(x，y，z)：y位于x和z之間。a：北京，b：廣州，c：武漢。Q(a，c，b)109個體域定義2.1.4命題函數中，個體變元的取值范圍稱為個體域或論述域。

個體域可以是有限的，也可以是無限的。把宇宙中一切事物作為對象的的集合稱為全總個體域。通常，沒有特別說明時，個體變元的論述域是指全總個體域。如：A(x)表示：x是大學生。個體域：華工計科1班學生，則A(x)是永真式。個體域：華工附中1班學生，則A(x)是永假式。個體域：xx公司員工，其中有些是大學生，有些不是大學生，則對有些人，A(x)為真，對有些人，A(x)為假。110例題給出執(zhí)行語句“If

P(x)then