离散数学集合论部分

离散数学集合论部分第一页，共一百九十二页，编辑于2023年，星期一对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如程序设计语言、数据结构、形式语言等都离不开子集、幂集、集合的分类等概念。集合成员表和范式在逻辑设计、定理证明中也都有重要应用。本部分从集合的直观概念出发，介绍了集合论中的一些基本概念和基本理论。第二页，共一百九十二页，编辑于2023年，星期一

集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。集合论总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。集合论的特点是研究对象的广泛性，集合是各种不同对象的抽象，这些对象可以是数或图形，也可以使任意其它事务。

第三页，共一百九十二页，编辑于2023年，星期一1.二十六个英文字母可以看成是一个集合；2.所有的自然数看成是一个集合；3.重庆邮电大学计算机学院2010级的本科学生可以看成是一个集合；4.这间教室中的所有座位可以看成是一个集合。例:集合的基本概念第四页，共一百九十二页，编辑于2023年，星期一

组成一个集合的那些对象或单元称为这个集合的元素。通常，用小写的英文字母a,b,c,…表示集合中的元素。元素可以是单个的数字也可以是字母，还可以是集合。

如：A={a,c,b};B={{a},{b},{c}}集合的元素第五页，共一百九十二页，编辑于2023年，星期一元素与集合的属于关系：设A是一个集合，a是集合A中的元素，元素与集合的关系：属于∈；不属于

若a是集合A中的元素记为aA，读作a属于A；若a不是集合A中的元素，则记为aA，读作a不属于A。例如：A是正偶数集合，则2A，4A，6A；而1A，3A，19A。第六页，共一百九十二页，编辑于2023年，星期一特别注意：①集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不改变，即{a,a,b,c,d,c}={a,b,c,d}。②集合的元素可以是具体事物，可以是抽象概念，也可以是集体，如一本书，一支笔；集合{1,2,3}可以是集合B={一本书，一支笔，{1,2,3}}的元素。特别地，以集合为元素的集合称为集合族或集合类如A={{1,2,3},{8,9,6}}。③集合中元素之间可以有某种关联，也可以彼此毫无关系。第七页，共一百九十二页，编辑于2023年，星期一

有限集A中所含元素的个数称为集合的元数。记作：|A|

如：A={1,3,2,4,5,9}则|A|=

6；

设A是所有英文字母组成的集合，则

A=26。特别，||=0集合的元素数第八页，共一百九十二页，编辑于2023年，星期一列举法(列元素法)：将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：V={a,b,c,d,e}或B={1,2,3,4,5,6,……}。描述法(谓词表示法):将集合元素的条件或性质用文字或符号在花括号内竖线后面表示出来。A={x|关于x的一个命题P};如：B={x|0<x<10};B={x|x=a2,a是自然数}。集合的表示法第九页，共一百九十二页，编辑于2023年，星期一EAae文氏图

用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素。

例如：集合A={a,b,c,d,e}，用文氏图表示如下:dcb第十页，共一百九十二页，编辑于2023年，星期一几类特殊集合:N={0,1,2,3,···}，即自然数集合。Z={···,-2,-1,0,1,2,3,···}，即整数集合。Z+={1,2,3,···}，即正整数集合。Q=有理数集合。R=实数集合。C=复数集合。第十一页，共一百九十二页，编辑于2023年，星期一确定性；互异性；无序性；多样性；集合的特征第十二页，共一百九十二页，编辑于2023年，星期一任何一个对象，或者是这个集合的元素，或者不是，二者必居其一；

例如：A={x|x是自然数，且x<100}； B={x|x+1=3}； C={x|x是大学生}。确定性第十三页，共一百九十二页，编辑于2023年，星期一集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。

例如：集合A={a,b,c,c,b,d}，实际上，应该是A={a,b,c,d}。

再如{1,2,3,2,4}={1,2,3,4}。互异性第十四页，共一百九十二页，编辑于2023年，星期一集合与其中的元素的顺序无关；

例如：

集合{a,b,c,d,e}、{d,c,e,a,b}、{e,c,d,b,a}，都是表示同一个集合。集合{4,2,1,3}={1,2,3,4}。无序性第十五页，共一百九十二页，编辑于2023年，星期一集合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征。

例如：

A={a,{a},{{a},b},{{a}},1}；

A={1,a,*,-3,{a,b},{x|x是汽车},地球}注意:对于任何集合A,都有AA。多样性第十六页，共一百九十二页，编辑于2023年，星期一设A，B是两个集合，若B的元素都是A的元素，则称B是A的子集，也称A包含B，或B被A包含，记以BA

，或AB

。若BA

，且AB，则称B是A的真子集，也称A真包含B，或B真包含于A，记以AB，或BA。子集：第十七页，共一百九十二页，编辑于2023年，星期一例3.1设A={a,b,{c},{a},{a,b}}试判断下列表达式正确与否。（1）aA（2）{a}A（3）{a}

A（4）ØA（5）Ø

A（6）bA（7）{b}A（8）{b}

A（9）{a,b}A

