第三章集合与关系-最终版

集合与关系的结构图枚举法有向图矩阵等价关系有向图等价类商集划分偏序关系相容类最大相容类完全覆盖简化图全序哈斯图计算方法运算性质二元关系概念及表示方法性质自反对称传递反对称反自反相容关系运算复合求逆闭包重要元素1第3章集合与关系离散数学河南工业大学信息科学与工程学院2第二篇集合论集合论是现代数学的基础，几乎与现代数学的各个分支都有着密切联系，并且渗透到所有科技领域，是不可缺少的数学工具和表达语言。集合论的起源可以追溯到16世纪末期，为了追寻微积分的坚实基础，开始时，人们仅进行了有关数集的研究。1876～1883年，康托尔(GeorgCantor)发表了一系列有关集合论研究的文章，奠定了集合论的深厚基础。集合论在程序语言、数据结构、编译原理、数据库与知识库、形式语言和人工智能等领域都得到了广泛的应用，并且还得到了发展。康托尔3第四章内容（自学）第三章内容（重点）第二篇集合论主要包括如下内容：集合论初步二元关系函数实数集合与集合的基数4第三章集合与关系本章的主要内容3-1集合的概念和表示法3-2集合的运算3-3包含排斥原理*3-4序偶和笛卡尔积3-5关系和表示3-6关系的性质（重点）3-7复合关系和逆关系3-8关系的闭包（重点）3-9集合的划分和覆盖3-10等价关系与等价类（重点）3-11相容关系3-12序关系51-2节的内容提要集合间的关系3特殊集合4集合的概念1集合的概念1集合的表示方法2集合的表示方法2无限集合5集合的运算561-2节学习要求重点掌握一般掌握11集合的概念及集合间关系2集合的表示3集合运算及定律4幂集P(A)

21集合的归纳法表示2集合的对称差运算73-1集合一、集合的概念集合（SET）：即是由一些确定的彼此不同的客体（事物）汇集到一起组成一个整体，称为集合。讨论：客体：泛指一切，可以是具体的、抽象的。元素(element，成员)：

即组成集合的客体，称之为元素。二、集合的记法通常用带(不带)标号的大写字母A、B、C、...、A1、B1、C1、...、X、Y、Z、...表示集合；通常用带（不带）标号的小写字母a、b、c、...、a1、b1、c1、...、x、y、z、...表示元素。8固定的符号0,1,2,…自然数集合N…,-2,-1,0,1,2,…整数集合

Ip/q,p,q是整数，且q≠0

有理数集合

Q

实数集合

R复数集合

C9三、集合与元素的关系客体a与集合A之间的关系只能是属于和不属于之一。a是集合A的元素或a属于集合A，记为aA，称a是A的成员，A包含a，a在A中。a不是集合A的元素或a不属于集合A，记为aA，或者(aA)，称a不是A的成员，A不包含a，a不在A中。例如，对元素2和自然数集合N，就有2属于N，即2N，对元素-2和自然数集合N，就有-2不属于N，即-2N。有限集：组成集合的元素个数是有限的。|A|：有限集合A中元素的个数。无限集：组成集合的元素个数是无限的。10四、集合的表示方法集合是由它包含的元素完全确定的，为了表示一个集合，通常有：

枚举法（列举法）谓词表示法（隐式法、叙述法）文氏(Venn)图-辅助的集合的表示方法111、枚举法（显式表示法）就是把集合的元素（全部或部分）写在花括号的里面，每个元素仅写一次，不考虑顺序，并用”,”分开。例

（1）命题的真假值组成的集合：S={T,F}

（2）A＝{a，e，i，o，u}12在使用中，分两种情况：（1）当集合中元素个数有限且较少时，将元素全部写出。例1：设集合A是由绝对值不超过3的整数组成。A={-3,-2,-1,0,1,2,3}（2）当集合A元素的个数无限或有限但个数较多时，不能或不需要一一列举出来，只要写出少数元素，以显示出它的规律。（当规律不明确，不能用此方法）。例2：设集合B是由自然数的平方构成的集合。B={0,1,4,9,16,…,n2,…}适用场景：一个集合仅含有限个元素。一个集合的元素之间有明显关系。132、谓词表示法（隐式法、叙述法）用谓词描述集合中元素的属性，称为谓词表示法（叙述法、隐式法）一般表示方法：A＝{x|P(x)}若个体域内，客体a使得P(a)为真，则a∈A，否则aA。例如：大于10的整数的集合：S={x|x∈I∧x>10)}命题的真假值组成的集合：S={F,T}={x|x=F∨x=T}适用场景：一个集合含有很多或无穷多个元素；一个集合的元素之间有容易刻画的共同特征。其突出优点是原则上不要求列出集合中全部元素，而只要给出该集合中元素的特性。P(x)是谓词公式，x具有的性质P代表元素14A3、文氏(Venn)图-辅助的集合的表示方法文氏(Venn)图是一种利用平面上的点构成的图形来形象展示集合的一种方法，用一个矩形的内部表示全集，其他集合用矩形内的园面或一封闭曲线圈成的面积来表示。U15说明：集合中的元素都是不同的，凡是相同的元素，均视为同一个元素；{1,1,2}={1,2}一旦给定了集合A，对于任意客体a，可以准确地判定a是否在A中。

集合中的元素是没有顺序的。

