離散數學/集合論

離散數學
← 簡介	集合論	集合論/第 2 頁 →

維基百科在 集合論 有相關資訊

簡介

集合論從最簡單的概念開始：它考察一個物件是否屬於或不屬於一個集合，該集合以某種明確的方式描述了一組物件。從這個簡單的開始，可以發展出一系列越來越複雜（而且有用！）的概念，這些概念最終會引申出具有多種應用的符號和技巧。

定義：集合

集合的當前定義可能聽起來很模糊。一個集合可以定義為實體的無序集合，這些實體因為符合某個規則而關聯在一起。

'實體'可以是任何東西，從字面上講：數字、人、形狀、城市、文字片段，... 等等

關於它們都遵循的'規則'的關鍵事實是它必須是明確定義的。換句話說，它必須清楚地描述實體遵循的規則。例如，如果我們談論的是單詞，一個明確定義的規則是

X is English

一個未明確定義的規則（因此不能用來定義集合）可能是

X is hard to spell

其中 X 是任何單詞

元素

屬於給定集合的實體稱為該集合的元素。例如

Henry VIII is an element of the set of Kings of England. : kings of England {Henry VIII}

集合符號

要列出集合的元素，我們將它們用花括號括起來，並用逗號隔開。例如

 $\{-3,-2,-1,0,1,2,3\}$

集合的元素也可以用文字描述

 $\{{\text{ integers between }}-3{\text{ and  }}3{\text{ inclusive}}\}$

集合生成器符號可用於描述那些顯式列出太繁瑣的集合。要表示任何特定的集合，我們使用字母 $x$

 $\{x|x{\text{ is an integer and }}|x|<4\}$

或等效地

 $\{x|x\in \mathbb {Z} ,|x|<4\}$

符號 $\in$ 和 $\notin$ 分別表示元素的包含和排除

 ${\text{dog }}\in \{{\text{quadrupeds}}\}$ 
 ${\text{Washington DC}}\notin \{{\text{European capital cities}}\}$

集合可以包含無限多個元素，例如素數集合。省略號用於表示模式的無限延續

 $\{2,3,5,7,11,\dots \}$

請注意，省略號的使用可能會導致歧義，上面的集合可以看作是可被 4 整除的整數集合，例如。

集合通常用大寫字母表示： $A$ , $B$ , ...
元素通常用小寫字母表示： $x$ , $y$ , ...

特殊集合

全集

當前上下文中所有實體的集合稱為全集，或簡稱為宇宙。它用 $U$ 表示。

例如，上下文可能是一道作業練習，其中全集被限制為其所考慮的特定實體。同樣，它也可能是一道任意問題，我們清楚地知道它應用於何處。

空集

不包含任何元素的集合稱為空集或空集。它用一對空括號表示： $\{\}$ 或符號 $\varnothing$ 表示。

定義一個不包含任何元素的集合可能看起來很奇怪。但是，請記住，人們可能正在尋找問題的解決方案，而這些解決方案是否存在尚不清楚。如果事實證明沒有解決方案，那麼解決方案集就是空的。

例如

如果 $U=\{{\text{words in the English language}}\}$ ，那麼 $\{{\text{words with more than 50 letters}}\}=\varnothing$ 。

如果 $U=\{{\text{whole numbers}}\}$ ，那麼 $\{x|x^{2}=10\}=\varnothing$ 。

空集上的運算

對空集執行的運算（作為要進行運算的一組事物）也可能令人困惑。（此類運算為空運算。）例如，空集元素的總和為零，但空集元素的乘積為一（見空積）。這可能看起來很奇怪，因為空集沒有元素，那麼它們加起來或乘起來是否重要？（因為“它們”不存在？）最終，這些運算的結果更多地反映了所討論的運算，而不是空集本身。例如，請注意零是加法的單位元，而一是乘法的單位元。

特殊的數字集合

一些集合使用頻率很高，因此被賦予了特殊的符號。

自然數

從 1 開始的“計數”數（或整數）稱為自然數。此集合有時用N 表示。所以N = {1, 2, 3, ...}。

請注意，當我們用手寫此集合時，我們無法用粗體型別寫入，因此我們用黑板粗體字型寫入 N： $\mathbb {N}$

