離散數(shù)學及其應用DiscreteMathematics

1、2022-3-7重慶郵電大學 理學院 12022-3-7重慶郵電大學 理學院 離散數(shù)學類課程地位： 計算機相關(guān)專業(yè)核心課程 信息類部分專業(yè)必修課程 其它部分專業(yè)的選修課程離散數(shù)學的后繼課程： 數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、 算法分析與設計、人工智能、 數(shù)據(jù)庫、C+語言，22022-3-7重慶郵電大學 理學院 學習該課程的目的： 一方面，它給后繼課，如數(shù)據(jù)結(jié)構(gòu)、編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫原理、軟件工程與方法學、計算機網(wǎng)絡、程序設計等，提供必要的數(shù)學基礎（邏輯、關(guān)系、代數(shù)系統(tǒng)、圖論等）； 另一方面，通過學習離散數(shù)學，可以培養(yǎng)和提高自己的抽象思維和邏輯推理能力，為以后的軟、硬件學習和研究開發(fā)工作，打下堅實的理

2、論基礎。32022-3-7重慶郵電大學 理學院 教學要求： 通過該課程的學習，學生應當了解并掌握計算機科學中普遍采用的離散數(shù)學中的一些基本概念、基本思想、基本方法。自學要求： 通過反復看書及做課后習題，來加深對該課程中的一些基本概念的理解，逐步提高自己的抽象思維和邏輯推理能力。42022-3-7重慶郵電大學 理學院 離散數(shù)學課程的學習方法： 強調(diào)：邏輯推理、抽象思維； 注重：概念、方法與應用離散數(shù)學的學習要領(lǐng)： 概念（正確）熟練掌握大量的基本概念（多、散） 判斷（準確）根據(jù)概念對屬性進行判斷（巧） 推理（可靠）根據(jù)多個結(jié)論推出新的論斷（難）5課程主要內(nèi)容 第一部分 數(shù)理邏輯：命題邏輯、謂詞邏輯

3、。 第二部分 集合論：集合、關(guān)系、函數(shù)。 第三部分 代數(shù)系統(tǒng)：二元運算、代數(shù)系統(tǒng)、半群、群。 第四部分 圖論：圖的基本概念、 路與圈、最短路、歐拉圖、 哈密爾頓圖、樹、平面圖。2022-3-7重慶郵電大學 理學院 6離散數(shù)學與計算機的關(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)為基礎。第四部分 圖論 數(shù)據(jù)結(jié)構(gòu)

4、、操作系統(tǒng)、編譯原理計算機網(wǎng)絡原理的基礎。 2022-3-7重慶郵電大學 理學院 7課程教學學時與作業(yè)課程學時： 64學時：主要講述第一部分數(shù)理邏輯、第二部分集合與關(guān)系，第三部分代數(shù)系統(tǒng)（講到群的定義及其性質(zhì)）；第四部分圖論。 48學時：主要講述第一部分數(shù)理邏輯（主要講命題邏輯）、第二部分集合與關(guān)系；第四部分圖論。成績構(gòu)成： 30%的平時成績+70%期末考試成績。 2022-3-7重慶郵電大學 理學院 8第一章 命題邏輯 數(shù)理邏輯是研究推理（即研究人類思維的形式結(jié)構(gòu)和規(guī)律）的科學，起源于17世紀，它采用數(shù)學符號化的方法，因此也稱為符號邏輯。 從廣義上講，數(shù)理邏輯包括四論、兩演算即集合論、模型論

5、、遞歸論、證明論和命題邏輯演算、謂詞邏輯演算，但現(xiàn)在提到數(shù)理邏輯，一般是指命題邏輯和謂詞邏輯。本書也只研究這兩個邏輯演算。2022-3-7重慶郵電大學 理學院 9 數(shù)理邏輯的創(chuàng)始人是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)生，十年后，第一臺電子計算機問世。2022-3-7重慶郵電大學 理學院 10 數(shù)理邏

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

