离散数学课件：2-3 谓词演算的等价式与蕴含式

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，则，则 ( x)P(x) (P(a1) P(a2) P(an)

4、 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) 量词的作用域中，常有合取或析取项，如量词的作用域中，常有合取或析取项，如果其中一个为命题，则可将该命题移至该量词果其中一个为命题，则可将该命题移至该量词作用域之外作用域之外.( x)(A(x) B(

5、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)三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式( x)(A(x)B)

6、( 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三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式( x)(BA(x) B( x) A(x) ( x)(BA(x) ( x)( B A(x) 解：解： B ( x)A(x) B( x) A(x) E20作用域的收缩作用域的收缩E20三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式(IV) 量词分配等价式量词分配等价式( x)(A(x) B(x)( x)(A(x) B

7、(x)F 对对 ， 对对 不存在分配等价式不存在分配等价式.( x)A(x) ( x)B(x)( 对对 的分配的分配)( x)A(x) ( x)B(x) ( 对对 的分配的分配)三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式( 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量 词 的 分 配量 词 的 分 配E20( x)A(x)( x)B(x).( x)A(x) ( x)B(x)量 词 转 化 律量 词 转 化 律三、谓词演算的等价式与蕴含式三、谓词演算的等

8、价式与蕴含式公公式式(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)设个体域为自然数集合，设个体域为自然数集合， A(x): x为奇数为奇数. B(x): x为偶数为偶数.则则(2)( x)A(x)为真，为真，( x)B(x)为真，为真，

9、 故故( 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)两式反过来均不成立两式反过来均不成立.三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式 ( x)(A(x) B(x)( x)A(x) ( x)B(x)(3)( x)(A(x)B(x) ( x)A(x)( x)B(x)谓词演算中

10、常见的蕴含式谓词演算中常见的蕴含式(4)( x)(A(x) B(x) ( x)A(x) ( x)B(x)后面会给出后面会给出证明证明三、谓词演算的等价式与蕴含式三、谓词演算的等价式与蕴含式利用蕴含式利用蕴含式(3)可推得可推得.( x)A(x)( 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)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)