(10){a,b}A(11)cA(12){c}A(13){c}

A(14){a,b,c}A。

解：(4)，(7)，(11)，(13),(14)错误。第十八页，共一百九十二页，编辑于2023年，星期一例3.2

对于任意集合A,B和C,下述论断是否正确（1）若AB,BC则AC（2）若AB,BC则AC（3）若AB,BC则AC

解：（1）√（2）×（3）×对(3)举反例A=Ø,B={1},C={{1}}。第十九页，共一百九十二页，编辑于2023年，星期一例3.3设A={{1,2,3},{4,5},{6,7,8}}下列选项正确的是（3）；（1）1A（2）{1,2,3}

A

（3）{{4,5}}

A（4）ØA

例3.4

下列各选项错误的是（2）；（1）ØØ

（2）Ø

Ø

（3）Ø{

Ø}

（4）Ø{

Ø}

例3.5

在0___Ø之间填上正确的符号：（4）（1）=

（2）

（3）

（4）

第二十页，共一百九十二页，编辑于2023年，星期一当两个集合A和B的元素完全一样，即A，B实际上是同一个集合时，则称集合A，B相等，记为A=B。

符号化表示为：A=BAB∧BA

例：设A={x|x是偶数，且0<x<10}，B={2,4,6,8}，则A=B。集合相等第二十一页，共一百九十二页，编辑于2023年，星期一注：说明两个集合A、B相等，需说明两个问题：1、A是集合B的子集（AB）（任意元素a∈A，有a∈B）2、B是集合A的子集（AB）

（任意元素a∈B，有a∈A）第二十二页，共一百九十二页，编辑于2023年，星期一集合的包含关系也可表成AB(x)(xAxB)这表明，要证明AB，只需对任意元素x，有下式xAxB成立即可。第二十三页，共一百九十二页，编辑于2023年，星期一空集不含任何元素的集合叫做空集，记作φ。空集的符号化表示为：={x|P(x)P(x)}。其中P(x)为任何谓词公式。

如：A={x|x∈R∧x2+1=0}。该方程无实数解。

注意：φ≠{φ}由定义可知，对任何集合A，有A。这是因为任意元素x，公式xxA总是为真。第二十四页，共一百九十二页，编辑于2023年，星期一注意：与{}是不同的。{}是以为元素的集合，而没有任何元素，能用构成集合的无限序列：，{}，{{}}，···该序列除第一项外，每项均以前一项为元素的集合。第二十五页，共一百九十二页，编辑于2023年，星期一定理：空集是一切集合的子集。证明：对于任何集合A，由子集定义有,φAx(x∈φx∈A)右边的蕴涵式中前件为x∈φ为假，所以整个蕴涵式对一切x为真，所以φA为真推论：空集是唯一的。

证明:如不唯一,设存在空集φ1和φ2,由空集是一切集合的子集得φ1φ2和φ2φ1。根据集合相等的定义得，φ1=φ2第二十六页，共一百九十二页，编辑于2023年，星期一全集：

如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为E或U。它可形式地表为E={x|P(x)P(x)}。其中P(x)为任何谓词公式。第二十七页，共一百九十二页，编辑于2023年，星期一注意符号和意义的区别：表示元素与集合之间的关系，而则表示集合与集合之间的关系。但由于集合的抽象性，集合中的元素可以是集合，故可以发生如：AB且AB的情形

例设A={{1,2,3},1,2,3}，则{1,2,3}

A且{1,2,3}

A。

注意：第二十八页，共一百九十二页，编辑于2023年，星期一对任意集合A,有AA。空集是任意集合的子集，且空集是唯一的。对于任意两个集合A、B，A=B的充要条件是AB且BA。（这个结论非常简单，但它非常重要，很多证明都是用这个方法或思路来证明。）重要结论第二十九页，共一百九十二页，编辑于2023年，星期一设A是集合，A的所有子集为元素做成的集合称为A的幂集,记以P(A)

符号化表示为：P(A)={x|xA}。例：A={a,b,c}，则

P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。幂集第三十页，共一百九十二页，编辑于2023年，星期一例3.6设A={a,{a}}下列选项错误的是A.aP(A)B.{a}P

(A)C.{{a}}P(A)D.{{a}}P

