离散数学谓词逻辑推理.ppt

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

1、西华大学第二章第二章 谓词逻辑谓词逻辑第第3节节 一阶逻辑推理理论一阶逻辑推理理论西华大学推理的定义推理的定义称蕴涵式称蕴涵式(A1 A2 Ak)B为推理的形式结构，为推理的形式结构，A1,A2,Ak为推理的前提，为推理的前提，B为推理的结论。为推理的结论。若若(A1 A2 Ak)B为永真式，则称从前提为永真式，则称从前提A1,A2,Ak推出结论推出结论B的推理正确（或说有效），的推理正确（或说有效），B是是A1,A2,Ak的逻辑结论或称有效结论，否的逻辑结论或称有效结论，否则称推理不正确。若从前提则称推理不正确。若从前提A1,A2,Ak推出推出结论结论B的推理正确，则记为的推理正确，则记为(

2、A1 A2 Ak)B。西华大学推理规则推理规则在证明中常用的推理规则有：在证明中常用的推理规则有：1.前前提提引引入入规规则则P：在在证证明明的的任任何何步步骤骤都都可可以以引引入已知的前提；入已知的前提；2.结结论论引引入入规规则则：在在证证明明的的任任何何步步骤骤都都可可以以引引入这次已经得到的结论作为后续证明的前提；入这次已经得到的结论作为后续证明的前提；3.置置换换规规则则E：在在证证明明的的任任何何步步骤骤上上，一一阶阶公公式式中中的的任任何何子子公公式式都都可可用用与与之之等等值值的的公公式式置置换换，得得到到证明的公式序列的另一公式。证明的公式序列的另一公式。以及以及CP规则规则