整數

所有整數，正數、負數和零構成整數集合。它有時用Z 表示。所以Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}。

在黑板粗體中，它看起來像這樣： $\mathbb {Z}$

實數

如果我們將整數集合擴充套件到包括所有小數，我們將構成實數集合。實數集合有時用R 表示。

實數的小數點後可能具有有限個數字（例如 3.625），或者具有無限個小數數字。在無限個數字的情況下，這些數字可能是

迴圈的；例如 8.127127127...

... 或者它們可能不迴圈；例如 3.141592653...

在黑板粗體中： $\mathbb {R}$

有理數

小數位數有限或迴圈的那些實數稱為有理數。有理數集合有時用字母Q 表示。

有理數總是可以寫成精確的p/q 分數；其中p 和q 是整數。如果q 等於 1，則分數只是整數p。請注意，q 不能等於零，因為該值將是未定義的。

例如：0.5、-17、2/17、82.01、3.282828... 都是有理數。

在黑板粗體中： $\mathbb {Q}$

無理數

如果一個數字不能用分數p/q精確地表示，則稱該數字為無理數。

例如：√2，√3，π。

集合論練習 1

點選連結檢視集合論練習 1

集合之間的關係

現在我們將研究集合之間各種關係。

相等

兩個集合 $A$ 和 $B$ 被稱為相等，當且僅當它們具有完全相同的元素。在這種情況下，我們簡單地寫

 $A=B$

注意關於相等集合的另外兩個事實

元素的順序無關緊要。

如果一個元素被列出多次，則忽略任何重複出現的元素。

因此，例如，以下集合都是相等的

 $\{1,2,3\}=\{3,2,1\}=\{1,1,2,3,2,2\}$

