離散數(shù)學(xué)知識點(diǎn)

1、1內(nèi)容及范圍主要來自ppt ，標(biāo)簽對應(yīng)書本2可能有錯，僅供參考離散數(shù)學(xué)知識點(diǎn)說明：定義 ：紅色表示 。定理性質(zhì)： 橙色表示。公式： 藍(lán)色表示 。算法 : 綠色表示頁碼 ：灰色 表示數(shù)理邏輯：1.命題公式： 命題，聯(lián)結(jié)詞 (， ，)，合式公式，子公式2. 公式的真值： 賦值，求值函數(shù)，真值表，等值式，重言式，矛盾式3. 范式： 析取范式，極小項(xiàng)，主析取范式，合取范式，極大項(xiàng)，主合取范式4. 聯(lián)結(jié)詞的完備集： 真值函數(shù)，異或，條件否定，與非，或非，聯(lián)結(jié)詞完備集5.推理理論： 重言蘊(yùn)含式，有效結(jié)論，P 規(guī)則， T 規(guī)則，CP 規(guī)則，推理6. 謂詞與量詞 :謂詞，個體詞，論域，全稱量詞，存在量詞7.

2、項(xiàng)與公式 :項(xiàng)，原子公式，合式公式，自由變元，約束變元，轄域，換名，代入8. 公式語義 :解釋，賦值，有效的，可滿足的，不可滿足的9. 前束范式 :前束范式10. 推理理論 :邏輯蘊(yùn)含式，有效結(jié)論，- 規(guī)則（ US），+ 規(guī)則（ UG ），- 規(guī)則 (ES)，+ 規(guī)則 (EG), 推理集合論：1. 集合: 集合, 外延性原理 , , , , 空集, 全集, 冪集, 文氏圖 , 交, 并, 差, 補(bǔ), 對稱差2.關(guān)系 : 序偶 , 笛卡爾積 , 關(guān)系 , domR, ranR,關(guān)系圖 , 空關(guān)系 , 全域關(guān)系 , 恒等關(guān)系.3. 關(guān)系性質(zhì)與閉包 :自反的 , 反自反的 , 對稱的 , 反對稱的

3、, 傳遞的 ,自反閉包 r(R), 對稱閉包 s(R), 傳遞閉包 t(R)4. 等價關(guān)系 : 等價關(guān)系 , 等價類 , 商集 , 劃分5. 偏序關(guān)系 :偏序 , 哈斯圖 , 全序 (線序 ), 極大元 / 極小元 , 最大元 / 最小元 , 上界 / 下界6. 函數(shù) : 函數(shù) , 常函數(shù) , 恒等函數(shù) , 滿射 ,入射 ,雙射，反函數(shù) , 復(fù)合函數(shù)7. 集合基數(shù) :基數(shù) , 等勢 , 有限集 / 無限集 , 可數(shù)集 , 不可數(shù)集代數(shù)結(jié)構(gòu)：1. 運(yùn)算及其性質(zhì)： 運(yùn)算，封閉的 ,可交換的 ,可結(jié)合的 ,可分配的 ,吸收律 , 冪等的，幺元 ,零元 ,逆元2. 代數(shù)系統(tǒng)： 代數(shù)系統(tǒng)，子代數(shù)，積代數(shù)

4、，同態(tài)，同構(gòu)。3. 群與子群： 半群 ,子半群 ,元素的冪，獨(dú)異點(diǎn)，群，群的階數(shù)，子群 ,平凡子群，陪集，拉格朗日（ Lagrange ）定理4. 阿貝爾群和循環(huán)群： 阿貝爾群 (交換群 )，循環(huán)群 ,生成元5. 環(huán)與域： 環(huán)，交換環(huán)，含幺環(huán)，整環(huán)，域6. 格與布爾代數(shù)： 格，對偶原理，子格，分配格，有界格，有補(bǔ)格，布爾代數(shù)，有限布爾代數(shù)的表示定理圖論：1. 圖的基本概念： 無向圖、有向圖、關(guān)聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補(bǔ)圖，握手定理，圖的同構(gòu)2. 圖的連通性 :通路，回路，簡單通路，簡單回路（跡）初級通路（路徑） ，初級回路（圈），點(diǎn)連通，連通圖，點(diǎn)割集，割點(diǎn)，邊割集，割邊，點(diǎn)連