3、、.和和.的合取的合取、永真蕴涵、永真蕴涵I等。等。使使用用一一阶阶逻逻辑辑公公式式进进行行推推理理还还有有其其他他一一些些推推理理规规则，这些规则建立在下面一些推理定律上。则，这些规则建立在下面一些推理定律上。西华大学一阶逻辑的永真蕴涵式一阶逻辑的永真蕴涵式推推理理定定律律是是一一阶阶逻逻辑辑的的一一些些永永真真蕴蕴涵涵式式，重重要要的推理定律有：的推理定律有：1.附加律：附加律：A(A B)/或称为或称为析取的引入析取的引入2.化简律：化简律：(A B)A,(A B)B/或称为或称为合取的消除合取的消除3.假言推理：假言推理：(AB)AB/或称为或称为分离规则分离规则4.拒取式：拒取式：(

4、AB)BA5.析取三段论：析取三段论：(A B)BA6.假言三段论：假言三段论：(AB)(BC)(AC)/或称为或称为传递规则传递规则西华大学一阶逻辑的永真蕴涵式一阶逻辑的永真蕴涵式(续续)7.等价三段论：等价三段论：(AB)(BC)(AC)8.构造性二难：构造性二难：(AB)(CD)(A C)(B D)西华大学一阶逻辑中一阶逻辑中特有的推理定律特有的推理定律 1.x(A(x)B(x)(x A(x)(x B(x)2.x(A(x)B(x)(x A(x)(x B(x)3.x(A(x)B(x)(x A(x)(x B(x)4.x(A(x)B(x)(x A(x)(x B(x)西华大学一阶逻辑中特有的推理

5、规则一阶逻辑中特有的推理规则 1.全称量词消除规则（全称量词消除规则（UI规则）规则）：(i).x A(x)A(y)(ii).x A(x)A(c)成立的条件是：成立的条件是：(1).x是是A(x)的自由变元；的自由变元；(2).在在(i)中中，y为为不不在在A(x)中中约约束束出出现现的的变变元元，y可可以以在在A(x)中中自自由由出出现现，也也可可在在证证明明序序列列中中前前面面的的公公式中出现。式中出现。(3).在在(ii)中，中，c是是任意的个体常项任意的个体常项，可以是证，可以是证明序列中前面公式所指定的个体常项。明序列中前面公式所指定的个体常项。西华大学举例：全称量词消除规则举例：全

6、称量词消除规则指出下列推导中的错误，并加以改正：指出下列推导中的错误，并加以改正：A(1).(x)(P(x)Q(x)/前提前提(2).P(a)Q(b)/全称量词消除规则全称量词消除规则解：解：在使用量词消除规则时，应使用个体替换量在使用量词消除规则时，应使用个体替换量词词所约束的变元在所约束的变元在公式中的所有出现，正确的推公式中的所有出现，正确的推理是：理是：(1).(x)(P(x)Q(x)/前提前提(2).P(a)Q(a)/全称量词消除规则全称量词消除规则西华大学举例：全称量词消除规则举例：全称量词消除规则指出下列推导中的错误，并加以改正：指出下列推导中的错误，并加以改正：B (1).x

7、P(x)Q(x)/前提前提(2).P(y)Q(y)/全称量词消除规则全称量词消除规则量量词词 x的的辖辖域域为为P(x)，而而非非P(x)Q(x)，所所以以不不能能直接使用全称量词消除规则。直接使用全称量词消除规则。西华大学一阶逻辑中特有的推理规则一阶逻辑中特有的推理规则(续续)2.全称量词引入规则（全称量词引入规则（UG规则）规则）：A(y)x A(x)成立的条件是：成立的条件是：(1).y在在A(y)中自由出现；中自由出现；(2).替换替换y的的x要选择在要选择在A(y)中不出现中不出现的变元符号；的变元符号；西华大学一阶逻辑中特有的推理规则一阶逻辑中特有的推理规则(续续)3.存在量词引入

8、规则（存在量词引入规则（EG规则）规则）：A(c)x A(x)成立的条件是：成立的条件是：(1).c在是在是特定的个体常项特定的个体常项；(2).替替换换c的的x要要选选择择在在A(c)中中不不出出现现的变元符号；的变元符号；西华大学举例：存在量词引入规则举例：存在量词引入规则指出下列推导中的错误，并加以改正：指出下列推导中的错误，并加以改正：A(1).P(a)Q(b)/前提前提 (2).(x)(P(x)Q(x)/存在量词引入规则存在量词引入规则前前提提中中的的个个体体a和和b不不同同，不不能能一一次次同同时时使使用用存存在在量词引入规则，正确的推理可以为：量词引入规则，正确的推理可以为：(1

9、).P(a)Q(b)/前提前提(2).x(P(x)Q(b)/存在量词引入规则存在量词引入规则(3).y x(P(x)Q(y)/存在量词引入规则存在量词引入规则西华大学举例：存在量词引入规则举例：存在量词引入规则指出下列推导中的错误，并加以改正：指出下列推导中的错误，并加以改正：B(1).P(x)Q(c)/前提前提 (2).x(P(x)Q(x)/存在量词引入规则存在量词引入规则在使用存在量词引入规则时，替换个体在使用存在量词引入规则时，替换个体c的变元应选择的变元应选择在公式中没有出现的变元符号，正确的推理是：在公式中没有出现的变元符号，正确的推理是：(1).P(x)Q(c)/前提前提(2).y

10、(P(x)Q(y)/存在量词引入规则存在量词引入规则西华大学一阶逻辑中特有的推理规则一阶逻辑中特有的推理规则(续续)4.存在量词消除规则（存在量词消除规则（EI规则）规则）x A(x)A(c)成立的条件是：成立的条件是：(1).c是是特特定定的的个个体体常常项项，是是使使得得A(c)为为真真的的个个体体常常项项，c不不能能在在前前面面的的公公式式序序列列中中出出现；现；(2).c不在不在A(x)中出现；中出现；(3).A(x)中自由出现的个体变元只有中自由出现的个体变元只有x；西华大学举例：举例：存在量词消除规则存在量词消除规则指出下列推导中的错误，并加以改正：指出下列推导中的错误，并加以改正

11、：A(1).x P(x)/前提前提(2).P(c)/存在量词消除规则存在量词消除规则(3).x Q(x)/前提前提(4).Q(c)/存在量词消除规则存在量词消除规则 A解解：第第二二次次使使用用存存在在量量词词消消除除规规则则时时，所所指指定定的的特特定定个个体体应应该该在在证证明明序序列列以以前前的的公公式式中中不不出出现现，正正确确的的推推理是：理是：(1).x P(x)/前提前提(2).P(c)/存在量词消除规则存在量词消除规则(3).x Q(x)/前提前提(4).Q(d)/存在量词消除规则存在量词消除规则西华大学举例：举例：指出下列推导中的错误，并加以改正：指出下列推导中的错误，并加以

12、改正：(1).x y(x y)/前提前提(2).y(z y)/全称量词消除规则全称量词消除规则(3).(z c)/存在量词消除规则存在量词消除规则(4).x(x c)/全称量词引入规则全称量词引入规则(5).c c/全称量词消除规则全称量词消除规则由由(2)得到得到(3)不能使用存在量词消除规不能使用存在量词消除规则，因为则，因为(2)中含有除中含有除y以外的自由变元以外的自由变元z。西华大学推理举例推理举例1每一个大学生不是文科生就是理科生；有的大学生是优每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生。因此，如果小张是等生；小张不是文科生但他是优等生。因此，

13、如果小张是大学生，他就是理科生。大学生，他就是理科生。个体域取全总域，要引入的谓词包括：个体域取全总域，要引入的谓词包括：P(x):x 是一个大学生；是一个大学生；Q(x):x是文科生；是文科生；S(x):x 是理科生；是理科生；T(x):x 是优等生。是优等生。要引入的个体常项是：要引入的个体常项是：c:小张。小张。前提：前提：x(P(x)(Q(x)S(x)、x(P(x)T(x)、Q(c)T(c)结论：结论：P(c)S(c)，西华大学推理举例推理举例(续续)前提：前提：x(P(x)(Q(x)S(x)、x(P(x)T(x)、Q(c)T(c)结论：结论：P(c)S(c)，证明证明:(1).x(P

14、(x)(Q(x)S(x)P规则规则 (2).P(c)(Q(c)S(c)全全称称量量词词消消除除规规则则 (3).P(c)CP规则规则 (4).Q(c)S(c)(2)(3)I(5).Q(c)T(c)P规则规则(6).Q(c)(5)I(7).S(c)(4)和和(6)I西华大学推理举例推理举例2 每个旅客或者坐头等舱或者坐二等舱；每个旅客每个旅客或者坐头等舱或者坐二等舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等舱。所有的旅客都富裕。因此，有些旅客坐二等舱。解：解：P(x):x是旅客；是旅客；Q(x):x坐头

15、等舱；坐头等舱；R(x):x坐二等舱；坐二等舱；S(x):x是富裕的。是富裕的。前提：前提：x(P(x)(Q(x)R(x)、x(P(x)(Q(x)S(x)、x(P(x)S(x)、(x(P(x)S(x)结论：结论：x(P(x)R(x)西华大学前提：前提：x(P(x)(Q(x)R(x)、x(P(x)(Q(x)S(x)、x(P(x)S(x)、(x(P(x)S(x)结论：结论：x(P(x)R(x)证明证明:(1).(x(P(x)S(x)P规则规则(2).x(P(x)S(x)(1)E(3).P(c)S(c)全称量词消除规则全称量词消除规则(4).P(c)(3)I(5).S(c)(3)I(6).x(P(x)(Q(x)R(x)P规则规则(7).P(c)(Q(c)R(c)(6)全全称称量量词词消消除除规规则则，使使用用(3)中中个个体体c(8).Q(c)R(c)(4)(7)I(9).x(P(x)(Q(x)S(x)P规则规则(10).P(c)(Q(c)S(c)全称量词消除规则，使用全称量词消除规则，使用(3)中个体中个体c(11).Q(c)S(c)(4)(11)I(12).Q(c)S(c)(11)I(13).Q(c)(12)(5)I(14).R(c)(13)(8)I(15).P(c)R(c)(4)和和(14)的合取的合取(16).x(P(x)R(x)(15)存在量词的引入存在量词的引入