离散数学_谓词逻辑2

1、离散数学离散数学第二章第二章 谓词逻辑谓词逻辑谓词演算的推理理论谓词演算的推理理论等价式与永真蕴含式等价式与永真蕴含式离散数学离散数学2主要内容主要内容v 等价式与永真蕴含式等价式与永真蕴含式v 谓词推理理论谓词推理理论离散数学离散数学3谓词公式的等价谓词公式的等价v 给定两个谓词公式给定两个谓词公式A A和和B B，v 设它们有设它们有共同的个体域共同的个体域E E，v 如果对如果对A A和和B B的的任一组变元（个体词）任一组变元（个体词）进行进行赋值，赋值，v 所得命题的真值相同，所得命题的真值相同，v 则称谓词公式则称谓词公式A A和和B B在在E E上等价上等价v 记做记做A AB

2、B离散数学离散数学4谓词公式的等价与命题公式的等价举例谓词公式的等价与命题公式的等价举例PQP Q P QTTTTTFFFFTTTFFTTP Q P QF(x) W (x) F(x) W(x)X的范围是：所有正整数的范围是：所有正整数xF(x) W(x) F(x) W(x)1T/F?T/F?2T/F？T/F?离散数学离散数学5命题演算中等价公式的推广应用命题演算中等价公式的推广应用v用同一谓词公式代替两个等价命题公式中的同一用同一谓词公式代替两个等价命题公式中的同一命题变元，所得到的谓词公式也等价。命题变元，所得到的谓词公式也等价。v例如：例如： ( x)F(x) W(x)( x)F(x) W

3、(x) PQPQ( x)F(x) G(x) QPQ( x)F(x) G(x) P ()离散数学离散数学6等价变换基本规则等价变换基本规则 1 1置换规则置换规则 2 2约束元的换名规则约束元的换名规则 3 3自由元的代入规则自由元的代入规则 离散数学离散数学7等价演算的基本规则等价演算的基本规则(1)(1)1.1.置换规则：置换规则： 设设P(A)P(A)是含公式是含公式A A的公式，若的公式，若A A B,B,则用公式则用公式B B取代取代P(A)P(A)中所有的中所有的A A之后的公式之后的公式P(B)P(B)与与P(A)P(A)等价。等价。 例：例：( x) (A(x) B) ( x)

