7.1-集合与关系(2)(部编)课件

二元关系<a,b>可表达关系：兄弟、同事、小于、等于、整除。定义：任何一个有序对集合称为一个二元关系，简称关系，记作R。(R为A×B的子集)、(A2的子集R称为A上的二元关系)R由<a,b>组成，若<a,b>

R，称a,b有关系R,记aRb，否则aRb。

1例如，集合A={a,b,c},B={b,c,d},A到B的一个二元关系R={<a,b>,<b,c>,<b,d>}.几种特殊的关系若R=

，称R为空关系；若R=A×B，称R为全关系；若IA={<a,a>|a

A},称IA为A上的恒等关系。2解：全关系：A×A=A2={<a,a>,<a,b>,<a,c>, <b,a>,<b,b>,<b,c>,<c,a>,<c,b>,<c,c>}.

恒等关系：IA={<a,a>,<b,b>,<c,c>}.■例2：A={2,3,5},B={2,3,4,5,6}. R={<a,b>|a|b

a

A,b

B}. 求R.解：R={<2,2>,<2,4>,<2,6>,<3,3>,<3,6>,<5,5>}。 ■例1：A={a,b,c},求A上的全关系和恒等关系。3解:R={<1,1>,<1,3>,<2,2>,<2,4>,<3,1>,<3,3>,<4,2>, <4,4>}.S={<4,1>}.R∪S={<1,1>,<1,3>,<2,2>,<2,4>,<3,1>,<3,3>,<4,1>, <4,2>,<4,4>}.R∩S=.~R={<1,2>,<1,4>,<2,1>,<2,3>,<3,2>,<3,4>,<4,1>,<4,3>}.S－R={<4,1>}=S.

■显然，R∪S,R∩S,~R,S－R仍为关系。（定理）例3:A={1,2,3,4},R={<a,b>| 是整数，a,b

A}

={<a,b>|a,b

A,a≡b(mod2)},

S={<a,b>| 是正整数},

求R∪S,R∩S,~R,S-R.4例4:H={f,m,s}表示一家庭成员。试确定H上的全关系，空关系，另外再确定一关系。解：设R1

为同一家庭成员关系，则

R1={<f,f>,<f,m>,<f,s>,<m,f>,<m,m>,<m,s>, <s,f>,<s,m>,<s,s>}=H×H.为H的全关系。 设R2

为互不相识关系，则R2=

. 为H的空关系。 设R3

为长幼关系，则R3={<f,s>,<m,s>}. ■5例5:A={a,b},R是ρ(A)上的包含(于)关系。求R.解：ρ(A)={,{a},{b},{a,b}}.

={,{a},{b},A}.R={<,>,<,{a}>,<,{b}>,<,A>,<{a},{a}>, <{a},A>,<{b},{b}>,<{b},A>,<A,A>}.■另有≤关系,<关系。关系的另两种表示方法：矩阵、图形。6关系矩阵和关系图当|A|=|B|时，MR为方阵。定义A={a1,a2,…,am},B={b1,b2,…,bn},R是A,B上的二元关系。7例6.A={1,3,5,7},B={2,4,6},

R={<x,y>|x

A∧y

B∧x>y}.求MR.解:R={<3,2>,<5,2>,<5,4>,<7,2>,<7,4>,<7,6>}.反过来，可从MR写出关系R.8例7.A={1,2,3,4,5,6},R={<x,y>|x/y

N,x,y

A}.求MR.解:R={<1,1>,<2,1>,<2,2>,<3,1>,<3,3>,<4,1>,<4,2>,<4,4>,<5,1>,<5,5>,<6,1>,<6,2>,<6,3>,<6,6>}.9几个特殊关系的关系矩阵空关系全关系恒等关系10二元关系的图表示定义A={a1,a2,…,am},B={b1,b2,…,bn},R是A,B上的二元关系，用空心点表示a1,a2,…,am,b1,b2,…,bn,称为结点。若<ai,bj>R,则结点ai到bj用有向弧连接，若<ai,bj>R,则结点ai到bj无有向弧连接，这样得到R的关系图。若<ai,aj>

