關係&函數(Relations & Functions)


二元關係(binary relation)

探討兩物件之間關係形成的集合,記為「ρ」(發音為「rho」),兩物件 a 與 b 之間的二元關係記為「aρb」或「(a,b)∈ρ」,兩種表示方式實質等價。


一、單一集合的二元關係

二元關係為該集合本身笛卡爾積的子集。

舉例來說,若在集合 S 中包含 a、b、c 三個元素,則 S 的二元關係形成的集合「ρ」必定為「S×S」這個超集「{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)}」的子集。

「單一集合二元關係」範例

若有一集合 S={0,1,2,3},(aρb)↔(a>b),請問「ρ」為何?

首先我們知道,「ρ」必為「S×S={(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(3,3)}」的子集,而在 S×S 中,有哪些元素符合「a>b」條件呢?

答案是 {(1,0),(2,0),(2,1),(3,0),(3,1),(3,2)},在 S×S 中這些元素形成的子集「ρ」中的每個元素都符合「a>b」二元關係。


二、多個集合的二元關係

二元關係為不同集合間笛卡爾積的子集。

舉例來說,若在集合 S 中包含 a、b、c 三個元素、集合 T 中包含 x、y 兩個元素,則 S 與 T 的二元關係「ρ」形成的集合必定為「S×T」這個超集「{(a,x),(a,y),(b,x),(b,y),(c,x),(c,y))}」的子集。

「多個集合二元關係」範例

若有一集合 S={0,1,2,3}、集合 T={-1,-2,-3},(xρy)↔(x+y=0),請問「ρ」為何?

「ρ」必為「S×T={(0,-1),(0,-2),(0,-3),(1,-1),(1,-2),(1,-3),(2,-1),(2,-2),(2,-3),(3,-1),(3,-2),(3,-3)}」的子集,而在 S×T 中,有哪些元素符合「x+y=0」條件呢?

答案是 {(1,-1),(2,-2),(3,-3)},在 S×T 中這些元素形成的子集「ρ」中的每個元素都符合「x+y=0」二元關係。


三、齊次關係(homogeneous relation)

描述「同一集合中」的元素自己跟自己、或跟其他元素形成的二元關係。

齊次關係共有下列八種性質:

自反性(reflexive)

若在一集合 S 中有二元關係「ρ」,取 S 中任意元素 x,(x,x) 皆屬於「ρ」這層關係時,稱「ρ」這個二元關係具有自反性。
[∀(x)∈ S]‧[(x,x) ∈ ρ]
舉例來說,若 S={1,2,3},S 中的一個二元關係 ρ 為「=」,因為 1=1、2=2、3=3,用 ρ 描述 S 當中每個元素跟自己的關係皆正確,就可以說 ρ(即「=」)這個二元關係在 S 集合中具有自反性。

非自反性(irreflexive)

即「自反性」的相反,若在一集合 S 中有二元關係「ρ」,取 S 中任意元素 x,(x,x) 皆不屬於「ρ」這層關係,稱「ρ」這個二元關係具有非自反性。
[∀(x)∈ S]‧[(x,x) ∉ ρ]
舉例來說,若 S={1,2,3},S 中的一個二元關係 ρ 為「>」,因為 1>1、2>2、3>3 皆錯誤,ρ 無法用於描述 S 當中每個元素跟自己的關係,就可以說 ρ(即「>」)這個二元關係在 S 集合中具有非自反性。

對稱性(symmetric)

若在一集合 S 中有二元關係「ρ」,取 S 中任意兩元素 x、y,若 (x,y) 屬於 ρ,則 (y,x) 也屬於 ρ,則稱此二元關係「ρ」具有對稱性。
[∀(x,y)∈ S]‧{[(x,y)∈ ρ] → [(y,x)∈ ρ]}
舉例來說,若 S={1,2,3},S 中的一個二元關係 ρ 為「皆為奇數」,則 ρ 包含 {(1,3)} 這個集合,也必會包含 {(3,1)} 這個集合,就可以說 ρ(即「皆為奇數」)這個二元關係在 S 集合中具有對稱性。

