资源描述
1,第2章一阶逻辑,2.1一阶逻辑基本概念2.2一阶逻辑合式公式及解释2.3一阶逻辑等值式与前束范式,2,2.1一阶逻辑基本概念,个体词谓词量词一阶逻辑中命题符号化,命题逻辑的局限性,苏格拉底三段论：凡是人都要死的.苏格拉底是人.所以苏格拉底是要死的.在命题逻辑中，只能用p、q、r表示以上3个命题，上述推理可表成(pq)r这不是重言式,3,4,基本概念个体词、谓词、量词,个体词（个体）:所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a,b,c表示个体变项：抽象的事物，用x,y,z表示个体域:个体变项的取值范围有限个体域，如a,b,c,1,2无限个体域，如N,Z,R,全总个体域:宇宙间一切事物组成,5,基本概念(续),谓词:表示个体词性质或相互之间关系的词谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F一元谓词:表示事物的性质多元谓词(n元谓词,n2):表示事物之间的关系如L(x,y)：x与y有关系L，L(x,y)：xy，0元谓词:不含个体变项的谓词,即命题常项或命题变项,6,基本概念(续),量词:表示数量的词全称量词:表示任意的,所有的,一切的等如x表示对个体域中所有的x存在量词:表示存在,有的,至少有一个等如x表示在个体域中存在x,7,一阶逻辑中命题符号化,例用0元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1)墨西哥位于南美洲,在命题逻辑中,设p:墨西哥位于南美洲符号化为p,在一阶逻辑中,设a：墨西哥，F(x)：x位于南美洲,符号化为F(a),8,例(续),(2)是无理数仅当是有理数,在命题逻辑中,设p：是无理数，q：是有理数.符号化为pq,在一阶逻辑中,设F(x):x是无理数,G(x):x是有理数符号化为,在命题逻辑中,设p：23，q：3y，G(x,y)：x3，则3yx(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)两者等值,11,一阶逻辑中命题符号化(续),几点注意：1元谓词与多元谓词的区分无特别要求,应使用全总个体域,引入特性谓词量词顺序一般不能随便颠倒两个基本形式x(F(x)G(x)和x(F(x)G(x)的使用否定的表示，如“没有不呼吸的人”等同于“所有的人都呼吸”“不是所有的人都喜欢吃糖”等同于“存在不喜欢吃糖的人”,12,2.2一阶逻辑公式及解释,合式公式(简称公式)个体变项的自由出现和约束出现解释与赋值公式分类永真式，矛盾式,可满足式,13,字母表,定义字母表包含下述符号：(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)括号与逗号：(,),，,14,项,定义项的定义如下：(1)个体常项和个体变项是项.(2)若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的.个体常项、变项是项，由它们构成的n元函数和复合函数还是项,15,原子公式,定义设R(x1,x2,xn)是任意的n元谓词，t1,t2,tn是任意的n个项，则称R(t1,t2,tn)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式,16,合式公式,定义合式公式（简称公式）定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式，则xA,xA也是合式公式(5)只有有限次地应用(1)(4)形成的符号串是合式公式.如x0,x(F(x)G(x),xy(x+y=1),17,个体变项的自由出现与约束出现,定义在公式xA和xA中，称x为指导变元，A为相应量词的辖域.在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现.例如,在公式x(F(x,y)G(x,z)中,A=(F(x,y)G(x,z)为x的辖域，x为指导变元,A中x的两次出现均为约束出现，y与z均为自由出现.闭式:不含自由出现的个体变项的公式.,18,公式的解释与分类,给定闭式A=x(F(x)G(x)取个体域N,F(x):x2,G(x):x1代入得A=x(x2x1)真命题给定非闭式B=xF(x,y)取个体域N,F(x,y):xy代入得B=x(xy)不是命题令y=1,B=x(x1)假命题,19,解释和赋值,定义解释I由下面4部分组成：(a)非空个体域DI(b)对每一个命题常项a指定一个DI(c)对每一个函数符号f指定一个DI上的函数(d)对每一个谓词符号F指定一个DI上的谓词赋值：对每一个命题变项x指定一个值(x)DI公式A在解释I和赋值下的含义：取个体域DI,并将公式中出现的a、f、F分别解释成、,把自由出现的x换成(x)后所得到的命题.在给定的解释和赋值下,任何公式都成为命题.,20,实例,例给定解释I如下:(a)个体域D=N(b)(c)(d)谓词以及赋值：(x)=0,(y)=1,(z)=2.说明下列公式在I与下的涵义,并讨论真值(1)xF(g(x,a),y),x(2x=1)假命题,21,例(续),(2)xF(f(x,a),y)yF(x,f(y,a),x(x+2=1)y(0=y+2)真命题,xyz(x+y=z)真命题,(3)xF(f(x,y),g(x,z),x(x+1=2x)真命题,(5)xyzF(f(y,z),x),xyz(y+z=x)假命题,(4)xyzF(f(x,y),z),闭式只需要解释,如(4),(5),22,公式的分类,永真式(逻辑有效式):在任何解释和赋值下为真命题矛盾式(永假式):在任何解释和赋值下为假命题可满足式：存在成真的解释和赋值说明：永真式为可满足式，但反之不真谓词公式的可满足性（永真性,永假性)是不可判定的,23,代换,定义设A0是含命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai处处代替A0中的pi(1in)，所得公式A称为A0的代换实例.如F(x)G(x),xF(x)yG(y)是pq的代换实例定理重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.,实例,例判断下列公式的类型(1)xF(x)xF(x)；,24,设I为任意的解释，若xF(x)为假，则xF(x)xF(x)为真.若xF(x)为真，则xF(x)也为真，所以xF(x)xF(x)也为真.是逻辑有效式.,(2)xF(x)(xyG(x,y)xF(x)；,重言式p(qp)的代换实例，是逻辑有效式.,例(续),(3)xF(x)(xF(x)yG(y)；,25,重言式p(pq)的代换实例,是逻辑有效式.,(4)(F(x,y)R(x,y)R(x,y)；,矛盾式(pq)q的代换实例,是矛盾式.,例(续),(5)xyF(x,y)xyF(x,y).,26,取解释I：个体域N,F(x,y)为x=y.公式被解释为xy(x=y)xy(x=y)，其值为假.,解释I:个体域N,F(x,y)为xy,得到一个新的在I下,公式被解释为xy(xy)xy(xy)，其值为真.是非逻辑有效式的可满足式.,例(续),(6)xF(x,y),27,取解释I：个体域N,F(x,y)为xy.赋值1：1(y)=1.在I和1下,x(x1)，真命题.,取解释I:个体域N,F(x,y)为xy.赋值2：2(y)=0.在I和2下,x(x0)，假命题是非逻辑有效式的可满足式.,
展开阅读全文