离散数学CH01集合论与关系代数课件

离散数学

DiscreteMathematics计算机与信息工程学院第1章集合论与关系代数内容提要集合的基本概念和运算1.1笛卡尔积与关系1.31.4关系的基本运算集合元素的计数1.2内容提要关系的性质1.5等价关系1.71.8相容关系关系的特殊运算1.6内容提要偏序关系1.9函数与复合和反函数1.11函数的定义1.101.1集合的基本概念和运算集合的基本概念集合的基本运算1.2集合中元素的计数【本章内容】1.7等价关系1.8相容关系1.9偏序关系1.10函数的定义和性质1.11函数的复合和反函数【本章内容】集合论(SetTheory)的创始人是德国数学家康托(G.Cantor,1845～1918)，1874年康托发表了集合论的头一篇论文《论所有实代数的集合的一个性质》，直至1897年他发表了有关集合论的最后一篇论文，其间共发表了十多篇有关论文，奠定了集合论的基础。

【绪论：集合论历史简要回顾】

康托指出（1897年）：一个集合就是指我们观察到的或在我们思维中的一些确定的、不同事物的总体；这些事物称为该集合的元素。康托虽然患有精神分裂症，但其思想方法奇特而富有革命性。其关于集合论的重要成果是提出了用“势”的概念对无穷集合进行计数，并比较大小。【1.康托——集合论的创始人】【绪论：集合论历史简要回顾】BertrandRussell(1918)：一个乡村理发师，自夸无人可与之相比。宣称他当然不给自己刮脸的人刮脸，但却给所有自己不刮脸的人刮脸。问题：他是否应该给自己刮脸？【绪论：集合论历史简要回顾】【2.罗素——理发师悖论】罗素(英,1872-1970)1903年罗素悖论:把集合分成两类：凡不以自身为元素的集合称为第一类集合，凡以自身做为元素的集合称为第二类的集合，每个集合或为第一类集合或为第二类集合．设M表示第一类集合全体所成的集合．若M是第一类集,则MM,由M的定义,M∈M,矛盾;若M是第二类集,则M∈M,由M的定义,MM,矛盾.【2.罗素悖论】【绪论：集合论历史简要回顾】在某一非空全集中，有这样一个确定的集合，这个集合中“只有不属于这个集合的元素”。集合论矛盾的出现，形成第三次数学危机，动摇了整个数学的基础,导致罗素类型论和策梅罗系统的诞生【绪论：集合论历史简要回顾】1897年3月28日，布拉里·福蒂第一个提出了集合论中存在悖论，罗素悖论的提出更是震动了整个数学界，造成了第三次数学危机。1908年，策墨罗采用了把集合论公理化的方法来消除悖论，随后又经过多人的努力，公理化集合论已成为数学中发展最为迅速的一个分支。【绪论：集合论历史简要回顾】（1）上帝全能悖论。甲说“上帝是全能的”。乙说“全能就是世界上任何事情都能办到”。请问“上帝能创造出一个对手来击败他自己吗？”（2）唐吉诃德悖论。一个残酷的国王，在其所统治的国家里有一条法律：每个旅游者都要回答一个问题：“您来这里干什么？”。如果回答对了，一切事情都好办；如果回答错了，立刻被绞死。“我是来被绞死的。”【绪论：集合论历史简要回顾】【3.悖论欣赏】（3）柏拉图与苏格拉底悖论柏拉图调侃他的老师，曰：“苏格拉底老师下面的话是假话。”苏格拉底对曰：“柏拉图上面的话是对的。”（4）蠕虫悖论一只蠕虫从一米长的橡皮绳之一端以每秒1厘米的速度向另一端爬去，橡皮绳同时均匀地以每秒伸长1米的速度向同方向延伸，蠕虫会爬到另一端吗？【3.悖论欣赏】【绪论：集合论历史简要回顾】集合的定义与表示集合与元素集合之间的关系空集全集幂集集合的运算：并、交、补、差、对称差【1.1集合的基本概念】集合没有精确的数学定义理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员。集合的表示列元素法

A={a,b,c,d}

谓词表示法B={x|P(x)}B由使得P(x)为真的

x

构成常用数集

N,Z,Q,R,C分别表示自然数、整数、有理数、实数和复数集合，注意0是自然数.