{2,1}={1,2}集合的三大特征1、互异性－2、确定性－3、无序性－集合中的元素可以是集合。如S={a,{1,2},p,{q}}16同一个集合可以用不同的表示方法：

例方程x2-1=0的所有实数解的集合A；谓词法：A={x|xR∧x2-1=0}或A={x|x是实数且x2-1=0}枚举法：A={1，-1}17五、集合与集合的关系（一）包含关系（二）相等关系（三）真包含关系18“包含关系”的谓词表示：

ABBA

(x)(x∈Ax∈B)（一）包含关系例：设A={ADA,BASIC,PASCAL}，B={BASIC,PASCAL,ADA,C,JAVA}定义：

A包含在B内，A包含于B，B包含A设A，B是任意两个集合，若A的每个元素都是B的元素，则称A是B的子集(Subset)，也称A包含在B内，B包含A，记作BA或AB，若A不被B所包含，则记作A

B。显然，对任意集合A，都有AA。AB19（二）相等关系定义A＝B当且仅当A与B具有相同的元素，否则，AB。即集合A,B中的元素完全相同，称这样的两个集合相等。

{1,2,4}={1,4,2}≠{1,{2,4}}定理3-1.1

设A和B是任意两个集合，A=BAB且BA。集合相等的谓词表示：A=B(x)(x∈Ax∈B)20定理3-1.1

A=B

AB且BA。证明：(1)证：若AB且BA，则A=B。(反证法)

已知AB且BA，假设A≠B，则至少有一个元素x，使得x∈A而xB；或者x∈B而xA。如果x∈A而xB，则与AB矛盾。如果x∈B而xA，则与BA矛盾。

所以A=B。(2)证：若A=B

，则AB且BA

。若A=B，则两个集合有相同的元素，即(x)(x∈Ax∈B)为真，且(x)(x∈Bx∈A)为真，即必有AB且BA。所以，A=B

AB且BA。该定理是证明两个集合相等的基本思路和依据。21集合相等的谓词定义A=BAB∧BA(x)(x∈Ax∈B)∧(x)(x∈Bx∈A)(x)((x∈Ax∈B)∧(x∈Bx∈A))(x)(x∈Ax∈B)A=B(x)(x∈Ax∈B)22（三）真包含关系定义1.2.2

：A真包含于B设A,B是任意两个集合，集合A中的每一个元素都属于B，但集合B中至少有一个元素不属于A。则称A是B的真子集(ProperSubset)，记作AB，如果A不是B的真子集，则记作AB。“真包含关系”的谓词表示：ABAB∧A≠BAB(x)(x∈Ax∈B)∧(x)(x

B∧xA)对任意x，如xA，则xB，并且存在xB，但是xA。23自学真包含关系的谓词定义：ABAB∧A≠B(x)(x∈Ax∈B)∧

(x)(x∈Ax∈B)(x)(x∈Ax∈B)∧

((x)(x∈Ax∈B)∨

(x)(x∈Bx∈A))((x)(x∈Ax∈B)∧(x)(x∈Ax∈B))

∨

((x)(x∈Ax∈B)∧(x)(x∈Bx∈A))(x)(x∈Ax∈B)∧(x)(x∈B

∧

xA)集合A中的每一个元素都属于B，但集合B中至少有一个元素不属于A。24六、几个特殊集合1、全集2、空集3、幂集251、全集定义

在一个相对固定的范围内，包含此范围内所有客体的集合，称为全集或论集(UniversalSet)，用U或E表示。

E={x|P(x)∨P(x)}其中：P(x)为任何谓词。用文氏图描述如下:U六、几个特殊集合一般地，根据讨论问题的范围，选择对问题讨论方便的集合作为全集。在实际应用中，常常把某个适当大的集合看成全集。262、空集定义：不含任何元素的集合叫做空集(EmptySet)，记作Φ。空集可以符号化为

Φ={x|P(x)∧P(x)}={}其中：P(x)为任何谓词。例

设A={x|(x∈R)∧(x2<0)}，试列举A中的所有元素。解：A=Φ。Φ与{Φ}:Φ是不含任何元素的集合，{Φ}是含一个元素Φ的集合。

{Φ}={{}}，|Φ|=0，|{Φ}|=1，Φ∈{Φ}定理3-1.2（1）空集是一切集合的子集；（2）空集是绝对唯一的。27反证法（1）空集是一切集合的子集；ΦA证明：因为(x)(x∈Φx∈A)为永真式，所以ΦA。（2）空集是绝对唯一的。分析：对“唯一性”的证明通常采用反证法。即假设“不唯一”，得出矛盾，从而说明结论正确。证明：（反证法）假设空集不唯一，即存在Φ1和Φ2两个空集，且Φ1≠Φ2，因为是Φ1空集，则由性质1得Φ1

Φ2

。因为是Φ2空集，则由性质1得Φ2

Φ1

。所以Φ1=Φ2

。与假设矛盾，所以空集是唯一的。定理3-1.2的证明Φ{Φ}283、幂集

引例：求集合的子集及子集的个数例A子集子集个数ΦΦ1{a}Φ,{a}2{a,b}Φ,{a},{b},{a,b}4{a,b,c}Φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}8一般来说，对于n个元素的集合A，它的不同的子集总数有：＝(1+1)n＝2n所以，n元集共有2n个子集。Cn2＋……Cn0Cn1Cnn＋＋＋29一般来说，对于n个元素的集合A，它的不同的子集总数有

