離散數學

《離散數學》作者參考了若干國內外相關教材，並結合十多年的教學體會，編寫了本教材。全書主要特色如下：《離散數學》較全面地介紹了離散數學的各知識點。在講解的過程中盡量結合實例，避免抽象和枯燥的論述不僅強調基本內容、基本概念及其實際背景，以及各概念間相互關係，而且強化了證明的思想和方法的介紹，以培養學生的數學思維能力在內容組成方面，圖論部分通過圖模型的引入來加強解決實際問題的能力，代數結構部分則強調了在計算機系統和編碼技術中有著重要作用的本原元和本原多項式的內容，而數理邏輯則是通過泛代數引入，和代教部分一氣呵成總之，《離散數學》結構合理、內容豐富，講解由淺入深，體現知識點的連貫性、完整性，有利於讀者得到離散數學思維方法的訓練，為從事計算學科的學習和研究提供必要的理論儲備。《離散數學》的作者長期從事離散教學的課程教學，具有較豐富的教學經驗，並在演演算法理論，密碼與信息安全和資訊理論與 編碼等研究領域取得許多有影響的成果，發表了較高學術水平的論文。計算學科的重要數學基礎，教學實踐的多年系統總結，知識體系的完美提煉組合。

這是復旦大學離散數學教材。全書介紹離散數學中的5個部分，即集合論、組合數學、圖論、代數結構和數理邏輯的初步知識。在內容組織上，不但介紹基本內容、基本概念及其實際背景、各概念間的相互關係，而且強化了證明的思想和方法。《離散數學》可作為高等院校計算機科學與技術、軟體工程等專業的離散數學課程教材，也可以作為該課程的教學參考書。

趙一鳴 復旦大學畢業后留校，任計算機科學與技術專業、軟體工程專業教師。現任復旦大學軟體學院副院長，中國人工智慧學會離散數學專業委員會副主任，全國高等學校計算機教育研究會常務理事，中國計算機學會教育專業委員會常委。多年來在密碼和信息安全方面從事教學和研究工作。曾獲教育部科技進步二等獎和國家級教學成果二等獎。長期主講離散數學，信息安全原理等課程。

Ⅰ集合論概述

第1章 集合的基本概念 2

1.1 集合的表示 2

1.2 集合的子集 3

1.3 笛卡兒積 4

1.4 集合的運算 5

1.5 羅素悖論 7

習題 9

第2章 關係 11

2.1 二元關係 11

2.2 關係的性質 13

2.3 關係的運算 14

2.4 關係資料庫的一個實例 17

2.5 關係的閉包 20

2.6 等價關係與劃分 23

2.7 次序關係 27

習題 29

第3章 函數 34

3.1 函數的基本概念 34

3.2 逆函數與複合函數 35

3.3 集合的特徵函數 37

習題 38

第4章 無限集 41

4.1 集合的遞歸定義與自然數集合 41

4.2 基數 46

4.3 可列集與不可列集 48

4.4 基數的比較 51

習題 54

Ⅱ 組合數學初步

第5章 鴿籠原理 58

5.1 鴿籠原理的簡單形式 58

5.2 鴿籠原理的加強形式 59

習題 61

第6章 排列與組合 62

6.1 基本計數原理 62

6.2 集合的排列 62

6.3 集合元素的組合 64

6.4 多重集的排列和組合 67

6.5 容斥原理 69

習題 71

第7章 生成函數與遞推關係 74

7.1 冪級數型生成函數 74

7.2 指數型生成函數 77

7.3 遞推關係 78