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

《交大数理逻辑课件5-1 谓词逻辑的等值和推理演算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、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是奇数和偶数否定型等值式的分析设

3、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下有¬(

4、x)P(x)=T则(x)P(x)=F即存在一个x0,使P(x0)=F于是，¬P(x0)=T∴在解释I下(x)¬P(x)=TB真Þ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

5、))=(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)是含自由变元

6、x的任意谓词公式。q是不含变元x的谓词公式量词的扩展量词的收缩量词分配等值式的证明(x)(P(x)∨q)=(x)P(x)∨q依据：若存在一个解释I，使A真B就真，B真A就真，则A=BB真Þ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)=TA真ÞB真设在一解释I下，有(x)(P(x)∨q)=T从而对任一个x,使P(x)∨q=T又①设q=T,有(x)P(x)∨q=T②

7、若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的谓词公式量词的扩展量词的收缩(x)(P(x)→q)=(x)(¬P(x)∨q)=(x)¬P(x)∨q=¬(x)P(x)∨q=(x)P(x)→q(x)(P(x)∨q)=(

8、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)