【1.1集合的基本概念】【1.1.1集合的定义及其表示】元素与集合的关系：隶属关系属于，不属于实例：A={x|xRx2-1=0},

A={-1,1}1A,2A注意：对于任何集合A和元素x(可以是集合)，xA和xA两者成立其一，且仅成立其一.【1.1集合的基本概念】【1.1.2集合与元素】例1.1A={a,{b,c},d,{{d}}}{b,c}AbA{{d}}A{d}AdA

【1.1集合的基本概念】【1.1.3隶属关系的层次结构】

包含（子集）

A

B

x(xA

xB)

不包含

A⊈B

x(xA

且xB)

相等

A=B

A

B

且B

A

不相等

AB

真包含

A

B

A

B且

A

B

不真包含

AB

思考：和的定义注意和是不同层次的问题.【1.1集合的基本概念】【1.1.4集合之间的关系】空集不含任何元素的集合实例{x|x2+1=0且xR}就是空集命题空集是任何集合的子集

Ax(xxA)T

推论空集是惟一的.证假设存在1和2，则12且12，因此1=2全集E

相对性:在给定问题中，全集包含任何集合，即A

(AE)【1.1集合的基本概念】【1.1.5空集与全集】定义P(A)={x|xA}实例（1）P()=？（2）P({})=？（3）P({1,{2,3}})=？（4）设A={

a,b,c}，则P(A)=？【1.1集合的基本概念】【1.1.6幂集】【实例解答】

（1）P()={}，（2）P({})={,{}}

（3）P({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}}

（4）设A={

a,b,c}，则P(A)={,{

a},{

b},{

c},{

a,b},{

a,c},{

b,c},{

a,b,c}}【1.1集合的基本概念】【1.1.6幂集】【思考题】如果|A|=n，则|P(A)|=？【1.1集合的基本概念】【1.1.6幂集】【思考题解答】证明：如果|A|=n，则|P(A)|=2n

【1.1集合的基本概念】【1.1.6幂集】集合基本运算的定义

文氏图（JohnVenn）例题集合运算的算律集合包含或恒等式的证明【1.2集合的基本运算】并

AB={x|xA

或

xB}交

AB={x|xA

且xB}相对补

AB={x|xA

且xB}对称差

AB=(AB)(BA)=(AB)(AB)

绝对补

A=EA

【1.2集合的基本运算】【1.2.1集合的基本运算】【1.2集合的基本运算】【1.2.2文氏图表示】运算顺序：和幂集优先，其他由括号确定并和交运算可以推广到有穷个集合上，即

A1A2…An={x|xA1xA2…xAn}

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

ABAB=（后面证明）

AB=AB=A【1.2集合的基本运算】交换AB=BAAB=BAAB=BA结合(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)幂等AA=AAA=A与与分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)=AA(AB)=A吸收律的前提：、可交换【1.2集合的基本运算】【1.2.3集合运算的算律】D.M律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC双重否定A=AE补元律AA=AA=E零律A=AE=E同一律A=AAE=A否定=EE=【1.2集合的基本运算】【1.2.3集合运算的算律】证明

XY命题演算法包含传递法等价条件法反证法并交运算法以上的X,Y代表集合公式【1.2集合的基本运算】【1.2.4集合包含的证明方法】任取x，

xX…xY

例1证明AB

P(A)P(B)

任取x

xP(A)xAxBxP(B)

任取x

xA{x}A{x}P(A){x}P(B){x}B

xB【1.2集合的基本运算】【方法1：命题演算法证XY】P(A)={x|xA}找到集合T满足XT且TY，从而有XY例2AB

AB证

ABAA

AB

所以

AB

AB【1.2集合的基本运算】【方法2：包含传递法证XY

】例3AC且BCABC

证AC

AC=C

BC

BC=C(AB)C=A(BC)=AC=C结合律(AB)C=CABC

命题得证.AB

AB=BAB=A【1.2集合的基本运算】【方法3：利用包含的等价条件证XY

】欲证XY,假设命题不成立，必存在x使得

xX且xY.然后推出矛盾.例4证明AC且BCABC证假设ABC不成立，则

x(xAB但xC)

因此

xA或

xB，且xC

若xA,则与AC矛盾；

若xB,则与BC矛盾.

【1.2集合的基本运算】【方法4：反证法证XY

