1、離散數(shù)學(xué),董笑菊BASICS,計算機(jī)科學(xué)與工程系上海交通大學(xué)xjdong@sjtu.edu.cn 電院3-327Tel:34205060 EXT 602http://basics.sjtu.edu.cn/~xiaoju/dm,2,離散數(shù)學(xué),離散數(shù)學(xué)是：現(xiàn)代數(shù)學(xué)的一個重要分支計算機(jī)科學(xué)與技術(shù)的理論基礎(chǔ)是計算機(jī)應(yīng)用必不可少的工具，所以又稱為計算機(jī)數(shù)學(xué),離散數(shù)學(xué)離我們很遠(yuǎn)嗎？,數(shù)理邏輯,電燈開關(guān)兩個開關(guān)A、B同

2、時控制一盞燈C,只要有一個開關(guān)處于開啟狀態(tài)燈就會亮只有兩個開關(guān)之一處于開啟狀態(tài)燈才亮請具體列出燈C在開關(guān)A和B處于什么情況下會亮,集合,自然數(shù)集合實數(shù)集合集合的運(yùn)算幻方、數(shù)獨問題(Magic Square、Sudoku),8 1 6 3 5 7 4 9 2,圖論,人狼羊菜過河 有一個人帶著一只狼，一只羊，一筐菜過河，當(dāng)這個人在狼和羊身邊時，狼不敢吃羊，羊也不敢吃菜，但是當(dāng)人不在它們身邊時，羊就可能把羊吃

3、掉，羊也可能把菜吃掉，現(xiàn)在，渡船時只有一只船，能承載一個人及一件東西或物品，問怎樣渡才能使人.狼.羊.菜安全過河？,離散數(shù)學(xué)就在我們身邊！,8,離散數(shù)學(xué),事實上，從計算機(jī)產(chǎn)生到其發(fā)展每一步都離不開數(shù)學(xué)1936年，英國數(shù)學(xué)家圖靈(A.M.Turing)發(fā)表了著名論文 “理想計算機(jī)”，從而給出了計算機(jī)的理論模型1946年在著名數(shù)學(xué)家馮·諾依曼(J.Von Neumann)的領(lǐng)導(dǎo)下，制造了世界上第一臺現(xiàn)代意義的通用計算機(jī)EDVA

4、C (Electronic Discrete Variable Automatic Computer) ．．．為什么離散數(shù)學(xué)對計算機(jī)科學(xué)來說如此重要？數(shù)字電子計算機(jī)是一個離散結(jié)構(gòu)，它只能處理離散的或離散化了的數(shù)量關(guān)系無論計算機(jī)科學(xué)本身，還是與計算機(jī)科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨著如何對離散結(jié)構(gòu)建立相應(yīng)的數(shù)學(xué)模型；又如何將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化，從而可由計算機(jī)加以處理,9,離散數(shù)學(xué)與計算機(jī)科學(xué)的關(guān)

5、系,數(shù)理邏輯：人工智能、程序正確性證明、　　　　　程序驗證等集合論：　關(guān)系數(shù)據(jù)庫模型等圖論：　　數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫模型、　　　　　網(wǎng)絡(luò)模型等代數(shù)結(jié)構(gòu)：軟件規(guī)范、形式語義、編譯系統(tǒng)、 編碼理論、密碼學(xué)、數(shù)據(jù)倉庫等組合數(shù)學(xué)：算法分析與設(shè)計、編碼理論、容錯等,10,離散數(shù)學(xué)課程說明,研究對象----離散個體及其結(jié)構(gòu)研究思想----以集合和映射為工具、體現(xiàn)公理化和結(jié)構(gòu)的思想研究內(nèi)容----包含不同的數(shù)學(xué)分支，模塊化結(jié)構(gòu)

6、數(shù)理邏輯：推理、形式化方法集合論：離散結(jié)構(gòu)的表示、描述工具圖論：離散結(jié)構(gòu)的關(guān)系模型代數(shù)結(jié)構(gòu)：離散結(jié)構(gòu)的代數(shù)模型組合數(shù)學(xué)：離散結(jié)構(gòu)的存在性、計數(shù)、枚舉、優(yōu)化、設(shè)計離散概率（概率統(tǒng)計課程）,11,課程內(nèi)容,數(shù)理邏輯圖論,考核 平時成績30%: 作業(yè)+點名+課堂練習(xí)期末考試70%,12,希望,掌握離散數(shù)學(xué)的各個分支的基本概念、基本理論和基本方法 提高概括抽象能力、邏輯思維能力、歸納構(gòu)造能力 培養(yǎng)嚴(yán)謹(jǐn)、完整、規(guī)范的科學(xué)態(tài)度

