模型论及其在计算机科学中的应用

当前位置:首页 > 教材 > 研究生/本专科 > 模型论及其在计算机科学中的应用

出版社:北京师范大学出版社
出版日期:2012-1
ISBN:9787303136025
作者:罗里波
页数:300页

作者简介

《新世纪高等学校教材•数学与应用数学基础课系列教材:模型论及其在计算机科学中的应用》共分为二十章,主要内容包括:模型论的发生与发展;关于集合论的准备知识;模型论的形式语言;模型的基本性质;紧致性定理与LST定理;初等予模型与模型完全的理论等。《新世纪高等学校教材•数学与应用数学基础课系列教材:模型论及其在计算机科学中的应用》给供相关人员参考阅读。

章节摘录

版权页:   第十三章无原子布尔代数理论的计算复杂度 13.1 一个系统的定理判定的计算复杂度 在这一章里我们要介绍在理论判定的计算复杂度的研究中应用模型论的方法来解决问题。在计算机的理论研究中常常会遇到一个系统的定理判定的计算复杂度问题。首先我们对一个系统的判定所需的时间的数量级是一个什么函数作以下几点说明: (1)所谓系统是指一个公理系统和它所定义的全体模型。例如布尔代数系统,可换群系统等。 (2)系统的判定是指对这个系统的所对应的语言的全体语句正确与否提出证明或者辨别的统一过程。 (3)系统的计算复杂度是指判定这个系统定理的过程的复杂度计量。为了要对这个过程进行测定我们使用Turing机。首先将系统的判定过程转化为一个Turing机,而系统的定理将成为Turing机的输入。这个Turing机的输出就是“yes”或者“Do”,“yes”是说该输入是一个定理,而“no”就说该输入不是一个定理。系统的判定过程的复杂度就用这个Turing机的输入和所用的时间与空间的比例函数来衡量。 (4)为了计算这个复杂度,系统的定理必须用记号来输入。这样一来模型论就派上了用场。系统的每一个定理都通过模型论用一个逻辑式子来表达,这个式子所用的记号的总数就计算为输入的长度。 (5)当系统的定理输入到了这个Turing机,机器开始运行直到得到输出Turing机停了下来。从Turin9机开始运行到Turing机停机所用到的Turing步子数目作为计算机器所耗费的时间,而所用到的Turing方格(胞腔,cell)数目就作为计算机器所耗费的空间。假设Turing机的输入的长度为n机器运行所耗费的步子数目为。f(n),机器运行所耗费的空间数目为g(n),系统的时间复杂度就是f(n),系统的空间复杂度就是g(n)。 (6)Turing机对相同长度的不同的输入可能反应是不一样的,对某些输入机器在很短的时间内就得到了结论而对另外一些输入机器却需要运转很长一段时间才能得到结论。我们要考虑对所有长度为n的输入,机器运转所需的时间中最长的时间作为Thring机的时间复杂度f(n),同时也在把机器运转所需的空间中消耗最多的空间作为Turing机的空间复杂度g(n)。

书籍目录

第一章 模型论的发生与发展
 1.1 模型论在科学发展中的地位
 1.2 模型论的发展概述
 1.3 模型论与计算机科学的关系
 1.4 模型论研究的方法与特点
 1.5 语法与语义
第二章 关于集合论的准备知识
 2.1 完整的集合论公理系统
 2.2 有限集与无限集
 2.3 集合之间元素个数的比较
 2.4 选择公理和可良序化定理
 2.5 基数的定义和性质
 2.6 序数定义和超限归纳过程
 2.7 可数集的性质
 2.8 序数,基数的运算
 2.9 实数的不可数性
 2.10 连续统假设简介
 练习题
第三章 模型论的形式语言
 3.1 形式逻辑中的命题演算
 3.2 一阶逻辑简介
 3.3 命题演算的模型论的补充性质
 3.4 模型论的形式语言
 3.5 模型论的式子和它们的构成
 3.6 模型论的式子推演
 练习题
第四章 模型的基本性质
 4.1 形式语言的解释与模型
 4.2 模型的同构,同态,子模型,扩张,膨胀,归约
 4.3 式子的代入与验证
 4.4 理论,公理,定理和模型的理论
 4.5 语言和理论的模型数
 4.6 模型的同构嵌入
 4.7 模型的初等等价
 练习题
第五章 紧致性定理与LST定理
 5.1 从理论构造模型
 5.2 紧致性定理
 5.3 紧致性定理的应用
 5.4 模型的图像
 5.5 模型论的内语言与外语言
 练习题
