3第1章_数学语言与证明方法.ppt

《3第1章_数学语言与证明方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1章数学语言与证明方法林昌露12离散数学与其他课程的关系高等代数数学分析概率统计概率统计离散数学算法设计与分析算法与数据结构编译技术网络技术软件工程人工智能基础数学的延伸算法与数据结构的理论基础概率统计、算法设计与分析的理论基础其他专业课程的描述和建模工具3第1章数学语言与证明方法1.1常用的数学符号1.2集合及其运算1.3证明方法概述41.1常用的数学符号1.1.1集合符号1.1.2运算符号1.1.3逻辑符号集合论概述朴素(经典)集合论:1874年德国数学家康托(Cantor)创立了朴素集合论,没作完全形式的刻划,导致悖论(paradox)。公理化集合论:1908年另一个德国数学家蔡梅罗(

2、Zermelo)的抽象建立了集合论公理系统。从集合论出发,数学家们推出了数学上许多重要的结果。一百多年来,集合论已成为数学中不可缺少的基本描述工具,现代连续数学和离散数学的“大厦”就是建立在集合论的基础之上的。不属于自身的类随着计算机时代的开始,集合的元素已由数学的“数集”和“点集”拓展成包含文字、符号、图形、图表和声音等多媒体multimedia的信息,构成了各种数据类型的集合。集合论的原理和方法已成为计算机科学的重要基础理论之一。在自然科学中,除了研究处于孤立下的单个个体,更经常是将一些相关的个体联合在一起进行研究。一、集合的概念集合的含义：一个集合是作为整体识别的、确定的、互相区别的一些

3、事物的聚集(全体或总和等)。严格地说这不能算是集合的定义,这只是一种描述,因为“聚集(全体或总和等)”是集合一词的同义反复。集合的基本概念正像几何学中的点、线、面等概念一样,集合也是一种不加定义而可直接引入的最基本原始概念。构成一个集合的每个事物,称为这个集合中的元素(element)或成员(member)。集合一般用大写英文字母表示,集合中的元素用小写英文字母表示。但这不是绝对的,因为一个集合可以作为另一个集合的元素，如幂集。如果x是集合S的一个元素,记作xS,读为x属于S;y不是集合S的元素,记作yS,读为y不属于S。在本书所采用的体系中规定集合的元素都是集合。元素和集合之间的关系是隶

4、属关系,即属于或不属于。例A={a,{b,c},d,{{d}}}其中aA，{b,c}A，{{d}}A，但bA，{d}A可以用一种树形图来表示这种隶属关系。Aa{b,c}d{{d}}bc{d}d“集合”、“元素”和“属于”是集合论的三个最基本概念,它们是未加形式定义的原始概念,仅如上作了直观的描述。集合论中的其它概念,均可由这三个概念出发,给予严格定义。例(1)偶素数集合{2},称为单元集。(2)二进制的基数集合{0,1}。(3)英文字母(大写和小写)的集合。(4)C#语言的基本字符构成一个字符集。(5)计算机主存的全部存储单元集合。(6)全体实数的集合。(7)宇宙中的全部星球是一个集

5、合。集合的特性集合论依赖于三大基本原理,它们从根本上规定了集合概念的意义。外延(extension)公理概括(comprehension)公理正则(regularity)公理121.1.1集合符号集合是数学中最基本的概念,没有严格的定义理解成某些个体组成的整体,常用A,B,C等表示元素:集合中的个体xA(x属于A):x是A的元素xA(x不属于A):x不是A的元素包含(子集)AB即A中的每个元素都是B的元素不包含A⊈B即合B不包含集合A相等A=B即AB且BA不相等ABA⊈B或B⊈A真包含(真子集)AB即AB且AB131.1.1集合符号续（1）NZQRC（2）NZQ

6、RC141.1.2运算符号151.1.2运算符号(续)161.1.3逻辑符号命题与真值联结词(¬,,,,,)命题公式(重言式,矛盾式,可满足式)重要等值式重要推理规则个体,个体域与谓词全称量词与存在量词17命题:具有确定真值的陈述句,如:2+2=4;3是偶数；命题的符号化：用p,q,r等表示命题，如p:2+2=4;q:3是偶数;真与假的符号化:用1表示真,用0表示假真命题:真值为真的命题假命题:真值为假的命题例如,p:2+2=4,q:3是偶数它们都是命题,p是真命题,q是假命题.1.1.3逻辑符号18联结词(续)否定联结词否定式p:非p(p的否定)p为真当且仅当p为假合取联结

7、词合取式pq:p并且q(p与q)pq为真当且仅当p与q同时为真析取联结词析取式pq:p或qpq为假当且仅当p与q同时为假19联结词(续)排斥或联结词排斥或pq:p并且非q,或者q并且非ppq为真当且仅当p与q中一个为真,另一个为假蕴涵联结词蕴涵式pq:如果p,则qpq为假当且仅当p为真q为假等价联结词等价式pq:p当且仅当qpq为真当且仅当p与q同时为真或同时为假20实例: