集合论与图论第二章

离散数学教程（集合论与图论）离散数学：计算机科学与技术的数学基础课内容：集合论，图论，组合数学，代数结构，数理逻辑集合论:（第1-4章）组合数学初步:（第5-7章）图论:（第8-11章）教师介绍⏹教师：吴永辉博士副教授⏹简历：⏹1984-1988 上海科技大学计算机系本科⏹1988-1991 复旦大学计算机系硕士⏹1991-2003 华东师范大学计算机系工作⏹1998-2001 复旦大学计算机系博士⏹2003-复旦大学计算机系工作⏹答疑E-mail: yhwu@《集合论与图论》课件制作软件⏹Microsoft PowerPoint⏹MathType Equation《集合论与图论》课程大纲⏹课程性质与目的⏹教学内容与要求⏹使用教材、参考书籍⏹命题说明和题型课程性质、目的与基本要求⏹课程性质本课程讲授计算机科学与技术的数学基础课《离散数学》的部分主要内容：集合论、图论与组合数学初步，是计算机专业的主干课程之一。

本课程前行课程为线性代数，数学分析(上)。

⏹课程目的使学生掌握集合论、图论与组合数学初步的基本内容，并对证明的思想和方法深入理解和体会，初步培养学生的思维过程的数学化。

⏹基本要求：⏹掌握集合论、组合学和图论的基本概念，清楚了解引入基本概念的实际背景、各概念间相互关系；掌握基本定理以及有关理论题的证明技巧；掌握解决计数问题的基本方法和技巧；掌握图论中各算法设计的思想、正确性证明以及算法的应用。

为进一步学习计算机其他课程打下坚实的基础。

教学方式本课程以课堂讲授为主。

考核方式⏹平时作业；⏹集合论、组合数学和图论3次课堂练习；⏹期中，期末的两次笔试考试。

教学内容与要求----集合论⏹第一章集合的基本概念掌握：集合的基本概念，集合的运算。

了解：集合论的悖论。

掌握证明两个集合相等的基本法和公式法。

⏹第二章关系掌握：关系的性质、运算和关系的闭包，以及等价关系和偏序关系。

了解：关系在关系数据库中的应用。

掌握证明的类型。

第一篇集合论集合论是德国数学家康托（Contor）在1874年建立的，它是现代数学的基础，当今数学中的每个对象本质上都是集合。

有时我们说：“数学能嵌套在集合论中”其含义就是指数学的一些对象如数、函数、线、面等都可以用集合来定义。

换句话说，数学的各个分支在本质上都是研究这种或那种对象的集合。

例如：几何学是研究点、线、面的集合；数学分析是研究函数的集合；代数学是研究数的集合以及在此集合上有关运算的集合等。

因此，我们把集合论作为现代各种数学的基础是有道理的、合适的。

集合论也是计算机科学的重要工具。

集合论在程序设计、数据结构、形式语言、操作系统等计算机科学中，都有重要应用，成为计算机科学工作者必不可少的基础知识。

计算机科学领域中的大多数基本概念和理论，几乎均采用集合论的术语来描述和论证。

集合论主要有以下几个特点：第一、第一、它所研究的对象十分广泛。

例如数、图形或其它任何客体作为对象。

第二、第二、因为它研究的对象是如此广泛，为了便于研究，就必须寻找对象的共性。

而要做到这一点，就必须进行抽象。

第三、第三、在抽象化的基础上，可以用统一的方法来研究和处理集合论中的各种问题。

总之，集合论的主要特点是研究对象的广泛性，分析思考问题的抽象性和处理问题的统一性。

正是这些特点，使我们便于用它来描述和研究离散对象及其关系。

第一章集合及其运算基本要求1. 1.掌握集合、子集、全集、空集和幂集等概念。

熟悉常用的表示集合的方法以及用文氏图来表示集合的方法。

能够判定元素与集合、集合与集合之间的关系；熟练掌握两个集合相等关系和包含关系的定义和性质，能够利用定义证明两个集合相等。

2. 2.熟练掌握集合之间的各种运算以及集合运算的基本等式，能够利用它们来证明更复杂的集合等式。

3. 3.掌握余集与集合笛卡儿乘积的概念以及De Morgan公式。

4．掌握求解与有穷集合计数相关的实际问题。

1.1 必备知识和考试要点1.1.1基本定义集合是一个不能精确定义的数学概念。

