《集合及逻辑习题》PPT课件.ppt_第1页
《集合及逻辑习题》PPT课件.ppt_第2页
《集合及逻辑习题》PPT课件.ppt_第3页
《集合及逻辑习题》PPT课件.ppt_第4页
《集合及逻辑习题》PPT课件.ppt_第5页
已阅读5页,还剩21页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

,第三章 集合,第十七讲,集合的对称差运算,对称差的性质: (1)交换律: (2)结合律: (3)交对对称差的分配律: (4),内 容 回 顾,3.4 容斥原理,在介绍容斥原理之前先介绍如何利用文氏图来解决有关集合的应用问题。 例如假设有170个学生,其中120学英语;80人学法语;60人学西班牙语;50人既学英语,又学法语;25人既学英语又学西班牙语;30人同时学法语和西班牙语;还有10个人三种语言都学,问有多少人这三种语言都有没学? 解:先画出文氏图,由里及外标出各个子集人数,然后统计。,例如假设有170个学生,其中120学英语;80人学法语;60人学西班牙语;50人既学英语,又学法语;25人既学英语又学西班牙语;30人同时学法语和西班牙语;还有10个人三种语言都学,问有多少人这三种语言都有没学?,E,F,S,|E|=120 |F|=80 |S|=60 |EF|=50 |ES|=25 |FS|=30 |EFS|=10 |EFS|=55+40+10+15+10+20+15=165 170-165=5 答:有5人这三种语言都没学。,10,40,15,20,15,10,55,3.4.1 容斥原理 假设A、B为有限集合,每个集合的基数分别为|A|、|B|,由文氏图可知: 这就是容斥原理。,定理 对于任意三个集合A、B、C有: 证明:,上面实例可以计算如下: |E|=120 |F|=80 |S|=60 |EF|=50 |ES|=25 |FS|=30 |EFS|=10 =120+80+60-50-25-30+10 =165 容斥原理可以推广到n个集合: 定理 设 为有限集合,其基数分别为: 则 该公式可以通过数学归纳法加以证明。,例2 求从1到500的整数中,能被3或5除尽的数的个数。 解:,例3 一个班级共有52名学生。其中有24人喜欢打篮球,有15人喜欢下棋,有20人喜欢游泳,有6人既喜欢打篮球又喜欢下棋,有7人既喜欢打篮球又喜欢游泳,有2人这3项活动都喜欢,有9人这3项活动都不喜欢。问有多少人既喜欢下棋又喜欢游泳? 解:,例4 一个班级共有50名学生。在一次考试中,有15人英语得90分以上,有18人计算机得90分以上,有22人这两门课程均没有得到90分以上。问有多少人这两门课程均得到90分以上? 解 设全班学生为全集E,英语得90分以上的学生为集合A,计算机数学得90分以上的学生为集合B。,|E|=50, |A|=15, |B|=18,|(AB)|=28.,|(AB)|=5.,练 习 1.试决定在1至250之间能被2、3、5、7 中任何一数整除的整数个数。 2.设某校足球队有球衣38件,篮球队有球衣15件,棒球队有球衣20件,三队队员的总数为58人,且其中只有三人同时参加三队,试求同时参加二队的队员共有几人。 3. 75个儿童到游乐场,那里可以骑木马,坐滑行铁道,乘宇宙飞船,已知其中20人三样都坐过,其中55人至少坐过其中的两种。若每样乘坐一次的费用都是0.5元,游乐场总共收入70元,试确定有多少儿童没有乘坐过其中任何一种。,3.解: 设骑木马的学生集合为A,坐滑行铁道的学生集合为B,乘宇宙飞船的学生集合为C。 |A|+|B|+|C|=70/0.5=140 人次 |ABC|=20 (|AB|-|ABC|)+(|AC|-|ABC|)+(|BC|-|ABC|)=55-20 |AB|+|AC|+|BC|=35+20+20+20=95 |ABC|=140-95+20=65 75-65=10,课后作业,讲解课堂测试题 讲解第二章的所有作业题 第四章下次课讲,第四章 关系,笛卡尔积,所谓关系是指个体之间的联系,是一种普遍存在的现象。例如人与人之间有夫妻、父子、师生关系;两个数之间有等于、大于、小于、小于等于等关系等等。 关系在计算机科学中应用非常普遍,如开关理论、数据结构、算法分析、形式语言、程序设计、数据库等方面都有卓有成效地应用关系的理论。特别是以关系的基础理论-关系模式建立起来的关系数据库管理系统独占数据库市场,形成一支独秀的局面。 本章将介绍二元关系的基本知识、二元关系的应用和多元关系及其应用。,4.1.1 序偶及笛卡儿积 (一)序偶 所谓序偶是成对出现且有一定次序的个体的集合,例如日常生活中的亲属关系、数据的比较关系等等。这些都是由两个有固定次序的个体组成的序列,我们称之为序偶。 定义4-1 由两个元素x和y按一定次序排列而成的序列,称为有序对或序偶,记作。其中,x是它的第一元素,y是它的第二元素。 例如,平面直角坐标系中任意一点的坐标(x,y)就是一个序偶。,序偶有别于由两个元素组成的集合: (1)在序偶中的元素是有序的,集合中的元素是无序的。例如: 而1,2=2,1 。 (2) 两个序偶和相等充分必要条件,是a=c且b=d。 序偶中的元素可以来自同一集合,也可以来自不同集合。例如在计算机的符号指令中,一条操作指令就是一个序偶, ,其中 为操作码,D为地址码。,(二)笛卡儿积 定义4-2 设A、B是两个集合,若序偶的第一元素取自集合A,第二元素取自集合B,则所有这样的序偶组成的集合称为集合A和B的笛卡儿积,也称为直积,记作AB ,即AB =|xA y B 例如:设集合 则 其中 若A、B是有限集合,则有,Notice:,(1)笛卡儿积不服从交换律,且当其中有一个为空 集,约定其笛卡儿积也为

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论