離散數(shù)學(xué)-大學(xué)數(shù)學(xué)網(wǎng)

1、離 散 數(shù) 學(xué)及其應(yīng)用Discrete Mathematics,張清華 蒲興成 尹邦勇 劉勇重慶郵電大學(xué),2024/2/29,重慶郵電大學(xué) 理學(xué)院,1,2024/2/29,重慶郵電大學(xué) 理學(xué)院,,離散數(shù)學(xué)類課程地位：計(jì)算機(jī)相關(guān)專業(yè)核心課程信息類部分專業(yè)必修課程其它部分專業(yè)的選修課程離散數(shù)學(xué)的后繼課程：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、算法分析與設(shè)計(jì)、人工智能、數(shù)據(jù)庫(kù)、C++語(yǔ)言，……,2,2024/2/29,重慶郵電大學(xué) 理學(xué)院

2、,,學(xué)習(xí)該課程的目的： 一方面，它給后繼課，如數(shù)據(jù)結(jié)構(gòu)、編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫(kù)原理、軟件工程與方法學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)、程序設(shè)計(jì)等，提供必要的數(shù)學(xué)基礎(chǔ)（邏輯、關(guān)系、代數(shù)系統(tǒng)、圖論等）； 另一方面，通過(guò)學(xué)習(xí)離散數(shù)學(xué)，可以培養(yǎng)和提高自己的抽象思維和邏輯推理能力，為以后的軟、硬件學(xué)習(xí)和研究開發(fā)工作，打下堅(jiān)實(shí)的理論基礎(chǔ)。,3,2024/2/29,重慶郵電大學(xué) 理學(xué)院,,教學(xué)要求： 通過(guò)該課程的學(xué)習(xí)，學(xué)生應(yīng)

3、當(dāng)了解并掌握計(jì)算機(jī)科學(xué)中普遍采用的離散數(shù)學(xué)中的一些基本概念、基本思想、基本方法。自學(xué)要求： 通過(guò)反復(fù)看書及做課后習(xí)題，來(lái)加深對(duì)該課程中的一些基本概念的理解，逐步提高自己的抽象思維和邏輯推理能力。,4,2024/2/29,重慶郵電大學(xué) 理學(xué)院,,離散數(shù)學(xué)課程的學(xué)習(xí)方法：強(qiáng)調(diào)：邏輯推理、抽象思維；注重：概念、方法與應(yīng)用離散數(shù)學(xué)的學(xué)習(xí)要領(lǐng)：概念（正確）熟練掌握大量的基本概念（多、散） 判斷（準(zhǔn)確）根據(jù)概念對(duì)屬性進(jìn)行

4、判斷（巧） 推理（可靠）根據(jù)多個(gè)結(jié)論推出新的論斷（難）,5,課程主要內(nèi)容第一部分 數(shù)理邏輯：命題邏輯、謂詞邏輯。第二部分 集合論：集合、關(guān)系、函數(shù)。 第三部分 代數(shù)系統(tǒng)：二元運(yùn)算、代數(shù)系統(tǒng)、半群、群。第四部分 圖論：圖的基本概念、 路與圈、最短路、歐拉圖、 哈密爾頓圖、樹、平面圖。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,6,離散數(shù)學(xué)與

5、計(jì)算機(jī)的關(guān)系（簡(jiǎn)要）,第一部分 數(shù)理邏輯 計(jì)算機(jī)是數(shù)理邏輯和電子學(xué)相結(jié)合的產(chǎn)物，本章是智能科學(xué)中的知識(shí)表示、知識(shí)推理的基礎(chǔ)。 第二部分 集合論 集合是一種重要的數(shù)據(jù)結(jié)構(gòu)關(guān)系，關(guān)系數(shù)據(jù)庫(kù)的理論基礎(chǔ)函數(shù)，所有計(jì)算機(jī)語(yǔ)言中不可缺少的一部分。 第三部分 代數(shù)系統(tǒng) 計(jì)算機(jī)編碼和糾錯(cuò)碼理論數(shù)字邏輯設(shè)計(jì)基礎(chǔ)計(jì)算機(jī)使用的各種運(yùn)算，信息安全的密碼學(xué)需要代數(shù)系統(tǒng)為基礎(chǔ)。第四部分 圖論

