计算机数学-3 -1 2 序关系

3-12序关系

上次课我们介绍了一个非常重要的关系——等价关系。R是A上

的等价关系，将与a等价的元素放在一起构成了a的等价类

[a]人={x\xA/\aJRx}

由⑷及可知:商集A/R={[a]R\a^A}A/R是A的一个划分。

今天学习3—12序关系

1.定义：R是A上关系，满足自反性，反对称性，传递性，则

称R为偏序关系记作"0"。序偶vA,W>称为偏序集。

如W，=等都是偏序关系。vR£>,<夕<忠〉偏序集。

举例如下：

A={2,3,6,8}.R={<x,y>|x整除y}

R={<292>,<2,6>,<2,8>,<3,3>,<3,6>,<6,6>,

v8,8>}

3-12序关系

[0001i

易于验证，R满足自反性，反对称，传递性

***R是偏序关系vA,R＞是偏序集

偏序可以由A中元素按层次划分，为此先定义“盖住”。

2.定义：在vA,g＞中，若x,y£A,x＜y,但xry且不存在

另外的z£A,使得xgz,z＜y,贝Ll称y盖住x。（即x与y直接有

＜,中间不能再添加其他元素构成关系）如上例中＜2,6＞是满足条

件的，6盖住2。＜3,6＞,＜2,8＞都是。

3-12序关系

例：A={x|x是12的因子}={1,2,3,4,6,12}。

<={<x,y>|x整除y}o

<1?12>,<2?2>,<2,4>,<2?6>,<2912>,

<393>,<3,6>,<3?12>,<4,4>9<4?12>?

<6?6>,<6,12>,<12,12>}

可证3是偏序关系。

将所有这些y盖住x的序偶记作COVA={<x,y>|且y盖住x}

COVA={v1,2>,<1,3>,<2,4>,<2,6>,<3,6>,

<4,12>,<6,12>}

3-12序关系

3.偏序集可用盖住的性质画出偏序集合中所有元素图形称为

哈斯图(Hasse),其规则为：

(1).A中的元素用1个圆圈表示。

(2).若xgy,且xRy,则将代表y的圆圈画在代表x的圆圈之上。

(3).若vx,y>£COVA,贝在x与y之间用直线连接。

这样得到的图形称为哈斯图。

由Hasse图，可以清楚地看出结点的层次关系。

3-12序关系

如上例中，其Hasse图为：

先画6个小圆圈，2在1上，3在1上，…，12在6上面

由covA可画出：

12

46

A中元素按层次排列

,M3

1

3-12序关系

偏序集中并非所有元素之间都有偏序关系，如＜2,3＞对偏序集中

所有元素之间都有偏序关系，我们叫它全序，因此，首先定义链。

4.链：偏序集vA,W＞,BoA,若对于任意x,y£B都有

xgyoryWx则称B是链。若B中每两个元素都不满足，则称B是反

链。（即链中任两个元素都是有关系的，反链中任两个元素无偏序

关系）

约定：若B中只有一个元素，规定B既是链又是反链。

3-12序关系

a,b,c,d,e）其关系矩阵为:

MR可以证明R是偏序关系

[<a,a><a,b><a,c><a,d><a,e>

<b,b><b,c><b,e>

<c,c><c,e>

<d,d><d,e>

<e,e>

<A,R>是一'偏序集。

3-12序关系

链：{a}"b}"c}"d}"e}"a,

b},{b,c},{a,c},{a,b,c},

四边形+两对角线

反链：{a}"b}"c}"b,d},

{c,d}等。

三个点均不相连

3-12序关系

5.定义：偏序集<A,W>,若A是一个链，则A是全序集或线

性集。即A中任何元素x,y有关系或xgy或ygx

例：P={①，{a},{a,b},{a,b,c}}

vP,三＞是全序集。{a,b,c}

但(〃a,b,c})={①，{a},{b},{c},

{a,b},{a,c},{b,c},{a}/{a,b}

{a,b,c}}不是全序关系/

・・・{a},{b}无关/

A＜A{a,b,c}),1＞不是全序集0

3-12序关系

从哈斯图我们可以看出，A中各元素位于不同层次，有一些特殊位