7、,教材和輔導(dǎo)書,參考教材：數(shù)理邏輯與集合論（第二版）：石純一，清華大學(xué)出版社圖論與代數(shù)結(jié)構(gòu)：戴一奇，清華大學(xué)出版社輔導(dǎo)書：數(shù)理邏輯：莫紹揆，科學(xué)文獻(xiàn)出版社數(shù)理邏輯教程：莫紹揆，華中工學(xué)院出版社集論與邏輯：沈恩紹，科學(xué)出版社A Mathematical Introduction to Logic, 2nd. Ed, H.Enderton, Academic Press Logic for Applications, 2n

8、d ed., A. Nerode, Springer離散數(shù)學(xué)（第4版），Richard Johnsonbaugh，電子工業(yè)出版社,PPT下載地址,http://basics.sjtu.edu.cn/~xiaoju/dm/,15,第一部分 數(shù)理邏輯,邏輯學(xué)研究人的思維形式和規(guī)律的科學(xué)．由于研究的對象和方法各有側(cè)重而又分為形式邏輯、辯證邏輯和數(shù)理邏輯數(shù)理邏輯用數(shù)學(xué)方法研究推理，是研究推理中前題和結(jié)論之間的形式關(guān)系的科學(xué)所謂推

9、理就是由一個或幾個判斷推出一個新判斷的思維形式這里所說的數(shù)學(xué)方法就是建立一套表意符號體系，對具體事物進(jìn)行抽象的形式研究的方法. 因此, 數(shù)理邏輯又稱符號邏輯,,數(shù)理邏輯前史時期－古典形式邏輯時期,這一時期主要工作有亞里士多德的三段論，斯多阿學(xué)派的命題邏輯和中世紀(jì)形式邏輯的形成與發(fā)展。,數(shù)理邏輯初創(chuàng)時期－邏輯代數(shù)時期,數(shù)理邏輯創(chuàng)建于17世紀(jì)末，創(chuàng)始人是德國哲學(xué)家和數(shù)學(xué)家萊布尼茨。這一時期的主要成就有萊布尼茨的數(shù)理邏輯的偉大思想的

10、形成，邏輯代數(shù)和關(guān)系邏輯的建立和發(fā)展。,數(shù)理邏輯的奠定時期,這一時期從1879年弗雷格G. Frege《概念語言》的出版到希爾伯特的元數(shù)學(xué)綱領(lǐng)的提出，主要工作有邏輯演算的建立，樸素集合論、公理集合論以及第三次數(shù)學(xué)危機(jī)。為解決第三次數(shù)學(xué)危機(jī)所取得的結(jié)果：邏輯類型論，直覺主義數(shù)學(xué)基礎(chǔ)和邏輯，形式公理學(xué)和證明論。,數(shù)理邏輯發(fā)展初期,這一時期是20世紀(jì)30十年代，主要工作體現(xiàn)為哥德爾(Godel)的幾項重大成果－完全性定理、理、

11、不完全性定理和連續(xù)統(tǒng)假設(shè)的一致性等,數(shù)理邏輯現(xiàn)代發(fā)展時期,這一時期從20世紀(jì)40年代開始。主要內(nèi)容是各種非經(jīng)典邏輯和四論－模型論、集合論、遞歸論和證明論的突飛猛進(jìn)的發(fā)展,,,,,數(shù)理邏輯的發(fā)展歷程,17,內(nèi)容體系,18,第一章 命題邏輯的基本概念,命題邏輯(Logic)研究命題的推理演算命題邏輯的應(yīng)用數(shù)學(xué)上定理的推導(dǎo)在計算機(jī)科學(xué)上，驗證程序的正確性主要內(nèi)容命題的基本概念命題聯(lián)結(jié)詞命題合式公式、重言式自然語句的形式

12、化,19,命題邏輯應(yīng)用實例,在舉重比賽中，有一名主裁判，兩名副裁判。當(dāng)兩名以上裁判（必須包括主裁判在內(nèi)）認(rèn)為運(yùn)動員舉杠鈴合格，按電鈕，才裁決合格。試用與非門設(shè)計該電路設(shè)計一個樓上、樓下開關(guān)的控制邏輯電路來控制樓梯上的路燈。使之在上樓前，用樓下開關(guān)打開電燈，上樓后，用樓上開關(guān)關(guān)滅電燈；或者在下樓前，用樓上開關(guān)打開電燈，下樓后，用樓下開關(guān)關(guān)滅電燈,20,1.1 命題（Proposition）,命題是一個非真即假(不可兼)的陳述句命題

