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

第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)=(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)可见，否定词越过量词的内移规律，就是摩根律的推广,(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,否定型等值式举例,“天下乌鸦一般黑”的表示设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)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(x)q=T,量词分配等值式,量词对的分配律(x)(P(x)q)=(x)P(x)q(x)(P(x)q)=(x)P(x)q(x)(qP(x)=q(x)P(x)(x)(qP(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)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)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(