離散數學

離散數學作為一門理論兼實際應用的綜合性學科，既具有嚴謹的理論基礎，又具備應用學科的特點，它是計算機科學和其他應用科學的基礎理論課.

本教材以《中國計算機科學與技術學科教程(2002)》中制定的關於“離散數學”的知識結構和內容體系編寫.全書分為數理邏輯、集合與關係、代數系統與布爾代數4篇，共9章.內容包括：命題邏輯，一階謂詞邏輯，集合及其運算，二元關係，函數，代數結構，格與布爾代數，無向圖和有向圖，基本圖類的算法等. ^[1] 

離散數學作為一門理論兼應用的綜合性學科，既具有嚴謹的理論基礎，又具備應用學科的特點，它是計算機科學和其他應用科學的基礎理論課.讀者通過本課程學習，能培養和訓練抽象思維能力和嚴格的邏輯推理的能力，並瞭解離散數學在計算機學科和日常生活中的作用，為以後處理離散信息以及用計算機處理大量的日常事務和科研項目，從事計算機科學和應用打下堅實基礎.特別是對那些從事計算機科學與理論研究的高層次計算機人員來説，這更是一門必不可少的基礎理論工具.

離散數學的主要內容和作用包括：① 數理邏輯：含命題邏輯、謂詞邏輯和數理邏輯在計算機科學中的應用三部分.其中命題邏輯有：命題、聯結詞、真值表、公式與公式解釋、公式等價和藴涵關係、範式、命題演算的方法；謂詞邏輯有：謂詞、量詞、謂詞公式等價與藴涵關係，SKOLEM範式、謂詞演算的推理規則與推理方法；數理邏輯在計算機科學中的應用有：命題邏輯在計算機科學中的應用，謂詞邏輯與數據子語言，謂詞邏輯與邏輯程序設計語言，並對以後學習奠定邏輯基礎.② 集合論：集合的基本概念與各種表示、集合的運算與性質、無限集合、笛卡兒積、序列、整除、容斥原理和鴿籠原理.二元關係、特殊關係及關係在計算機科學中的應用：關係及其表示、關係運算與性質、等價關係、偏序關係、全序關係、良序關係、函數及其特殊函數的定義與性質、關係與函數的證明方法、關係在關係數據庫中的應用、關係代數與數據子語言、關係閉包與計算機程序、劃分在計算機中的應用.③ 代數系統：一般代數系統和子代數系統的基本概念及其基本性質、代數系統的同態與同構、同餘關係與商代數、半羣與羣的基本概念與性質、特殊羣、陪集與拉格朗日定理、商集、環和域的基本概念與判斷方法、格的定義與基本性質、偏序關係與代數系統的關係、特殊格、布爾代數與布爾表達式、有限自動機、計數問題、糾錯碼和開關電路.④ 圖論：圖的基本概念及其各種表示、圖的通路與連通性、圖的矩陣表示、特殊圖（歐拉圖、哈密頓圖、平面圖、二分圖、樹）的定義和判別方法以及圖論在計算機科學中的應用.

本教材以《中國計算機科學與技術學科教程(2002)》中制定的關於離散數學的知識結構和內容體系編寫，內容設計增加了幫助理解理論的習題分析，對於培養學生的抽象思維和邏輯表達能力，提高發現問題、分析問題、解決問題的能力起着引導和幫助作用.教材編寫力求體系嚴謹、選材適當、針對性強、有利教學，在素材組織上更加註重在計算機科學技術中的應用.注重語言的通俗性和符號的統一性、規範性、簡潔性.注重邏輯思維能力的訓練,將數理邏輯教學內容放在第一部分，在集合與關係、代數系統、圖與樹的教學內容中始終貫穿數理邏輯的推理思想，以鍛鍊學生嚴謹的邏輯思維能力. ^[1] 

前言

第1篇　數理邏輯

第1－1章 命題邏輯

第1－2章 一階謂詞邏輯

第2篇　集合與關係

第2－1章 集合及其運算

第2－2章 二元關係

第2－3章 函數

第3篇　代數系統篇

第3－1章 代數結構

第3－2章 格與布爾代數

第4篇　圖論

第4－1章 無向圖和有向圖

第4－2章 基本圖類和算法

附錄　各章知識結識 ^[1]