13、是一個陳述句，命令句、疑問句和感嘆句都不是命題命題只有兩個取值：真或假。這個陳述句所表達(dá)的內(nèi)容可決定是真還是假，而且不是真的就是假的，不能不真又不假，也不能又真又假真假命題凡與事實相符的陳述句為真語句，而與事實不符的陳述句為假語句．這就是說，一個命題具有兩種可能的取值(又稱真值)，為真或為假，并且只能取其一通常用大寫字母“T”(1)表示真值為真，用“F”(0)表示真值為假．因為只有兩種取值，所以這樣的命題邏輯稱為二值邏輯,21,

14、命題舉例,(1) “雪是白的”。 ?(2) “雪是黑的”。 ?(3) “好大的雪啊” ！ ? 不是陳述句，不是命題(4) “一個偶數(shù)可表示成兩個素數(shù)之和”。 ? 只不過當(dāng)今尚不知其是真命題還是假命題(5) “1+101＝110”。 ? 這是一個數(shù)學(xué)表達(dá)式，相當(dāng)于一個陳述句，可以敘述為“1加101等于110”，這個句子所表達(dá)的內(nèi)容在十進(jìn)制范圍中真值為假，而在二進(jìn)制范圍中真值為真?？梢?，這個命題

15、的真值與所討論問題的范圍有關(guān)。(6) “x>y” ?,22,命題變項,為了對命題作邏輯演算，采用數(shù)學(xué)手法將命題符號化(形式化)是十分重要的命題的表示：大寫符號P表示“雪是白的”Q表示“北京是中國的首都”命題變項：P表示任一命題時，P就稱為命題變項(變元)．命題與命題變項含義是不同的：命題指具體的陳述句，是有確定的真值命題變項的真值不定，只當(dāng)將某個具體命題代入命題變項時，命題變項化為命題，方可確定其真值命題與命題

16、變項像初等數(shù)學(xué)中常量與變量的關(guān)系一樣．如5是一個常量，是一個確定的數(shù)字，而x是一個變量，賦給它一個什么值它就代表什么值，即x的值是不定的,23,簡單命題和復(fù)合命題,簡單命題又稱原子命題(Primitive proposition)簡單命題是不包含任何的與、或、非一類聯(lián)結(jié)詞的命題簡單命題不可再分割，如“雪是白的”再分割就不是命題了．命題“雪是白的而且1+1＝2”不是簡單命題，它可以分割為“雪是白的”以及“1+1＝2”兩個簡單命題，聯(lián)

17、結(jié)詞是“而且”在簡單命題中，盡管常有主語和謂語，但我們不去加以分割，是將簡單命題作為一個不可分的整體來看待，進(jìn)而作命題演算．在謂詞邏輯里，才對命題中的主謂結(jié)構(gòu)進(jìn)行深入分析,24,復(fù)合命題(Compound proposition),復(fù)合命題：把一個或幾個簡單命題用聯(lián)結(jié)詞(如與、或、非等)聯(lián)結(jié)所構(gòu)成的新的命題“張三學(xué)英語和李四學(xué)日語”就是一個復(fù)合命題由簡單命題“張三學(xué)英語” “李四學(xué)日語”經(jīng)聯(lián)結(jié)詞“和”聯(lián)結(jié)而成復(fù)合命題的真值：依

18、賴于構(gòu)成該復(fù)合命題的各個簡單命題的真值以及聯(lián)結(jié)詞上例中，當(dāng)以上兩個簡單命題真值均為真時，該復(fù)合命題方為真命題邏輯所討論的是多個命題聯(lián)結(jié)而成的復(fù)合命題的規(guī)律性,25,內(nèi)容 / 形式,命題是一個可取真或可取假的陳述句數(shù)理邏輯不關(guān)心內(nèi)容 這些具體的陳述句的真值究竟為什么或在什么環(huán)境下是真還是假數(shù)理邏輯只關(guān)心形式 命題可以被賦予真或假這樣的可能性，以及規(guī)定了真值后怎樣與其他命題發(fā)生聯(lián)系,26,1.2 命題聯(lián)結(jié)詞及真

