离散-1-5-题逻辑(1).ppt

主要内容:§:逻辑电路设计1实例:下午小王去看电影或去游泳。他没去看电影,所以他去游泳了。解:设P:小王下午去看电影;Q:小王下午去游泳;前提:P∨Q,┐P;结论:Q;推理形式:(P∨Q)┐PQ2实例2:在《四签名》开头,谈到逻辑推理时认为,即令一件日常用品,也可以根据找到的痕迹推出使用者的特征,于是华生拿出一只旧怀表,让福尔摩斯推断,我们看作者的一联串推理:表背面刻写姓名缩写,表系五十年前制造,表背刻字与制表时间相近推出其父为表的主人;已知其父已去世多年,又根据背景知识:珠宝一类多传给长子、又推出表后归其兄所有;表价值贵重推出其兄所获遗产丰厚;然而表背有无数划痕,推出其兄生话不检点;表四次送去典当推出其兄景况常潦倒;当而能换回推出有时景况很好;表钥匙孔伤痕累累推出其兄酗酒,生活不检点。这类推理属条件推理,知道前件,推出后件,3§(也称论证):,把从前题(公理或假设)出发,依据公认的推理规则,推导出结论,这一过程称为有效推理或形式证明,,而是推理的有效性。数理逻辑中,注重的是研究用来从前提导出结论的推理规则和论证原理,与这些规则和原理有关的理论称为推理理论。如果H1H2…HnC,则称C是一组前提H1,H2,…,Hn的有效结论,或称C是从前提H1,H2,…,Hn逻辑推出的结论。§。常用演绎证明方法:直接证法、附加前提法和反证法。在数理逻辑中,从前提推导出结论,要依据事先提供的公认的推理规则。推理规则:规则P(前提引入规则):在推导的任何步骤上都可引入前提。规则T(结论引入规则):在推导的任何步骤上所得到的结论都可在其后的任何步骤中引入使用。由基本蕴涵式/基本恒等式得出推理规则»当且仅当A1∧A2∧…∧AnB时,称5§:从前提(一组命题公式)出发,应用推理规则(蕴涵式恒等式),推导出结论(一个公式).例1证明下列推理有效:如果今天下大雨,则这里难通行;如果这里难通行,则他们不能准时达到。他们准时达到,所以今天没下大雨。证明:设P:::他们准时达到.(P→Q)∧(Q→┐R)∧R┐P证法1:P→Q前提Q→┐R前提P→┐R(1)(2)假言三段论R前提┐P(3)(4)拒取式»证法2:P→Q前提Q→┐R前提R前提┐Q(2)(3)拒取式┐P(1)(4)拒取式6§(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)前提Q∨R(1)(2)假言推论Q→┐P前提┐Q(1)(4)拒取式»(6)R(3)(5)析取三段论(7)S→┐R前提(8)┐S(6)(7)拒取式(9)P→┐SCP规则7§(归谬法)把结论的否定作为附加前提,与给定前提一起推证,若能引出矛盾,则说明结论是有效的。要证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)(P→Q)前提(4)Q(2)(3)假言推论(5)(Q→┐R)前提(6)┐R(4)(5)假言推论(7)R前提(8)R∧┐R(6)(7)8应用:逻辑电路设计(1)。命题变元---二值器件,如开关,电灯,电子管、晶体管等┐---非门、反相器---与门,串联---或门,并联化简电路电路设计非门:与门:或门:描述设计要求将设计要求表示成公式将公式化简画出逻辑电路图P┐PPQPQPQPQ9应用:数字逻辑电路设计(2)例:设计一个报警装置,其要求是:如果总经理室的人工控制开关合上,那么,当仓库的门被撬,或当工作人员尚未切断监视器电源,且通向仓库的通道有人时,:人工控制开关合上;Q:仓库的门被撬;R:监视器电源未切断;S:通向仓库的通道有人;W:报警器响输入端:P,Q,R,S;输出端:WWP(Q(RS))PQRSW方法2:列出输入/输出表构造主范式化简公式画