5、通度，邊連通度，弱連通圖，單向連通圖，強(qiáng)連通圖，二部圖（二分圖）;.3. 圖的矩陣表示： 關(guān)聯(lián)矩陣，鄰接矩陣，可達(dá)矩陣4. 歐拉圖與哈密頓圖： 歐拉通路、歐拉回路、歐拉圖、半歐拉圖，哈密頓通路、哈密頓回路、哈密頓圖、半哈密頓圖5.無向樹與根樹：無向樹，生成樹，最小生成樹，Kruskal ，根樹， m 叉樹，最優(yōu)二叉樹， Huffman算法6. 平面圖 :平面圖，面，歐拉公式， Kuratoski 定理數(shù)理邏輯：命題：具有確定真值的陳述句。否定詞符號：設(shè) p 是一個命題，p 稱為 p 的否定式。p 是真的當(dāng)且僅當(dāng) p 是假的。 p 是真的當(dāng)且僅當(dāng)p 是假的?！径x 1.1 】合取詞符號：設(shè) p

6、， q 是兩個命題，命題“ p 并且 q ”稱為 p， q 的合取，記以pq ，讀作 p且 q 。 p q 是真的當(dāng)且僅當(dāng) p 和 q 都是真的。【定義 1.2】析取詞符號：設(shè) p ， q 是兩個命題，命題“ p 或者 q ”稱為 p， q 的析取，記以pq ，讀作 p或 q 。 p q 是真的當(dāng)且僅當(dāng) p， q 中至少有一個是真的。 【定義 1.3 】蘊(yùn)含詞符號：設(shè) p，q 是兩個命題，命題“如果 p ，則 q ”稱為 p 蘊(yùn)含 q，記以 pq。pq是假的當(dāng)且僅當(dāng)p 是真的而 q 是假的?！径x 1.4 】等價詞符號：設(shè) p ，q 是兩個命題， 命題 “ p 當(dāng)且僅當(dāng) q ”稱為 p 等價

7、q ，記以 pq 。pq是真的當(dāng)且僅當(dāng)p ， q 或者都是真的，或者都是假的?！径x 1.5 】合式公式 :(1) 命題常元和變元符號是合式公式；(2)若 A 是合式公式，則(A) 是合式公式，稱為A 的否定式；;.(3)若 A ， B 是合式公式，則(AB)，(AB)， (AB)， (AB)是合式公式；(4) 所有合式公式都是有限次使用(1) ， (2) ， (3) 、 (4) 得到的符號串。子公式 : 如果是合式公式A 的一部分，且本身也是一個合式公式，則稱為公式A 的子公式?！径x 1.6 】賦值（ 指派，解釋 ）：設(shè)是命題變元集合，則稱函數(shù)v ：1 ， 0 是一個真值賦值。 【定義1.

8、8 】真值表： 公式 A 在其所有可能的賦值下所取真值的表，稱為A 的真值表?！径x1.9 】重言式（ 永真式 ） :任意賦值 v ， vA矛盾式（ 永假式 ） :任意賦值 v ， 有 vA 【定義1.10 】等值式： 若等價式 AB 是重言式，則稱A 與 B 等值，記作AB?！径x 2.1 】基本等值式雙重否定律AA冪等律A AA, AAA交換律A BBA,ABB A結(jié)合律(AB) CA(BC), (AB)CA (BC)分配律A(BC)(AB)(AC),A(BC) (A B)(A C)德摩根律(A B)AB,(AB)AB吸收律A(AB)A, A(AB)A零律A, A同一律AA, AA排中律A

