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

《离散数学-2-7 谓词演算的推理理论.ppt》由会员分享，可在线阅读，更多相关《离散数学-2-7 谓词演算的推理理论.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、下，当A为真时，B也为真的推理关系。n全称指定规则（简称US规则）n全称推广规则（简称UG规则）n存在量词指定规则（简称ES规则）n存在推广规则（简称EG规则）4二、全称指定规则全称指定规则1全称指定规则全称指定规则（简称简称USUS规则规则）(x)P(x)P(c)这条规则可以有二种形式：nxP(x)P(y)nxP(x)P(c)在推理过程中，两种形式可根据需要选用。两式成立的条件是：n（1）x为P（x）中自由出现的个体变元(不在P(x)中受约束）n（2）在中，y为不在P（x）中约束出现的个体变元；n（3）在中，C为任意的论域中某个客体。5二、全称指定规则全称指定规则*全称指定规则在使用中，若不

4、注意条件会犯错误。例如例如 在实数集中的二元谓词F（x，y）：xy，则公式 xy F(x,y)为真命题。设P（x）=y F(x,y),此时x在P（x）中自由出现，若用y取代x，则得 x(yF(x,y)y F(y,y),结论为“存在y，yy”，这是假命题 *出错原因为y在P（x）中是约束出现。6三、全称推广规则2 2全称推广规则全称推广规则（简称简称UGUG规则规则）P(x)(x)P(x)P（y）xP(x)上式成立，要求以下条件：上式成立，要求以下条件：（1）y在P（y）中自由出现，且且y y取任何值时取任何值时P P（y y）均为真均为真；（2）取代y的x不能在P（y）中约束出现，否则产生错误

5、。7三、全称推广规则例例 在实数集中F（x，y）：xy，取P（y）=x F(x,y)对给定y都成立。若应用上式时，以x取代y 得x(x(xx)，这是假命题 *出错原因是违背了（2）。8四、存在量词指定规则 3 3存在量词指定规则（存在量词指定规则（简称简称ESES规则规则）(x)P(x)P(c)xPxP(x)(x)P(c)P(c)上式的成立，要求满足以下条件：上式的成立，要求满足以下条件：(1)c是使P（x）为真的特定个体常项；(2)c不曾在P（x）中出现；(3)P（x）中除x还有其它自由的客体变元时，不能用此规则。9四、存在量词指定规则 例：在自然数集中，设F（x）：x为奇数，G（x）：x为

6、偶数。则 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)EG(5)*以上结论显然错的，其原因是违背条件（1），2步与4步中的c不应相同。10四、存在量词指定规则 又如，在实数集中，xy(xy)是真命题，请看下面推导：1xy(xy)P 2y（zy）US(1)3zc ES(2)4x(xc)UG(3)而x(xc)是假命题。*结论是错的，其原因是违背了（3），对2使用ES规则时，z为自由出现的个体变项。11五、

7、存在推广规则 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 F(x,3),P(3)为真命题。在使用上式，若用x取代3，则得到x F(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)才是整个公式。正确：（

8、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)错：要统一全称量词消去正确：（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）1 x(F(x)G(x)P 2F(y)G(y)US(1)3 x F(x)P 4F(y)ES(3)5G(y)T(2)(3)I

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

10、 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 *在本例中，没指明个体域，因而应取全总个体域。并引入特性谓词。17六、例题例：例：人会说话，猴子不会说话，所以猴子不是人。解：设论域为全域，设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(

11、y)S(y)T(2),(5)I (7)S(y)M(y)T(6)E (8)x(S(x)M(x)UG(7)18六、例题例：每个学术会的成员都是工人并且是专家，有些成员是青年人。所以例：每个学术会的成员都是工人并且是专家，有些成员是青年人。所以有的成员是青年专家。请在谓词逻辑中证明上面推理。有的成员是青年专家。请在谓词逻辑中证明上面推理。解：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

12、(x)P 4F(c)G(c)H(c)US(3)5F(c)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)19六、例题若将证明步骤改为：若将证明步骤改为：1 x(F(x)G(x)H(x)P 2F(c)G(c)H(c)US(1)3 x(F(x)R(x)P 4F(c)R(c)ES(3)最后也能得出结论，但此证明是错的。原因出在最后也能得出结论，但此证明是错的。原因出在3，4上，上，2中的中的c不一定能满足不一定能满足4。*因此因此，若在前提中，既有存在量词公式，又

13、有全称量词公若在前提中，既有存在量词公式，又有全称量词公式，应先引入存在量词规则。式，应先引入存在量词规则。20六、例题例：构造下面推理的证明。例：构造下面推理的证明。前提：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(2)E4H(y)F(y)US(3)5x(G(x)H(x)P 6G(y)H(y)US(5)7G(y)F(y)T(4)(6)I8x(G(x)F(x)UG(7)21本课小结US规则UG规则ES规则EG规则22课后作业P79(1)补充:符号化下列命题并推证其结论。所有的人或者是吃素的或者是吃荤的，吃素的常吃豆制品，因而不吃豆制品的人是吃荤的。（个体域为人的集合）令F(x)：x是吃素的，G(x)：x是吃荤的，H(x)：x吃豆制品。23