離散數(shù)學教程-北大社

內(nèi)容簡介本書共分五編。第一編為集合論，其中包括集合的基本概念、二元關系、函數(shù)、自然數(shù)、基數(shù)、序數(shù)。第二編為圖論，其中包括圖的基本概念、圖的連通性、歐拉圖與哈密頓圖、樹、平面圖、圖的著色、圖的矩陣表示、覆蓋集、獨立集、匹配、帶權圖及其應用。第三編為代數(shù)結構，其中包括代數(shù)系統(tǒng)的基本概念、幾個重要的代數(shù)系統(tǒng)：半群、群、環(huán)、域、格與布爾代數(shù)。第四編為組合數(shù)學，其中包括組合存在性、組合計數(shù)、組合設計與編碼以及組合最優(yōu)化。第五編為數(shù)理邏輯，其中包括命題邏輯、一階謂詞邏輯、Herbrand定理和直覺邏輯。本書體系嚴謹、內(nèi)容豐富、配有大量的例題和習題，并與計算機科學的理論與實踐密切結合。本書不僅適用于計算機及相關專業(yè)的本科生或研究生，也可供計算機專業(yè)的科技人員使用或參考。目錄第一編集合論第一章集合(1)1.1預備知識(1)1.2集合的概念及集合之間的關系(7)1.3集合的運算(10)1.4基本的集合恒等式(13)1.5集合列的極限(17)習題一(20)第二章二元關系(23)2.1有序?qū)εc卡氏積(23)2.2二元關系(26)2.3關系矩陣和關系圖(32)2.4關系的性質(zhì)(34)2.5二元關系的冪運算(37)2.6關系的閉包(39)2.7等價關系和劃分(45)2.8序關系(49)習題二(53)第三章函數(shù)(58)3.1函數(shù)的基本概念(58)3.2函數(shù)的性質(zhì)(59)3.3函數(shù)的合成(62)3.4反函數(shù)(64)習題三(68)第四章自然數(shù)(70)4.1自然數(shù)的定義(70)4.2傳遞集合(74)4.3自然數(shù)的運算(76)4.4N上的序關系(78)習題四(80)第五章基數(shù)(勢)(81)5.1集合的等勢(81)5.2有窮集合與無窮集合(83)5.3基數(shù)(84)5.4基數(shù)的比較(85)5.5基數(shù)運算(89)習題五(93)第六章序數(shù)(95)6.1關于序關系的進一步討論(95)6.2超限遞歸定理(97)6.3序數(shù)(99)6.4關于基數(shù)的進一步討論(105)習題六(105)第二編圖論第七章圖(107)7.1圖的基本概念(107)7.2通路與回路(119)7.3無向圖的連通性(121)7.4無向圖的連通度(123)7.5有向圖的連通性(129)習題七(130)第八章歐拉圖與哈密頓圖(132)8.1歐拉圖(132)8.2哈密頓圖(137)習題八(142)第九章樹(144)9.1無向樹的定義及性質(zhì)(144)9.2生成樹(146)9.3環(huán)路空間(149)9.4斷集空間(151)9.5根樹(153)習題九(154)第十章圖的矩陣表示(156)10.1關聯(lián)矩陣(156)10.2鄰接矩陣與相鄰矩陣(159)習題十(163)第十一章平面圖(165)11.1平面圖的基本概念(165)11.2歐拉公式(168)11.3平面圖的判斷(170)11.4平面圖的對偶圖(172)11.5外平面圖(175)11.6平面圖與哈密頓圖(177)習題十一(179)第十二章圖的著色(180)12.1點著色(180)12.2色多項式(181)12.3地圖的著色與平面圖的點著色(185)12.4邊著色(187)習題十二(189)第十三章支配集、覆蓋集、獨立集與匹配(190)13.1支配集、點覆蓋集、點獨立集(190)13.2邊覆蓋集與匹配(193)13.3二部圖中的匹配(198)習題十三(199)第十四章帶權圖及其應用(201)14.1最短路徑問題(201)14.2關鍵路徑問題(204)14.3中國郵遞員問題(206)14.4最小生成樹(208)14.5最優(yōu)樹(213)14.6貨郎擔問題(216)習題十四(220)第三編代數(shù)結構第十五章代數(shù)系統(tǒng)(222)15.1二元運算及其性質(zhì)(222)15.2代數(shù)系統(tǒng)、子代數(shù)和積代數(shù)(227)15.3代數(shù)系統(tǒng)的同態(tài)與同構(230)15.4同余關系和商代數(shù)(233)15.5Σ代數(shù)(236)習題十五(237)第十六章半群與獨異點(240)16.1半群與獨異點(240)16.2有窮自動機(242)習題十六(247)第十七章群(249)17.1群的定義和性質(zhì)(249)17.2子群(253)17.3循環(huán)群(255)17.4變換群和置換群(257)17.5群的分解(263)17.6正規(guī)子群和商群(269)17.7群的同態(tài)與同構(272)17.8群的直積(278)習題十七(281)第十八章環(huán)與域(285)18.1環(huán)的定義和性質(zhì)(285)18.2子環(huán)、理想、商環(huán)和環(huán)同態(tài)(289)18.3有限域上的多項式環(huán)(294)習題十八(296)第十九章格與布爾代數(shù)(299)19.1格的定義和性質(zhì)(299)19.2子格、格同態(tài)和格的直積(303)19.3模格、分配格和有補格(307)19.4布爾代數(shù)(311)習題十九(318)第四編組合數(shù)學第二十章組合存在性定理(322)20.1鴿巢原理和Ramsey定理(322)20.2相異代表系(331)習題二十(335)第二十一章基本的計數(shù)公式(337)21.1兩個計數(shù)原則(337)21.2排列和組合(338)21.3二項式定理與組合恒等式…(343)21.4多項式定理(347)習題二十一(349)第二十二章組合計數(shù)方法(352)22.1遞推方程的公式解法(352)22.2遞推方程的其他解法(361)22.3生成函數(shù)的定義和性質(zhì)(370)22.4生成函數(shù)與組合計數(shù)(375)22.5指數(shù)生成函數(shù)與多重集的排列問題(384)22.6Catalan數(shù)與Stirling數(shù)(388)習題二十二(394)第二十三章組合計數(shù)定理(398)23.1包含排斥原理(398)23.2對稱篩公式及應用(403)23.3Burnside引理(410)23.4Polya定理(414)習題二十三(420)第二十四章組合設計與編碼(422)24.1拉丁方(422)24.2t設計(427)24.3編碼(436)24.4編碼與設計(446)習題二十四(449)第二十五章組合最優(yōu)化問題(450)25.1組合優(yōu)化問題的一般概念…(450)25.2網(wǎng)絡的最大流問題(452)習題二十五(457)第五編數(shù)理邏輯第二十六章命題邏輯(458)26.1形式系統(tǒng)(458)26.2命題和聯(lián)結詞(461)26.3命題形式和真值表(464)26.4聯(lián)結詞的完全集(468)26.5推理形式(471)26.6命題演算的自然推理形式系統(tǒng)N(473)26.7命題演算形式系統(tǒng)P(486)26.8N與P的等價性(494)26.9賦值(496)26.10可靠性、和諧性與完備性…(505)習題二十六(507)第二十七章一階謂詞演算(511)27.1一階謂詞演算的符號化(511)27.2一階語言(515)27.3一階謂詞演算的自然推演形式系統(tǒng)NL(519)27.4一階謂詞演算的形式系統(tǒng)KL(530)27.5NL與KL的等價性(534)27.6KL的解釋與賦值(536)27.7KL的可靠性與和諧性(547)27.8KL的完全性(551)習題二十七(558)第二十八章消解原理(562)28.1命題公式的消解(562)28.2Herbrand定理(567)28.3代換與合一代換(572)28.4一階謂詞公式的消解(576)習題二十八(581)第二十九章直覺主義邏輯(583)29.1直覺主義邏輯的直觀介紹(583)29.2直覺主義的一階謂詞演算的自然推演形式系統(tǒng)(585)29.3直覺主義一階謂詞演算形式系統(tǒng)IKL(594)29.4直覺主義邏輯的克里普克(Kripke)語義(597)29.5直覺主義邏輯的完備性(602)習題二十九(607)附錄1第一編與第二編符號注釋與術語索引(608)附錄2第三編與第四編符號注釋與術語索引(614)附錄3第五編符號注釋與術語索引(620)參考書目和文獻(624)05668本書共分4大部分，數(shù)理邏輯部分包括命題邏輯的基本概念、等值演算、范式與推理理論，一階邏輯的基本概念、前束范式以及推理理論。集合論部分包括集合的基本概念與運算，二元關系的性質(zhì)與運算、等價關系與偏序關系，函數(shù)及其性質(zhì)，復合函數(shù)與反函數(shù)等。代數(shù)結構部分包括二元運算及代數(shù)系統(tǒng)，半群、獨異點、群、環(huán)與域、格與布爾代數(shù)等。圖論部分包括圖的基本概念和矩陣表示，樹的概念、性質(zhì)及應用，二部圖，歐拉圖，哈密爾頓圖，平面圖，圖的著色等。本書作為北京市高等教育計算機及應用專業(yè)自學考試的指定教材，體系嚴謹，選材精煉，深淺適度，并配有大量的例題，習題解答。本書既適合自學，也可以作為普通高校計算機及先關專業(yè)離散數(shù)學的入門教材或參考書。第一部分數(shù)理邏輯命題邏輯命題與聯(lián)結詞命題公式與賦值等值演算析取范式與合取范式命題邏輯的推理理論例題分析習題一一階邏輯2.1一階邏輯的基本概念2.2一階邏輯公式及解釋2.3一階邏輯等值式與前束范式2.4一階邏輯推理理論2.5例題分析習題二第二部分集合論集合的基本概念和運算3.1集合的基本概念3.2集合的基本運算3.3集合恒等式3.4有窮集合的計數(shù)3.5例題分析習題三二元關系和函數(shù)4.1集合的笛卡兒積和二元關系4.2關系的運算4.3關系的性質(zhì)4.4關系的閉包4.5等價關系和偏序關系4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復合和反函數(shù)4.8例題分析習題四第三部分代數(shù)結構代數(shù)系統(tǒng)的一般概念5.1二元運算極其性質(zhì)5.2代數(shù)系統(tǒng)極其子代數(shù)和積代數(shù)5.3代數(shù)系統(tǒng)的同態(tài)與同構5.4例題分析習題五幾個典型的代數(shù)系統(tǒng)6.1半數(shù)與獨異點6.2群與子群6.3循環(huán)群與置換群6.4群的直積與同態(tài)