谓词逻辑

《谓词逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章谓词逻辑1.定义:在原子命题中，所描述的对象称为个体；用以刻划个体的性质或个体间关系的部分，称为谓词．2.个体的表示：用a,b,c…或带下角标的ai,bi,ci····表示具体的个体，称为个体常元；用x,y,z…或带下角标的xi,yi,zi····泛指一般的个体，称为个体变元．3．量词全称量词：符号"称为全称量词符“所有的”、“每一个”、“任何一个”和“一切”存在量词:$称为存在量词符“存在”、“一些”、“至少有一个”、“某个”4.定义项由下列规则形成：①个体常元和个体变元是项；②若f是n元个体函数

2、符号，且t1,t2,…,tn是项，则f(t1,t2,…,tn)是项；③由①和②有限次生成都是项5.定义(一阶谓词公式)当且仅当由下列原则形成的符号串：①原子谓词公式是一阶谓词公式；②若A是一阶谓词公式，则(ØA)是一阶谓词公式；③若A,B是一阶谓词公式，则(A∧B),(A∨B),(A®B)和(A«B)都是一阶谓词公式；④若A是一阶谓词公式，x是A中不受量词作用的个体变元，则("x)A和($x)A都是一阶谓词公式；⑤仅有有限次使用①、②、③和④规则形成的是一阶谓词公式．定义2.4.1给定一个谓词公式A，其中

3、有一部分公式形如("x)B(x)或($x)B(x)，则称它为A的x约束部分，称B(x)为相应量词的作用域或辖域．在辖域中，x的所有出现称为约束出现，x称为约束变元,B中不是约束出现的其它个体变元的出现称为自由出现，这些个体变元称自由变元．①约束变元改名规则.将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变．②自由变元代入规则.对某自由出现的个体变元可用个体常元或用与原子公式中与所有个体变元不同的个体变元去代入，且处处代入．2.5Lp中的普遍有效式与蕴含式定理2.

4、5.11设D＝{a1,a2,…,an}.则有下列两个等价式：①("x)A(x)＝A(a1)∧A(a2)∧…∧A(an)②($x)A(x)＝A(a1)∨A(a2)∨…∨A(an)定义2.5.5若存在解释I，使得一阶谓词公式G在解释I中取得真值真，则称一阶谓词公式G是可满足的；若对于所有的解释I，使得一阶谓词公式G在解释I中取得真值真，则称一阶谓词公式G为永真式；若对于所有的解释I，使得一阶谓词公式G在解释I中取得真值假，则称一阶谓词公式G为永假式；定义2.5.6：设A和B是两个一阶谓词公式，若A®B是永真式

5、，则称A蕴含B，记作AÞB；若A«B是永真式，则称A与B等价，记作A＝B。（1）命题公式等价式和蕴含式的推广命题公式的等价式(1)重非律:¬¬P＝P(2)交换律:P∧Q＝Q∧P,P∨Q＝Q∨P,P«Q＝Q«P(3)结合律:(P∧Q)∧C＝P∧(Q∧C),(P∨Q)∨C＝P∨(Q∨C)，(P«Q)«C＝P«(Q«C)(4)分配律：P∧(Q∨C)＝(P∧Q)∨(P∧C)，P∨(Q∧C)＝(P∨Q)∧(P∨C)，(5)德·摩根律:¬(P∧Q)＝¬P∨¬Q,¬(P∨Q)＝¬P∧¬Q(6)等幂律:P∧P＝P，P∨P

6、＝P(7)同一律:P∧T＝P，P∨F＝P(8)零律:P∧F＝F，P∨T＝T(9)吸收律:P∧(P∨Q)＝P,P∨(P∧Q)＝P(10)互补律:P∧¬P＝F(矛盾律)P∨¬P＝T(排中律)(11)条件式转化律：P®Q＝¬P∨Q,P®Q＝¬Q®¬P(12)双条件式转化律：P«Q＝(P®Q)∧(Q®P),P«Q＝(P∧Q)∨(¬P∧¬Q),¬(P«Q)＝¬P«Q(13)输出律:(P∧Q)®R＝P®(Q®R)(14)归谬律:(P®Q)∧(P®¬Q)＝¬P命题公式基本蕴含式:(1)P∧QÞP，P∧QÞQ化简式(2)

7、PÞP∨Q，QÞP∨Q附加式(3)P∧(P®Q)ÞQ假言推论(4)¬Q∧(P®Q)Þ¬P拒取式(5)¬P∧(P®Q)ÞQ析取三段论(6)(P®Q)∧(Q®R)ÞP®R假言(条件)三段论(7)(P∨Q)∧(P®R)∧(Q®S)ÞR∨S二难推论(8)(P«Q)∧(Q«R)ÞP«R等价(双条件)三段论(9)P，QÞP∧Q合成式(2)量词在否定词下的转化：①Ø("x)A(x)＝($x)ØA(x)②Ø($x)A(x)＝("x)ØA(x)(3)量词辖域的扩展和收缩．令A(x)为只含自由变元x出现的谓词公式，而B为不含

8、变元x的谓词公式，则有：基本式：①("x)(A(x)∨B)＝("x)A(x)∨B②("x)(A(x)∧B)＝("x)A(x)∧B③($x)(A(x)∨B)＝($x)A(x)∨B④($x)(A(x)∧B)＝($x)A(x)∧B⑤("x)(A(x)®B)＝($x)A(x)®B⑥("x)(B®A(x))＝B®("x)A(x)⑦($x)(A(x)®B)＝("x)A(x)®B⑧($x)(B®A(x))＝B®($x)A(x)2.6Lp中一