Cn2＋……Cn0Cn1Cnn＋＋＋Cn2＋…Cn0Cn1Cnn＋＋＋xn-1yxn-2y2xnynCn2＋……Cn0Cn1Cnn＋＋＋而(x+y)n=令x=y=1时得

2n=所以不同子集总数有2n30幂集定义：幂集(powerset)给定集合A，由A的所有子集为元素组成的集合称为A的幂集(powerset)，记为ρ(A)

。幂集的符号化表示为ρ(A)＝{x|xA}例如：计算下列幂集:(1)ρ(Φ)；(2)ρ({a});(3)ρ({Φ})。解：(1)ρ(Φ)={Φ}；(2)ρ({a})={Φ,{a}}(3)ρ({Φ})={Φ,{Φ}}；定理3-1.3若有限集合Ａ有n个元素，则其幂集ρ(A)共有2n个元素。|A|=n,|ρ(A)|=2n31子集Bijk编码Ａ＝{a,b,c}

ijk是二进制数，

Bi

jk

A,i=1，a∈Bijk；i=0，aBijk；j=1，b∈Bijk；j=0，bBijk；k=1，c∈Bijk；k=0，cBijk

。例：Ａ＝{a,b,c}则B000B001B010B011B100B101B110B111Φ{c}{b}{b,c}{a}{a,c}{a,b}{a,b,c}B0

B1B2B3B4B5B6B7故：ρ(A)={Φ,{c},{b},{b,c},{a},{a,c},{a,b},{a,b,c}}例：Ａ＝{a,{b,c,d}}

B0=B00=Φ，B1=

B01={{b,c,d}}，B2=B10={a}，

B3=B11={a,{b,c,d}}故：ρ(A)={Φ,{{b,c,d}},{a},{a,{b,c,d}}}利用子集Ba1a2a3…an的下标编码求集合A的幂集，a1a2a3…an为二进制编码，n为集合A的元素个数。32设A={Φ}，B=ρ(ρ(A))ρ(A)={Φ,{Φ}}在求ρ(ρ(A))时，实际上是将{Φ,{Φ}}中的元素分别看成Φ=a,{Φ}=b,于是{Φ,{Φ}}={a,b}B=ρ(ρ(A))=ρ({a,b})={B0,

B1,B2,B3}={B00,

B01,B10,B11}={Φ,{b},{a},{a,b}}然后再将a,b代回即可B=ρ(ρ(A))=ρ({Φ,{Φ}})={Φ,{{Φ}},{Φ},{Φ,{Φ}}}以后熟悉后就可以直接写出。练习

P86(7)333-2集合的运算一、定义

设A、B是两个集合，={x|x∈A∨x∈B}x∈A∪B

x∈A∨x∈B

={x|xA

∧

xB}x∈A∩B

x∈A∧x∈B

={x|x∈A∧x

B}x∈A-B

x∈A∧xB

={x|x∈E∧x

A}={x|x

A}

x∈~A

xA

(x∈A)

={x|((xA)∧(xB))∨((xB)∧(xA))}AB=(A-B)∪(B-A)AB=(A∪B)-(A∩B)EAB差集EAB交集补集EA并集EAB(1)并集A∪B(2)交集A∩B(3)差集A-B(4)补集~A(5)对称差集AB34例：A={4,{1,2},{3}},B={{3},{1,2,3},4,{1,2},{1}}则：A∩B={4,{1,2},{3}}=AA∪B={4,{1,2},{3},{1,2,3},{1}}=BA-B=ΦB-A={{1,2,3},{1}}35二、集合的运算律等幂律:A∪A=A；A∩A=A；交换律:A∪B=B∪A;A∩B=B∩A结合律:A∪(B∪C)=(A∪B)∪C；A∩(B∩C)=(A∩B)∩C；恒等律:A∪Φ=A； A∩E=A；零律:A∪E=E； A∩Φ=Φ；分配律:A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)吸收律:A∩(A∪B)=A; A∪(A∩B)=A；

集合的运算律是指集合的交、并、补、差等运算的主要性质，也称为集合的基本定律。36定理否定律：

~~A=A；德摩根定律：~(A∩B)=~A∪~B~(A∪B)=~A∩~B矛盾律：

A∩~A＝Φ；排中律：

A∪~A＝E。其他：

A-A=Φ；A-B=A-(A∩B)；

A-B=A∩~B;(A-B)-C=A-(B∪C)；A∪(B-A)=A∪B；EAB37三、证明集合相等的四种方法方法一：命题演算法（逻辑等价式和推理规则）方法二：等式代入法(假设交换律、分配律、同一律、零律已经成立)方法三：证明出：AB且BA，则A=B。方法四：反证法38三、证明集合相等的四种方法方法一：命题演算法（逻辑等价式和推理规则）例：证明A∪(A∩B)=A

（吸收律）证任取x,

x(A

∪(A∩

B))

xA∨x(A∩

B)

xA∨

(xA∧xB)

xA

因此得A∪(AB)=A。方法二：等式代入法(假设交换律、分配律、同一律、零律已经成立)例证明吸收律A∪(A∩

B)=(A∩

E)∪(A∩

B)=A∩(E∪

B)=A∩

E=A39集合等式的证明方法三：证明出：AB且BA，则A=B

依据：定理3-1.1

