1.6 变元约束

1、授课教师：程文刚 个体、谓词和量词 谓词公式与翻译 把一个文字叙述的命题，用谓词公式表示出来， 称为谓词逻辑的翻译或符号化，其步骤如下： 正确理解给定命题。必要时把命题改叙，使其中 每个原子命题、原子命题之间的关系能明显表达 出来。 把每个原子命题分解成个体、谓词和量词；在全 总论域讨论时，要给出特性谓词。 找出恰当量词。应注意全称量词(x)后跟条件式， 存在量词(x)后跟合取式。 用恰当的联结词把给定命题表示出来。 凡偶数均能被2整除 存在偶素数 没有不犯错误的人 在北京工作的未必都是北京人 闪闪发光的不都是金子 直线A与B平行当且仅当直线A和B不相交 对于两个点，有且仅有一条直线通过该两点

2、 那位戴眼睛的用功的大学生在看这本大而厚的巨著 并非一切劳动都能用机器代替 黛玉葬花,宝玉伤神,否则何为痴男怨女 生命诚可贵，爱情价更高，若为自由故，两者皆可抛 不管白猫黑猫，逮住老鼠就是好猫 习题解析 对于两个点，有且仅有一条直线通过该两点 解： 习题解析 黛玉葬花,宝玉伤神,否则何为痴男怨女。 解： 令 A(x): x葬花; B(x): x伤神; M(x):x是痴男; W(x) : x是怨女 a: 黛玉; b:宝玉; 本题符号化为: (A(a)B(b)(M(x)W(x) 习题解析 生命诚可贵，爱情价更高，若为自由故，两者皆可抛。 解： 令 M(x) : x是人; P(x): x是可贵的;

3、Q(x) : x是具有更高价值的; R(x, y) : x为y奋斗; S(x, y) : x抛弃y。 f(x): x的生命; g(x) : x的爱情; i: 我; j: 自由; 故： (x)(M(x)P(f(x)(x)(M(x)Q(g(x)(R(i,j)S(i,f(i)S(i,g(i) 习题解析 不管白猫黑猫，逮住老鼠就是好猫。 解： 令 C(x) : x是猫; M(x): x是老鼠; G(x): x是好猫; R(x, y) : x逮住y. 故： (x) (y)(C(x)M(y)R(x, y)G(x) (x) (C(x) (y)(M(y)R(x, y)G(x) 我骑着马儿过草原。 哥伦布发现了

4、新大陆。 沁园春雪是伟人毛泽东的名作。 苏格拉底有死论。 所有的学生都钦佩爱因斯坦。 不存在一个函数,它可导但不连续。 每一位母亲都爱她自己的孩子。 每个人的外公都是他母亲的父亲。 变元的约束 改名和代入规则 公式解释 公式类型 掌握辖域、约束变元和自由变元的概念及判别方法。 理解改名与代入规则，应用 学会在给定公式解释下，公式真值的求取方法 公式类型的判定方法 换名与代入的深刻理解与应用 几个名词 （1）指导变元（作用变元） （2）作用域（辖域） （3）约束出现 （4）约束变元、自由变元 定义2.3.1 给定一个谓词公式A，其中有一部分公 式形如(x)B(x)或(x)B(x)，则称它为A的x

5、约束部 分，称B(x)为相应量词的作用域或辖域。在辖域中， x的所有出现称为约束出现，x称为约束变元；B中 不是约束出现的其它个体变元的出现称为自由出现， 这些个体变元称自由变元。 通常，一个量词的辖域是某公式A的一部分，称为 A的子公式。因此，确定一个量词的辖域即是找出 位于该量词之后的相邻接的子公式，具体地讲： 若量词后有括号，则括号内的子公式就是该量词 的辖域； 若量词后无括号，则与量词邻接的子公式为该量 词的辖域。 判定给定公式A中个体变元是约束变元还是自由 变元，关键是要看它在A中是约束出现，还是自由 出现。 例：例： 说明以下各公式的作用域与变元的约束情况。说明以下各公式的作用域与

6、变元的约束情况。 a)a) ( ( x)(P(x)x)(P(x)Q(y)Q(y) (x)的作用域是P(x)Q(y)， x为约束变元。 b) (b) ( x)(P(x)x)(P(x)( ( y)y)(R(x,y)(R(x,y) (x)的作用域是(P(x)(y)(R(x,y)， (y)的作用域是R(x,y)。 x,y为约束变元。 指导变元指导变元 作用域 c) (c) ( x)(x)( y)(P(x,y)y)(P(x,y) Q(y,z)Q(y,z) ( ( x)Px)P(x,(x,y)y) (x)(y)的作用域是(P(x,y)Q(y,z) x,y为约束变元，z是自由变元。 (x)的作用域是P(x,

7、y) x为约束变元，y是自由变元。 常用元语言符号A(x)表示x是其中的一个个体变元 自由出现的任意公式，如A(x)可为P(x)Q(x)， P(x)(y)Q(x,y)等。一旦在A(x)前加上量词(x)或 (x)，即得公式(x)A(x),或(x)A(x)。这时，x即 是约束出现了。类似地，用A(x,y)表示x和y是自由 出现的公式。 定义2.3.2 设A为任意一个公式，若A中无自由出 现的个体变元，则称A为封闭的合式公式，简称 闭式。 由闭式定义可知，闭式中所有个体变元均为约束 出现。例如，(x)(P(x)Q(x)和 (x)(y)(P(x)Q(x,y)是闭式，而 (x)(P(x)Q(x,y)和(

8、y)(z)L(x,y,z)不是闭式。 就成为一个命题。 自由变元出现，则该式此如果谓词公式中没有 元谓词，因个变元进行约束则成为对其中 ，若个相互独立的自由变元元谓词，它有是 看出，从约束变元的概念可以 knk nn xxxP n , 21 具有相同的意义与同理 具有相同的意义与 yPyxPx yPyxPx 一个公式的约束变元所使用的名称符号是无关紧要 的 目的：使得一个变元在一个公式中只是一种形式出 现，即呈自由出现或呈约束出现 约束变元的换名规则约束变元的换名规则 (1) (1) 对于约束变元可以换名，其更改的变元名称范对于约束变元可以换名，其更改的变元名称范 围是量词中的指导变元，以及该

9、量词作用域中所出围是量词中的指导变元，以及该量词作用域中所出 现的该变元，在公式的其余部分不变。现的该变元，在公式的其余部分不变。 (2) (2) 换名时一定要为作用域中没有出现过的变元名换名时一定要为作用域中没有出现过的变元名 称。称。 例例: : 对对( ( x)(P(x)x)(P(x)R(x,y) R(x,y) Q(x,y) Q(x,y)换名。换名。 解：可换名为解：可换名为 ( ( z)(P(z)z)(P(z)R(z,y) R(z,y) Q(x,y) Q(x,y) 但不可换名为但不可换名为 ( ( y y)(P(y)(P(y)R(y,y) R(y,y) Q(x,y) Q(x,y) 或或

10、 ( ( z z)(P(z)(P(z)R(x,y) R(x,y) Q(x,y) Q(x,y) 自由变元的代入规则：自由变元的代入规则： (1)(1)对于自由变元可以代入，代入时需对公式中出现该自由对于自由变元可以代入，代入时需对公式中出现该自由 变元的每一处进行代入。变元的每一处进行代入。 (2)(2)用以代入的变元与原公式中的所有变元的名称不能相同。用以代入的变元与原公式中的所有变元的名称不能相同。 例：例： 对对( ( x)(P(y)x)(P(y) R(x,y)R(x,y)作自由变元代入。作自由变元代入。 解：解： 对对y y施行代入，得到：施行代入，得到： ( ( x)(P(z)x)(P

11、(z) R(x,z)R(x,z) 但是但是 ( ( x)(P(x)x)(P(x) R(x,x)R(x,x) 和和 ( ( x)(P(z)x)(P(z) R(x,y)R(x,y) 都是错误的。都是错误的。 改名规则与代入规则的共同点都是不能改变约束关 系，而不同点是： 施行的对象不同。改名是对约束变元施行，代入是 对自由变元施行。 施行的范围不同。改名可以只对公式中一个量词及 其辖域内施行，即只对公式的一个子公式施行；而 代入必须对整个公式同一个自由变元的所有自由出 现同时施行，即必须对整个公式施行。 施行后的结果不同。改名后，公式含义不变，因为 约束变元只改名为另一个个体变元，约束关系不改 变

12、。约束变元不能改名为个体常元；代入，不仅可 用另一个个体变元进行代入，并且也可用个体常元 去代入，从而使公式由具有普遍意义变为仅对该个 体常元有意义，即公式的含义改变了。 一般情况下，Lp中的公式含有：个体常元、个体变 元（约束变元或自由变元）、函数变元、谓词变元 等，对各种变元用指定的特殊常元去代替，就构成 了一个公式的解释。当然在给定的解释下，可以对 多个公式进行解释。下面给出解释的一般定义。 定义定义2.4.12.4.1 一个解释I由下面4部分组成： 非空个体域DI。 DI中部分特定元素a，b，。 DI上的特定一些函数f，g，。 DI上特定谓词：P，Q，。 在一个具体解释中，个体常元、函

13、数符号、谓词符号的数 量一般是有限的，并且其解释一旦确定下来就不再改变， 只是个体变元的值在个体域DI内变化，量词符或仅作用 于DI中的元素。 从以上两个例子中可以看出，有的公式在具体的解 释中真值确定，即为命题。有的公式在具体解释中 真值不确定，即不是命题。然而对闭式来说（上例 (1)-(4)），由于每个个体变元都受到量词的约束， 因而具体解释中总是表达一个意义明确的语句，即 是一个具有真值的命题，而不是闭式的公式(上例 (5)就不一定具有这种性质了。 定义定义2.4.22.4.2 若一公式在任何解释下都是真的，称该公式为逻辑有效 的，或永真的。 若一公式在任何解释下都是假的，称该公式为矛盾

14、式， 或永假式。 若一公式至少存在一个解释使其为真，称该公式为可满 足式。 从定义可知，逻辑有效式为可满足式，反之未必成 立。 与命题公式中分类一样，谓词公式也分为三种类型， 即逻辑有效式（或重言式）、矛盾式（或永假式） 和可满足式。 由于谓词公式的复杂性和解释的多样性，至今还没 有一个可行的算法判定任何公式的类型。早在 1936年，Churen和Turing各自独立地证明了：对 于Lp，其判定问题是不可解的。但是，Lp是个半个 可判定的，即若Lp中公式是重言式，则存在算法在 有限步骤内能验证它。当然，对于一些较为简单的 公式，或某些特殊公式，还是可以判定其类型的。 在2.3节中，介绍了自由变

15、元的代入规则，实际上代 入规则并非只局限于自由变元，对公式中命题变元、 谓词变元均可实施代入，其关键是不能因为代入而改 变原有公式的约束关系。谓词变元（包括命题变元） 的代入规则描述如下： 在一公式中，一个n元(n0)谓词变元 P(x1,x2,xn)可以代至少有n个自由变元的公式 B(y1,y2,yn,yn+1,yn+2,yn+r)，其中r0， y1,y2,yn是分别对应于x1,x2,xn的任意选 定的n个自由变元，且对P出现进行处处代入，B中的r 个自由变元不允许在原公式中以约束出现，P中的个 体变元也不允许在B中以约束出现。 为保证代入规则顺利而正确地实行，常常对约束变元 改名而适应之。 在公式( ( y y)(P)(PQ(y)Q(y)(P(P( ( y)y)Q(x)Q(x)中将中将P P代以代以 ( ( y)R(x,y)y)R(x,y)和和( ( x)R(x,y)x)R(x,y) 对公式对公式( ( y y)(P(x)(P(x)Q(y)Q(y)中谓词变元中谓词变元P(x)P(x)代以代以 ( ( x)(R(x)x)(R(x)S(y,z)S(y,z) 若原公式为永真式，则代入后仍为永真式； 若原公式为矛盾式，则代入后仍为矛盾式； 若原公式为可满足式，则带