《命题逻辑》由会员分享，可在线阅读，更多相关《命题逻辑（35页珍藏版）》请在金锄头文库上搜索。
1、,第八讲 推理理论,课 后 作 业,下周上交作业,回 顾,一、 蕴含公式 定义1-13 设A，B是命题公式, 若AB是重言式, 则称AB是蕴含重言式，记为AB ，读作“A永真蕴含B”。简称A蕴含B 即 AB iff AB 1 注意: 与 是意义不同的符号。,二、证明A永真蕴含B的方法,方法一：用真值表法或等价变换(推导)法证明AB 1,方法二：通过分析的方法来证明一个条件命题是蕴含式,方法二：由于原命题等值于其逆反命题，即 ABBA ，所以用分析法证明AB ， 有如下两种方法: (1) 假设前件A为真时, 推出后件B也为真, 则AB ; (2) 假设后件B为假时, 推出前件A也为假, 则AB
2、。,证明下列各式: (PQ)Q(PQ) (PPQ) (PPR) QR,推理的形式结构,定义1 设A1, A2, , Ak, B为命题公式. 若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真， 则称由前提A1, A2, , Ak推出结论B的推理是有效的或正确的, 并称B是有效结论.,定理3.1 由命题公式A1, A2, , Ak 推B的推理正确当且仅当A1A2AkB为重言式 注意: 推理正确不能保证结论一定正确,推理理论,推理的形式结构,2. A1A2AkB若推理正确, 记为A1 A2 Ak B 3. 前提： A1, A2, , Ak结论： B 判断推理是否正确的方法:真值
3、表法等值演算法主析取范式法,推理的形式结构 1. A1, A2, , Ak B若推理正确, 记为A1,A2,An B,推理实例,例1 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号.,解 设 p：今天是1号，q：明天是5号. (1) 推理的形式结构:,(pq)pq,用等值演算法(pq)pq (pq)p)q pqq 1由定理可知推理正确,推理实例,(2) 推理的形式结构:,(pq)qp,用主析取范式法(pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(
4、pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确,推理定律重言蕴涵式,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) 等价三段论 8. (AB)(CD)(AC) (BD) 构造性二难(AB)(AB) B 构造性二难(特殊形式)9. (AB)(CD)( BD) (AC) 破坏性二难 每个等值式可产生两个推理定律 如, 由AA可产生 AA 和 AA,自然推理系统P,定义2 一个形式系统 I 由下
5、面四个部分组成：(1) 非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作 E(I).(3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I).(4) 推理规则集，记作 R(I). 记I=, 其中是 I 的形式语言系统, 是 I 的形式演算系统. 自然推理系统: 无公理, 即AX(I)= 公理推理系统 推出的结论是系统中的重言式, 称作定理。,自然推理系统P,定义3 自然推理系统 P 定义如下: 1. 字母表(1) 命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：, , , , (3) 括号与逗号：(, ), ， 2. 合式公
6、式 3. 推理规则(1) 前提引入规则(P规则)(2) 结论引入规则(3) 置换规则(4) 代入规则(2)、(3)和(4)都称为T规则。,T规则：在推导中，如果有一个或多个公式永真蕴含 公式S，则可把S引入到推导过程之中。,推理规则,(4) 假言推理规则(6) 化简规则(8) 假言三段论规则,(5) 附加规则(7) 拒取式规则(9) 析取三段论规则,推理规则,(10) 构造性二难推理规则(12) 合取引入规则,(11) 破坏性二难推理规则,在自然推理系统P中构造证明,设前提A1, A2, Ak,结论B及公式序列C1, C2, Cl. 如果每一个Ci(1il)是某个Aj, 或者可由序列中前面的公
7、式应用推理规则得到, 并且Cl =B, 则称这个公式序列是由A1, A2, Ak推出B的证明 例2 构造下面推理的证明：若明天是星期一或星期三，我明天就有课. 若我明天有 课，今天必备课. 我今天没备课. 所以，明天不是星期一、也不是星期三. 解 (1) 设命题并符号化 设 p：明天是星期一，q：明天是星期三，r：我明天有课，s：我今天备课,直接证明法,(2) 写出证明的形式结构前提：(pq)r, rs, s结论：pq (3) 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换,例2 证明证明：,P T(1)E11 联结词归化 P T(2)(3)
8、I13 假言三段论 T(4)E14 P T(5)(6)I13 假言三段论 T(7)E11 联结词归化,P T(1)E11 联结词归化 P T(2)(3)I12 拒取式 P T(5) E10 德.摩根公式 T(6)E11 联结词归化 T(4)(7)I12 拒取式,例3 推理证明,前提：如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。 结论：羊不吃草。（注意：一般以分号“；”或句号“。”表示 一个完整独立的前提语句）,解 首先将命题符号化。设 P： 马会飞 ； Q： 羊吃草； R： 母鸡是飞鸟； S： 烤熟的鸭子还会跑；则上述命题符号化为： 前提：PQ
9、R，RS，S； 结论：Q。,证明：(1) S P(2)RS P(3)R T(1),(2) I(4)PQR P(5)(PQ) T(3),(4) I(6)PQ T(5) E(7)Q T(6) I,前提：PQR，RS，S； 结论：Q。,例4 张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎，问张三、李四、王五三人到底谁说真话，谁说假话？ 解:设 P：张三说真话;Q：李四说真话;R：王五说真话,则依题意可得前提:,推理过程如下：,P P T(1)(2)I13 P T(3)(4)I13 T(5)E11 T(6)E9 P T(7)(8)I11 P T(9)(10)I11 T(7)(9)(11)
10、I9,推导结果:李四说真话,其余两人说假话。,【案例】公安局审理一起盗窃案,已知: （1）甲或乙盗窃了电脑。 （2）若甲盗窃电脑，则作案时间不可能发生在午夜前。 （3）若乙证词正确，则在午夜时屋里灯光未灭。 （4）若乙证词不正确，则作案时间发生在午夜前。 （5）午夜时屋里灯光灭了。 问：谁是盗窃犯？ 解: 设P：甲盗窃了电脑，Q：乙盗窃了电脑，R：作案时间发生在午夜前，S：乙证词正确，T：午夜时屋里灯光灭了。 前提：PQ ，PR ，ST ，SR，T 推理过程如下：,P P T(1)(2)I12 拒取式 P T(3)(4)I11 假言推论 P T(5)(6)I12 拒取式 P T(7)(8)I1
11、0,推导结果：乙盗窃了电脑。,前提：PQ ，PR ，ST ，SR，T,附加前提证明法(CP规则),附加前提证明法 适用于结论为蕴涵式 欲证前提：A1, A2, , Ak结论：CB 等价地证明前提：A1, A2, , Ak, C结论：B 理由：(A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,附加前提证明法实例,例5 构造下面推理的证明2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明(1) 设 p：2是素数，q：2是合数，r： 是无理数，s：4是素数(2)
12、推理的形式结构前提：pq, pr, rs结论：sq,附加前提证明法实例,(3) 证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论,练习 推理证明 证明：,CP规则 T(1)I1 化简式 P T(2)(3)I11 假言推论 P T(1)I2 化简式 T(5)(6)I11 假言推论 T(4)(7)I9 附加前提回归,反证法,反证法 欲证前提：A1, A2, , Ak 结论：B 做法在前提中加入B，推出矛盾. 理由A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB0,反证法实例,例6 前提：(pq)r, rs, s, p 结论：q 证明 用反证法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入pp 合取,
