离散数学---推理理论

西华大学制作§1.6推理理论一、有效论证推理规则二、基本蕴涵式三、自然推理系统P四、推理证明的方法西华大学制作一、有效论证与推理规则•定义：A1∧A2∧…∧An→A,其为永真式，则称由前提A1,A2,…,An得到有效结论A；从前提公式得到有效结论的过程称为正确推理。•若AB是永真式，则记为AB；•若A→B是永真式，则记为AB。•前提一致和不一致：•如果前提A1∧A2∧…∧An为可满足式，则称为前提A1,A2,…,An一致。西华大学制作实例分析判断推理是否正确：张红不管有无空闲都不看电影。张红看了电影。所以张红有空闲时间又没有空闲时间。解：P:张红有空闲时间；Q：张红看电影。前提：A1=P∨P→QA2=Q结论：A=P∧P问题：该结论是否有效结论。(该推理是否正确)。01010000110111111101110110111100(P∨P→Q)∧Q→P∧PQP所以，结论A是有效结论；该推理是正确的。而前提是不一致的。西华大学制作基本蕴涵式名称蕴涵关系式化简式A∧BAA∧BB(A→B)A(A→B)B附加式AA∨BBA∨BAA→BBA→B假言推理(A→B)∧AB拒取式(A→B)∧BA析取三段式(A∨B)∧AB假言三段式(A→B)∧(B→C)A→C等价三段式(AB)∧(BC)AC二难推论(A→B)∧(C→D)∧(A∨C)B∨D西华大学制作(A→B)∧BA的证明AB(A→B)∧B→A0011111011001110001101110010西华大学制作法一、真值表法：011011110101011010111000(A→B)→BBA法二、利用等值演算法证明：证：(A→B)→B(A∨B)→B(A∨B)∨B(A∨B)∨BA∨(B∨B)A∨TT所以,(A→B)B(A→B)B的证明?第三种方法?西华大学制作自然推理系统P形式系统自然推理系统公理系统特点：只能从几个给定的公理出发，应用系统中的推理规则进行推演，得到的结论是系统中的定理。特点：可以从任意给定的前提出发，应用系统中的推理进行推演，得到的结论在系统中被认为是有效的。西华大学制作自然推理系统P自然推理系统P定义如下：1.字母表(1)命题常元，命题变元：P,Q,R,…,Pi,Qi,…,1,0(T,F)(2)命题联结词：、∧、∨、→、(3)括号：(,)2.合式公式：(略)3.推理规则：(1).前提引入规则(P规则)：在证明的任何步上，都可引入前提；(2).结论引用规则(T规则)：在证明的任何步上，所得的结论都可作为证明得前提；(3).置换规则：在证明的任何步上，命题公式的任何子命题公式都可以用与之等价的命题公式置换。(4).永真蕴涵规则：使用基本蕴涵式，常常将条件用‘，’分开。西华大学制作基本蕴涵式证明的另一种方法(A→B)B的证明证明：(A→B)(A∨B)A∧BA∧BB(简化式）(A→B)B的证明西华大学制作推理过程的证明形式规范化的形式：序号公式理由①B1E或I或P或…的合取或cp②B2..③B3..……注意：1)并非B1B2B32)Bi的获取：前提、中间结论西华大学制作构造下列的推理的证明：前提：P∨Q,P→R,S→M,S→R,M结论：Q。证：①MP②S→MP③S①②I拒取式④S→RP⑤R③④I假言推理⑥P→RP⑦P⑤⑥I拒取式⑧P∨QP⑨Q⑦⑧I析取三段式西华大学制作一公安人员审查一件案件。一致的事实如下：(1).张三或李四盗窃了录像机；(2).如果张三盗窃了录像机，则作案时间不能在午夜前；(3).如果李四证词正确，则午夜时屋内灯光未灭；(4).如果李四证词不正确，则作案时间在午夜前；(5).午夜时屋内灯灭了。①MP②S→MP③S①②I拒取式④S→RP⑤R③④I假言推理⑥P→RP⑦P⑤⑥I拒取式⑧P∨QP⑨Q⑦⑧I析取三段式解：将已知事实符号化：设P:张三盗窃录像机；Q:李四盗窃录像机;R:作案时间发生在午夜前；S:李四证词正确；M:午夜时灯光未灭。则前提为:(1)P∨Q,(2)P→R,(3)S→M,(4)S→R,(5)M。结论未定。所以，可以得出是李四盗了录像机。西华大学制作例如前提：p((r∧s)q)，p，s结论：q。证明：⑴pp规则⑵p((r∧s)q)p规则⑶(r∧s)q⑴⑵I⑷sp规则⑸s∨r⑷I⑹(r∧s)⑸E⑺q⑶⑹I西华大学制作推理证明的方法前提的合取→结论是永真式间接证明法推理证明演绎证明归纳证明直接证明法附加前提证法(CP)归谬法(反证法)西华大学制作附加前提证法(CP)针对这种情况：前提：A1，A2，…，An结论：A→B前提：A1，A2，…，An，A结论：B西华大学制作例：前提：P,P→(Q→R∧S)结论：Q→S证明：(1)Pcp规则(2)P→(Q→R∧S)cp规则(3)Q→R∧S(1)(2)I(4)Qcp规则(5)R∧S(3)(4)I(6)S(5)I课堂作业：前提：P∧Q→R，S∨P，Q结论：S→R西华大学制作归谬法(反证法)针对这种情况：前提：A1，A2，…，An结论：A前提：A1，A2，…，An，A结论：0（F）A(A)西华大学制作例：前提：R→Q，R∨S，S→Q，P→Q结论：P证明：①(P)否定结论引入（CP规则）②P①E③P→QP④Q②③I⑤R→QP⑥R④⑤I⑦R∨SP⑧S⑥⑦I⑨S→QP⑩Q⑧⑨I⑾F④⑩的合取