《離散數(shù)學(xué)》課件-第1章

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

1.2命題公式

1.3邏輯等價與蘊(yùn)含

1.4聯(lián)結(jié)詞的完備集

1.5對偶式

1.6范式

1.7命題邏輯的推理理論第1章命題邏輯1.1.1命題

命題邏輯主要研究前提(premises)和結(jié)論(conclusion)之間的邏輯關(guān)系。例如，由前提“如果我平時不努力學(xué)習(xí)離散數(shù)學(xué)，那么我的期末成績就會不及格”和“期末成績出來，我的離散數(shù)學(xué)及格了”可以推出“我平時努力學(xué)習(xí)了”的結(jié)論。這里前提和結(jié)論都是斷言(陳述句)，具有確定的真假值，它們是推理的基本單位，在數(shù)理邏輯中稱為命題(proposition)。本節(jié)首先給出命題的定義并引入命題的邏輯運(yùn)算。1.1命題和聯(lián)結(jié)詞

定義1.1.1

一個具有真或假但不能兩者都是的斷言稱為命題。

如果一個命題所表達(dá)的判斷為真，則稱其真值(truthvalue)為“真”，用大寫字母T或數(shù)字1表示；如果一個命題所表達(dá)的判斷為假，則稱其真值為“假”，用大寫字母F或數(shù)字0表示。為簡便起見，本書在構(gòu)建真值表時一般用0表示“假”，用1表示“真”。

由命題的定義可知，命題必須滿足以下兩個條件：

(1)命題是表達(dá)判斷的陳述句。疑問句、祈使句和感嘆句等都不是命題。

(2)命題有確定的真假值，它的真值或者為真，或者為假，兩者必居其一。1.1.2聯(lián)結(jié)詞

在代數(shù)中，用“＋”、“×”等運(yùn)算符連接數(shù)字得到代數(shù)表達(dá)式，例如“3＋2”等。同樣，在數(shù)理邏輯中，也存在運(yùn)算符，稱為邏輯聯(lián)結(jié)詞(logicconnective)，簡稱聯(lián)結(jié)詞。五個常用聯(lián)結(jié)詞的定義如下所述。

1.否定聯(lián)結(jié)詞

否定聯(lián)結(jié)詞也稱為“非”運(yùn)算，它對單個命題進(jìn)行操作，是一個一元運(yùn)算符。

定義1.1.2

設(shè)P是命題，P的否定(negation)是一個復(fù)合命題，記做P

，稱為“非P”。符號用于表示否定聯(lián)結(jié)詞。P為真，當(dāng)且僅當(dāng)P為假。

下面引入真值表(truthtable)來描述復(fù)合命題的真值。真值表的左邊列出參與運(yùn)算的命題真值的所有可能組合，復(fù)合命題的真值結(jié)果列在最右邊一列。因此，否定聯(lián)結(jié)詞的定義如表1.1.1所示。表1.1.1

2.合取聯(lián)結(jié)詞

定義1.1.3

如果P和Q是命題，那么“P并且Q”是一個復(fù)合命題，記做P∧Q，稱為P和Q

的合取(conjunction)。符號∧用于表示合取聯(lián)結(jié)詞。P∧Q

為T，當(dāng)且僅當(dāng)P、Q

均為T。

“∧”是一個二元運(yùn)算符。合取聯(lián)結(jié)詞∧的定義如表1.1.2所示。表1.1.2

3.析取聯(lián)結(jié)詞

定義1.1.4

如果P和Q是命題，那么“P或Q”是一個復(fù)合命題，記做P∨Q，稱為P和Q

的析取(disjunction)。符號∨用于表示析取聯(lián)結(jié)詞。P∨Q

為T，當(dāng)且僅當(dāng)P、Q

至少有一個為T。

“∨”是一個二元運(yùn)算。析取聯(lián)結(jié)詞∨的定義如表1.1.3所示。表1.1.3

4.條件聯(lián)結(jié)詞

定義1.1.5

如果P和Q是命題，那么“如果P，那么Q”是一個復(fù)合命題，記做P→Q

，稱為P和Q

的條件命題(conditionalproposition)。符號→用于表示條件聯(lián)結(jié)詞。當(dāng)且僅當(dāng)P

為T且Q

為F時，P→Q

為F。這里，稱P

為假設(shè)(hypothesis)或前件(antecedent)，稱Q

為結(jié)論(conclusion)或后件(consequent)。

“→”是一個二元運(yùn)算。條件聯(lián)結(jié)詞→的定義如表1.1.4所示。表1.1.4

