离散数学课件：第1章 命题逻辑4

1、11.7 推理理论推理理论 推理的形式结构推理的形式结构判断推理是否正确的方法判断推理是否正确的方法推理定律与推理规则推理定律与推理规则构造证明构造证明 直接证明法直接证明法, 附加前提证明法附加前提证明法, 归缪法归缪法 2推理的形式结构推理的形式结构问题的引入问题的引入 推理举例推理举例: (1) 正项级数收敛当且仅当部分和有上界正项级数收敛当且仅当部分和有上界. (2) 若若A C B D，则，则A B且且C D.推理推理 从前提出发推出结论的思维过程从前提出发推出结论的思维过程上面上面(1)是正确的推理，而是正确的推理，而(2)是错误的推理是错误的推理. 证明证明 描述描述推理正确推理

2、正确的过程的过程. 3推理的形式结构推理的形式结构 定义定义 若若(A1 A2 Ak ) B为重言式，则称：为重言式，则称：由前由前提提A1, A2, , Ak推出结论推出结论B的的推理正确推理正确（或者说，（或者说， B是是A1, A2, , Ak的的逻辑结论或有效结论逻辑结论或有效结论）。）。概念上可称概念上可称(A1 A2 Ak ) B 为由为由A1,A2, , Ak推出结论推出结论B的的推理的形式结构推理的形式结构。推理的形式结构推理的形式结构的另一常见表达为以下格式：的另一常见表达为以下格式： 前提：前提： A1, A2, , Ak 结论：结论： B 若推理正确，则记作：若推理正确，

3、则记作：A1 A2 AkB.4判断推理是否正确的方法判断推理是否正确的方法真值表法真值表法等值演算法等值演算法 判断判断推理是否正确推理是否正确主范式法主范式法构造构造证明法证明法 展现推理过程正确展现推理过程正确 说明：用前说明：用前3 3个方法时采用的个方法时采用的形式结构形式结构表述是表述是 “ A1 A2 AkB” . 用构造证明时用构造证明时, 采用的采用的形式结构形式结构表述表述前提前提: A1, A2, , Ak, 结论结论: B5实例实例例例 判断下面推理是否正确判断下面推理是否正确 (1) 若今天是若今天是1号，则明天是号，则明天是5号号. 今天是今天是1号号. 所所 以明天

4、是以明天是5号号. 解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号. 推理的形式结构为推理的形式结构为: (pq) pq证明（用等值演算法）证明（用等值演算法） (pq) pq ( p q) p) q pq q 1可知可知推理正确推理正确 6实例实例 (续续)(2) 若今天是若今天是1号，则明天是号，则明天是5号号. 明天是明天是5号号. 所以今天是所以今天是1号号. 解解 设设p：今天是：今天是1号，号，q：明天是：明天是5号号. 推理的形式结构为推理的形式结构为: (pq) qp 证明（化主析取范式）证明（化主析取范式） (pq) qp ( p q) qp ( p q)

5、q) p q p pq M1 m0 m2 m3 结果不含结果不含m1, 故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确. 7重言蕴涵式重言蕴涵式推理定律推理定律重要的推理定律重要的推理定律 A (A B) 附加律附加律 (A B) A 化简律化简律 (AB) A B 假言推理假言推理 (AB)B A 拒取式拒取式 (A B)B A 析取三段论析取三段论 (AB) (BC) (AC) 假言三段论假言三段论 (AB) (BC) (AC) 等价三段论等价三段论 (AB) (CD) (A C) (B D) 构造性二难构造性二难 8推理定律推理定律 (续续)(AB) ( AB) B 构造性

6、二难（特殊形式）构造性二难（特殊形式）(AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难构造证明构造证明就是：描述推理过程的命题公式就是：描述推理过程的命题公式序列序列，其中每个命题公式或是其中每个命题公式或是已知的前提已知的前提，或是由在其，或是由在其之前出现的命题公式应用推理规则之前出现的命题公式应用推理规则推出的结论推出的结论. .9推理规则推理规则(1) 前提引入规则前提引入规则(P)(2) 结论引入规则结论引入规则(3) 置换规则置换规则(等值等值)(4) 假言推理规则假言推理规则 AB A B(5) 附加规则附加规则 A A B (6) 化简规则化简规则 A B A

7、(7) 拒取式规则拒取式规则 AB B A(8) 假言三段论规则假言三段论规则 AB BC AC 10推理规则推理规则( (续续) ) (11) 破坏性二难推理破坏性二难推理规则规则 AB CD BD AC(12) 合取引入规则合取引入规则 A B A B (9) 析取三段论规则析取三段论规则 A B B A (10)构造性二难推理构造性二难推理规则规则 AB CD A C B D11构造证明（一）构造证明（一）直接证明法直接证明法例例 构造下面推理的证明：构造下面推理的证明： 若明天是星期二或星期五，我就有课若明天是星期二或星期五，我就有课. 若明天若明天有课，今天必备课有课，今天必备课.

8、我今天没备课我今天没备课. 所以所以， 明天不是星期二和星期五明天不是星期二和星期五. 解解 设设 p：明天是星期二，：明天是星期二，q：明天是星期五，：明天是星期五， r：我明天有课，：我明天有课，s：我今天备课：我今天备课推理的形式结构为推理的形式结构为 前提：前提：(p q)r, rs, s 结论：结论： pq 12直接证明法直接证明法 (续续)证明证明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q) 拒取式拒取式 pq 置换置换 13构造证明（二）构造证明（二）附加前提法附加前提法 例例 构造下面推理的证明构造下面推理的证明:

9、 2是素数或合数是素数或合数. 若若2是素数，则是素数，则 是无理数是无理数. 若若 是无理数，则是无理数，则4不是素数不是素数. 所以，如果所以，如果4是是 素数，则素数，则2是合数是合数. 解：设解：设 p：2是素数，是素数，q：2是合数，是合数， r： 是无理数，是无理数，s：4是素数是素数推理的形式结构推理的形式结构 前提：前提：p q, pr, rs 结论：结论：sq试证一下。试证一下。22214附加前提证明法附加前提证明法 (续续)欲证明欲证明 前提：前提：A1, A2, , Ak 结论：结论：CB等价于等价于证明证明 前提：前提：A1, A2, , Ak, C 结论：结论：B C

10、P规则规则理由：理由： (A1 A2 Ak) (CB) ( A1 A2 Ak) ( C B ) ( A1 A2 Ak C) B (A1 A2 Ak C) B15附加前提证明法附加前提证明法 (续续)证明证明 ： s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假言三段论假言三段论 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 sq CP16构造证明（三）构造证明（三）归谬法归谬法(反证法反证法) 欲证明欲证明 前提：前提：A1, A2, , Ak 结论：结论：B将将 B加入前提，若推出矛盾，则得证推理正确加入前提，若推出矛盾，则得证推

11、理正确.理由理由: A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB)可见：可见：(A1 A2 AkB)为重言式当且仅当为重言式当且仅当括号括号内部为矛盾式内部为矛盾式17归谬法归谬法 (续续)例例 构造下面推理的证明构造下面推理的证明 前提：前提： (p q) r, rs, s, p 结论：结论： q证明（用归缪法）证明（用归缪法） q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式18归谬法归谬法 (续续) (p q) r 前提引入前提引入 (p q) 析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 p p 合取合取 （这是矛盾式！这是矛盾式！）请用直接证明法证明之请用直接证明法证明之 19本章小结本章小结一一. 主范式与真值表的关系主范式与真值表的关系(主析取