離散數學

2/31Whatis

DiscreteMathematics?又稱電腦數學是現代數學的重要分支電腦專業課程中的核心基礎課程之一Mathematicsthatdealswithdiscreteobjectsandstructures緒論3/31WhatisDiscreteMathematics?離散數學是專門研究離散量的結構與相互間關係的數學理論與數學方法屬於現代數學的一個分支，是電腦科學基礎理論的核心課程，是電腦專業(CS、CE、SE)最重要的專業基礎課之一旨在訓練分析問題的能力介紹研究問題的方法論培養抽象思維和嚴密邏輯推理的能力4/31離散對象（DiscreteObjects）有限或可數個元素Separatedfromeachother(Oppositeofcontinuous)e.g.,integers,people,house,Continuousobjects:e.g.,realnumber離散結構（DiscreteStructures）Theabstractmathematicalstructuresusedtorepresentdiscreteobjectsandrelationshipsbetweentheobjectse.g.集合(sets),關係(relations),圖(graphs)WhatisDiscreteMathematics?5/31離散性是電腦科學的顯著特點也是研究自動控制、管理科學、電子工程等的重要工具Informationisstoredandmanipulatedbycomputersinadiscretefashion.0101101…Asastudentincomputersciencemajor,youneedtoknowthebasiclanguageandconceptualfoundationforallofthecomputerscience,i.e.,DiscreteMath!Discretemathconceptsarealsowidelyusedthroughoutmath,science,engineering,economics,biology,etc.,…Whystudy

DiscreteMathematics?6/31Gettrainingforrationalthought!離散數學是一門高度概括性、抽象性的科學研究一類問題的解決方法為一類問題建立統一的求解過程按照規定的程式步驟機械地進行下去為機械化提供可能Whystudy

DiscreteMathematics?7/31UsesofDiscreteMathinComputerScienceNetworkingDatabaseImageProcessingProgrammingLanguagesCompilers&InterpretersArtificialIntelligenceDigitalCircuit&CircuitDesignComputerArchitectureOperatingSystemsSecurity&Cryptography(密碼學)AdvancedAlgorithms&DataStructuresGraphics&Animationlogistics(物流)SoftwareEngineering8/31Somequestions在舉重比賽中，有兩名副裁判，一名主裁判。當兩名以上裁判（必須包括主裁判在內）認為運動員舉杠鈴合格，按電鈕，才裁決合格。試設計該表決器的電路。設計一臺自動售貨機，它只能接受五毛和一元的硬幣，當投入硬幣總值超過一塊五時，給出一根冰棍，並找回餘額。9/31Somequestions印刷電路板需要多少層？哪些線路斷開會導致整個電路不通？網路設計的可靠性怎麼樣？如果某些線路受損是否還能通訊？10/31Somequestions有N個士兵（1<=N<=100),編號依次為1,2,...,N.佇列訓練時，指揮官要把士兵從高到矮排成一行，但指揮官只知道“1比2高，7比5高”這樣的比較結果，能否把士兵排好隊呢？在設計一個組裝工件的流水線時，我們知道零件2要在零件1之前裝，零件5要在零件9之前裝…，如何設計這個流水線呢？11/31軟體工程的離散數學基礎抽象與逐步求精

為了對付大型複雜的軟體系統，須採用傳統的“分解”方法。軟體工程的分解是從橫向和縱向(即空間和時間)兩個方面進行的。

自頂向下逐層分解的過程，也是一個逐層抽象的過程。12/31軟體工程的離散數學基礎抽象

人類在認識複雜現象的過程中使用的最強有力的思維工具是抽象。人們在實踐中認識到，在現實世界中一定事物、狀態或過程之間總存在著某些相似的方面(共性)。把這些相似的方面集中和概括起來，暫時忽略它們之間的差異，這就是抽象。或者說，抽象就是抽出事物的本質特性而暫時不考慮它們的細節。13/31軟體工程的離散數學基礎抽象

由於人類思維能力的限制，如果每次面臨的因素太多，是不可能做出精確思維的。處理複雜系統的惟一有效的方法是用層次的方式構造和分析它。一個複雜的動態系統首先可以用一些高級的抽象概念構造和理解，這些高級概念又可以用一些較低級的概念構造和理解，如此進行下去，直至最低層的具體元素。14/31軟體工程的離散數學基礎抽象

軟體工程過程的每一步都是對軟體解法的抽象層次的一次精化。在可行性研究階段，軟體作為系統的一個完整部件；在需求分析期間，軟體解法是使用在問題環境內熟悉的方式描述的；當由總體設計向詳細設計過渡時，抽象的程度也就隨之減少了；最後，當根源程式寫出來以後，也就達到了抽象的最低層。15/31軟體工程的離散數學基礎抽象

隨著軟體開發工程的進展，在軟體結構每一層中的模組，表示了對軟體抽象層次的一次精化。軟體結構頂層的模組，控制了系統的主要功能並影響全局；在軟體結構底層的模組，完成對數據的一個具體處理，用自頂向下由抽象到具體的方式分配控制，簡化了軟體的設計和實現，提高了軟體的可理解性和可測試性，使軟體更容易維護。16/31軟體工程的離散數學基礎逐步求精

逐步求精是人類解決複雜問題時採用的基本方法，也是許多軟體工程技術(例如，規格說明技術，設計和實現技術)的基礎。可以把逐步求精定義為：“為了集中精力解決主要問題而儘量推遲對問題細節的考慮。”17/31軟體工程的離散數學基礎逐步求精

逐步求精能幫助軟體工程師把精力集中在與當前開發階段最相關的那些方面上，而忽略那些對整體解決方案來說雖然是必要的，然而目前還不需要考慮的細節，這些細節將留到以後再考慮。

