离散数学推理理论.ppt

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

1、离散数学推理理论现在学习的是第1页，共18页一、有效论证与推理规则一、有效论证与推理规则定义：定义：A1A2AnA,其为永真式，则称由其为永真式，则称由前提前提A1,A2,An得到得到有效结论有效结论A；从前提公式得；从前提公式得到有效结论的过程称为到有效结论的过程称为正确推理正确推理。若若AB是永真式，则记为是永真式，则记为AB；若若AB是永真式，则记为是永真式，则记为AB。前提一致和不一致：前提一致和不一致：如果前提如果前提A1A2An为可满足式，则称为可满足式，则称为前提为前提A1,A2,An一致。一致。现在学习的是第2页，共18页实例分析实例分析 判断推理是否正确：张红不管有无空闲都不

2、看电影。张红看了电影。所以张红有空闲判断推理是否正确：张红不管有无空闲都不看电影。张红看了电影。所以张红有空闲时间又没有空闲时间。时间又没有空闲时间。解：解：P:张红有空闲时间；张红有空闲时间；Q：张红看电影：张红看电影。前提：前提：A1=P P Q A2=Q 结论：结论：A=P P 问题：问题：该结论是否有效结论。该结论是否有效结论。(该推理是否正确该推理是否正确)。010100001101111111011101101 11100(P P Q)Q P PQP 所以，结论所以，结论A是有效结论；该推理是正确的。而前提是不一致的。是有效结论；该推理是正确的。而前提是不一致的。现在学习的是第3页

3、，共18页基本蕴涵式基本蕴涵式名称蕴涵关系式化简式化简式 A BA A BB (AB)A (AB)B 附加式附加式 AA B BA B AAB BAB 假言推理假言推理 (AB)AB拒取式拒取式 (AB)B A析取三段式析取三段式 (A B)AB假言三段式假言三段式 (AB)(BC)AC等价三段式等价三段式 (AB)(BC)AC二难推论二难推论 (AB)(CD)(A C)B D现在学习的是第4页，共18页(AB)B A的证明的证明AB(A B)B A0011111011001110001101110010现在学习的是第5页，共18页法一、真值表法：法一、真值表法：011011110101011

4、010111000(A B)BBA法二、利用等值演算法证明：法二、利用等值演算法证明：证：证：(A B)B (AB)B (AB)B(AB)B A(B B)AT T 所以所以,(AB)B(AB)B的证明的证明?第三种方法第三种方法?现在学习的是第6页，共18页自然推理系统自然推理系统P形式系统形式系统自然推理系统自然推理系统公理系统公理系统特点特点：只能从几个给定的公理几个给定的公理出发，应用系统中的推理规则进行推演，得到的结论是系统中的定理定理。特点特点：可以从任意给定的前提任意给定的前提出发，应用系统中的推理进行推演，得到的结论在系统中被认为是有效的有效的。现在学习的是第7页，共18页自然推

5、理系统自然推理系统P 自然推理系统自然推理系统P定义如下定义如下：1.字母表字母表 (1)命题常元，命题变元：命题常元，命题变元：P,Q,R,Pi,Qi,1,0(T,F)(2)命题联结词：命题联结词：、(3)括号：括号：(,)2.合式公式：合式公式：(略略)3.推理规则：推理规则：(1).前提引入规则前提引入规则(P规则规则)：在证明的任何步上，都可引入前提；：在证明的任何步上，都可引入前提；(2).结论引用规则结论引用规则(T规则规则)：在证明的任何步上，所得的结论都可：在证明的任何步上，所得的结论都可作为证明得前提；作为证明得前提；(3).置换规则：置换规则：在证明的任何步上，命题公式的任

