《离散数学推理理论.ppt》由会员分享，可在线阅读，更多相关《离散数学推理理论.ppt（18页珍藏版）》请在装配图网上搜索。
1、1.6 推理理论,一、有效论证推理规则 二、基本蕴涵式 三、自然推理系统P 四、推理证明的方法,一、有效论证与推理规则,定义：A1A2AnA,其为永真式，则称由前提A1,A2,An得到有效结论A；从前提公式得到有效结论的过程称为正确推理。 若AB是永真式，则记为AB； 若AB是永真式，则记为AB。 前提一致和不一致： 如果前提A1A2An为可满足式，则称为前提A1,A2,An一致。,实例分析,判断推理是否正确：张红不管有无空闲都不看电影。张红看了电影。所以张红有空闲时间又没有空闲时间。 解：P:张红有空闲时间；Q：张红看电影 。 前提：A1=P P Q A2=Q 结论：A=P P 问题：该结论
2、是否有效结论。(该推理是否正确)。,所以，结论A是有效结论；该推理是正确的。而前提是不一致的。,基本蕴涵式,(AB) B A的证明,法一、真值表法：,(AB) B的证明,?第三种方法?,自然推理系统P,形式系统,自然推理系统,公理系统,特点：只能从几个给定的公理出发，应用系统中的推理规则进行推演，得到的结论是系统中的定理。,特点：可以从任意给定的前提出发，应用系统中的推理进行推演，得到的结论在系统中被认为是有效的。,自然推理系统P,自然推理系统P定义如下： 1.字母表 (1)命题常元，命题变元：P,Q,R,Pi,Qi,1,0(T,F) (2)命题联结词：、 (3)括号：(,) 2.合式公式：(
3、略) 3.推理规则： (1).前提引入规则(P规则)：在证明的任何步上，都可引入前提； (2).结论引用规则(T规则)：在证明的任何步上，所得的结论都可作为证明得前提； (3).置换规则：在证明的任何步上，命题公式的任何子命题公式都可以用与之等价的命题公式置换。 (4).永真蕴涵规则：使用基本蕴涵式，常常将条件用，分开。,基本蕴涵式证明的另一种方法,(AB) B的证明 证明： (AB) ( AB) A B A B B (简化式）,(AB) B的证明,推理过程的证明形式,规范化的形式： 序号 公式 理由 B1 E 或 I 或 P 或 的合取 或 cp B2 . B3 . ,注意：1)并非B1B2
4、B3 2)Bi的获取：前提、中间结论,构造下列的推理的证明： 前提：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析取三段式,一公安人员审查一件案件。一致的事实如下： (1).张三或李四盗窃了录像机； (2).如果张三盗窃了录像机，则作案时间不能在午夜前； (3).如果李四证词正确，则午夜时屋内灯光未灭； (4).如果李四证词不正确，则作案时间在午夜前； (5).午夜时屋内灯灭了。, M P, SM P, S I拒取式, SR P, R I假言推理, P R P, P I拒
5、取式, PQ P, Q I析取三段式,解：将已知事实符号化： 设 P:张三盗窃录像机； Q:李四盗窃录像机; R:作案时间发生在午夜前； S:李四证词正确； M:午夜时灯光未灭。,则前提为: (1) PQ, (2)P R, (3)SM, (4)SR, (5) M。 结论未定。,所以，可以得出是李四盗了录像机。,例如,前提：p (rs)q)，p，s 结论：q。 证明： p p规则 p (rs)q) p规则 (rs)q I s p规则 s r I (rs) E q I,推理证明的方法,前提的合取结论 是永真式,间接证明法,推理证明,演绎证明,归纳证明,直接证明法,附加前提证法 (CP),归谬法(反
6、证法),附加前提证法(CP),针对这种情况： 前提： A1，A2，An 结论： AB,前提： A1，A2，An ，A 结论： B,例： 前提：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,归谬法(反证法),针对这种情况： 前提： A1，A2，An 结论： A,前提： A1，A2，An ，A 结论： 0 （F）,例： 前提：RQ，RS ，SQ，PQ 结论： P,证明： ( P) 否定结论引入（CP规则） P E PQ P Q I RQ P R I RS P S I SQ P Q I F 的合取,
离散数学推理理论.ppt