Miller法則：一個人在任何時候都只能把注意力集中在(7±2)個知識塊上。18/31軟體工程的離散數學基礎逐步求精

人類智力有局限性，我們只能在這個前提下盡我們的最大努力工作。可以把逐步求精看作是一項把一個時期內必須解決的種種問題按優先順序排序的技術。逐步求精方法確保每個問題都將被解決，而且每個問題將在適當的時候被解決，但是，在任何時候一個人都不需要同時處理7個以上知識塊。19/31軟體工程的離散數學基礎逐步求精

逐步求精最初是由Wirth提出的一種自頂向下的設計策略。Wirth本人對逐步求精曾做過如下概括說明：20/31軟體工程的離散數學基礎逐步求精“我們對付複雜問題的最重要的辦法是抽象，因此，對一個複雜的問題不應該立刻用電腦指令、數字和邏輯符號來表示，而應該用較自然的抽象語句來表示，從而得出抽象程式。抽象程式對抽象的數據進行某些特定的運算並用某些合適的記號(可能是自然語言)來表示。對抽象程式做進一步的分解，並進入下一個抽象層次，這樣的精細化過程一直進行下去，直到程式能被電腦接受為止。這時的程式可能是用某種高級語言或機器指令書寫的。”21/31軟體工程的離散數學基礎逐步求精

求精實際上是細化過程。我們從在高抽象級別定義的功能陳述(或資訊描述)開始，也就是說，該陳述僅僅概念性地描述了功能或資訊，但是並沒有提供功能的內部工作情況或資訊的內部結構。求精要求設計者細化原始陳述，隨著每個後續求精(即細化)步驟的完成而提供越來越多的細節。22/31軟體工程的離散數學基礎逐步求精

抽象與求精是一對互補的概念。抽象使得設計者能夠說明過程與數據，同時卻忽略低層細節。事實上，可以把抽象看作是一種通過忽略多餘的細節同時強調有關的細節而實現逐步求精的方法。求精則幫助設計者在設計過程中逐步揭示出低層細節。這兩個概念都有助於設計者在設計演化過程中創造出完整的設計模型。23/31離散數學的主要內容數理邏輯：研究推理的共性關係理論：研究關係的共性代數結構：研究運算的共性圖論：數論：數理邏輯邏輯學研究人的思維形式和規律的科學根據研究的對象和方法形式邏輯辯證邏輯數理邏輯用數學方法研究推理的規律和形式的科學推理：由一個或幾個判斷推出一個新判斷的思維形式數學方法建立一套表意符號體系，對具體事物進行抽象的形式研究方法又稱符號邏輯兩種演算命題邏輯謂詞邏輯需要建立一套表意符號體系文法充分定義(well-defined)的形式語言符號體系自然語言有二義性Doubleclickthemouse,thenit’llrun.小王現在不方便接電話，他方便去了建立形式語言符號體系的目的消除二義性普適(高度概括)只關心推理過程的正確性,而不是推理的依據用數學方法研究推理的規律和形式主要內容命題與聯結詞命題公式重言式範式命題演算的推理理論謂詞和量詞謂詞演算的永真公式謂詞演算的推理規則命題邏輯謂詞邏輯命題（Proposition）斷言一個陳述語句命題命題是一個非真即假(不可兼)的斷言如果命題是真命題的真值（TruthValues）為真真命題大寫字母“T”(1)表示如果命題是假命題的真值是假假命題大寫字母“F”(0)表示能夠判斷真假的陳述句有確定真假含義的陳述句例今天下雪。雪是黑的。3+3=6。明年的今天會下雨。較大的偶數都可表為兩個質數之和。1+101=110。那個商店已經關門了。2是偶數而3是奇數。例(續)x+y＞4。x=3。0*x=0。真好啊！全體立正！你去哪里?我正在說謊。有確定的真假含義不等同於已知其真假含義較大的偶數都可表為兩個質數之和。除地球外，別的星球上也存在生物。數理邏輯不關心內容具體的陳述句的真值究竟為什麼或在什麼環境下是真還是假數理邏輯只關心形式命題可以被賦予真或假這樣的可能性，以及規定了真值後怎樣與其他命題發生聯繫原子命題(Primitiveproposition)由簡單陳述句表示的判斷命題邏輯規定：原子命題是不可再分的複合命題(Compoundproposition)一個或幾個簡單命題用聯結詞聯結所構成的命題(複合陳述句)例：“如果天氣好，我就去散步。”“2是偶數而3是奇數。”命題的表示常用大寫英文字母(或帶下標)表示原子命題P表示“雪是白的。”Q表示“北京是中國的首都。”表示命題的形式符號叫命題識別字表示原子命題的命題識別字叫命題詞命題變元P表示任一命題時，P就稱為命題變元命題詞不是命題,是表示任意命題的位置標誌命題指具體的陳述句，是有確定的真值命題變元的真值不定，只當將某個具體命題代入命題變元時(解釋、真值指派)，命題變元成為命題，方可確定其真值兩個特殊的命題詞命題常量T：永遠表示真命題F：永遠表示假命題T和F的兩種含義命題常量命題的真值邏輯聯結詞命題和原子命題常可通過一些聯結詞構成新命題,這種新命題叫複合命題例：

P:明天下雪,Q:明天下雨。“明天不下雪。”“非P”“明天下雪並且明天下雨。”“P並且Q”“明天下雪或者明天下雨。”“P或Q”TFFT┐PP真值表（TruthTable)與自然語言中的“不”，“否”，“非”，“沒有”，“未必”等表示否定的詞類似1.否定詞┐(～，negation)設P表示命題,那麼“P不真”是一個複合命題,記為┐P,叫做P的否定,讀做“非P”。如果P是假,則┐P是真,反之亦然。例(a)P:4是質數。

