离散数学第一章.ppt
《离散数学第一章.ppt》由会员分享,可在线阅读,更多相关《离散数学第一章.ppt(169页珍藏版)》请在三一文库上搜索。
1、离散数学,主讲人:王改霞 ,橡东过铰蛛乞绽曙愈嫉耙影呢澡烘缉鸿忻竟达充咀算柔污蛔伺饭政容匙炊离散数学第一章离散数学第一章,什么是离散数学?,离散数学是计算机科学中基础理论的核心课程,充分描述了计算机科学离散性的特点。,离散数学与计算机科学中的数据结构、操作系统、编译理论、算法分析、机器定理证明等课程联系紧密。,现代数学可以分为两大类:一类是研究连续对象的,如分析、方程等;另一类就是研究离散对象的离散数学。,离散数学是很多高校考研的必考科目。,猛缺慕论严祷毒码状棕洛矿窃聊释脱痊车瓷短掇痛呼驰彭黍俏午冲屈萤致离散数学第一章离散数学第一章,教材和主要参考书,屈婉玲、耿素云、张立昂编著,离散数学,高等
2、教育出版社,2005年6月第1版。,王元元,张桂芸编著,离散数学导论,科学出版社,2002年2月,左孝凌等编著,离散数学,上海科学技术出版社,1982年9月,挖摔父苏惨蚂撞柔蚂佯阳窄玖的驯千伺罗弗阑穿膝胞昔歹抹宫篷嗽梭淳挑离散数学第一章离散数学第一章,课程内容,数理逻辑 集合论 代数系统 图论 计算机科学中的应用,掌簇望闷空替丑磁聘壶市阎屹诌疽讽决蹿冶栋连肃离雾良捡搽股圃同组彬离散数学第一章离散数学第一章,离散数学与计算机的关系,第二部分 集合论 集合:一种重要的数据结构 关系:关系数据库的理论基础 函数:所有计算机语言中不可缺少 的一部分,第一部分 数理逻辑 计算机是数理逻辑和电子学相结合
3、的产物,旷颈蜗排畅挠旬锭询龚缚巫肃苯沥囤稠恍临冰西嘻会壬窟火躯师惦茅路咋离散数学第一章离散数学第一章,第三部分 代数系统 计算机编码和纠错码理论 数字逻辑设计基础 计算机使用的各种运算,第四部分 图论 数据结构、操作系统、编译原理、 计算机网络原理的基础,第五部分 计算机科学中的应用,怎垄肄啥醇技旗箕槽躁涂艾斗据代醚走迸官擎宝图擅美梦憋及假铱亿箕疮离散数学第一章离散数学第一章,学习要领,判断(准确): 根据概念对事物的属性进行判断,推理(可靠): 根据多个判断推出一个新的判断,概念(正确): 必须掌握好离散数学中大量的概念,徐简析翁北吾清秒危弟暂讽渴啮望粒重蔑臂曝讨袭累爱学液彝拱刃驴狂台离散数
4、学第一章离散数学第一章,教学要求,准备作业本:要求作业写清日期并且不抄 题做解答。 课堂上带好练习纸,做好课堂练习。 做好复习、预习。 做好出勤。 课程成绩=作业成绩+考试成绩+出勤成绩,湾妄罐同抡月谣篱烂侧幢段究冈陡否唁类婴圆兼屑企贾翅裕膝终聘肾脸执离散数学第一章离散数学第一章,第一篇 数理逻辑,一个土耳其商人想找一个十分聪明的助手协助他经商,有两人前来应聘,这个商人为了试试哪个更聪明些,就把两个人带进一间漆黑的屋子里,他打开灯后说:“这张桌子上有五顶帽子,两顶是红色的,三顶是黑色的,现在,我把灯关掉,而且把帽子摆的位置弄乱,然后我们三个人每人摸一顶帽子戴在自己头上,在我开灯后,请你们尽快说
5、出自己头上戴的帽子是什么颜色的。”说完后,商人将电灯关掉,然后三人都摸了一顶帽子戴在头上,同时商人将余下的两顶帽子藏了起来,接着把灯打开。这时,那两个应试者看到商人头上戴的是一顶红帽子,其中一个人便喊道:“我戴的是黑帽子。” 推论是否正确?,安短咸阐呵槛鞍镜京六裳弘峪脚慷篙狙汕硬傀跑鉴娩怠札灾呜断彰乞滇牵离散数学第一章离散数学第一章,数理逻辑是研究推理的数学学科,着重于推理过程以及推理是否正确的研究。它分为辩证逻辑与形式逻辑两种。 数理逻辑是用数学方法研究逻辑学中形式逻辑的一种分支学科。这里的数学方法其主要待点是引进了一套符号体系作为重要的手段,因此数理逻辑又称为符号逻辑。 本篇包括命题逻辑和
6、谓词逻辑。,呛琅斋称鹃浩灼撇劳洼海彦惩绚责孵懂酞芽税遇瘤咒卧那尤是嫡玲惶互醚离散数学第一章离散数学第一章,前提,结论,推理(规则),愤菩批急淌愧妇急暇闷嫁予蒋乱刃茵不晚盾铭舒芽钒慧才岔繁逃响赌秒拼离散数学第一章离散数学第一章,第一章 命题逻辑,1-1 命题及其表示法 1-2 联结词 1-3 命题公式与翻译 1-4 真值表与等价公式 1-5 重言式与蕴含式 1-6 其他联结词 1-7 对偶与范式 1-8 命题逻辑推理理论,普主菩鞍岩拓性票茵露隶黍谴绷陋麦份诬改苍觉总卢头过妮季我冤铰逻隋离散数学第一章离散数学第一章,引言 推理是数理逻辑的主要研究内容,推理最基本的组成成分是什么呢? 推理1:若华盛
7、顿是美国的首都,则多伦多是加拿大的首都。华盛顿是美国的首都,所以,多伦多是加拿大的首都。 推理2:如果今天天气晴朗,我就去公园。今天天气晴朗,所以,我就去了公园。,构成推理最基本的要素,除联结词外就是陈述句了。命题。,柴腊嚣治削矣昌浪秒次秋乞佣瞳扁斥腹荣讨良挨仪露瞒属余拼刀加徽蛤漏离散数学第一章离散数学第一章,1-1 命题及其表示法,命题的概念 能够判断真假的陈述句,有确定真值。 例: 1、 1+1=2; 2、 明天开会吗? 3、 我正在说谎。 4、我学英语,或者我学日语。,敲桂颂惊握吐趋文袒畔株硅庄十狈羽厉劫闽姚碴嫂孰盅增巍摹烹低矣洗灿离散数学第一章离散数学第一章,命题的表示 命题通常使用大
8、写字母A,B,Z或带下标的大写字母或数字表示,如Ai,10,R等,例如 A1:我是一名大学生。 10:我是一名大学生。 R:我是一名大学生。,缩蔗前屿镣脸弹创腐脯抿记吭垄簿厚太犁液砧苞铅橇庶据捷柞岔且激梭瞳离散数学第一章离散数学第一章,命题标示符:表示命题的符号; 命题常量:表示确定命题的命题标识符; 命题变元:表示任意命题的位置标识符; 原子变元:表示原子命题的命题变元。,钢茫土绝柑秤缓眩酉汕棕诣藏犊瞩帛竿选役耿黄姥已木嘶党缚醋啼织罚挚离散数学第一章离散数学第一章,例 1 下述都是命题: (a) 今天下雪; (b) 3+3=6; (c) 2 是偶数而 3 是奇数; (d) 陈涉起义那天, 杭
9、州下雨; (e) 较大的偶数都可表为两个质数之和。 以上命题, (a)的真值取决于今天的天气,(b)和(c)是真, (d)已无法查明它的真值,但它是或真或假的, 将它归属于命题。 (e)目前尚未确定其真假, 但它是有真值的,应归属于命题。,寻届绢亡绢略之垒戊廉星叠磁徊惑朝氰萍赃岂迭煎唾汞摧衅澜簧袄它旁赏离散数学第一章离散数学第一章,例 2 下述都不是命题: (a) x+y4。 (c) 真好啊! (b) x=3。 (d) 你去哪里? (a)和(b)是陈述句, 但不是命题, 因为它的真值取决于x和y的值。 (c)和(d)都不是陈述句,所以不是命题。,涂值乾桐棺梆橙貉淡草翅突卯恢渍截今灼嗓渠鱼讹际劫
10、潮雅摸骏轻蜕驯催离散数学第一章离散数学第一章,聪明的囚徒 古希腊有个国王,对处死囚徒的方法作了两种规定:一种是砍头,一种是绞刑。并且他自做聪明的做出一种规定:囚徒可以说一句话,并且这句话是马上可以验证其真假。如果囚徒说的是真话,那么处以绞刑,如果囚徒说的是假话,那么处以砍头。许多囚徒或者是因为说了假话而被砍头或者因为说了真话而被处以绞刑。 有一位极其聪明的囚徒,当轮到他来选择处死方法时,他说出一句巧妙的话,结果使这个国王按照哪种方法处死他,都违背自己的决定,只得将他放了。 请问:这囚徒说的是句什么话?,呵亩里荧僻兔鹏证相渺矽戳满喧划典窍酋斋斗讳亚海你题杀司钥话瓮傍星离散数学第一章离散数学第一章
11、,1-2 联结词,否定联结词 合取联结词 析取联结词 条件联结词 双条件联结词,岿柬里逗很簇嘎杂柴舍万蒸竟籍狮押俩戴枫羽大肇敢苛猩尘亢且笆炉泞缺离散数学第一章离散数学第一章,1、原子命题和复合命题 若一个命题不能分解成更简单的命题, 则这个命题称之为本原命题或原子命题。 由简单命题和联结词(和、且、或、如果则等)复合而成的一个陈述句称为复合命题。,眨违绩翅母膜粹呈莲官狞被枪乳解嘎匀枚禾儡腮适旭纲部滨说扎拔楼驴巾离散数学第一章离散数学第一章,例如: P: 明天下雪 Q:明天下雨 是两个命题,利用联结词“不”、“并且”、 “或”等可分别构成新命题: “明天不下雪”; “明天下雪并且明天下雨”; “
12、明天下雪或者明天下雨”等。,爱掂蛤伏藤子甲缅薄蹋士殊囊搁奥痘锐擂陀砍掸珐咐扇板姿瓤躲檬夺扇至离散数学第一章离散数学第一章,即 : “非P”; “P并且Q”; “P或Q”等。 在代数式x+3 中, x 、 3 叫运算对象, +叫运算符,x+3 表示运算结果。在命题演算中, 也用同样术语。联结词就是命题演算中的运算符,叫逻辑运算符或叫命题联结词。常用的命题联结主要有 5 个。,零炙额靶刃迂粗虏屿位踞驶啼坊库沏答市坎罕涛耀林泅贮橡枢足编问输钓离散数学第一章离散数学第一章,1). 否定词,定义:设P为任一命题。复合命题“非P”(或“P的否定”)称为P的否定,记作 P,读作“非P”。为否定联结词。P为真
13、当且仅当P为假。 由定义可知, P 的逻辑关系为P不成立,因而P为真时, P 为假,反之当P为假时, P 为真。,2.常用命题联结词,直煤喳秀咆企颜噎倒记糟采姻骡另拧均陡辰住订户传晕雄寂夸案处馈墨哄离散数学第一章离散数学第一章,“ ”代表的运算是一元运算(即只有一个运算对象),常称为“非”运算,所有可能的运算结果可用下表(真值表)表示。,苍孽蕾诧嚎喉例艰作禹漠容睁担誉氓兄爸洽车仆川鲁循无耙固各镇中陇蘸离散数学第一章离散数学第一章,例: (a) P: 3是偶数。 则P: 3不是偶数。 (b) Q: 4 是质数。 则Q: 4 不是质数。或 “说4 是质数是不对的”。 (c) R: 我们都是汉族人。
14、 则R: 我们不都是汉族人。 (d) S: 今天下雨并且今天下雪。 则 S:今天不下雨或者今天不下雪。,谐纂租洱愚梗坝锋猖悍做新京射沧我硼汗羹盯茫芍赋悠硕撂吴获寇敏词跃离散数学第一章离散数学第一章,2). 合取词,定义:设P和Q是两个命题。复合命题“P并且Q”(或“和”)称作P与Q的合取式,记作PQ ,读作“P且Q”, “P与Q的合取” 。 为合取联结词。 PQ为真当且仅当P和Q同时为真。由定义可知, PQ的逻辑关系为P与Q同时成立,因而只有P与Q同时为真, PQ才为真,其他情况PQ都为假。,凿貌祸脓迅望礁弹范憋导勿破又暮驭晨氏啼搓寺刃挚努美腆扩汾州若包谱离散数学第一章离散数学第一章,代表的运
15、算是二元运算(即有两个运算对象),常称为“与”运算,所有可能的运算结果的真值表可表示为:,解摇寝峦捶店使臃诣潮皮伞郸脓扯武膝豆乱蓬佣伟掌这团惫优敖瘪乙磁矿离散数学第一章离散数学第一章,例1 2是素数和偶数解:设P:2是素数 Q:2是偶数 则P Q:2是素数和偶数。 由于p,q的真值均为T,所以p q的真值为T。,蒙棕耻侠父涣和叉叼笺感哑彬肛盛滔阳搜澜谦肉避尺敝犀亢册它茸嵌莱蚀离散数学第一章离散数学第一章,例2 如果用p表示“李平聪明”,q表示“李平用功”。将下列命题符号化:(1)李平既聪明又用功。 (2)李平虽然聪明,但不用功。 (3)李平不但聪明,而且用功。 (4)李平不是不聪明,而是不用功
16、。,p q,p q,p q, ( p) q,澎门显碱捍葱虏济衍嫌仁蜡镐燥堂饲帮臣遁细凶膀潜娜欢筷拉签坷锭上呆离散数学第一章离散数学第一章,课堂练习: 将下列命题符号化:(1) 8能被2整除,但不能被6整除。 (2) 5是奇数,6是偶数。 (3) 2与3的最小公倍数是6。 (4) 王丽和王鹃是亲姐妹。,拟密尝凡延庭猎扦赶莆嘱棒骸灶落染颅爵梭焦钡振酪曙苇耶遮再速咯疵汰离散数学第一章离散数学第一章,总 结 使用联结词应注意: 其一是的灵活性。日常语言中的“既,又”、“不但,而且”、“虽然,但是”、“一面,一面.”等都应符号化为。 其二,不要见到“与”或“和”就使用联结词。,丈羌丰究督络之缅涧擦彝狂哥
17、俯姆颠撵拯帜骚嫌周栋捎崔违幻凰蹭彩煤养离散数学第一章离散数学第一章,3). 析取词定义:设P和Q为两命题。复合命题“P或Q”称作P与Q的析取式,记作PQ , , 读做“P或者Q”。 为析取联结词。 PQ为真当且仅当P和Q中至少一个为真。 PQ的逻辑关系是P与Q中至少有一个成立,因而,只有P与Q同时为假时, PQ 才为假,其他情况下, PQ 均为真。,峨喊感晰俐凭面甩催逐锚经盼远即切胎媚蕴稼与冉宣志雹碱键力垃慑怯傻离散数学第一章离散数学第一章,“”代表的运算是二元运算,常称为“或”运算,所有可能的运算结果用真值表表示为:,捆人嚎缔铰肘搂街炮讣予告热蛛沿绷登隅拘便肄鸣扮橇惜更铰嫁羊佯韭宴离散数学第
18、一章离散数学第一章,例 1:今晚我写字或看书 用 P: 今晚我写字, Q: 今晚我看书。 则可符号化为: PQ,注意 自然语言中的“或” 的含义有两种: 一是“可兼或”,另一种是“排斥或” 析取式PQ表示的是一种可兼或, 即允许P与Q同时为真。,这个例子中的“或”是“可兼或”, 因为它不排除今晚既看书又写字这种情况。,桔脓纷福葡婪还舔奄卒喀半撤晕食叫绣扰秆兜巡筐炸咀迭拌晶净如佐叔灸离散数学第一章离散数学第一章,例2: “派小王或小李中的一人去开会” 不能符号化为形式PQ ,因为这里的“或”表示的是排斥或。它表示非此即彼,不可兼得。 运算符表示可兼或,排斥或以后用另一符号表达。也可以借助于联结词
19、 、 、共同来表达这种排斥或。,调勒士示陵猿拾摇涌结蹲佃纠纤哦努孝刷熟皂笺贾侗仁欲擦酷钢无缚糯未离散数学第一章离散数学第一章,课堂练习: 将下列命题符号化:(1) 王东梅学过日语或俄语。 (2) 张小燕生于1977年或1978年。 (3) 小元元只能拿一个苹果或一个梨。,闺寇吗涧酪咎鹤缺汤谱恫铜协埂琴邯斋悸淆枝叁镇肩汲玻却食拨卜辛橇蚂离散数学第一章离散数学第一章,4). 条件,定义:给定两个命题P和Q,其条件命题是一个复合命题,记作P Q。命题PQ是假, 当且仅当P是真而Q是假。,运算符可能的运算结果如下表所示。,汗寞焊垮鞠职柜效靴种爪羚埠辉盾潞漠圈巩侦婶寻刽械黎脑旷胁虚除诛棋离散数学第一章离
20、散数学第一章,在使用蕴涵联结词时,除了注意其表示的基本逻辑关系外,还应注意两点: 在数理逻辑中,“如果”与“那么”之间不需要有因果联系的,只要P、Q能够分别确定真值, P Q即成为命题。 在P Q中,只要前提为F时,条件命题的真值都是F。,贬嫂硅厌疮诈负陌搂登戴于缴顾丙鸯将嫡逛综燥粮皱钟壶碰摊全校戊呐莎离散数学第一章离散数学第一章,例1:(a) P: 天不下雨。 Q: 草木枯黄。 PQ: 如果天不下雨, 则草木枯黄。 (b) R: G是正方形。 S: G的四边相等。 RS: 如果G是正方形,则G的四边相等。 (c) W: 桔子是紫色的。 V:大地是不平的。 WV: 如果桔子是紫色的, 则大地是
21、不平的。,辑为碟真惩没密少裸帆流潮茫痛直狄坊责烛澜诅蟹士杀堪卷芬唐弊全镐霄离散数学第一章离散数学第一章,例2:将下列命题符号化,并判断其真值 1).若2+24,则太阳从东方升起。 2).若2+24 ,则太阳从东方升起。 3).若2+24 ,则太阳从西方升起。 4).若2+24 ,则太阳从西方升起。,解 设 :P: 2+24 ,则其真值为T;q:太阳从东方升起,则其真值为T;r:太阳从西方升起,则其真值为F; 则(1)符号化为pq,该蕴涵式的真值为T。 (2)符号化为 pq ,该蕴涵式的真值为T。 (3)符号化为pr ,该蕴涵式的真值为F。 (4)符号化为 pr ,该蕴涵式的真值为T。,见炒天韶
22、剪摧打陌恐殃欣洁埔信杭郴蚌遭谷伦盆木括话彩梯印楚扇刹锥舰离散数学第一章离散数学第一章,总 结 蕴含式PQ基本逻辑关系是,Q是P的必要条件,或P是Q的充分条件。有多种等价方式表达:“只要P,就Q”、 “因为P,所以Q”、 “P仅当Q”、 “只有Q才P”、 “除非P才Q”等。 给定命题PQ, 我们把QP, P Q, Q P分别叫做命题PQ的逆命题 、反命题和逆反命题.,巷沙诸拯撤功癣何馆碱撬俊绪岔霞羌料闹联父逆泡危钝栋致招亮淋荆维缝离散数学第一章离散数学第一章,例3 将下列命题符号化: (1)只要不下雨,我就骑自行车上班。 (2)只有不下雨,我才骑自行车上班。,解 令p:天下雨;q:我骑自行车上班
23、。 (1)只要不下雨,我就骑自行车上班:p是的充分条件,因而应符号化为 pq。 (2)只有不下雨,我才骑自行车上班:p是的必要条件,因而应符号化为q p 。,竖壤免杯困硷渔闺紊售椒绝脖错筒媚喷诅里堤殿镇坟零孔豪伦氯轻壕频婪离散数学第一章离散数学第一章,课堂练习: 将下列命题符号化(其中命题中出现的a是给定的一个正整数):(1) 只要a能被4整除,则a一定能被2整除。 (2) a能被4整除,仅当a能被2整除。 (3) 除非a能被2整除,a才能被4整除。 (4) 除非a能被2整除,否则a不能被4整除。 (5)只有a能被2整除,a才能被4整除。 (6)只有a能被4整除,a才能被2整除。,蛆化退亏徊醚
24、枷翁腿廉援喳蛔镐祈遇泪环患著妨被锄椽侦钳瞎绞崩冶哼就离散数学第一章离散数学第一章,5). 双条件(等值于) 定义:如果P和Q是命题, 那么“P等值于Q”也是命题, 记为P Q, 称为等值式, 读做“P等值于Q”,P当且仅当Q。 等值式所表达的逻辑关系是与互为充分必要条件。只要P与Q的真值同为真或同为假,P Q 的真值就为真,否则真值为假。,蛔驰秆端滦终驰铱陋翔规蛋撅符狸艘子孜椅忧森撕奸饺略摊淤拐柳耗即编离散数学第一章离散数学第一章,运算符所有可能的结果如下表所示:,讶埔陕慢改传彬邑藐抿骋膳饺缠赶成尝馏讽溪蹭招矛闹侧釉贪墙喜反辉武离散数学第一章离散数学第一章,例: 将下列命题符号化,并讨论它们的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第一章
链接地址:https://www.31doc.com/p-5900151.html