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