离散-3-1-命题逻辑.ppt

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

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

3、的任何步骤中引入使用。 由基本蕴涵式/基本恒等式得出推理规则 当且仅当 A1A2An B 时，称,4,1.5 推理理论 2.直接证法,直接证法: 从前提(一组命题公式)出发，应用推理规则(蕴涵式恒等式)， 推导出结论（一个公式）. 例1 证明下列推理有效:如果今天下大雨，则这里难通行；如果这里难通行， 则他们不能准时达到。他们准时达到，所以今天没下大雨。 证明：设 P: 今天下大雨. Q: 这里难通行. R: 他们准时达到. (PQ)(QR)R P,证法1： PQ 前提 QR 前提 PR (1)(2)假言三段论 R 前提 P (3)(4)拒取式,证法2： PQ 前提 QR 前提 R 前提 Q

4、(2)(3)拒取式 P (1)(4)拒取式,. -吴扬扬制-,5,1.5 推理理论 3.附加前提法(CP规则),如果欲推出的结论为条件式RC时，只需将其前件R加入到前提中, 作为附加前提，再去推出后件C即可。 要证 A1A2An AB, 只需证 A1A2AnA B (A1A2An)(AB) (A1A2An)(AB) (A1A2AnA)B (A1A2AnA)B 例2：证明：P(QR), QP, SR PS,P 附加前提 P(QR) 前提 QR (1)(2)假言推论 QP 前提 Q (1)(4)拒取式,(6) R (3)(5)析取三段论 (7) SR 前提 (8) S (6)(7)拒取式 (9)

5、PS CP规则,. -吴扬扬制-,6,1.5 推理理论 4.反证法(归谬法),把结论的否定作为附加前提，与给定前提一起推证，若能引出矛盾， 则说明结论是有效的。 要证 A1A2AnB,只需证A1A2AnB是永假式。,蕴涵式 恒等式,A1,A2,An,B不相容,例3：用反证法证明例1的(PQ)(QR)R P。 证明：（1） （P） 附加前提 （2） P (1)双重否定律 （3） (PQ) 前提 （4） Q (2)(3)假言推论 （5） (QR) 前提 （6） R (4)(5)假言推论 (7) R 前提 (8) RR (6)(7),7,应用: 逻辑电路设计(1),1938年C.Shannon的硕士

6、论文第一次把开关电路设计和二值逻辑联系起来。 命题变元 - 二值器件，如开关，电灯，电子管、晶体管等 - 非门、反相器 - 与门,串联 - 或门,并联 化简电路 电路设计,非门：,与门：,或门：,描述设计要求,将设计要求表示成公式,将公式化简,画出逻辑电路图,. -吴扬扬制-,8,应用: 数字逻辑电路设计（2）,例：设计一个报警装置，其要求是：如果总经理室的人工控制开关合上， 那么，当仓库的门被撬，或当工作人员尚未切断监视器电源，且 通向仓库的通道有人时，就必须报警. P:人工控制开关合上; Q: 仓库的门被撬; R:监视器电源未切断; S: 通向仓库的通道有人; W:报警器响 输入端: P,

7、Q,R,S; 输出端:W,W P(Q(RS),P Q R S,W,方法2：,列出输入/输出表,构造主范式,化简公式,画出电路图,. -吴扬扬制-,9,作业：P31 1(1)， 2(1)， 3(1),. -吴扬扬制-,10,基本永真蕴涵式：,附加式： P PQ 化简式： PQ P 假言推论： P(PQ) Q 假言三段论:(PQ)(QR) PR 析取三段论: P(PQ) Q 拒取式： Q(PQ) P,推理规则 直接证法 附加前提法 反证法,. -吴扬扬制-,11,基本逻辑恒等式（P9）,双重否定律：P P 补余律：PP T PP F 等幂律：PP P PP P 交换律：PQ QP PQ QP 结合律:(PQ)R P(QR) (PQ)R P(QR) 分配律: P(QR)(PQ