模型論及其在計(jì)算機(jī)科學(xué)中的應(yīng)用

內(nèi)容概要

　　《模型論及其在計(jì)算機(jī)科學(xué)中的應(yīng)用》是為了給數(shù)學(xué)系和計(jì)算機(jī)科學(xué)系的本科生和研究生開設(shè)模型論課而寫的，它的主要內(nèi)容是模型論的基本原理和它在計(jì)算機(jī)科學(xué)中的計(jì)算復(fù)雜度理論和機(jī)器證明等方面的應(yīng)用。本書共二十章節(jié)，內(nèi)容包括模型論的發(fā)生與發(fā)展、關(guān)于集合論的準(zhǔn)備知識(shí)、模型論的形式語言、模型的基本性質(zhì)、緊致性定理與LST定理等。本書給供相關(guān)人員參考閱讀。

書籍目錄

第一章　模型論的發(fā)生與發(fā)展
　1.1　模型論在科學(xué)發(fā)展中的地位
　1.2　模型論的發(fā)展概述
　1.3　模型論與計(jì)算機(jī)科學(xué)的關(guān)系
　1.4　模型論研究的方法與特點(diǎn)
　1.5　語法與語義
第二章　關(guān)于集合論的準(zhǔn)備知識(shí)
　2.1　完整的集合論公理系統(tǒng)
　2.2　有限集與無限集
　2.3　集合之間元素個(gè)數(shù)的比較
　2.4　選擇公理和可良序化定理
　2.5　基數(shù)的定義和性質(zhì)
　2.6　序數(shù)定義和超限歸納過程
　2.7　可數(shù)集的性質(zhì)
　2.8　序數(shù)，基數(shù)的運(yùn)算
　2.9　實(shí)數(shù)的不可數(shù)性
　2.10　連續(xù)統(tǒng)假設(shè)簡介
　練習(xí)題
第三章　模型論的形式語言
　3.1　形式邏輯中的命題演算
　3.2　一階邏輯簡介
　3.3　命題演算的模型論的補(bǔ)充性質(zhì)
　3.4　模型論的形式語言
　3.5　模型論的式子和它們的構(gòu)成
　3.6　模型論的式子推演
　練習(xí)題
第四章　模型的基本性質(zhì)
　4.1　形式語言的解釋與模型
　4.2　模型的同構(gòu)，同態(tài)，子模型，擴(kuò)張，膨脹，歸約
　4.3　式子的代入與驗(yàn)證
　4.4　理論，公理，定理和模型的理論
　4.5　語言和理論的模型數(shù)
　4.6　模型的同構(gòu)嵌入
　4.7　模型的初等等價(jià)
　練習(xí)題
第五章　緊致性定理與LST定理
　5.1　從理論構(gòu)造模型
　5.2　緊致性定理
　5.3　緊致性定理的應(yīng)用
　5.4　模型的圖像
　5.5　模型論的內(nèi)語言與外語言
　練習(xí)題
第六章　初等子模型與模型完全的理論
　6.1　初等子模型
　6.2　初等圖像和它的應(yīng)用
　6.3　強(qiáng)LST定理
　6.4　完全的理論
　6.5　模型完全的理論
　練習(xí)題
第七章　初等鏈的構(gòu)造與應(yīng)用
　7.1　模型的鏈的構(gòu)造
　7.2　模型的鏈的并
　7.3　初等鏈定理
　7.4　式子集的實(shí)現(xiàn)與省略
　練習(xí)題
第八章　保持性定理
　8.1　研究保持性定理的意義和方法
　8.2　子模型的保持性定理
　8.3　模型鏈的并保持性定理
　8.4　同態(tài)象的保持性定理
　8.5　保持性的部分表
　練習(xí)題
第九章　可數(shù)語言的幾種特殊模型
　9.1　素模型與原子模型
　9.2　齊次模型
　9.3　可數(shù)飽和模型
　練習(xí)題
第十章　一些具體的模型和邏輯性質(zhì)
　10.1　模型與語言的關(guān)系
　10.2　偏序、全序集模型
　10.3　布爾代數(shù)模型
　10.4　群，環(huán)，域系列的模型
　10.5　其他系列的模型
　練習(xí)題
第十一章　量詞消去法和可判定的理論
　11.1　量詞消去法的重要性
　11.2　量詞消去法的一般步驟
　11.3　無端稠密有序集的量詞消去法
　11.4　整數(shù)加運(yùn)算的量詞消去法
　11.5　代數(shù)模型的模型數(shù)
　11.6　布爾代數(shù)模型的模型數(shù)
　11.7　W-范疇的可數(shù)完全的理論
　11.8　范疇性研究介紹
　練習(xí)題
第十二章　不可判定的理論
　12.1　自然數(shù)理論系統(tǒng)□□的不可判定性
　12.2　有理數(shù)加法、乘法系統(tǒng)的不可判定性
　12.3　自由群T-理論的不可判定性
　練習(xí)題
第十三章　無原子布爾代數(shù)理論的計(jì)算復(fù)雜度
　13.1　一個(gè)系統(tǒng)的定理判定的計(jì)算復(fù)雜度
　13.2　無原子布爾代數(shù)的公理系統(tǒng)
　13.3　量詞消去法的作用與過程
　13.4　無原子布爾代數(shù)的性質(zhì)
　13.5　無原子布爾代數(shù)的量詞消去法
　13.6　無原子布爾代數(shù)的計(jì)算復(fù)雜度
第十四章　可換群定理判定的計(jì)算復(fù)雜度
　14.1　可換群的理論和結(jié)構(gòu)
　14.2　模型的Ehrenfeucht博弈
　14.3　群Dp博弈的準(zhǔn)備工作
　14.4　群Dp的Ferrente和：Rackoff博弈
　14.5　群Dp的計(jì)算復(fù)雜度上界
　14.6　可換群理論的計(jì)算復(fù)雜度
第十五章　對(duì)數(shù)論模型的研究
　15.1　廣義中國剩余定理
　15.2　□的w-和模型
　15.3　孿生準(zhǔn)素?cái)?shù)問題
　15.4　對(duì)Goldbach猜想和孿生素?cái)?shù)問題的研究
第十六章　有限模型論的保持性定理
　16.1　模型的初等性質(zhì)
　16.2　保持性定理
第十七章　集合論的可數(shù)模型
　17.1　實(shí)數(shù)的相對(duì)性
　17.2　集合論的可數(shù)模型
　17.3　ZFG模型中元素的不可區(qū)分群組
　17.4　無限小數(shù)的不確定性
　17.5　康托爾實(shí)數(shù)的局限性
　17.6　計(jì)算機(jī)科學(xué)與無限概念的關(guān)系
第十八章　非良基集合論模型悖論
　18.1　集合論的新悖論
　18.2　良基性定理與非良基的集合論模型
　18.3　非良基的集合論模型的精確化
　18.4　非良基集合論模型中的良序集與類
　18.5　結(jié)論
第十九章　可數(shù)多個(gè)單元關(guān)系的研究
　19.1　可數(shù)多個(gè)獨(dú)立單元關(guān)系系統(tǒng)
　19.2　可數(shù)多個(gè)單元關(guān)系的完全理論
第二十章　多項(xiàng)式復(fù)雜度的計(jì)算問題
　20.1　一些引理
　20.2　二次模方程的解
參考文獻(xiàn)
索引

