离散数学笔记-0329

解释：文中出现的“逆”都用 ^-1 表示，但作业中需要写成 $R^{-1}$的形式

一、与二元关系有关的概念

定义域,值域, 域

对***任意集合***R, 可以定义:

• **定义域(domain) : **

  dom R = { x | ∃y (xRy) }
  

• 值域(range):

  ran R = { y | ∃x (xRy) }
  

• 域(field):

  fld R = dom R ∪ ran R
  

注释：即便R不是关系，只要R有子集是关系，那么R就有非空的定义域和值域。

逆,合成(复合)

• 逆：

  F^-1 = { <x, y> | <y,x> ∈ F } (* 为F的逆 *)
  

• 逆序合成（逆序复合）：

  F °G = { <x, y> | ∃z( <x,z> ∈G ∧ <z,y> ∈F ) }
  

限制，像

• F在A上的限制(restriction):

  F↑A = { <x,y> | <x,y> ∈F ∧ x∈A }
  

• A在F下的像(image):

  F[A] = ran(F↑A)
  F[A] = { y | ∃x(x∈A ∧ <x,y> ∈F) }
  

单根 , 单值

对于任意集合F，定义

• F是单根的 ⇔

  ∀y( y∈ranF → ∃!x( x∈domF ∧ xFy ) )		(* ∃!意思是存在唯一*)
  

• F是单值的 ⇔

  ∀x( x∈domF → ∃!y( y∈ranF ∧ xFy ) )
  

二、运算顺序

• 第一级最高, 依次降低
  • 第一级：求逆
  • 第二级：合成，限制，象运算，求定义域，值域和域运算
  • 第三级：绝对补, 幂，
  • 第四级：广义并，广义交，
  • 第五级：并，交，相对补，对称差
• 同一级: 用括号表示先后顺序,否则在式子中从左向右运算

三、运算定理汇总

定理2.3：域的恒等式和推算式

(1) dom(F∪G) = domF ∪ domG
(2) ran(F∪G) = ranF ∪ ranG
(3) dom(F∩G) ⊆ domF ∩ domG
(4) ran(F∩G) ⊆ ranF ∩ ranG
(5) domF-domG ⊆ dom(F-G)
(6) ranF-ranG ⊆ ran(F-G)

定理2.4：逆运算定理

(1) domF^-1 = ranF;
(2) ranF^-1 = domF;
(3) (F-1)^-1 ⊆ F, 
(* 当F是关系时, (F-1)^-1 = F. *)

定理2.5：合成结合律

(* 若R1、R2、R3为集合，则： *)
(R1 °R2) °R3 = R1 °(R2 °R3)

定理2.6：合成对并和交的分配律和半分配律

(* °对∪的分配律: *)
(1) R1 °(R2∪R3) = (R1 °R2)∪(R1 ° R3) 
(2) (R1∪R2) ° R3 = (R1 ° R3)∪(R2 ° R3)
(* °对∩的半分配律 *)
(3) R1 °(R2∩R3) ⊆ (R1 ° R2)∩(R1 ° R3) 
		(* 非等于实例： R1 ={<b,a>,<c,a>}, R2={<a,b>}, R3={<a,c>} *)
(4) (R1∩R2) ° R3 ⊆ (R1 ° R3)∩(R2 ° R3)

定理2.7：逆合成律

(* 设 F, G 为二集合, 则 *)
(F ° G)^-1 = G-1 ° F^-1

补充内容：

(1) (R1∪R2)^-1 = R1-1∪R2^-1
(2) (R1∩R2)^-1 = R1-1∩R2^-1
(3) (R1°R2)^-1 = R2^-1 ° R1^-1
(4) (A×B)^-1 = B×A
(5) (~R)^-1 = ~R^-1 (* 这里 ~R=A×B-R *)
(6) (R1-R2)^-1 = R1^-1-R2^-1

定理2.8：象的性质

(* 记C为非空集族 *)
(1) R↑(A∪B) = (R↑A)∪(R↑B);
(2) R↑∪C = ∪{ R↑A | A∈C };
(3) R↑(A∩B) = (R↑A)∩(R↑B);
(4) R↑∩C = ∩{ R↑A | A∈C };
(5) (R ° S)↑A = R °(S↑A).

定理2.9：限制的性质

(* 记C为非空集族 *)
(1) R[A∪B] = R[A]∪R[B];
(2) R[∪A ] = ∪{ R[A] | A∈A };
(3) R[A∩B] ⊆ R[A]∩R[B];
(4) R[∩A ] ⊆ ∩{ R[A] | A∈A };
(5) R[A]-R[B] ⊆ R[A-B];
(6) (R°S)[A] = R[S[A]].
(* 当R为单根关系时，(3)(4)(5)中等号成立 *)