置的元素。下面将单独讨论这些元素。

6.极大元，极小元

定义偏序集<A,S>,B鱼。

(a)b£B,若不存在x£B使得x，b且

b<x,则称b是B的极大元。

(b).beB,若不存在x£B使得xRb且

x<b,则称b是B的极小元。

如人={2,3,6,12,18,24,36}。<

W={<x,y>|x整除y)

<A,>偏序集。Hasse囱为：

3-12序关系

B={2,3,6,12,18}

COVB={<2,6>,<3,6>,

<6,12>,<6,18>}

<B?<>HASSE图为：

B极大元：12,18o极小元：2,3

Hasse图中最底层的元素是极小元

JHasse图中最顶层的元素是极大元

2,3无关，并且不同极大（小）元的之间是无关的

3-12序关系

7.最大元，最小元

定义：＜A,W＞偏序集，B公

(a).beB,对每个x£B都有xSb,则称b是B的最大元。

(b).beB,对每个x£B都有bgx,则称b是B的最小元。

加上例中，B没有最大元最小元。

例：〈夕({a,b,c}),=

夕({a,b,c})={①，{a}

{b,c},{a,b,c}}

Hasse图：

3-12序关系

Bl={①，{a}}最大元：{a}。最小元：①o

B2={{a},{b}}无最大最小元。

B3={{a},{b},{ab}}最大元:{a,b}。无最小元。

，最大（小）元写极大（小?）元不同。

（1）.是最大（小）元=＞极大（小）元，反之未必。

（2）.极大（小）元不是唯一的，最大（小）元是唯一的。

极大元是B中没有元素比它小，可以是所有元素比它小，也可以是

不存在元素比它小，不好比较也成立

3-12序关系

证：反证，若a,b都是B的最大元，由定义a是B的最大元

b<a,

又b是B的最大元・・・a0b而W反对称的

，a=b矛盾。

・・・最大元唯一，最小元类似可证

8.上界，下界

定义：偏序集<A,S>,B0

（a）.若a£A,对x£B者B有xga,则称a为B的上界。

（b）.若a£A,对x£B者B有aSx,则称a为B的下界。

最大（小）元与上（下）界有区别的

最大元b£B,而上（下）界a£A即可。最大（小）元是上（下）界,

反之未必。

例：<A,<>Hasse图为：

3-12序关系

Bl={2,1?f,（1,6,九8}上界：h,i,j,

ko下界：无。

B2={h,i,j,k}上界：无，下界：a,

b,c,d,e,f,g

B3={h,i,f,g}上界：k,下界：a（不

是bcde）o

3-12序关系

例：<A,<>

B

={2,3,6}

上

界：

上6,12,24,36

确

B界：6

={6,12}

最大上界：12

最小下界：6

又如上例中取B={h,iJ,k}则无最大下界

/.LUB,GLB未必存在

3-12序关系

10.良序集定义：＜A,0＞偏序集，若对A的每个非空子集都有最

小兀，则称vA,＜＞为良序集。

全序、出一届

偏序集

良序F

良序集全序集

良序集全序集

A为有限时成立

3-12序关系

(1).定理：每个良序集必是全序集合

(2).定理：A有限时，全序一良序，每个有限的全序集合，一定是

良序集。A无限时未必如vA=(0,1),全序集，但

(0,1)无最小元，不是良序集，对有限集而言，偏序集

中，全序良序

(1).每个良序集一定是全序集。

证：设＜A,W＞是一良序集，要证＜A,S＞是全序集，即证A是一个

链

x,y£A,x,y有关系

而｛x,y｝0,而＜A,S＞良序

工｛x,y|必有最小元，不是x就是y

**.x＜y或yWx必有一个成立

・・・A中任两元都有关系，即＜A,0＞全序。

3-12序关系

⑵.每个有限的全序集一定是良序集合

证：设A={a—az〉......}是全序集,

要证＜A,w＞是良序集（任一非子集有最小元）

若不然，则①，BS,而B中无最小元

而B是一有限集，必有最小元，矛盾。

*,•＜A,＜＞是良序。

3-11相容关系

前面两次课我们介绍了等价关系，偏序关系，这里两种非常重要