6、 數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理計(jì)算機(jī)網(wǎng)絡(luò)原理的基礎(chǔ)。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,7,課程教學(xué)學(xué)時(shí)與作業(yè),課程學(xué)時(shí)： 64學(xué)時(shí)：主要講述第一部分?jǐn)?shù)理邏輯、第二部分集合與關(guān)系，第三部分代數(shù)系統(tǒng)（講到群的定義及其性質(zhì)）；第四部分圖論。 48學(xué)時(shí)：主要講述第一部分?jǐn)?shù)理邏輯（主要講命題邏輯）、第二部分集合與關(guān)系；第四部分圖論。成績(jī)構(gòu)成： 30%的平時(shí)成績(jī)+70%期末考試

7、成績(jī)。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,8,第一章 命題邏輯,數(shù)理邏輯是研究推理（即研究人類思維的形式結(jié)構(gòu)和規(guī)律）的科學(xué)，起源于17世紀(jì)，它采用數(shù)學(xué)符號(hào)化的方法，因此也稱為符號(hào)邏輯。從廣義上講，數(shù)理邏輯包括四論、兩演算——即集合論、模型論、遞歸論、證明論和命題邏輯演算、謂詞邏輯演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題邏輯和謂詞邏輯。本書也只研究這兩個(gè)邏輯演算。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,9,數(shù)理邏輯的創(chuàng)始人

8、是Leibniz，為了實(shí)現(xiàn)把推理變?yōu)檠菟愕南敕?，他把?shù)學(xué)引入了形式邏輯。其后，又經(jīng)多人努力，逐漸使得數(shù)理邏輯成為一門專門的學(xué)科。上個(gè)世紀(jì)30年代以后，數(shù)理邏輯進(jìn)入一個(gè)嶄新的發(fā)展階段，邏輯學(xué)不僅與數(shù)學(xué)結(jié)合，還與計(jì)算機(jī)科學(xué)等密切關(guān)聯(lián)。1931年Godel不完全性定理的提出，以及遞歸函數(shù)可計(jì)算性的引入，促使了1936年Turing機(jī)的產(chǎn)生，十年后，第一臺(tái)電子計(jì)算機(jī)問(wèn)世。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,10,數(shù)理邏輯與計(jì)算機(jī)

9、學(xué)、控制論、人工智能的相互滲透推動(dòng)了其自身的發(fā)展，模糊邏輯、概率邏輯、歸納邏輯、時(shí)態(tài)邏輯等都是目前比較熱門的研究領(lǐng)域。本章和下一章我們只從簡(jiǎn)單語(yǔ)義出發(fā)，對(duì)數(shù)理邏輯中的命題邏輯與謂詞邏輯等作一簡(jiǎn)單的、直接的、非形式化的介紹，不涉及公理系統(tǒng)。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,11,第一章 命題邏輯,1. 命題及其表示命題：是指具有確定真值的陳述句或者能夠判斷真假的陳述句。命題的真值：命題的判斷結(jié)果。真值只取兩個(gè)值： 真（1

10、或T）、假（0或F）。真命題：真值為真的命題。假命題：真值為假的命題。判斷命題的兩個(gè)步驟： 1、是否為陳述句？ 2、是否有確定的、唯一的真值？,1.1節(jié) 命題及聯(lián)結(jié)詞,2024/2/29,重慶郵電大學(xué) 理學(xué)院,12,注意: 感嘆句、祈使句、疑問(wèn)句都不是命題。 陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題。,,例1.1 下列句子中那些是命題？ （1）重慶是直轄市。（2）教師是人類靈魂的工程師。（3）4是

