計算機科學的數學基礎

第一部分 形式語言與自動機理論
　第一章 語言與正規(guī)語言
　1.1 符號、符號串及其運算
　 1.2 文法與語言的形式定義
　1.3 正規(guī)表達式
　 1.4 正規(guī)文法與正規(guī)式
　第二章 有限自動機
　2.1 有限自動機的定義與構造
　 2.2 確定的有限自動機（DFA）
　2.3 不確定的有限自動機（NFA）
　 2.4 NFA的確定化
　2.5 DFA的最小化
　 2.6 正規(guī)集與有限自動機的等價性
　2.7 雙向有限自動機
　 2.8 具有輸出的有限自動機
　第三章 正規(guī)集的性質
　3.1 正規(guī)集的泵作用引理
　 3.2 正規(guī)集的封閉性質
　3.3 正規(guī)集的一些判定算法
　第四章 上下文無關語言
　4.1 上下文無關文法
　 4.2 上下文無關文法的簡化
　4.3 Chomsky范式
　 4.4 Greibach范式
　4.5 先天歧義的上下文無關語言的存在
　第五章 下推自動機
　5.1 非形式的描述
　 5.2 下推自動機的定義
　5.3 下推自動機和上下文無關語言
　第六章 上下文無關語言的性質
　6.1 對CFL的泵作用引理
　 6.2 上下文無關語言的封閉性質
　6.3 CFL的某些判定算法
第二部分 可計算理論
　第七章 圖靈機
　7.1 圖靈機模型
　 7.2 可計算語言和函數
　7.3 圖靈機的構造技術
　 7.4 圖靈機的修改
　7.5 Church假設
　 7.6 圖靈機作為枚舉器
　7.7 等價于基本模型的受限圖靈機
　第八章 短語結構語言與上下文有關語言
　8.1 短語結構語言與圖靈機
　8.2 上下文有關語言與線性有界自動機
　 8.3 上下文無關語言與遞歸集合
　 8.4 上下文有關語言類的性質
　第九章 可判定性
　9.1 遞歸語言和遞歸可枚舉語言的性質
　 9.2 通用圖靈機和一個不可判定問題
　9.3 RICE定理和某些其他的不可判定問題
　 9.4 POST對應問題的不可判定性
　9.5 圖靈機的有效計算和無效計算
　 9.6 Greibach定理
　9.7 圣人計算
　第十章 可計算理論
　10.1 原始遞歸函數
　 10.2 遞歸函數與部分遞歸函數
　10.3 圖靈機與部分遞歸函數的等價性
第三部分 邏輯學
　第十一章 命題邏輯與一階邏輯
　11.1 命題邏輯的自然推理
　 11.2 命題演算的公理系統(tǒng)
　11.3 PC的可靠性與一致性
　 11.4 PC的完備性
　11.5 一階邏輯
　第十二章 直覺主義邏輯
　12.1 直覺主義的一些基本觀點
　 12.2 一階直覺主義邏輯的形式化
　12.3 完全性定理
　第十三章 模態(tài)邏輯
　13.1 模態(tài)詞“必然”與“可能”
　 13.2 模態(tài)命題邏輯系統(tǒng)
　13.3 模態(tài)狹義謂詞邏輯
　第十四章 非單調邏輯
　14.1 單調性與非單調性
　 14.2 非單調邏輯
　14.3 缺省推理
　 14.4 非單調邏輯系統(tǒng)
　14.5 限定理論
　第十五章 模糊邏輯
　15.1 邏輯與不確定性的研究
　 15.2 模糊集
　15.3 模糊邏輯的代數模型——De-Morgan代數
　 15.4 模糊變量與模糊邏輯公式（函數）
　15.5 模糊邏輯真值表與范式
　 15.6 模糊邏輯公式的極小化
　 15.7 似然推理
　15.8 模糊歸納推理
　第十六章 多值邏輯
　16.1 三值邏輯
　　16.2 多值命題邏輯
　 16.3 三值邏輯代數系統(tǒng)
　16.4 n值邏輯代數系統(tǒng)
　 16.5 閾值邏輯
第四部分 程序設計理論
　第十七章 程序的指稱語義
　 17.1 把程序看作函數
　17.2 序列程序結構的程序函數
　 17.3 分支程序結構的程序函數
　17.4 循環(huán)程序結構的程序函數
　 17.5 循環(huán)程序的正確性證明
　第十八章 程序的公理語義
　 18.1 程序的公理語義
　18.2 霍爾公理系統(tǒng)
　 18.3 最弱前置謂詞與程序的公理語義
　第十九章 程序的形式推導
　19.1 程序形式推導的基本思想
　 19.2 選擇語句的設計
　19.3 循環(huán)程序的設計
　 19.4 不變式與界函數的構造
　第二十章 遞歸程序理論
　20.1 遞歸的基本概念
　 20.2 遞歸數據結構
　20.3 遞歸程序的證明
習題
參考文獻