┐P:4不是質數。

(b)Q:這些都是男同學。

┐Q:這些不都是男同學。PQP∧Q000110110001例P:王華的成績很好。

Q:王華的品德很好。

P∧Q:王華的成績很好並且品德很好。2.合取詞∧(Conjunction)如果P和Q是命題,那麼“P並且Q”是一個複合命題,記為P∧Q,稱為P和Q的合取,讀做“P與Q”或“P並且Q”。用法靈活與自然語言中表示並列、加強、轉折等的詞：“和”、“與”、“且”、“而且”、“並且”、“既…又…”、“不但…而且…”、“雖然…但是…”、“而”類似沒有明顯否定、選擇、因果的表述也應該是合取PQP∨Q0001101101113.析取詞∨(disjunction)如果P和Q是命題,則“P或Q”是一個複合命題,記作P∨Q,稱為P和Q的析取,讀做“P或Q”。大致與自然語言中表示選擇的“或”,“或者”類似，但自然語言中的或具有二義性，用“或”聯結的命題，有時具有相容性，有時具有排斥性可兼或(R∨S)∧┐(R∧S)(R∧┐S)∨(┐R∧S)例(a)今晚我寫字或看書。

P:今晚我寫字，Q:今晚我看書。

P∨Q

(b)選小王或小李當班長。

R:選小王當班長，S:選小李當班長。

R∨S？

排斥或或×PQP→Q000110111101與自然語言中表示因果的“若…則…”、“如果…則…”、“如果…那麼…”、“只要…就…”等類似4.條件詞→(蘊涵,蘊含,conditional)如果P和Q是命題,那麼“P蘊含Q”是一個複合命題,記為P→Q,稱為條件式,讀做“如果P,那麼Q”或“P則Q”。運算對象P叫做前提,假設或前件,而Q叫做結論或後件。例(a)P:天不下雨,Q:草木枯黃。P→Q:如果天不下雨,那麼草木枯黃。(b)R:G是正方形,S:G的四邊相等。R→S:如果G是正方形,那麼G的四邊相等。(c)W:桔子是紫色的,V:大地是平的。W→┐V:如果桔子是紫色的,那麼大地是不平的。因果關係引入→的目的是希望用來描述命題間的推理，表示因果關係使用P→Q能描述推理如果n>3，那麼n2>9。A是B的子集是指A的成員都是B的成員。→與“如果…那麼…”有一致的一面,同時也有與常識不一致的地方如果今天是星期二，那麼明天是星期天。如果今天是星期一，那麼明天是星期天。

在自然語言中，條件和結論往往有某種內在聯繫，並且往往表示若條件成立則結論也成立這樣的推理關係；

而在數理邏輯中，條件和結論不一定有內在聯繫，且若條件為假則條件式為真。數理邏輯不關心具體命題，只關心推理的形式人為的規定，對P為F時P→Q的值另作規定也是可以的應是人類思維共性的總結PQP→QTFF**TFTT條件式P→Q可以用多種方式陳述:

“P是Q的充分條件”“Q是P的必要條件”“Q每當P”“只有Q，才P”“P僅當Q”……

Q→P,┐P→┐Q,┐Q→┐P分別叫做P→Q的逆命題、反(否)命題和逆反(否)命題/

逆換式、反換式和逆反式。例令：P：天氣好。Q：我去公園。1.如果天氣好，我就去公園。2.只要天氣好，我就去公園。3.天氣好，我就去公園。4.僅當天氣好，我才去公園。5.只有天氣好，我才去公園。6.我去公園，僅當天氣好。P→QP→QP→QQ→PQ→PQ→P100100011011P?QPQ5.雙條件詞?(等值，Biconditional)如果P和Q是命題,那麼“P等值於Q”是一個複合命題,記為P?Q,稱為雙條件式（等值式）,讀做“P當且僅當Q”、“PiffQ”或“P等值於Q”。

P?Q也讀做“P的充要條件是Q”。有時“除非”也有互為因果的意義。聯結詞的注意事項熟練掌握這五個聯結詞在自然語言中所表示的含義(但要注意具體語言環境)以及它們的真值表的定義特別要注意“或”的二義性，即要區分給定的“或”是“可兼取的或”還是“不可兼取的或”特別要注意“”的用法，它既表示“充分條件”也表示“必要條件”，即要弄清哪個作為前件，哪個作為後件聯結詞的優先順序順序┐，∧,∨,→,?練習：填空已知P∧Q為T，則P為()，Q為()已知P∨Q為F，則P為()，Q為()已知P為F，則P∧Q為()已知P為T，則P∨Q為()已知P∨Q為T，且P為F，則Q為()已知P

Q為F，則P為()，Q為()已知P為F，則P

Q為()已知Q為T，則P

Q為()已知

P

Q為F，則P為()，Q為()命題演算的合適公式命題變元與命題常元命題常元命題有具體含義(真值)的例：“3是素數。”；T；F命題變元用大寫的英字母如P、Q等表示任何命題真值指派解釋將一個命題常元賦予命題變元的過程或者是直接賦給命題變元真值“T”或“F”的過程注意：命題變元本身不是命題，只有給它一個解釋，才變成命題。遞歸定義法如何定義自然數集N？可採用以下方式遞歸定義(1)1∈N；(2)若n∈N,則n+1∈N；(3)N是滿足條件(1)和(2)的最小集合(換句話說，n∈N當且僅當能有限次應用(1)和(2)得到)。(1)——基本項，是遞歸的基礎(2)——遞歸項，是遞推規則(3)——極小化，保證所構造集合的唯一性是一個無限集合，但每個成員都是有限的命題公式命題公式(命題演算的合適公式,wff,wellformattedformula)定義：⑴單個命題詞是個合適公式。⑵若A是合適公式，則(

A)是合適公式。⑶若A和B是合適公式，則(A∧B)，(A∨B)，(A

B)和(A

B)都是合適公式。⑷當且僅當有限次地應用⑴，⑵，⑶所得到的含有命題變元、聯結詞和圓括號的符號串是合適公式。 此外，稱逐次使用規則⑴，⑵，⑶的過程中所得到的命題公式為最後構成的命題公式的子公式。(1)——基本項(2)(3)——遞歸項(4)——極小化例(P→(

(Q∨R)))解