11、素?cái)?shù)。（4）1+1＝2。（5）2100年的春節(jié)是晴天。（6）火星上有生物。（7）請(qǐng)安靜?。?）今天天氣多好啊!（9）現(xiàn)在是幾點(diǎn)鐘?（10）我正在說(shuō)假話。（11）,2024/2/29,重慶郵電大學(xué) 理學(xué)院,13,（1）、（2）、（3）、（4）、（5）和（6）都是命題。其中 （1）、（2）、（4）是真命題，（3）是假命題。至于（5）和（6）真假值是確定的，只是現(xiàn)在無(wú)法知道，因此它是命題。（7）、（8）、（9）、

12、（10）、（11）都不是命題。原因在于（7）是祈使句，（8）是感嘆句，（9）是疑問(wèn)句，而（10）是悖論，即若(10)的真值為真，即“我正在說(shuō)假話”為真，也就是我說(shuō)的是假話，因此（10）又是錯(cuò)誤的；反之，若（10）的真值為假，即“我正在說(shuō)假話”為假，也就是我在說(shuō)真話，因此 （10）的真值應(yīng)為真。像（10）這樣既不為真又不為假的陳述句不是命題，這種陳述句稱為悖論。凡是悖論都不是命題。（11）中的x、y 的值不確定，某些x、y使為真，某些x

13、、y使為假，即的真假隨x、y的變化而變化。因此，的真假無(wú)法確定，所以不是命題。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,14,練習(xí) 判斷下列句子是否為命題？1. 100是自然數(shù)。2. 太陽(yáng)從西方升起。3. 北京是中國(guó)的首都。4. 重慶是中國(guó)最大的城市。5. 關(guān)門!6. 你去哪里?7. How do you do ?8. 凡石頭均可煉成金。9. x+3>910.皇馬中國(guó)之行沒(méi)有提升國(guó)家隊(duì)的水平。,2024/2

14、/29,重慶郵電大學(xué) 理學(xué)院,15,命題表示 在本書中，用大寫的英文字母P,Q,R,…P1,P2,P3，…，[1]，[2]等表示命題,用“1(或者T）”、“0（或者F）”分別表示真值的真、假。 如 P：太陽(yáng)從東邊升起。 Q：5是負(fù)數(shù)。 [1]：2008北京舉辦奧運(yùn)會(huì) 。 其真值依次為1、0、1。,2024/2/29,重慶郵電大學(xué) 理學(xué)院

15、,16,命題的分類簡(jiǎn)單/原子命題：不能再分解為更簡(jiǎn)單的陳述句的陳述句稱為原子命題。 復(fù)合命題：由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句。如：命題“如果2是素?cái)?shù)，則3也是素?cái)?shù)”通過(guò)“如果……，則……” 組合而成，是復(fù)合命題，而“2是素?cái)?shù)”和“3是素?cái)?shù)”是簡(jiǎn)單命題。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,17,2. 命題聯(lián)結(jié)詞,在日常語(yǔ)言中，一些簡(jiǎn)單的陳述句，可以通過(guò)某些聯(lián)結(jié)詞聯(lián)結(jié)起來(lái)，組成較為復(fù)雜的語(yǔ)句。 例

16、如可以說(shuō)：“如果下星期日是晴天，那么我就去春游?！边@里就是用：“如果……，那么……”把兩個(gè)陳述句“下星期日是晴天”和“我去春游”聯(lián)結(jié)起來(lái)組成的一個(gè)新復(fù)合命題。 在日常語(yǔ)言中還有許多聯(lián)結(jié)詞，如“不”、“并且”、“或者”、“當(dāng)且僅當(dāng)”，“只要……就……”，“除非……否則……”等都是聯(lián)結(jié)詞。 使用它們可以將一個(gè)命題加以否定或?qū)蓚€(gè)命題連接起來(lái)得到新的復(fù)合命題。 下面介紹常用的5種常用的聯(lián)結(jié)詞。,2024/2/29,重慶郵