的关系，今天我们来学习相容关系。（另一种重要关系）。

定义：R是A上的关系，若R是自反的，对称的，则称R是相

容关系。

对于等价关系来说，条件比它强，因而等价关系一定是相容

关系，反之未必。

例如:A={2166,243,375,648,455,9}

R={<x,y>|x,y£A且x布y有相同伍数字}

则R是自反的，对称的

JR是相容关系记作〜

3-11相容关系

MR

是对称的，主对角线元素为1,由于儿鼠对称，因而只要

知道下三角形元素就可知上三角形元素。而对角线为1，可

省略

为

X1

简2

O1

化X

3±

的X11O

4±

梯

Xo111

5±

形

XoOOO

北6

兀

xl

3-11相容关系

2.前面我们介绍了由等价关系可产生等价类，由序关系可有链，

使链中所有元素有序关系，与之类似。

定义：R是A上的相容关系，C=A,若Vx,y£C,都有xRy,

则称C为相容关系R产生的相容类或相容类。

如上例中:{xl,x2},{xl,x4},{x2,x3}等

{xl,x2,x4},{x2,x3,x5},{x2,x4,x5}等

{x6}均是相容类

有些相容类，如{xl,x2}可以加入x4,仍是相容类，但有些如{xl,

x2,x4}不能再加入任何其它元素构成相容类，这种相容类均为最

大相容类

3-11相容关系

定义：R是A上的相容关系，C三A,C是由R产生的相容类，

若C不能真包含在任何由R产生的相容类中，称C为最大相容类

记作CR

如何找？从相容关系图中，最大完全多边形的顶点构

成的集合，即为最大相容类。

完全多边形：每个顶点与其余顶点连接的多边形。

如：…G

孤立点，不是完全多边形的两个结点的连线，也是最大相容类

不是唯一的

CR

3-11相容关系

例如：相容关系图为:

a3

佰7}

{a4,a5}9{a35a4,a6}?

{al,a2,a4,a6}

另外，日常生活中也有相容类的例子:

例：A={a,b,c,d}四个人

a:爱好游泳，下棋，跳舞b:爱好跳舞，游泳

c:爱好跳舞，打球d:爱好下棋，游泳

3-11相容关系

R：具有共同爱好的序偶，则R是相容关系。

则相容关系为：

a___/b

LXJ最大相容类为：{a,b,c},{a,b,d}

dc

对于有限集，由任一相容类可扩充为好，有如下定理：

4.定理：R是有限集A上的相容关系，C是一相容类，那么必

存在一最大相容类满足（只须将c添加元素使cu{a}

成为相容类，依次类推，有限步必终止）z

*注意：CU{。}成为相容类：即见.与c中所有元素有关系,

而为瀛大相容类

即A—。井任一元素不能与g所有元素有关系R,

3-11相容关系

由于Va£A,<a,a>^R｛a｝是一相容类，因而有｛a｝必是某一

的子集。a£A，v有分隹盖住a

推论：所有最大相容类的集合一定覆盖A,将这一覆盖称为完全

覆盖。

定义：R是A上的相容关系，其最大相容类的集合称为A的完全

覆盖，

记作G(A).

有如下关系：

3-11相容关系

定理：集合A上的相容关系R与完全覆盖。火（/）存在一一对应。

（双射）

A上的相容关系。次（㈤是唯一的。（最大

相容类的集合）再证

力上的覆盖{4,W

定理：给定A的覆盖…，4},由它确定的关系R是相

容关系。

3-11相容关系

证：HU4U…U4=N

R自反十生:VJVWEl"x巨A

vx>巨N.xN.uR.

V—X>w尺

又寸杨生：VJV9y巨/>vy>巨7?,

贝Ijm/z,vx>y>三4x4

x—w4

1.vy,X>wN为XN为二R

.二人是相容关系o

3-11相容关系

P139

(4).C={A1，A2，...An}为A的覆盖,

C是相容关系，何时为等价关系？

^=(4x4)

传递性即可

若vx,y>£Rvy,z>£R

则

3-11相容关系

(羽»eA,x4-。/)eAjxAj

(x,2)eAjxAj9未必GR

y£4nAj

