第三章 命题逻辑的推理理论.ppt

1、第三章 命题逻辑的推理理论,本章的主要内容 推理的形式结构 自然推理系统P 本章与其他章的联系 本章是第五章的特殊情况和先行准备,3.1 推理的形式结构,一、何为推理？何为证明？ 1例（1）正项级数收敛当且仅当部分和有上界 （2）若AB且CD，则ACBD （3）若今天是星期一，则明天是星期二 （4）若ACBD，则AB且CD,2推理从前提出发推出结论的思维过程 上例中，（1），（2），（3）是正确的推理，而（4）是错误的推理.,3证明描述推理正确或错误的过程。,二、推理的形式结构及证明方法,1推理的正确与错误 定义3.1 设A1, A2, , Ak, B为命题公式 （1）若对于每组赋值，或者A1

2、A2 Ak 均为假，或者当A1A2Ak为真时，B也为真，则称由前提A1, A2, , Ak推出B的推理正确，并称B是有效结论； （2）否则称推理不正确（错误）；,定理3.1 命题公式A1, A2, , Ak 推B的推理正确当且仅当 A1A2AkB为重言式,2推理的形式结构（多种形式） （1）设= A1, A2, , Ak B （2）A1A2AkB （3）前提： A1, A2, , Ak 结论： B,说明： 当推理正确时， （1）中记为 B， （2）中记为A1A2AkB,3判断推理是否正确的方法（多种） （1）真值表法 （2）等值演算法 （3）主析取范式法 （4）构造证明法,说明： 当命题变项少

