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

1、第二章谓词逻辑2-7 谓词演算的推理实际授课人：李朔:chn.nj.lsgmail一、谓词演算推理规那么n谓词演算的推理方法,可以看作是命题演算推理方法的扩张。n在一阶逻辑中，推理的方式构造仍为n H1 H2 HnB。n 假设该式为逻辑有效式，那么称推理正确，称B是H1 ，H2 ，Hn，的逻辑结论，记H1 H2 Hn B。n普通的，将逻辑有效蕴含式称为推理定律。命题逻辑中的重言蕴含式，在一阶逻辑中的代入实例，都是一阶逻辑中的推理定律。另外，每个等值式都可产生两条推理定律。一、谓词演算推理规那么谓词演算推理规那么谓词演算推理规那么P规那么：前提在推导过程中的任何时候都规那么：前提在推导过程中的任

2、何时候都可以引入运用。可以引入运用。T规那么：在推导过程中，假设有一个或多规那么：在推导过程中，假设有一个或多个公式重言蕴涵这公式个公式重言蕴涵这公式S，那么公式，那么公式S可以可以引入推导之中。引入推导之中。 命题演算推理中的命题演算推理中的P规那么、规那么、T规那么置规那么置换规那么、合取引入规那么在谓词推理换规那么、合取引入规那么在谓词推理中都是对的，都可以运用；中都是对的，都可以运用；一、谓词演算推理规那么n 在谓词推理中，某些前提与结论可受量词限制，为了运用等价式和蕴含式，必需在推理过程中有消去和添加的规那么，使推理类似于命题演算中的推理实际。n 在推理过程中，除了用到命题逻辑中的推