第六章 初等子模型与模型完全的理论
 6.1 初等子模型
 6.2 初等图像和它的应用
 6.3 强LST定理
 6.4 完全的理论
 6.5 模型完全的理论
 练习题
第七章 初等链的构造与应用
 7.1 模型的链的构造
 7.2 模型的链的并
 7.3 初等链定理
 7.4 式子集的实现与省略
 练习题
第八章 保持性定理
 8.1 研究保持性定理的意义和方法
 8.2 子模型的保持性定理
 8.3 模型链的并保持性定理
 8.4 同态象的保持性定理
 8.5 保持性的部分表
 练习题
第九章 可数语言的几种特殊模型
 9.1 素模型与原子模型
 9.2 齐次模型
 9.3 可数饱和模型
 练习题
第十章 一些具体的模型和逻辑性质
 10.1 模型与语言的关系
 10.2 偏序、全序集模型
 10.3 布尔代数模型
 10.4 群,环,域系列的模型
 10.5 其他系列的模型
 练习题
第十一章 量词消去法和可判定的理论
 11.1 量词消去法的重要性
 11.2 量词消去法的一般步骤
 11.3 无端稠密有序集的量词消去法
 11.4 整数加运算的量词消去法
 11.5 代数模型的模型数
 11.6 布尔代数模型的模型数
 11.7 W-范畴的可数完全的理论
 11.8 范畴性研究介绍
 练习题
第十二章 不可判定的理论
 12.1 自然数理论系统□□的不可判定性
 12.2 有理数加法、乘法系统的不可判定性
 12.3 自由群T-理论的不可判定性
 练习题
第十三章 无原子布尔代数理论的计算复杂度
 13.1 一个系统的定理判定的计算复杂度
 13.2 无原子布尔代数的公理系统
 13.3 量词消去法的作用与过程
 13.4 无原子布尔代数的性质
 13.5 无原子布尔代数的量词消去法
 13.6 无原子布尔代数的计算复杂度
第十四章 可换群定理判定的计算复杂度
 14.1 可换群的理论和结构
 14.2 模型的Ehrenfeucht博弈
 14.3 群Dp博弈的准备工作
 14.4 群Dp的Ferrente和:Rackoff博弈
 14.5 群Dp的计算复杂度上界
 14.6 可换群理论的计算复杂度
第十五章 对数论模型的研究
 15.1 广义中国剩余定理
 15.2 □的w-和模型
 15.3 孪生准素数问题
 15.4 对Goldbach猜想和孪生素数问题的研究
第十六章 有限模型论的保持性定理
 16.1 模型的初等性质
 16.2 保持性定理
第十七章 集合论的可数模型
 17.1 实数的相对性
 17.2 集合论的可数模型
 17.3 ZFG模型中元素的不可区分群组
 17.4 无限小数的不确定性
 17.5 康托尔实数的局限性
 17.6 计算机科学与无限概念的关系
第十八章 非良基集合论模型悖论
 18.1 集合论的新悖论
 18.2 良基性定理与非良基的集合论模型
 18.3 非良基的集合论模型的精确化
 18.4 非良基集合论模型中的良序集与类
 18.5 结论
第十九章 可数多个单元关系的研究
 19.1 可数多个独立单元关系系统
 19.2 可数多个单元关系的完全理论
第二十章 多项式复杂度的计算问题
 20.1 一些引理
 20.2 二次模方程的解
参考文献
索引

图书封面


 模型论及其在计算机科学中的应用下载 更多精彩书评



发布书评

 
 


精彩书评 (总计1条)

  •     从业于计算机,因数学理论欠缺,买来此书,本想补课,无奈此书有国内数学书的通病,即不适合与初学者。网上找来 [数学基础引论] 黄耀枢著 北京大学出版社 87,放在 kindle 中,此书要好读得多,早知买此书好了。

精彩短评 (总计9条)

  •     模型论经典的中文教材
  •     内容思路不是很清晰。。。
  •     这本书很专业,还没看完,但我很喜欢。
  •     罗先生的著作是模型论入门的一本好书,再结合CCChang的书,很容易进入该领域
  •     有点抽象,不过科研适当时候拿出来参考下还行
  •     书的质量非常的好!!!!!态度也很好!!!!!
  •     模型论重要的一本书
  •     很不错,有深度。
  •     这本书没有例子,很难看懂。基本上只有定理,推论之类的。而且很羞涩难懂,但相同的概念,上维基百科,人家的解释比这本书好很多了
 

中考,文化人类学,图书馆学档案学,校园,中考,科幻,德语,研究生/本专科图书,。 图书零零三 

图书零零三 @ 2019