【正文】 2A讀作 A的冪集。 冪集 (power set) ⑴ Φ∈ 2A。 ⑵ Φ?2A。 ⑶ Φ?2A。 ⑷ 2Φ={Φ}。 ⑸ A∈ 2A。 ⑹ 如果 A是有窮集 ， 則 |2A|=2|A|。 ⑺ 2A∩B=2A∩2B。 ⑻ 如果 A?B，則 2A?2B。 補集 (plementary set) A是論域 U上的一個集合， A補集 是由 U中的、不在 A中的所有元素組成的集合，記作 AUA ??U????U補集 (plementary set) ??AA ?????? BAUBAAB ?? amp。BABA ?? ?BABA ?? ?AB ?UAA ??如果 A?B，則 。 。 。 。 。 。 關(guān)系 ? 二元關(guān)系 ? 遞歸定義與歸納證明 ? 關(guān)系的閉包 二元關(guān)系 (binary relation) ? 二元關(guān)系 – 任意的 R?A B， R是 A到 B的 二元關(guān)系。 – (a， b) ∈ R，也可表示為： aRb。 – A稱為 定義域 (domain)， B稱為 值域 (range)。 – 當 A=B時，則稱 R是 A上的二元關(guān)系。 ? 二元關(guān)系的性質(zhì) – 自反 (reflexive)性、反自反 (irreflexive)性、對稱(symmetric)性、反對稱 (asymmetric)性、傳遞(transitive)性。 二元關(guān)系 (binary relation) ? 三歧性 –自反性、對稱性、傳遞性。 ? 等價關(guān)系 (equivalence relation) –具有三歧性的二元關(guān)系稱為 等價關(guān)系。 二元關(guān)系 (binary relation) ? 等價類 (equivalence class) S的滿足如下要求的劃分： S S S … 、 Sn… 稱為 S關(guān)于 R的等價劃分， Si稱為等價類。 ⑴ S= S1∪ S2∪ S3∪ … ∪ Sn∪ … ； ⑵ 如果 i≠j， 則 Si∩Sj=Φ； ⑶ 對任意的 i， Si中的任意兩個元素 a、 b， aRb恒成立； ⑷ 對任意的 i， j， i≠j， Si中的任意元素 a和 Sj中的任意元素 b， aRb恒不成立 二元關(guān)系 (binary relation) ? 指數(shù) (index) – 把 R將 S分成的等價類的個數(shù)稱為是 R在 S上的指數(shù) 。如果 R將 S分成有窮多個等價類，則稱 R具有有窮指數(shù)；如果 R將 S分成無窮多個等價類，則稱 R具有無窮指數(shù)。 – 給定集合 S上的一個等價關(guān)系 R， R就確定了 S的一個等價分類，當給定另一個不同的等價關(guān)系時，它會確定 S的一個新的等價分類。 二元關(guān)系 (binary relation) ? 關(guān)系的合成 (position) 設 R1?A B是 A到 B的關(guān)系、 R2?B C是 B到C的關(guān)系， R1與 R2的 合成 R1R2是 A到 C的關(guān)系：R1R2={(a， c)| ?(a， b) ∈ R1且 (b， c) ∈ R2 。 二元關(guān)系 (binary relation) ⑴ R1R2≠R2R1。 ⑵ (R1R2)R3=R1(R2R3)。 (結(jié)合率 ) ⑶ (R1∪ R2)R3=R1R3∪ R2R3。 (右分配率 ) ⑷ R3(R1∪ R2)=R3R1∪ R3R2。 (左分配率 ) ⑸ (R1∩R2)R3?R1R3∩R2R3。 ⑹ R3(R1∩R2)?R3R1∩R3R2。 二元關(guān)系 (binary relation) 1. 關(guān)系這一個概念用來反映對象 ——集合元素之間的聯(lián)系和性質(zhì) 2. 二元關(guān)系則是反映兩個元素之間的關(guān)系 ，包括某個元素的某種屬性 。 3. 對二元關(guān)系的性質(zhì) ， 要強調(diào)全稱量詞是對什么樣的范圍而言的 。 等價關(guān)系與等價類 （略） 關(guān)系的合成 （略） 遞歸定義與歸納證明 ? 遞歸定義 (recursive definition) – 又稱為 歸納定義 (inductive definition)，它來定義一個集合。 – 集合的遞歸定義由三部分組成： ? 基礎(chǔ) (basis)：用來定義該集合的最基本的元素。 ? 歸納 (induction)：指出用集合中的元素來構(gòu)造集合的新元素的規(guī)則。 ? 極小性限定：指出一個對象是所定義集合中的元素的充要條件是它可以通過有限次的使用基礎(chǔ)和歸納條款中所給的規(guī)定構(gòu)造出來。 遞歸定義與歸納證明 ? 歸納證明 – 與遞歸定義相對應。 – 歸納證明方法包括三大步： ? 基礎(chǔ) (basis)：證明最基本元素具有相應性質(zhì)。 ? 歸納 (induction)：證明如果某些元素具有相應性質(zhì)，則根據(jù)這些元素用所規(guī)定的方法得到的新元素也具有相應的性質(zhì)。 ? 根據(jù)歸納法原理，所有的元素具有相應的性質(zhì)。 遞歸定義與歸納證明 ? 定義 117 設 R是 S上的關(guān)系 ， 我們遞歸地定義 Rn的冪： ⑴ R0={(a， a)|a∈ S}。 ⑵ Ri=Ri1R (i=1,2,3,4,5,…) 。 遞歸定義與歸納證明 例 117 著名的斐波那契 (Fibonacci)數(shù)的定義 ⑴ 基礎(chǔ)： 0是第一個斐波那契數(shù) ， 1第二個斐波那契數(shù)； ⑵ 歸納：如果 n是第 i個斐波那契數(shù) ， m是第 i+1個斐波那契數(shù) ， 則 n+m是第 i+2個斐波那契數(shù) ，這里 i為大于等于 1的正整數(shù) 。 ⑶ 只有滿足 (1)和 (2)的數(shù)才是斐波那契數(shù) 0， 1， 1， 2， 3， 5， 8， 13， 21， 34，55， … 遞歸定義與歸納證明 例 118 算術(shù)表達式 ⑴ 基礎(chǔ)：常數(shù)是算術(shù)表達式 ， 變量是算術(shù)表達式； ⑵ 歸納：如果 E E2是表達式 ， 則 +E EE1+E E1E2 、 E1*E2 、 E1/E E1**EFun(E1)是算術(shù)表達式 。 其中 Fun為函數(shù)名 。 ⑶ 只有滿足 (1)和 (2)的才是算術(shù)表達式。 遞歸定義與歸納證明 例 119 對有窮集合 A， 證明 |2A|=2|A|。 證明： 設 A為一個有窮集合 , 施歸納于 |A|： ⑴ 基礎(chǔ)：當 |A|=0時 ,|2A|=|{Φ}|=1。 ⑵ 歸納：假設 |A|=n時結(jié)論成立，這里 n ≥0，往證當 |A|=n+1時結(jié)論成立 2A=2B∪ {C∪ {a}|C∈ 2B} 2B∩{C∪ {a}|C∈ 2B}=Φ 遞歸定義與歸納證明 |2A|=|2B∪ {C∪ {a}|C∈ 2B}| =|2B|+|{C∪ {a}|C∈ 2B}| =|2B|+|2B| =2*|2B| =2*2|B| =2|B|+1 =2|A| ⑶ 由歸納法原理 ， 結(jié)論對任意有窮集合成立 。 遞歸定義與歸納證明 例 120 表達式的前綴形式是指將運算符寫在前面，后跟相應的運算對象。如： +E1的前綴形式為 +E1， E1+E2的前綴形式為 +E1E2 ，E1*E2的前綴形式為 *E1E2， E1**E2的前綴形式為 ** E1， Fun(E1) 的前綴形式為 FunE1 。 證明例 118所定義的表達式可以用這里定義的前綴形式表示。 遞歸定義與歸納證明 ? 遞歸定義給出的概念有利于歸納證明。在計算機科學與技術(shù)學科中，有許多問題可以用遞歸定義描述或者用歸納方法進行證明，而且在許多時候，這樣做會帶來許多方便。 ? 主要是掌握 遞歸定義與歸納證明 的敘述格式。 關(guān)系的