离散数学谓词逻辑推理

《离散数学谓词逻辑推理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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的推理正确，则记为(A1A2…Ak)B。推理规则在证明中常用的推理规则有：[1].前提引入规则P：在证明的任何步骤都可以引入已知的前提；[2].结论引入规则：在证明的任何步骤都可以引入这次已经得到的结论作为

2、后续证明的前提；[3].置换规则E：在证明的任何步骤上，一阶公式中的任何子公式都可用与之等值的公式置换，得到证明的公式序列的另一公式。以及CP规则、..和..的合取、永真蕴涵I等。使用一阶逻辑公式进行推理还有其他一些推理规则，这些规则建立在下面一些推理定律上。一阶逻辑的永真蕴涵式推理定律是一阶逻辑的一些永真蕴涵式，重要的推理定律有：[1].附加律：A(AB)//或称为析取的引入[2].化简律：(AB)A,(AB)B//或称为合取的消除[3].假言推理：(AB)AB//或称为分离规则[4].拒取式：(AB)BA[5].析取三段论：(AB)

3、BA[6].假言三段论：(AB)(BC)(AC)//或称为传递规则一阶逻辑的永真蕴涵式(续)[7].等价三段论：(AB)(BC)(AC)[8].构造性二难：(AB)(CD)(AC)(BD)一阶逻辑中特有的推理定律[1].x(A(x)B(x))(xA(x))(xB(x))[2].x(A(x)∧B(x))(xA(x))∧(xB(x))[3].x(A(x)B(x))(xA(x))(xB(x))[4].x(A(x)B(x))(xA(x))(xB(x))一阶逻辑中特有的推理规则[1].全称量词

4、消除规则（UI规则）：(i).xA(x)A(y)(ii).xA(x)A(c)成立的条件是：(1).x是A(x)的自由变元；(2).在(i)中，y为不在A(x)中约束出现的变元，y可以在A(x)中自由出现，也可在证明序列中前面的公式中出现。(3).在(ii)中，c是任意的个体常项，可以是证明序列中前面公式所指定的个体常项。举例：全称量词消除规则指出下列推导中的错误，并加以改正：A(1).(x)(P(x)Q(x))//前提(2).P(a)Q(b)//全称量词消除规则解：在使用量词消除规则时，应使用个体替换量词所约束的变元在公式中的所有出现，正确的推理是：(

5、1).(x)(P(x)Q(x))//前提(2).P(a)Q(a)//全称量词消除规则举例：全称量词消除规则指出下列推导中的错误，并加以改正：B(1).xP(x)Q(x)//前提(2).P(y)Q(y)//全称量词消除规则量词x的辖域为P(x)，而非P(x)Q(x)，所以不能直接使用全称量词消除规则。一阶逻辑中特有的推理规则(续)[2].全称量词引入规则（UG规则）：A(y)xA(x)成立的条件是：(1).y在A(y)中自由出现；(2).替换y的x要选择在A(y)中不出现的变元符号；一阶逻辑中特有的推理规则(续)[3].存在量词引入规则（EG规则）

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

7、(c)//前提(2).x(P(x)Q(x))//存在量词引入规则在使用存在量词引入规则时，替换个体c的变元应选择在公式中没有出现的变元符号，正确的推理是：(1).P(x)Q(c)//前提(2).y(P(x)Q(y))//存在量词引入规则一阶逻辑中特有的推理规则(续)[4].存在量词消除规则（EI规则）xA(x)A(c)成立的条件是：(1).c是特定的个体常项，是使得A(c)为真的个体常项，c不能在前面的公式序列中出现；(2).c不在A(x)中出现；(3).A(x)中自由出现的个体变元只有x；举例：存在量词消除规则指出下列推导中的错误，并加以改正：A