離散數(shù)學

華南理工大學計算機學院張芩arcview@126.com1離散數(shù)學（DiscreteMath）數(shù)學所研究的對象根據(jù)它們的取值分為：

連續(xù)的，如長度、溫度、面積等。

離散的，如商店商品，學生所學課程等。離散數(shù)學是研究離散對象的結(jié)構(gòu)以及它們之間相互關(guān)系的一門數(shù)學學科。因為計算機不論硬件還是軟件都屬于離散結(jié)構(gòu)，所以所應用的數(shù)學必是離散數(shù)學。2課程的性質(zhì)、目的和任務

離散數(shù)學是計算機學科的專業(yè)基礎(chǔ)課，通過介紹離散數(shù)學的基本理論、基本思想和基本方法，使學生掌握學習后繼課程，如數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫、網(wǎng)絡、人工智能等必備的基礎(chǔ)知識和基本技術(shù)，得到一個較好的數(shù)學訓練，為從事計算機科學技術(shù)領(lǐng)域的工作打下一個扎實的理論基礎(chǔ)。

3課程的要求教學基本要求要求掌握基本概念、基本原理，培養(yǎng)學生用離散數(shù)學的觀點去分析解決計算機科學及工程應用中所遇到的問題，努力提高邏輯推理和抽象思維的能力。先修課程高等數(shù)學、線性代數(shù)4學習內(nèi)容數(shù)理邏輯

（第二、三章）計算機科學的基礎(chǔ)，應熟練掌握將現(xiàn)實生活中的條件化成邏輯公式，并能做適當?shù)耐评恚@對程序設計、數(shù)字電路等課程是極有用處的。集合論

（第一、四、五章）數(shù)學的基礎(chǔ)，對于學習程序設計、數(shù)據(jù)結(jié)構(gòu)、編譯原理等幾乎所有計算機專業(yè)課程和數(shù)學課程都很有用處。熟練掌握有關(guān)集合、映射、關(guān)系等基本概念。圖論

（第六、七章）對于解決許多實際問題很有用處，對于學習數(shù)據(jù)結(jié)構(gòu)、編譯原理課程也很有幫助。要求掌握有關(guān)圖、樹的基本概念，以及如何將圖論用于實際問題的解決，并培養(yǎng)其使用數(shù)學工具建立模型的思維方式。5數(shù)理邏輯邏輯是研究人的思維的科學。辯證邏輯：研究人的思維中的辯證法。

用全面的和發(fā)展的觀點觀察事物；具體問題具體分析；實踐是檢查事物正誤的唯一標準；等等。形式邏輯：研究人的思維的形式和一般規(guī)律。這里我們只關(guān)心形式邏輯。6形式邏輯人的思維過程：概念

判斷

推理

正確的思維：概念清楚，判斷正確，推理合乎邏輯。人們是通過各種各樣的學習(理論學習和從實踐中學習)來掌握許多概念和判斷。而形式邏輯主要是研究推理的。推理：是由若干個已知的判斷(前提)，推出新的判斷(結(jié)論)的思維過程。7推理方法類比推理：由個別事實推出個別結(jié)論。如：地球上有空氣、水，地球上有生物。火星上有空氣、水。

火星上有生物。歸納推理：由若干個別事實推出一般結(jié)論。如：銅能導電。鐵能導電。錫能導電。鉛能導電。

一切金屬都導電。演繹推理：由一般規(guī)律推出個別事實。形式邏輯主要是研究演繹推理的。8演繹推理舉例例1：如果天下雨，則路上有水。(一般規(guī)律)

天下雨了。(個別事實)

推出結(jié)論：路上有水。(個別結(jié)論)例2：

(大前提)：所有金屬都導電。(一般規(guī)律)(小前提)：銅是金屬。(個別事實)

推出結(jié)論：銅能導電。(個別結(jié)論)9數(shù)理邏輯數(shù)理邏輯是用數(shù)學方法來研究推理過程的科學。主要是指引進一套符號體系的方法，因此數(shù)理邏輯一般又叫“符號邏輯”。基本內(nèi)容

第二章命題邏輯

