离散数学I省公开课一等奖全国示范课微课金奖课件.pptx

离散数学I肖明军Web:/~xiaomjEmail:xiaomj@张浩zhh1000@第1页

引言课程介绍离散数学是当代数学一个主要分支，是计算机科学中基础理论关键课程，它研究对象是有限个或可数离散量。充分描述了计算机科学离散性特征。离散数学是传统逻辑学、集合论、数论基础、算法设计、组合分析、离散概率、关系理论、图论与树、抽象代数、布尔代数、计算模型等聚集起来一门综合学科。离散数学应用遍布当代科学技术很多领域。离散数学是伴随计算机科学发展而逐步建立起来一门新兴工具性学科，形成于七十年代。第2页

引言课程意义离散数学是计算机科学数学基础，其基本概念、理论、方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法设计、人工智能、计算机网络等专业课程中，是这些课程基础课程。离散数学学习十分有益于概括抽象能力、逻辑思维能力、归纳结构能力提升，能够培养提升学生数学思维能力和对实际问题求解能力。教学内容数理逻辑、集合论、代数结构、图论第3页

引言教学内容第一部分数理逻辑第一章命题逻辑第二章谓词逻辑第二部分集合论第三章集合代数第四章二元关系第4页

引言教学内容第二部分集合论第五章函数第六章集合基数第三部分代数结构第七章代数系统第八章群论第5页

引言教学内容第三部分代数结构第九章环与域第十章格与布尔代数第6页

第一部分数理逻辑逻辑学是一门研究思维形式和规律科学。分为辩证逻辑和形式逻辑两种。思维形式结构包含了概念﹑判断和推理之间结构和联络，其中概念是思维基本单位，经过概念对事物是否含有某种属性进行必定或否定回答，就是判断。由一个或几个判断推出另一判断思维形式就是推理。数理逻辑用数学方法研究推理规律称为数理逻辑。所谓数学方法就是引用一套符号体系方法，所以数理逻辑又称作符号逻辑。第7页

第一部分数理逻辑当代数理逻辑逻辑演算、逻辑演绎、模型论、证实论、递归函数论、公理化集合论等。我们要介绍是数理逻辑中最基本内容：命题逻辑和谓词逻辑。即普通所谓古典逻辑。德国数学家莱布尼茨Leibniz（当代逻辑首席创始人）；布尔Boole（奠基人，逻辑数学分析）；弗雷格（数论基础）第8页

第一章命题逻辑 命题逻辑也称命题演算或语句逻辑。它研究以“命题”为基本单位组成前提和结论之间可推导关系，研究什么是命题？怎样表示命题？怎样由一组前提推导一些结论。概念判断推理第9页

1.1命题与命题联结词1.1.1命题定义1.1：含有确切真值陈说句(或断言)称为命题(Proposition)。命题取值称为真值。真值只有“真”和“假”两种，分别用“T”或“1”和“F”或“0”表示。注意：命题真值非真即假，只有两种取值，这么系统为二值逻辑系统。第10页

1.1命题与命题联结词例1-1：命题示例。(a):今天下雪 (b):3+3=6 (c):2是偶数而3是奇数(d):陈胜起义那天，杭州下雨 (e):较大偶数都可表为两个质数之和(f):x+y4 (g):真好啊! (h):x=3(i):你去哪里？ (j):我正在说谎。注意：由定义知，一切没有判断内容句子如命令，感叹句，疑问句，祈使句，二义性陈说句等都不能作为命题。第11页

1.1命题与命题联结词例1-2：以下句子哪些是命题，判断命题真假。 (1):2是素数 (2):北京是中国首都 (3):这个语句是假 (4):x+y0 (5):我喜欢踢足球 (6):地球外星球上也有些人 (7):明年国庆节是晴天 (8):把门关上 (9):你要出去吗？ (10):今天天气真好啊！第12页

注意命题一定是经过陈说句来表示；反之，并非一切陈说句都一定是命题。命题真值有时可明确给出，有时还需要依靠环境条件，实际情况，时间才能确定其真值。但其真值一定是唯一确定。1.1命题与命题联结词第13页

1.1命题与命题联结词命题可分为两种类型：简单命题：若一个命题已不能分解成更简单命题，则该命题叫原子命题或本原命题或简单命题（SimpleProposition）复合命题（CompoundProposition）：能够分解为简单命题命题，而且这些简单命题之间是经过关联词（如“或者”,“而且”,“不”，“假如…则…”,“当且仅当”等）和标点符号复合而组成一个复合命题。例，合肥是安徽省会当且仅当鸟会飞。注意：命题通惯用大写英文字母（可带下标）来表示。第14页

1.1.2命题联结词 命题通常能够经过一些联结词复合而组成新命题，这些联结词被称为逻辑联结词。用数学方法研究命题之间逻辑关系时（也就是在命题演算中），这些联结词能够看作是运算符，所以也叫作逻辑运算符。 惯用联结词有以下5个：定义1.2：设P是任一命题，复合命题“非P”（或“P否定”）称为P否定式（Negation），记作?P，“?”为