离散数学(第四章)解读..ppt

,第二章谓词逻辑,2.1谓词的概念与表示(Predicateanditsexpression)2.2谓词公式与翻译(Predicateformulae)2.3谓词演算的等价式与蕴含式(Equivalences个体变元x,y,z具有关系A，记作A(x,y,z).,H(x)、L(x,y)、A(x,y,z)本身并不是一个命题。只有用特定的个体取代客体变元x,y,z后，它们才成为命题。我们称H(x)、L(x,y)、(x,y,z)为命题函数。,2.1一阶逻辑命题符号化,2.1一阶逻辑命题符号化,n元谓词就是有n个个体变元的命题函数.当n=0时,称为0元谓词.因此,一般情况下,命题函数不是命题;特殊情况0元谓词就变成一个命题.复合命题函数:由一个或几个简单命题函数以及逻辑联结词组合而成的表达式.,2.1一阶逻辑命题符号化,例1:若x的学习好,则x的工作好设S(x):x学习好；W(x):x工作好则有S(x)W(x)例2:将下列命题用0元谓词符号化.(1)2是素数且是偶数.(2)如果2大于3,则2大于4.(3)如果张明比李民高,李民比赵亮高,则张明比赵亮高.,2.1一阶逻辑命题符号化,解:(1)设F(x):x是素数.G(x):x是偶数.则命题符号化为：F(2)G(2)(2)设L(x,y)：x大于y.则命题符号化为：L(2,3)L(2,4)(3)设H(x,y):x比y高.a:张明b:李民c：赵亮则命题符号化为：H(a,b)H(b,c)H(a,c)注意:命题函数中,个体变元在哪些范围内取特定的值,对命题的真值极有影响.,例如:H(x,y)H(y,z)H(x,z)若H(x,y)解释为:x大于y,当x,y,z都在实数中取值时,则这个式子表示“若x大于y且y大于z，则x大于z”。这是一个永真式。如果H(x,y)解释为:“x是y的儿子”,当x,y,z都指人时，则这个式子表示“若x为y的儿子且y是z的儿子，则x是z的儿子”。这是一个永假式。如果H(x,y)解释为:“x距y10米”,当x,y,z为平面上的点，则这个式子表示“若x距y10米且y距z10米，则x距z10米”。这个命题的真值将由x,y,z的具体位置而定，它可能是1，也可能是0。,2.1一阶逻辑命题符号化,在命题函数中，个体变元的取值范围称为个体域，又称之为论域。个体域可以是有限事物的集合，也可以是无限事物的集合。全总个体域：宇宙间一切事物组成的个体域称为全总个体域。,2.1一阶逻辑命题符号化,2.1一阶逻辑命题符号化,量词(Quantifiers)量词：分为全称量词()和存在量词()1.全称量词(TheUniversalQuantifiers)对日常语言中的“一切”、“所有”、“凡”、“每一个”、“任意”等词，用符号“”表示，表示对个体域里的所有个体，()表示个体域里的所有个体具有性质F.符号“”称为全称量词.,2.1一阶逻辑命题符号化,例3：在谓词逻辑中将下列命题符号化.（1）凡是人都呼吸。（2）每个学生都要参加考试。（3）任何整数或是正的或是负的。解:(1)当个体域为人类集合时：令F(x):x呼吸。则（1）符号化为xF(x)当个体域为全总个体域时：令M(x):x是人。则（1）符号化为x(M(x)F(x).,2.1一阶逻辑命题符号化,(2)当个体域为全体学生的集合时：令P(x):x要参加考试。则（2）符号化为xP(x)当个体域为全总个体域时：令S(x):x是学生。则（2）符号化为x(S(x)P(x).,2.1一阶逻辑命题符号化,(3)当个体域为全体整数的集合时：令P(x):x是正的。N(x):x是负的。则（3）符号化为x(P(x)N(x)当个体域为全总个体域时：令I(x):x是整数。则（3）符号化为x(I(x)(P(x)N(x).,2.1一阶逻辑命题符号化,2.存在量词(TheExistentialQuantifiers)对日常语言中的“有一个”、“有的”、“存在着”、“至少有一个”、“存在一些”等词，用符号“”表示，表示存在个体域里的个体，()表示存在个体域里的个体具有性质F.符号“”称为存在量词.,2.1一阶逻辑命题符号化,“”表达式的读法：xA(x)：存在一个x,使x是；xA(x)：存在一个x,使x不是；xA(x)：不存在一个x,使x是；xA(x)：不存在一个x,使x不是。,2.1一阶逻辑命题符号化,例4设P(x)表示x喜欢梦八队，则P(x)表示x不喜欢梦八队。(个体域限定为人)（1）不是所有人都喜欢梦八队：(x)P(x)（2）存在一些人不喜欢梦八队：(x)P(x)（3）不会有人喜欢梦八队：(x)P(x)（4）所有人都不喜欢梦八队：(x)P(x)可以看出命题(1)(2)意义完全相同，(3)(4)意义也完全相同,2.1一阶逻辑命题符号化,解:(1)令Q(x):x是有理数。则（1）符号化为Q(x)（2）当个体域为人类集合时：令G(x):x活百岁以上则（2）符号化为：xG(x)当个体域为全总个体域时：令M(x):x是人。则（2）符号化为：x(M(x)G(x),例5：在谓词逻辑中将下列命题符号化.（1）一些数是有理数。（2）有些人活百岁以上。,有时需要同时使用多个量词。例6.命题“对任意的x,存在y,使得x+y=5”,取个体域为实数集合,则该命题符号化为:xyH(x,y).其中H(x,y):x+y=5.这是个真命题.,2.1一阶逻辑命题符号化,3.使用量词时应注意的问题（1）在不同的个体域，同一命题的符号化形式可能相同也可能不同。（2）在不同的个体域，同一命题的真值可能相同也可能不同。(如,R（x）表示x为大学生。如果个体域为大学里的某个班级的学生，则xR（x）为真；若个体域为中学里的某个班级的学生，则xR（x）为假.).,2.1一阶逻辑命题符号化,（3）约定以后如不指定个体域，默认为全总个体域。对每个客体变元的变化范围,用特性谓词加以限制.特性谓词:限定客体变元变化范围的谓词(如例3中的M（x）).一般而言，对全称量词，特性谓词常作蕴含的前件，如（x）(M(x)F(x)；对存在量词，特性谓词常作合取项，如（x）(M(x)G(x).,2.1一阶逻辑命题符号化,2.1一阶逻辑命题符号化,(4)一般来说，当多个量词同时出现时，它们的顺序不能随意调换。如：在实数域上用H(x,y)表示x+y=5,则命题“对于任意的x,都存在y使得x+y=5”可符号化为：xyH(x,y),其真值为1.若调换量词顺序后为：yxH(x,y),其真值为0。(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),2.1一阶逻辑命题符号化,例7：在谓词逻辑中将下列命题符号化.（1）所有的人都长头发。（2）有的人吸烟。（3）没有人登上过木星。（4）清华大学的学生未必都是高素质的。解：令M(x):x是人。（特性谓词）（1）令F(x):x长头发。则符号化为：（x）(M(x)F(x),2.1一阶逻辑命题符号化,（2）令S(x):x吸烟。则符号化为：（x）(M(x)S(x)（3）令D(x):x登上过木星。则符号化为：(x)(M(x)D(x)（4）令Q(x):x是清华大学的学生。H(x):x是高素质的。则符号化为：(x)(Q(x)H(x),2.1一阶逻辑命题符号化,小结:本节将原子命题进行分解,分为客体和谓词两部分.进而介绍了客体和谓词、一元谓词和n元谓词、命题函数、全称量词和存在量词等概念。重点掌握：一元谓词和n元谓词的概念、全称量词和存在量词及量化命题的符号化。作业:1.预习4.22.习题4、5、6,上节学习了一阶逻辑的基本概念：个体词、谓词、量词一阶逻辑符号化的有关概念和方法本节学习一阶逻辑公式的概念：字母表、项、原子公式、公式、指导变元、辖域、闭式等一阶逻辑公式的解释及公式类型的判断。,2.2一阶逻辑公式及其解释,2.2一阶逻辑公式及其解释,一阶语言用于一阶逻辑公式的形式语言一、一阶语言F与合式公式定义4.1一阶语言F的字母表定义如下：（1）个体常项：a,b,c,ai,bi,ci,i1（2）个体变项：x,y,z,xi,yi,zi,i1（3）函数符号：f,g,h,fi,gi,hi,i1（4）谓词符号：F,G,H,Fi,Gi,Hi,i1（5）量词符号：,（6）联结词符号：,（7）括号与逗号：(,),，,2.2一阶逻辑公式及其解释,定义4.2F的项的定义如下：（1）个体常项和个体变项是项.（2）若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项.（3）所有的项都是有限次使用（1），（2）得到的.其实，个体常项、变项是项，由它们构成的n元函数和复合函数还是项.,2.2一阶逻辑公式及其解释,例1：D是个体名称的集合，x,y（D）为个体变项，a：张三，b：李四所以x，y，a，b是项假设f(x):x的父亲，F(x,y):x是y的父亲f(a),f(f(a),F(a,b),F(f(f(a),b)则f(a):张三的父亲，是项f(f(a):张三的祖父，是项,在谓词逻辑中，项起的是名词的作用，不是句子,2.2一阶逻辑公式及其解释,定义4.3设R(x1,x2,xn)是F的任意n元谓词，t1,t2,tn是F的任意的n个项，则称R(t1,t2,tn)是F的原子公式.其实，原子公式是由项组成的n元谓词.,原子公式是谓词逻辑公式的最小单位，最小的句子单位,2.2一阶逻辑公式及其解释,例1：D是个体名称的集合，x,y（D）为个体变项，a：张三，b：李四所以x，y，a，b是项假设f(x):x的父亲，F(x,y):x是y的父亲F(a,b):张三是李四的父亲，是原子公式F(f(f(a),b):张三的祖父是李四的父亲，是原子公式,定义4.4（谓词公式）谓词公式也称为合式公式，其递归定义如下：（1）原子公式是合式公式。（2）若A是合式公式，则(A)也是合式公式。（3）若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。（4）若A是合式公式，x是A中出现的任何变元,则(x)A,(x)A，也是合式公式。(5)只有有限次应用(1)(4)得到的公式是合式公式.,2.2一阶逻辑公式及其解释,二、封闭的公式（简称闭式）1量词的辖域、个体变项的约束与自由出现定义4.5在公式xA和xA中，称x为指导变元，A为相应量词的辖域.在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现的.,在公式x(F(x,y)G(x,z)中，设A=(F(x,y)G(x,z)（也可记为A(x)）,则x为指导变元，A为x的辖域，A中x的两次出现均为约束出现，y与z均为自由出现.,2.2一阶逻辑公式及其解释,说明:(1)n元谓词公式A(x1，x2.xn)中有n个自由变元,若对其中的k(kn)个进行约束,则构成了n-k元谓词;如果一个公式中没有自由变元出现,则该公式就变成了一个命题(2)一个公式的约束变元所使用的名称符号是无关紧要的,如(x)M(x)与(y)M(y)意义相同.,2.2一阶逻辑公式及其解释,辖域,自由变元与约束变元举例,在xP(x)Q(x)中,x的辖域是P(x);在y(C(y)x(T(x)uQ(x,u)中,u的辖域是Q(x,u);x的辖域是T(x)uQ(x,u);y的辖域是C(y)x(T(x)uQ(x,u).,2.2一阶逻辑公式及其解释,例：xy(P(x,y)Q(y,z)(x)p(x,y),下面的描述中错误的是（）A.(x)的辖域是（y）（P（x,y）Q(y,z)）Bz是该谓词公式的约束变元C.(x）的辖域是P（x,y）D.x是该谓词公式的约束变元,2闭式定义4.6若公式A中不含自由出现的个体变项，则称A为闭式.,例如:,xy(F(x)G(y)H(x,y),x(F(x)G(x,y),闭式,不是闭式,2.2一阶逻辑公式及其解释,由闭式定义可知，闭式中所有个体变元均为约束出现。例如，(x)(P(x)Q(x)和(x)(y)(P(x)Q(x,y)是闭式，而(x)(P(x)Q(x,y)和(y)(z)L(x,y,z)不是闭式。,2.2一阶逻辑公式及其解释,约束变元的换名与自由变元的代入规则一个变元在同一个公式中既是自由出现又是约束出现,这样在理解上容易发生混淆.为了避免这种混乱,可对约束变元进行换名.换名规则:(对约束变元而言）对约束变元进行换名,使得一个变元在一个公式中只呈一种形式出现.,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),2.2一阶逻辑公式及其解释,(1)约束变元可以换名,其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的该变元,公式的其余部分不变.(2)换名时一定要更改为作用域中没有出现的变元名称.,2.2一阶逻辑公式及其解释,例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),2.2一阶逻辑公式及其解释,例：xP(x)yR(x,y)可改写成:xP(x)zR(x,z)，但不能改成:xP(x)xR(x,x)，因为xR(x,x)中前面的x原为自由变元，现在变为约束变元了。,2.2一阶逻辑公式及其解释,代入规则（对自由变元而言）对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入,代入时需要对公式中出现该自由变元的每一处进行;(2)用以代入的变元与原公式中所有变元的名称不能相同.例如对例1中的公式x(P(x)R(x,y)L(x,y)自由变元y用z来代入,得x(P(x)R(x,z)L(x,z),2.2一阶逻辑公式及其解释,区别是命题还是命题函数的方法（a）若在谓词公式中出现有自由变元，则该公式为命题函数；（b）若在谓词公式中的变元均为约束变元，则该公式为命题。例：xP(x,y,z)是二元命题函数，yxP(x,y,z)是一元命题函数，谓词公式中如果没有自由变元出现，则该公式是一个命题。根据闭式定义和命题与命题函数的区别方法可知：闭式为命题，命题函数不是闭式。,三、解释与公式的分类1给定公式对它们进行解释：（1）给出公式x(F(x)G(x)一个成真解释，一个成假解释；（2）给出公式x(F(x)G(x)一个成真解释，一个成假解释；（3）xF(x)xF(x)有成真解释吗？（4）xF(x)xF(x)有成假解释吗？,2F中的解释定义4.7F的解释I由下面4部分组成：(a)非空个体域DI(b)DI中一些特定元素的集合(c)DI上特定函数集合(d)DI上特定谓词的集合,例：给定解释I如下：(a)个体域D=N（N为自然数集合，即N=0,1,2,）(b)(c)(d)为x=y.(e),在I下，下列哪些公式为真？哪些为假？哪些真知还不能确定？,3闭式的性质.定理4.1闭式在任何解释下都是命题.,4公式的类型定义4.8（1）永真式（逻辑有效式）（2）矛盾式（永假式）（3）可满足式,注意：不是闭式的公式在某些解释下也可能是命题.,说明：,永真式为可满足式，但反之不真;判断公式是否为永真式不是易事;通过某些代换实例可判断公式类型.,定义4.9设A0是含命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai(1in)处处代替A0中的pi，所得公式A称为A0的代换实例.,例如,定理4.2重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.,pq的代换实例,F(x)G(x),xF(x)yG(y),例判断下列公式中，哪些是永真式，哪些是矛盾式？（1）x(F(x)G(x)（2）x(F(x)G(x)（3）xF(x)(xyG(x,y)xF(x)（4）(xF(x)yG(y)yG(y),解（1），（2）为可满足式.（3）为p(qp)（重言式）的代换实例，为永真式.（4）为(pq)q（矛盾式）的代换实例，为永假式.,第四章小结,一、本章的主要内容与要求1主要内容个体词、谓词、量词；一阶逻辑命题符号化；F的合式公式、闭式；F的解释；公式的类型：永真式、矛盾式、可满足式,2要求（1）准确地将给定命题在F中符号化：当指定个体域时，就使用它；当没指定个体域时，就使用全总个体域；在符号化时注意两个基本公式中量词与联结词的搭配。（2）深刻理解永真式、矛盾式、可满足式的概念及相互之间的关系；（3）记住闭式的性质并能应用它；（4）对于给定的解释会判断公式的真值，或判定真值不确定（即仍不是命题）。,二、例1在一阶逻辑中将下面命题符号化，并讨论真值：（1）存在x，使得x+7=5(a)D1为全总个体域(b)D2=N(c)D3=R,（1）(a)xH(x)，H(x)：x+7=5，为真(b)x(F(x)H(x)，H(x)同(a)中，F(x)：x为自然数，为假.(c)x(F(x)H(x)，H(x)同(b)中，F(x)：x为实数，为真本例说明：不同个体域内，命题符号化形式可能不同（也可能相同），真值可能不同（也可能相同）.,2在一阶逻辑中将下列命题符号化（1）大熊猫都可爱（2）有人爱发脾气（3）说所有人都爱吃面包是不对的（4）没有不爱吃糖的人（5）一切人都不一样高（6）并不是所有的汽车都比火车快,由于没指出个体域，故用全总个体域（1）x(F(x)G(x)其中，F(x):x为大熊猫，G(x):x