《阶逻辑基本概念》PPT课件.ppt

第四章一阶逻辑基本概念,本章的主要内容一阶逻辑基本概念、命题符号化一阶逻辑公式、解释及分类,4.1一阶逻辑命题符号化,一、基本概念个体词、谓词、量词,（1）个体常项：具体的事务，用a,b,c表示,（2）个体变项：抽象的事物，用x,y,z表示,（3）个体域个体变项的取值范围,有限个体域，如a,b,c,1,2无限个体域，如N,Z,R,全总个体域宇宙间一切事物组成,1个体（个体词）所研究对象中可以独立存在的具体或抽象的客体（名词或代词充当）,2.谓词表示个体词性质或相互之间关系的词,（1）谓词常项：F:是人，F(a)：a是人,（2）谓词变项：F:具有性质F，F(x)：x具有性质F,（3）n（n1）元谓词n=1，一元谓词表示性质n2，多元谓词表示事物之间的关系L(x,y)：x与y有关系L，L(x,y)：xy，,(4)0元谓词不含个体变项的谓词(命题常项或变项),3量词表示数量的词（1）全称量词：“”，x（2）存在量词：“”，x,例用0元谓词将命题符号化：（1）墨西哥位于南美洲（2）是无理数仅当是有理数（3）如果23，则33，q：3y，G(x,y)：xyx(F(x)y(G(y)L(x,y)xy(F(x)G(y)L(x,y)（以后讨论）,（2）令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：xyx(F(x)y(G(y)L(x,y)xy(F(x)G(y)L(x,y)（以后讨论）,注意否定式的使用：没有不呼吸的人不是所有的人都喜欢吃糖不是所有的火车都比所有的汽车快以上命题应如何符号化？,练习：1、令S(x):x是学生；F(x):x是教授；A(x,y):x问过y问题；论域是学校所有人员的集合.符号化下列语句:（1）lois问过Gross问题。（2）每个学生都问过Gross问题。（3）每位学生都问过Gross问题或被Gross问过问题。（4）某个学生从未问过任何教授问题。（5）有位教授从未被学生问过问题。（6）有个学生问过所有教授问题。,1、解：(1)A(lois,Gross)(2)x(S(x)A(x,Gross)(3)x(S(x)(A(x,Gross)A(Gross,x)(4)x(S(x)y(F(y)A(x,y)(5)x(F(x)y(S(y)A(y,x)(6)x(S(x)y(F(y)A(x,y),2（1）所有的狮子都是凶猛的。（2）有些狮子不喝咖啡。（3）有些凶猛的动物不喝咖啡。论域为动物的集合：3、如果某人是女性而且有子女，那么此人一定是某人的母亲。论域为人的集合。,2、解：令P(x):x是狮子；Q(x):x是凶猛的；R(x):x喝咖啡；则有：(1)x(P(x)Q(x)(2)x(P(x)R(x)(3)x(Q(x)R(x)3、解：令F(x):x是女性；P(x):x有子女；M(x,y):x是y的母亲；则有：x(F(x)P(x)yM(x,y),4.2一阶逻辑公式及解释,一阶语言用于一阶逻辑公式的形式语言一、一阶语言F与合式公式1F的字母表，定义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）括号与逗号：(,),，,2F的项定义4.2F的项的定义如下：（1）个体常项和个体变项是项.（2）若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项.（3）所有的项都是有限次使用（1），（2）得到的.其实，个体常项、变项是项，由它们构成的n元函数和复合函数还是项.,3F的原子公式定义4.3设R(x1,x2,xn)是F的任意n元谓词，t1,t2,tn是F的任意的n个项，则称R(t1,t2,tn)是F的原子公式.其实，原子公式是由项组成的n元谓词.,例如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式,4F的合式公式定义4.4.F的合式公式定义如下：（1）原子公式是合式公式.（2）若A是合式公式，则(A)也是合式公式（3）若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式.（4）若A是合式公式，则xA,xA也是合式公式.（5）只有有限次地应用（1）（4）形成的符号串才是合式公式.,二、封闭的公式（简称闭式）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闭式定义4.6若公式A中不含自由出现的个体变项，则称A为闭式.,例如:,xy(F(x)G(y)H(x,y),x(F(x)G(x,y),闭式,不是闭式,三、解释与公式的分类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.,在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的代换实例,非pq的代换实例,x(F(x)G(x),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，可进行因式分解，即（2）存在x，使得x+7=5(a)D1为全总个体域(b)D2=N(c)D3=R,（1）(a)xG(x)，G(x)：,为真(b)x(F(x)G(x)，其中G(x)同(a)中，F(x)：x是自然数，为假（会出现前件真，后件假）(c)x(F(x)G(x)，F(x)：x是实数,G(x)同(b)中，为真（2）(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可爱（2）x(F(x)G(x)其中，F(x):x是人，G(x):x爱发脾气（3）x(F(x)G(x)或x(F(x)G(x)其中，F(x):x是人，G(x):x爱吃面包（4）x(F(x)G(x)或x(F(x)G(x)其中，F(x):x是人，G(x):x爱吃糖（5）x(F(x)y(F(y)H(x,y)L(x,y),或xy(F(x)F(y)H(x,y)L(x,y)其中，F(x):x是人,H(x,y),x与y相同,L(x,y):x与y一样高（6）xy(F(x)G(y)H(x,y)或xy(F(x)G(y)H(x,y)其中,F(x):x是汽车,G(y):y是火车,H(x,y):x比y快,说明：,使用的是全总个体域(1)与(2)是两个基本公式的使用(3)与(4)是否定式(5)与(6)使用了二元谓词(3)-(6)的不同符号化形式是等值的,3.给定解释I如下:(a)个体域D=N(b)=2(c)(x,y)=x+y,(x,y)=xy(d)谓词(x,y):x=y说明下列公式在I下的涵义,并讨论真值(1)xF(g(x,a),x)(2)xy(F(f(x,a),y)F(f(y,a),x)(3)xyzF(f(x,y),z)(4)xF(f(x,x),g(x,x)(5)xyzF(f(y,z),x),答案(3),(4)为真,其余的均为假,说明：5个小题都是闭式,在I下全是命题；(3)与(5)说明，量词顺序不能随意改变。,练习：1、证明：(PQ),(