反對稱性(antisymmetric)

若在一集合 S 中有二元關係「ρ」,取 S 中任意兩元素 x、y,若 (x,y) 屬於 ρ、(y,x) 也屬於 ρ 時才能說「x=y」,則稱此二元關係「ρ」具有反對稱性。
[∀(x,y)∈ S]‧{[(x,y)∈ ρ ∧ (y,x) ∈ ρ] → (x=y)}
舉例來說,在自然數「N」這個集合中的一個二元關係 ρ 為「÷」,若要兩個數可互被對方除,則兩數必定相等,例如 4 可以被 2 整除、但 2 無法被 4 整除,若要讓這個雙向除法關係成立,則被除數跟除數必定相等,如 4÷4,因此稱 ρ(即「÷」)這個二元關係在N集合中具有反對稱性。

非對稱性(asymmetric)

若在一集合 S 中有二元關係「ρ」,取 S 中任意兩元素 x、y,若 (x,y) 屬於 ρ,則 (y,x) 不屬於 ρ,則稱此二元關係「ρ」具有非對稱性,符合此條件的二元關係必也同時滿足「非自反性」與「反對稱性」。
[∀(x,y)∈ S]‧[(x,y)∈ ρ → (y,x) ∉ ρ]
舉例來說,在實數「R」這個集合中的一個二元關係 ρ 為「<」,√2<√3 正確,但 √3<√4 錯誤,ρ 只滿足兩元素間的單向關係,就可以說 ρ(即「<」)這個二元關係在 R 集合中具有反對稱性。

遞移性(transitive)

若在一集合 S 中有二元關係「ρ」,取 S 中任意三元素 x、y、z,若 (x,y) 屬於 ρ 且 (y,z) 也屬於 ρ,則 (x,z) 也屬於 ρ,則稱此二元關係「ρ」具有遞移性,符合此條件的二元關係必也同時滿足「非自反性」與「非對稱性」。
[∀(x,y,z)∈ S]‧[(x,y)∈ ρ ∧ (y,z) ∈ ρ→ (x,z) ∈ ρ]
舉例來說,在實數「R」這個集合中的一個二元關係 ρ 為「<」,當 √2<√3 正確、√2<√4 也正確時,√2<√4 依然成立,就可以說 ρ(即「<」)這個二元關係在 R 集合中具有遞移性。

弱連通性(connected)

若在一集合 S 中有二元關係「ρ」,取 S 中任意兩元素 x、y,只要 x 跟 y 相異,則 x 跟 y 有關,或 y 跟 x 有關,則稱 x 跟 y 間的二元關係「ρ」具有弱連通性。
[∀(x,y)∈ S]‧{(x≠y) → [(x,y)∈ ρ] ∨ [(y,x)∈ ρ]}
舉例來說,在實數「R」這個集合中的一個二元關係 ρ 為「<」,取兩個相異的數 √2 及 √3,√2<√3 正確、√3<√2 錯誤,但因為兩元素間只要其中一個方向關係成立就具弱連通性,因此依然可以說 ρ(即「<」)這個二元關係在 R 集合中具有弱連通性。

連通性/全關係/完全性(strongly connected / totality)

若在一集合 S 中有二元關係「ρ」,取 S 中任意兩元素 x、y,只要 x 與 y 符合 ρ,或者 y 與 x 符合 ρ,就可以說稱 x 跟 y 之間的二元關係「ρ」具有連通性。
[∀(x,y)∈ S]‧[(x,y)∈ ρ) ∨ (y,x)∈ ρ)]
舉例來說,在實數「R」這個集合中的一個二元關係 ρ 為「≤」,取兩相異數 √2 及 √3,√2≤√3 正確、√3≤√2 錯誤,兩元素間其中一個方向關係成立;如果取兩相同數 2 及 2,2≤2 正確、把兩個 2 顛倒相比依然正確,就可以說 ρ(即「≤」)這個二元關係在 R 集合中具有連通性。

