1、10/10/2020,Discrete Math. , Hongzhi Qiao,1,Discrete Mathematics 30課時(shí)，15次課 聯(lián)系方式：,10/10/2020,Discrete Math. , Hongzhi Qiao,2,緒論,離散數(shù)學(xué)是指計(jì)算機(jī)科學(xué)中所使用的各種離散的數(shù)學(xué)結(jié)構(gòu)。 結(jié)構(gòu)是指系統(tǒng)中的各個(gè)組成部分有機(jī)地搭配和排列。 任何事物都有自己的結(jié)構(gòu)。 每一門學(xué)科也有自己的結(jié)構(gòu)。,10/10/2020,Discrete Math. , Hongzhi Qiao,3,緒論,1. 人體的結(jié)構(gòu) 人體由大腦、五官、四肢、心、肝、肺等器官所組成。 基本元素是各種細(xì)胞。 2. 房屋

2、的結(jié)構(gòu) 房屋由地基、墻、門、窗、地板、房頂?shù)冉ㄖ锼M成。 基本材料是磚、瓦、鋼筋、水泥、石灰等。 3. 學(xué)校的結(jié)構(gòu) 學(xué)校由若干院、系、所、處、科室、班級(jí)等單位所組成。 基本成員是教師、學(xué)生、管理人員、實(shí)驗(yàn)人員等。 4. 計(jì)算機(jī)的結(jié)構(gòu) 計(jì)算機(jī)由主板、CPU、內(nèi)存條、硬盤、軟驅(qū)、電源、機(jī)箱、顯示器、鍵盤、鼠標(biāo)等部件所組成。 基本成員是各種超大規(guī)模集成電路芯片。,10/10/2020,Discrete Math. , Hongzhi Qiao,4,緒論,化學(xué)的結(jié)構(gòu) 化學(xué)主要由無(wú)機(jī)化學(xué)和有機(jī)化學(xué)所組成。 基本成員是各種化學(xué)元素。 物理的結(jié)構(gòu) 物理主要由力學(xué)、電學(xué)、光學(xué)、熱學(xué)所組成。 基本成員是各種場(chǎng)

3、。 數(shù)學(xué)的結(jié)構(gòu) 數(shù)學(xué)主要由連續(xù)數(shù)學(xué)和離散數(shù)學(xué)所組成。 基本成員是各種集合的元素。,10/10/2020,Discrete Math. , Hongzhi Qiao,5,緒論,1. 離散數(shù)學(xué)是離散的數(shù)學(xué)結(jié)構(gòu)的縮寫。 2. 離散數(shù)學(xué)的研究對(duì)象是世間一切事物之間的關(guān)系。 3. 離散數(shù)學(xué)所采用的研究方法有集合、代數(shù)、圖、數(shù)理邏輯等。,10/10/2020,Discrete Math. , Hongzhi Qiao,6,離散數(shù)學(xué)的內(nèi)容： 數(shù)理邏輯（Mathematics Logic) 集合論(Sets) 組合論（Combination) 圖論（Graph Theory) 代數(shù)結(jié)構(gòu)（Algbra Stru

4、cture) 線性代數(shù)(Linear Algbra ) 概率論（Propobility Theory),緒論,10/10/2020,Discrete Math. , Hongzhi Qiao,7,緒論,數(shù)理邏輯 計(jì)算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物 集合論 集合：一種重要的數(shù)據(jù)結(jié)構(gòu) 關(guān)系：關(guān)系數(shù)據(jù)庫(kù)的理論基礎(chǔ) 函數(shù)：所有計(jì)算機(jī)語(yǔ)言中不可缺少的一部分 圖論 數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計(jì)算機(jī)網(wǎng) 絡(luò)原理的基礎(chǔ) 代數(shù)系統(tǒng) 計(jì)算機(jī)編碼和糾錯(cuò)碼理論 數(shù)字邏輯設(shè)計(jì)基礎(chǔ) 計(jì)算機(jī)使用的各種運(yùn)算,10/10/2020,Discrete Math. , Hongzhi Qiao,8,18世紀(jì)，東普魯士的哥尼斯堡

