离散数学命题逻辑课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《离散数学命题逻辑课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 命题逻辑 课件
- 资源描述:
-
1、1离散数学离散数学云南大学软件学院云南大学软件学院任课教师:谢仲文任课教师:谢仲文2013年秋季学期年秋季学期2绪论绪论 课程介绍和要求课程介绍和要求主要内容主要内容l教材说明教材说明l什么是离散数学?什么是离散数学?l为什么要学习离散数学?为什么要学习离散数学?l怎样学习离散数学?怎样学习离散数学?l课程要求与考试课程要求与考试3教材教材主教材:主教材:1、郝林等编著、郝林等编著.离散数学离散数学.北京北京:科学出版社科学出版社,2012年年5月月参考书目:参考书目:2、屈婉玲等编著、屈婉玲等编著.离散数学离散数学.北京北京:高等教育出版高等教育出版社,社,2008年年3月月3、左孝凌等编著
2、、左孝凌等编著.离散数学离散数学.上海上海:上海科学技上海科学技术文献出版社术文献出版社,2004年年1月月4问题问题l 什么是数理逻辑?(什么是数理逻辑?(符号化符号化+推理规则推理规则)l 经典数理逻辑经典数理逻辑和现代数理逻辑和现代数理逻辑主要内容主要内容l 命题逻辑命题逻辑l 谓词逻辑谓词逻辑l 推理与证明技术推理与证明技术第一部分第一部分 数理逻辑数理逻辑5第一讲第一讲 命题逻辑的基本概念命题逻辑的基本概念主要内容主要内容l命题与联结词命题与联结词 命题及其分类命题及其分类 联结词与复合命题联结词与复合命题l命题公式及其赋值命题公式及其赋值6命题与真值命题与真值 命题:命题:判断结果
3、惟一的陈述句判断结果惟一的陈述句 命题的命题的真值真值:判断的结果:判断的结果 真值的真值的取值范围取值范围:真与假:真与假 真命题与假命题真命题与假命题注意:注意:感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的陈述句中的悖论悖论,判断结果不惟一确定的不是命题,判断结果不惟一确定的不是命题 1.1 命题与联结词命题与联结词7悖论悖论如果有一个句子如果有一个句子B,如果,如果承认承认B,则可以推出,则可以推出非非B成立;成立;反之,如果承认反之,如果承认非非B,又可推出,又可推出B成立成立。例子:例子:1、我正在说假话。、我正在说假话。2、罗素的理发师悖论。、罗素的理
4、发师悖论。3、克里特人伊壁孟德、克里特人伊壁孟德:所有的克里特人都是撒谎者。所有的克里特人都是撒谎者。悖论不是命题!悖论不是命题!悖论的共同特征:悖论的共同特征:论断者属于论断主体集论断者属于论断主体集。8例例1 1 下列句子中那些是命题?下列句子中那些是命题?(1)是有理数是有理数.(2)2+5=7.(3)x+5 3.(4)你去教室吗?你去教室吗?(5)这个苹果真大呀!这个苹果真大呀!(6)请不要讲话!请不要讲话!(7)2050年元旦下大雪年元旦下大雪.2 假命题假命题命题概念命题概念 真命题真命题不是命题不是命题 不是命题不是命题 不是命题不是命题不是命题不是命题命题,但真值现在不知道命题
5、,但真值现在不知道判断给定句子是否为命题的方法和步骤:判断给定句子是否为命题的方法和步骤:1、判断它是否为陈述句;、判断它是否为陈述句;2、判断它是否有唯一的真值。、判断它是否有唯一的真值。9命题分类:命题分类:简单命题简单命题(也称原子命题)与(也称原子命题)与复合命题复合命题简单命题符号化简单命题符号化:命题常量:命题常量l 用小写英文字母用小写英文字母 p,q,r,pi,qi,ri(i 1)表示简单命表示简单命题题l 用用“1”或或“1”表示真,用表示真,用“0”或或“0”表示假表示假 例如,令例如,令 p:是有理数,(是有理数,(p 的真值为的真值为0)q:2+5=7,(,(q 的真值
6、为的真值为1)复合命题符号化复合命题符号化:由常量和:由常量和联结词联结词组成的公式组成的公式 2命题分类命题分类10否定、合取、析取联结词否定、合取、析取联结词定义定义1.3 设设p,q为两个命题,复合命题为两个命题,复合命题“p或或q”称作称作p与与q的的析取式析取式,记作,记作pq,称作称作析取联结词析取联结词.规定规定pq为假当为假当且仅当且仅当p与与q同时为假同时为假.定义定义1.1 设设 p为命题,复合命题为命题,复合命题“非非p”(或或“p的否定的否定”)称称为为p的的否定式否定式,记作,记作 p,符号,符号 称作称作否定联结词否定联结词.规定规定 p 为真当且仅当为真当且仅当p
7、为假为假.定义定义1.2 设设p,q为两个命题,复合命题为两个命题,复合命题“p并且并且q”(或或“p与与 q”)称为称为p与与q的的合取式合取式,记作,记作pq,称作称作合取联结词合取联结词.规定规定pq为真当且仅当为真当且仅当p与与q同时为真同时为真.11例例2 将下列命题符号化将下列命题符号化.(1)吴颖既用功又聪明吴颖既用功又聪明.(2)吴颖不仅用功而且聪明吴颖不仅用功而且聪明.(3)吴颖虽然聪明,但不用功吴颖虽然聪明,但不用功.(4)张辉与王丽都是三好生张辉与王丽都是三好生.(5)张辉与张辉与王丽是同学王丽是同学.合取联结词的实例合取联结词的实例12解解 令令p:吴颖用功吴颖用功,q
8、:吴颖聪明吴颖聪明(1)p q(2)p q(3)p q(4)设设p:张辉是三好生张辉是三好生,q:王丽是三好生王丽是三好生 p q(5)p:张辉与张辉与王丽是同学王丽是同学(1)(3)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性(4)(5)要求分清要求分清“与与”所联结的成分所联结的成分合取联结词的实例合取联结词的实例13例例3 将下列命题符号化将下列命题符号化(1)2 或或 4 是素数是素数.(2)2 或或 3 是素数是素数.(3)4 或或 6 是素数是素数.(4)小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨.(5)王小红生于王小红生于 1975 年或年或 197
9、6 年年.析取联结词的实例析取联结词的实例14解解 (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)(1)(3)为为相容或相容或(4)(5)为为排斥或排斥或合取和析取如何记忆?合取和析取如何记忆?析取联结词的实例析取联结词的实例15定义定义1.4 设设p,q为两个命题,复合
10、命题为两个命题,复合命题“如果如果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恒为真恒
11、为真(4)常出现的错误:不分充分与必要条件常出现的错误:不分充分与必要条件16例例4 设设 p:天冷,:天冷,q:小王穿羽绒服,将下列命题符号化:小王穿羽绒服,将下列命题符号化(1)只要天冷,小王就穿羽绒服只要天冷,小王就穿羽绒服.(2)因为天冷,所以小王穿羽绒服因为天冷,所以小王穿羽绒服.(3)若小王不穿羽绒服,则天不冷若小王不穿羽绒服,则天不冷.(4)只有天冷,小王才穿羽绒服只有天冷,小王才穿羽绒服.(5)除非天冷,小王才穿羽绒服除非天冷,小王才穿羽绒服.(6)除非小王穿羽绒服,否则天不冷除非小王穿羽绒服,否则天不冷.(7)如果天不冷,则小王不穿羽绒服如果天不冷,则小王不穿羽绒服.(8)小
12、王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.蕴涵联结词的实例蕴涵联结词的实例pq注意:注意:pq 与与 qp、p q等值(真值相同)等值(真值相同)pqpqqpqppqqpqp17定义定义1.5 设设 p,q为两个命题,复合命题为两个命题,复合命题“p当且仅当当且仅当q”称作称作p与与q的的等价式等价式,记作,记作pq,称作称作等价(双条件)联结词等价(双条件)联结词.规规定定pq为真当且仅当为真当且仅当p与与q同时为真或同时为假同时为真或同时为假.pq 的逻辑关系:的逻辑关系:p与与q互为充分必要条件互为充分必要条件等价联结词等价联结词例例5 5 求下列复合命题的真值求下列复合命题的
13、真值(1)2+2 4 当且仅当当且仅当 3+3 6.(2)2+2 4 当且仅当当且仅当 3 是偶数是偶数.(3)2+2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起.(4)2+2 4 当且仅当当且仅当 美国位于非洲美国位于非洲.(5)函数函数 0(x)在在 x0 可导的充要条件是可导的充要条件是 它在它在 x0 连续连续.1001018自学内容自学内容课本课本P8P9:l 四种次重要联结词四种次重要联结词19l 本小节中本小节中p,q,r,均表示命题均表示命题.l 联结词集为联结词集为,,p,p q,p q,pq,pq为为基本复合命题基本复合命题.其中要特别注意理解其中要特别注意理解pq
14、的涵义的涵义.反复使用反复使用,中的联结词组成更为复杂的复合命题中的联结词组成更为复杂的复合命题.l 复合命题的各个原子命题之间可以无任何实际联系。复合命题的各个原子命题之间可以无任何实际联系。设设 p:是无理数,是无理数,q:3是奇数,是奇数,r:苹果是方的,苹果是方的,s:太阳绕地球转太阳绕地球转 则复合命题则复合命题(pq)(rs)p)是假命题是假命题.2小结小结l 联结词的运算顺序:联结词的运算顺序:,同级按先出现者先运算同级按先出现者先运算.l 联结词的对称性。联结词的对称性。201.2 命题公式及其赋值命题公式及其赋值命题变项与合式公式命题变项与合式公式l 命题变项命题变项l 合式
15、公式合式公式l 合式公式的层次合式公式的层次公式的赋值公式的赋值l 公式赋值公式赋值l 公式类型公式类型l 真值表真值表21命题变项与合式公式命题变项与合式公式 命题常项、命题变项(命题变元):类比常量和变量。命题常项、命题变项(命题变元):类比常量和变量。常项与变项均用常项与变项均用 p,q,r,pi,qi,ri,等表示等表示.定义定义1.6 合式公式合式公式(简称公式)的递归定义:(简称公式)的递归定义:(1)单个命题变项和命题常项是合式公式单个命题变项和命题常项是合式公式,称作称作原子命题公式原子命题公式 (2)若若A是合式公式,则是合式公式,则(A)也是也是 (3)若若A,B是合式公式
16、,则是合式公式,则(A B),(A B),(AB),(AB)也是也是 (4)只有只有有限次有限次地应用地应用(1)(3)形成的符号串才是合式公式形成的符号串才是合式公式几点说明:几点说明:1、命题公式可以是没有真假值的;、命题公式可以是没有真假值的;2、并不是由命题常(变)元、联结词和一些括号组成的字符、并不是由命题常(变)元、联结词和一些括号组成的字符串都能成为命题公式串都能成为命题公式;3、递归定义:由、递归定义:由基础基础、归纳归纳和和界限界限组成。组成。22合式公式的层次合式公式的层次定义定义1.7(1)若公式若公式A是单个命题变项,则称是单个命题变项,则称A为为0层公式层公式.(2)
17、称称 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)分别为
18、分别为0层,层,1层,层,2层,层,3层,层,4层公式层公式.23第二讲第二讲 命题逻辑的等值演算命题逻辑的等值演算上一讲主要内容回顾:上一讲主要内容回顾:简单命题和复合命题、简单命题和复合命题、5个重要联结词;个重要联结词;命题常项和命题变项;命题常项和命题变项;公式的递归定义、公式的层次;公式的递归定义、公式的层次;第二讲主要内容第二讲主要内容1-4 真值表与等价公式真值表与等价公式1-5 重言式与蕴含式重言式与蕴含式24定义定义1.8 设设p1,p2,pn是出现在公式是出现在公式A中的全部中的全部命题变项命题变项,给给p1,p2,pn各指定一个真值各指定一个真值,称为对称为对A的一个的一
19、个赋值赋值或或解释解释.若使若使A为为1,则称这组值为则称这组值为A的的成真赋值成真赋值;若使若使A为为0,则称这组则称这组值为值为A的的成假赋值成假赋值.例:如例:如 000,010,101,110是是(pq)r的成真赋值的成真赋值 001,011,100,111是成假赋值是成假赋值.说明:说明:l A中仅出现中仅出现 p1,p2,pn,给,给A赋值赋值=1 2 n是指是指 p1=1,p2=2,pn=n,i=0或或1,i之间不加标点符号之间不加标点符号l A中仅出现中仅出现 p,q,r,给给A赋值赋值 1 2 3是指是指 p=1,q=2,r=3 思考:含思考:含n个命题变项的公式有多少个赋值
20、?个命题变项的公式有多少个赋值?公式赋值公式赋值25定义定义1-4.1 将命题公式将命题公式A在所有在所有赋值赋值下取值的情况列成表下取值的情况列成表,称称作作A的的真值表真值表.构造真值表的步骤构造真值表的步骤:(1)找出公式中所含的全部命题变项找出公式中所含的全部命题变项p1,p2,pn(若无下角标若无下角标 则按字母顺序排列则按字母顺序排列),列出列出2n个全部赋值个全部赋值,从从000开始开始,按按 二进制加法二进制加法,每次加每次加1,直至直至111为止为止.(2)按从低到高的顺序写出公式的各个按从低到高的顺序写出公式的各个层次层次.(3)对每个赋值依次计算各层次的真值对每个赋值依次
21、计算各层次的真值,直到直到最后计算出公式最后计算出公式 的真值为止的真值为止.真值表真值表26例例6 写出下列公式的真值表写出下列公式的真值表,并求它们的成真赋值和成假并求它们的成真赋值和成假 赋值赋值:(1)(p q)r (2)(qp)qp (3)(p q)q真值表真值表27(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 真值表真值表128(2)B(qp
22、)qp成真赋成真赋值值:00,01,10,11;无成假赋值无成假赋值p q qp(qp)q(qp)qp0 00 11 01 1101100011111真值表真值表229(3)C (p q)q的真值表的真值表成假赋值成假赋值:00,01,10,11;无成真赋值无成真赋值p q p p q (p q)(p q)q0 00 11 01 11100110100100000真值表真值表330问题思考问题思考1、回顾:含、回顾:含n个命题变元的公式共有多少个不同的个命题变元的公式共有多少个不同的赋值?赋值?2、含、含n个命题变元的个命题变元的真值表真值表共有多少种不同的真值共有多少种不同的真值情况?情况?
23、3、真值表与公式之间的关系?、真值表与公式之间的关系?31公式的类型公式的类型定义定义1.10 (1)若若A在它的任何赋值下均为真在它的任何赋值下均为真,则称则称A为为重言式重言式或或永永真式真式;(2)若若A在它的任何赋值下均为假在它的任何赋值下均为假,则称则称A为为矛盾式矛盾式或或永永假式假式;(3)若若A不是矛盾式不是矛盾式,则称则称A是是可满足式可满足式.由例由例1可知可知,(p q)r,(qp)qp,(p q)q 分别为非重言式的可满足式分别为非重言式的可满足式,重言式重言式,矛盾式矛盾式.思考:思考:重言式与可满足式、矛盾式之间的关系?重言式与可满足式、矛盾式之间的关系?32真值表
24、的用途真值表的用途 真值表可用于求出公式的真值表可用于求出公式的全部成真赋值与成假赋值全部成真赋值与成假赋值,判断公式的类型判断公式的类型注意:注意:1、如果两个公式的真值表对所有赋值最后一列都相、如果两个公式的真值表对所有赋值最后一列都相同,则称两个公式的同,则称两个公式的真值表相同真值表相同;2、真值表只考虑、真值表只考虑最后的结果最后的结果,而不考虑构造真值表,而不考虑构造真值表的中间过程。的中间过程。33等价公式概念等价公式概念两种定义:两种定义:1、给定两个命题公式、给定两个命题公式A和和B,设,设P1,P2,Pn为所为所有出现于有出现于A和和B中的原子变元,若给中的原子变元,若给P
25、1,P2,Pn任一组真值指派,任一组真值指派,A和和B的真值都相同,则称的真值都相同,则称A和和B是是等价公式等价公式或逻辑相等,记作或逻辑相等,记作AB。2、若等价式若等价式AB是重言式,则称是重言式,则称A与与B等值等值,记作,记作AB,并称,并称AB是是等值式,等值式,A和和B是是等价公式。等价公式。说明:说明:1、与与的区别;的区别;2、A或或B中可能有中可能有哑元哑元出现出现.例例 (pq)(p q)(r r)r为左边公式的哑元为左边公式的哑元.34等值式例题等值式例题例例1 判断下列各组公式是否等值判断下列各组公式是否等值:(1)p(qr)与与(p q)r 11111101 111
展开阅读全文