离散数学PPT教学谓词逻辑.ppt

《离散数学PPT教学谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学PPT教学谓词逻辑.ppt（75页珍藏版）》请在三一办公上搜索。

1、第三章 谓词逻辑,第一节 谓词和量词第二节 谓词演算的永真公式第三节 前 束 范 式,本 章 重 难 点,重点：1、谓词，个体域，全总体域，全称量词，存在量词，谓词公式的定义和理解；2、谓词公式的符号化形式3、谓词演算推理中的等价公式难点：1、谓词公式的翻译2、谓词演算的推理理论,为什么引入谓词逻辑？,著名的苏格拉底三段论问题！：所有的人都是要死的。：苏格拉底是人。：所以苏格拉底是要死的。无法用命题逻辑推理证明：但用自然语言逻辑可推出是有效结论！可看出命题逻辑的局限性，由此引出谓词逻辑！,一、谓词二、量词 1.全称量词x 2存在量词x 3量词的作用 4全总个体域 5举例 三、量化断言和命题的关

2、系,第一节 谓词和量词,四、谓词公式 1.原子公式 2.谓词演算的合式公式 五、自由变元与约束变元 1.量词的辖域 2.自由变元与约束变元 3.约束变元改名规则,第一节 谓词和量词,a.小陈是大学生 b.小张生于苏州 c.8=3*2 x是大学生 小陈-客体；是大学生-谓词：是大学生刻划了x 的性质x生于y 生于-谓词：刻划了x和y的关系,一、谓 词,x=y*z.=.-谓词：刻划了x，y，z三 元的关系,定义 返回目录,1定义：代表客体（个体）的变元叫客体（个体）变元。,一、谓 词,例：A表示 是大学生 则A(x)表示x是大学生这个命题变元 B表示 生于 则B（x,y）表示x生于y这个命题变元

3、C表示=*，则C(x,y,z)表示x=y*z这个命题 变元 A(x)，B(x,y)，C(x，y，z)称为谓词 定义2 返回,客体（个体）变元常用x，y，z，u，v表示，刻划客体的性质或几个客体间关系的模式叫谓词，常用大写字母A，B，P，Q,表示。,2.定义：有N个客体变元的谓词称为N元谓词 谓词命名式中客体变元的取值范围叫客体域 例：论述域a人，b人，地名，c实数，实数，实数 注意：空集不能作为论述域 若A代表一特定谓词，A称为谓词常元。若A 代表任意谓词，A称为谓词变元。注：(1)单独的客体或单独的谓词不能构成命题,一、谓 词,(2)在谓词命名式中,若谓词是常元,个体变元代以 论述域中某客体

4、才成为命题,(3)命题是0元谓词 返回,x读作对任意x xP(x)表示：对一切x,P(x)为真 xP(x)表示：对任意x,P(x)是真xP(x)表示：并非对任意x,P(x)是真 xP(x)表示：并非对任意x,P(x)是真,二、量 词,1.全称量词x,x读作至少有一x，存在一x x P(x)表示 存在一x，使P(x)为真 x P(x)表示 并非存在一个x，使 P(x)为真,二、量 词,2存在量词x,返回目录,在P(x)，P(x,y)前加上x或x，称变元x被存在量 化或全称量化。,二、量 词,将谓词F(x)变成命题有两种方法。a.将x取定值 例：F(x)表示x是质数，那么F(4)是命题（假）b.将

