命题逻辑推理理论离散数学精.ppt

《命题逻辑推理理论离散数学精.ppt》由会员分享，可在线阅读，更多相关《命题逻辑推理理论离散数学精.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、命题逻辑推理理论离散数学1第1页，本讲稿共26页2.4.1 推理的形式结构推理的形式结构一、什么是推理一、什么是推理定定义义2.19 设设A1，A2，Ak，B都都是是命命题题公公式式，若若对对于于每每组组赋赋值值,A1 A2 Ak为为假假,或或者者当当A1 A2 Ak为为真真时时，B也也为为真真,则则称称由由前前提提A1，A2，,Ak推推B的的推推理理有有效效或或推推理理正正确确,并称并称B是是有效的结论。有效的结论。2第2页，本讲稿共26页定理定理2.8 由前提由前提A1,A2,Ak 推出推出B 的推理正确当且仅当的推理正确当且仅当 A1 A2 Ak B为重言式为重言式.如果把（如果把（A1

2、 A2 Ak）B为永真式记为：为永真式记为：上式的含义？上式的含义？3第3页，本讲稿共26页二、推理的形式结构二、推理的形式结构定定义义2.20 称称（A1 A2 Ak）B为为由由前前提提 A1,A2,Ak推结论推结论 B 的推理的形式结构。的推理的形式结构。推理的形式结构一般有以下三种：推理的形式结构一般有以下三种：形式形式(1)A1 A2 Ak B 形式形式(2)前提前提:A1,A2,Ak 结论结论:B 形式形式(3)A1，A2，Ak B4第4页，本讲稿共26页n真值表法真值表法n等值演算法等值演算法n主析取范式法主析取范式法n构造证明法构造证明法判断推理是否正确的方法判断推理是否正确的方

3、法:真值表的方法参见真值表的方法参见P.67例例2.23。5第5页，本讲稿共26页例例1 判断下面推理是否正确判断下面推理是否正确:(1)若今天是若今天是1号号,则明天是则明天是5号号.今天是今天是1号号.所以所以,明天是明天是5号号.解解 设设 p:今天是今天是1号号,q:明天是明天是5号号 推理的形式结构为推理的形式结构为证明证明 用等值演算法用等值演算法 所以，原推理正确。所以，原推理正确。6第6页，本讲稿共26页例例1(2)若若今今天天是是1号号,则则明明天天是是5号号.明明天天是是5号号.所所以以,今今天天是是1号。号。解解 设设 p:今天是今天是1号号,q:明天是明天是5号号 推理

4、的形式结构为推理的形式结构为证明证明 用主析取范式法用主析取范式法 这不是一个永真式，这不是一个永真式，01是该公式成假的赋值，所以推是该公式成假的赋值，所以推理不正确。理不正确。7第7页，本讲稿共26页三、推理定律重言蕴涵式 A (A B)附加律附加律(A B)A 化简律化简律(AB)A B 假言推理假言推理(AB)B A 拒取式拒取式(A B)B A 析取三段论析取三段论(AB)(BC)(AC)假言三段论假言三段论(AB)(BC)(AC)等价三段论等价三段论(AB)(CD)(A C)(B D)构造性二难构造性二难(AB)(AB)B 构造性二难构造性二难(特殊形式特殊形式)(AB)(CD)(

5、BD)(AC)破坏性二难破坏性二难8第8页，本讲稿共26页n注意：注意：（1）推理规则中出现的）推理规则中出现的A、B、C 等是元语言符号；等是元语言符号；（2）直接引用而不需证明，只要说明所引用规则的名称；）直接引用而不需证明，只要说明所引用规则的名称；（3）24个永真公式每个都可以等效为个永真公式每个都可以等效为2个推理规则。个推理规则。9第9页，本讲稿共26页2.4.2 自然推理系统P自然推理系统自然推理系统P由下述由下述3部分组成部分组成:1.字母表字母表(1)命题变项符号命题变项符号:p,q,r,pi,qi,ri,(2)联结词联结词:,(3)括号与逗号括号与逗号:(),2.合式公式合