第三章一階邏輯10數(shù)理邏輯把推理符號化之一設P表示：天下雨。設Q表示：路上有水。設表示：如果…則…例1的推理過程表示為：前提1:PQ(如果天下雨,則路上有水。)前提2：P(天下雨了。)結(jié)論：Q(路上有水。)這就是第二章“命題邏輯”中要討論的問題。11數(shù)理邏輯把推理符號化之二設M(x):x是金屬。設C(x):x能導電。設

x表示:所有的x。設

a表示銅。例2的推理過程表示為：前提1:

x(M(x)

C(x))(所有金屬都導電)前提2:M(a)(銅是金屬)結(jié)論:C(a)(銅能導電)其中符號M(x)是謂詞，所以這就是第三章“一階邏輯”中所討論的內(nèi)容.12第2章命題邏輯2.1命題邏輯基本概念

2.2命題邏輯等值演算

2.3范式2.4命題邏輯推理理論

132.1命題邏輯基本概念

2.1.1命題與聯(lián)結(jié)詞命題與真值(簡單命題,復合命題)聯(lián)結(jié)詞(?,,,,)

2.1.2

命題公式與分類命題公式及其賦值真值表命題公式的分類

14命題及其真值命題:判斷的結(jié)果惟一的陳述句命題的真值:判斷的結(jié)果,真或假真命題:真值為真的命題假命題:真值為假的命題注意:感嘆句、祈使句、疑問句都不是命題。陳述句中的悖論以及判斷的結(jié)果不惟一確定的也不是命題。15例1

下列句子中那些是命題？

(1)北京是中華人民共和國的首都.(2)2+5＝8.(3)x+5＞3.(4)你會開車嗎？(5)2050年元旦北京是晴天.(6)這只兔子跑得真快呀！(7)請關(guān)上門！(8)我正在說謊話.真命題假命題真值不確定疑問句感嘆句祈使句悖論(1),(2),(5)是命題,(3),(4),(6),(7),(8)都不是命題真值確定,但未知實例16簡單命題與復合命題簡單命題(原子命題):簡單陳述句構(gòu)成的命題簡單命題的符號化:p,q,r,…,pi,qi

,ri(i≥1)用“1”表示真，用“0”表示假復合命題:由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句

例如如果明天天氣好,我們就出去郊游設p:明天天氣好,q:我們出去郊游,如果p,則q

又如張三一面喝茶一面看報設p:張三喝茶,q:張三看報,p并且q17聯(lián)結(jié)詞與復合命題定義2.1

設p為命題,復合命題“非p”(或“p的否定”)稱為p的否定式,記作

p,符號

稱作否定聯(lián)結(jié)詞,并規(guī)定

p為真當且僅當p為假。P

PT

FF

T例如p:2是合數(shù),

p:2不是合數(shù),

p為假,

p為真18聯(lián)結(jié)詞與復合命題定義2.2

設p,q為二命題,復合命題“p并且q”(或“p與q”)稱為p與q的合取式,記作p∧q,∧稱作合取聯(lián)結(jié)詞,并規(guī)定

p∧q為真當且僅當p與q同時為真。

PQ

P

Q

TT

T

TF

F

FT

F

FF

F例如p:2是偶數(shù),q:2是素數(shù),

p∧q

:2是偶素數(shù),p為真,q為真,p∧q為真“和”，“與”，“并且”，“既...又...”，“不僅...而且...”“雖然...但是...”19實例例2

將下列命題符號化.(1)王曉既用功又聰明.(2)王曉不僅聰明，而且用功.(3)王曉雖然聰明，但不用功.(4)

張輝與王麗都是三好生.(5)張輝與王麗是同學.解

記p:王曉用功,q:王曉聰明(1)p∧q(2)p∧q(3)

p∧q(4)記r:張輝是三好生,s:王麗是三好生,r∧s(5)簡單命題,記

t:張輝與王麗是同學20聯(lián)結(jié)詞與復合命題(續(xù))定義2.3設p,q為命題,復合命題“p或q”稱作p與q的析取式,記作p∨q,∨稱作析取聯(lián)結(jié)詞,并規(guī)定p∨q為假當且僅當p與q同時為假.例如張三和李四至少有一人會英語設p:張三會英語,q:李四會英語,符號化為p∨q“相容或”與“排斥或”例如這件事只能由張三和李四中的一人去做設p:張三做這件事,