】由已知包含式通过运算产生新的包含式

XYXZYZ,XZYZ例5证明

ACBCACBCAB证

ACBC，AC

BC

上式两边求并，得

(AC)(AC)(BC)(BC)

(AC)(AC)(BC)(BC)

A(CC)

B(CC)

AE

BE

A

B【方法5：利用已知包含式并交运算证XY

】【1.2集合的基本运算】【1.2集合的基本运算】【1.2.5集合包含或相等的证明方法】证明X=Y互为子集法命题演算法等式代入法反证法运算法方法1——最常用的方法是：互为子集法。即证明：①XY,任取x

，xX…xY②YX任取x

，xY…xX

或者

xX…xY【1.2集合的基本运算】【方法1：互为子集法证明X=Y】例6证明A(AB)=A

（吸收律）证任取x,

xA(AB)xAxABxA(xA

xB)xA

析取对合取的吸收律【1.2集合的基本运算】【方法2：命题演算法证明X=Y】不断进行代入化简，最终得到两边相等例7证明A(AB)=A

（吸收律）证(假设交换律、分配律、同一律、零律成立)

A(AB)=(AE)(AB)同一律

=A(EB)分配律

=A(BE)交换律

=AE

零律

=A

同一律【1.2集合的基本运算】【方法3：等价置换法证明X=Y】假设X=Y不成立，则存在x使得xX且xY，或者存在x使得xY且xX，然后推出矛盾.注：尤其在证明类似X=的时候经常使用反证法。【1.2集合的基本运算】【方法4：反证法证明X=Y】例8证明以下等价条件

AB

AB=B

AB=A

AB=

(1)(2)(3)(4)证明顺序：

(1)(2),(2)(3),(3)(4),(4)(1)【1.2集合的基本运算】(1)(2)显然BAB，下面证明ABB.任取x，

xAB

xAxBxBxBxB因此有ABB.综合上述（2）得证.(2)(3)

A=A(AB)A=AB

（将AB用B代入)【1.2集合的基本运算】(3)(4)假设AB,即xAB，那么xA且xB.而

xB

xAB.从而与AB=A矛盾.(4)(1)假设AB不成立，那么x(xA

xB)xAB

AB与条件（4）矛盾.【1.2集合的基本运算】由已知等式通过运算产生新的等式

X=Y

XZ=YZ,XZ=YZ，X-Z=Y-Z例11证明AC=BC

AC=BC

A=B证由AC=BC

和

AC=BC

得到

(AC)-(AC)=(BC)-(BC)

从而有AC=BC

因此

AC=BC(AC)C=(BC)C

A(CC)=B(CC)A=BA=B【1.2集合的基本运算】【方法5：集合运算法证明X=Y】有穷集合的计数包含排斥原理无穷集的基数【1.3集合中元素的计数】集合A的基数：集合A中的元素数，记作cardA有穷集

A：cardA=|A|=n，n为自然数.有穷集的实例：

A={a,b,c},cardA=|A|=3；

B={x|x2+1=0,xR},cardB=|B|=0无穷集的实例：

N,Z,Q,R,C等【1.3集合中元素的计数】【1.3.1有穷集合的计数】(定理1.3.1——加法原理)：若A和B均为有限集，则：|A∪B|=|A|+|B|-|AB|【1.3集合中元素的计数】【1.3.1有穷集合的计数】【证明】(1)易见，若A∩B=Ø,则|A∪B|=|A|+|B|.【1.3集合中元素的计数】【1.3.1有穷集合的计数】(2)若A与B的交集不为空，则：

A∪B=(A-B)∪(B-A)∪(A∩B).

而A-B,B-A及A∩B均为两两不相交集合，故

|A∪B|=|A-B|+|B-A|+|A∩B|……(1)

另一方面,A=(A-B)∪(A∩B)且

B=(B-A)∪(A∩B),

又(A-B)∩(A∩B)=Ø且(B-A)∩(A∩B)=Ø,

故|A|=|A-B|+|A∩B|且|B|=|B-A|+|A∩B|.【1.3集合中元素的计数】故|A-B|=|A|-|A∩B|……(2)|B-A|=|B|-|A∩B|……(3)因此,|A∪B|=|A-B|+|B-A|+|A∩B|=|A|-|A∩B|+|B|-|A∩B|+|A∩B|=|A|+|B|-|A∩B|定理得证.【1.3集合中元素的计数】定理1.3.2

