离散数学课件第

离散数学课件第第一页，共一百三十九页，2022年，8月28日第二篇：集合论

集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。在现代数学中，每个对象（如数，函数等）本质上都是集合，都可以用某种集合来定义。数学的各个分支本质上都是在研究这种或那种对象集合的性质。集合论已经称为全部现代数学的理论基础。第二页，共一百三十九页，2022年，8月28日第二篇：集合论集合论的特点是研究对象的广泛性。它总结出由各种对象组成的集合的共同性质，并用统一的方法来处理。因此，集合论被广泛应用于各个科学和技术领域中。

由于集合论的语言适合描述和研究离散对象及其关系，所以也是计算机科学与工程的理论基础，在程序设计、关系数据库、排队论、开关理论、形式语言和自动机理论等学科领域中都有重要的应用。本篇主要介绍：集合、二元关系和函数第三页，共一百三十九页，2022年，8月28日第三章：集合与关系§3.1集合的概念与表示§3.2集合的运算§3.3序偶与笛卡尔积§3.4关系及其表示§3.5关系的性质§3.6复合关系和逆关系§3.7关系的闭包运算§3.8集合的划分和覆盖§3.9等价关系与等价类§3.10相容关系§3.11序关系第四页，共一百三十九页，2022年，8月28日第三章：集合与关系教学目的及要求：深刻理解和掌握有关集合和关系的基本概念和基本运算。教学类容：集合的概念和表示方法、集合的运算、序偶与笛卡尔积、关系及其表示、关系的性质、复合关系和逆关系、关系的闭包运算、集合的划分和覆盖、等价关系与等价类、相容关系、序关系。教学重点：关系及关系的运算、等价关系、序关系教学难点：关系的闭包运算、等价关系、等价类。第五页，共一百三十九页，2022年，8月28日第三章：集合与关系§3.1集合的概念与表示1、集合的基本概念【定义】具有某种特定性质的事物（客体）的总体。这里的“事物”可以是人，物品，也可以是数学元素。定义的讨论：

符号表示：通常用大写的英文字母表示，如A、B、C等。组成集合的对象叫做集合的元素或成员，常用小写的英文字母表示。第六页，共一百三十九页，2022年，8月28日第三章：集合与关系集合的性质

确定性：所谓确定的，是指任何一个对象是不是集合的元素是明确的、确定的，不能模棱两可。每一个对象都能确定是不是某一集合的元素，没有确定性就不能成为集合，例如“个子高的同学”“很小的数”都不能构成集合。这个性质主要用于判断一个集合是否能形成集合。

互异性：集合的元素又是能区分的，能区分的是指集合中的元素是互不相同的。如果一个集合中有几个元素相同，算做一个。例如集合1,2,3,3和1,2,3是同一集合。

无序性：集合的元素又是无序的，即1,2,3和3,1,2是同一集合第七页，共一百三十九页，2022年，8月28日第三章：集合与关系集合与元素的关系：设S是集合，a是S的一个元素，记为aS，读做“a属于S”，也可读做“a在S中”。如果a不是S的元素，记为aS，读做“a不属于S”，也可读做“a不在S中”。例如：①26个英文字母组成一个集合，任一英文字母是该集合的元素。②河南理工大学全体学生组成一个集合，该校的每一个学生是这个集合的元素。集合的基数（势）：集合中元素的个数，假设集合为S，则集合S的基数为|S|，根据集合的基数（元素）是否为有限个，又分为有限集合和无限集合第八页，共一百三十九页，2022年，8月28日第三章：集合与关系2、集合的表示方法集合有三种表示法。列举法：在花括号“”中列举出该集合的元素，元素之间用逗号隔开。例如：I5=1,2,3,4,5I+=1,2,3,…I=0,1,-1,2,-2,…S=T,F

第二种表示法是描述法：用谓词界定集合的元素。例如：Q=x|x是有理数

R=x|x是实数

C=x|x是复数

A=x|xI∧0＜x∧x＜5

文氏图法：用一条封闭的曲线的内部来表示一个集合的方法，人们常用文氏图描述集合运算和它们之间的关系。如图3.1

（形象，直观）。第九页，共一百三十九页，2022年，8月28日第三章：集合与关系

3、集合间的关系【定义】设A，B是任意的集合，当A的每一元素都是B的元素时，则称A是B的子集，也称A包含在B内或B包含A。记为AB或BA。