q:李四做這件事應符號化為(p∧

q)∨(

p∧q)

PQ

P

Q

TT

T

TF

T

FT

T

FF

F21實例例3

將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)元元只能拿一個蘋果或一個梨.(5)王曉紅生于1975年或1976年.解記p:2是素數(shù),q:3是素數(shù),r:4是素數(shù),s:6是素數(shù)(1)p∨r,(2)

p∨q,(3)r∨s,(4)記t:元元拿一個蘋果,u:元元拿一個梨真值:1真值:1真值:0(t∧

u)∨(

t∧u)(5)記v:王曉紅生于1975年,w:王曉紅生于1976年(v∧

w)∨(

v∧w)22聯(lián)結(jié)詞與復合命題(續(xù))定義2.4設p,q為二命題,復合命題“如果p,則q”稱作p與q的蘊涵式,記作p

q,并稱p是蘊涵式的前件,q為蘊涵式的后件.

稱作蘊涵聯(lián)結(jié)詞,并規(guī)定,p

q為假當且僅當p為真且q為假.

T

T

F

T

P

Q

FF

FT

TF

TT

PQ例如如果明天天氣好,我們就出去郊游。設p:明天天氣好,

q:我們出去郊游,形式化為p

q23蘊涵聯(lián)結(jié)詞(續(xù))p

q

的邏輯關(guān)系:q為p的必要條件“如果p,則q”的多種表述方式：若p,就q

只要p,就qp僅當q

只有q

才p除非q,才p

除非q,否則非p當p為假時，p

q為真(不管q為真還是為假)24實例例4

設p:天冷,q:小王穿羽絨服，將下列命題符號化

(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當天冷的時候.注意：

p

q與

q

p

等值（真值相同）p

qp

q

q

p

或p

q

q

p

或p

qq

p

p

q

或q

p

p

q或

q

pq

p25聯(lián)結(jié)詞與復合命題(續(xù))定義2.5設p,q為命題,復合命題“p當且僅當q”稱作p與q的等價式,記作p

q,

稱作等價聯(lián)結(jié)詞.并規(guī)定p

q為真當且僅當p與q同時為真或同時為假.

p

q

的邏輯關(guān)系:p與q互為充分必要條件例如這件事張三能做好,且只有張三能做好。設p:張三做這件事,q:這件事做好了。形式化為:p

q

T

F

F

T

P

Q

FF

FT

TF

TT

PQ26實例例5

求下列復合命題的真值(1)2+2＝4當且僅當3+3＝6.(2)2+2＝4當且僅當3是偶數(shù).(3)2+2＝4當且僅當太陽從東方升起.(4)2+2＝5

當且僅當美國位于非洲.101127聯(lián)結(jié)詞與復合命題(續(xù))聯(lián)結(jié)詞優(yōu)先級:(),

,

,

,

,

同級按從左到右的順序進行

pq

pp∧qp∨qp

qp

q

0010011011011010001001101111基本復合命題的真值28合式公式命題常項:簡單命題

命題變項:真值不確定的陳述句定義2.6

合式公式(命題公式,公式)遞歸定義如下：(1)單個命題常項或變項是合式公式,并稱作原子合式公式(2)若A是合式公式,則(

A)也是合式公式(3)若A,B是合式公式,則(A

B),(A

B),(A

B),(A

B)也是合式公式(4)只有有限次地應用(1)~(3)形成的符號串才是合式公式說明:在不影響運算順序時,括號可以省去

例如0,p,

p

q,(p

q)

(

p

r),

p

q

r,(p

q)

r29公式的賦值定義2.8設p1,p2,…,pn是出現(xiàn)在公式A中全部的命題變項,給p1,p2,…,pn指定一組真值,稱為對A的一個賦值或解釋.使公式為真的賦值稱作成真賦值,使公式為假的賦值稱作成假賦值。說明:(1)賦值記作

=

1

2…

n,

i=0或1,諸

i之間不加標點符號(2)通常賦值與命題變項之間按下標或字母順序?qū)?即當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,…30實例例6

公式A=(

p1

p2

p3

)

(p1

p2)000是成真賦值,001是成假賦值公式B=(p

q)

r000是成假賦值,001是成真賦值31真值表例7給出公式的真值表(1)

(q

p)

q

p

pq

q

p

(q

p)

q

(q

p)

q

p

00011011

1011

0001

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

(

p

q)

q

pq

p

p

q

(

p

q)

(

p

q)

q00011011

110011010010000033實例(續(xù))(3)(p

q)

r

pqr

p

q

r

(p

q)

r

000001010011100101110111

00111111

10101010

1110101034命題公式的分類重言式(永真式):無成假賦值的命題公式矛盾式(永假式):無成真賦值的命題公式可滿足式:非矛盾式的命題公式注意:重言式是可滿足式，但反之不真.例如上例中(1)

(q

p)

q

p為重言式(2)

(

p

q)

q為矛盾式(3)(p

q)

r為可滿足式352.2命題邏輯等值演算2.2.1等值式與等值演算等值式與基本等值式真值表法與等值演算法2.2.2聯(lián)結(jié)詞完備集真值函數(shù)聯(lián)結(jié)詞完備集與非聯(lián)結(jié)詞和或非聯(lián)結(jié)詞36定義2.11若等價式A

B是重言式,則稱A與B等值,記作A

B,并稱A

B是等值式說明:(1)

不要混同于

和=(2)A與B等值當且僅當A與B在所有可能賦值下的真值都相同,即A與B有相同的真值表。(3)可能有啞元出現(xiàn).在B中出現(xiàn),但不在A中出現(xiàn)的命題變項稱作A的啞元.同樣,在A中出現(xiàn),但不在B中出現(xiàn)的命題變項稱作B的啞元.啞元的值不影響命題公式的真值.等值式37真值表法例1

判斷

(p

q)與

p

q

是否等值解結(jié)論:

(p

q)

(

p

q)

pq

p

qp

q

(p

q)

p

q

(p

q)(

p

q)0011011101101001100110011100100138真值表法(續(xù))例2判斷下述3個公式之間的等值關(guān)系:

p

(q

r),(p

q)

r,(p

q)

r解

pqrp

(q

r)(p

q)

r(p

q)

r000101

001111010101011111100111101111110000111111p

(q

r)與(p

q)

r等值,但與(p

q)

r不等值39基本等值式雙重否定律

A

A冪等律

A

A

A,A

A

A交換律

A

B

B

A,A

B

B

A結(jié)合律(A

B)

C

A

(B

C)(A

B)

C

A

(B

C)分配律

A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)德摩根律

(A

B)

A

B

(A

B)

A

B吸收律

A

(A

B)

A,A

(A

B)

A40基本等值式(續(xù))零律

A

1

1,A

0

0同一律

A

0

A,

A

1

A排中律

A

A

1矛盾律

A

A

0蘊涵等值式

A

B

A

B等價等值式

A

B

(A

B)

(B

A)假言易位

A

B

B

A等價否定等值式

A

B

A

B歸謬論(A

B)

(A

B)

A41等值演算等值演算:由已知的等值式推演出新的等值式的過程置換規(guī)則:若A

B,則

(B)

(A)

例3

證明

p

(q

r)

(p

q)

r證

p

(q

r)

p

(

q

r)（蘊涵等值式）

(

p

q)

r

（結(jié)合律）

(p

q)

r

（德摩根律）

(p

q)

r

（蘊涵等值式）42實例等值演算不能直接證明兩個公式不等值.證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假.例4證明:p

(q

r)(p

q)

r方法一真值表法（見例2）方法二觀察法.容易看出000使左邊成真,使右邊成假.方法三先用等值演算化簡公式,再觀察.43實例例5

用等值演算法判斷下列公式的類型(1)q

(p

q)

解q

(p

q)

q

(

p

q)（蘊涵等值式）

q

(p

q)（德摩根律）

p

(q

q)（交換律，結(jié)合律）

p

0（矛盾律）

0（零律）該式為矛盾式.44實例(續(xù))(2)(p

q)

(

q

p)解(p

q)

(

q

p)

(

p

q)

(q

p)（蘊涵等值式）

(

p

q)

(

p

q)（交換律）

1該式為重言式.45實例(續(xù))(3)((p

q)

(p

q))