(A)例3.7幂集P(P(P()))为（C）A.{{

},{,{

}}}B.{,{,{

},{}}

C.{,{,{

}},{{}},{

}}D.{,{,{

}}}∵P(A)={,{a},{{a}},{a,{a}}}第三十一页，共一百九十二页，编辑于2023年，星期一例3.8判断下面的关系是否正确,并简要说明理由。⑴{a,b}{a,b,c,{a,b,c}}⑵{a,b}∈{a,b,c,{a,b,c}}⑶{a,b}{a,b,{{a,b}}}⑷{a,b}∈{a,b,{{a,b}}}第三十二页，共一百九十二页，编辑于2023年，星期一解答：

对选项⑴,因为{a,b}中每个元素(只有a和b)均在集合{a,b,c,{a,b,c}}对选项⑶,因为{a,b}中每个元素(只有a和b)均在集合{a,b,{{a,b}}}对选项⑵,集合{a,b,c,{a,b,c}}中含有4个元素，分别为a,b,c,{a,b,c}没有{a,b}，所以不正确。对选项⑷,集合{a,b,{{a,b}}}中含有3个元素，分别为a,b,{{a,b}}没有{a,b}，所以不正确。第三十三页，共一百九十二页，编辑于2023年，星期一若A为有穷集，|A|=n，则

|2A|=Cn0+Cn1+

…+Cnn=2n。xP(A)当且仅当xA。设A、B是两个集合，AB当且仅当P(A)P(B)。幂集的性质第三十四页，共一百九十二页，编辑于2023年，星期一并

AB={x|xA

xB}；交

AB={x|xA

xB}；相对补

AB={x|xA

xB}；对称差

AB=(AB)(BA)=(AB)(AB)；绝对补

A=EA。§3.2集合的基本运算第三十五页，共一百九十二页，编辑于2023年，星期一ABAAB~AABABA-BABAABBCAB(AB)-C集合运算对应的文氏图表示第三十六页，共一百九十二页，编辑于2023年，星期一并和交运算可以推广到有穷个集合上，即

A1A2…An={x|xA1xA2…xAn}

A1A2…An={x|xA1xA2…xAn}某些重要结果：ABA

ABAB=

AB=AB=A第三十七页，共一百九十二页，编辑于2023年，星期一集合的广义交和广义并

设S为集合，S的元素的元素构成的集合称为S的广义并，记为S，其中S={xz(zSxz}；

设S非空集合，S的元素的公共元素构成的集合称为S的广义交，记为S，其中S={xz(zSxz}。第三十八页，共一百九十二页，编辑于2023年，星期一说明：（1）规定=，无意义。（2）若，则由定义不难证明S=S=（3）并运算和广义并运算的运算符相同，但前者是二元运算，后者是一元运算，因此在运算过程中不会对产生误解。第三十九页，共一百九十二页，编辑于2023年，星期一

例：设集合A={{a,b,c},{a,c,d},{a,c,e}}，求A，A，A，A，A，A。解：

A={a,b,c,d,e}；A={a,c}；A=abcde；A=ac；A=ac；A=abcde。第四十页，共一百九十二页，编辑于2023年，星期一优先级一般地,一元运算符(补集,幂集,广义并,广义交)优先于二元运算符(差集,并集,交集,对称差,笛卡儿积)；二元运算符优先于集合关系符(∈,,＝,)。此外,许多集合表达式里还使用到联结词,和逻辑关系符以及括号,我们规定:(1)集合运算优先于逻辑运算；(2)括号内优先于括号外；(3)同一括号内,同一优先级按从左至右运算。第四十一页，共一百九十二页，编辑于2023年，星期一集合运算律幂等律：A∪A＝A；A∩A＝A同一律：A∪＝A；A∩E=A零律：A∪E=E；A∩＝结合律：(A∪B)∪C＝A∪(B∪C)；(A∩B)∩C＝A∩(B∩C)交换律：A∪B＝B∪A；A∩B＝B∩A分配律：A∪（B∩C）＝（A∪B）∩(A∪C)；A∩(B∪C)=(A∩B)∪(A∩C)第四十二页，共一百九十二页，编辑于2023年，星期一排中律：矛盾律：吸收律：A∩（A∪B）＝AA∪(A∩B)＝A摩根律：双重否定律：第四十三页，共一百九十二页，编辑于2023年，星期一其它常用结论：A∩BA,A∩BB；AA∪B,BA∪B；A-BA，A-B=A∩~B；A∪B=BABA∩B=AA-B=；

AB=BA；(AB)C=A(BC)

A=A；AA=；AB=ACB=C。第四十四页，共一百九十二页，编辑于2023年，星期一集合等式的证明，可采用命题逻辑的等值式证明，其基本思想是互为子集：欲证:A=B即证:即证:对任意的x,，当上述过程可逆时，可以合并为对任意的x,集合相等的证明方法第四十五页，共一百九十二页，编辑于2023年，星期一例：证明下列集合恒等式。（1）A∪（B∩C）＝（A∪B）∩(A∪C)（2）（3）证明：(1)对任意的x第四十六页，共一百九十二页，编辑于2023年，星期一(2)对任意的x(3)对任意的x第四十七页，共一百九十二页，编辑于2023年，星期一例3.3.2证明：（1）（2）AB=（A∪B）-（A∩B）证明：(1)(2)AB=（A-B）（B-A）第四十八页，共一百九十二页，编辑于2023年，星期一例证明(A∪B)-C=(A-C)∪(B-C).证明:对于xx∈(A∪B)-Cx∈(A∪B)∧xC(

x∈A∨x∈B)∧xC(

x∈A∧xC)∨(x∈B∧xC)x∈(A-C)∨x∈(B-C)x∈(A-C)∪(B-C)∴(A∪B)-C=(A-C)∪(B-C)第四十九页，共一百九十二页，编辑于2023年，星期一例证明证明：(1)必要性：对任意的X,因此，。(2)充分性：对任意的x，因此，结论得证。第五十页，共一百九十二页，编辑于2023年，星期一例求在1和1000之间不能被5或6，也不能被8整除的数的个数解：设1到1000之间的整数构成全集E，A，B，C分别表示其中可被5，6或8整除的数的集合。解：在A∩B∩C中的数一定可被5,6和8的最小公倍数5,6,8=120整除，即A∩B∩C=1000/5,6,8=8同样可得A∩B=1000/5,6=33；

A∩C=1000/5,8=25；B∩C=1000/6,8=41；第五十一页，共一百九十二页，编辑于2023年，星期一然后计算A=1000/5=200；B=1000/6=166；C=1000/8=125从而得到A∪B∪C=200+100+33+67=400所以，不能被5或6,也不能被8整除的数有600个。150100671733258第五十二页，共一百九十二页，编辑于2023年，星期一对上述子集计数：

|S|=1000；|A|=1000/5=200；|B|=1000/6=133；|C|=1000/8=125；|AB|=1000/30=33；|BC|=1000/40=25|BC|=1000/24=41；|ABC|=1000/120=8。代入公式：

N=1000(200+133+125)+(33+25+41)8=600。这个方法叫容斥原理。第五十三页，共一百九十二页，编辑于2023年，星期一称为包含排斥原理，简称容斥原理。容斥原理定理：有穷集S中不具有p1,p2,…,pm元素数是第五十四页，共一百九十二页，编辑于2023年，星期一推论设A1,A2,…,An是n个集合，则第五十五页，共一百九十二页，编辑于2023年，星期一例

某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球(指篮球或排球)，求不会打这三种球的人数。解：设会打排球、网球、篮球的学生集合分别为A，B和C，则有A=12，B=6，C=14，S=25A∩C=6，B∩C=5，A∩B∩C=2第五十六页，共一百九十二页，编辑于2023年，星期一现在求A∩B，因为会打网球的人都会打另一种球，即篮球和排球，而其中会打篮球的有5人，那么另一个人肯定会打排球但不会打篮球，再加上会打三种球的2人，共有3人会打排球和网球，即A∩B=3，根据容斥定理有A∩B∩C=25-（12+6+14）+（3+6+5）-2=5324排球12篮球14网球6155不会打三种球人数为：25-(12+5+3)=5第五十七页，共一百九十二页，编辑于2023年，星期一课堂练习：证明下列等式第五十八页，共一百九十二页，编辑于2023年，星期一第四章二元关系和函数

说起关系这个词，对我们并不陌生，世界上存在着各种各样的关系，人与人之间的“同志”关系；“同学”关系；“朋友”关系；“师生”关系；“上下级”关系；“父子”关系；两个数之间有“大于”关系；“等于”关系和“小于”关系；两个变量之间有一定的“函数”关系；计算机内两电路间有导线“连接”关系；程序间有“调用”关系等等。所以对关系进行深刻的研究，对数学与计算机科学都有很大的用处。第五十九页，共一百九十二页，编辑于2023年，星期一集合的笛卡尔积与二元关系由两个元素x,y（允许x=y）按一定顺序排列成的二元组叫做一个有序对或序偶，记作<x,y>,其中x是它的第一元素，y是它的第二元素。有序对<x,y>具有以下性质：(1)当x≠y时，<x,y>≠<y,x>(2)<x,y>=<w,v>x=w∧y=v例：已知<x+3,y-2>=<y+7,3y-x>，求x和y。解：由有序对相等的充要条件得x+3=y+7y-2=3y-x解得x=6,y=2。第六十页，共一百九十二页，编辑于2023年，星期一一个有序n元组

(n≥3)是一个有序对，其中第一个元素是一个有序n-1元组，一个有序n元组记作<x1,x2,…,xn>,即<x1,x2,…,xn>=<

<x1,x2,…,xn-1>,xn>

例：空间直角坐标系中点的坐标<1,-1,3>,<2,4.5,0>等都是有序3元组。n维空间中点的坐标或n维向量都是有序n元组。形式上也可以把<x>看成有序1元组。第六十一页，共一百九十二页，编辑于2023年，星期一设A，B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作A×B。笛卡儿积的符号化表示为：A×B={<x,y>|x∈A∧y∈B}例：若A={1,2},B={a,b,c},则A×B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}B×A={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}易知：若|A|=m,(即集合A的元素的个数),|B|=n,则|A×B|=|B×A|=mn第六十二页，共一百九十二页，编辑于2023年，星期一

有序对就是有顺序的数组，如<x,y>，x,y的位置是确定的，不能随意放置。

注意：有序对<a，b><b,a>，以a,b为元素的集合{a,b}={b,a}；有序对(a,a)有意义，而集合{a,a}不成立。

笛卡儿积是一种集合合成的方法，把集合A，B合成集合A×B，规定A×B＝{<x,y>xA,yB}。由于有序对<x,y>中x,y的位置是确定的，因此A×B的记法也是确定的，不能写成B×A。

笛卡儿积也可以多个集合合成A1×A2×…×An。

笛卡儿积的运算性质。第六十三页，共一百九十二页，编辑于2023年，星期一笛卡儿积的性质：1、对任意集合A，根据定义有A×φ=φ×A=φ2、一般来说，笛卡儿积不满足交换律，即A×B≠B×A（当A≠BB≠φ、A≠φ时）3、笛卡儿积不满足结合律，即(A×B)×C≠A×(B×C)（当A≠φ∧B≠φ∧C≠φ时）4、笛卡儿积运算对并和交运算满足分配律，即

A×(B∪C)=(A×B)∪(A×C)

(B∪C)×A=(B×A)∪(C×A)

A×(B∩C)=(A×B)∩(A×C)

(B∩C)×A=(B×A)∩(C×A)第六十四页，共一百九十二页，编辑于2023年，星期一例：证明(B∩C)×A=(B×A)∩(C×A)对于<x,y><x,y>∈(B∩C)×Ax∈(B∩C)∧y∈Ax∈B∧x∈

C∧y∈Ax∈B∧x∈C∧y∈A∧y∈A(x∈B∧y∈A)∧(x∈C∧y∈A)<x,y>∈B×A∧<x,y>∈C×A<x,y>∈(B×A)∩(C×A)∴(B∩C)×A=(B×A)∩(C×A)第六十五页，共一百九十二页，编辑于2023年，星期一例：设A，C，B，D为任意集合，判断以下命题是否为真，并说明理由。(1)A×B=A×C=>B=

C。(2)A-(B×C)=(A-B)×(A-C)。(3)存在集合A,使得AA×A。解：(1)不一定为真。反例A=φ,B、C为任意不相等的非空集合。(2)不一定为真。反例A={1},B={2},C={3}.(3)为真。当A=φ时成立。第六十六页，共一百九十二页，编辑于2023年，星期一

设A1,A2,…,An,是集合(n≥2),它们的n阶笛卡儿积记作A1×A2×…×An，其中A1×A2×…×An={<x1,x2,…,xn>

|x1A1∧x2A2∧…∧xnAn

}。当A1=A2=…=An=A时,将起n阶笛卡儿积记作An例，A={a,b},则：A3=A×A×A={a,b}×{a,b}×{a,b}={<a,a,a>,<a,a,b>,<a,b,a>,<a,b,b>,<b,a,a>,<b,a,b>,<b,b,a>,<b,b,b>}。第六十七页，共一百九十二页，编辑于2023年，星期一例：设集合A={a,b},B={1,2,3},C={d},求A×B×C，B×A。解：

先计算A×B＝{<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}A×B×C＝{<a,1>,<a,2>,<a,3>,<b,1>,<b,2>,<b,3>}×{d}＝{<a,1,d>,<a,2,d>,<a,3,d>,<b,1,d>,<b,2,d>,<b,3,d>}B×A＝{<1,a>,<2,a>,<3,a>,<1,b>,<2,b>,<3,b>}

。第六十八页，共一百九十二页，编辑于2023年，星期一例：设集合A＝{1,2},求A×P(A)。解：P(A)={,{1},{2},{1,2}} A×P(A)＝{1,2}×{,{1},}{2},{1,2} ={<1,>,<2,>,<1,{1}>,<2,{1}>,<1,{2}>,<2,{2}>,<1,{1,2}>,<2,{1,2}>}第六十九页，共一百九十二页，编辑于2023年，星期一

如果一个集合符合以下条件之一：(1)集合非空，且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系，记作R，简称为关系。对于二元关系R，若<x,y>∈R,可记作xRy;如果<x,y>R,则记作xRy。例：R1={<1,2>,<a,b>}aR1b,1R12。第七十页，共一百九十二页，编辑于2023年，星期一二元关系是两种客体之间的联系，例如某学生学习语文、数学、外语，表示为：A＝{语文,数学,外语}功课的成绩分四个等级，记作B＝{A，B，C，D}于是该生成绩的全部可能为A×BA×B＝{<语文,A>,<语文,B>,<语文,C>,<语文,D>,<数学,A>,<数学,B>,<数学,C>,<数学,D>,<外语,A>,<外语,B>,<外语,C>,<外语,D>}而该生的实际成绩P＝{<语文,B>,<数学,A>,<外语,D>}P是A×B的一个子集，它表示了功课与其成绩的一种关系。由此可见：两个集合之间的二元关系，实际上就是两个元素之间的某种相关性。第七十一页，共一百九十二页，编辑于2023年，星期一设A，B为集合，A×B的任何子集所定义的二元关系叫做从A到B的二元关系；特别当A=B时则叫做A上的二元关系。例：若A={a,b}，B={1,2,3}，则A×B={<a,1>,<a,2>,<a,3>,<b,1>,<b,2><b,3>}令R1={<a,1>,<a,3>,<b,1>},R2={<a,2>,<b,1><b,2>},R3={<a,1>}。因为R1A×B，R2A×B，R3A×B，所以R1,

R2和R3均是由A到B的二元关系。第七十二页，共一百九十二页，编辑于2023年，星期一又例：若A={a,b}，B={1,2,3}，则

B×A={<1,a>,<1,b>,<2,a>,<2,b>,<3,a><3,b>}令R4={<1,a>,<1,b>},R5={<2,a>,<3,a><3,b>},因为R4B×A，R5B×A，所以R4和R5均是由B到A的关系。又B×B={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}。令R6={<1,1>，<3,2>},R7={<3,2>,<2,1><1,3>}因为R6B×B，R7B×B，所以R6和R7均是集合B上的关系。第七十三页，共一百九十二页，编辑于2023年，星期一若集合|A|=n,则集合A上的二元关系有多少个？答：|A|=n，则|A×A|=n2,A×A的任一个子集就是A上的二元关系，即P(A)=2n个。２

例

A={1,2}则A×A有2n个不同的二元关系；A×A={1,2}×{1,2}={<1

1>,<1,2>,<2,1>,<2,2>}。A×A的任一个子集就是A×A的幂集，即P(A)P(A)={,{<1,1>},{<1,2>},{<2,1>},{<2,2>}{<1,1>,<1,2>},{<1,1>,<2,1>},{<1,1>,<2,2>}

{<1,2>,<1,1>},{<1,2>,<2,1>},{<1,2>,<2,2>}

{<2,2>,<1,1>},{<2,2>,<1,2>},{<2,2>,<2,1>}

{<1,1>,<1,2>,<2,1>},

{<1,1>,<1,2>,<2,2>},{<1,1>,<2,1>,<2,2>},{<1,2>,<2,1>,<2,2>}{<1,1>,<1,2>,<2,1>,<2,2>}}２第七十四页，共一百九十二页，编辑于2023年，星期一三类特殊的关系空关系：对于任何集合A，空集φ是A×A的子集，称作A上的空关系；全关系：定义EA={<x,y>|x∈A∧y∈A}=A×A为全域关系；恒等关系：定义IA={<x,x>|x∈A}为A上恒等关系。例：若A={1,2,3}，则EA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}

IA={<1,1>,<2,2>}。第七十五页，共一百九十二页，编辑于2023年，星期一例：设A={1,2,3,4}，请表示下列关系。(1)R={<x,y>|x是y的倍数}(2)R={<x,y>|(x-y)2∈A}(3)R={<x,y>|x除y是素数}(4)R={<x,y>|x≠y}解：(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<2,1>,<3,1>,<4,1>,<4,2>}；(2)R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>,<2,4>,<4,2>,<3,4>,<4,3>}；(3)R={<1,2>,<1,3>,<2,4>}；(4)R=

