离散-3-1-命题逻辑

《离散-3-1-命题逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容：§1.5.1推理理论推理规则常用推理方法直接证法附加前提证法反证法应用：逻辑电路设计1.-吴扬扬制-§1.5推理理论推理(也称论证)：由已知命题得到新的命题的思维过程.逻辑学中,把从前题(公理或假设)出发,依据公认的推理规则,推导出结论,这一过程称为有效推理或形式证明,所得结论叫做有效结论.关心的不是结论的真实性,而是推理的有效性。数理逻辑中，注重的是研究用来从前提导出结论的推理规则和论证原理，与这些规则和原理有关的理论称为推理理论。如果H1H2…HnC,则称C是一组前提H1，H2，…，Hn的有效结论，或称C是从前提H1

2、，H2，…，Hn逻辑推出的结论。判断有效结论的方法：证明蕴涵关系演绎法：构造命题公式的一个有限序列：A1，A2，…，An其中：A1是某个前提Hi；Ai(i≥2)或是某个前提Hi，或是某些Aj(j＜i)的有效结论,并且An就是C，公式C称为该演绎的有效结论，或称从H1，…，Hn演绎出C。§1.5推理理论1.推理规则B称为推理规则的结论。常用演绎证明方法:直接证法、附加前提法和间接证法。在数理逻辑中，从前提推导出结论，要依据事先提供的公认的推理规则。推理规则：规则P(前提引入规则):在推导的任何步骤上都可引入前提。规则T(结论引入规则):在推

3、导的任何步骤上所得到的结论都可在其后的任何步骤中引入使用。由基本蕴涵式/基本恒等式得出推理规则»当且仅当A1∧A2∧…∧AnB时，称3.-吴扬扬制-§1.5推理理论2.直接证法直接证法:从前提(一组命题公式)出发，应用推理规则(蕴涵式恒等式)，推导出结论（一个公式）.例1证明下列推理有效:如果今天下大雨，则这里难通行；如果这里难通行，则他们不能准时达到。他们准时达到，所以今天没下大雨。证明：设P:今天下大雨.Q:这里难通行.R:他们准时达到.(P→Q)∧(Q→┐R)∧R┐P证法1：P→Q前提Q→┐R前提P→┐R(1)(2)假言三段论R

4、前提┐P(3)(4)拒取式»证法2：P→Q前提Q→┐R前提R前提┐Q(2)(3)拒取式┐P(1)(4)拒取式4§1.5推理理论3.附加前提法(CP规则)如果欲推出的结论为条件式R→C时，只需将其前件R加入到前提中,作为附加前提，再去推出后件C即可。要证A1∧A2∧…∧AnA→B,只需证A1∧A2∧…∧An∧AB∵(A1∧A2∧…∧An)→(A→B)┐(A1∧A2∧…∧An)∨(┐A∨B)┐(A1∧A2∧…∧An∧A)∨B(A1∧A2∧…∧An∧A)→B例2：证明：P→(Q∨R),Q→┐P,S→┐RP→┐SP附加前提P→(Q∨R

5、)前提Q∨R(1)(2)假言推论Q→┐P前提┐Q(1)(4)拒取式»(6)R(3)(5)析取三段论(7)S→┐R前提(8)┐S(6)(7)拒取式(9)P→┐SCP规则5.-吴扬扬制-§1.5推理理论4.反证法(归谬法)把结论的否定作为附加前提，与给定前提一起推证，若能引出矛盾，则说明结论是有效的。要证A1∧A2∧…∧AnB,只需证A1∧A2∧…∧An∧┐B是永假式。»蕴涵式»恒等式{A1,A2,…,An,┐B}不相容例3：用反证法证明例1的(P→Q)∧(Q→┐R)∧R┐P。证明：（1）┐（┐P）附加前提（2）P(1)双重否定律（3）(

6、P→Q)前提（4）Q(2)(3)假言推论（5）(Q→┐R)前提（6）┐R(4)(5)假言推论(7)R前提(8)R∧┐R(6)(7)6.-吴扬扬制-应用:逻辑电路设计(1)1938年C.Shannon的硕士论文第一次把开关电路设计和二值逻辑联系起来。命题变元---二值器件，如开关，电灯，电子管、晶体管等┐---非门、反相器---与门,串联---或门,并联化简电路电路设计非门：与门：或门：描述设计要求将设计要求表示成公式将公式化简画出逻辑电路图P┐PPQPQPQPQ7应用:数字逻辑电路设计（2）例：设计一个报警装置，其要求是：如果总经

7、理室的人工控制开关合上，那么，当仓库的门被撬，或当工作人员尚未切断监视器电源，且通向仓库的通道有人时，就必须报警.P:人工控制开关合上;Q:仓库的门被撬;R:监视器电源未切断;S:通向仓库的通道有人;W:报警器响输入端:P,Q,R,S;输出端:WWP(Q(RS))PQRSW方法2：列出输入/输出表构造主范式化简公式画出电路图8.-吴扬扬制-作业：P311(1)，2(1)，3(1)9.-吴扬扬制-基本永真蕴涵式：附加式：PP∨Q化简式：P∧QP假言推论：P∧(P→Q)Q假言三段论:(P→Q)∧(Q→R)P→R析取三段论:┐P

8、∧(P∨Q)Q拒取式：┐Q∧(P→Q)┐P«推理规则«直接证法«附加前提法«反证法10.-吴扬扬制-基本逻辑恒等式（P9）双重否定律：┐┐PP补余律：┐P∨PT┐P∧PF等幂律：P∨