7、聯(lián)結(jié)詞2022-3-7重慶郵電大學 理學院 12注意: 感嘆句、祈使句、疑問句都不是命題。 陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題。例1.1 下列句子中那些是命題？ （1）重慶是直轄市。（2）教師是人類靈魂的工程師。（3）4是素數(shù)。（4）1+12。（5）2100年的春節(jié)是晴天。（6）火星上有生物。（7）請安靜！（8）今天天氣多好啊!（9）現(xiàn)在是幾點鐘?（10）我正在說假話。（11）3x y 2022-3-7重慶郵電大學 理學院 13 （1）、（2）、（3）、（4）、（5）和（6）都是命題。其中 （1）、（2）、（4）是真命題，（3）是假命題。 至于（5）和（6）真假值是確定的，只是現(xiàn)

8、在無法知道，因此它是命題。 （7）、（8）、（9）、（10）、（11）都不是命題。原因在于（7）是祈使句，（8）是感嘆句，（9）是疑問句，而（10）是悖論，即若(10)的真值為真，即“我正在說假話”為真，也就是我說的是假話，因此（10）又是錯誤的；反之，若（10）的真值為假，即“我正在說假話”為假，也就是我在說真話，因此 （10）的真值應為真。 像（10）這樣既不為真又不為假的陳述句不是命題，這種陳述句稱為悖論。凡是悖論都不是命題。（11）中的x、y 的值不確定，某些x、y使為真，某些x、y使為假，即的真假隨x、y的變化而變化。因此，的真假無法確定，所以不是命題。 2022-3-7重慶郵電大學

9、 理學院 14練習 判斷下列句子是否為命題？1. 100是自然數(shù)。2. 太陽從西方升起。3. 北京是中國的首都。4. 重慶是中國最大的城市。5. 關(guān)門!6. 你去哪里?7. How do you do ?8. 凡石頭均可煉成金。9. x+3910.皇馬中國之行沒有提升國家隊的水平。2022-3-7重慶郵電大學 理學院 15命題表示 在本書中，用大寫的英文字母P,Q,R,P1,P2,P3，1，2等表示命題,用“1(或者T）”、“0（或者F）”分別表示真值的真、假。 如 P：太陽從東邊升起。 Q：5是負數(shù)。 1：2008北京舉辦奧運會 。 其真值依次為1、0、1。2022-3-7重慶郵電大學 理學

10、院 16命題的分類簡單/原子命題：不能再分解為更簡單的陳述句的陳述句稱為原子命題。 復合命題：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的陳述句。如：命題“如果2是素數(shù)，則3也是素數(shù)”通過“如果，則” 組合而成，是復合命題，而“2是素數(shù)”和“3是素數(shù)”是簡單命題。2022-3-7重慶郵電大學 理學院 172. 命題聯(lián)結(jié)詞 在日常語言中，一些簡單的陳述句，可以通過某些聯(lián)結(jié)詞聯(lián)結(jié)起來，組成較為復雜的語句。 例如可以說：“如果下星期日是晴天，那么我就去春游。”這里就是用：“如果，那么”把兩個陳述句“下星期日是晴天”和“我去春游”聯(lián)結(jié)起來組成的一個新復合命題。 在日常語言中還有許多聯(lián)結(jié)詞，如“不”、“并且”、“或者

11、”、“當且僅當”，“只要就”，“除非否則”等都是聯(lián)結(jié)詞。 使用它們可以將一個命題加以否定或?qū)蓚€命題連接起來得到新的復合命題。 下面介紹常用的5種常用的聯(lián)結(jié)詞。2022-3-7重慶郵電大學 理學院 18（1）否定聯(lián)結(jié)詞 設P為命題，復合命題“非P”（或“P的否定”）稱為P的否定式，記作 P，符號 稱為否定聯(lián)結(jié)詞。 運算規(guī)則：一元運算PP10012022-3-7重慶郵電大學 理學院 19（2）合取聯(lián)結(jié)詞 設P,Q為二命題變元，復合命題“P并且Q”（或“P與Q”）稱為P與Q的合取式，記作P Q，符號稱為合取聯(lián)結(jié)詞。 運算規(guī)則：二元運算PQP Q000 0 10 10 0 1112022-3-7重慶