当A不是B的子集时，记为A⊈B。

AB用谓词公式表示为：AB(x)(xA→xB)A⊈B用谓词公式表示为：A⊈B(x)(xA∧xB)

例如：设A=1，B=1,2，C=1,2,3

则

AAAB，BC，ACC⊈B

可以证明，集合的包含有下列性质：①自反性。即对任意集合A，AA。②传递性。即对任意集合A、B、C，当AB和BC时，AC。第十页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】设A，B是集合，如果AB且BA，则称A与B相等。记为A=B。如果A与B不相等，记为A≠B。集合相等也可用谓词公式表示为：

A=BAB∧BA

(x)(xA→xB)∧(x)(xB→xA)

(x)(xA↔xB)

例如：设A=1,2，B=1,2，C=2,1

则A=C，A≠B

由集合相等的定义可以看出，集合相等有下列性质：①自反性:即对任意集合A，A=A。②对称性:即对任意集合A、B，当A=B时，B=A。③传递性:即对任意集合A、B、C，当A=B和B=C时，A=C。

第十一页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】

设A，B是集合，如果AB且A≠B，则称A是B的真子集。记为AB。如果A不是B的真子集，记为AB。真子集用谓词公式表示为：

ABAB∧A≠B

(x)(xA→xB)∧(x)(xB∧xA)

例如：设A=a，B=a,b，C=a,b,c

则

AB，BC，ACAA

又如，自然数集是整数集合的真子集，也是有理数集合和实数集合的真子集，即NI，NQ，NR。

第十二页，共一百三十九页，2022年，8月28日【定义】不包含任何元素的集合叫空集。记为Æ。空集可以表示为：Æ=x|P(x)∧P(x)其中，P(x)为任意谓词空集Æ是不包含任何元素的集合，所以，|Æ|=0。【定理1】空集是任意集合的子集。

证明：设A是任意集合。对任意对象x，由空集的定义知，xÆ为假，由条件联结词的定义知，xÆ→xA为真。根据全称推广规则有(x)(xÆ→xA)为真，故ÆA

第三章：集合与关系第十三页，共一百三十九页，2022年，8月28日根据定理1，空集是任意集合的子集，即ÆA；对任意集合A，AA。一般地说，任意集合A至少有两个子集，一个是空集Æ，另一个是它本身A。

推论空集是惟一的。

证明：设有两个空集Æ1和Æ2，由定理1有Æ1Æ2和Æ2Æ1，根据集合相等的定义知，Æ1=Æ2。【定义】在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集。记为E。全集是相对的，不同的问题有不同的全集。即使是同一问题也可以取不同的全集。第三章：集合与关系第十四页，共一百三十九页，2022年，8月28日第三章：集合与关系4、幂集合【定义】设A是集合，A的所有子集构成的集合称为A的幂集合，记为P(A)，即

P(A)=S|SA【例】设A=a,b,c，Æ是空集，试求P(A)，P(P(Æ))。

解：P(A)=Æ,a,b,c,a,b,a,c,b,c,a,b,c

P(Æ)=Æ

P(P(Æ))=Æ,Æ

第十五页，共一百三十九页，2022年，8月28日第三章：集合与关系【定理】设A为有限集合，则|P

(A)|=2|A|

证明:设|A|=n，A的子集有：不含元素的子集Æ一个，即个。含一个元素的子集n个，即个。含两个元素的子集个。

……含n个元素的子集个。|P(A)|=++…+=2n=2|A|在上例中，|A|=3，|P(A)|=8=23=2|A||Æ|=0，|P

(Æ)|=1=20

=2|Æ||P

(Æ)|=1，|

P(P(Æ))|=2=21

=2|P(Æ)|第十六页，共一百三十九页，2022年，8月28日第三章：集合与关系§3.2集合的运算【定义】

设A，B是任意的集合，由A中的元素或B中的元素组成的集合，称为A和B的并集，记为A∪B。

A∪B=x|xA∨xB

并集的定义如图3.2所示。从并集的定义可以得到：

AA∪B，BA∪B第十七页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】设A，B是集合，由A与B的公共元素组成的集合，称为A和B的交集，记为A∩B。A∩B=x|xA∧xB交集的定义如图3.3所示。从交集的定义可以得到：

A∩BA，A∩BB如果A与B无公共元素，即A∩B=Æ，则称A和B是互不相交的。例如，令A=a,b,c，B=d,e，则A∩B=Æ，A和B是互不相交的。