(i)P是命題公式根據條款(1)(ii)Q是命題公式根據條款(1)(iii)R是命題公式根據條款(1)(iv)(Q∨R)是命題公式根據(ii)(iii)和條款(3)(v)(

(Q∨R))是命題公式根據(iv)和條款(2)(vi)(P→(

(Q∨R)))是命題公式根據(i)(v)和條款(3)例下麵的式子是否為合適公式：

P∧Q，PR，P∨Q∧R修改

(P∧Q)，((P)R)，((P∨Q)∧R)圓括弧的省略規則最外層的圓括號可以省去符合聯結詞優先順序順序的,括弧可省去相同的聯結詞,按從左至右次序計算時,括弧可省去

(┐((P∧(┐Q))∨R)→((R∨P)∨Q))┐((P∧(┐Q))∨R)→((R∨P)∨Q)

┐(P∧┐Q∨R)→(R∨P∨Q)┐(P∧┐Q∨R)→R∨P∨Q命題符號化(翻譯)用形式語言所表示的命題公式符號串來表示給定的命題命題詞表示原子命題邏輯聯結詞聯結例他既有理論知識又有實踐經驗。P：他有理論知識，Q：他有實踐經驗。

P∧Q如果明天不是雨夾雪則我去學校。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

僅當明天不下雪並且不下雨時我才去學校。

R→┐P∧┐Q說小學生編不了程式,或說小學生用不了個人電腦,那是不對的。P：小學生會編程序，Q：小學生會用個人電腦。 ┐(┐P∨┐Q)練習將下列命題符號化張三與李四是表兄弟。張三或李四都能做這件事。今晚我在家裏看電視或去體育場看球賽。今天我上班，除非今天我病了。除非你努力，否則你不會成功。如果明天不下雨，我就進城，否則就在家讀書或看報。真值指派(解釋)命題公式不是命題——命題函數有n個命題變元的命題公式可用函數A(P1,P2,…,Pn)的形式表示其中P1,P2,…,Pn按字典順序排列對應的真值指派可記為I=(P1’,P2’,…,Pn’)，其中Pi’=0或1例A(P,Q,R)=P(R

Q),真值指派(1,0,1)，(1,1,0)真值分別為F和T有n個命題變元的命題公式共有2n個不同的真值指派注意真值表設A(P1,P2,…,Pn)是一個wff，P1,P2,…,Pn是出現於其中的全部命題變元。如果有一張表列出了在P1,P2,…,Pn

的所有2n種真值指派的每一種下，公式A對應的真值，則稱此表為公式A的真值表。按子公式列表按邏輯聯結詞列表重言式/矛盾式/可滿足式重言式(tautology)/矛盾式(contradiction)A(P1,P2,…,Pn)是命題公式，P1,P2,…,

Pn是出現於其中的全部命題變元，如在P1,P2,…,

Pn的任何真值指派下，A(P1,P2,…,

Pn)的真值皆為真(假)，則稱A為重言式(矛盾式),也稱之為永真式

(永假式)例：P∨P和

P∧P偶然式不是永真式,也不是永假式例：P,P∧Q可滿足式（satisfactableformula

）非矛盾式

P∨P，P∧Q重言式的性質重言式/矛盾式/可滿足式是公式的性質(類別)性質對運算的封閉性(保持)偶數加(乘)偶數、可導函數之和(積)……如果A是重言式，則

A是矛盾式如果A是矛盾式，則

A是重言式如果A，B是重言式，則(A∧B)、(A∨B)、(A

B)和(A

B)也都是重言式如果A，B是矛盾式，則(A∧B)、(A∨B)是矛盾式如果A，B是矛盾式，則(A

B)和(A

B)是重言式思考：可滿足式是什麼情況？重言式的證明方法方法1：列真值表方法2：公式的等價變換，化簡成“T”方法3：用公式的主析取範式證明(P∧(PQ))Q

為重言式PQ(P∧(PQ))Q00011011TTTT命題公式的等價與蘊含恒等式(等價式，

equivalent)設A:A(P1,P2,…,Pn),B:B(P1,P2,…,Pn)是兩個命題公式,這裏Pi(i=1,2,…,n)不一定在兩公式中同時出現，如不論對P1,P2,…,Pn作何種指派，A和B恒有相同的真值，則稱之為A與B等價(恒等、邏輯相等)，記作A

B，讀做“A等價於B”或“A恒等於B”等價定理：A

B

當且僅當A

B是重言式注意：“

”與“

”不同：邏輯聯結詞：描述兩個命題公式之間的關係若A與B是wff

，A

B是wff，A

B不是問題：由n個命題變元可構成多少個不等價的命題公式？常用邏輯恒等式1雙重否定律A

??A2交換律A∨B

B∨AA∧B

B∧A3結合律(A∨B)∨C

A∨(B∨C)(A∧B)∧C

A∧(B∧C)4分配律A∧(B∨C)

(A∧B)∨(A∧C)A∨(B∧C)

(A∨B)∧(A∨C)5德摩根律?(A∨B)

?A∧?B?(A∧B)

?A∨?B6冪等律A∧A

A，A∨A

A7吸收律A∨(A∧B)

