离散数学-公开课一等奖优质课大赛微课获奖课件.pptx
《离散数学-公开课一等奖优质课大赛微课获奖课件.pptx》由会员分享,可在线阅读,更多相关《离散数学-公开课一等奖优质课大赛微课获奖课件.pptx(32页珍藏版)》请在咨信网上搜索。
主要内容主要内容命题逻辑基本概念命题逻辑基本概念命题逻辑等值演算命题逻辑等值演算命题逻辑推理理论命题逻辑推理理论一阶逻辑基本概念一阶逻辑基本概念一阶逻辑等值演算与推理一阶逻辑等值演算与推理第一部分第一部分 数理逻辑数理逻辑1第1页第1页第一章第一章 命题逻辑基本概念命题逻辑基本概念主要内容主要内容命题与联结词命题与联结词 命题及其分类命题及其分类 联结词与复合命题联结词与复合命题命题公式及其赋值命题公式及其赋值2第2页第2页命题与真值命题与真值 命题:判断结果惟一陈说句命题:判断结果惟一陈说句 命题真值:判断结果命题真值:判断结果 真值取值:真与假真值取值:真与假 真命题与假命题真命题与假命题注意:注意:感慨句、祈使句、疑问句都不是命题感慨句、祈使句、疑问句都不是命题陈说句中悖论,判断结果不惟一拟定不是命题陈说句中悖论,判断结果不惟一拟定不是命题 1.1 命题与联结词命题与联结词3第3页第3页例例1 1 下列句子中那些是命题?下列句子中那些是命题?(1)是有理数是有理数.(2)2+5=7.(3)x+5 3.(4)你去教室吗?你去教室吗?(5)这个苹果真大呀!这个苹果真大呀!(6)请不要发言!请不要发言!(7)2050年元旦下大雪年元旦下大雪.假命题假命题命题概念命题概念 真命题真命题不是命题不是命题 不是命题不是命题 不是命题不是命题不是命题不是命题命题,但真值现在不知道命题,但真值现在不知道4第4页第4页命题分类:简朴命题(也称原子命题)与复合命题命题分类:简朴命题(也称原子命题)与复合命题简朴命题符号化简朴命题符号化用小写英文字母用小写英文字母 p,q,r,pi,qi,ri(i 1)表示简朴命表示简朴命题题用用“1”表示真,用表示真,用“0”表示假表示假 比如,令比如,令 p:是有理数,则是有理数,则 p 真值为真值为0,q:2+5=7,则,则 q 真值为真值为1 命题分类命题分类5第5页第5页否认、合取、析取联结词否认、合取、析取联结词定义定义1.3 设设p,q为两个命题,复合命题为两个命题,复合命题“p或或q”称作称作p与与q析析取式取式,记作,记作pq,称作称作析取联结词析取联结词.要求要求pq为假当为假当且仅当且仅当p与与q同时为假同时为假.定义定义1.1 设设 p为命题,复合命题为命题,复合命题“非非p”(或或“p否认否认”)称为称为p否认式否认式,记作,记作 p,符号,符号 称作称作否认联结词否认联结词.要求要求 p 为真为真当且仅当当且仅当p为假为假.定义定义1.2 设设p,q为两个命题,复合命题为两个命题,复合命题“p并且并且q”(或或“p与与 q”)称为称为p与与q合取式合取式,记作,记作pq,称作称作合取联结词合取联结词.要要求求pq为真当且仅当为真当且仅当p与与q同时为真同时为真.6第6页第6页例例2 将下列命题符号化将下列命题符号化.(1)吴颖既用功又聪明吴颖既用功又聪明.(2)吴颖不但用功并且聪明吴颖不但用功并且聪明.(3)吴颖即使聪明,但不用功吴颖即使聪明,但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与张辉与王丽是同窗王丽是同窗.合取联结词实例合取联结词实例7第7页第7页解解 令令p:吴颖用功吴颖用功,q:吴颖聪明吴颖聪明(1)p q(2)p q(3)p q(4)设设p:张辉是三好生张辉是三好生,q:王丽是三好生王丽是三好生 p q(5)p:张辉与张辉与王丽是同窗王丽是同窗(1)(3)阐明描述合取式灵活性与多样性阐明描述合取式灵活性与多样性(4)(5)要求分清要求分清“与与”所联结成份所联结成份合取联结词实例合取联结词实例8第8页第8页例例3 将下列命题符号化将下列命题符号化(1)2 或或 4 是素数是素数.(2)2 或或 3 是素数是素数.(3)4 或或 6 是素数是素数.(4)小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.(5)王小红生于王小红生于 1975 年或年或 1976 年年.析取联结词实例析取联结词实例9第9页第9页解解 (1)令令p:2是素数是素数,q:4是素数是素数,p q(2)令令p:2是素数是素数,q:3是素数是素数,p q(3)令令p:4是素数是素数,q:6是素数是素数,p q(4)令令p:小元元拿一个苹果小元元拿一个苹果,q:小元元拿一个梨小元元拿一个梨 (pq)(p q)(5)p:王小红生于王小红生于 1975 年年,q:王小红生于王小红生于1976 年年,(pq)(p q)或或 p q(1)(3)为相容或为相容或(4)(5)为排斥或为排斥或,符号化时符号化时(5)可有两种形式,而可有两种形式,而(4)则不则不能能析取联结词实例析取联结词实例10第10页第10页定义定义1.4 设设p,q为两个命题,复合命题为两个命题,复合命题“假如假如p,则则q”称作称作p与与q蕴蕴涵式涵式,记作,记作pq,并称,并称p是蕴涵式是蕴涵式前件前件,q为蕴涵式为蕴涵式后后件件,称称作作蕴涵联结词蕴涵联结词.要求:要求:pq为假当且仅当为假当且仅当p为真为真q为假为假.蕴涵联结词蕴涵联结词(1)pq 逻辑关系:q为 p 必要条件(2)“假如 p,则 q”有很多不同表述方法:若p,就q 只要p,就q p仅当q 只有q 才p 除非q,才p 或 除非q,不然非p,(3)当 p 为假时,pq恒为真,称为空证实(4)常出现错误:不分充分与必要条件11第11页第11页例例4 设设 p:天冷,:天冷,q:小王穿羽绒服,将下列命题符号化:小王穿羽绒服,将下列命题符号化(1)只要天冷,小王就穿羽绒服只要天冷,小王就穿羽绒服.(2)由于天冷,因此小王穿羽绒服由于天冷,因此小王穿羽绒服.(3)若小王不穿羽绒服,则天不冷若小王不穿羽绒服,则天不冷.(4)只有天冷,小王才穿羽绒服只有天冷,小王才穿羽绒服.(5)除非天冷,小王才穿羽绒服除非天冷,小王才穿羽绒服.(6)除非小王穿羽绒服,不然天不冷除非小王穿羽绒服,不然天不冷.(7)假如天不冷,则小王不穿羽绒服假如天不冷,则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷时候小王穿羽绒服仅当天冷时候.蕴涵联结词实例蕴涵联结词实例pq注意:注意:pq 与与 qp 等值(真值相同)等值(真值相同)pqpqqpqppqqpqp12第12页第12页定义定义1.5 设设 p,q为两个命题,复合命题为两个命题,复合命题“p当且仅当当且仅当q”称作称作p与与q等价式等价式,记作,记作pq,称作称作等价联结词等价联结词.要求要求pq为真当且为真当且仅当仅当p与与q同时为真或同时为假同时为真或同时为假.pq 逻辑关系:逻辑关系:p与与q互为充足必要条件互为充足必要条件等价联结词等价联结词例例5 5 求下列复合命题真值求下列复合命题真值(1)2+2 4 当且仅当当且仅当 3+3 6.(2)2+2 4 当且仅当当且仅当 3 是偶数是偶数.(3)2+2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2+2 4 当且仅当当且仅当 美国位于非洲美国位于非洲.(5)函数函数 f(x)在在 x0 可导充要条件是可导充要条件是 它在它在 x0 连续连续.1001013第13页第13页本小节中本小节中p,q,r,均表示命题均表示命题.联结词集为联结词集为,,p,p q,p q,pq,pq为基本复合命题为基本复合命题.其中要尤其注意理解其中要尤其注意理解pq涵义涵义.重复使重复使用用,中联结词构成更为复杂复合命题中联结词构成更为复杂复合命题.设设 p:是无理数,是无理数,q:3是奇数,是奇数,r:苹果是方,苹果是方,s:太阳绕地球转太阳绕地球转 则复合命题则复合命题(pq)(rs)p)是假命题是假命题.小结小结联结词运算顺序:联结词运算顺序:,同级按先出现者先运算同级按先出现者先运算.14第14页第14页1.2 命题公式及其赋值命题公式及其赋值命题变项与合式公式命题变项与合式公式命题变项命题变项合式公式合式公式合式公式层次合式公式层次公式赋值公式赋值公式赋值公式赋值公式类型公式类型真值表真值表15第15页第15页命题变项与合式公式命题变项与合式公式 命题常项命题常项 命题变项(命题变元)命题变项(命题变元)常项与变项均用常项与变项均用 p,q,r,pi,qi,ri,等表示等表示.定义定义1.6 合式公式合式公式(简称公式)递归定义:(简称公式)递归定义:(1)单个命题变项和命题常项是合式公式单个命题变项和命题常项是合式公式,称作称作原子命题公式原子命题公式 (2)若若A是合式公式,则是合式公式,则(A)也是也是 (3)若若A,B是合式公式,则是合式公式,则(A B),(A B),(AB),(AB)也是也是 (4)只有有限次地应用只有有限次地应用(1)(3)形成符号串是合式公式形成符号串是合式公式几点阐明:几点阐明:归纳或递归定义归纳或递归定义,元语言与对象语言元语言与对象语言,外层括号能够省去外层括号能够省去16第16页第16页合式公式层次合式公式层次定义定义1.7(1)若公式若公式A是单个命题变项,则称是单个命题变项,则称A为为0层公式层公式.(2)称称 A 是是 n+1(n0)层公式是指下面情况之一:层公式是指下面情况之一:(a)A=B,B 是是 n 层公式;层公式;(b)A=B C,其中其中B,C 分别为分别为 i 层和层和 j 层公式,层公式,且且 n=max(i,j);(c)A=B C,其中其中 B,C 层次及层次及 n 同同(b);(d)A=BC,其中其中B,C 层次及层次及 n 同同(b);(e)A=BC,其中其中B,C 层次及层次及 n 同同(b).(3)若公式若公式A层次为层次为k,则称则称A为为k层公式层公式.比如比如 公式公式 A=p,B=p,C=pq,D=(pq)r,E=(p q)r)(r s)分别为分别为0层,层,1层,层,2层,层,3层,层,4层公式层公式.17第17页第17页定义定义1.8 设设p1,p2,pn是出现在公式是出现在公式A中所有命题变项中所有命题变项,给给p1,p2,pn各指定一个真值各指定一个真值,称为对称为对A一个一个赋值赋值或或解释解释.若使若使A为为1,则称这组值为则称这组值为A成真赋值成真赋值;若使若使A为为0,则称这组则称这组值为值为A成假赋值成假赋值.几点阐明:几点阐明:A中仅出现中仅出现 p1,p2,pn,给,给A赋值赋值=1 2 n是指是指 p1=1,p2=2,pn=n,i=0或或1,i之间不加标点符之间不加标点符号号 A中仅出现中仅出现 p,q,r,给给A赋值赋值 1 2 3是指是指 p=1,q=2,r=3 含含n个命题变项公式有个命题变项公式有2n个赋值个赋值.如如 000,010,101,110是是(pq)r成真赋值成真赋值 001,011,100,111是成假赋值是成假赋值.公式赋值公式赋值18第18页第18页定义定义1.9 将命题公式将命题公式A在所有赋值下取值情况列成表在所有赋值下取值情况列成表,称作称作A真值表真值表.结构真值表环节结构真值表环节:(1)找出公式中所含所有命题变项找出公式中所含所有命题变项p1,p2,pn(若无下角标若无下角标 则按字母顺序排列则按字母顺序排列),列出列出2n个所有赋值个所有赋值,从从000开始开始,按按 二进制加法二进制加法,每次加每次加1,直至直至111为止为止.(2)按从低到高顺序写出公式各个层次按从低到高顺序写出公式各个层次.(3)对每个赋值依次计算各层次真值对每个赋值依次计算各层次真值,直到最后计算出公式直到最后计算出公式 真值为止真值为止.真值表真值表19第19页第19页例例6 写出下列公式真值表写出下列公式真值表,并求它们成真赋值和成假并求它们成真赋值和成假 赋值赋值:(1)(p q)r (2)(qp)qp (3)(p q)q真值表真值表20第20页第20页(1)A=(p q)r成真成真赋值赋值:000,001,010,100,110;成假成假赋值赋值:011,101,111 p q rp q r(p q)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 真值表真值表121第21页第21页(2)B(qp)qp成真赋成真赋值值:00,01,10,11;无成假赋值无成假赋值p q qp(qp)q(qp)qp0 00 11 01 1101100011111真值表真值表222第22页第22页(3)C (p q)q真值表真值表成假赋值成假赋值:00,01,10,11;无成真赋值无成真赋值p q p p q (p q)(p q)q0 00 11 01 11100110100100000真值表真值表323第23页第23页公式类型公式类型定义定义1.10 (1)若若A在它任何赋值下均为真在它任何赋值下均为真,则称则称A为为重言式重言式或或永真式永真式;(2)若若A在它任何赋值下均为假在它任何赋值下均为假,则称则称A为为矛盾式矛盾式或或永假式永假式;(3)若若A不是矛盾式不是矛盾式,则称则称A是是可满足式可满足式.由例由例1可知可知,(p q)r,(qp)qp,(p q)q 分别为非重言式可满足式分别为非重言式可满足式,重言式重言式,矛盾式矛盾式.注意:重言式是可满足式,但反之不真注意:重言式是可满足式,但反之不真.真值表用途真值表用途:求出公式所有成真赋值与成假赋值求出公式所有成真赋值与成假赋值,判断公式类型判断公式类型24第24页第24页第一章第一章 习题课习题课主要内容主要内容命题、真值、简朴命题与复合命题、命题符号化命题、真值、简朴命题与复合命题、命题符号化联结词联结词,及复合命题符号化及复合命题符号化命题公式及层次命题公式及层次公式类型公式类型真值表及应用真值表及应用基本要求基本要求深刻理解各联结词逻辑关系深刻理解各联结词逻辑关系,纯熟地将命题符号化纯熟地将命题符号化会求复合命题真值会求复合命题真值深刻理解合式公式及重言式、矛盾式、可满足式等概念深刻理解合式公式及重言式、矛盾式、可满足式等概念纯熟地求公式真值表,并用它求公式成真赋值与成假赋值纯熟地求公式真值表,并用它求公式成真赋值与成假赋值及判断公式类型及判断公式类型25第25页第25页1.将下列命题符号化将下列命题符号化 (1)豆沙包是由面粉和红小豆做成豆沙包是由面粉和红小豆做成.(2)苹果树和梨树都是落叶乔木苹果树和梨树都是落叶乔木.(3)王小红或李大明是物理组组员王小红或李大明是物理组组员.(4)王小红或李大明中一人是物理组组员王小红或李大明中一人是物理组组员.(5)由于交通阻塞,他迟到了由于交通阻塞,他迟到了.(6)假如交通不阻塞,他就不会迟到假如交通不阻塞,他就不会迟到.(7)他没迟到,因此交通没阻塞他没迟到,因此交通没阻塞.(8)除非交通阻塞,不然他不会迟到除非交通阻塞,不然他不会迟到.(9)他迟到当且仅当交通阻塞他迟到当且仅当交通阻塞.设设 p:交通阻塞,交通阻塞,q:他迟到他迟到练习练习126第26页第26页提醒:提醒:分清复合命题与简朴命题分清复合命题与简朴命题分清相容或与排斥或分清相容或与排斥或分清必要与充足条件及充足必要条件分清必要与充足条件及充足必要条件答案答案:(1)是简朴命题是简朴命题 (2)是合取式是合取式 (3)是析取式(相容或)是析取式(相容或)(4)是析取式(排斥或)是析取式(排斥或)设设 p:交通阻塞,交通阻塞,q:他迟到他迟到 (5)pq,(6)pq或或qp (7)qp 或或pq,(8)qp或或 pq (9)pq 或或 pq可见可见(5)与与(7),(6)与与(8)相同(等值)相同(等值)练习练习1解答解答27第27页第27页2.设设 p:2是素数是素数 q:北京比天津人口多北京比天津人口多 r:美国首都是旧金山美国首都是旧金山 求下面命题真值求下面命题真值 (1)(p q)r (2)(q r)(pr)(3)(qr)(pr)(4)(qp)(pr)(rq)0练习练习210028第28页第28页3.用真值表判断下面公式类型用真值表判断下面公式类型 (1)p r(qp)(2)(pq)(qp)r (3)(pq)(pr)练习练习329第29页第29页练习练习3解答解答(1)p r(qp)矛盾式矛盾式p q rqp (qp)p r(qp)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11001111 00110000 00000000 30第30页第30页练习练习3解答解答(2)(pq)(qp)r 永真式永真式11111111 11110011 11110011 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1(pq)(qp)r qp pq p q r31第31页第31页练习练习3解答解答(3)(pq)(pr)非永真式可非永真式可满满足式足式p q rpq pr (pq)(pr)0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 11110011 11110101 11111001 32第32页第32页- 配套讲稿:
如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。
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。
关于本文