離散數學（集合論）

離散數學（集合論） ... 子集(subset)：設A，B是兩個集合，若A的元素都是B的元素，則稱A是B的子集，也稱B 包含A，或A包含於B記以A \(\subseteq\) B. MdEditor 離散數學（集合論） 語言:CN/TW/HK 時間 2021-06-1719:44:00 部落格園精華區 主題: 離散數學 第一章集合論 集合的基本概念 集合的元素 屬於\(\in\) 空集\(\varnothing\)全集 有限集、無限集 集合的元素數（基數）：特別的：|\(\varnothing\)|=0，|{\(\varnothing\)}|=1 集合的特徵：確定性、互異性、無序性、多樣性 集合相等：兩個集合A和B的元素完全一樣 子集(subset)：設A，B是兩個集合，若A的元素都是B的元素，則稱A是B的子集，也稱B包含A，或A包含於B記以A\(\subseteq\)B 若A\(\subseteq\)B，且A\(\ne\)B，則稱A是B的真子集(propersubset)，也稱B真包含A，或A真包含於B，記以A\(\subset\)B 集合的運算及性質： 並集(Union)： 交集(Intersection)： 差集(Difference)： 餘集(Complement)： 環和（對稱差）： 環積： 集合的算律： 集合的證明題： 集合的冪與笛卡爾積： 冪集的性質： 2. 3. 有序n元組(orderedn-tuple)：(a1,a2,…,an) 有序對(orderedpairs)：當n=2時，將其稱作有序對，也稱作序偶，或有序二元組 有序對特點： 若a\(\ne\)b,則（a，b）\(\ne\)（b，a） 兩個有序對(a,b)和(c,d)相等當且僅當a=c，b=d 笛卡兒積(Cartesianproduct)： 笛卡兒積的性質： |A\(\times\)B|=|A|\(\times\)|B|； 對任意集合A，有A\(\times\)\(\varnothing\)=\(\varnothing\)，\(\varnothing\)\(\times\)A=\(\varnothing\)； 笛卡兒積運算不滿足交換律，即A\(\times\)B\(\ne\)B\(\times\)A； 笛卡兒積運算不滿足結合律，即(A\(\times\)B)\(\times\)C\(\ne\)A\(\times\)(B\(\times\)C) 笛卡兒積運算對並和交運算滿足分配律 設A，B，C，D是集合，若A\(\subseteq\)C且B\(\subseteq\)D，則A\(\times\)B\(\subseteq\)C\(\times\)D。

證明集合的包含關係的常用方法： 利用定義：首先任取x\(\in\)A，再演繹地證出x\(\in\)B成立 設法找到一個集合T,滿足A\(\subseteq\)T且T\(\subseteq\)B,由包含關係的傳遞性有A\(\subseteq\)B. 利用A\(\subseteq\)B的等價定義,即A\(\cup\)B=B,A\(\cap\)B=A或A-B=\(\varnothing\)來證. 利用已知包含式的並、交等運算得到新的包含式 反證法 證明集合相等的常用方法： 若A，B是有限集，證明A=B可通過逐一比較兩集合所有元素均一一對應相等，若A，B是無限集，通過證明集合包含關係的方法證A\(\subseteq\)B，B\(\subseteq\)A即可 反證法 利用集合的基本算律以及已證明的集合等式，通過相等變換將待證明的等式左（右）邊的集合化到右（左）邊的集合，或者兩邊同時相等變換到同一集合 關係 非空集合中的空關係是反自反的、對稱的、反對稱的和傳遞的，但不是自反的； 空集合中的空關係則是自反的、反自反的、對稱的、反對稱的和傳遞的。

關係的定義：xRy 關係的特點： A\(\times\)A的任一子集都是A上的一個關係 若|A|=n，則A上的關係有\(2^{\mathrm{n}^2}\)個 A上有三個特殊關係，即空關係\(\varnothing\)；全域關係EA=A\(\times\)A；相等關係IA={(x,x)|x\(\in\)A} 關係的表示： 集合表示：設A={1,2,3,4}，A上的關係R={(1,1),(1,2),(1,3),(2,1),(2,2)} 關係矩陣 關係圖： 關係作為集合的運算： 關係的交：R∩S={(x,y)|x\(\in\)A,y\(\in\)A,xRy且xSy} 關係的並：R∪S={(x,y)|x\(\in\)A,y\(\in\)A,xRy或xSy} 關係的差：R-S={(x,y)|x\(\in\)A,y\(\in\)A,xRy並且xS/y} 逆關係：R-1={(y,x)|x\(\in\)A,y\(\in\)A,並且有xRy} 關係的乘積：稱關係R•S為關係R和S的乘積或合成 關係的乘法的結論： 關係的乘法不滿足交換律 關係的乘法滿足結合律 關係的冪 定理1.2.1： \(\mathrm{R}^{\mathrm{m}}\cdot\mathrm{R}^{\mathrm{n}}=\mathrm{R}^{\mathrm{m}+\mathrm{n}}\) \(\left(\mathrm{R}^{\mathrm{m}}\right)^{\mathrm{n}}=\mathrm{R}^{\mathrm{mn}}\) 定理1.2.3： 幾種特殊關係及特點： 自反關係： 反自反關係 對稱關係 反對稱關係 傳遞關係定理1.2.4：集合A上的關係R具有傳遞性的充要條件是\(\mathrm{R}^2\subseteq\mathrm{R}\) 常用結論： 集合A上的關係是對稱的，反對稱的，試指明關係R的結構——\(\mathrm{I}_{\mathrm{A}}\)的任意子集 集合A有n個元素，則A上有多少個即具有對稱性又具有反對稱性的關係？\(2^{\mathrm{n}}\)（取對角線元素） 關係的性質總結： 關係的閉包：R的自反閉包、對稱閉包和傳遞閉包分別記為r(R)，s(R)，t(R)，也稱r，s，t為閉包運算，它們作用於關係R後，產生包含R的最小的自反、對稱、傳遞的關係。

