《离散数学 第2版 教学课件 ppt 作者 王元元 离散第27讲 关系的特性》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第27讲 关系的特性（31页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：王元元 单位：计算机理论教研室,理工大学指挥自动化学院,PowerPoint Template_Sub,二元关系,等价关系,序关系,关系的特性,离散数学第27讲,Page 164 to 167,-4-,第27讲 关系的特性,引言,不研究具体某一个关系，而是研究某一类关系，对关系分类 分类依据关系的特性 关系有哪些基本特性？ 自反性、反自反性 对称性、反对称性 传递性,-5-,第27讲 关系的特性,定义：设R是集合A上的关系，如果对任意xA，均有xRx，则称R是自反的(reflexive)。 R自反当且仅当 x(xAxRx),10.1.3 关系的特性,自反性（ref
2、lexivity）,集合I+ 为正整数集，I+上的整除关系,集合A=1, 2, 3，A上的空关系 相等关系 全关系,空集上的空关系,示例判别,集合A=1, 2, 3，(A)上的包含关系,三角形的相似关系 人类的父子关系,集合I 为整数集，I上的整除关系 I上的大于关系,-6-,第27讲 关系的特性,A = 1, 2, 3, 4 R = , , , , ,1,2,3,4,10.1.3 关系的特性,自反性与关系图,-7-,第27讲 关系的特性,A = 1, 2, 3, 4 R = , , , , , ,1,2,3,4,10.1.3 关系的特性,自反性与关系图,-8-,第27讲 关系的特性,定义：设
3、R是集合A上的关系，如果对任意xA， xRx均不成立，则称R是反自反的(irreflexive)。 R反自反当且仅当 x(xAxRx),10.1.3 关系的特性,反自反性（irreflexivity）,集合I+ 为正整数集，I+上的整除关系,集合A=1, 2, 3，A上的空关系 相等关系 全关系,空集上的空关系,示例判别,集合A=1, 2, 3，(A)上的包含关系,人类的父子关系,集合I 为整数集，I上的整除关系 I上的大于关系,-9-,第27讲 关系的特性,A = 1, 2, 3, 4 R = ,1,2,3,4,10.1.3 关系的特性,反自反性与关系图, , , , ,-10-,第27讲
4、关系的特性,自反性与反自反性的关系,自反和反自反并非互为否定 有些关系既是自反的，也是反自反的 上的空关系 任何集合上的空关系都是反自反的 非空集合上的空关系不是自反的。 有些关系既不自反也不反自反 整数集合上的整除关系 A=1, 2, 3, A上关系R=, ,-11-,第27讲 关系的特性,定义：设R是集合A上的关系，如果对任意x, yA，均有xRy蕴涵yRx，则称R是对称的（symmetric） R对称当且仅当 xy(x,yAxRy yRx),10.1.3 关系的特性,对称性（symmetry）,集合I+ 为正整数集，I+上的整除关系,集合A=1, 2, 3，A上的全关系 相等关系 空关系
5、,集合A=1, 2, 3， A上的关系R= , ,示例判别,集合A=1, 2, 3，(A)上的包含关系,三角形的相似关系 人类的父子关系,集合I 为整数集，I上的小于等于关系 不等于关系,-12-,第27讲 关系的特性,A = 1, 2, 3, 4 R = , , , , ,1,2,3,4,10.1.3 关系的特性,对称性与关系图,-13-,第27讲 关系的特性,定义：设R是集合A上的关系，如果对任意x, yA，均有xRy且yRx蕴涵x=y，则称R是反对称的（antisymmetric） R反对称当且仅当 xy(x,yAxRyyRxx=y),10.1.3 关系的特性,反对称性（antisymm
6、etry）,集合I+ 为正整数集，I+上的整除关系,集合A=1, 2, 3，A上的全关系 相等关系 空关系,集合A=1, 2, 3， A上的关系R= , ,示例判别,集合A=1, 2, 3，(A)上的包含关系,三角形的相似关系 人的父子关系,集合I 为整数集，I上的整除关系 小于等于关系 小于关系,-14-,第27讲 关系的特性,A = 1, 2, 3, 4 R = , , , ,1,2,3,4,10.1.3 关系的特性,反对称性与关系图,-15-,第27讲 关系的特性,对称性与反对称性的关系,对称和反对称也并非互为否定 有些关系既是对称的，也是反对称的 任意集合上的相等关系、空关系 A=1,
7、 2, 3, A上关系R=, 有些关系既不对称也不反对称 整数集合上的整除关系 A=1, 2, 3, A上关系R=, , , ,-16-,第27讲 关系的特性,反对称性似应定义为 xy(x,yAxRy yRx) 但注意：当x=y时上述定义是有问题的 x (xAxRxxRx) 可以修改为： xy(x,yAxRyxyyRx) 逻辑上等价于 xy(x,yAxRyyRxx=y),关于反对称性定义的思考,-17-,第27讲 关系的特性,定义：设R是集合A上的关系，如果对任意x, y, zA，均有xRy且yRz蕴涵xRz，则称R是传递的（transitive ） R传递当且仅当 xyz(x,y,zAxRy
8、yRzxRz),10.1.3 关系的特性,传递性（ transitivity ）,集合I+ 为正整数集，I+上的整除关系,集合A=1, 2, 3，A上的全关系 相等关系 空关系,集合A=1, 2, 3， A上的关系R= S= , ,示例判别,集合A=1, 2, 3，(A)上的包含关系 元素的隶属关系,三角形的相似关系 国家之间的外交关系 人的父子关系,集合I 为整数集，I上的整除关系 小于等于关系 小于关系,-18-,第27讲 关系的特性,A = 1, 2, 3, 4 R = , , ,1,2,3,4,10.1.3 关系的特性,传递性与关系图,-19-,第27讲 关系的特性,关系的特性与关系图
9、、关系矩阵,关系的五大特性与关系图、关系矩阵,-20-,第27讲 关系的特性,关系的五大特性,同时兼具5个特性的关系？ 全关系？相等关系？ 空关系？ 上的空关系？ 同时不具有5个特性的关系？,1,2,3,4,-21-,第27讲 关系的特性,关系特性成立的充要条件,设R为集合A上的关系 (1) R自反当且仅当 (2) R反自反当且仅当 (3) R对称当且仅当 (4) R反对称当且仅当 (5) R传递当且仅当,EA R,EAR = ,R = R,RR EA,R2 R,-22-,第27讲 关系的特性,关系特性成立的充要条件,R对称当且仅当R = R,再证必要性 已知R对称，欲证R = R 对任意x,
10、y，设R，那么 R对称 R，即R R R 同理可证，R R 综上，R = R,证：先证充分性 已知R = R，欲证R对称 设R，那么 R = R R，即R R对称,-23-,第27讲 关系的特性,关系特性成立的充要条件,再证必要性。已知R反对称，欲证RR EA 对任意的x,y,设 RR ，那么 R，因而 R。又因为 R，且R反对称 x=y，即EA,证：先证充分性。已知RR EA ，欲证R反对称。 设 R， R，则由 R知 R 所以 RR RR EA EA，即 x=y R反对称,R反对称当且仅当RR EA,-24-,第27讲 关系的特性,关系特性成立的充要条件,R传递当且仅当R2 R,再证必要性
11、。已知R传递，欲证R2 R。 对任意x,y，设R2，根据合成运算的定义，必存在z使得R, R R传递 R，即R2 R,证：先证充分性。已知R2 R ，欲证R传递。 设R， R，那么R2 R2 R R R传递,-25-,第27讲 关系的特性,五大特性对关系运算的封闭性,定义：已知某些关系同时具有某一性质，若经过某种关系运算后所得结果仍然具有这一性质，则称该性质对这一运算封闭 五大特性：自反、反自反、对称、反对称、传递 六大运算：交、并、差、补、逆、合成 哪些特性对哪些运算封闭？,-26-,第27讲 关系的特性,五大特性对关系运算的封闭性,任意集合A，A上关系R，S,1、R、S均自反， RS 是否
12、自反？,R S 有自反性,R=R，S= S，(RS) = RS = RS,RR EA, SS EA, (RS)(RS)=(RS)(RS) EA,R2 R，S2 S，(RS)2 R2RSSRS2 RS,对交运算的封闭性,EA R，EA S，EA RS,2、R、S均反自反， RS 是否反自反？,EAR= ，EAS= ，EA(RS) = ,3、R、S均对称， RS 是否对称？,RS 有反自反性,RS 有对称性,4、R、S均反对称， RS 是否反对称？,RS 有反对称性,5、R、S均传递， RS 是否传递？,R S 有传递性,五大特性对交运算均封闭,-27-,第27讲 关系的特性,五大特性对关系运算的
13、封闭性,对并运算的封闭性,设R,S对称。对x,y，设RS，那么xRy或者xSy，由R、S对称可知yRx或者ySx，从而RS。所以RS对称。,例如R=，S= R、S均反对称、传递， 而RS=, 既不反对称，也不传递。,自反性、反自反性、对称性对并运算封闭,EA R，EA S，EA RS,EAR= ，EAS= ，EA(R S) = ,反对称性、传递性对并运算不封闭,-28-,第27讲 关系的特性,五大特性对关系运算的封闭性,对差运算的封闭性,设R,S对称。对任意x,y，设RS，那么xRy且xSy，由R、S对称可知yRx且ySx，从而RS。所以RS对称。,R=, , ，S=，R、S均传递， RS=,
14、 不传递。,自反性对差运算不封闭,反自反性、对称性、反对称性对差运算封闭,传递性对差运算不封闭,-29-,第27讲 关系的特性,五大特性对关系运算的封闭性,对补运算的封闭性,只有对称性对补运算封闭,R=R，R = R = R,A=1, 2, 3 R = , , ，R反对称、传递 R =, , , , , 既不反对称也不传递。,对求逆运算的封闭性,五大特性对求逆运算均封闭,R2 R，R R = (RR) R,传递性对求逆运算封闭,-30-,第27讲 关系的特性,五大特性对关系运算的封闭性,反自反性对合成运算不封闭 R=，S=，R、S均反自反，而RS=不反自反。 对称性对合成运算不封闭 R=, ，S=, ，R、S均对称，而RS=不对称。,反对称、传递性对合成运算也不封闭。 R=, ，S=, ，R、S均反对称、传递 RS=, 既不
