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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、 解：設P：天下雨；Q：我們在室內(nèi)活動； 原命題符號化為：P?Q 。 （2）只要天下雨，我們就在室內(nèi)活動。 解：設P：天下雨；Q：我們在室內(nèi)活動； 原命題符號化為：P?Q 。 （3）因為天下雨，所以我們在室內(nèi)活動。 解：設P：天下雨；Q：我們在室內(nèi)活動； 原

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

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

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