離散數(shù)學課件（第4版）

離散數(shù)學

、/一.1.

刖a

課程性質(zhì)：計算機數(shù)學基礎(chǔ)

課程安排:三個學期教授三個部分

第一部分:離散數(shù)學第一篇:數(shù)理邏輯

第二篇:集合論

第三篇：圖論代數(shù)系統(tǒng)

第二部分:計算數(shù)學

第三部分:組合數(shù)學

學習目的：1、初步掌握現(xiàn)代數(shù)學的觀點和方法；

2、初步掌握處理離散結(jié)構(gòu)和方法，提高計算機系統(tǒng)設(shè)計和程序設(shè)計的邏輯數(shù)

字的能力；

3、初步掌握計算機在進行數(shù)的處理時的方法和計算；

4、培養(yǎng)學習抽象思維和縝密思考的能力；

第一篇數(shù)理邏輯

第一章命題邏輯

?1.1命題和命題聯(lián)結(jié)詞

一.命題：

定義:具有確定真值的表達判斷的陳述句稱為命題。

說明:？命題的真值:作為命題所表達的判斷只有兩個結(jié)果:正確和錯誤，此結(jié)果

稱為

命題的真值。

命題是正確的，稱此命題的真值為真;命題是錯誤的，稱此命題的真值為假。

真值為真的命題稱為真命題；真值為假的命題稱為假命題。

?其它類型的句子，如疑問句、祈使句、感嘆句均沒有真假意義，因為均不是

題。

在數(shù)理邏輯中，命題的真值的真和假，有時分別用1和0來表達，也有時分別

用T和F來表達。

命題的分類：

原子命題:不能分解成更簡單的命題的命題。

復(fù)合命題：由若干個原子命題用命題聯(lián)結(jié)詞、標點符號聯(lián)結(jié)起來的命題。

例：

(1)10是整數(shù)。真原子命題

(2)北京是我們祖國的首都。真原子命題

(3)雪是黑的。假原子命題

(4)煤是白的。假原子命題

(5)今天是7號。在一定條件下是真命題(如果今天是7號)。

(6)1+11=100。在一定條件下是真命題(在二進制中)。

(7)我學英語，或者學法文。復(fù)合命題(8)如果天氣好，我就去游泳。復(fù)合

命題(9)向右看齊?祈使句非命題

(10)請勿吸煙?祈使句非命題

(11)你吃飯了嗎,疑問句非命題

(12)你上網(wǎng)了嗎,疑問句非命題

(13)本命題是假的。悖論

(14)我正在說謊。悖論

（15）我不給所有自己給自己理發(fā)的人理發(fā)，但是卻會給所有自己不給自己理發(fā)

的人理

發(fā)。悖論

命題標識符:用大寫字母P、Q、R、P、P來表示命題，這些大寫字母稱12

為命題標識符。

命題常量:用命題標識符表示的確定的命題稱為命題常量，它有確定的真值。

命題變量:表示任何一個命題的標識符，稱為命題變量，它有不確定的真值。

二（命題聯(lián)結(jié)詞：

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

否定、合取、析取、蘊含、等價和異或

,1.否定符號：

,P是命題，P讀作“非P”。

，P真值表為

，PP

01

10

否定的性質(zhì)

,,雙重否定律：（P）P,

,說明：1、P是一元聯(lián)結(jié)詞

所謂一元聯(lián)結(jié)詞就是聯(lián)結(jié)一個命題的聯(lián)結(jié)詞。

2、念作“等值”，表示該符號兩邊的兩個命題在任何情況下真值相同。，

2.合取符號：,

P、Q是命題

PQ讀作“P且Q”，“P合取Q”。,

PQ真值表，

PQPQ,

000

010

100

111

例:P：今天下雨。Q：今天刮風。則PQ:今天下雨且刮風。

合取的性質(zhì)

1）幕等律PPP,,

2）交換律PQQP,,,

3）結(jié)合律（PQ）CP（QC）,,,,,

4）零一律P00,,

5）同一律PlP,,

，6）否定律PP0,,

3.析取符號：，

P、Q是命題，記作PQ，讀作“P或Q”，“P析取Q”。

PQ真值表，

PQPQ,

000

011

101

111

例:P：今天下雨。Q：今天刮風。則PQ:今天下雨或刮風。

析取的性質(zhì)：

1)嘉等律ppp,,

QQP2)交換律P,,,

3)結(jié)合律(PQ)CP(QC),,,,,

OP4)同一律P,,

5)零一律PH,,

,6)否定律PP0,,

7)吸收律P(PQ)P,P(PQ)P,,,,,,

8)分配律P(QC)(PQ)(PC)P(QC)(PQ),,,,,,,,,,

(PC),,

,,,,,,9)德、摩根律(PQ)PQ,(PQ)PQ,,,,,,說明：(1)和混合運算

只能用分配律，不能用結(jié)合律。例:P(PQ)與P

不等值。

(2)和的分配律:P(QC)(PQ)(PC),形如乘與加的分配律

PX,,,,,,,,(Q+C)。

(3)可兼或與不可兼或

可兼或：明天下雨或刮風。

不可兼或:今天晚上去電影院看電影，或在家看電視。

4.蘊含符號：，

P、Q是命題

PQ讀作''P蘊含Q"，“如果P則Q”，“當P,則Q"，“P是Q的充分條

件”。，

例:P:我去上海。Q:我給你買衣服。

PQ:如果我去上海，就給你買衣服。，

P假Q(mào)假我沒去上海，也沒給你買衣服。PQ真，

P假Q(mào)真我沒去上海，但沒給你買衣服。PQ真，

P真Q假我去了上海，但沒給你買衣服。PQ假，

P真Q真我沒去上海，也沒給你買衣服。PQ真，

PQ真值表，

PQPQ,

001

011

100

111

P也稱為前件;Q稱為后件。

前件為假時，PQ必為真；，

后件為真時，PQ必為真。，

蘊含的性質(zhì)

,,1)歸化:PQPQ所謂歸化就是用、、表示其它聯(lián)結(jié)詞。，，，，，

,,2)PQQP,,,

證明：

,,QPPQ,PQP,,

00111

01111

10000

11011

,,,,在全部四種情況下，PQ與QP的真值表相同，所以PQQP,,,,,

