工科离散数学课件 第二章 2_5_谓词逻辑的推理理论(1) - 定律与规则.pptx

2.5 谓词演算的推理理论谓词逻辑的形式推理以命题逻辑为基础，但命题包括谓词填式和量化命题两类，通常需要在二者之间转换。 2.5.1 推理定律2.5 谓词演算的推理理论-推理定律序号等价或蕴含关系含义E27E28┐?xA(x) ? ?x┐A(x)┐?xA(x) ? ?x┐A(x)量词否定等值式E29E30?x(A(x)∧B(x)) ? ?xA(x)∧?xB(x)?x(A(x)∨B(x)) ? ?xA(x)∨?xB(x)量词分配等值式（量词分配律）E31E32E33E34E35E36?x(A(x)∨B) ? ?xA(x)∨B?x(A(x)∧B) ? ?xA(x)∧B?x(A(x)∨B) ? ?xA(x)∨B?x(A(x)∧B) ? ?xA(x)∧B?x(B∨A(x)) ? B∨?xA(x)?x(B∧A(x)) ? B∧?xA(x)量词作用域的扩张与收缩 2.5 谓词演算的推理理论-推理定律E37E38E39E40E41E42E43?x(B∨A(x)) ? B∨?xA(x)?x(B∧A(x)) ? B∧?xA(x)?x(A(x)?B(x)) ? ?xA(x)??xB(x)?x(A(x)?B) ? ?xA(x)?B?xA(x)?B? ?x(A(x)?B)A??xB(x) ? ?x(A?B(x))A??xB(x) ? ?x(A?B(x))量词作用域的扩张与收缩I22I23?xA(x)∨?xB(x) ??x(A(x)∨B(x))?x(A(x)∧B(x)) ??xA(x)∧?xB(x)I24?xA(x)??xB(x) ??x(A(x)?B(x))（续） 2.5.2 量词的消除与产生规则2.5 谓词演算的推理理论-量词的消除与产生规则问：为什么还需引入新的推理规则呢？观察：(a) ?xM(x)→?xD(x), ?xM(x) ? ?xD(x) ——全量化命题(b) M(s)→D(s), M(s) ? D(s) ——全谓词填式命题(c) ?x(M(x)→D(x)), M(s) ? D(s) ——量化命题、谓词填式混合结论：现有定律不能满足谓词逻辑的推理要求。——命题逻辑中只有一种命题，但谓词逻辑中有2种：量词量化的命题和谓词填式。要引入新规则完成两类命题之间的转换。——仅用一种命题论证的情况十分罕见，也失去了谓词逻辑本身的意义。 2.5 谓词演算的推理理论-量词的消除与产生规则(1) 全称指定（全称消除/全称实例化）规则(US、?-、UI)示例：已知前提?x(P(x)→Q(y))。可实例化为： P(a)→Q(y),不可实例化为：P(y)→Q(y)。∵ ?xA(x)∴ A(a) 若?xA(x)为1，则A(a)为1，即 其中的a为论域中的任意一个个体，不能与A中的其他个体名重复。——量化命题→谓词填式 2.5 谓词演算的推理理论-量词的消除与产生规则(2) 全称推广（全称产生）规则(UG、?+)示例：已知前提P(a)→Q(y)。可推广为： ?x(P(x)→Q(y)) ，不能推广为：?y(P(y)→Q(y)) 。∵ A(a)∴ ?xA(x) 若A(a)为1，则?xA(x)为1，即 其中的a为论域中的任意一个个体；x不能与A中的其他个体名重复。——谓词填式→量化命题 2.5 谓词演算的推理理论-量词的消除与产生规则(3) 存在指定（存在消除/存在实例化）规则(ES、? -、EI)例2-26：对?xP(x)，?x(P(x)∧Q(y))?Q(s)的论证： (1) ?xP(x) P (2) P(u) ?-(1) (3) ?x(P(x)∧Q(y)) P (4) P(v)∧Q(y) ?-(2)∵ ?xA(x)∴ A(s) 若?xA(x)为1，则A(s)为1，即其中的s为论域中的特殊个体，不能与A中的其他个体名重复。——步骤(2)用u实例化存在量词，必须与y、s都不相同。步骤(4)用v实例化存在量词，必须与u、y和s都不相同。——量化命题→谓词填式 2.5 谓词演算的推理理论-量词的消除与产生规则(4) 存在推