離散數(shù)學(xué)第2章(屈)

離散數(shù)學(xué)

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

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

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

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

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

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

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

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

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

判斷

推理

正確的思維：概念清楚，判斷正確，推理合乎邏輯。人們是通過(guò)各種各樣的學(xué)習(xí)(理論學(xué)習(xí)和從實(shí)踐中學(xué)習(xí))來(lái)掌握許多概念和判斷。而形式邏輯主要是研究推理的。推理：是由若干個(gè)已知的判斷(前提)，推出新的判斷(結(jié)論)的思維過(guò)程。7推理方法類比推理：由個(gè)別事實(shí)推出個(gè)別結(jié)論。如：地球上有空氣、水，地球上有生物?；鹦巧嫌锌諝狻⑺?。

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

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

天下雨了。(個(gè)別事實(shí))

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

(大前提)：所有金屬都導(dǎo)電。(一般規(guī)律)(小前提)：銅是金屬。(個(gè)別事實(shí))

推出結(jié)論：銅能導(dǎo)電。(個(gè)別結(jié)論)9數(shù)理邏輯數(shù)理邏輯是用數(shù)學(xué)方法來(lái)研究推理過(guò)程的科學(xué)。主要是指引進(jìn)一套符號(hào)體系的方法，因此數(shù)理邏輯一般又叫“符號(hào)邏輯”?；緝?nèi)容

第二章命題邏輯

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

x表示:所有的x。設(shè)

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

x(M(x)

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

2.2命題邏輯等值演算

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

132.1命題邏輯基本概念

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

2.1.2

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

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

下列句子中那些是命題？

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

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

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

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

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

p,符號(hào)

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

p為真當(dāng)且僅當(dāng)p為假。P

PT

FF

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

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

p為假,

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

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

p∧q為真當(dāng)且僅當(dāng)p與q同時(shí)為真。

PQ

P

Q

TT

T

TF

F

FT

F

FF

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

p∧q

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

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

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

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

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

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

q:李四做這件事應(yīng)符號(hào)化為(p∧

q)∨(

p∧q)

PQ

P

Q

TT

T

TF

T

FT

T

FF

F21實(shí)例例3

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

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

u)∨(

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

w)∨(

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

q,并稱p是蘊(yùn)涵式的前件,q為蘊(yùn)涵式的后件.

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

q為假當(dāng)且僅當(dāng)p為真且q為假.

T

T

F

T

P

Q

FF

FT

TF

TT

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

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

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

q

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

只要p,就qp僅當(dāng)q

只有q

才p除非q,才p

除非q,否則非p當(dāng)p為假時(shí)，p

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

設(shè)p:天冷,q:小王穿羽絨服，將下列命題符號(hào)化

(1)只要天冷，小王就穿羽絨服.(2)因?yàn)樘炖?，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時(shí)候.注意：

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é)詞與復(fù)合命題(續(xù))定義2.5設(shè)p,q為命題,復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式,記作p

q,

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

q為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假.

p

q

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

q

T

F

F

T

P

Q

FF

FT

TF

TT

PQ26實(shí)例例5

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

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

,

,

,

,

同級(jí)按從左到右的順序進(jìn)行

pq

pp∧qp∨qp

qp

q

0010011011011010001001101111基本復(fù)合命題的真值28合式公式命題常項(xiàng):簡(jiǎn)單命題

命題變項(xiàng):真值不確定的陳述句定義2.6

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

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

B),(A

B),(A

B),(A

B)也是合式公式(4)只有有限次地應(yīng)用(1)~(3)形成的符號(hào)串才是合式公式說(shuō)明:在不影響運(yùn)算順序時(shí),括號(hào)可以省去

例如0,p,

p

q,(p

q)

(

p

r),

p

q

r,(p

q)

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

=

1

2…

n,

i=0或1,諸

i之間不加標(biāo)點(diǎn)符號(hào)(2)通常賦值與命題變項(xiàng)之間按下標(biāo)或字母順序?qū)?yīng),即當(dāng)A的全部命題變項(xiàng)為p1,p2,…,pn時(shí),給A賦值

1

2…

n是指p1=

1,p2=

