離散數(shù)學(xué)及其應(yīng)用-第2版 課件全套 第1-12章 命題邏輯 - 格和布爾代數(shù)

第1章

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

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

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

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

聯(lián)結(jié)詞

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

定義1.1.4

設(shè)p是一個(gè)命題，

p表示一個(gè)新命題“非p”。命題

p稱為p的否定。當(dāng)且僅當(dāng)p的真值為假時(shí)，

p的真值為真。

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

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

來表示。9p

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

定義1.1.5設(shè)p、q表示任意兩個(gè)命題,p

q可表示復(fù)合命題“p并且q”。當(dāng)且僅當(dāng)p和q的真值同時(shí)為真時(shí)，p

q的真值為真。p

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

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

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

來表示。10p

qp

qT

TT

FF

TF

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

定義1.1.6設(shè)p、q表示任意兩個(gè)命題,p

q可表示復(fù)合命題“p或q”。當(dāng)且僅當(dāng)p和q的真值同時(shí)為假時(shí)，p

q的真值為假。p

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

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

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

表示。11p

qp

qT

TT

FF

TF

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

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

派小王或小李中的一人去開會(huì)

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

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

q)

(

p

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

定義1.1.7設(shè)p、q表示任意兩個(gè)命題,p

q可表示復(fù)合命題“如果p，則q”。當(dāng)且僅當(dāng)p的真值為真，q的真值為假時(shí)，p

q的真值為假。p

q的真值表：例如：p:今天天氣晴朗；q:我們?nèi)ズ?。p

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

qp

qT

TT

FF

TF

FTFTT聯(lián)結(jié)詞蘊(yùn)涵式：p

qp為蘊(yùn)涵前件，q為蘊(yùn)涵后件p是q的充分條件，q是p的必要條件表示：“如果p，則q”，“如果p，那么q”，“當(dāng)p則q”，“p僅當(dāng)q”等。假設(shè)：p：天氣晴朗；q：我們?nèi)ズ?。如果天氣晴朗，我們?nèi)ズ?。p

q僅當(dāng)天氣晴朗，我們?nèi)ズ?。q

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

定義1.1.8設(shè)p、q表示任意兩個(gè)命題,p

q可表示復(fù)合命題“p當(dāng)且僅當(dāng)q”。當(dāng)且僅當(dāng)p和q的真值同時(shí)為真或同時(shí)為假時(shí)，p

q的真值為真。p

q的真值表：例如：p:兩個(gè)三角形是全等的。q：兩個(gè)三角形的三條對(duì)應(yīng)邊相等。

p

q表示“兩個(gè)三角形是全等的當(dāng)且僅當(dāng)它們的三條對(duì)應(yīng)邊相等”。15p

qp

qT

TT

FF

TF

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

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

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

設(shè)p：天氣很冷。q：老王來了。

則符號(hào)化為：p

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

這句雖然有連詞“和”，但是個(gè)簡(jiǎn)單句，

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

設(shè)p：“小王是好學(xué)生”

q：“小李是好學(xué)生”，

則符號(hào)化為：p

q。18

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

(p

q)

(

p

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

設(shè)

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

r

(p

q)如果明天早晨6點(diǎn)不下雨，我就去跑步。設(shè)p：明天早晨6點(diǎn)下雨。q：我去跑步

符號(hào)化為：

p

q,或者：

q

p。19

解：今天下雨與3+3=6。設(shè)p：今天下雨。q：3+3=6。符號(hào)化為：p

q。登陸服務(wù)器必須輸入一個(gè)有效的口令。設(shè)p：登陸服務(wù)器,q:輸入一個(gè)有效的口令,符號(hào)化為：p

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

q。20聯(lián)結(jié)詞

（），

，

，

，

，

優(yōu)先級(jí)高

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

pq

pp∧qp∨qp

qp

q0010011011011010001001101111聯(lián)結(jié)詞的真值表低例題將下列命題符號(hào)化，并指出它們的真值：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當(dāng)且僅當(dāng)猴子不是飛禽。22解

設(shè)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當(dāng)且僅當(dāng)猴子不是飛禽。q

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

設(shè)p和q是任意兩個(gè)命題,p

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

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

q稱為p和q的與非式。當(dāng)且僅當(dāng)p和q的真值同時(shí)為真時(shí)，p

q的真值為假.p

q的真值表25p

qp

qT

TT

FF

TF

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

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

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

q稱為p和q的或非式。當(dāng)且僅當(dāng)p和q的真值同時(shí)為假時(shí)，p

q的真值為真.p

q的真值表26p

qp

qT

TT

FF

TF

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

q可表示復(fù)合命題“p、q之中恰有一個(gè)成立”,

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

q稱為p和q的異或式。當(dāng)且僅當(dāng)p和q的真值恰有一個(gè)為真時(shí)，p

q的真值為真。p

q的真值表27p

qp

qT

TT

FF

TF

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

28

pq

p∧qp

qp∨qp

q

p

q

p

q000

1

0

1

10010

1100110011001111

010

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

q1101邏輯關(guān)系的數(shù)字門電路實(shí)現(xiàn)

用數(shù)字電路中的“非門”實(shí)現(xiàn)，

聯(lián)結(jié)詞用“與門”實(shí)現(xiàn)，

聯(lián)結(jié)詞用“或門”實(shí)現(xiàn)29非門與門或門

邏輯門電路符號(hào)命題公式的門電路實(shí)現(xiàn)命題公式G

(p

q)

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

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

q

r為真。根據(jù)第一個(gè)客人的回答“我不知道?！?，服務(wù)生可以判斷p為真；根據(jù)第二個(gè)人的回答“我不知道?！笨梢耘袛鄎為真

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

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

命題公式（公式）的定義如下：每一個(gè)命題常元或命題變?cè)际敲}公式。如果A是命題公式，則(

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

B)，(A

B)，(A

B)，(A

B)都是命題公式。一個(gè)由命題常元或命題變?cè)?、?lián)結(jié)詞和括號(hào)所組成的符號(hào)串是命題公式，當(dāng)且僅當(dāng)這個(gè)符號(hào)串是有限次應(yīng)用上面的步驟得到的。34命題公式一個(gè)含有命題變?cè)拿}公式的真值是不確定的.只有當(dāng)公式中的所有命題變?cè)恢付ù硖囟ǖ拿}時(shí)，命題公式才成為命題，其真值才唯一確定。

例如，命題公式p

q若指定p為“2是素?cái)?shù)”，q為“3是奇數(shù)”

則p

q為真命題

若指定p為“2是素?cái)?shù)”，q為“3是偶數(shù)”

則p

q為假命題

35公式的賦值定義1.2.2

若命題公式A含有的全部命題變?cè)獮閜1,p2,…,pn，給p1,p2,…,pn指定一組真值，稱為對(duì)A的一個(gè)解釋或賦值。使A的真值為真的賦值稱為成真賦值，使A的真值為假的賦值稱為成假賦值。說明通常賦值與命題變?cè)g按下標(biāo)或字母順序?qū)?yīng),即當(dāng)A的全部命題變?cè)獮閜1,p2,…,pn時(shí),給A賦值

1

2…

n，是指p1=

1,p2=

2,…,pn=

n;當(dāng)A的全部命題變?cè)獮閜,q,r,…時(shí),給A賦值

1

2

3…是指p=

1,q=

2,r=

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

p

(q

r)(p

q)

(

p

q)

(

p

q)

q37真值表:命題公式在所有可能的賦值下的取值的列表含n個(gè)變項(xiàng)的公式有2n個(gè)賦值例題(續(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個(gè)命題變?cè)牟煌恼嬷当碛忻}公式的分類定義1.2.3設(shè)A為一個(gè)命題公式(1)若A在它的各種賦值下取值均為真，則稱A為重言式或永真式。(2)若A在它的各種賦值下取值均為假，則稱A為矛盾式或永假式。(3)若至少存在一種賦值使A的真值為真，則稱A為可滿足式。例如(1)p

(q

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

（2）(p

q)

(

p

q)為重言式(3)

(

p

q)

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

A永假，反之亦然。公式A是可滿足的，當(dāng)且僅當(dāng)

A不是永真式。公式A不是可滿足的，則一定是永假式。公式A不是永假式，則一定是可滿足的。判斷命題公式類型的方法：構(gòu)造真值表421.3命題演算的關(guān)系式等價(jià)關(guān)系式定義1.3.1

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

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

B。說明：A

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

43例題證明：p

q和

p

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

q

p

qp

qp

q

p

p

q00111011111000011101例題證明p

(q

r)和(p

q)

(p

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

(q

r)和(p

q)

(p

r)等價(jià)p

q

rp

(q

r)(p

q)

(p

r)0000000100010000110010000101111101111111等價(jià)關(guān)系式雙重否定律

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結(jié)合律(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蘊(yùn)涵等值式p

q

p

q等價(jià)等值式p

q

(p

q)

(q

p)假言易位p

q

q

p等價(jià)否定等值式p

q

p

q歸謬論(p

q)

(p

q)

p47等價(jià)運(yùn)算置換規(guī)則

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

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

q

q

p解

p

q

p

q

蘊(yùn)涵等價(jià)式

(

q)

p

交換律和雙重否定式

q

p

蘊(yùn)涵等價(jià)式

條件命題：

p

q否命題：

p

q

逆命題：

q

p逆否命題：

q

p

條件命題和它的逆否命題等價(jià)49例題例1.3.4

利用命題的等價(jià)運(yùn)算判斷下列公式的類型。（1）

p

(p

q)解

p

(p

q)

p

(

p

q)蘊(yùn)涵等價(jià)式

p

(p

q)摩根律

(

p

p)

q

結(jié)合律

F

q

矛盾式

F

零元律

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

(p

q)解p

(p

q)

p

(

p

q)蘊(yùn)涵等價(jià)式

(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例題化簡(jiǎn)公式(p

q)

(p

q)解(p

q)

(p

q)

p

(q

q)分配律

p

T

排中律

p

同一律53例題對(duì)于圖1.3.1所示的邏輯電路，可否用更簡(jiǎn)單的電路實(shí)現(xiàn)該邏輯關(guān)系？54解：F

(p

q)

(

p

q)

(p

q)

(p

q)

q

p

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

、

、

}，{

、

}，{

、

}，{

、

}，{

}和{

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

、

}，{

、

}，{

、

}，{

}和{

}都是最小全功能聯(lián)結(jié)詞集。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)結(jié)詞集證：

p(p

p)

p

pp

q(p

q)(p

q)(p

q)(p

q)得證{

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

}可類似證明.

只用一個(gè)

或

就可以實(shí)現(xiàn)聯(lián)結(jié)詞

，

，

、

、

表示的邏輯關(guān)系。在數(shù)字電子技術(shù)中，只用與非門或者或非門組成的電路就可以實(shí)現(xiàn)任何邏輯運(yùn)算。56

與非門或非門例題用只有一種與非門的邏輯電路實(shí)現(xiàn)F

(p

q)

(

p

q)

(p

q)。解：F

(p

q)

(

p

q)

(p

q)

p

q

(

p

q)

(p

p)

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

，

，

的公式A中，將其中的

換成

，

換成

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

q

和p

q

，p

q和p

q，

p

(q

r)和

p

(q

r)，p

q和p

q都互為對(duì)偶式58對(duì)偶式設(shè)A(p1，p2，…pn)和A*(p1，p2，…pn)互為對(duì)偶式，其中p1，p2，…pn是出現(xiàn)在A和A*中的全部的命題變?cè)?，則

A(p1，p2，…pn)

A*(

p1，

p2，…

pn)

A(

p1，

p2，…

pn)

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

B，則A*

B*。證明

因?yàn)锳(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))的對(duì)偶式。解

公式A的對(duì)偶式A*為：A*

p

(

p

(q

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

A2

….

.An(n

1)，其中A1，A2，

….，An

都是由命題變?cè)蚱浞穸ㄋM成的合取式，則稱該命題公式為析取范式。

如：

p

(p

q

r)

(

p

q)

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

B2

….

.Bn(n

1)，其中B1，B2，

….，Bn都是由命題變?cè)蚱浞穸ㄋM成的析取式，則稱該命題公式為合取范式。

如：(p

q

r)

(

p

q)

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

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

設(shè)G為任意一個(gè)公式，將公式化成只含

、

、

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

以上亦是求析取范式和合取范式的步驟。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個(gè)命題變?cè)暮先∈街校裘總€(gè)命題變?cè)c其否定不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，這樣的合取式稱為極小項(xiàng)。定義1.4.4含有n個(gè)命題變?cè)奈鋈∈街?，若每個(gè)命題變?cè)c其否定不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，這樣的析取式稱為極大項(xiàng)。說明:(1)由n個(gè)命題變?cè)a(chǎn)生的不同的極大項(xiàng)和極小項(xiàng)的個(gè)數(shù)均為2n個(gè)。(2)每個(gè)極小項(xiàng)在它的2n個(gè)賦值中只有一個(gè)成真賦值(3)每個(gè)極大項(xiàng)在它的2n個(gè)賦值中只有一個(gè)成假賦值

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個(gè)命題變?cè)臉O小項(xiàng)

一般地，n個(gè)命題變?cè)纬傻臉O小項(xiàng)可表示為：主析取范式與主合取范式(續(xù))3個(gè)命題變?cè)臉O大項(xiàng)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個(gè)命題變?cè)纬傻臉O小項(xiàng)可表示為：主析取范式與主合取范式定義1.4.5如果含n個(gè)命題變?cè)拿}公式的析取范式的每個(gè)合取式全是極小項(xiàng)，則稱該析取范式為主析取范式。定理1.4.2任何命題公式的主析取范式都是存在的，并且是唯一的。證明

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