A=B，当且仅当AB且BA。例如：（P91定理3-2.5的证明方法）方法四：反证法假设不等，推出矛盾。40分析：(x)(x∈A∩Bx∈A)(x)(x∈Ax∈B)证明：A∩B=A，(x)(x∈A∩Bx∈A)(x)((x∈A∩B

x∈A)∧(x∈Ax∈A∩B))(x)((xA∩B∨x∈A)∧(xA∨x∈A∩B))(x)(((x∈A∧x∈B)∨x∈A)∧(xA∨(x∈A∧x∈B))(x)(((xA∨xB)∨x∈A)∧

(xA∨(x∈A∧x∈B)))(x)(T∧(T∧(

xA∨x∈B)))(x)(

xA∨x∈B)(x)(x∈Ax∈B)AB证明P90定理3-2.3：A∩B=A

AB41四、证明AB的四种方法：方法一：A和B是用枚举方式定义的：依次检查A的每个元素是否在B中出现。方法二：通过集合运算判断AB：即A∪B=B,A∩B=A,AB=三个等式中有一个为真，则AB。方法三：通过文氏图判断集合的包含（注意这里是判断，而不是证明）方法四：A和B是谓词定义的，且A和B中元素的性质分别为P和Q：（即：A={x|P(x)}B={x|Q(x)}利用的定义证明（按定义证明法）。42按定义证明的方法若定义中有“若…则…”来描述的，则在证明时应采用离散数学中特有的按定义证明方法即证明时，首先叙述定义的前半部分“若…”，将这部分的内容称为“附加的已知条件”，此时利用该“附加的已知条件”和题目本身所给的已知条件证明出定义的后半部分“则…”，这部分的内容称为定义中的结论。这种证明问题的方法在于：证明时不能单纯利用题目所给的已知条件，而应同时利用定义中的“已知”，推出的并非整个定义，而是定义中的结论。这与一般的证明思路：已知→中间结果→结论是完全不同的。本章的证明大部分都采用按定义证明方法。利用的定义证明：AB定义：AB(x)(x∈Ax∈B)证明：假设(x)(x∈A)，利用题目中的已知条件和已有的定理和公理去推出即(x)(x

∈B)，从而证明AB。注意：若已知AB，则可以设(x)(x∈A)(x)(x

∈B)

43六、证明集合不等的方法证AB：

方法一：举例或画文氏图示意。方法二：转化为证明逻辑判断式不等价。A≠B(x)(xA且xB)∨(x)(xB且xA)方法三：反证法，假设A=B，推出矛盾。五、判断客体a是否是集合A元素的基本方法：把a作为一个整体，检查它在A中是否出现。44七、证明集合A是空集的方法方法一： 其逻辑判断条件是永假。

Φ={x|P(x)∧P(x)}方法二： 用反证法：设aA，引出矛盾的结果。 45自学求证(A-B)-C=(A-C)-(B-C)证明：任取x，

x∈(A-C)-(B-C)x∈(A-C)∧x(B-C)(x∈A∧xC)∧(x∈B∧xC)(x∈A∧xC)∧

(xB∨x∈C)(x∈A∧xC∧xB)∨(x∈A∧xC∧x∈C)x∈A∧xC∧xBx∈A∧xB∧xC(x∈A∧xB)∧xCx∈A-B∧xCx∈(A-B)-C所以(A-B)-C=(A-C)-(B-C)46自学A-(B∩C)=(A-B)∪(A-C)A-(B∪C)=(A-B)∩(A-C)证明：任取x∈A-(B∪C)x∈A∧x(B∪C)x∈A∧(x∈B∨x∈C)x∈A∧(xB∧xC)(x∈A∧xB)∧(x∈A∧xC)x∈A-B∧x∈A-Cx∈(A-B)∩(A-C)所以A-(B∪C)=(A-B)∩(A-C))A∩(B-C)=(A∩B)-(A∩C)但∪对-

是不可分配的，如A∪(A-B)=A，而(A∪A)-(A∪B)=Φ注意:这不是分配律47自学证明：AB~B~A证明：AB(x)(x∈Ax∈B)

(x)(xBxA)x(x∈~Bx∈~A)

~B~A∴AB~B~A证明：德摩根定律(1)~(A∩B)=~A∪~B(2)~(A∪B)=~A∩~B证明:(1)：任取x∈~(A∩B)x∈~(A∩B)

xA∩B(x∈A∧x∈B)(xA)∨(xB)(x∈~A)∨(x∈~B)x∈(~A∪~B)

