哈师大毕业论文 逻辑

哈尔滨师范大学

学 年 论 文

题 目 谓词演算在数学理论中的应用

学 生

指导教师 庞健 教授

年 级 2007级

专 业 数学与应用数学

系 别 数学系

学 院 数学与计算机科学学院

哈尔滨师范大学

2010年05月

论 文 纲 要

在基础数学课程改革的背景下，高中阶段开设数理逻辑课程哪些方面展开更有利于老师的教和学生的学，是一个非常重要的问题。本文通过对谓词演算的了解来解决在数学理论中存在的一些逻辑问题，谓词演算对于描述更复杂的数学结构是不充分的。从文法上说谓词演算在现存的命题演算上增加了“谓词-主词结构”和量词。谓词演算在函数、集合、离散数学等方面的诸多应用和诸多理论。

谓词演算在数学理论中的应用

吕姗姗

摘 要：在基础数学课程改革的背景下，高中阶段开设数理逻辑课程哪些方面展开更有利于老师的教和学生的学，是一个非常重要的问题。本文通过对谓词演算的了解来解决在数学理论中存在的一些逻辑问题，谓词演算对于描述更复杂的数学结构是不充分的。从文法上说谓词演算在现存的命题演算上增加了“谓词-主词结构”和量词。谓词演算在函数、集合、离散数学等方面的诸多应用和诸多理论。

关键词：谓词演算 数学理论 数理逻辑

数理逻辑最基本的形式系统。又称一阶逻辑。一个可以回答真假的命题，不仅可以分析到简单命题，还可以分析到其中的个体、量词和谓词。个体表示某一个物体或元素，量词表示数量，谓词表示个体的一种属性 。例如用P(x)表示x 是一棵树，则P(y)表示y 是一棵树，用Q(x)表示x 有叶 ，则Q(y)表示y 也有叶。这里P 、Q 是一元谓词，x ，y 是个体，公式"x(P(x)→Q(x))表示每一棵树都有叶子 ，这里" 是全称量词表示“每一个” 。公式$x(P(x)∧Q(x))表示有一棵没有叶的树，这里$是存在量词，表示“存在一个”。

在数学中的关系，函数都可以看成谓词 。例如x

谓词可以在一定的个体集合中给出解释，谓词连接可以在这样的个体集合中取到真假值。例如在实数集R 中解释Q(x)为x 是有理数，则谓词公式(*)取值为真。如果在R 中解释Q(x)为“x是整数”，谓词公式(*)就取值为假了。谓词公式在个体集合中取值的严格定义称为基本语义定义，这个定义是波兰籍数学家A. 塔尔斯基在20 世纪 30年代给出的 。给定了谓词解释的个体集合称为模型。基本语义定义使谓词公式和模型都可以被当作数学对象加以研究。一个谓词公式在任意一个模型中都取真值，就称之谓恒真式。两个谓词公式A ，B 在任意模型的任何一种解释下都取相同的值，就称A ，B 逻辑等价。命题演算中的恒真式和等价式所反映的规律在谓词演算中仍成立。谓词演算中还有一些有关量词的等价式，如："xP(x)Û$鰔黀(x)，"x(j→ψ)Ûj→"xψ（x 不在j 中自由出现），"x(j→ψ)?xj→ψ（x 不在ψ中自由出现）。利用这些有关量词的等价式作等价变换，可以把任何一个谓词公式的量词移到公式的最前面，得到与之等价的前束标准形公式。形如Qx1，Qx2，… ，QxnB 的公式称为前束型公式 ，其中Qxi 表示$xi或"xi ，B 是一个不含量词的公式。

谓词演算中命题函数与量词有谓词H 表示“能够到达山顶”,客体p 表示李四,q 表示老虎,r 表示汽车。那么 H(p), H(q), H(r)表示三个不同的命题，相同点：H(x)

由一个谓词, 一些客体变元组成的表达式称为简单命题函数。由一个或者n 个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。客体变元的取值范围称为个体域(或论述域) 。个体域可以是有限客体的集合, 如：{a、b 、c}、{计算机系的学生}；也可以是无限客体的集合, 如实数几何、自然数集合等。

特别是, 当没有特别声明时, 可以将宇宙间的一切事物和概念构成的集合作为个体域, 称为全总个体域。

例如：

∀ xF(x)表示个体域中的所有客体都有性质F ；

∃ xF(x)表示存在着个体域中的客体具有性质F 。

当个体域有限时, 设个体域为{a1,a2,…,an },则

∀x F(x)⇔F(a1)∧F(a2)∧… ∧ F(an )

