文档介绍:1. 自反性与反自反性
定义:设R是A上的关系,若对于每一个a∈A,都有<a,a>∈R,则称关系R是A上的自反关系,或称R具有自反性。即:R在A上具有自反性(a)(aAaRa)
例:实数集R上,“”,“”都是自反关系。
特点:
具有自反性的关系矩阵主对角线元素全是1;
关系图上每个结点都有自回路。
思考:
具有自反性的关系与恒等关系有何区别和联系?
关系的性质
1
定义:设R是A上的关系,若对于每一个a∈A,都有<a,a>R,则称关系R是A上的反自反关系,或称R具有反自反性。即: R在A上具有反自反性(a)(aA<a,a>R)
例:实数集R上,“<”和“>”是反自反的,∵aR,有a<a不成立,a>a不成立。
特点:
具有反自反性的关系矩阵主对角线元素全是0;
关系图上每个结点都没有自回路。
2
例:设集合A={a,b,c}上有下列关系:R1={<a,a>,<b,b>,<c,c>,<a,b>,<c,a>}R2={<a,b>,<b,c>,<c,a>}R3={<a,a>,<b,c>} (4)A上的空关系
分析它们的自反性和反自反性,并画关系图和关系矩阵。
解:R1是自反关系,关系图和关系矩阵略
R2是反自反关系,关系图和关系矩阵略
R3中缺<b,b>,<c,c>,故不是自反关系,又因R3中有<a,a>,故R3又不是反自反关系。关系图和关系矩阵如下:
a
b
c
1 0 0
0 0 1
0 0 0
MR3=
A上的空关系是反自反关系,关系图和关系矩阵略
3
注意:
如果R不是自反关系,则R未必一定是反自反关系,一个关系可能既不是自反关系,也不是反自反关系;
一个非空集合上的关系不能既是自反关系,又是反自反关系。
结论:
R是A上的关系,则:
1) R是自反关系的充要条件是IAA;
2) R是反自反关系的充要条件是R∩IA=Ф。
4
2. 对称性与反对称性
定义:设R是A上的关系,若对于任意a,b∈A,每当<a,b>∈R,则必有<b,a>∈R,则称R为A上的对称关系,或称R具有对称性。即:R在A上具有对称性 (a)(b)(aAbAaRbbRa)
例:实数集R上的“=”,三角形集合上的相似关系,朋友关系,都是对称的。
特点:
具有对称性的关系矩阵关于主对角线对称(rij=rji);
关系图的特点是任何两个不同的结点之间,或者是一来一回两条弧,或者是没有弧。是否有自回路,对对称性没有影响。
5
定义:设R是A上的关系,若对于任意a,b∈A,每当<a,b>∈R且<b,a>∈R,则必有a=b,则称R为A上的反对称关系,或称R具有反对称性。即:R具有反对称性 (a)(b)(aAbAaRbbRaa=b)
例:实数集R上的“≤”、“≥”,集合上的“”关系,都是反对称的。
特点:
具有反对称性的关系矩阵如果在非对角元上rij=1,则在其对称位置上,rji=0,即rij和rji(i≠j)这两个数至多一个是1,但允许两个均为0;
关系图上任何两个不同的结点之间,至多有一条弧,但允许没有弧。
6
说明:
1) 反对称性的等价说法:
a,b∈A,如a≠b且<a,b>∈R,则必有<b,a>R即两个不同点结点间不允许有两条弧;
2) 该定义的否命题说法并不成立,如“a≠b且<a,b>R,则<b,a>∈R”并不成立,即反对称关系的关系图允许两个不同点间没有弧。
7
例3:A={a,b,c},考察以下几个关系的对称性和反对称性:
R1={<a,b>,<b,a>}
R2={<a,b>,<b,c>,<c,b>}
R3={<a,a>,<b,b>}
R4={<a,a>,<b,b>,<c,c>}
R5={<a,b>,<b,c>}
R6={ }
注:
有些关系既不是对称的,也不是反对称的;
有些关系既是对称的,也是反对称的;
空关系、恒等关系既是对称的,也是反对称的;
全关系EA不是反对称的。
8
3. 传递性
定义:设R是A上的关系,若对于任意a,b,c∈A,每当<a,b>∈R且<b,c>∈R,就有<a,c>∈R,则称R为A上的传递关系,或称R具有传递性。即:R具有传递性(a)(b)(c)(aAbAcAaRbbRcaRc)
例:实数集R上的“>”、“<”、“≤”、“≥”,集合上的“”关系,都是传递的。
特点:
如R是传递关系,如果结点a能通过有向弧组成的有向路通向结点x,(该有向路包含两条或两条以上的弧)则a必须有有向弧直接指向x,否则R就不是传递的;
传递关系的关系矩阵的特点不是很容易看出,后面会讲到。
9
例4:A={a,b,c},考察下列关系的传递性
R1={<