数理逻辑与图论-Ubicom泛在通信实验室.PDF

《数理逻辑与图论》 信息安全专业 2017-2018学年第一学期 中国科学技术大学 刘斌 Email: flowice@ 办公室：科技实验楼西楼1711室 助教：张宇飞 课程主页： /teach/dismath/ 中国科学技术大学 刘斌 《数理逻辑与图论》 1 课程内容  第1章：基础：逻辑和证明  第2章：基本结构：集合、函数、数列与求 和  第3章：计数  第4章：高级计数技术  第5章：关系  第6章：图  第7章：树（7.1-7.2） 中国科学技术大学 刘斌 《数理逻辑与图论》 2 第二章 基本结构：集合、函数、数列和求和  2.1 集合  2.2 集合运算  2.3 函数  2.4 序列和求和 中国科学技术大学中国科学技术大学 刘斌刘斌 《数理逻辑与图论》 33 2.1 集合  定义 集合 （set）：一组无序的对象。  定义 元素 （element）：集合中的对象也称为 该集合的元素，或成员 （member）。  集合的表示方法：花括号之间列出所有元素 英语字母中所有元音字母的集合：V={a,e,i,o,u} 例 小于10的正奇数集合：O={1,3,5,7,9}  集合中的元素表面上可以看起来毫不相干： {a,2,Fred,New Jerseg}  通常用大写字母表示集合：自然数集合N，整数集合Z，正整 数集合Z+，有理数集合Q，实数集合R  集合的表示方法：花括号中列出集合的部分元素，其余用省略 号表示： {1,2,3…,99} 中国科学技术大学中国科学技术大学 刘斌刘斌 《数理逻辑与图论》 44 集合的基本定义和性质  定义 两个集合相等 （equal）当且仅当它们有 相同的元素。  元素的顺序不起作用：集合{1,3,5}和集合{3,5,1}相等；  同一个元素被列出来不止一次也没关系：{1,3,3,3,5,5,5,5} 和{1,3,5}是同一个集合。  集合的描述方式：使用集合构造符号（谓词公式） O={x|x是小于10的奇数}，O={x|P(x)} 例 R={x|x是实数}  集合的描述方式：文式图 （Venn diagram ）  全集 （universal set）：我们所考虑的所有对象的集合U，在 文式图中用长方形代替  用圆或其他几何图形表示集合，用点表示特定元素 中国科学技术大学中国科学技术大学 刘斌刘斌 《数理逻辑与图论》 55 集合的文式图表示 例 中国科学技术大学中国科学技术大学 刘斌刘斌 《数理逻辑与图论》 66 集合成员的关系  a是集合A的一个元素：a∈A 。  a不是集合A的一个元素：a∉A 。  空集 （empty set, null set）：不含任何元素的特殊 集合，用∅表示 2 +  {x|xx , x∈Z }是一个空集  ∅和{∅}不一样，是两个集合  单元集 （singleton set）：只含有一个元素的集合  定义 集合A是集合B的子集 （subset）当且仅当 A的每个元素也是B的元素，用A⊆B表示A是B的子集。  A⊆B当且仅当量化语句∀x(x ∈A→x∈B)为真。 中国科学技术大学中国科学技术大学 刘斌刘斌 《数理逻辑与图论》