,,3)(PQ)PQ,,,

例:將下列命題符號化

1)如果1+2,3,則太陽從東邊升起PQ,

,2)如果1+2?3,則太陽從東邊升起PQ,

,3)如果1+2,3,則太陽從東邊升起PQ,

,,4)如果1+2?3,則太陽從東邊升起PQ,P:1+2=3

Q：表示太陽從東邊升起

說明(1)蘊涵不存在交換律、結(jié)合律

PQ與QP不等值,,

(PQ)R與P(QP)等值,,,,

(2)在數(shù)理邏輯中，即使

Q沒有內(nèi)在聯(lián)系PQ仍有意義P、，

5.等價符號：，

P、Q是命題

從讀作“P等價于Q”，“P當且僅當Q"，“P是Q的充要條件”。

PQ真值表，

PQPQ,

001

010

100

111

等價的性質(zhì)PQ(PQ)(QP)從,，，，，

,,,,(PQ)(PQ)(PQ)(PQ,,,,,,,

1)交換律:PQQP,,,

2)結(jié)合律：(PQ)RP(QR),,,,,

3)PQ(PQ)(QP),,,,,

,,，，4)歸化:PQ(PQ)(PQ)(PQ)(PQ),,,,,,,,,

證明結(jié)合律

PQRP(QR)QPQR(PQ)R,,,,,,

0001010

0011101

0100101

0110010

1000111

1010000

1101000

1111111

左右兩邊在全部八種情況下均相等，所以兩邊等值，(PQ)RP(QR)。，，，，，

說明：

1)是邏輯聯(lián)結(jié)詞，而是公式關(guān)系符。A、B是命題，AB仍是命題，而AB,,,,

不是命題。

2)P、Q兩命題，沒有內(nèi)在聯(lián)系PQ仍有意義。,

例:2+2=5的充要條件是太陽從西邊升起。真

該命題為真

6.不可兼或(異或)，

兩個公式P、Q的異或是復(fù)合命題，

記作“PQ”,

讀作“P異或Q”，“P不可兼析取Q”。

不可兼或就是兩個命題不可能同時為真，當且僅當一個為真，一個為假時，為

真。

例：(1)今天下雨或刮風。(可兼或)

(2)今天第一節(jié)課是語文課或數(shù)學課。(不可兼或)

(3)他現(xiàn)在在301室或302室。(不可兼或)

P.Q真值表

PQP.Q

000

011

101

110

與或的區(qū)別:P為1且Q為1時，PQ為假。，

性質(zhì)：(1)PQQP交換律，，，

(2)(PQ)RP(QR)結(jié)合律，，，，，

(3)P(QR)(PQ)(PR)對的分配律,,,,,,,,

,,(4)PQ(PQ)(PQ),,,,,

,,(PQ)(PQ),,,,

,(5)PQ(PQ),,,