12、郵電大學 理學院 20合取運算特點： 只有參與運算的二命題全為真時，運算結(jié)果才為真，否則為假。自然語言中、“并且”、“既又”、“不但而且”、“雖然但是”等都可以符號化為 例如：將下列命題符號化 (1) 北京不僅是中國的首都而且是一個故都。2022-3-7重慶郵電大學 理學院 解：設P：北京是中國的首都；Q：北京是一個故都；則原命題符號 化為： PQ。 21（2）小麗既聰明，又能干。 解：設P：小麗聰明；Q：小麗能干； 則原命題符號化為： PQ。（3）小剛聰明但不努力。 解：設P：小剛聰明；Q：小剛努力； 則原命題符號化為： PQ。（4）小剛和小明是同學。 解：這是一個原子命題，不能分解為更細的

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

14、家聽音樂； 則原命題符號化為： P Q 。（可兼或） （2）從重慶到北京的T10次列車是中午1點或1點半開。解：該命題中的“或”不是“可兼或”，不能用聯(lián)結(jié)詞析取。我們用 一種等價形式來代替。 設P：重慶到北京的T10次列車是中午1點開； Q：重慶到北京的T10次列車是中午1點半開； 則原命題符號化為： (PQ) (PQ). （排斥或）2022-3-7重慶郵電大學 理學院 25（3）小剛是山東或山西人。 解：設P：小剛是山東人；Q：小剛是山西人； 則原命題符號化為： (PQ) (PQ).（排斥或）（4）小剛是有20或30歲。 解：這是一個原子命題，這里的“或”表示一個模糊數(shù)據(jù)。 在遇到含有“或”

15、的命題符號化時，要分清它是“可兼或”、“排 斥或”、還是表示模糊數(shù)的“或”，析取聯(lián)結(jié)詞表示“可兼或”。 2022-3-7重慶郵電大學 理學院 26（4）單條件聯(lián)結(jié)詞 設P,Q為二個命題變元,復合命題“如果P,則Q” 稱為P與Q的單條件（蘊涵式），記作PQ，并稱P為單條件的前件，Q為單條件的后件，符號稱為單條件結(jié)詞。 運算規(guī)則：二元運算 與自然語言的不同：前件與后件可以沒有任何內(nèi)在聯(lián)系！PQP Q0010111001112022-3-7重慶郵電大學 理學院 27說明：PQ 的邏輯關(guān)系：Q 為 P 的必要條件 “如果 P，則 Q ” 的不同表述法很多： “若P，就Q” “只要P，就Q” “P僅當Q

16、” “只有Q才P” “除非Q,才P”或“除非Q, 否則非P” .等等。當P為假時，無論Q是什么，PQ均為真。常出現(xiàn)的錯誤：不分充分與必要條件！2022-3-7重慶郵電大學 理學院 28例如：（1） 如果天下雨，那么我們在室內(nèi)活動。 解：設P：天下雨；Q：我們在室內(nèi)活動； 原命題符號化為：PQ 。 （2）只要天下雨，我們就在室內(nèi)活動。 解：設P：天下雨；Q：我們在室內(nèi)活動； 原命題符號化為：PQ 。 （3）因為天下雨，所以我們在室內(nèi)活動。 解：設P：天下雨；Q：我們在室內(nèi)活動； 原命題符號化為： PQ 。 在實際的語言中，很多聯(lián)結(jié)詞可以轉(zhuǎn)化為用單條件，但是要注意前件和后件的關(guān)系。2022-3-7重慶郵電大學 理學院 29（4）只有天下雨，我們才在室內(nèi)活動。 解：設P：天下雨；Q：我們在室內(nèi)活動； 原命題符號化為：QP 。（5） 僅當天下雨，我們在室內(nèi)活動。 解：設P：天下雨；Q：我們在室內(nèi)活動； 原命題符號化為：QP 。（6） 除非天下雨，否則我們不在室內(nèi)活動。 解：設P：天下雨；Q：我們在室內(nèi)活動； 原命題符號化為：QP ，或者 P Q 。2022-3-7重慶郵電大學 理學院 30（5）雙條件聯(lián)結(jié)詞 設P,Q為二個命題變元，復合命題“P當且僅當Q” 稱為P與Q的雙