19、值表,聯(lián)結(jié)詞可將命題聯(lián)結(jié)起來構(gòu)成復(fù)雜的命題命題邏輯聯(lián)結(jié)詞的引入是十分重要的，其作用相當(dāng)于初等數(shù)學(xué)里在實數(shù)集上定義的+、?、?、÷等運(yùn)算符通過聯(lián)結(jié)詞便可定義新的命題，從而使命題邏輯的內(nèi)容變得豐富起來我們要討論的僅只是復(fù)合命題的真值，此值可由組成它的簡單命題的真值所確定值得注意的是邏輯聯(lián)結(jié)詞與日常自然用語中的有關(guān)聯(lián)結(jié)詞的共同點和不同點,27,常用的邏輯聯(lián)結(jié)詞(五個),否定詞（negation）“ ?”是個一元聯(lián)結(jié)詞，亦稱否

20、定符號．一個命題P加上否定詞就形成了一個新的命題，記作? P，這個新命題是命題的否定，讀作非P。 否定詞 “ ?”的真值規(guī)定如下：若命題P的真值為真，那么? P的真值就為假；若P的真值為假，那么? P的真值就為真． ? P與P間的真值關(guān)系，常常使用稱作真值表的一種表格來表示.,28,?P的定義,真值表,真值表表明了?P的真值如何依賴于P的真值真值表描述了命題之間的真值關(guān)系，很直觀真值表是命題邏輯里研究真值關(guān)系的重要工具,29,

21、例1,“昨天張三去看球賽了”．該命題以P表示；“昨天張三沒有去看球賽”，該新命題便可用?P表示． 若昨天張三去看球賽了，命題P是真的，那么新命題?P必然是假的．反之，若命題P是假的，那么?P就是真的．,30,例2,Q：今天是星期三?Q：今天不是星期三?Q不能理解為“今天是星期四”，因為“今天是星期三”的否定，并不一定必是星期四，還可能是星期五、星期六……Q：這些都是男同學(xué)。?Q：這些不都是男同學(xué)。 (翻譯成“

22、這些都不是男同學(xué)”是錯的。),31,合取詞?,合取詞(Conjunction)?是個二元命題聯(lián)結(jié)詞，亦稱合取符號將兩個命題P, Q聯(lián)結(jié)起來，構(gòu)成一個新的命題 P ? Q，讀作P , Q的合取，也可讀作P與Q這個新命題P ? Q的真值與構(gòu)成它的命題P, Q的真值間的關(guān)系，由合取詞真值表來規(guī)定。,32,合取詞真值表,只有當(dāng)兩個命題變項P＝T，Q=T時方有 P?Q ＝T。而P，Q只要有一為F，則P?Q =F。P?Q可用來表

23、示日常用語P與Q，或P并且Q。,33,例3,P：教室里有10名女同學(xué)；Q：教室里有15名男同學(xué)；命題P ? Q : “教室里有10名女同學(xué)與15名男同學(xué)”。,34,例4,A：今天下雨了．B：教室里有100張桌子。命題A ? B是 ：“今天下雨了并且教室里有100張桌子”．,35,合取詞與日常自然用語中的聯(lián)結(jié)詞,邏輯聯(lián)結(jié)詞是自然用語中聯(lián)結(jié)詞的抽象，與”合取詞?”并不等同，這是需注意的．日常自然用語里的聯(lián)結(jié)詞“和”、“與”、“并

24、且”，一般是表示兩種同類有關(guān)事物的并列關(guān)系。而在邏輯語言中僅考慮命題與命題之間的形式關(guān)系并不顧及日常自然用語中是否有此說法。 這樣，“?”同“與”、“并且”又不能等同視之。日常自然用語中說，“這臺機(jī)器質(zhì)量很好，但是很貴”，這句話的含義是說同一臺機(jī)器質(zhì)量很好而且很貴。 若用P表示“這臺機(jī)器質(zhì)量很好”，用Q表示“這臺機(jī)器很貴”，那么這句話的邏輯表示就是P ? Q ，盡管這句話里出現(xiàn)的聯(lián)結(jié)詞是“但是”?？傊?，合

25、取詞有“與”、“并且”的含義。,36,析取詞∨,析取詞(disjunction)“∨”是個二元命題聯(lián)結(jié)詞將兩個命題P, Q聯(lián)結(jié)起來，構(gòu)成一個新的命題P∨Q，讀作P, Q的析取，也讀作P或Q這個新命題的真值與構(gòu)成它的命題P, Q的真值間的關(guān)系，由析取詞真值表來規(guī)定,37,析取詞真值表,當(dāng)P、Q有一取值為T時, P∨Q便為T。僅當(dāng)P、Q均取F值時, P∨Q方為F。這就是析取詞的定義, P∨Q可用來表示自然用語P或Q。,38,例,例5