5.雙條件聯(lián)結(jié)詞

定義1.1.6

如果P和Q是命題，那么“P當(dāng)且僅當(dāng)Q”是一個復(fù)合命題，記做

P

Q，稱為P和Q的雙條件命題(biconditionalproposition)。符號用于表示雙條件聯(lián)結(jié)詞。P

Q為T，當(dāng)且僅當(dāng)P和Q

的真值相同。

“”是一個二元運(yùn)算。雙條件聯(lián)結(jié)詞的定義如表1.1.5所示。表1.1.51.2.1命題公式及其符號化

定義1.2.1

用于代表取值為真(T、1)或假(F、0)之一的變量，稱為命題變元，通常用大寫字母或帶下標(biāo)或上標(biāo)的大寫字母表示，如P、Q、R、P1、P2等。將T和F稱為命題常元。

通常把由命題常元、命題變元、聯(lián)結(jié)詞以及括弧組成的式子稱為表達(dá)式，但是只有按照特定組合規(guī)則所形成的表達(dá)式才有實際意義。1.2命題公式

定義1.2.2

命題合式公式(簡稱命題公式)：

(ⅰ)(基礎(chǔ))單個命題常元或命題變元是命題合式公式。

(ⅱ)(歸納)如果A和B是命題公式，則A、(A∧B)、(A∨B)、(A→B)、(AB)是命題合式公式。

(ⅲ)(極小性)只有有限次地應(yīng)用條款(ⅰ)和(ⅱ)生成的表達(dá)式才是命題合式公式。圖1.2.1

定義1.2.3

若B是命題公式A的一個連續(xù)段且B也是命題公式，則稱B是A

的一個子公式。

例如，

等均為的子公式。

在命題公式中，為了減少括號的使用，可以作以下約定：

(1)聯(lián)結(jié)詞運(yùn)算的優(yōu)先次序：的運(yùn)算優(yōu)先級最高，∧、∨的運(yùn)算優(yōu)先級次之，→、的運(yùn)算優(yōu)先級最低，不改變運(yùn)算先后次序的括號可省去。

(2)相同的聯(lián)結(jié)詞，按從左至右順序計算時，括號可省去。

(3)最外層的括號可省去。

定義1.2.4

把一個用自然語言敘述的命題寫成與之內(nèi)涵相同的命題公式的形式，稱為命題的符號化。

1.2.2命題公式的賦值

命題公式的真值取決于其所含命題變元的真值，為了討論命題公式，有必要引入賦值(assign)的概念。

定義1.2.5

設(shè)p1,p2,…,pn是命題公式A中出現(xiàn)的所有命題變元，如果給p1,p2,…,pn指定一組真值，則稱為對命題公式A

賦值(指派或解釋)。

不難驗證，對于含有n

個命題變元的公式，由于每個命題變元可以有0(F)、1(T)兩個不同賦值，因此有2n

個不同賦值。對含有n個命題變元的命題公式，為方便地觀察命題公式在不同賦值下的真值，可以采用真值表的方式將命題公式在所有可能賦值下的真值列出來。對于真值表,可以作如下約定：

(1)將公式中出現(xiàn)的n

個命題變元按字典升序或降序排列。

(2)對2n

個不同賦值，按其對應(yīng)的n

位二進(jìn)制數(shù)從小到大或從大到小順序排列。

(3)若公式較復(fù)雜，可從里層向外層先列出各子公式的真值，最后列出所求公式的真值。公式的真值表如表1.2.1所示。表1.2.1公式的真值表如表1.2.2所示。表1.2.2

公式的真值表如表1.2.3所示。表1.2.3

定義1.2.6

給定一個命題公式，如果在任何賦值下，它的真值都為T，則稱該命題公式為重言式(tautology)或者永真式。

定義1.2.7

給定一個命題公式，如果在任何賦值下，它的真值都為F，則稱該命題公式為矛盾式(contradiction)或者永假式。

定義1.2.8

給定一個命題公式，如果既不是永真式，也不是永假式，則稱該命題公式為偶然式(contingency)。

對于某一個命題公式A

，如果至少存在一種賦值，使得它的真值為T，則A

是可滿足式(satisfiable)。事實上,重言式和偶然式都是可滿足式。如果一個命題公式不是可滿足式，那么它是矛盾式。構(gòu)造公式的真值表，如表1.2.4所示。表1.2.41.3.1等價

定義1.3.1