A2

….

.An(n

1)；；

2.若A′中的某個(gè)簡(jiǎn)單合取式Ai不是極小項(xiàng)，則補(bǔ)入在Ai中沒有出現(xiàn)的變?cè)?。例如，若pi和

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

Ai

(pi

pi)

(Ai

pi)

(Ai

pi);3.重復(fù)步驟2)，直到所有的簡(jiǎn)單合取式都含有所有的命題變?cè)蛩姆穸ㄊ剑?.消去重復(fù)出現(xiàn)的命題變項(xiàng)、矛盾式及重復(fù)出現(xiàn)的極小項(xiàng)。

按上述步驟求得的就是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)一個(gè)命題公式的主析取范式中的每一個(gè)極小項(xiàng)的成真賦值就是該公式的一個(gè)成真賦值70p

q

rp

q

r00000101001110010111011101010111主析取范式與主合取范式定義1.4.6如果含n個(gè)命題變?cè)拿}公式的析取范式的每個(gè)合取式全是極小項(xiàng)，則稱該析取范式為

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

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

B2

….

.Bn(n

1)；2.若B′中的某個(gè)析取式Bi不是極大項(xiàng)，則補(bǔ)入在Bi中沒有出現(xiàn)的變?cè)?。例如，若pi和

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

Bi

Bi

(pi

pi)

(B

pi)

(B

pi);3.重復(fù)步驟2)，直到所有的簡(jiǎn)單析取式都含有所有的命題變?cè)蛩姆穸ㄊ剑?.消去重復(fù)出現(xiàn)的命題變項(xiàng)、重言式及重復(fù)出現(xiàn)的極大項(xiàng)。

按上述步驟求得的就是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）判斷命題公式是否等價(jià)例1.4.5判斷(

p

q)

(

q

r)

(

r

p)和(p

q)

(q

r)

(r

p)是否等價(jià)。解

(

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)等價(jià)。73主析(合）取范式的用途(2)求公式的成真賦值和成假賦值設(shè)公式A含n個(gè)命題變項(xiàng),A的主析取范式有s個(gè)極小項(xiàng),則A有s個(gè)成真賦值,它們是極小項(xiàng)下標(biāo)的二進(jìn)制表示,其余2n-s個(gè)賦值都是成假賦值例如

(p

q)

r

m0

m2

m4

m5

m6

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

A為可滿足式當(dāng)且僅當(dāng)A的主合取范式不是包含全部2n個(gè)極大項(xiàng)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

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

7800000010010001111000101111011111

例題

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

三個(gè)表決者的按鈕分別為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è)務(wù)骨干去進(jìn)修，由于工作需要，選派要滿足如下條件：若A去，則C同去。若B去，則C不能去。若C不去，則A或B可以去。問可以有哪些選派方案？80例題（續(xù)）解

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

1.5命題演算的推理1.5.1推理理論1.5.2推理證明方法82推理理論定義1.5.1設(shè)A和B是兩個(gè)命題公式，當(dāng)且僅當(dāng)命題A

B是重言式時(shí)(即A

B

T時(shí))，稱從A可推出B，或A蘊(yùn)涵B，或B是前提A的結(jié)論，可以表示成A

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

A2

An)

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

，An可推出結(jié)論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例題證明“如果牛吃草，則馬會(huì)飛；馬不會(huì)飛，所以牛不吃草?！笔钦_的推理。證明

設(shè)：p：牛吃草；q：馬會(huì)飛。前提符號(hào)化為：p

q，

q，結(jié)論符號(hào)化為：

p。

而(p

q)

q

p

((p

q)

q)

p

(p

q)

q

p

(p

q)

(p

q)T所以，

p是p

q和

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

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

Q。證明

從定理的假設(shè)有：H1

H2

...

Hm

P

Q

根據(jù)定義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推理證明方法真值表法等價(jià)演算法演繹法附加前提證明法間接推演法(歸謬法)歸結(jié)證明法881、真值表法通過寫出真值表判斷A

B的類型，若A

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

q和

p

r，可以推出結(jié)論q

r。證明

根據(jù)定義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，可以推出結(jié)論q

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

B的類型，若A

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

p和

p

q的結(jié)論。證明

p

(p

q)

q

(

p

(p

q))

q

p

(

p

q)

q

p

q

q

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

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

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

