离散数学3PPT学习教案_第1页
离散数学3PPT学习教案_第2页
离散数学3PPT学习教案_第3页
离散数学3PPT学习教案_第4页
离散数学3PPT学习教案_第5页
已阅读5页,还剩19页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、会计学1 离散数学离散数学3 2 第一章 命题逻辑的推理理论 3.1 推理的形式结构 3.2 自然推理系统P 第1页/共24页 3 推理是指从一些已知的命题公式(称为前提)应用推理规则推演出另一些命题公式(称为结论)的过程。 定义3.1 设A1, A2, , Ak和B是命题公式,若对于A1, A2, , Ak, B中出现的命题变项的任一组赋值,要么A1A2Ak为假,要么A1A2Ak为真且B也为真, 则称由前提A1, A2, , Ak 推出B的推理是有效的(或正确的),并称B是有效的结论。 3.1 推理的形式结构 A1A2AkB永真 注: 1、由前提A1,A2,Ak 推结论B的推理是否正确与诸前

2、提的排列次序无关。 将一个推理诸前提的集合记为,则由推出结论B的推理记为 B。若该推理是正确的,则记为 B (或B), 否则记为 B (或 B)。称 B 和 A1,A2,Ak B为推理的形式结构。 第2页/共24页 4 2、设命题公式A1, A2, , Ak, B中共有n个命题变项。对于任一组 赋值1, 2, , n (i 取0或1, i=1,2, n), 前提和结论的取值 情况有如下四种: (1) A1A2 Ak 为0,B为0 (2) A1A2 Ak 为0,B为1 (3) A1A2 Ak 为1,B为0 (4) A1A2 Ak 为1,B为1 12k 0 0 , B= AA.A =1 1 , B

3、=1 按照定义,只要不出现(3),推理就是正确的。因而判断一个推理正确与否,只需判断是否会出现情况(3)即可。 3、推理正确,并不能保证结论B一定为真。因为前提可能是假的(情况(1)。 第3页/共24页 5 例3.1 判断下列推理是否正确 (1)p, pq q; (2)p, qp q 解:用真值表法 p qp(pq) qp(qp) q 0 0 0 1 1 0 1 1 (1) 从真值表可见,没有出现前提p(pq)为真,结论q为假的情况,故p, pq q。 (2) 在赋值为10时,出现了前提p(qp)为真而q为假的情况,故p,qp q。 0 0 0 1 0 0 0 1 0 0 1 0 1 11 1

4、 第4页/共24页 6 定理3.1 命题公式 A1,A2,Ak推 B的推理正确, 即A1,A2,Ak B当且仅当(A1A2Ak)B为重言式。 证明 见教材43页。 由该定理,推理的形式结构: A1,A2,AkB (3.1) 可用 (A1A2Ak)B (3.2) 表示。 判断推理是否正确的三种直接方法: 1、真值表法 2、等值演算法 3 、主析取范式法 或写成 前提:A1,A2,Ak 结论:B (3.5) 然后论证推理是否正确! 同时A1,A2,Ak B 换成A1A2Ak B 第5页/共24页 7 (1) 若a能被4整除,则a能被2整除。a 能被4整除,所以 a能被2 整除。 (2) 下午马芳或

5、去看电影或去游泳。她没去看电影,所以她去 游泳了。 (3) 若下午气温超过30,则王小燕必去游泳。若她去游泳, 她就不去看电影了。所以,若王小燕没去看电影,下午气温必 超过了30。 解:(1) 设p:a能被4整除; q:a能被2整除 前提:pq,p 结论:q 推理的形式结构:(pq)pq 由例3.1知道此推理正确,即(pq)p q。 例3.2 判断下列推理是否正确。 第6页/共24页 8 (2) 设 p: 马芳下午去看电影;q:马芳下午去游泳。 前提:pq, p 结论:q 推理的形式结构:(pq)p)q 我们用等值演算来检验该蕴含式是否为重言式。 (pq)p)q (pq)p)q (pq)p)q