給定兩個命題公式A和B，設(shè)P1,P2,…,Pn為所有出現(xiàn)在A和B中的命題變元，但Pi(i=1,2,…,n)不一定在A和B中同時出現(xiàn)，若對于P1,P2,…,Pn的任一賦值，A和B的真值都相同，則稱A和B邏輯等價(logicallyequivalent)，記做AB，讀做“A等價于B”。

要注意符號和的區(qū)別:是聯(lián)結(jié)詞，而表示兩個命題公式之間的關(guān)系。1.3邏輯等價與蘊(yùn)含由表1.3.1可見，P→Q和P∨Q在每一種賦值情況下，都具有相同的真值，所以二者是等價的。表1.3.1構(gòu)造真值表，如表1.3.2所示。表1.3.2表1.3.3列出了一些常見的命題等價公式，這些結(jié)論都可以通過構(gòu)造真值表進(jìn)行驗證。表1.3.3驗證德·摩根定律(DeMorgan’slaws)構(gòu)造真值表,如表1.3.4所示。表1.3.4

定理1.3.1(代入規(guī)則)

設(shè)

A、B是命題公式，其中A是重言式，P是A中的命題變元，如果將A中每一處出現(xiàn)的P均用B代入，則所得命題公式A′仍然是一個重言式。

定理1.3.2

設(shè)

A、B是命題公式，則A和B邏輯等價，當(dāng)且僅當(dāng)A

B是一個重言式。

定理1.3.3(替換規(guī)則)

設(shè)A、X、Y是命題公式，X是A的子公式，且有X

Y。如果將A中的X用Y來替換(不必每一處都替換)，則所得到的公式B與A等價，即B

A。

定理1.3.4(傳遞規(guī)則)

設(shè)A、B、C是命題公式，若

A

B且B

C，則有A

C。1.3.2蘊(yùn)含

定義1.3.2

設(shè)A、B是命題公式，如果A→B是一個重言式，則稱A

蘊(yùn)含(implicate)B，記做

A

B。

由表1.3.5可見，(P→Q)→P是重言式，所以(P→Q)P。表1.3.5由表1.3.6可見，P∧(P→Q)→Q是重言式，所以P∧(P→Q)

Q

。表1.3.6表1.3.7列出了一些常見的蘊(yùn)含公式，這些結(jié)論都可以通過構(gòu)造真值表進(jìn)行驗證。表1.3.7

定理1.3.5

設(shè)A和B是任意兩個命題公式，A

B當(dāng)且僅當(dāng)A

B且B

A。

下面列出蘊(yùn)含關(guān)系的幾個常用性質(zhì)：

性質(zhì)1

設(shè)A、B和C是命題公式，如果A

B并且A是重言式，則B

也是重言式。

性質(zhì)2

如果A

B并且B

C，則A

C，即蘊(yùn)含關(guān)系是傳遞的。

性質(zhì)3

如果A

B并且A

C，則A

B∧C。

性質(zhì)4

如果A

C并且B

C，則A∨B

C。

1.1節(jié)定義了5種聯(lián)結(jié)詞，那么是否使用這5種聯(lián)結(jié)詞就能夠表達(dá)所有命題呢？本節(jié)討論其他聯(lián)結(jié)詞和聯(lián)結(jié)詞的完備性理論。

對于一個一元運(yùn)算符，只作用于一個命題變元，則其可能的運(yùn)算結(jié)果就只有4種情況，如表1.4.1所示。1.4聯(lián)結(jié)詞的完備集表1.4.1對于二元運(yùn)算，有兩個命題變元參與運(yùn)算，共4種賦值，則有16種可能的運(yùn)算結(jié)果，如表1.4.2所示。表1.4.2其余幾個運(yùn)算可以定義如下新的聯(lián)結(jié)詞：關(guān)于以上4個新定義的聯(lián)結(jié)詞，有如下性質(zhì)：

定義1.4.1

給定一個聯(lián)結(jié)詞集合，如果所有的命題公式都能用其中的聯(lián)結(jié)詞等價表示出來，則稱該聯(lián)結(jié)詞集合為全功能聯(lián)結(jié)詞集合，或稱該聯(lián)結(jié)詞集合是功能完備的(functionallycomplete)。證明不是全功能聯(lián)結(jié)詞集合。

設(shè)f(P,Q)表示僅用命題變元P和Q以及聯(lián)結(jié)詞構(gòu)成的任意命題公式，現(xiàn)證明對P、Q的任意4種指派，f(P,Q)的取值封閉在表1.4.3所列的8種結(jié)果之中。表1.4.3