在推導(dǎo)的過程中，可隨時(shí)引入前提集合中的任意一個(gè)前提。2）結(jié)論引入規(guī)則

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

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

Q，則可以把P放到前提中去，設(shè)法推出Q即可。93例題證明：前提“今天下午有課且今天比昨天冷；只有今天下午沒有課，我們才去游泳；如果我們不去游泳，則我們打藍(lán)球；如果我們打籃球，我們就會(huì)感到精力充沛。”推出結(jié)論“我們感到精力充沛”是正確的。證明：設(shè)：p：今天下午有課，q：今天比昨天冷，r：我們?nèi)ビ斡荆瑂：我們打籃球，h：我們感到精力充沛。則前提為：p

q，r

p，

r

s，s

h，結(jié)論是：h

94例題

證明：

步驟

公式

理由p

q

前提引入p(1)化簡(jiǎn)r

p

前提引入

r(2)，(3)拒取式

r

s

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

h

前提引入

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

95例題證明

r

s是p

(q

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

步驟

公式

理由p

q

前提引入p(1)化簡(jiǎn)q(1)化簡(jiǎn)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的結(jié)論。證明

步驟

公式

理由r

附加前提引入

r

p

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

(q

s)前提引入q

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

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

定義1.5.2設(shè)H1，H2，.....Hr是r個(gè)命題公式。若H1

H2

.....

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

p是p

q，q

r，r

s的結(jié)論證明：

步驟

公式

理由

p

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

q

前提引入

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

r

前提引入

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

s

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

q)?(

p

r)

q

r歸結(jié)證明法：前提和結(jié)論必須被表示為子句，對(duì)于非子句的語句，可以用一個(gè)或多個(gè)等價(jià)的是子句的語句替換它子句是變?cè)蚱浞穸ǖ奈鋈。鏿

q、

p

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

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

r，

r?s，

s結(jié)論：

p?

q前提中的(p?q)

r

(p

q)

r

(

p

r)?(

q

r)，所以用兩個(gè)子句

p

r和

q

r代替(p?q)

r。結(jié)論為兩個(gè)子句：

p和

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

公式

理由

p

r

前提引入

r

s

前提引入

p

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

q

r

前提引入

q

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

s

前提引入

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

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

p?

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

謂詞是用來說明個(gè)體的性質(zhì)或個(gè)體間的關(guān)系。例如，小王是個(gè)大學(xué)生

3大于2105謂詞個(gè)體詞個(gè)體詞個(gè)體詞謂詞謂詞

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

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

個(gè)體常元

表示具體的或特定的個(gè)體，如a，b，c，

等；個(gè)體變?cè)?/p>

表示抽象的或泛指的個(gè)體，如x，y，z，

等。

謂詞常項(xiàng)

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

謂詞變項(xiàng)

表示抽象或泛指的謂詞

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

一個(gè)原子命題可以用一個(gè)謂詞常項(xiàng)P和幾個(gè)個(gè)體常元，如a，b，c，

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

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

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

一個(gè)謂詞常項(xiàng)P和幾個(gè)個(gè)體變?cè)鐇，y，z，

表示成P(x，y，z，

)的形式，稱為命題函數(shù)，其中的個(gè)體變?cè)梢源砣我庖粋€(gè)個(gè)體。注意：命題的謂詞表達(dá)式是有真值的，命題函數(shù)的真值是不確定的。107例題寫出下列命題的謂詞表達(dá)式。

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

A(a)

A(b)2.

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

P(a)

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

2，2

1，則3

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

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

：

B(a，b)

B(b，c)

B(a，c)武漢位于北京和廣州之間。解：設(shè)Q(x，y，z)：y位于x和z之間。a：北京，b：廣州，c：武漢。Q(a，c，b)109個(gè)體域定義2.1.4命題函數(shù)中，個(gè)體變?cè)娜≈捣秶Q為個(gè)體域或論述域。

個(gè)體域可以是有限的，也可以是無限的。把宇宙中一切事物作為對(duì)象的的集合稱為全總個(gè)體域。通常，沒有特別說明時(shí)，個(gè)體變?cè)恼撌鲇蚴侵溉倐€(gè)體域。如：A(x)表示：x是大學(xué)生。個(gè)體域：華工計(jì)科1班學(xué)生，則A(x)是永真式。個(gè)體域：華工附中1班學(xué)生，則A(x)是永假式。個(gè)體域：xx公司員工，其中有些是大學(xué)生，有些不是大學(xué)生，則對(duì)有些人，A(x)為真，對(duì)有些人，A(x)為假。110例題給出執(zhí)行語句“If

P(x)then