Ⅰ 離散數學 第二章 集合
一個 集合 是一些對象的整體
序列 和集合的不同之處是要考慮次序數字系統包括眾所周知的十進制，二進制等等
關系 是序偶的集合
函數 是關系的一個特例
一個集合是一些對象的整體
可以用枚舉法描述它:A={1,2,3,4}
也可以列出其元素的性質來描述:B={x│x是正偶數}
如果X是一個有限集合，令| X |=X中元素的個數，
沒有元素的集合稱為空集(或零集)用符號∅表示,∅={}，
兩個集合X和Y有相同的元素,說兩個集合相等，記為X=Y。
子集
設 X 和 Y 是集合。如果X的所有元素都是Y的元素，我們說X是Y的子集,寫為X⊆Y。
真子集
如X是Y的子集但X不等於Y,則X是Y的一個真子集。記為：X⊊Y
空集是任何集合的子集。
集合X的所有子集的集合,稱為X的冪集，用P(×)表示。
並集、交集、差集
並集XUY={x|x∈X or y ∈Y}
交集X∩Y= {x|x∈X and y∈ Y}
差集X-Y= {x|x∈X or x ∉ Y}
不相交 X∩Y=∅；
U：全集 X：子集
則U-X為X的補集
一個由集合X的非空子集的整體組成的S，如X的每個元素都只屬於S的某一個元素，S就稱為X的一個劃分。
笛卡爾積
—個由兩個元素組成的有序對(或序偶)，寫為(a,b)
(a,b)=(c,d)當且僅當a=c,b=d. X,Y集合，X×Y稱為X和Y的笛卡兒積
一個序列(或有序組)是一個表,要計及其元素出現的次序。
如果s是一個序列，一般的，s.表示序列的第n項。我們把n稱為序列的下標。
序列3,5,5,7,8,8,13是增序列。對於所有的n, S n >S n+1 ,則稱S n 為增序列。
對於n=m,m+1,..,令{S n }是一個序列，且令n1，n2,...是一個增序列，值在{m,m+1,..}中,滿足n k <n k+1 ，稱序列{S nk }是{S n }的一個子序列
X 集合
X* X上所有串的集合
α串,| α |串的長度。
如果α和β是兩個串，由α後面跟著β所組成的串α β ,稱為α和β的連接。
①比特bit ②二進制系統,16進制系統,8進制系統 ③系統的基數
這個就不多闡述了，計組中已經學過了！
關系可以想成一張表，其中列出了一些元素和其他元素之間的關系。
X到Y的關系R,是笛卡兒積X*Y的一個子集。如果(x, y)∈R，我們寫為xRy且說x和y有關。當X=Y，我們稱R是X上的(二元)關系。
定義 ：
令S是集合X的一個劃分。 定義xRy:
對於S的某些集合干,x和y都屬於T。則R是自反，對稱和傳遞的。
X上的一個自反的，對稱的和傳遞的關系稱為X上的一個等價關系。
令R是集合×上的一個等價關系。對於每個a∈X，
令[a]={x∈X]xRa};則s={[a]la∈X}是X的一個劃分。
令R是集合x上的一個等價關系集合[a]，稱為由關系R確定的x的等價類。
令R表示一個有限集合x上的等價關系。如每個等價類有r個元素,則共有|X|/r個等價類。
一個表示從X到Y的關系的方法是使用矩陣。如果xRy，則×行y列的元素之值為1,否則，其值為0。這即是關系矩陣。
定理
R₁的關系(X到Y)矩陣A₁，R₂的關系(到Z)矩陣A₂。
R₁○R₂的關系矩陣:
在矩陣的積A₁A₂中，把非0項用1代替而得的矩陣。
函數是特殊的關系。
R的定義域=
{x∈X│|存在y ∈ Y,(×,y) ∈R}f 關系，f函數，f的定義域=X，且.(x,y')在f 中，y=y'。
Ⅱ 離散數學中fg(x)等不等於gf(x)
不同的教材關於合成函數f•g記法中的次序與關系可能不一樣（可能剛好相反）為了迎合函數習慣，近自變元的函數先發生作用，作如下定義：
設f:X→Y和g:Y→Z是函數, 它們組成一個合成函數h=f•g: X→Z。即h= f•g={(x,z)| x∈X, z∈Z 且至少存在一個y∈Y，使y=f(x),z=g(y)}，那麼對一切x∈X, (f•g)(x)=g(f(x)).
Ⅲ 簡單的離散數學問題
1. S上的有序對有<1,1>,<1,2>，<2,1>,<2,2> 4個
偏序關系需要滿足自反，反對稱，傳遞
即<1,1>,<2,2>都屬於偏序集，<1,2>,<2,1>不能同時屬於偏序集
所以一共有2^2-1=3個偏序關系
因為S上有序對有4個，所以二元關系有2^4=16個
2 4個元素集合的滿射，即是4個元素集合的雙射個數
顯然雙射有4！=24個
3 x中有3個元素，設等價關系為R
等價關系是自反，對稱，傳遞
所以對任意的a∈X,<a,a>都屬於這個等價關系R
對稱需要滿足對於任意的a,b ,若<a,b>屬於R,則<b,a>屬於R
傳遞需要滿足對於任意的a,b,c 若<a,b>,<b,c>屬於R, 則<a,c>屬於R
只需要計算R中出現不同的a,b <a,b>∈R一共有幾種可能
1）一個<a,b>屬於R都沒有，這樣的等價關系只有一種為恆等關系Ix
2)有一個<a,b>屬於R，則根據對稱<b，a>也屬於R
這樣的<a,b>一共有C(3,2)=3個
3）有2個不同的有序對<a,b><a,c>,因為對稱和傳遞性可知，<b,a>,<c,a><b,c><c,b>都屬於R,這樣的等價關系也只有一種，即X上的全關系Ex
所以一共有5種