设A,B,C是有限集，则

|A∪BUC|=|A|+|B|+|C|-|AB|-|BC|-|AC|+|ABC|【1.3集合中元素的计数】【1.3.1有穷集合的计数】定理1.3.3设Ai(I=1,2,…n)为有限集合，则：【1.3集合中元素的计数】【1.3.1有穷集合的计数】推论：（包含排斥原理）设S为有穷集，P1,P2,…,Pm

是m种性质，Ai是S

中具有性质Pi

的元素构成的子集，i=1,2,…,m.则S

中不具有性质P1,P2,…,Pm的元素数为【1.3集合中元素的计数】【1.3.1有穷集合的计数】证设x不具有性质P1,P2,…,Pm,

xAi

,i=1,2,…,m

xAiAj

,1i<jm

…

xA1A2…Am

,x对右边计数贡献为

10+00+…+(1)m·0=1证明要点：任何元素x，如果不具有任何性质，则对等式右边计数贡献为１，否则为０【证明】【1.3集合中元素的计数】【1.3集合中元素的计数】x

对|S|贡献为1x

对贡献为

x

对贡献为

x

对|A1A2…Am|贡献为x对右边计数贡献为设x具有n条性质，1nm

解：S={x|xZ,1x1000},

如下定义S

的3个子集A,B,C：

A={x|xS,5|x}，

B={x|xS,6|x}，

C={x|xS,8|x}例1求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？【1.3集合中元素的计数】【应用】对上述子集计数：

|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【1.3集合中元素的计数】【例1（续）】例1：求1到1000之间（包含1和1000在内）既不能被5和6整除，也不能被8整除的数有多少个？【1.3集合中元素的计数】【文氏图法】例2：24名科技人员，每人至少会1门外语.英语：13；日语：5；德语：10；法语：9英日：2;英德：4；英法：4；法德：4会日语的不会法语、德语求：只会1种语言人数，会3种语言人数.x+2(4-x)+y1+2=13x+2(4-x)+y2=10x+2(4-x)+y3=9x+3(4-x)+y1+y2+y3=19x=1,y1=4,y2=3,y3=2

【1.3集合中元素的计数】定义1.4.1设A是非空集合，π=S1，S2，…，Sm，Si≠Æ，i=1,…,m，且满足：⑴Siπ，SiA⑵S1∪S2∪…∪Sm=A则称π是A的一个覆盖。【1.4集合的覆盖与划分】定义1.4.2设A是非空集合，π=S1，S2，…，Sm，Si≠Æ，i=1,…,m，π是A的一个覆盖，满足Si∩Sj=Æ，i≠j，则称π是A的一个划分。称Si，i=1,…,m，是A的划分块。定义中的“Si∩Sj=Æ，i≠j”是指π中的元素两两互不相交。【1.4集合的覆盖与划分】【例1.4.1】设

A=a,b,c，以下是A的子集构成的集合：

S=a,b,b,cQ=a,a,b,a,cD=a,b,cG=a,b,cE=a,b,cF=a,a,c

试确定哪些集合是A的覆盖？哪些集合是A的划分？哪些集合既不是覆盖，也不是划分？解：S和Q是A的覆盖，但不是划分；D、G和E是A的覆盖，也是划分；F不是A的覆盖，也不是划分。【1.4集合的覆盖与划分】

集合G=a,b,c是单元素集，它有一个元素a,b,c。对单元素集a,b,c，认为它的元素的并集就是a,b,c，同时也认为它的元素是两两互不相交的。所以集合G=a,b,c是A的划分。

在A的所有划分中基数最大的划分叫做A的最大划分，基数最小的划分叫做A的最小划分。【1.4集合的覆盖与划分】【例1.4.2】设A=1,2,3，试确定A的所有划分。

解：有一个划分块的划分是：1,2,3

有两个划分块的划分是：1,2,32,1,33,1,2

有三个划分块的划分是：1,2,3

图3.9是A的所有划分的示意图。(a)表示有一个划分块的划分1,2,3。(b)、(c)和(d)表示有两个划分块的划分1,2,3、2,1,3和3,1,2。(e)表示有三个划分块的划分1,2,3。【1.4集合的覆盖与划分】定理1.4.1设A=A1，A2，…，Ar与B=B1，B2，…，Bs是C的两种划分，则集合X=Ai∩Bj|i=1,…,r，j=1,…,s，Ai∩Bj≠Æ也是C的划分。证明:

⑴先证Ai∩BjC

由A，B是C的划分知，AiC，BjC，所以Ai∩BjC。【1.4集合的覆盖与划分】

⑵再证:(A1∩B1)∪(A1∩B2)∪…∪(A1∩Bs)∪(A2∩B1)∪(A2∩B2)∪…∪(A2∩Bs)∪…(Ar∩B1)∪(Ar∩B2)∪…∪(Ar∩Bs)=(A1∩(B1∪B2∪…∪Bs))∪…∪(Ar∩(B1∪B2∪…∪Bs))=(A1∪A2∪…∪Ar)∩(B1∪B2∪…∪Bs)=C∩C=C【1.4集合的覆盖与划分】⑶最后证X中的元素是两两互不相交的。在X中取任意两个不同元素，Ai∩Bh与Aj∩Bk，分三种情况讨论：①设i≠j，h=k(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)=Æ∩(Bh∩Bk)=Æ②设i≠j，h≠k(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)=Æ∩Æ=Æ③设i=j，h≠k(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)=(Ai∩Aj)∩Æ=Æ【1.4集合的覆盖与划分】定义1.4.2定理1.4.1中定义的集合X叫做原来两种划分A和B的交叉划分。定义1.4.3设A=A1，A2，…，Ar与B=B1，B2，…，Bs是C的两种划分，如果AiA

，BkB，使得Ai

Bk。则称A是B的加细，也称A是B的细分。定理1.4.2任何两种划分的交叉划分都是原来两种划分的一种加细。

证明：设A=A1，A2，…，Ar与B=B1，B2，…，Bs是C的两种划分。

X=Ai∩Bj|i=1,…,r，j=1,…,s，Ai∩Bj≠Æ是A和B的交叉划分。因为Ai∩BjAi，Ai∩BjBj，所以X是A的一种加细，也是B的一种加细。【1.4集合的覆盖与划分】思考题：若|A|=n,则集合A上可以确定多少种不同的划分？【1.4集合的覆盖与划分】

序偶（有序对）笛卡儿积及其性质二元关系的定义二元关系的表示【1.5关系及其表示】定义

由两个客体x和y，按照一定的顺序组成的二元组称为有序对，记作<x,y>实例：点的直角坐标(3,4)有序对性质有序性<x,y><y,x>（当xy时）

<x,y>与<u,v>相等的充分必要条件是

<x,y>=<u,v>x=uy=v例1<2,x+5>=<3y4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

【1.5关系及其表示】【1.5.1序偶】定义一个有序n(n3)元组<x1,x2,…,xn>是一个有序对，其中第一个元素是一个有序n-1元组，即

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

当n=1时,<x>形式上可以看成有序1元组.实例

n维向量是有序

n元组.【1.5关系及其表示】【1.5.1序偶】定义设A,B为集合，A与B的笛卡儿积记作AB，即AB={<x,y>|xAyB}例2A={1,2,3},B={a,b,c}

AB={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}

A={},P(A)A={<,>,<{},>}

【1.5关系及其表示】【1.5.2笛卡尔积及其性质】不适合交换律

ABBA(AB,A,B)不适合结合律

(AB)CA(BC)(A,B)对于并或交运算满足分配律

A(BC)=(AB)(AC)(BC)A=(BA)(CA)

A(BC)=(AB)(AC)(BC)A=(BA)(CA)若A或B中有一个为空集，则AB就是空集.

A=B=

若|A|=m,|B|=n,

则|AB|=mn

【1.5关系及其表示】【1.5.2笛卡尔积及其性质】证明A(BC)=(AB)(AC)证任取<x,y><x,y>∈A×(B∪C)

x∈A∧y∈B∪C

x∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)<x,y>∈A×B∨<x,y>∈A×C<x,y>∈(A×B)∪(A×C)所以有A×(B∪C)=(A×B)∪(A×C).【1.5关系及其表示】【1.5.2笛卡尔积及其性质】例3(1)证明A=B且C=DAC=BD

(2)AC=BD是否推出A=B且C=D?为什么？解(1)任取<x,y><x,y>AC

xAyC