第十八页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】设A，B是集合，属于A的而不属于B的元素组成的集合，称为B对于A的补集，也叫B对于A的相对补集。记为A-B。A-B=x|xA∧xB相对补集定义如图3.4所示。【例】令A=Æ,Æ，B=Æ，则A-B=Æ,Æ-Æ=Æ,Æ又如，令C=a，D=a,b，则C-D=a-a,b=ÆC-C=Æ第十九页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】

设A是集合，A对于全集E的相对补集，称为A的绝对补集，记为~A。

~A=E-A=x|xE∧xA=x|xA~A的定义如图3.5所示。例如，令全集E=1,2,3,4，A=

1,2,3

则~A=1,2,3,4-1,2,3=4【例】设A,B是任意的集合，求证:A-B=A∩(~B)

证明：xA-BxA∧xBxA∧x~B

xA∩~B即A-BA∩~B。xA∩~BxA∧x~BxA∧xBxA-B故A∩~BA-B所以，A-B=A∩(~B)。A-B=A∩(~B)是一个重要的公式，在集合的运算中经常用到，它的意义在于将相对补运算转换绝对补和交运算。第二十页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】设A，B是集合，由A中元素或B中元素，但不是A与B的公共元素组成的集合，称为A和B的对称差，记为AB。AB=x|xA▽

xB=(A∪B)-(A∩B)AB的定义如图3.6所示。例如，令A=1,2,3,4，

B=

1,2,5,6，则AB=A∪B-A∩B=1,2,3,4,5,6-1,2=3,4,5,6第二十一页，共一百三十九页，2022年，8月28日第三章：集合与关系【例】设A,B是任意的集合，求证:

AB=(A-B)∪(B-A)=(A∩~B)∪(B∩~A)。

证明：先证AB=(A-B)∪(B-A)。xABxA▽xB(xA∧xB)∨(xA∧xB)xA-B∨xB-Ax(A-B)∪(B-A)所以，AB=(A-B)∪(B-A)。再证(A-B)∪(B-A)=(A∩~B)∪(B∩~A)。由前面一个例子很容易得到此结论。这里从略。第二十二页，共一百三十九页，2022年，8月28日第三章：集合与关系利用上例中的公式可以证明对称差AB下列的性质。设A,B是任意的集合。①AA=Æ

证明：AA=(A-A)∪(A-A)=ÆÆ=Æ②AÆ=A

证明：AÆ=(A-Æ)∪(Æ-A)=A∪Æ=A③AE=~A

证明：AE=(A-E)∪(E-A)=Æ∪~A=~A为了使集合的表达式更加简洁，我们对集合运算的优先顺序规定如下：绝对补的运算级别比其它的4个运算高，先进行绝对补运算，再进行其它的4个运算；其它的4个运算的运算顺序由括号决定。第二十三页，共一百三十九页，2022年，8月28日第三章：集合与关系用文氏图不仅可以表示集合的运算和它们之间的关系，而且还可以很方便地解决有限集合的计数问题。用文氏图解决有限集合的计数问题的方法是：每一条性质定义一个集合，画一个圆表示这个集合。如果没有特别说明，任何两个圆画成相交的。将已知集合的元素数填入表示该集合的区域内。通常从n个集合的交集填起，根据计算的结果逐步将数字填入其它各空白区域内。如果交集的值是未知的，可以设为x。根据题目的条件，列出方程或方程组，求出所需的结果。第二十四页，共一百三十九页，2022年，8月28日第三章：集合与关系【例】某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两次考试中都不为优的共17人。问两次考试中都为优的有多少人？解：设A，B分别表示第一次和第二次考试中成绩为优的学生集合。画出文氏图，如图3.7所示。首先填

A∩B中的人数，这正是要求的，设为x。A-B中的人数是26-x，B-A中的人数是21-x，分别填入对应的区域。并列出如下方程：

(26-x)＋x＋(21-x)＋17=50

