《交大数理逻辑课件5-1谓词逻辑的等值和推理演算.ppt》由会员分享，可在线阅读，更多相关《交大数理逻辑课件5-1谓词逻辑的等值和推理演算.ppt（13页珍藏版）》请在三一办公上搜索。
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)是含自由变项x的任意谓词公式。则(x)P(x)
2、=(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),设个体域为实数RP(x):x是有理数,设个体域为自然数NP(x):x是奇数和偶数,否定型等值式的分析,设P(x)是含自由变项x的任意谓词公式。则(x)P(x)=(x)P(x)(x)P(x)=(x)P(x)在1,2域上分析(x)P(x)=(P(1)P(2)=P(1)P(2)=(x)P(x)可见，否
3、定词越过量词的内移规律，就是摩根律的推广,(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)=T即存在一个x0,使P(x0)=T于是，P(x0)=F则(x)P(x)=F 即(x)P(x)=T,依据：若存在一个解释I，使A真B就真，B真A就真，则A=B
4、,否定型等值式举例,“天下乌鸦一般黑”的表示设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和乌鸦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
5、)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,有 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(
6、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的谓词公式,(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)
7、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),量词分配等值式,量词 对的分配律(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)
8、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),只要的人，他就会犯错误,有的人不爱看电影,作业6,P68:7(7),8(2),10(1)P84:1(1)(7),2(1)(2),3(1),
