本教材以離散數學課程重要知識點為紐帶，夯實程序設計思路，拓展數據結構中數據和關繫的表示方法，提高學生從實例計算到類計算的應用能力。使學生充分掌握“問題-形式化-自動化（計算機化）”方法，結合近期新知識分類方法和圖論的相關研究成果拓展課程涉及的相關原理與方法，為培養創新研究型人纔打下良好的基礎。本教材為全國高等學校計算機教育研究會2018 年度課題。

●目錄 第1章命題演算基礎11.1命題和聯結詞11.1.1命題11.1.2聯結詞21.1.3合式公式61.1.4命題邏輯的應用61.2真假性91.2.1解釋91.2.2等價公式101.2.3聯結詞的完備集121.2.4對偶式和內否式131.3範式及其應用151.3.1範式151.3.2主範式171.3.3範式的應用201.4典型例題21習題23第2章命題演算的推理理論262.1命題演算的公理繫統262.1.1公理繫統的組成部分272.1.2公理繫統的推理過程282.2若干重要的導出規則302.2.1分離規則的討論302.2.2公理和定理的導出規則302.3命題演算的假設推理繫統322.3.1假設推理繫統的組成322.3.2假設推理繫統的推理過程33〖1〗離 散 數 學 〖1〗目錄 2.3.3額外假設推理法352.4命題演算的歸結推理法372.4.1歸結證明過程382.4.2歸結證明示例392.5典型例題40習題43第3章謂詞演算基礎453.1謂詞和個體453.1.1個體453.1.2謂詞453.2函數項和量詞483.2.1函數項483.2.2量詞493.3和513.3.1自由出現和約束出現513.3.2改名和代入513.4永真性和可滿足性533.4.1真假性533.4.2同真假性、永真性和可滿足性553.4.3範式583.5專享性量詞和摹狀詞593.5.1專享性量詞593.5.2摹狀詞603.6典型例題61習題62第4章謂詞演算的推理理論654.1謂詞演算的永真推理繫統654.1.1公理繫統的組成部分654.1.2公理繫統的推理過程674.2謂詞演算的假設推理繫統684.2.1假設推理繫統的組成及證明方法684.2.2定理的假設推導過程694.3謂詞演算的歸結推理繫統714.3.1置換724.3.2歸結反演繫統724.3.3霍恩子句邏輯程序754.4Prolog簡介784.5典型例題80習題82第5章遞歸函數論855.1數論函數和數論謂詞855.1.1數論函數855.1.2數論謂詞和特征函數865.2函數的構造885.2.1迭置法885.2.2算子法905.2.3原始遞歸函數915.3典型例題92習題92第6章集合946.1集合的基本概念946.1.1集合的定義946.1.2集合的表示956.1.3集合的包含關繫966.1.4集合的特點976.1.5多重集976.2集合的基本運算986.2.1集合的並、交、差986.2.2集合的對稱差996.2.3文氏圖1006.2.4集合的冪集合1016.2.5多個集合的並與交1016.3全集和補集1026.3.1全集和補集的定義1026.3.2基本運算定理1036.3.3集合的計算機表示1046.4自然數與自然數集1056.4.1後繼1056.4.2自然數和自然數集1056.4.3皮亞諾公理假設1066.4.4自然數集的性質1076.4.5集合的遞歸定義與遞歸子程序1086.5包含與排斥原理1106.6典型例題112習題113第7章關繫1187.1集合的笛卡兒積集1187.1.1組1187.1.2笛卡兒積集1187.1.3組、n個集合的笛卡兒積集1197關繫的基本概念1207.2關繫1207.2關繫的表示1207.2關繫與數據結構1227.2關繫的運算1227關繫及其運算1257.3關繫1257.3關繫的運算1257關繫的性質1287.4.1自反性、反自反性、對稱性、反對稱性、傳遞性和反傳遞性1287.4關繫性質的判定定理1307關繫的閉包運算1327.5.1自反閉包、對稱閉包和傳遞閉包1327.5.2閉包的判定定理1327.6等價關繫和集合的劃分1377.6.1等價關繫和等價類1377.6.2商集合1387.6.3集合的劃分1387.7偏序關繫和格1417.7.1偏序關繫和偏序集1417.7.2哈斯圖1427.7.3鏈、反鏈、全序集1427.7.1437.7.5上界、下界、最小上界和優選下界1437.7.6格1447.7.7拓撲排序1457.8粗糙集概論1477.8.1知識與知識分類1477.8.2集合近似與粗糙集概念1507.9典型例題151習題152第8章函數與集合的勢1578.1函數的基本概念1578.1.1函數(映射)的定義1578.1.2函數的性質1598.2函數的復合和逆函數1608.2.1函數的復合1608.2.2左可逆函數、右可逆函數和逆函數1628.3無限集1648.3.1勢1648.3.2有限集和無限集1668.3.3可數無限集和不可數無限集1668.4集合勢大小的比較1688.4.1集合勢的大小1688.4.2伯恩斯坦定理1698.5鴿巢原理1698.6典型例題171習題172第9章圖論1759.1圖的基本概念1759.1.1有向圖和無向圖1769.1.2圖的同構、子圖和補圖1779.1.3頂點的度1789.2圖中的通路、圖的連通性和圖的矩陣表示1799.2.1通路、回路和連通性1799.2.2圖的矩陣表示1819.3帶權圖與帶權圖中的最短通路1849.4歐拉圖1879.5哈密頓圖1909.6二部圖1949.7平面圖與平面圖的著色1979.7.1平面圖1979.7.2平面圖的著色2009.8典型例題203習題204第10章樹和有序樹20910.1樹的基本概念20910.2連通圖的生成樹和帶權連通圖的最小生成樹21110.3有序樹21410.3.1根樹21410.3.2根樹的應用21610.4前綴碼和很優2分樹21810.4.1前綴碼21810.4.2很優2分樹22010.4.3赫夫曼編碼22210.5典型例題224習題226第11章群和環22911.1代數運算的基本概念22911.1.1代數運算22911.1.2交換律、結合律23011.1運算23111.2代數繫統和半群23211.2.1代數繫統23211.2.2同態映射和同構映射23311.2.3半群與含幺半群23511.3群的基本概念23611.323611.3.2群的定義23711.3.3群的同態、同構24011.3.4無限群、有限群、交的階24211.4群的幾個等價定義24411.5變換群和置換群24511.5.1變換群24611.5.2置換群24711.6循環群25011.7子群25211.7.1子群的定義25211.7.2子群的判定定理25211.8子群的陪集25411.8.1按子群劃分的剩餘類25411.8.2右陪集25411.8.3左陪集25611.8.4拉格朗日定理25711.9正規子群和商群25911.9.1正規子群25911.9.2商群26011.10環和域26211.10.1環、子環與理想26311.10.2交換環和整環26411.10.3除環和域26411.11典型例題265習題268第12章格與布爾代數27112.1格定義的代數繫統27112.2格的代數定義27312.2.1格的代數定義27312.2.2子格27512.2.3格的同態和同構27512.3一些特殊的格27612.3.1分配格27612.3.2布爾格和布爾代數27812.4有限布爾代數的專享性27912.4.1原子27912.4.2有限布爾代素的表達27912.4.3布爾代數的同構28012.5布爾表達式和布爾函數28212.5.1布爾表達式28212.5.2布爾函數28312.6典型例題285習題286參考文獻288

