第一次課緒論與數(shù)理邏輯初步

1、2021年10月20日15時31分 discrete math. , hongzhi qiao1 離散數(shù)學離散數(shù)學離散數(shù)學離散數(shù)學 discrete mathematics30課時，課時，15次課次課主講：喬洪志主講：喬洪志聯(lián)系方式：聯(lián)系方式：2021年10月20日15時31分 discrete math. , hongzhi qiao2緒論緒論 離散數(shù)學離散數(shù)學是指計算機科學中所使用的各種離是指計算機科學中所使用的各種離散的數(shù)學結構。散的數(shù)學結構。結構結構是指系統(tǒng)中的各個組成部分有機地搭配是指系統(tǒng)中的各個組成部分有機地搭配和排列。和排列。任何任何事物事物都有自己的結構。都有自己的結構。每一門

2、每一門學科學科也有自己的結構。也有自己的結構。2021年10月20日15時31分 discrete math. , hongzhi qiao3緒論緒論 1. 人體的結構 人體由大腦、五官、四肢、心、肝、肺等器官所組成。人體由大腦、五官、四肢、心、肝、肺等器官所組成。 基本元素是各種細胞。基本元素是各種細胞。2. 房屋的結構 房屋由地基、墻、門、窗、地板、房頂?shù)冉ㄖ锼M成。房屋由地基、墻、門、窗、地板、房頂?shù)冉ㄖ锼M成。 基本材料是磚、瓦、鋼筋、水泥、石灰等?；静牧鲜谴u、瓦、鋼筋、水泥、石灰等。3. 學校的結構 學校由若干院、系、所、處、科室、班級等單位所組成。學校由若干院、系、所、處、科

3、室、班級等單位所組成。 基本成員是教師、學生、管理人員、實驗人員等?；境蓡T是教師、學生、管理人員、實驗人員等。4. 計算機的結構 計算機由主板、計算機由主板、cpu、內存條、硬盤、軟驅、電源、機、內存條、硬盤、軟驅、電源、機箱、顯示器、鍵盤、鼠標等部件所組成。箱、顯示器、鍵盤、鼠標等部件所組成。 基本成員是各種超大規(guī)模集成電路芯片。基本成員是各種超大規(guī)模集成電路芯片。2021年10月20日15時31分 discrete math. , hongzhi qiao4緒論緒論 化學的結構 化學主要由無機化學和有機化學所組成。化學主要由無機化學和有機化學所組成。 基本成員是各種化學元素?；境蓡T是各

4、種化學元素。物理的結構 物理主要由力學、電學、光學、熱學所組成。物理主要由力學、電學、光學、熱學所組成。 基本成員是各種場?；境蓡T是各種場。數(shù)學的結構 數(shù)學主要由連續(xù)數(shù)學和離散數(shù)學所組成。數(shù)學主要由連續(xù)數(shù)學和離散數(shù)學所組成。 基本成員是各種集合的元素。基本成員是各種集合的元素。2021年10月20日15時31分 discrete math. , hongzhi qiao5緒論緒論 1. 1. 離散數(shù)學是離散數(shù)學是離散的數(shù)學結構離散的數(shù)學結構的縮寫。的縮寫。2. 2. 離散數(shù)學的研究對象是世間一切離散數(shù)學的研究對象是世間一切事物之間的關系。事物之間的關系。3. 3. 離散數(shù)學所采用的研究方法有

5、集離散數(shù)學所采用的研究方法有集合、代數(shù)、圖、數(shù)理邏輯等。合、代數(shù)、圖、數(shù)理邏輯等。2021年10月20日15時31分 discrete math. , hongzhi qiao6 離散數(shù)學的內容：離散數(shù)學的內容： 數(shù)理邏輯（數(shù)理邏輯（mathematics logic) 集合論集合論(sets) 組合論（組合論（combination) 圖論（圖論（graph theory) 代數(shù)結構（代數(shù)結構（algbra structure) 線性代數(shù)線性代數(shù)(linear algbra ) 概率論（概率論（propobility theory) 緒論緒論 2021年10月20日15時31分 discre

6、te math. , hongzhi qiao7緒論緒論 數(shù)理邏輯 計算機是數(shù)理邏輯和電子學相結合的產(chǎn)物計算機是數(shù)理邏輯和電子學相結合的產(chǎn)物集合論 集合：一種重要的數(shù)據(jù)結構集合：一種重要的數(shù)據(jù)結構 關系：關系數(shù)據(jù)庫的理論基礎關系：關系數(shù)據(jù)庫的理論基礎 函數(shù)：所有計算機語言中不可缺少的一部分函數(shù)：所有計算機語言中不可缺少的一部分圖論 數(shù)據(jù)結構、操作系統(tǒng)、編譯原理、計算機網(wǎng)數(shù)據(jù)結構、操作系統(tǒng)、編譯原理、計算機網(wǎng) 絡原理的基礎絡原理的基礎代數(shù)系統(tǒng) 計算機編碼和糾錯碼理論計算機編碼和糾錯碼理論 數(shù)字邏輯設計基礎數(shù)字邏輯設計基礎 計算機使用的各種運算計算機使用的各種運算2021年10月20日15時31分

