离散数学关系的概念、性质及运算

《离散数学关系的概念、性质及运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6节关系的概念、性质及合成主要内容：关系的概念关系的性质关系的合成1定义1设A,B是两个集合。AB的任一子集R称为从A到B的一个二元关系。如果A=B，则称R为A上的一个二元关系。1关系的概念如果(a,b)R，则称a与b符合关系R，并记为aRb;如果(a,b)R，则称a与b不符合关系R，并记为aRb。2定义2设RAB，集合{xxA且yB使得(x,y)R}称为R的定义域，并记为dom(R)。例如：设A={1,2,3,4}，B={a,b,c,d,e}，{(1,a),(2,b),(2,c),(3,c)}是一个二元关系。{1,2,3}是定义域，{a,b,c}

2、是值域一般情况下：Adom(R);Bran(R)。集合{yyB且xA使得(x,y)R}称为R的值域，并记为ran(R)。dom(R)A;ran(R)B。定义域与值域3例如:A={1,2}，B={a,b,c}。映射是特殊的二元关系。令f:AB，f(1)=a，f(2)=b，则映射f就对应着AB的子集{(1,a)，(2,b)}关系与映射问题1：映射与二元关系有什么联系？（前提：映射和二元关系都是从A到B的）4定义1’设A,B是两个集合，一个从AB到{是,否}的映射R，称为从A到B的一个二元关系，或A与B间的一个二元关系。(a,b)AB，如果(a,

3、b)在R下的象为“是”，则a与b符合关系R，记为aRb；若A=B，则称R为A上的二元关系。如果(a,b)在R下的象为“否”，则说a与b没有或不符合关系R，并记为aRb。关系与映射5定义1’’一个从A到B的多值部分映射R称为从A到B的一个二元关系。关系与映射设A,B是两个集合，一个从A到2B的映射R称为从A到B的一个多值部分映射。如果aA，R(a)=，则称R在a无定义；而如果R(a)，则bR(a)，b称a在R下的一个象或值。6例如：设A={1,2}，B={a,b,c}，AB={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}。AB有

4、6个元素，从而有26个子集，因此从A到B就有26个关系。答案：2mn问题2：A到B的关系的个数设

5、A

6、=m，

7、B

8、=n，则A到B上有多少个二元关系？关系的个数7集合{(a,a)aA}称为A上的恒等关系或相等关系，并记为IA。空集也是AB的一个子集。空集叫做A到B的空关系。AB是AB的一个子集，按定义AB也是从A到B的一个二元关系。AB叫做A到B的全关系。四个特殊二元关系设R是A到B的二元关系，集合{(y,x)(x,y)R}称为R的逆关系，简称R的逆，记为R-1。显然：R-1是B到A的二元关系。8例1：整除关系例2：整数集Z上的模n同余关系设Z为整数

9、集，Z上的整除关系记为。m,nZ,mn当且仅当m能除尽n。设n为任一给定的自然数。对任意两个整数m,k，如果m和k被n除，所得余数相等，则称m与k为模n同余，并记为：mk(modn)当n=3时，25(mod3)，57(mod3)。关系实例例3：设X是一个集合，集合的包含于“”是2X上的二元关系。9定义3设A1,A2,...,An是n个集合，一个A1A2...An的子集R称为A1,A2,...,An间的n元关系。每个Ai称为R的一个域。例4：设1、A为某单位职工“姓名”的集合；2、B为“性别”之集合，B={男，女}；3、C为职工年龄集合C={1,2,

10、...,100};4、D表示“文化程度”；D={小学,初中,高中,大学,硕士,博士}；5、E是“婚否”集合，E={是，否}；6、F表示月工资，F=[0,20000]。二元关系到n元关系的推广10姓名A性别B年龄C文化程度D婚否E工资F张三男28大学是400李四男50硕士是1400李晓芬女18高中否300这其实就是关系型数据库的一个数据表。n元关系是关系数据模型的核心，而关系数据模型是关系型数据库的基础。二元关系到n元关系的推广112关系的性质定义1X上的二元关系R称为自反的，如果xX,xRx。在这个定义中，要求X的每个元素x，都有xRx，即(x,x)R。设IX是X

11、上的恒等关系，即：IX={(x,x)xX}。显然：R是自反的，当且仅当IXR。12例1：IX是X上的自反关系，但IX的任一真子集RIX不是X上的自反关系。例2：实数集上的“小于或等于”关系“≤”是不是自反的？小于关系“<”是不是自反的？例3：令X={a,b,c}，R={(a,b),(a,a),(b,c),(c,c)}，则R是不是自反的?关系的性质：自反13定义2X上的二元关系R称为反自反的，如果xX，都有(x,x)R。例4：实数集R上的“大于”关系>是反自反的。注意：①反自反的二元关系必不是自反的；②但不是自反的二元关系，却