上学期课件ch3章节

《上学期课件ch3章节》由会员分享，可在线阅读，更多相关《上学期课件ch3章节（45页珍藏版）》请在金锄头文库上搜索。

1、1,第三章 命题逻辑的推理理论,推理的形式结构 推理的正确与错误 推理的形式结构 判断推理正确的方法 推理定律 自然推理系统P 形式系统的定义与分类 自然推理系统P 在P中构造证明:直接证明法、附加前提证明法、归谬法,2,3.1 推理的形式结构,定义3.1 设A1, A2, , Ak, B为命题公式. 若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，则称由前提A1, A2, , Ak推出结论B的推理是有效的或正确的, 并称B是有效结论.,3,实例,判断下列推理是否正确： q, p q p,q, p q p,方法1：假定q (p q) 为1, 则q 为1, 且(p q)

2、为1。 由于 q 为 0, (p q) 为1，则必须 p 为 0, 故 p为1。 方法2：假定p 为 0, 则 p 为1. 若 q 为0, 则 pq 为 0, q (p q) 为 0. 若 q 为1, 则 q 为 0, q (p q) 为0.,4,实例,判断下列推理是否正确： p q, q p,q, p q p,5,推理的形式结构,定理3.1 由命题公式A1, A2, , Ak 推B的推理正确当且仅当A1A2AkB为重言式。 推理的形式结构2： A1A2AkB 若推理正确, 记为A1 A2 Ak B 也可以采用下述形式 前提： A1, A2, , Ak 结论： B 注意：推理正确不能保证结论一

3、定正确。,6,判断推理是否正确的方法,真值表法 等值演算法 主析取范式法,7,真值表法,从真值表上找出 A1, A2, , Ak真值均为 1的行，对每一个这样的行，若 B 的真值也为 1,则 A1 A2 Ak B成立。 或者看 B为0的行,在每个这样的行中，A1, A2, , Ak真值中至少有一个为 0， 则 A1 A2 Ak B成立。,8,推理实例,考察 B 是否是下列前提 A1, A2 的有效结论？ A1: p q A2 : p B: q A1: p q A2 : p B: q A1: p q A2 : q B: p,是,否,否,9,推理实例,例1 判断下面推理是否正确 (1)若今天是1号