∴~(A∩B)=~A∪~B48自学~A=B当且仅当A∪B=E且A∩B=Φ证明：(A∪B=E)∧(A∩B=Φ)(x)(x∈A∪Bx∈E)∧(PT=P)(x)(x∈A∩Bx∈Φ)(PF=P)(x)(x∈A∪BT)∧x(x∈A∩BF)(x)(x∈A∪B∧(x∈A∩B))(x)((x∈A∨x∈B)∧(x∈A∧x∈B))(x)((x∈A∨x∈B)∧(xA∨xB))(x)((xAx∈B)∧(x∈BxA))(x)((x∈~Ax∈B)∧(x∈Bx∈~A))(x)((x∈~Ax∈B)~A=B49设A是有穷集合，其元素个数为|A|。这节主要解决集合的计数问题。例如有AB两个商店，A店经营1000种商品，B店经营1200种商品，其中有100种商品两个商店都经营，问两个商店共经营多少种商品？显然|A∪B|=|A|+|B|-|A∩B|如果有ABC三个有限集合，则|A∪B∪C|=|A∪B|+|C|-|(A∪B)∩C|=|A|+|B|-|A∩B|+|C|-|(A∩C)∪(B∩C)|=|A|+|B|-|A∩B|+|C|-(|A∩C|+|B∩C|-|A∩B∩C|)=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|ABA∩BA∪B*3-3.包含排斥原理ABCU50一般地，有n个有限集合A1,A2,...An,则*3-3.包含排斥原理51令U为全集，E、F、J分别为会英语、法语和日语人的集合。|U|=170|E|=120|F|=80|J|=60|E∩F|=50|E∩J|=25|F∩J|=30|E∩F∩J|=10|E∪F∪J|=|E|+|F|+|J|-|E∩F|-|E∩J|-|F∩J|+|E∩F∩J|=120＋80＋60－50－25－30＋10＝165|U-(E∪F∪J)|=170-165=5即有5人不会这三种语言。例3-3.1某个研究所有170名职工，其中120人会英语，80人会法语，60人会日语，50人会英语和法语，25人会英语和日语，30人会法语和日语，10人会英语、日语和法语。问有多少人不会这三种语言？EFJ10U521.掌握集合的定义、谓词定义、证明方法。2.掌握三个特殊集合，会求集合的幂集。3.掌握集合的五种运算定义、计算方法、性质。*4.会用包含排斥原理解决集合计数问题.

作业：第94页⑶d)⑷⑸b)⑼3.1~3.3小结533.4序偶与集合的笛卡尔积要求：1、理解概念；2、掌握序偶和笛卡尔积的定义和性质。54一、序偶与有序n元组两个具有固定次序的客体x、y组成序偶，也称为有序二元组，记作<x,y>；称x、y分别为序偶<x,y>的第一，第二元素。固定次序是指调换第一和第二元素位置后，含义不同。注意，第一、二元素未必不同。1.定义：说明<2,3><3,2><1,-2><-2,1><-4,-3>55序偶的性质（1）当x≠y时，<x,y>≠<y,x>。

{x,y}={y,x}（2）序偶二个元素可以重复，即<x,x>也是序偶。

无{x,x}（3）序偶中两个元素可以来自不同的集合。<x,y>：x∈A,y∈B{x,y}∈A（4）序偶与集合的统一：

<x,y>={{x},{x,y}}（5）序偶相等的定义：

(x,y=u,v)(x=u)∧(y=v)由序偶相等的定义有

x+2＝5 2x+y＝4解得x＝3,y＝-2。解答例

已知<x+2,4>＝<5,2x+y>，求x和y。56序偶的推广：

有序N元组

定义

由N个元素x1,x2,…,xn-1,xn按照一定的次序组成的N元组称为有序N元组，记为<x1,x2,…,xn-1,xn>。xi叫做该

n元组的第i个分量i=1,…,n。有序N元组与序偶的关系：<x1,x2,…,xn-1,xn>

=x1,x2,…,xn-1,xn三元组

x1,x2,x3

=x1,x2,x3四元组x1,x2,x3,x4=x1,x2,x3,x4

=<x1,x2>,x3>,x4注意：x1,x2,x3≠

x1,x2,x3x1,x2,x3,x4

≠

x1,x2,x3,x4x1,x2,x3,x4,x5≠

x1,x2,x3,x4,x5例如：a年b月c日d时e分f秒，可用六元组表示<a,b,c,d,e,f>57定义：两个n元组相等设x1,x2,…,xn与y1,y2,…,yn是两个n元组，如果xi=yi，i=1,…,n，则称这两个n元组相等，记为x1,x2,…,xn=y1,y2,…,yn。用逻辑的方法表示为(x1,x2,…,xn=y1,y2,…,yn)(x1=y1)∧(x2=y2)∧…∧(xn=yn)。

<a,b,c,d><b,a,d,c><a,b,d,c>58二、集合的笛卡尔积

引例

“斗兽棋”虎象狮豹狼鼠猫狗虎象狮豹狼鼠猫狗每个棋子可以看成一个序偶:<红,象>,<红,狮>,<红,虎>,<红,豹>,<红,狼>,<红,狗>,<红,猫>,<红,鼠>,<蓝,象>,<蓝,狮>,<蓝,虎>,<蓝,豹>,<蓝,狼>,<蓝,狗>,<蓝,猫>,<蓝,鼠>可看成是由两种颜色的集合A和8种动物的集合B做运算得到的。

A={红,蓝}B={象,狮,虎,豹,狼,狗,猫,鼠}斗兽棋可记成集合：}{斗兽棋可记成集合：59补充的定义:A和B的笛卡尔积或直积设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成的所有序偶的集合，称为A和B的笛卡尔积或直积，记作A×B，即

AB={<x,y>|xA∧yB}<x,y>AB

xA

∧

yB<x,y>AB

xA

∨

yB例如：A表示某大学所有学生的集合，B表示大学开设的所有课程的集合。则A×B可以用来表示该校学生选课的所有可能情况。1、集合的笛卡尔积的定义60AB={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}BA={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}AA={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<2,2>}可见A×B≠B×A集合的笛卡尔积运算不满足交换律。例：A={0,1}，B={a,b}，C={z}(AB)C={<0,a>,<0,b>,<1,a>,<1,b>}×{z}={<0,a,z>,<0,b,z>,<1,a,z>,<1,b,z>}A(BC)={0,1}{<a,z>,<b,z>}={<0,<a,z>>,<0,<b,z>>,<1,<a,z>>,<1,<b,z>>}

(AB)C={<<x,y>,z>|<x,y>AB∧

zC}A(BC)={<x,<y,z>>|xA∧<y,z>BC},可见(AB)CA(BC)。集合的笛卡尔积运算也不满足结合律。例：设A={0,1,2}，B={a,b}，求AB，BA，AA。|AB|=6=|BA||AA|=9611)如果A、B都是有限集，且|A|=m,|B|=n，

