【数理逻辑如何入门】:函数与谓词
理解了形式系统的概念,下一个问题就是:如何设计这个系统的语言?——这是该形式系统最主要的成分。首先,设计一个形式系统一定是有一定目的的。例如,设计一门程序设计语言,因此在考虑设计形式系统的语言结构时就一定要事先考虑未来所要绑定的语义。不过,我们这里这个形式系统未来所要指称的语义是某个数学分支,为这个数学分支建立公理系统。换句话说,当我们在设计一个形式系统时,需要要考虑的是:要拿这个东西干什么用?它所描述的对象是什么?这就是所谓的语义【对应理论】(correspondence theory)。很明显,设计某个数学分支公理化的形式系统与设计一门程序设计语言的形式系统的形式语言是完全不同的。这种不同,被称作【类】(class)。
设计形式系统另一个要考虑的因素是覆盖面,亦即、形式系统所要描述的对象——更准确的名称是——【数学结构】,也就是说,形式系统要为这个【数学结构】「量身定做」,使得形式系统表达力足够大能够覆盖结构的所有方面:语言的词汇、句法和语言结构,以及逻辑演算系统。
为了讨论方便,这里把笔记《【数理逻辑如何入门】公理系统和形式系统》中所归纳的形式系统复制到这篇笔记:
一个形式系统是由三个部分构成:
语言 —— 一阶语言
一组真值为真的句子 —— 公理集合
演算规则 —— 推理规则更形式化更代数化的表达
其中,最主要的成分之一是一阶语言。因此,设计形式系统的首要任务是确定形式语言的结构。而为了形式化精确定义语言,先要定义这个语言的基本构件 —— 词汇表。如果将词汇表看做是符号的集合,那么和自然语言一样,每个符号都属于某个词类,不同词类的符号在句子中起的作用自然也不同。如果我们的形式系统是描述整数的代数结构,那么下列表达式就是其中的一个例子:
2 + 1 < 4
从我们的数学常识来看,这是个不等式;从形式系统的角度来看,这是形式语言的一个句子;从结构的角度来看,这个句子包含了【运算】与【关系】以及整数集合Z的两个成员;从语义的角度来看,这个句子给出了真值为「真」的命题;从语言的角度来看,这个表达式是由五个符号、三类词汇构成,其中,2、1、4是整数,+是函数符号,<是谓词符号。而【函数】与谓词的通用句法形式为:
函数 (a, b)
谓词 (a, b)
其中,(a, b)称作【元组】,二元元组又称为「有序对」。而【元组】的概念来自于笛卡尔乘积,因此,【函数】与【谓词】句法形式应当是:函数/谓词符号应用于元组:
函数 (a1,a2,..an)
谓词 (a1,a2,..an)
从句法上看,【函数】与【谓词】相同,但是从语义上看则不同:【函数】返回与a、b属于相同集合的某一元素,而【谓词】返回集合{T, F}中的某个元素。
因此,我们这个形式语言词汇表中包含三个词类:整数符号、函数符号、关系符号
上面我们用中文——自然语言非形式化地简述了函数符号和谓词符号作为形式语言一部分的定义。这个时候,中文就是这个形式语言的【元语言】。下面,我们换一种【元语言】—— 「集合论语言」再重复一遍上述的定义。
设有整数集合Z —— 有名称,集合元素数量无限;更难懂的的说法是:集合的势无法被表达为一个自然数
设有真值集合 {T, F} —— 无名称,集合元素数量有限;更难懂的的说法是:集合的势可以被表达为一个自然数,这个自然数被称作「基数」(cardinal)
映射:M:A → B
函数:f ∈ M:Z * Z *,.. * Z → Z
谓词:p ∈ P:Z * Z *,.. * Z → {T, F}
元组:(a1,a2,...,an) ∈ Z * Z *,.., * Z
注意:上述定义中的中文、波折号后面的中文可以看做是类似于程序语言中的注释文本,不属于集合论元语言。其中,元组中符号的个数称作元;
例如,
f(a) 是一元 (unary) 函数,p(a)是一元谓词;
f(a,b)是二元函数 (binary),p(a,b)是二元谓词;
f(a,b,c)是三元 (ternary) 函数,p(a,b,c)是三元谓词;
一般地,f(a1,a2,...,an) 是n元 (n -ary)函数,p(a1,a2,...,an)是n元谓词。
除此之外,也允许出现零元函数或谓词。例如一个整数可以看做是一个零元函数,一个真值T或F可以看做是一个零元谓词。
有了上面的基本构件,我们就可以定义一个形式语言:
词汇表:V ={a,b,c,..}
形式语言:(V, +, <, = )
句法规则:
若a ∈ V,则 a是表达式
若a和b是表达式,则 a + b 也是表达式
若a和b是表达式,则 a < b 也是表达式
若a和b是表达式,则 a = b 也是表达式
其中,词汇表又称为【论域】(universe),除了+、<和=,外,其它拉丁字母符号又称作【名称】。
这个形式语言和下列代数结构可以建立语义解释关系
代数结构:S = <Z, +, <, = >
整数集合:Z
在这个集合上可定义关系:<, =
在这个集合上可定义函数:+
这个函数符合结合律
这个函数符合交换律
0是这个集合的元素使得任何a∈Z,都有a+0=a, 0+a=a
存在集合元素-a 使得 a + (-a) = 0
这样,我们就可以建立完整的关于这个数学结构的公理系统。我们下次再谈。
小结:
几个重点:形式系统,公理系统,形式语言、句法、语义、函数、谓词、元语言、集合论语言
本文依据《Mathematical Logic》by Sheonfield 1967写成
设计形式系统另一个要考虑的因素是覆盖面,亦即、形式系统所要描述的对象——更准确的名称是——【数学结构】,也就是说,形式系统要为这个【数学结构】「量身定做」,使得形式系统表达力足够大能够覆盖结构的所有方面:语言的词汇、句法和语言结构,以及逻辑演算系统。
为了讨论方便,这里把笔记《【数理逻辑如何入门】公理系统和形式系统》中所归纳的形式系统复制到这篇笔记:
一个形式系统是由三个部分构成:
语言 —— 一阶语言
一组真值为真的句子 —— 公理集合
演算规则 —— 推理规则更形式化更代数化的表达
其中,最主要的成分之一是一阶语言。因此,设计形式系统的首要任务是确定形式语言的结构。而为了形式化精确定义语言,先要定义这个语言的基本构件 —— 词汇表。如果将词汇表看做是符号的集合,那么和自然语言一样,每个符号都属于某个词类,不同词类的符号在句子中起的作用自然也不同。如果我们的形式系统是描述整数的代数结构,那么下列表达式就是其中的一个例子:
2 + 1 < 4
从我们的数学常识来看,这是个不等式;从形式系统的角度来看,这是形式语言的一个句子;从结构的角度来看,这个句子包含了【运算】与【关系】以及整数集合Z的两个成员;从语义的角度来看,这个句子给出了真值为「真」的命题;从语言的角度来看,这个表达式是由五个符号、三类词汇构成,其中,2、1、4是整数,+是函数符号,<是谓词符号。而【函数】与谓词的通用句法形式为:
函数 (a, b)
谓词 (a, b)
其中,(a, b)称作【元组】,二元元组又称为「有序对」。而【元组】的概念来自于笛卡尔乘积,因此,【函数】与【谓词】句法形式应当是:函数/谓词符号应用于元组:
函数 (a1,a2,..an)
谓词 (a1,a2,..an)
从句法上看,【函数】与【谓词】相同,但是从语义上看则不同:【函数】返回与a、b属于相同集合的某一元素,而【谓词】返回集合{T, F}中的某个元素。
因此,我们这个形式语言词汇表中包含三个词类:整数符号、函数符号、关系符号
上面我们用中文——自然语言非形式化地简述了函数符号和谓词符号作为形式语言一部分的定义。这个时候,中文就是这个形式语言的【元语言】。下面,我们换一种【元语言】—— 「集合论语言」再重复一遍上述的定义。
设有整数集合Z —— 有名称,集合元素数量无限;更难懂的的说法是:集合的势无法被表达为一个自然数
设有真值集合 {T, F} —— 无名称,集合元素数量有限;更难懂的的说法是:集合的势可以被表达为一个自然数,这个自然数被称作「基数」(cardinal)
映射:M:A → B
函数:f ∈ M:Z * Z *,.. * Z → Z
谓词:p ∈ P:Z * Z *,.. * Z → {T, F}
元组:(a1,a2,...,an) ∈ Z * Z *,.., * Z
注意:上述定义中的中文、波折号后面的中文可以看做是类似于程序语言中的注释文本,不属于集合论元语言。其中,元组中符号的个数称作元;
例如,
f(a) 是一元 (unary) 函数,p(a)是一元谓词;
f(a,b)是二元函数 (binary),p(a,b)是二元谓词;
f(a,b,c)是三元 (ternary) 函数,p(a,b,c)是三元谓词;
一般地,f(a1,a2,...,an) 是n元 (n -ary)函数,p(a1,a2,...,an)是n元谓词。
除此之外,也允许出现零元函数或谓词。例如一个整数可以看做是一个零元函数,一个真值T或F可以看做是一个零元谓词。
有了上面的基本构件,我们就可以定义一个形式语言:
词汇表:V ={a,b,c,..}
形式语言:(V, +, <, = )
句法规则:
若a ∈ V,则 a是表达式
若a和b是表达式,则 a + b 也是表达式
若a和b是表达式,则 a < b 也是表达式
若a和b是表达式,则 a = b 也是表达式
其中,词汇表又称为【论域】(universe),除了+、<和=,外,其它拉丁字母符号又称作【名称】。
这个形式语言和下列代数结构可以建立语义解释关系
代数结构:S = <Z, +, <, = >
整数集合:Z
在这个集合上可定义关系:<, =
在这个集合上可定义函数:+
这个函数符合结合律
这个函数符合交换律
0是这个集合的元素使得任何a∈Z,都有a+0=a, 0+a=a
存在集合元素-a 使得 a + (-a) = 0
这样,我们就可以建立完整的关于这个数学结构的公理系统。我们下次再谈。
小结:
几个重点:形式系统,公理系统,形式语言、句法、语义、函数、谓词、元语言、集合论语言
本文依据《Mathematical Logic》by Sheonfield 1967写成
> 我来回应