解得：x=14第二十五页，共一百三十九页，2022年，8月28日第三章：集合与关系§3.3序偶与笛卡尔积【定义】两个个体x，y的有序序列，称为二重组，也称为有序对或序偶。记为x,y。x，y分别叫做二重组的第一分量和第二分量。所谓有序序列是指调换第一分量和第二分量位置后，就和原来的含义不同了。【定义】设x,y与a,b是两个二重组，如果x=a且y=b，则称二重组x,y与a,b相等，记为x,y=a,b。二重组x,y与a,b相等，用逻辑的方法表示为(x,y=a,b)(x=a)∧(y=b)。由定义可以看出，当x≠y时，x,y≠y,x。例如，平面上的点P1=2,1和点P2=1,2是两个不同的点，它们都是二重组。第二十六页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】二重组x1,x2,…,xn-1,xn叫做n重组。记为x1,x2,…,xn，xi叫做该n重组的第i个分量i=1,…,n。由定义可看出：三重组x1,x2,x3定义为x1,x2,x3，其中第一分量是二重组；四重组x1,x2,x3,x4定义为x1,x2,x3,x4，其中第一分量是三重组；……。根据三重组的定义，第一分量是二重组，第二分量是一个个体的序偶x1,x2,x3是3重组。而第一分量是一个个体，第二分量是二重组的序偶x1,x2,x3不是三重组。这个结论对任意的n(n=3,4,5,…)重组也是对的。例如，x1,x2,x3,x4是四重组，而x1,x2,x3,x4不是四重组；x1,x2,x3,x4,x5是五重组，而x1,x2,x3,x4,x5不是五重组。……。第二十七页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】设x1,x2,…,xn与y1,y2,…,y

n是两个n重组，如果xi=yi，i=1,…,n，则称这两个n重组相等，记为x1,x2,…,xn=y1,y2,…,y

n。n重组x1,x2,…,xn与y1,y2,…,y

n相等，用逻辑的方法表示为(x1,x2,…,xn=y1,y2,…,y

n)(x1=y1)∧(x2=y2)∧…∧(xn=yn)。【定义】设A，B是集合，集合a,b|aA∧bB叫做A，B的笛卡尔积，也叫A，B的叉乘积，直积。记为：A×B。如果A，B都是有限集，|A|=n，|B|=m，根据排列组合原理，|A×B|=nm=|A||B|。第二十八页，共一百三十九页，2022年，8月28日第三章：集合与关系【例】设A=a,b，B=1,2,3，⑴试求A×B和B×A⑵验证|A×B|=|A||B|和|B×A|=|B||A|

解：⑴求A×B和B×AA×B=a,1,a,2,a,3,b,1,b,2,b,3

B×A=1,a,1,b,2,a,2,b,3,a,3,b⑵验证|A×B|=|A||B|和|B×A|=|B||A||A×B|=6=2×3=|A||B||B×A|=6=3×2=|B||A|如果把×看成运算，笛卡尔积有以下的性质：①设A为任意的集合，则A×Æ=Æ×A=Æ②一般地说，×不满足交换律：即A×B≠B×A。在上例中，A×B≠B×A③一般地说，×不满足结合律：即(A×B)×C≠A×(B×C)第二十九页，共一百三十九页，2022年，8月28日第三章：集合与关系【定理】设A，B，C是集合，则⑴A×(B∪C)=(A×B)∪(A×C)⑵A×(B∩C)=(A×B)∩(A×C)⑶(A∪B)×C=(A×C)∪(B×C)⑷(A∩B)×C=(A×C)∩(B×C)

证明：仅证明⑴,可类似地证明⑵、⑶、⑷。

a,bA×(B∪C)aA∧bB∪C

aA∧(bB∨bC)(aA∧bB)∨(aA∧bC)a,bA×B∨a,bA×Ca,b(A×B)∪(A×C)故A×(B∪C)=(A×B)∪(A×C)

第三十页，共一百三十九页，2022年，8月28日第三章：集合与关系【定理】设A，B，C是集合，C≠Æ，则⑴AB的充分必要条件是A×CB×C⑵AB的充分必要条件是C×AC×B

证明:仅证明⑴,可类似地证明⑵。设AB，下证A×C

B×Ca,bA×CaA∧bCaB∧bCa,bB×C所以A×CB×C设A×CB×C，下证AB因为C≠Æ，所以存在bCaAaA∧bCa,bA×Ca,bB×CaB∧bCaB所以AB第三十一页，共一百三十九页，2022年，8月28日第三章：集合与关系【定理】设A，B，C，D是非空集合，则

A×BC×D的充分必要条件是AC且BD。

