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

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

1.2命題公式

1.3邏輯等價與蘊含

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

1.5對偶式

1.6范式

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

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

定義1.1.1

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

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

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

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

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

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

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

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

定義1.1.2

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

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

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

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

定義1.1.3

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

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

為T，當且僅當P、Q

均為T。

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

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

定義1.1.4

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

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

為T，當且僅當P、Q

至少有一個為T。

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

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

定義1.1.5

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

，稱為P和Q

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

為T且Q

為F時，P→Q

為F。這里，稱P

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

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

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

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

定義1.1.6

如果P和Q是命題，那么“P當且僅當Q”是一個復合命題，記做

P

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

Q為T，當且僅當P和Q

的真值相同。

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

定義1.2.1

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

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

定義1.2.2

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

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

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

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

定義1.2.3

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

的一個子公式。

例如，

等均為的子公式。

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

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

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

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

定義1.2.4

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

1.2.2命題公式的賦值

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

定義1.2.5

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

賦值(指派或解釋)。

不難驗證，對于含有n

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

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

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

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

(2)對2n

個不同賦值，按其對應的n

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

(3)若公式較復雜，可從里層向外層先列出各子公式的真值，最后列出所求公式的真值。公式的真值表如表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)。事實上,重言式和偶然式都是可滿足式。如果一個命題公式不是可滿足式，那么它是矛盾式。構造公式的真值表，如表1.2.4所示。表1.2.41.3.1等價

定義1.3.1

給定兩個命題公式A和B，設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)結詞，而表示兩個命題公式之間的關系。1.3邏輯等價與蘊含由表1.3.1可見，P→Q和P∨Q在每一種賦值情況下，都具有相同的真值，所以二者是等價的。表1.3.1構造真值表，如表1.3.2所示。表1.3.2表1.3.3列出了一些常見的命題等價公式，這些結論都可以通過構造真值表進行驗證。表1.3.3驗證德·摩根定律(DeMorgan’slaws)構造真值表,如表1.3.4所示。表1.3.4

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

設

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

定理1.3.2

設

A、B是命題公式，則A和B邏輯等價，當且僅當A

B是一個重言式。

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

設A、X、Y是命題公式，X是A的子公式，且有X

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

A。

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

設A、B、C是命題公式，若

A

B且B

C，則有A

C。1.3.2蘊含

定義1.3.2

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

蘊含(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列出了一些常見的蘊含公式，這些結論都可以通過構造真值表進行驗證。表1.3.7

定理1.3.5

設A和B是任意兩個命題公式，A

B當且僅當A

B且B

A。

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

性質(zhì)1

設A、B和C是命題公式，如果A

B并且A是重言式，則B

也是重言式。

性質(zhì)2

如果A

B并且B

C，則A

C，即蘊含關系是傳遞的。

性質(zhì)3

如果A

B并且A

C，則A

B∧C。

性質(zhì)4

如果A

C并且B

C，則A∨B

C。

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

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

定義1.4.1

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

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

定義1.4.2

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

定義1.5.1

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

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

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

定理1.5.1

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

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

定理1.5.2

設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)結詞∨構成的命題公式稱為析取式。

1.6范式

定義1.6.2

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

定義1.6.3

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

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

定義1.6.4

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

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

(1)將公式中的聯(lián)結詞都歸約成、∨和∧。

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

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

定義1.6.5

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

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

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

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

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

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

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

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

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

定義1.6.6

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

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

定理1.6.1

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

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

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

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

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

P∨P，再應用分配律展開)。

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

與主析取范式相對應的還有主合取范式。下面介紹主合取范式的相關概念以及求一個命題公式的主合取范式的方法。

定義1.6.7

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

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

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

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

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

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

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

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

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

定義1.6.8

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

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

定理1.6.2

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

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

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

P，再應用分配律展開)。

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

定理1.6.3

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

，則有

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

且。由此可得：

則有

因為

故有

又因為

定義1.7.1

設H1,H2,…,Hn,C是命題公式，若H1∧H2∧…∧Hn

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

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

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

C寫做H1,H2,…,Hn

C。

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

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

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

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