17、電大學(xué) 理學(xué)院,18,（1）否定聯(lián)結(jié)詞 設(shè)P為命題，復(fù)合命題“非P”（或“P的否定”）稱為P的否定式，記作 ?P，符號(hào) ? 稱為否定聯(lián)結(jié)詞。 運(yùn)算規(guī)則：一元運(yùn)算,2024/2/29,重慶郵電大學(xué) 理學(xué)院,19,（2）合取聯(lián)結(jié)詞 設(shè)P,Q為二命題變?cè)瑥?fù)合命題“P并且Q”（或“P與Q”）稱為P與Q的合取式，記作P ∧ Q，符號(hào)∧稱為合取聯(lián)結(jié)詞。 運(yùn)算規(guī)則：二元運(yùn)算,2024/2/29,重慶郵

18、電大學(xué) 理學(xué)院,20,合取運(yùn)算特點(diǎn)： 只有參與運(yùn)算的二命題全為真時(shí)，運(yùn)算結(jié)果才為真，否則為假。自然語(yǔ)言中、“并且”、“既…又…”、“不但…而且…”、“雖然…但是”等都可以符號(hào)化為∧,例如：將下列命題符號(hào)化 (1) 北京不僅是中國(guó)的首都而且是一個(gè)故都。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,解：設(shè)P：北京是中國(guó)的首都；Q：北京是一個(gè)故都；則原命題符號(hào) 化為： P∧Q。,21,（2）小麗既聰明，又能干。

19、解：設(shè)P：小麗聰明；Q：小麗能干； 則原命題符號(hào)化為： P∧Q。（3）小剛聰明但不努力。 解：設(shè)P：小剛聰明；Q：小剛努力； 則原命題符號(hào)化為： P∧Q。（4）小剛和小明是同學(xué)。 解：這是一個(gè)原子命題，不能分解為更細(xì)的命題。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,22,（3）析取聯(lián)結(jié)詞 設(shè)P,Q為二個(gè)命題變?cè)瑥?fù)合命題“P或Q” 稱為P與Q的析取式， 記作P ∨ Q，符號(hào)∨稱為析取聯(lián)結(jié)詞

20、。 運(yùn)算規(guī)則：二元運(yùn)算。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,23,說(shuō)明：聯(lián)結(jié)詞析取∨的意義與日常所使用的“或”意思并不完全相同。在日常生活中，“或”實(shí)際上分為 “排斥或”和“可兼或”。 還有一種是描述模糊數(shù)據(jù)。本書將析取表示“可兼或”?！芭懦饣颉庇玫葍r(jià)的聯(lián)結(jié)詞代替。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,24,例：（1）今天晚上我在家看電視或聽音樂(lè)。解：設(shè)P：今天晚上我在家看電視； Q：今天晚

21、上我在家聽音樂(lè)； 則原命題符號(hào)化為： P ∨ Q 。（可兼或） （2）從重慶到北京的T10次列車是中午1點(diǎn)或1點(diǎn)半開。解：該命題中的“或”不是“可兼或”，不能用聯(lián)結(jié)詞析取。我們用 一種等價(jià)形式來(lái)代替。 設(shè)P：重慶到北京的T10次列車是中午1點(diǎn)開； Q：重慶到北京的T10次列車是中午1點(diǎn)半開； 則原命題符號(hào)化為： (P∧?Q) ∨(?P∧Q). （排斥或）,202

22、4/2/29,重慶郵電大學(xué) 理學(xué)院,25,（3）小剛是山東或山西人。 解：設(shè)P：小剛是山東人；Q：小剛是山西人； 則原命題符號(hào)化為： (P∧?Q) ∨(?P∧Q).（排斥或）（4）小剛是有20或30歲。 解：這是一個(gè)原子命題，這里的“或”表示一個(gè)模糊數(shù)據(jù)。 在遇到含有“或”的命題符號(hào)化時(shí)，要分清它是“可兼或”、“排 斥或”、還是表示模糊數(shù)的“或”，析取聯(lián)結(jié)詞表示“可兼

