补集( complementary set) 如果AcB,则BcA A∪A=U A∩A=Φ B=A分→A∪B=U&A∩B=Φ A∩B=A∪B A∪B=A∩B 2021/2/20
2021/2/20 21 补集(complementary set) A A = B = A A B =U & A B = A B = A B A B = A B B A A A =U 如果AB，则 。 。 。 。 。
12关系 二元关系 递归定义与归纳证明 关系的闭包 2021/2/20 22
2021/2/20 22 1.2 关系 • 二元关系 • 递归定义与归纳证明 • 关系的闭包
121二元关系( binary relation) 二元关系 任意的RcA×B,R是A到B的二元关系。 (a,b)∈R,也可表示为:aRb A称为定义域( domain),B称为值域( range) 当A=B时,则称R是A上的二元关系 二元关系的性质 自反( Reflexive)性、反自反( irreflexive)性、对称 ( symmetric)性、反对称( asymmetric性、传递 ( transitive)性 2021/2/20
2021/2/20 23 1.2.1 二元关系(binary relation) • 二元关系 – 任意的RA× B，R是A到B的二元关系。 – (a，b) ∈R，也可表示为：aRb。 – A称为定义域(domain)，B称为值域(range)。 – 当A=B时，则称R是A上的二元关系。 • 二元关系的性质 – 自反(reflexive)性、反自反(irreflexive)性、对称 (symmetric)性、反对称(asymmetric)性、传递 (transitive)性
121二元关系( binary relation) 三歧性 自反性、对称性、传递性。 等价关系( equivalence relation 具有三歧性的二元关系称为等价关系。 2021/2/20 24
2021/2/20 24 1.2.1 二元关系(binary relation) • 三歧性 – 自反性、对称性、传递性。 • 等价关系(equivalence relation) – 具有三歧性的二元关系称为等价关系
121二元关系( binary relation) 等价类 equivalence class S的满足如下要求的划分 称 n 为S关于R的等价划分,S称为等价类。 (1)S=S1US,US2U…∪Sn∪…; (2)如果,则S∩S=Φ; (3)对任意的i,S中的任意两个元素a、b,aRb恒成 立 (4)对任意的j,i,S中的任意元素a和S中的任 意元素b,aRb恒不成立 2021/2/20 25
2021/2/20 25 1.2.1 二元关系(binary relation) • 等价类 (equivalence class) S的满足如下要求的划分：S1、S2、S3、…、Sn…称 为S关于R的等价划分，Si称为等价类。 ⑴ S= S1∪S2∪S3∪…∪Sn∪…； ⑵ 如果i≠j，则Si∩Sj =Φ； ⑶ 对任意的i，Si中的任意两个元素a、b，aRb恒成 立； ⑷ 对任意的i，j，i≠j，Si中的任意元素a和Sj中的任 意元素b，aRb恒不成立