《离散数学绪论、命题》由会员分享，可在线阅读，更多相关《离散数学绪论、命题（62页珍藏版）》请在金锄头文库上搜索。
1、1,离散数学,广州大学数学与信息科学学院 钟育彬 2013年9月,2,第一讲,课程绪论 命题与命题公式,3,引言,离散数学的内容是什么？ 离散数学在科学发展中的地位如何？ 计算机专业为什么要学习离散数学？ 如何学好离散数学？,4,引言,离散数学的内容是什么？ 离散数学是研究离散量的结构和相互关系，研究对象是有限个或可数个元素，体现了计算机离散性的特点。 本课程的内容包括数理逻辑、集合论、代数系统、图论四大部分。 离散数学是现代数学的重要分支，是计算机科学理论的基础。,5,引言,离散数学在科学发展中的地位如何？ 原始经济时代： 产品交换的需要发展了算术； 农业经济时代： 土地丈量等经济活动，产生
2、了几何学； 工业经济时代 ： 在牛顿力学的基础上，产生了微积分；有关能量转换和守恒、能量的传送、动力、瞬时速度、运动加速度、运动与运动之间的关系等问题可以在数学分析这个层面上统一认识,6,引言,离散数学在科学发展中的地位如何？ 知识经济时代： 计算机科学在信息革命中的学科地位有如牛顿力学在工业革命中的学科地位，起着主导的作用，需要用一种符号语言构成一个包括了不同领域的通用模型。 离散数学就是指出构成一个包括了不同领域的通用模型的思维方法，并且告诉我们怎样用不同的语言（符号语言、图形语言、逻辑语言等）从最简单的对象（集合）出发表示通用模型。,7,引言,计算机专业为什么要学习离散数学？ 离散数学的
3、思维方法能够为计算机科学所用，能使我们在更高的高度去了解和学习计算机科学，发展和创造具有时代特点的先进的思维方式。 离散数学的大部分内容是讨论构造或生成领域性模型的基本方法，并为转换成通用的计算模型准备了必要的条件。,8,计算机专业人员需要三方面的能力： 构造模型的能力 算法设计的能力 程序设计的能力,（离散数学） （数据结构） （程序设计）,引言,引言,9,引言,如何学好离散数学？ 学习离散数学，是以学习离散数学的内容来掌握关于计算机科学的最基本的思维方法，如演绎法、分析法、枚举法、归纳法、反证法、归谬法、对应法、构造法等，形成慎密的思维习惯。更重要的是，离散数学的定理证明、解题方法不一定有
4、固定套路，有时需要另类的思路，见仁见智，富有启发性。,10,Quick Overview,Discrete 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 operating one jumpy, discontinuous step at a time, Discrete Math is the right framew
5、ork for describing precisely Computer Science concepts.,11,Quick Overview,Discrete Math helps provide the machinery necessary for creating sophisticated algorithms the tools for analyzing their efficiency the means of proving their validity,12,逻辑推理,某地方有两个村落，A村的人讲真话，B村的人讲假话。一天，旅行者到了这个地方，碰见一村民甲，旅行者问甲：
6、“你是哪个村的人？”甲回答：“我是A村的人。”在远处又有一个村民乙出现，旅行者请甲去问乙是哪个村的人，甲到远处与乙谈了话，回到旅行者处告诉旅行者说：“他说：我是A村的人”。请问，甲是哪个村落的人？,13,MBA入学考试逻辑模拟题,有一个车间，有甲乙丙丁四个小组。有一天，这四个小组的青工举行了一次拔河比赛。比赛结果是：当甲乙两组为一方，丙丁两组为另一方的时候，双方势均力敌，不相上下。但当甲与丙对调以后，丁甲一方就轻而易举地战胜了丙乙一方。然而，乙组的青工并不服气，他们用自己一个组同甲丙两个组的联合队进行较量，结果取胜了。 试问四个组的强弱顺序是什么？ （A）甲乙丙丁。 （B）丙乙丁甲。 （C）丁
7、乙甲丙。 （D）乙甲丁丙。 （E）丙甲乙丁。,14,离散数学：Discrete Mathematics 数理逻辑：Symbolic Logic Natural Language “I dont drink and drive” is logically equivalent to “If I drink, then I dont drive”,英文表达,15,第一章 命题逻辑,命题的定义：客观上能够确定真假的陈述句。 1、中国的首都是北京。 2、这道菜很咸。 3、明天开会吗？ 4、天气真好！ 5、全体立正！ 6、1+101=110 7、别的星球上有生物。 8、如果天塌下来，我顶着。 9、我正在
8、说谎。 10、明天要下雨。,16,第一章 命题逻辑,命题的分类： 原子命题： 不能分解为更简单的陈述句。 复合命题：,由联结词、标点符号和原子命题复合构成的命题。,17,英文表达,命题 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 can be obtained by the combination of other pro
9、positions are known as compound propositions. 原子命题：A proposition that is not a combination of other propositions is called an atomic proposition.,18,第一章 命题逻辑,命题常量： 用来表示确定命题的标识符。 例如：P表示“今天下雨。” 命题变元： 表示任意命题位置标志的命题标识符。 例如：PP， PQ 命题变元可以表示任何命题； 当用一个特定命题取代命题变元P时，称为对P指派。,19,第一章 命题逻辑,联结词： 用于把原子命题联结成复合命题，是复合
10、命题的重要组成部分。 例如：或、与、但是、如果、 符号化的联结词（命题的五个基本联结词） ：否定 ：合取 ：析取 ：条件 ：双条件,在表达式中的优先级顺序,20,第一章 命题逻辑,：否定 例如：P表示“广州是个大都市。” P表示“广州不是个大都市。” 否定运算的真值表：,21,第一章 命题逻辑,：合取。当仅当两个命题同时为真时，其合取的复合命题为真。 例如：P表示“触摸屏是输入设备。” Q表示“触摸屏是输出设备。” PQ表示“触摸屏既是输入设备，也是输出设备。” 合取运算的真值表：,22,第一章 命题逻辑,：析取。当仅当两个命题同时为假时，其析取的复合命题为假。 例如：P表示“她是100米赛跑
11、冠军。” Q表示“她是400米赛跑冠军。” PQ表示“她是100米或400米的赛跑冠军。” 析取运算的真值表：,23,第一章 命题逻辑,注意区分汉语中的“或”的意义： 例1：他出生于1980年或1981年。 例2：程序错误可能是语法错误或逻辑错误。 例3：他昨天做了20或30道习题。,分析： 例1的“或”是不可兼取，称为“不可兼析取”，严格的表示应为 (PQ)(PQ) 其中P表示“他出生于1980年。”Q表示“他出生于1981年。” 例2的“或”是可兼取，称为“可兼析取”；PQ 例3的“或”只表示了习题的近似数，不能用联结词“析取”表达，例3整句话是个原子命题。,24,第一章 命题逻辑,：条件
12、。PQ 读作“如果P，那么Q。” 当仅当P为真，Q为假时， PQ为假。 P称为“前件”，Q称为“后件”。 例1：如果下雨，我就不去看电影。 （如果不下雨，是不是就一定去看电影呢？） 例2：如果太阳从西边出来，那么1+1=1。 蕴涵运算的真值表：,25,第一章 命题逻辑,：双条件。P Q 读作“P当仅当Q。” 当P、Q真值相同时， P Q的值为真。 例1：燕子飞回南方，春天来了。 例2：2+2=4当仅当雪是白的。 注意：双条件命题可以不顾其因果关系。 也可记为 iff ( if and only if ) 双条件运算的真值表：,26,英文表达,：否定 The negation of a prop
13、osition 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,27,英文表达,：析取 The disjunction of
14、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 and is denoted
15、by pq,28,英文表达,：条件 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 co
16、nclusion ).,29,英文表达,：双条件 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.,30,英文与程序的表达,31,把自然语言中的命题翻译成数理逻辑中的符号形式。, 米饭或面条都能吃饱。,分析：用P表示米饭能吃饱，用Q表示面条能吃饱。这句话的意思是“单独吃米饭可以饱，单独吃面条也饱，两样都吃也一样饱。”结合真值表，其符号形式是：PQ,命题公式 与翻译,32, 我可以乘飞机或火车直达北京。,分析：用P表示我可以乘飞机直达北京，用Q表示我可以乘火车直达北京。这句话的意思是“我可以乘飞机直达北京，或乘火车直达北京，但不可能既乘飞机又乘火车直达北京。”即两者只能取其一，
