离散数学ppt (3).ppt

1,主要内容 推理的形式结构 推理的正确与错误 推理的形式结构 判断推理正确的方法 推理定律 自然推理系统P 形式系统的定义与分类 自然推理系统P 在P中构造证明:直接证明法、附加前提证明法、归谬法,第三章 命题逻辑的推理理论,2,3.1 推理的形式结构,定义3.1 设A1, A2, …, Ak, B为命题公式. 若对于每组赋值， A1A2… Ak 为假，或当A1A2…Ak为真时，B也为真， 则称由前提A1, A2, …, Ak推出结论B的推理是有效的或正确 的, 并称B是有效结论.,定理3.1 由命题公式A1, A2, …, Ak 推B的推理正确当且仅当 A1A2…AkB为重言式注意: 推理正确不能保证结论一定正确,3,推理的形式结构,2. A1A2…AkB若推理正确, 记为A1  A2  …  Ak  B 3. 前提： A1, A2, … , Ak结论： B判断推理是否正确的方法:真值表法等值演算法主析取范式法,推理的形式结构 1. {A1, A2, …, Ak} B若推理正确, 记为{A1,A2,,An} B,4,推理实例,例1 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号.,解 设 p：今天是1号，q：明天是5号. (1) 推理的形式结构:,(pq)pq,用等值演算法(pq)pq ((pq)p)q pqq  1由定理3.1可知推理正确,5,推理实例,(2) 推理的形式结构:,(pq)qp,用主析取范式法(pq)qp (pq)qp  ((pq)q)p qp (pq)(pq) (pq)(pq)  m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确,6,推理定律——重言蕴涵式,1. A  (AB) 附加律 2. (AB)  A 化简律 3. (AB)A  B 假言推理 4. (AB)B  A 拒取式 5. (AB)B  A 析取三段论 6. (AB)(BC)  (AC) 假言三段论 7. (AB)(BC)  (AC) 等价三段论 8. (AB)(CD)(AC)  (BD) 构造性二难(AB)(AB)  B 构造性二难(特殊形式) 9. (AB)(CD)( BD)  (AC) 破坏性二难每个等值式可产生两个推理定律 如, 由AA可产生 AA 和 AA,7,3.2 自然推理系统P,定义3.2 一个形式系统 I 由下面四个部分组成：(1) 非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作 E(I).(3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I).(4) 推理规则集，记作 R(I). 记I=, 其中是 I 的 形式语言系统, 是 I 的形式演算系统.自然推理系统: 无公理, 即AX(I)= 公理推理系统 推出的结论是系统中的重言式, 称作定理,8,自然推理系统P,定义3.3 自然推理系统 P 定义如下: 1. 字母表(1) 命题变项符号：p, q, r, …, pi, qi, ri, …(2) 联结词符号：, , , , (3) 括号与逗号：(, ), ， 2. 合式公式（同定义1.6） 3. 推理规则(1) 前提引入规则(2) 结论引入规则(3) 置换规则,9,推理规则,(4) 假言推理规则(6) 化简规则(8) 假言三段论规则,(5) 附加规则(7) 拒取式规则(9) 析取三段论规则,10,推理规则,(10) 构造性二难推理规则 (11) 破坏性二难推理规则(12) 合取引入规则,11,在自然推理系统P中构造证明,设前提A1, A2,, Ak,结论B及公式序列C1, C2,, Cl. 如果每 一个Ci(1il)是某个Aj, 或者可由序列中前面的公式应用推理 规则得到, 并且Cl =B, 则称这个公式序列是由A1, A2,, Ak推 出B的证明例2 构造下面推理的证明：若明天是星期一或星期三，我明天就有课. 若我明天有课，今天必备课. 我今天没备课. 所以，明天不是星期一、也不是星期三. 解 (1) 设命题并符号化 设 p：明天是星期一，q：明天是星期三，r：我明天有课，s：我今天备课,12,直接证明法,(2) 写出证明的形式结构前提：(pq)r, rs, s结论：pq (3) 证明① rs 前提引入② s 前提引入③ r ①②拒取式④ (pq)r 前提引入⑤ (pq) ③④拒取式 ⑥ pq ⑤置换,13,附加前提证明法,附加前提证明法 适用于结论为蕴涵式 欲证前提：A1, A2, …, Ak结论：CB 等价地证明前提：A1, A2, …, Ak, C结论：B 理由：(A1A2…Ak)(CB) ( A1A2…Ak)(CB) ( A1A2…AkC)B (A1A2…AkC)B,14,附加前提证明法实例,例3 构造下面推理的证明2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明(1) 设 p：2是素数，q：2是合数，r： 是无理数，s：4是素数(2) 推理的形式结构前提：pq, pr, rs结论：sq,15,附加前提证明法实例,(3) 证明① s 附加前提引入② pr 前提引入③ rs 前提引入④ ps ②③假言三段论⑤ p ①④拒取式⑥ pq 前提引入⑦ q ⑤⑥析取三段论,16,归谬法（反证法）,归谬法 (反证法) 欲证前提：A1, A2, … , Ak 结论：B 做法在前提中加入B，推出矛盾. 理由A1A2…AkB (A1A2…Ak)B (A1A2…AkB) (A1A2…AkB)0 A1A2…AkB0,17,归谬法实例,例4 前提：(pq)r, rs, s, p 结论：q 证明 用归缪法① q 结论否定引入② rs 前提引入③ s 前提引入④ r ②③拒取式⑤ (pq)r 前提引入 ⑥ (pq) ④⑤析取三段论⑦ pq ⑥置换 ⑧ p ①⑦析取三段论⑨ p 前提引入pp ⑧⑨合取,18,第三章 习题课,主要内容 推理的形式结构 判断推理是否正确的方法真值表法 等值演算法主析取范式法 推理定律 自然推理系统P 构造推理证明的方法直接证明法附加前提证明法归谬法(反证法),19,基本要求,理解并记住推理形式结构的两种形式：1. (A1A2…Ak)B2. 前提：A1, A2, … , Ak 结论：B 熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等） 牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法 会解决实际中的简单推理问题,20,练习1：判断推理是否正确,1. 判断下面推理是否正确:(1) 前提：pq, q结论：p,解 推理的形式结构:,(pq)qp,方法一：等值演算法(pq)qp ((pq)q)p (pq)qp ((pq)(qq))p pq,易知10是成假赋值，不是重言式，所以推理不正确.,21,练习1解答,方法二：主析取范式法，(pq)qp((pq)q)ppqM2m0m1m3 未含m2, 不是重言式, 推理不正确.,22,练习1解答,方法三 真值表法不是重言式, 推理不正确,方法四 直接观察出10是成假赋值,23,练习1解答,用等值演算法(qr)(pr)(qp) (qr)(pr)(qp) ((qr)(pr))(qp) ((qp)(qr)(rp))(qp)  ((qp)(qr)(rp))(qp) 1 推理正确,(2) 前提：qr, pr 结论：qp,解 推理的形式结构：,(qr)(pr)(qp),24,练习2：构造证明,2. 在系统P中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和园游人太多，就不去颐和园. 今天是周六，并且颐和园游人太多. 所以, 我们去圆明园或动物园玩.,证明：(1) 设 p：今天是周六，q：到颐和园玩，r：到圆明园玩，s：颐和园游人太多t：到动物园玩(2) 前提：p(qr), sq, p, s结论：rt,25,练习2解答,(3) 证明：① p(qr) 前提引入② p 前提引入③ qr ①②假言推理④ sq 前提引入⑤ s 前提引入⑥ q ④⑤假言推理⑦ r ③⑥析取三段论⑧ rt ⑦附加,。