离散数学命题逻辑推理理论优秀课件.ppt

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

1、离散数学命题逻辑推理理论1第1 页，本讲稿共23 页有效推理定义2.20 若对于每组赋值,A1A2 Ak 为假,或者当A1A2Ak为真时,B 也为真,则称由前提A1,A2,Ak推B 的推理有效或推理正确,并称B 是有效的结论定理2.8 由前提A1,A2,Ak 推出B 的推理正确当且仅当 A1A2AkB为重言式.2第2 页，本讲稿共23 页推理的形式结构形式(1)A1A2AkB形式(2)前提:A1,A2,Ak 结论:B 推理正确记作 A1A2AkB判断推理是否正确的方法:真值表法 等值演算法 主析取范式法 构造证明法3第3 页，本讲稿共23 页实例例1 判断下面推理是否正确:(1)若今天是1号,

2、则明天是5号.今天是1号.所以,明天是5号.解 设 p:今天是1号,q:明天是5号 推理的形式结构为(pq)pq证明 用等值演算法(pq)pq(pq)p)q(pq)p)q pqq 1得证推理正确4第4 页，本讲稿共23 页实例(续)(2)若今天是1号,则明天是5号.明天是5号.所以,今天是1号.解 设p:今天是1号,q:明天是5号.推理的形式结构为(pq)qp证明 用主析取范式法(pq)qp(pq)qp(pq)q)p qp(pq)(pq)(pq)(pq)m0m2m3 01是成假赋值,所以推理不正确.5第5 页，本讲稿共23 页推理定律重言蕴涵式 A(AB)附加律(AB)A 化简律(AB)A B

3、 假言推理(AB)B A 拒取式(AB)B A 析取三段论(AB)(BC)(AC)假言三段论(AB)(BC)(AC)等价三段论(AB)(CD)(AC)(BD)构造性二难(AB)(AB)B 构造性二难(特殊形式)(AB)(CD)(BD)(AC)破坏性二难6第6 页，本讲稿共23 页自然推理系统P自然推理系统P 由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,pi,qi,ri,(2)联结词:,(3)括号与逗号:(),2.合式公式3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则7第7 页，本讲稿共23 页自然推理系统P(续)(7)拒取式规则 AB B A(8)假言三段论规则

4、 AB BC AC(4)假言推理规则 AB A B(5)附加规则 A AB(6)化简规则 AB A 8第8 页，本讲稿共23 页自然推理系统P(续)(11)破坏性二难推理规则 AB CD BD AC(12)合取引入规则 A B AB(9)析取三段论规则 AB B A(10)构造性二难推理规则 AB CD AC BD9第9 页，本讲稿共23 页直接证明法例2 在自然推理系统P 中构造下面推理的证明:前提:pq,qr,ps,s结论:r(pq)证明 ps 前提引入 s 前提引入 p 拒取式 pq 前提引入 q 析取三段论 qr 前提引入 r 假言推理 r(pq)合取推理正确,r(pq)是有效结论10

5、第10 页，本讲稿共23 页实例例3 构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必需备课.我今天下午没备课.所以,明天不是星期一和星期三.解 设 p:明天是星期一,q:明天是星期三，r:我有课，s:我备课前提:(pq)r,rs,s结论:pq 1 1第1 1 页，本讲稿共23 页实例(续)前提:(pq)r,rs,s结论:pq 证明 rs 前提引入 s 前提引入 r 拒取式(pq)r 前提引入(pq)拒取式 pq 置换结论有效,即明天不是星期一和星期三12第12 页，本讲稿共23 页附加前提证明法欲证明 等价地证明前提:A1,A2,Ak 前提:A1,A2,Ak,C结论:CB 结

6、论:B理由:(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B(A1A2AkC)B13第13 页，本讲稿共23 页实例例4 构造下面推理的证明:前提:pq,qr,rs结论:ps证明 p 附加前提引入 pq 前提引入 q 析取三段论 qr 前提引入 r 析取三段论 rs 前提引入 s 假言推理推理正确,ps 是有效结论14第14 页，本讲稿共23 页归谬法(反证法)欲证明前提：A1,A2,Ak 结论：B将B 加入前提,若推出矛盾,则得证推理正确.理由:A1A2AkB(A1A2Ak)B(A1A2AkB)括号内部为矛盾式当且仅当(A1A2AkB)为重言式15第15 页，本讲稿共23

7、 页实例例5 构造下面推理的证明前提:(pq)r,rs,s,p结论:q证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式16第16 页，本讲稿共23 页实例(续)(pq)r 前提引入(pq)析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取推理正确,q是有效结论17第17 页，本讲稿共23 页归结证明法理由(pq)(pr)(qr)(pq)(pr)(qr)(pq)(pr)qr(pq)q)(pr)r)(pq)(pr)1归结规则 A B A C B C18第18 页，本讲稿共23 页归结证明法(续)在自然推理系统P 中只需下述推理规则:(1)前提引入规则(2)结

8、论引入规则(3)置换规则(4)化简规则(5)合取引入规则(6)归结规则19第19 页，本讲稿共23 页归结证明法的基本步骤1.将每一个前提化成等值的合取范式,设所有合取范式的全部简单析取式为A1,A2,At2.将结论化成等值的合取范式B1B2Bs,其中每个Bj是简单析取式3.以A1,A2,At为前提,使用归结规则推出每一个Bj,1js4.由合取引入规则得到结论B1B2Bs20第20 页，本讲稿共23 页实例例6 用归结证明法构造下面推理的证明:前提:(pq)r,rs,s结论:(pq)(ps)解(pq)r(pq)r(pq)r(pr)(qr)rs rs(pq)(ps)(pq)(ps)(pq)(ps

9、)p(qs)推理可表成前提:pr,qr,rs,s结论:p(qs)21第21 页，本讲稿共23 页实例(续)前提:pr,qr,rs,s结论:p(qs)证明 qr 前提引入 rs 前提引入 qs 归结 s 前提引入 s0 置换 r0 归结 pr 前提引入 p0 归结 p 置换 p(qs)合取引入22第22 页，本讲稿共23 页实例：公安破案 一个公安人员审查一件盗窃案，已知的事实如下：A 或B 盗窃了钻石；若A 盗窃了钻石，则作案时间不能发生在午夜前；若B 证词正确，则在午夜时屋里灯光未灭；若B 证词不正确，则作案时间发生在午夜前；午夜时屋里灯光灭了。谁盗窃了钻石呢？23第23 页，本讲稿共23 页