∃x F(x)⇔F(a1) ∨ F(a2)∨… ∨F(an)

符号化:谓词F(x)表示是要死的。

当个体域为人类集合时, 上述两命题可分别符号化为

① ∀ x F(x) ② ∃x F(x)。

(所有的人都是要死的。 有些人是要死的。)

引入新的谓词M(x),将人类分离出来。在全总个体域下, 以上两命题可分别叙述为：

∀ x(M(x)→F(x))

∃ x (M(x)∧F(x))

在谓词逻辑中将下列命题符号化。

(1)没有不死的人。 (2)不存在最小数。

(3)教育技术系的学生都学离散数学。

解 题目中没有指定个体域, 取个体域为全总个体域。

(1)假设,M(x)：x 是人,F(x)：x 是要死的，那么

ㄱ∃x(M(x) ∧ㄱF(x))

(2)假设,N(x)：x 是数,L(x,y)：x 小于y ，那么

ㄱ∃x(N(x) ∧ ∀y(N(y) →L(x,y)))

(3)假设,S(x)：x 是教育技术系的学生,F(x)：x 要学离散数学，那么

(∀x)(S(x) →F(x))

本题也可以引入二元谓词G(x,y)：x 是学习y, 以及客体常元a ：离散数学, 进行如下符号化：

(∀x)(S(x)→G(x,a))

谓词演算也研究谓词公式的推演。谓词演算自然推演的一些规则为：

①全称量词消去

②全称量词引入

③存在量词消去

④存在量词引入

