等價類

在離散數學中，等價關係是指定義在集合A上的關係，滿足自反的、對稱的和傳遞的等性質。設R是定義在集合A上的等價關係，與A中一個元素a有關係的所有元素的集合叫做a的等價類。等價類套用十分廣泛，如在程式語言中，我們使用等價類來判定標識符是不是表示同一個事物。

基本介紹

• 中文名：等價類
• 外文名：Equivalence class
• 1：定義
• 2：分類
• 3：舉例

定義

在離散數學中，等價關係是指定義在集合A上的關係，滿足自反的、對稱的和傳遞的等性質。設R是定義在集合A上的等價關係，與A中一個元素a有關係的所有元素的集合叫做a的等價類。A的關於R的等價類記作 。當只考慮一個關係時，我們省去下表R並把這個等價類寫作[a]。

在軟體工程中，是把所有可能輸入的數據，即程式的輸入域劃分成若干部分（子集），然後從每一個子集中選取少數具有代表性的數據作為測試用例，從而減少了數據輸入量從而提高了效率，稱之為等價類方法，該方法是一種重要的、常用的黑盒測試用例設計方法。

分類

在離散數學中，等價類的劃分基於以下定理：設R是定義在集合A上的等價關係。那么R的等價類構成S的劃分。反過來，給定集合S的劃分{ |i∈I},則存在一個等價關係R，它以集合 作為它的等價類。

因為等價關係的 a 在 a 中和任何兩個等價類要么相等要么不交集不相交的性質。得出 X 的所有等價類的集合形成 X 的集合劃分劃分: 所有 X 的元素屬於一且唯一的等價類。反過來，X 的所有劃分也定義了在 X 上等價關係。

在軟體工程中等價類劃分及標準如下：

劃分等價類

等價類是指某個輸入域的子集合。在該子集合中，各個輸入數據對於揭露程式中的錯誤都是等效的，併合理地假定：測試某等價類的代表值就等於對這一類其他值的測試，因此，可以把全部輸入數據合理劃分為若干等價類，在每一個等價類中取一個數據作為測試的輸入條件就可以用少量代表性的測試數據取得較好的測試結果。等價類劃分有兩種不同的情況：有效等價類和無效等價類。

1）有效等價類

是指對於程式的規格說明來說是合理的、有意義的輸入數據構成的集合。利用有效等價類可檢驗程式是否實現了規格說明所規定的功能和性能。

2）無效等價類

指對程式的規格說明是不合理的或無意義的輸入數據所構成的集合。對於具體的問題，無效等價類至少應有一個，也可能多個。

設計測試用例時，要同時考慮這兩種等價類。因為軟體不僅要能接收合理的數據，也要能經受意外的考驗，這樣的測試才能確保軟體具有更高的可靠性。

3.劃分等價類的標準

1) 完備測試、避免冗餘

2) 劃分等價類重要的是：集合的劃分、劃分為互不相交的一組子集，而子集的並是整個集合

3) 並是整個集合：備性

4) 子集互不相交：保證一種形式的無冗餘性

5) 同一類中標識（選擇）一個測試用例，同一等價類中，往往處理相同，相同處理映射到“相同的執行路徑”。

舉例

* 如果 X 是轎車的集合，而 ~ 是“顏色相同”的等價關係，則一個特定等價類由所有綠色轎車組成。X / ~ 自然的被認同於所有轎車顏色的集合。

* 考慮在整數集合 Z 上的“模 2”等價關係: X~y 若且唯若 X-y 是偶數。這個關係精確的引發兩個等價類: 0 由所有偶數組成，1 由所有奇數組成。在這個關係下 7 9 和 1 都表示 Z / ~ 的同一個元素。

* 有理數可以構造為整數的有序對 (a,b) 的等價類的集合，b 不能為零，這裡的等價關係定義為

(a,b) ~ (c,d) 若且唯若 ad = bc。

:這裡的有序對 (a,b) 的等價類可以被認同於有理數 a/b。

* 任何函式 f: X → Y 定義在 X 上的等價關係，通過 X1 ~ X2 若且唯若 f(X1) = f(X2)。X 的等價類是在 X 中被映射到 f(X) 的所有元素的集合，就是說，類 X 是f(X) 的像逆像。這個等價關係叫做 f的函式的核核。

* 給定群 G 和群子群 H，我們可以定義在 G 上的等價關係，通過 X ~ y 若且唯若 xy^ -1 ∈ H。這個等價類叫做 H 在 G 中的右陪集；其中之一是 H 自身。它們都有同樣數目的元素(在無限集合無限 H 的情況下是勢)。如果 H 是群正規子群，則所有陪集的集合自身是在自然方式下的一個群。

* 所有群都可以劃分成叫做共軛類的等價類。

* 連續函式連續映射 f的同倫類是所有同倫於 f的所有映射的等價類。

* 在自然語言處理中，等價類是對一個個人、位置、事物或事件的所有提及的要么真實要么虛構的集合。例如，在句子 “GE 股東將投票公司傑出的 CEO Jack Welch 的繼任者”。“GE”和“公司”是同義的，所以構成一個等價類。對“GE 股東”和“Jack Welch”有單獨的等價類。

下面是一個軟體工程的簡單例子

三角形問題

1、某程式規定：“輸入三個整數a、b、c分別作為三邊的邊長構成三角形。通過程式判定所構成的三角形的類型，當此三角形為一般三角形、等腰三角形、等邊三角形時，分別做計算。。。”用等價類劃分方法為該程式進行測試用例設計。（三角形問題的複雜之處在於輸入與輸出之間的關係比較複雜。）

分析題目中給出和隱含的對輸入條件的要求：

（1）整數

（2）三個數

（3）非零數

（4）整數

（5）兩邊之和大於第三邊

（6）等腰

（7）等邊

如果a、b、c滿足條件（1）~（4），則輸出下列四種情況之一：

1）如果不滿足條件（5），則程式輸出為“非三角形”

2）如果三條邊相等即滿足條件（7），則程式輸出為“等邊三角形”

3）如果只有兩條邊相等，及滿足條件（6），則程式輸出為“等腰三角形”

4）如果三條邊都不相等，則程式輸出為“一般三角形”

列出等價類表並編號

覆蓋有效等價類的測試用例：

a b c覆蓋等價類號碼

3 4 5 （1） （7）

4 4 5（1）（7） （8）

4 5 5 （1） （7） （9）

5 4 5 （1） （7） （10）

4 4 4 （1） （7） （11）

覆蓋無效等價類的測試用例：