<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}第七十六页，共一百九十二页，编辑于2023年，星期一关系表示法有穷集合上的二元关系的三种表示方法：集合表示法（前已使用）关系矩阵法关系图关系矩阵是表示关系的另一种有效的方法，其优点是可以利用矩阵作为研究关系的手段，而且这样做便于计算机进行处理。

第七十七页，共一百九十二页，编辑于2023年，星期一设R：AB，A和B都是有限集，且

|A|=n,|B|=m,A,B中的元素已按一定的次序排列若A={x1,x2,…,xn},B={y1,y2,…,ym}且RAB,若则称矩阵M(R)=(rij)nm为R的关系矩阵。关系矩阵法第七十八页，共一百九十二页，编辑于2023年，星期一

0111MR=001100010000例

A={1,2,3,4},R为A上的小于关系，则R={<1,2>,<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}R的关系矩阵为：12341234第七十九页，共一百九十二页，编辑于2023年，星期一例:设集合A＝{2,3,4},B={8,9,12,14}。R是由A到B的二元关系，定义：R={<a,b>|a整除b}写出R的表达式和关系矩阵。

解：R={<2,8>,<2,12>,<2,14>,<3,9>,<3,12>,<4,8>,<4,12>}R的关系矩阵：

第八十页，共一百九十二页，编辑于2023年，星期一关系图关系图是表示关系的一种直观形象的方法，设R：AB，A和B都是有限集，A={x1,x2,…,xn},B={y1,y2,…,ym}关系R的有序对<xi,yj>可用图中从结点xi到yj的有向边表示，这样即可将关系用图表示之。例设R:AB，A={x1,x2,x3,x4},B={y1,y2,y3}R={<x1,y2>,<x2,y1>,>,<x2,y2>，<x2,y3><x3,y3>}R的关系如下图所示x1x2x3x4y1y2y3第八十一页，共一百九十二页，编辑于2023年，星期一设R是在A上的二元关系，A={x1,x2,…,xn}关系R的有序偶<xi,xj>可用图中从结点xi到xj的有向边表示，这样即可将关系用图表示之。

