《计算机数学基础—离散数学》谓词逻辑.doc

第2章 谓词逻辑一、教学要求1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将不太复杂的命题符号化。2. 掌握在有限个体域下求公式的真值和某些公式在给定解释下真值的方法，判别公式类型(永真式、永假式和可满足式)的方法。3. 掌握谓词演算的等值式和重言蕴含式 (六种情况：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词，的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式)。会进行谓词公式的等值演算。4. 了解前束范式的概念，会求公式的前束范式。5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(ES规则)；存在量词附加规则(EG规则)本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明。二、学习辅导在命题逻辑中，我们把原子命题作为基本研究单位，对原子命题不再进行分解，只有复合命题才可以分解，揭示了一些有效的推理过程. 但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去. 例如“凡人要死，张三是人，张三要死”显然是正确推理. 用命题逻辑解释三段式. 设P：人要死；Q张三是人；R：张三要死。表示成复合命题有 PQR这不是重言式，即R不是前提P，Q的有效结论. 这反映了命题逻辑的局限性，其原因是把本来有内在联系的命题P，Q，R，视为独立的命题。要反映这种内在联系，就要对命题逻辑进行分析，分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是谓词逻辑的研究内容。1. 谓词与量词学习这一部分要反复理解谓词和量词引入的意义，概念的含义。在谓词逻辑中，原子命题分解成个体词和谓词。个体词是可以独立存在的客体，它可以是具体事物或抽象的概念，如小张，房子，南京，大米，思想，实数2等等。谓词是用来刻划个体词的性质或事物之间的关系的词。例如(1) (1) ln5是无理数；(2) (2) 高可比李木相高4cm；(3) 郑州位于北京和广州之间。这时三个简单命题，其中ln5，高可，李木相，郑州，北京，广州等都是个体词，而“是无理数”，“比高4cm”，“位于和之间”等都是谓词。个体词分个体常项(用a,b,c,d,表示)和个体变项(用x,y,z,表示)；谓词分谓词常项(表示具体性质和关系的词)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,表示。个体常项a和个体变项都具有性质F，记作F(a)或F(x);个体常项a,与b或个体变项x与y具有关系L,记作L(a,b)或L(x,y)。一般地，用F(a)表示a是无理数，其中a表示ln5，F表示的是“是无理数”。当F的含义不变时，则F(x)表示x是无理数，x是个体变项，F谓词常项，F(x)不是命题，而是命题变项，F(a)是命题。用M(x,y,z)表示“z=xy”，M(x,y,z)不是命题。a表示3，b表示5，c表示15，M(a,b,c)表示“1535”。M(a,b,c)是命题，真值为1，若c=12，那么M(a,b,c)是命题，真值为0。注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题。例2.1 将下列命题符号化：(1) 丘华和李兵都是学生；(2) 2既是偶数又是素数；(3) 如果张华比黎明高，黎明比王宏高，则张华比王宏高。 解 (1) 设个体域是人的集合。 P(x)：:x是学生。a：丘华b：黎兵该命题符号化为P(a)P(b)(2) 设个体域为正整数集合N。F(x)：x是偶数，Q(x)：x是素数a：2该命题符号化为F(a)Q(a)(3) (3) 设个体域是人的集合。G(x,y)：x比y高。a：张华b：黎明c：王宏该命题符号化为G(a,b)G(b,c)G(a,c)量词是在命题中表示数量的词，量词有两类：全称量词，表示“所有的”或“每一个”；存在量词$，表示“存在某个”或“至少有一个”。例2.2 将下列命题符号化(1) (1) 每个母亲都爱自己的孩子；(2) 所有的人都呼吸；(3) 有某些实数是有理数。解 (1) 设个体域是所有母亲的集合。M(x)：x表示爱自己的孩子；该命题符号化为xM(x)。(2) 设个体域为人的集合。H(x)：x表示要呼吸。该命题符号化为xH(x)或设个体域为生物集合，M(x)：x是人。H(x)：x表示要呼吸。该命题符号化为x(M(x)H(x)(3) 设个体域为数的集合。R(x)：x表示实数Q(x)：x表示有理数。该命题符号化$x(R(x)Q(x)。在谓词逻辑，使用量词应注意以下几点：(1) (1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变。(2) (2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全个体域。 (3) (3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的涵义。 2. 公式与解释学习这一部分内容要侧重于能将谓词逻辑公式表达式中，量词消除写成与之等值的公式，然后将解释中的数值代入，求出真值，并着重理解在谓词和量词的作用下变元的自由性、约束性和更名规则、代入规则等。我们将命题常数0，1，一个命题和命题变元以及一个命题函数P(x1,x2,xn)，统称原子公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材)。命题的符号化结果都是谓词公式，例如x(F(x)G(x)，$x(F(x)G(x)，xy(F(x)F(y)L(x,y)H(x,y)等都是谓词公式，当然$x(F(x)G(x,y),x(F(x)G(x,y)等也是谓词公式。在谓词公式xA和$xA中，x是指导变元，A是相应量词的辖域。在x和$x的辖域A中，x的所有出现都是约束出现，即x是约束变元，不是约束出现的变元，就是自由变元。也就是说，量词后面的式子是辖域。量词只对辖域内的同一变元有效。例2.3 指出下列公式中量词的每次出现的辖域，并指出变元的每次出现是约束出现，还是自由出现，以及公式的约束变元，自由变元。(1) (2) 解 (1) 在公式中，x只有一次出现，辖域是；y只有一次出现，辖域是；$x只有一次出现，辖域是H(x,y)。变元x在公式中有四次出现，其中第一次出现是在x中的出现，是约束出现；第二次出现是在x的辖域中的出现，也是约束出现；第三次出现是在$x中的出现，也是约束出现；第四次出现是在$x的辖域中的出现，也是约束出现。这四次出现都是约束出现，所以x是该公式的约束变元。不是它的自由变元。变元y在公式中有四次出现。其中第一次是在y中的出现，是约束出现；第二次出现和第三次出现是在y的辖域中的出现，也是约束出现；第四次出现是自由出现。Y在该公式中有三次约束出现，一次自由出现，因此变元y既是该公式的约束变元，也是自由变元。变元z在该公式中只有一次自由出现，所以z是该公式的自由变元，约束也是变元。(2) 在公式中，x有二次出现，其第一次出现的辖域是；其第二次出现的辖域是。变元x在公式中有六次出现，其中第一次出现和第四次出现是在x中的出现，是约束出现；第二次出现和第三次出现是在x的第一次出现的辖域中的出现，是约束出现，第五次出现是在x的第二次出现的辖域中的出现，也是约束出现；x的第六次出现是自由出现。变元x在该公式中五次约束出现，一次自由出现。因此变元x既是该公式的约束变元，也是自由变元。从例3看到，同一个个体变项，在同一个公式中，既可以是约束出现，也可以是自由出现，这种情况有时会造成一些混淆，带来不变。要改变这种情况，使一个个体变项在同一个公式中不同时既是约束出现，又是自由出现，采取换名规则或代入规则。换名规则，就是把公式中量词的指导变元及其该量词的辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变。代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的该符号。如例3(1)中，变元y既是约束出现，又是自由出现，把约束变元y换名为u.。于是原公式换为 也可以将自由变元y代换为t，原公式变为都是与原公式等值的。例3(2)中，原公式换为是与原公式等值的，且个体变元符号不再相同。谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题。所谓解释就是使公式中的每一个变项都有个体域中的元素相对应。解释有四部分组成：(1) 非空个体域D；(2) D中有一部分特定元素，用来解释个体常项；(3) D上一些特定函数，用来解释出现的函数变项； (4) D上一些特定谓词，用来解释谓词变项。例2.4 给定解释I： D2,3; D中特定元素a=2； 函数为 谓词F(x)为F(2)=0,F(3)=1G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0求在解释I下各公式的真值。 (1) ;(2) ；(3) ；(4) 。解 设所求四个公式分别记作A，B，C，D。有 由例4的(3)，(4)可知，量词的次序不能随便颠倒。和命题逻辑一样，在谓词逻辑中，有的公式在任何解释下都真，也有的公式在任何解释下都假。以此，把公式分为三类：在任何解释下公式A为真，或者公式A的真值表全为1，这就是永真式；在任何解释下公式A为假，或者公式A的真值表全为0，这就是永假式；公式A不总是假，或者公式A的真值表至少有一个1，这就是可满足式。由此可见，永真式也是可满足式。一般地，判定一个公式是不是可满足式，还没有一定的算法。但是，可以证明，重言式的代换实例一定是永真式。而矛盾式的代换实例均为矛盾式。例2.5 讨论下列公式的类型：(1) ;(2)证明 设(1)，(2)的公式分别记作A，B。(1) 设I为任意一个解释，其个体域为D，若存在,使得F(x0)为假，则为假，从而A为真。若对于任意的,F(x)均为真。则与都为真。从而A也为真。故在解释I下A为真。由于I的任意性，所以A是永真式。(2) (2) 取解释I如下：个体域仍为自然数集，F(x,y)：x y。 在I下，B的前、后件均为真。所以B为真，这说明B不是是矛盾式；再取解释I：个体域认为N。F(x,y)：x=y。在解释I下，B的前件为真，后件为假。故B为假，这又说明B不是永真式。综上所述，B是非永真式的可满足式。3. 前束范式一个谓词公式的前束范式，仍然是谓词公式，只是把谓词公式的所有量词均提到公式的开头，而且它的辖域一直延伸到公式的末尾。如若一个谓词公式F等值地转化成那么就是谓词公式F的前束范式，其中Q1，Q2，Qk只能是或$，而x1,x2,xk是个体变元，B是不含量词的谓词公式。如等是前束范式，而等不是前束范式，因为没有把所有量词放到公式的开头。每个谓词公式F都可以变换成与它等值的前束范式。其步骤如下： 消去联结词，； 将联结词向内深入，使之只作用于原子谓词公式； 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同； 利用量词辖域的扩张和收缩律，扩大量词的辖域至整个公式； 利用分配律将公式化为前束范式。例2.6 将公式F化为前束范式。解 消去联结词，； 将联结词深入至原子公式 换名 把量词提到整个公式的前面为所求前束范式。重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换名规则，把一个谓词公式化为前束范式，虽然前束范式是谓词公式的一种标准形式，但是一般一个谓词公式的前束范式并不是唯一的。4.谓词逻辑的推理理论谓词演算的推理是命题演算推理的推广和扩充，命题演算中的一些规则，如基本等值公式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用。但是在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，必须在推理过程中，有消去和附加量词的规则，即US规则(全称量词消去规则)，UG规则(全称量词附加规则)，ES规则(存在量词消去规则)，EG规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行。例2.7 试证证明 方法1 等值演算法。要证明，只需证明的真值是1。证 方法2形式证明。 (PQ)R P RP CP (PQ)P ,I13假言三段式 (PQ)P ,E16 (PQ)P ,E8,E9,E1 P ,E14SP ,I6 ,CP例2.8 证明：证明 前提： 结论： (1) 附加前提 (2) (1) ,T,E (3) (2),ES(4) A(c) (3),T,E(5) B(c) (3),T,E (6) (4),EG (7) P(8) (6),(7),T,E(9) B(c) (8),US(10) (5),(9)矛盾式三、举例例1谓词公式中量词x的辖域是( )(A) (B) P(x) (C) (D) 答案：(C)解答：x后面的公式是。故应选择(C)。例2 设个体域为整数集，下列公式中其值为1的是( )(A) (B) (C) (D) 答案：(A)解答：任意一个整数x，都能找到yx，有x+y=0,故(A)式是永真式。 例3 设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y。那么命题“所有演员都佩服某些老师”符号化为( )(A) (B) (C) (D) 答案：(D)解答：将命题符号化为“”，故应选择(D)。注意：符号化为“”是不对的，它的意义是所有演员和某些老师，x佩服y。例4 在谓词演算中，P(a)是的有效结论，根据是 ( ) (A)US规则