离散数学discrete2D..doc

3. 一阶逻辑公式及解释(续) 一阶逻辑公式的含义（解释）显然比命题逻辑公式要复杂得多，因为一阶逻辑公式有非逻辑的符号。对于一阶逻辑公式的解释依赖于一阶逻辑公式所基于的非逻辑符号。 设有非逻辑符号集L，它由三部分组成L = C ( F ( P： (1). 个体常项所组成的集合C = {c1, c2, …, cn, …}； (2). 函数符号所组成的集合F = { f1, f2, …, fn, …}，每个函数fi有一个元数n，表明它是n元函数； (3). 谓词符号所组成的集合P = {F1, F2, …, Fn, …}，每个谓词Fi有一个元数n，表明它是n元谓词。 由该非逻辑符号集L生成的项可记为Term(L)，生成的公式可记为Form(L)。为了确定Form(L)中公式的真值，先要给出非逻辑符号集L的解释。 【定义2.10】非逻辑符号集L的一个解释[[L]]由四个部分组成： [1]. 一个非空集合D，D称为解释[[L]]的论域； [2]. 对于C的个体常项c，其解释为[[c]]( D是D中的某个元素； [3]. 对于F的n元函数f，其解释是D上的一个n元函数：[[f ]] : Dn(D； [4]. 对于P的n元谓词F，其解释是D上的一个n元关系：[[F]] ( Dn(= D (..( D) 【注解】 1. 定义2.10所给出的解释方法是对非逻辑符号集的一种最直观的解释，称为非逻辑符号集L的塔斯基(Tarski)语义，塔斯基是研究语义学的一个最有名的学者，这种语义解释方法在各种自然语言及形式语言的语义研究中也被广泛使用。 2. 对L的一个解释也可看成是为L构造了一个模型，研究一个形式语言的模型的有关内容构成了数理逻辑的一个重要分支：模型论(Model Theory)。 3. 教材p79的定义2.7给出的定义实际是一个不严谨的、直观的定义，因为教材在此之前没有引进函数、关系等概念。该定义的本质与我们这里的定义是一致的，因此根据书上的记号，我们也用符号I来表示某个解释。要说明的是，教材例2.7中所给定的谓词F的为F(2) = 0, F(3) = 1，实际上是表示F = {3}(D1(={2, 3})，是一个一元关系，而G(2, 2) = G(2, 3) = G(3, 2) = 1, G(3, 3) = 0，表明G = {2, 2, 2, 3, 3, 2} (D1(D1，是一个二元关系。 4. 给定一阶语言，我们可以构造它的一个解释，我们也可以给定一个解释所需的东西，然后研究公式的真值，这种研究实际上从某种意义说是对解释的形式化研究。 5. 只给出解释还不能确定Form(L)中的公式的真值，因为公式中可能存在自由变元，必需为这些自由变元指派具体的个体，不指定具体的个体，则带有自由变元的公式还不能成为命题逻辑的公式。教材p81例2.8中的(5)没有真值就是因为它存在自由变元。 6. 以下定义2.11到定义2.14为选学内容，读者如果不理解则可按书上的更直观的定义来学习定义2.14以后的内容。 【定义2.11】给定非逻辑符号集L的一个解释[[L]]，其论域为D。设公式集Form(L)中出现个体变元集为Var = {x1, x2, …, xn, …}。公式集Form(L)在解释[[L]]下的一个指派(是函数( : Var ( D，((xi)称为xi在指派下的值。 【假定与记号】个体变元指派了值之后，就可以归纳定义项的值。在本节后面的定义中，我们总是假定非逻辑符号集是L，它生成的项集合为Term(L)，生成的公式集为Form(L)，公式集Form(L)中出现个体变元集为Var = {x1, x2, …, xn, …}。L的一个解释是[[L]]，其论域为D，Form(L)在该解释下的一个指派是(。 【定义2.12】项t在指派的值((t)( D归纳定义为： [1]. 若t是个体变元xi，则((t) = ((xi)； [2]. 若t是个体常项c，则((c) = [[c]]； [3]. 若t是f (t1, t2, …, tn)，则(( f(t1, t2, …, tn)) = [[f ]](((t1), ((t2), …, ((tn)) 注意在对指派(的定义2.11中，定义了对出现在Form(L)中每个个体变元都指派一个值，但实际上，只要对Form(L)中的自由变元指派值就可以了。不过如果指派(只定义在自由变元上，则不好归纳定义项t的值了，因为无法断定项t中的变元是自由变元还是约束变元。为了区分指派(对约束变元和自由变元的定义的不同，引入如下概念： 【定义2.13】设(是在上述假定与记号下的指派，xi是一个个体变元，a( D，定义Form(L)在解释[[L]]下的指派([xi /a]是： [1]. ([xi /a](