上面舉例的「<」在取兩相同數 2 及 2 時,不論方向,「2<2」皆錯誤,因此「<」不具連通性。


四、關係閉包(closure of relation)

讓不滿足某一特定關係的集合,在經過增加最少序對的情況下,變得滿足該特定關係。

舉例來說,若在集合 S={1,2,3,4} 的笛卡爾積中有一集合 A={(1,1),(2,3)},則 A 不具備「自反性」,那麼要如何使 A 變得有「自反性」呢?

在 A 集合中,我們少了 (2,2)、(3,3) 及 (4,4) 三個元素,A 集合中「至少」要加上這三個元素,才能變得有自反性,A 中原本有的元素則全部保留,最終變成 {(1,1),(2,2),(2,3),(3,3),(4,4)},這個新的集合就是「自反閉包(reflexive closure)」。

另有「對稱閉包(symmetric closure)」、「傳遞閉包(transitive closure)」等。


五、偏序關係(partial order relation)

若一個二元關係同時滿足下列三種條件,則稱為「偏序關係」:

  1. 自反性(reflexive)
  2. 反對稱性(antisymmetric)
  3. 遞移性(transitive)

舉例來說,在實數集合「R」中,我們可以依序檢查「x≤y」這個二元關係是否為一個「偏序關係」。

  1. 自反性:在 R 中,任意數必「≤」自己,因此具有自反性。
  2. 反對稱性:在 R 中,如果 x≤y 又 y≤x,則 x=y,因此具有反對稱性。
  3. 遞移性:在 R 中,如果 x≤y 又 y≤z,則 x≤z,因此具有遞移性。

「x≤y」在 R 中同時具備自反性、反對稱性與遞移性,因此可說「≤」這個二元關係為一「偏序關係」。

哈斯圖(Hasse diagram)

用來表示有限「偏序關係」集合的圖,其精神在於「用最簡化的方式描述該偏序集合元素間的關係」。繪製哈斯圖包含下列步驟:

  1. 由下而上標示集合中各個元素。
  2. 繪製各相同與相異元素間「有向圖(directed graph)」。
  3. 移除所有表示「自反性」的箭頭小圈。
  4. 移除所有表示「遞移性」的長箭頭。
  5. 因所有箭頭方向皆為由下往上,可將所有箭頭改為無方向性的線段。

例如有一個集合為 S={1,2,3,4},當中有一偏序關係 ρ 為 x|y(即 x 可整除 y,或 y 可被 x 整除),可以用「ρ={(x,y)| x|y }」表示,要如何用哈斯圖表示在 S 中,「ρ」這個偏序關係呢?

  1. 由下而上依序標示元素 1、2、3、4。
  2. ρ 包含 {(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)},將這些二元關係全部以箭頭表示。
  3. 移除所有表示「自反性」關係的小圈箭頭,包含 {(1,1),(2,2),(3,3),(4,4)},ρ 集合中剩下 {(1,2),(1,3),(1,4),(2,4)}。
  4. 移除所有表示「遞移性」的長箭頭,因為 1 可以連到 2、2 也能連到 4,因此移除 {(1,4)},此時 ρ 集合中剩下 {(1,2),(1,3),(2,4)}。
  5. 因所有箭頭方向皆往上,故可移除所有箭頭。

各步驟圖示如下:

實質等價/若且唯若(equivalence / if and only if)

同時滿足下列三條件的二元關係,可與「偏序關係」對照:

  1. 自反性(reflexive),同「偏序關係」
  2. 對稱性(symmetric),「偏序關係」為「反對稱性」
  3. 遞移性(transitive),同「偏序關係」

