离散数学-第四章-关系.ppt

4.1二元关系4.2关系的性质4.3复合关系与逆关系4.4关系的闭包4.5等价关系4.6序关系例：A={1,2},则

UA={1,1,1,2,2,1,2,2}

IA={1,1,2,2}例：小于等于关系L,整除关系D,包含关系R定义：L={x,y|x,y∈A∧x≤y},A?R，R为实数集合；D={x,y|x,y∈B∧x整除y},B?Z*,Z*为非0整数集；R={x,y|x,y∈A∧x?y},A是集合族.（类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.）例：A={1,2,3},B={a,b},则

L={1,1,1,2,1,3,2,2,2,3,3,3}；

D={1,1,1,2,1,3,2,2,3,3}；P(B)={?,{a},{b},{a,b}},P(B)上的包含关系是R={?,?,?,{a},?,{b},?,{a,b},{a},{a},{a},{a,b},{b},{b},{b},{a,b},{a,b},{a,b}}

例：R={1,2,1,3,2,4,4,3},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}4.1二元关系4.2关系的性质4.3复合关系与逆关系4.4关系的闭包4.5等价关系4.6序关系例：A={1,2,3},R1,R2,R3是A上的关系,其中

R1＝{1,1,2,2}

R2＝{1,1,2,2,3,3,1,2}

R3＝{1,3}例：设A＝{1,2,3},R1,R2,R3和R4都是A上的关系,其中

R1＝{1,1,2,2}，R2＝{1,1,1,2,2,1}

R3＝{1,2,1,3}，R4＝{1,2,2,1,1,3}例：设A＝{1,2,3},R1,R2,R3是A上的关系,其中

R1＝{1,1,2,2}

R2＝{1,2,2,3}

R3＝{1,3}

例：判断以下关系的性质（A为非空集合）1.A上的全域关系；2.A上的恒等关系；3.A上的空关系；4.R={x,y|x,y∈Z∧(x-y)/2∈Z}例：设X={1，2，3}，试构造R1、R2，使得R1具有对称性和传递性而不具有自反性，R2具有自反性和对称性而不具有传递性。关系性质的判别4.1二元关系4.2关系的性质4.3复合关系与逆关系4.4关系的闭包4.5等价关系4.6序关系定理2：设R?A×B，S?B×C，T?C×D,则(R°S)°T=R°(S°T).证明见书P72。定理3：设R?A×B，S、T?B×C，W?C×D,则1)R°(S∪T)=(R°S)∪(R°T)；2)R°(S∩T)?(R°S)∩(R°T)；3)(S∪T)°W=(S°W)∪(T°W)；4)(S∩T)°W?(S°W)∩(T°W)。证明见书P72。例：设R?A2，试证R传递?RoR?R。例：设R?A2，试证R传递?RoR?R。证：若R传递，设任意a,c?RoR，必存在b?A，使得a,b?R且b,c?R，所以a,c?R。若RoR?R，假设任意a、b、c?A，若有a,b?R且b,c?R，则有a,c?RoR，得a,c?R，所以R传递。由上可知，R传递?RoR?R。3.幂运算设R为A上的关系,n为自然数,则R的n次幂定义为：(1)R0={x,x|x∈A}=IA；(2)Rn+1=Rn°R.注意：(1)对于A上的任何关系R1和R2都有R10=R20=IA;(2)对于A上的任何关系R都有R1=R.定理：设R是A上的关系，m,n∈N,则(1)Rm°Rn=Rm+n(2)(Rm)n=Rmn证：用归纳法

(1)对于任意给定的m∈N,施归纳于n.

若n=0,则有

Rm°R0=Rm°IA=Rm=Rm+0假设Rm°Rn=Rm+n,则有

Rm°Rn+1=Rm°(Rn°R)=(Rm°Rn)°R=Rm+n+1,所以对一切m,n∈N有Rm°Rn=Rm+n.