離散數學（微課版 第2版）

陳誌奎，大連理工大學教授，從事人工智能算法與大數據計算等方面的研究。主講“離散數學”課程，該課程為遼寧省一流本科課程、2023 年國家本科教學工程入庫項目。主編教材《離散數學》《移動技術與應用》《XBRL 技術及其在財務報告中的應用》等，其中《離散數學》入選“十四五”普通高等教育本科國家級規劃教材。

【章名目錄】 第 一篇　數理邏輯 第 1章　命題邏輯 第 2章　謂詞邏輯 第二篇　集合與關系理論 第3章　集合論 第4章　二元關系 第5章　函數 第三篇　代數系統 第6章　代數系統基本概念及性質 第7章　群與環 第8章　格與布爾代數 第四篇　圖論 第9章　圖的基本概念及其矩陣表示 第 10章　特殊圖 第 11章　樹 參考文獻 【詳細目錄】 第 一篇　數理邏輯 第 1章　命題邏輯　002 1.1　命題和邏輯聯結詞　002 1.1.1　命題的概念　003 1.1.2　邏輯聯結詞　003 1.2　合式公式與真值表　007 1.2.1　合式公式　007 1.2.2　真值表　008 1.3　永真式、等價式及代入規則和替換規則　009 1.3.1　永真式　009 1.3.2　等價式　010 1.3.3　代入規則和替換規則　011 1.4　對偶式與蘊涵式　012 1.4.1　對偶式　012 1.4.2　蘊涵式　013 1.5　範式和判定問題　014 1.5.1　析取範式和合取範式　014 1.5.2　主析取範式和主合取範式　016 1.6　命題演算的推理理論　019 1.7　應用與拓展　022 1.7.1　命題邏輯與SAT：計算機的“智力遊戲”　022 1.7.2　谷歌OR-Tools的CP-SAT：解決現實難題的“萬能工匠”　022 習題　023 第 2章　謂詞邏輯　027 2.1　基本概念和表示　027 2.1.1　個體、謂詞和謂詞形式　028 2.1.2　量詞　028 2.1.3　謂詞邏輯的合式公式　030 2.1.4　自由變元和約束變元　030 2.2　謂詞邏輯的翻譯與解釋　031 2.2.1　謂詞邏輯的翻譯　031 2.2.2　謂詞公式的解釋　032 2.3　謂詞邏輯的等價式與永真蘊涵式　033 2.4　謂詞邏輯中的推論理論　035 2.4.1　推理規則　035 2.4.2　推理實例　036 2.5　謂詞邏輯中的範式　039 2.5.1　前束範式　039 2.5.2　斯柯林範式　040 2.6　應用與拓展　041 2.6.1　謂詞邏輯與知識推理：讓計算機學會“舉一反三”　041 2.6.2　Prolog：用“邏輯”寫程序，而不是用“步驟”　042 習題　042 第二篇　集合與關系理論 第3章　集合論　046 3.1　集合的概念及其表示　047 3.2　集合的運算及恒等式　049 3.3　有窮集的計數和包含排斥原理　054 3.4　應用與拓展　057 3.4.1　PointNet與Deep Sets：讓計算機“看懂”三維世界的集合　057 3.4.2　DETR：用集合匹配讓計算機“一眼看清”畫面中所有目標　058 習題　059 第4章　二元關系　062 4.1　多重序元與笛卡兒積　062 4.2　關系的基本概念　064 4.3　關系的運算　065 4.4　關系的性質　070 4.5　關系的表示　072 4.6　關系的閉包運算　077 4.7　特殊關系　080 4.7.1　集合的劃分和覆蓋　080 4.7.2　等價關系　082 4.7.3　相容關系　085 4.7.4　次序關系　088 4.7.5　偏序集合與哈斯圖　091 4.8　應用與拓展　093 4.8.1　關系型數據庫：用“表格”管理世界的秩序　093 4.8.2　圖神經網絡中的關系傳播：當“關系”可以被多層傳遞　094 習題　094 第5章　函數　100 5.1　函數的基本概念和性質　100 5.2　函數的合成和合成函數的性質　103 5.3　特殊函數　105 5.4　反函數　107 5.5　特征函數　109 5.6　基數　111 5.7　應用與拓展　114 5.7.1　不可解問題：有些事，計算機永遠做不到　114 5.7.2　Transformer中的函數復合：人工智能大模型背後的數學骨架　114 習題　115 第三篇　代數系統 第6章　代數系統基本概念及性質　119 6.1　代數系統的一般概念　120 6.1.1　二元運算　120 6.1.2　代數系統　121 6.2　代數系統的基本性質　122 6.3　同態與同構　128 6.3.1　同態　128 6.3.2　同構　130 6.3.3　同態與同構的性質　134 6.4　同余關系　134 6.5　商代數　135 6.6　積代數　136 6.7　應用與拓展　138 6.7.1　同構與遷移學習：從數學結構到“舉一反三”的人工智能　138 6.7.2　BERT模型微調：讓通用語言模型“適配”你的任務　138 習題　139 第7章　群與環　141 7.1　半群　141 7.2　群　144 7.2.1　群的概念　144 7.2.2　群的性質　145 7.3　子群與群的陪集分解　148 7.3.1　子群　148 7.3.2　子群的判定　149 7.3.3　子群的性質　149 7.3.4　子群的陪集分解　150 7.3.5　拉格朗日定理　152 7.4　循環群與置換群　153 7.4.1　循環群　154 7.4.2　置換群　154 7.5　群的同態與同構　155 7.6　環與域　156 7.6.1　環的概念與性質　156 7.6.2　域的概念　157 7.7　應用與拓展　158 7.7.1　群與糾錯編碼：讓計算機在“宇宙射線”下依然可靠　158 7.7.2　群與網絡安全：谷歌Gboard如何學習輸入習慣且保護隱私　159 習題　160 第8章　格與布爾代數　162 8.1　格的定義與性質　163 8.2　分配格、有補格與布爾代數　165 8.3　應用與拓展　166 8.3.1　格與數字電路：從數學公式到芯片的“邏輯骨架”　166 8.3.2　格與靜態分析：不運行程序，也能找出漏洞　166 習題　167 第四篇　圖論 第9章　圖的基本概念及其矩陣表示　170 9.1　圖的基本概念　171 9.1.1　圖的定義及相關概念　171 9.1.2　節點的度　173 9.2　子圖和圖的運算　175 9.2.1　子圖和補圖　175 9.2.2　圖的運算　176 9.3　路徑、回路和連通性　178 9.3.1　路徑和回路　178 9.3.2　圖的連通性　180 9.4　圖的矩陣表示　183 9.4.1　鄰接矩陣　184 9.4.2　可達性矩陣　187 9.4.3　關聯矩陣　190 9.5　應用與拓展　192 9.5.1　知識圖譜：讓機器真正“理解”世界的語義網絡　192 9.5.2　圖神經網絡與消息傳遞：當深度學習“遇上”圖結構　193 習題　193 第 10章　特殊圖　198 10.1　歐拉圖　198 10.2　哈密頓圖　200 10.3　二部圖及匹配　202 10.3.1　二部圖的概念及性質　203 10.3.2　二部圖匹配　204 10.4　平面圖　205 10.4.1　平面圖的概念及性質　206 10.4.2　多邊形圖、對偶圖及平面圖著色　208 10.5　網絡　211 10.5.1　網絡的基本概念　211 10.5.2　網絡流　212 10.5.3　網絡最大流求解　213 10.5.4　開關網絡　220 10.6　應用與拓展　227 10.6.1　中國郵遞員問題：如何讓郵遞員不走冤枉路　227 10.6.2　最短路徑問題：導航軟件每天都在用的經典算法　227 習題　228 第 11章　樹　232 11.1　樹與生成樹　232 11.1.1　樹及其性質　232 11.1.2　生成樹與最小生成樹　234 11.2　有向樹及其應用　236 11.2.1　有向樹　236 11.2.2　m叉樹　236 11.2.3　有序樹　238 11.2.4　二叉樹的遍歷　240 11.2.5　搜索樹　242 11.3　應用與拓展　244 11.3.1　MST在計算機視覺圖像分割中的應用　244 11.3.2　搜索樹在強化學習與博弈智能中的應用　244 習題　245 參考文獻　248