离散数学基础 (8)

等值变换关系。 [5]. 用Z(x)表示x是一个整数，则可符号化为： (?x)(Z(x) ? (?y)(Z(y) ? (x>y) ) ) [6]. 符号化为：(??)((? > 0)?(?? )((? >0) ? ((|x-a|

【例子2.4】将下列命题符号化： [1]. 每一个有理数都是实数 [2]. 某些实数是有理数 [3]. 不是没一个实数都是有理数 [4]. 存在偶素数 [5]. 会叫的狗未必会咬人 [6]. 每个人的外祖母都是他母亲的母亲 [7]. 任何自然数的后继数必大于零 [8]. 有些液体能溶解任何金属 [9]. 任何金属均可溶解于某种液体中 [10]. 没有不犯错误的人 [11]. 小莉是非常聪明和美丽的 [12]. 小李是一个田径运动员

【解答】（请同学们下载后，先思考，课堂上讲解）

【例子2.5】将下列公式翻译成自然语言，并确定其真值，这里假定个体域是正整数： [1]. (?x)(?y)G(x, y)，其中G(x, y)表示：x * y = y。 [2]. (?x)(?y)F(x, y)，其中F(x, y)表示：x + y = y。 [3]. (?x)(?y)H(x, y)，其中H(x, y)表示：x + y = x。 [4]. (?x)(?y)L(x, y)，其中L(x, y)表示：x * y = x。 [5]. (?x)(?y)M(x, y)，其中M(x, y)表示：x * y = 1。 [6]. (?x)(?y)N(x, y)，其中N(x, y)表示：y = 2 * x。 【解答】（请同学们下载后，先思考，课堂上讲解） 【例子2.6】给定下述谓词，请把下列公式翻译成自然语言： P(x): x是素数 E(x): x是偶数 Q(x): x是奇数 N(x, y): x可以整除y [1]. P(5)

[2]. E(2)?P(2)

[3]. (?x)(N(2, x)?E(x)) [4]. (?x)(E(x)?N(x, 6))

[5]. (?x)(?E(x) ? ?N(2, x))

[6]. (?x)(E(x)?(?y)(N(x, y)?E(y))) [7]. (?x)(P(x)?(?y)(Q(y)?N(y, x))) [8]. (?x)(Q(x)?(?y)(E(y)??N(y, x))) 【解答】（请同学们下载后，先思考，课堂上讲解）

作业：教材p101-102的1, 2。

31

3. 一阶逻辑公式及解释

每个系统有它自己的符号表，由这些符号表所构成的某些符号串是该系统中的语言，也是我们所研究的目标语言。

【定义2.3】一阶逻辑语言的符号包括：

[1]. 个体常项：通常用排在前面的小写字母表示，a, b, c, …, ai, bi, ci, … [2]. 个体变项：通常用排在后面的小写字母表示，x, y, z, …, xi, yi, zi, … [3]. 函数符号：通常用排在中间的小写字母表示，f, g, h, …, fi, gi, hi, … [4]. 谓词符号：通常用排在中间的大写字母表示，F, G, H, …, Fi, Gi, Hi, … [5]. 量词符号：全称量词?、存在量词? [6]. 联结符号：?、?、?、?、? [7]. 辅助符号：(、)、,(逗号)

【注解】

1. 上述符号可分为两大类，一类是非逻辑符号，包括个体常项、函数符号、谓词符号等，一类是逻辑符号，包括个体变项、量词符号、联结符号、辅助符号等。

2. 在命题逻辑只有逻辑符号，而没有任何非逻辑符号，命题逻辑中的命题常项和命题变量的区分是非本质的，对于命题逻辑本身来说没有什么意义，正如在一阶逻辑中，谓词常项和谓词变项的区分也是非本质的，对于一阶逻辑来说没有什么意义，但个体常项和个体变项的区分是本质的，对于一阶逻辑来说有重要的意义。

3. 一阶逻辑中的逻辑符号对于将一阶逻辑应用于任何问题时都是通用的、不变的，而其中的非逻辑符号则在不同的应用问题（或者说不同的讨论范围）中有所不同，可以变化，因此一阶逻辑语言的表达能力是非常强的，它可通过采用不同的非逻辑符号来增强自己的表达能力。

【定义2.4】一阶逻辑语言的项(term)递归定义为： [1]. 个体常项和个体变项是项；

[2]. 若f (x1, x2, …, xn)是n元函数，t1, t2, …, tn是n个项，则f (t1, t2, …, tn)是项； [3]. 一阶逻辑语言的所有项都通过有限次使用上述两步生成。

【定义2.5】一阶逻辑语言的合式公式(well-formed formula)递归定义为：

[1]. 若F(x1, x2, …, xn)是n元谓词，t1, t2, …, tn是n个项，则F(t1, t2, …, tn)是合式公式，此类合式公式称为原子公式；

[2]. 若A、B是合式公式，则(?A)、(A?B)、(A?B)、(A?B)、(A?B)也是合式公式； [3]. 若A是合式公式，则(?x)A、(?x)A也是合式公式；

[4]. 一阶逻辑语言的所有公式都通过有限次使用上述步骤生成。

通常用r, s, t, ri, si, ti, …等表示项，而用A, B, C, …Ai, Bi, Ci, …表示合式公式。 【注解】

1. 一阶逻辑语言的合式公式随着采用不同的非逻辑符号而不同，但对于不同的非逻辑符号采用相同的方式构造公式，一旦非逻辑符号确定之后，则一阶逻辑公式也就确定下来了，所以可以说一阶逻辑公式是某个非逻辑符号集生成的语言。

2. 虽然说采用不同的非逻辑符号可生成不同的一阶逻辑公式，但所有一阶逻辑公式的逻辑符号是相同的，而我们在这里对一阶逻辑的讨论只是讨论这些逻辑符号的性质，而与非逻辑符号无关，则我们的讨论对于任意的非逻辑符号生成的一阶逻辑公式都是成立的。

3. 一阶逻辑语言的直观意义容易理解：“符号表”相当于英语的字母表，“项”相当于单词或词组，它们不表达完整的判断，还只是代表个体，而“公式”则代表完整的句子。而其中的函数符号用来构造复杂的个体（项），谓词符号则用来构造最原子的公式。

32

4. 在定义2.5的[4]中，没有要求个体变项x一定要出现在合式公式A中，因此下述符号串都是合式公式：(?x)F(x, y)、(?z)F(x, y)。

5. 可通过假设联结符号及量词之间的优先级而去掉一些括号，使得公式的书写更为简洁，约定：

(1). 公式的最外层括号可省略； (2). 联结词?的优先级高于?，而?高于?，?高于?，?高于?，所以公式： ?F(x, y)?Q(y, z)??F(y, z)?G(y, x)?Q(x, z)?F(y, z)

表示：(((((?F(x, y))?Q(y, z))?(?F(y, z)))?G(y, x))?(Q(x, z)?F(y, z)))，但通常在书写时也不可将所有的括号省略，应该既比较简洁，又比较容易理解，例如上述公式可写成：

((?F(x, y)?Q(y, z)??F(y, z)) ? G(y, x)) ? (Q(x, z)?F(y, z))

由于一阶逻辑语言的公式比较复杂，其中的括号比较多，请注意讲究书写的方法。 (3). A1?A2?…?An-1?An表示(A1?(A2?…?(An-1?An)…))。 (4). 量词的优先级高于任何联结符号，所以(?x)A、(?x)A可分别写成?xA、?xA，但要注意明确量词的辖域（下面定义什么是辖域）。

【定义2.6】称公式(?x)A中的A为量词(?x)的辖域(scope)，称公式(?x)A中的A为量词(?x)的辖域。称变元x在公式A中的某处出现是约束出现，如果该出现处于量词(?x)或(?x)的辖域内，或者就是量词中的x。若x在公式A中的某处出现不是约束出现，则此出现称为自由出现。 【例子2.7】(教材p76的例2.6。)指出下列公式中，各量词的辖域以及变元的自由出现和约束出现：

[1]. ?x(F(x, y, z)??yG(x, y)) [2]. ?xF(x, y)?G(x, y) [3]. ?x?y(F(x)?G(y)?H(x, y)) 【解答】 [1]. 量词?x的辖域为：(F(x, y, z)??yG(x, y))，而量词?y的辖域为G(x, y)。变元的自由出现和约束出现分别为： ?x (F( x, y, z) ? ?y G(x, y)) ? ? ? ? ? ? ? 约束 约束 自由 自由 约束 约束 约束 [2]. 量词?x的辖域为：F(x, y)。变元的自由出现和约束出现分别为： ?x F( x, y) ? G(x, y) ? ? ? ? ? 约束 约束 自由 自由 自由 [3]. 量词?x的辖域为：?y(F(x)?G(y)?H(x, y))，量词?y的辖域为(F(x)?G(y)?H(x, y))。变元的自由出现和约束出现分别为：

?x ?y (F(x) ? G(y)?H(x, y))

? ? ? ? ? ? 约束 约束 约束 约束 约束 约束

【定义2.7】设变元x在公式A中出现，如果x在A中的所有出现都是约束出现，则称x为A的约束变元(bounded variable)，否则称x为A的自由变元(free variable)。

【注解】 1. 变元x在公式A中可同时有约束出现和自由出现两种情况，而只有当x的所有出现都是约束出现时，称x为A的约束变元。 2. 为了明确起见，我们通常在用字母A, B, C, …表示一阶逻辑公式时，同时列出该公

33

式中的自由变元，而写成A(x1, x2, …, xn)等，表示公式A中的所有自由变元皆在x1, x2, …, xn中。 3. 为了清晰起见，通常运用换名规则和替换规则使得公式A满足下列条件： (1). 所有变元在公式A中要么自由出现，要么约束出现，不要既有自由出现，又有约束出现。 (2). 所有量词后面采用的约束变元互不相同。量词后面的约束变元只在它的辖域里有意义，处于其辖域以外的同名变元与该约束变元实际上无关。所以不同量词采用不同约束变元是可以的，而且也是必要的。进一步变元的辖域实际上是可嵌套的，例如对于公式： ?x(F(x)??x(G(x)?F(x)))

其中量词?x的辖域为：(F(x)??x(G(x)?F(x)))，而量词?x的辖域为(G(x)?F(x))。实际上在子公式(G(x)?F(x))中的x被量词?x约束，而不是被量词?x约束。实际上，上述公式等价于：

?x(F(x)??y(G(y)?F(y)))

在使用一阶逻辑公式符号化命题时，要小心地选择变元，以使得到的公式满足上述两个条件。

【定理2.8】约束变元换名规则和自由变元替换规则：

[1]. 换名规则：对于公式(?x)A或(?x)A，设变元y不在A中出现，则将其中(?x)或(?x)改为(?y)或(?y)，且将A中出现的所有x都改为y，得到公式(?y)A或(?y)A与原公式等价。 [2]. 替换规则：对于公式A(x)，设y不在A中出现，将其中所有自由出现的x改为y，得到公式A(y)与原公式等价。

【注解】 1. 这里的等价于后面要讲的等值（目前可参考命题逻辑公式的等值）不一样，等值建立在某种解释下，而这里的等价只与语法有关，换名规则和替换规则只是在某种意义上说明公式中使用的变元是可任意选择的，选择不同的变元对于公式的本质没什么改变，就象在编写同一程序时，不同的程序员给具有同样功能的变量起不同名字一样，不影响程序本身的功能。

【例子2.8】使用换名规则和替换规则变换下列公式，使得满足定义2.7 的注解3中的两个条件：

[1]. (?x)((P(x)?R(x))?S(x))?(?x)(P(x)?Q(x)) [2]. (?x)(P(x)?Q(x))?(?x)R(x)?S(x) [3]. (?x)P(x)?(?x)Q(x)?((?x)P(x)?Q(x)) 【解答】首先确定量词的辖域，然后确定变元的约束出现和自由出现，再进行变换： [1]. (?x)的辖域是((P(x)?R(x))?S(x))，其中的x都是约束出现，而(?x)的辖域是(P(x)?Q(x))，其中的x是约束出现。为了使得不同量词后面的变元不同，可将(?x)(P(x)?Q(x))中的x换名为y，得到：(?x)((P(x)?R(x))?S(x))?(?y)(P(y)?Q(y))。 [2]. (?x)的辖域是(P(x)?Q(x))，其中的x是约束出现，而(?x)的辖域是P(x)，其中的x是约束出现，而最后S(x)中的x是自由出现。为了满足上述两个条件，可将(?x)R(x)中的x换名为y，而将S(x)中的x替换为z，得到：(?x)(P(x)?Q(x))?(?y)R(y)?S(z)。 [3]. 第一个(?x)的辖域是P(x)，而(?x)的辖域是Q(x)，第二个(?x)的辖域是P(x)，而最后Q(x)中的x是自由出现。为满足上述两个条件，可将(?x)Q(x)中的x换名为y，而将 (?x)P(x)中的x换名为z，最后将Q(x)中的x替换为u，得到：(?x)P(x)?(?y)Q(y)?((?z)P(z)?Q(u))。

【定义2.9】如果公式A没有自由变元，则称公式A为闭公式(closed formula)。

34

一阶逻辑公式的含义（解释）显然比命题逻辑公式要复杂得多，因为一阶逻辑公式有非逻辑的符号。对于一阶逻辑公式的解释依赖于一阶逻辑公式所基于的非逻辑符号。 设有非逻辑符号集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))

35

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究离散数学基础 (8)全文阅读和word下载服务。