章節(jié)摘錄

版權(quán)頁：   第十三章無原子布爾代數(shù)理論的計(jì)算復(fù)雜度 13.1 一個(gè)系統(tǒng)的定理判定的計(jì)算復(fù)雜度 在這一章里我們要介紹在理論判定的計(jì)算復(fù)雜度的研究中應(yīng)用模型論的方法來解決問題。在計(jì)算機(jī)的理論研究中常常會(huì)遇到一個(gè)系統(tǒng)的定理判定的計(jì)算復(fù)雜度問題。首先我們對(duì)一個(gè)系統(tǒng)的判定所需的時(shí)間的數(shù)量級(jí)是一個(gè)什么函數(shù)作以下幾點(diǎn)說明： （1）所謂系統(tǒng)是指一個(gè)公理系統(tǒng)和它所定義的全體模型。例如布爾代數(shù)系統(tǒng)，可換群系統(tǒng)等。 （2）系統(tǒng)的判定是指對(duì)這個(gè)系統(tǒng)的所對(duì)應(yīng)的語言的全體語句正確與否提出證明或者辨別的統(tǒng)一過程。 （3）系統(tǒng)的計(jì)算復(fù)雜度是指判定這個(gè)系統(tǒng)定理的過程的復(fù)雜度計(jì)量。為了要對(duì)這個(gè)過程進(jìn)行測定我們使用Turing機(jī)。首先將系統(tǒng)的判定過程轉(zhuǎn)化為一個(gè)Turing機(jī)，而系統(tǒng)的定理將成為Turing機(jī)的輸入。這個(gè)Turing機(jī)的輸出就是“yes”或者“Do”，“yes”是說該輸入是一個(gè)定理，而“no”就說該輸入不是一個(gè)定理。系統(tǒng)的判定過程的復(fù)雜度就用這個(gè)Turing機(jī)的輸入和所用的時(shí)間與空間的比例函數(shù)來衡量。 （4）為了計(jì)算這個(gè)復(fù)雜度，系統(tǒng)的定理必須用記號(hào)來輸入。這樣一來模型論就派上了用場。系統(tǒng)的每一個(gè)定理都通過模型論用一個(gè)邏輯式子來表達(dá)，這個(gè)式子所用的記號(hào)的總數(shù)就計(jì)算為輸入的長度。 （5）當(dāng)系統(tǒng)的定理輸入到了這個(gè)Turing機(jī)，機(jī)器開始運(yùn)行直到得到輸出Turing機(jī)停了下來。從Turin9機(jī)開始運(yùn)行到Turing機(jī)停機(jī)所用到的Turing步子數(shù)目作為計(jì)算機(jī)器所耗費(fèi)的時(shí)間，而所用到的Turing方格（胞腔，cell）數(shù)目就作為計(jì)算機(jī)器所耗費(fèi)的空間。假設(shè)Turing機(jī)的輸入的長度為n機(jī)器運(yùn)行所耗費(fèi)的步子數(shù)目為。f（n），機(jī)器運(yùn)行所耗費(fèi)的空間數(shù)目為g（n），系統(tǒng)的時(shí)間復(fù)雜度就是f（n），系統(tǒng)的空間復(fù)雜度就是g（n）。 （6）Turing機(jī)對(duì)相同長度的不同的輸入可能反應(yīng)是不一樣的，對(duì)某些輸入機(jī)器在很短的時(shí)間內(nèi)就得到了結(jié)論而對(duì)另外一些輸入機(jī)器卻需要運(yùn)轉(zhuǎn)很長一段時(shí)間才能得到結(jié)論。我們要考慮對(duì)所有長度為n的輸入，機(jī)器運(yùn)轉(zhuǎn)所需的時(shí)間中最長的時(shí)間作為Thring機(jī)的時(shí)間復(fù)雜度f（n），同時(shí)也在把機(jī)器運(yùn)轉(zhuǎn)所需的空間中消耗最多的空間作為Turing機(jī)的空間復(fù)雜度g（n）。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    模型論及其在計(jì)算機(jī)科學(xué)中的應(yīng)用 PDF格式下載

---