则|AB|=m•n.证明：由笛卡尔积的定义及排列组合中的乘法原理，直接推得此定理。

2)AΦ=ΦB=Φ3)对∪和∩满足分配律。

设A,B,C是任意集合，则

①A(B∪C)=(AB)∪(AC)；②A(B∩C)=(AB)∩(AC)；③(A∪B)C=(AC)∪(BC)；④(A∩B)C=(AC)∩(BC)4)若C,则AB(ACBC)(CACB)。5)设A,B,C,D为非空集合，则ABCDAC∧BD。（两个笛卡尔积具有包含关系，则相应的分量也具有包含关系）2、集合的笛卡尔积的性质622、集合的笛卡尔积的性质（续）求证：①A(B∪C)=(AB)∪(AC)分析：<x,y>A(B∪C)??<x,y>(AB)∪(AC)

证明：任取<x,y>A(B∪C)

xA∧

y(B∪C)xA∧(yB∨yC)(xA∧

yB)∨(xA∧

yC)<x,y>AB∨<x,y>AC<x,y>(AB)∪(AC)

所以A(B∪C)=(AB)∪(AC)其余可以类似证明。A(B∪C)

<x,y>A(B∪C)

(AB)∪(AC)

<x,y>(AB)∪(AC)A={a},B={1,2},C={2,3}A(B∪C)={a}{1,2,3}={<a,1>,<a,2>,<a,3>}AB={a}{1,2}={<a,1>,<a,2>}AC={a}{2,3}={<a,2>,<a,3>}(AB)∪(AC)={<a,1>,<a,2>,<a,3>}A(B∪C)=(AB)∪(AC)

63即AB(ACBC)类似可以证明AB(CACB)。4)若C,则AB(ACBC)(CACB).证明:证AB(ACBC)①证：ABACBC

设AB,任取<x,y>ACxA

∧

yC

(由AB)

xB

∧

yC<x,y>BC即<x,y>BC

所以,ACBC。2、集合的笛卡尔积的性质（续）②证：(ACBC)

AB若C,任取yC,任取xA

xA

∧

yC<x,y>AC(由ACBC)

<x,y>BCxB

∧

yCxB

所以,AB。<x,y>AB

xA

∧

yBAB(x)(x∈A

x∈B)64

5)设A,B,C,D为非空集合，则ABCDAC∧BD。证明:①证：由ABCDAC∧BD。任取xA，任取yB，

xA∧

yB<x,y>A×B(由ABCD)<x,y>C×DxC∧

yD

即xC∧

yD

所以,AC∧BD.②证：由AC∧BDABCD。任取<x,y>A×B

<x,y>A×B

xA∧

yB(由AC，BD)

xC∧

yD<x,y>C×D即<x,y>C×D所以,ABCD

因此，ABCDAC∧BD。2、集合的笛卡尔积的性质（续）65注意：两集合的笛卡尔积仍是一个集合，故对于有限集合可进行多次笛卡尔积运算。A×B×C=(A×B)×C

A×B×C×D=(A×B×C)×D=((A×B)×C)×DA1×A2×…

×An=(A1×A2×…×An-1)×An={<x1,x2,…,xn>|x1∈A1,x2∈A2,…,xn∈An}A×A=A2,A×A×A=A3,A×A×…×A=An

66例：令A1={x|x是学号}A2={x|x是姓名}A3={男,女}

A4={x|x是出生日期}A5={x|x是班级}

A6={x|x是籍贯}

则A1A2A3A4A5A6中一个元素：<001，王强，男，1981-02-16，计2001-1，河南>是学生档案数据库的一条信息，所以学生的档案就是A1A2A3A4A5A6的一个子集。3、集合的笛卡尔积的应用作业第105页⑵673.5关系及其表示法关系是一个非常普遍的概念，如数值的大于关系、整除关系，人类的父子关系、师生关系、同学关系等。要求：1、理解定义关系定义域（前域）、值域2、掌握关系的表示方法3、熟记特殊的关系4、会计算关系的集合运算681.关系的定义

空集或任一序偶的集合，都称为一个二元关系。

设A、B是集合，若RA×B，则称R是一个从A到B的二元关系。

若RA×A，则称R是A上的二元关系。二元关系简称为关系。<x,y>R可记作xRy