证明：设A×BC×D，下证AC且BDaA∧bBa,bA×Ba,bC×DaC∧bD所以AC且BD设AC且BD，下证A×BC×Da,bA×BaA∧bBaC∧bDa,bC×D所以A×BC×D第三十二页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】叉乘积A1×A2×…×An定义为(A1×A2×…×An-1)×An，即A1×A2×…×An

=a1,a2,…,an|a1A1∧a2A2∧…∧anAn

由定义可以看出：当n=3时，A1×A2×A3定义为(A1×A2)×A3A1×A2×A3=a1,a2,a3|a1A1∧a

2A2∧a3A3当n=4时，A1×A2×A3×A4定义为(A1×A2×A3)×A4A1×A2×A3×A4

=a1,a2,a3,a4|a1A1∧a2A2∧a3A3∧a4A4

……约定An=第三十三页，共一百三十九页，2022年，8月28日第三章：集合与关系【例】设A=1,2，B=a,b，A=x,y，求：

A×B×C，A×(B×C)。

解：A×B×C=(A×B)×C=1,a,1,b,2,a,2,b×x,y=1,a,x,1,b,x,2,a,x,2,b,x,1,a,y,1,b,y,2,a,y,2,b,y

=1,a,x,1,b,x,2,a,x,2,b,x,

1,a,y,1,b,y,2,a,y,2,b,y

A×(B×C)=1,2×a,x,a,y,b,x,b,y=1,a,x,1,a,y,1,b,x,1,b,y2,a,x,2,a,y,2,b,x,2,b,y显然A×B×C≠A×(B×C)。第三十四页，共一百三十九页，2022年，8月28日第三章：集合与关系§3.4关系及其表示1、二元关系的概念【定义】设A和B是任意集合，如果RA×B，则称R是A到B的二元关系。如果R是A到A的二元关系，则称R是A上的二元关系。设A=1,2,3，B=a,b，R=1,a,2,a,3,b。R是A到B的二元关系。S=3,1,2,2,2,1,1,1。S是A上的二元关系。【定义】设A和B是任意集合，RA×B，若x,yR，则称x与y有R关系。记为xRy。若x,yR，则称x与y没有R关系。记为xy。第三十五页，共一百三十九页，2022年，8月28日第三章：集合与关系

如果R是A到B的二元关系，根据【定义】，x,yR与xRy，x,yR与xy的意义相同。【定义】设A和B是任意集合，空集Æ叫做A到B的空关系，仍然记为Æ。A，B的笛卡尔积A×B叫做A到B的全域关系，记为E。集合a,a|aA叫做A上的恒等关系。记为IA。【例1】设A=a,b，B=1,2，求A上的恒等关系IA和A到B的全域关系A×B。

解：A上的恒等关系IA=a,a,b,b，A到B的全域关系E=A×B=a,1,a,2,b,1,b,2【定理】设A是具有n个元素的有限集，则A上的二元关系有2n2种。

证明：设A为具有n个元素的有限集，即|A|=n，由排列组合原理知|A×A|=n2。根据幂集合定理定理有|P

(A×A)|=2|A×A|=2，即A×A的子集有2个。所以具有n个元素的有限集A上有2种二元关系。第三十六页，共一百三十九页，2022年，8月28日第三章：集合与关系2、关系的表示（1）用列举法表示二元关系上例中的A到B的全域关系

E=A×B=a,1,a,2,b,1,b,2

A上的恒等关系:IA=a,a,b,b都是用列举法表示的。（2）用描述法表示二元关系设R是实数集，LR=x,y|xR∧yR∧x≤y，LR是实数集R上的二元关系。

（3）用矩阵表示二元关系如果A，B是有限集，

A=a1,a2,…,am，B=b1,b2,…,bn，

R是A到B的二元关系，R的关系矩阵定义为：

MR=mn第三十七页，共一百三十九页，2022年，8月28日第三章：集合与关系i=1,…,m

j=1,…,n称为二元关系R的关系矩阵。【例2】设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为：R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2写出R的关系矩阵。解：R的关系矩阵为：MR=

第三十八页，共一百三十九页，2022年，8月28日第三章：集合与关系【例3】设A=1,2,3,4，R是A的二元关系，定义为：R=1,1,1,2,2,1,3,2,3,1,4,3,4,2,4,1写出A上二元关系R的关系矩阵。解：R的关系矩阵为：

MR=上例中的二元关系R是A上的二元关系，只需看成A到A的二元关系，利用上述定义，就可以方便地写出它的关系矩阵。A上的二元关系和A到B的二元关系的关系矩阵的定义是相同的。第三十九页，共一百三十九页，2022年，8月28日第三章：集合与关系

