离散数学(第26讲)
- 格式:ppt
- 大小:866.50 KB
- 文档页数:21
《离散数学教案》PPT课件第一章:离散数学简介1.1 离散数学的定义离散数学是研究离散结构及其相互关系的数学分支。
离散数学与连续数学相对,主要研究对象是集合、图、逻辑等。
1.2 离散数学的应用离散数学在计算机科学、信息技术、密码学等领域有广泛应用。
学习离散数学能够为编程、算法设计、数据结构等课程打下基础。
第二章:集合与逻辑2.1 集合的基本概念集合是由明确定义的元素组成的整体。
集合的表示方法:列举法、描述法、图示法等。
2.2 集合的基本运算集合的并、交、差运算。
集合的幂集、子集、真子集等概念。
2.3 逻辑基本概念命题:可以判断真假的陈述句。
逻辑联结词:与、或、非等。
逻辑等价式与蕴含式。
第三章:图论基础3.1 图的基本概念图是由点集合及连接这些点的边集合组成的数学结构。
图的表示方法:邻接矩阵、邻接表等。
3.2 图的基本运算图的邻接、关联、度等概念。
图的遍历:深度优先搜索、广度优先搜索。
3.3 图的应用图在社交网络、路径规划、网络结构等领域有广泛应用。
学习图论能够帮助我们理解和解决现实世界中的问题。
第四章:组合数学4.1 排列与组合排列:从n个不同元素中取出m个元素的有序组合。
组合:从n个不同元素中取出m个元素的无序组合。
4.2 计数原理分类计数原理、分步计数原理。
函数:求排列组合问题的有效工具。
4.3 鸽巢原理与包含-排除原理包含-排除原理:解决计数问题时,通过加减来排除某些情况。
第五章:命题逻辑与谓词逻辑5.1 命题逻辑命题逻辑关注命题及其逻辑关系。
命题逻辑的基本运算:联结词、逻辑等价式、蕴含式等。
5.2 谓词逻辑谓词逻辑是命题逻辑的推广,引入量词和谓词。
谓词逻辑的基本结构:个体、谓词、量词、逻辑运算等。
5.3 谓词逻辑的应用谓词逻辑在计算机科学中用于描述和验证程序正确性。
学习谓词逻辑能够提高对问题本质的理解和表达能力。
第六章:组合设计6.1 组合设计的基本概念组合设计是指从给定的有限集合中按照一定规则选取元素,构成满足特定条件的组合。
笛卡尔乘积及相关性质一、笛卡尔乘积1、定义令A和B为任意两个集合, 如果序偶的第一元素是A 的元素, 第二元素是B的元素;所有这样的序偶的集合称为集合A 和B的笛卡尔乘积或者直积, 记作A ⨯ B. 笛卡尔乘积的符号化表示为:A ⨯B = { <x, y> | (x∈A)∧(y∈B) }例如, 设A = { a, b }, B = { 0, 1, 2 }, 则A ⨯B = { <a, 0>, <a, 1>, <a, 2>, <b, 0>, <b, 1>, <b, 2> }B ⨯ A = { <0, a>, <0, b>, <1, a>, <1, b>, <2, a>, <2, b> }A⨯B≠B⨯A 即“⨯”是不满足交换律.笛卡尔乘积举例Jerry,Kelly,July三人去访友,可选择的汽车线路有:382,381。
每人与一个汽车线路配对,共有多少种方式?设集合A={ Jerry,Kelly,July },集合B={ 382,381 }所有可能的配对的集合是A B。
共有6种方式.2、笛卡尔积运算性质1).对任意集合A,根据定义有A×Φ = Φ, Φ×A = Φ2).一般的说,笛卡尔积运算不满足交换律,即A×B≠B×A(当A≠Φ∧B≠Φ∧A≠B时)3).笛卡尔积运算不满足结合律,即(A×B)×C≠A×(B×C) (当A≠Φ∧B≠Φ∧C≠Φ时)注意:(A×B)×C的元素是三元组,但A×(B×C)的元素不是三元组.例1 设A={a,b},B={1,2},C={z}(A⨯B)⨯C={〈a,1〉,〈a,2〉,〈b,1〉,〈b,2〉}⨯{z}={〈a,1,z〉,〈a,2,z〉,〈b,1,z〉,〈b,2,z〉}A⨯ ( B⨯C ) ={a, b}⨯{〈1,z〉,〈2,z〉}={〈a,〈1,z〉〉,〈a,〈2,z〉〉,〈b,〈1,z〉〉,〈b,〈2,z〉〉} 故(A⨯B)⨯C≠A⨯(B⨯C)“⨯”不满足结合律.二、笛卡尔乘积相关定理1.定理3-4.1 笛卡尔积运算对并和交运算满足分配律,即A×(B∪C) = (A×B)∪(A×C)A×(B∩C) = (A×B)∩(A×C)(A∪B)×C = (A×C)∪(B×C)(A∩B)×C = (A×C)∩(B×C)2.定理3-4.2 设A, B, C为任意集合,若C≠Φ,则:A⊆B ⇔(A⨯C⊆B⨯C) ⇔ (C⨯A⊆C⨯B)3.定理3-4.3 若A,B,C,D为四个非空集合,则A⊆C∧B⊆D ⇔ A×B⊆C×D求证:A ⨯ (B∪C) = (A ⨯ B)∪(A ⨯ C).证明任取<x, y> ∈A ⨯ (B∪C) ,<x, y>∈A ⨯ (B∪C)⇔ x∈A∧y∈(B∪C)⇔ x∈A∧(y∈B∨y∈C)⇔ (x∈A∧y∈B)∨(x∈A∧y∈C)⇔ <x, y>∈A ⨯ B∨<x, y>∈A ⨯ C⇔ <x, y>∈(A ⨯ B)∪(A ⨯ C)定理3-4.2 A, B, C是任意三个集合, C≠Φ,(1) A ⊆ B ⇔ (A⨯C⊆B⨯C);(2) A ⊆ B ⇔ (C⨯A⊆C⨯B)(1)证明(必要性)因C非空,存在c∈C,若A⊆B,则对任意的<a,c> ∈A⨯C,其中a∈ A ⊆ B,c ∈ C,必有<a,c> ∈ B ⨯ C,所以A⨯C ⊆ B ⨯ C. (充分性)因C非空,存在c∈C,任意a∈ A ,有<a,c> ∈ A⨯C,因为A⨯C ⊆ B ⨯ C ,则必有<a,c> ∈ B ⨯ C,所以a∈ B,所以 A⊆B.同理可证(2).定理3-4.3 若A,B,C,D为四个非空集合,则(A⊆C)∧(B⊆D) ⇔ A×B⊆C×D证:(充分性)若A⨯B ⊆ C⨯D,又A,B,C,D都不是空集, 故对任意的a∈A,b∈B,<a,b>∈ A⨯B ⊆ C⨯D.所以a∈C, b∈D, 所以 A ⊆ C, B ⊆ D.(必要性)若A ⊆C, B ⊆D,故对任意的<a,b>∈A×B ,必有a∈A⊆C, b∈B⊆D.所以<a,b> ∈ C×D,所以A×B ⊆ C×D.例2 设A , B , C , D 为任意集合,判断下列命题是否为真.(1)A ×B =A ×C ⇒ B=C(2)(A –B)×C = (A ×C) – (B ×C)(3)(A=B)∧(C=D) ⇒ A ×C=B ×D(4)存在集合A,使 A ⊆A ×A解:(1) 不一定为真.(3) 为真. (4) 为真. (2) 为真.等量代入.当A = Φ时,使A ⊆A ×A. 当A=Φ, B={1}, C={2,3}时,便不真.。