舉例來說,在實數集合「R」中,我們可以依序檢查「x=y」這個二元關係是否為一個「實質等價關係」。

  1. 自反性:在 R 中,任意數必「=」自己,因此具有自反性。
  2. 對稱性:在 R 中,如果 x=y,則 y=x,因此具對稱性。
  3. 遞移性:在 R 中,如果 x=y 又 y=z,則 x=z,因此具有遞移性。

「x=y」在 R 中同時具備自反性、對稱性與遞移性,因此可說「=」這個二元關係為一「實質等價關係」。

至於偏序關係中的範例「≤」呢?我們可以檢查其是否具備「對稱性」:在 R 中,如果 x≤y,則 y≤x 是否為真?答案很明顯是否定的,例如 x=3、y=5,當 3≤5 時,5≤3 並不成立,因此「≤」不具備「對稱性」,也不會是「實質等價」關係。


函數(function)

代表「兩集合間」的二元關係,與函數相關的幾個名詞如下:

  1. 自變數(independent variable):函數輸入值,如 f(x) 函數的 x。
  2. 應變數(dependent variable):函數輸出值,如 x 經 f(x) 函數得到的值。
  3. 原像(preimage):經函數逆向處理的結果,相當於自變數。
  4. 像(image):經函數順向處理的結果,相當於應變數。
  5. 定義域(domain):自變數的集合。
  6. 對應域(codomain):應變數存在的集合,為值域的超集,當中不屬於值域的元素無法在定義域中找到可對應的自變數。
  7. 值域(range):應變數的集合,為對應域的子集。

上面的敘述有些饒口,改用圖示理解會容易許多:

f(x) 函數將 X 集合中的「原像」對應到 Y 集合中的「像」

若要使 f(x) 符合「函數」的定義,則每個自變數都只能對應到恰好 1 個應變數,不得對應 0 個也不得對應多於 1 個應變數,但多個應變數可以對應到同一個自變數。

函數與非函數範例,凡有一個 x 對應超過一個 f(x) 者皆非函數

我們可以把函數想成超市的條碼掃描器,自變數 x 是商品、應變數 f(x) 是商品價格,所有商品刷過條碼之後都能跑出商品價格,同一種商品不可能同時有兩個價格,但同一個價格可能對應多種商品。


一、單射/嵌射(one-to-one / injection)

令 f 為一函數,只要對應域中的 f(a)=f(b),則定義域 X 中的元素 a 與 b 相等。用符號表示如下:
∀(a,b)∈ X,f(a)=f(b) → a=b
依照換質換位律,也可以表示如下:
∀(a,b)∈ X,a≠b → f(a)≠f(b)
用簡單一點的方式理解就是「對於自變數 x 與應變數 y 而言,每個 x 都只會對應到一個 y」,如同其英文名「one-to-one(一對一)」,圖示如下:

單射函數個數

由於單射函數的每個定義域元素必只對應到一個對應域元素,因此定義域元素個數必不超過對應域元素個數。設定義域為 X、對應域為 Y,|X|≤|Y|。

現假設 |X|=m、|Y|=n,則 m≤n。

要將 X 中的元素配對到 Y 中的元素時,第一個 X 元素共有 n 種 Y 元素可配對:

當 X 的第一個元素選擇了 Y 的其中一個元素(假設為第一個),則 X 的第二個元素只剩下 Y 中的 (n–1) 個元素可以選擇:

當 X 的第二個元素也選擇了 Y 的其中一個元素(假設為第二個),則 X 的第三個元素只剩下 Y 中的 (n–2) 個元素可以選擇:

依此類推,每將一個 X 元素配對到 Y 元素,下一個 X 元素都會少一個 Y 中的元素可供配對:

配對到第 (m–1) 個 X 元素時,Y 剩下 [n–(m–2)] 個元素可供選擇:

等配對到X的最後一個元素時,Y 剩下 [n–(m–1)] 個元素:

綜合以上結果,可推斷出共有以下配對數量:

上式可用「階乘」概念表示如下,若將紅字部分約分將得上式:

上式可再用「排列」方式呈現如下:

若 f 代表以 X 為定義域、Y 為對應域的單射函數,|X|=m、|Y|=n,m≤n,f 的個數為 P(n,m),可以想成「在 n 個對應域元素中,挑 m 個出來配對定義域元素」。


二、滿射/蓋射(onto / surjection)

若 X→Y 代表一函數關係 f,則對於對應域 Y 中任一元素 y,必能在定義域中 X 找到對應的元素 x,使 f(x)=y。用符號表示如下:
(∀y∈ Y), (∃x∈ X), f(x)=y
用簡單一點的方式理解就是「對於自變數 x 與應變數 y 而言,所有的 y 都不會落單」,要達成這個條件,對應域中的元素必定不會超過定義域的元素數量。

兩種符合「滿射」的情況

滿射函數個數

由於「滿射」的定義是「每個對應域的元素都不能落單」,因此,要找出滿射函數個數,就是「所有函數可能數」扣除「有對應域元素落單個數」。

首先來看「所有函數可能數」,若定義域 X 中的元素有 m 個,只要不設定任何條件,每個 X 中的元素都有 n 個 Y 中的元素可配對,一共有「nᵐ」種配對方式,圖示如下:

不設定任何條件下的所有配對可能,其中 m 不一定與 n 相等

為了要滿足「滿射」函數條件,定義域 X 元素個數至少要與對應域 Y 元素個數相等,即「|X|≥|Y|」,若定義域X中的元素比對應域 Y 中的元素少,又要達成「滿射」,那將有定義域X元素配對到超過一個對應域 Y 的元素,這並不符合「函數」的定義。

若定義域元素比對應域元素少、又要達成滿射,將無法符合「函數」定義

如果其中一個 Y 的元素不取,共有 C(n,1) 種可能,而對於 X 中 m 個元素而言,每個元素都只剩下 (n–1) 種選擇可供配對,圖示如下,紅字代表 Y 中不取的元素:

如果其中兩個 Y 的元素不取,共有 C(n,2) 種可能,而對於 X 中 m 個元素而言,每個元素都只剩下 (n–2) 種選擇可供配對,部分範例圖示如下,紅字代表 Y 中不取的元素:

依上述範例類推,若 f 代表以 X 為定義域、Y 為對應域的滿射函數,|X|=m、|Y|=n,m≥n,f 的個數如下:


三、雙射/對射(bijection)

函數 f 中,每個定義域的元素都只對應一個對應域元素,每個對應域元素也只會對應一個定義域元素。現假設函數 f 代表 X→Y,若 f 為一「雙射函數」,則必符合下列性質:

  1. 每個 X 中的元素必至少與一個 Y 中的元素配對。
  2. 每個 X 中的元素必不與超過一個 Y 中的元素配對(即「單射」)。
  3. 每個 Y 中的元素必至少與一個 X 中的元素配對(即「滿射」)。
  4. 每個 Y 中的元素必不與超過一個 X 中的元素配對。

統整上述四點可知,「雙射」函數就是「X 的元素與 Y 的元素之間每一組的配對都是唯一的」,且必同時滿足「單射」與「滿射」條件。


四、反函數(inverse function)

若有一函數 f 代表 X→Y,則其反函數 f⁻¹ 就是 Y→X,可以有反函數的函數稱為「可逆函數(invertible function)」,所有可逆函數必為雙射函數。

在下圖中,f(x) 與 f⁻¹(x) 互為反函數關係、g(x) 與 g⁻¹(x) 亦互為反函數關係。對於 f(x) 及 g⁻¹(x) 而言,藍色區域為定義域、粉紅區域為對應域;對於 f⁻¹(x) 與 g(x) 而言,藍色區域為對應域、粉紅區域為定義域。