2.3 关系的运算*关系的运算有七种,分别列出如下:定义7.6: 设R是二元关系.(1)R中所有有序对的第一个元素构成的集合称为R的定义域, 记作domR.domR={x | ∃y(<x,y>∈R)}(2)R中所有有序对的第二个元素构成的集合称为R的值域,记作ranR.ranR={y | ∃x(<x,y>∈R)}.(3)R的定义域和值域的并集称为R的域,记作fldR.fldR = domR ∪ ranR .例1: R={<1,2>,<1,3>,<2,4>,<4,3>},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}定义7.7:设R为二元关系,R的逆关系,简称R的逆,记作R-1,定义为R-1={<x,y>|<y,x>∈R}.定义7.8:设F,G为二元关系,G对F的右复合,记做F G,定义为F G={<x,y>|∃t(<x,t>∈F∧<t,y>∈G)} .例2:设F={<3,3>,<6,2>}, G={<2,3>},则F-1={<3,3>,<2,6>}F G={<6,3>}G F={<2,3>}.*左复合:F G={<x,y>| t(<x,t>∈G∧<t,y>∈F)}*有些书上用左复合,但右复合比较直观,本书用右复合. 定义7.9:设R为二元关系,A是集合(1)R在A上的限制,记作R|A,定义为R|A={<x,y>|xRy∧x∈A}(2)A在R下的像,记作R[A],定义为R[A]=ran(R|A)*R|A是R的子关系,R[A]是ranR的子集.例3:设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>},则R|{1}={<1,2>,<1,3>}R|φ=φR|{2,3}={<2,2>,<2,4>,<3,2>}R[{1}]={2,3}R[φ]=φR[{3}]={2} .*关系运算的优先级:1.逆运算2.关系的其它运算3.集合运算4.先括号里后括号外5.同级运算从左到右例子: ranF-1, F G∪F H, ran(F|A).*关系运算的性质:定理7.1:设F是任意的关系,则(1)(F-1)-1= F(2)domF-1=ranF, ranF-1=domF.证明: (1)任取<x,y>,由逆的定义,有<x,y>∈(F-1)-1⇔<y,x>∈F-1⇔<x,y>∈F,所以(F-1)-1= F.(2)任取x,x∈domF-1⇔∃y(<x,y>∈F-1)⇔∃y(<y,x>∈F)⇔x∈ranF . 所以 domF-1 = ranF.同理可证ranF-1 = domF.定理7.2:设F,G,H是任意的关系,则(1)(F G) H=F (G H)(2)(F G)-1=G-1 F-1证明:(1)任取<x,y>,<x,y>∈(F G) H⇔∃t(<x,t>∈F G∧<t,y>∈H)⇔∃t(∃s(<x,s>∈F∧<s,t>∈G)∧<t,y>∈H)⇔∃t∃s(<x,s>∈F∧<s,t>∈G∧<t,y>∈H)⇔∃s(<x,s>∈F∧∃t(<s,t>∈G∧<t,y>∈H))⇔∃s(<x,s>∈F∧<s,y>∈G H)⇔<x,y>∈F (G H)所以(F G) H=F (G H).(1)的另一种证明:对任意<x,y>∈(F G) H,则存在t使得<x,t>∈F G且<t,y>∈H.又由<x,t>∈F G,有s使得<x,s> ∈F且<s,t>∈G.由<s,t>∈G和<t,y>∈H,有<s,y>∈G H, 再由<x,s>∈F,有<x,y>∈F (G H).故(F G) H⊆F (G H).对任意<x,y>∈F (G H),存在s,使得<x,s>∈F且<s,y>∈G H.再由<s,y>∈G H,存在t,使得<s,t>∈G且<t,y>∈H.由<x,s>∈F和<s,t>∈G,有<x,t>∈F G,再由<t,y>∈H,有<x,y>∈(F G) H.故(F G) H⊇F (G H).因此(F G) H=F (G H).(2)任取<x,y>,<x,y>∈(F G)-1⇔<y,x>∈F G⇔∃t(<y,t>∈F∧<t,x>∈G)⇔∃t(<t,y>∈F-1∧<x,t>∈G-1)⇔∃t(<x,t>∈G-1∧<t,y>∈F-1)⇔<x,y>∈G-1 F-1 .定理7.3:设R是A上的关系,则R I A = I A R = R .证明:任取<x,y>,<x,y>∈R I A⇔∃t(<x,t>∈R∧<t,y>∈I A)⇔∃t(<x,t>∈R∧t=y)⇒<x,y>∈R<x,y>∈R⇒<x,y>∈R∧y∈A⇒<x,y>∈R∧<y,y>∈I A⇒<x,y>∈R I A从而有R I A=R.同理可证I A R=R .定理7.4:设F,G,H为任意关系,则(1)F (G∪H)=(F G)∪(F H)(2)(G∪H) F=(G F)∪(H F)(3)F (G∩H)⊆F G∩F H(4)(G∩H) F⊆G F∩H F .证明:只证(3)式.任取<x,y>,<x,y>∈F (G∩H)⇔∃t(<x,t>∈F∧<t,y>∈G∩H)⇔∃t(<x,t>∈F∧(<t,y>∈G∧<t,y>∈H))⇔∃t((<x,t>∈F∧<t,y>∈G)∧(<x,t>∈F∧<t,y>∈H)) ⇒∃t(<x,t>∈F∧<t,y>∈G)∧∃t(<x,t>∈F∧<t,y>∈H) ⇔<x,y>∈F G∧<x,y>∈F H⇔<x,y>∈F G∩F H .定理7.5:设F为关系,A,B为集合,则(1)F|(A∪B)=F|A∪F|B(2)F[A∪B]=F[A]∪F[B](3)F|(A∩B)⊆F|A∩F|B(4)F[A∩B]⊆F[A]∩F[B]证明:只证(4).任取y,若y∈F[A∩B],则存在x,使得<x,y> ∈F且x∈A∩B,那么有x∈A且x∈B,也就存在x,使得<x,y> ∈F且x∈A,故y∈F[A];同时还有<x,y>∈F且x∈B.故y∈F[B].从而y∈F[A]∩F[B].因此F[A∩B]⊆F[A]∩F[B] .定义7.10:设R为A上的关系,n为自然数,则R的n次幂定义为:(1)R0={<x,x>|x∈A}=I A ;(2)R n+1=R n R .*利用关系矩阵计算R n:设M为R的关系矩阵,则R n的关系矩阵为M n.即n个M的乘积,其中的加法为逻辑加法:1+1=1, 1+0=1, 0+1=1, 0+0=0.例4:设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}关系矩阵如下.计算后可知,M4=M2.即R4=R2,从而有R2=R4=R6=…R3=R5=R7=…M=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0000100001010010 R 0和I A 的关系矩阵为单位矩阵.定理7.6:设A 为n 元集,R 是A 上的关系,则存在自然数s 和t,使得R s =R t .证明:设R 为A 上的关系,对任意自然数k,R k 都是A ×A 的子集.又知|A ×A|=n 2,|P(A ×A)|=22n ,即A ×A 的不同子集仅有 22n 个,当列出R 的各次幂R 0,R 1,…,R m 时(m=22n ),必有自然数s 和t,使得R s =R t .*如上例中的R 2=R 4.定理7.7: 设R 为A 上的关系,m,n ∈N,则(1) R m R n =R m+n ;(2) (R m )n =R mn .证明:用归纳法.(1) 对任意给定的m ∈N,施归纳于n.若n=0,则有R m R 0=R m I A =R m =R m+0 .假设R m R n =R m+n .R m R n+1=R m (R n R)=(R m R n ) R=R m+n R=R m+n+1.*最后一步由定义可得.(2) 对于任意给定的m ∈N,施归纳于n.若n=0,则有(R m )0=I A =R 0=R m ×0.假设(R m)n,则有(R m)n+1=(R m)n R m=R mn R m=R mn+m=R m(n+1).所以对一切m,n∈N,有(R m)n=R mn.定理7.8:设R为A上的关系,若存在自然数s,t(s<t)使得R s=R t,则(1)对任何k∈N,有R s+k=R t+k .(2)对任何k,i∈N,有R s+kp+i=R s+i,其中p=t―s.(3)令S={R0,R1,…,R t-1},则对于任意的q∈N,有R q∈S.证明:(1)R s+k=R s R k=R t R k=R t+k .(2)对k归纳.若k=0,则有R s+0×p+i=R s+i .假设R s+kp+i=R s+i,其中p=t―s,则R s+(k+1)p+i=R s+kp+i+p=R s+kp+i R p=R s+i R p=R s+p+i=R s+t-s+i=R t+i=R s+i .(3)任取q∈N,若q<t,显然有R q∈S.若q≥t,则存在自然数k和i使得q=s+kp+i, 其中0≤i≤p-1.于是R q=R s+kp+i=R s+i,而s+i≤s+p―1=s+t―s―1=t―1.这就证明了R q∈S.作业:1.设A={0,1,2,3},R是A上的关系,且R={<0,0>,<0,3>,<2,0>,<2,1>,<2,3>,<3,2>}给出R的关系矩阵和关系图.2.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>}.求A∪B,A∩B,domA,domB,dom(A∪B),ranA,ranB,ran(A∩B),fld(A―B).3.设A={a,b,c,d},R1和R2为A上的关系.其中:R1={<a,a>,<a,b>,<b,d>}R2={<a,d>,<b,c>,<b,d>,<c,b>}求R1 R2, R2 R1,2R, 32R.14.证明:定理7.4的(1),(4)和定理7.5的(3).。