（4）用图表示二元关系如果A和B是有限集，R是A到B二元关系，还可以用图表示二元关系R。表示二元关系R的图叫做R的关系图。A到B二元关系的关系图和A上的二元关系的关系图的定义是不一样的。分别描述如下：

㈠

A到B二元关系R的关系图设A=a1,a2,…,am，B=b1,b2,…,bn，R是A到B二元关系，R的关系图的绘制方法如下：①画出m个小圆圈表示A的元素，再画出n个小圆圈表示B的元素。这些小圆圈叫做关系图的结点(下同)。②如果ai,bj

R，则从ai到bj画一根有方向(带箭头)的线。这些有方向(带箭头)的线叫做关系图的边(下同)。

第四十页，共一百三十九页，2022年，8月28日第三章：集合与关系【例2】中的二元关系R的关系图如图3.8。

㈡A上的二元关系R的关系图设A=a1,a2,…,am，R是A上的二元关系，其关系图如下绘制：①画出m个小圆圈表示A的元素。②如果ai,ajR，则从ai到aj画一根有方向(带箭头)的线。【例3】中的二元关系R的关系图如图3.9。第四十一页，共一百三十九页，2022年，8月28日第三章：集合与关系3、关系的运算【定义】设A，B是集合，RA×B。domR=x|x,yR

叫做R的定义域。ranR=y|x,yR

叫做R的值域。FLDR=domR∪ranR叫做R的域。

A叫做R的前域；B叫做R的陪域。二元关系的交、并、补、对称差运算【定理】设R，S是X到Y的二元关系，则R∪S，R∩S，R-S，~R，RS也是X到Y的二元关系。证明：因为R，S是X到Y的二元关系，所以，

RX×Y且SX×Y。显然，R∪SX×Y，即R∪S是X到Y的二元关系。R∩SX×Y，即R∩S是X到Y的二元关系。R-SX×Y，即R-S是X到Y的二元关系。第四十二页，共一百三十九页，2022年，8月28日第三章：集合与关系在二元关系运算中，认为全域关系是全集。所以~R=X×Y-R

X×Y，即~R是X到Y的二元关系。由以上结论可以得到：(R－S)X×Y和(S－R)X×Y，从而(R－S)∪(S－R)X×Y，所以RS=(R－S)∪(S－R)X×Y，即RS是X到Y的二元关系。

【例4】设X=1,2,3,4，X上的二元关系H和S定义如下：

H=x,y|是整数S=x,y|是正整数试求H∪S，H∩S，~H，S-H第四十三页，共一百三十九页，2022年，8月28日第三章：集合与关系解：将H和S用列举法表示：H=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2S=4,1H∪S=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2,4,1H∩S=Æ~H=X2-

H=1,2,1,4,2,1,2,3,3,2,3,4,

4,3,4,1

S－H=4,1

第四十四页，共一百三十九页，2022年，8月28日第三章：集合与关系§3.5关系的性质【定义】设RX×X，(x)(xX→x,xR)，则称R在X上是自反的。设R是X上的自反关系，由【定义】知，R的关系矩阵MR的主对角线全为1；在关系图中每一个结点上都有自回路。设X=1,2,3，X上的二元关系R=1,1,2,2,3,3,1,2R是自反的,它的关系图如图3.10所示，关系矩阵如下：

MR=第四十五页，共一百三十九页，2022年，8月28日第三章：集合与关系【定理】设R是X上的二元关系，R是自反的当且仅当IXR。证明：设R在X上是自反的，下证IXR。x,yIXx=yx,yR，即IXR。设IXR，下证R在X上是自反的。xXx,xIXx,xR，即R在X上是自反的。【定义】设RX×X，(x)(xX→x,xR)，则称R在X上是反自反的。设R是X上的反自反关系，由【定义】可知，R的关系矩阵MR的主对角线全为0；在R的关系图中每一个结点上都没有自回路。设X=1,2,3，X上的二元关系R=1,2,2,3,3,1，R是反自反的,它的关系图如图3.11所示，关系矩阵如下：第四十六页，共一百三十九页，2022年，8月28日第三章：集合与关系MR=

