《离散数学-2-7谓词演算的推理理论》由会员分享，可在线阅读，更多相关《离散数学-2-7谓词演算的推理理论（23页珍藏版）》请在金锄头文库上搜索。
1、第二章谓词逻辑2-7 谓词演算的推理理论 授课人：李朔 Email:1一、谓词演算推理规则n谓词演算的推理方法,可以看作是命题演 算推理方法的扩张。n在一阶逻辑中，推理的形式结构仍为H1 H2 HnB。若该式为逻辑有效式，则称推理正确，称B是 H1 ，H2 ，Hn，的逻辑结论，记H1 H2 Hn B。n一般的，将逻辑有效蕴含式称为推理定律。 命题逻辑中的重言蕴含式，在一阶逻辑中的 代入实例，都是一阶逻辑中的推理定律。另 外，每个等值式都可产生两条推理定律。2一、谓词演算推理规则n谓词演算推理规则nP规则：前提在推导过程中的任何时候都可以 引入使用。nT规则：在推导过程中，如果有一个或多个公 式
2、重言蕴涵这公式S，则公式S可以引入推导 之中。 n命题演算推理中的P规则、T规则（置换规则、合取 引入规则）在谓词推理中都是对的，都可以使用；3一、谓词演算推理规则n 在谓词推理中，某些前提与结论可受量词限制 ，为了使用等价式和蕴含式，必须在推理过程 中有消去和添加的规则，使推理类似于命题演 算中的推理理论。 n 在推理过程中，除了用到命题逻辑中的推理规则外，还 须用到下面4条规则。其中A B不一定表示AB是逻 辑有效式(非永真)，而仅表示在一定条件下，当A为真 时，B也为真的推理关系。n全称指定规则（简称US规则）n全称推广规则（简称UG规则） n存在量词指定规则（简称ES规则）n存在推广规
3、则（简称EG规则）4二、全称指定规则1全称指定规则（简称US规则）(x)P(x)P(c) n 这条规则可以有二种形式：nxP(x)P(y) nxP(x)P(c) 在推理过程中，两种形式可根据需要选用。两式成 立的条件是：n（1）x为P（x）中自由出现的个体变元(不 在P(x)中受约束）n（2）在中，y为不在P（x）中约束出现的 个体变元；n（3）在中，C为任意的论域中某个客体。5二、全称指定规则*全称指定规则在使用中，若不注意条件会犯错误。 例如 在实数集中的二元谓词F（x，y）：xy，则公式xy F(x, y)为真命题。 设P（x）=y F(x, y),此时x在P（x）中自由出现，若用y取代
4、x，则得x(yF(x, y)y F(y ,y), 结论为“存在y，yy” ，这是假命题*出错原因为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）：xy，取P（y）= x F(x, y)对给定y都成立。若应用上式时，以x取代y得x(x(xx)，这是假命题*出错原因是违背了（2）。8四、存在量词指定规则 3存在量词指定规则（简称ES规则）
5、 (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为偶 数。则 x F(x)x G(x) 为真命题。如果不注意以上条件的使用，从x F(x)，x G(x) 会推出假命题来：1x F(x) P2F（c） ES(1)3x G(x) P4G（c） ES(3)5F（c） G(c) T(2),(4)I6x( F(x)G(x) EG(5) *以上结论显然错的，其原
6、因是违背条件（1），2步与4步 中的c不应相同。10四、存在量词指定规则 又如，在实数集中，xy(xy)是真命题，请看 下面推导：1xy(xy) P2y（zy） US(1)3zc ES(2)4x(xc) UG(3)而x(xc)是假命题。 *结论是错的，其原因是违背了（3），对2使用 ES规则时 ，z为自由出现的个体变项。 11五、存在推广规则 4存在推广规则（简称EG规则）P(c) (x)P(x) P（c）x P(x) 上式成立，要求以下条件： （1）c为特定的个体常项； （2）取代c的x不能已在P（c）中出现过。 12五、存在推广规则 例 在实数集中，取F（x，y）：xy，并取P(3)=x
7、F(x, 3), P(3)为真命题。在使用上式，若用x取代3，则得到x F(x, x)这是假命题 *其原因是违背了（2）13六、例题n 例：找出下述推导的错误原因 (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)14六、例题(b) (1) (x)(P(x) Q(x) P (2) P(a) Q(b) US(1) 错：要统
8、一全称量词消去 正确： （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六、例题例：给定下面2个推理,找出错误.（1） 1x (F(x) G(x) P2F(y) G(y) US(1)3x F(x) P4F(y) ES(3)5G(y) T(2)(3) I6xG(x) UG(5) （2） 1xy F(x, y) P2y F(z, y) US(1)3F(z, c) ES(2)4x F(x, c) UG5yx F(x, y) EG *在
9、上面推理中（1）中从3到4有错，（2）中从2到3有错16六、例题n 希望在应用上述规则时，千万注意条件，否则 会犯错误。下面给出几个谓词逻辑中构造证明 的例子。 例：证明苏格拉底三段论“凡人都是要死的，张三是人，所以张三要死。”首先将命题符号化：解： F（x）：x是人。 G（x）：x要死。 a：张三。前提： x F(x) G(x), F(a)结论：G(a)。证明：1x (F(x) G(x) P2F(a) G(a) US(1)3F(a) P4G(a) T(2)(3) I *在本例中，没指明个体域，因而应取全总个体域。并引入特性谓词 。17六、例题n 例：人会说话，猴子不会说话，所以猴子不是 人。
10、 解：设论域为全域，设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) 18六、例题例：每个学术会的成员都是工人并且是专家，有些成员是青年人。所 以有的成员是青年专家
11、。请在谓词逻辑中证明上面推理。解： 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) ) P2F(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) I6G(c) H(c) T(4)(5) I 7R(c) T(2) I8G(c) T(6) I9F(c) R(c) G(c) T(5)(7)(8) I10x (F(x) R(x) G(
12、x) EG(9) 19六、例题若将证明步骤改为：1x (F(x) G(x) H(x) P2F(c) G(c) H(c) US(1)3x (F(x) R(x) ) P4F(c) R(c) ES(3) 最后也能得出结论，但此证明是错的。原因出在3，4上， 2中的c不一定能满足4。 *因此，若在前提中，既有存在量词公式，又有全称量词公 式，应先引入存在量词规则。20六、例题例：构造下面推理的证明。 前提：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) US(5) 7G(y) F(y) T(4)(6) I 8x (G(x) F(x) UG(7)21本课小结nUS规则 nUG规则 nES规则 nEG规则22课后作业nP79 (1) n补充