A，A∧(A∨B)

A8零元律A∨T

T，A∧F

F9同一律A∨F

A，A∧T

A10排中律A∨?A

T11矛盾律A∧?A

F12條件等價式A→B

?A∨B13雙條件等價式A?B

(A→B)∧(B→A)14假言易位式A→B

?B→?A15雙條件否定等價式A?B

?A??B16輸出式A→(B→C)

A∧B→C公式等價的證明方法1：列真值表方法2：等價變換方法3：主範式例：證明：P→Q

?P∨QTTFFTTTT11011000┐P∨QP

QQP永真蘊含式(implication)定義給定兩個命題公式A和B，如果公式A

B是重言式，則稱A重言(永真)蘊含B，或簡單的說A蘊含B，記作A

B注意：“”不是聯結詞表示公式間的“永真蘊含”關係也可看成“推導”關係A

B可以理解成由A可推出B，即由A為真，可以推出B也為真蘊含式的證明方法真值表等價變換邏輯推證假定前件是真,若能推出後件是真,則此蘊含式是真假定後件是假,若能推出前件是假,則此蘊含式是真PQP→Q000110111101用真值表證明蘊含關係證明：(P∨Q)∧(P→R)∧(Q→R)

R111011101001110010100000(P∨Q)∧(P→R)∧(Q→R)→R(P∨Q)∧(P→R)∧(Q→R)RQP1110111011101010

方法1:設┐Q∧(P→Q)是真則┐Q,P→Q是真所以,Q是假,

P是假。因而┐P是真。故┐Q∧(P→Q)

┐P

方法2:設┐P是假,則P是真。以下分情況討論。

(i)若Q為真,則┐Q是假,

所以┐Q∧(P→Q)是假

(ii)若Q是假,則P→Q是假所以┐Q∧(P→Q)是假故┐Q∧(P→Q)

P

例證明：┐Q∧(P→Q)

┐P考慮任一使┐Q∧(P→Q)為真的解釋I，在I下：

┐QP→QTT嚴謹嗎？

……公式怎麼能是真？用邏輯推證方法證明蘊含關係引用聯詞定義逐步推演

例證明：(P→(Q→R))∧(┐S∨P)∧Q

S→R考慮任一使(P→(Q→R))∧(┐S∨P)∧Q為T的解釋I，在I下：(P→(Q→R))(┐S∨P)QTTT怎麼辦？

輸出式E19：P→(Q→R)

P∧Q→RP

Q

R

原題轉變為證明：(P→(Q→R))∧(┐S∨P)∧Q∧S

RP→(Q→R)是永真式等同於P∧Q→R是永真式

考慮任一使(P→(Q→R))∧(┐S∨P)∧Q和S皆為T的解釋I，在I下：(P→(Q→R))(┐S∨P)QSTTTT例證明：(P→(Q→R))∧(┐S∨P)∧Q

S→R

┐SFPTQ→RTRT這種證明方法叫附加前提證明法(CP規則)邏輯推證存在格式與過程不規範的問題永真蘊含式1附加律A

A∨B，B

A∨B2化簡律A∧B

A，A∧B

B3假言推理A∧(A→B)

B4拒取式?B∧(A→B)

?A5析取三段論?A∧(A∨B)

B，?B∧(A∨B)

A6假言三段論(A→B)∧(B→C)

(A→C)7等價三段論(A?B)∧(B?C)

(A?C)8構造性二難(A∨C)∧(A→B)∧(C→D)

B∨D(A∨?A)∧(A→B)∧(?A→B)

B9破壞性二難(?B∨?D)∧(A→B)∧(C→D)

(?A∨?C)等價和蘊含的性質等價關係的性質自反性任何命題公式A，有A

A對稱性若A

B，則B

A傳遞性若A

B且B

C，則A

C蘊含關係的性質自反性任何命題公式A，有A

A反對稱性若A

B且B

A，則A

B傳遞性若A

B且B

C，則A

C若A

B,A

C,則A

B∧C思考：若A

B，則┐A┐B？No！

┐B┐A證明若A

B,B

C則A

C

證明：A→B永真;B→C永真,所以

(A→B)∧(B→C)永真由公式I6得A→C永真,即A

C

若A

B,A

C,則A

B∧C

證明：A是真時,B和C都真,所以B∧C也真因此A→B∧C永真,則A

B∧C

由已知的等價式按照合理的規則逐步推演出新的等價式例證明：A∨B→C

(A→C)∧(B→C)

證：A∨B→C

(A→C)∧(B→C)等價變換┐(A∨B)∨C(┐A∨C)∧(┐B∨C)依據何在？

代入實例設A和B是兩個命題公式，如果將A中的某些命題變元用命題公式進行代換便可得到B，並且此種代換滿足：（1）被代換的是命題變元（2）如果要代換某個命題變元，則要將該命題變元在A中的一切出現進行代換（3）代換必須同時獨立進行此時稱B是A的一個代換實例（代入實例）例A(P,Q)=P→Q A(P,Q∧┐R)=P→Q∧┐RA(P,Q,R,S)=(P→Q)∧R∧(S→(P→Q)) (P→Q)∧S∧(R→(P→Q))，(┐P→Q)∧┐R∧(┐S→(┐P→Q))

P∧R∧(S→P)，(┐P→Q)∧R∧(R→(P→Q))代入規則和替換規則簡單地說，命題公式A(X1,X2,…,Xn)是A(P1,P2,…,Pn)的代入實例,只要Xi是命題公式(允許Xi=Pi

，i=1,2,…,n)。代入規則(RuleofSubstitution，代入定理)重言式的代入實例是重言式例(R∧Q)∨┐(R∧Q)(R∨Q)