26、P: 今天刮風(fēng) Q: 今天下雨命題“今天刮風(fēng)或者下雨”便可由P∨Q來描述了例6A: 2小于3B: 雪是黑的A∨B就是命題“2小于3或者雪是黑的” 由于2小于3是真的，所以A∨B必取值為真，盡管“雪是黑的”這命題取假,39,蘊(yùn)涵詞?,蘊(yùn)涵詞(implication)“?”是個二元命題聯(lián)結(jié)詞將兩個命題P, Q聯(lián)結(jié)起來, 構(gòu)成一個新的命題P?Q，讀作如果P則Q，或讀作P蘊(yùn)涵Q如果P那么Q，其中P

27、稱前件(前項、條件)，Q稱后件(后項、結(jié)論)規(guī)定只有當(dāng)P為T而Q為F時，P?Q = F 而P = F，Q任意，或P = T，Q = T時P?Q均取值為T。,40,蘊(yùn)涵詞?真值表,P?Q = T下, 若P = T必有Q = T, 而不會出現(xiàn)Q = F, 這表明P?Q體現(xiàn)了P是Q成立的充分條件。P?Q = T下, 若P = F可有Q = T, 這表明P?Q體現(xiàn)了P不必是Q成立的必要條件。,,P: 下雨；Q: 地濕,41,例7,P

28、：天下雨了Q：地上是濕的P?Q如果天下雨，那么地是濕的。 T如果天下雨，那么地不是濕的。 F如果天沒有下雨，那么地是濕的。 T如果天沒有下雨，那么地不是濕的。T,42,P?Q = ?P∨Q,在P、Q的所有取值下, P?Q同?P∨Q都有相同的真值: P?Q = ?P∨Q (真值相同的等值命題以等號聯(lián)結(jié))這也說明?可由?、∨來表示, 從邏輯上看“如果P則Q”同“非P或Q”是等同的兩個命題實際

29、上，{?, ∨}構(gòu)成一個聯(lián)結(jié)詞的完備集，可表達(dá)任何聯(lián)結(jié)詞,43,因果關(guān)系,引入?的目的是希望用來描述命題間的推理，表示因果關(guān)系使用P?Q能描述推理P?Q為真時，只要P為真必有Q真，而不能出現(xiàn)P真而Q假就夠了P為假時，Q取真取假，并不違背P為真時Q必真。從而仍可規(guī)定P為假時，P?Q取真當(dāng)P = F時對P?Q真值的不同定義方式將給推理的討論帶來不同的表示形式，也是允許的,44,例8,P: n > 3 (n為整數(shù)) Q:

30、n2 > 9 命題P?Q表示“如果n > 3那么n2 > 9”, 分析P?Q的真值P = Q = T。這時如n = 4 > 3，有n2 = 16 > 9，這符合事實 P?Q = T，正是我們所期望的可以P?Q表示P、Q間的因果關(guān)系，這時規(guī)定P? Q是自然的P = T, Q = F。如n > 3而 n2 9 由于前提條件n > 3不成立，而n2 > 9 

31、;成立與否并不重要，都不違反對自然用語“如果n > 3那么n2 > 9”成立的肯定。于是 P = F時可規(guī)定P ?Q = T,45,如果……那么……,蘊(yùn)涵詞?與自然用語“如果…那么…”有一致的一面，可表示因果關(guān)系 然而P、Q是無關(guān)的命題時，邏輯上允許討論P(yáng)?Q。并且P = F則P?Q = T，這在自然用語中是不大使用的。對P = F時P?Q的值另作規(guī)定也是可以的, 同樣不違反自然語句“如果……那么……”可以用P?Q

32、來描述。總之，對P?Q的這種說明是可接受的, 但也不是說僅只有這樣的解釋才是合理的,46,例9,P: 2 + 2 = 5Q: 雪是黑的P?Q就是命題“如果2 + 2 = 5, 那么雪是黑的”從蘊(yùn)涵詞的定義看，由2 + 2 = 5是不成立的或說P取F值, 不管Q取真取假都有P?Q = T,47,蘊(yùn)涵詞,蘊(yùn)含式P→Q可以用多種方式陳述: 給定命題P→Q, 我們把Q→P, ?P→?Q, ?Q→?P分別叫做命題P→Q的逆命

33、題, 否命題和逆否命題,48,雙條件詞?,雙條件詞(Biconditional)“?”是個二元命題聯(lián)結(jié)詞,49,(P?Q)∧(Q?P) = P?Q,只有當(dāng)兩個命題P、Q的真值相同或說P = Q時，P?Q的真值方為T。而當(dāng)P、Q的真值不同時， P?Q = F若建立(P?Q)∧(Q?P)的真值表，就可發(fā)現(xiàn)(P?Q)∧(Q?P)和P?Q有相同的真值，于是 (P?Q)∧(Q?P) = P?Q,50,例10,

