在
模型论,给定在同一个语言L中的两个结构M和N,我们称M是N的基本子结构(有时表示为M
集合之间的关系。
在
模型论,给定在同一个语言L中的两个结构M和N,我们称M是N的基本子结构(有时表示为M
1. M是N的子结构,且
2. 对于所有有限元组 ,对于所有语言L的公式 ,我们有 当且仅当 。
我们称N是M的基本扩展当且仅当M是N的基本子结构。
有时对第二个条件使用一个等价的陈述。我们可以通过对所有 增加一个常量符号 来扩展L为一个新语言 。那么M和N是解释每个 为m的 的结构。
设 和 分别是在M和N中为真的 -句子的集合(称为它们的“基本图”)。那么上述条件(2)等价陈述
在模型论中,塔斯基-沃特测试是用来判定一个子结构是否是基本子结构的定理。
模型论
模型论(Model theory)是数学的一个学科,模型论的一些重要定理,如紧致性定理,L-S-T 定理,
省略型定理,插值定理等等,不仅对逻辑,集合论,递归论的研究有重要作用,而且也在数论、代数、拓扑等数学学科中得到应用。
研究形式语言与其解释(模型)之间的关系,也就是形式语言的语法与语义之间的关系。数理逻辑的主要分支之一。模型论把形式语言中的公式、句子、理论(句子集)和模型当作数学对象,引进了近世代数中的一些概念、方法,从而模型论的一些结果和方法也被用到数学之中。因此,模型论的一些基本方法,如构造模型的常量方法,图像方法,模型链,超积也已成为常用的方法。一阶逻辑的模型论是模型论的基础,事实上,任何一种逻辑系统都有各自的模型论。 除各种逻辑的模型论外,模型论的新发展层出不穷 ; 用模型论手法来研究逻辑系统,也叫做模型论逻辑;用模型论方法比较各种逻辑系统的强弱,分析各种逻辑系统的特点,叫抽象逻辑的模型论。用递归论方法研究模型论问题产生递归模型论。只研究有限模型的构造和判定叫有限模型论。 用模型论的思想去研究代数结构、群、环、模、域等叫做代数模型论。研究模型分类的理论叫稳定性理论。现代模型论对计算机科学也有一定影响。
初等等价结构
在数学中,特别是模型论中,给定语言的两个结构被称为初等等价的,如果它们的理论相同,就是说任何被一个模型满足的句子也被另一个模型满足。当且仅当两个模型是基本等效的时,一阶理论是完整的。例如考虑带有二元关系符号 '<' 的语言。实数模型 R 和有理数模型 Q 是初等等价的,因为它们都转换 '<' 为无界稠密线性次序。还存在数论的
非标准模型,它包含不只是数 0, 1, 2, 的其他对象。但是这个语言同于标准数论,因为这些额外的对象不能被提及。所以数论的标准模型和非标准模型是初等等价的。
形式语言
数学、
逻辑和计算机科学中,形式语言(
英语:Formal language)是用精确的数学或机器可处理的公式定义的语言。
如
语言学中语言一样,形式语言一般有两个方面:
语法和
语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论,它只研究语言的语法而不致力于它的语义。在形式语言理论中,形式语言是一个
字母表上的某些有限长
字符串的
集合。一个形式语言可以包含无限多个字符串。按一定规律构成的句子或符号串的有限或无限的集合。
形式语言的字母是从该语言的字符串可以形成的一组符号,字母,或标记,;通常它的要求是有限的。
字符串
字符串由这个称为字的字母形成,这些词属于一个特定的形式语言有时被称为形式公式。一个正式的语言,往往是通过一个正式的语法,如正则文法或上下文无关文法定义,称作形成规律。形式语言理论主要研究的是内部结构模式这类语言的纯粹的语法领域。形式语言理论是从语言学衍生而来,作为一种理解自然语言的句法规律。在计算机科学中,形式语言通常作为定义编程语言和语法的基础,是正式版本的自然语言的子集。在
计算复杂性理论中,决策问题通常定义为形式语言,复杂类被定义为形式语言的集合,它能被具有有限计算能力的机器所解析。在逻辑和数学基础中,形式语言是用来表示公理系统的语法。
应用
基本子结构在基本结构如集合,序列,求和等中有着广泛应用。在计算机编译原理中和自然语言处理也广泛存在。