(您可能想知道為什麼有人會寫出像 $\{1,1,2,3,2,2\}$ 這樣的集合。您可能還記得，當我們定義空集時，我們注意到可能沒有特定問題的解決方案 - 因此需要一個空集。好吧，這裡我們可能正在嘗試幾種不同的解決問題的方法，其中一些實際上導致了相同的解決方案。但是，當我們考慮不同的解決方案時，任何這樣的重複將被忽略。）

子集

如果集合 $A$ 的所有元素也是集合 $B$ 的元素，那麼我們說 $A$ 是 $B$ 的子集，我們寫成

 $A\subseteq B$

例如

在下面的例子中

If  $T=\{2,4,6,8,10\}$  and  $E=\{{\text{even integers}}\}$ , then  $T\subseteq E$ 
If  $A=\{{\text{alphanumeric characters}}\}$  and  $P=\{{\text{printable characters}}\}$ , then  $A\subseteq P$ 
If  $Q=\{{\text{quadrilaterals}}\}$  and  $F=\{{\text{plane figures bounded by four straight lines}}\}$ , then  $Q\subseteq F$

請注意 $A\subseteq B$ 並不意味著 $B$ 必須包含不在 $A$ 中的額外元素；這兩個集合可能是相等的 - 就像上面 $Q$ 和 $F$ 一樣。但是，如果另外 $B$ 確實包含至少一個不在 $A$ 中的元素，那麼我們說 $A$ 是 $B$ 的真子集。在這種情況下，我們將寫

 $A\subset B$

在上面的例子中

 $E$  contains ... -4, -2, 0, 2, 4, 6, 8, 10, 12, 14, ... , so  $T\subset E$

 $P$  contains $, ;, &, ..., so  $A\subset P$

但 $Q$ 和 $F$ 只是說同一件事的不同方式，所以 $Q=F$

使用 $\subset$ 和 $\subseteq$ ；與使用 < 和 ≤ 來比較兩個數字顯然是類似的。

還要注意，每個集合都是全集的子集，而空集是每個集合的子集。

（你可能對最後一個陳述感到好奇：空集怎麼能是任何東西的子集，因為它不包含任何元素？這裡關鍵在於，對於每個集合 $A$ ，空集不包含任何不在 $A$ 中的元素。所以 $\oslash \subseteq A$ 對於所有集合 $A$ ）。

最後，請注意，如果 $A\subseteq B{\text{ and }}B\subseteq A{\text{ then }}A$ 和 $B$ 必須包含完全相同的元素，因此相等。換句話說

 $A\subseteq B{\text{ and }}B\subseteq A{\text{ then }}A=B$

不相交

如果兩個集合沒有共同的元素，則稱它們是不相交的。例如

If  $A=\{{\text{even numbers}}\}$  and  $B=\{1,3,5,11,19\}$ , then  $A$  and  $B$  are disjoint sets

韋恩圖

韋恩圖可以是說明集合之間關係的一種有用方法。

在韋恩圖中

全集用一個矩形表示。矩形內的點表示屬於全集的元素；矩形外的點表示不屬於全集的元素。那麼，你可以將這個矩形看作一個“籬笆”，它將不需要的東西拒之門外，並將我們的注意力集中在我們正在討論的事情上。

其他集合用迴圈表示，通常呈橢圓形或圓形，繪製在矩形內。同樣，給定迴圈內的點表示它所代表的集合中的元素；迴圈外的點表示不屬於該集合的元素。

在左邊，集合A和B是不相交的，因為迴圈沒有重疊。

在右邊，A是B的子集，因為代表集合A的迴圈完全被迴圈B包含。

韋恩圖：習題

示例 1

圖 3表示一個韋恩圖，顯示了兩個集合A和B，在一般情況下，我們對集合之間的任何關係一無所知。

注意，代表全集的矩形被劃分為四個區域，分別標記為i、ii、iii和iv。

如果事實證明

（a）區域ii為空？

（b）區域iii為空？

（a）如果區域ii為空，則A不包含任何不屬於B的元素。所以A是B的子集，並且應該像上面的圖 2那樣重新繪製圖表。

（b）如果區域iii為空，則A和B沒有共同的元素，因此是不相交的。然後應該像上面的圖 1那樣重新繪製圖表。

示例 2

（a）繪製一個韋恩圖來表示三個集合A、B和C，在一般情況下，我們對集合之間可能的關係一無所知。

（b）現在代表U的矩形被劃分為多少個區域？

（c）當這些區域的各種組合為空時，討論集合A、B和C之間的關係。

（a）圖 4中的圖表顯示了三個集合的一般情況，我們對它們之間可能存在的任何關係一無所知。

（b）現在代表U的矩形被劃分為 8 個區域，用羅馬數字i到viii表示。

（c）各種組合的空區域都是可能的。在每種情況下，可以重新繪製韋恩圖，以便不再包含空區域。例如

如果區域ii為空，則應縮小代表A的迴圈，並將其移動到B和C內部以消除區域ii。

如果區域ii、iii和iv為空，則縮小A和B，並將它們移動到C內部（從而消除所有這三個區域），但以一種它們仍然相互重疊的方式這樣做（從而保留區域vi）。

如果區域iii和vi為空，則“拉開”迴圈A和B以消除這些區域，但保持每個迴圈與迴圈C重疊。

...等等。繪製上述每個示例的韋恩圖留作讀者練習。

示例 3

定義以下集合

U = {1, 2, 3, …, 10}

A = {2, 3, 7, 8, 9}

B = {2, 8}

C = {4, 6, 7, 10}

使用下面描述的兩階段技術，繪製一個文氏圖來表示這些集合，並將所有元素標記在相應的區域中。

該技術如下

繪製一個“通用”的 3 集合文氏圖，類似於示例 2中的那個。

一次只處理一個元素，遍歷通用集合中的所有元素，並將每個元素輸入到圖表的相應區域。

如果需要，重新繪製圖表，將迴圈移到彼此內部或彼此分開，以消除任何空區域。

不要先輸入集合A的元素，然後輸入集合B的元素，再輸入集合C的元素，因為你可能會漏掉元素或者重複包含元素！

解決方案

在繪製了三個空迴圈後，繪製一個類似於圖 4的圖表（但沒有羅馬數字！），遍歷U中的十個元素（數字 1 到 10），依次問每個元素三個問題，如下所示

第一個元素：1

你在A中嗎？不

你在B中嗎？不

你在C中嗎？不

對所有三個問題的回答都是“否”，這意味著數字 1 在所有三個迴圈之外。因此，將其寫入相應的區域（圖 4中的區域編號i）。

第二個元素：2

你在A中嗎？是

你在B中嗎？是

你在C中嗎？不

是，是，否：因此數字 2 在A和B內部，但在C外部。然後將其放入區域iii中。

… 等等，元素 3 到 10 也是如此。

生成的圖表看起來像圖 5。

最後一步是檢查圖表中是否有空區域 - 在本例中，我們稱之為圖 4中的iv、vi和vii的區域 - 然後重新繪製圖表以消除這些區域。完成後，我們將清楚地看到三個集合之間的關係。

因此，我們需要

將B和C拉開，因為它們沒有共同的元素。

將B推到A的內部，因為它在A外部沒有元素。

最終結果顯示在圖 6中。

文氏圖和真值表中的區域

也許你已經意識到，向文氏圖新增一個額外的集合會將表示通用集合的矩形劃分成的區域數量翻倍。這給了我們一個非常簡單的模式，如下所示

用一個集合迴圈，將只有兩個區域：迴圈內部和迴圈外部。

用兩個集合迴圈，將有四個區域。

用三個迴圈，將有八個區域。

… 等等。

不難看出為什麼應該是這樣。我們向圖表新增的每個新的迴圈都會將每個現有區域分成兩個，從而使區域總數翻倍。

在A中嗎？	在B中嗎？	在C中嗎？
Y	Y	Y
Y	Y	N
Y	N	Y
Y	N	N
N	Y	Y
N	Y	N
N	N	Y
N	N	N

但還有另一種看待這個問題的方式，那就是：在上面示例 3的解決方案中，我們對每個元素都問了三個問題：你在 A 中嗎？你在 B 中嗎？以及你在 C 中嗎？現在，對每個問題顯然都有兩個可能的答案：是和否。當我們組合三個問題的答案時，一個接一個，那麼總共有 2³ = 8 種可能的答案集。這八種可能的答案組合中的每一種都對應於文氏圖上的不同區域。

完整的答案集與真值表非常相似 - 這是邏輯中的一個重要概念，邏輯處理可能為真或假的陳述。右邊的表格顯示了 3 個集合A、B和C的八種可能的答案組合。

你會發現研究每列中 Y 和 N 的模式很有幫助。

當你向下閱讀C列時，字母在每一行都會改變：Y、N、Y、N、Y、N、Y、N

向下閱讀B列，字母每隔一行就會改變：Y、Y、N、N、Y、Y、N、N

向下閱讀A列，字母每隔四行就會改變：Y、Y、Y、Y、N、N、N、N

集合論練習 2

點選連結檢視集合論練習 2

集合上的運算

正如我們可以將兩個數字組合成第三個數字，使用像“加”、“減”、“乘”和“除”這樣的運算，我們也可以用各種方式將兩個集合組合成第三個集合。我們首先再看一下文氏圖，它顯示了兩個集合A和B的通用位置，我們不知道它們之間有什麼關係。

在A中嗎？	在B中嗎？	區域
Y	Y	iii
Y	N	ii
N	Y	iv
N	N	i

右邊的表格中的前兩列顯示了對兩個集合A和B提出問題你在 A 中嗎？和你在 B 中嗎？的四組可能的答案；第三列中的羅馬數字顯示了圖 7中文氏圖中的相應區域。

交集

區域iii，即兩個迴圈重疊的地方（對應於“是”後跟“是”的區域），稱為集合A和B的交集。它用A ∩ B表示。因此，我們可以將交集定義如下

兩個集合A和B的交集，寫作A ∩ B，是屬於A並且屬於B的元素的集合。

（請注意，在符號邏輯中，一個類似的符號， $\scriptstyle \wedge$ ，用於使用AND運算子連線兩個邏輯命題。）

例如，如果A = {1、2、3、4} 且B = {2、4、6、8}，則A ∩ B = {2、4}。

因此，我們可以說，我們已經使用交集運算將兩個集合組合成第三個集合。

並集

以類似的方式，我們可以將兩個集合的並集定義如下

兩個集合A和B的並集，寫作A ∪ B，是屬於A或屬於B（或兩者都屬於）的元素的集合。

因此，並集由圖 7中的區域ii、iii和iv表示。

（同樣，在邏輯中，一個類似的符號， $\scriptstyle \vee$ ，用於使用OR運算子連線兩個命題。）

因此，例如，{1、2、3、4} ∪ {2、4、6、8} = {1、2、3、4、6、8}。

你會看到，要進入交集，一個元素必須對兩個問題都回答“是”，而要進入並集，任一答案都可以是“是”。

∪ 符號看起來像“Union”的第一個字母，也像一個可以容納很多物品的杯子。∩ 符號看起來像一個溢位的杯子，不能容納很多物品，或者可能像字母“n”，代表“i'n'tersection”。注意不要將兩者混淆。

差集

兩個集合A和B的差集（也稱為A和B的集合論差集，或B在A中的相對補集）是屬於A但不屬於B的元素的集合。

這寫成A - B，或者有時寫成A \ B。

因此，差集中的元素是那些對第一個問題你在 A 中嗎？回答“是”，但對第二個問題你在 B 中嗎？回答“否”的元素。這種答案組合在上面表格的第 2 行，對應於圖 7中的區域ii。

例如，如果A = {1、2、3、4} 且B = {2、4、6、8}，則A - B = {1、3}。

補集

到目前為止，我們已經考慮了兩個集合組合成第三個集合的運算：二元運算。現在我們來看看一個一元運算——它只涉及一個集合。

集合 *A* 中**不包含**的元素的集合被稱為 *A* 的**補集**。它被記作 *A*′（有時也記作 *A*^C 或 ${\bar {A}}$ ）。

顯然，這是一個對問題“你在 *A* 中嗎？”回答“否”的元素的集合。

例如，如果 **U** = **N** 且 *A* = {奇數}，則 *A*′ = {偶數}。

注意單詞 *complement* 的拼寫：它的字面意思是“互補的物品或專案”；換句話說，就是“完成某件事的東西”。因此，如果我們已經擁有了 *A* 的元素，那麼 *A* 的補集就是 *完成* 整個全集的集合。

集合運算的性質

1. 交換律

$A\cup B=B\cup A$

$A\cap B=B\cap A$

2. 結合律

$A\cup (B\cup C)=(A\cup B)\cup C$

$A\cap (B\cap C)=(A\cap B)\cap C$

3. 分配律

$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

4. 補集的特殊性質

$(A')'=A$

$U'=\phi$

$\phi '=U$

$A\cap B'=A-B$

5. 德摩根定律

$(A\cap B)'=A'\cup B'$

$(A\cup B)'=A'\cap B'$ .

總結

交集：既在 A 中又在 B 中的東西	並集：在 A 中或在 B 中（或兩者都在）的東西
差集：在 A 中但不在 B 中的東西	對稱差：在 A 中或在 B 中，但不在兩者中的東西
補集：不在 A 中的東西

基數

最後，在 *集合運算* 這一部分，我們看一下對集合進行操作，它得到的不是另一個集合，而是一個整數。

有限集合 *A* 的 *基數*，記作 | *A* |（有時記作 #( *A* ) 或 *n* ( *A* )），是 *A* 中的元素個數（不重複）。例如

如果A = {字母表的字母}, | A | = 26。

廣義集合運算

如果我們想要表示n個集合的交集或並集，A₁, A₂, ..., A_n（我們可能不知道n的值）那麼以下廣義集合符號可能有用

A₁ ∩ A₂ ∩ ... ∩ A_n =

\scriptstyle \bigcap _{i=1}^{n}

A_i

A₁ ∪ A₂ ∪ ... ∪ A_n =

\scriptstyle \bigcup _{i=1}^{n}

A_i

在符號 $\scriptstyle \bigcap _{i=1}^{n}$ A_i中，i是一個變數，取值從1到n，表示所有集合A₁到A_n的重複交集。

集合論練習3

點選連結檢視集合論練習3

離散數學
← 簡介	集合論	集合論/第 2 頁 →

交集：既在 A 中又在 B 中的東西	並集：在 A 中或在 B 中（或兩者都在）的東西
差集：在 A 中但不在 B 中的東西	對稱差：在 A 中或在 B 中，但不在兩者中的東西
補集：不在 A 中的東西