离散数学第2章第3节.ppt
《离散数学第2章第3节.ppt》由会员分享,可在线阅读,更多相关《离散数学第2章第3节.ppt(52页珍藏版)》请在咨信网上搜索。
1、离离 散散 数数 学学Discrete Mathematics 山东科技大学山东科技大学信息科学与工程学院信息科学与工程学院.上次课回顾上次课回顾v指导变元、作用域、约束变元、自由变元、闭式指导变元、作用域、约束变元、自由变元、闭式v约束变元换名和自由变元代入约束变元换名和自由变元代入v有限论域客体变元的枚举有限论域客体变元的枚举v谓词公式赋值、谓词公式等价、永真式、不可满足谓词公式赋值、谓词公式等价、永真式、不可满足式、可满足式式、可满足式v谓词公式的等价式和蕴含式谓词公式的等价式和蕴含式.四、谓词演算的等价式和蕴含式四、谓词演算的等价式和蕴含式1、命题公式的推广、命题公式的推广v结论结论:
2、命题演算中的等价公式表和蕴含公式表都:命题演算中的等价公式表和蕴含公式表都可推广到谓词演算中使用。可推广到谓词演算中使用。命题演算的等价式命题演算的等价式谓词演算的等价式谓词演算的等价式.2、量词与联结词、量词与联结词之间的关系之间的关系v将量词前面将量词前面的移到量词后面去时,存在量词的移到量词后面去时,存在量词改为全称量词,全称量词改为存在量词;改为全称量词,全称量词改为存在量词;v反之,将量词后面的反之,将量词后面的移到量词前面去时,也移到量词前面去时,也要做相应的改变。要做相应的改变。(x)P(x)(x)P(x)(x)P(x)(x)P(x).这里这里A(x)是任意包括个体变元是任意包括
3、个体变元x的谓词公式,的谓词公式,B是不包括个体变元是不包括个体变元x的任意谓词公式。的任意谓词公式。3、量词扩张、量词扩张/收缩律收缩律(1).证明证明 当当B为真时为真时,左右两边都为真左右两边都为真;否则否则,B为假为假,此时左右此时左右两边都等价于两边都等价于(x)Ax)A(x)(x),证迄证迄.(x)Ax)A(x)B(x)B (x)(Ax)(A(x)B)(x)B).3、量词扩张、量词扩张/收缩律收缩律(2)这里这里A(x)是任意包括个体变元是任意包括个体变元x的谓词公式,的谓词公式,B是不包括个体变元是不包括个体变元x的任意谓词公式。的任意谓词公式。.证明证明(x)A(x)B(x)(
4、A(x)B)(B不含不含x)证证 (x)A(x)B (x)A(x)B 条件表达式条件表达式 (x)A(x)B 量词否定量词否定 (x)(A(x)B)量词辖域扩张量词辖域扩张 (x)(A(x)B)条件表达式条件表达式.证明证明 B(x)A(x)(x)(BA(x)(B不含不含x)证证 B(x)A(x)B(x)A(x)条件表达式条件表达式 (x)(BA(x)量词辖域扩张量词辖域扩张 (x)(BA(x)条件表达式条件表达式.4、量词与命题联结词之间的一些等价式、量词与命题联结词之间的一些等价式量词分配律量词分配律(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)
5、(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x).5、量词与命题联结词之间的一些蕴含式、量词与命题联结词之间的一些蕴含式(x)Ax)A(x)(x)(x)x)B(x)B(x)(x)(Ax)(A(x)(x)B B(x)(x)(x)(Ax)(A(x)B(x)(x)B(x)(x)Ax)A(x)(x)(x)Bx)B(x)(x)(x)Ax)A(x)(x)(x)x)B(x)B(x)(x)(Ax)(A(x)(x)B B(x)(x)(x)(Ax)(A(x)(x)B(x)B(x)(x)Ax)A(x)(x)(x)Bx)B(x)(x)(x)(Ax)(A(x)(x)B(x)B(x)(x)Ax)A(x)
6、(x)(x)Bx)B(x)(x).用分析法证明用分析法证明(x)A(x)(x)B(x)(x)(A(x)B(x)。证明证明 若若(x)(A(x)B(x)为为假假,则则必必有有个个体体a,使使A(a)B(a)为假为假;因此因此A(a),B(a)皆为假皆为假,所以所以(x)A(x)和和(x)B(x)为假,为假,即即(x)A(x)(x)B(x)为假。为假。故故(x)A(x)(x)B(x)(x)(A(x)B(x).表表 2 1 谓词演算中常用的等价式和蕴含式谓词演算中常用的等价式和蕴含式.6、多个量词的使用、多个量词的使用考虑两个量词的情况。更多量词的使用方法与其类似。考虑两个量词的情况。更多量词的使用
7、方法与其类似。对于二元谓词如果不考虑自由变元,可以有以下八种情况。对于二元谓词如果不考虑自由变元,可以有以下八种情况。全称量词与存在量词在公式中出现的次序,不能随意更换。全称量词与存在量词在公式中出现的次序,不能随意更换。用双向箭头表示等价,单向箭头表示蕴含,见它们之间的关系。用双向箭头表示等价,单向箭头表示蕴含,见它们之间的关系。.有两个等价关系:有两个等价关系:.具有两个量词的谓词公式有如下一些蕴含关系:具有两个量词的谓词公式有如下一些蕴含关系:.作业P66:3,4,5 P72:2a),4,7.定义定义2-6.1 一个合式公式称为前束范式,如果它有如下一个合式公式称为前束范式,如果它有如下
8、形式:形式:(Q1x1)(Q2x2)(Qkxk)A其中其中Qi(1ik)为为 或或,A为不含有量词的谓词公式。为不含有量词的谓词公式。v特别地,若谓词公式中无量词,则该公式也看作特别地,若谓词公式中无量词,则该公式也看作是前束范式。是前束范式。v前束范式的特点前束范式的特点:所有量词均非否定地出现在公式所有量词均非否定地出现在公式最前面,且它的辖域一直延伸到公式之末。最前面,且它的辖域一直延伸到公式之末。一、前束范式一、前束范式.例如,例如,(x)(y)(z)(P(x,y)Q(y,z)R(x,y)都是前束范式,都是前束范式,而而(x)P(x)(y)Q(y),(x)(P(x)(y)Q(x,y)不
9、是前束范式。不是前束范式。.定理定理2.6.1 (前束范式存在定理前束范式存在定理)任意谓词公式任意谓词公式A都有与都有与之等价的前束范式。之等价的前束范式。证明:证明:.前束范式的求取方法前束范式的求取方法.举例举例73页 例题1、例题2、例题3.例题例题2 化公式化公式(x x)(y y)()(z)(P(x,z)z)(P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)为前束为前束范式范式解解 原公式原公式(x x)(y y)()(z)(P(x,z)z)(P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)(x x)(y y)()(z)(
10、z)(P(x,z)P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)(x x)(y y)()(z)z)(u)u)(P(x,z)P(x,z)P(y,z)P(y,z)Q(x,y,u)Q(x,y,u).解解 第一步否定深入第一步否定深入原式原式第二步改名,以便把量词提到前面。第二步改名,以便把量词提到前面。例题例题3 把公式把公式将约束变元x改名为u,将约束变元y改名为z,化为前束范式化为前束范式.定义定义2-6.2 一个一个wffA称为前束合取范式,如果它有如下称为前束合取范式,如果它有如下形式:形式:(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21
11、A22A2l2)(Am1Am2Amlm)其中:其中:vQi(1ik)为量词为量词 或或,vxi(i=1,2,n)是客体变元,是客体变元,vAij是原子公式或其否定。是原子公式或其否定。二、前束合取范式二、前束合取范式.是前束合取范式是前束合取范式举例举例.定理定理2-6.2 每一个每一个wffA都可转化为与其等价的前束合都可转化为与其等价的前束合取范式。取范式。证明:略。证明:略。.例题例题4 将将wffD:转化为与其等价的前束合取范式。转化为与其等价的前束合取范式。解解 第一步取消多余量词第一步取消多余量词第二步换名第二步换名第三步消去条件联结词第三步消去条件联结词第四步将否定深入第四步将否
12、定深入第五步将量词推到左边第五步将量词推到左边D(x)(z)(w)(P(x)R(x,w)(Q(z,y)R(x,w)第六步化为合取范式第六步化为合取范式.求前束合取范式的方法求前束合取范式的方法第一步:消去多余量词第一步:消去多余量词第二步:换名第二步:换名第三步:消去条件联结词第三步:消去条件联结词第四步:将否定深入第四步:将否定深入第五步:将量词推到左边第五步:将量词推到左边第六步:化为合取范式第六步:化为合取范式.定义定义2-6.3 一个一个wffA称为前束析取范式,如果它有称为前束析取范式,如果它有如下形式:如下形式:(Q1x1)(Q2x2)(Qkxk)(A11A12A1l1)(A21A
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。