第四章-一阶逻辑基本概念

第四章一阶逻辑基本概念【教学目的与要求】1．掌握一阶逻辑的命题符号化；2．理解谓词公式与解释。【教学重点、难点】个体词、谓词、量词；谓词公式及其解释。【教学方法】：讲授法【主要内容】一阶逻辑命题符号化个体词、谓词、量词一阶逻辑命题符号化一阶逻辑公式及其解释一阶语言合式公式合式公式的解释永真式、矛盾式、可满足式【教学过程】4.1一阶逻辑命题符号化1.个体词——所研究对象中可以独立存在的具体或抽象的客体。个体常项：具体的事务，用a,b,c表示。个体变项：抽象的事物，用x,y,z表示。个体域(论域)——个体变项的取值范围。有限个体域，如{a,b,c},{1,2}；无限个体域，如N,Z,R,…；全总个体域——由宇宙间一切事物组成。2.谓词——表示个体词性质或相互之间关系的词。谓词常项如,F(a)：a是人谓词变项如,F(x)：x具有性质Fn（n1）元谓词一元谓词(n=1)——表示性质；多元谓词(n2)——表示事物之间的关系。如,L(x,y)：x与y有关系L，L(x,y)：xy，…0元谓词——不含个体变项的谓词,即命题常项或命题变项。3.量词——表示数量的词全称量词:表示所有的.x:对个体域中所有的x.如,xF(x)表示个体域中所有的x具有性质F；xyG(x,y)表示个体域中所有的x和y有关系G。存在量词:表示存在,有一个.x:个体域中有一个x.如,xF(x)表示个体域中有一个x具有性质F;xyG(x,y)表示个体域中存在x和y有关系G.xyG(x,y)表示对个体域中每一个x都存在一个y使得x和y有关系G;xyG(x,y)表示个体域中存在一个x使得对每一个y,x和y有关系G.例1用0元谓词将命题符号化(1)墨西哥位于南美洲;(2)2是无理数仅当3是有理数;(3)如果23，则34.解：在命题逻辑中：(1)p,p为墨西哥位于南美洲（真命题）.(2)p→q,其中,p:2是无理数，q：3是有理数.是假命题.(3)pq,其中，p：23，q：34.是真命题.在一阶逻辑中：(1)F(a)，其中，a：墨西哥，F(x)：x位于南美洲.(2)F(2)G(3),其中，F(x)：x是无理数，G(x)：x是有理数.(3)F(2,3)G(3,4)，其中，F(x,y)：xy，G(x,y)：xy.例2在一阶逻辑中将下面命题符号化(1)人都爱美;(2)有人用左手写字.个体域分别为(a)D为人类集合;(b)D为全总个体域.解:(a)(1)xG(x),G(x)：x爱美(2)xG(x),G(x)：x用左手写字(b)F(x)：x为人，G(x)：x爱美(1)x(F(x)G(x))(2)x(F(x)G(x))注：1.引入特性谓词F(x)；2.(1),(2)是一阶逻辑中两个“基本”公式。例3在一阶逻辑中将下面命题符号化(1)正数都大于负数；(2)有的无理数大于有的有理数。解注意：题目中没给个体域，一律用全总个体域(1)令F(x)：x为正数，G(y)：y为负数,L(x,y)：xyx(F(x)y(G(y)L(x,y)))或者xy(F(x)G(y)L(x,y))(2)令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：xyx(F(x)y(G(y)L(x,y)))或者xy(F(x)G(y)L(x,y))例4在一阶逻辑中将下面命题符号化(1)没有不呼吸的人；(2)不是所有的人都喜欢吃糖。解：(1)F(x):x是人,G(x):x呼吸x(F(x)G(x))x(F(x)G(x))(2)F(x):x是人,G(x):x喜欢吃糖x(F(x)G(x))x(F(x)G(x))例5设个体域为实数域,将下面命题符号化(1)对每一个数x都存在一个数y使得xy(2)存在一个数x使得对每一个数y都有xy解：L(x,y):xy(1)xyL(x,y)(2)xyL(x,y)注意:与不能随意交换.显然(1)是真命题,(2)是假命题.4.2一阶逻辑公式及解释1.定义4.1设L是一个非逻辑符集合,由L生成的一阶语言L的字母表包括下述符号：非逻辑符号(1)个体常项符号：a,b,c,…,ai,bi,ci,…,i1(2)函数符号：f,g,h,…,fi,gi,hi,…,i1(3)谓词符号：F,G,H,…,Fi,Gi,Hi,…,i1逻辑符号(4)个体变项符号：x,y,z,…,xi,yi,zi,…,i1(5)量词符号：,(6)联结词符号：,,,,(7)括号与逗号：(,),，定义4.2L的项的定义如下：(1)个体常项和个体变项是项.(2)若(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任意的n个项，则(t1,t2,…,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的.如,a,x,x+y,f(x),g(x,y)等都是项定义4.3设R(x1,x2,…,xn)是L的任意n元谓词，t1,t2,…,tn是L的任意n个项，则称R(t1,t2,…,tn)是L的原子公式.如，F(x,y),F(f(x1,x2),g(x3,x4))等均为原子公式定义4.4L的合式公式定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式，则xA,xA也是合式公式(5)只有有限次地应用(1)—(4)形成的符号串才是合式公式.合式公式简称公式.如,F(x),F(x)G(x,y),x(F(x)G(x)),xy(F(x)G(y)L(x,y))等都是合式公式.定义4.5在公式xA和xA中，称x为指导变元，A为相应量词的辖域.在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现的.例如，x(F(x,y)G(x,z))，x为指导变元，(F(x,y)G(x,z))为x的辖域，x的两次出现均为约束出现，y与z均为自由出现；又如,x(F(x,y,z)y(G(x,y)H(x,y,z))),x中的x是指导变元,辖域为(F(x,y,z)y(G(x,y)H(x,y,z))).y中的y是指导变元,辖域为(G(x,y)H(x,y,z)).x的3次出现都是约束出现,y的第一次出现是自由出现,后2次是约束出现,z的2次出现都是自由出现。定义4.6若公式A中不含自由出现的个体变项，则称A为封闭的公式，简称闭式.例如，xy(F(x)G(y)H(x,y))为闭式，而x(F(x)G(x,y))不是闭式。定义4.7设L是L生成的一阶语言,L的解释I由4部分组成：(a)非空个体域DI.(b)对每一个个体常项符号aL,有一个aDI,称a为a在I中的解释.(c)对每一个n元函数符号fL,有一个DI上的n元函数,称f为f在I中的解释.(d)对每一个n元谓词符号FL,有一个DI上的n元谓词常项F,称F为F在I中的解释.设公式A,取个体域DI,把A中的个体常项符号a、函数符号f、谓词符号F分别替换成它们在I中的解释a、f、F,称所得到的公式A为A在I下的解释,或A在I下被解释成A.例6给定解释I如下：(a)个体域D=R；(b)0a；(c)yxyxgyxyxf),(,),(；(d)yxyxF:),(写出下列公式在I下的解释,并指出它的真值.(1)xF(f(x,a),g(x,a))x(x+0=x0)真(2)xy(F(f(x,y),g(x,y))F(x,y))xy(x+y=xyx=y)假(3)xF(g(x,y),a)x(xy=0)真值不定,不是命题2.公式的类型定理4.1闭式在任何解释下都是命题.InIDDf:注意:不是闭式的公式在解释下可能是命题,也可能不是命题.定义4.8若公式A在任何解释下均为真,则称A为永真式(逻辑有效式).若A在任何解释下均为假,则称A为矛盾式(永假式).若至少有一个解释使A为真,则称A为可满足式.几点说明：永真式为可满足式，但反之不真；判断公式是否是可满足的(永真式,矛盾式)是不可判定的。定义4.9设A0是含命题变项p1,p2,…,pn的命题公式，A1,A2,…,An是n个谓词公式，用Ai(1in)处处代替A0中的pi，所得公式A称为A0的代换实例.例如，F(x)G(x),xF(x)yG(y)等都是pq的代换实例.定理4.2重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.例7判断下列公式中，哪些是永真式，哪些是矛盾式？(1)xF(x)(xyG(x,y)xF(x))重言式p(qp)的代换实例，故为永真式.(2)(xF(x)yG(y))yG(y)矛盾式(pq)q的代换实例，故为永假式.(3)x(F(x)G(x))解释I1:个体域N,F(x):x5,G(x):x4,公式为真解释I2:个体域N,F(x):x5,G(x):x4,公式为假结论:非永真式的可满足式