R,则结点ai到aj有一条有向的封闭弧，称为自回路。11例8.A={1,3,5,7},B={2,4,6},

R={<x,y>|x

A∧y

B∧x>y}.求R的关系图.解:前面已求R={<3,2>,<5,2>,<5,4>,<7,2>,<7,4>,<7,6>}.

R的关系图:反过来，可从关系图写出关系R.1357246AB12例9.A={1,2,3,4,5,6},R={<x,y>|x/y

N,x,y

A}.求R的关系图.解:R={<1,1>,<2,1>,<2,2>,<3,1>,<3,3>,<4,1>,<4,2>,<4,4>,<5,1>,<5,5>,<6,1>,<6,2>,<6,3>,<6,6>}.A123456关系图

R关系矩阵三者之间关系.(知道其中之一就能推出另两个)137.1.5关系的性质

自反与反自反性定义7.6:R

A2,若aA都有<a,a>R,则称R是自反的。若a

A都有<a,a>R,则称R是反自反的。≤、≥、、整除、同余——自反关系。14例1:A={a,b,c},A上的二元关系R={<a,a>,<c,c>},S={<a,a>,<a,b>,<b,b>,<b,c>,<c,c>},

T={<a,c>,<b,a>},试判断R,S,T是否为A上的自反关系或反自反关系。解：abcRabcSabcT∵IA

S

∴S是自反关系；∵IA∩T=

∴T是反自反关系.15对称与反对称性定义7.6:R

A2,a,b

A，若<a,b>R就必有<b,a>R,则称R是对称的。若<a,b>R且<b,a>R，就必有a=b,则称R是反对称的。R对称MR对称关系图中有向弧成对出现。16例3:设集合A={a,b,c}上的二元关系R={<a,a>,<a,b>,<b,a>,<b,c>,<c,b>},

S={<a,a>,<c,c>},T={<a,c>,<b,b>},判断R,S,T是否为A上的对称关系或反对称关系。解：abcRabcSabcTR和S是对称关系。S和T是反对称关系。17例4:A上的关系R={<x,y>|x,y

A∧(x－y)/2是整数}.证R在A上自反和对称。证:

x

A,∵(x－x)/2=0,即<x,x>

R,∴R自反。

x,y

A,若<x,y>R,即(x－y)/2是整数,则

(y－x)/2也是整数,∴<y,x>

R,得R对称.■≤、

为反对称关系。18

R是反对称的MR的对称位置上不能同时为1.R是反对称的关系图中如果两点间有弧，只能有一条。非对称也非反对称的例:R={<1,2>,<1,3>,<3,1>}.对称也是反对称的例:R={<1,1>,<2,2>,<3,3>}.19传递性

定义7.6:R

A2,a,b,c

A若<a,b>R∧<b,c>R,必有<a,c>R,则称R是传递的。≤、是传递关系。例5:A={a,b,c},R1={<a,a>,<a,b>,<a,c>,<b,c>}, R2={<a,b>},R3={<a,b>,<b,c>}.

R1,R2是传递的，R3不是传递的。abcabcabc传递若a→b,b→c有弧，则a→c有弧.20关系性质在矩阵和图上的反映性质矩阵MR关系图自反主对角线全为1各结点有自回路对称MR对称两点之间弧成对出现反对称对称元素不能同时为1两点之间弧不成对出现传递a→b,b→c有弧，则a→c有弧21小结：(关系已有4种运算，5种性质)R1A×B~R1R1R2A×BR1

R2R1R2A×BR1

R2R1R2A×BR1﹣R222<a,a>

a

AR自反<a,b><b,a>R对称<a,b>R反对称<b,a><a,b>,<b,c><a,c>R传递R反自反

aA

<a,a>23关系的运算:∪,∩,－,~.关系的性质:自反、反自反、对称、反对称、传递。下面介绍二类特殊的关系： 等价关系 偏序关系 24

等价关系定义7.7设R是非空集合A上的二元关系，若R具有自反、对称、传递性，则称R为A上的等价关系。（≌）三角形相似关系。居住同一区域关系。25例1:设集合A={1,2,3,4,5,6,7,8}上的“模3同余”关系