34、P: ?ABC是等腰三角形Q: ?ABC中有兩個角相等命題P?Q就是“?ABC是等腰三角形當(dāng)且僅當(dāng)?ABC中有兩個角相等”。顯然就這個例子而言P?Q = T,51,總結(jié),定義的五個聯(lián)結(jié)詞是數(shù)理邏輯中最基本最常用的邏輯運(yùn)算一元二元聯(lián)結(jié)詞還有多個，此外還有三元以至更多元的聯(lián)結(jié)詞，因其極少使用，況且又都可由這五個基本聯(lián)結(jié)詞表示出來，所以無需一一定義了聯(lián)結(jié)詞是由命題定義新命題的基本方法命題邏輯的許多問題都可化成是計算復(fù)合命題的真假值問

35、題，真值表方法是極為有力的工具，是應(yīng)十分重視和經(jīng)常使用的,52,總結(jié),由聯(lián)結(jié)詞構(gòu)成新命題的真值表中，對僅由兩個變元P、Q構(gòu)成的新命題A而言，每個變元有T、F兩種取值，從而P、Q共有四種可能的取值，對應(yīng)于真值表中的四行,，每一行下命題A都有確定的真值對P、Q的每組真值組合(如P = T, Q = F)或說真值指派，都稱作命題A的一個解釋一般地說，當(dāng)命題A依賴于命題P1,…, Pn，從P1,…, Pn 到A的真值表就有2n行, 每一行對

36、應(yīng)著P1, …, Pn的每組真值都稱作命題A的一個解釋，A有2n個解釋，命題的解釋用符號I表示,53,總結(jié),由于數(shù)理邏輯是采用數(shù)學(xué)的符號化的方法來研究命題間最一般的真值規(guī)律的，而不涉及判斷一個命題本身如何取真取假，拋開命題的具體含義，而是抽象形式地討論邏輯關(guān)系，這就導(dǎo)致了數(shù)理邏輯中所討論的命題與自然用語的差異聯(lián)結(jié)詞∧、∨、?同構(gòu)成計算機(jī)的與門、或門和非門電路是相對應(yīng)的。從而命題邏輯是計算機(jī)硬件電路的表示、分析和設(shè)計的重要工具。也正是數(shù)

37、理邏輯應(yīng)用于實際特別是應(yīng)用于計算機(jī)學(xué)科推動了數(shù)理邏輯的發(fā)展,54,不同的符號,五個聯(lián)結(jié)詞在不同的書中會采用不同的符號?P以～P表示P∧Q以P·Q表示P∨Q以P + Q表示 P?Q以P?Q表示 P?Q以P?Q表示,55,1.3 合式公式(Well Formed Formula),命題公式是命題邏輯討論的對象由命題變項使用聯(lián)結(jié)詞可構(gòu)成任意多的復(fù)合命題，如P∧Q, P∧Q∨R, P??Q等。問題是它們是否都有意義呢？

38、只有一個聯(lián)結(jié)詞的命題?P，P∧Q，P?Q當(dāng)然是有意義的由兩個聯(lián)結(jié)詞構(gòu)成的命題P∧Q∨R至少意義不明確，是先作P∧Q再對R做∨，還是先作Q∨R再對P作∧呢? 括號解決 由命題變項、命題聯(lián)結(jié)詞和圓括號便組成了命題邏輯的全部符號進(jìn)一步的問題是建立一個一般的原則以便生成所有的合法的命題公式，并能識別什么樣的符號串是合法的（有意義的）？,56,合式公式(簡記為Wff)的定義,簡單命題是合式公式如果A是合式公式，那么?A也是合式公式如果A

39、、B是合式公式，那么(A∧B)，(A∨B)， (A?B)和(A?B)是合式公式當(dāng)且僅當(dāng)經(jīng)過有限次地使用1, 2, 3所組成的符號串才是合式公式這個定義給出了建立合式公式的一般原則，也給出了識別一個符號串是否是合式公式的原則這是遞歸(歸納)的定義。在定義中使用了所要定義的概念，如在2和3中都出現(xiàn)了所要定義的合式公式字樣，其次是定義中規(guī)定了初始情形，如1中指明了已知的簡單命題是合式公式。條件4說明了哪些不是合式公式，而1、2和3說明

