互斥集

在數學裏，若兩個集合沒有共同的元素，稱為互斥（disjoint）。例如$\{1,2,3\}$和$\{4,5,6\}$為互斥集（disjoint sets）。

兩個互不相交的集合（disjoint sets）。

解釋

從定義說，兩個集合$A$和$B$為互斥，若其交集為空集，即

$A\cap B=\varnothing$

此一定義可推廣至集族上。若然一個集族裏的任意兩個相異集合均為互斥，則稱之為兩兩互斥。

形式上，設$I$為索引集，且對$I$內的任一元素$i$，設$A_{i}$為一集合。然後$\{A_{i}:i\in I\}$為兩兩互斥，當對任何於$I$內的$i$和$j$且$i\neq j$，有

$A_{i}\cap A_{j}=\varnothing$

舉例來說，$\{\{1\},\{2\},\{3\},\dots \}\}$便為兩兩互斥。若$\{A_{i}\}$為兩兩互斥，則$\{A_{i}\}$中各集合的交集為空集：

$\bigcap _{i\in I}A_{i}=\varnothing$

相反則不必為真：$\{\{1,2\},\{2,3\},\{3,1\}\}$內各集合的交集為空集，但非兩兩互斥。事實上，其內的集合甚至沒有兩個是互斥集。

集合劃分$X$是由一群兩兩互斥的非空集合$\{A_{i}:i\in I\}$組成的集族。

$\bigcup _{i\in I}A_{i}=X$

另見

• 幾乎互斥集
• 互斥併
• 互斥集資料結構