∧┐(R∨Q)→(P∨Q→S∨Q)矛盾式的代入實例是矛盾式嗎？YesP∨┐PP∧┐P→Q替換規則(RuleofReplacement，置換定理)子公式定義：如果X是合適公式A的一部分且X本身也是合適公式，則稱X為公式A的子公式例：A

Q→(P∨(P∧Q))，X

P∧Q替換規則定理：設X是合適公式A的子公式，若X

Y，如果將A中的X用Y來置換，得到的公式記為B，則B與A等價，即A

B

例：Q→(P∨(P∧Q))

Q→P代入與替換的區別代入是對命題變元進行取代，替換對子公式代入必須取代該命題變元的一切出現，替換不用可用任意wff去代換命題變元，只能用與子公式等價的公式去替換代入實例一般不與原公式等價，替換後的公式必與原公式等價由已知的等價式按照合理的規則逐步推演出另外一些等價式的過程反復應用代入規則和替換規則每個常用邏輯恒等式都是一個模式，對應著無數個同型的等價式等價變換（等值演算）

E3：P∨Q

Q∨PA∧B┐A∧┐B∨

A∧B┐A∧┐B∨E16：P

Q

┐P∨Q由等價定理：例由代入定理：由等價定理：又如PQ?┐P∨Q是重言式(R∨Q)

P?┐(R∨Q)∨P是重言式(R∨Q)

P

┐(R∨Q)∨P是重言式例(a)證明P∧┐Q∨Q

P∨Q

證明：P∧┐Q∨Q

Q∨P∧┐Q E3

(Q∨P)∧(Q∨┐Q) E7

(Q∨P)∧T E24和替換規則

Q∨P E12

P∨Q E3

(b)證明(P→Q)→(Q∨R)

P∨Q∨R證明：(P→Q)→(Q∨R)

(┐P∨Q)→(Q∨R)E16和替換規則

┐(┐P∨Q)∨(Q∨R)E16

P∧┐Q∨(Q∨R)E9、E1和替換規則

(P∧┐Q∨Q)∨RE5

P∨Q∨R例(a)和替換規則存在過程不規範的問題(c)試將語句“情況並非如此:如果他不來,那麼我也不去”化簡。 解：設P:他來, Q:我去 ┐(┐P→┐Q)

┐(P∨┐Q) E16和替換規則

┐P∧Q E9，E1和替換規則(d)找出P→(P?Q)∨R的僅含∧和┐兩種聯結詞的等價運算式。

P→(P?Q)∨R

P→(P→Q)∧(Q→P)∨R

┐P∨(┐P∨Q)∧(┐Q∨P)∨R

(┐P∨┐P∨Q)∧(┐P∨┐Q∨P)∨R

(┐P∨Q)∧T∨R

┐

P∨Q∨R

┐(P∧┐Q∧┐R)(e)證明：(P∨Q)∧(P→R)∧(Q→R)R證：(P∨Q)∧(P→R)∧(Q→R)→R

(P∨Q)∧(┐P∨R)∧(┐Q∨R)→R

(P∨Q)∧(┐P∧┐Q∨R)→R

(P∨Q)∧R→R

T證：(P∨Q)∧(P→R)∧(Q→R)

(P∨Q)∧(┐P∨R)∧(┐Q∨R)

(P∨Q)∧(┐P∧┐Q∨R)

(P∨Q)∧R

R功能完備集及其他聯結詞聯結詞的擴充問題的提出：對n個命題變元P1…Pn來說,共可定義出多少個聯結詞?

在那麼多聯結詞中有多少是相互獨立的?4個新聯結詞：與非:P↑Q┐(P∧Q)或非:P↓Q┐(P∨Q)排斥或(異或):P⊕Q┐(P

Q)

P∧┐Q∨┐P∧Q蘊含否定(條件否定):P→Q┐(P→Q)

Q1：可定義多少個聯結詞？命題變元和命題聯結詞可以構成無限多個合適公式把所有的合適公式分類：將等值的公式視為同一類，對於該類合適公式，就可定義一個聯結詞與之對應一元聯結詞的個數一元聯結詞是聯結一個命題變元的由一個命題變元P可構成4種不等價的命題公式相應的可定義出4個不同的一元聯結詞Pf1f2

f3f

40100110101

永假恒等否定永真二元聯結詞的個數二元聯結詞聯結兩個命題變元由兩個命題變元P，Q可構成16種不等價的命題公式相應的可定義出16個不同的二元聯結詞n元聯結詞的個數對n個命題變元P1,…,Pn,每個Pi有2種取值,從而對P1…Pn來說共有2n種取值情形相應的可定義出22n個n元聯結詞

二元運算聯結詞的歸約Q2：聯結詞是否都是獨立的，或者說能否相互表示定義1.4-1

一個聯結詞集合,用其中聯結詞構成的式子足以把一切命題公式等價地表達出來,則這個聯結詞集合稱為全功能的，相應的把這個集合稱為聯結詞功能完備集完備集全體聯結詞的無限集合是完備的{

,∨,∧}是完備的聯結詞集合{

,∨}是聯結詞的完備集證明：已知{

,∨,∧}是全功能的，又P∧Q

(

P∨

Q)，因此∧可由{

,∨}表示，所以{

,∨}是全功能的{

,∧}是聯結詞的完備集{

,→}是完備集{↑}是完備集{↓}是完備集(獨立的完備集){

,∧,∨,→,?}是完備的不完備集{∨,∧,→,?}{?,?}{∨,∧,→,?}其任何子集都是不完備的{?,?}{∨,∧}其他聯接詞異或與非↑或非↓{↑}是完備集{↓}是完備集對偶原理交換律A∨B

B∨AA∧B

