概念與性質

定義：
X和Y是集合，f是X到Y的二元關系，且有以下性質
1）dom(f) = X
2)對任意x∈X，$y_1$∈Y，$y_2$∈Y，(x,y1)∈f和(x,y2)∈f，那么有y1 = y2
稱f是X到Y的函數或映射，記為f ：X->Y
x關于f有且只有一個后件，稱x在f(x)在f下的一個原像，若X = Y，稱X到X函數是X上的函數

定義：
1）$ran(f)=Y$，稱f是到上的到映上的
圖：至少一個指向它的箭頭
矩陣：每列至多一個1

2）對于任意$x_1,x_2\in X$，$x_1=x_2$ 有 $f(x_1)=f(x_2)$,f是一對一的
圖：至多一個指向它的箭頭
矩陣：每列至少一個1

3）f即使一對一，又是到上的，稱f是一一對應
一對一函數稱為單射，到上的函數稱為滿射，一一對應稱為雙射
圖：有且只有一個箭頭
矩陣：有且僅有一個1

定義：
設X是集合，X上一一對應稱為X上的變換，有限集上的變換又稱為置換

函數的復合與逆

$f:X\to Yg:Y\to Z$那么$f°g$是X到Z的函數

定理： f:X->Y,g:Y->Z
1)f,g到上的，$f°g$也是到上的
2）f,g一對一的，$f°g$也是一對一的
3） f和g都一一對應 $f°g$也是一一對應的

定理：
f:X->Y
1)$f^{?1}$是Y到X的函數當且僅當f是一一對應
2）f是一一對應，$f^{?1}$也是一一對應
3）若f是一一對應，$f°f^{?1}=I_X{f}^{?1}°f=I_Y$

基數

設A和B是集合，存在A到B的一一對應，稱集合A和B等勢，記為A~B
（0，1）~R

性質：
1）自反性：A~A
2）對稱性，A~ B，有B ~A
3）傳遞性： A ~ B， B ~ C， A ~ C

可數集

定義：
A是有限集合或與自然數集等勢，稱A是可數集

定理：
A是可數集當且僅當A所有元素可以逐個排列成一個序列，讓其中每個元素都屬于A，且A中每個元素都在期中某個位置上出現且僅出現一次

定理：
可數個可數集合的并是可數集

無限集和集合的基數

定理：
(0,1)不是可數集

定義：
把互相等勢的集合歸為一類，賦予每一個類一個記號，稱之為該類中集合的基數或勢，A的基數記為|A|，規定有限集基數是他的計數，自然數集合基數記為a，實數集基數記為c

定義：
A和B是集合，存在B的子集B_1, 滿足A~B_1,稱|A|不大于|B|
記為$|A|\le |B|$
在此基礎上|A|≠B，則稱$|A|<|B|$

定理：
任意無限集都含有可數的無限子集

定理：
|A| < |P(A)|

定理：
|A| ≤ |B|且|B| ≤ |A|,有 |A| = |B|

定理：
任意無限集都有和他等勢的真子集

不可解問題

存在問題使得編程語言的程序無法解決

總結

以上是生活随笔為你收集整理的05笔记 离散数学——函数——基于离散数学(第3版)_章炯民,陶增乐的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。