r)解((p

q)

(p

q))

r)

(p

(q

q))

r

（分配律）

p

1

r

（排中律）

p

r

（同一律）非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié):A為矛盾式當且僅當A

0;A為重言式當且僅當A

1說明:演算步驟不惟一,應盡量使演算短些46真值函數(shù)定義2.12稱F:{0,1}n

{0,1}為n元真值函數(shù)n元真值函數(shù)共有個每一個命題公式對應于一個真值函數(shù)每一個真值函數(shù)對應無窮多個命題公式1元真值函數(shù)

p

0001110101472元真值函數(shù)

pq

0000000000010000111110001100111101010101pq

001111111101000011111000110011110101010148聯(lián)結(jié)詞完備集定義2.13

設S是一個聯(lián)結(jié)詞集合,如果任何n(n

1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示,則稱S是聯(lián)結(jié)詞完備集定理2.1下述聯(lián)結(jié)詞集合都是完備集:(1)S1={

,

,

,

,

}(2)S2={

,

,

,

}(3)S3={

,

,

}(4)S4={

,

}(5)S5={

,

}(6)S6={

,

}A

B(A

B)(B

A)A

B

A

BA

B

(A

B)

(A

B)A

B

(A

B)A

B

(A)B

A

B49復合聯(lián)結(jié)詞與非式:p

q(p

q),

稱作與非聯(lián)結(jié)詞p

q為真當且僅當p,q不同時為真

T

T

T

Fp

q

FF

FT

TF

TT

pqpp

(p

p)

p(pq)(pq)

（p

q)

p

q(pp)(qq)

p

q

p

q50復合聯(lián)結(jié)詞或非式:p

q(p

q),

稱作或非聯(lián)結(jié)詞p

q為真當且僅當p,q不同時為假

T

F

F

Fp

q

FF

FT

TF

TT

pqp

p

(p

p)

p(pq)(pq)

（p

q)

p

q(pp)(qq)

p

q

p

q定理2.2{

},{

}是聯(lián)結(jié)詞完備集512.3范式2.3.1析取范式與合取范式簡單析取式與簡單合取式析取范式與合取范式2.3.2主析取范式與主合取范式極小項與極大項52簡單析取式與簡單合取式文字:命題變項及其否定的統(tǒng)稱簡單析取式:有限個文字構(gòu)成的析取式如p,

q,p

q,p

q

r,…簡單合取式:有限個文字構(gòu)成的合取式如p,

q,p

q,p

q

r,…定理2.3

(1)一個簡單析取式是重言式當且僅當它同時含某個命題變項和它的否定(2)一個簡單合取式是矛盾式當且僅當它同時含某個命題變項和它的否定例如，簡單析取式p

q

p是重言式。簡單合取式p

p

q是矛盾式。53析取范式與合取范式析取范式:由有限個簡單合取式組成的析取式

A1

A2

Ar,其中A1,A2,,Ar是簡單合取式例如,

p

(pq)(p

qr)是析取范式。合取范式:由有限個簡單析取式組成的合取式

A1

A2

Ar,其中A1,A2,,Ar是簡單析取式例如：(p

q

r)

(

pq)

q是合取范式。范式:析取范式與合取范式的統(tǒng)稱

定理2.4

(1)一個析取范式是矛盾式當且僅當它的每一個簡單合取式都是矛盾式(2)一個合取范式是重言式當且僅當它的每一個簡單析取式都是重言式54范式存在定理定理2.5

任何命題公式都存在著與之等值的析取范式與合取范式.證求公式A的范式的步驟：(1)消去A中的

,

A

B

A

B

A

B

(

A

B)

(A

B)(2)否定聯(lián)結(jié)詞

的內(nèi)移或消去

A

A

(A

B)

A

B

(A

B)

A

B55范式存在定理(續(xù))(3)使用分配律A

(B

C)

(A

B)

(A

C)求合取范式

A

(B

C)

(A

B)

(A

C)求析取范式例1

求

(p

q)

r的析取范式與合取范式解

(p

q)

r

(

p

q)

r

(p

q)

r

析取范式

(p

r)(q

r)合取范式注意:公式的析取范式與合取范式不惟一.56極小項與極大項定義2.17

