《离散数学---谓词逻辑推理》由会员分享，可在线阅读，更多相关《离散数学---谓词逻辑推理（20页珍藏版）》请在金锄头文库上搜索。
1、西华大学第二章 谓词逻辑第3节 一阶逻辑推理理论西华大学推理的定义称蕴涵式(A1A2Ak)B为推理的形式结构，A1, A2, , Ak为推理的前提，B为推理的结论。若(A1A2Ak)B为永真式，则称从前提A1, A2, , Ak推出结论B的推理正确（或说有效），B是A1, A2, , Ak的逻辑结论或称有效结论，否则称推理不正确。若从前提A1, A2, , Ak推出结论B的推理正确，则记为(A1A2Ak)B。 西华大学推理规则在证明中常用的推理规则有： 1. 前提引入规则P：在证明的任何步骤都可以引 入已知的前提； 2. 结论引入规则：在证明的任何步骤都可以引 入这次已经得到的结论作为后续证明
2、的前提； 3. 置换规则E：在证明的任何步骤上，一阶公式 中的任何子公式都可用与之等值的公式置换，得到 证明的公式序列的另一公式。 以及CP规则、.和.的合取、永真蕴涵I等。使用一阶逻辑公式进行推理还有其他一些推理规 则，这些规则建立在下面一些推理定律上。西华大学一阶逻辑的永真蕴涵式推理定律是一阶逻辑的一些永真蕴涵式，重要 的推理定律有： 1. 附加律：A(AB) / 或称为析取的引入 2. 化简律： (AB)A, (AB)B/ 或称为合取的消除 3. 假言推理：(AB)AB/ 或称为分离规则 4. 拒取式：(AB)BA 5. 析取三段论：(AB)BA 6. 假言三段论：(AB)(BC)(AC
3、)/ 或称为传递规则西华大学一阶逻辑的永真蕴涵式(续)7. 等价三段论：(AB)(BC)(AC) 8. 构造性二难：(AB)(CD)(AC)(BD)西华大学一阶逻辑中特有的推理定律 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) 西华大学一阶逻辑中特有的推理规则 1. 全称量词消除规则（UI规则）：(i).x A(x) A(y)(ii).x A(x) A(c) 成立的条件是：(1).x是A(x)的自由变
4、元；(2).在(i)中，y为不在A(x)中约束出现的变元，y 可以在A(x)中自由出现，也可在证明序列中前面的公式 中出现。(3).在(ii)中，c是任意的个体常项，可以是证明 序列中前面公式所指定的个体常项。 西华大学举例：全称量词消除规则指出下列推导中的错误，并加以改正：A (1). (x)(P(x)Q(x)/ 前提(2). P(a)Q(b) / 全称量词消除规则解：在使用量词消除规则时，应使用个体替换量 词所约束的变元在公式中的所有出现，正确的推 理是：(1).(x)(P(x)Q(x)/ 前提(2).P(a)Q(a) / 全称量词消除规则西华大学举例：全称量词消除规则指出下列推导中的错误
5、，并加以改正：B (1).x 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. 存在量词引入规则（EG规则）： A(c) x A(x) 成立的条件是：(1). c在是特定的个体常项；(2). 替换c的x要选择在A(c)中不出现 的变元符号
6、；西华大学举例：存在量词引入规则指出下列推导中的错误，并加以改正： 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).yx(P(x)Q(y)/ 存在量词引入规则西华大学举例：存在量词引入规则指出下列推导中的错误，并加以改正： B (1).P(x)Q(c) / 前提(2). x (P(x)Q(x) / 存在量词引入规则在使用存在量词引入规则时，替换个体c的变元应选择在公式中没有出现的变元符
7、号，正确的推理是：(1).P(x)Q(c)/ 前提(2). y (P(x)Q(y)/ 存在量词引入规则西华大学一阶逻辑中特有的推理规则(续 ) 4. 存在量词消除规则（EI规则） x A(x) A(c) 成立的条件是：(1). c是特定的个体常项，是使得A(c)为 真的个体常项，c不能在前面的公式序列中出 现；(2). c不在A(x)中出现；(3). A(x)中自由出现的个体变元只有x；西华大学举例：存在量词消除规则 指出下列推导中的错误，并加以改正： A(1). x P(x)/ 前提 (2).P(c)/ 存在量词消除规则 (3).x Q(x)/ 前提 (4).Q(c) / 存在量词消除规则
8、A解：第二次使用存在量词消除规则时，所指定的特 定个体应该在证明序列以前的公式中不出现，正确的推 理是： (1).x P(x)/ 前提 (2).P(c) / 存在量词消除规则 (3).x Q(x)/ 前提 (4).Q(d)/ 存在量词消除规则西华大学举例：指出下列推导中的错误，并加以改正：(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每一个
9、大学生不是文科生就是理科生；有的大学生是优 等生；小张不是文科生但他是优等生。因此，如果小张是 大学生，他就是理科生。个体域取全总域，要引入的谓词包括： 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(x)(Q(x)S(x) P规则(2). P(c)(Q
10、(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坐头等舱；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
11、(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) 存在量词的引入