；一、基本概念设R1＝{<1,2>,<a,b>}，R2＝{<1,2>,a,b}。则R1是二元关系，R2不是二元关系，只是一个集合。举例关系是以序偶为元素的集合。<x,y>R可记作xRy定义1：定义2：<x,y>R,xRy，表示x和y具有关系R。<x,y>R，表示x和y不具有关系R。69注意：关系集合满足以下条件之一：(1)集合非空，且它的元素都是序偶；(2)集合是空集，即空集也可称作关系。序偶是讲究次序的，关系也是有序的。即<x,y>∈R未必有<y,x>∈R，x与y有关系R，未必y与x有关系R。例：甲与乙有父子关系，则乙与甲肯定没有父子关系。由于任何A×B的子集都是一个二元关系，而A×B共有2|A|╳|B|个不同的子集。因此，从A到B不同的关系共

有2|A|╳|B|个。1.2.3.70例3-5.1①A={0,1}，B={x,y,z}，则R1={<0,x>，<1,z>}，R2=A×B，R3=等都是从A到B的二元关系；R4={<0,0>}和R3同时也是A上的二元关系。②A为整数集合，则R={<x,y>|x能整除y(即x|y),x,yA}为A上的整除关系。如：<1,3>,<2,8>,<4,80>,<7,84>等等。③父子关系：{<x,y>|x人类，y人类，且x是y的父亲(y是x的儿子)}71④有王、张、李、赵是某校的老师，该校有三门课程：程序设计、离散数学和英语，已知王可以教程序设计和离散数学，张可以教程序设计和英语，李可以教离散数学，赵可以教英语，若记A={王,张,李,赵}，B={程序设计,离散数学,英语}。那么这些老师与课程之间的对应关系就可以用由A到B的一个关系R中的序偶来表示。R={<王,程序设计>,<王,离散数学>,<张,程序设计>,<张,英语>,<李,离散数学>,<赵,英语>}

722.三个特殊关系（1）空关系Φ：

因为ΦA×B，(或ΦA×A)，所以Φ也是一个从A

到B(或A上)的关系，称为空关系。（2）完全关系(全域关系)E：即含有A×B(或A×A)全部序偶的关系，A×B(或A×A)本身也是一个从A到B(或A上)的关系，称为完全关系。（3）A上的恒等关系IA：

IAA×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>,<3,3>}。举例73其他常见的关系小于或等于关系：

LA={<x,y>|x,y∈A∧x≤y}，其中AR。整除关系：

DA={<x,y>|x,y∈A∧x整除y}，其中AZ*Z*是非零整数集包含关系：R＝{<x,y>|x,y∈A∧xy},其中A是集合族。设A={1,2,3}，B＝{a,b},则(1)LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}(2)令C=ρ(B)={,{a},{b},{a,b}}，则C上的包含关系是

R＝{<,>,<,{a}>,<,{b}>,<,{a,b}>,

<{a},{a}>,<{a},{a,b}>,<{b},{b}>,

<{b},{a,b}>,<{a,b},{a,b}>}举例74二、关系的表示方法1.枚举法即将关系中所有序偶一一列举出，写在大括号内。如R

={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>}。2.谓词公式法即用谓词公式表示序偶的第一元素与第二元素间的关系。如“<”={<x,y>|x∈N∧y∈N∧x<y}3.有向图法4.关系矩阵法

753.有向图法表示二元关系R的图叫做R的关系图。⑴从A到B的二元关系R的关系图。⑵A上的二元关系R的关系图。76

ABR:⑴A到B二元关系R的关系图

设A={a1,a2,…,am}，B={b1,b2,…,bn}，R是A到B二元关系，R的关系图的绘制方法如下：

4。3。2。1。。c。b。a①画出m个小圆圈（实心或空心）表示A的元素，再画出n个小圆圈表示B的元素。这些小圆圈叫做关系图的结点。②关系中的序偶ai,bj

，画一条从ai到bj的有方向(带箭头)的线。这些有方向的线叫关系图的边。

(注意ai是始点，bj是终点，次序不能颠倒)。例3-5.3：设A={1,2,3,4},B={a,b,c}，RA×B，R={<1,a>,<1,c>,<2,b>,<3,c>}，

R的关系图如下：77

⑵A上的二元关系R的关系图设A={a1,a2,…,am}，R是A上的二元关系，其关系图的绘制方法如下：①画出m个小圆圈表示A的元素。②若ai,ajR，则从ai到aj画一根有方向(带箭头)的线。③若<ai,ai>R，则从ai到ai画一条有向环(自回路)。例：设函数集合P={P1,P2,P3,P4,P5}，考虑它们之间的调用关系R：P1调用P2；P2调用P4；P3调用P1；P4调用P5；P5调用P2；

