• 集合的概念和性质,以及集合之间的运算
• 集合{所有课程全体}和集合{所有教室}这两个集合 之间就存在着某种联系。
• 例：A={a,b,c}为学生集合，B={x,y,z,w}为课程集 合，则笛卡儿积A×B就是学生与课程所组成的有序 对全体。
• A×B={(a,x),(a,y),(a,z),(a,w),(b,x),(b,y),(b,z),
1 mij 0
(ai,bj)R (ai,bj)R
当A=B时,A上的二元关系R可以用方阵来表示。
2020/9/28
• 例 : A={1,2,3,4} 上 模 3 同 余 关 系 R={(1,1),(2,2),(3,3), (4,4),(1,4),(4,1)}, 其 关系矩阵为
1234
11 0 0 1
(b,w),(c,x),(c,y),(c,z),(c,w)} • 若(a,x)表示学生a选修课程x，则当a,b,c三个学生选
定课程，其情况是： • (a,y),(a,w),(b,x),(b,y),(b,w)，而c什么课也没选，
• R={(a,y),(a,w),(b,x),(b,y),(b,w)} • 反映了学生与课程的联系。 • RA×B,即R是A×B 的子集。 • 集合A到集合B的关系。
并且Dom RA,Ran RB。
• 例 : A={1,3,5,7},B={0,2,4,6}, 定 义 关 系 R:(a,b)R当且仅当a<b
• 关系还可以用表格表示
• R={(1,2),(1,4),(1,6),(3,4), (3,6),(5,6)}
2020/9/28
• A={1,2,3,4},定义A上二元关系:(a,b)R当 且仅当(a-b)/3为整数。称为模3同余关系 。
bRa , 则称R是对称的。
• A={1,2,3,4} • S1={(1,2),(2,1),(1,3),(3,1)} 对称 • S2={(1,2),(2,1),(1,3)} • 因为(1,3)S2,而(3,1)S2, • 所以S2不是对称的 • S3={(1,2),(2,1),(3,3)} 对称
2020/9/28
R={(a,y),(a,w),(b,x),(b,y),(b,w)} (a,y)R,aRy. (a,x)R, aR/x
2020/9/28
• 定义 2.2:设R是从A到B的二元关系,A的 一个子集{a|存在b, 使得(a,b)R}称为R
的定义域,记为Dom R。B的一个子集{b| 存 在 a, 使 得 ( a,b)R} 称 为 R 的 值 域 , 记 为 Ran R。A称为R的前域,B称为R的陪域,
• (4)对任意a,bA,如果aRb且bRa,必有a=b,则
称R是反对称的。
• 该定义实际上表明：当ab时，若有(a,b)R, 则(b,a)R。
• 不是对称，不一定是反对称的 • 不是反对称的，也不一定是对称的。 • 可以既是对称的，又是反对称的
2020/9/28
• (5)对任意a,b,cA, 如果aRb且bRc,必有
• A={1,2,3,4} • R1={(1,1),(2,2),(3,3)} ? • R2={(1,1),(1,2),(2,2),(3,3),(4,4)} ? • 对于自反,必须是对于每个xA,都去检验
是否有xRx。
2020/9/28
• (2)反自反：如果对任意aA,有(a,a)R ,
则称R是反自反的。
2020/9/28
2020/9/28
定义 2.1:设 A 和 B 是任意两个集合,A ×B 的子集 R 称为从 A 到 B 的二元关 系。当 A=B 时,称 R 为 A 上的二元关系。 若(a,b)R,则称 a 与 b 有关系 R ,记为 aRb。若(a,b)R,则称 a 与 b 没有关系 R,记为 aR/b。若 R=,则称 R 为空关系。 若 R=A×B,则称 R 为全关系。
义 A1×A2×…×An的 子 集 R为 A1,A2,…An 的 n 元 关 系 , 当 A1=A2=…=An 时 , R 称 为 A 上 的n元关系。 2020/9/28
2.2关系的性质
• 定义2.4：设R是集合A上的二元关系。 • (1)自反：如果对任意aA,有aRa,则称R
是自反的。
• 自反集合下
2020/9/28
• A到B的关系是A×B的子集。 • 关系的表示，可以用集合的表示方法 • 对于有限集, 关系还可以用矩阵或图形来表示 • 定义 2.5：设A和B是两个有限集A={a1,a2,…,
am},B={b1,b2,…,bn}，R是从A到B的二元关系, 称m×n阶矩阵MR=(mi,j)为R的关系矩阵,其中
• R={(a,b)|(a-b)/3 为 整 数 ， a,bA}={(1,1), (2,2),(3,3), (4,4),(1,4),(4,1)}
• Dom R=Ran R=A。 • 进一步可定义整数集上的模r同余关系： • {(a,b)|(a-b)/r为整数,a、bZ,rZ+} • 定义 2.3：设A1,A2,…An是n个任意集合,定
aRc , 则称R是传递的。
• 注意：传递要求是：只要有aRb,bRc,则必 须有aRc
• 但若没有aRb,bRc ，当然也就不需要讨论 是否有aRc 。
2020/9/28
• 例：A上的非空关系R是对称的和反自反的， 则R不是传递的。
• 证明:反证法.假设R传递. • 注意，当导出(a,a)R时，千万不能说R自反。 • 因为自反的要求是：如果对任意aA,有aRa。
• 反 自 反 要 求 对 任 意 的 A 中 元 素 a， 有 (a,a)R。
2020/9/28
• 不是自反的，不一定反自反
• 不是反自反的，也不一定是自反的。
• R3={(1,2),(3,2)} 是A上的反自反关系
• 思考：非空集合A上的空关系是否自反？ 反自反？
• (3)对称：对任意a,bA ,如果aRb必有
M
R
20 30
1 0
0 1
0 0
4
1
0
0
1
2020/9/28
• 例 ： A={2,3,4},B={1,3,5,7},A 到 B 的 < 关
系
R={(2,3),(2,5),