![image]()**等價關係**：如果R具有**自反性**，**對稱性**，**傳遞性**，則稱R是一個等價關係 等價類 定理1.2.7： 劃分： 商集：設R是非空集合A上的等價關係，以R的所有不同等價類為元素作成的集合稱為A關於R的商集，簡稱A的商集，記作A/R 等價關係=>商集： 商集=>等價關係： 定理1.2.8：設A為一個非空集合。

(1)設R為A上的任意一個等價關係，則對應R的商集A/R為A的一個劃分。

(2)設C為A的任一個劃分，令\(\mathrm{R}_{\mathrm{c}}\)={(x,y)|x,y\(\in\)A並且x,y屬於C的同一劃分塊}，則\(\mathrm{R}_{\mathrm{c}}\)為A上的等價關係 第二類Stirling數： 將n個不同的球放入r個相同的盒中去，並且要求無空盒，有多少種不同的放法？這裡要求n\(\geqslant\)r。

不同的放球方法數即為將n元集合A分為r塊的不同的劃分數。

（1）特值： （2）遞推公式： 加細：設C和C'都是集合A的劃分，若C的每個劃分塊都包含於C'的某個劃分塊中，則稱C是C'的加細。

C是C'的加細當且僅當\(\mathrm{R}_{\mathrm{c}}\)$\subseteq$$\mathrm{R}_{\mathrm{c'}}$ 綜合例題： 偏序關係： 自反性，反對稱性，傳遞性 偏序集(半序集、部分序集)。

記作(A，R) 寫做“≤” 哈斯圖： 鏈： 對任意x,y\(\in\)A，如果x≤y，或y≤x，稱x與y可比 一個部分序集的子集，其中任意兩個元素都可比，稱該子集為一條鏈 全序集：一個部分序集(A,≤)說是一個全序集，如果(A,≤)本身是一條鏈 擬序關係： 反自反性，反對稱，傳遞性 最大(最小)元極大(極小)元：只從給定集合裡找 上(下)界，上(下)確界：從全體裡找 上(下)確界：找所有上(下)界裡距離所求集合最近的上(下)界。

上下界未必存在，存在時又未必唯一. 即使有上下界時，最小上界和最大下界也未必存在。

映射 對映：設A，B是兩個集合，若對A的每個元素a，規定了B的一個確定元素b與之對應，則稱此對應為由A到B內的一個對映 將此對映記為\(\mathrm{\sigma}\)，於是對任意a\(\in\)A，若\(\mathrm{\sigma}\)(a)=b，則b表示B中與a對應之元素，b稱為a的映像(image)，a稱為b的原像(pre-image) 滿射：設\(\mathrm{\sigma}\)是A到B內的對映，如果B中每一個元素都一定是A中某元素的映像，就稱\(\mathrm{\sigma}\)是A到B上的對映（滿射） 白話：B中所有元素都被箭頭指向。

特別，A到A上的對映，稱為變換 單射：設\(\mathrm{\sigma}\)是A到B內的對映，如果對任意a\(\in\)A，b\(\in\)A且a\(\ne\)b，都有\(\mathrm{\sigma}\)(a)\(\ne\)\(\mathrm{\sigma}\)(b)，就稱\(\mathrm{\sigma}\)是A到B的單射 白話：B中的元素最多隻能有一個箭頭指向。

注意：單射未必滿射；滿射未必單射 1-1對映（雙射）：既滿射，又單射。

逆對映 對映的乘積：\(\mathrm{\sigma}\cdot\mathrm{\tau}=\mathrm{\tau}*\mathrm{\sigma}\)（運算順序相反） 集合的基數：有限集合的元素數(勢，濃度)。

集合A的基數記為|A| 1-1對映，則稱A與B基數相同，也稱A與B對等（等勢，等濃），記為|A|=|B| 把自然數集合的基數記為\(\aleph_0\)（讀作阿列夫零），於是凡是與自然數集合對等的集合A，其基數|A|=\(\aleph_0\) 若A與B的某一子集有1-1對應關係，則|A|\(\leqslant\)|B|；若A與B的某一子集有1-1對應關係，且A與B不存在1-1對應關係，則|A|