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

离散数学2012

第二章谓词逻辑2-7 谓词演算的推理理论 授课人：李朔 Email:chn.nj.ls@http://1

离散数学2012

一、谓词演算推理规则 谓词演算推理规则谓词演算的推理方法,可以看作是命题演算 推理方法的扩张。在一阶逻辑中，推理的形式结构仍为 H1 ∧ H2 ∧…∧ Hn→B。 若该式为逻辑有效式，则称推理正确，称B是 H1 ,H2 ,…,Hn,的逻辑结论，记H1 ∧ H2 ∧…∧ Hn B。 一般的，将逻辑有效蕴含式称为推理定律 推理定律。命 推理定律 题逻辑中的重言蕴含式，在一阶逻辑中的代入 实例，都是一阶逻辑中的推理定律。另外，每 个等值式都可产生两条推理定律。2

离散数学2012

一、谓词演算推理规则 谓词演算推理规则谓词演算推理规则P规则 ： 前提在推导过程中的任何时候都可以 规则： 规则 引入使用。 引入使用。 T规则：在推导过程中，如果有一个或多个公 规则： 规则 在推导过程中， 式重言蕴涵这公式S,则公式S可以引入推导之 式重言蕴涵这公式 ，则公式 可以引入推导之 中。命题演算推理中的P规则、T规则(置换规则、合取引 入规则)在谓词推理中都是对的，都可以使用；

离散数学2012

一、谓词演算推理规则 谓词演算推理规则在谓词推理中，某些前提与结论可受量词限制， 为了使用等价式和蕴含式，必须在推理过程中有 消去和添加的规则，使推理类似于命题演算中的 推理理论。在推理过程中，除了用到命题逻辑中的推理规则外，还须 用到下面4条规则。其中A B不一定表示A→B是逻辑有 效式(非永真),而仅表示在一定条件下，当A为真时，B也 为真的推理关系。 全称指定规则(简称US规则) 全称推广规则(简称UG规则) 存在量词指定规则(简称ES规则) 存在推广规则(简称EG规则)4

离散数学2012

二、全称指定规则 全称指定规则1.全称指定规则 简称US规则 全称指定规则(简称US规则 全称指定规则 简称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

离散数学2012

二、全称指定规则 全称指定规则*全称指定规则在使用中，若不注意条件会犯错误。例如 在实数集中的二元谓词F(x,y):x>y,则公式 x y F(x, y)为真命题。 设P(x)= y F(x, y),此时x在P(x)中自由出现， 若用y取代x,则得 x( yF(x, y)) y F(y ,y), 结论为“存在y,y>y”, 这是假命题 *出错原因为y在P(x)中是约束出现。

离散数学2012

三、全称推广规则简称UG UG规则 2.全称推广规则

(简称UG规则)

P(x) ∴( x)P(x) P(y) xP(x)上式成立，要求以下条件： 上式成立，要求以下条件： (1)y在P(y)中自由出现，且y取任何值时P(y)均为真 均为真； 且 取任何值时P (2)取代y的x不能在P(y)中约束出现，否则产生错误。

离散数学2012

三、全称推广规则例 在实数集中F(x,y):x>y, 取P(y)= x F(x, y)对给定y都成立。 若应用上式时，以x取代y 得 x( x(x>x)),这是假命题 *出错原因是违背了(2)。

离散数学2012

四、存在量词指定规则3.存在量词指定规则(简称ES规则) 存在量词指定规则(简称ES规则) ES规则

( x)P(x) ∴P(c) xP(x) P(c)上式的成立，要求满足以下条件： 上式的成立，要求满足以下条件： (1)c是使P(x)为真的特定个体常项； (2) c不曾在P(x)中出现； (3) P(x)中除x还有其它自由的客体变元时，不能 用此规则。9

离散数学2012

四、存在量词指定规则例：在自然数集中，设F(x):x为奇数，G(x):x为偶数。则 x F(x)∧ x G(x) 为真命题。 如果不注意以上条件的使用，从 x F(x), x G(x)会 推出假命题来： 1. x F(x) P 2.F(c) ES(1) 3. x G(x) P 4.G(c) ES(3) 5.F(c)∧ G(c) T(2),(4)I 6. x( F(x)∧G(x)) EG(5) *以上结论显然错的，其原因是违背条件(1),2步与4步中 的c不应相同。10

离散数学2012

四、存在量词指定规则又如，在实数集中， x y(x>y)是真命题，请看下 面推导： 1. x y(x>y) P 2. y(z>y) US(1) 3.z>c ES(2) 4. x(x>c) UG(3) 而 x(x>c)是假命题。 *结论是错的，其原因是违背了(3),对2使用ES规 则时，z为自由出现的个体变项。11

离散数学2012

五、存在推广规则4.存在推广规则 简称 规则 存在推广规则(简称 规则) 存在推广规则 简称EG规则 P(c) ∴( x)P(x) P(c) x P(x) 上式成立，要求以下条件： (1)c为特定的个体常项； (2)取代c的x不能已在P(c)中出现过。

离散数学2012

五、存在推广规则例 在实数集中，取F(x,y):x>y,并取 P(3)= x F(x, 3), P(3)为真命题。 在使用上式，若用x取代3,则得到 x F(x, x) 这是假命题 *其原因是违背了(2)

离散数学2012

六、例题例：找出下述推导的错误原因 (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) (2) ( x)A(x) → S(y) (3) A(x) → S(y) P T(1) E(换名规则) US(2)14

离散数学2012

六、例题(b) (1) ( x)(P(x) → Q(x)) P (2) P(a) →Q(b) US(1) 错：要统一全称量词消去 正确： (2) P(a) →Q(a) US(1) (c) (1) S(c) → Q(c) P (2) xS(x) → Q(x) EG(1) 错：使用EG规则时，P(x)应是整个公式 正确：(2) x(S(x) → Q(x)) EG(1)15

离散数学2012

六、例题个推理,找出错

误 例：给定下面2个推理 找出错误 给定下面 个推理 找出错误. P (1) 1. x (F(x) → G(x)) ) . 2.F(y) → G(y) US(1) . 3. x F(x) P . 4.F(y) . ES(3) 5.G(y) T(2)(3) I . 6. xG(x) UG(5) . P (2) 1. x y F(x, y) ) . 2. y F(z, y) US(1) . 3.F(z, c) . ES(2) 4. x F(x, c) UG . 5. y x F(x, y) EG . *在上面推理中(1)中从 到4有错，( )中从 到3有错 在上面推理中( )中从3到 有错，(2)中从2到 有错 有错，( 在上面推理中16