i=/或，w/但4Pl//=。

若%wn//=°

就不可能有这种情况

・・.当此覆盖是A的划分时，R为等价关系。

3-11相容关系

(3).若S是自反的，则S・S=S,其逆为真吗？

证：首先由(2)S传递，则(S.S)1S

要证S屋(S・S)

用自反性，V<x,y>GS,而<x,x>£S

所以<x,x>•<x,y>=<x,y>GS*S

所以<x,y>GS・SSO(S.S)从而S=(S・S)

其逆不真如：S={<1,1>}X={1,2,3}.

习题有关

考试情况：对基本概念重视不够，掌握

基本方法，理论。

(A-B)-C=(A-C)-(B-C)

RA(P-Q)A(Q-R)一P(X)

VR^JT,

Q—R为T时：Q可为F—P可为F

P-Q为T

P-Q的合取式：nPVQ

析取式：-1PVQ

主合取式：-1PVQ

主析取式：(P/\Q)V(qPAQ)

V(-]PA-]Q)

习题有关

最大元：b是B的最大元b£B,Vx£Bx<b

极大元：b是B的极大元beB,且B中没有任何元素x,满足

x?b,且bSxo

F(x,y)=X+Y不能直接用x+y表示，不符合项的定义。

特别地：

若M三工

则x的象：

f(^)={yI(3x)(x仁X人/(x)=y)}

习题有关

P127(8).7?*=

贝【」(&)(△+)+=R+

衣+=t(R),gp%—)=t(R)

由，(区)传递性可得

___]_51c

S)衣•衣=R+=R-R

习题有关

证：R•t〃(R)=R•t(R)

=K・«(K)U/、)

=R-t(R)UR-Ix

=R^t(R)\jR

OO

=(K・|jRjUK

i=\

=(火2口火3口...)口太

OO

=\JRJ=t(R)=R+

7=1

习题有关

另一类似:

注意：，（衣衣2

）z7?uu・.・u7r

对X个数有限n时才对！

k

i=l

n

可推之为：|JR=«火）

i=\

习题有关

***

（c）（火）=R

于尸（于尸（衣））

=自反

=E5（Ryy

=t（tyQJRy）传递

=看尸（衣）

4-1函数的概念

从这节课开始，我们介绍第四章函数，在高等数学中，我们

介绍过函数。它是定义在实数集上的，这里我们将函数概念扩充

为一种特殊的关系，首先4-1函数的概念。

1.函数在离散数学中又是怎样定义的呢？

定义：X,Y是两个集合，而f是X到Y的一个关系，如果满足：1)

对每一个x£X,都有y£Y,使得〈x,y〉ef；2)对每一个

xex,仅有唯一的y£Y,使得〈X,y〉ef,则称f是X到Y的函

数或映射。记作：f：XfY或x/＞丫

x称为自变量，y称为在f作用下x的象，记作:x,y〉£f,或

y=f(x)

f(X)={f(x)|xex},Y为的勺象集

例X={“X2,X39工4，”5}

Y二

4-1函数的概念

/={<x1,yl>,<x2,y3>,<x3,y3>,<%，匕>,<%,%>}

则关系f是一个函数，关系图为：

Vx‘.，有唯^匕^Y.<xi.yj.>ef

何以是多对一，一对一，但不能是一对多。

4-1函数的概念

注：1函数不同于关系，X是每一个点都有象，domQX一定义域

而不是X的某一个子集。

27(%)-y^Y.Rf=ranf={f(x)}---f的值域,象集

称为的共域。

RJf—^Y7.Yf

例：f={<Xx,X2>Xl?X2GN,X\+x?v10}判断关系f是否为函数?

定义域NN,V2,X2不！/不是函数。

2

/={<九匕>1乂，匕㊂凡匕=%}

>0时，有2个匕，所以也不是。

f={<Xix2>|x1?x2^N,X2为小于巧的素数个数},是函数。

4-1函数的概念

2下面给出两数相等的定义。

定义：f：A-B,g:CfD若人=。B=D时，且对每个

xA=C

均有f(x)=g(x),则称f和g相等,记作f=g。

因而对两个函数相等，必须前域，值域都分别相同，

”作用结果相同。

3