例：设R:AA，A={a,b,c,d}R={<a,b>,<a,c>,<b,a>,<b,c>,<c,c>}R的关系如下图所示：abcd第八十二页，共一百九十二页，编辑于2023年，星期一

例：设集合A={a,b,c,d},R是A上的关系R={<a,a>,<a,b>,<a,c>,<b,c>,<d,c>,<d,d>},试以关系矩阵和关系图来表示关系R。解：（1）关系矩阵为：（2）关系图为：第八十三页，共一百九十二页，编辑于2023年，星期一关系的运算（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=domRranR例：设R={<1,1>,<1,4>,<2,2>,<3,3>}则domR={1，2，3}ranR={1，2，3，4}fldR={1，2，3，4}第八十四页，共一百九十二页，编辑于2023年，星期一限制关系设R为二元关系，A是集合（1）R在A上的限制，记作RA,其中RA={<x,y>|xRyxA}（2）A在R下的象，记作R[A]，其中R[A]=ran(RA)例：设集合A={1,2,3,4},R是A上的关系R={<1,1>,<1,3>,<2,4>,<3,2>,<3,4>,<4,1>},集合B={1,2,4},试求RB及R[B]。解：RB={<1,1>,<1,3>,<2,4>,<4,1>}；R[B]={1，3，4}。第八十五页，共一百九十二页，编辑于2023年，星期一逆运算设R为二元关系，称为R的逆关系，其中={<x,y>|<y,x>R}