2,…,pn=

n;當(dāng)A的全部命題變項(xiàng)為p,q,r,…時(shí),

給A賦值

1

2

3…是指p=

1,q=

2,r=

3,…30實(shí)例例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個(gè)變項(xiàng)的公式有2n個(gè)賦值32實(shí)例(續(xù))(2)

(

p

q)

q

pq

p

p

q

(

p

q)

(

p

q)

q00011011

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

q)

r

pqr

p

q

r

(p

q)

r

000001010011100101110111

00111111

10101010

1110101034命題公式的分類重言式(永真式):無(wú)成假賦值的命題公式矛盾式(永假式):無(wú)成真賦值的命題公式可滿足式:非矛盾式的命題公式注意:重言式是可滿足式，但反之不真.例如上例中(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若等價(jià)式A

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

B,并稱A

B是等值式說(shuō)明:(1)

不要混同于

和=(2)A與B等值當(dāng)且僅當(dāng)A與B在所有可能賦值下的真值都相同,即A與B有相同的真值表。(3)可能有啞元出現(xiàn).在B中出現(xiàn),但不在A中出現(xiàn)的命題變項(xiàng)稱作A的啞元.同樣,在A中出現(xiàn),但不在B中出現(xiàn)的命題變項(xiàng)稱作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個(gè)公式之間的等值關(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蘊(yùn)涵等值式

A

B

A

B等價(jià)等值式

A

B

(A

B)

(B

A)假言易位

A

B

B

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

A

B

A

B歸謬論(A

B)

(A

B)

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

B,則

(B)

(A)

例3

證明

p

(q

r)

(p

q)

r證

p

(q

r)

p

(

q

r)（蘊(yùn)涵等值式）

(

p

q)

r

（結(jié)合律）

(p

q)

r

（德摩根律）

(p

q)

r

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

(q

r)(p

q)

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

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

(p

q)

解q

(p

q)

q

(

p

q)（蘊(yùn)涵等值式）

q

(p

q)（德摩根律）

p

(q

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

p

0（矛盾律）

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

q)

(

q

p)解(p

q)

(

q

p)

(

p

q)

(q

p)（蘊(yùn)涵等值式）

(

p

q)

(

p

q)（交換律）

1該式為重言式.45實(shí)例(續(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為矛盾式當(dāng)且僅當(dāng)A

0;A為重言式當(dāng)且僅當(dāng)A

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

{0,1}為n元真值函數(shù)n元真值函數(shù)共有個(gè)每一個(gè)命題公式對(duì)應(yīng)于一個(gè)真值函數(shù)每一個(gè)真值函數(shù)對(duì)應(yīng)無(wú)窮多個(gè)命題公式1元真值函數(shù)

p

0001110101472元真值函數(shù)

pq

0000000000010000111110001100111101010101pq

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

設(shè)S是一個(gè)聯(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復(fù)合聯(lián)結(jié)詞與非式:p

q(p

q),

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

q為真當(dāng)且僅當(dāng)p,q不同時(shí)為真

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復(fù)合聯(lián)結(jié)詞或非式:p

q(p

q),

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

q為真當(dāng)且僅當(dāng)p,q不同時(shí)為假

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析取范式與合取范式簡(jiǎn)單析取式與簡(jiǎn)單合取式析取范式與合取范式2.3.2主析取范式與主合取范式極小項(xiàng)與極大項(xiàng)52簡(jiǎn)單析取式與簡(jiǎn)單合取式文字:命題變項(xiàng)及其否定的統(tǒng)稱簡(jiǎn)單析取式:有限個(gè)文字構(gòu)成的析取式如p,

q,p

q,p

q

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

q,p

q,p

q

r,…定理2.3

(1)一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)和它的否定(2)一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)和它的否定例如，簡(jiǎn)單析取式p

q

p是重言式。簡(jiǎn)單合取式p

p

q是矛盾式。53析取范式與合取范式析取范式:由有限個(gè)簡(jiǎn)單合取式組成的析取式

A1

A2

Ar,其中A1,A2,,Ar是簡(jiǎn)單合取式例如,

p

(pq)(p

qr)是析取范式。合取范式:由有限個(gè)簡(jiǎn)單析取式組成的合取式

A1

A2

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

q

r)

(

pq)

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

定理2.4

(1)一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每一個(gè)簡(jiǎn)單合取式都是矛盾式(2)一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每一個(gè)簡(jiǎn)單析取式都是重言式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極小項(xiàng)與極大項(xiàng)定義2.17

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

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

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

mi

Mi,

Mi

mi極小項(xiàng)極大項(xiàng)公式成真賦值名稱公式成假賦值名稱

p

q00m0

p

q00M0

p

q01m1

p

q01M1p

q10m2

p

q10M2

p

q11m3

p

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

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M1

M5

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

=B1

B2

…

Bs，其中Bj

是簡(jiǎn)單合取式j(luò)=1,2,…,s

(2)若某個(gè)Bj

既不含pi，又不含

pi，則將Bj

展開成

Bj

Bj

(pi

pi)(Bj

pi)(Bj

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

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

=B1

B2

…

Bs,其中Bj

是簡(jiǎn)單析取式j(luò)=1,2,…,s

(2)若某個(gè)Bj

既不含pi，又不含

pi

，則將Bj

展開成

Bj

Bj

(pi

pi)(Bj

pi)(Bj

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

Mi(4)將極大項(xiàng)按下標(biāo)從小到大排列61實(shí)例例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實(shí)例(續(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快速求法設(shè)公式含有n個(gè)命題變項(xiàng),則長(zhǎng)度為k的簡(jiǎn)單合取式可展開成2n

k個(gè)極小項(xiàng)的析取例如公式含p,q,r

q

(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m2

m3

m6

m7長(zhǎng)度為k的簡(jiǎn)單析取式可展開成2n

k個(gè)極大項(xiàng)的合取例如p

r

(p

q

r)(p

q

r)

M1

M364實(shí)例例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實(shí)例(續(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)求公式的成真賦值和成假賦值設(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,11167主析取范式的用途(續(xù))(2)判斷公式的類型

設(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)68實(shí)例例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)判斷兩個(gè)公式是否等值例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實(shí)例(續(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實(shí)例例5某單位要從A,B,C三人選派若干人出國(guó)考察,需滿足下述條件:(1)若A去,則C必須去;(2)若B去,則C不能去;(3)A和B必須去一人且只能去一人.問(wèn)有幾種可能的選派方案?解記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實(shí)例(續(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主合取范式由主析取范式求主合取范式設(shè)沒(méi)有出現(xiàn)的極小項(xiàng)是其中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個(gè)極大項(xiàng)重言式的主合取范式不含任何極大項(xiàng),記作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若對(duì)于每組賦值,A1ùA2ù…ù

Ak

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

推出B的推理正確當(dāng)且僅當(dāng)

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實(shí)例例1判斷下面推理是否正確:(1)若今天是1號(hào),則明天是5號(hào).今天是1號(hào).所以明天是5號(hào).解設(shè)p:今天是1號(hào),q:明天是5號(hào)推理的形式結(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實(shí)例(續(xù))(2)若今天是1號(hào),則明天是5號(hào).明天是5號(hào).所以今天是1號(hào).解設(shè)p:今天是1號(hào),q:明天是5號(hào).推理的形式結(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推理定律——重言蘊(yùn)涵式

A

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

A

化簡(jiǎn)律(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)等價(jià)三段論(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)命題變項(xiàng)符號(hào):p,q,r,…,pi,qi

,ri

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

,

,,,(3)括號(hào)與逗號(hào):()，,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)化簡(jiǎn)規(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實(shí)例例3構(gòu)造推理的證明:若明天是星期一或星期三,我就有課.若有課,今天必須備課.我今天下午沒(méi)備課.所以,明天不是星期一和星期三.解設(shè)p:明天是星期一,q:明天是星期三，

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

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

證明①r?s

前提引入②?s

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

前提引入⑤?(púq)③④拒取式⑥?pù?q⑤置換結(jié)論有效,即明天不是星期一和星期三88附加前提證明法欲證明等價(jià)地證明前提: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實(shí)例例4構(gòu)造下面推理的證明:前提:?p

úq,?