R={<a,b>|a≡b(mod3),a,b

A}={<a,b>|(a-b)/3

Z,a,b

A}.

⑴证R为等价关系。

⑵求MR,关系图。解:R={<1,1>,<1,4>,<1,7>,<2,2>,<2,5>,<2,8>,<3,3>,<3,6>,<4,1>,<4,4>,<4,7>,<5,2>,<5,5>,<5,8>,<6,3>,<6,6>,<7,1>,<7,4>,<7,7>,<8,2>,<8,5>,<8,8>}.⑴a)a

A,∵(a-a)/3=0

Z,∴<a,a>

R.R自反。

b)设<a,b>R(a-b)/3Z(b-a)/3Z <b,a>R,∴R对称.c)设<a,b>R∧<b,c>R(a-b)/3Z∧(b-c)/3Z

(a-b)/3+(b-c)/3Z(a-c)/3Z<a,c>R, ∴R传递. ∴R为等价关系。26⑵71463825试通过关系图来验证R是等价关系。27由R划分A定义7.8

设R是非空集合A上的等价关系，对任意a

A，令则称[a]R为a关于R的一个等价类。记作[a]

。A

1,4,7[1]2,5,8[2]3,6[3]如前例1:28（选）整数集合Z上的模

n同余等价关系

R={<a,b>|a≡b(mod3)∧a,b

A}.构成n个等价类：[0]={,－2n,－n,0,n,2n,};[1]={,－2n+1,－n+1,1,n+1,2n+1,};[2]={,－2n+2,－n+2,2,n+2,2n+2,};

[n-1]={,－n－1,－1,n－1,2n－1,3n－1,};29

定理若R是非空A上的等价关系,对

a,b

A

(1)[a],且[a]A;

(2)若aRb,则[a]=[b];

(3)若a

R

b,则[a]∩[b]=;

(4)∪{[a]|a

A}=A.等价关系R把A分成互不相关的等价类。例2.A={1,2,3,4},[1]={1},[2]={2,3},[4]={4},求等价关系R.解:R={<1,1>,<2,2>,<3,3>,<4,4>,<2,3>,<3,2>}.■30设R是非空集合A上的等价关系，以R的所有等价类作为元素的集合，称为A关于R的商集，记作A/R。

即A/R={[a]R|a

A}前例1:设集合A={1,2,3,4,5,6,7,8}上的“模3同余”关系R={<a,b>|a≡b(mod3),a,bA}={<1,1>,<1,4>,<1,7>,<2,2>,<2,5>,<2,8>,<3,3>,<3,6>,<4,1>,<4,4>,<4,7>,<5,2>,<5,5>,<5,8>,<6,3>,<6,6>,<7,1>,<7,4>,<7,7>,<8,2>,<8,5>,<8,8>}，有三个等价类：[1]={1,4,7},[2]={2,5,8},[3]={3,6}.∴A/R={[1],[2],[3]}.31偏序关系定义7.9:设R是非空集合A上的二元关系，若R具有自反、反对称、传递性，则称R为A上的偏序关系，或称半序关系，记作≤。如果<a,b>

≤则记作a≤b。数的关系：≤、≥。偏序关系是广义的≤关系。整除关系：|。包含关系：、等。32例3:设集合A={a,b,c}上的二元关系R={<a,a>,<a,b>,<a,c>,<b,b>,<b,c>,<c,c>}，试用关系图、矩阵来验证R为偏序关系。解:cab 图中存在自回路、两点间单条弧、有a→b,b→c弧,就有a→c弧。∴R为偏序关系。（矩阵类似）■33例4:实数集R上的“≥”关系S是偏序关系。 S={<a,b>|a≥b,a,bR}.证:a)a

R,∵a≥a,∴<a,a>

S.S自反。

b)设a≠b∧<a,b>S

a≥b

b不≥a <b,a>S,∴S反对称.c)设<a,b>S∧<b,c>S

a≥b

∧b≥c

a≥c

<a,c>S, ∴S传递. ∴S为偏序关系。■考虑:实数集R上的“>”关系,