9、A矛盾律AA蘊(yùn)涵等值式ABA B等價等值式AB(AB) (BA)假言易位ABBA等價否定等值式ABAB歸謬論(AB) (AB)A置換規(guī)則： 設(shè)是公式A 的子公式 ,Y。將 A 中的（可以是全部或部分X）用 Y 來置換，所得到的公式B，則 AB。文字:設(shè)A（命題變元集）,則A和A 都稱為命題符號A 的文字，其中前者稱為正文字，后者稱為負(fù)文字。 【定義2.2 】析取范式： 形如 A 1A 2A n (n1)的公式稱為析取范式，其中Ai (i=1,n)是由文字組成;.的合取范式。合取范式： 形為 A1A2An(n 1)的公式稱為合取范式，其中A,A都是由文字組成1n的析取式?！径x2.3 】極小項(xiàng)：

10、 文字的合取式稱為極小項(xiàng)，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次。極大項(xiàng)： 文字的析取式稱為極大項(xiàng)，其中公式中每個命題符號的文字都在該合取式中出現(xiàn)一次?！径x 2.4 】主析取范式：給定的命題公式的主析取范式是一個與之等價的公式，后者由極小項(xiàng)的析取組成。主合取范式：給定的命題公式的主合取范式是一個與之等價的公式，后者由極大項(xiàng)的合取組成?！径x2.5 】公式的真值表中真值為F 的指派所對應(yīng)的極大項(xiàng)的合取，即為此公式的主合取范式。真值函數(shù)：稱 F:0,1n0,1為 n 元真值函數(shù) .【定義2.6 】聯(lián)結(jié)詞的完備集：設(shè) C 是聯(lián)結(jié)詞的集合，若對于任意一個合式公式均存在一個與之等價的公式，

11、而后者只含有C 中的聯(lián)結(jié)詞，則稱C 是聯(lián)結(jié)詞的完備集。 【定義2.7 】， ， ， ， , ， ， ， 是聯(lián)結(jié)詞的完備集。 【定理2.6】異或 Pc(PQ)Q ：條件否定 PQ ：(PQ)與非 PQ ：(PQ)或非 PQ ：(PQ) 【定義2.8 】 , 都是聯(lián)結(jié)詞的完備集【定理 2.7】重言蘊(yùn)含式： 當(dāng)且僅當(dāng) PQ 是一個重言式時，稱P 重言蘊(yùn)含 Q，記為 P Q。有效結(jié)論： 設(shè) A 、 C 是兩個命題公式，若AC ，稱 C 是 A 的有效結(jié)論。 【定義3.1 】推理定律重言蘊(yùn)涵式1.A(AB)附加律2.(AB)A化簡律3.(AB)AB假言推理;.4.(AB)BA拒取式5.(AB)BA析取三

12、段論6.(AB)(BC)(AC)假言三段論7.(AB)(BC)(AC)等價三段論8.(AB)(CD)(A C)(BD)構(gòu)造性二難(A B)(A B)B構(gòu)造性二難 ( 特殊形式 )9.(AB)(CD)(BD)(AC)破壞性二難形式系統(tǒng) :一個形式系統(tǒng)I由下面四個部分組成：(1) 非空的字母表，記作 A (I).(2) A(I) 中符號構(gòu)造的合式公式集，記作E(I).(3) E(I) 中一些特殊的公式組成的公理集，記作A X(I).(4) 推理規(guī)則集，記作 R(I ).記 I=< A (I),E(I),A X(I),R(I)>,其中 < A(I),E(I)> 是 I 的形式

13、語言系統(tǒng), < A X(I),R(I)>是I 的形式演算系統(tǒng) .自然推理系統(tǒng): 無公理 , 即 A X(I)=公理推理系統(tǒng) : 推出的結(jié)論是系統(tǒng)中的重言式, 稱作定理 【定義 3.2 】P 規(guī)則： 在推導(dǎo)過程中 ,可以隨時添加前提。T 規(guī)則： 在推導(dǎo)過程中 ,可以引入公式S，它是由其前題的一個或多個公式借助重言、蘊(yùn)含而得到的。推理（ 證明 ）：從前提A1 ,A2 , k到結(jié)論B的推理是一個公式序列1 ,C2,Cl. 其中i(1il)ACC是某個 A j, 或者可由序列中前面的公式應(yīng)用推理規(guī)則得到, 并且 Cl = B?！径x3.3 】CP 規(guī)則 ( 演繹定理 )：若R|- S ，則