4、，则明天是5号. 今天是1号. 所以, 明天是5号. (2)若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号.,10,推理实例,(1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. 解：设 p：今天是1号，q：明天是5号. (1) 推理的形式结构:(pq)pq 用等值演算法 (pq)pq (pq)p)q (pq)p)q pqq 1 由定理3.1可知推理正确,11,推理实例,(2) 若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号. 推理的形式结构:(pq)qp 用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (

5、pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确,12,推理定律重言蕴涵式,1. A (AB) 附加律 2. (AB) A 化简律 3. (AB)A B 假言推理 4. (AB)B A 拒取式 5. (AB)B A 析取三段论 6. (AB)(BC) (AC) 假言三段论 7. (AB)(BC) (AC) 等价三段论,13,推理定律重言蕴涵式,8. (AB)(CD)(AC) (BD) 构造性二难 (AB)(AB) B 构造性二难(特殊形式) (AB)(CD)( BD) (AC) 破坏性二难 10. 每个等值式可产生两个推理定律.,14,实例,判断下面推理是否正确

6、现在气温在零度以下。所以现在气温在零度以下或者正在下雨。 现在气温在零度以下并且正在下雨。以现在气温在零度以下。 现在气温在零度以下或者正在下雨。现在气温不在零度以下。所以现在正在下雨。,A (AB) 附加律,(AB) A 化简律,(AB)B A 析取三段论,15,实例,现在气温在零度以下或者正在下雨。所以现在正在下雨。 若今天下雨，则我们今天将不野餐。若我们今天不野餐，则我们明天将野餐。因此，若今天下雨，则我们明天将野餐。,(AB)(BC) (AC) 假言三段论,推理错误,16,3.2 自然推理系统P,定义3.2 一个形式系统 I 包括下面四个部分： (1) 非空的字母表，记作 A(I).

7、(2) A(I) 中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集,记作 AX(I). (4) 推理规则集，记作 R(I). 记I=, 其中是 I 的形式语言系统.,17,自然推理系统P,自然推理系统: 无公理, 即AX(I)=. 公理推理系统: 推出的结论是系统中的重言式, 称作定理.,18,自然推理系统P,定义3.3 自然推理系统 P 定义如下: 1. 字母表 (1) 命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：, , , , (3) 括号与逗号：(, ), ， 2. 合式公式（同定义1.6） 3. 推理规则 (1

8、) 前提引入规则 (2) 结论引入规则 (3) 置换规则,19,推理规则,(4) 假言推理规则 (6) 化简规则 (8) 假言三段论规则,(5) 附加规则 (7) 拒取式规则 (9) 析取三段论规则,AB B A,20,推理规则,(10) 构造性二难规则 (11) 破坏性二难规则 (12) 合取引入规则,21,在自然推理系统P中构造证明,设前提A1, A2, Ak,结论B及公式序列C1, C2, Cl. 如果每一个Ci(1il)是某个Aj, 或者可由序列中前面的公式应用推理规则得到, 并且Cl =B, 则称这个公式序列是由A1, A2, Ak推出B的证明. 可以证明，存在由A1, A2, Ak

9、推出B的证明的充要条件是B是A1, A2, Ak的有效结论，即A1 A2 Ak B.,22,说明证明的合理性,引理1: 设A, C1, C2是公式. 如果A C1, A C2, 则A C1 C2. 引理2：如果A B， B C，则A C. 定理: 设A是公式集合，B是一个公式。于是，从A证明出B的充要条件是B是A的有效结论。,23,说明证明的合理性,证明：必要性，设存在从A推出B的证明，令C1，Ck=B是这个证明序列。 对任意 Ci (i=1，k)，往证Ci 是A的有效结论。 对i用归纳法: (1) 当i =1时，因C1A，显然, C1 C1 是恒真公式，故AC1，即 C1是A的有效结论。 (

10、2) 设in时，命题成立。 (3) 当i=n时，若 CnA，则ACn，归纳法完成,24,说明证明的合理性,若Cn是某些Cj (jn)的有效结论，不妨设 (Cj1 Cjh ) Cn (1) 其中j1，jh都小于n。 由归纳假设知，A Cjm ，m=1，h。 由引理1知： A ( Cji Cjh ) (2) 根据(1)，(2)式及引理2，得 A Cn 即Cn是A的有效结论，归纳完成。,25,说明证明的合理性,充分性，若B是A的有效结论，则存在如下的序列： C1，Ck，B 其中 C1，Ck 是A中所有公式，且 C1 CkB， 这个序列就是由A到B的证明。 证毕。,26,实例,例2 构造下面推理的证明

11、： 若明天是星期一或星期三，我明天就有课. 若我明天有课，今天必备课. 我今天没备课. 所以，明天不是星期一、也不是星期三. 解 (1) 设命题并符号化 设 p：明天是星期一，q：明天是星期三， r：我明天有课，s：我今天备课,27,直接证明法,(2) 写出证明的形式结构 前提：(pq)r, rs, s 结论：pq (3) 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换,28,附加前提证明法,附加前提证明法 适用于结论为蕴涵式 欲证 前提：A1, A2, , Ak 结论：CB 等价地证明 前提：A1, A2, , Ak, C 结论：B 理由：

12、(A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,29,附加前提证明法实例,例3 构造下面推理的证明 2是素数或合数. 若2是素数，则是无理数. 若是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明 (1) 设 p：2是素数，q：2是合数， r： 是无理数，s：4是素数 (2) 推理的形式结构 前提：pq, pr, rs 结论：sq,30,附加前提证明法实例,(3) 证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论 sq CP规则,31,归

13、谬法（反证法）,归谬法 (反证法) 欲证 前提：A1, A2, , Ak 结论：B 做法 在前提中加入B，推出矛盾. 理由: A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB0,32,归谬法实例,例4 前提：(pq)r, rs, s, p 结论：q 证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论,33,归谬法实例, pq 置换 p 析取三段论 p 前提引入 pp 合取,34,第三章 习题课,主要内容 推理的形式结构 判断推理是否正确的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系统P 构造推理证明的方法 直接证明法 附加前提证明法 归谬法(反证法),35,基本要求,理解并记住推理形式结构的两种形式： 1. (A1A2Ak)B 2. 前提：A1, A2, , Ak 结论：B 熟练掌握判断推理是否正确的不同方法（如真值表法、等值演