離散數學

本書介紹了離散數學基礎知識和應用方法。全書共分4篇。第1篇為數理邏輯，其中包括命題邏輯、一階謂詞邏輯。第2篇為集合論，其中包括集合的基本概念、二元關係、函數、自然數、基數、序數。第3篇為代數系統，其中包括代數系統的基本概念、幾個重要的代數系統：半群、群、環、域、格與布爾代數。第4篇為圖論，其中包括圖的基本概念、圖的連通性、歐拉圖與漢密爾頓圖、樹、平面圖、圖的著色、圖的矩陣表示等。

第1篇　數理邏輯

第1章　命題邏輯

1-1　命題與聯結詞

1-1-1　命題

1-1-2　聯結詞

1-2　命題公式及其賦值

1-2-1 命題公式

1-2-2　命題公式的真值表

1-2-3　語句的形式化

1-3　重言式

1-3-1 重言式

1-3-2　等價式

1-3-3　蘊含式

1-4　對偶與範式

1-4-1　對偶

1-4-2　範式

1-4-3　聯結詞完備集

1-5　推理理論

1-6　小結

習題

第2章　謂詞邏輯

2-1　謂詞邏輯基本概念

2-1-1　個體和謂詞

2-1-2　量詞

2-1-3　謂詞公式及語句的符號化

2-2　謂詞邏輯永真式

2-2-1　公式的解釋

2-2-2　謂詞演算永真式

2-3　謂詞公式的前束範式

2-4　謂詞演算推理理論

2-5　消解原理

2-5-1　化為子句集

徠2-5-2　消解推理規則

2-5-3　含有變數的消解式

2-5-4　消解反演求解過程

2-3 小結

習題

第2篇　集合論

第3章 集合

3-1　集合的概念與表示

3-1-1　集合及其元素

3-1-2　集合的表示

3-1-3　集合之間的關係

3-2　集合的基本運算

3-2-1　集合的交、並、補及對稱差

3-2-2　證明集合相等的方法

3-3　集合的笛卡兒積運算

3-4　有限集合中元素的計數

3-4-1　鴿籠原理

3-4-2　容斥原理

3-5　集合的覆蓋與劃分

3-6　小結

習題

第4章 關係

4-1　n元組與關係

4-1-1 關係的基本概念

4-1-2　二元關係的表示

4-2　二元關係的性質與類型

4-2-1 自反性與反自反性

4-2-2　對稱性與反對稱性

4-2-3 傳遞性

4-2-4　關係性質的等價描述

4-2-5　關係性質的證明

4-3　關係的運算

4-3-1 關係的基本運算

4-3-2　關係的複合運算

4-3-3　關係的逆運算

4-3-4　利用關係矩陣求解複合關係

……

第5章　函數

第3篇　代數系統

第6章　代數系統

第7章　群、環、域

第8章　格與布爾代數

第4章　圖論

第9章　圖

第10章　特殊圖

附錄A　初等數論

附錄B　計數原理

參考文獻