本書是全國高等學校計算機教育研究會支持的立項教材，較全面地介紹了離散數學的基本理論及基本方法。本書以離散數學課程重要知識點為紐帶，夯實程序設計思路，拓展數據和關繫的表示方法，強化從實例計算到模型計算和問題—形式化—自動化（計算機化）等方法，旨在為後續的科學研究打下良好的基礎。全書由命題演算基礎、命題演算的推理理論、謂詞演算基礎、謂詞演算的推理理論、遞歸函數論、集合、關繫、函數與集合的勢、圖論、樹和有序樹、群和環、格與布爾代數共12章組成。本書可作為高等院校計算機科學與技術及相關專業離散數學課程教材，也可作為教師、研究生或軟件技術人員的參考書。

    第5章遞歸函數論遞歸函數是數論函數，以自然數為研究對像，定義域和值域均為自然數。它為能行可計算函數找出各種理論上的、嚴密的類比物，即某個函數能否用若干可計算函數通過某種已有的算法（如迭置或算子）在有限步內遞歸產生，若能，說明該函數為可計算函數，否則為不可計算函數，因此，遞歸函數論又稱為可計算性理論。下面舉幾個例子說明函數的可計算性。例5.1： g(n)=n表示取自然數n的平方根的整數部分。將n依次與12，22，32，…作比較，總可求得g(n)的值，所以g(n)是可計算的。例5.2： g(n)=0π的展開式中有n個連續的91否則因π的展開式是一個無窮序列，要計算上述函數可能是一個無限過程，故函數g(n)為不可計算函數。5.1數論函數和數論謂詞〖1〗5.1.1數論函數定義5.1： 數論函數是指以自然數集為定義等

離散數學是計算機科學與技術重要的理論基礎課程，它不僅是計算機科學的核心課程，而且已成為電子信息類專業的熱門選修課。離散數學與計算機科學有著十分密切的關繫。無論是數字計算機雛形的圖靈機，還是數字電路的布爾代數，以及程序設計語言、關繫數據庫、知識表示、人工智能等領域均離不開離散數學；同時兩者的相互滲透推動了離散數學的發展。因此，學好離散數學對計算機科學與理論的研究有著重要的作用。離散數學以研究離散量的結構和相互間的關繫為主要目標，旨在介紹離散數學各個分支的基本概念、基本理論和基本方法。本書以離散數學課程重要知識點為紐帶，夯實程序設計思路，拓展數據和關繫的表示方法，強化從實例計算到模型計算的應用能力，使讀者充分掌握問題—形式化—自動化（計算機化）方法，為後續的學習和科學研究打下良好的基礎。本書基於全國高等學校計算機教育研究會的教材規範對離散數學教學內容進行編著，強化了離散數學的相關概念及等