这些规则中横线上是条件，横线下是结论，j(x)是含自由变元x 的谓词公式，y 是不在j(x）中出现的变元 ，c 是特定的个体常元，j(y)，j(c)是以y ，c 分别代替j(x)中所有自由出现的x 得到的谓词公式 。与命题公式的推演不同 ，谓词公式的推演要求条件是恒真式时得到的结论也是恒真式。

谓词演算也可以公理化。从符号到公式的定义，从公理到推演都严格形式化，构成完全的公理系统，使系统所推演出的都是恒真式，且每个恒真式都能从公理推演出来。与命题演算不同的是，谓词演算是一个不可判定的系统，即不存在一个算法来判定谓词公式是否恒真式。

谓词演算是命题演算的扩展，命题演算对于描述更复杂的数学结构是不充分的。从文法上说谓词演算在现存的命题演算上增加了“谓词-主词结构”和量词。主词是给定

的个体群组(集合) 的一个成员的名字，而谓词是在这个群组上的关系，一元谓词在哲学中称为性质，在数学中称为指示函数，在数理逻辑中称为布尔值函数。

谓词演算在数学当中有很多的词汇应用，如：谓词变量(或关系) 的集合，每个都有某个价(或元数) ≥1，经常指示为大写字母 P, Q, R,... 。

常量的集合，经常指示为小写字母，开始于字母 a, b, c,... 。

函数的集合，每个都有某个价 ≥ 1，经常指示为小写字母 f, g, h,... 。 变量的有限集合，经常指示小写字母，结束于字母 x, y, z,... 。

表示逻辑算子(或连结词) 的符号: (逻辑非), (逻辑与), (逻辑或), → (逻辑条件), (逻辑双条件) 。

表示量词的符号: (全称量化), (存在量化).

左和右圆括号。

同一或等于符号 = 有时但不总是在词汇表中。

下面列出一些次要的变化:

基本(primitive)符号(算子和量词) 的集合经常变化。有些符号可以被省略并被接受为简写；比如 (P Q) 是 (P → Q) (Q → P) 的简写。在另一方面，有可能包含其他算子作为基本算子，比如真值常量 ⊤ ("真") 和 ⊥ ("假")(它们是 0 价算子) ，或Sheffer 竖线(P | Q) 。需要的基本符号的极小数目是一，但是如果我们把自身限制于上述列出的算子，我们就需要三个；比如 ¬、∧ 和 ∀ 就足够了。

某些旧的书籍和论文使用符号 φ ⊃ ψ 表示 φ → ψ，~φ 表示 ¬φ，φ & ψ 表示 φ ∧ ψ，和大量的表示量词的符号；比如 ∀x φ 可以被写为 (x)φ。 等式有时被认为是一阶逻辑的一部分；如果是这样，等号包含在词汇表中，而它们的行为在语法上如同二元谓词。这种情况有时叫做有等式的一阶逻辑。

常量实际上同于 0 价的函数，所以有可能并且是便利的省略常量并允许函数有任何价。但是传统上只对至少 1 价的函数使用术语" 函数" 。

在上述关系的定义中必须有至少 1 价。有可能允许 0 价关系；它们可以被认为是命题变量。

对放置括号有很多不同的约定；例如，你可以写 ∀x 或 (∀x) 。有时使用冒号或句号来替代圆括号使公式免除歧义。一个有趣但非常不常用的约定是" 波兰表示法" ，这里忽略所有圆括号，在其参数之前写 ∧、∨ 等等，而不是在它们中间。波兰表示法是简约和优雅的，但因为不适合人类阅读而少用。

有一个技术观察，如果有表示有序对的 2 元函数符号(或表示有序对的投影的二元谓词符号) ，则可以完全分配元数 > 2 的函数或谓词。当然有序对或投影需要满足那些自然公理。

常量、函数和关系的集合通常被认为形成了一个语言，而变量、逻辑算子和量词通常被认为属于逻辑。例如，群论的语言由一个常量(单位元素) ，一个 1 价函数(反) ，一个 2 价函数(积) ，和一个 2 价关系(等于) 组成，等号可以被包含在底层的逻辑中而被忽略。

项的集合按如下规则递归的定义:

任何常量是项。

任何变量是项。

n ≥ 1 个参数的任何表达式 f(t1,...,tn) (这里的每个参数 ti 都是项，而 f 是 n 价的函数符号) 是项。

闭包条款: 其他东西都不是项。

合式公式

合式公式(通常叫做 wff 或只是公式) 按如下规则递归的定义:

简单和复杂谓词 如果 P 是 n ≥ 1 价的关系而 ai 是项，则 P(a1,...,an) 是合式的。如果等式被认为是逻辑的一部分，则 (a1 = a2) 是合式的。所有这个公式都被称为是原子。

归纳条款 I: 如果 φ 是 wff ，则 ¬φ 是 wff 。

归纳条款 II: 如果 φ 和 ψ 是 wff ，则 (φ → ψ) 是 wff 。

归纳条款 III: 如果 φ 是 wff 而 x 是变量，则 ∀x φ 是 wff 。

闭包条款: 其他东西都不是 wff 。

因为 ¬(φ → ¬ψ) 逻辑等价于 (φ ∧ ψ)，(φ ∧ ψ) 经常用做简写。(φ ∨ ψ) 和 (φ ψ) 也是同样的道理。还有 ∃x φ 是 ¬∀y ¬φ 的简写。 实际中，如果 P 是 2 价关系，我们经常写 "a P b" 替代 "P a b" ；例如，我们写 1

例如：有序阿贝尔群的语言有一个常量 0，一个一元函数 −，一个二元函数 +，和一个二元关系 ≤。所以

0, x, y 是原子项

+(x, y), +(x, +(y, −(z))) 是项，通常写为 x + y, x + y − z

=(+(x, y), 0), ≤(+(x, +(y, −(z))), +(x, y)) 是原子公式，通常写为 x + y = 0, x + y - z ≤ x + y

(∀x ∃y ≤( +(x, y), z)) ∧ (∃x =(+(x, y), 0)) 是公式，通常写为 (∀x ∃y x + y ≤ z) ∧ (∃x x + y = 0)

对于任何理论，知道公理的集合是否可用算法生成，或是否存在算法确定合式公式为公理，是很有价值的。

如果存在生成所有公理的算法，则公理的集合被称为递归可枚举的。

如果存在算法在有限步骤后确定一个公式是否是公理，则公理的集合被称为递归的或“可判定的”。在这种情况下，你还可以构造一个算法来生成所有的公理: 这个算法简单的(随着长度增长) 一个接一个的生成所有可能的公式，而算法对每个公式确定它是否是个公理。

谓词演算在数学中的灵活应用虽然现在不是太完善的一种数学方法，但是应用谓词演算来解决数学问题能更清晰的解决数学中存在的一些不能表达的数学难题，合理的运用谓词演算不但对数学学习有帮助，而且对信息科学与技术的发展也有着不可限量的作用，主要体现在函数、集合、离散数学等方面。还有很多的信息需要继续的研

究发现，我们应该正确的对待谓词演算在数学理论中的重要地位，学习它应用它解决更多的数学问题，为我们能从多角度的去研究数学。

参考文献：

【1】 Barnes ， D W ．et a1．，in Algebraic． Imroducsion to Mathematical

Logic,springer-Verlag ，1975．

【2】 Curry ，H.B ,et a1. ，in Combinatory Logic ，Vol.l ，No rth —Holland Co ．，1958．

【3】 Hindley ，J ．R ．er al.， in lntroduction to Combinasors amd Cambridge

University Press,1986.

【4】 江明德，计算机学报，11(1988)，5：286-293。

学年论文（设计）成绩表