定義1.4.2

一個聯(lián)結(jié)詞集合是全功能的，并且去掉其中任意一個聯(lián)結(jié)詞后均不是全功能的，則稱其為極小全功能聯(lián)結(jié)詞集合。

定義1.5.1

設(shè)有命題公式A，其中僅含有聯(lián)結(jié)詞、∨和∧，如果將A中的∨換成∧，∧換成∨，常元F和T

也互相替換，所得公式記做A*，則稱A*為A的對偶(dual)公式。

顯然，A也是A*的對偶公式，即對偶是相互的，即(A*)*=A。1.5對偶式

定理1.5.1

設(shè)A和A*是對偶公式，其中僅含有聯(lián)結(jié)詞、∨和∧，P1,P2,…,Pn是出現(xiàn)在A和A*中的所有命題變元，于是有

(證明過程用到的歸納法將在本書3.4節(jié)中詳細(xì)給出。)

定理1.5.2

設(shè)A和B是命題公式，P1，P2，…，Pn是出現(xiàn)在A和B中的命題變元，則有：

(1)如果A

B，則A*B*。

(2)如果A

B，則B*A*。1.6.1析取范式和合取范式

定義1.6.1

僅由若干命題變元和若干命題變元之否定通過聯(lián)結(jié)詞∨構(gòu)成的命題公式稱為析取式。

1.6范式

定義1.6.2

僅由若干命題變元和若干命題變元之否定通過聯(lián)結(jié)詞∧組成的命題公式稱為合取式。

定義1.6.3

一個命題公式稱為析取范式(disjunctivenormalform)，當(dāng)且僅當(dāng)它具有如下形式：

A1∨A2∨…∨An(n≥1)

定義1.6.4

一個命題公式稱為合取范式(conjunctivenormalform)，當(dāng)且僅當(dāng)它具有如下形式：

A1∧A2∧…∧An(n≥1)對于任何一個命題公式，都可以求得它的合取范式或者析取范式，步驟如下：

(1)將公式中的聯(lián)結(jié)詞都?xì)w約成、∨和∧。

(2)利用德·摩根定律將否定聯(lián)結(jié)詞直接移到各命題變元之前。

(3)利用分配律、結(jié)合律將公式歸約成合取范式或者析取范式。1.6.2主析取范式

定義1.6.5

一個含n個命題變元的合取式，如果其中每個變元與其否定不同時存在，但兩者之一必須出現(xiàn)且僅出現(xiàn)一次，則稱該合取式為極小項(minterm)。

n個命題變元P1，P2，…，Pn可構(gòu)成2n個不同的極小項，具有如下形式：

現(xiàn)以兩個變元P、Q為例，編碼如下：

依次類推，含n個命題變元P1,P2,…,Pn的極小項的編碼為

表1.6.1列出了兩個變元P和Q及其極小項的真值表。由表1.6.1可以看出，沒有兩個極小項是等價的，且每個極小項都恰對應(yīng)P和Q的一組賦值使其為真。表1.6.1

n個命題變元P1,P2,…,Pn構(gòu)成的極小項具有如下性質(zhì)：

(1)每一個極小項當(dāng)其賦值與編碼相同時，其真值為T，在其余2n－1種賦值下其真值均為F。

(2)任意兩個不同極小項的合取式永假，即

(3)所有極小項的析取式永真，記為

定義1.6.6

設(shè)P1,P2,…,Pn是命題公式A中包含的所有命題變元，若由P1,P2,…,Pn的若干極小項析取所構(gòu)成的析取范式與A等價，則稱該析取范式為A的主析取范式(principledisjunctivenormalform)。

對于一個給定的命題公式，可以用構(gòu)造真值表的方法求得它的主析取范式。

定理1.6.1

在一個命題公式A的真值表中，使A的真值為T的所有賦值所對應(yīng)的極小項構(gòu)成的析取范式即為A的主析取范式。用構(gòu)造真值表的方法求命題公式P∧(Q→R)的主析取范式。構(gòu)造其真值表如表1.6.2所示。表1.6.2

P∧(Q→R)的主析取范式為

除了用真值表求一個命題公式的主析取范式外，還可以用常用等價公式進(jìn)行等價推演的方法，得到它的主析取范式。這是因為任何一個命題公式都可以求得它的析取范式，而析取范式可轉(zhuǎn)化為主析取范式，步驟如下：

(1)將原命題公式轉(zhuǎn)化為析取范式。

