最新离散数学3ppt课件.ppt

《最新离散数学3ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学3第一章命题逻辑的推理理论3.1推理的形式结构3.2自然推理系统P2DiscreteMath.推理是指从一些已知的命题公式（称为前提)应用推理规则推演出另一些命题公式（称为结论）的过程。定义3.1设A1,A2,…,Ak和B是命题公式，若对于A1,A2,…,Ak,B中出现的命题变项的任一组赋值，要么A1∧A2∧…∧Ak为假，要么A1∧A2∧…∧Ak为真且B也为真,则称由前提A1,A2,…,Ak推出B的推理是有效的（或正确的)，并称B是有效的结论。§3.1推理的形式结构A1∧A2∧…∧AkB永真注：1、由前提A1,A

2、2,…,Ak推结论B的推理是否正确与诸前提的排列次序无关。将一个推理诸前提的集合记为Г，则由Г推出结论B的推理记为Г├B。若该推理是正确的，则记为Г╞B(或ГB),否则记为Г⊭B(或Г⇏B)。称Г├B和{A1,A2,…,Ak}├B为推理的形式结构。3DiscreteMath.(1)若a能被4整除，则a能被2整除。a能被4整除，所以a能被2整除。(2)下午马芳或去看电影或去游泳。她没去看电影，所以她去游泳了。(3)若下午气温超过30℃，则王小燕必去游泳。若她去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温必超过

3、了30℃。解：(1)设p：a能被4整除；q：a能被2整除前提：p→q，p结论：q推理的形式结构：(p→q)∧p→q由例3.1知道此推理正确，即(p→q)∧pq。例3.2判断下列推理是否正确。7DiscreteMath.(2)设p:马芳下午去看电影；q：马芳下午去游泳。前提：p∨q,┐p结论：q推理的形式结构：((p∨q)∧┐p)→q我们用等值演算来检验该蕴含式是否为重言式。((p∨q)∧┐p)→q┐((p∨q)∧┐p)∨q(┐p∧┐q)∨p)∨q((┐p∨p)∧(┐q∨p))∨q┐q∨p∨q1可见((p∨q)∧

4、┐p)→q是重言式，故(p∨q)∧┐p)q,推理正确。8DiscreteMath.(3)设p:下午超过30℃；q：王小燕去游泳；r：王小燕去看电影。前提：p→q，q→┐r结论：┐r→p推理形式结构：((p→q)∧(q→┐r))→(┐r→p)我们用主析取式法检验该蕴含式是否为重言式。((p→q)∧(q→┐r))→(┐r→p)┐((┐p∨q)∧(┐q∨┐r))∨(r∨p)((p∧┐q)∨(q∧r))∨r∨pp∨r两次吸收律(p∧┐q∧┐r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨(p∧q∧r)∨(┐p∧┐q∧r)∨(┐

5、p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧r)(用例2.11(1))m1∨m3∨m4∨m5∨m6∨m7可见，主析取范式中少两个极小项m0和m2，从而推理不正确。9DiscreteMath.在研究推理过程中，人们发现了一些重要的重言蕴含式，并将它们作为推理定律，在推理过程中可直接引用。常用的推理定律有：(1)附加律:A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)等价三段论

6、:(A↔B)∧(B↔C)(A↔C)(8)构造性二难:(A→B)∧(C→D)∧(A∨C)(B∨D)构造性二难(特殊形式):(A→B)∧(┐A→B)∧(A∨┐A)B(9)破坏性二难:(A→B)∧(C→D)∧(┐B∨┐D)(┐A∨┐C)推理定律10DiscreteMath.此外,§2.1中给出的24个等值式中的每一个都派生出两条推理定律.比如┑┑AA产生出┑┑AA和A┑┑A.还有一些等值式和重言蕴含式可在推理中引用。如:A(A∧B)∨(A∧┐B)┐(A→B)A∧┐BA→(B→C)(A∧B)→C(A↔B)(A

7、∧B)∨(┐A∧┐B)┐(A↔B)A↔┐B┐AA→BBA→BA→B(A∨C)→(B∨C)A→B(A∧C)→(B∧C)11DiscreteMath.“证明”是一个描述推理过程的命题公式序列,其中的每个公式或者是已知前提,或者是由某些前提应用推理规则得到的结论.注:前已述及,可以用真值表法、等值演算法和主析取范式法来判断推理是否正确。但当推理中包含的命题变项较多时,这些方法的演算量很大.因而需要对推理进行严谨的证明。证明应在推理系统中进行.§3.2自然推理系统12DiscreteMath.形式系统定义3.2一个形式系

8、统I由下面四个部分组成：(1)非空的字母表集，记作A(I).(2)A(I)中符号构造的合式公式集，记作E(I).(3)E(I)中一些特殊的公式组成的公理集，记作AX(I).(4)推理规则集，记作R(I).这样可将I记为4元组.其中是I的形