【例】设R是实数集合，＞=x,y|xR∧yR∧x＞y是实数集合上的大于关系。证明实数集合上的大于关系是反自反的。证明：xR，x≯x，x,x＞，所以＞是反自反的。第四十七页，共一百三十九页，2022年，8月28日第三章：集合与关系【定理】

设R是X上的二元关系,R是反自反的当且仅当R∩IX=Æ。证明：设R在X上是反自反的，下证R∩IX=Æ。假设R∩IX≠Æ必存在x,yR∩IXx,yR∧x,yIXx,yR∧x=y，即x,xR，这与R是X上的反自反关系相矛盾。所以R∩IX=Æ。设R∩IX=Æ，下证R在X上是反自反的。任取xX

x,xIX，由于R∩IX=Æ，必然x,xR，即R在X上是反自反的。

第四十八页，共一百三十九页，2022年，8月28日第三章：集合与关系【例】设A=1,2,3，定义A上的二元关系如下：

R=1,1,2,2,3,3,1,3

S=1,3

T=1,1试说明R，S，T是否是A上的自反关系或反自反关系。解：因为1,1、2,2和3,3都是R的元素，所以R是A上的自反关系，不是反自反关系。因为1,1、2,2和3,3都不是S的元素，所以S是反自反关系，不是A上的自反关系。因为2,2T，所以T不是A上的自反关系。因为1,1T，所以T不是A上的反自反关系

第四十九页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】设RX×X，

(x)(y)(xX∧yX∧x,yR→y,xR)，则称R在X上是对称的。R是X上的对称关系，由定义知，R的关系矩阵MR是对称阵。在R的关系图中，如果两个不同的结点间有边，一定有方向相反的两条边。设X=1,2,3，X上的二元关系R=1,2,2,1,3,3，R是对称的。它的关系图如图3.12所示，关系矩阵如下：MR=第五十页，共一百三十九页，2022年，8月28日第三章：集合与关系【例】设A=1,3,5,7，定义A上的二元关系如下：

R=a,b|(a－b)/2是整数试证明R在A上是自反的和对称的。证明：aA，(a-a)/2=0，0是整数，所以

a,aR。即R是自反的。aA，bA，a,bR，(a-b)/2是整数，因为整数的相反数也是整数，所以(b-a)/2=-(a-b)/2是整数，b,aR。即R是对称的。第五十一页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】设RX×X，(x)(y)(xX∧yX∧x,yR∧y,xR→(x=y))则称R在X上是反对称的。x,yR∧y,xR→(x=y)(x=y)→(x,yR∧y,xR)(x=y)→(x,yR∨y,xR)((x=y)∨x,yR)∨y,xR

((x≠y)∧x,yR)∨y,xR(x≠y)∧x,yR→y,xR

x,yR∧(x≠y)→y,xR由此，反对称的定义又可以等价的描述为：(x)(y)(xX∧yX∧x,yR∧(x≠y)→y,xR)第五十二页，共一百三十九页，2022年，8月28日第三章：集合与关系设R是X上的反对称关系，由【定义】知，在R的关系矩阵MR中以主对角线为轴的对称位置上不能同时为1(主对角线除外)。在R的关系图中每两个不同的结点间不能有方向相反的两条边。设X=1,2,3，X上的二元关系R=1,2,2,3,3,3，R是反对称的。它的关系图如图3.13所示，关系矩阵如下：MR=

第五十三页，共一百三十九页，2022年，8月28日第三章：集合与关系【例】

设A=1,2,3，定义A上的二元关系如下：

R=1,1,2,2

S=1,1,1,2,2,1

T=1,2,1,3

U=1,3,1,2,2,1试说明R，S，T，U是否是A上的对称关系和反对称关系。解：R是A上的对称关系，也是A上的反对称关系。

S是A上的对称关系。因为1,2和2,1都是S元素，而1≠2，所以S不是A上的反对称关系。因为1,2T，而2,1T，所以T不是A上的对称关系。T是A上的反对称关系。U不是A上的对称关系，也不是A上的反对称关系。第五十四页，共一百三十九页，2022年，8月28日第三章：集合与关系【定义】设RX×X，(x)(y)(z)(xX∧yX∧zX∧x,yR∧y,z

R

→x,zR)则称R在X上是传递的。