7、 discrete math. , hongzhi qiao8 18世紀，東普魯士的哥尼斯堡（現(xiàn)今叫加里寧格勒，世紀，東普魯士的哥尼斯堡（現(xiàn)今叫加里寧格勒，在波羅的海南岸）是一座景致迷人的城市，普勒格爾河橫在波羅的海南岸）是一座景致迷人的城市，普勒格爾河橫貫其境，并在這兒形成兩條支流，把整座城市分割成貫其境，并在這兒形成兩條支流，把整座城市分割成4個區(qū)個區(qū)域：河的兩岸（域：河的兩岸（a和和b），河中的島（），河中的島（c）和兩條支流之間）和兩條支流之間的半島（的半島（d）。當時有七座橋橫跨普勒格爾河及其支流，把）。當時有七座橋橫跨普勒格爾河及其支流，把河岸、半島和河心島連接起來。有人在游覽時提

8、出這樣的河岸、半島和河心島連接起來。有人在游覽時提出這樣的問題：能否從某個地方出發(fā)，穿過所有的橋各一次后再回問題：能否從某個地方出發(fā)，穿過所有的橋各一次后再回到出發(fā)點到出發(fā)點. konigsbergkonigsberg七橋問題七橋問題緒論緒論 2021年10月20日15時31分 discrete math. , hongzhi qiao9離散數(shù)學課程設置：離散數(shù)學課程設置： 計算機系核心課程計算機系核心課程 信息類專業(yè)必修課程信息類專業(yè)必修課程 其它類專業(yè)的重要選修課程其它類專業(yè)的重要選修課程緒論緒論 2021年10月20日15時31分 discrete math. , hongzhi qia

9、o10 離散數(shù)學的后繼課程：離散數(shù)學的后繼課程： 數(shù)據(jù)結構、編譯技術、數(shù)據(jù)結構、編譯技術、 算法分析與設計、人工智能、算法分析與設計、人工智能、 數(shù)據(jù)庫、數(shù)據(jù)庫、緒論緒論 2021年10月20日15時31分 discrete math. , hongzhi qiao11 教材：教材： 離散數(shù)學離散數(shù)學（第二版）（第二版） 方世昌方世昌 編著編著 西安電子科技大學出版社出版西安電子科技大學出版社出版 緒論緒論 2021年10月20日15時31分 discrete math. , hongzhi qiao12 參考教材：參考教材： discrete mathematics and its appl

10、ication (forth edition: 1998) author: kenneth h. reson publisher: mcgraw-hill 機械工業(yè)出版社機械工業(yè)出版社 http:/ 緒論緒論 2021年10月20日15時31分 discrete math. , hongzhi qiao13教學內容教學內容: : 數(shù)理邏輯（數(shù)理邏輯（mathematics logic) 集合論集合論(sets) 圖論（圖論（graph theory)緒論緒論 2021年10月20日15時31分 discrete math. , hongzhi qiao14離散數(shù)學課程的學習方法離散數(shù)學課程的學

11、習方法: 強調：邏輯性、抽象性；強調：邏輯性、抽象性； 注重：概念、方法與應用注重：概念、方法與應用緒論緒論 2021年10月20日15時31分 discrete math. , hongzhi qiao15緒論緒論 概念（正確）（正確） 必須掌握好離散數(shù)學中大量的概念必須掌握好離散數(shù)學中大量的概念判斷（準確）（準確） 根據(jù)概念對事物的屬性進行判斷根據(jù)概念對事物的屬性進行判斷推理（可靠）（可靠） 根據(jù)多個判斷推出一個新的判斷根據(jù)多個判斷推出一個新的判斷2021年10月20日15時31分 discrete math. , hongzhi qiao16第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯1.1.

12、1 命題邏輯命題邏輯 proposition logic邏輯學：邏輯學： 研究推理的一門學科研究推理的一門學科數(shù)理邏輯：數(shù)理邏輯： 用數(shù)學方法研究推理的一門數(shù)學學科用數(shù)學方法研究推理的一門數(shù)學學科 - 一套符號體系一套符號體系 + 一組規(guī)則一組規(guī)則2021年10月20日15時31分 discrete math. , hongzhi qiao17數(shù)理邏輯的內容：數(shù)理邏輯的內容： 古典數(shù)理邏輯：古典數(shù)理邏輯： 命題邏輯、謂詞邏輯命題邏輯、謂詞邏輯 現(xiàn)代數(shù)理邏輯：現(xiàn)代數(shù)理邏輯： 公理化集合論、遞歸論、模型論、證明論公理化集合論、遞歸論、模型論、證明論第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年1

