《《阶谓词原理》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《阶谓词原理》PPT课件.ppt（35页珍藏版）》请在三一办公上搜索。
1、一阶谓词逻辑,CH4 一阶逻辑基本概念CH5 一阶逻辑等值演算与推理,*,2,内容要点：,置换规则,*,3,1.命题的表达,例1.1：凡偶数都能被2整除，6是偶数。所以，6能被2整除将它们命题符号化：p：凡偶数都能被2整除 q：6是偶数 r：6能被2整除则推理的形式结构符号化为：(p q)r,由于上式不是重言式，所以不能由它判断推理的正确性。为了克服命题逻辑的局限性，就应该将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是谓词逻辑。,*,4,(1)是自然数。(2)21世纪末，人类将住在月球。(3)x+y=y+x(4)只有x能被2整除，x才能被4整除
2、。,A.个体词,x,y的取值范围：复数域a的取值范围：整数域,是指所研究对象中可以独立存在的具体的或抽象的客体。,表示具体或特定的客体的个体词称作个体常项；常用a,b,c,表示。,表示抽象或泛指的客体的个体词称作个体变项；常用x,y,z,表示。,全总个体域：由宇宙间一切事物组成的域为全总个体域。,*,5,a.小陈是大学生 b.小张生于苏州 c.8=3*2 x是大学生 小陈-个体；是大学生-谓词：是大学生刻划了x 的性质x生于y 生于-谓词：刻划了x和y的关系,x=y*z.=.-谓词：刻划了x，y，z三 元的关系,一、谓词和个体,B.谓词,*,6,B.谓词,(1)是自然数。(2)21世纪末，人类
3、将住在月球。(3)x 与 y 具有关系L(4)只有x能被2整除，x才能被4整除。,谓词：用来刻划个体词性质及个体词之间相互关系的词,*,7,一般的用F(a)表示个体常项a具有性质F（F是谓词常项或谓词变项），用F(x)表示个体变项x具有性质F。而用F(a,b)表示个体常项a,b具有关系F，用F(x,y)表示个体变项x,y具有关系F。,定义：一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为谓词。如果括号内有n个客体变元，称该谓词为n元谓词。,*,8,例如 S(x):表示x是大学生。一元谓词 G(x,y)：表示 xy。二元谓词 B(x,y,z)：表示
4、x在y与z之间。三元谓词一般地 P(x1,x2,xn)是n元谓词。,0元谓词：有时将不带个体变项的谓词称为0元谓词，例如上面提到的F(a)，H(a,b)，P(a1,a2,an)等都是0元谓词，当F,H,P为谓词常项时，0元谓词为命题。这样，命题逻辑中的命题均可表示成0元谓词，因而可以将命题看成是特殊的谓词。,*,9,(1)2是素数且是偶数(2)如果2大于3，则2大于4 解：(1)设一元谓词F(x)：x是素数；一元谓词G(x)：x是偶数；a：2。则(1)中命题符号化为0元谓词的合取式：F(a)G(a)。(2)设二元谓词L(x,y)：x大于y；a：2；b：3；c：4.L(a,b),L(a,c)是两
5、个0元谓词，把(2)中命题符号化为L(a,b)L(a,c),例题：将下列命题用0元谓词符号化，并讨论它们的真值。,*,10,x读作对任意x xP(x)表示对一切x,P(x)为真 xP(x)表示 并非对任意x,P(x)是真,(1)全称量词x,C.量词,*,11,x读作至少有一x，存在一x x P(x)表示 存在一x，使P(x)为真 x P(x)表示 并非存在一个x，使 P(x)为真,(2)存在量词x,C.量词,*,12,在P(x)，P(x,y)前加上x或x，称变元x被存在量化或全称量化。,将谓词F(x)变成命题有两种方法。a.将x取定值 例：F(x)表示x是质数，那么F(4)是命题（假）b.将谓
6、词量化 例：1).xF(x)F(x)：任意的x是质数 2).y(yy+1)3).y(yy+1),量词的作用,C.量词,*,13,(1)分析命题中表示性质和关系的谓词，分别符号化为一元和n（n 2）元谓词。(2)根据命题的实际意义选用全称量词或存在量词。(3)在不同的个体域中，命题符号化的形式可能不一样。如果事先没有给出个体域，都应以全总个体域为个体域。(4)多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原命题的含义。,在使用量词时，应注意以下几点：,*,14,(5)当个体域为有限集时，如D=a1,a2,an，由量词的意义可以看出，对于任意的谓词A(x)，都有 x A(x)A(a1)A
7、(a2)A(an)x A(x)A(a1)A(a2)A(an)这实际上是将谓词逻辑中命题公式转化为命题逻辑中的命题公式问题。,*,15,1.设个体域为D=0,1,2,10,将下列命题符号化：(1)D中所有元素都是整数；(2)D中有的元素是偶数；(3)D中所有的偶数都能被2整除；(4)D中有的偶数是4的倍数。,D.举例,xF(x),其中F(x)：x是整数,xG(x),其中G(x)：x是偶数,x(G(x)H(x),其中G(x):x是偶数;H(x):x能被2整除,x(G(x)R(x),其中G(x):x是偶数;R(x):x是4的倍数,*,16,2.设个体域为D=x|x为人，将下列命题符号化：(1)人都生
8、活在地球上；(2)有的人长着黑头发；(3)中国人都用筷子吃饭；(4)有的中国人不住在中国；,D.举例,xF(x),其中F(x)：x生活在地球上,xG(x),其中G(x)：x长着黑头发,x(H(x)I(x),其中H(x):x是中国人；I(x)：x用筷子吃饭,x(H(x)R(x),其中H(x):x是中国人；R(x):x住在中国,*,17,D.举例,3.用量词、谓词来表述命题。(1)凡是人都是要死的。(2)某些实数是有理数。,x(F(x)H(x),其中F(x):x是人；H(x):是要死的；,x(G(x)Q(x),其中G(x):x是实数；H(x):是有理数；,4.在个体域限制为（a）和（b）条件时，将
9、下列命题符号化：（1）对于任意的x，均有x23x2(x1)(x-2)（2）存在x，使得x53 其中：（a）个体域D1N（N为自然数集合）（b）个体域D2R（R为实数集合）解：(a)令F(x)：x23x2(x1)(x-2)，G(x)：x53。命题（1）的符号化形式为 x F(x)(*)命题（2）的符号化形式为 x G(x)(*)显然（1）为真命题，而（2）为假命题。(b)在D2内，（1）与（2）的符号化形式还是(*)和(*)式，（1）仍然为真命题，而此时（2）也为真命题。,*,19,谓词逻辑中命题符号化一般遵循的原则：,(1)名词：专有名词多译为个体常元，如“地球”等；普通名词一般译为谓词，如“
10、自然数”；,(2)代词：无论是人称代词，如“你”，“我”，“他”等，还是指示代词，如“这个”，“那个”等多译为个体常元；,(3)形容词：多译为谓词；,(4)动词：多译为谓词；,(5)数量词：表示全体概念的数量词，如“每个”、“任何”、“所有”等译为全称量词，表示部分概念的数量词，如“有”、“存在”、“若干”、“有些”等，译为存在量词；,(6)副词和前置词与其它词类合并，不再进行单独分析；,(7)连词一般译为逻辑联结词。,*,20,定义：不出现命题联结词和量词的谓词命名式 P(X1,X2Xn)称为谓词演算的原子公式。,A.原子公式,2.谓词合式公式,前面例子中的1元谓词F(x)，G(x)，2元谓
11、词H(x,y)，L(x,y)等都是原子公式。,*,21,谓词合式公式简称谓词公式定义:1)原子公式是谓词合式公式 2)若A，B是谓词合式公式，则,(A)，(AB)，(AB)，(AB)，(AB)，(XA)和(XA)是谓词合式公式,3)只有有限次应用步骤1)和2)构成的公式才是谓词合式公式,注：由定义知，命题公式也是谓词公式例：XR(X)(XR(X)(XR(X)XS(X)(XR(X)XS(X)A(BC)命题公式均是谓词公式,B.谓词合式公式,*,22,定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。例：XP(X)Q(X)X的辖域是P(X)X(P(X
12、,Y)Q(X，Y)P(Y,Z)X的辖域是P(X，Y)Q(X，Y),(1)量词的辖域,C.自由变元与约束变元,*,23,定义：在量词X，X辖域内变元X的一切出现叫约束出现，称这样的X为约束变元。,变元的非约束出现称为自由出现,称这样的变元为自由变元。,例：指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域X(P(X)R(X)XP(X)Q(X)解：表达式中的X(P(X)R(X)中X的辖域是 P(X)R(X),其中的X是约束出现 Q(X)中的X是自由变元,*,24,例：指出下列谓词公式中的自由变元和约束变元。并指明量词的辖域(2)X(P(X，Y)YR(X，Y)解：其中的P(X，Y)中的Y是自由
13、变元，X是约束变元，R(X，Y)中的X，Y是约束变元。,注：在一个公式中，一个变元既可以约束出现，又可以 自由出现。为避免混淆可用改名规则对变元改名。,*,25,(1)若要改名，则该变元在量词及该量词的辖域中的所有 出现须一起更改。,(2)改名时所选用变元必须是量词辖域内未出现的，最好 是公式中未出现的。,注：对自由变元换名，可称为代入,D.约束变元改名规则,*,26,例1：X(P(X，Y)YR(X，Y)可改为 X(P(X，Y)ZR(X，Z)例2：XP(X)Q(X)可改为YP(Y)Q(X)例3：X(A(X)B(X，Y)C(X)D(W)可改为：X(A(X)B(X，Y)C(Z)D(W)注意：Z(A
14、(Z)B(Z，Y)C(X)D(W)不可改为：Y(A(Y)B(Y，Y)C(X)D(W),*,27,E.闭公式,定义：设A是任意的公式，若A中不含自由出现的个体变项，则称A为封闭的公式，简称闭式。例如，x(F(x)G(x)，x y(F(x)G(x,y)都是闭式，而x(F(x)G(x,y)，z y L(x,y,z)都不是闭式。要想使含有r(r1)个自由出现个体变项的公式变成闭式，至少要加上r个量词,*,28,例题：在一阶逻辑中将简单的数学命题符号化,1.设个体域为整数集合Z，将下列问题符号化：(1)对于任意的x和y，存在着z，使得x+y=z;(2)存在着x，对于任意的y和z，均有y-z=x是不成立的
15、。(3)设y=f(x)在x=x0处连续，将下面命题符号化。任给Z0，存在d 0,使得当|x-x0|d 时，均有|f(x)-f(x0)|Z.,xyz(x+y=z),(xyz(x2+y2=z2),Z0d0(|x-x0|d|f(x)-f(x0)|Z),*,29,谓词公式的解释：,定义 一个解释I由下面4部分组成：（1）非空个体域D；（2）D中一些特定元素的集合（3）D上特定函数集合（4）D上特定谓词的集合,在I 下，下列哪些公式为真？哪些为假？哪些的真值还不能确定？,(1)F(f(x,y),g(x,y),在I下，被解释成“x+y=xy”,这不是命题,(2)F(f(x,a),y)F(g(x,y),z)
16、,在I下，被解释成“(x+0=y)(xy=z)”,这不是命题,(3)F(g(x,y),g(y,z),在I下，被解释成“xyyz”,这不是命题,(4)xF(g(x,y),z),在I下，被解释成“x(xyz)”,这不是命题,(5)xF(g(x,a),x)F(x,y),在I下，被解释成“x(x0=x)(x=y)”,由于蕴含式前件为假，所以被解释的公式为真。,(6)xF(g(x,a),x),在I下，被解释成“x(x0=x)”,这不是命题,(7)xy F(f(x,a),y)F(f(y,a),x),在I下，被解释成“xy(x+0=y)(y+0=x)”,这是真命题,(8)xyz F(f(x,y),z),在I
17、下，被解释成“xyz(x+y=z)”,这是真命题,(9)x F(f(x,x),g(x,x),在I下，被解释成“x(x+x=xx)”,这是真命题,解 为方便起见，用A，B，C分别记(1)，(2)，(3)中的公式。(1)取解释I1:个体域为实数集合R，F(x):x是整数，G(x):x是有理数。在I1下A为真，因而A不是矛盾式。取解释I2:个体域仍然为R，F(x):x是无理数，G(x):x能表示成分数。在I2下A为假，所以A不是永真式。故A是非永真式的可满足式。(2)易知B是命题公式p(qp)的代换实例，而该命题公式是重言式，所以B是永真式。(3)C是命题公式(pq)q的代换实例，而该命题公式是矛盾
18、式，所以C是矛盾式。,*,32,注：,在证明一个谓词公式既不是永真式也不是矛盾式时，可以为公式分别找一个成真的解释和一个成假的解释。当证明一个谓词公式是永真式或矛盾式时，可以使用相应的命题公式进行代换。若命题公式为永真式，则原谓词公式也是永真式；若命题公式为矛盾式，则原谓词公式也是矛盾式。,*,33,内容小结：,置换规则,*,34,CH4基本要求,准确的将给定命题符号化掌握永真式、矛盾式和可满足式的概念及判断方法深刻理解闭式的概念及闭式的性质（闭式在任何解释下都是命题）对于给定的解释会判断给定公式是否成为命题，对是命题的能够判断出真假,*,35,Ch作业,P681，3，5，6(1)(2)，7，8，10，11(1)(2)(3)12,
