《离散数学绪论、命题.ppt》由会员分享，可在线阅读，更多相关《离散数学绪论、命题.ppt（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学广州大学数学与信息科学学院广州大学数学与信息科学学院钟育彬钟育彬2013年年9月月1第一讲第一讲课程绪论课程绪论命题与命题公式命题与命题公式2引言离散数学的内容是什么？离散数学在科学发展中的地位如何？计算机专业为什么要学习离散数学？如何学好离散数学？3引言离散数学的内容是什么？离散数学是研究离散量的结构和相互关系，研究对象是有限个或可数个元素，体现了计算机离散性的特点。本课程的内容包括数理逻辑、集合论、代数系统、图论四大部分。离散数学是现代数学的重要分支，是计算机科学理论的基础。4引言离散数学在科学发展中的地位如何？原始经济时代：产品交换的需要发展了算术算术；农业经济时代：土地丈量等经
2、济活动，产生了几何学几何学；工业经济时代：在牛顿力学的基础上，产生了微积分微积分；有关能量转换和守恒、能量的传送、动力、瞬时速度、运动加速度、运动与运动之间的关系等问题可以在数学分析这个层面上统一认识 5引言离散数学在科学发展中的地位如何？知识经济时代：计算机科学在信息革命中的学科地位有如牛顿力学在工业革命中的学科地位，起着主导的作用，需要用一种符号语言构成一个包括了不同领域的通用模型。离散数学离散数学就是指出构成一个包括了不同就是指出构成一个包括了不同领域的通用模型的思维方法，并且告诉我们领域的通用模型的思维方法，并且告诉我们怎样用不同的语言（符号语言、图形语言、怎样用不同的语言（符号语言、
3、图形语言、逻辑语言等）从最简单的对象（集合）出发逻辑语言等）从最简单的对象（集合）出发表示通用模型表示通用模型。6引言计算机专业为什么要学习离散数学？离散数学的思维方法能够为计算机科学所用，能使我们在更高的高度去了解和学习计算机科学，发展和创造具有时代特点的先进的发展和创造具有时代特点的先进的思维方式思维方式。离散数学的大部分内容是讨论构造或生成领域性模型的基本方法，并为转换成通用的计算模型准备了必要的条件。7计算机专业人员需要三方面的能力：构造模型的能力算法设计的能力程序设计的能力（离散数学）（数据结构）（程序设计）引言引言8引言如何学好离散数学？学习离散数学，是以学习离散数学的内容来掌握关
4、于计算机科学的最基本的思维方法，如演绎法、分析法、枚举法、归纳法、反证法、归谬法、对应法、构造法等，形成慎密的思维习惯。更重要的是，离散数学的定理证明、解题方法不一定有固定套路，有时需要另类的思路，见仁见智，富有启发性。9Quick OverviewDiscrete Math is essentially that branch of mathematics that does not depend on limits;in this sense,it is the anti-thesis of Calculus.As computers are discrete object operati
5、ng one jumpy,discontinuous step at a time,Discrete Math is the right framework for describing precisely Computer Science concepts.10Quick OverviewDiscrete Math helps providethe machinery necessary for creating sophisticated algorithmsthe tools for analyzing their efficiencythe means of proving their
6、 validity11逻辑推理 某地方有两个村落，A村的人讲真话，B村的人讲假话。一天，旅行者到了这个地方，碰见一村民甲，旅行者问甲：“你是哪个村的人？”甲回答：“我是A村的人。”在远处又有一个村民乙出现，旅行者请甲去问乙是哪个村的人，甲到远处与乙谈了话，回到旅行者处告诉旅行者说：“他说：我是A村的人”。请问，甲是哪个村落的人？12MBA入学考试逻辑模拟题有一个车间，有甲乙丙丁四个小组。有一天，这四个小组的青工举行了一次拔河比赛。比赛结果是：当甲乙两组为一方，丙丁两组为另一方的时候，双方势均力敌，不相上下。但当甲与丙对调以后，丁甲一方就轻而易举地战胜了丙乙一方。然而，乙组的青工并不服气，他们用
7、自己一个组同甲丙两个组的联合队进行较量，结果取胜了。试问四个组的强弱顺序是什么？（A）甲乙丙丁。（B）丙乙丁甲。（C）丁乙甲丙。（D）乙甲丁丙。（E）丙甲乙丁。13离散数学：Discrete Mathematics数理逻辑：Symbolic LogicNatural Language“I dont drink and drive”is logically equivalent to“If I drink,then I dont drive”英文表达14第一章 命题逻辑命题的定义命题的定义：客观上能够确定真假的陈述句。1、中国的首都是北京。2、这道菜很咸。3、明天开会吗？4、天气真好！5、全体立
8、正！6、1+101=1107、别的星球上有生物。8、如果天塌下来，我顶着。9、我正在说谎。10、明天要下雨。15第一章 命题逻辑命题的分类：原子命题原子命题：不能分解为更简单的陈述句。复合命题复合命题：由联结词、标点符号和原子命题复合构成的命题。16英文表达命题命题 DEF:A proposition is a statement that is true or false.A proposition is a statement that is either true or false but not both.命题的分类命题的分类：复合命题复合命题：Propositions that ca
9、n be obtained by the combination of other propositions are known as compound propositions.原子命题原子命题：A proposition that is not a combination of other propositions is called an atomic proposition.17第一章 命题逻辑命题常量命题常量：用来表示确定命题的标识符。例如：P表示“今天下雨。”命题变元命题变元：表示任意命题位置标志的命题标识符。例如：PP，PQ命题变元可以表示任何命题；当用一个特定命题取代命题变元P
10、时，称为对P指派指派。18第一章 命题逻辑联结词联结词：用于把原子命题联结成复合命题，是复合命题的重要组成部分。例如：或、与、但是、如果、符号化的联结词符号化的联结词（命题的五个基本联结词）：否定：合取：析取：条件：双条件在表达式中的优先级顺序19第一章 命题逻辑：否定：否定例如：P表示“广州是个大都市。”P表示“广州不是个大都市。”否定运算的真值表：PPTFFT20第一章 命题逻辑：合取：合取。当仅当两个命题同时为真时，其合取的复合命题为真。例如：P表示“触摸屏是输入设备。”Q表示“触摸屏是输出设备。”PQ表示“触摸屏既是输入设备，也是输出设备。”合取运算的真值表：21第一章 命题逻辑：析取
11、：析取。当仅当两个命题同时为假时，其析取的复合命题为假。例如：P表示“她是100米赛跑冠军。”Q表示“她是400米赛跑冠军。”PQ表示“她是100米或400米的赛跑冠军。”析取运算的真值表：22第一章 命题逻辑注意区分汉语中的区分汉语中的“或或”的意义：例1：他出生于1980年或1981年。例2：程序错误可能是语法错误或逻辑错误。例3：他昨天做了20或30道习题。分析分析：例1的“或”是不可兼取，称为“不可兼析取”，严格的表示应为(PQ)(PQ)其中P表示“他出生于1980年。”Q表示“他出生于1981年。”例2的“或”是可兼取，称为“可兼析取”；PQ 例3的“或”只表示了习题的近似数，不能用
12、联结词“析取”表达，例3整句话是个原子命题。23第一章 命题逻辑：条件。：条件。PQ 读作“如果P，那么Q。”当仅当P为真，Q为假时，PQ为假。P称为“前件”，Q称为“后件”。例1：如果下雨，我就不去看电影。（如果不下雨，是不是就一定去看电影呢？）例2：如果太阳从西边出来，那么1+1=1。蕴涵运算的真值表：24第一章 命题逻辑：双条件：双条件。P Q 读作“P当仅当Q。”当P、Q真值相同时，P Q的值为真。例1：燕子飞回南方，春天来了。例2：2+2=4当仅当雪是白的。注意：双条件命题可以不顾其因果关系。也可记为 iff(if and only if)双条件运算的真值表：25英文表达：否定：否定
13、The negation of a proposition p is a proposition p which is true if and only if p is false.：合取：合取The conjunction of two propositions p and q is a proposition that is true if and only if both p and q are true propositions.The conjunction of p and q is called“p and q”and is denoted by pq 26英文表达：析取：析取T
14、he disjunction of two propositions p and q is a proposition that is false if and only if both p and q are false propositions.The disjunction of p and q is called“p or q”and is denoted by pq.不可兼析取不可兼析取The exclusive disjunction of two proposition that is true if and only exactly one of the two is true
15、 and is denoted by p q27英文表达：条件：条件implication proposition:“if p,then q”or“p implies q”“the proposition p is a sufficient condition for the proposition q”or“the proposition q is a necessary condition for q”p is called the hypothesis(or antecedent or premise)and q is called the consequence(or conclusi
16、on).28英文表达：双条件：双条件pq:“p if and only if q”p is both necessary and sufficient for q,and vice versa.the two proposition p and q are said to be equivalent.29英文与程序的表达OperatorSymbolUsageC+Negationnot!Conjunctionand&Disjunctionor|Exclusive orxor(p|q)&(!p|!q)Conditionalif,thenp?q:trueBiconditionaliff(p&q)|(
17、!p&!q)30把自然语言中的命题翻译成数理逻辑中的符号形式。米饭或面条都能吃饱。分析：用P表示米饭能吃饱，用Q表示面条能吃饱。这句话的意思是“单独吃米饭可以饱，单独吃面条也饱，两样都吃也一样饱。”结合真值表，其符号形式是：PQ命题公式 与翻译31 我可以乘飞机或火车直达北京。分析：用P表示我可以乘飞机直达北京，用Q表示我可以乘火车直达北京。这句话的意思是“我可以乘飞机直达北京，或乘火车直达北京，但不可能既乘飞机又乘火车直达北京。”即两者只能取其一，因此，其符号形式是：（PQ）（PQ）或(PQ)命题公式 与翻译32 你或他都可以做这件事。分析：用P表示你可以做这件事，用Q表示他可以做这件事。从
18、这件事的完成结果来看，由你做或由他做都行，可表示为PQ；但从人的能力来看，则这件事你有能力完成，并且他也有能力完成，这句话就表示为PQ。应该选择哪种含义，要结合上下文再作出判断。命题公式 与翻译33 我今天进城，除非下雨。分析：用A表示我今天进城，用B表示天下雨。这句话的意思是“如果不下雨，我就进城。”所以用符号可把这句话表示为BA。注意，这里只是说，不下雨就进城，并不意味着下雨就一定不进城（即原句的逆命题BA）。命题公式 与翻译34 除非努力，否则不能成功。分析：用A表示努力，用B表示成功。这句话的意思是“如果不努力，就不成功。”所以用符号可把这句话表示为AB。同样，这并不意味着努力就一定成
19、功，但成功一定要付出努力（即原句的逆否命题BA）。实际上，若这句话的前半句和后半句颠倒，成为“不能成功，除非努力”，则语法结构和逻辑结构都和上例一样。命题公式 与翻译35 当你走，我将留下。A B 当仅当你走，我将留下。A B 仅当你走我将留下。A B 或 B A用A表示你走，用B表示我留下。命题公式 与翻译36思考：区分下列两组句子的含义：只要努力，就能成功。只有努力，才能成功。没有共产党，就没有新中国。有了共产党，就有了新中国。命题公式 与翻译37从逻辑的角度分析以下句子：如果天塌下来，有我顶着。牙好，胃口就好，身体倍棒，吃饭倍香。纽约著名的广告人路易斯先生说：“如果广告是一门科学，那我就
20、是个女人。”“只要有足够的钱，就可以买到一切”可以推导出“有足够的钱，能买到友谊健康爱情等”把“金钱如粪土，朋友值千金”作为前提，可以推出“朋友如粪土”命题公式 与翻译38本节总结内容内容：1、什么是命题，命题常量，命题变元2、命题的五个基本联结词及优先级3、自然语言的翻译要求要求：判别一个句子是否命题判别一个句子是否命题 （自身矛盾的句子不是命题，暂时未知真假的是命题）39课 后 任 务复习复习：课本P2-P7（即1.11.2）作业作业：P8 习题（1）、（3）、（4）、（5）、（6）*思考：思考：如何把以下汉语联结词翻译成命题联结词：既又,且，与,如果就,只要就,只有才,当仅当,当,仅当,
21、除非,要且只要，*预习：预习：课本P9-12（即1.3）40命题公式命题公式 的定义：1、单个命题变元或常元本身是一个命题公式；2、如果A是命题公式，则 A是命题公式；3、如果A和B是命题公式，则(AB)、(AB)、(AB)、(AB)都是命题公式。4、当仅当能够有限次地应用1、2、3所得到的包含命题变元、联结词和括号的符号串是命题公式。这是一个递归递归定义，1、为基础，2、3为归纳，4、为界限（停机条件）。例如：(P(Q R)是命题公式 P Q R 不是命题公式定义命题公式命题公式按优先级约定省去括号之后也是命题公式41定义真值表在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公
22、式的各种真值情况，把它汇列成表，就是命题公式的真值表。见课本P13例题42真值表的讨论变元取值的顺序：按二进制递增或递减n个命题变元组成的命题公式共有 种真值情况。特殊的命题公式：T（F）不论命题变元作何种指派，其真值永为真（假）P14表1-4.5和表1-4.6的结论今后可作定理使用。2n 43列出命题公式的真值表课本P17习题（1）（P Q）（Q R）(P Q)(Q R)(P R)44定义逻辑等价两个命题公式A和B，对于任意一组真值指派，A和B的真值都相同，则称A和B是逻辑等价的或等价的。记作 A A B B注意：不是注意：不是 A A B B 逻辑等价符逻辑运算符45命题的定律用真值表真值
23、表证明以下定律：P24对合律结合律交换律分配律吸收律摩根律同一律零律否定律46置换规则定义子公式子公式：如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。置换规则置换规则：设X是合式公式A的子公式，若X Y，如果将A中的X用Y来置换，所得到公式B与公式A等价，即A B47证明命题公式等价方法一：列真值表方法二：利用置换规则进行等价变换见P16-17例题48练习：由n个命题变元组成不等价的命题公式的个数为：(A)2n (B)2n (C)n2 (D)利用真值表判断：运算运算 和 运算运算 是否满足交换律、结合律？课本P60习题49本节总结内容内容：1、如何列给定命题公式
24、的真值表？2、列真值表有什么用？3、熟记P15命题的定律4、把下面五个等价命题作为定律使用：PQ PQP Q （PQ）（PQ）P Q （PQ）（QP）满足结合律：(PQ)R P(QR)不满足结合律：(PQ)R P(QR)50本节总结要求要求：会列真值表；会列真值表；能能灵灵活活利利用用真真值值表表或或命命题题定定律律证证明明两个命题公式是否等价；两个命题公式是否等价；51课 后 任 务复习复习：课本P9-P19（即1.3、1.4）书面作业书面作业：P12 习题(5)(6)P19 习题(7)(f)P19 习题(8)(a)(b)P19 习题(9)*思考：思考：如何深刻理解P15的命题定律？课本P1
25、8习题(6)*预习：预习：课本P19-28（即1.5、1.6）52MBA入学考试语文逻辑题母亲：你不把房间整理好，就别想去看电影。儿子：我早已整理好了，这下我可以去看电影了。母亲：胡说，我只是说，如果你不整理房间，你就不能去看电影。根据上文，判断下列语句中哪句是错误的？（A）母亲的意思是儿子只有整理好房间才能去看电影。（B）母亲的意思是儿子没有整理好房间就不能去看电影。（C）母亲的意思是如果儿子整理好房间就可以去看电影。（D）儿子以为母亲的意思是只要他整理好房间就能去看电影。（E）母亲的意思是儿子即使整理好房间也不一定能去看电影。53MBA入学考试语文逻辑题甲和乙任何一人都比丙丁高。如果上述为
26、真，再加上下述哪项，则可作出戊比丁高的结论？（A）戊比甲矮。（B）乙比甲高。（C）乙比甲矮。（D）戊比丙高。（E）戊比乙高。54MBA入学考试语文逻辑题一家珠宝店的珠宝被盗，经查可以肯定是甲乙丙丁中的某一个人所为。审讯中，甲说：我不是罪犯。乙说：丁是罪犯。丙说：乙是罪犯。丁说：我不是罪犯。经调查证实四人中只有一个人说的是真话。根据知条件，下列哪个为真？（A）甲说的是假话，因此，甲是罪犯。（B）乙说的是真话，丁是罪犯。（C）丙说的是真话，乙是罪犯。（D）丁说的是假话，丁的确是罪犯。（E）四个人说的全是假话，丙才是罪犯。55MBA入学考试语文逻辑题甲乙丙三人分别是游泳跳伞田径运动员中的一个，已知（
27、1）乙从未上过天；（2）跳伞运动员已得过两块金牌；（3）丙还未得过第一名，但他与田径运动员同年出生。请指出这三人各是什么运动员。（A）甲是游泳运动员，乙是跳伞运动员，丙是田径运动员。（B）甲是游泳运动员，乙是田径运动员，丙是跳伞运动员。（C）甲是跳伞运动员，乙是游泳运动员，丙是田径运动员。（D）甲是跳伞运动员，乙是田径运动员，丙是游泳运动员。（E）甲是田径运动员，丙和乙既是跳伞运动员，又是游泳运动员。56MBA入学考试语文逻辑题晚会上，老师要同学们做一个游戏。他手里拿着三颗糖，一颗软糖，两颗硬糖，分发给甲乙两位同学，看谁最先猜出对方手中拿的是什么糖。当两位同学拿到老师发给的糖以后都楞了一下，这
28、时甲抢先说，我知道了，对方手中是硬糖。甲是根据什么推出这一结论的？（A）参与做游戏的只有两个人，很容易回答。（B）完全是猜测。（C）观察老师发糖时的面部表情。（D）如果对方得到的是软糖他就能立即回答，而对方并没有立即回答出来。（E）甲手中拿的是硬糖。57MBA入学考试语文逻辑题相传有两个怪城，一座真城，一座假城。凡真城里的人个个说真话，假城里的人个个说假话。一位知晓这一情况的旅行者第一次来到其中一座城市，他只要问他第一个遇到的人一个是非问题，就明白了自己所在的是真城还是假城。下列哪个问句是最恰当的？（A）你是真城的人吗？（B）你是假城的人吗？（C）你是说真话的人吗？（D）你是说假话的人吗？（E
29、）你是这座城市的人吗？58MBA入学考试语文逻辑题以如果甲乙都不是木工，那么丙是木工为一前提，若再增加另一前提则可必然推出乙是木工的结论。下列命题中的哪一个最适合？（A）丙是木工。（B）丙不是木工。（C）甲不是木工。（D）甲和丙都不是木工。（E）甲是木工。59MBA入学考试语文逻辑题有一个车间，有甲乙丙丁四个小组。有一天，这四个小组的青工举行了一次拔河比赛。比赛结果是：当甲乙两组为一方，丙丁两组为另一方的时候，双方势均力敌，不相上下。但当甲与丙对调以后，丁甲一方就轻而易举地战胜了丙乙一方。然而，乙组的青工并不服气，他们用自己一个组同甲丙两个组的联合队进行较量，结果取胜了。试问四个组的强弱顺序是什么？（A）甲乙丙丁。（B）丙乙丁甲。（C）丁乙甲丙。（D）乙甲丁丙。（E）丙甲乙丁。60MBA入学考试语文逻辑题当并且只有当苹果是绿色时，辣椒是红色的，但浆果此时不是蓝色的；当并且只有当浆果是蓝色时，樱桃是不成熟的；当并且只有当樱桃是不成熟时草是褐色的，或叶子是小的，或两者都出现。如果草是褐色的，下面哪项一定是对的？（A）苹果不是绿色的。（B）浆果不是蓝色的。（C）辣椒是红色的。（D）樱桃是成熟的。（E）叶子是小的。61Bye-Bye!62