13、0月20日15時31分 discrete math. , hongzhi qiao18命題命題 proposition 一個有確定真或假意義的語句一個有確定真或假意義的語句.命題邏輯命題邏輯 proposition logic第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao19 命題命題是一個非真即假（不可兼）的陳述句。是一個非真即假（不可兼）的陳述句。有兩層意思，首先命題是一個陳述句，而命有兩層意思，首先命題是一個陳述句，而命令句、疑問句和感嘆句都不是命題。其次是令句、疑問句和感嘆句都不是命題。其次是說這個陳

14、述句所表達的內容可決定是真還是說這個陳述句所表達的內容可決定是真還是假，而且不是真的就是假的，不能不真又不假，而且不是真的就是假的，不能不真又不假，也不能又真又假。假，也不能又真又假。 凡與事實相符的陳述句為真語句，而與凡與事實相符的陳述句為真語句，而與事實不符的陳述句為假語句。事實不符的陳述句為假語句。第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao20 這就是說，一個命題具有兩種可能的取值這就是說，一個命題具有兩種可能的取值（又稱真值）為真或為假，又只能取其一。通常（又稱真值）為真或為假，又只能取其一。通常

15、用大寫字母用大寫字母t表示真值為真，用表示真值為真，用f表示真值為假，表示真值為假，有時也可分別用有時也可分別用1和和0表示它們。表示它們。 因為只有兩種取值，所以這樣的命題邏輯也因為只有兩種取值，所以這樣的命題邏輯也稱為二值邏輯。稱為二值邏輯。 我們把以這種非真必假的命題作為研究對象的我們把以這種非真必假的命題作為研究對象的邏輯稱為古典邏輯，但也有人反對關于命題的這種邏輯稱為古典邏輯，但也有人反對關于命題的這種觀點，認為存在既不真也不假的命題，例如：直覺觀點，認為存在既不真也不假的命題，例如：直覺主義邏輯、多值邏輯等。主義邏輯、多值邏輯等。第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10

16、月20日15時31分 discrete math. , hongzhi qiao21舉例：下列句子不是命題。舉例：下列句子不是命題。 （1） 8大于大于12嗎？嗎？ （2） 請勿吸煙。請勿吸煙。 （3） x大于大于y。 （4） 本頁這一行的這句話是假話。本頁這一行的這句話是假話。第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao22（1）是一個疑問句，不是陳述句。）是一個疑問句，不是陳述句。（2）是一個祈使句。）是一個祈使句。（3）是一個不能確定其真假的句子，它可能為真，）是一個不能確定其真假的句子，它可能為真，

17、也可能為假，從而不為命題。在判斷一個語句是否是也可能為假，從而不為命題。在判斷一個語句是否是命題時，從語法上就是看他是否是陳述句。但值得注命題時，從語法上就是看他是否是陳述句。但值得注意的是，這里所說的陳述句不包括那些意的是，這里所說的陳述句不包括那些“自指謂自指謂”的的語句。語句。（4）這個語句，它的結論是對自身而言的，就是所）這個語句，它的結論是對自身而言的，就是所謂謂“自指謂自指謂”的。這種自指謂的語句往往會產(chǎn)生自相的。這種自指謂的語句往往會產(chǎn)生自相矛盾的結論，即悖論。矛盾的結論，即悖論。第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math

18、. , hongzhi qiao23 all the following statements are propositions. 1. washington, d.c., is the capital of the united states of america. 2. toronto is the capital of canada. 3. 1+1=2. 4. 2+2=3. propositions 1 and 3 are true, whereas 2 and 4 are false. 第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math

19、. , hongzhi qiao24 consider the following sentences. 1. what time is it? 2. read this carefully. 3. x+1 =2. 4. x+y = z. sentences 1 and 2 are not propositions because they are not statements. sentences 3 and 4 are not propositions because they are neither true nor false, since the variables in these

20、 sentences have not been assigned values. various ways to form propositions from sentences of this type will be discussed in section 1.3. 第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao25命題的語句形式命題的語句形式 陳述句陳述句非命題語句：非命題語句： 疑問句疑問句 命令句命令句 感態(tài)句感態(tài)句 非命題陳述句：悖論語句非命題陳述句：悖論語句第一章第一章 - - 數(shù)理邏輯數(shù)理

21、邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao26命題的符號表示：命題的符號表示： 大小寫英文字母：大小寫英文字母：p、q、r、 p 、q 、r、。、。命題真值（命題真值（truth values）的表示：）的表示： 真：真：t、1 假：假：f、0 第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao27命題語句真值確定的幾點說明：命題語句真值確定的幾點說明： 1、時間性、時間性 2、區(qū)域性、區(qū)域性 3、標準性、標準性命題真值間的關系表示：命題真值間的關系表示：

