离散数学-2-7谓词演算的推理理论

《离散数学-2-7谓词演算的推理理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章谓词逻辑2-7谓词演算的推理理论授课人：李朔Email:chn.nj.ls@gmail.com1一、谓词演算推理规则谓词演算的推理方法,可以看作是命题演算推理方法的扩张。在一阶逻辑中，推理的形式结构仍为H1H2…HnB。若该式为逻辑有效式，则称推理正确，称B是H1，H2，…，Hn，的逻辑结论，记H1H2…HnB。一般的，将逻辑有效蕴含式称为推理定律。命题逻辑中的重言蕴含式，在一阶逻辑中的代入实例，都是一阶逻辑中的推理定律。另外，每个等值式都可产生两条推理定律。2一、谓词演算推理规则谓词演算推理规则P规则：前提在推导过程中的任何时候都可以引入

2、使用。T规则：在推导过程中，如果有一个或多个公式重言蕴涵这公式S，则公式S可以引入推导之中。命题演算推理中的P规则、T规则（置换规则、合取引入规则）在谓词推理中都是对的，都可以使用；3一、谓词演算推理规则在谓词推理中，某些前提与结论可受量词限制，为了使用等价式和蕴含式，必须在推理过程中有消去和添加的规则，使推理类似于命题演算中的推理理论。在推理过程中，除了用到命题逻辑中的推理规则外，还须用到下面4条规则。其中AB不一定表示A→B是逻辑有效式(非永真)，而仅表示在一定条件下，当A为真时，B也为真的推理关系。全称指定规则（简称US规则）全称推广规则（简称UG规则）

3、存在量词指定规则（简称ES规则）存在推广规则（简称EG规则）4二、全称指定规则1．全称指定规则（简称US规则）(x)P(x)∴P(c)这条规则可以有二种形式：xP(x)P(y)①xP(x)P(c)②在推理过程中①，②两种形式可根据需要选用。两式成立的条件是：（1）x为P（x）中自由出现的个体变元(不在P(x)中受约束）（2）在①中，y为不在P（x）中约束出现的个体变元；（3）在②中，C为任意的论域中某个客体。5二、全称指定规则*全称指定规则在使用中，若不注意条件会犯错误。例如在实数集中的二元谓词F（x，y）：x>y，则公式xyF(x,y)为真命题。

4、设P（x）=yF(x,y),此时x在P（x）中自由出现，若用y取代x，则得x(yF(x,y))yF(y,y),结论为“存在y，y>y”，这是假命题*出错原因为y在P（x）中是约束出现。6三、全称推广规则2．全称推广规则（简称UG规则）P(x)∴(x)P(x)P（y）xP(x)上式成立，要求以下条件：（1）y在P（y）中自由出现，且y取任何值时P（y）均为真；（2）取代y的x不能在P（y）中约束出现，否则产生错误。7三、全称推广规则例在实数集中F（x，y）：x>y，取P（y）=xF(x,y)对给定y都成立。若应用上式时，以x取代y得x(x(x

5、>x))，这是假命题*出错原因是违背了（2）。8四、存在量词指定规则3．存在量词指定规则（简称ES规则）(x)P(x)∴P(c)xP(x)P(c)上式的成立，要求满足以下条件：(1)c是使P（x）为真的特定个体常项；(2)c不曾在P（x）中出现；(3)P（x）中除x还有其它自由的客体变元时，不能用此规则。9四、存在量词指定规则例：在自然数集中，设F（x）：x为奇数，G（x）：x为偶数。则xF(x)xG(x)为真命题。如果不注意以上条件的使用，从xF(x)，xG(x)会推出假命题来：1．xF(x)P2．F（c）ES(1)3．xG(x)P4．G（

6、c）ES(3)5．F（c）G(c)T(2),(4)I6．x(F(x)G(x))EG(5)*以上结论显然错的，其原因是违背条件（1），2步与4步中的c不应相同。10四、存在量词指定规则又如，在实数集中，xy(x>y)是真命题，请看下面推导：1．xy(x>y)P2．y（z>y）US(1)3．z>cES(2)4．x(x>c)UG(3)而x(x>c)是假命题。*结论是错的，其原因是违背了（3），对2使用ES规则时，z为自由出现的个体变项。11五、存在推广规则4．存在推广规则（简称EG规则）P(c)∴(x)P(x)P（c）xP(x)上式成立，要求

7、以下条件：（1）c为特定的个体常项；（2）取代c的x不能已在P（c）中出现过。12五、存在推广规则例在实数集中，取F（x，y）：x>y，并取P(3)=xF(x,3),P(3)为真命题。在使用上式，若用x取代3，则得到xF(x,x)这是假命题*其原因是违背了（2）13六、例题例：找出下述推导的错误原因(a)(1)(x)A(x)S(x)P(2)A(x)S(x)US(1)错：(x)P(x)使用US规则时，P(x)是整个公式，上述公式中A(x)S(x)才是整个公式。正确：（1）(x)A(x)S(x)P（2）(x)A(x)S(y)T(1)E(换名规则

8、)(3)A(x)S(y