4、(? A(x) B)离散数学离散数学8等价替换基本规则等价替换基本规则(2)(2)2 2约束元的换名规则约束元的换名规则 设设A A为一公式，将为一公式，将A A中某量词辖域中某约束变量中某量词辖域中某约束变量的指导变元及相应的约束变元改成该量词辖域中未的指导变元及相应的约束变元改成该量词辖域中未曾出现过的某个体变量符号，公式的其余部分不变，曾出现过的某个体变量符号，公式的其余部分不变，所得公式与所得公式与A A等价等价. . 例：例：( ( x) (P(x,y) Q(x) xR(x) ( ( z) (P(z,y) Q(z) xR(x) 离散数学离散数学9等价替换基本规则等价替换基本规则(3)

5、(3)3 3自由元的代入规则自由元的代入规则 设设A A为一公式，将为一公式，将A A中某个自由出现的个体变元的中某个自由出现的个体变元的所有出现用所有出现用A A中未曾出现过的个体变元符号代替，中未曾出现过的个体变元符号代替，A A中其余部分不变，所得公式与中其余部分不变，所得公式与A A等价等价. . 例：例：( x) (P(x,y) Q(x) xR(x) ( x) (P(x,w) Q(x) xR(x) 离散数学离散数学10常用等价式常用等价式1 1： 否定与量词否定与量词v量词量词与与否定联结词否定联结词的关系的关系：(1)(x) P(x) (x) P(x)(2)(x) P(x) (x)

6、 P(x)证法一:(1) “并非对任意x， P(X)是真” 等价于 “至少存在一 个x，使P(X)为假”。(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 2： 量词的分配公式（量词的分配公式（1 1）1)1)

7、对对可分配：可分配：x x( (A(x) A(x) B(x)B(x) ) x A(x) x A(x) xB(x)xB(x) 设x的个体域为a1，a2，anx x( (A(x) A(x) B(x) B(x) ) (A( (A(a1) )B(B(a1) ) (A(A(a2) )B(B(a2) ) (A(A(an) )B(B(an) ) ( (A(A(a1) )A(A(a2) )A(A(an) ) ) ( (B(B(a1) )B(B(a2) )B(B(an) ) ) x A(x) x A(x) x B(x)x B(x)离散数学离散数学13量词的分配公式量词的分配公式x x( (A(x)A(x)B(x

8、)B(x) ) x A(x) x A(x) x B(x)x B(x)？ 举例：举例：令令 x x的个体域为正整数。的个体域为正整数。 A(x) A(x)：x x是奇数是奇数 B(x)B(x)：x x是偶数是偶数 x x ( (A(x) A(x) B(x)B(x) ) 所有正整数是奇数所有正整数是奇数或者或者偶数。偶数。 x A(x) x A(x) x B(x)x B(x) 所有正整数都是奇数所有正整数都是奇数或者或者所有正整数都是所有正整数都是偶数。偶数。离散数学离散数学14常用等价式常用等价式2 2： 量词的分配公式（量词的分配公式（2 2）2)2) 对对可分配：可分配： x x( (A(x

9、) A(x) B(x) B(x) ) xA(x)xA(x) xB(x)xB(x) 设x的个体域为a1，a2，anx x( (A(x) A(x) B(x) B(x) ) (A( (A(a1) )B(B(a1) ) (A(A(a2) )B(B(a2) ) (A(A(an) )B(B(an) ) ( (A(A(a1) )A(A(a2) )A(A(an) ) ) ( (B(B(a1) )B(B(a2) )B(B(an) ) ) xA(x)xA(x) xB(x)xB(x)离散数学离散数学15析取、合取与量词析取、合取与量词( ( x)x)( (A(x)A(x) B(x)B(x) ) ( ( x)A(x)

10、 x)A(x) ( ( x)B(x)x)B(x)？举例：举例：令令 x x的个体域为正整数。的个体域为正整数。 A(x) A(x)：x x是奇数是奇数 B(x)B(x)：x x是偶数是偶数 x x ( (A(x) A(x) B(x)B(x) ) 存在既是奇数存在既是奇数又是又是偶数的正整数。偶数的正整数。 x A(x) x A(x) x B(x)x B(x) 存在为奇数的正整数存在为奇数的正整数且且存在为偶数的正整存在为偶数的正整数。数。离散数学离散数学16常用等价式常用等价式2 2： 析取、合取与量词析取、合取与量词 量词与联结词量词与联结词，的关系总结的关系总结：1)1) x x( (A(

11、x) A(x) B(x)B(x) ) x A(x) x A(x) xB(x)xB(x) x x( (A(x)A(x)B(x)B(x) ) x A(x) x A(x) x B(x)x B(x)2)2) x x ( (A(x) A(x) B(x) B(x) ) x A(x)x A(x) x B(x)x B(x) x x ( (A(x) A(x) B(x) B(x) ) x A(x) x A(x) x B(x)x B(x)离散数学离散数学17常用等价式常用等价式3 3：量词辖域收缩与扩张量词辖域收缩与扩张设设A(x)A(x)是任意一个含个体变量是任意一个含个体变量x x的公式，的公式，B B中不含中

12、不含x x，(P:288)(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)辖域辖域扩张扩张方向方向辖域辖域收缩收缩方向方向离散数学离散数学181.1.证明证明: :(x)A(x) B (x)(A(x) B) 因B的值与x无关。若B为真，等价式两边都真。若B为假，两边也都为xA(x)。离散数学离散数学19常用等价式常用等价式3 3：量词辖域收缩与扩张量词辖域收缩与扩张( (续续) ) 3. ( x) A(x)

13、 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 3：量词辖域收缩与扩张量词辖域收缩与扩张（证明（证明 1 1）3. 证明：证明： ( x ) (A(x) B) ( x) A(x) B ( x) (A(x) B) ( x) (? A(x) B) /* 命题等价式在谓词演算中的推广命题等价式在谓词演算中的推广 ( x) ? A(x) B /* 辖域的收缩辖域的收缩

14、? ( 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) / /* * 命题等价式在谓词演算中命题等价式在谓词演算中推广推

15、广x (A(x) B(x) x A(x) x B(x)离散数学离散数学22永真蕴含式永真蕴含式v 定义定义 永真式永真式 设设A A是谓词公式，如果在其个体域上，对于是谓词公式，如果在其个体域上，对于A A的所有赋值，的所有赋值，A A都取值为真，则称都取值为真，则称A A是是永真式永真式。v 定义定义 永真蕴含式永真蕴含式 设设P P、Q Q是谓词公式，如果是谓词公式，如果P QP Q是是永真式，永真式，则称则称P P永真蕴含永真蕴含Q Q，记作，记作P P Q Q。离散数学离散数学23命题演算中的永真蕴含公式的推广应用命题演算中的永真蕴含公式的推广应用v用同一谓词公式代替命题永真蕴含公式中

16、的同一用同一谓词公式代替命题永真蕴含公式中的同一命题变元，所得到的谓词公式也是永真蕴含公式。命题变元，所得到的谓词公式也是永真蕴含公式。例如：例如： 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) 离散数学离散数学24证明永真蕴含式方法证明永真蕴含式方法设设P P、Q Q是谓词公式，证明是谓词公式，证明P PQ Q方法一：假设方法一：假设P P为真，证明为真，证明Q Q为真为真方法二：利用常用永真蕴含式和等价式

17、证明方法二：利用常用永真蕴含式和等价式证明 P P （） （） （） （） Q Q离散数学离散数学25常用永真蕴含式常用永真蕴含式v 量词分配的蕴含式量词分配的蕴含式( 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) 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)v 量词分配等价式量词分配等价式 ( x)(A(x) B(x) ( x)A(x) (

18、x)B(x) ( x)(A(x) B(x) ( x)A(x) ( x)B(x)离散数学离散数学26永真蕴含式证明永真蕴含式证明 举例举例1 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)B(x) 为真，显然，有为真，显然，有( x) (A(x) B(x) 也为真，得证。也为真，得证。用类似方法可证：用类似方法可证：( x) (A(x) B(

19、x) ( x) A(x) ( x)B(x)离散数学离散数学27永真蕴含式证明永真蕴含式证明 举例举例2 2v 试证明试证明 x (A(x) B(x) x C(x) x (B(x) C(x)v 证明：证明： 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)

20、 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)离散数学离散数学28关于多个量词的等价式和永真式关于多个量词的等价式和永真式v 1. 1. 多个相同量词的位置可以互换多个相同量词的位置可以互换 x x y A(x,y) y A(x,y) y y x A(x,y)x A(x,y) x x y A(x,y) y A(x,y) y y x A(x,y)x A(x,y)v 2. (2. (x

21、 x y)y)可以可以推出推出( (y y x)x)或或( (x x y)y) x x y A(x,y) y A(x,y) y y x A(x,y)x A(x,y) x x y A(x,y) y A(x,y) x x y A(x,y) y A(x,y) v 3. (3. (x x y y) )可以可以推出推出( (y y x)x) x x y A(x,y) y A(x,y) y y x A(x,y)x A(x,y)v 4. 4. ( (x x y y) )可以可以推出推出( (y y x x) )或或( (x x y y) ) x x y A(x,y) y A(x,y) y y x A(x,y

22、)x A(x,y) x x y y A(x,y) A(x,y) x x y A(x,y)y A(x,y)离散数学离散数学29前束范式v 定义定义 前束范式前束范式v 一个一个谓词公式谓词公式，如果量词均在，如果量词均在公式的公式的开头开头，且其辖域延伸到，且其辖域延伸到公式的公式的末尾末尾，则该公式称为，则该公式称为前束范式前束范式。形如：。形如： v v1 1 v v2 2 v vn n A A 其中，其中， 可以是可以是或或，v vi i(i = 1, (i = 1, , n), n)是是个体变元个体变元，A A是是不含量词不含量词的的谓词公式谓词公式。v 举例举例 前束范式：前束范式：

23、x xy yz z( (P(x,y) P(x,y) Q(z) R(x,z)Q(z) R(x,z) ) x xz z ( (P(x,y) Q(z)P(x,y) Q(z) ) x P(x,y) x P(x,y) z R(x,z)z R(x,z)离散数学离散数学30v 任意谓词公式都可以转化成前束范式任意谓词公式都可以转化成前束范式离散数学离散数学31前束范式转换前束范式转换v 一般公式向前束范式转换的步骤：一般公式向前束范式转换的步骤：v 1.1. 先把公式中的联结词转换为先把公式中的联结词转换为, , , , v 2.2. 使用量词转换律和摩根律把公式中的使用量词转换律和摩根律把公式中的移到简单

24、命题函数移到简单命题函数的的前面前面v 3.3. 利用约束元换名规则和自由元代入规则，使所有约束元和利用约束元换名规则和自由元代入规则，使所有约束元和自由元均不重名自由元均不重名v 4.4. 把所有量词以把所有量词以公式中出现的顺序公式中出现的顺序移到公式最前面移到公式最前面离散数学离散数学32前束范式转换例前束范式转换例2 2）x x y y( (z P(x,z) P(y,z)z P(x,z) P(y,z) ) u Q(x, y, u)u Q(x, y, u)v 解解: : x x y y( (z P(x,z) P(y,z)z P(x,z) P(y,z) ) u Q(x, y, u)u Q(

25、x, y, u)x x y(y(z z P(x, P(x, z z) P(y,z) ) P(y,z) u Q(x, y, u) u Q(x, y, u) / /* *消去规则消去规则* */ /x xy(y(z z P(x, P(x, z z) ) P(y, z) P(y, z) u Q(u Q(x x, ,y y,u),u) / /* *量词转化律量词转化律* */ /x xy(y(w w P(x,P(x,w w) ) P(y,z) P(y,z) u Q(u Q(s s, , t t, u), u) / /* *改名及代入规则改名及代入规则* */ /x x y y w w u u( (P(

26、x,w) P(x,w) P(y,z) Q(s,t,u)P(y,z) Q(s,t,u) ) / /* *量词辖域扩张量词辖域扩张* */ /离散数学离散数学33前束范式转换练习前束范式转换练习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) / /* *改名及代入规则改名及代入规则* */ / ( x y(P(x,t) Q(y) z R(z) / /* *辖域扩张辖域扩张* */ / x y z

27、(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)离散数学离散数学34谓词演算的推理理论谓词演算的推理理论 前提和结论都以前提和结论都以谓词公式谓词公式表示。表示。 如：如：前提前提：P P1 1，P P2 2, ,P,Pn n， 结论结论：Q Q (1) (1) P P1 1,P,P2 2, ,P,Pn n Q Q (2) (2) P P1 1 P P2 2 P Pn n Q Q离散数学离散数学35谓词演算的推理方法谓词演算的推理方法v

28、谓词演算的推理方法，可以看作是命题演算推理方法谓词演算的推理方法，可以看作是命题演算推理方法的的扩展扩展。(1) (1) 命题演算中的蕴含式和等价式可推广到谓词演算中使用。命题演算中的蕴含式和等价式可推广到谓词演算中使用。(2) P(2) P、T T和和CPCP规则等规则等都可以在谓词的推理理论中应用都可以在谓词的推理理论中应用。(3)(3)某些前提与结论可能会某些前提与结论可能会受量词限制受量词限制，为了使用这些等价式和，为了使用这些等价式和蕴含式，蕴含式，必须在推理过程中使用消去和添加量词的规则（必须在推理过程中使用消去和添加量词的规则（USUS、ESES、UGUG、EGEG），以便使谓词

29、演算公式的推理过程可类似于命题，以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。演算中推理理论那样进行。离散数学离散数学36消去和添加量词的规则消去和添加量词的规则v消去量词的规则消去量词的规则 全称指定规则全称指定规则（USUS规则）（规则）（U Universal niversal S Specifypecify） 存在指定规则存在指定规则（ESES规则）（规则）（E Existential xistential S Specifypecify）v添加量词的规则添加量词的规则 全称推广规则全称推广规则（UGUG规则）（规则）（U Universal niversal G G

30、eneralizeeneralize） 存在推广规则存在推广规则（EGEG规则）（规则）（E Existential xistential G Generalizeeneralize）量词这四条重要推理规则量词这四条重要推理规则只能对前束范式使用只能对前束范式使用离散数学离散数学37全称指定规则（全称指定规则（USUS规则）规则） xP(x)xP(x)P(c)P(c)全称指定规则说明：全称指定规则说明： 若个体域中的若个体域中的所有所有个体个体x x都使得谓词都使得谓词P P(x)(x)为真，为真，则个体域中任一个体则个体域中任一个体c c也使得谓词也使得谓词P P(x)(x)为真。为真。 体

31、现了在逻辑推理中体现了在逻辑推理中由一般到特殊由一般到特殊的推导方法的推导方法离散数学离散数学38存在指定规则（存在指定规则（ESES规则）规则） xP(x) xP(x) P(c) P(c)存在指定规则说明：存在指定规则说明：若个体域中存在一些个体满足若个体域中存在一些个体满足谓词谓词P P，则至少有某个确定的个体，则至少有某个确定的个体c c满足谓词满足谓词P P。离散数学离散数学39全称推广规则（全称推广规则（UGUG规则）规则）vP(c) P(c) xP(x)xP(x) 全称推广规则说明全称推广规则说明：对个体域中任意一个个体对个体域中任意一个个体c c，如果能够证明，如果能够证明，P(

32、c)P(c)为真，则可得结论为真，则可得结论xP(x)xP(x)离散数学离散数学40存在推广规则（存在推广规则（EGEG规则）规则）vP(c)P(c)xP(x)xP(x) 存在推广规则说明：存在推广规则说明：如果能够证明，存在着个如果能够证明，存在着个体域中的个体体域中的个体c c，使，使P P成立，就能得出一般性的结成立，就能得出一般性的结论论xP(x)xP(x)离散数学离散数学41例例1 1、苏格拉底三段论证明、苏格拉底三段论证明v 苏格拉底三段论苏格拉底三段论： 凡是人都是要死的。凡是人都是要死的。 苏格拉底是人。苏格拉底是人。 苏格拉底是要死的。苏格拉底是要死的。符号化：符号化：H(x

33、):xH(x):x是一个人。是一个人。M(x):x M(x):x 是要死的。是要死的。s:s:苏格拉底。苏格拉底。 前提：前提：( ( x) x) ( (H(x) H(x) M(x) M(x) ) H(s) H(s)结论：结论： M(s)M(s)证明：证明： (1) (1) ( ( x) (H(x)x) (H(x)M(x) M(x) P P (2) H(s) (2) H(s)M(s) M(s) US(1)US(1) (3) H(s) (3) H(s) P P (4) M(s) (4) M(s) T T(2)(3)(2)(3)证毕证毕离散数学离散数学42例例2例例2 乌鸦都不是白色的，北京鸭是白

34、色的，因此，北京鸭不是乌鸦。乌鸦都不是白色的，北京鸭是白色的，因此，北京鸭不是乌鸦。令令 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 P F(c) H(c) USUS H(c) F(c) T T x (G(x) H(x) P P G(c) H(c) USUS G(c) F(c) T T x (G(x) F(x) UGUG 离散数学离散数学43例例3 CP3 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