5、（現(xiàn)今叫加里寧格勒，在波羅的海南岸）是一座景致迷人的城市，普勒格爾河橫貫其境，并在這兒形成兩條支流，把整座城市分割成4個(gè)區(qū)域：河的兩岸（A和B），河中的島（C）和兩條支流之間的半島（D）。當(dāng)時(shí)有七座橋橫跨普勒格爾河及其支流，把河岸、半島和河心島連接起來(lái)。有人在游覽時(shí)提出這樣的問(wèn)題：能否從某個(gè)地方出發(fā)，穿過(guò)所有的橋各一次后再回到出發(fā)點(diǎn).,Konigsberg七橋問(wèn)題,緒論,10/10/2020,Discrete Math. , Hongzhi Qiao,9,離散數(shù)學(xué)課程設(shè)置： 計(jì)算機(jī)系核心課程 信息類專業(yè)必修課程 其它類專業(yè)的重要選修課程,緒論,10/10/2020,Discrete Math.

6、 , Hongzhi Qiao,10,離散數(shù)學(xué)的后繼課程： 數(shù)據(jù)結(jié)構(gòu)、編譯技術(shù)、 算法分析與設(shè)計(jì)、人工智能、 數(shù)據(jù)庫(kù)、,緒論,10/10/2020,Discrete Math. , Hongzhi Qiao,11,教材： 離散數(shù)學(xué)（第二版） 方世昌 編著 西安電子科技大學(xué)出版社出版,緒論,10/10/2020,Discrete Math. , Hongzhi Qiao,12,參考教材： Discrete Mathematics and Its Application (Forth Edition: 1998) Author: Kenneth H. Reson Publisher: McGraw

7、-Hill 機(jī)械工業(yè)出版社 http:/,緒論,10/10/2020,Discrete Math. , Hongzhi Qiao,13,教學(xué)內(nèi)容:,數(shù)理邏輯（Mathematics Logic) 集合論(Sets) 圖論（Graph Theory),緒論,10/10/2020,Discrete Math. , Hongzhi Qiao,14,離散數(shù)學(xué)課程的學(xué)習(xí)方法: 強(qiáng)調(diào)：邏輯性、抽象性； 注重：概念、方法與應(yīng)用,緒論,10/10/2020,Discrete Math. , Hongzhi Qiao,15,緒論,概念（正確） 必須掌握好離散數(shù)學(xué)中大量的概念 判斷（準(zhǔn)確） 根據(jù)概念對(duì)事物的屬性進(jìn)

8、行判斷 推理（可靠） 根據(jù)多個(gè)判斷推出一個(gè)新的判斷,10/10/2020,Discrete Math. , Hongzhi Qiao,16,第一章 - 數(shù)理邏輯,1.1.1 命題邏輯 Proposition Logic,邏輯學(xué)： 研究推理的一門學(xué)科 數(shù)理邏輯： 用數(shù)學(xué)方法研究推理的一門數(shù)學(xué)學(xué)科,- 一套符號(hào)體系 + 一組規(guī)則,10/10/2020,Discrete Math. , Hongzhi Qiao,17,數(shù)理邏輯的內(nèi)容： 古典數(shù)理邏輯： 命題邏輯、謂詞邏輯 現(xiàn)代數(shù)理邏輯： 公理化集合論、遞歸論、模型論、證明論,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. ,

9、 Hongzhi Qiao,18,命題 Proposition 一個(gè)有確定真或假意義的語(yǔ)句.,命題邏輯 Proposition Logic,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,19,命題是一個(gè)非真即假（不可兼）的陳述句。有兩層意思，首先命題是一個(gè)陳述句，而命令句、疑問(wèn)句和感嘆句都不是命題。其次是說(shuō)這個(gè)陳述句所表達(dá)的內(nèi)容可決定是真還是假，而且不是真的就是假的，不能不真又不假，也不能又真又假。 凡與事實(shí)相符的陳述句為真語(yǔ)句，而與事實(shí)不符的陳述句為假語(yǔ)句。,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. ,

10、 Hongzhi Qiao,20,這就是說(shuō)，一個(gè)命題具有兩種可能的取值（又稱真值）為真或?yàn)榧伲种荒苋∑湟?。通常用大寫字母T表示真值為真，用F表示真值為假，有時(shí)也可分別用1和0表示它們。 因?yàn)橹挥袃煞N取值，所以這樣的命題邏輯也稱為二值邏輯。 我們把以這種非真必假的命題作為研究對(duì)象的邏輯稱為古典邏輯，但也有人反對(duì)關(guān)于命題的這種觀點(diǎn)，認(rèn)為存在既不真也不假的命題，例如：直覺主義邏輯、多值邏輯等。,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,21,舉例：下列句子不是命題。 （1） 8大于12嗎？ （2） 請(qǐng)勿吸煙。 （3） X大于Y。 （4）

