离散数学高等教育出版社屈婉玲市公开课一等奖百校联赛特等奖课件.pptx
《离散数学高等教育出版社屈婉玲市公开课一等奖百校联赛特等奖课件.pptx》由会员分享,可在线阅读,更多相关《离散数学高等教育出版社屈婉玲市公开课一等奖百校联赛特等奖课件.pptx(36页珍藏版)》请在咨信网上搜索。
1、主要内容主要内容一阶逻辑等值式与基本等值式一阶逻辑等值式与基本等值式置换规则、换名规则、代替规则置换规则、换名规则、代替规则前束范式前束范式自然推理系统自然推理系统NL 及其推理规则及其推理规则第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理1第1页5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则定义定义5.1 设设A,B是两个谓词公式是两个谓词公式,假如假如AB是永真式是永真式,则称则称A与与B等值等值,记作记作AB,并称并称AB是是等值式等值式基本等值式基本等值式第一组第一组 命题逻辑中命题逻辑中16组基本等值式代换实例组基本等值式代换实例 比如,比如,xF(x)xF(x
2、),xF(x)yG(y)xF(x)yG(y)等等第二组第二组 (1)消去量词等值式消去量词等值式 设设D=a1,a2,an xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)2第2页基本等值式基本等值式(2)量词否定等值式量词否定等值式 xA(x)x A(x)xA(x)x A(x)(3)量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式.A(x)是含是含 x 自由出现公式,自由出现公式,B 中不含中不含 x 自由出现自由出现 关于全称量词:关于全称量词:x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x
3、)3第3页基本等值式基本等值式 关于存在量词:关于存在量词:x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x)(4)量词分配等值式量词分配等值式 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意:注意:对对,对对 无分配律无分配律4第4页置换规则、换名规则、代替规则置换规则、换名规则、代替规则1.置换规则置换规则 设设(A)是含是含A公式公式,那么那么,若若AB,则则(A)(B).2.换名规则换名规则 设设A为一公式,将为一公式,将A中某量词辖域中个体变项全部约束中某量词辖域中个体变项全部约束
4、 出现及对应指导变元换成该量词辖域中未曾出现过个出现及对应指导变元换成该量词辖域中未曾出现过个 体变项符号,其余部分不变,设所得公式为体变项符号,其余部分不变,设所得公式为A,则,则AA.3.代替规则代替规则 设设A为一公式,将为一公式,将A中某个个体变项全部自由出现用中某个个体变项全部自由出现用A中中 未曾出现过个体变项符号代替,其余部分不变,设所得未曾出现过个体变项符号代替,其余部分不变,设所得 公式为公式为A,则,则AA.5第5页实例实例例例1 将下面命题用两种形式符号化将下面命题用两种形式符号化,并证实二者等值并证实二者等值:(1)没有不犯错误人没有不犯错误人解解 令令F(x):x是人
5、,是人,G(x):x犯错误犯错误.x(F(x)G(x)或或 x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)量词否定等值式量词否定等值式 x(F(x)G(x)置换置换 x(F(x)G(x)置换置换6第6页实例实例(2)不是全部人都爱看电影不是全部人都爱看电影解解 令令F(x):x是人,是人,G(x):爱看电影:爱看电影.x(F(x)G(x)或或 x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)量词否定等值式量词否定等值式 x(F(x)G(x)置换置换 x(F(x)G(x)置换置换7第7页实例实例例例2 将公式化成等值不含现有约束出现、又有自由出现将公式化成等值不含现有约
6、束出现、又有自由出现个体变项个体变项:x(F(x,y,z)yG(x,y,z)解解 x(F(x,y,z)yG(x,y,z)x(F(x,y,z)tG(x,t,z)换名规则换名规则 x t(F(x,y,z)G(x,t,z)辖域扩张等值式辖域扩张等值式或者或者 x(F(x,y,z)yG(x,y,z)x(F(x,u,z)yG(x,y,z)代替规则代替规则 x y(F(x,u,z)G(x,y,z)辖域扩张等值式辖域扩张等值式8第8页实例实例例例3 设个体域设个体域D=a,b,c,消去下述公式中量词消去下述公式中量词:(1)x y(F(x)G(y)解解 x y(F(x)G(y)(y(F(a)G(y)(y(F
7、(b)G(y)(y(F(c)G(y)(F(a)G(a)(F(a)G(b)(F(a)G(c)(F(b)G(a)(F(b)G(b)(F(b)G(c)(F(c)G(a)(F(c)G(b)(F(c)G(c)9第9页实例实例解法二解法二 x y(F(x)G(y)x(F(x)yG(y)辖域缩小等值式辖域缩小等值式 x(F(x)G(a)G(b)G(c)(F(a)G(a)G(b)G(c)(F(b)G(a)G(b)G(c)(F(c)G(a)G(b)G(c)10第10页实例实例(2)x yF(x,y)x yF(x,y)x(F(x,a)F(x,b)F(x,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(
8、b,b)F(b,c)(F(c,a)F(c,b)F(c,c)11第11页5.2 一阶逻辑前束范式一阶逻辑前束范式定义定义5.2 设设A为一个一阶逻辑公式,若为一个一阶逻辑公式,若A含有以下形式含有以下形式 Q1x1Q2x2QkxkB则称则称A为为前束范式前束范式,其中,其中Qi(1 i k)为为 或或,B为不含量词为不含量词公式公式.比如,比如,x(F(x)G(x)x y(F(x)(G(y)H(x,y)是前束范式是前束范式而而 x(F(x)G(x)x(F(x)y(G(y)H(x,y)不是前束范式,不是前束范式,12第12页前束范式存在定理前束范式存在定理定理定理5.1(前束范式存在定理)(前束范
9、式存在定理)一阶逻辑中任何公式都存在与之等值前束范式一阶逻辑中任何公式都存在与之等值前束范式例例4 求以下公式前束范式求以下公式前束范式 (1)x(M(x)F(x)解解 x(M(x)F(x)x(M(x)F(x)(量词否定等值式)(量词否定等值式)x(M(x)F(x)后两步结果都是前束范式,说明公式前束范式不惟一后两步结果都是前束范式,说明公式前束范式不惟一.13第13页求前束范式实例求前束范式实例 (2)xF(x)xG(x)解解 xF(x)xG(x)xF(x)x G(x)(量词否定等值式)(量词否定等值式)x(F(x)G(x)(量词分配等值式)(量词分配等值式)或或 xF(x)xG(x)xF(
10、x)x G(x)量词否定等值式量词否定等值式 xF(x)y G(y)换名规则换名规则 x y(F(x)G(y)辖域收缩扩张规则辖域收缩扩张规则14第14页求前束范式实例求前束范式实例(3)xF(x)y(G(x,y)H(y)或或 xF(x)y(G(z,y)H(y)代替规则代替规则 x y(F(x)(G(z,y)H(y)解解 xF(x)y(G(x,y)H(y)zF(z)y(G(x,y)H(y)换名规则换名规则 z y(F(z)(G(x,y)H(y)辖域收缩扩张规则辖域收缩扩张规则15第15页5.3 一阶逻辑推论理论一阶逻辑推论理论推理形式结构推理形式结构1.A1 A2Ak B 若次式是永真式若次式
11、是永真式,则称推理正确则称推理正确,记作记作A1 A2Ak B2.前提前提:A1,A2,Ak 结论结论:B推理定理推理定理:永真式蕴涵式永真式蕴涵式16第16页推理定理推理定理第一组第一组 命题逻辑推理定理代换实例命题逻辑推理定理代换实例 如如,xF(x)yG(y)xF(x)第二组第二组 基本等值式生成推理定理基本等值式生成推理定理 如如,xF(x)xF(x),xF(x)xF(x)xF(x)x F(x),x F(x)xF(x)第三组第三组 其它惯用推理定律其它惯用推理定律 (1)xA(x)xB(x)x(A(x)B(x)(2)x(A(x)B(x)xA(x)xB(x)(3)x(A(x)B(x)xA
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 高等教育出版社 屈婉玲市 公开 一等奖 联赛 特等奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。