40、不了這一點,57,判斷一個公式是否為合式公式,若判斷一個公式是否為合式公式，必然要層層解脫回歸到簡單命題方可判定合式公式?(P∧Q), (P?(P∧Q)), (((P?Q)∧(Q?R))?(P?R))非合式公式 ?P∨Q∨, ((P?Q)?( ∧Q)), (P?Q,58,約定,為了減少圓括號的數(shù)量，可以引入一些約定規(guī)定聯(lián)結(jié)詞優(yōu)先級的辦法，可按?， ∧， ∨，?，?的排列次序安排優(yōu)先的級別多個同一聯(lián)結(jié)詞按從左到右的優(yōu)

41、先次序。這樣，在書寫合式公式時，可以省去部分或全部圓括號。通常采用省略一部分又保留一部分括號的辦法，這樣選擇就給公式的閱讀帶來方便。如 (P?(Q∨R))可寫成P?(Q∨R)或P?Q∨R(P?(P?R))可寫成P?(P?R)命題演算中只討論合式公式，將合式公式就稱作公式,59,1.4 重言式 /可滿足式/矛盾式,如果一個公式，對于任一解釋I其值都為真，就稱為重言式（永真式）。如P∨?P是一個重言式由∨、∧、

42、?和?聯(lián)結(jié)的重言式仍是重言式。一個公式，如在某個解釋I0下值為真, 則稱它是可滿足的。如P∨Q，當(dāng)取I0 = (T, F)，即P = T, Q = F時便有P∨Q = T, 所以是可滿足的重言式當(dāng)然是可滿足的矛盾式（永假式或不可滿足式）：如果一個公式，對于任一解釋I值都是假的，便稱是矛盾式。如P∧?P就是矛盾式,60,三類公式間關(guān)系,1. 公式A永真， 當(dāng)且僅當(dāng)?A永假2. 公式A可滿足, 當(dāng)且僅當(dāng)?A非永真3. 不是可滿

43、足的公式必永假4. 不是永假的公式必可滿足,61,1.4.2 代入規(guī)則,A是一個公式，對A使用代入規(guī)則得公式B，若A是重言式，則B也是重言式為保證重言式經(jīng)代入規(guī)則仍得到保持，要求公式中被代換的只能是命題變元(原子命題), 而不能是復(fù)合命題對公式中某命題變元施以代入，必須對該公式中出現(xiàn)的所有同一命題變元代換以同一公式。,62,規(guī)則1舉例 如可用(R∧S)來代換某公式中的P，而不能反過來將公式中的(R∧S)以P代之

44、 這一要求可以以代數(shù)的例子來說明，如對(a + b)2 = a2 + 2ab + b2 可以a = cd代入，仍會保持等式成立。而若將a + b以cd代入，結(jié)果左端得(cd)2，而右端無法代入cd，不能保持等式成立了規(guī)則2舉例A = (R∨S)∨?(R∨S)，用?S只代換第二個R，則有： B = (R∨S)∨?(?S ∨S) = R∨S 不是重言式,例11,63,使用代入規(guī)則證明重言式,例12. 判斷

45、(R∨S) ∨?(R∨S)為重言式。因P∨?P為重言式, P以(R∨S)代入即得例13. 判斷((R∨S)∧((R∨S)?(P∨Q)))?(P∨Q)為重言式。不難驗證(A∧(A?B))?B是重言式，A 以R∨S代入，B 以P∨Q代入即得,64,1.5 命題形式化,一些推理問題的描述，常是以自然語句來表示的，需首先把自然語句形式化成邏輯語言，即以符號表示的邏輯公式，然后根據(jù)邏輯演算規(guī)律進(jìn)行推理演算先要引入一些命題符號

46、P, Q, …用來表示自然語句中所出現(xiàn)的簡單命題，進(jìn)而依自然語句通過聯(lián)結(jié)詞將這些命題符號聯(lián)結(jié)起來，以形成表示自然語句的合式公式,65,1.5.1 簡單自然語句的形式化,命題1. 北京不是村莊。令P表示“北京是村莊”，于是命題1可表示為?P。命題2. 李明既聰明又用功。令P表示“李明聰明”，Q表示“李明用功”，于是命題2可表示為P∧Q。命題3. squr(2)是有理數(shù)的話, 2squr(2)也是有理數(shù)。令P表示“squr

47、(2)是有理數(shù)”，Q表示“2squr(2)是有理數(shù)”，于是命題3可表示為P?Q。,66,1.5.2 較復(fù)雜自然語句的形式化,需注意的是邏輯聯(lián)結(jié)詞是從自然語句中提煉抽象出來的，它僅保留了邏輯內(nèi)容，而把自然語句所表達(dá)的主觀因素、心理因素以及文藝修辭方面的因素全部撇開了，從而命題聯(lián)結(jié)詞只表達(dá)了自然語句的一種客觀性質(zhì)又由于自然語句本身并不嚴(yán)謹(jǐn)，常有二義性，自然會出現(xiàn)同一自然語句的不等價的邏輯描述，其根由在于人們對同一自然語句的不同理解例

48、如: 愛因斯坦是我的崇拜者自然語句聯(lián)結(jié)詞與邏輯聯(lián)結(jié)詞無固定關(guān)系,67,張三與李四是表兄弟。 這是普通的自然用語，它是一個命題，令以R表示。若形式地規(guī)定: P: 張三是表兄弟。Q: 李四是表兄弟。 那么R = P∧Q顯然，這樣的形式化是錯誤的。原因是“張三是表兄弟”，“李四是表兄弟”都不是命題。實際上“張三與李四是表兄弟”才是一個命題，而且是一個簡單命題。這例子說明自然語句中的“與”不一定都能用合取詞來表

49、達(dá),例12 (“與”未必為合取詞),68,張三或李四都能做這件事。這句話中的“或”不一定就用析取詞來表示，應(yīng)允許有的人把這命題的內(nèi)容理解為： 張三能做這件事而且李四也能做這件事 這樣，這句話便可以P∧Q的形式表示了,例13 (“或”未必為析取詞),69,例14 (“或”未必為析取詞),A: 今晚我在家里看電視。B: 今晚我去體育場看球賽。C: 今晚我在家里看電視或去體育場看球賽。問題是C與A∨B是否表達(dá)的

50、是同一命題呢?,70,否。因為C同A、B的真值關(guān)系為,,例14,71,異或(不可兼或),這表的前三行很容易理解，而第四行是說今晚我在家看電視，又去體育場看球賽。顯然對同一個人來說這是不可能的，從而這時C的真值為F。這就說明了C與A∨B邏輯上是并不相等的。即C中出現(xiàn)的“或”不能以“∨”來表示C同A, B的邏輯關(guān)系，常稱為異或(不可兼或), 以 表示, 有不難驗證 C = (?A∧B) ∨ (A∧?B),72,例

51、15,今天我上班, 除非今天我病了以P表示今天我病了，Q表示今天我上班 可以理解為：除非今天我病了，否則今天我來上班進(jìn)一步： 如果今天我不生病，那么我來上班可描述成?P?Q,73,作業(yè),P12 1(2, 4, 6, 8) 4(2, 4, 6) 5(2, 4, 6, 8),74,悖論,“我正在說謊”。他是在說謊還是在說真話呢? 如果他講真話, 那么他所說的是真, 也就是他在說謊。我們

52、得出結(jié)論如果他講真話, 那么他是在說謊另一方面, 如果他是說謊, 那么他說的是假; 因為他承認(rèn)他是說謊, 所以他實際上是在說真話, 我們得出結(jié)論如果他是說謊, 那么他是講真話。從以上分析, 我們得出他必須既非說謊也不是講真話。這樣, 陳述句“我正在說謊”事實上不能指定它的真假, 所以不是命題，而是“悖論”。,75,悖論,悖論是自相矛盾的命題。即如果承認(rèn)這個命題成立，就可推出它的否定命題成立；反之，如果承認(rèn)這個命題的否定命題成立，

53、又可推出這個命題成立 A paradox is a statement or group of statements that leads to a contradiction or a situation which defies intuition 例如比較有名的理發(fā)師(羅素)悖論：某鄉(xiāng)村有一位理發(fā)師，一天他宣布：只給不自己刮胡子的人刮胡子。這里就產(chǎn)生了問題：理發(fā)師給不給自己刮胡子？如果他給自己刮胡子，他就是自己刮胡

54、子的人，按照他的原則，他不能給自己刮胡子；如果他不給自己刮胡子，他就是不自己刮胡子的人，按照他的原則，他就應(yīng)該給自己刮胡子。這就產(chǎn)生了矛盾,76,悖論,1900年前后,在數(shù)學(xué)的集合論中出現(xiàn)了三個著名悖論: 羅素悖論、康托爾悖論、布拉利—福爾蒂悖論。這些悖論特別是羅素悖論，在當(dāng)時的數(shù)學(xué)界與邏輯界內(nèi)引起了極大震動。觸發(fā)了數(shù)學(xué)的第三次危機(jī),77,蘊(yùn)涵詞形式化,設(shè) P:天冷，Q:小王穿羽絨服，將下列命題符號化 (1) 只要天冷，小王就穿