23、或”。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,26,（4）單條件聯(lián)結(jié)詞 設(shè)P,Q為二個(gè)命題變?cè)?復(fù)合命題“如果P,則Q” 稱為P與Q的單條件（蘊(yùn)涵式），記作P?Q，并稱P為單條件的前件，Q為單條件的后件，符號(hào)?稱為單條件結(jié)詞。 運(yùn)算規(guī)則：二元運(yùn)算 與自然語(yǔ)言的不同：前件與后件可以沒(méi)有任何內(nèi)在聯(lián)系！,2024/2/29,重慶郵電大學(xué) 理學(xué)院,27,說(shuō)明：P?Q 的邏輯關(guān)系：Q 為 P 的必要條

24、件 “如果 P，則 Q ” 的不同表述法很多： “若P，就Q” “只要P，就Q” “P僅當(dāng)Q” “只有Q才P” “除非Q,才P”或“除非Q, 否則非P” ...等等。當(dāng)P為假時(shí)，無(wú)論Q是什么，P?Q均為真。常出現(xiàn)的錯(cuò)誤：不分充分與必要條件！！,2024/2/29,重慶郵電大學(xué) 理學(xué)院,28,例如：（1） 如果天下雨，那么我們?cè)谑覂?nèi)活動(dòng)。

25、 解：設(shè)P：天下雨；Q：我們?cè)谑覂?nèi)活動(dòng)； 原命題符號(hào)化為：P?Q 。 （2）只要天下雨，我們就在室內(nèi)活動(dòng)。 解：設(shè)P：天下雨；Q：我們?cè)谑覂?nèi)活動(dòng)； 原命題符號(hào)化為：P?Q 。 （3）因?yàn)樘煜掠辏晕覀冊(cè)谑覂?nèi)活動(dòng)。 解：設(shè)P：天下雨；Q：我們?cè)谑覂?nèi)活動(dòng)； 原

26、命題符號(hào)化為： P?Q 。 在實(shí)際的語(yǔ)言中，很多聯(lián)結(jié)詞可以轉(zhuǎn)化為用單條件，但是要注意前件和后件的關(guān)系。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,29,（4）只有天下雨，我們才在室內(nèi)活動(dòng)。 解：設(shè)P：天下雨；Q：我們?cè)谑覂?nèi)活動(dòng)； 原命題符號(hào)化為：Q?P 。（5） 僅當(dāng)天下雨，我們?cè)谑覂?nèi)活動(dòng)。 解：設(shè)P：天下雨；Q：我們?cè)谑覂?nèi)活動(dòng)； 原命題符號(hào)化為：

27、Q?P 。（6） 除非天下雨，否則我們不在室內(nèi)活動(dòng)。 解：設(shè)P：天下雨；Q：我們?cè)谑覂?nèi)活動(dòng)； 原命題符號(hào)化為：Q?P ，或者? P? ? Q 。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,30,（5）雙條件聯(lián)結(jié)詞 設(shè)P,Q為二個(gè)命題變?cè)?，?fù)合命題“P當(dāng)且僅當(dāng)Q” 稱為P與Q的雙條件，記作P ?Q， 符號(hào)?稱為雙條件聯(lián)結(jié)詞。 說(shuō)明：(1) P?Q 的邏輯關(guān)系:P與Q互為充分

28、必要條件 (2) P?Q為真當(dāng)且僅當(dāng)P與Q同真或同假。 運(yùn)算規(guī)則：二元運(yùn)算。,2024/2/29,重慶郵電大學(xué) 理學(xué)院,31,例如：（1） 2+2＝4 當(dāng)且僅當(dāng) 3+3＝6。 解：設(shè)P： 2 + 2 ＝ 4 ；Q： 3 + 3 ＝ 6.； 原命題符號(hào)化為：P ? Q 。 （2）1+1=2當(dāng)且太陽(yáng)從東邊升起。