![点击分享此内容可以赚币 分享](/master/images/share_but.png)
离散数学第1章重言式与蕴含式和其它连接词.ppt
《离散数学第1章重言式与蕴含式和其它连接词.ppt》由会员分享,可在线阅读,更多相关《离散数学第1章重言式与蕴含式和其它连接词.ppt(54页珍藏版)》请在咨信网上搜索。
1、1离离 散散 数数 学学Discrete Mathematics 山东科技大学山东科技大学信息科学与工程学院信息科学与工程学院2为什么要学习离散数学?李开复:给中国学生的第四封信给中国学生的第四封信大学四年应该这么度过大学四年应该这么度过数学是理工科学生必备的基础。很多学生在高中时认为数学是最难学的,到了大学里,一旦发现本专业对数学的要求不高,就会彻底放松对数学知识的学习,而且他们看不出数学知识有什么现实的应用或就业前景。但大家不要忘记,绝大多数理工科专业的知识体系都建立在数学的基石之上。例如,要例如,要想学好计算机工程专业,那至少要把离散数学(包括集合论、想学好计算机工程专业,那至少要把离散
2、数学(包括集合论、图论、数理逻辑等)、图论、数理逻辑等)、线性代数、概率统计和数学分析学好;要想进一步攻读计算机科学专业的硕士或博士学位,可能还需要更高的数学素养。3课程回顾第1次课:命题;5个联结词第2次课:合式公式命题的翻译命题公式等价的两种证明方法真值表利用命题定律推导第一章 命题逻辑 第3讲15 重言式与蕴含式 16 其他连结词重点:重言式、蕴含式难点:用推理方法证明蕴含式。5回顾PQPQ(PQ)PQPQ(PQ)(PQ)TT T F F F F TTF F T F T T TFT F T T F T TFF F T T T T T表1-4.46回顾 表 1-4.2 PQ PQP(PQ)
3、PTT T F FTF F F FFT F T FFF F T F7一、重言式和矛盾式一、重言式和矛盾式 定义定义1-5.1 给定一命题公式,若无论对分量作怎样的指派,其对应的真值永为T,则称该命题公式为重言式重言式或永真公式永真公式。定义定义1-5.2 给定一命题公式,若无论对分量作怎样的指派,其对应的真值永为F,则称该命题公式为矛盾式矛盾式或永假公式永假公式。对于矛盾式也有类似于定理1-5.1和定理1-5.2的结果。证明 由于重言式的真值与分量的指派无关,故对同一分量以任何合式公式置换后,重言式的真值仍永为T。口定理定理1-5.2 一个重言式,对同一分量都用任何合式公式置换,其结果仍为一重
4、言式。证明 设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为T,故ABT,ABT。口 定理定理1-5.1 任何两个重言式的合取或析取,仍然是一个重言式。因为重言式的否定是矛盾式,矛盾式的否定是重言式,这样只研究其一就可以了,后面将重点研究重言式。重言式最有用,因为它有以下特点:两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是,由简单的重言式可构造出复杂的重言式。由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。10证明重言式的方法证明重言式的方法v给定一命题公式,至少存在一个指派,公式相应确定真值为真,称为可满足式。v重言式必是可满足式,反之一般不真。v
5、判定给定公式是否为永真式、永假式或可满足式的问题,称为给定公式的判定问题。v在命题逻辑中,由于任何一个命题公式的指派数目总是有限的,所以命题逻辑的判定问题是可解的。其判定方法有真值表法和公式推演法。例题1 证明(PS)R)V(PS)R)为重言式。证明 因为PVPT,如以(PS)R)置换P即得 (PS)R)V(PS)R)T 定理定理1-5.3 设A、B为两个命题公式,A B当且仅当A B为一个重言式。证明 若AB,则A、B有相同真值,即A B永为T。若A B为重言式,则A B永为T,故A、B的真值相同,即AB。定理定理1-5.3的作用:为的作用:为A B又提供了一种方法。又提供了一种方法。其他方
6、法:其他方法:(1)真值表法)真值表法(2)利用命题定律推导证明)利用命题定律推导证明13例题2 证明(PQ)(PQ)证明:据定理1-5.3,只需证:(PQ)(PQ)为重言式。PQPQ(PQ)PQPQ(PQ)(PQ)TT T F F F F TTF F T F T T TFT F T T F T TFF F T T T T T二、蕴含式二、蕴含式 联结词 可用来表达。由第4节例题5可知:A B(AB)(BA)下面讨论AB的重言式。1.定义定义定义1-5.3 当且仅当PQ是一个重言式时,我们称“P蕴含Q”,并记作P Q。符号和的区别与联系类似于和的关系。区别:是逻辑联结词,属于对象语言中的符号,
7、是公式中的符号;不是联结词,属于元语言中的符号,表示两个公式之间的关系,不是两公式中符号。2.蕴含式的证明方法:(1)列真值表法:根据定义,只需证PQ是重言式(2)逻辑推论前真看后真后假看前假(3)等价置换 例题3 证明P PQ 证明 列出真值表:从表中看出PPQ是一个重言式,故P PQ成立。P Q PQPPQT T T TT F T TF T T TF F T T 证明 列出真值表:从表中看出PQP 不是一个重言式,故 PQ P不成立。P Q PQPQPT T T TT F T TF T T FF F F T例题4 考察PQ P是否成立。由例题3和例题4可知,PQ和QP不等价。对PQ来说,v
8、QP称作它的逆换式逆换式;vPQ称为它的反换式反换式;vQP称为它的逆反式逆反式。它们之间的关系如表所示。P Q PQPQ原式原式Q P 逆反式逆反式QP逆换式逆换式PQ 反换式反换式T T F F T T T TT F F T F F T TF T T F T T F FF F T T T T T T从表1-5.1中看出:(PQ)(QP)(QP)(PQ)因此要证明P Q,只需证明Q P,反之亦然。v要证明P Q,即证PQ是重言式。v对于PQ来说,除P的真值取T,Q的真值取F这样一种指派时,PQ的真值为F外,其余情况,PQ的真值为T。v要证PQ是重言式:(1)只要对条件命题PQ的前件P,指定真
9、值为T,若由此推出Q的真值也为T,则PQ是重言式,即P Q成立(前前真看后真真看后真);(2)同理,如条件命题PQ中,假定后件Q的真值取F,若由此推出P的真值为F,即推证了Q P 故P Q成立(后假看前假后假看前假)。例题1 推证Q(PQ)P 证法2(后假看前假)假定P为F,则P为T。(a):若Q为F,则PQ为F,Q(PQ)为F。(b):若Q为T,则Q为F,Q(PQ)为F。所以Q(PQ)P成立。证法1(前真看后真)假定Q(PQ)为T,则Q为T,且(PQ)为T。由Q为F,则必须P为F,故P为T。表 1-5.2 常用的蕴含重言式 PQ P1 PQ Q2 P PQ3 P PQ4 Q PQ5 (PQ)
10、P6 (PQ)Q7 P(PQ)Q8 Q(PQ)P9 P(PQ)Q10 (PQ)(QR)PR11 (PQ)(PR)(QR)R12 (PQ)(RS)(PR)(QS)13 (P Q)(Q R)(P R)14三、等价式和蕴含式的关系三、等价式和蕴含式的关系 就象联结词 和的关系一样,等价式与蕴含式之间也有紧密的联系。定理1-5.4 设P、Q为任意两个命题公式,PQ的充分必要条件是P Q且Q P。证明 若PQ,则P Q为重言式,因为P Q(PQ)(QP),故PQ为T且QP为T,即P Q,Q P成立。反之,若P Q且Q P,则,PQ为T且QP为T,因此P Q为T,P Q是重言式,即PQ。这个定理也可作为两
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 重言式 蕴含 其它 连接词
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。