数据结构：
?D,{R1,......,Rn},{O1,......,Om}?D:数据集R1,......,Rn:数据集上的关系.
O1,......,Om:数据集上的操作(运算).极限描述：limn??xn?a
对于任意的??0,存在自然数N?0,当n?N时, |xn-a|
二元：大于、小于； 函数：求绝对值。 函数极限描述：limx?af(x)?A
对于任意的??0,存在??0,对任何x,当|x-a|
25
一阶语言L的构造
符号系统：
个体：常元：a,b,c,…;
自由变元：u,v,w,…; 约束变元：x,y,z,…; 函数符号：f, g, h,…; 关系符号：P, Q，R,…; 联结词：?,?,?,?,?
量词：?,?。辅助符号： (，)，[ ，]，{ ，}（用于区分） 例：自然数系统：?N,0,s,{?,*},??
生成元：0
生成函数：后继函数s(x)=x+1, 生成自然数集。
(Peano公理)
运算：+，* 为两个二元运算。 关系：= 为一个二元关系。
项集合Term(L)的归纳定义：（其中的元素称为项） (1) 个体常元a?Term(L)
个体自由变元u?Term(L)
(2) 若t1,......,tn?Term(L)，f是一个n元函数，则
f(t1,......,tn)?Term(L)；
(3) 对任何t?Term(L)，可以经由(1)、(2)有限步递归生成。
项集合Term(L)中的项元素被解释成论域中的元素。是基本数据的抽象。函数对应数据操作运算。
等价定义(项集合Term(L))：满足如下条件的最小集合S称为项集合。记为Term(L) (1) a,u?S (归纳基)
26
(2) 对任何t1,......,tn?S，及任意的n元函数f，有f(t1,......,tn)?S。(归纳步)
原子谓词公式集Atom(L)：
对任何t1,....t.,Term，L(及)任意的n元关系R，R(t1,......,tn)?Atom(L)。n.?（R(t1,......,tn)可判断）
在命题语言中，原子命题是最小单位，用一个命题符号表示。一阶语言中，原子命题不是最小单位，它刻画基础对象之间的某种关系（或性质）。对象之间有这种关系（或性质）就取真，否则就假。
谓词公式集Form(L)的归纳定义：
(1) 原子公式集Atom(L)?Form(L)。
(2) 若A,B?Form(L)，则(?A),(A*B)?Form(L) 。 其中*?{?,?,?,?}
(2) 若A(u)?Form(L)，x不在A(u)中出现，则
(?x)A(x),(?x)A(x)?Form(L)。
在一阶语言中，变元只对个体，函数符号和谓词符号视为常元符号。量词只作用在个体变元上。
谓词语言的表达能力仍然有限！ 如下推理一阶语言不能表达： （1）
前提：自然数集的任何子集都有最小元。
A是自然数集的一个子集。 结论：A有最小元。
子集的描述可用一元谓词。“任何子集”的表达需要将谓词作为变元，用全称量词才能表达！
需要引入关系变元（二阶语言）： （2）
(?A)?(x)A[x?()?y(A)y(?( ?x)y前提：有算法就能用程序实现。
27
存在求解问题A的算法。 结论：存在求解问题A的程序。
算法和程序可用函数表达。“存在算法”的表达需要将函数作为变元，用存在量词才能表达！ 例1. 公式(?x)[F(x)?(?y)[(?z)G(y,z)?H(u,x,y)]的归纳生成过程。 （1）F(u1),G(u2,u3),H(u,u1,u2)
（2）(?z)G(u2,z)
（3）(?z)G(u2,z)?H(u,u1,u2)] （4）(?y)[(?z)G(y,z)?H(u,u1,y)] （5）F(u1)?(?y)[(?z)G(y,z)?H(u,u1,y)] （6）(?x)[F(x)?(?y)[(?z)G(y,z)?H(u,x,y)] 例2.自然语言陈述表达公式表达 （1）苏格拉底论断。
前提：所有的人要死。（(?x)[M(x)?D(x)]） 苏格拉底是人。（a：苏格拉底，M(a)）
结论：苏格拉底要死。D(a)
（2）前提：有人在教室看书则灯亮。（(?x)[R(x)?Q]）
张三在教室看书。（a：张三，R(a)） 结论：教室灯亮。（Q）
例3. 前提：相互认识的人是朋友。
(?x)(?x)[K(x,y)?F(x,y)] 张三和李四相互认识。
（a：张三，b：李四。K(a,b)）
结论：张三和李四是朋友。F(a,b)
28
例4. 每一个自然数都存在唯一后继。
存在性：N(u)?(?y)(N(y)?(y?s(u)))]
唯一性：(?z)(?w){([N(z)?(z?s(u))]?[N(w)?(w?s(u))])?(z?w)} 最后公式：
(?x){N(x)?[(?y)(N(y)?(y?s(x)))]? (?z)(?w){([N(z)?(z?s(x))]?[N(w)?(w?s(x))])?(z?w)}一元谓词N(x)作为特称（限定）谓词可以省去。
(?x){[(?y)(y?s(x))]?(?z)(?w){([(z?s(x))?(w?s(x))]?(z?w)}}
(?x){[(?y)(N(y)?(y?s(x)))]?(?z)(?w){([N(z)?(z?s(x))]
?[N(w)?(w?s(x))])?(z?w)}例5.三人行，必有我师。
含义：任意三个人中，有一位是我的老师。
(?x)(?y)(?z)[T(x,a)?T(y,a)?T(z,a)]
论域：人构成的集合。特称（限定）谓词M(x)。
习题：
P92：3.2.2, 3.2.4
29