《离散数学课件：2-3 谓词演算的等价式与蕴含式》由会员分享，可在线阅读，更多相关《离散数学课件：2-3 谓词演算的等价式与蕴含式（16页珍藏版）》请在金锄头文库上搜索。
1、 谓词公式的等价谓词公式的等价：任意给定两个谓词公式任意给定两个谓词公式wff A和和wff B，设它们有共同的个体域，设它们有共同的个体域E，若对，若对A和和B的任一组变元进行赋值，所得命题的真值相同，的任一组变元进行赋值，所得命题的真值相同，则称谓词公式则称谓词公式A和和B在在E上是上是等价等价的，并记作：的，并记作：AB.(一一) 谓词公式等价和蕴含的概谓词公式等价和蕴含的概念念三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式蕴含蕴含：ABT，记作，记作AB.(二二) 谓词演算中常见的等价式：谓词演算中常见的等价式：(I) 命题公式的推广命题公式的推广 26个常用的命题演算等价式
2、及其代换可推个常用的命题演算等价式及其代换可推广到谓词演算中使用，如：广到谓词演算中使用，如：2. ( x)P(x) ( y)R(x, y)3. ( x)H(x, y) ( x)H(x, y)1. ( x)(P(x)Q(x) ( x)( P(x) Q(x) ( ( x)P(x) ( y)R(x, y)F 三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式() 量词否定等价式量词否定等价式 (量词转化律量词转化律) ( x)P(x) ( x) P(x)即，出现在量词之前的否定，不是否定该量词，而是即，出现在量词之前的否定，不是否定该量词，而是否定被量化了的整个命题否定被量化了的整个命题.实
3、例：实例： “不是所有人今天来校上课不是所有人今天来校上课.” “存在一些人今天不来校上课存在一些人今天不来校上课.” “ 不存在一些人今天来校上课不存在一些人今天来校上课”“ 今天所有人都没有来上课今天所有人都没有来上课.” ( x) P(x) ( x) P(x)三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式() 量词否定等价式量词否定等价式 (量词转化律量词转化律) ( x)P(x) ( x) P(x) ( x)(P(x) ( x) P(x)量词转化律量词转化律,可以在有限个体域上证明可以在有限个体域上证明:设个体域中的客体变元为设个体域中的客体变元为a1, a2, an，则则
4、( x)P(x) (P(a1) P(a2) P(an) P(a1) P(a2) P(an) ( x) P(x)三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式() 量词作用域的扩张与收缩等价式量词作用域的扩张与收缩等价式( x)(A(x) B)( x)(A(x) B)F或者，量词的作用域中有自由变元时，也有类或者，量词的作用域中有自由变元时，也有类似的扩张或收缩似的扩张或收缩. 例如：例如：( x)A(x) B( x)A(x) B(1)(2) 量词的作用域中，常有合取或析取项，如量词的作用域中，常有合取或析取项，如果其中一个为命题，则可将该命题移至该量词果其中一个为命题，则可将该命题移
5、至该量词作用域之外作用域之外.( x)(A(x) B(y)( x)A(x) B(y).( x)(A(x) B)( x)(A(x) B)( x)A(x) B( x)A(x) B(3)(4)三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式() 量词作用域的扩张与收缩等价式量词作用域的扩张与收缩等价式( x)(A(x)B)( x)(BA(x) ( x)A(x)BB( x)A(x)(7)(8)由上述几个式子，可推得下列等价式也成立：由上述几个式子，可推得下列等价式也成立：( x)(BA(x)( x)(A(x)B) ( x)A(x)B B( x) A(x) (5)(6)三、谓词演算的等价式与蕴含
6、式三、谓词演算的等价式与蕴含式例例例例2.3.12.3.1 证明证明证明证明( 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)BE20作作用用域域的的收收缩缩量量 词词 转转 化化 律律E20三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式例例例例2.3.22.3.2 证明证明证明证明( x)(BA(x) B( x) A(x) ( x)(BA(x) ( x)( B A(x) 解：解： B ( x)A(x) B( x) A(x) E20作作用用域域的的收收缩缩E20三、谓
7、词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式(IV) 量词分配等价式量词分配等价式( x)(A(x) B(x)( x)(A(x) B(x)F 对对 ， 对对 不存在分配等价式不存在分配等价式.( x)A(x) ( x)B(x)( 对对 的分配的分配)( x)A(x) ( x)B(x) ( 对对 的分配的分配)三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式例例例例2.3.32.3.3证明证明证明证明: :( x)(A(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)E20量
8、量 词词 的的 分分 配配E20( x)A(x)( x)B(x).( x)A(x) ( x)B(x)量量 词词 转转 化化 律律三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式公公式式(V) 多个量词的使用多个量词的使用( x)( y)A(x, y)( x)( y)A(x, y)F其他情况下量词换序后一般不等价其他情况下量词换序后一般不等价.( y)( x)A(x, y) ( y)( x)A(x, y)三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式(三三) 谓词演算中常见的蕴含式：谓词演算中常见的蕴含式：(2)( x)(A(x) B(x)(1)( x)A(x) ( x)B(x
9、)反例反例反例反例 设个体域为自然数集合，设个体域为自然数集合， A(x): x为奇数为奇数. B(x): x为偶数为偶数.则则(2)( x)A(x)为为真，真，( x)B(x)为真，为真， 故故( x)A(x) ( x)B(x)为真为真,但但( x)(A(x) B(x)为为假，假，所以所以(2)式反过来也不成立式反过来也不成立.而而( x)A(x)为假，为假， ( x)B(x)为假，为假，(1)( x)(A(x) B(x)为真，为真，所以所以(1)式反过来不成立；式反过来不成立；故故( x)A(x) ( x)B(x)为为假，假，F(1), (2)两式反过来均不成两式反过来均不成立立.三、谓词
10、演算的等价式与蕴含式三、谓词演算的等价式与蕴含式 ( x)(A(x) B(x)( x)A(x) ( x)B(x)(3)( x)(A(x)B(x) ( x)A(x)( x)B(x)谓词演算中常见的蕴含式谓词演算中常见的蕴含式(4)( x)(A(x) B(x) ( x)A(x) ( x)B(x)后面会给出后面会给出证明证明三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式利用蕴含式利用蕴含式(3)可推得可推得.例例例例2.3.42.3.4证明证明证明证明: : ( x)A(x)( x)B(x)( x)A(x)( x)B(x) ( x)A(x) ( x)B(x)证：证： ( x)( A(x)
11、( x)B(x) ( x)( A(x) B(x)E20蕴含式蕴含式(1)E20( x)(A(x) B(x)量量 词词 转转 化化 律律( x)(A(x)B(x).三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式公式公式谓词演算中常见的蕴含式谓词演算中常见的蕴含式(5)( x)( y)A(x,y) ( y)( x)A(x,y)(6)( y)( x)A(x,y) ( x)( y)A(x,y)(7)( x)( y)A(x,y) ( y)( x)A(x,y)反例反例反例反例 设个体域为实数集合，设个体域为实数集合，A(x, y): x-y=1. 则则( x)( y)A(x, y)为为真，真，而而( y)( x)A(x, y)为为假，假，所以所以(6)式反过来不成立式反过来不成立.F(5)(6)(7)三式反过来均不成立三式反过来均不成立.下面以下面以(6)式为例说明：式为例说明：三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式 x y y x y x x y y x x y x y y xHW: 2-5习题习题 (6)(7)
