离散数学第二章-命题演算的推理理论-命题演算的公理系统.ppt

目录（数理逻辑） 第一章 命题演算基础 （6学时） 第二章 命题演算的推理理论（4学时） 第三章 谓词演算基础（5学时） 第四章 谓词演算的推理理论（5学时） 第五章 递归函数论（4学时） 第二章 命题演算的推理理论 例 判断下面各推理是否正确: (1) 如果天气凉快,小王就不去游泳。 天气凉快, 所以小王没去游泳。 (2) 如果天气凉快,小王就不去游泳。 天气不凉快, 所以小王去游泳了。 推理是否正确： 形式化 引入符号： P表示天气凉快， Q表示小王去游泳 (1)如果天气凉快,小王就不去游泳。天气凉快, 所以小王没去游泳。 (PQ)P)Q (2)如果天气凉快,小王就不去游泳。天气不凉 快, 所以小王去游泳了。 (PQ)P)Q 推理是否正确? 考察主析取范式 (PQ)P)Q = (PQ)P)Q =(PQ)PQ =(P Q) P Q =(P Q) P Q =(P Q) ( P (QQ) (Q (PP) =(P Q) ( P Q)( P Q) (Q P) = m0m2m3m1 永真公式 推理是否正确? 考察主析取范式 (PQ) P) Q = (PQ) P) Q =(PQ)PQ =(P Q) P Q =(P Q) P Q =(P Q) (P(QQ) ( Q (PP) =(P Q) (PQ) ( Q P) = m0m1m2 非永真公式 推理是否正确：真值表 P Q (PQ)P)Q (PQ)P)Q T T T T T F T T F T T F F F T T (PQ)P)Q为永真公式 而(PQ)P)Q不是永真的。 三段 论 三段论 可用三段论表示(PQ)P)Q 如下： P Q 大前提 P 小前提 Q 结 论 例 如果今天下雨，则运动会将推迟举行； 今天下雨； 运动会将推迟举行。 逻辑推理 由前提推出结论 （前提与结论都是命题，可真可假） 演绎推理 归纳推理 归纳推理 从真的前提出发，得到的结论只能够要求它与 前提是协调的，但不一定是真的。 它基于对特殊的代表的有限观察， 或基于对反 复再现的现象的模式的有限观察，用公式表达 规律。 所有观察到的乌鸦都是黑的。 所以所有乌鸦都是黑的。 演绎推理 可推导性当前提的真蕴涵结论的真时，称前提和 结论之间有可推导性关系，即前提和结 论之间的推理是正确的。 演绎推理前提和结论之间有可推导性关系的这种 推理。 前提和结论间的形式关系(而不考虑内容) 如果 1+1=3，则雪是黑的。 1+1=3。 雪是黑的。 该推理过程正确, 但不意味着前提 与结论正确 第二章 命题演算的推理理论 2.1 命题演算的公理系统 2.1.1 公理系统的组成部分 2.1.2 公理系统的推理过程 2.2 命题演算的假设推理系统 2.3 命题演算的归结推理法 21 命题演算的公理系统 l 给出若干条永真公式(称为公理)， l 再给出若干条由永真公式推出永真公式 的推理规则， 由它们出发推出一切永真公式的系统。 了解公理系统的构成规则和推理形式， 培养读者构造公理系统及利用该公理系统进 行推理的能力。 211 公理系统的组成部分 一、语法部分 基本符号 公理系统所允许出现的全体符号的集合 公理 规则 二、语义部分 基本符号 u 命题变元 P，Q，R，等字母表示命题变元 u 联结词 、是联结词 u 括号 (，)是括号 u 合式公式 (1) 任何命题变元均是公式； (2) 如果P为公式，则 P为公式； (3) 如果为P，Q为公式，则 PQ，PQ，PQ，PQ为公式； (4) 当且仅当经过有限次使用(1),(2),(3) 所组成的符号串才是公式。 u 推出符 表示其后的公式为永真公式 (教材中遗漏 ) 公理 公理1 PP 公理2 (P(QR)(Q(PR) 公理3 (PQ)(QR)(PR) 公理4 (P(PQ)(PQ) 公理5 (PQ)(PQ) 公理6 (PQ)(QP) 公理7 (PQ)(QP)(PQ) 调头 传递 凝缩 与有关 公理 公理8 (PQ)P 公理9 (PQ)Q 公理10 P(Q(PQ) 公理11 P(PQ) 公理12 Q(PQ) 公理13 (PR)(QR)(PQ)R) 公理14 (PQ)(QP) 公理15 PP 与有关 与有关 与有关 常用推理定律(详见耿素云离散数学) P(PQ) 附加 (PQ)P 化简 (PQ)P)Q 假言推理 (PQ)Q)P 拒取式 (AB)A) B 析取三段论 (AB)(BC) (AC) 假言三段论 (AB)(BC) (AC) 等价三段论 (AB)(CD)(AC)(BD) 构造性二难 常用推理定律(详见方世昌的离散数学) P(PQ) 加法式 (PQ)P 简化式 (PQ)P)Q 假言推理 (PQ)Q)P 拒取式 (AB)A) B 析取三段论 (AB)(BC) (AC) (假言)前提三段论 (AB)(CD)(AC)(BD) 构造性二难 (AB)(CD)(BD)(AC) 破坏性二难 规则 (1)代入规则：将公式中出现的某一符号 B 每处均代以某一公式C， 所到的公式D 称为C 对 的 代入。 (2)分离规则：如果AB且A，则B。 二、语义部分 (1) 公理是永真公式。 (2) 规则规定如何从永真公式推出永真公式。分离规 则指明，如果AB永真且A永真，则B也为永真公 式。 (3) 代入规则指明如果为永真公式，则某一个公式 正确代入公式后所得的公式也为永真公式。 (4) 定理为永真公式，它们是从公理出发利用分离规 则和代入规则推出来的公式。 第二章 命题演算的推理理论 2.1 命题演算的公理系统 2.1.1 公理系统的组成部分 2.1.2 公理系统的推理过程 2.2 命题演算的假设推理系统 2.3 命题演算的归结推理法 定理1(p18) PP 证明： (1) (PQ)(QP) 公理14 (2) (PP)(PP) P用P，Q用P代入 (3) PP 公理1 (4) PP P用P代入 (5) PP (2)(4)分离 P=P 例 (PP) P 证明： (1) (PR) (QR) (PQ) R) 公理13 (2) (PP) (PP) (PP) P) (1)式中Q用P、R用P代入 (3) PP 公理1 (4) (PP) (PP) P) (2)(3)分离 (5) (PP) P (3)(4)分离 例 P(PP) 证明 (1) (PR) (QR) (PQ) R) 公理13 (2) (PP) (PP) (PP) P) (1)式中Q用P、R用P代入 (3) PP 公理1 (4) (PP) (PP) P) (2)(3)分离 (5) (PP) P (3)(4)分离 (6) P(PQ) 公理11 (7) P(PP) (6)式中Q用P代入 (8) (PQ)(QP)(PQ) 公理7 (9) (P(PP)(PP)P)(P(PP) (8)式中Q用PP代入 (10) (PP)P)(P(PP) (7)(9)分离 (11) P(PP) (5)(10)分离 定理2(p18) (PQ)(RP)(RQ) 分析：由传递公理3知道 (RP)(PQ)(RQ) 与要求证的公式的联系是两个前件次序换 一换，就可以用调头公理2： (P(QR)(Q(PR) 加头公式 定理2(p18) (PQ)(RP)(RQ) 证明： (1) (PQ)(QR)(PR) 公理3 (2) (RP)(PQ)(RQ) P用R，Q用P，R用Q代入 (3) (P(QR)(Q(PR) 公理2 (4) (RP)(PQ)(RQ) (PQ)(RP)(RQ) P用RP，Q用PQ，R用RQ代入 (5) (PQ)(RP)(RQ) (4)(2)分离 定理3 (p18,拒取式) (PQ)(QP) 分析：由公理14，(PQ)(QP)， 可以得到 (PQ)(QP) 下面就是要建立(PQ)与(PQ)之间的联系。 如果 (PQ) (PQ)， 则由传递性知道结论成立。 下面先证明(PQ) (PQ)。 证明：先证 (PQ) (PQ) (1)PP 定理1 (2)QQ P用Q代入 (3)(PQ)(QP) 公理14 (4)(PQ)(QP) Q用Q代入 (5)(PQ)(RP)(RQ) 加头定理2 (6)(QQ)(PQ)(PQ) (5)式中P用Q代入，Q用Q代入，R用P代入 (7)(PQ)(PQ) (6)(2)分离 定理3 (p18,拒取式) (PQ)(QP) 证明： (1)PP 定理1 (2)QQ P用Q代入 (3)(PQ)(QP) 公理14 (4)(PQ)(QP) Q用Q代入 (5)(PQ)(RP)(RQ) 定理2 (6)(QQ)(PQ)(PQ) (5)式中P用Q代入，Q用Q代入，R用P代入 (7)(PQ)(PQ) (6)(2)分离 (8)(PQ)(QR)(PR) 公理3 (9)(PQ)(PQ) (PQ)(QP)(PQ)(QP) (8)式中P用PQ，Q用PQ，R用QP代入 (10)(PQ)(QP)(PQ)(QP) (9)(7)分离 (11)(PQ)(QP) (10)(4)分离 例 （同定理3） 已知公理 A: PP B: (PQ) (QP) C: (PQ) (RP) (RQ) D: (PQ) (QR) (PR) 要证 (PQ) (QP)为本系统中的定理。 公理推理证明定理的方法 对于简单题，可以把待证明的公式变成永 真蕴涵式的后件，再证明前件永真。 引理 P(PQ)Q) 证明： (1) (P(QR)(Q(PR) 公理2 (2) (PQ)(PQ) (P(PQ)Q) Q用P代入，R用Q代入，P用P Q代入 (3) PP 公理1 (4) (PQ)(PQ) 代入 (5) P(PQ)Q) 分离(2)(4) 例1(p18) 已知引理，试证明(PP) P (1) P(PQ)Q) 定理 (2) P(PP)P) Q用P代入 (3) (PQ)(QP) 公理14 (4) (PP)P)(P(PP) P用PP代入，Q用P代入 (5) (PQ)(RP)(RQ) 定理2 (6) (PP)P)(P(PP) (P(PP)P)(P(P(PP) P用(PP)P，Q用P(PP)，R用P代入 (7) (P(PP)P)(P(P(PP) (6)(4)分离 (8) P(P(PP) (7)(2)分离 (9) (P(PQ)(PQ) 公理4 (10) (P(P(PP)(P(PP) Q用(PP)代入 (11) (P(PP) (10)(8)分离 (12) (P(PP)(PP) P) (3)式中Q用PP代入 (13) (PP) P (12)(11)分离 例2(p19) 已知公理： A P(Q P) B (P(Q R)(PQ)(PR) C (P(QR)(Q(PR) D P(PQ) E (PQ)(QP) 及分离规则和代入规则 证明公式(RR)(PP)为定理。 PP ？ 例2的分析 先要证明 PP 如果用公理A： P（QP），得到 P（PP）， 难以继续。 证明: 先证 PP (1) P(Q P) 公理A (2) (P(Q R)(PQ)(PR) 公理B (3) (P(Q P)(PQ)(PP) R用P代入(2) (4) (PQ)(PP) (3)(1)分离 (5) (P(Q P)(PP) Q用Q P代入(4) (6) PP (5)(1)分离 例2的证明(p19) (1) P(Q P) 公理A (2) (P(Q R)(PQ)(PR) 公理B (3) (P(Q P)(PQ)(PP) R用P代入(2) (4) (PQ)(PP) (3)(1)分离 (5) (P(Q P)(PP) Q用Q P代入(4) (6) PP (5)(1)分离 (7) P(PQ) 公理D (8) (PP)(PP )(RR) P用PP，Q用RR代入(7) (9) (PP )(RR) (8)(6)分离 (10) (PQ)(QP) 公理E (11) (PP )(RR)(RR)(PP ) P用PP，Q用RR代入(10) (12) (RR)(PP ) (11)(9)分离 已知公理 A: (pq) (qp) (pq) B: ppq C: pp D: (pr) (qr) (pq) r) E: pqp 证明定理: p(pp) 同 前 例 ! 例3 (1) ppq 公理B (2) ppp 代入 (3) (pr) (qr) (pq) r) 公理D (4) (pp) (pp) (pp) p) 代入 (5) p p 公理C (6) (pp) (pp) p) (4)(5)分离 (7) (pp) p (5)(6)分离 证明：先证 (pp) p (1) ppq 公理B (2) ppp 代入 (3) (pr) (qr) (pq) r) 公理D (4) (pp) (pp) (pp) p) 代入 (5) p p 公理C (6) (pp) (pp) p) (4)(5)分离 (7) (pp) p (5)(6)分离 (8) (pq) (qp) (pq) 公理A (9) (p(pp) (pp)p) (p(pp) 代入 (10) (pp)p) (p(pp) (2)(9)分离 (11) (p(pp) (7)(10)分离 例3的证明 例4 已知公理 A： (QR)(PQ)(PR) B： (P(QR)(Q(PR) C： (PQ)(QR) (PR) D