3、时，（1）（3）方便 （1），（2）, （3）用形式结构（2） 构造证明法用形式结构（3）,例 判断下面推理是否正确?（1）若今天是1号，则明天是5号. 今天是1号. 所以明天是5号. （2）若今天是1号，则明天是5号. 明天是5号. 所以今天是1号.,解 设p：今天是1号，q：明天是5号. 证明的形式结构采用（2）. （1）(pq)pq （2）(pq)qp,证明（1）（用等值演算法） (pq)pq (pq)p)q pqq 1 由定理3.1可知推理正确,证明：（2）（用主析取范式法） (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m

4、1, 故01是成假赋值,所以推理不正确,4.推理定律 （1）推理定律重言蕴涵式 （2）重要的推理定律 A (AB) 附加律 (AB) A 化简律 (AB)A B 假言推理 (AB)B A 拒取式 (AB)B A 析取三段论 (AB)(BC) (AC) 假言三段论 (AB)(BC) (AC) 等价三段论 (AB)(CD)(AC) (BD) 构造性二难 (AB)(AB)(AA)B 构造性二难(特殊形式) (AB)(CD)( BD) (AC) 破坏性二难,3.2 自然推理系统P,一、形式系统 1形式系统的定义 定义3.2 一个形式系统I由下面四个部分组成： （1）非空的字母表，记作A(I). （2）

5、A(I)中符号构造的合式公式集，记作E(I). （3）E(I)中一些特殊的公式组成的公理集，记作AX(I). （4）推理规则集，记作R(I).,2形式系统的分类 （1）自然推理系统 （2）公理系统,二、自然推理系统P 定义3.3 P的定义如下 1字母表 （1）命题变项符号：p, q, r, , pi, qi, ri, （2）联结词符号：, , , , （3）括号与逗号：(, ), ， 2合式公式（同定义1.6）,3推理规则,（4）假言推理规则,（5）附加规则：,（1）前提引入规则,（2）结论引入规则,（3）置换规则,AB,A,B,A,AB,（6）化简规则：,（7）拒取式规则：,AB,A,AB,

6、B,A,（8）假言三段论规则：,AB,BC,AC,（9）析取三段论规则：,AB,B,A,（10）构造性二难推理规则：,AB,CD,AC,BD,(11) 破坏性二难推理规则：,AB,CD,BD,AC,（12）合取引入规则：,A,B,AB,三、在自然推理系统P中构造证明,1直接证明法,例：证明 (pq) , (pr) ,(qs) sr,思路：由前提出发，通过形式推理，往结论上靠 （1） pq 前提引入 （2） p q (1) 置换 （3） q s 前提引入 （4） p s (2) ,(3) ,假言三段论 （5） s p (4) ,置换 （6） pr 前提引入 （7） s r (5),(6),假言三

7、段论 （8） sr (7) ,置换,例：证明pq,q(rs),r(t u), ptu,证明： (1)pq 前提引入 (2)q(rs) 前提引入 (3)p(rs) (1),(2)假言三段论 (4)pt 前提引入 (5)p (4),化简 (6) (rs) (5),(3),假言推理,(7)r (6),化简 (8) r(t u) 前提引入 (9) (rt) u (8),置换 (10)t (4),化简 (11) rt (7),(10),合取 (12) u (9),(11),析取三段论,例 用直接证明法构造下面推理的证明： 若明天是星期一或星期三，我就有课。 若有课，今天必备课。我今天下午没备课. 所以，

8、说明天是星期一或星期三是不对的。,构造证明（1）设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课 （2）形式结构： 前提：(pq)r, rs, s 结论：(p q),（3）证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式,练习： 1.证明：(pr),qs ,p,q rs 2.在自然推理系统中构造下面推理的证明： 若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理，所以小赵喜欢数学。,练习： 3.如果乐队不能演奏摇滚乐或者点心没有准时送上来，那么新年音乐会就将取消，并且玛丽会很生气。如果音乐会

9、取消，那么就要办理退款。没有办理退款。所以乐队能演奏摇滚乐。,2. 附加前提证明法 （1）欲证： 前提：A1, A2, , Ak 结论：CB,（2）等价地证明 前提: A1, A2, , Ak, C 结论： B,（3）理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,例 构造下面推理的证明：2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数.,用附加前提证明法构造证明 （1）设p：2是素数，q：2是合数， r： 是无理数， s：4是素数,（2）形式结构 前提：pq, pr, rs

10、结论：sq,（3）证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论,请用直接证明法证明之,练习：证明： (1)p(qr)，(uv)r，q(ps)qu (2)p（qs），rp，q， rs,3归谬法（或称反证法） （1）欲证 A1A2AkB 前提：A1, A2, , Ak 结论：B,（2）将B当前提，推出矛盾，得证（1）正确,（3）理由： A1A2AkB (A1A2Ak)B (A1A2AkB) 括号内部为矛盾式当且仅当 (A1A2AkB)为重言式,例 前提：(pq)r, rs, s, p结论：q,证明（用归缪法） q 结论否定引入

11、 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取,请用直接证明法证明之,练习： 证明： (1)pq，(qr)r，(ps)s (2) (pq) (qr) p,第三章 小 结,一、本章的主要内容及要求 1主要内容 推理的形式结构的不同形式 判断推理是否正确的不同方法 真值表法 等值演算法 主析取范式法 构造证明法 在自然推理系统P中构造证明,2. 要求 理解并记住推理形式结构的如下形式： (A1A2Ak)B 前提：A1, A2, , Ak 结论：B 熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法

12、、主析取范式法等） 牢记P系统中各条推理规则（内容与名称） 会用附加前提证明法及归谬法,二、练习 1用不同的方法验证下面推理是否正确. 对于正确的推理还要在P系统中给出证明. （1）前提：pq, q 结论：p （2）前提：qr, pr 结论：qp,解（1）答案：不正确。验证答案，需将推理形式结构改为另一种形式 (pq)qp () 只需证明()不是重言式,方法一 等值演算 (pq)qp (pq)q)p (pq)qp (pq)(qq)p pq 易知10是成假赋值，故()不是重言式，所以推理不正确.,方法二 主析取范式法经过演算后可知 () m0m1m3未含m2, 故()不是重言式.,方法三 真值表法，()的真值表为,结论（不正确）是对的,方法四 直接观察出10是成假赋值,解（2）答案：推理正确 方法一 真值表法（自己做） 方法二 等值演算法（自己做） 方法三 主析取范式法（自己做）,方法四 P系统中构造证明 证明：（直接证明法） pr （前提引入） rp （置换） qr （前提引入） qp （假言三段论）,请用附加前提证明法证明之,2在P系统中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和园游人太多，就不去颐和园. 今天是周六，并且颐和园游人太多.