离散数学离散数学 任课教师：任课教师： 臧鸿雁臧鸿雁Email：zhylixiangsina.com绪论绪论 1、离散数学：主要研究、离散数学：主要研究离散量的结构离散量的结构及相互关系及相互关系的科学。其研究对象一般的科学。其研究对象一般是有限个或可数个元素。是有限个或可数个元素。不同领域会提出一些共同问题，这些不同领域会提出一些共同问题，这些问题会涉及到离散点的集合上的元素问题会涉及到离散点的集合上的元素的性质。的性质。微积分是连续模型微积分是连续模型绪论绪论2、离散数学的地位和重要性、离散数学的地位和重要性1）离散数学充分描述了计算机科学）离散数学充分描述了计算机科学离散型特点，是计算机科学与技术的离散型特点，是计算机科学与技术的 数学基础，又称数学基础，又称计算机数学计算机数学。为后继学科如操作系统，数据结构，后继学科如操作系统，数据结构，人工智能，信息编码等提供数学基础。人工智能，信息编码等提供数学基础。n n计算机解决问题的基本模式计算机解决问题的基本模式实实际际问问题题数数学学建建模模算算法法设设计计编编程程实实现现2）应试）应试3）思维能力）思维能力3、离散数研究内容：、离散数研究内容： 包含不同的数学分支，模块化结构包含不同的数学分支，模块化结构n第1篇 数理逻辑 n第2篇 集合论 n第3篇 代数结构 n第4篇 图论推理，形式化方法离散结构的表示描述的工具离散结构的代数模型离散结构的关系模型n n4、 学科特点学科特点n n5、 教学要求，目的，教学安排教学要求，目的，教学安排 平时成绩平时成绩30(考勤考勤,作业作业,测验测验) 期末闭卷考试期末闭卷考试 70 开放性作业开放性作业 5% 教教 学学 安安 排排作业和测验作业和测验：每周第一次上课时交作业每周第一次上课时交作业. . 考考 核核 办办 法法:n n6、参考教材、参考教材n n 离散数学离散数学 左孝凌等左孝凌等n n 上海科学技术文献出版社上海科学技术文献出版社第1篇 数理逻辑n n数理逻辑数理逻辑(符号逻辑符号逻辑)1、用数学的方法研究推理的科学、用数学的方法研究推理的科学2、其创始人：莱布尼兹、其创始人：莱布尼兹3、思想：把语言符号化形式化，把逻辑、思想：把语言符号化形式化，把逻辑所涉所涉 及的及的 “概念，推理，判断概念，推理，判断”用符用符号来表示，用公理体系来刻画，并基于号来表示，用公理体系来刻画，并基于符号串形式的演绎来描述推理过程符号串形式的演绎来描述推理过程 的一的一般规律般规律n n4、 “形式化形式化” 是使用计算机解决问是使用计算机解决问题的一个必要条件。在数理逻辑中，题的一个必要条件。在数理逻辑中，将人类的推理过程分解成一些简单的将人类的推理过程分解成一些简单的机械的工作，为用计算机代替人类推机械的工作，为用计算机代替人类推理提供了可能理提供了可能n n第1章 命题逻辑n n第2章 谓词逻辑第第1章章 命题逻辑命题逻辑1.1 命题与联结词命题与联结词 一、一、 命题的概念命题的概念 1、命题，是具有真假意义的陈述句。命题，是具有真假意义的陈述句。命题，是具有真假意义的陈述句。命题，是具有真假意义的陈述句。 命题具有一个确定的值，称为真值命题具有一个确定的值，称为真值命题具有一个确定的值，称为真值命题具有一个确定的值，称为真值 。 真值真值真值真值1 1或或或或0 0。 注意：不能作为命题的句子：注意：不能作为命题的句子：注意：不能作为命题的句子：注意：不能作为命题的句子： 一切没有判断内容的句子，无所谓是非的句子。一切没有判断内容的句子，无所谓是非的句子。一切没有判断内容的句子，无所谓是非的句子。一切没有判断内容的句子，无所谓是非的句子。 如感叹句，疑问句，祈使句，陈述句中的悖论等。如感叹句，疑问句，祈使句，陈述句中的悖论等。如感叹句，疑问句，祈使句，陈述句中的悖论等。如感叹句，疑问句，祈使句，陈述句中的悖论等。【例例1.1】 判断下句是否为命题 1 1）该吃早饭了！）该吃早饭了！2 2）多漂亮的花呀！）多漂亮的花呀！3 3）明天你有什么安排吗？）明天你有什么安排吗？4 4）我正在说谎。）我正在说谎。5 5）x x y y2 2。6 6）明天将会下雨）明天将会下雨 7 7） 郑州是河南省的省会。郑州是河南省的省会。郑州是河南省的省会。郑州是河南省的省会。8 8） 今年的冬天将是一个暖冬。今年的冬天将是一个暖冬。今年的冬天将是一个暖冬。今年的冬天将是一个暖冬。9 9） 这碗汤味太淡了。这碗汤味太淡了。这碗汤味太淡了。这碗汤味太淡了。1010） 10111011 100010001001110011。 n n命题的表示命题的表示: 使用小写字母使用小写字母p,q,r, (4)无法判定其真假值（语义上的悖论）2、简单命题（原子命题）与复合命题、简单命题（原子命题）与复合命题命题有两种类型：命题有两种类型：命题有两种类型：命题有两种类型： 1 1） 原子命题原子命题原子命题原子命题: : 由简单陈述句构成；由简单陈述句构成；由简单陈述句构成；由简单陈述句构成； 2 2）复合命题）复合命题）复合命题）复合命题: : 由联结词、标点符号和原子命题由联结词、标点符号和原子命题由联结词、标点符号和原子命题由联结词、标点符号和原子命题复合构成的命题。复合构成的命题。复合构成的命题。复合构成的命题。 例如：例如：例如：例如： 2 2是偶数是偶数是偶数是偶数并且并且并且并且3 3是偶数是偶数是偶数是偶数。 如果如果如果如果明天是个好天气明天是个好天气明天是个好天气明天是个好天气，那么，那么，那么，那么我们就去野炊我们就去野炊我们就去野炊我们就去野炊。 ( (如果如果如果如果那么那么那么那么 ) )二、二、二、二、 联结词联结词联结词联结词1、否定联结词、否定联结词p的否定命题否定命题，记作p，读作“非p”。 P P01102、 合取联结词合取联结词p p与命题与命题与命题与命题q q的合取命题，记作的合取命题，记作的合取命题，记作的合取命题，记作p pq q，读作读作读作读作“ “p p与与与与q q” ”。 pq00011011p q00013、 析取联结词析取联结词命题命题命题命题 p p 和命题和命题和命题和命题 q q的析取命题，记作的析取命题，记作的析取命题，记作的析取命题，记作 p pq q读作读作读作读作“ “p p或或或或q q” ”。pq00011011p q0111【例例1.2】1）晚上我们去教室学习或去电影院看电影。）晚上我们去教室学习或去电影院看电影。2）他可能数学考了）他可能数学考了100分或英语考了分或英语考了100分。分。是“排斥或” “可兼或”（相容或）3）他乘飞机或火车来）他乘飞机或火车来4）他出生在）他出生在1989年或年或1990年年排斥或的符号表示排斥或的符号表示pq00011011P q01104、蕴涵联结词、蕴涵联结词 记为记为记为记为 p p q q，读作，读作，读作，读作 “ “若若若若p p则则则则q q” ”。称。称。称。称 p p为前件或者前提，为前件或者前提，为前件或者前提，为前件或者前提，q q 为后件或者结论。为后件或者结论。为后件或者结论。为后件或者结论。 【例例例例1.31.3】老师对学生说：老师对学生说：老师对学生说：老师对学生说：“ “如果你期末考了如果你期末考了如果你期末考了如果你期末考了100100分，我就请你你分，我就请你你分，我就请你你分，我就请你你吃饭。吃饭。吃饭。吃饭。” ”请问：在什么情形下，学生认为老师的这句话是假？请问：在什么情形下，学生认为老师的这句话是假？请问：在什么情形下，学生认为老师的这句话是假？请问：在什么情形下，学生认为老师的这句话是假？学生期末考了学生期末考了学生期末考了学生期末考了100100分分分分(1)(1)，老师请吃饭，老师请吃饭，老师请吃饭，老师请吃饭(1)(1)，学生期末没考学生期末没考学生期末没考学生期末没考100100分分分分(0)(0)，老师请吃饭，老师请吃饭，老师请吃饭，老师请吃饭(1)(1)，学生期末考了学生期末考了学生期末考了学生期末考了100100分分分分(1)(1)，老师没请吃饭，老师没请吃饭，老师没请吃饭，老师没请吃饭(0)(0)， 则也不能认为甲的话为假则也不能认为甲的话为假则也不能认为甲的话为假则也不能认为甲的话为假(1)(1)。 则自然认为老师说的话为真则自然认为老师说的话为真则自然认为老师说的话为真则自然认为老师说的话为真(1)(1)； 则显然认为老师的话为假则显然认为老师的话为假则显然认为老师的话为假则显然认为老师的话为假(0)(0)；则没有理由认为甲的话为假则没有理由认为甲的话为假则没有理由认为甲的话为假则没有理由认为甲的话为假(1)(1)；学生期末没考学生期末没考学生期末没考学生期末没考100100分分分分(0)(0)，老师没请吃饭，老师没请吃饭，老师没请吃饭，老师没请吃饭(0)(0)，pq00011011p q11015 5 等价联结词等价联结词等价联结词等价联结词 记作记作记作记作 p p q q，读作，读作，读作，读作 “ “p p当且仅当当且仅当当且仅当当且仅当q”q”。 pq00011011“ “若若若若 p p 则则则则 q q，并且若，并且若，并且若，并且若 q q 则则则则 p p ” ”p q1001【例例例例1.41.4】 p p：5 53 3 q q：5 5 3 30 0 则则则则 p p q q表示表示表示表示: : 3 3当且仅当当且仅当当且仅当当且仅当5 5 3 30 0。 n n注：自然语言中， p q 中，中， p，q 之之间往往有有某种内在联系，在数理逻辑间往往有有某种内在联系，在数理逻辑中，中， p q 中的中的 p，q 之间未必有什么之间未必有什么内在联系内在联系例如：若2+1=4，则太阳从西方升起n n三、命题符号化三、命题符号化 用命题符号用命题符号p,q,r,.和和6个常用联结词组个常用联结词组成的符号串表示复合命题成的符号串表示复合命题n n1、虽然塞车，他还是按时到达、虽然塞车，他还是按时到达n n2、张三和李四是好朋友、张三和李四是好朋友【例例1.5】 命题符号化命题符号化p pq qp p q qp pn n4 如果每门功课都在如果每门功课都在80分以上，就能保研分以上，就能保研n n5 只有每门功课都在只有每门功课都在80分以上，才能保研分以上，才能保研n n3、李明是计算机系的学生，他住、李明是计算机系的学生，他住312或或313p pq qr rp p （q rq r）p pq qp p q qq q p pn n6 6 如果天不下雨，我今天就进城如果天不下雨，我今天就进城如果天不下雨，我今天就进城如果天不下雨，我今天就进城n n7 我明天进城，除非下雨我明天进城，除非下雨p p：天下雨：天下雨：天下雨：天下雨q q：我进城：我进城：我进城：我进城n n8 如果我上街，我就去书店看看，除非我很累如果我上街，我就去书店看看，除非我很累 p:我上街，我上街，q:我去书店看看，我去书店看看，r:我很累我很累