22、真值表（真值表（truth table) 第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao28let p be a proposition. the statement it is not the case that p. is another proposition, called the negation of p. the negation of p is denoted by p. the proposition p is read not p.p的否定的否定第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯202

23、1年10月20日15時31分 discrete math. , hongzhi qiao29 find the negation of the proposition today is friday and express this in simple english.the negation is it is not the case that today is friday. this negation can be more simply expressed by today is not friday.第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discr

24、ete math. , hongzhi qiao30第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao31 let p and q be propositions. the proposition p and q, denoted by pq, is the proposition that is true when both p and q are true and is false otherwise. the proposition pq is called the conjunction of p and

25、 q. the truth table for pq is shown in table 2.p和和q的合取的合取第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao32第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao33 find the conjunction of the propositions p and q where p is the proposition today is friday and q is the p

26、roposition it is raining today.solution: the conjunction of these propositions, pq, is the proposition today is friday and it is raining today. this proposition is true on rainy fridays and is false on any day that is not a friday and on fridays when it does not rain.第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15

27、時31分 discrete math. , hongzhi qiao34 let p and q be propositions.the proposition p or q, denoted by pq,is the proposition that is false when p and q are both false and true otherwise. the proposition pq is called the disjunction of p and q.the truth table for pq is shown in table 3.p和q的析取第一章第一章 - -

28、數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao35第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao36 what is the disjunction of the propositions p and q where p and q are the same propositions as in example 4?solution: the disjunction of p and q, p q, is the proposition toda

29、y is friday or it is raining today. this proposition is true on any day that is either a friday or a rainy day (including rainy fridays). it is only false on days that are not fridays when it also does not rain.第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao37 let p and q be propo

30、sitions.the implication p q is the proposition that is false when p is true and q is false and true otherwise. in this implication p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).如果如果p,則則q單條件單條件, 蘊涵蘊涵p:前提前提q:結論結論第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時3

31、1分 discrete math. , hongzhi qiao38第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao39“pq”真假值的這種取法也有人為因素，表現(xiàn)在：真假值的這種取法也有人為因素，表現(xiàn)在：（1） 根據(jù)根據(jù)pq真假值取法的定義可以看出，若真假值取法的定義可以看出，若p為假，為假，不論不論q是否為真，則是否為真，則pq為真。為真。我們來看我們來看 命題：命題：如果月亮從西邊出來，則太陽也從西邊出來。如果月亮從西邊出來，則太陽也從西邊出來。由定義這是一個真命題，但這使人感到有點不自然，既由定義這是一個

32、真命題，但這使人感到有點不自然，既然月亮不會從西邊出來，我們完全可以認為這個命題毫無用然月亮不會從西邊出來，我們完全可以認為這個命題毫無用處或毫無意義。但是，我們感興趣的主要是（數(shù)學）推理和處或毫無意義。但是，我們感興趣的主要是（數(shù)學）推理和證明的方法，在這種情況下，命題證明的方法，在這種情況下，命題pq真的意義在于我們能真的意義在于我們能從從p真推出真推出q真，而沒有必要追求從真，而沒有必要追求從p假能推出什么來。假能推出什么來。例如，關于整數(shù)的如下命題：例如，關于整數(shù)的如下命題：對某個實數(shù)對某個實數(shù)n，如果，如果n 2，那么，那么n*2 4。這是個真命題，而無須考慮命題變項取什么值。這是個

33、真命題，而無須考慮命題變項取什么值。第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao40（2） 蘊涵詞可以連接兩個以上意義毫不相干的命題，只要蘊涵詞可以連接兩個以上意義毫不相干的命題，只要前件和后件滿足前件和后件滿足p ? q為真的定義所規(guī)定的條件，我們便可說為真的定義所規(guī)定的條件，我們便可說“pq為真為真”。pq真假的這種規(guī)定也引起了爭論。真假的這種規(guī)定也引起了爭論。例如：例如：如果地球停止了轉動，則大熊貓產(chǎn)在中國。如果地球停止了轉動，則大熊貓產(chǎn)在中國。 但注意到，我們關心的是推理，關心能否從但注意到，我們關

34、心的是推理，關心能否從p真推出真推出q真，真，不關心各命題之間實際意義是否有聯(lián)系。不關心各命題之間實際意義是否有聯(lián)系。 第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao41 find the converse and the contrapositive of the implication if today is thursday, then i have a test today.solution: the converse is if i have a test today, then today is

35、thursday.and the contrapositive of this implication is if i do not have a test today, then today is not thursday.第一章第一章 - - 數(shù)理邏輯數(shù)理邏輯2021年10月20日15時31分 discrete math. , hongzhi qiao42 let p and q be propositions, the biconditional p q is the proposition that is true when p and q have the same truth values a