5、谓词量化 例：1).xF(x)F(x)：任意的x是质数 2).y(yy+1)3).y(yy+1)返回目录,3量词的作用,任意谓词中任意个体变元的所有个体域称全总个体域。注：使用全总个体域后，个体变元取值范围一致。但不同论述对象须用不同的特性谓词加以刻划。例：F(x)：x是不怕死的 D(x)：x是要死的 M(x)：x是人 解：返回目录,二、量 词,4.全总个体域,4全总个体域 例：若论述域是全人类：则人总是要死的 可译为 xD(x)有些人不怕死 可译为 xD(x)返回,4全总个体域若论述域是全总个体域：则译为x(M(x)D(x)注意：不能译为x(M(x)D(x)。这样意义成为 所有的x，x都是人

6、并且都是要死的。全总个体域 人全总个体域要死的二条规则 返回,4全总个体域 故得二条规则：对全称量词，特性谓词作为蕴含式之前件而加入之。对存在量词，特性谓词作为合取项而加入之。返回,5、举例 a，b，c，d，e 注：命题翻译为谓词公式，由于对个体的刻划深度不 同，可译成不同形式的谓词公式。返回目录,5、举例 a.没有不犯错误的人 解：设F(x)为x是犯错误,M(x)为x是人,则译为:(x(M(x)F(x)返回,b.某些人对某些食物过敏 解：设F(x,y)为x对y过敏,M(x)为x是人,G(x)为x是食物,则译为:x y(M(x)G(x)F(x,y)返回,c.尽管有人聪明，但未必一切人聪明 解：

7、设M(x)为x是人,F(x)为x聪明则译为:x(M(x)F(x)x(M(x)F(x)返回,d.如果XY，并且Z 0，那么XYYZ 解：设(X,Y)为XY，R(X)为X是实数 则译为：XYZ(R(X)R(Y)R(Z)(X,Y)(Z,0)(XY,YZ)返回,e.每个建筑物都有一些装饰品 解：设A(X)为X是建筑物,B(X,Y)为X有Y，C(X)为 X是装饰品，则可译为：X(A(X)Y(B(X,Y)C(Y)返回,1.若论述域是有限的，设是1，2，N 则XP(X)P(1)P(2)P(N)XP(X)P(1)P(2)P(N)2.若论述域是可数无限 则XP(X)为P(0)P(1)P(2)P(N)XP(X)为

8、P(0)P(1)P(2)P(N),三、量化断言和命题的关系,返回目录,定义：不出现命题联结词和量词的谓词命名式 P(X1,X2Xn)称为谓词演算的原子公式。返回目录,四、谓 词 公 式,1.原子公式,谓词演算的合式公式简称谓词公式定义:1)谓词演算的原子公式是谓词演算公式 2)若A，B是谓词演算公式，则,2、谓词演算的合式公式,返回目录,(A)，(AB)，(AB)，(AB)，(AB)，(XA)和(XA)是谓词演算公式,3)只有有限次应用步骤1）和2）构成的公式才是谓词演算公式,注：由定义知，命题公式也是谓词公式例：XR(X)(XR(X)(XR(X)XS(X)(XR(X)XS(X)AB C 命题

9、公式均是谓词公式,定义:量词的辖域是邻接量词之后的最小子公式，故除 非辖域是个原子公式，否则应在该子公式的两端 有括号。例：XP(X)Q(X)X的辖域是P(X)X(P(X,Y)Q(X，Y)P(Y,Z)X的辖域是P(X，Y)Q(X，Y)返回目录,五、自由变元与约束变元,1.量词的辖域,定义：在量词X，X辖域内变元X的一切出现叫约束出 现，称这样的X为约束变元。,变元的非约束出现称为自由出现,称这样的变元 为自由变元。例 返回目录,五、自由变元与约束变元,例：指出下列谓词公式中的自由变元和约束变元。并指明量词的辖域a.X(P(X)R(X)XP(X)Q(X)解：表达式中的X(P(X)R(X)中X的辖

10、域是 P(X)R(X),其中的X是约束出现 Q(X)中的X是自由变元b.X(P(X，Y)YR(X，Y)解：其中的P(X，Y)中的Y是自由变元，X是约束变元，R(X，Y)中的X，Y是约束变元。,注：在一个公式中，一个变元既可以约束出现，又可以 自由出现。为避免混淆可用改名规则对变元改名。返回,五、自由变元与约束变元,1.若要改名，则该变元在量词及该量词的辖域中的所有 出现须一起更改。,3、约束变元改名规则,2.改名时所选用变元必须是量词辖域内未出现的，最好 是公式中未出现的。,注：对自由变元换名，可称为代入例 返回目录上一页26 下一页28,例1：X(P(X，Y)YR(X，Y)可改为 X(P(X

11、，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(Z)B(Z，Y)C(X)D(W)不可改为：Y(A(Y)B(Y，Y)C(X)D(W)（想想为什么？）返回,3、约束变元改名规则,一.基本定义 二.谓词演算的基本永真公式上一节 下一节,第二节 谓词演算的永真公式,1.公式A和B在个体域上等价定义：,一、基 本 定 义,对公式A和B中的谓词变元（包括命题变元），指派任 一在E上有定义的确定的谓词，指派E中任一确定的个 体，若所得命题有相同的真值，称在E上AB。,2.A与B等价

12、定义：若两公式A，B在任意论述域上都等价，称AB。3 返回目录,3.对任一公式A，若在论述域E上，对A中的谓词和个体变元进行指派后，所得命题：,一、基 本 定 义,1)都真。称A在E上永真或在E上有效，若E任意，称A永真。2)至少一个为真，称A在E上可满足。3)都假，称A永假或在E上不可满足。若E任意，称A永假或不可满足。,注：当谓词公式A的个体域有限，谓词变元的指派也有限，才能用真值表判定A是否为永真。例,返回,例：当A（x）P（x）X P（x）且P（x）只能解释：（1）R（x）：x是质数（2）S（x）：x是合数。论述域为3，4，判定A（x）是否为永真解：P（x）x P（x）X P（x）-R

13、(x)3 111 S(x)3 010 R(x)4 010 S(x)4 111 所以，一般用真值表难以判定谓词公式是否为真。必须使用推导方法。首先讨论基本的谓词公式永真公式,一、基 本 定 义,1.命题演算的永真公式也是谓词演算的永真公式2.含有量词的谓词演算的永真公式3.量词的否定4.量词辖域的扩展和收缩5.结束量词的分配公式6.量词对及的处理7.关于多个量词的永真式 返回 返回目录,二、谓词演算的基本永真公式,例：XP(X)XR(X)XP(X)XR(X)例：Q(X)XP(X)(Q(X)XP(X)返回,1、命题演算的永真公式也是谓词演算的永真公式,1).XA A XA A 这里A不含自由变元X

14、 证：因A的真值与X无关例 XP(y，z)P(y，z)但是：yP(y，z)P(y，z)(不一定成立)2)返回,2、含有量词的谓词演算的永真公式,2).a.XP(X)P(Y)或XP(X)P(X)b.P(Y)X P(X)或P(X)P(X)c.XP(X)XP(X)证：a.对XP(X)为真，则对某一具体Y，P(Y)为真 b.对某一确定的Y，P(Y)为真，即则存在一X，使 P(X)为真 c.XP(X)P(X)X P(X)返回,2、含有量词的谓词演算的永真公式,3）a）(XP(X)XP(X)b）(XP(X)XP(X)证法1：,3、量词的否定,a)并非对任意x，P(X)是真 等价于至少存在一 个x，使P(X

15、)为假。,b)并非存在一个x，使P(X)为真等价于对所有的x，P(X)为假。,注：（1）从上述公式可以看出，X和X具有对偶性（将X与X互换，可看出）（2）出现在量词之前的否定，是否定量词。而是否定 被量化了的整个命题。证法2 返回,证法2：对个体域为a1，a2，an可详细证明如下(XP(X)(P(a1)P(a2)P(an)P(a1)P(a2)P(an)X P(X)返回,3、量词的否定,4）a.XA(X)P X(A(X)P)b.XA(X)P X(A(X)P)c.XA(X)P X(A(X)P)d.XA(X)P X(A(X)P)这里P是不含自由变元X的谓词公式。证明：a.因P的值与x无关。若P为真，

16、等价式两边都真。若P为假，两边也都为XA(X)。例 返回82 上一页26 下一页28,4、量词辖域的扩展和收缩,例1：XA(X，Y)P(Y)X(X，Y)P(Y)XP(X，Y)XP(X，Z)X(P(X，Y)XP(X，Z)(定理证法2)证明：当个体域为a1，a2，an 证明如下，其余式子证明类同。XA(X)P(P(a1)P(a2)P(an)P)(P(a1)P)(P(a2)P)(P(an)P)X(A(X)P)例2返回,4、量词辖域的扩展和收缩,例2：XY(P(X)Q(Y)(X P(X)YQ(Y)证明：XY(P(X)Q(Y)XY(P(X)Q(Y)X(P(X)Y Q(Y)XP(X)YQ(Y)X P(X)

17、Y Q(Y)X P(X)YQ(Y)4返回,4、量词辖域的扩展和收缩,5、量词的分配公式,a.X(A(X)B(X)X A(X)X B(X)证明:因为对一切X,A(X)B(X)为真,所以对一切X A(X)为真,对一切X B(X)为真。,b.X(A(X)B(X)XA(X)X B(X)证:X(A(X)B(X)XA(X)XB(X)X(A(X)B(X)X(A(X)XB(X)两边取非：X(A(X)B(X)(XA(X)XB(X)X(A(X)B(X)XA(X)XB(X)C 返回,5、量词的分配公式,a.X(A(X)B(X)XA(X)XB(X)证法二:证:对个体域为a1，a2，an X(A(X)B(X)XA(X)

18、XB(X)(A(a0)B(a0)(A(an)B(an)(A(a0)A(a1)A(an)(B(a0)B(a1)B(an)XA(X)XB(X)b.返回,5、量词的分配公式,c.X(A(X)B(X)XA(X)XB(X),5、量词的分配公式,证：因存在x使A(X)B(X)为真，故该X使A(X)为 真，该X使B(X)为真,即XA(X)XB(X)为真。,注意：注意逆方向不成立 即XA(X)X B(X)X(A(X)B(X)不成立证：举反例：设论述域是整数。A(x)：x为奇数，B(x)：x为偶数 则XA(X)XB(X)为真。但X(A(X)B(X)为假 d 返回,d.X A(X)X B(X）X(A(X)B(X)

19、证:若XA(X)为真，则 X(A(X)B(X)为真，若X B(X)为真，则X(A(X)B(X)亦真。注意逆方向不成立。返回,5、量词的分配公式,注：只须应用量词对，的恒等式即可推出例：证明XA(X)XB(X)X(A(X)B(X)证：XA(X)XB(X)XA(X)XB(X)XA(X)XB(X)X(A(X)B(X)X(A(X)B(X)返回,6、量词对及的处理,XYP(X，Y)Y XP(X，Y)二者同义 XYP(X，Y)Y XP(X，Y)XYP(X，Y)X YP(X，Y)yxP(x，y)xyP(x，y)证 例返回,7、关于多个量词的永真式,注意逆方向不成立例：设论述域为有理数。P(x,y)表示x+y

20、=0，则xy(x+y)=0为真。但是，yx(x+y)=0为假。返回,7、关于多个量词的永真式,yxP(x，y)xyP(x，y)证法1：存在一y，对任意的x，P(x，y)为真 即对任意x存在，对这个y而言，使P(x，y)为真证法2:yxP(x，y)(P(a1，a1)P(a1，a2)P(a1，an)(P(a2，a1)P(a2，a2)P(an，an)(P(an，a1)P(an，a2)P(an，an)(P(a1，a1)P(a1，a2)P(a1，an)(P(a1，a1)P(a1，a2)P(a1，an)(P(a1，a1)P(a1，a2)P(a1，an)xyP(x，y),返回,7、关于多个量词的永真式,xy

21、P（x，y）xyP(x，y)yxP（x，y）yxP(x，y)yxP（x，y）yxP(x，y),7、关于多个量词的永真式,注：上述公式，当论述域为a1,a2,时，亦均可用 列举法证明例：对第式证明 返回,一前束范式 1.定义 2.任意谓词公式均可化为前束范式 3.举例二前束合取范式和前束合取析取范式 1.定义 2.任意谓词公式均可化为前束合取范式和前束合取 析取范式 3.举例上一节 下一节,第三节 前 束 范 式,1定义：量词均在谓词公式开头，作用域延伸到整个谓词公式末尾的谓词公式称为前束范式。,一、前 束 范 式,例1：xyz(Q(x，y)R(z)例2：xy(P(x，y)Q(y)返回目录,证：

22、(1)把否定词深入到命题变元和谓词前面(2)利用AxB(x)x(AB(x)AxB(x)x(AxB(x)把量词推到前面(3)利用改名规则：x A(x)xB(x)uA(u)xB(x)ux(A(u)B(x)把量词推到前面 返回目录,2、任意谓词公式均可化为前束范式,3.举例例1把xy(zP(x,y,z)P(y,z)uQ(x,y,u)化为前束范式。,前 束 范 式,解：原式xy(z(P(x，z)P(y，z)uQ(x，y，u)xy(z(P(x，z)P(y，z)uQ(x，y，u)xyzu(P(x，y)P(y，z)Q(x，y，u)例2返回目录,3.举例例2：把x P(x，y)xQ(x，z)化为前束范式解：原

23、式xP(x，z)uQ(z，u)xu(P(x，y)Q(z，u)返回,前 束 范 式,1定义：若谓词公式是前束范式且作用域为合取范式,则称为前束合取范式。,二、前束合取范式和前束合取析取范式,前束合取范式形式:(u1)(u2).(un)(A11A1m1)(An1.Anmn),定义：若谓词公式是前束范式且作用域为析取范式,则称为前束析取范式。前束析取范式形式:(u1)(u2).(un)(A11A1m1)(An1.Anmn)返回目录,2.任一谓词公式均可化为前束析取范式或前束合取范式,二、前束合取范式和前束合取析取范式,证：首先把谓词公式化为前束范式，然后对作用域用命 题演算方法转化之。返回目录,3.

24、举例例1xy(zP(x，y，z)uQ(x，u)uR(x，u)化为前束合取范式。,二、前束合取范式和前束合取析取范式,解：原式 xy(zP(x，y，z)uQ(x，u)vQ(y，v)xyzuv(P(x，y，z)Q(x，u)Q(y，v)xyzuv(P(x，y，z)Q(y，v)Q(x，u)Q(y，v)返回目录,一.命题演算中的所有推理规则都是谓词演算中的推理规则，谓词演算的所有永真式也是谓词推理规则。,4、谓词演算与推理规则,二.四条重要的推理规则 1.全称指定规则，简记为US 2.存在指定规则，简记为EG 3.存在推广规则，简记为EG 4.全称推广规则，简记为UG三举例 上一节,1.全称指定规则 简

25、记为US规则xP(x)P(c),二、四条重要的推理规则,返回目录,含义：对一切x，P(x)为真,可推得任意一个确定的c，使 P(c)为真。,意义：删除全称量词例：x(P(x，y)yQ(x，y)P(c，y)yQ(c，y)但 x(P(x，y)yQ(x，y)P(y，y)yQ(y，y)错误,2.存在指定规则 简记为EG规则 xP(x)P(c)含义：至少存在一个x使得A(x)为真.即可推得有一个确定的c,使P(c)为真注意：选定的变元c必须是谓词公式中没有出现过的.例：y(Q(y)Q(x)xA(x,z)y(Q(y)Q(y)A(y,z)均错 x(A(x,z)A(y)(A(y,z)A(y)均错 返回目录,二

26、、四条重要的推理规则,3.存在推广规则 简记为EG规则P(c)x P(x)含义：c是某个确定的个体,若P(c)为真,则x P(x)为真注意：c不能出现在P(c)中的x的辖域中例：x(P(c)z Q(c,z)x(x P(x)zQ(x,z)为错 x(P(c)z Q(c,z)y(x P(y)z Q(y,z)正确 返回目录,二、四条重要的推理规则,4.全称推广规则简记为UG规则 P(c)x P(x)含义：若对个体域中每一个客体c，P(c)断言为真 则x P(x)为真 P(x)x P(x)注意：(1)P(x)中的x不是使用ES而引入的。,二、四条重要的推理规则,(2)若 x是使用us而自由的，后继推导中

27、，使用ES 而引入的新变元都没有在P(x)中自由出现的 情况下,才能使用UG规则。所以，一般推导中只能先采用ES规则，后采用US规则。例 返回目录,例：观察下列推理过程 y=x+11.xy P(x，y)p2.y P(c，y)T1，US3.P(c，d)T2，ES4.y P(y，d)T3，UG5.yx P(y，x)T4，EG错在何处？第4条错误例：xy（y=x+1）正确，但是y x（y=x+1）错误 返回,二、四条重要的推理规则,例1：下列推导有何错误？1.(1)y(P(y)Q(y)P(2)P(a)P(b)T 1，ES 解：(2)应改为P(a)P(a)2.(1).xP(x)Q(x)P(2).P(x

28、)Q(x)P 1，us解：仅当x（P(x)Q(x)）为真时，才能推出：P(x)Q(x)3.(1).xR(x)x(Q(x)R(x)P(2).P(a)x(Q(x)R(x)T 1，ES解 例2 返回目录,三 举 例,3:应改为(1).xR(x)(Q(x)R(x)P(2).x R(x)x(Q(x)R(x)T 1(3).R(a)x(Q(x)R(x)T 2，ES 返回,三.举 例,例2.会议的每一个成员都是专家并且都是党员，一些成 员是老人。,三 举 例,所以成员有一些是老党员。试构造一个证明。解：设C(x)表示x是会议成员。S(x)表示x是专家。W(x)表示x是党员。O(x)表示x是老人。则 x(C(x

29、)(W(x)S(x)x(C(x)O(x)x(O(x)W(x)证 例3返回,例2 证：1.x(C(x)(W(x)S(x)P 2.x(C(x)O(x)P 3.C(y)(W(y)S(y)T 1，US 4.C(y)O(y)T 2，ES 3.C(y)O(y)T 2，ES 4.C(y)(W(y)S(y)T 1，US 5.C(y)T 3 6.W(y)S(y)T 5，4 7.O(y)T 3 8.W(y)T 6 9.O(y)W(y)T 7，8 10.x(O(x)W(x)T 9，EG 是否有错？错在哪里？返回,三 举 例,例3：证明:x(P(x)Q(x)x(R(x)Q(x)x(R(x)P(x)证:1.x(P(x)

30、Q(x)P 2.x(R(x)Q(x)P 3.P(x)Q(x)T1,US 4.R(x)Q(x)T2,US 5.Q(x)R(x)T4 6.P(x)R(x)T3,5 7.x(R(x)P(x)T6，UG 例4返回,三 举 例,例4证明x(P(x)Q(x)xP(x)xQ(x)法一：附加前提法（略），自己动手做！法二：用归谬法1.x(P(x)Q(x)P2.(xP(x)x Q(x)P，归谬法3.xP(x)x Q(x)T24.xP(x)T35.xQ(x)T6.P(y)T4，ES7.Q(y)T5，US8.(P(y)Q(y)T6，79.P(y)Q(y)T1，US10(P(y)Q(y)(P(y)Q(y)T8，9矛盾,三 举 例,返回,本 章 小 结,本章是因为命题逻辑的局限性才引入的谓词逻辑，重点介绍了谓词和量词及谓词公式的符号化，谓词等价式的转换和谓词演算的推理理论。通过研究命题本身的内部结构关系才看出命题结构的相似性、共通性和公用性。,课后练习和作业,课后练习：P74：1（所有奇数题）P75：9，10P76：12，13课后作业：P74：1(所有偶数题)P76：11，14,谢谢！,