xByD<x,y>BD

(2)不一定.反例如下：

A={1}，B={2},C=D=,则AC=BD但是AB.【1.5关系及其表示】【1.5.2笛卡尔积及其性质】定义如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.如<x,y>∈R,可记作xRy；如果<x,y>R,则记作xy实例：R={<1,2>,<a,b>},S={<1,2>,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系根据上面的记法，可以写1R2,aRb,ac等.【1.5关系及其表示】【1.5.3二元关系的定义】定义设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例4A={0,1},B={1,2,3},R1={<0,2>},R2=A×B,R3=,R4={<0,1>}.那么R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.【1.5关系及其表示】【1.5.3二元关系的定义】直观地看，二元关系就是反映“多值对应”的二维表，例如，学生－选课表：学生课程张三离散数学李四微积分张三高级语言......【1.5关系及其表示】

把学生选课表用集合来表示：R={（张三,离散数学）,

（李四,微积分）,

（张三,高级语言）,

…}序偶的集合R同样也刻画了学生集合A=｛张三，李四，…｝与课程集合B=｛离散数学，微积分，高级语言，…｝之间“多值对应”的联系。【1.5关系及其表示】『思考题』计数若|A|=n,则集合A上有多少个不同的二元关系？【1.5关系及其表示】【1.5.3二元关系的定义】设A1,A2,…An是集合，则称A1×A2×…×An的任意一个子集R为A1,A2,…An间的n元关系。集合A1,A2,…,An叫做关系的域,n叫做它的阶。若RAn,则称R为A上的n元关系。可以利用n元关系表示计算机的数据库:数据库由记录组成，这些记录是由字段构成的n元组。字段是n元组的数据项。【1.5关系及其表示】例设R是A×N×S×D×T

的子集，其中A是所有航空公司的集合，N是航班号的集合，S是出发地的集合，D是目的地的集合，T是起飞时间的集合。则R是由5元组(a,n,s,d,t)组成的表示飞机航班的关系。例如，设R表示由国内航空公司飞机航班构成的关系，如果南方航空公司在15:00有从广州到北京的2963航班，那么(

南方航空，2963，广州，北京，15:00)属于R。【1.5关系及其表示】继续考察日常生活和科学技术中的“关系”A上重要关系的实例：设A为任意集合，是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系，定义如下：EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}

例如,A={1,2},则

EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}【1.5关系及其表示】【1.5.3二元关系的定义】小于等于关系LA,整除关系DA,包含关系R定义：

LA={<x,y>|x,y∈A∧x≤y},AR，R为实数集合

DB={<x,y>|x,y∈B∧x整除y},BZ*,Z*为非0整数集

R={<x,y>|x,y∈A∧xy},A是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.【1.5关系及其表示】【1.5.3二元关系的定义】例如A={1,2,3},B={a,b},则

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

A=P(B)={,{a},{b},{a,b}},则A上的包含关系是R={<,>,<,{a}>,<,{b}>,<,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}【1.5关系及其表示】【1.5.3二元关系的定义】定义域domain、值域range

和域

domR={x|y(<x,y>R)}R中所有序偶的第一元素构成的集合ranR={y|x(<x,y>R)}R中所有序偶的第二元素构成的集合fldR=domR

ranR例1R={<1,2>,<1,3>,<2,4>,<4,3>},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}【1.5关系及其表示】【1.5.3二元关系的定义】相关集：设R是A到B的二元关系，xA,定义R(x)如下：R(x)={yB|xRy}，则称R(x)为x的R相关集。若A1A,定义R(A1)如下：R(A1)={yB|xA1andxRy},称R(A1)为A1的相关集。【1.5关系及其表示】【1.5.3二元关系的定义】

【例】A={1,2,3},B={x,y,z,w,p,q}R={(1,x),(1,z),(2,w),(2,p),(3,y)}Dom(R)={1,2,3}=ARan(R)={x,y,z,w,p}R(1)={x,z}A1={1,2},R(A1)={x,z,w,p}【1.5关系及其表示】【1.5.3二元关系的定义】【定理1.5.1】

设R是A到B的二元关系,A1和A2是A的子集。则:(a)若A1A2,则R(A1)R(A2)(b)R(A1A2)=R(A1)R(A2)(c)R(A1A2)R(A1)R(A2)【1.5关系及其表示】表示方式：关系的集合表达式关系矩阵关系图【1.5关系及其表示】【1.5.4关系的表示】关系矩阵：若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中rij