B∧A結合律(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

A，A∨A

A吸收律A∨(A∧B)

A，A∧(A∨B)

A零元律A∨T

T，A∧F

F同一律A∨F

A，A∧T

A排中律A∨?A

T矛盾律A∧?A

F關於?、∧、∨聯詞的基本等價式均成對出現共軛聯詞共軛常量共軛量詞()對偶式設有公式A,其中僅有聯結詞∧,∨,┐。在A中將∧,∨,T,F分別換以∨,∧,F,T得公式A*,則A*稱為A的對偶(公)式。(A*)*?(A*)*

A例

(a)A=P∨F

，A*=？

A*=P∧T

(b)A=┐P∨Q∧R，A*=？

A*=┐P∧Q∨R

注意定理設A和A*是對偶式。P1,P2,…,Pn是出現於A和A*中的所有命題變元,於是

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)證明：反復地使用德-摩根定律A(P,Q)

P∨Q，A*(P,Q)

P∧Q

A(P,Q)

(P∨Q)A*(

P,

Q)

P∧

Q

A(P,Q)

A*(

P,

Q)推論:A(

P1,

P2,…,

Pn)

A*(P1,P2,…,Pn)

因為

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)

所以A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)即A(P1,P2,…,Pn)?A*(

P1,

P2,…,

Pn)是重言式則A(

P1,

P2,…,

Pn)?A*(P1,P2,…,Pn)是重言式所以A(

P1,

P2,…,

Pn)

A*(P1,P2,…,Pn)定理（對偶原理）若A

B,且A,B為命題變元P1,P2,…..,Pn及聯結詞∧,∨,

構成的公式,則A*

B*。 證明：因為A(P1,P2,…,Pn)

B(P1,P2,…,Pn)

故A(

P1,

P2,…,

Pn)

B(

P1,

P2,…,

Pn)

而A(

P1,

P2,…,

Pn)

A*(P1,P2,…,Pn)

B(

P1,

P2,…,

Pn)

B*(P1,P2,…,Pn)

故A*(P1,P2,…,Pn)

B*(P1,P2,…,Pn)

所以A*(P1,P2,…,Pn)

B*(P1,

P2,…,

Pn)若A

B,且A,B為命題變元P1,P2,…..,Pn及聯結詞∧,∨,

構成的公式,則A*

B*成立嗎？如果是，請證明；如果否，為什麼？若A

B,且A,B為命題變元P1,P2,…..,Pn及聯結詞∧,∨,

構成的公式,則B*

A*等價變換存在過程不規範的問題初等數學中範式x2+xy+2y(x+y)應化成：x2+3xy+2y2或(x+y)(x+2y)x2+3yx+2y2(y+x)(x+2y)雖然等值，但不規範命題邏輯中，將公式化成主範式可使公式有唯一表示形式而：析取範式和合取範式範式就是命題公式形式的規範(標準化)形式範式中只含有聯結詞

、∨和∧基本積、基本和文字（因數）原子或原子的否定稱為文字(基子句)例：P，

PP與

P稱為互補對基本積文字的合取式（短語）P、

P、P∧Q、P∧Q∧R基本和文字的析取式（子句）P、

P、P∨Q、P∨Q∨R定理一個基本積是永假式,當且僅當它含有P,┐P形式的兩個因數。 證明： 充分性：

P∧┐P是永假式,

而Q∧F

F,

所以含有P和┐P形式的兩個因數時,此基本積是永假式

必要性：（反證法） 設基本積永假但不含P和┐P形式的兩個因數,

則給這個基本積中不帶否定符的命題變元指派真值T,

帶有否定符的命題變元指派真值F,得基本積的真值是T,

與題設矛盾。 證畢。析取範式一個由基本積之和組成的公式,如果與給定的命題公式A等價,則稱它是A的析取範式,記為

A

A1∨A2∨…∨An

,n≥1

這裏A1,A2,…,An是基本積。任何一個命題公式都可求得它的析取範式一個命題公式的析取範式不是唯一的最簡析取範式：運算符最少的析取範式合取範式一個由基本和之積組成的公式,如果與給定的命題公式A等價,則稱它是A的合取範式,記為

A

A1∧A2∧…∧An

,n≥1

這裏A1,A2,…,An是基本和任何一個命題公式都可求得它的合取範式一個命題公式的合取範式不是唯一的最簡合取範式：運算符最少的合取範式析取範式與合取範式的求法⑴先用相應的公式去掉和。公式E16P

Q

P∨Q

公式E21PQ(P∧Q)∨(

P∧

Q)

公式E20PQ(P

Q)∧(Q

P)

再用E16PQ(P∨Q)∧(P∨

Q)⑵用公式的否定公式或摩根律將後移到命題變元之前。

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)

摩根律

(P∨Q)

P∧

Q

(P∧Q)

P∨

Q⑶用分配律、冪等律等公式進行整理，使之成為所要求的形式。

例(a)求P∧(P→Q)的析取範式。解P∧(P→Q)

P∧(┐P∨Q)

P∧┐P∨P∧Q

或：P∧(P→Q)

F∨P∧Q

P∧Q最簡析取範式同時是個合取範式(b)求┐(P∨Q)?(P∧Q)的最簡析取範式。解┐(P∨Q)?(P∧Q)

(┐(P∨Q)∧(P∧Q))∨((P∨Q)∧┐(P∧Q))

(┐P∧┐Q∧P∧Q)∨((P∨Q)∧(┐P∨┐Q))

┐P∧Q∨P∧┐Q

例(a)證明Q∨P∧┐Q∨┐P∧┐Q是永真式。解Q∨P∧┐Q∨┐P∧┐Q

Q∨(P∨┐P)∧┐Q

(Q∨P∨┐P)∧(Q∨┐Q)

Q∨P∨┐P

