离散数学左孝凌 课件.ppt

计算机学院,第二章 谓词逻辑（Predicate Logic）,2-1谓词的概念与表示2-2 命题函数与量词2-3谓词公式与翻译2-4变元的约束2-5谓词演算的等价式与蕴含式2-7前束范式2-7谓词演算的推理理论,计算机学院,第二章 谓词逻辑（Predicate Logic）2-1 谓词的概念与表示(Predicate and Its Expression),命题逻辑的局限性：在命题逻辑中，命题是命题演算的基本单位，不再对原子命题进行分解，因而无法研究命题的内部结构、成分及命题之间的内在联系，甚至无法处理一些简单而又常见的推理过程。,计算机学院,例如，下列推理：所有的人都是要死的。苏格拉底是人。苏格拉底是要死的。众所周知,这是真命题。但在命题逻辑中,如果用P,Q,R表示以上三个命题，则上述推理过程为：（PQ）R。借助命题演算的推理理论不能证明其为重言式。,第二章 谓词逻辑（Predicate Logic）2-1 谓词的概念与表示(Predicate and Its Expression),计算机学院,第二章 谓词逻辑（Predicate Logic）2-1 谓词的概念与表示(Predicate and Its Expression),原因：命题逻辑不能将命题之间的内在联系和数量关系反映出来。解决办法：将命题进行分解。,计算机学院,第二章 谓词逻辑（Predicate Logic）2.1 谓词的概念与表示(Predicate and Its Expression),2-1谓词的概念与表示(Predicate and its expression)2-1.1 客体和谓词 在谓词逻辑中，可将原子命题划分为客体和谓词两部分。客体：可以独立存在的具体事物的或抽象的概念。例如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等，客体也可称之为主语。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-1 谓词的概念与表示(Predicate and Its Expression),谓词：用来刻划客体的性质或客体之间的相互关系的词。例如在下面命题中：（1）张明是个劳动模范。（2）李华是个劳动模范。刻划客体的性质（3）王红是个大学生。（4）小李比小赵高2cm。（5）点a在b与c之间。刻划客体之间的相互关系（6）阿杜与阿寺同岁。“是个劳动模范”、“是个大学生”、“比高2cm”、“在与之间”都是谓词。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-1 谓词的概念与表示(Predicate and Its Expression),刻划一个客体性质的词称之为一元谓词,刻划n个客体之间关系的词称之为n元谓词.一般我们用大写英文字母表示谓词，用小写英文字母表示客体名称，例如，将上述谓词分别记作大写字母F、G、H、R，S则上述命题可表示为：(1)F(a)a：张明(2)F(b)b：李华(3)G(c)c：王红(4)H(s,t)s：小李 t：小赵(5)R(a,b,c)(6)S(a,b)a:阿杜。b:阿寺。其中(1)、(2)、(3)为一元谓词，(4)、(6)为二元谓词，(5)为三元谓词。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-1 谓词的概念与表示(Predicate and Its Expression),注:(1)单独一个谓词并不是命题，在谓词字母后填上客体所得到的式子称之为谓词填式。(2)在谓词填式中，若客体确定，则A(a1，a2.an)就变成了命题(3)在多元谓词表达式中，客体字母出现的先后次序与事先约定有关,一般不可以随意交换位置(如,上例中H(s,t)与H(t,s)代表两个不同的命题)。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-1 谓词的概念与表示(Predicate and Its Expression),设谓词H表示“是劳动模范”,a表示客体名称张明,b表示客体名称李华,c表示客体名称这只老虎，那么H(a)、H(b)、H(c)表示三个不同的命题,但它们有一个共同的形式,即H(x).一般地，H(x)表示客体x具有性质H。这里x表示抽象的或泛指的客体，称为客体变元，常用小写英文字母x,y,z,表示。相应地，表示具体或特定的客体的词称为客体常项，常用小写英文字母a,b,c,表示。,计算机学院,2-1 谓词的概念与表示(Predicate and Its Expression),同理，客体变元x，y具有关系L，记作L(x,y);客体变元x,y,z具有关系A，记作A(x,y,z).,H(x)、L(x,y)、A(x,y,z)本身并不是一个命题.只有用特定的客体取代客体变元x,y,z后，它们才成为命题。,计算机学院,2-2 命题函数与量词,2-2.1 命题函数一般来说，当谓词P给定，x1,x2,xn是客体变元，P(x1,x2,xn)不是一个命题，因为他的真值无法确定，要想使它成为命题，要用n个客体常项代替n个客体变元。P(x1,x2,xn)就是命题函数。比如L(x,y)表示“x小于y”，那么L(2,3)表示了一个真命题“2小于3”。而 L(5,1)表示了一个假命题“5小于1”,计算机学院,2-2.1 命题函数,定义2-2.1：简单命题函数(simple propositional function)：由一个谓词，一些客体变元组成的表达式称为简单命题函数。比如：A(x)，B(x,y)，L(x,y,z)简单命题函数不是命题，只有当变元x,y,z等取特定的客体才确定了一个命题。对于n元谓词，当n=0时，称为0元谓词，它本身就是一个命题，故命题是n元谓词的一个特殊情况。,计算机学院,2-2.1 命题函数,比如：L(x,y)表示“x小于y”是二元谓词，L(x,3)表示“x小于3”是一元谓词，L(2,3)表示“2小于3”是0元谓词。因此可以将命题看成n元谓词的一个特殊情况。0元谓词都是命题，命题逻辑中的简单命题都可以用0元谓词表示。,计算机学院,2-2.1 命题函数,定义2-2.2：复合命题函数（compound propositional function）：由一个或n个简单命题函数以及逻辑联结词组合而成的表达式。命题逻辑中的联结词在谓词逻辑中含义完全相同。举例说明：P56例，例,计算机学院,2-2.1 命题函数,定义2-2.3：谓词填式单独一个谓词不是完整的命题，把谓词字母以客体填后所得的式子称为谓词填式。例如：P(x)表示x3，则P(1)、P(2)、P(5)分别表示1大于3，2大于3，5大于3，P(1)、P(2)、P(5)即是谓词填式。,计算机学院,2-2.1 命题函数,定义2-2.4：谓词表达式简单命题函数与逻辑联结词组合而成。示例分析 P59(1)a),b),c)设W(x):x是工人，z:小张，则原命题表示为：W(z)设S(x):x是田径运动员，B(x):x是球类运动员，h:他，则原命题表示为：S(h)B(h)设C(x):x是聪明的，B(x):x是美丽的，a:小莉，则原命题表示为：C(a)B(a),计算机学院,注意：命题函数不是一个命题，只有客体变元取特定客体时，才能成为一个命题。但是客体变元在哪些范围取特定的值，对命题函数以下两方面有极大影响：(1)命题函数是否能成为一个命题；(2)命题的真值是真还是假。,2-2.1 命题函数,计算机学院,2-2.1 命题函数,个体域(universe of discourse)：在命题函数中，命题变元的论述范围称为个体域。全总个体域：个体域可以是有限的，也可以是无限的，把各种个体域综合在一起，作为论述范围的域，称为全总个体域。,计算机学院,2-2.2 量词,例题：符号化以下命题所有人都要死去。有的人的年龄超过百岁。以上给出的命题，除了有个体词和谓词以外，还有表示数量的词，称表示数量的词为量词。量词有两种：全称量词(universal quantifier)存在量词(existential quantifier),计算机学院,2-2.2 量词,定义2-2.5全称量词(universal quantifier)用符号“”表示，“x”表示对个体域里的所有个体。(x)P(x)表示对个体域里的所有个体都有属性P。表达“对所有的”，“每一个”，“对任一个”，“凡”，“一切”等词。,定义2-2-7存在量词(existential quantifier)用符号“”表示。x表示存在个体域里的个体。(x)P(x)表示存在个体域里的个体具有性质P。符号“”称为存在量词，用以表达“某个”，“存在一些”，“至少有一个”，“对于一些”等词。,计算机学院,2-2.2 量词,现在对以上两个命题进行符号化，在进行符号化之前必须确定个体域。第一种情况个体域D为人类集合。设：F(x)：x是要死的。G(x)：x活百岁以上。则有(x)F(x)和(x)G(x)这两个命题都是真命题,计算机学院,2-2.2 量词,第二种情况个体域D为全总个体域。不能符号化为(x)F(x)和(x)G(x)，因为:(x)F(x)表示宇宙间一切事物都要死的，这与原命题不符。(x)G(x)表示宇宙间一切事物中存在百岁以上，这与原命题不符。,计算机学院,2-2.2 量词,因此必须引入一个新的谓词，将人分离出来。在全总个体域的情况下，以上两个命题叙述如下：(1)对于所有个体而言，如果它是人，则它要死去。(2)存在着个体，它是人并且活过百岁以上。于是，再符号化时必须引入一个新的谓词 M(x)：x是人。称这个谓词为特性谓词。,计算机学院,2-2.2 量词,定义：特性谓词在讨论带有量词的命题函数时，必须确定其个体域，为了方便，可使用全总个体域。限定客体变元变化范围的谓词，称作特性谓词。利用特性谓词，对以上两个命题进行符号化(1)(x)(M(x)F(x)(2)(x)(M(x)G(x),计算机学院,使用量词时应注意的问题：,在讨论有量词的命题函数时如果事先没有给出个体域，那么都应以全总个体域为个体域。对全称量词，特性谓词常做蕴含的前件。对存在量词，特性谓词常做合取项。,2-2.2 量词,计算机学院,举例说明：,例1“有些人是要死的”.解1：采用全体人作为个体域.设:G(x):x是要死的.原命题符号化成:(x)G(x)解2：采用全总个体域.设:M(x):x是人;G(x):x是要死的.原命题符号化成:(x)(M(x)G(x),2-2.2 量词,计算机学院,例2“凡人都是要死的”.解1:采用全体人作为个体域.设:G(x):x是要死的.原命题符号化成:(x)G(x)解2:采用全总个体域.设:M(x):x是人;G(x):x是要死的.原命题符号化成:(x)(M(x)G(x),2-2.2 量词,计算机学院,例3:“存在最小的自然数”。解1:采用全体自然数作为个体域.设:G(x,y):xy;原命题符号化成:(x)(y)G(x,y)注意量词顺序:(y)(x)G(x,y):“没有最小的自然数”.解2:设:F(x):x是自然数;G(x,y):xy;原命题符号化成:(x)(F(x)(y)(F(y)G(x,y),2-2.2 量词,计算机学院,例4:“不存在最大的自然数”。解:设:F(x):x是自然数;G(x,y):xy;原命题符号化成:(x)(F(x)(y)(F(y)G(x,y)或:(x)(F(x)(y)(F(y)G(x,y),2-2.2 量词,计算机学院,例5:“火车比汽车快”。解:设:F(x):x是火车;G(x):x是汽车;H(x,y):x比y快原命题符号化成:(x)(F(x)(y)(G(y)H(x,y)或:(x)(y)(F(x)G(y)H(x,y),2-2.2 量词,计算机学院,例6:“有的汽车比火车快”。解:设:F(x):x是汽车;G(x):x是火车;H(x,y):x比y快原命题符号化成:(x)(F(x)(y)(G(y)H(x,y)或:(x)(y)(F(x)G(y)H(x,y),2-2.2 量词,计算机学院,例7:“有些病人相信所有的医生”。解:设:F(x):x是病人;G(x):x是医生;H(x,y):x相信y原命题符号化成:(x)(F(x)(y)(G(y)H(x,y),2-2.2 量词,计算机学院,例8:“存在唯一的对象满足性质P”。解:设:P(x):x满足性质P原命题符号化成:(!x)P(x)或:设:P(x):x满足性质P;E(x,y):x和y是同一个个体原命题符号化成:(x)(P(x)(y)(P(y)E(x,y),2-2.2 量词,计算机学院,第二章 谓词逻辑（Predicate Logic）,小结:本节将原子命题进行分解,分为客体和谓词两部分.进而介绍了客体和谓词、一元谓词和n元谓词、命题函数、全称量词和存在量词等概念。重点掌握一元谓词和n元谓词的概念、全称量词和存在量词及量化命题的符号化。作业:2-1，2-2，P59-60(1)a),c),e),g)(2)a),c),e),g),i),k),计算机学院,第二章 谓词逻辑（Predicate Logic）2-3 谓词公式与翻译(Predicate formulae),2-3谓词公式与翻译(Predicate formulae)n元谓词A(x1，x2.xn)称为谓词演算的原子公式。定义2-3.1谓词演算的合式公式,可由下述各条组成:（1）原子谓词公式是合式公式。（2）若A 是合式公式，则(A)也是合式公式。（3）若A，B是合式公式，则(A B)，(A B)，(A B)，(A B)也是合式公式。（4）若A是合式公式，x是A中出现的任何变元,则(x)A,(x)A，也是合式公式。(5)只有有限次应用(1)(4)得到的公式是合式公式.,计算机学院,第二章 谓词逻辑（Predicate Logic）2-3 谓词公式与翻译(Predicate formulae),例1：在谓词逻辑中将下列命题符号化.（1）凡正数都大于零。（2）存在小于2的素数。（3）没有不能表示成分数的有理数。（4）并不是所有参加考试的人都能取得好成绩。解：（1）令F(x):x是正数。M(x):x大于零。则符号化为：（x）(F(x)M(x),计算机学院,第二章 谓词逻辑（Predicate Logic）2-3 谓词公式与翻译(Predicate formulae),（2）令E(x):x小于2。S(x):x是素数。则符号化为：（x)(E(x)S(x)真值为0。（3）令D(x):x是有理数。F(x):x能表示成分数。则符号化为：(x)(D(x)F(x)或(x)(D(x)F(x)真值为。（4）令M(x)：x是人.Q(x):x参加考试。H(x):x取得好成绩。则符号化为：(x)(M(x)Q(x)H(x)或(x)(M(x)Q(x)H(x),计算机学院,第二章 谓词逻辑（Predicate Logic）2-3 谓词公式与翻译(Predicate formulae),例2：在谓词逻辑中将下列命题符号化.（1）所有运动员都钦佩某些教练.（2）有些运动员不钦佩教练.设：L(x):x是运动员 J(y):y是教练 A(x,y):x钦佩y(1)(x)(L(x)（y)(J(y)A(x,y)(2)（x)(L(x)(y)(J(y)A(x,y),计算机学院,第二章 谓词逻辑（Predicate Logic）2-3 谓词公式与翻译(Predicate formulae),例3：在谓词逻辑中将下列命题符号化.（1）那位戴眼镜的用功的大学生在看这本大而厚的巨著.（2）P63(7)解:(1)设：S(x):x是大学生.A(x):x戴眼镜.B(x):x用功.D(x):x是巨著.F(x,y):x看y.E(y):y是大的.G(y):y是厚的.a:那位 b:这本(1)符号化为:A(a)B(a)S(a)D(b)E(b)G(b)F(a,b),计算机学院,第二章 谓词逻辑（Predicate Logic）2-3 谓词公式与翻译(Predicate formulae),（2）设：P(x,y):x在y连续.Q(x,y):x大于y.(2)符号化为:P(f,a)()(Q(,0)()Q(,0)(x)(Q(,)Q(,)P(f,a)()()(x)(Q(,0)(Q(,0)(Q(,)Q(,).,计算机学院,第二章 谓词逻辑（Predicate Logic）2-3 谓词公式与翻译(Predicate formulae),小结：本节介绍了谓词合式公式的概念，重点掌握谓词公式的翻译.作业:P62(2)(3)(6),计算机学院,第二章 谓词逻辑（Predicate Logic）2-4 变元的约束(Bound of variable),2-4 变元的约束(Bound of variable)2-4.1 变元的约束2-4.2 约束变元的换名与自由变元的代入,计算机学院,第二章 谓词逻辑（Predicate Logic）2-4 变元的约束(Bound of variable),2-4.1变元的约束(Bound of variable)定义2-4.1:在谓词公式中,形如(x)P(x)和(x)P(x)的部分,称为谓词公式的x约束部分.(x)P(x)或(x)P(x)中的x叫做量词的指导变元或作用变元，P(x)称为相应量词的作用域或辖域。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-4 变元的约束(Bound of variable),在x和x的辖域中，x的所有出现都称为约束出现，相应的x称为约束变元;P(x)中除约束变元以外出现的变元称为是自由变元。例1：1、x(H(x,y)y(W(y)L(x,y,z)2、x(H(x)W(y)y(F(x)L(x,y,z),计算机学院,第二章 谓词逻辑（Predicate Logic）2-4 变元的约束(Bound of variable),说明:(1)n元谓词公式A(x1，x2.xn)中有n个自由变元,若对其中的k(kn)个进行约束,则构成了n-k元谓词;如果一个公式中没有自由变元出现,则该公式就变成了一个命题(2)一个公式的约束变元所使用的名称符号是无关紧要的,如(x)M(x)与(y)M(y)意义相同.,计算机学院,第二章 谓词逻辑（Predicate Logic）2-4 变元的约束(Bound of variable),2-4.2 约束变元的换名与自由变元的代入规则 在例1中,一个变元在同一个公式中既是自由出现又是约束出现,这样在理解上容易发生混淆.为了避免这种混乱,可对约束变元进行换名.换名规则:(对约束变元而言）对约束变元进行换名,使得一个变元在一个公式中只呈一种形式出现.,计算机学院,第二章 谓词逻辑（Predicate Logic）2-4 变元的约束(Bound of variable),(1)约束变元可以换名,其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的该变元,公式的其余部分不变.(2)换名时一定要更改为作用域中没有出现的变元名称.,计算机学院,第二章 谓词逻辑（Predicate Logic）2-4 变元的约束(Bound of variable),例1:x(P(x)R(x,y)L(x,y)换名为t(P(t)R(t,y)L(x,y)x(H(x,y)y(W(y)L(x,y,z)换名为x(H(x,y)s(W(s)L(x,s,z),计算机学院,第二章 谓词逻辑（Predicate Logic）2-4 变元的约束(Bound of variable),代入规则（对自由变元而言）对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入,代入时需要对公式中出现该自由变元的每一处进行;(2)用以代入的变元与原公式中所有变元的名称不能相同.例如对例1中的公式x(P(x)R(x,y)L(x,y)自由变元y用z来代入,得 x(P(x)R(x,z)L(x,z),计算机学院,第二章 谓词逻辑（Predicate Logic）2-4 变元的约束(Bound of variable),小结：本节介绍了约束变元、自由变元的概念，重点掌握约束变元的换名与自由变元的代入.作业:P65(2)c)d)(4)(5),计算机学院,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,2-5谓词演算的等价式与蕴含式(Equivalences&implications of predicate calculus)2-5.1谓词的等价和永真的概念2-5.2谓词演算的等价式与蕴含式,计算机学院,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,2-5.1谓词的等价和永真的概念 定义2-5.1:给定任何两个谓词公式Wff A和Wff B，设他们有共同的个体域E，若对A和B的任一组变元进行赋值，所得命题的真值都相同，则称谓词公式A和B在E上是等价的，并记作A B。,定义2-5.2 给定任意谓词公式wffA,其个体域为E，对于A的所有赋值，wffA都为真，则称WffA在E上是有效的（或永真的）。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,定义2-5.3 一个谓词公式wffA，如果在所有赋值下都为假，则称该wffA为不可满足的。公式A不可满足时也称A为永假式。,定义2-5.4 一个谓词公式wffA，如果至少在一种赋值为真，则称该wffA为可满足的。,有了谓词公式的等价和永真等概念，就可以讨论谓词演算的一些等价式和蕴含式。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,1、命题公式的推广在命题公式中成立的式子，用谓词公式去代换其中相应的命题变元，得到的公式依然成立如：x(P(x)Q(x)x(P(x)Q(x)xP(x)xQ(x)(xP(x)xQ(x)2、量词与之间的关系(x)P(x)(x)P(x)(x)P(x)(x)P(x),计算机学院,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,3、量词辖域的扩张与收缩量词辖域中如果有合取或析取项，且其中有一个是命题，则可将该命题移至量词辖域之外。如：（x）（A(x)B）（x）A(x)B（x）（A(x)B）（x）A(x)B（x）（A(x)B）（x）A(x)B（x）（A(x)B）（x）A(x)B,计算机学院,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,量词辖域的扩张（xA(x)B）（x)(A(x)B）(（x)A(x)B)(x)(A(x)B）(B(x)A(x)）（x)(B A(x)）(B(x)A(x)(x)(B A(x)另有多个公式见课本70页,计算机学院,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,4、量词分配等价式设A(x)、B(x)是任意的含自由出现个体变元x的公式，则(1)x(A(x)B(x)x A(x)x B(x)(2)x(A(x)B(x)x A(x)x B(x)(3)x(A(x)B(x)x A(x)x B(x)(4)x(A(x)B(x)x A(x)x B(x),计算机学院,5.谓词演算蕴含式 xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)x A(x)x B(x)6.多个量词的使用 多个量词同时出现时,其顺序是至关重要的.,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,计算机学院,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,计算机学院,第二章 谓词逻辑（Predicate Logic）2-5 谓词演算的等价式与蕴含式,小结：本节介绍了谓词公式的概念及谓词演算的等价式与蕴涵式，重点掌握谓词演算的等价式与蕴涵式作业:P72(2)b)d)(4)(7),计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),2-6 前束范式(Prenex normal form)2-6.1 前束范式(Prenex normal form)2-6.2 前束析取范式和前束合取范式(Prenex disjunctive normal form&Prenex conjunctive normal form),计算机学院,它具有如下形式：(x1)(x2)(xk)B其中为或，B为不含有量词的公式。称 x1 x2 xk为公式的首标。特别地，若中无量词，则也看作是前束范式。,定义2-6.1 一个公式，如果量词均非否定地出现在公式的最前面，且它们的作用域，延伸到整个公式的末尾，则该公式叫做前束范式(prenex normal forms),第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),计算机学院,第二章 谓词逻辑（Predicate Logic）2-6前束范式(Prenex Normal Form),定理2-6.1:任意一个谓词公式，均和一个前束范式等价。前束范式的求法：第一步：否定深入。即利用量词转化公式，把否定联结 词深入到命题变元和谓词填式的前面。第二步：改名。即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。这样便可求出与公式等价的前束范式。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),例2:求下列公式的前束范式。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),解:,计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),2-6.2前束析取范式和前束合取范式(Prenex disjunctive normal form&Prenex conjunctive normal form)在前束范式的基础上,可以定义前束析(合)取范式.定义2-6.2:任何一个谓词公式A，如果具有如下形式则称为前束合取范式：(x1)(x2)(xn)(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)其中n大于等于1,Aij(j=1,ki,i=1,2,3,m)为原子谓词公式或其否定,为量词或量词，xi（i=1，n）为客体变元.,计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),定义2-6.3 任何一个谓词公式A，如果具有如下形式则称为前束析取范式：(x1)(x2)(xn)(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)其中m大于等于1,Aij(j=1,ki,i=1,2,3,m)为原子谓词公式或其否定,为量词或量词，xi（i=1，n）为客体变元.定理2-6.2:每一个谓词公式都可以转化为与其等价的前束析(合)取范式.,计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),例2:求下列公式的前束析取范式和前束合取范式.解:,计算机学院,第二章 谓词逻辑（Predicate Logic）2-6 前束范式(Prenex Normal Form),小结：本节介绍了谓词公式的前束范式、前束析取范式和前束合取范式.重点掌握前束析取范式和前束合取范式求法。作业:P75(1)a)c)(2)b)d),计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,2-7 谓词演算的推理理论(Inference theory of predicate calculus)2-7.1 推理规则(Rules of inference)2-7.2 证明举例(Examples of proof),计算机学院,2-7.1推理规则(Rules of inference)在谓词演算中，推理的形式结构仍为 H1H2H3.HnC若 H1H2H3.HnC是永真式，则称由前提H1,H2,H3,.,Hn逻辑的推出结论C，但在谓词逻辑中,H1,H2,H3,.,Hn,C均为谓词公式。命题演算中的推理规则，可在谓词推理理论中应用。,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,计算机学院,与量词有关的四条重要推理规则：1、全称指定规则（US规则）2、全称推广规则（UG规则）3、存在指定规则（ES规则）4、存在推广规则（EG规则）注意：只能对前束范式适用上述规则。,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,计算机学院,1.全称指定规则（US）：x P(x)P(c)使用此规则时要注意：（1）x是P(x)中的自由变元；（2）c是论域中的某个任意的客体.,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,计算机学院,2.全称推广规则（UG）：P(y)x P(x)使用此规则时注意:(1)y在P(y)中自由出现，且y取任何值时P均为真。(2)x不在P(y)中约束出现.,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,3.存在指定规则(ES):x P(x)P(c)注:c是论域中的某些客体,c并不是任意的使用此规则时应注意：c是使P为真的特定客体；,计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,(4)存在推广规则(EG):P(c)x P(x)使用此规则时注意:(1)C是个体域中某个确定的个体。(2)代替C的x不能已在P(c)中出现。,计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,例1证明苏格拉底三段论:凡是人都是要死的。苏格拉底是人。苏格拉底是要死的。设：M(x):x是人。D(x):x 是要死的。a:苏格拉底。则 前提：x(M(x)D(x)，M(a）.结论：D(a).证明：x(M(x)D(x)P M(a)D(a)US M(a)P D(a)T I11(直接证法),2-7.2证明举例(Examples of proof),计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,例2:前提：x(F(x)G(x)，x G(x).结论：x F(x).证明：x G(x)P x G(x)T 置换规则 G(a)US x(F(x)G(x)P F(a)G(a)US F(a)T x F(x)EG,计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,例3:前提：x(A(x)B(x)，x A(x)结论：x B(x)证明：x A(x)P前提引入 A(c)ES x(A(x)B(x)P前提引入 A(c)B(c)US B(c)T x B(x)EG 注意：引入的顺序不可更改！,计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,例4:前提：x(F(x)G(x),x(R(x)G(x),x R(x).结论：x F(x).(归谬法)证明：x F(x)P结论否定引入 x F(x)T F(a)ES x(F(x)G(x)P F(a)G(a)US G(a)T,计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,x(R(x)G(x)P R(a)G(a)US R(a)T x R(x)P(11)R(a)US(12)R(a)R(a)矛盾式,计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,例5:证明:x(P(x)Q(x)=(x)P(x)(x)Q(x)(附加前提法)证明：(1)(x)P(x)P(附加前提)(2)(x)P(x)T(1)(3)P(c)ES(2)(4)x(P(x)Q(x)P(5)P(c)Q(c)US(4),计算机学院,第二章 谓词逻辑（Predicate Logic）2-7 谓词演算的推理理论,(6)Q(c)T(3)(5)(7)(x)Q(x)EG(6)(8)(x)P(x)(x)Q(x)CP小结：本节介绍了谓词演算的推理规则,并举例说明了它们的应用.重点:深刻理解四个推理规则,会应用它们推理证明.作业:P79(1)a)c)(2)a)(3),