语言背后的代数学(三):语义模型


1. 回顾

上文我们从代数学角度重新认识了自然数,

认识了自然数是如何被编码为符号串的,

以及自然数在数学上是如何表示的。


我们的整体思路是,首先用公理化的方式建立一个形式系统,

然后为这个形式系统选择一种数学解释作为它的语义,

这样就建立了符号和数学对象之间的对应关系。


一般的,这些数学对象需要具有不同的运算性质,有不同的结构,

因此构成了不同的代数。


在《你好,类型》系列文章中,

我们介绍了命题逻辑和一阶谓词逻辑,

当时,我们只是从形式系统(符号演算)的角度来介绍它们。


例如,我们只要知道公理和推导规则,就可以做出形式证明,


但是,这些符号到底代表什么含义呢?

我们当时故意没有提及。


本文从模型论角度来做出一些解释。


2. 一阶语言



首先让我们回顾以下一阶谓词逻辑有哪些符号构成,


(1)变元符号集合

它由可数个(包括0个)变元符号组成,用表示。

(2)逻辑连接词符号集合

它由逻辑连接词符号组成。

(3)量词符号集合,包括

(4)等词符号集合,只包括一个符号

(5)括号集合,包括


以上这些符号称为逻辑符号,每个一阶逻辑都有这些符号。

而不同的一阶逻辑,还有属于自己的非逻辑符号


(1)常元符号集合

它由可数个(包括0个)常元符号组成,用表示。

(2)函数符号集合

它由可数个(包括0个)函数符号组成,用表示。

(3)谓词符号集合

它由可数个(包括0个)谓词符号组成,用表示。

等词符号实际上可以看做是一个谓词符号。


因此,一阶谓词逻辑是一种一阶逻辑。

一阶逻辑中的逻辑符号和非逻辑符号,称为一阶语言,记为


3. 初等算术语言



初等算术语言是一个一阶语言,记为

它的常元符号集合为,函数符号集合为

谓词符号集合为


其中,可以表示算术中的后继函数,

而二元函数符号可以分别表示算术中的加法和乘法,

谓词符号可以描述自然数之间的小于关系。


4. 语法项和逻辑公式



从形式语言的角度来看,除了知道语言包含哪些符号之外,还要指定语法,

习惯上,我们经常使用BNF来指定,


即一个合法的,可以归纳定义为,

(1)每一个常元都是合法的项,

(2)每一个变元都是合法的项,

(3)如果都是合法的项,而是一个元函数符号,

那么也是一个合法的项。


初等算术语言中的合法项,

以下符号串都是合法的,

是不合法的。


我们知道逻辑证明,并不是建立在形式语法之上的,

而是建立在公理系统上面,而每一个推导规则都表明了前提和结论之间的关系,

这些前提和结论,称为逻辑公式


一阶语言中的逻辑公式,用大写字母表示,定义为,


即,逻辑公式可以归纳的定义为,

(1)如果是合法的项,则是公式,

(2)如果是合法的项,而是一个元谓词,则是公式,

(3)如果是公式,则是公式,

(4)若是公式,则都是公式,

(5)若是公式并且是一个变元,那么也是公式,称为约束变元


例,以下符号串可以看做一个初等算术公式,


5. 语义模型



有了一阶语言之后,我们就可以为符号选择语义了,

通常的,语言的语义有两部分组成,

其一称为结构,用来解释常元符号,函数符号和谓词符号,

其二称为赋值,用来解释变元符号。


5.1 语言结构

一阶语言结构是一个偶对,记为,其中,

(1)是一个非空集合,称为论域

(2)是从的映射,称为解释,记为,它满足下面三个条件

  1. 中的每一个常元符号中的元素

  2. 中的每一个n元函数符号上的n元函数

  3. 中的每一个n元谓词符号上的一个n元关系


例,我们可以指定初等算术语言的结构为,偶对

其中论域为自然数集,

为自然数集上的加函数,为自然数加法运算,为自然数乘法运算。

为自然数集上的小于关系。


5.2 变元赋值

赋值是一个映射,

它将中的每一个变元,赋以论域中的一个元素

记为,其中


有了赋值运算之后,公式中的变元就固定下来了,

我们就可以谈论,在某一指定赋值运算下公式的语义了。


5.3 模型和语义



给定一阶语言,并指定结构和赋值

我们称是,我们为语言选择的一个模型


项的语义

选择了模型之后,

中的合法项语义

就可以归纳的定义为论域中的元素了,记为

(1)为变元符号

(2)为常元符号

(3)


例,初等算术中项的语义,


逻辑公式的语义

公式在模型下的语义是一个真假值,用表示,归纳定义如下,

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)


其中,二元真值函数

分别逻辑连接词符号的语义。


至此,我们通过为一阶语言指定模型,

将语言中所有的符号串都进行了解释。


6. 总结

本文以一阶逻辑为例,从逻辑学角度给出了语义模型的定义,

由此,一阶逻辑系统中的符号串,都有了一个数学对象与之对应,

它们是论域,论域集合上的函数和运算。


可想而已,这些数学对象是有代数性质的,

下文我们将继续深入了解。


参考

你好,类型(五):Predicate logic

数理逻辑

一阶逻辑