三(命題公式：

1(命題公式

由命題標識符、邏輯聯(lián)結(jié)詞和圓括號按照一定的正確規(guī)則組成的合式，簡稱公

式。

命題公式的規(guī)定：

(1)單個命題變項是合式公式。

,(2)如果A是合式公式，則A是合式公式。

(3)如果A、B是合式公式,則AB、AB、AB、AB、AB也是合,，，，,

式公式。

(4)當且僅當有限次運用(1)(2)(3)所得到的符號串是合式公式。

邏輯聯(lián)結(jié)詞的運算優(yōu)先次序依次為：

'，，，，，

，例:(PQ)，P(QR)，P(QR)是公式,,,,,

,(PQ,P,PQ,P不是公式，，，

P(QR)的括號可以省略，，

(PQ)R的括號不能省略,,

2(命題變項的指派(賦值)

,公式(PQ)(PQ)對命題變項P、Q、R沒有真值指定，公式?jīng)]有確定,，，

的真值。

指派(賦值)：命題公式中出現(xiàn)n個不同的命題變項PP,對這n個命題給定In

一組真值指定稱為這個公式的一個指派或稱為一個賦值。

若一個公式中出現(xiàn)n個不同的命題變項，每個變項分別可以取成1、0,那么該

n式共有個2不同的指派。

3例:前面公式共有P、Q、R三個不同命題變項，則共有2=8個指派。

PQR

000

001

010

011

100

101

110

111

3(公式的真值表

列出公式的所有指派及其相應(yīng)的公式真值形成的表格稱為公式的真值表

PC(QR)的真值表例：，

PQR(QR)P(QR,,,

00001

00101

01001

01111

10000

10100

11000

11111

公式真值表對我們進行證明以及判斷公式的恒真、恒假起很大作用

4(兩公式的等值

n給定兩公式A、B,A、B中共出現(xiàn)n個不同的命題變項，對于所有的個2不同

的

指派，A、B兩公式的真值均相同，記AB,讀作“A與B等值”。，說明：

等值與等價不是一回事

等價是命題聯(lián)結(jié)詞，是AB公式，在某些指派下為真，某些指派下為假。，

等值不是邏輯聯(lián)結(jié)詞是公式關(guān)系符，AB描述了A、B兩公式之間的關(guān)系，，

只有“成立”，“不成立”的區(qū)別。

5(全功能聯(lián)結(jié)詞組

定義了六個聯(lián)結(jié)詞，某些聯(lián)結(jié)詞可以同其他聯(lián)結(jié)詞替換

，例:PQPQ,,,

,,PQ(PQ)(PQ),,,,,

,,P,Q(PQ)(PQ),,,,

,、、，可以用、、等代換，，，，

一個聯(lián)結(jié)詞集合，若對于任何一個公式均可以用該集合中的聯(lián)結(jié)詞來等值比

較，

就稱他為全功能聯(lián)結(jié)詞組(聯(lián)結(jié)功能完備集)如果該集合任意去掉一個聯(lián)結(jié)

詞，就不再具備這種特性，就稱為最小全功能聯(lián)結(jié)

詞組(最小功能完備集)

,例：｛、、｝是全功能聯(lián)結(jié)詞組,,

，,，又因PQ=(PQ),,

,,｛、｝、｛、｝是最小全功能聯(lián)結(jié)詞組，，

第一節(jié)小結(jié)

必須熟練掌握:什么是命題

什么是命題邏輯聯(lián)結(jié)詞

命題聯(lián)結(jié)詞的真值表的定義及命題聯(lián)結(jié)詞的性質(zhì)

?1.2命題公式與賦值

命題公式:簡單講就是由命題表示符，邏輯聯(lián)結(jié)詞，括號按正確的規(guī)律聯(lián)結(jié)起

來，形成

的符號串。

n公式的指派:一個公式中如果出現(xiàn)n個不同的命題變項，那么此公式就有2個

公式指

派。

公式真值表:將所有的公式指派列出來，并且相對應(yīng)的列出公式的真值所得到

的表格。

例:求下列公式的真值表

，(1)PQ,

，(2)(PQ)P,,

，一(3)(PQ)(PQ),,,

,(4)(PQ)R,,

(5)(P(PQ))R,,,

,(6)(PQ)QR,,,

六個公式的真值表如下:

，⑴PQ,

,PQPQ,

001

011

100

111

,(2)(PQ)P,,

,PQPQ(PQ)P,,,

0000

0100

1000

1110

,,,(3)(PQ)(PQ),,,

,，(PQ)(PQ),,PQRPQ(PQ)PQ,,,,

0000111

0010111

0100111

0110111

1000111

1010111

1101001

1111001

Q)R⑷(P,,

PQRQPQ(PQ)R,,,000101001101010001011

001100110101111110001111001

，(5)(PQ)QR,,,

QP,,(PQ)(PQ)QR,,,PQR,,

000100

001100

010100

011100

100010

101010

110100

111100

(6)(P(PQ))R,,,

(PQ)(P(PQ))RPPQRPQ,,,,,,

0000110010110101110111111001111011

11110111111111

命題公式的分類：

永真式（重言式）：公式在一切賦值下的真值均為真。永假式（矛盾式）：公式在

一切賦值下的真值均為假。

可滿足式：如公式不是矛盾式就是可滿足式，即至少存在一個賦值使公式為

真。

僅可滿足式:既不是矛盾式，又不是重言式的公式，即至少存在一個指派使公

式為真，

至少存在一個指派使公式為假。

,矛盾式

公式，，重言式

,可滿足式，

,僅可滿足式

說明：

（1）公式若不是永真式未必是永假式。

,（2）如公式G是永真式，則公式G是永假式（反之也成立）。

（3）證明公式是永真式和永假式的方法：

方法之一:使用真值表

方法之二：

，否定律:PP1（永真式），，

,PP0（永假式），,

零一律:P00（永假式），，

P11（永真式），,

第二節(jié)小結(jié)

講解了公式的分類，永真式、永假式及其判斷方法，，，，，，

第四節(jié)范式

一、對偶式和對偶原理

定義1:在僅含有聯(lián)結(jié)詞，，，，，，的命令題公式A中，將，換成，，將，換

成，，同時T和F

**(既0和1)互相替代，所得公式A稱為A的對偶式。顯然A是A的對偶式A

的對偶式。

例一(試寫出下列命題公式的對偶式

(1)A:(P,Q),R

*則A為(P,Q),R

(2)A:(P,Q),(P,,(Q,,S))

*則A為(P,Q),(P,,(Q,,S))

(3)A:((P,Q),O),(1,,(R,,P))

*則A為((P,Q),1),(0,,(R,,P))

下面兩個定理是對偶定理

定理2:A和是互為對偶式，P,P,,,,,P是出現(xiàn)在A和的原子變元，則2n*,

A(P,”，P),A(,P,,,,,P)nn**A(,P,”，，P),,A(P,,,,P)nn

即公式的否定等值于其變元否定的對偶式。

*例:A為P,Q,則A為P,Q,則，(P,Q),,P,,Q這就是DeMorgan律。

*再例如:A為(P,,刈，(i則人為小,，R),Q則，((P,,R),Q),(,P,R),,Q

****定理3:設(shè)A,B分別是A和B的對偶式，如果A,B,則A,B。這就是對

偶原理。如果證明了一個等值公式，其對偶式的等值式同時也成立?？梢云鸬绞掳?/p>

功倍的效果。

例如:A,(P,Q),(,P,(,P,Q))B,,P,Q可以證明A,B

*而人的對偶式為A,(P,Q),(,P,(,P,Q))

*B的對偶式為B,,P,Q

**根據(jù)對偶原理，則A,B也成立。

說明：1)含有另外三個聯(lián)結(jié)詞，，，，，的公式，必須將其歸化為然后再化為對

偶式。例:P,Q,(,P,Q),(P,,Q)

P,Q,(,P,Q),(P,,Q)

從而可知P,Q的對偶式是P,Q

*2)對偶原理不是說A與其對偶式A等值，一般公式與對偶是不是等值的。

二、范式：

1(簡單析取式和簡單合取式

定義2:僅有有限個命題變元或其否定的析取構(gòu)成的析取式稱為簡單析取式。而

僅有有限個命題變元或其否定的合取構(gòu)成的合取式稱為簡單合取式。例如：，

P,Q,R,,P,,Q,P是簡單析取式，，P,R,Q,R,,Q是簡單合取式。P,,Q一個

變項本身可以看作簡單析取式也可以看作簡單合取式。

而，P,(Q,R),(P,Q),,R不是簡單析取式。

2(范式：

定義3:

?析取范式：由有限個簡單合取式的析取構(gòu)成的析取式稱為析取范式。

?合取范式：由有限個簡單析取式的合取構(gòu)成的合取式稱為合取范式。

例:P,(P,Q),(,P,,Q,,R)是析取范式

(P,Q),,Q,(Q,,R,S)是合取范式

P,Q,R是析取范式是三個簡單合取范式的析取，同時也是合取范式是一個簡單

析取范式的合取。而(P,Q),(,P,(Q,R))不是析取范式，因為，P,(Q,R)不是簡單合

取范式。含有雙重刮號的公式，肯定不是范式。

(P,Q),(Q,R)不是合取范式，因為其含有，，范式中只能包含，、，、，等邏輯

聯(lián)結(jié)詞。3、范式的存在性

定理:任意一個命題公式均存在一個與之等值的析取范式和合取范式

此定理證明是一個構(gòu)造性證明，證明過程說明了公式的范式如何求得。

,第一步：將公式中出現(xiàn)的，，，，用，，來歸化。，，，，

，所用公式為?PQPQ,,,

,,?PQ(PQ)(PQ),,,,,

,,(PQ)(PQ),,,,

,,?PQ(PQ)(PQ),,,,,

,,(PQ)(PQ),,,,

,,,第二步:用雙重否定律PQ,或用德莫根律將一直移到命題變元之前，

第三步:用分配律、結(jié)合律化去額二重以上刮號成為析取范式或合取范式例2:

求公式((PQ)R)的析取范式和合取范式，，

,,,解：((PQ)R)((PQ)R)P((PQ)R)P,,,,,,,,,,

,,(PQ)(QR)P析取范式，，，，，

,,,(P(PR))(QR)P(QR)析取范式，，，，，，，，

,,，原式：((PQ)R)P(PQP)(RP)合取范式(PQ)(PR),,,,,,,,,,,,,合取范式

例3:求公式(PQ)(QR)的析取范式和合取范式，，，

,,,,,解：(PQ)(QR)(PQ)(QR)(QR)(PQ),,,,,,,,,,,,

,,91?)—析取范式，，,

,,,,,,,原式(PQ)((QR)(QR))(PQ)((QR)(QR)),,,,,,,,,,,,

,,,,,,,,(PQR)(PQR)(QQR)(QQR)合取范,，，，，，，，，，，，

，,，，,式(PQR)(PQR)(QR)合取范式，，，，，，，,

總結(jié)：

一個公式的析取范式與合取范式并不唯一。要使任一命題公式化為唯一的等值

命題的標準形式，就要用到主析取范式與主合取范式的概念。

三、主析取范式：

1(極小項

定義4:如公式中共有N個命題變項P,……，P這N個變項的合取n

式中，每個變項P或其否定，P,均出現(xiàn)且兩者僅出現(xiàn)一個，并且按ii

命題變項的下標排列(字母按字典序列)這樣的簡單合取式稱為極小項，又稱布

爾合取。

例如:公式中出現(xiàn)P,Q,R三個命題變項

P,,Q,R,,P,Q,,R是極小項

P,,Q不是極小項，其中沒出現(xiàn)R

P,,Q,,P不是極小項，P,,P同時出現(xiàn)

2(極小項和賦值的一一對應(yīng)

n每一個極小項只有一個賦值使其為真，其余2-1個賦值使其為假。

例如:公式中出現(xiàn)P,Q,R三個不同的賦值。極小項，P,Q,,R,賦

3值010使其為真，其余2-1=7個賦值使其為假。這樣極小項與賦值建立了一

一對應(yīng)關(guān)系。而，P,Q不是極小項，有兩個賦值010,011使其為真，其余6個賦

值使其為假。

3(極小項的記法

n公式共有2個賦值，每個賦值對應(yīng)一個極小項。如極大項對應(yīng)賦值

naaa,把其看作二進數(shù)，化為十進數(shù)為k,k,2-1,則該極小項記作1230

m,也記作mala2a3k

極小項對應(yīng)的賦值十進制數(shù)記法

0000M或M,P,,Q,,R0000

0011M或M,P,,Q,R0011

0102M或M,P,Q,,R0102

0113或MM,P,Q,R0113

1004或MMP,,Q,,R1004

1015M或MP,,Q,R1015

1106M或MP,Q,,R1106

1117M或MP,Q,R1117

4.主析取范式：

定義4:若干個不同的極小項的析取式，稱為主析取范式定理5:任何一個命題

公式均存在一個與之等值的主析取范式，

而且是唯一的。

例如：

P,(,P,Q),(P,Q),(,P,R)是析取范式,但不是主析取范式。(P,Q,,R),(,

P,Q,R)是主析取范式，當然也是析取范式。5(求主析取范式方法之一:真值表法

一個公式的主析取范式與該公式的真值是一一對應(yīng)的例如：由三個極小項組成

的主析取范式

(P,Q,R),(,P,Q,R),(,P,Q,,R)

這三個極小項對應(yīng)的賦值分別是111,Oil,010,則該三個賦值使公式為真，

而其它五個賦值使公式為假。

而反過來如果這三個賦值公式為真，而其它賦值使公式為假，則該公式的主析

取范式就是有這三個賦值對應(yīng)的極小值的析取而成。

因此我們可以用真值表的方法來求出公式的主析取范式。例4:用真值表的方

法求，(P,Q)的主析取范式

解：，(P,Q)的真值表

PQ,(P,Q)P,Q

0001

0101

1001

1110

找使公式為真的賦值。

00對應(yīng)的極小項是，P,,Q(m)0

01對應(yīng)的極小項是，P,Q(m)1

10對應(yīng)的極小項是P,,Q(m)2

則原公式的主析取范式是

，(P,Q),(,P,,Q),(,P,Q),(P,,Q)

,m,m,m012

例5:用真值表的方法求(P,Q),(Q,R)的主析取范式。解：(P,Q),(Q,R)的真值表

PQR(P,Q),(Q,R)對應(yīng)極小項P,QQ,R

000011,P,,Q,,R001001,P,,Q,R01010001111

1,P,Q,R100111P,,Q,,R101100110100111111

P,Q,R找使公式真值為1的賦值。

由此主析取范式為：

(P.Q),(Q,R),(,P,,Q,,R),(,P,,Q,R),(,P,Q,R)

,(P,,Q,,R),(P,Q,R)

,m,m,m,m,m01347

6.求主析取范式的方法之二:等值演算法

利用十六個命題公式、命題定理用等值演算的方法一步步將它化為主析取范

式。第一步:將公式化為析取范式，“消去”含有矛盾式的簡單合取式，這是因

為(P,,P,Q),G,G,而P,P用P代替。0

第二步:若析取范式中的簡單合取式項不是極小項，即該項中缺命題變項，則

添加(P,,P)再用分配律展開。ii

例如:公式中含P、Q、R,某合取項為P,,R,缺Q。則P,,R,P,,R,(Q,,

Q),(P,Q,,R),(P,,Q,,R)第三步:用幕等律將重復(fù)的極小項刪去，即m,m,m然

后將各極小iil

項按順序排列。

例6:求(求Q),R),P的主析取范式。

解:原公式，，(，(P,Q),R),P

,((P,Q),,R),P

,(P,,R),(Q,,R),P(析取范式)

,P,(Q,,R)(析取范式)

,(P,(Q,,Q),(R,,R)),((Q,,R),(P,,P))

,(P,Q,R),(P,Q,,R),(P,,Q,R),(P,,Q,,R)

,(P,Q,,R),(,P,Q,,R)

(六個極小項，其中重復(fù)了一個)

,(P,Q,R),(P,Q,,R),(P,,Q,R),(P,,Q,,R)

,(,P,Q,,R)

,m,m,m,m,m24567

,,(2,4,5,6,7)

5、間接證法

1)CP規(guī)則:

有時要證的結(jié)論以蘊含的形式出現(xiàn)。要證Al?A2?,,?Am,B,C。如果把結(jié)論中的

前件B作為附加條件加入前提集合中，即證出了Al,A2,,,,Am,B,C,則原來要證的

結(jié)論成立。稱之為附加前提證明法。

簡稱CP規(guī)則。

證明:Al,A2,”,Am,B,C,Al,A2,,,,Am,B,C證明:Al,A2,,,,Am,B,C,Al,A2,Am,

(B,C),,(Al,A2,,,,Am),(,B,C),(,(Al,A2,”,Am),,B),C,,

(Al,A2,,,,Am,B),C,(Al,A2,?,Am,B),C?CP規(guī)則成立。

例6:試證(P?(Q?S))?(,R?P)?Q,R?S前提公式集合P?(Q?S),,R?P,Q,結(jié)論

R?S將結(jié)論R,S中的前項R引入前提集合，而去演繹出S。證明：(1),R?P規(guī)則P

(2)R規(guī)則P(附加前提)

(3)P規(guī)則T由⑴(2)(析取三段論)

(4)P?(Q?S)規(guī)則P

(5)Q?S規(guī)則T由⑶(4)(假言推理)

(6)Q規(guī)則P

(7)S規(guī)則T由(5)(6)(假言推理)

(8)R?S規(guī)則CP

例：證明｛,A?B,,B?C,C?D｝邏輯的推出A?D證法1:用CP規(guī)則

(1),A?B規(guī)則P

(2)A規(guī)則P(附加前提)

(3)8規(guī)則丁由(1)(2)(析取三段論)

(4),B?C規(guī)則P

⑸C規(guī)則T由⑶(4)(析取三段論)

(6)C?D規(guī)則P

(7)D規(guī)則T由⑸(6)(假言推理)

(8)A?D規(guī)則CP

證法2:不用CP規(guī)則

(1),A?B規(guī)則P

(2)A?B規(guī)則T由(1)(蘊含律)

(3),B?C規(guī)則P

(5)A?C規(guī)則T由(2)(4)(假言三段論)

(4)B?C規(guī)則T由(3)(蘊含律)

(6)C?D規(guī)則P

(7)A?D規(guī)則T由(5)(6)(假言三段論)

2)歸謬法

設(shè)Al,A2,,,,Am是命題公式，

如果Al?A2,,,,Am是可滿足的,稱Al,A2,”,Am是相容的。如果Al,A2,”,Am

是矛盾式，稱Al,A2,”，Am是不相容的。理論根據(jù)

Al,A2,Am,C,,,Al,A2,Am,,C,,,Al,A2,Am,,C)則

Al,A2,,,,Am,C,即Al,A2,,,,Am,C為重言式，Al,A2,,,,Am,,C是矛盾式。

從而得到如Al,A2,”，Am,,C不相容，則C是Al,A2,”，Am的有效結(jié)

論。

因此我們可以把，C作為附加前提推出矛盾來，從而可以得到C是Al,A2,

,,,Am的有效結(jié)

論。這種方法稱為歸謬法，也就是我們通常說的反證法。例7:是證明(R,,

Q),(R,S),(S,,Q),(P,Q),,P證明：(1)P,Q規(guī)則P

(2)P規(guī)則P(附加前提)

⑶Q規(guī)則T由⑴(2)(假言推理)

(4)R,,Q規(guī)則P

(5),R規(guī)則T由(3)(4)(拒取式)

(6)S,,Q規(guī)則P

(7),S規(guī)則T由(3)(6)(拒取式)

(8),R,,S規(guī)則T由⑷(7)(合取引入)

(9),,R.S,規(guī)則T由(8)(德.摩根律)

(10)R,S規(guī)則P

(11),,R,S,,,R,S,規(guī)則T由⑼(10)(合取引入)(12),,R,S,,,

R,S,是矛盾式，所以P為前提公式的有效結(jié)論

?1.7自我練習

1：求命題公式(P,(P,Q)),R的真值表

自我練習2:

求(P,Q,R),(,P,,Q,,R)的主析取范式。

解:原公式，(，P,(Q,R)),(P,(,Q,,R))

,(,P,P),(,P,,Q,,R),(Q,R,P),(Q,R,,Q,,R),0,(,P,,Q,,R),

(P,Q,R),0

,0,(,P,,Q,,R),(P,Q,R),m0,m7,?(0,7)自我練習3:

((A,B),C),(B,(D,0),(B,(D,A)),C

證明：左邊，(，(A,B),C),(,B,(D.O),(,A,,B,C),(,B,C,D)

右邊，，(B,(,D,A)),C,(,B,(D,,A)),C,(,A,,B,C),(,B,C,D)所以左邊,

右邊

自我練習4:構(gòu)造下面推理證明

前提:，，P,,Q,,,Q,R,,R

結(jié)論:，P

證明：

(1),Q,R規(guī)則P

(2),R規(guī)則P

(3),Q規(guī)則T由(1)(2)(析取三段論)

(4),(P,,Q)規(guī)則P

(5),P,Q規(guī)則T由(3)(德?摩根律)

(6),P規(guī)則T由(3)(5)(析取三段論)

作業(yè)：

P32練習1.5:(A)l,3,5(B)1,2,3P35習題1:8(2)(3)(4)(5)

第二章謂詞邏輯

蘇格拉底三段論：

凡人要死，蘇格拉底是人，所以蘇格拉底要死，

P：凡人要死

Q：蘇格拉底是人

R：蘇格拉底要死

此三段論表示為(P,Q),R

蘇格拉底三段論是正確的，但P,Q,R卻不是重言式，這就是命題邏

輯的局限性。

?2.1謂詞邏輯的基本概念

一、謂詞

1.個體域：

命題邏輯中將命題(句子)繼續(xù)細分。命題是由主語和謂語

兩部分組成。主語是名詞，稱之為個體詞。是獨立存在的客體，可以

是具體事物也可以是抽象概念。

在謂語中含有賓語，它也是名詞，它也是個體詞。個體域:客體(個體)的取值

范圍。

例如:吳華是大學生，用P表示，

李明是大學生，用Q表示。

在命題邏輯中就沒辦法表示出兩句的聯(lián)系。

“……是大學生”用A(X)表示，x是大學生，命題符號含有個體詞變量。

a表示吳華，A(a)表示吳華是大學生。

b表示李明，A(b)表示李明是大學生。

相當于“……是大學生”，用A(?)來表示，這就是謂詞。例：張三比李四高，

用H(x,y)表示x比y高。

a:張三b:李四

H(a,b):張三比李四高

H(b,a):李四比張三高

x,y,a,b表示客體，H(?,?)是謂詞這個謂詞涉及了兩個客體，是二元謂詞。

2.謂詞：

只涉及一個客體的謂詞稱為一元謂詞，涉及兩個客體的謂詞稱為二元謂詞，涉

及n個客體的謂詞稱為n元謂詞。

一般，如A表示謂詞符號，用X表示第i個客體變項，則ni

元謂詞表示為A(x,…,x),如a,a,…,a是個體域中的客體名詞,則lnl2n

A(a,a,…,a)是個命題。不含客體變項的謂詞稱零元謂詞，零元謂12n

詞本身就是命題。

注意：

(1)n元謂詞中，客體變項的次序很重要。

例：F(x,y)表示x是y的父親，

a:張三，b:張小明。

F(a,b)表示張三是張小明的父親。

F(b,a)表示張小明是張三的父親。

兩個命題至多一個是真

(2)在討論一個問題是必須先確定好個體域D。

如不作限制，表示宇宙一切事物組成的個體，成為全總個體域。(3)同一個n

元謂詞，取不同的客觀，真假會不同。

A(x):x是大學生。A(a)真值可能為真，而A(b)真

值可能為假。

(4)對于同一謂詞，個體域D不同，真值可能也不同。

例:對于A(x),x是大學生。

如口=｛大學生全體｝,A(x)是重言式。

如口=｛學生全體｝,A(x)是僅可滿足式。

如口=｛計算機全體｝,A(x)是永假式。3.命題函數(shù)

對于謂詞B(x),B(x,y),H(x,y,z)等，本身不是命

題。

只有命題變項在D中取出個體名稱時才成為一個確定的命題。

故謂詞也稱為命題函數(shù)或簡單命題函數(shù)。

有限個簡單命題函數(shù)用聯(lián)結(jié)詞，，，，，，，，，，，進行聯(lián)結(jié)而成，成為復(fù)合命

題函數(shù)。

二、量詞：

1.全稱量詞：

“所有的”，“任何一個”，“每一個”，“凡是”，“一切”表示個體域中

每一個，用符號”表示，稱為全稱量詞。

例1:將下列命題符號化

(1)所有人都要呼吸

(2)每個人都是要死的

解：(1)設(shè)M(x):x是人，M(x):x是要呼吸。

命題符號化為:,x(M(x),H(x))。

(3)設(shè)M(設(shè)：x是人,D(x):x是要死的。

命題符號化為:,x(M(x),D(x))0

2.存在量詞：

“有些”，“存在”，“至少有一個”，表示個體域D中存在個體，用符號

”表示。

例2:將下列命題符號化

(1)有些人是聰明和美麗的。

(2)有人早飯吃面包。

解：(1)設(shè)M(x):x是人，Q(x):x是聰明的，

R(x):x是美麗的。

命題符號化為：，x(M(x),Q(x),R(x))o

(3)設(shè)M(x):x是人，E(x):x是早飯時吃面包，

命題符號化為：，x(M(x),E(x))

說明:命題符號化之前，必須明確個體域的范圍，以上兩例子均為

全總個體域。

如果將個體域改為D=｛人類｝,則特性謂詞M(x)就不需要

了。

例1:(1),xH(x),(2),xD(x)

例2:(1),x(Q(x),R(x))

(2),xE(x)

3.含量詞的謂詞的真值規(guī)定

說明：不含量詞的謂詞公式G(x),它不是命題，而是命題函

數(shù)，其真值依賴于x從個體域中取的個體名詞的不同而不

同。

例:D表示某班全體學生，G(x)表示x是男生。

則G(李剛)是真，而G(王芳)是假。

而,xG(x)與,xG(x)是命題了，x僅是一個“指導(dǎo)變量”

,xG(x)與,xG(y)意義完全相同。

,xG(x):全班每個人均是男生。

,xG(x):全班存在一個人是男生。

含量詞的謂詞公式的真值不再依賴于x的選取了。

(1),xG(x)的真值規(guī)定

,xG(x)的命題是“對任意x,D,均有G(x)”

,xG(x)的真值為1,當且僅當，對一切x,D,G(x)真值

均為1,,xG(x)的真值為0,當且僅當，對一切x,D,0

G(x)真值為0。0

(2),xG(x)的真值規(guī)定

,xG(x)的命題是“存在一個x,D,使得G(x)成00立”

，xG(x)的真值為1,當且僅當存在x,D,0

66)的真值為1。0

,xG(x)的真值為0,當且僅當，對一切x,D,

G(x)的真值為0。

例如:D={a,b,c},由以上規(guī)定可知：

,xG(x),G(a),G(b),G(c)

,xG(x),G(a),G(b),G(c)

注:對于一個謂詞，如其每個變量均在量詞的管轄下，則該

不是命題函數(shù)，而是命題了，它有確定的真值了。

例3將下列語句表示為謂詞邏輯的命題。

(1)所有的正數(shù)均可開方。

)若個體域為全體正實數(shù)R+,S(X):X可以開方，則命題符號化為:，xS(x)

解：(i

(ii)若個體域為全體實數(shù)集R,G(x,y):x>y,則命題符號化為:，x((G(x,0),

S(x))(iii)若D,全總個體域,R(x):x是實數(shù),則符號化為:,x(R(x)?G(x,0),

S(x))

4:03

(2)沒有最大的自然數(shù)

即理解為“對所有x,若x是自然數(shù)，則存在y,y也是自然數(shù)，且y>x”

解:N(x):x是自然數(shù)，G(x,y):x>y,符號化為:，x(N(x),,y(N(y)?G(y,x))也可以

理解為“下句話是不對的'存在一個x,x是自然數(shù)且對一切自然數(shù)y,x均大于

y’”,符號化為:，，x(N(x)?,y(N(y),G(x,y))

以后可以證明，這兩個公式是等值的。8:15注:不可以用最大來直接定義謂

詞。

設(shè)B(x):x是最大的,N(x):x是自然數(shù)。

以上命題可以表示為：，，x(B(x)?N(x))

這是不對的?！白畲蟆笔潜容^而來，依賴于其它客體，最大最小不能直接作謂

而jO

10:08

?2.2謂詞公式

一、謂詞公式的定義：

L謂詞公式中出現(xiàn)的字母表：

定義1：字母表如下：

(1)個體常量:a,b,c,...,al,a2,a3,...

(2)個體變量:x,y,z,...,xl,x2,x3,...

(3)函數(shù)符號:f,g,h,...,f1,f2,f3,...

(4)謂詞符號:P,Q,R,....SO,SI,S2,...

(5)量詞符號:，…

(6)邏輯符號：，，，，，，，，，，，

(7)括號和逗號：(,)，15:10:302.項的定義:

項在謂詞公式中起的是名詞的作用，它不是句子。

定義2:項的遞歸定義如下：

(1)任意個體常量或個體變量是項。

(2)如果f(Xl,X2,X3,...,Xn)是任意n元函數(shù),tl,t2,...tn是項,則

f(tl,t2,...,tn)

仍然是項。

(3)只有有限次使用(1),(2)生成的符號串才是項。19:10例:D是個體名稱

集，x,D,人名變量，a:張三，b:李四。

x,a,b是項,

f(x):x的父親,S(x,y),x和y的兒子。

f(a):張三的父親，仍然是個名詞，不是句子，它仍是項。

f(f(a)):張三的祖父,

而P(x,y):x是y的父親，是句子而不是名詞。其是命題函數(shù)，而不是項了。

23:17

例:D:是實數(shù)集的全體。

f(x)=lnx,g(x,y)=x+y,h(x,y)=x*y

其均是函數(shù)，算術(shù)表達式，其結(jié)果仍是數(shù)，仍可以在函數(shù)的自變量位置上出

現(xiàn)。g(g(x,y),h(x,y))=((x+y)+(x*y))

f(g(x,y))=In(x+y)

x+y=5,x*y+a〉5,此類是邏輯表達式，其結(jié)果不是數(shù)了，是成立或不成立，是真

或

假,因而不是項。26:51

3(原子公式的定義

原子公式是公式的最小單位，最小的句子單位。項不是公式。

定義3:若P(xl,...,xn)是n元謂詞，tl,...,tn是項，則tn)為

原子公式。(1)從中可以看出，項也可以出現(xiàn)在謂詞的變量位置，相當于名詞，可

以做句子的主語或賓語。

(2)函數(shù),tn)不是句子，僅是詞，因而不是公式僅是項。項的結(jié)果仍

是個體名稱集中的名詞，而公式的結(jié)果(真值)是成立或不成立(是1或0)。30:37

4(謂詞公式的定義：

定義4:合式公式的遞歸定義如下：

(1)原子公式是合式公式；

(2)如A,B是公式,則，A,A,B,A,B,A,B,A,B,A,B也是公式；

(3)如A是公式，x是A中出現(xiàn)的任意有關(guān)變元，貝LxA,,xA也是合式公式。

(4)只有有限次使用(1)(2)(3)生成的符號串才是合式公式(也稱謂詞公式)

例:H(a,b),C(x),B(x),,x(M(x),H(x)),,x(M(x),C(x),B(x)),,x,y(M(x),

H(x,y),L(x,y))等均是合式公式。當然以上出現(xiàn)的大寫英文字母均是謂詞符號。

38:01二、約束變量和自由變量

定義5:在合式公式,xA和，xA中，x是指導(dǎo)變元，A為相應(yīng)量詞的作用域或轄

域。在轄域中x的出現(xiàn)稱為x在公式A中的約束出現(xiàn);約束出現(xiàn)的變元稱為約束變

元;A中不是約束出現(xiàn)的其它變元稱為該變元的自由出現(xiàn)，自由出現(xiàn)的變元成為自

由變元。40:05例一指出各公式的指導(dǎo)變元，轄域、約束變元和自由變元。

(1),x(p(x),,yQ(x,y))

解：由，x后的()，x是指導(dǎo)變元，，x的轄域是后面整個式子，y是指導(dǎo)變元，

轄域僅Q(x,y)此部分。x兩次出現(xiàn)均是約束出現(xiàn)，y的一次出現(xiàn)是約束出現(xiàn)，故

x,y是約束變元，而不是自由變元。

(2),xF(x),G(x,y))

解：，x的轄域僅F(x),x是指導(dǎo)變元，變元x第一次出現(xiàn)是約束出現(xiàn)，第二次

出現(xiàn)是自由出現(xiàn)，y的出現(xiàn)是自由出現(xiàn)。所以第一個x是約束變元，第二個x是自

由變元，本質(zhì)上這兩個x的含義是不同的;而y僅是自由變元。45:22

22(3),x(x=y,x+x<5,x<z),x=5y

222x+x是函數(shù)不是謂詞，x=y,x+x<5,x〈z,x=5y這是四個原子公式。用邏輯

詞，，，，，來聯(lián)結(jié)起來的。

x是指導(dǎo)變元、，x的轄域是0內(nèi)的這部分。因此，x第一、二、三、四次出現(xiàn)

是約束出現(xiàn)，x第五次出現(xiàn)是自由出現(xiàn)。而y,z的出現(xiàn)均是自由出現(xiàn)。47:56

三、換名規(guī)則

從以上例子中可以看此在謂詞公式中一個變元可能既是約束出現(xiàn)，同時又有自

由出現(xiàn),則該變元既是自由變元又是約束變元,本質(zhì)上這兩種出現(xiàn),用的是一個符號,

實質(zhì)上是不同的含義。為避免混淆，需要改名。改名要采用以下規(guī)則，使謂詞公式的

含義不改變。2:151、換名規(guī)則:對約束變元進行換名。

將量詞轄域內(nèi)出現(xiàn)的某個約束變元及其相應(yīng)量詞中的指導(dǎo)變元，可以換成一個

其他變元，

改變元不能與本轄域內(nèi)的其他變元同名，公式中的其他部分不改變。

2、代入規(guī)則:對自由變元進行代入。

整個謂詞公式中同一個字母的自由變元是指同一個個體名詞。因此可以用整個

公式中所

有變元的符號來代替，且要求整個公式中該變元同時用同一個符號代替。

4:35例：(l),xF(x,y)?,xG(x,y)

x是約束變元,y是自由變元。而x的兩次出現(xiàn)盡管均是約束的，但分別在不同

的轄域。含義是互相無關(guān)的?？梢詫⒁惶帗Q名，但不能與y同名。

改為,xF(x,y)?,uG(u,y)

(2),x(F(x,y),P(x))?,y(Q(x,y),R(x)

x前兩次出現(xiàn)是約束的,后兩次出現(xiàn)是自由的。y第一次出現(xiàn)是自由的，第二次

是約束的,準備將自由變元x改為u,自由變元y改為V,成為

,x(F(x,v),P(x))?,y(Q(u,y),R(u))11:04

說明：(1)如果D是有限集，謂詞公式中的量詞可以用邏輯聯(lián)結(jié)詞來解釋。例

D={a,b,c)

,xP(x),P(a)?P(b)?P(c)

,,xP(x),P(a),P(b),P(c)

(2)量詞不能隨便換順序。對于，和，這兩個量詞交換位置，其意義不同了，相應(yīng)

真值也可能改變。

例:D:自然數(shù)全體,G(x,y):x小于y?

,x,yG(x,y)表示任意一個自然數(shù)x,總存在自然數(shù)y,使得x小于y,該命題是真

的。

,y,xG(x,y)表示存在一個自然數(shù)y,使得對一切自然數(shù)x,使x小于y,即y是最

的自然數(shù)。該命題是假的。14:55

?2.3謂詞的等值演算

一、謂詞邏輯中的解釋(賦值)

在命題邏輯對每個命題符號作個真值指定可以得一個公式的一個指派，又稱賦

n值,又稱解釋。如公式中共出現(xiàn)n個不同的命題符號,則共有2個解釋，因而可

列出公式的真值表。而謂詞邏輯中公式的賦值解釋是怎樣的呢，

16:33

1.謂詞公式的賦值(解釋)

定義6:謂詞公式的賦值是對以下一些符號進行指定:謂詞公式A的個體域為

D(這也必須指定)

(1)每一個個體常項指定D中的一個元素

n(2)每一個n元函數(shù)D到D的一個映射

n(3)每一個n元謂詞D到{0,1}的一個映射

以上一組指定稱為謂詞公式A的一個解釋或賦值19:16

例1:已知一個解釋I如下：

1)0={2,3}2)指定a=2?Dx

3)函數(shù)f:D,D指定f(2)=3,f(3)=2

4)謂詞P:D,{0,1}指定P(2)=0,P(3)=1。

2Q:D,{O,ll.QCi,j)=l,i,J=2,3

在該解釋I下

,x(P(x),Q(x,y)),(P(2),Q⑵2)),(P(3),Q(3,2)),(0,1),

(1,1),0

公式，x(P(f(x)),Q(x,f(a)),(P(f(2)),Q(2,f(2)),

(P(f(3)),Q(3,f(2)),(P(3)

,Q(2,3)),(P(2),Q(3,3),(1,1),1

25:25

例2:已知指定一個解釋N如下：

(1)個體域為自然數(shù)集合DN

(2)指定常項a=0

(3)D上的指定函數(shù)f(x,y)=x+y,g(x,y)=x*yN

(4)指定謂詞F(x,y)為x=y

在以上指定的解釋N下，說明下列公式的真值

(1),xF(g(x,a),x)即，x(x*0=x)該命題假的(2),x,

y(F(f(x,a),y),F(f(y,a),x))

在解釋N下此公式:，，x,y(x+0=y,y+0=x)此命題為真

(3)F(f(x,y),f(y,z))在解釋N下該公式,x+y=y+z

此時,x,y,z均為自由變元,解釋不對自由變元進行指定。因而該公式是命題函

數(shù)，

不是命題，真值不能確定。34:23

說明：

(1)一個謂詞公式如果不含自由變元,則在一個解釋下,可以得到確定的診治，

不同的解釋下可能得到不同的真值。

(2)公式的解釋并不對變元進行指定,如果公式中含有自由變元,即使對公式進

行了一個指派,也得不到確定的真值,其僅是個命題函數(shù)，但約束變元不受此限制。

(3)有公式的解釋定義可以看出，公式的解釋有許多的解釋，當D為無限集時，

公式有無限多個解釋,根本不可能將其一一列出，因而謂詞邏輯的公式不可

能有真值表可列。38:50

2.永真式和永假式

定義7:設(shè)A為一個謂詞公式,如果A在任何解釋下均為真,稱A為邏輯有效式

(或稱永真式)；如果A在任何解釋下均為假,稱A為矛盾式(或稱永假式);如果存在

一個解釋使A為真,則稱A為可滿足式；

例如：，P(x),P(x)是永真式

,P(x),P(x)是永假式

43:33

作業(yè)布置：

P14練習2.1(A)1(2)(3),2(1),(B)l,2,4

P44練習2.2(A),(B)2,5

47:28

第2編集合論

第3章集合及其運算

?3.1集合的概念和表示方法

一、集合：

將一個確定的，可以區(qū)分的事物的全體稱為集合，而這些事物稱為集合的元

素。

集合用大寫字母A,B,”來表示，而集合的元素一般用小寫字母表示。

若a是A的元素稱a屬于A,記作