五、複合函數/合成函數(composite function)

一個函數中另有一個函數,也就是把某函數的應變數變成另一函數的應變數。可以同時表示所有其他函數運算結果的函數,稱為「複合函數」。

在下圖中,下方的 y(x) 即為一「複合函數」。


錯排(derangement)

若有 n 個元素排列,經「錯排」後,每個元素都不在自己原本的位置上,其數量記為「Dₙ」或「!n」。

錯排數量

若給定 n 個數排列,經過錯排後,總排列數 Dₙ 為多少呢?

設 A₁ 代表有一個數在原來位置、A₂ 代表有兩個數在原來位置、…、Aₙ 代表有 n 個數在為來位置,則 Dₙ 的數量如下:

扣除部分為「有 1~n 個數排在原來位置」的數量,根據「排容原理」,可改寫如下:

等號右方包含幾個部分,各以不同顏色區別:

  1. 白色:錯排前所有排列可能性個數,共有 n! 種。
  2. 黃色:有一個數在原位置個數,共有 C(n,1)(n–1)! 種。
  3. 綠色:有兩個數在原位置個數,共有 C(n,2)(n–2)! 種。
  4. 藍色:有三個數在原位置個數,共有 C(n,3)(n–3)! 種。
  5. 橘色:所有數都在原位置個數,共有 C(n,n)(n–n)!=1 種。

確認每個數值後,上式可再改寫如下:

將有色部分每項係數展開,發現皆可約分:

約分後得到下式:

再把「n!」提出後可得下式:

若用 Σ 表示括號內的所有項次,可得錯排組合數如下:

當 n 趨近於無限大時,Σ 內的值會趨近於 e⁻¹,因此錯排數又能改寫如下:

上述的「e」指的是「自然常數/尤拉數(Euler’s number)」。


模除(modulo operation)

符號記為「%」,用來計算兩數相除後的餘數,設該餘數為「r」,則「0≤r<除數」,舉例如下:

  1. 3÷3=1…0,因此 3%3=0
  2. 2÷3=0...2,因此 2%3=2
  3. 1÷3=0…1,因此 1%3=1
  4. 0÷3=0…0,因此 0%3=0
  5. (-1)÷3=(-1)…2,因此 (-1)%3=2
  6. (-2)÷3=(-1)…1,因此 (-2)%3=1
  7. (-3)÷3=(-1)…0,因此 (-3)%3=0

一、模算數(modular arithmetic)

若有兩整數 a、b,兩者的差 (a–b) 可被另一正整數 n 整除,則 a、b 各自除以 n,所得餘數相同,此時稱「a、b 同餘模」,符號表示如下:

舉例來說,若 a=5、b=3、n=2,則 a、b 各自與 n 之間有什麼關係呢?

  1. 5%2=1
  2. 3%2=1

由上述兩者可發現,不論 a 除以 n,或者 b 除以 n,餘數都是一樣的,而當我們檢視 a 跟 b 的差,可以發現:

  1. a–b=5–3=2

這個 a 跟 b 的差值正好可以被 n 整除。

模算數原理

為何只要兩數的差可以被另一正整數整除,就說這兩個數除以該正整數的餘數相同、有「同餘模」關係呢?我們可以用更具體的方式理解:

現假設 n=3,則任何整數除以 n 所得的餘數必定只有 0、1、2 三種,現我們將餘數相同者歸類在同一集合:

  1. 餘數為 0 者:{…(-9),(-6),(-3),0,3,6,9…}
  2. 餘數為 1 者:{…(-8),(-5),(-2),1,4,7,…}
  3. 餘數為 2 者:{...(-7),(-4),(-1),2,5,8…}

只要同一集合內,任兩個數的差剛好都是 3 的倍數,就因為同集合內任兩數的差可以被 n 整除,可說明這兩個數同屬於「除以 n 的餘數相同」這個群體。