则R={<P1,P2>,<P2,P4>,<P2,P2>,<P3,P1>,<P4,P5>,<P5,P2>

R的关系图为：P1P2P3P4P578有限集合之间的关系也可以用矩阵来表示，这种表示法便于用计算机来处理关系。设A={a1,a2,,am}，B={b1,b2,,bn}是个有限集，RA×B，定义R的关系矩阵是m×n

阶矩阵

MR=(rij)m×n，其中A={a1,a2,,am}是个有限集，RA×A，定义R的关系矩阵是m×m阶矩阵MR=(rij)m×m，其中1若<ai,bj>∈R0若<ai,bj>∈R(1≤i≤m,1≤j≤n)4.矩阵表示法rij=1若<ai,bj>∈R0若<ai,bj>∈R(1≤i,j≤m)rij=79A={a,b,c}，B={1,2,3,4},R1A×BR1={<a,1>,<c,1>,<b,2>,<a,3>,<c,4>}A={1,2,3,4}，R2A×AR2={<1,1>,<1,4>,<2,3>,<3,1>,<3,4>,<4,1>,<4,2>}

1010010010013×41234注意MR1=MR2=abc

1001001010014×4123412341100在写关系矩阵时，首先应对集合A和B中的元素进行排序，不同的排序会得到不同的关系矩阵。当集合以枚举法表示时，如果没有对集合的元素排序，则默认枚举的次序为元素的排序。80A={1,2,3}上的Φ、完全关系及IA的关系图及矩阵如下：MIA=1000100013×30000000003×3MΦ=1111111113×3MA×A=1。。2。3Φ。1。2。3A×A。1。2。3IA特殊关系的表示81例3-5.4(1)设A={1,2,3,4}，B={2,4,6}，R表示A与B的整除关系，写出关系R的四种表示法。解：由题意得枚举法：谓词公式法：对应的关系图为：关系矩阵为：1234246

1114×3246MR=1234

111

001

010R={<1,2>,<1,4>,<1,6>,<2,2>,<2,4>,<2,6>,<3,6>,<4,4>}；R={<x,y>|x能整除y，x∈A,y∈B}。82由于关系就是集合，所以集合的∩、∪、~和-运算对关系也适用。定理3-5.1

设R和S是从集合X到集合Y的两个关系，则R∩S，R∪S，~R，R-S仍是从X到Y的关系。证明：因为RXY，SXY，所以R∩SXY，R∪SXY；~R=XY-RXY，同理：~SXYR-S=R∩~SXY。故R∩S，R∪S，~R，R-S是从X到Y的关系。三、关系的集合运算

83A是学生集合，R是A上的同乡关系，S是A上的同姓关系，则R∪S：或同乡或同姓关系R∩S：既同乡又同姓关系R-S：同乡而不同姓关系~R：不是同乡关系,这里~R=(A×A)-R例3-5.284作业第109页⑵、⑸c)d)853.6关系的性质本节将研究关系的一些性质，它们在关系的研究中起着重要的作用。这是本章最重要的一节。本节中所讨论的关系都是集合A上的关系。本节要点：五个性质：自反性、反自反性--自己和自己的关系对称性、反对称性–两个元素之间的关系传递性--三个元素之间的关系相关证明86定义：设R是集合A上的关系，若对于任意x∈A都有<x,x>∈R(xRx)，则称R是A中的自反关系。即R是A中自反的(x)(xA<x,x>∈R)该定义表明在自反关系R中，除其他序偶外，必须包括有全部由每个x∈A所组成的相同元素的序偶。一、自反性非（不是）自反的(x)(xA∧<x,x>R)例如：设X={a,b,c},R1={<a,a>,<b,b>,<c,c>,<a,b>}R2={<a,a>,<b,b>,<a,b>}

例如：相等关系(=)，小于等于关系()，包含关系()等是自反关系。是自反关系。不是自反关系。87定义：设R是集合A上的关系，若对于任意x∈A都有<x,x>∈R(xRx)，则称R是A中的自反关系。即R是A中自反的(x)(xA<x,x>∈R)从关系矩阵看自反性：从关系有向图看自反性：1？？？1？？？1具有自反性的关系的关系矩阵和关系图的特点。1。2。3主对角线都为1。每个结点都有环。88定义：设R是集合A上的关系，若对于任意的x∈A都有<x,x>R

，则称R为A中的反自反关系。即R是A中反自反的(x)(xA<x,x>R)该定义表明了，一个反自反的关系不应包括有任何相同元素的序偶。二、反自反性非（不是）反自反的(x)(xA∧<x,x>R)例如：设X={a,b,c},R1={<a,b>,<b,c>}

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

不相等关系()，小于关系()，真包含关系()，父子关系是反自反关系。是反自反关系。不是反自反关系89定义：设R是集合A上的关系，若对于任意的x∈A都有<x,x>R

，则称R为A中的反自反关系。即R是A中反自反的(x)(xA<x,x>R)从关系矩阵看反自反性：从关系有向图看反自反性：0？？？0？？？0具有反自反性的关系的关系矩阵和关系图的特点1。。2。3主对角线都为0。每个结点都无环。90R1、R3、R4是自反的，R2、R5、R8均是反自反关系。注意：任何一个不是自反的关系，未必是反自反的，任何一个不是反自反的关系，未必是自反的，如R6、R7非自反，也非反自反。存在既不是自反的也不是反自反的关系。例1。2。。1。2。。1。2。。1。2。。33331。2。。1。2。。1。2。。1。2。。3333R2R1R3R4R5R6R7R8自反

反自反反自反反自反

自反

自反

非自反非反自反非自反非反自反91定义：R是集合A上的关系，若对任何x,y∈A，若有<x,y>R，必有<y,x>R

，则称R为A中的对称关系。

R是A上对称的(x)(y)((xA∧yA∧<x,y>R)

<y,x>R)在有对称性的关系中，若有序偶<x,y>，必有序偶<y,x>。例如：设集合A={1,2,3}有下列关系：1）R1={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<3,1>}2）R2={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}三、对称性非（不是）对称的(x)(y)(xA∧yA∧<x,y>R∧

<y,x>

R)例如：相等关系(=)，不相等关系()，朋友关系，同学关系，同乡关系等是对称关系。是对称关系不是对称关系92定义：R是集合A上的关系，若对任何x,y∈A，若有<x,y>R，必有<y,x>