【例】设R是实数集合，S=x,y|xR∧yR∧x=y是实数集合上的等于关系。证明实数集合上的等于关系是传递的。证明：xR，yR，zR，x,yS且y,zS，由S的定义有x=y和y=z，由实数相等的概念得x=z。再根据S的定义，x,zS。故实数集合上的等于关系S是传递的。第五十五页，共一百三十九页，2022年，8月28日第三章：集合与关系§3.6复合关系和逆关系1、复合关系【定义】设X，Y，Z是集合，RX×Y，SY×Z，集合x,zxX∧zZ∧(y)(yY∧x,yR∧y,zS)叫做R和S的复合关系。记为R∘S，R∘SX×Z，即R∘S是X到Z的二元关系。

【例3.6.1】X=1,2,3,4,5，X上的二元关系R和S定义如下：

R=1,2,3,4,2,2

S=4,2,2,5,3,1,1,3试求R∘S，S∘R，R∘(S∘R)，(R∘S)∘R，R∘R，S∘S，R∘R∘R第五十六页，共一百三十九页，2022年，8月28日第三章：集合与关系解：R∘S=1,5,3,2,2,5S∘R=4,2,3,2,1,4(R∘S)∘R=3,2R∘(S∘R)=3,2R∘R=1,2,2,2S∘S=4,5,3,3,1,1R∘R∘R=1,2,2,2从该例可以看出，R∘S≠S∘R，这说明，二元关系的复合运算不满足交换律。

第五十七页，共一百三十九页，2022年，8月28日第三章：集合与关系【定理】设X，Y，Z，W是集合，RX×Y，SY×Z，T

Z×W，则(R∘S)∘T=R∘(S∘T)证明：x,w(R∘S)∘T(z)(x,zR∘S∧z,wT)

(z)((y)(x,yR∧y,zS)∧z,wT) (z)(y)((x,yR∧y,zS)∧z,wT) (y)(z)(x,yR∧(y,zS∧z,wT))(y)(x,yR∧(z)(y,zS∧z,wT)) (y)(x,yR∧y,wS∘T)x,wR∘(S∘T)所以(R∘S)∘T=R∘(S∘T)第五十八页，共一百三十九页，2022年，8月28日第三章：集合与关系【定理】

设R是A上的二元关系，R∘IA=IA∘R=R证明：先证R∘IA=Rx,yR∘IA(z)(x,zR∧z,yIA)(z)(x,zR∧z=y)x,yR所以

R∘IARx,yRx,yR∧y,yIAx,yR∘IA所以

RR∘IA故

R∘IA=R类似的，可以证明IA∘R=R

第五十九页，共一百三十九页，2022年，8月28日第三章：集合与关系【定理】设R，S，T是A上的二元关系,则⑴

R∘(S∪T)=R∘S∪R∘T⑵(R∪S)∘T=R∘T∪S∘T⑶

R∘(S∩T)R∘S∩R∘T⑷(R∩S)∘TR∘T∩S∘T证明：仅证明⑶，类似地可证明⑴、⑵和⑷。x,yR∘(S∩T)(z)(x,zR∧z,yS∩T)(z)(x,zR∧(z,yS∧z,yT))(z)((x,zR∧z,yS)∧(x,zR∧z,yT))(z)(x,zR∧z,yS)∧(z)(x,zR∧z,yT)x,yR∘S∧x,yR∘Tx,yR∘S∩R∘T故

R∘(S∩T)R∘S∩R∘T第六十页，共一百三十九页，2022年，8月28日第三章：集合与关系

一般地说，R∘S∩R∘T⊈R∘(S∩T)，举反例如下：设A=1,2,3,4,5R=4,1,4,2A×AS=1,5,3,5A×AT=2,5,3,5A×AR∘S∩R∘T=4,5∩4,5

=4,5R∘(S∩T)=4,1,4,2∘3,5=ÆR∘S∩R∘T⊈R∘(S∩T)

【定理】⑴说明，关系的复合运算“∘”对并运算“∪”满足左分配律。⑵说明，关系的复合运算“∘”对并运算“∪”满足右分配律。所以，复合运算“∘”对并运算“∪”满足分配律。由⑶和⑷知，复合运算“∘”对交运算“∩”不满足分配律。

第六十一页，共一百三十九页，2022年，8月28日【定义】设R是A上的二元关系，n为自然数，R的n次幂记为Rn，定义为：⑴

R0=IA⑵

Rn+1=Rn∘R由该定义可以看出，A上的任何二元关系的0次幂都相等，等于A上的恒等关系IA。由该定义还可以看出：R1=R0∘

R=IA∘R=R