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

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

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

3、,5,二、全称指定规则,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为任意的论域中某个客体。,6,二、全称指定规则,*全称指定规则在使用中，若不注意条件会犯错误。 例如 在实数集中的二元谓词F（x，y）：xy，则公式 xy F(x, y)为真命题。 设P（x）=y F(x, y),此时x在P（x）中自由出现， 若用y取代x，则得

4、x(yF(x, y)y F(y ,y), 结论为“存在y，yy”，这是假命题 *出错原因为y在P（x）中是约束出现。,7,三、全称推广规则,2全称推广规则（简称UG规则） P(x) (x)P(x) P（y） xP(x) 上式成立，要求以下条件： （1）y在P（y）中自由出现，且y取任何值时P（y）均为真； （2）取代y的x不能在P（y）中约束出现，否则产生错误。,8,三、全称推广规则,例 在实数集中F（x，y）：xy， 取P（y）= x F(x, y)对给定y都成立。 若应用上式时，以x取代y 得x(x(xx)，这是假命题 *出错原因是违背了（2）。,9,四、存在量词指定规则,3存在量词指定规

5、则（简称ES规则） (x)P(x) P(c) xP(x) P(c) 上式的成立，要求满足以下条件： (1)c是使P（x）为真的特定个体常项； (2) c不曾在P（x）中出现； (3) P（x）中除x还有其它自由的客体变元时，不能用此规则。,10,四、存在量词指定规则,例：在自然数集中，设F（x）：x为奇数，G（x）：x为偶数。则 x F(x)x G(x) 为真命题。 如果不注意以上条件的使用，从x F(x)，x G(x)会推出假命题来： 1x F(x) P 2F（c） ES(1) 3x G(x) P 4G（c） ES(3) 5F（c） G(c) T(2),(4)I 6x( F(x)G(x) E

6、G(5) *以上结论显然错的，其原因是违背条件（1），2步与4步中的c不应相同。,11,四、存在量词指定规则,又如，在实数集中，xy(xy)是真命题，请看下面推导： 1xy(xy) P 2y（zy） US(1) 3zc ES(2) 4x(xc) UG(3) 而x(xc)是假命题。 *结论是错的，其原因是违背了（3），对2使用ES规则时，z为自由出现的个体变项。,12,五、存在推广规则,4存在推广规则（简称EG规则） P(c) (x)P(x) P（c）x P(x) 上式成立，要求以下条件： （1）c为特定的个体常项； （2）取代c的x不能已在P（c）中出现过。,13,五、存在推广规则,例 在实数

7、集中，取F（x，y）：xy，并取 P(3)=x F(x, 3), P(3)为真命题。 在使用上式，若用x取代3，则得到x F(x, x)这是假命题 *其原因是违背了（2）,14,六、例题,例：找出下述推导的错误原因 (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(换名规则) (3) A(x) S(y) US(2),15,六、例题,(b) (1) (x)(P(x) Q

8、(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）,16,六、例题,例：给定下面2个推理,找出错误. （1） 1x (F(x) G(x) P 2F(y) G(y) US(1) 3x F(x) P 4F(y) ES(3) 5G(y) T(2)(3) I 6xG(x) UG(5) （2） 1xy F(x, y) P 2y F(z, y) US(1) 3F

9、(z, c) ES(2) 4x F(x, c) UG 5yx F(x, y) EG *在上面推理中（1）中从3到4有错，（2）中从2到3有错,17,六、例题,希望在应用上述规则时，千万注意条件，否则会犯错误。下面给出几个谓词逻辑中构造证明的例子。 例：证明苏格拉底三段论“凡人都是要死的，张三是人，所以张三要死。” 首先将命题符号化： 解： F（x）：x是人。 G（x）：x要死。 a：张三。 前提： x F(x) G(x), F(a) 结论：G(a)。 证明： 1x (F(x) G(x) P 2F(a) G(a) US(1) 3F(a) P 4G(a) T(2)(3) I *在本例中，没指明个体

10、域，因而应取全总个体域。并引入特性谓词。,18,六、例题,例：人会说话，猴子不会说话，所以猴子不是人。 解：设论域为全域，设M(x):x是人。S(x):x是猴子。T(x):x会说话。 则前提为： x( M(x) T(x), x (S(x) T(x) 结论为： x(S(x) M(x) 证明：(1) x( M(x) T(x) P (2) M(y) T(y) US(1) (3) x (S(x) T(x) P (4)S(y) T(y) US(3) (5)T(y) S(y) T(4) E (6) M(y) S(y) T(2),(5) I (7) S(y) M(y) T(6) E (8) x(S(x) M

11、(x) ) UG (7),19,六、例题,例：每个学术会的成员都是工人并且是专家，有些成员是青年人。所以有的成员是青年专家。请在谓词逻辑中证明上面推理。 解： F（x）：x为学术会成员。G（x）：x是专家。 H（x）：x是工人。 R（x）：x是青年人。 前提：x (F(x) G(x) H(x), x (F(x) R(x) 结论：x (F(x) R(x) G(x) 证明：1x (F(x) R(x) ) P 2F(c) R(c) ES(1) 3x (F(x) G(x) H(x) P 4F(c) G(c) H(c) US(3) 5F(c) T(2) I 6G(c) H(c) T(4)(5) I 7R

12、(c) T(2) I 8G(c) T(6) I 9F(c) R(c) G(c) T(5)(7)(8) I 10 x (F(x) R(x) G(x) EG(9),20,六、例题,若将证明步骤改为： 1x (F(x) G(x) H(x) P 2F(c) G(c) H(c) US(1) 3x (F(x) R(x) ) P 4F(c) R(c) ES(3) 最后也能得出结论，但此证明是错的。原因出在3，4上，2中的c不一定能满足4。 *因此，若在前提中，既有存在量词公式，又有全称量词公式，应先引入存在量词规则。,21,六、例题,例：构造下面推理的证明。 前提：x (F(x) H(x), x (G(x) H(x) 结论：x (G(x) F(x) 证明： 1x (F(x) H(x) P 2x (F(x) H(x) T(1) E 3x (H(x) F(x) T(2) E 4H(y) F(y) US(3) 5x (G(x) H(x) ) P 6G(y) H(y)