小結

  1. 二元關係(ρ):同一集合中或相異集合間,兩元素間關係的集合。
  2. 齊次關係:描述同一集合內元素自己跟自己、或跟其他元素間的二元關係。
  3. 自反性:齊次關係性質之一,描述一集合中某元素自己跟自己有關。
  4. 非自反性:齊次關係性質之一,描述一集合中某元素自己跟自己無關。
  5. 對稱性:齊次關係性質之一,若一集合中兩元素 (a,b) 有該二元關係,(b,a) 也有該二元關係,則兩元素相等。
  6. 反對稱性:齊次關係性質之一,若一集合中兩元素 (a,b)、(b,a) 都有該二元關係,則 a=b。
  7. 非對稱性:齊次關係性質之一,若一集合中兩元素 (a,b) 有該二元關係,則 (b,a) 沒有該二元關係。
  8. 遞移性:齊次關係性質之一,若一集合中兩元素 (a,b) 及另外兩元素 (b,c) 都有該二元關係,則 (a,c) 也有該二元關係。
  9. 弱連通性:齊次關係性質之一,對於一集合中兩元素 a、b,只要兩元素相異,則 (a,b) 或 (b,a) 屬於該二元關係。
  10. 強連通性:齊次關係性質之一,對於一集合中兩元素 a、b,(a,b) 或 (b,a) 屬於該二元關係。
  11. 關係閉包:對於某一不滿足特定二元關係的集合,經增加最少序對後,形成符合該二元關係的新集合。
  12. 偏序關係:同時滿足自反性、反對稱性、遞移性的二元關係。
  13. 哈斯圖:用最簡化的方式表示有限偏序關係集合的圖。
  14. 實質等價:同時滿足自反性、對稱性、遞移性的二元關係。
  15. 函數:兩集合間的二元關係,每個自變數只能對應一個應變數。
  16. 自變數=原像:函數輸入值。
  17. 應變數=像:函數輸出值。
  18. 定義域:自變數的集合。
  19. 對應域:應變數存在的集合,包含非應變數與所有應變數。
  20. 值域:對應域中,所有應變數的集合。
  21. 單射:每個自變數都只對應一個應變數。
  22. 單射函數個數:若一函數定義域有 m 個元素、對應域有 n 個元素,m≤n,則有 P(n,m) 個單射函數。
  23. 滿射:每個應變數都有自變數與其對應。
  24. 滿射函數個數:若一函數定義域有 m 個元素、對應域有 n 個元素,m≥n,則有 nᵐ–[C(n,1)(n–1)ᵐ+C(n,2)(n–2)ᵐ+...+C(n,n)(n–n)ᵐ] 個滿射函數。
  25. 雙射:所有自變數跟應變數都是一對一配對。
  26. 反函數:函數的逆向運作,如對於函數 f 而言,f⁻¹ 為其反函數;所有反函數皆為雙射函數。
  27. 複合函數:若 y(x)=f(g(x)),則 y(x) 為複合函數。
  28. 錯排(Dₙ或!n):排列好的物件重新排列後,每個物件都不在原來的位置上。
  29. 錯排數量:可用「排容原理」計算,最終約等於 n!/e。
  30. 模除(%):用於求除法中的餘數。
  31. 模算數:若兩整數 a、b 之差可被一正整數 n 整除,若且唯若 a%n=b%n。
#離散數學 #關係 #函數







你可能感興趣的文章

[25] 強制轉型 - 隱含的強制轉型、Addition Operator、Strings <> Numbers

[25] 強制轉型 - 隱含的強制轉型、Addition Operator、Strings <> Numbers

Day02  深入了解 Lazy-load 的背後實作 - Intersection Observer API

Day02 深入了解 Lazy-load 的背後實作 - Intersection Observer API

串接 Firebase SDK 做 Google OAuth 第三方登入

串接 Firebase SDK 做 Google OAuth 第三方登入






留言討論