離散數學chap2 Relations觀念

Relational Thinking

§2–4 Relations and Equivalence
▪Def. & Ex.
▪Graphs of Relation
▪Relations vs. Functions
▪Equivalence Relations
▪Modular Arithmetic

§2–5 Selections & Arrangement
▪Def. & Ex.
▪Hasse Diagrams
▪Topological Sorting

Relation：乘積空間的子集
Definition: 集合的(二元)關係 (Relation on a Set)
令 ｘ為任意集合，我們說集合 Ｒ為 Ｘ上的 (二元) 關係 若下列條件滿足：
集合Ｒ中的元素由從 Ｘ而來的 有序配對元素 (ordered pairs of elements)， (x,y)(x,y) 所組成，其中 x∈X 且y∈X。

Relation VS Function
Relation：any given x may be related to several other elements or none at all.
1->多 or 1->無
___

Function：
If we graph a function y = f (x)
y: dependent variable
x: independent variable
1->1 or 1->多

等價關係(Equivalent Relation)
Definition:
一個在集合 Ｘ上的 等價關係(Equivalent Relation) 為一個在集合 Ｘ上的關係 “ Ｒ” 滿足下列三個性質：
若 x∈X, 則 xＲx. (Reflexivity)
若 x,y∈X 且 xＲy, 則 yＲx. (Symmetry)
若 x,y,z∈X且 xＲy 與 yＲz, 則xＲz. (Transitivity)

換句話說，等價關係要求

1. (x,x)∈R 對任意 x∈X
2. (x,y)∈R⇒(y,x)∈R
3. 若 (x,y)∈R與 (y,z)∈R則 (x,z)∈R

§2–5 Partial Orderings
▪Def. & Ex.

▪Hasse Diagrams

▪Topological Sorting