在含有n個命題變項的簡單合取式(簡單析取式)中,若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項或它的否定式出現(xiàn)在從左算起的第i位上(按下標或字母順序排列),稱這樣的簡單合取式(簡單析取式)為極小項(極大項)。說明:(1)

n個命題變項產(chǎn)生2n個極小項和2n個極大項(2)2n個極小項(極大項)均互不等值(3)用mi表示第i個極小項,其中i是該極小項成真賦值的十進制表示.用Mi表示第i個極大項,其中i是該極大項成假賦值的十進制表示,mi(Mi)稱為極小項(極大項)的名稱.

57極小項與極大項(續(xù))定理2.6設mi與Mi是由同一組命題變項形成的極小項和極大項,則

mi

Mi,

Mi

mi極小項極大項公式成真賦值名稱公式成假賦值名稱

p

q00m0

p

q00M0

p

q01m1

p

q01M1p

q10m2

p

q10M2

p

q11m3

p

q11M3p,q形成的極小項與極大項58主析取范式與主合取范式主析取范式:由極小項構(gòu)成的析取范式主合取范式:由極大項構(gòu)成的合取范式例如，n=3,命題變項為p,q,r時，(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M1

M5

是主合取范式定理2.7任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是惟一的.59求主析取范式的步驟設公式A含命題變項p1,p2,…,pn(1)求A的析取范式A

=B1

B2

…

Bs，其中Bj

是簡單合取式j=1,2,…,s

(2)若某個Bj

既不含pi，又不含

pi，則將Bj

展開成

Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)重復這個過程,直到所有簡單合取式都是長度為n的極小項為止(3)消去重復出現(xiàn)的極小項,即用mi代替mi

mi(4)將極小項按下標從小到大排列60求主合取范式的步驟設公式A含命題變項p1,p2,…,pn(1)求A的合取范式A

=B1

B2

…

Bs,其中Bj

是簡單析取式j=1,2,…,s

(2)若某個Bj

既不含pi，又不含

pi

，則將Bj

展開成

Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)重復這個過程,直到所有簡單析取式都是長度為n的極大項為止(3)消去重復出現(xiàn)的極大項,即用Mi代替Mi

Mi(4)將極大項按下標從小到大排列61實例例1(續(xù))

求

(p

q)

r的主析取范式與主合取范式解(1)

(p

q)

r

(p

q)

r

p

q

(p

q)1同一律

(p

q)(r

r)排中律

(p

q

r)

(p

q

r)分配律

m4

m5

r

(p

p)(q

q)

r

同一律,排中律