14、|-R S, 其中為命題公式的集合。個體詞： 用于表示命題中主語部分的符號或符號串。個體常元表示確指個體。個體變元表示不確指個體。個體域 : 個體變元的取值范圍，常用D 表示。;.量詞： 限定個體數(shù)量特性的詞。全稱量詞：對所有的存在量詞：有些謂詞語言 ：用符號串表示個體、謂詞、量詞和命題個體變元符號：x， y ， z， 個體常元符號：a， b ， c ， 函數(shù)符號： f， g ， 謂詞符號： P， Q ， R， 命題常元符號：，量詞符號：，連接詞符號：,輔助符號：）, （【定義4.1】項(xiàng): (1) 個體常元和變元是項(xiàng)；(2)若 f 是 n 元函數(shù)符號，t1, 項(xiàng)是,tn，則f(t1, tn)是

15、項(xiàng)；(3)僅僅有限次使用(1) ， (2) 產(chǎn)生的符號串是項(xiàng)。【定義 4.2 】原子公式 : 若 P 是一個元謂詞符號，t1, 是 項(xiàng) ,tn則 P(t1,tn)是原子公【式定。義 4.3 】合式公式：(1)原子公式是公式；(2) 若 A 是合式公式，則 ( A) 是合式公式；(3)若 A，B 是公式，則 (A B)，(A B)，AB)，(AB)是公式；(4)若 A 是公式， x 是變元，則xA ， xA是公式；(5)僅僅有限次使用得到的符號串才是合式公式?！径x4.4 】設(shè)公式的一個子公式為x A 或x A 。則稱：;.指導(dǎo)變元： x 是或的指導(dǎo)變元。轄域： A 是相應(yīng)量詞的轄域。約束出現(xiàn)：

16、 轄域中 x 的一切出現(xiàn)，以及(x) 中的 x 稱為 x 在中的約束出現(xiàn)。自由出現(xiàn)： 變元的非約束出現(xiàn)。約束變元： 約束出現(xiàn)的變元。自由變元： 自由出現(xiàn)的變元?！径x4.5 】封閉的： 一個公式A 是封閉的，若其中不含自由變元?！径x4.6 】變元換名：（ 1） 換名的范圍是量詞的指導(dǎo)變元, 及其相應(yīng)轄域中的變元，其余部分不變。（ 2） 換名時最好選用轄域中未出現(xiàn)的變元名。變元代入： 代入對自由變元進(jìn)行。不能改變約束關(guān)系。解釋：謂詞語言的一個解釋I= (D,) 包括：(1) 非空集合 D ，稱之為論域；(2) 對應(yīng)于每一個個體常元a， (a) D ；(3)對應(yīng)于每一個n 元函數(shù)符號f 都有一個