6、式公式3.推理规则推理规则(1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则10第10页，本讲稿共26页自然推理系统P(续)(7)拒取式规则拒取式规则 AB B A(8)假言三段论规则假言三段论规则 AB BC AC(4)假言推理规则假言推理规则 AB A B(5)附加规则附加规则 A A B(6)化简规则化简规则 A B A 11第11页，本讲稿共26页自然推理系统P(续)(11)破坏性二难推理规则破坏性二难推理规则 AB CD BD AC(12)合取引入规则合取引入规则 A B A B(9)析取三段论规则析取三段论规则 A B B A(10)构造性二难推理规

7、则构造性二难推理规则 AB CD A C B D12第12页，本讲稿共26页直接证明法例例2 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明:前提前提:p q,qr,ps,s结论结论:r(p q)证明证明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 qr 前提引入前提引入 r 假言推理假言推理 r(p q)合取合取推理正确推理正确,r(p q)是有效结论是有效结论13第13页，本讲稿共26页实例例例3 构造推理的证明构造推理的证明:若明天是星期一或星期三若明天是星期一或星期三,我就有我就有课课.若有

8、课若有课,今天必需备课今天必需备课.我今天下午没备课我今天下午没备课.所以所以,明天明天不是星期一和星期三不是星期一和星期三.解解 设设 p:明天是星期一明天是星期一,q:明天是星期三，明天是星期三，r:我有课，我有课，s:我备课我备课前提前提:(p q)r,rs,s结论结论:pq 14第14页，本讲稿共26页实例(续)前提前提:(p q)r,rs,s结论结论:pq 证明证明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式(p q)r 前提引入前提引入 (p q)拒取式拒取式 pq 置换置换结论有效结论有效,即明天不是星期一和星期三即明天不是星期一和星期三15第15页，本讲稿共

9、26页附加前提证明法欲证明欲证明 等价地证明等价地证明前提前提:A1,A2,Ak 前提前提:A1,A2,Ak,C结论结论:CB 结论结论:B理由理由:(A1 A2 Ak)(CB)(A1 A2 Ak)(C B)(A1 A2 Ak C)B (A1 A2 Ak C)B16第16页，本讲稿共26页实例例例4 构造下面推理的证明构造下面推理的证明:前提前提:p q,q r,rs结论结论:ps证明证明 p 附加前提引入附加前提引入 p q 前提引入前提引入 q 析取三段论析取三段论 q r 前提引入前提引入 r 析取三段论析取三段论 rs 前提引入前提引入 s 假言推理假言推理推理正确推理正确,ps是有效

10、结论是有效结论17第17页，本讲稿共26页归谬法(反证法)欲证明欲证明前提：前提：A1,A2,Ak 结论：结论：B将将 B加入前提加入前提,若推出矛盾若推出矛盾,则得证推理正确则得证推理正确.理由理由:A1 A2 AkB (A1 A2 Ak)B (A1 A2 AkB)括号内部为矛盾式当且仅当括号内部为矛盾式当且仅当(A1 A2 AkB)为重言式为重言式18第18页，本讲稿共26页实例例例5 构造下面推理的证明构造下面推理的证明前提前提:(p q)r,rs,s,p结论结论:q证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式1

11、9第19页，本讲稿共26页实例(续)(p q)r 前提引入前提引入 (p q)析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 p p 合取合取推理正确推理正确,q是有效结论是有效结论20第20页，本讲稿共26页课堂练习11、证明证明2、证明证明21第21页，本讲稿共26页证证证明证明前提前提附加前提附加前提、，假言推理，假言推理前提前提、，拒取式，拒取式、，析取三段论，析取三段论前提前提、，拒取式，拒取式、，CP22第22页，本讲稿共26页证证 证明证明假设前提假设前提，E1前提前提、，假言推理，假言推理前提前提、，析取三段论，析取三段论前提前提，化简，化

12、简、，合取引入，合取引入 是一个永假式，因此，原推理正确。是一个永假式，因此，原推理正确。23第23页，本讲稿共26页应用实例应用实例1 分析下列事实分析下列事实“如果我有很高的收入，那如果我有很高的收入，那么我就能资助许多贫困学生；如果我能资助许多贫困么我就能资助许多贫困学生；如果我能资助许多贫困学生，那么我很高兴；但我不高兴，所以我没有很高学生，那么我很高兴；但我不高兴，所以我没有很高的收入。的收入。”试指明前提和结论，并给予证明。试指明前提和结论，并给予证明。课堂练习课堂练习224第24页，本讲稿共26页应用实例应用实例2 将下列条件作为前提，验证所得结论是否将下列条件作为前提，验证所得结论是否有效：有效：(a)明天或是天晴，或是下雨；明天或是天晴，或是下雨；(b)如果是天晴，我去公园；如果是天晴，我去公园；(c)如果我去公园，我就不看书。如果我去公园，我就不看书。结论：如果我在看书，则天下雨。结论：如果我在看书，则天下雨。25第25页，本讲稿共26页本节习题本节习题P.83:2.33（1）、（）、（3）2.35 2.36（1）26第26页，本讲稿共26页