6、 (pp)(qp)q qpq 1 可见(pq)p)q 是重言式,故(pq)p) q, 推理正确。 第7页/共24页 9 (3) 设p: 下午超过30;q:王小燕去游泳;r:王小燕去看电影。 前提:pq,q r 结论:rp 推理形式结构:(pq)(q r)(rp) 我们用主析取式法检验该蕴含式是否为重言式。 (pq)(q r)(rp) (pq)(q r)( rp) (pq)(q r )rp pr 两次吸收律 (pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr)(pqr) (用例2.11(1) m1 m3 m4m5 m6 m7 可见,主析取范式中少两个极小项m0和 m2,从而推

7、理不正确。 第8页/共24页 10 在研究推理过程中,人们发现了一些重要的重言蕴含式,并将它 们作为推理定律,在推理过程中可直接引用。常用的推理定律有: (1) 附加律: A AB (2) 化简律: AB A (3) 假言推理: (AB)A B (4) 拒取式: (AB)B A (5) 析取三段论: (AB)B A (6) 假言三段论: (AB)(BC) (AC) (7) 等价三段论: (AB)(BC) (AC) (8) 构造性二难: (AB)(CD)(AC) (BD) 构造性二难(特殊形式): (AB)(AB)(AA) B (9) 破坏性二难: (AB)(CD)(BD)(AC) 推理定律 第

8、9页/共24页 11 此外, 2.1中给出的24个等值式中的每一个都派生出两条推理定律. 比 如 A A产生出AA 和A A . 还有一些等值式和重言蕴含式可在推理中引用。如: A (AB)(AB) (AB) AB A(BC) (AB) C (AB) (AB)(AB) (AB) AB A AB B AB AB (AC)(BC) AB (AC)(BC) 第10页/共24页 12 “证明”是一个描述推理过程的命题公式序列,其中的每个公式或者是已知前提,或者是由某些前提应用推理规则得到的结论. 注: 前已述及,可以用真值表法、等值演算法和主析取范式法来判断推理是否正确。但当推理中包含的命题变项较多时

9、,这些方法的演算量很大.因而需要对推理进行严谨的证明。证明应在推理系统中进行. 3.2 自然推理系统 第11页/共24页 13 第12页/共24页 14 定义3.3 自然推理系统P由以下三部分要素组成: 1. 字母表: (1) 命题变项符号: p, q, r, (2) 联结词符号: , , (3)逗号与括号: ,, ( ) 2. 合式公式集 (合式公式的定义见定义1.6). 3. 推理规则: (1) 前提引入规则: 在证明的任何步骤上都可引入前提; (2) 结论引入规则: 在证明的任何步骤上所得到的结论都可做为 后续证明的前提. (3) 置换规则: 在证明的任何步骤上, 命题公式中的子公式都可

10、 以用与之等值的公式置换. P 第13页/共24页 15 推理规则推理规则 (4)假言推理规则 AB _A_ B (6)化简规则 AB_ A (7)拒绝式规则 AB _B_ A (5)附加规 则 _A_ AB (8)假言三段论规则 AB _BC_ AC (9)析取三段论规则 AB _B _ A (10)构造性二难推理规则 AB CD _AC_ BD (12)合取引入规则 A _B_ AB (11)破坏性二难推理规则 AB CD _BD_ AC 第14页/共24页 16 q qr r r(pq) 前提引入规则, 结论引入规则, 置换规则, 假言推理规则, 附加规则, 化简规则, 拒绝式规则,假言

11、三段论规则, 析取三段论规则, 构造性二难推理规则, 破坏性二难推理规则, 合取引入规则 例3.3 在自然推理系统P中构造下面推理的证明: (1) 前提: pq,qr,ps,s 结论: r(pq) qr r(pq) spqps pq r p q 证明: ps s p pq 合取 假言推理 拒取式 析取三段 式 前提引入 前提引入 拒取式 前提引入 析取三段式 前提引入 假言推理 合取 第15页/共24页 17 (2) 前提: pq, rq, rs 结论: ps 前提引入规则, 结论引入规则, 置换规则, 假言推理规则, 附加规则, 化简规则, 拒绝式规则,假言三段论规则, 析取三段论规则, 构

12、造性二难推理规则, 破坏性二难推理规则, 合取引入规则 证明: pq pq rq qr pr rs ps pr 假言三段论 pqrqrs ps rs pqqr 置换置换 假言三段论 前提引入 置换 前提引入 置换 假言三段论 前提引入 假言三段论 第16页/共24页 18 证明: ps p s p(qr) 例3.4 在自然推理系统P中构造下面推理的证明: 若数a 是实数, 则它不是有理数就是无理数。若a不能表示成分数, 则它 不是有理数。a 是实数且它不能表示成分数, 所以a是无理数。 解: 令 p: a是实数; q: a是有理数; r: a是无理数; s: a能表示成分数. 前提: p(qr

13、), s q, p s 结论: r qr s q q r p(qr)s qp s r q ps qr 析取三段论 假言推理 p 化简 假言推理 前提引入 化简 化简 前提引入 假言推理 前提引入 假言推理 析取三段论 第17页/共24页 19 1.附加前提证明法: 欲证 (A1A2 Ak)(AB), (A1A2Ak) (AB) (A1A2Ak) (AB) (A1 A2Ak A)B (A1A2Ak A) B (A1A2Ak A) B 可改证(A1A2AkA)B。 道理如下: 构造证明的两个技巧构造证明的两个技巧 第18页/共24页 20 例3.5 在自然推理系统P中构造下面推理的证明: 如果小张

14、和小王去看电影,则小李也去看电影。小赵不去看电影或小 张去看电影。小王去看电影。所以,当小赵去看电影时,小李必定也去。 解:令 p: 小张去看电影;q: 小王去看电影; r: 小李去看电影; s: 小赵去看电影。 前提:(pq) r, sp, q 结论:sr 证明:用附加前提法。 s sp p q pq (pq)r r r (pq) r spqs pq p 假言推理 合取 析取三段论 附加前提引入 前提引入 析取三段 论 前提引入 合取 前提引入 假言推理 附加前提证明法附加前提证明法 第19页/共24页 21 前提:(pq) r, sp, q 结论:sr 证明: sp s p (pq)r p

15、qr q pr s r s r (pq) r spq 析取三段论 直接证明法 s p p r pqr 置换 置换 假言三段论 前提引入 置换 前提引入 置换 前提引入 析取三段论 假言三段论 第20页/共24页 22 2.归谬法: 欲证 (A1A2 Ak)B, 道理如下: 若将B做为附加前提后能得出矛盾(比如得到AA), 则说明原推理正确。 (A1A2Ak ) B (A1A2Ak) B (A1A2Ak B) 可见,若A1A2AkB为矛盾式, 则A1A2AkB为重言式。 归谬法归谬法 第21页/共24页 23 如果小张守第一垒并且小李向B队投球,则A 队将取胜。或者A队未取 胜,或者A队成为联赛第一名。A队没有成为联赛第一名。小张守第一垒。 因此,小李没向 B队投球。 例3.6 在自然推理系统P 中构造下面推理的证明: 解:令 p: 小张守第一垒; q: 小李向B队投球; r: A队取胜; s: A队成为联赛第一名。 前提:(pq) r, rs, s, p 结论:q (pq) r rs s

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论