(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m0

m2

m4

m6

分配律得

(p

q)

r

m0

m2

m4

m5

m6可記作

(0,2,4,5,6)62實例(續(xù))(2)

(p

q)

r

(p

r)(q

r)

p

r

p0r

同一律

p(q

q)r矛盾律(p

q

r)(p

q

r)

分配律

M1

M3

q

r

(p

p)q

r

同一律,矛盾律(p

q

r)

(

p

q

r)分配律

M3

M7得

(p

q)

r

M1

M3

M7可記作

(1,3,7)63快速求法設公式含有n個命題變項,則長度為k的簡單合取式可展開成2n

k個極小項的析取例如公式含p,q,r

q

(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m2

m3

m6

m7長度為k的簡單析取式可展開成2n

k個極大項的合取例如p

r

(p

q

r)(p

q

r)

M1

M364實例例2(1)求A(p

q)(p

q

r)

r

的主析取范式解用快速求法(1)

p

q

(

p

q

r)

(

p

q

r)

m2

m3

p

q

r

m1r

(

p

q

r)

(

p

q

r)

(p

q

r)

(p

q

r)

m1

m3

m5

m7得A

m1

m2

m3

m5

m7

(1,2,3,5,7)65實例(續(xù))(2)求B

p(p

q

r)的主合取范式解

p

(

p

q

r)(

p

q

r)

(

p

q

r)

(

p

q

r)

M4

M5

M6

M7p

q

r

M1得B

M1

M4

M5

M6

M7

(1,4,5,6,7)66主析取范式的用途(1)求公式的成真賦值和成假賦值設公式A含n個命題變項,A的主析取范式有s個極小項,則A有s個成真賦值,它們是極小項下標的二進制表示,其余2n

s

個賦值都是成假賦值例如

(p

q)

r

m0

m2

m4

m5

m6

成真賦值:000,010,100,101,110;成假賦值:001,011,11167主析取范式的用途(續(xù))(2)判斷公式的類型

設A含n個命題變項，則

A為重言式當且僅當A的主析取范式含2n個極小項A為矛盾式當且僅當

A的主析取范式不含任何極小項,記作0A為可滿足式當且僅當A的主析取范式中至少含一個極小項68實例例3用主析取范式判斷公式的類型:(1)A

(p

q)

q

(2)B

p(p

q)(3)C(p

q)r解(1)A

(

p

q)

q

(p

q)

q0矛盾式(2)B

p(p

q)1m0

m1

m2

m3

重言式(3)C

(p

q)r

(p

q)r

(p

q

r)(p

q

r)(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m0

m1

m3

m5

m7

非重言式的可滿足式69主析取范式的用途(續(xù))(3)判斷兩個公式是否等值例4用主析取范式判斷下面2組公式是否等值:(1)p與(p

q)(p

q)解p

p(q

q)(p

q)(p

q)

m2

m3(p

q)(p

q)(p

q)(p

q)

(p

q)(p

q)

m2

m3故p

(p

q)(p

q)70實例(續(xù))(2)(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

r)

m1

m3

m5

m6

m7p(q

r)(p

q)(p

r)(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m5

m6

m7故(p

q)r

p(q

r)71實例例5某單位要從A,B,C三人選派若干人出國考察,需滿足下述條件:(1)若A去,則C必須去;(2)若B去,則C不能去;(3)A和B必須去一人且只能去一人.問有幾種可能的選派方案?解記p:派A去,q:派B去,r:派C去(1)p

r,(2)q

r,(3)(p

q)

(

p

q)求下式的成真賦值A(chǔ)=(p

r)

(q

r)

((p

q)

(

p

q))72實例(續(xù))求A的主析取范式A=(p

r)

(q

r)

((p

q)

(

p

q))

(

p

r)

(

q

r)

((p

q)

(

p

q))((

p

q)

(

p

r)

(r

q)

(r

r))

((p

q)

(

p

q))((

p

q)

(p

q))((

p

r)

(p

q))

((r

q)

(p

q))

((

p

q)

(

p

q))((

p

r)

(

p

q))((r

q)

(

p

q))

(p

q

r)(p

q

r)成真賦值:101,010結(jié)論:方案1派A與C去,方案2派B去73主合取范式由主析取范式求主合取范式設沒有出現(xiàn)的極小項是其中t=2n

s,于是74主合取范式(續(xù))例6求A=(p

q

r)(p

q

r)(p

q

r)的主合取范式解A

m1

m3

m7

M0

M2

M4

M5

M6矛盾式的主合取范式含全部2n個極大項重言式的主合取范式不含任何極大項,記作175pqr000001010011100

101110111p

（q

r)

00001011p

（q

r)(4,6,7)

（主析取范式）

(0,1,2,3,5)（主合取范式）已知真值表，寫出主范式。例題762.4命題邏輯推理理論2.4.1推理的形式結(jié)構(gòu)推理的前提與結(jié)論,正確推理推理定律2.4.2自然推理系統(tǒng)P推理規(guī)則直接證明法,附加前提證明法,歸謬法(反證法),歸結(jié)證明法77有效推理定義2.20若對于每組賦值,A1ùA2ù…ù

Ak

為假,或者當A1ùA2ù…ùAk為真時,B也為真,則稱由前提A1,A2,…,Ak推B的推理有效或推理正確,并稱B是有效的結(jié)論定理2.8由前提A1,A2,…,Ak

推出B的推理正確當且僅當

A1ùA2ù…ùAk?B為重言式.78推理的形式結(jié)構(gòu)形式(1)

A1ùA2ù…ùAk?B形式(2)前提:A1,A2,…,Ak

結(jié)論:B

推理正確記作A1ùA2ù…ùAkTB判斷推理是否正確的方法:真值表法等值演算法主析取范式法構(gòu)造證明法79實例例1判斷下面推理是否正確:(1)若今天是1號,則明天是5號.今天是1號.所以明天是5號.解設p:今天是1號,q:明天是5號推理的形式結(jié)構(gòu)為(p?q)ùp?q證明用等值演算法(p?q)ùp?q

?

?((?púq)ùp)úq?((pù?q)ú?p)úq?((pú?p)ù(?qú?p))úq?(1ù(?qú?p))úq?

?pú

(?qúq)?1得證推理正確80實例(續(xù))(2)若今天是1號,則明天是5號.明天是5號.所以今天是1號.解設p:今天是1號,q:明天是5號.推理的形式結(jié)構(gòu)為(p?q)ùq?p證明用主析取范式法(p?q)ùq?p

?(?púq)ùq?p

?

q?p

?

?qúp

?(?pù?q)ú(pù?q)ú(pù?q)ú(pùq)

?

m0úm2úm301是成假賦值,所以推理不正確.81推理定律——重言蘊涵式

A

T(AúB)附加律(AùB)T

A

化簡律(A?B)ùA

T

B

假言推理(A?B)ù?B

T

?A

拒取式(AúB)ù?B

T

A

析取三段論(A?B)ù(B?C)T(A?C)假言三段論(A?B)ù(B?C)T(A?C)等價三段論(A?B)ù(C?D)ù(AúC)T(BúD)構(gòu)造性二難(A?B)ù(?A?B)ù(Aú?A)T

B

構(gòu)造性二難(特殊形式)(A?B)ù(C?D)ù(?Bú?D)T(?Aú?C)破壞性二難82自然推理系統(tǒng)P自然推理系統(tǒng)P由下述3部分組成:1.字母表(1)命題變項符號:p,q,r,…,pi,qi

,ri

,…(2)聯(lián)結(jié)詞:

,

,,,(3)括號與逗號:()，,2.合式公式3.推理規(guī)則(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則83自然推理系統(tǒng)P(續(xù))(7)拒取式規(guī)則

A?B

?B

\?A(8)假言三段論規(guī)則

A?B

B?C

\A?C

(4)假言推理規(guī)則

A?BA

\B(5)附加規(guī)則

A

\AúB(6)化簡規(guī)則

AùB

\A

84自然推理系統(tǒng)P(續(xù))(11)破壞性二難推理規(guī)則

A?B

C?D

?Bú?D

\?Aú?C(12)合取引入規(guī)則

A

B

\AùB

(9)析取三段論規(guī)則

AúB

?B

\A(10)構(gòu)造性二難推理規(guī)則

A?B

C?D

AúC

\BúD85直接證明法例2在自然推理系統(tǒng)P中構(gòu)造下面推理的證明:前提:

púq,q?r,p?s,?s結(jié)論:rù(púq)證明①

p?s前提引入

②?s

前提引入

③

?p

①②拒取式

④

púq

前提引入

⑤q

③④析取三段論

⑥q?r

前提引入

⑦r

⑤⑥假言推理

⑧rù(púq)

⑦④合取推理正確,rù(púq)是有效結(jié)論86實例例3構(gòu)造推理的證明:若明天是星期一或星期三,我就有課.若有課,今天必須備課.我今天下午沒備課.所以,明天不是星期一和星期三.解設p:明天是星期一,q:明天是星期三，

r:我有課，s:我備課前提:(púq)?r,r?s,?s結(jié)論:?pù?q

87實例(續(xù))前提:(púq)?r,r?s,?s結(jié)論:?pù?q

證明①r?s

前提引入②?s

前提引入③?r①②拒取式④(púq)?r

前提引入⑤?(púq)③④拒取式⑥?pù?q⑤置換結(jié)論有效,即明天不是星期一和星期三88附加前提證明法欲證明等價地證明前提:A1,A2,…,Ak

前提:A1,A2,…,Ak

,C結(jié)論:C?B結(jié)論:B理由:(A1ùA2ù…ùAk)?(C?B)

?

?(A1ùA2ù…ùAk)ú(?CúB)

?

?(A1ùA2ù…ùAkùC)úB

?(A1ùA2ù…ùAkùC)?B89實例例4構(gòu)造下面推理的證明:前提:?p

úq,?