第二章 一阶逻辑.doc

122.1 一阶逻辑基本概念 教学重点 量词的概念、谓词逻辑符号化的规则 教学目的1：使学生理解谓词逻辑的含义。 2：熟练掌握量词的意义。3：理解并学会应用一阶语言的概念及其中的逻辑符号化的规则。 教学准备 教学方法讲述法 课时安排二课时。 教学过程讲述：命题逻辑是逻辑理论的基础，是以命题为最小单元来分析研究推理理论的，现在来看如下日常生活中一个常见的推理。l 所有的人都是要死的；l 苏格拉底是人。l 所以，苏格拉底是要死的。符号化为： (pq) r显然这是一个推理，但是是不正确的推理。日常推理却是正确的。命题逻辑无法准确描述这个推理过程，原因在于命题逻辑本身未对各原子命题之间的内部成分的逻辑关系加以研究。为了更准确地对命题进行符号化，我们需要把一个逻辑判断的对象和谓语分离并细化，分析出其中的个体词、谓词和量词，研究它们的形式结构和逻辑关系，推理规则和推理形式，这就是本章的基本内容。本节主要讨论一阶逻辑（谓词逻辑）的基本概念。板书2.1 谓词逻辑基本概念讲述谓词逻辑是以谓词为基础的，类似以命题为基础的命题逻辑首先从命题开始，我们这里也必须先从谓词开始。在谓词逻辑中，需要将简单命题拆开，作为最为简单的命题的陈述句，至少有主语和谓语组成，谓词就是句子中相当谓语部分的词，而把主语对应的部分称为个体词。板书：一、个体词可以独立存在的具体或抽象的客体。个体常项（a,b,c）、个体变项(x,y,z)个体域：个体变项的取值范围。 全总个体域：将宇宙间的一切事物组成个体域。二、谓词表示个体词性质的或个体词之间相互关系的词谓词常项：表示具体性质或关系的谓词，用F、G、H表示谓词变项：表示抽象的、泛指的性质或关系的谓词，也用F、G、H表示n元谓词：含有n个个体的谓词n=0，0元谓词，不含有任何个体变项的谓词n=1，1元谓词，以此类推。示例1：H(a)，a：张华，H(x): “是学生”H(x)是1元谓词，不是命题，H(a)是0谓词，是命题，示例2：小魏乘机去深圳；设a：小魏， b：飞机，c：深圳；P(x, y, z)：x乘y去z；P(a, b, c)提问：如何分析下列公式：F(a)，F(x)，F(x，y)，F(a，b)，P（x1， x2，。xn）实质上：n元谓词P（x1， x2，。xn）可以看成以个体域为定义域，以T，F为值域的n元函数。当P为谓词常项，a1， a2，。an为个体常项时，P（a1， a2，。an）才是命题。示例3：（1）所有的人都要死的（2）有的人活百岁以上讲述：这两个命题中，除了个体词和谓词外，还有表示数量的词，称为量词板书：2 量词A 全称量词对应日常语言中的“一切”、“所有的”、“任意的”等词，以符号表示。x F(x)表示个体域里的所有个体都有性质F。B存在量词对应日常语言中的“存在着”、“有一个”、“至少有一个”等词，用符号$表示。形成的命题公式为$x F(x)，即“存在x值，使F(x)为真”。讲述：符号化之前必须先明确个体域板书：第一种情况，个体域D为人类集合。（1）x F(x)，其中F(x)：x是要死的（2）$x G(x)，其中G(x)：x活百岁以上第二种情况，个体域为全总个体域 这时必须引入一个特性谓词，M(x)：x是人（1）x(M(x) F(x)，其中F(x)：x是要死的（2）$x (M(x) G(x)，其中G(x)：x活百岁以上使用量词时，注意以下几点：（1） 在不同的个体域中，命题符号化的形式可能不一样。（2） 如果事先没有给出个体域，以全总个体域为个体域。（3） 引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。（4） 个体域和谓词的含义确定之后，n元谓词要转化为命题至少需要n个量词。例如：x P(x，y，z)是二元谓词，因为若D=a1 ,a2 ,an，x P(x，y，z) P(a1，y，z) P(a2，y，z) P(an，y，z)（5） 当个体域为有限集时，如D=a1 ,a2 ,an，对于任意的谓词A(x)，有x A(x) A(a1) A(a2) A(an)$x A(x) A(a1) A(a2) A(an)这就是将谓词逻辑中命题公式转化为命题逻辑中的命题公式问题，叫做消去量词等价式（6） 多个量词同时出现时，不能随意颠倒它们的顺序。比如：对于任意的x，存在着y，使得x+y=5。取个体域为实数集。命题符号化为：x$y H(x, y)，其中，H(x, y)：x+y=5。这是真命题如果将量词颠倒，变为$y x H(x, y)，意义与原意不符，成了假命题。板书：例：求下列各式的真值（1）。其中个体域；一元谓词，。（2）。其中个体域；一元谓词， 。（3）。其中个体域；零元谓词；一元谓词，；个体常元。解 根据量词的含义，我们有：（1） （2）（3） 下面举几个例子说明如何将命题符号化板书：例1：将下列命题符号化（1）所有的人都长着黑头发。（2）有的人登上过月球。（3）没有人登上过火星。（4）在美国留学的学生未必都是华人。解：本题没有指明个体域，我们这里采用全总个体域。并设一元谓词是人。（1）设长着黑头发。命题符号化为这是个假命题。（2）设登上过月球。命题符号化为或者这是个真命题。（3）设登上过火星。命题符号化为这是个真命题。（4）设是在美国留学的学生，是华人。命题符号化为或者例2：(1)兔子比乌龟跑的快(2)有的兔子比所有的乌龟跑的快(3)并不是所有的兔子都比乌龟跑得快(4)不存在跑得同样快的两只兔子例3：（1）火车比轮船快.（2）有些汽车比所有火车慢.解：1 F(x): x是火车，G(x): x是轮船，H(x, y): x比y快。 xy (F(x) G(y) H(x, y) 2 F(x): x是汽车，G(x): x是火车，H(x, y): x比y慢。 $x(F(x) y (G(y) H(x, y)或者$xy (F(x) (G(y) H(x, y)例3：形式逻辑中有：*是*，*不是*两句话，例如，“张三是教授”和“张三不是教授”。若其中一句是正确的，另一句就肯定不正确。请你构造出同时为真的两个句子。如：有些自然数是偶数，有些自然数不是偶数；符号化为：$xF(x) $xF(x)例4：当趋向时，函数以为极限的定义：“任给，存在，当时，有”。以实数集为个体域将该极限定义符号化。解 令二元谓词大于，则 表示： 表示：所以该极限定义表示为作业：P53，2.2，2.32.2一阶逻辑合式公式及解释 教学重点 公式解释与赋值的意义，等值演算的规则 教学目的1：使学生理解公式解释和赋值的含义。 2：熟习掌握等值演算的规则。3：理解并学会应用一阶语言及其中的逻辑符号化的规则。 教学准备 教学方法讲述法 课时安排二课时 教学过程讲述：上节讨论了谓词逻辑的谓词、量词、及符号化问题，按照命题逻辑讲述的顺序，下面需要涉及合式公式基本概念、公式的解释和分类，然后是等值演算，最后就是推理理论。 一、谓词公式1) 字母表：个体常元：a, b, c, , ai, bi, ci, (i1)；个体变元：x, y, z, , xi, yi, zi, (i1)；函数符号：f, g, h, , fi, gi, hi, (i1)；谓词符号：F, G, H, , Fi, Gi, Hi, (i1)；量词符号：, $；联结词：, , , , ；括号和逗号：( , ) , 。2) 项的递归定义： a) 个体常项和个体变项是项；b) 如果x1, x2, , xn是项，则fi(x1, x2, , xn)是项，其中fi(x1, x2, , xn)是x1, x2, , xn的函数；c）只有有限次地使用（1）（2）生成的符号串才是项。3) 合式公式（谓词公式）：原子公式：若P为不能再分解的一元或n元谓词，P(x)或P(x1, x2, , xn)为原子公式。合式公式的递归定义为：(1) 原子公式为合式公式；(2) 若A为合式公式，则A也是；(3) 若A、B为合式公式，则AB、AB、AB、AB也是；(4) 若A为合式公式，x为任意变元，则x A、$x A也是；(5) 只有有限次应用1)-4)构成的符号串，才是合式公式。例：说明表达式P(f(a)，b)(x)(P(f(x)，g(x，f(x)Q(x)二、 自由与约束在合式公式xA和$xA中，称x为指导变项，A为相应量词的辖域。在辖域中，x的所有出现称为约束出现，A中不是约束出现的其他变项的出现称为自由出现。约束变元：约束出现的变元自由变元：非约束变元的变元。示例1：x(P(x) Q(y)R(y) 答：的辖域是P(x)Q(y)，指导变元是x。 整个公式中，x 是约束出现，受x 的约束，y是自由出现示例2：(x P(x,y) R(y,z) y Q(y) 答：的指导变元是 x ，辖域是 P(x,y) (x P(x, y) R(y, z)中，是 x 约束出现且受x 的约束， y，z 是自由出现。 y Q(y)中，的指导变元是 y ，辖域是 Q(y) ， y 是约束出现。 整个公式中， x 约束出现， y 既有约束出现又有自由出现， z 是自由出现。 在一个公式中，某一个体变元既可以自由出现，又可以约束出现。为了研究方便，而不致引起混淆，我们希望一个个体变元在同一个公式中只以一种身份出现，应用下面两条规则可以做到这一点。1、约束变元的换名规则将量词辖域中出现的某个约束变元及相应的指导变元，换成一个在辖域中未曾出现过的个体变元名。公式的其余部分不变。例如：(x P(x,y)R(y,z) )y Q(y) 用代替y Q(y)中出现的y,变成 (x P(x,y)R(y,z) )Q()2、自由变元的替换规则对于谓词公式中出现该自由变元的每一处，都使用同一个未在公式中出现过的变元替代。例如：(x P(x,y)R(y,z) y Q(y) 用代替(x P(x,y)R(y,z)中的y： (x P(x, )R(, z) )y Q(y)如果合式公式A中无自由变元，则称A是封闭的。三、闭式 设A为任一公式，若A中无自由出现的个体变项，则称A是封闭的合式公式，简称闭式。 闭式的重要性质：闭式在任何解释下不是真就是假，不可能给出解释I，使得闭式在I下真值不确定，这是闭式的一个重要特征。 例如：x$y H(x,y)，xy(F(x)F(y)L(x,y),x(F(x) G(x)F(a) G(a) 都是闭式。例：将下列两个公式中的变项指定为常项使其成为命题：(1)x(F(x)G(x) (2) xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y) 解(1)个体域 F(x) G(x) 命题 真值 全总 x是人 x是黄种人 所有人都是黄种人 1 实数 x是自然数 x是整数 所有自然数都是整数 0 (2)含两个2元函数变项，一个1元谓词变项，两个2元谓词变项。个体域 F(x) G(x, y) H(x, y) f(x, y) g(x, y) 全总 x是实数 xy xy x2+y2 2xy命题1：对于任意的x，y，若x与y都是实数且xy，则x2+y22xy.真值为真。讲述：对各种变项的指定也称为对它们的解释。这里是先给出公式再对它们进行解释，也可以先给出解释，再去解释各种公式。 四、谓词逻辑公式的解释和分类1、公式A的一个解释：对公式A指定其中个体域的范围，并指定其中谓词的具体含义使其成为命题， 一个一阶语言中公式的解释I包含：1) 非空个体域DI；2) 个体域DI中一部分特定元素的集合a1, a2, , ai, ；3) DI上的函数集合 fi | i1，且所有函数的定义域和值域均为DI；4) DI上的谓词集合 Fi | i1；例子见P44，例2.7，2.82、公式的分类逻辑有效式或永真式：在任何解释中都为真的谓词公式示例xP(x) $x P(x)xP$xP矛盾式或永假式：在任何解释中都为假的谓词公式可满足式：至少有一个解释能满足的谓词公式讲述：显然，判定一个谓词公式是否为逻辑有效式或矛盾式，都要求所有的解释满足或不满足该公式，而解释依赖一个非空集合D，从后面集合的概念可以知道，集合可以是无限集，而且各集合可不同，也有无数个，这样解释的“所有”含义实际是无法考虑的，这使得谓词公式的永假、永真的判断实际是异常的困难，在1936年，丘吉(A. Church)和图灵(A. Turing)分别证明了“谓词逻辑的永假或永真问题是不可判定的。”不过，幸好只要谓词公式确实是永真的、或永假的，则有算法可在有限步内判定这个事实。五、代换实例设A0是含有命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai(1in)处处代替A0中的pi，所得公式A称为A0的代换实例。例如，F(x)G(x), xF(x)$yG(y)等都是pq的代换实例，而x(F(x)G(x)等不是pq的代换实例。*重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。例子见P45，例2.92.3 一阶逻辑等值式讲述：在讨论过公式的分类后，接下来应该讨论两大应用问题，当然最终目的还是其中之一：逻辑推理。首先讨论等值演算的问题。板书：一、等值式概念：设A、B是谓词逻辑中任意的两谓词公式，若AB为逻辑有效式，则称A与B是等值的，记作AB，称“AB”为谓词逻辑等值式(Equivalent)。由于重言式及其代换实例都是逻辑有效式，因而命题逻辑中所提到的等值式及其代换实例都是谓词逻辑中的等值式。例xF(x)xF(x)xF(x)是等值式，对应于AAA；xF(x)xG(x)与xF(x)xG(x)对应于ABAB，也是等值的。在谓词逻辑中也有置换规则：设是含公式A的命题公式，是用公式B置换了中的A之后得到的命题公式，如果则。还有一些应用上很重要的等值式。1、量词否定等值式：(1) x P(x) $x P(x)(2) $x P(x) x P(x)当个体域为有限集时，如何验证？当给定个体域D为有限集时，比如D=a1,a2,，an，定理2.3-1的两个等值式是容易验证的。xA(x)(A(a1)A(a2)A(an)A(a1)A(a2)A(an)xA(x)；xA(x)(A(a1)A(a2)A(an)A(a1)A(a2)A(an)xA(x)。2、量词辖域扩大或缩小的等值式：(1) x (P(x) Q) (x (P(x) Q)(2) x (P(x) Q) (x (P(x) Q)(3) x (P(x) Q) x P(x) Q(4) x (Q P(x) Q x P(x)(5) $x (P(x) Q) ($x (P(x) Q)(6) $x (P(x) Q) ($x (P(x) Q)(7) $x (P(x) Q) x P(x) Q(8) $x (Q P(x) Q $x P(x)3、有关量词分配的等值式：(1) $x (P(x) Q(x) $x P(x) $x Q(x)(2) $x (P(x) Q(x) $x P(x) $x Q(x)4、（1）x yP(x，y) y x P(x，y) （2）$x $yP(x，y) $y $x P(x，y)5、有关蕴涵式的等值式：(1) $x (P(x) Q(x) x P(x) $x Q(x)(2) $x P(x) x Q(x) x (P(x) Q(x)在命题演算中有时需将命题公式化成与之等价的规范形式, 在谓词演算中也需将谓词公式化成与之等价的规范形式。6、前束范式一个谓词公式中, 如果量词都在公式的开头, 而它们的作用域延伸至整个公式的末尾, 则称该公式为前束范式。例如, (x)(y)($z)(Q(x, y)R(z), (y)(x)(P(x, y)Q(y