(2)將每個合取式等價變換為若干極小項的析取(對每個合取式填補(bǔ)沒有出現(xiàn)的變元，如缺P和P，則合取

P∨P，再應(yīng)用分配律展開)。

(3)重復(fù)的極小項只保留一個。1.6.3主合取范式

與主析取范式相對應(yīng)的還有主合取范式。下面介紹主合取范式的相關(guān)概念以及求一個命題公式的主合取范式的方法。

定義1.6.7

一個含n個命題變元的析取式，如果其中每個變元與其否定不同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次，則這樣的析取式稱為極大項(maxterm)。

n個命題變元P1，P2，…，Pn可構(gòu)成2n個不同的極大項，具有如下形式：

現(xiàn)以兩個變元P、Q為例進(jìn)行編碼。

依次類推，含n個命題變元P1,P2,…,Pn的極大項的編碼為

表1.6.3列出了兩個變元P和Q及其極大項的真值表。由表1.6.3可以看出，沒有兩表1.6.3讀者可以驗證，這個結(jié)論可以推廣到三個和三個以上變元的情況。

n個命題變元P1,P2,…,Pn構(gòu)成的極大項具有如下性質(zhì)：

(1)每一個極大項當(dāng)其真值賦值與編碼相同時，其真值為F，在其余2n－1種指派下其真值均為T。

(2)任意兩個不同極大項的析取式永真。

(3)所有極大項的合取式永假，記為

定義1.6.8

設(shè)P1,P2,…,Pn是命題公式A中包含的所有命題變元，若由P1,P2,…,Pn的若干極大項合取所構(gòu)成的合取范式與A等價，則稱其為A的主合取范式(principleconjunctivenormalform)。

對于一個給定的命題公式，也可以用真值表求得它的主合取范式。

定理1.6.2

在一個命題公式A的真值表中，使A的真值為F的所有賦值所對應(yīng)的極大項構(gòu)成的合取范式即為A的主合取范式。用構(gòu)造真值表的方法求命題公式P∧(Q→R)的主合取范式。構(gòu)造其真值表如表1.6.4所示。表1.6.4除了用真值表求一個命題公式的主合取范式外，也可以用基本等價公式進(jìn)行等價推演的方法得到它的主合取范式。這是因為任何一個命題公式都可以求得它的合取范式，而合取范式可轉(zhuǎn)化為主合取范式，步驟如下：

(1)將原命題公式轉(zhuǎn)化為合取范式。

(2)將每個析取式等價變換為若干極大項的合取(對每個析取式填補(bǔ)沒有出現(xiàn)的變元，如缺P和P，則析取P∧

P，再應(yīng)用分配律展開)。

(3)重復(fù)的極大項只保留一個。

定理1.6.3

已知由n個不同命題變元構(gòu)成的命題公式A的主析取范式為，其主合取范式為

，則有

證明由于命題公式A的主析取范式為，主合取范式為，則有

且。由此可得：

則有

因為

故有

又因為

定義1.7.1

設(shè)H1,H2,…,Hn,C是命題公式，若H1∧H2∧…∧Hn

C，則稱C是一組前提H1,H2,…,Hn的有效結(jié)論(validconclusion)，或者稱C可由前提H1,H2,…,Hn邏輯推出。從前提H1,H2,…,Hn推出結(jié)論的過程，稱為推理(reasoning)、論證(argument)或證明(proof)。1.7命題邏輯的推理理論如果H1∧H2∧…∧Hn

C，說明H1,H2,…,Hn可以邏輯推出C，即推理是正確的。但推理正確不保證結(jié)論C一定正確，結(jié)論的真假取決于前提H1∧H2∧…∧Hn的真假，前提為真時，結(jié)論C為真,前提為假時，結(jié)論C可能為真，也可能為假。

為了方便起見，通常也可將H1∧H2∧…∧Hn

C寫做H1,H2,…,Hn

C。

表1.3.3和表1.3.7所列的等價公式和蘊(yùn)含公式都可以作為推理規(guī)則使用。另外，在推理過程中還有兩條常用的重要推理規(guī)則：

(1)P規(guī)則：在推導(dǎo)過程中，前提可以在任何步驟引入。

(2)T規(guī)則：在推導(dǎo)過程中，如果由已經(jīng)推出的一個或多個公式蘊(yùn)含S，則公式S可以引入到推導(dǎo)過程中。判別結(jié)論是否有效有各種不同的方法。下面介紹幾種常用的證明方法。

方法1：無義證明法。如果能夠證明