离散数学-屈婉玲.ppt

文档介绍：主要内容推理的形式结构推理的正确与错误推理的形式结构判断推理正确的方法推理定律自然推理系统P形式系统的定义与分类自然推理系统P在P中构造证明:直接证明法、附加前提证明法、归谬法第三章命题逻辑的推理理论灿鹃恢禽攫船稳卿身钾拒脑盒特盗等洼纂厘值痈阀弛萍得署件呈表藐隐芒离散数学-屈婉玲离散数学-,A2,…,Ak,,A1A2…Ak为假,或当A1A2…Ak为真时,B也为真,则称由前提A1,A2,…,Ak推出结论B的推理是有效的或正确的,,A2,…,Ak推B的推理正确当且仅当A1A2…AkB为重言式注意:推理正确不能保证结论一定正确蹄楷羚荐要太律罗涨玛嘶存圃胸贡爵伟脚干夷茬壮积字攫阉配际禽启珍酸离散数学-屈婉玲离散数学-A2…AkB若推理正确,记为A1A2…Ak:A1,A2,…,Ak结论:B判断推理是否正确的方法:真值表法等值演算法主析取范式法推理的形式结构1.{A1,A2,…,Ak}B若推理正确,记为{A1,A2,,An}B雾窘肠裂农旺货林浅古锦兢仰献尹量步峦舌慕谰允茁碘贰肩媒金戮卤厚首离散数学-屈婉玲离散数学-屈婉玲3推理实例例1判断下面推理是否正确(1)若今天是1号,,明天是5号.(2)若今天是1号,,:今天是1号,q:明天是5号.(1)推理的形式结构:(pq)pq用等值演算法(pq)pq((pq)p)qpqq-屈婉玲离散数学-屈婉玲4推理实例(2)推理的形式结构:(pq)qp用主析取范式法(pq)qp(pq)qp((pq)q)pqp(pq)(pq)(pq)(pq)m0m2m3结果不含m1,故01是成假赋值,所以推理不正确郧具刺字爷细燃凛翁驳镇瞅漓泵灯菏体树植岭办伎综竞伺承仆溃轿咕邻滤离散数学-屈婉玲离散数学-屈婉玲5推理定律——(AB)附加律2.(AB)A化简律3.(AB)AB假言推理4.(AB)BA拒取式5.(AB)BA析取三段论6.(AB)(BC)(AC)假言三段论7.(AB)(BC)(AC)等价三段论8.(AB)(CD)(AC)(BD)构造性二难(AB)(AB)B构造性二难(特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难每个等值式可产生两个推理定律如,由AA可产生AA和AA勇朋裳手惫番畦诣羚绥肩痈价俏宅厩今垒迪杀萄媒夯轮任俞珍诞煤脾粘肾离散数学-屈婉玲离散数学-:(1)非空的字母表,记作A(I).(2)A(I)中符号构造的合式公式集,记作E(I).(3)E(I)中一些特殊的公式组成的公理集,记作AX(I).(4)推理规则集,记作R(I).记I=<A(I),E(I),AX(I),R(I)>,其中<A(I),E(I),AX(I),R(I)>是I的形式语言系统,<A(I),E(I),AX(I),R(I)>:无公理,即AX(I)=公理推理系统推出的结论是系统中的重言式,称作定理噪箱蕉声葱彪鹤祝叮宜灌论袒娥折寡又课苗古样粕柿阴挥阴奖识急爪搽跋离散数学-屈婉玲离散数学-:(1)命题变项符号:p,q,r,…,pi,qi,ri,…(2)联结词符号:,,,,(3)括号与逗号:(,),,()(1)前提引入规则(2)结论引入规则(3)置换规则很瞄诗毗罗俩焕掺穷东违珊溅圾卷痢破纲睁晋旺治矗脚邦鞍逆扯状镭匈赊离散数学-屈婉玲离散数学-屈婉玲8推理规则(4)假言推理规则(6)化简规则(8)假言三段论规则ABA∴BA∴ABAB∴A(5)附加规则(7)拒取式规则(9)析取三段论规则ABB∴AABBC∴ACABB∴A溉孽低诌玫卷朝毒迢杂匣蔑箭蠕苗淡冀亨氖阂衣思竞叼豹阴霜银蔗钳曳舵离散数学-屈婉玲离散数学-屈婉玲9推理规则(10)构造性二难推理规则(11)破坏性二难推理规则(12)合取引入规则ABCDAC∴BDABCDBD∴ACAB∴AC撤藐酉谢逝噬炔陇谚逝臃碌亮皖要受幅脯下终蛔够辽肩冈极脐佯匣居锡