《交大数理逻辑课件5-1谓词逻辑的等值和推理演算.ppt》由会员分享，可在线阅读，更多相关《交大数理逻辑课件5-1谓词逻辑的等值和推理演算.ppt（13页珍藏版）》请在金锄头文库上搜索。
1、第5章 谓词逻辑的等值和推理演算 5.1 否定型等值式5.2 量词分配等值式5.3 范式5.4 基本的推理公式5.5 推理演算5.6 谓词逻辑的归结推理法5.1 否定型等值式等值n设设P、Q是任意两个谓词公式，若是任意两个谓词公式，若PQ为普遍有效式，为普遍有效式，则称则称P与与Q是是等值等值的，记作的，记作 PQ，或或P=Q.n由命题公式移植来的等值式n若将命题公式的等值式，直接以若将命题公式的等值式，直接以谓词公式谓词公式代入代入命题变命题变项项便可得谓词等值式便可得谓词等值式n如由：如由： (P Q) = PQ ，得得n ( x)F(x) ( y)G(y) = ( x)F(x)( y)G
2、(y)n如由：如由： PQ = P Qn ( x)F(x)( y)G(y) = ( x)F(x) ( y)G(y)5.1.2 否定型等值式n设P(x)是含自由变项x的任意谓词公式。则 ( x)P(x) = ( x)P(x) ( x)P(x) = ( x)P(x)n从语义上说明n( x)P(x)：并非所有的并非所有的x都具有性质都具有性质P，n相当于至少存在一个相当于至少存在一个x不具有性质不具有性质P，即，即( x)P(x)n所以：所以：( x)P(x) = ( x)P(x)n( x)P(x)：并不存在一个：并不存在一个x具有性质具有性质Pn相当于没有相当于没有x具有性质具有性质P，即，即(
3、x)P(x)n所以，所以，( x)P(x) = ( x)P(x)设个体域为实数设个体域为实数RP(x): x是有理数是有理数设个体域为自然数设个体域为自然数NP(x): x是奇数和偶数是奇数和偶数否定型等值式的分析n设P(x)是含自由变项x的任意谓词公式。则 ( x)P(x) = ( x)P(x) ( x)P(x) = ( x)P(x)n在1, 2域上分析n ( x)P(x) =(P(1) P(2) =P(1) P(2) = ( x)P(x)可见，否定词越过量词的内移规律，就是摩根律的推广可见，否定词越过量词的内移规律，就是摩根律的推广n ( x)P(x) =(P(1) P(2) =P(1)
4、P(2) =( x)P(x)否定型等值式的证明n设P(x)是含自由变项x的任意谓词公式。则 ( x)P(x) = ( x)P(x) ( x)P(x) = ( x)P(x)n在语义上证明n A真真 B真真设任一解释设任一解释I I下有下有 ( x)P(x)=T 则则 ( x)P(x)=F 即存在一个即存在一个x0,使使P(x0)= F 于是，于是，P(x0)= T 在解释在解释I下下 ( x)P(x)=Tn B真真 A真真设任一解释设任一解释I I下有下有 ( x)P(x)=T即存在一个即存在一个x0,使使P(x0)=T于是，于是， P(x0)=F则则 ( x)P(x)=F 即即 ( x)P(x
5、)=T依据：依据：若存在一个解若存在一个解释释I I，使使A真真B就真，就真，B真真A就真，则就真，则A=B否定型等值式举例n“天下乌鸦一般黑”的表示n设设F(x): x是乌鸦，是乌鸦，G(x,y): x与与y是一般黑。是一般黑。n原句可表示成：原句可表示成：若若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
6、(y) G(x,y)不存在乌鸦不存在乌鸦x和乌鸦和乌鸦y，它们是不一样黑的。，它们是不一样黑的。5.2 量词分配等值式n量词对、 的分配律 n( x)(P(x)q) = ( x)P(x)qn( x)(P(x)q) = ( x)P(x)qn( x)(P(x)q) = ( x)P(x)qn( x)(P(x)q) = ( x)P(x)q 设：P(x)是含自由变元x的任意谓词公式。 q是不含变元x的谓词公式 量词的扩展量词的扩展 量词的收缩量词的收缩量词分配等值式的证明n(x)(P(x)q) = (x)P(x)q依据：依据：若存在一个解若存在一个解释释I I，使使A真真B就真，就真，B真真A就真，则就
7、真，则A=Bn B真真 A真真设任一解释设任一解释I I下有下有 ( 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) =T n A真真 B真真设在一解释设在一解释I 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)
8、q =T 量词分配等值式n量词对的分配律 n( x)(P(x) q) = ( x)P(x) qn( x)(P(x) q) = ( x)P(x) qn( x)(q P(x) = q ( x)P(x)n( x)(q P(x) = q ( x)P(x) 设：设：P(x)是含自是含自由变元由变元x的任意的任意谓词公式。谓词公式。 q是是不含变元不含变元x的谓的谓词公式词公式 量词的扩展量词的扩展 量词的收缩量词的收缩n ( 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量词分配等值式n
9、量词对的分配律n( x)(P(x)Q(x) = ( x)P(x)( x)Q(x)n注意：对无分配律n从从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) ( x)Q(x) ( x)(P(x) Q(x) 量词分配等值式n量词 对的分配律n ( x)(P(x)Q(x) = ( x)P(x)( x)Q(x)n
10、注意：对无分配律n由前面证明代换得： ( 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 ( F(x)G(x) = x(F(x)G(x)( x)P(x) = ( x)P(x) ( x)P(x) = ( x)P(x)只要的人，他就会犯错误只要的人，他就会犯错误有的人不爱看电影有的人不爱看电影作业6P68: 7(7), 8(2), 10(1)P84: 1(1)(7), 2(1)(2), 3(1)
