4命题演算(推理理论).ppt

1、1,第四讲 命题逻辑的推理理论,命题逻辑的推理理论也称为命题演算 主要内容 一、推理的形式结构 二、推理定律和推理规则 三、逻辑证明方法,2,数理逻辑的推理理论主要研究推理的“思维过程”，为推理提供一定的推理规则。它只关心从前提得到结论这种推理的正确有效性。无论前提是否真得正确，它总是假设其是成立的。所以推理的正确性和结论的正确性可能是不一致的。推理理论在应用上常常是将一些定理，定律，公理和条件作为前提，通过推理得到新的定理。,引言,3,一、推理的形式结构,定义1 设A1, A2, , Ak, B为命题公式. 若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，则称由前提A

2、1, A2, , Ak推出结论B的推理是有效的或正确的, 并称B是有效结论或称B可由A1, A2, , Ak逻辑推出.,定理1 由命题公式A1, A2, , Ak 推B的推理正确当且仅当A1A2AkB为重言式,4,推理的形式结构,2. A1A2AkB 若推理正确, 记为A1 A2 Ak B 3. 前提： A1, A2, , Ak 结论： B,推理的形式结构 1. A1, A2, , Ak B 若推理正确, 记为A1,A2,An B,5,二、推理定律重言蕴涵式,1. A (AB) 附加律 2. (AB) A 化简律 3. (AB)A B 假言推理 4. (AB)B A 拒取式 5. (AB)B

3、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,6,推理规则,(1) 前提引入规则(P) 在推理过程中，可以随时引入已知的前提。 (2) 结论引入规则(T) 在推理过程中，前面已推出的有效结论都可作为后续推理的前提引用。 (3) 置换规则(R) 在推理过程中，命题公式中的子公式都可以用与之等值的命题公式置换，得到证明

4、的公式序列的另一公式。 (4) 代入规则(S) 在推理过程中，重言式中的任一命题变元都可以用一命题公式代入，得到的仍是重言式。,7,推理规则,(4) 假言推理规则 (6) 化简规则 (8) 假言三段论规则,(5) 附加规则 (7) 拒取式规则 (9) 析取三段论规则,8,推理规则,(10) 构造性二难推理规则 (12) 合取引入规则,(11) 破坏性二难推理规则,9,三、逻辑证明方法,判断有效结论的过程就是论证过程。 基本方法： （1）真值表法 （2）直接证明法 （3）间接证明法（反证法） 具体：等值演算、 主析取范式、构造证明法等,10,例：判断下列推理是否正确。 今天杨尚树或去网吧或去教室

5、。他没去教室，所以他去网吧了。 设 p：杨尚树去网吧。q：杨尚树去教室。则， 前提：p q , q 结论：p 推理的形式结构： (p q) q) p,真值表法,11,真值表法,该命题公式为重言式，说明推理正确，所以杨尚树去网吧,(p q) q) p,12,推理实例,例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 由定理1可知推理正确

6、,13,推理实例,(2) 推理的形式结构:,(pq)qp,用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确,14,例2 构造下面推理的证明： 若明天是星期一或星期三，我明天就有课. 若我明天有课，今天必备课. 我今天没备课. 所以，明天不是星期一、也不是星期三. 解 (1) 设命题并符号化 设 p：明天是星期一，q：明天是星期三， r：我明天有课，s：我今天备课,(2) 写出证明的形式结构 前提：(pq)r, rs, s 结论：pq,15,直接证明法,(2) 写出证明的形式结构

7、前提：(pq)r, rs, s 结论：pq (3) 证明（证明过程三列式） 序号 当前得到的结论 当前得到结论的理由 rs P( 前提引入) s P r T I (拒取式) (pq)r P (pq) T E (拒取式) pq TE 德摩根率,16,附加前提证明法,附加前提证明法 适用于结论为蕴涵式(CP规则) 欲证 前提：A1, A2, , Ak 结论：CB 等价地证明 前提：A1, A2, , Ak, C 结论：B 理由：(A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,17,附加前提证明法实例,例3 构造下面推理的证明 2是素数或合数. 若

8、2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明 (1) 设 p：2是素数，q：2是合数， r： 是无理数，s：4是素数 (2) 推理的形式结构 前提：pq, pr, rs 结论：sq,18,附加前提证明法实例,(3) 证明 s CP规则 pr P rs P ps T I (假言三段论) p T I (拒取式) pq P q TI (析取三段论),19,归谬法（反证法）,归谬法 (反证法) 欲证 前提：A1, A2, , Ak 结论：B 做法 在前提中加入B，推出矛盾. 理由 A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB0,20,归谬法实例,例4 前提：(pq)r, rs,