=1<xi,yj>R.【1.5关系及其表示】【1.5.4关系的表示——关系矩阵】关系图：若A={x1,x2,…,xm}，R是从A上的关系，R的关系图是GR=<A,R>,其中A为结点集，R为边集.如果<xi,xj>属于关系R，在图中就有一条从xi

到xj的有向边.注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系【1.5关系及其表示】【1.5.4关系的表示——关系图】A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系矩阵MR和关系图GR如下：【1.5关系及其表示】【1.5.4关系的表示——关系图】关系图情形1：R是从A到B的关系,采用如下的图示:

1）用大圆圈表示集合A和B，里面的小圆圈（或实心圆）表示集合中的元素;2）若a∈A，b∈B，且(a,b)∈R，则在图中将表示a和b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。【1.5关系及其表示】例如：

A={a1,a2,a3,a4}

B={b1,b2,b3,b4,b5}

R={(a1,b1),(a2,b3),(a3,b2),(a4,b4),(a4,b5)}【1.5关系及其表示】情形2：R是A上的关系,其画法如下:1)集合A中的每一个元素a用带有元素符号的顶点(称作顶点a)表示。2)若a,b∈A,且(a,b)∈R,则将顶点a和顶点b用一条带有箭头的有向边连接起来,其方向由顶点a指向顶点b。【1.5关系及其表示】【例】A={a1,a2,a3,a4,a5}，

R={(a1,a1),(a1,a2),(a2,a3),(a3,a4),(a4,a1),(a4,a5),(a5,a3)}。求R的关系图。【1.5关系及其表示】【例】设A＝{1,2,3,4,5},B＝{a,b,c},求下面两个关系的关系矩阵。A到B的关系:R1＝{(1,a),(1,b),(2,b),(3,a)}B到A的关系:R2＝{(a,2),(c,4),(c,5)}【1.5关系及其表示】

【例】

求A＝{1,2,3,4}上的≤关系、EA和IA的关系矩阵。【定义】设R是集合A上的二元关系.R中从a到b的一条长度为n的路是指一个有限序列:a,x1,x2,…,xn-1,b,即aRx1,x1Rx2,…,xn-1Rb.【1.5关系及其表示】【1.5.5关系中的路】【定义】

一条起点和终点为同一节点的路称为环.【定义】

设n为正整数，定义A上的二元关系Rn

如下：Rn={<x,y>|R中有一条从x到y的长度为n的路}.【1.5关系及其表示】【1.5.5关系中的路】【定义】

设R是集合A上的二元关系，定义A上的二元关系R∞

如下：

R∞={<x,y>|R中有一条从x到y的路}.R∞称为R的连通关系。【定义】设R是集合A上的二元关系，定义A上的二元关系R*

如下：

R*={<x,y>|x=y或R中有一条从x到y的路}.R*称为R的可达关系。【1.5关系及其表示】【1.5.5关系中的路】

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

计算R2,R3,R4,R∞【1.5关系及其表示】【1.5.5关系中的路】【定义】矩阵A称为布尔矩阵（Booleanmatrix），若其每个元素要么是1要么是0.【定义】设A=[aij]，B=[bij]均为m×n的布尔矩阵，定义:A∨B=C=[cij]如下：

cij=称之为A和B的并。1aij=1或bij=10aij=0且bij=0【1.5关系及其表示】【1.5.6布尔矩阵及其运算】【定义】设A=[aij]，B=[bij]均为m×n的布尔矩阵，定义:A∧B=C=[cij]如下：

cij=称之为A和B的交。1aij=1且bij=10aij=0或bij=0【1.5关系及其表示】【1.5.6布尔矩阵及其运算】【定义】设A=[aij]是m×p的布尔矩阵，B=[bij]是p×n的布尔矩阵.定义:A⊙B=E=[eij],

eij=为A和B的布尔积。1k,1≤k≤n，使得aik=1且bkj=10否则【1.5关系及其表示】【1.5.6布尔矩阵及其运算】【定理1.5.2】