3、理规那么外，还须用到下面4条规那么。其中A B不一定表示AB是逻辑有效式(非永真)，而仅表示在一定条件下，当A为真时，B也为真的推理关系。n 全称指定规那么简称US规那么n 全称推行规那么简称UG规那么 n 存在量词指定规那么简称ES规那么n 存在推行规那么简称EG规那么二、全称指定规那么1全称指定规那么简称US规那么 (x)P(x) P(c)这条规那么可以有二种方式：xP(x)P(y) xP(x)P(c) 在推理过程中，两种方式可根据需求选用。两式成立的条件是：1x为Px中自在出现的个体变元(不在P(x)中受约束2在中，y为不在Px中约束出现的个体变元；3在中，C为恣意的论域中某个客体。二、

4、全称指定规那么 *全称指定规那么在运用中，假设不留意条件会犯错误。例如 在实数集中的二元谓词Fx，y：xy，那么公式 xy F(x, y)为真命题。设Px=y F(x, y),此时x在Px中自在出现， 假设用y取代x，那么得 x(yF(x, y)y F(y ,y), 结论为“存在y，yy，这是假命题 *出错缘由为y在Px中是约束出现。 三、全称推行规那么2 2全称推行规那么简称全称推行规那么简称UGUG规那么规那么 P(x) P(x) ( (x)P(x)x)P(x) P Py y xP(x)xP(x)上式成立，要求以下条件：上式成立，要求以下条件：1 1y y在在P Py y中自在出现，且中自

5、在出现，且y y取任何值时取任何值时P Py y均为真；均为真；2 2取代取代y y的的x x不能在不能在P Py y中约束出现，否那么中约束出现，否那么产生错误。产生错误。三、全称推行规那么例例 在实数集中在实数集中F Fx x，y y：xyxy， 取取P Py y= = x F(x, y)x F(x, y)对给定对给定y y都成立。都成立。 假设运用上式时，以假设运用上式时，以x x取代取代y y 得得x(x(x(xx)x(xx)，这是假命题，这是假命题 * *出错缘由是违背了出错缘由是违背了2 2。四、存在量词指定规那么 3 3存在量词指定规那么简称存在量词指定规那么简称ESES规那么规

6、那么( (x)P(x) x)P(x) P(c)P(c)xP(x) xP(x) P(c) P(c)上式的成立，要求满足以下条件：上式的成立，要求满足以下条件：(1)c(1)c是使是使P Px x为真的特定个体常项；为真的特定个体常项；(2) c(2) c不曾在不曾在P Px x中出现；中出现；(3) P(3) Px x中除中除x x还有其它自在的客体变元时，不还有其它自在的客体变元时，不能用此规那么。能用此规那么。四、存在量词指定规那么 例：在自然数集中，设Fx：x为奇数，Gx：x为偶数。那么 x F(x)x G(x) 为真命题。 假设不留意以上条件的运用，从x F(x)，x G(x)会推出假命

7、题来： 1x F(x) P 2Fc ES(1) 3x G(x) P 4Gc ES(3) 5Fc G(c) T(2),(4)I 6x( F(x)G(x) EG(5)*以上结论显然错的，其缘由是违背条件1，2步与4步中的c不应一样。四、存在量词指定规那么 又如，在实数集中，xy(xy)是真命题，请看下面推导： 1xy(xy) P 2yzy US(1) 3zc ES(2) 4x(xc) UG(3) 而x(xc)是假命题。*结论是错的，其缘由是违背了3，对2运用ES规那么时，z为自在出现的个体变项。 五、存在推行规那么 4存在推行规那么简称EG规那么 P(c)(x)P(x)Pcx P(x)上式成立，要

8、求以下条件：1c为特定的个体常项；2取代c的x不能已在Pc中出现过。 五、存在推行规那么 例例 在实数集中，取在实数集中，取Fx，y：xy，并取，并取 P(3)=x F(x, 3), P(3)为真命题。为真命题。 在运用上式，假设用在运用上式，假设用x取代取代3，那么得到，那么得到x F(x, x)这是假命题这是假命题*其缘由是违背了其缘由是违背了2六、例题例：找出下述推导的错误缘由(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

9、) P 2 (x)A(x) S(y) T(1) E(换名规那么) (3) A(x) S(y) US(2)六、例题(b)(1) (x)(P(x) Q(x) P(2) P(a) Q(b) US(1)错：要一致全称量词消去正确： 2 Pa) Q(a) US(1)(c)(1) S(c) Q(c) P(2) xS(x) Q(x) EG1错：运用EG规那么时，P(x)应是整个公式正确：2 xS(x) Q(x) EG1六、例题例：给定下面例：给定下面2个推理个推理,找出错误找出错误. 1 1x (F(x) G(x) P 2F(y) G(y) US(1) 3x F(x) P 4F(y) ES(3) 5G(y)

10、 T(2)(3) I 6xG(x) UG(5)2 1xy F(x, y) P 2y F(z, y) US(1) 3F(z, c) ES(2) 4x F(x, c) UG 5yx F(x, y) EG*在上面推理中在上面推理中1中从中从3到到4有错，有错，2中从中从2到到3有错有错六、例题n 希望在运用上述规那么时，千万留意条件，否那希望在运用上述规那么时，千万留意条件，否那么会犯错误。下面给出几个谓词逻辑中构造证明么会犯错误。下面给出几个谓词逻辑中构造证明的例子。的例子。n 例：证明苏格拉底三段论例：证明苏格拉底三段论“凡人都是要死的，张三凡人都是要死的，张三是人，所以张三要死。是人，所以张三

11、要死。n 首先将命题符号化：首先将命题符号化：n 解：解： Fx：x是人。是人。 Gx：x要死。要死。 a：张三。张三。n 前提：前提： x F(x) G(x), F(a)n 结论：结论：G(a)。n 证明：证明：n 1x (F(x) G(x) Pn 2F(a) G(a) US(1)n 3F(a) Pn 4G(a) T(2)(3) I n *在本例中，没指明个体域，因此应取全总个体在本例中，没指明个体域，因此应取全总个体域。并引入特性谓词。域。并引入特性谓词。六、例题例：人会说话，猴子不会说话，所以猴子不是人。例：人会说话，猴子不会说话，所以猴子不是人。解：设论域为全域，设解：设论域为全域，设

12、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(x) ) UG (7) 六、例题例：每个学术会的成员都是工人并且是专家，有些

13、成员是青年人。所以例：每个学术会的成员都是工人并且是专家，有些成员是青年人。所以有的成员是青年专家。请在谓词逻辑中证明上面推理。有的成员是青年专家。请在谓词逻辑中证明上面推理。 解：解： Fx：x为学术会成员。为学术会成员。Gx：x是专家。是专家。 Hx：x是工人。是工人。 Rx：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

14、) T(2) I 6G(c) H(c) T(4)(5) I 7R(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)六、例题假设将证明步骤改为：假设将证明步骤改为： 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。*因此，假设在前提中，既有存在量词公式，又有全称量词因此，假设在前提中，既有存在量词公式，又有全称量词公式，应先引入存在量词规那么。公式，应先引入存在量词规那么。六、例题例：构造下面推理的证明。例：构造下面推理的证明。前提：前提：x (F(x) H(x), x (G(x) H(x)结论：结论：x (G(x) F(x)证明：证明：1x (F(x) H(x) P2x (F(x) H(x) T(1) E3x (H(x) F(x) T