《离散数学》PPT课件.ppt

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

1、第七章 谓词逻辑,广东工业大学计算机学院,7.3 谓词演算的推理理论,7.2 等价式与永真蕴含式,2,主要内容,等价式与永真蕴含式 谓词推理理论,3,谓词公式的等价,给定两个谓词公式A和B，设它们有共同的个体域E，如果对A和B的任一组变元（个体词）进行赋值，所得命题的真值相同，则称谓词公式A和B在E上等价 记做AB,4,谓词公式的等价与命题公式的等价举例,P Q P Q,F(x)W(x)F(x)W(x),X的范围是：所有正整数,5,命题演算中等价公式的推广应用,用同一谓词公式代替两个等价命题公式中的同一命题变元，所得到的谓词公式也等价。例如：,(x)F(x),W(x),(x)F(x),W(x)

2、,P,Q,P,Q,(x)F(x),G(x),Q,P,Q,(x)F(x),G(x),P,(,),6,等价变换基本规则,1置换规则 2约束元的换名规则 3自由元的代入规则,7,等价演算的基本规则(1),1.置换规则：设P(A)是含公式A的公式，若A B,则用公式B取代P(A)中所有的A之后的公式P(B)与P(A)等价。例：(x)(A(x)B)(x)(A(x)B),8,等价替换基本规则(2),2约束元的换名规则 设A为一公式，将A中某量词辖域中某约束变量的指导变元及相应的约束变元改成该量词辖域中未曾出现过的某个体变量符号，公式的其余部分不变，所得公式与A等价.例：(x)(P(x,y)Q(x)xR(x

3、)(z)(P(z,y)Q(z)xR(x),9,等价替换基本规则(3),3自由元的代入规则 设A为一公式，将A中某个自由出现的个体变元的所有出现用A中未曾出现过的个体变元符号代替，A中其余部分不变，所得公式与A等价.例：(x)(P(x,y)Q(x)xR(x)(x)(P(x,w)Q(x)xR(x),10,常用等价式1：否定与量词,量词与否定联结词的关系：(1)(x)P(x)(x)P(x)(2)(x)P(x)(x)P(x),证法一:(1)“并非对任意x，P(X)是真”等价于“至少存在一 个x，使P(X)为假”。(2)“并非存在一个x，使P(X)为真”等价于“对所有的x，P(X)为假”。,注意：出现在

4、量词前面的否定，不是否定该量词本身，而是否定被量化了的整个公式。,11,证法2：设个体域为a1，a2，an(x)P(x)(P(a1)P(a2)P(an)P(a1)P(a2)P(an)(x)P(x),12,常用等价式2：量词的分配公式（1）,1)对可分配：x(A(x)B(x)x A(x)xB(x)设x的个体域为a1，a2，an x(A(x)B(x)(A(a1)B(a1)(A(a2)B(a2)(A(an)B(an)(A(a1)A(a2)A(an)(B(a1)B(a2)B(an)x A(x)x B(x),13,量词的分配公式,x(A(x)B(x)x A(x)x B(x)？,举例：令 x的个体域为正整

5、数。A(x)：x是奇数 B(x)：x是偶数 x(A(x)B(x)所有正整数是奇数或者偶数。x A(x)x B(x)所有正整数都是奇数或者所有正整数都是偶数。,14,常用等价式2：量词的分配公式（2）,2)对可分配：x(A(x)B(x)xA(x)xB(x)设x的个体域为a1，a2，an x(A(x)B(x)(A(a1)B(a1)(A(a2)B(a2)(A(an)B(an)(A(a1)A(a2)A(an)(B(a1)B(a2)B(an)xA(x)xB(x),15,析取、合取与量词,(x)(A(x)B(x)(x)A(x)(x)B(x)？,举例：令 x的个体域为正整数。A(x)：x是奇数 B(x)：x

6、是偶数 x(A(x)B(x)存在既是奇数又是偶数的正整数。x A(x)x B(x)存在为奇数的正整数且存在为偶数的正整数。,16,常用等价式2：析取、合取与量词,量词与联结词，的关系总结：1)x(A(x)B(x)x A(x)xB(x)x(A(x)B(x)x A(x)x B(x)2)x(A(x)B(x)x A(x)x B(x)x(A(x)B(x)x A(x)x B(x),17,常用等价式3：量词辖域收缩与扩张,设A(x)是任意一个含个体变量x的公式，B中不含x，(P:288)1.(x)A(x)B(x)(A(x)B)(x)A(x)B(x)(A(x)B)(补充)2.(x)A(x)B(x)(A(x)B

7、)(补充)(x)A(x)B(x)(A(x)B),辖域扩张方向,辖域收缩方向,18,1.证明:(x)A(x)B(x)(A(x)B)因B的值与x无关。若B为真，等价式两边都真。若B为假，两边也都为xA(x)。,19,常用等价式3：量词辖域收缩与扩张(续),3.(x)A(x)B(x)(A(x)B)(x)A(x)B(x)(A(x)B)4.B(x)A(x)(x)(B A(x)B(x)A(x)(x)(B A(x),辖域扩张方向,辖域收缩方向,20,常用等价式3：量词辖域收缩与扩张（证明 1）,3.证明：(x)(A(x)B)(x)A(x)B(x)(A(x)B)(x)(A(x)B)/*命题等价式在谓词演算中的

8、推广(x)A(x)B/*辖域的收缩(x)A(x)B/*量词与否定联结词的等价交换(x)A(x)B,21,谓词演算举例,试证明：(x)(A(x)B(x)(x)A(x)(x)B(x)证明：(x)(A(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)/*对的分配率*/(x)A(x)(x)B(x)/*量词转化率*/(x)A(x)(x)B(x)/*命题等价式在谓词演算中推广,x(A(x)B(x)x A(x)x B(x),22,P 288：列出的等价式在证明中可直接使用。,23,永真蕴含式,定义永真式 设A是谓词公式，如果在其个体域上，对于A的所有赋值，A都取值为真，则称A是永真式。定义永

9、真蕴含式 设P、Q是谓词公式，如果P Q是永真式，则称P永真蕴含Q，记作P Q。,24,命题演算中的永真蕴含公式的推广应用,用同一谓词公式代替命题永真蕴含公式中的同一命题变元，所得到的谓词公式也是永真蕴含公式。例如：P QP(x)F(x)(x)W(x)(x)F(x)(x)(F(x)W(x)(x)F(x)(P Q)Q(x)F(x)(x)G(x)(x)G(x)(x)(F(x)G(x)(x)G(x),25,证明永真蕴含式方法,设P、Q是谓词公式，证明PQ方法一：假设P为真，证明Q为真方法二：利用常用永真蕴含式和等价式证明 P（）（）（）（）Q,26,常用永真蕴含式,量词分配的蕴含式(x)A(x)(x

10、)B(x)(x)(A(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)(x)(A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)量词分配等价式(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x),27,永真蕴含式证明 举例1,(x)A(x)(x)B(x)(x)(A(x)B(x)证明：只需证明当(x)A(x)(x)B(x)为真时，(x)(A(x)B(x)也为真。若(x)A(x)(x)B(x)为真，则(x)A(x)为真或者(x)

11、B(x)为真，显然，有(x)(A(x)B(x)也为真，得证。用类似方法可证：(x)(A(x)B(x)(x)A(x)(x)B(x),28,永真蕴含式证明 举例2,试证明 x(A(x)B(x)x C(x)x(B(x)C(x)证明：x(A(x)B(x)x C(x)x(A(x)B(x)x C(x)/*消去规则*/x(A(x)B(x)x C(x)/*摩根律*/x(A(x)B(x)C(x)/*蕴涵式*/x(A(x)C(x)(B(x)C(x)/*命题分配律*/x(A(x)C(x)x(B(x)C(x)/*分配律*/x(B(x)C(x)x(B(x)C(x),量词与联结词的蕴含式：/*小()推出大()*/(x)A

12、(x)(x)B(x)(x)(A(x)B(x),29,关于多个量词的等价式和永真式,1.多个相同量词的位置可以互换 x y A(x,y)y x A(x,y)x y A(x,y)y x A(x,y)2.(x y)可以推出(y x)或(x y)x y A(x,y)y x A(x,y)x y A(x,y)x y A(x,y)3.(x y)可以推出(y x)x y A(x,y)y x A(x,y)4.(x y)可以推出(y x)或(x y)x y A(x,y)y x A(x,y)x y A(x,y)x y A(x,y),30,前束范式,定义前束范式一个谓词公式，如果量词均在公式的开头，且其辖域延伸到公式

13、的末尾，则该公式称为前束范式。形如：v1 v2 vn A 其中，可以是或，vi(i=1,n)是个体变元，A是不含量词的谓词公式。举例 前束范式：xyz(P(x,y)Q(z)R(x,z)xz(P(x,y)Q(z)x P(x,y)z R(x,z),31,任意谓词公式都可以转化成前束范式,32,前束范式转换,一般公式向前束范式转换的步骤：1.先把公式中的联结词转换为,2.使用量词转换律和摩根律把公式中的移到简单命题函数的前面3.利用约束元换名规则和自由元代入规则，使所有约束元和自由元均不重名4.把所有量词以公式中出现的顺序移到公式最前面,33,前束范式转换例,2）x y(z P(x,z)P(y,z)

14、u Q(x,y,u)解:x y(z P(x,z)P(y,z)u Q(x,y,u)x y(z P(x,z)P(y,z)u Q(x,y,u)/*消去规则*/xy(z P(x,z)P(y,z)u Q(x,y,u)/*量词转化律*/xy(w P(x,w)P(y,z)u Q(s,t,u)/*改名及代入规则*/x y w u(P(x,w)P(y,z)Q(s,t,u)/*量词辖域扩张*/,34,前束范式转换练习,3)(x P(x,y)y Q(y)xR(x)解：原式(x P(x,y)y Q(y)xR(x)(xP(x,y)yQ(y)xR(x)/*量词转化律*/(xP(x,t)yQ(y)zR(z)/*改名及代入规

15、则*/(x y(P(x,t)Q(y)z R(z)/*辖域扩张*/x y z(P(x,t)Q(y)R(z)/*辖域扩张*/,3.z A(z)B z(A(z)B),1.x A(x)B x(A(x)B)2.y A(y)B y(A(y)B),35,谓词演算的推理理论,前提和结论都以谓词公式表示。如：前提：P1，P2,Pn，结论：Q(1)P1,P2,Pn Q(2)P1 P2 Pn Q,36,谓词演算的推理方法,谓词演算的推理方法，可以看作是命题演算推理方法的扩展。(1)命题演算中的蕴含式和等价式可推广到谓词演算中使用。(2)P、T和CP规则等都可以在谓词的推理理论中应用。(3)某些前提与结论可能会受量词

16、限制，为了使用这些等价式和蕴含式，必须在推理过程中使用消去和添加量词的规则（US、ES、UG、EG），以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。,37,消去和添加量词的规则,消去量词的规则全称指定规则（US规则）（Universal Specify）存在指定规则（ES规则）（Existential Specify）添加量词的规则全称推广规则（UG规则）（Universal Generalize）存在推广规则（EG规则）（Existential Gpecify）,量词这四条重要推理规则只能对前束范式使用,38,全称指定规则（US规则）,xP(x)P(c),全称指定规则说明：

17、若个体域中的所有个体x都使得谓词P(x)为真，则个体域中任一个体c也使得谓词P(x)为真。体现了在逻辑推理中由一般到特殊的推导方法,39,存在指定规则（ES规则）,xP(x)P(c),存在指定规则说明：若个体域中存在一些个体满足谓词P，则至少有某个确定的个体c满足谓词P。,40,全称推广规则（UG规则）,P(c)xP(x)全称推广规则说明：对个体域中任意一个个体c，如果能够证明，P(c)为真，则可得结论xP(x),41,存在推广规则（EG规则）,P(c)xP(x)存在推广规则说明：如果能够证明，存在着个体域中的个体c，使P成立，就能得出一般性的结论xP(x),42,例1、苏格拉底三段论证明,苏

18、格拉底三段论：凡是人都是要死的。苏格拉底是人。苏格拉底是要死的。符号化：H(x):x是一个人。M(x):x 是要死的。s:苏格拉底。前提：(x)(H(x)M(x)H(s)结论：M(s)证明：(1)(x)(H(x)M(x)P(2)H(s)M(s)US(1)(3)H(s)P(4)M(s)T(2)(3)证毕,43,例2,例2 乌鸦都不是白色的，北京鸭是白色的，因此，北京鸭不是乌鸦。令 F(x):x是乌鸦；G(x):x是北京鸭；H(x):x是白色的前提：x(F(x)H(x)，x(G(x)H(x)结论：x(G(x)F(x)证明：x(F(x)H(x)P F(c)H(c)US H(c)F(c)T x(G(x

19、)H(x)P G(c)H(c)US G(c)F(c)T x(G(x)F(x)UG,44,例3 CP规则,例5 构造下述推理证明 前提：x(F(x)G(x)；结论：xF(x)xG(x)根据CP规则，等价于证明：x(F(x)G(x)，xF(x)xG(x)证明：x F(x)P(附加前提)F(c)US x(F(x)G(x)P F(c)G(c)US G(c)T x G(x)UG,45,例4,例4 构造下述推理证明 前提：x F(x)x G(x)；结论：x(F(x)G(x)证明：x F(x)xG(x)P x y(F(x)G(y)T/*P290:公式(3)*/x(F(x)G(c)US F(c)G(c)US

20、x(F(x)G(x)UG说明:1.不能对x F(x)x G(x)消去量词,因为它不是前束范式.2.对此题不能用附加前提证明法，因为结论中的x量词辖域是公式的从头到尾。,46,练习,例3 证明下列推理：任何自然数都是整数；存在自然数；所以存在着整数。个体域为实数集合R。解 先将谓词符号化。设 F(x):x为自然数；G(x):x为整数。前提：x(F(x)G(x),x F(x)结论：x G(x)判断下列证明是否正确：x(F(x)G(x)P F(c)G(c)US x F(x)P F(c)ES G(c)T x G(x)EG,c取1.2，则 F(c)=F(1.2)为假!,47,课堂练习正确证明,例3 在自然推理系统F中，构造下面推理的证明：任何自然数都是整数；存在着自然数；所以存在着整数。个体域为实数集合R。解 先将原子命题符号化。设 F(x):x为自然数；G(x):x为整数。前提：x(F(x)G(x),x F(x)结论：x G(x)正确证明：x F(x)P F(c)ES x(F(x)G(x)P F(c)G(c)US G(c)T x G(x)EG,48,课堂练习,P294：1（1）,49,作业：,P294:1（3）（4）2（3）3（1）（2）,