设R是集合A={a1,a2,…,an}上的二元关系,则：MR2=MR⊙MR【1.5关系及其表示】【1.5.6布尔矩阵及其运算】[Proof]LetMR=[mij]andMR2=[nij].Bydefinition,thei,jthelementofMR⊙MRisequalto1ofandonlyifrowIofMRandcolumnjofMRhavea1inthesamerelativeposition,saypositionk.Thismeansthatmik=1andmkj=1forsomek,1≤k≤n.BydefinitionofthematrixMR,theprecedingconditionsmeanthataiRakandakRaj.ThusaiR2aj,andsonij=1.Wehavethereforeshownthatpositioni,jofisequalto1ifandonlyifnij=1.ThismeansthatMR2=MR⊙MR【1.5关系及其表示】【1.5.6布尔矩阵及其运算】【定理1.5.3】设R是有限集A={a1,a2,…,an}上的二元关系,则MRn=MR⊙MR⊙…⊙MR(n为自然数)【1.5关系及其表示】【1.5.6布尔矩阵及其运算】R∞=R∪R2∪R3…MR∞=MR∨MR2∨MR3…

定义：关系R在集合A上的可达关系R*

定义如下:xR*y当且仅当x=y或

xR∞y.【1.5关系及其表示】【1.5.6布尔矩阵及其运算】【注意】关系是一个集合，因此，所有集合的运算及规律均适用于关系。逆运算复合运算闭包运算【1.6关系的运算】定义（逆）：设R是集合A到B的二元关系，称：R1={<y,x>|<x,y>R}为R的逆。例1令A={1,2,3,4},

R={<1,2>,<2,3>,<1,4>,<2,2>}R1={<2,1>,<3,2>,<4,1>,<2,2>}显然有：设R是任意的关系,则(R1)1=R

【1.6关系的运算】【1.6.1逆运算】【定理1.6.1】

设R和S是集合A到B的二元关系.则：（1）MR∩S=MR∧MS

（2）MR∪S=MR∨MS

（3）MR-1=(MR)T【1.6关系的运算】【1.6.1逆运算】【定理1.6.2】

设R和S是集合A到B的二元关系.则：

(1)若RS,则R-1S-1

(2)若RS,则ScRc(3)(R∩S)-1=R-1∩S-1

(R∪S)-1=R-1∪S-1(4)(R∩S)c=Rc∪Sc

(R∪S)c=Rc∩Sc【1.6关系的运算】【1.6.1逆运算】定义（复合运算）：

设R是从A到B的二元关系，S是从B到C的二元关系，定义：

R∘S=|<x,z>|

y(<x,y>R<y,z>S)}称R∘S

为R和S复合关系。例2令A={1,2,3,4},R和S均为集合A上的二元关系，

R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}

求：R∘S，S∘R【1.6关系的运算】【1.6.2复合运算】【解】R={<1,2>,<2,3>,<1,4>,<2,2>}

S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}R∘S={<1,3>,<2,2>,<2,3>}

S∘R={<1,2>,<1,4>,<3,2>,<3,3>}【1.6关系的运算】【1.6.2复合运算】

利用图示（不是关系图）方法求合成

R∘S={<1,3>,<2,2>,<2,3>}

S∘R={<1,2>,<1,4>,<3,2>,<3,3>}【1.6关系的运算】【1.6.2复合运算】【定理1.6.3】设F,G,H是任意的关系,则

(1)(F∘G)∘H=F∘(G∘H)(2)(F∘G)1=G1∘F1证(1)任取<x,y>,<x,y>(F∘G)∘Ht(<x,t>∈F∘G∧<t,y>∈H)t(s(<x,s>∈F∧<s,t>∈G)∧<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∘(G∘H)

所以(F∘G)∘H=F∘(G∘H)【1.6关系的运算】【1.6.2复合运算】

(2)任取<x,y>,<x,y>∈(F∘G)1

<y,x>∈F∘G

t(<y,t>∈F∧(t,x)∈G)

t(<x,t>∈G1∧(t,y)∈F1)

<x,y>∈G1∘F1

所以(F∘G)1=G1∘F1

【1.6关系的运算】【1.6.2复合运算】【定理1.6.4】

设集合A,B,C均为有限集，A={a1,a2,…,am}B={b1,b2,…,bn},C={c1,c2,…,cp},R是A到B的二元关系，S是B到C的二元关系,则：MR∘S

=MR⊙MS【证明留为作业】【1.6