6、何子命题公式都在证明的任何步上，命题公式的任何子命题公式都可以用与之等价的命题公式置换。可以用与之等价的命题公式置换。(4).永真蕴涵规则：永真蕴涵规则：使用基本蕴涵式，常常将条件用使用基本蕴涵式，常常将条件用，分开。分开。现在学习的是第8页，共18页基本蕴涵式证明的另一种方法基本蕴涵式证明的另一种方法(AB)B的证明的证明证明：证明：(AB)(AB)A B A B B (简化式）简化式）(AB)B的证明的证明现在学习的是第9页，共18页推理过程的证明形式推理过程的证明形式规范化的形式：规范化的形式：序号序号 公式公式 理由理由 B1 E 或或 I 或或 P 或或 的合取的合取 或或 cp B

7、2 .B3 .注意：注意：1)并非B1B2B3 2)Bi的获取：前提、中间结论现在学习的是第10页，共18页构造下列的推理的证明：构造下列的推理的证明：前提：前提：PQ,P R,SM,SR,M 结论：结论：Q。证：证：M P SM P S I拒取式 SR P R I假言推理 P R P P I拒取式 PQ P Q I析取三段式现在学习的是第11页，共18页一公安人员审查一件案件。一致的事实如下：一公安人员审查一件案件。一致的事实如下：(1).张三或李四盗窃了录像机；张三或李四盗窃了录像机；(2).如果张三盗窃了录像机，则作案时间不能在午夜前；如果张三盗窃了录像机，则作案时间不能在午夜前；(3)

8、.如果李四证词正确，则午夜时屋内灯光未灭；如果李四证词正确，则午夜时屋内灯光未灭；(4).如果李四证词不正确，则作案时间在午夜前；如果李四证词不正确，则作案时间在午夜前；(5).午夜时屋内灯灭了。午夜时屋内灯灭了。M P SM P S I拒取式拒取式 SR P R I假言推理假言推理 P R P P I拒取式拒取式 PQ P Q I析取三段式析取三段式解：将已知事实符号化：解：将已知事实符号化：设设 P:张三盗窃录像机；张三盗窃录像机；Q:李四盗窃录像机李四盗窃录像机;R:作案时间发生在午夜前；作案时间发生在午夜前；S:李四证词正确；李四证词正确；M:午夜时灯光未灭。午夜时灯光未灭。则前提为则

9、前提为:(1)PQ,(2)P R,(3)SM,(4)SR,(5)M。结论未定。结论未定。所以，可以得出是李四盗了录像机。所以，可以得出是李四盗了录像机。现在学习的是第12页，共18页例如例如前提：前提：p(rs)q)，p，s结论：结论：q。证明：证明：p p规则规则 p(rs)q)p规则规则 (rs)q I s p规则规则 s r I (rs)E q I现在学习的是第13页，共18页推理证明的方法推理证明的方法前提的合取前提的合取结论结论 是永真式是永真式间接证明法间接证明法推理证明推理证明演绎证明演绎证明归纳证明归纳证明直接证明法直接证明法附加前提证法附加前提证法(CP)归谬法归谬法(反证法

10、反证法)现在学习的是第14页，共18页附加前提证法附加前提证法(CP)针对这种情况：针对这种情况：前提：前提：A1，A2，An结论：结论：AB前提：前提：A1，A2，An，A结论：结论：B现在学习的是第15页，共18页例：例：前提：前提：P,P(Q R S)结论：结论：Q S证明：证明：(1)P cp规则规则 (2)P(Q R S)cp规则规则 (3)Q R S (1)(2)I (4)Q cp规则规则 (5)R S (3)(4)I (6)S (5)I 课堂作业：课堂作业：前提：前提：PQR，S P，Q 结论结论：SR现在学习的是第16页，共18页归谬法归谬法(反证法反证法)针对这种情况：针对这种情况：前提：前提：A1，A2，An结论：结论：A前提：A1，A2，An，A结论：0 （F）A(A)现在学习的是第17页，共18页例：例：前提：前提：R Q，RS，S Q，PQ 结论：结论：P证明：证明：(P)否定结论引入（否定结论引入（CP规则）规则）P E PQ P Q I R Q P R I RS P S I S Q P Q I F 的合取的合取现在学习的是第18页，共18页