离散数学左孝凌

会计学1离散数学左孝凌计算机学院第二章谓词逻辑（PredicateLogic）2-1谓词的概念与表示(PredicateandItsExpression)命题逻辑的局限性：在命题逻辑中，命题是命题演算的基本单位，不再对原子命题进行分解，因而无法研究命题的内部结构、成分及命题之间的内在联系，甚至无法处理一些简单而又常见的推理过程。第1页/共87页计算机学院例如，下列推理：所有的人都是要死的。苏格拉底是人。苏格拉底是要死的。众所周知,这是真命题。但在命题逻辑中,如果用P,Q,R表示以上三个命题，则上述推理过程为：（P∧Q）R。借助命题演算的推理理论不能证明其为重言式。第二章谓词逻辑（PredicateLogic）2-1谓词的概念与表示(PredicateandItsExpression)第2页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-1谓词的概念与表示(PredicateandItsExpression)原因：命题逻辑不能将命题之间的内在联系和数量关系反映出来。解决办法：将命题进行分解。第3页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2.1谓词的概念与表示(PredicateandItsExpression)2-1谓词的概念与表示(Predicateanditsexpression)2-1.1客体和谓词在谓词逻辑中，可将原子命题划分为客体和谓词两部分。客体：可以独立存在的具体事物的或抽象的概念。例如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等，客体也可称之为主语。第4页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-1谓词的概念与表示(PredicateandItsExpression)谓词：用来刻划客体的性质或客体之间的相互关系的词。例如在下面命题中：（1）张明是个劳动模范。（2）李华是个劳动模范。刻划客体的性质（3）王红是个大学生。（4）小李比小赵高2cm。（5）点a在b与c之间。刻划客体之间的相互关系（6）阿杜与阿寺同岁。“是个劳动模范”、“是个大学生”、“…比…高2cm”、“…在…与…之间”都是谓词。第5页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-1谓词的概念与表示(PredicateandItsExpression)刻划一个客体性质的词称之为一元谓词,刻划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)为三元谓词。第6页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-1谓词的概念与表示(PredicateandItsExpression)注:(1)单独一个谓词并不是命题，在谓词字母后填上客体所得到的式子称之为谓词填式。(2)在谓词填式中，若客体确定，则A(a1，a2...an)就变成了命题(3)在多元谓词表达式中，客体字母出现的先后次序与事先约定有关,一般不可以随意交换位置(如,上例中H(s,t)与H(t,s)代表两个不同的命题)。第7页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-1谓词的概念与表示(PredicateandItsExpression)设谓词H表示“是劳动模范”,a表示客体名称张明,b表示客体名称李华,c表示客体名称这只老虎，那么H(a)、H(b)、H(c)表示三个不同的命题,但它们有一个共同的形式,即H(x).一般地，H(x)表示客体x具有性质H。这里x表示抽象的或泛指的客体，称为客体变元，常用小写英文字母x,y,z,…表示。相应地，表示具体或特定的客体的词称为客体常项，常用小写英文字母a,b,c,…表示。第8页/共87页计算机学院2-1谓词的概念与表示(PredicateandItsExpression)同理，客体变元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后，它们才成为命题。第9页/共87页计算机学院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”第10页/共87页计算机学院2-2.1命题函数定义2-2.1：简单命题函数(simplepropositionalfunction)：由一个谓词，一些客体变元组成的表达式称为简单命题函数。比如：A(x)，B(x,y)，L(x,y,z)简单命题函数不是命题，只有当变元x,y,z等取特定的客体才确定了一个命题。对于n元谓词，当n=0时，称为0元谓词，它本身就是一个命题，故命题是n元谓词的一个特殊情况。第11页/共87页计算机学院2-2.1命题函数比如：L(x,y)表示“x小于y”是二元谓词，L(x,3)表示“x小于3”是一元谓词，L(2,3)表示“2小于3”是0元谓词。因此可以将命题看成n元谓词的一个特殊情况。0元谓词都是命题，命题逻辑中的简单命题都可以用0元谓词表示。第12页/共87页计算机学院2-2.1命题函数定义2-2.2：复合命题函数（compoundpropositionalfunction）：由一个或n个简单命题函数以及逻辑联结词组合而成的表达式。命题逻辑中的联结词在谓词逻辑中含义完全相同。举例说明：P56例１，例２第13页/共87页计算机学院2-2.1命题函数定义2-2.3：谓词填式单独一个谓词不是完整的命题，把谓词字母以客体填后所得的式子称为谓词填式。例如：P(x)表示x>3，则P(1)、P(2)、P(5)分别表示1大于3，2大于3，5大于3，P(1)、P(2)、P(5)即是谓词填式。第14页/共87页计算机学院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)第15页/共87页计算机学院\\\注意：命题函数不是一个命题，只有客体变元取特定客体时，才能成为一个命题。但是客体变元在哪些范围取特定的值，对命题函数以下两方面有极大影响：(1)命题函数是否能成为一个命题；(2)命题的真值是真还是假。2-2.1命题函数第16页/共87页计算机学院2-2.1命题函数个体域(universeofdiscourse)：在命题函数中，命题变元的论述范围称为个体域。全总个体域：个体域可以是有限的，也可以是无限的，把各种个体域综合在一起，作为论述范围的域，称为全总个体域。第17页/共87页计算机学院2-2.2量词例题：符号化以下命题所有人都要死去。有的人的年龄超过百岁。以上给出的命题，除了有个体词和谓词以外，还有表示数量的词，称表示数量的词为量词。量词有两种：全称量词(universalquantifier)存在量词(existentialquantifier)第18页/共87页计算机学院2-2.2量词定义2-2.5．全称量词(universalquantifier)用符号“”表示，“x”表示对个体域里的所有个体。(x)P(x)表示对个体域里的所有个体都有属性P。表达“对所有的”，“每一个”，“对任一个”，“凡”，“一切”等词。定义2-2-7．存在量词(existentialquantifier)用符号“”表示。x表示存在个体域里的个体。(x)P(x)表示存在个体域里的个体具有性质P。符号“”称为存在量词，用以表达“某个”，“存在一些”，“至少有一个”，“对于一些”等词。第19页/共87页计算机学院2-2.2量词现在对以上两个命题进行符号化，在进行符号化之前必须确定个体域。第一种情况．个体域D为人类集合。设：F(x)：x是要死的。　　G(x)：x活百岁以上。则有(x)F(x)和(x)G(x)这两个命题都是真命题第20页/共87页计算机学院2-2.2量词第二种情况．个体域D为全总个体域。不能符号化为(x)F(x)和(x)G(x)，因为:(x)F(x)表示宇宙间一切事物都要死的，这与原命题不符。(x)G(x)表示宇宙间一切事物中存在百岁以上，这与原命题不符。第21页/共87页计算机学院2-2.2量词因此必须引入一个新的谓词，将人分离出来。在全总个体域的情况下，以上两个命题叙述如下：(1)对于所有个体而言，如果它是人，则它要死去。(2)存在着个体，它是人并且活过百岁以上。于是，再符号化时必须引入一个新的谓词M(x)：x是人。称这个谓词为特性谓词。第22页/共87页计算机学院2-2.2量词定义：特性谓词在讨论带有量词的命题函数时，必须确定其个体域，为了方便，可使用全总个体域。限定客体变元变化范围的谓词，称作特性谓词。利用特性谓词，对以上两个命题进行符号化(1)(x)(M(x)→F(x))(2)(x)(M(x)∧G(x))第23页/共87页计算机学院使用量词时应注意的问题：在讨论有量词的命题函数时如果事先没有给出个体域，那么都应以全总个体域为个体域。对全称量词，特性谓词常做蕴含的前件。对存在量词，特性谓词常做合取项。2-2.2量词第24页/共87页计算机学院举例说明：例1．“有些人是要死的”.解1：采用全体人作为个体域.设:G(x):x是要死的.原命题符号化成:(x)G(x)解2：采用全总个体域.设:M(x):x是人;G(x):x是要死的.原命题符号化成:(x)(M(x)∧G(x))2-2.2量词第25页/共87页计算机学院例2．“凡人都是要死的”.解1:采用全体人作为个体域.设:G(x):x是要死的.原命题符号化成:(x)G(x)解2:采用全总个体域.设:M(x):x是人;G(x):x是要死的.原命题符号化成:(x)(M(x)→G(x))2-2.2量词第26页/共87页计算机学院例3:“存在最小的自然数”。解1:采用全体自然数作为个体域.设:G(x,y):x≤y;原命题符号化成:(x)(y)G(x,y)注意量词顺序:(y)(x)G(x,y):“没有最小的自然数”.解2:设:F(x):x是自然数;G(x,y):x<y;原命题符号化成:(x)(F(x)∧(y)(F(y)→G(x,y)))2-2.2量词第27页/共87页计算机学院例4:“不存在最大的自然数”。解:设:F(x):x是自然数;G(x,y):x＞y;原命题符号化成:(x)(F(x)(y)(F(y)G(x,y)))或:(x)(F(x)(y)(F(y)G(x,y)))2-2.2量词第28页/共87页计算机学院例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量词第29页/共87页计算机学院例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量词第30页/共87页计算机学院例7:“有些病人相信所有的医生”。解:设:F(x):x是病人;G(x):x是医生;H(x,y):x相信y原命题符号化成:(x)(F(x)(y)(G(y)H(x,y)))2-2.2量词第31页/共87页计算机学院例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量词第32页/共87页计算机学院第二章谓词逻辑（PredicateLogic）小结:本节将原子命题进行分解,分为客体和谓词两部分.进而介绍了客体和谓词、一元谓词和n元谓词、命题函数、全称量词和存在量词等概念。重点掌握一元谓词和n元谓词的概念、全称量词和存在量词及量化命题的符号化。作业:2-1，2-2，P59-60(1)a),c),e),g)(2)a),c),e),g),i),k)第33页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-3谓词公式与翻译(Predicateformulae)2-3谓词公式与翻译(Predicateformulae)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)得到的公式是合式公式.第34页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-3谓词公式与翻译(Predicateformulae)例1：在谓词逻辑中将下列命题符号化.（1）凡正数都大于零。（2）存在小于2的素数。（3）没有不能表示成分数的有理数。（4）并不是所有参加考试的人都能取得好成绩。解：（1）令F(x):x是正数。M(x):x大于零。则符号化为：　（x）(F(x)M(x))第35页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-3谓词公式与翻译(Predicateformulae)（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))第36页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-3谓词公式与翻译(Predicateformulae)例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)))第37页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-3谓词公式与翻译(Predicateformulae)例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)第38页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-3谓词公式与翻译(Predicateformulae)（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(ε,)))).第39页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-3谓词公式与翻译(Predicateformulae)小结：本节介绍了谓词合式公式的概念，重点掌握谓词公式的翻译.作业:P62(2)(3)(6)第40页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-4变元的约束(Boundofvariable)2-4变元的约束(Boundofvariable)2-4.1变元的约束2-4.2约束变元的换名与自由变元的代入第41页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-4变元的约束(Boundofvariable)2-4.1变元的约束(Boundofvariable)定义2-4.1:在谓词公式中,形如(x)P(x)和(x)P(x)的部分,称为谓词公式的x约束部分.(x)P(x)或(x)P(x)中的x叫做量词的指导变元或作用变元，P(x)称为相应量词的作用域或辖域。第42页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-4变元的约束(Boundofvariable)在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))第43页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-4变元的约束(Boundofvariable)说明:(1)n元谓词公式A(x1，x2...xn)中有n个自由变元,若对其中的k(k≤n)个进行约束,则构成了n-k元谓词;如果一个公式中没有自由变元出现,则该公式就变成了一个命题(2)一个公式的约束变元所使用的名称符号是无关紧要的,如(x)M(x)与(y)M(y)意义相同.第44页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-4变元的约束(Boundofvariable)2-4.2约束变元的换名与自由变元的代入规则在例1中,一个变元在同一个公式中既是自由出现又是约束出现,这样在理解上容易发生混淆.为了避免这种混乱,可对约束变元进行换名.换名规则:(对约束变元而言）对约束变元进行换名,使得一个变元在一个公式中只呈一种形式出现.第45页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-4变元的约束(Boundofvariable)(1)约束变元可以换名,其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的该变元,公式的其余部分不变.(2)换名时一定要更改为作用域中没有出现的变元名称.第46页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-4变元的约束(Boundofvariable)例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)))第47页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-4变元的约束(Boundofvariable)代入规则（对自由变元而言）对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入,代入时需要对公式中出现该自由变元的每一处进行;(2)用以代入的变元与原公式中所有变元的名称不能相同.例如对例1中的公式x(P(x)R(x,y))∧L(x,y)自由变元y用z来代入,得x(P(x)R(x,z))∧L(x,z)第48页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-4变元的约束(Boundofvariable)小结：本节介绍了约束变元、自由变元的概念，重点掌握约束变元的换名与自由变元的代入.作业:P65(2)c)d)(4)(5)第49页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-5谓词演算的等价式与蕴含式2-5谓词演算的等价式与蕴含式(Equivalences&implicationsofpredicatecalculus)2-5.1谓词的等价和永真的概念2-5.2谓词演算的等价式与蕴含式第50页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-5谓词演算的等价式与蕴含式2-5.1谓词的等价和永真的概念定义2-5.1:给定任何两个谓词公式WffA和WffB，设他们有共同的个体域E，若对A和B的任一组变元进行赋值，所得命题的真值都相同，则称谓词公式A和B在E上是等价的，并记作AB。定义2-5.2给定任意谓词公式wffA,其个体域为E，对于A的所有赋值，wffA都为真，则称WffA在E上是有效的（或永真的）。第51页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-5谓词演算的等价式与蕴含式定义2-5.3一个谓词公式wffA，如果在所有赋值下都为假，则称该wffA为不可满足的。公式A不可满足时也称A为永假式。定义2-5.4一个谓词公式wffA，如果至少在一种赋值为真，则称该wffA为可满足的。有了谓词公式的等价和永真等概念，就可以讨论谓词演算的一些等价式和蕴含式。第52页/共87页计算机学院第二章谓词逻辑（PredicateLogic）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)第53页/共87页计算机学院第二章谓词逻辑（PredicateLogic）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第54页/共87页计算机学院第二章谓词逻辑（PredicateLogic）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页第55页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-5谓词演算的等价式与蕴含式4、量词分配等价式设A(x)、B(x)是任意的含自由出现个体变元x的公式，则(1)x(A(x)∧B(x))xA(x)∧xB(x)(2)x(A(x)∨B(x))xA(x)∨xB(x)(3)x(A(x)∨B(x))xA(x)∨xB(x)(4)x(A(x)∧B(x))xA(x)∧xB(x)第56页/共87页计算机学院5.谓词演算蕴含式xA(x)∨xB(x)x(A(x)∨B(x))x(A(x)∧B(x))xA(x)∧xB(x)6.多个量词的使用多个量词同时出现时,其顺序是至关重要的.第二章谓词逻辑（PredicateLogic）2-5谓词演算的等价式与蕴含式第57页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-5谓词演算的等价式与蕴含式第58页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-5谓词演算的等价式与蕴含式小结：本节介绍了谓词公式的概念及谓词演算的等价式与蕴涵式，重点掌握谓词演算的等价式与蕴涵式作业:P72(2)b)d)(4)(7)第59页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)2-6前束范式(Prenexnormalform)2-6.1前束范式(Prenexnormalform)2-6.2前束析取范式和前束合取范式(Prenexdisjunctivenormalform&Prenexconjunctivenormalform)第60页/共87页计算机学院它具有如下形式：(□x1)(□x2)…(□xk)B其中□为或，B为不含有量词的公式。称□x1□x2…□xk为公式的首标。特别地，若Ａ中无量词，则Ａ也看作是前束范式。定义2-6.1一个公式，如果量词均非否定地出现在公式的最前面，且它们的作用域，延伸到整个公式的末尾，则该公式叫做前束范式(prenexnormalforms)第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)第61页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)定理2-6.1:任意一个谓词公式，均和一个前束范式等价。前束范式的求法：第一步：否定深入。即利用量词转化公式，把否定联结词深入到命题变元和谓词填式的前面。第二步：改名。即利用换名规则、代入规则更换一些变元的名称，以便消除混乱。第三步：量词前移。即利用量词辖域的收缩与扩张把量词移到前面。这样便可求出与公式等价的前束范式。第62页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)例2:求下列公式的前束范式。第63页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)解:第64页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)第65页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)第66页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)第67页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)2-6.2前束析取范式和前束合取范式(Prenexdisjunctivenormalform&Prenexconjunctivenormalform)在前束范式的基础上,可以定义前束析(合)取范式.定义2-6.2:任何一个谓词公式A，如果具有如下形式则称为前束合取范式：(□x1)(□x2)…(□xn)[(A11∨A12∨…∨A1k1)∧(A21∨A22∨…∨A2k2)∧…∧(Am1∨Am2∨…∨Amkm)]其中n大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)为原子谓词公式或其否定,□为量词或量词，xi（i=1，…n）为客体变元.第68页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)定义2-6.3任何一个谓词公式A，如果具有如下形式则称为前束析取范式：(□x1)(□x2)…(□xn)[(A11∧A12∧…∧A1k1)∨(A21∧A22∧…∧A2k2)∨…∨(Am1∧Am2∧…∧Amkm)]其中m大于等于1,Aij(j=1,…,ki,i=1,2,3,…,m)为原子谓词公式或其否定,□为量词或量词，xi（i=1，…n）为客体变元.定理2-6.2:每一个谓词公式都可以转化为与其等价的前束析(合)取范式.第69页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)例2:求下列公式的前束析取范式和前束合取范式.解:第70页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-6前束范式(PrenexNormalForm)小结：本节介绍了谓词公式的前束范式、前束析取范式和前束合取范式.重点掌握前束析取范式和前束合取范式求法。作业:P75(1)a)c)(2)b)d)第71页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论2-7谓词演算的推理理论(Inferencetheoryofpredicatecalculus)2-7.1推理规则(Rulesofinference)2-7.2证明举例(Examplesofproof)第72页/共87页计算机学院2-7.1推理规则(Rulesofinference)在谓词演算中，推理的形式结构仍为H1H2H3....HnC若H1H2H3....HnC是永真式，则称由前提H1,H2,H3,.…,Hn逻辑的推出结论C，但在谓词逻辑中,H1,H2,H3,.…,Hn,C均为谓词公式。命题演算中的推理规则，可在谓词推理理论中应用。第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论第73页/共87页计算机学院与量词有关的四条重要推理规则：1、全称指定规则（US规则）2、全称推广规则（UG规则）3、存在指定规则（ES规则）4、存在推广规则（EG规则）注意：只能对前束范式适用上述规则。第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论第74页/共87页计算机学院1.全称指定规则（US）：xP(x)∴P(c)使用此规则时要注意：（1）x是P(x)中的自由变元；（2）c是论域中的某个任意的客体.第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论第75页/共87页计算机学院2.全称推广规则（UG）：P(y)∴xP(x)使用此规则时注意:(1)y在P(y)中自由出现，且y取任何值时P均为真。(2)x不在P(y)中约束出现.第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论第76页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论3.存在指定规则(ES):xP(x)∴P(c)注:c是论域中的某些客体,c并不是任意的使用此规则时应注意：c是使P为真的特定客体；第77页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论(4)存在推广规则(EG):P(c)∴xP(x)使用此规则时注意:(1)C是个体域中某个确定的个体。(2)代替C的x不能已在P(c)中出现。第78页/共87页计算机学院第二章谓词逻辑（PredicateLogic）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证明举例(Examplesofproof)第79页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论例2:前提：x(F(x)∨G(x))，┐xG(x).结论：xF(x).证明：①┐xG(x)P②x┐G(x)T①置换规则③┐G(a)US②④x(F(x)∨G(x))P⑤F(a)∨G(a)US④⑥F(a)T③⑤⑦xF(x)EG⑥第80页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论例3:前提：x(A(x)B(x))，xA(x)结论：xB(x)证明：①xA(x)P前提引入②A(c)ES①③x(A(x)B(x))P前提引入④A(c)B(c)US③⑤B(c)T②④⑥xB(x)EG⑤注意：①③引入的顺序不可更改！第81页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论例4:前提：x(F(x)∨G(x)),x(┐R(x)∨┐G(x)),xR(x).结论：xF(x).(归谬法)证明：①┐xF(x)P结论否定引入②x┐F(x)T①③┐F(a)ES②④x(F(x)∨G(x))P⑤F(a)∨G(a)US④⑥G(a)T③⑤第82页/共87页计算机学院第二章谓词逻辑（PredicateLogic）2-7谓词演算的推理理论⑦x(┐R(x)∨┐G(x))P⑧┐R(a)∨┐G(a))US⑦⑨┐R(a)T⑥⑧⑩xR(x)P(11)R(a)US⑩(12)┐R(a)∧R(a)矛盾式第83页/共87页计算机学院第二章谓词逻辑（PredicateLogic）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)第84页/共87页计算机学院第二章谓词逻辑（PredicateLogic）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)第85页/共87页计算机学院结束谢谢!第二章谓词逻辑（PredicateLogic）第86页/共87页