T，(Q∨┐Q)

T

所以(Q∨P∨┐P)∧(Q∨┐Q)

T(b)求┐(P∨Q)?(P∧Q)的最簡合取範式。

解┐(P∨Q)?(P∧Q)

(┐(P∨Q)→(P∧Q))∧

((P∧Q)→┐(P∨Q))

((P∨Q)∨(P∧Q))∧(┐(P∧Q)∨┐(P∨Q))

(P∨Q)∧((┐P∨┐Q)∨(┐P∧┐Q))

(P∨Q)∧(┐P∨┐Q)主析取範式和主合取範式極小項在n個變元的基本積中,若每一個變元與其否定不同時存在,而兩者之一必出現一次且僅出現一次,則這種基本積叫關於這n個變元的極小項。設P1,P2,…,Pn是n個命題變元，則稱

P1’∧P2’

∧…∧Pn’

為關於P1,P2,…,Pn的極小項，其中Pi’

為Pi或┐Pi極小項(續)P∧Q、P∧Q、P∧Q、P∧Q？文字的出現順序與變元符號的字典順序一致n個變元可構成2n個不同的極小項命題變元看成1,命題變元的否定看成0,那麼每一極小項對應一個二進位數,因而也對應一個十進位數把對應的十進位數當作足標,用mi表示這一項m0

┐P∧┐Q∧┐R——000——0m1

┐P∧┐Q∧R——001——1m2

┐P∧Q∧┐R——010——2m3

┐P∧Q∧R——011——3m4

P∧┐Q∧┐R——100——4m5

P∧┐Q∧R——101——5m6

P∧Q∧┐R——110——6m7

P∧Q∧R——111——7一般地，對P1,…,Pn而言，2n個極小項為：三個變元八個小項的真值表PQRm0m1m2m3m4m5m6m70

000010

100111001011101111000000001000000001000000001000000001000000001000000001000000001m0

┐P∧┐Q∧┐Rm1

┐P∧┐Q∧Rm7

P∧Q∧R極小項的性質合取式每個極小項mk只在與其下標對應的真值指派下為T，其餘都為Fmi∧

mj

F，i≠j∨mi

T（0≤i≤2n-1）一個由極小項之和組成的公式,如果與給定的命題公式A等價,則稱它是A的主析取範式。小項應以下標遞增次序排列設G=(P

Q)

(

P

R)

(Q

R)PQRG0

00000110

10001111000101011011111┐P∧┐Q∧R┐P∧Q∧RP∧Q∧┐RP∧Q∧R∨∨∨

m1∨m3∨m6∨m7∑(1，3，6，7)定理每一個不為永假的命題公式A(P1,P2,…,Pn)必與一個由P1,P2,…,Pn所產生的主析取範式等價。且在A的真值表中，使A為T的指派所對應的諸小項之析取，即為A的主析取範式。永真公式的主析取範式包含所有2n個極小項永假公式的主析取範式是一空公式，用F表示證明：存在性：由上頁主析取範式的構造過程可證唯一性：設有兩個不同的主析取範式B和C都與A等價由於B和C不同，即必存在極小項mi在B中但不在C中，或在C中但不在B中，不妨設其在B中但不在C中。則在i對應的真值指派下，mi為T，即B為T，而C為F與B和C都是A的主析取範式矛盾唯一性得證唯一用等價變換求主析取範式先用相應的公式去掉和用公式的否定公式或摩根律將後移到命題變元之前用分配律、冪等律等公式進行整理，使之成為析取範式A1∨A2∨...∨An

為使每個Ai都變成極小項，對缺少變元的Ai補全變元，比如缺變元R，就用∧聯結永真式(R∨

R)形式補R消去重複的極小項，並將極小項按下標由小到大的次序排列規範(甚至可以機器完成)例求G=

(R

P)

(Q

(P

R))主析取範式G

(R

P)

(Q

(P

R))

(

R

P)

(Q

P)

(Q

R)

(

P

R)

(Q

P)

(Q

R)

((

P

R)

(

Q

Q))

((Q

P)

(

R

R))

( (Q

R)

(

P

P))

(

P

Q

R)

(

P

Q

R)

(P

Q

R)

(P

Q

R) ∑(1，3，6，7)利用主範式證明兩公式等價例證明：┐P∨Q和P→((P→Q)∧┐(┐Q∨┐P))二式等價。

證┐P∨Q

┐P∧(Q∨┐Q)∨Q∧(P∨┐P)

┐P∧Q∨┐P∧┐Q∨P∧Q

P→((P→Q)∧┐(┐Q∨┐P))

┐P∨((┐P∨Q)∧(Q∧P))

┐P∨(┐P∧Q∧P)∨(Q∧Q∧P)

┐P∨P∧Q

┐P∧(Q∨┐Q)∨P∧Q

┐P∧Q∨┐P∧┐Q∨P∧Q所以,二式邏輯等價。極大項在n個變元的基本和中,若每一個變元與其否定不同時存在,而兩者之一必出現一次且僅出現一次,則這種基本和叫關於這n個變元的極大項。關於P,Q：P∨Q、P∨Q、P∨Q、P∨Q文字的出現順序與變元符號的字典順序一致n個變元可構成2n個不同的極大項命題變元看成0,命題變元的否定看成1,那麼每一極大項對應一個二進位數,因而也對應一個十進位數把對應的十進位數當作足標,用Mi表示這一項M0

P∨Q∨R——000——0M1

P∨Q∨┐R——001——1M2

P∨┐Q∨R——010——2M3

P∨┐Q∨┐R——011——3M4

┐

P∨Q∨R——100——4M5

┐

P∨Q∨┐R——101——5M6

┐

P∨┐Q∨R——110——6M7

┐P∨┐Q∨┐R