17集合及逻辑习题课.ppt

 第三章 集合 集合的对称差运算 对称差的性质: （1）交换律： （2）结合律： （3）交对对称差的分配律： （4） 3.4 容斥原理 在介绍容斥原理之前先介绍如何利用文氏图来解决有关集合的应用问题。 例如假设有170个学生，其中120学英语；80人学法语；60人学西班牙语；50人既学英语，又学法语；25人既学英语又学西班牙语；30人同时学法语和西班牙语；还有10个人三种语言都学，问有多少人这三种语言都有没学？ 解：先画出文氏图，由里及外标出各个子集人数，然后统计。 例如假设有170个学生，其中120学英语；80人学法语；60人学西班牙语；50人既学英语，又学法语；25人既学英语又学西班牙语；30人同时学法语和西班牙语；还有10个人三种语言都学，问有多少人这三种语言都有没学？ 3.4.1 容斥原理 假设A、B为有限集合，每个集合的基数分别为|A|、|B|，由文氏图可知： 这就是容斥原理。 定理 对于任意三个集合A、B、C有： 证明： 上面实例可以计算如下： |E|=120 |F|=80 |S|=60 |E∩F|=50 |E∩S|=25 |F∩S|=30 |E∩F∩S|=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。 练 习 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 人次 |A∩B∩C|=20 (|A∩B|-|A∩B∩C|)+(|A∩C|-|A∩B∩C|)+(|B∩C|-|A∩B∩C|)=55-20 |A∩B|+|A∩C|+|B∩C|=35+20+20+20=95 |A∪B∪C|=140-95+20=65 75-65=10 课后作业 讲解课堂测试题 讲解第二章的所有作业题 第四章下次课讲  第四章 关系 所谓关系是指个体之间的联系，是一种普遍存在的现象。例如人与人之间有夫妻、父子、师生关系；两个数之间有等于、大于、小于、小于等于等关系等等。 关系在计算机科学中应用非常普遍，如开关理论、数据结构、算法分析、形式语言、程序设计、数据库等方面都有卓有成效地应用关系的理论。特别是以关系的基础理论----关系模式建立起来的关系数据库管理系统独占数据库市场，形成一支独秀的局面。 本章将介绍二元关系的基本知识、二元关系的应用和多元关系及其应用。 4.1.1 序偶及笛卡儿积 （一）序偶 所谓序偶是成对出现且有一定次序的个体的集合，例如日常生活中的亲属关系、数据的比较关系等等。这些都是由两个有固定次序的个体组成的序列，我们称之为序偶。 定义4-1 由两个元素x和y按一定次序排列而成的序列，称为有序对或序偶，记作x,y。其中，x是它的第一元素，y是它的第二元素。 例如，平面直角坐标系中任意一点的坐标(x,y)就是一个序偶。 序偶有别于由两个元素组成的集合： （1