定理4.1设F是任意关系，则（1）（2）证明：（1）对任意的<x,y>第八十六页，共一百九十二页，编辑于2023年，星期一（2）对任意的y对任意的x第八十七页，共一百九十二页，编辑于2023年，星期一复合运算设F,G为二元关系G对F的右复合记作FهG,其中FهG={<x,y>|t(<x,t>F<t,y>G}。说明：（1）本书采用右复合的规则，而有的教材采用左复合规则，两者都可行，只是需要注意它们的区别，从变换的角度来说，G对F的右复合是先F变换后G变换，而G对F的左复合是先G变换后F变换。（2）一般来说，并没有FهG等于GهF，请读者仔细注意其区别。例：设F={<3,3>,<6,2>},G={<2,3>},则求FهF，GهG，FهG和GهF。解：FهF={<3,3>}，GهG=

FهG={<6,3>}GهF={<2,3>}。第八十八页，共一百九十二页，编辑于2023年，星期一例：设有集合A={4,5,8,15},B={3,4,5,9,11}C={1,6,8,13},F是由A到B的关系,G是由B到C的关系,分别定义为F={<a,b>||b-a|=1}G={<b,c>||b-c|=2或|b-c|=4}求合成关系GF和FG

解：先求GF,由题意知F={<4,3>,<4,5>,<5,4>,<8,9>}；G={<3,1>,<4,6>,<4,8>,<5,1>,<9,13>,<11,13>}；GF={<4,1>,<5,6>,<5,8>,<8,13>}。

第八十九页，共一百九十二页，编辑于2023年，星期一定理：设F、G、H是任意关系,则(1)(F-1)-1=F(2)dom(F-1)=ranF,ranF-1=domF(3)(FG)H=F(GH)(4)(FG)-1=G-1F-1证明:(1)任取<x,y>,由逆的定义有<x,y>∈(F-1)-1<y,x>∈F-1<x,y>∈F∴(F-1)-1=F(2)任取x,x∈ranF-1y(<y,x>∈F-1)

y(<x,y>∈F)

x∈domF∴ranF-1=domF同理可证dom(F-1)=ranF第九十页，共一百九十二页，编辑于2023年，星期一证明:(3)任取<x,y>,<x,y>∈(FG)H

t(<x,t>∈FG∧<t,y>∈H)ts(<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(GH)(4)任取<x,y>,<x,y>∈(FG)-1<y,x>∈FGt(<y,t>∈F∧

<t,x>∈G)t(<x,t>∈G-1

∧

<t,y>∈F-1)<x,y>∈G-1

F-1

第九十一页，共一百九十二页，编辑于2023年，星期一定理：设F、G、H是任意关系,则(1)F(G∪H)=FG∪FH(2)(G∪H)F=GF∪HF(3)F(G∩H)FG∩FH(4)(G∩H)FGF∩HF证明:(1)任取<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>∈FG∨<x,y>∈FH<x,y>∈FG∪FH第九十二页，共一百九十二页，编辑于2023年，星期一证明:(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>∈FG∧

<x,y>∈FH<x,y>∈FG∩FH第九十三页，共一百九十二页，编辑于2023年，星期一本定理对有限个关系的并和交都成立。R(R1∪R2∪…∪Rn)=RR1∪RR2∪…∪RRn(R1∪R2∪…∪Rn)R=R1

R∪R2

R∪…∪RnRR(R1∩

R2∩…∩Rn)RR1∩RR2∩…∩RRn(R1∩R2∩…∩Rn)RR1

R∩R2R∩…∩RnR第九十四页，共一百九十二页，编辑于2023年，星期一幂运算：设R是A上的关系,n为自然数，则R的n次幂规定如下：(1)R0={<x,x>|x∈A}(2)Rn=Rn-1

Rn≥1由定义可以知道R0就是A上的恒等关系IA，不难证明下面的等式RR0=R=R0

R。由这个等式立即可以得到R1=R0

R=R例：设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>}求R0，R1，R2，R3，R4和R5解：R0={<a,a>,<b,b>,<c,c>,<d,d>}R1=R0

R={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,a>,<b,b>,<c,c>,<d,d>}={<a,b>,<b,a>,<b,c>,<c,d>}。第九十五页，共一百九十二页，编辑于2023年，星期一R2=RR={<a,b>,<b,a>,<b,c>,<c,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R3=R2

R={<a,a>,<a,c>,<b,b>,<b,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}R4=R3

R={<a,b>,<b,a>,<b,c>,<a,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,a>,<a,c>,<b,b>,<b,d>}R5=R4

R={<a,a>,<a,c>,<b,b>,<b,d>}

{<a,b>,<b,a>,<b,c>,<c,d>}={<a,b>,<b,a>,<b,c>,<a,d>}第九十六页，共一百九十二页，编辑于2023年，星期一定理：设R是A上的关系,m,n为自然数，则下面的等式成立(1)Rm

Rn=Rm+n(2)(Rm)n=Rmn证明：(1)任给m，对n作归纳法。

n=0时，Rm•R0=Rm=Rm+0。

假设Rm•Rn=Rm+n，那么Rm•Rn+1=Rm•(Rn•R1)=(Rm•Rn)•R1=Rm+n•R1=Rm+n+1=Rm+(n+1)。(2)任给m，对n作归纳法。

n=0时，(Rm)0=R0=Rm0。

假设(Rm)n=Rmn。那么(Rm)n+1=(Rm)n

•Rm

=Rmn•Rm=Rmn+m=Rm(n+1)

第九十七页，共一百九十二页，编辑于2023年，星期一例:已知集合A={a,b,c,d},A上的关系R={<a,b>,<b,a>,<b,c>,<c,d>}，求。解：法一：由复合定义知={<a,a>,<a,c>,<b,b>,<b,d>}={<a,b>,<a,d>,<b,a>,<b,c>}

法二：关系R矩阵为==第九十八页，共一百九十二页，编辑于2023年，星期一法三：R的关系图为的关系图为

的关系图为第九十九页，共一百九十二页，编辑于2023年，星期一定理

A为n元集,R为A上的关系,则存在自然数s和t，使得Rs=Rt证明：因为A为n元集，所以集合A上的关系为有限N=个，而关系序列存在无限多个关系，故存在自然数s和t，使得Rs=Rt.。第一百页，共一百九十二页，编辑于2023年，星期一设R是A上的关系，R的性质主要有以下5种:(1)自反性：若x(x∈A<x,x>∈R),则称R在A上是自反的。也就是说，对RAA，若A中每个x，都有xRx，则称R是自反的，即A上关系R是自反的x(xAxRx)。该定义表明了，在自反的关系R中，除其它有序对外，必须包括有全部由每个xA所组成的元素相同的有序对。例如：设A={1,2,3},R

是A上的关系，R={<1,1>,<2,2>,<3,3>,<1,2>}则R

是自反的关系的性质第一百零一页，共一百九十二页，编辑于2023年，星期一(2)反自反性：若x(x∈A<x,x>∈R)，则称R在A上是反自反的。也就是说，对RAA，若A中每个x，有xRx，则称R是反自反的，即A上关系R是反自反的x(xAxRx)该定义表明了，一个反自反的关系R中，不应包括有任何相同元素的有序对。例如：设A={1,2,3}，R

是A上的关系，R={<2,3>,<3,2>}

R是反自反的。第一百零二页，共一百九十二页，编辑于2023年，星期一应该指出：

任何一个不是自反的关系，未必是反自反的；任何一个不是反自反的关系，未必是自反的。这就是说，存在既不是自反的也不是反自反的二元关系。例：设A={1,2,3},R

是A上的关系，R={<1,1>,<2,2>}缺少{<3,3>}则R是既不是自反的，也不是反自反的。第一百零三页，共一百九十二页，编辑于2023年，星期一(3)对称性：若xy(x,y∈A∧<x,y>∈R<y,x>∈R),则称R在A上是对称的。也就是说,对RAA,对A中每个x和y,若xRy,则yRx,称R是对称的,即A上关系R是对称的(x)(y)(x,yAxRy→yRx)该定义表明了，在表示对称的关系R的有序对集合中，若有有序对<x,y>，则必定还会有<y,x>。例：设A={1,2,3},R是A上的关系，R4={<1,2>,<2,1>,<2,3>,<3,2>,<2,2>,<3,3>}则R

是对称的。第一百零四页，共一百九十二页，编辑于2023年，星期一(4)反对称性：若xy(x,y∈A∧<x,y>∈R∧x≠y<y,x>R),则称R在A上是反对称的。

也就是说，对RAA，对A中每个x和y，若xRy且yRx，则x=y，称R是反对称的，即A上关系R是反对称的(x)(y)(x,yAxRyyRx→x=y)该定义表明了，