離散數學（微課版）

本书编写组成员现为电子科技大学信息与软件工程学院和计算机科学与工程学院“离散数学”课程组教师，长期从事与离散数学密切相关的教学、科研、应用开发和社会服务等方面的工作，主要研究领域包括人工智能、大数据处理与应用、云计算等。

编写组成员长期致力于“离散数学”课程的教学与研究，具有丰富的“离散数学”教学研究经验，取得了丰硕的教学研究成果。2005年“离散数学”课程被评为国家级精品课程；2008年“离散数学”课程被评为国家双语示范课程；2009年“离散数学”教学团队被评为四川省省级教学团队；2012年“离散数学”被评为教育部精品资源共享课程；2018年“离散数学”课程被评为国家级精品在线开放课程；2020年编写组成员完成的“以学生为中心”的离散数学课程综合改革与实践”获电子科技大学教学成果二等奖。多人次获得电子科技大学优秀主讲教师、专业核心课程骨干教师等称号。

编写组成员先后编写了国家“十一五”规划教材《离散数学及应用（2019年第3版，2013年第2版，2007年第1版）》，《离散数学实验与习题解析》（2007年，高等教育出版社），《离散数学》（2004年，机械工业出版社），《离散数学及其应用》（1997年，电子工业出版社），编写《离散数学及其应用习题解析》（1997年，电子工业出版社），《计算复杂性》（2005年，机械工业出版社），《并行算法及其应用》（2005年，机械工业出版社）；自主研发了集作业发布、撰写、上传、批改及数据统计为一体“离散数学”教学辅助系统，实现了考核方式的科学化和标准化。

第 1章集合論

本章思維導圖1

歷史人物2

11集合的基本概念2

111集合的表示3

112集合與集合的關系4

113幾個特殊集合6

12集合的運算7

13無限集9

131可數集9

132不可數集11

14與集合相關的應用12

141集合的電腦表示12

142計數問題13

15習題14

第 2章命題邏輯

本章思維導圖16

歷史人物17

21命題與命題聯結詞17

211命題17

212命題聯結詞18

213自然語言的命題符號化23

22命題公式、解釋與真值表25

221命題公式25

222命題公式的解釋與真值表26

223命題公式的基本等價定律29

23公式的標準型——範式33

231命題聯結詞的完備集33

232析取範式和合取範式34

233主析取範式和主合取範式36

24命題邏輯的推理理論43

241推理的基本概念43

242推理有效性的判別方法44

25命題邏輯的應用51

251命題聯結詞的應用51

252命題公式的應用53

253範式的應用55

254命題邏輯推理的應用56

26習題58

第3章謂詞邏輯

本章思維導圖64

歷史人物65

31自然語言的謂詞符號化65

311謂詞65

312量詞67

32謂詞公式與解釋70

321謂詞公式70

322自由變元和約束變元71

323謂詞公式的解釋73

324謂詞公式的基本等價定律77

33謂詞公式的標準型——前束範式79

331前束範式80

332Skolem範式*80

34謂詞邏輯的推理理論81

341推理規則與推理定律81

342推理有效性的判別方法84

35謂詞邏輯的應用87

36習題89

第4章二元關系

本章思維導圖94

歷史人物95

41二元關系及其表示96

411序偶和笛卡兒積96

412關系的定義98

413關系的表示法99

42關系的運算104

421關系的復合運算104

422關系的逆運算107

423關系的冪運算109

43關系的性質111

431關系性質的定義111

432關系性質的判定定理117

433關系性質的保守性119

44關系的閉包120

45關系的應用124

451二元關系及表示的應用124

452關系運算的應用126

46習題127

第5章特殊關系

本章思維導圖131

歷史人物132

51相容關系132

511相容關系的定義132

512集合的覆蓋134

52等價關系134

521等價關系的定義135

522集合的劃分137

523等價類與商集137

524等價關系與劃分14053次序關系142

531擬序關系143

532偏序關系144

533全序關系149

534良序關系150

54函數151

541函數的基本概念151

542函數的運算157

543置換函數159

55特殊關系的應用160

551等價關系的應用160

552次序關系的應用161

553函數的應用162

554置換函數的應用165

56習題166

第6章圖

本章思維導圖171

歷史人物172

61圖的基本概念172

611圖的定義172

612圖的表示173

613圖的操作175

614鄰接點與鄰接邊176

615圖的分類178

616子圖與補圖180

62握手定理183

63圖的同構185

64通路與迴路187

641通路與迴路的概念187

642通路與迴路的計算188

643可達與距離191

644無向賦權圖的最短通路194

65圖的連通性196

651無向圖的連通性196

652有向圖的連通性198

66圖的應用200

661網絡的結構200

662渡河問題201

663均分問題202

67習題202

第7章特殊圖

本章思維導圖206

歷史人物207

71樹207

711樹的基本概念及性質208

712生成樹及算法210

72根樹216

721根樹的定義與分類216

722根樹的遍歷220

723最優樹與哈夫曼算法222

73歐拉圖224

731歐拉圖的引入與定義224

732歐拉圖的判定226

74哈密頓圖228

741哈密頓圖的引入與定義228

742哈密頓圖的判定230

75偶圖232

751偶圖的定義232

752偶圖的判定233

753匹配234

76平面圖236

761平面圖的定義236

762平面圖的簡單判定方法——觀察法237

763歐拉公式238

764庫拉托夫斯基定理241

77特殊圖的應用242

771無向樹的應用242

772根樹的應用242

773歐拉圖的應用247

774哈密頓圖的應用250

775偶圖的應用253

776平面圖的應用253

78習題253

第8章代數系統

本章思維導圖258

歷史人物259

81代數系統259

811代數運算259

812代數系統與子代數261

82代數系統的基本運算性質263

821二元運算律263

822二元運算的特殊元266

83同態與同構272

831同態與同構的定義273

832同態的性質275

84代數系統的應用276

841代數系統的電腦表示276

842數據庫與關系代數277

85習題277

第9章群、環、域

本章思維導圖280

歷史人物281

91群的基本概念281

911群的定義及基本性質281

912元素的階285

913子群287

914群的同態和同構290

92特殊群292

921循環群292

922置換群295

93陪集與拉格朗日定理300

931陪集300

932拉格朗日定理303

94正規子群與商群304

941正規子群304

942商群306

95環和域308

951環和域的定義308

952子環、理想和商環310

953環的同態和同構312

96與群、環、域相關的應用313

961計數問題313

962多項式編碼315

97習題317

第 10章格與布爾代數

本章思維導圖320

歷史人物321

101格的定義和性質321

1011格的定義321

1012格的性質325

102子格與格同態326

1021子格和理想326

1022格同態327

103特殊格328

1031分配格與模格328

1032有界格與有補格330

104布爾代數332

105格與布爾代數的應用333

1051格與樹形圖結構333

1052布爾函數及其表示334

106習題335

參考文獻337