《《离散数学》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)
2、F(x),W(x),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等价. 例
3、：(x) (P(x,y) Q(x) xR(x) (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)为
4、假”。 (2) “并非存在一个x，使P(X)为真” 等价于 “对所有的x，P(X)为假”。,注意：出现在量词前面的否定，不是否定该量词本身，而是否定被量化了的整个公式。,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(a
5、1)B(a2)B(an) x A(x) x B(x),13,量词的分配公式,x(A(x)B(x) x A(x) x B(x)？,举例： 令 x的个体域为正整数。 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)
6、(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是偶数 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
7、) 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) (补充) (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
8、) (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) /* 命题等价式在谓词演算中的推广 (x) A(x) B /* 辖域的收缩 (x) A(x) B /* 量词与否定联结词的等价交换 (x) A(x) B,21,谓词演算举例,试证明： (x) (A(x) B(x) (x)A(x)
9、(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是永真式。 定义永真蕴含式 设P、Q是谓词公式，如果P Q是永真式，则称P永真蕴含Q，记作P Q。,24,
10、命题演算中的永真蕴含公式的推广应用,用同一谓词公式代替命题永真蕴含公式中的同一命题变元，所得到的谓词公式也是永真蕴含公式。例如： 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)B(x) (x)(A(x)
11、 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,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
12、) 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(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
13、 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,前束范式,定义前束范式 一个谓词公式，如果量词均在公式的开头，且其辖域延伸到公式的末尾，则该公式称为前束范式。形如： 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. 把