11、 本頁(yè)這一行的這句話是假話。,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,22,（1）是一個(gè)疑問(wèn)句，不是陳述句。 （2）是一個(gè)祈使句。 （3）是一個(gè)不能確定其真假的句子，它可能為真，也可能為假，從而不為命題。在判斷一個(gè)語(yǔ)句是否是命題時(shí)，從語(yǔ)法上就是看他是否是陳述句。但值得注意的是，這里所說(shuō)的陳述句不包括那些“自指謂”的語(yǔ)句。 （4）這個(gè)語(yǔ)句，它的結(jié)論是對(duì)自身而言的，就是所謂“自指謂”的。這種自指謂的語(yǔ)句往往會(huì)產(chǎn)生自相矛盾的結(jié)論，即悖論。,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qi

12、ao,23,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ù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,24,Consider

13、 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 sentences have not been as

14、signed values. Various ways to form propositions from sentences of this type will be discussed in Section 1.3.,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,25,命題的語(yǔ)句形式 陳述句 非命題語(yǔ)句： 疑問(wèn)句 命令句 感態(tài)句 非命題陳述句：悖論語(yǔ)句,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,26,命題的符號(hào)表示： 大小寫英文字母：P、Q、R、 p 、q 、r、。 命題

15、真值（Truth Values）的表示： 真：T、1 假：F、0,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,27,命題語(yǔ)句真值確定的幾點(diǎn)說(shuō)明： 1、時(shí)間性 2、區(qū)域性 3、標(biāo)準(zhǔn)性 命題真值間的關(guān)系表示： 真值表（Truth Table),第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,28,Let p be a proposition. The statement It is not the case that p. is another proposition, called

16、 the negation of p. The negation of p is denoted by p. The proposition p is read not p.,p的否定,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,29,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 n

17、egation can be more simply expressed by Today is not Friday.,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,30,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,31,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 a

18、nd is false otherwise. The proposition pq is called the conjunction of p and q. The truth table for pq is shown in Table 2.,p和q的合取,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,32,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,33,Find the conjunction of the propositions p and q where p is

19、 the proposition Today is Friday and q is the proposition 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 i

20、t does not rain.,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,34,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 i

21、s shown in Table 3.,p和q的析取,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,35,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,36,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 prop

22、osition Today 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ù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,37,Let p and q be propos

23、itions.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,單條件, 蘊(yùn)涵 P:前提 Q:結(jié)論,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hon

24、gzhi Qiao,38,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,39,“PQ”真假值的這種取法也有人為因素，表現(xiàn)在： （1） 根據(jù)PQ真假值取法的定義可以看出，若P為假，不論Q是否為真，則PQ為真。 我們來(lái)看 命題：如果月亮從西邊出來(lái)，則太陽(yáng)也從西邊出來(lái)。由定義這是一個(gè)真命題，但這使人感到有點(diǎn)不自然，既然月亮不會(huì)從西邊出來(lái)，我們完全可以認(rèn)為這個(gè)命題毫無(wú)用處或毫無(wú)意義。但是，我們感興趣的主要是（數(shù)學(xué)）推理和證明的方法，在這種情況下，命題PQ真的意義在于我們能從P真推出Q真，而沒有必要追求從P假能推出什么來(lái)。 例如，關(guān)于整數(shù)的如下命

25、題：對(duì)某個(gè)實(shí)數(shù)n，如果n 2，那么n*2 4。這是個(gè)真命題，而無(wú)須考慮命題變項(xiàng)取什么值。,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,40,（2） 蘊(yùn)涵詞可以連接兩個(gè)以上意義毫不相干的命題，只要前件和后件滿足P ? Q為真的定義所規(guī)定的條件，我們便可說(shuō)“PQ為真”。PQ真假的這種規(guī)定也引起了爭(zhēng)論。 例如：如果地球停止了轉(zhuǎn)動(dòng)，則大熊貓產(chǎn)在中國(guó)。 但注意到，我們關(guān)心的是推理，關(guān)心能否從P真推出Q真，不關(guān)心各命題之間實(shí)際意義是否有聯(lián)系。,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,

26、41,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 Thursday. And the contrapositive of this implication is If I do not have a test today, then today is not Thursday.,第一章 - 數(shù)理邏輯,10/10/2020,Discrete Math. , Hongzhi Qiao,42,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 and is false otherwise. The truth table for p q is shown in Table 6.,P當(dāng)且僅當(dāng)q,雙條件，等價(jià),第一