交大数理逻辑课件5-1谓词逻辑的等值和推理演算.ppt

1、第5章 谓词逻辑的等值和推理演算,5.1 否定型等值式 5.2 量词分配等值式 5.3 范式 5.4 基本的推理公式 5.5 推理演算 5.6 谓词逻辑的归结推理法,5.1 否定型等值式,等值 设P、Q是任意两个谓词公式，若PQ为普遍有效式，则称P与Q是等值的，记作 PQ，或P=Q. 由命题公式移植来的等值式 若将命题公式的等值式，直接以谓词公式代入命题变项便可得谓词等值式 如由：(PQ) = PQ ，得 (x)F(x)(y)G(y) = (x)F(x)(y)G(y) 如由： PQ = PQ (x)F(x)(y)G(y) = (x)F(x)(y)G(y),5.1.2 否定型等值式,设P(x)是

2、含自由变项x的任意谓词公式。则 (x)P(x) = (x)P(x) (x)P(x) = (x)P(x) 从语义上说明 (x)P(x)：并非所有的x都具有性质P， 相当于至少存在一个x不具有性质P，即(x)P(x) 所以：(x)P(x) = (x)P(x) (x)P(x)：并不存在一个x具有性质P 相当于没有x具有性质P，即(x)P(x) 所以，(x)P(x) = (x)P(x),设个体域为实数R P(x): x是有理数,设个体域为自然数N P(x): x是奇数和偶数,否定型等值式的分析,设P(x)是含自由变项x的任意谓词公式。则 (x)P(x) = (x)P(x) (x)P(x) = (x)P

3、(x) 在1, 2域上分析 (x)P(x) =(P(1)P(2) =P(1) P(2) = (x)P(x) 可见，否定词越过量词的内移规律，就是摩根律的推广,(x)P(x) =(P(1) P(2) =P(1) P(2) =(x)P(x),否定型等值式的证明,设P(x)是含自由变项x的任意谓词公式。则 (x)P(x) = (x)P(x) (x)P(x) = (x)P(x) 在语义上证明 A真 B真 设任一解释I下有 (x)P(x)=T 则 (x)P(x)=F 即存在一个x0,使P(x0)= F 于是，P(x0)= T 在解释I下 (x)P(x)=T,B真 A真 设任一解释I下有 (x)P(x)=

4、T 即存在一个x0,使P(x0)=T 于是， P(x0)=F 则 (x)P(x)=F 即 (x)P(x)=T,依据：若存在一个解释I，使A真B就真，B真A就真，则A=B,否定型等值式举例,“天下乌鸦一般黑”的表示 设F(x): x是乌鸦，G(x,y): x与y是一般黑。 原句可表示成：若x是任一乌鸦，y是任一乌鸦，则x和y是一样黑的。 (x)(y)(F(x)F(y)G(x,y) = (x)(y)(F(x)F(y) G(x,y) =(x)(y)(F(x)F(y) G(x,y) =(x) (y) (F(x)F(y) G(x,y) =(x) (y) (F(x)F(y) G(x,y) 不存在乌鸦x和乌

5、鸦y，它们是不一样黑的。,5.2 量词分配等值式,量词对、 的分配律 (x)(P(x)q) = (x)P(x)q (x)(P(x)q) = (x)P(x)q (x)(P(x)q) = (x)P(x)q (x)(P(x)q) = (x)P(x)q 设：P(x)是含自由变元x的任意谓词公式。 q是不含变元x的谓词公式,量词分配等值式的证明,(x)(P(x)q) = (x)P(x)q,依据：若存在一个解释I，使A真B就真，B真A就真，则A=B,B真 A真 设任一解释I下有 (x)P(x)q =T 设q=T, 则 (x)(P(x)q) =T 若q=F, 必有 (x)P(x)=T 从而对任一个x, 有

6、P(x) =T 于是，对任一x有 P(x)q =T (x)(P(x)q) =T,A真 B真 设在一解释I下，有 (x)(P(x)q) =T 从而对任一个x, 使 P(x)q =T 又设q=T, 有 (x)P(x)q =T 若q=F, 从而对任一x,有 P(x)=T 即 (x)P(x)=T (x)P(x)q =T,量词分配等值式,量词对的分配律 (x)(P(x) q) = (x)P(x) q (x)(P(x) q) = (x)P(x) q (x)(q P(x) = q (x)P(x) (x)(q P(x) = q (x)P(x),设：P(x)是含自由变元x的任意谓词公式。 q是不含变元x的谓词公

7、式,(x)(P(x)q) = (x)(P(x)q) = (x)P(x)q = (x)P(x)q = (x)P(x)q,(x)(P(x)q) = (x)P(x)q,量词分配等值式,量词对的分配律 (x)(P(x)Q(x) = (x)P(x)(x)Q(x) 注意：对无分配律 从1,2域上分析 (x)P(x) (x)Q(x) =(P(1)P(2)(Q(1)Q(2) (x)(P(x)Q(x) =(P(1)Q(1) (P(2)Q(2) =(P(1)P(2)(P(1)Q(2)(Q(1)P(2) (Q(1)Q(2) =(x)P(x) (x)Q(x) (P(1)Q(2)(Q(1)P(2), (x)P(x) (

8、x)Q(x) (x)(P(x) Q(x),量词分配等值式,量词 对的分配律 (x)(P(x)Q(x) = (x)P(x)(x)Q(x) 注意：对无分配律 由前面证明代换得： (x)P(x)(x)Q(x)(x)(P(x)Q(x) 而 (x)P(x)(x)Q(x) = (x)P(x)(x) Q(x) = (x)P(x)(x) Q(x) (x)(P(x)Q(x) = (x) (P(x)Q(x) = (x)(P(x)Q(x) (x)P(x)(x) Q(x)(x)(P(x)Q(x),(x)P(x)(x) Q(x)(x)(P(x)Q(x),例 将下面命题用两种形式符号化,(1) 没有不犯错误的人 解： 设 F(x)：x是人，G(x)：x犯错误. x(F(x)G(x) = x (F(x) G(x) = x( F(x) G(x) = x(F(x)G(x) (2) 不是所有的人都爱看电影 解：令F(x)：x是人，G(x)：爱看电影. x(F(x)G(x) = x (F(x) G(x) = x (