17、函數(shù)(f):DnD ；(4)對應(yīng)于每一個n 元謂詞符號A 都有一個n 元關(guān)系(A)Dn ?！径x4.7 】賦值： 解釋 I 中的賦值v 為每一個個體變元x 指定一個值v(x）D ，即設(shè)V 為所個體變元的集合，則賦值v 是函數(shù)v:VD.可滿足的： 給定公式A ，若在某一解釋中至少有一種賦值使A 取值為1，則稱A 為可滿足的。否則稱 A 是不可滿足的。等值式 AB：若 AB 是有效的 【定義 5.1 】幾類等值式（ 1）命題公式的推廣e.g. P(x)Q(x)P(x)Q(x)（ 2）否定深入x P(x)x(P(x)xP(x)x (P(x)（ 3）量詞作用域的擴(kuò)張與收縮;.設(shè) B 中不含 x 的自由

18、出現(xiàn)，則x(A(x)B)x A(x)Bx(A(x)B)x A(x)Bx(A(x)B)x A(x)Bx(BA(x)Bx A(x)x(A(x)B)x A(x)Bx(A(x)B)x A(x)Bx(A(x)B)x A(x)Bx(BA(x)Bx A(x)（ 4）量詞分配等值式x(A(x)B(x)x A(x)x B(x)x(A(x)B(x)x A(x)x B(x)（ 5）多個量詞的使用xy A(x,y)yx A(x,y)xy A(x,y)yx A(x,y)置換規(guī)則： 設(shè) (A) 是含 A 的公式 ,那么 ,若 AB,則 (A)(B).換名規(guī)則： 設(shè) A 為一公式， 將 A 中某量詞轄域中個體變項(xiàng)的所有約束

19、出現(xiàn)及相應(yīng)的指導(dǎo)變元換成該量詞轄域中未曾出現(xiàn)過的個體變項(xiàng)符號，其余部分不變，設(shè)所得公式為A，則 AA.前束范式：如果謂詞公式A 有如下形狀： Qx Q xM ，其中 Q xi或者是x，或者是x，i=1 ， ，11n niiin ， M 是不含量詞的公式，Q 1 x1 Qn xn 稱為首標(biāo)， M 稱為母式?！径x5.2 】前束范式存在定理：對于任意謂詞公式，都存在與它邏輯等價的前束范式?！径ɡ?5.1 】前束范式的算法：步 1. 對約束出現(xiàn)的變元進(jìn)行必要的換名，使得約束出現(xiàn)的變元互不相同且不與任何自由變元同名。步 2. 將所有的否定號 深入到量詞后面。步 3. 將量詞符號移至公式最外層。邏輯蘊(yùn)含

20、式AC：當(dāng)且僅當(dāng)AC 是有效的。幾類邏輯蘊(yùn)涵式第一組命題邏輯推理定理的代換實(shí)例如 ,xF(x)yG(y)xF(x)第二組基本等值式生成的推理定理如 ,xF(x)xF(x),xF(x)xF(x)xF(x)xF(x),xF(x)xF(x)第三組其它常用推理定律(1)xA(x)xB(x)x(A(x)B(x)(2)x(A(x)B(x)xA(x)xB(x)(3)x(A(x)B(x)xA(x)xB(x)(4)x(A(x)B(x)xA(x)xB(x)推理規(guī)則;.-規(guī)則 (US) ：或x,y 個體變項(xiàng)， c 個體常項(xiàng)+規(guī)則 (UG) ：x 個體變項(xiàng)-規(guī)則 (ES) ：x 個體變項(xiàng) , c個體常項(xiàng)+ 規(guī)則 (E

21、G) ：或x,y 個體變項(xiàng)， c 個體常項(xiàng)或先用 ES，再用US自然推理系統(tǒng)N：L1. 字母表 . 同一階語言 L 的字母表2. 合式公式 . 同 L 的合式公式3. 推理規(guī)則 :(1) 前提引入規(guī)則(2) 結(jié)論引入規(guī)則(3) 置換規(guī)則(4) 假言推理規(guī)則(5) 附加規(guī)則(6) 化簡規(guī)則(7) 拒取式(8) 假言三段論規(guī)則(9) 析取三段論規(guī)則(10) 構(gòu)造性二難推理規(guī)則;.(11) 合取引入規(guī)則(12) - 規(guī)則(13) + 規(guī)則(14) - 規(guī)則(15) + 規(guī)則 【定義 5.3 】集合論：ABx ( xAxB)【定義 6.1 】A = BAB BA 【定義 6.2 】A BA B A B

22、【定義6.3】A ?Bx ( xAxB )空集：不含有任何元素的集合【定義 6.4 】空集是任何集合的子集?！径ɡ?.1 】冪集 P(A)= x | xA【定義6.5 】如果 |A|=n，則 |P(A)|=2n全集 E：包含了所有元素的集合【定義 6.6 】并 AB= x | xAxB交 AB= x | xAxB差（相對補(bǔ)）A B= x | xAxB【定義6.7 】對稱差 AB= (AB) (BA)【定義6.8 】補(bǔ)（絕對補(bǔ)） A= EA = x|xA 【定義6.9 】廣義并A= x |z ( zAxz ) 【定義6.10 】廣義交A= x |z ( zAxz ) 【定義 6.11 】集合恒等

23、式;.1. 只涉及一個運(yùn)算的算律：交換AB=BAAB=BAAB=B A結(jié)合(AB)C=A (BC)(AB)C=A (B C)(AB) C=A (B C)冪等AA=AAA=A2涉及兩個不同運(yùn)算的算律：與與分配A(BC)=(AB)(AC)A(B C)=(A B)(AC)A(BC)=(AB)(AC)吸收A(AB)=AA(AB)=A3涉及補(bǔ)運(yùn)算的算律：D.M律A (BC)=(AB)(AC)(BC)= BCA (BC)=(AB)(AC)(BC)= BC雙重否定A=A4涉及全集和空集的算律：E補(bǔ)元律AA=AA=E零律A=AE=E同一律A=AAE=A否定=EE=序偶（有序?qū)Γ河蓛蓚€元素x 和 y ，按照一

24、定的順序組成的二元組，記作 <x,y>. 【定義 7.1 】笛卡兒積 :設(shè) A,B 為集合， A 與 B 的笛卡兒積記作AB 定義為 AB = <x,y>| xAyB.【定義 7.2】笛卡爾積性質(zhì)：A=或 B=時,AB=“”不滿足結(jié)合律A (BC)=(AB)(A C)關(guān)系：（兩個定義）(1) 序偶的一個集合, 確定了一個二元關(guān)系R。R 中任一序偶<x,y>, 可記作<x, y>R 或;.xRy 【定義7.3 】(2) 笛卡爾積的子集：RA B【定義 7.4 】空關(guān)系 :全域關(guān)系： A ×B恒等關(guān)系I A = <x,x>| x

25、 A【定義7.5 】關(guān)系矩陣： 若 A = x1, x2 , xm ，B= y1 , y2 , yn， R 是從 A 到 B 的關(guān)系， R 的關(guān)系矩陣是布爾矩陣 MR= rmn,其中 r= 1< x , y>R.ijijij關(guān)系圖： 若 A = x, x , xm， R 是從 A 上的關(guān)系， R 的關(guān)系圖是 GR=< A , R>,其中 A 為結(jié)點(diǎn)12集，R為邊集 .如果 < xi,xj> 屬于關(guān)系 R，在圖中就有一條從xi到 xj 的有向邊 .前域 ( 定義域 ) dom(R)= x|y.<x,y>R值域 ran(R)=y|x.<x,y&

26、gt;R域 fld(R)= domRranR【定義 7.6】逆關(guān)系 R1= <y, x> | <x, y>R 【定義7.7 】互逆(R1)1 = R(RS)1 = R1S1(RS)1 = R1S1(AB)1= BA(R-S)1 = R1 - S1復(fù)合關(guān)系R S = <x, z> |y (<x, y>R<y, z>S) 【定義7.8 】(RS)P=R (SP)Rm = RRR設(shè) RXY,SYZ,則 (RS)1= S1R1 【定理7.2 】R 在 A 上的 限制 R?A = <x,y> | xRy x A A 在 R 下的 像

27、 R A =ran(R?A)【定義7.9 】自反的： 若x A，都有 <x,x>R,則稱 R是自反的反自反的： 若x A，都有 <x,x>R, 則稱R 是反自反的 .【定義 7.11 】;.對稱的： 對任意 x,y A, 滿足 ,若 <x,y>R,則 <y,x>R反對稱的： 對任意 x,yA, 滿足，若 <x,y>R 且 <y,x>R,則 x=y 【定義 7.12 】傳遞的： 對任意的 x,y,zA,滿足 :若 <x,y>R 且 <y,z>R, 則 <x,z>R,則稱 R 是傳遞的 【定

28、義7.13 】自反閉包（對稱、傳遞）：設(shè) R 是 A 上的二元關(guān)系,如果有另一個關(guān)系R'滿足 : R'是自反（對稱、傳遞）的 ; R' R; 對于任何自反的關(guān)系R” , 若R" R, 則有 R"R'.則稱關(guān)系 R' 為 R 的自反閉包 . 記為 r(R) （ 對稱閉包s(R) 和傳遞閉包t(R) ）?！径x 7.14 】設(shè) R為A上的關(guān)系 , 則有(1)r(R)=RI A(2)s(R)=RR 1(3)t(R)=RR 2R3 （若 | A|= n， 則 t(R)=R R2 Rn ）等價關(guān)系：設(shè) R 為集合A 上的一個二元關(guān)系。若R 是自

29、反的 , 對稱的 , 傳遞的 ,則稱R 為A上的等價關(guān)系【定義 7.15 】等價類：設(shè) R 為集合A 上的等價關(guān)系, 對aA, 定義 :a R = x|xA且 <a,x>R稱之為元素a 關(guān)于 R 的等價類?！径x 7.16 】給定 A 上的等價關(guān)系R, 對于 a,bA 有 <a,b> 當(dāng)且僅當(dāng) aR=bR【定理17.4 】商集： 設(shè) R 是 A 上的等價關(guān)系，定義A/R=aR |aA 稱之為 A 關(guān)于 R 的商集 .【定義7.17 】劃分： 設(shè) A 為非空集合 , 若 A 的子集族 (P(A) 滿足 :(1)(2)xy(x,yxyxy=)(3) = A則稱 是 A 的一

30、個劃分 , 稱 中的元素為A 的劃分塊 .【定義 7.18 】;.給定集合 A 上的等價關(guān)系 R, 則商集 A/R是 A的一個劃分 .集合 A 的一個劃分 誘導(dǎo)出 A 上的一個等價關(guān)系R. R 定義為 R= <x,y>| x,yA 且 x,y 在 的同一分塊中 設(shè) R 和 R 為非空集合 A 上的一個等價關(guān)系, 則 R1= R2當(dāng)且僅當(dāng) A/R= A/R2.121偏序 ：設(shè) A 是一個集合 . 如果 A上的二元關(guān)系R 是自反的 ,反對稱的和傳遞的,則稱R是A上的一個偏序關(guān)系. 記R為“ ” ,且稱序偶 <A,> 為偏序集 ?！径x 7.19】【定義 7.22 】全序（線

31、序）：設(shè) <A,> 為偏序集 ,若對任 意的 x,yA 滿足 : x y 或 y x則稱為全序關(guān)系 .<A,> 為全序集 .【定義7.21 】覆蓋： 設(shè) <A, > 為偏序集 ,若 x,y A,x y,xy 且沒有其它元素 z 滿足 x z,zy,則稱 y 覆蓋 x. 記covA= <x,y> |x,yA 且 y 覆蓋 x【定義7.23 】哈斯圖： 作圖規(guī)則 用小元圈代表元素 ;若 x y 且 x y,則將代表y 的小元圈畫在代表x 的小元圈之上;若<x,y>covA,則在 x,y 之間用直線連接。你極小元 / 極大元： 設(shè) <

32、A,> 為偏序集 , BA(1) 對 b B，若 B 中不存在 x 滿足 : b x 且 x b 則稱 b 為 B 的極小元 .(2)對 bB，若 B 中不存在x 滿足 : bx 且 bx 則稱 b 為 B 的極大元 .最小元 / 最大元： 設(shè) <A,> 為偏序集 ,BA, 若有某個bB(1) 對于 B 中每一個元素 x 都有 b x ，則稱 b 為 B 的最小元 .(2) 對于 B 中每一個元素 x 都有 x b ，則稱 b 為 B 的最大元 .【定義 7.24 】下界 / 上界： 設(shè)<A,> 為偏序集 , BA(1) 若有 aA, 且對xB 滿足a x，則稱a

33、 為 B 的下界 。進(jìn)一步 : 設(shè) a 為 B 的下界 ,若 B 的所有下界y 均有 y a,則稱 a 為 B 的下確界，記為glb B 。;.(2) 若有 aA, 且對xB 滿足x a，則稱a 為 B 的上界 。進(jìn)一步 : 設(shè) a 為 B 的上界 ,若 B 的所有上界y 均有 a y,則稱 a 為 B 的上確界，記為 lubB。【定義 7.25 】函數(shù)： 設(shè) X,Y為兩個集合,fX Y, 若對xX, !( 唯一的 )yY,滿足 : <x,y>f,則稱f 為函數(shù) .記為:f:X Y定義域 : domf=X值域 : ranf (有時記為 f(X)=f(x)|xX【定義8.1 】函數(shù)相

34、等：設(shè) f 和 g 都是從 A 到 B 的函數(shù) ,若對任意 x A, 有 f(x)=g(x),則稱 f 和 g相等 .記為 f=g【定義 8.2 】函數(shù)的個數(shù)：設(shè)f:AB,|A|=m, |B|=n.記 B A=f|f: AB, 則 | B A |= nm滿射 ( 到上映射 ) ：設(shè) f: XY, 若 ranf = Y,則稱 f為滿射的 .入射（單射） ( 一對一映射 ) ：設(shè) f: XY, 對x 1 , x2X, 滿足 :若 x1x 2 ,則 f(x 1 )f(x 2 ), 稱 f為入射的 .雙射 (一一對應(yīng)映射 )：設(shè) f:X Y, 若 f 既是滿射的 ,又是入射的 . 則稱 f 是雙射的

35、.【定義8.6 】常函數(shù) :設(shè) f:A B,如果存在 c B使得對所有的x A 都有 f(x)=c,則稱 f:AB是常函數(shù) .恒等函數(shù) :稱 A上的恒等關(guān)系IA 為 A 上的恒等函數(shù) ,對所有的 x A 都有 IA (x)=x.單調(diào)遞增 :設(shè) <A,? >,<B, ? > 為偏序集，f:A B，如果對任意的1,2 A,1 ?x2, 就有(1 )?xxxf xf (x2 ), 則稱f 為單調(diào)遞增的；嚴(yán)格單調(diào)遞增:如果對任意的x1 , x2 A, x1 ? x2 , 就有 f (x1 ) ? f (x2 ), 則稱f 為嚴(yán)格單調(diào)遞增的.類似的也可以定義單調(diào)遞減 和嚴(yán)格單調(diào)遞

36、減的函數(shù)特征函數(shù)：設(shè)A為集合 , 對于任意的A'A,A' 的特征函數(shù)A':A 0,1定義為A '(a)=1,a A'A '(a)=0, a AA'自然映射： 設(shè) R 是 A 上的等價關(guān)系, 令 g:A A/R ；g(a)=a,a A 稱 g是從A 到商集A/R;.的自然映射【定義 8.7 】復(fù)合函數(shù)： 設(shè) f:XY,g:YZ, 定義 : fg = <x,z>|xX 且 zZ 且可找到y(tǒng)Y 使 y=f(x),z=g(y)稱 fg 為 f 與 g的復(fù)合函數(shù) .設(shè) f:A B, g:B C(1)如果 f:A B, g:B C 是滿射

37、的 ,則 fg:AC 也是滿射的(2)如果 f:A B, g:B C 是單射的 ,則 fg:AC 也是單射的(3)如果 f:A B, g:B C 是雙射的 ,則 fg:AC 也是雙射的【定理 8.2】反函數(shù) （逆函數(shù)）：設(shè) f:X Y 是一個雙射函數(shù)，那么f -1 是 YX 的雙射函數(shù). 稱 f -1 為 f 的反函數(shù).互逆 (f-1 ) -1 =f設(shè) f : A B是雙射的 ,則f1 f基數(shù)： 用來衡量集合大小的一個概念= I ,f f1=IA【定理 8.5 】B.對于有限集合集來說, 集合的基數(shù)就是其中所含元素的個數(shù).等勢的：設(shè) A, B 是集合 , 如果存在著從A 到 B 的雙射函數(shù) , 就稱 A 和 B 是等勢的 , 記作 A B. 如果 A 不與 B 等勢 , 則記作A? B.注：通常將A 的基數(shù)記為|A|. 【定義8.8 】NZ Q N×N任何實(shí)數(shù)區(qū)間都與實(shí)數(shù)集合R 等勢0,1N R康托定理(1) N?R；(2) 對任意集合 A 都有 A? P(A). 【定義 8.7 】有限集 (有窮集 ) / 無限集(無窮集 ) ：設(shè) A 為一個集合 . 若存在某個自